# Proving or disproving product of two stochastic matrices is stochastic

Let $P$ and $Q$ be two stochastic matrices. Does the product $PQ$ have to be stochastic? Prove or disprove.

What Im thinking is that since matrix multiplication is only defined for two matrices $A$ and $B$ where $A$ has the same amount of columns as $B$ has rows and vice versa. Therefore the product of any two stochastic matrices $P$ and $Q$ can not be stochastic. This is not much of a proof though.

Note that 'stochastic' can have three meanings: the matrix $A$ might be row stochastic, so $\sum_{i=1}^nA_{ji}=1$ for each row $j\in\{1,\ldots,n\}$, column stochastic, so $\sum_{i=1}^nA_{ij}=1$ for each column $j\in\{1,\ldots,n\}$, or both, and in that case the matrix is called doubly stochastic. I show a way to prove that the product of two row stochastic matrices is again row stochastic, and I leave the proof for column stochastic matrices to you. Obviously if a matrix is doubly stochastic, it follows from the first two cases that the product is again doubly stochastic.

Now suppose that we have two row stochastic matrices $A$ and $B$, so for each row $j\in\{1,\ldots,n\}$ we have $\sum_{i=1}^nA_{ji}=1=\sum_{i=1}^nB_{ji}$. Now consider the sum of the elements on row $j\in\{1,\ldots,n\}$ of the product of the two matrices, $AB$. We find $$\sum_{i=1}^n(AB)_{ji}=\sum_{i=1}^n\left(\sum_{k=1}^nA_{jk}B_{ki}\right)=\sum_{k=1}^n\left(A_{jk}\left(\sum_{i=1}^nB_{ki}\right)\right)=\sum_{k=1}^nA_{jk}\cdot1=1.$$ You can swap the order of the summation because the sum is finite and because each $A_{jk}$ does not depend on $i$. You can also see this by rewriting the summation as $\sum_{i=1}^n\langle A_{j},B_i\rangle=\langle A_j,(1,\ldots,1)^T\rangle=1$, with $A_j^T$ the $j$'th row of $A$, and $B_i$ the $i$'th column of $B$, and using the linearity of the inner product. Thus the product is indeed row stochastic.

Note that troughout I assumed that a stochastic matrix is square, which is true by definition.

Note that it simplifies a lot if you recognize that a matrix being row stochastic is equivalent to $Ae=e$, with $e:=(1,\ldots,1)^T\in\mathbb{R}^{n\times1}$.

• So this assumes we have two $nxn$ matrices? Where does the $k$ come from? Also, what about the case where you're multiplying a row stochastic matrix and a column stochastic matrix?
– Pame
May 9, 2018 at 10:42
• Stochastic matrices are by definition sqaure matrices, and the product is defined only if they are both $n\times n$, indeed. See the definition of matrix multiplication, $(AB)_{ij}:=\sum_{k=1}^nA_{ik}B_{kj}$, so $k$ is just the summation variable. The notation, of course, is arbitrary. The product of a row stochastic matrix and a column stochastic matrix is, in general, neither row nor column stochastic. Consider $\begin{bmatrix}0.8&0.2\\0.6&0.4 \end{bmatrix}\cdot\begin{bmatrix}0.7&0.9\\0.3&0.1 \end{bmatrix}$. May 9, 2018 at 10:47
• I think what I don't understand is how you get $$\sum_{i=1}^n(AB)_{ji}=\sum_{i=1}^n\sum_{k=1}^nA_{jk}B_{ki}$$.
– Pame
May 9, 2018 at 11:07
• Given $j$ and $i$, $(AB)_{ji}=\sum_{k=1}^nA_{jk}B_{ki}$, this is true by definition of matrix multiplication. We have outer summation because we sum over all elements on row $j$. May 9, 2018 at 11:09
• Because it seems you still find it difficult, I made an edit to include more brackets. I hope it is clearer for you now what is going on. May 10, 2018 at 8:59

This answer is a bit late, but I did want to point t out that you can easily get the result for row-stochastic matrices from column-stochastic matrices (and vice versa).

Let A and B be two row-stochastic matrices and suppose we know the product of column stochastic matrices is column-stochastic. Observe that, $$AB = ((AB)^T)^T = (B^TA^T)^T$$ by properties of transpose of a matrix. Let us consider $$B^TA^T$$. It is easy to see that the transpose of a row-stochastic matrix is column-stochastic by definition (and vice versa). Thus, $$B^T$$ and $$A^T$$ are column stochastic and by our assumption, it must then be the case that $$B^TA^T$$ is column-stochastic. Since $$B^TA^T$$ is column-stochastic, then it's transpose $$(B^TA^T)^T = AB$$ is row stochastic.