Jtdylktuy

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 $jin{1,ldots,n}$, column stochastic, so $sum_{i=1}^nA_{ij}=1$ for each column $jin{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 $jin{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 $jin{1,ldots,n}$ of the product of the two matrices, $AB$. We find
$$sum_{i=1}^n(AB)_{ji}=sum_{i=1}^nleft(sum_{k=1}^nA_{jk}B_{ki}right)=sum_{k=1}^nleft(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}^nlangle A_{j},B_irangle=langle A_j,(1,ldots,1)^Trangle=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)^Tinmathbb{R}^{ntimes1}$.

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.