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

Question

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 $$

Answer 1

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

Answer 2

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.