\documentclass[a4paper]{article}
\usepackage{fullpage}
\pagestyle{empty}
\begin{document}
\title{Markov Matrix Multiplication}
\author{Brian Abram - Math 210 Fall 2001}
\date{November 16, 2001}
\maketitle
Indeed, it is the case that the product of any two Markov matrices yields a Markov matrix.  Let us first start with a simple case of a $2 \times 2$ matrix.

\begin{eqnarray*}
\left[ \begin{array}{ccc}
a & b \\
c & d \\
\end{array} \right]
\left[ \begin{array}{ccc}
e & f \\
g & h \\
\end{array} \right]
=
\left[ \begin{array}{ccc}
ae + bg & af + bh \\
ce + dg & cf + dh \\
\end{array} \right]
\end{eqnarray*}

Now we just have to show that the columns of this product equal one, knowing that $(a + c) = (b + d) = (e + g) = (f + h) = 1$.

\begin{eqnarray*}
ae + bg + ce + dg &=& ae + ce + bg + dg \\
&=& e(a + c) + g(b + d) \\
&=& (e + g) \\
&=& 1 \\
\\
af + bh + cf + dh &=& af + cf + bh + dh \\
&=& f(a + c) + h(b + d) \\
&=& (f + h) \\
&=& 1 \\
\end{eqnarray*}

Let us now formalize this for any Markov matrices.  Let $A$ and $B$ be $n \times n$ Markov matrices, and let $AB$ be the product of $A$ and $B$.

\begin{eqnarray*}
AB &=& \left[ \begin{array}{ccc}
a_{1,1} & \ldots & a_{1,n} \\
\ldots & \ldots & \ldots \\
a_{n,1} & \ldots & a_{n,n} \\
\end{array} \right]
\left[
\begin{array}{ccc}
b_{1,1} & \ldots & b_{1,n} \\
\ldots & \ldots & \ldots \\
b_{n,1} & \ldots & b_{n,n} \\
\end{array}
\right] \\
&=& \left[ \begin{array}{ccc}
a_{1,1}b_{1,1} + \ldots + a_{1,n}b_{n,1} & \ldots & a_{1,1}b_{1,n} + \ldots + a_{1,n}b_{n,n} \\
\ldots & \ldots & \ldots \\
a_{n,1}b_{1,1} + \ldots + a_{n,n}b_{n,1} & \ldots & a_{n,1}b_{1,n} + \ldots + a_{n,n}b_{n,n} \\
\end{array} \right] \\
\end{eqnarray*}

Adding up the columns in the matrix, we can see that these all add up to one.  In any column $i$, we know from before that $(a_{1,i} + \ldots + a_{n,i}) = (b_{1,i} + \ldots + b_{n,i}) = 1$.  Therefore:

\begin{eqnarray*}
a_{i,1}b_{1,i} + \ldots + a_{i,n}b_{n,i} + \ldots + a_{n,1}b_{1,i} + \ldots + a_{n,n}b_{n,i} \\
a_{i,1}b_{1,i} + \ldots + a_{n,1}b_{1,i} + \ldots + a_{i,n}b_{n,i} + \ldots + a_{n,n}b_{n,i} \\
(a_{1,i} + \ldots + a_{n,i})b_{1,i} + \ldots + (a_{1,i} + \ldots + a_{n,i})b_{n,i} \\
b_{1,i} + \ldots + b_{n,i} = 1 \\
\end{eqnarray*}

\end{document}


