5
$\begingroup$

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

$\endgroup$

2 Answers 2

7
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ It would help me understand this if I knew what $e$ is. Can you answer? Cheers! $\endgroup$ Commented May 9, 2018 at 18:33
  • 4
    $\begingroup$ $e$ is the vector of all one's. I prefer $\vec{1}$ myself, but to each their own. :-) $\endgroup$
    – Jason
    Commented May 9, 2018 at 18:39
  • $\begingroup$ 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. $\endgroup$ Commented May 9, 2018 at 18:42
  • $\begingroup$ 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? $\endgroup$
    – Pame
    Commented May 10, 2018 at 7:40
  • 2
    $\begingroup$ @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$ $\endgroup$
    – Exodd
    Commented May 10, 2018 at 8:30
6
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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/… $\endgroup$
    – Pame
    Commented May 10, 2018 at 7:44
  • 1
    $\begingroup$ @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)$ $\endgroup$
    – Exodd
    Commented May 10, 2018 at 8:35
  • $\begingroup$ 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 $\endgroup$ Commented May 10, 2018 at 8:40

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .