1

Let say I have set of real valued square matrices $\left(A_0, A_1, A_2, ..., A_n \right)$. All these matrices have constraint such that all row-sum of individual matrices equal to 1.

My question the row-sum of a matrix which is computed by multiplication of any subset of above set of matrices will remain to be 1? If yes, is there any matrix rule that govern this?

Brian Smith
  • 147
  • 1
    Use induction on $n$. – geetha290krm Nov 09 '22 at 08:02
  • 2
    Denote by $\mathbf 1$ the column vector of ones. That all row sums of a matrix $A$ are equal to $1$ means precisely that $A\mathbf 1=\mathbf1$. Now, if $A\mathbf 1=\mathbf1$ and $B\mathbf 1=\mathbf1$, then $AB\mathbf 1=A(B\mathbf1)=A\mathbf1=\mathbf1$ and hence all row sums of $AB$ are equal to $1$. This argument generalises to a product of $n$ matrices. – user1551 Nov 09 '22 at 12:04
  • @user1551 such an elegant proof. Thanks you! – Brian Smith Nov 09 '22 at 15:19

1 Answers1

1

The matrices you are referring to are row-stochastic. You can prove that the sum of each row will remain equal to one in many different ways. I will show it based on convex optimization arguments. Notice that you just need to show that the product of two of such matrices is one, since if it holds for 2 matrices, it also holds for $n$ matrices.

Consider then $A=X_1$ and $X_2$. Pick one row of $A$, let's name it $\alpha$. Then:

$$ \alpha^\top X= \alpha_1 x_1^\top + \ldots + \alpha_n x_n^\top$$

where $x_i^\top$ represents the $i$th row of matrix $X$. Since $\sum_{i=1}^n \alpha_i =1 $ what you are actually doing is a convex combination of vectors $x_i^\top$ which have sum-entries equal to one. As a result, the vector $\alpha^\top X$ has also a row-sum equal to one.

This is easy to show for instance if the number of row vectors in $X$ is $n=2$, because you would have:

$$\alpha_1 x_1^\top + (1-\alpha_1) x_2^\top$$ and if you sum the entries of this vector you obtain (assume each $x_n$ has $m$ entries): $$\sum_{l=1}^m \alpha_1 x_1(m) + (1-\alpha_1) x_2(m)= \alpha_1 \sum_{l=1}^m x_1(m) + (1-\alpha_1) \sum_{l=1}^mx_2(m)= \alpha+ 1 - \alpha=1$$

yes
  • 878