Why isn't every eigenvalue of a stochastic matrix equal to 1?

Question

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!

Answer 1

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

Answer 2

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.