# Proving product of two column stochastic matrices is column stochastic (Proof verification)

For a matrix to be column stochastic we know $\sum_{i=1}^nA_{ij}=1$ for each column $j\in\{1,\ldots,n\}$. We have $$\sum_{j=1}^n (AB)_{ji} = \sum_{j=1}^n \sum_{k=1}^n A_{jk}B_{ki} = \sum_{j=1}^nA_{jk} \sum_{k=1}^nB_{ki} = 1*1 = 1$$

It works, but a simpler proof may be $$e^TAB = e^TB = e^T$$

• It would help me understand this if I knew what $e$ is. Can you answer? Cheers! Commented May 9, 2018 at 18:33
• $e$ is the vector of all one's. I prefer $\vec{1}$ myself, but to each their own. :-) Commented May 9, 2018 at 18:39
• I think your proof is correct, but I also think the demonstration given by Pame in the post is erroneous. See my soon-to-be-forthcoming answer. Commented May 9, 2018 at 18:42
• I know $Ae = e$ for a row stochastic matrix, but I don't see why you get $e^tA = e^t$ for the column stochastic case?
– Pame
Commented May 10, 2018 at 7:40
• @Pame It's exactly the same: $A$ is column-stochastic if and only if $A^T$ is row-stochastic, so $A^Te=e$ and if you transpose everything you get $e^TA=e^T$ Commented May 10, 2018 at 8:30

The assertion is true but the demonstration has an error. You can't validly bring $A_{jk}$ out of a sum over the index $k$, since $A_{jk}$ is in general not a constant with respect to that index $k$. Indeed, the expression

$\displaystyle \sum_{j = 1}^n A_{jk} \sum_{k = 1}^n B_{ki} \tag 1$

is possessed of two free indices, $i$ and $k$, since in fact $k$ occurs as a dummy index in the sum $\sum_{k = 1}^n B_{ki}$; we could just as well have written

$\displaystyle \sum_{\alpha = 1}^n B_{\alpha i} \tag 2$

or

$\displaystyle \sum_{j = 1}^n A_{jk} \sum_{\alpha = 1}^n B_{\alpha i} \tag 3$

and obtained the same result. Note that $k$ is a free index in (1) and (3), but not in

$\displaystyle \sum_{j = 1}^n \sum_{k = 1}^n A_{jk} B_{ki}; \tag 4$

the general rule is that the ranges of variables specified in a summation symbol such as

$\displaystyle \sum_{\alpha = 1}^n \tag 5$

apply only on expressions to its right, but on to those on its left; thus, (1) and (4) are generally not the same:

$\displaystyle \sum_{j = 1}^n A_{jk} \sum_{k = 1}^n B_{k i} \ne \sum_{j = 1}^n \sum_{k = 1}^n A_{jk} B_{ki}. \tag 6$

So much for generalities around matrix multiplication; we note that nothing we have said so far invokes the column stochasticity of either $A$ or $B$.

We may, however, quite easily see the column stochasticity of $AB$ if, instead trying to pull $A_{jk}$ out from under the $\sum_{k = 1}^n$ sign, we simply reverse the order of the summations over $j$ and $k$, a permissible operation since it in no wise disturbs the set of quantities actually added together; that is, we write

$\displaystyle \sum_{j = 1}^n (AB)_{ji} = \sum_{j = 1}^n (\sum_{k = 1}^n A_{jk} B_{ki}) = \sum_{j = 1}^n \sum_{k = 1}^n A_{jk} B_{ki} = \sum_{k = 1}^n \sum_{j = 1}^n A_{jk} B_{ki}$ $= \displaystyle \sum_{k = 1}^n (\sum_{j = 1}^n A_{jk}) B_{ki} = \sum_{k = 1}^n (1) B_{ki} = \sum_{k = 1}^n B_{ki} = 1, \tag 7$

which shows the column stochasticity of $AB$ as per request.

Of course, this whole spiel may be presented much more elegantly and compactly if we realize that for any column stochastic matrix $A$ and vector $b$ the product $Ab$ is column stochastic (indeed this has been demonstrated in the above for each columnn of $B$), which facts as pointed out by Exodd in his/her answer may be expressed as

$\mathbf 1^T b = 1, \tag 8$

and

$\mathbf 1^T(Ab) = 1, \tag 9$

where $\mathbf 1$ is the column vector comprised entirely of $1$s:

$(\mathbf 1)_i = 1, \; 1 \le i \le n; \tag{10}$

then it is easy to see that $\mathbf 1^T$ is fixed upon right multiplication by $A$:

$\mathbf 1^T A = \mathbf 1^T, \tag{11}$

so that (9) follows from (8) by a simple application of the associative law for matrix multiplication:

$\mathbf 1^T(Ab) = (\mathbf 1^TA)b = \mathbf 1^T b = 1. \tag{12}$

We then see that $AB$ is column stochastic by a simple column-by-column application of $A$ to $B$; the details are easy and I leave them to the reader.

• My idea was that we can swap the order of summation because the sum is finite and because each $B_{ki}$ does not depend on $j$. See the answer here: math.stackexchange.com/questions/2773442/…
– Pame
Commented May 10, 2018 at 7:44
• @Pame you can swap the sums, but you can't separate them. Try to use parenthesis to get a clear look on what's happening and you will discover that what you have is $\sum(\cdot \sum \cdot)$, but what you did was $(\sum \cdot)(\sum \cdot)$ Commented May 10, 2018 at 8:35
• You should read this answer carefully @Pame. The main point is that you cannot take a variable depending on $k$ out of the summation over $k$. I did not do this in my linked answer and you should be really careful when you want to switch the order of summation. Note that working with all-ones vectors $e=(1,1,\ldots,1)$ makes the problem a lot easier, like you can see in the linked answer and the other answer here. But imo it's important to be comfortable with these kind of summations too Commented May 10, 2018 at 8:40