# A left stochastic matrix implies the solution to AX=X is non-trivial.

Theorem:

Let $$A \in \mathbb{R}^{n \times n}$$ whose (each) column sums to one. Then, $$A \vec{X} = \vec{X}$$ has non-trivial solution.

Proof:

By definition, A is a left stochastic matrix.

Observe:

$$A\vec{X}=\vec{X}$$ is a transformation under an identify map.

$$\Rightarrow \vec{X} = A^{-1}\vec{X}$$

But recall that for any matrix $$A \in \mathbb{n \times n}$$: $$A$$ is invertible so the inverse of $$A, A^{-1}$$ exists.

By the uniqueness theorem, any solution $$\vec{X}$$ to $$A\vec{X}=\vec{b}$$ is unique. Clearly, for $$\vec{b} = \vec{0}$$, $$A\vec{X}=\vec{0}$$ can be satisfied by $$\vec{X} = \vec{0}$$ and only $$\vec{X} = \vec{0}$$.

Since, $$A$$ is not the zero matrix and $$\vec{X} \neq \vec{0}$$, $$\vec{X} = A^{-1}\vec{X}$$ is not the zero vector.

Indeed, no trivial solution exists.

Am I going around in circles in my above attempt?

Any help is greatly appreciated.

• Take $X = [1,1,1,...,1]$, to see that $A^TX = X$ has a solution. Now, what is the relationship between the eigenvalues of $A$ and $A^T$? Also, why should $A^{-1}$ exist? The determinant has to be non-zero, but this is not clear from the condition given. Nov 28, 2018 at 5:33

Be careful: the inverse of $$A$$ need not exist. For instance, $$\left(\begin{matrix}0.4 & 0.4\\0.6&0.6\\ \end{matrix}\right)$$ is a stochastic matrix but it is non-invertible.
What you can see is that since for any stochastic matrix $$A$$ the columns add up to $$1$$, then the columns of $$A-I=A-1I$$ add up to $$0$$, that is the sum of the rows gives the null vector. This means $$A-1I$$ is non invertible, so $$1$$ is an eigenvalue of $$A$$. By definition there exists a vector $$x\neq 0$$ such that $$Ax=1x$$, that is, a non-trivial solution to $$Ax=x$$.