1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ Nov 28, 2018 at 5:33

1 Answer 1

1
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

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