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

Question

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.

Answer 1

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