8
$\begingroup$

In this question, we see a proof that the largest eigenvalue of a stochastic matrix is equal to 1:

Proof that the largest eigenvalue of a stochastic matrix is 1

However, I think I've found a proof that every eigenvalue of a stochastic matrix is equal to 1. Can you tell me where my proof is wrong?

Proof: Suppose ${\bf r}$ is an eigenvector of the column stochastic matrix $M$ (i.e. $M{\bf r} = \lambda {\bf r}$ for some $\lambda$), and assume without loss of generality that the entries of ${\bf r}$ sum to $1$. Then $$M{\bf r} = \begin{bmatrix} M_{11}\\ M_{21}\\ \vdots\\ M_{n1} \end{bmatrix} r_1 + \begin{bmatrix} M_{12}\\ M_{22}\\ \vdots\\ M_{n2} \end{bmatrix} r_2 + \dots + \begin{bmatrix} M_{1n}\\ M_{2n}\\ \vdots\\ M_{nn} \end{bmatrix} r_n$$

Since $M$ is column stochastic, each column must sum to $1$, so the sum of the entries in $M {\bf r}$ is just $1 \cdot r_1 + 1 \cdot r_2 + \dots + 1 \cdot r_n = 1$. Therefore, $\lambda$ must be $1$, and $M$ can only have one eigenvalue.

Thanks!

$\endgroup$
0
5
$\begingroup$

I think that you are assuming that the entries of $r$ are non-negative; in general, you cannot assume that the entries of $r$ add to 1, because they might add to zero. Take $$ M=\begin{bmatrix}1/2&1/2\\1/2&1/2\end{bmatrix}. $$ Eigenvalues are $1$ and $0$. The eigenvector for $0$ is $\begin{bmatrix}1\\-1\end{bmatrix}$.

$\endgroup$
1
  • $\begingroup$ Ah, I see. Thanks! $\endgroup$ – Jessica Nov 9 '16 at 18:19
3
$\begingroup$

The problem is when you assume WLOG that the entries of $\bf{r}$ sum to one. Consider what happens when entries of $\bf r$ sum to zero.

What your proof shows is that if $(\lambda,\bf{r})$ is an eigenpair, and $\lambda\neq 1$, then the entries of $\bf r$ sum to zero. For example, the matrix $$ \begin{bmatrix} 0&1\\1&0 \end{bmatrix} $$ is stochastic, with eigenvalues $\pm1$. The eigenspace for $+1$ is spanned by $(1/2,1/2)$, and for $-1$ is spanned by $(1/2,-1/2)$, where the latter's entries sum to zero.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.