Proof that the largest eigenvalue of a stochastic matrix is 1

The largest eigenvalue of a stochastic matrix (i.e. a matrix whose entries are positive and whose rows add up to 1) is 1.

Wikipedia marks this as a special case of the Perron-Frobenius theorem... but I wonder if there is a simpler (more direct) way to demonstrate this result?

-

Here's a really elementary proof (which is a slight modification of Fanfan's answer to a question of mine). As Calle shows, it is easy to see that the eigenvalue $1$ is obtained. Now, suppose $Ax = \lambda x$ for some $\lambda > 1$. Since the rows of $A$ are nonnegative and sum to $1$, each element of vector $Ax$ is a convex combination of the components of $x$, which can be no greater than $x_{max}$, the largest component of $x$. On the other hand, at least one element of $\lambda x$ is greater than $x_{max}$, which proves that $\lambda > 1$ is impossible.

-
Thank you, simple and self-contained, that is what I had in mind! –  koletenbert May 24 '11 at 6:59

Say $A$ is a $n \times n$ row stochastic matrix. Now: $$A \begin{pmatrix} 1 \\ 1 \\ \vdots \\ 1 \end{pmatrix} = \begin{pmatrix} \sum_{i=1}^n a_{1i} \\ \sum_{i=1}^n a_{2i} \\ \vdots \\ \sum_{i=1}^n a_{ni} \end{pmatrix} = \begin{pmatrix} 1 \\ 1 \\ \vdots \\ 1 \end{pmatrix}$$ Thus the eigenvalue 1 is attained.

To show that the this is the largest eigenvalue you can use the Gershgorin circle theorem. Take row $k$ in $A$. The diagonal element will be $a_{kk}$ and the radius will be $\sum_{i\neq k} |a_{ki}| = \sum_{i \neq k} a_{ki}$ since all $a_{ki} \geq 0$. This will be circle with it's center in $a_{kk}$, somewhere in $[0,1]$, and a radius of $1-a_{kk}$. So this circle will have 1 on its perimeter. This of course is true for all Gershgorin circles for this matrix. Thus, since all eigenvalues lie in the union of the Gershgorin circles, all eigenvalues $\lambda_i$ satisfy $|\lambda_i| \leq 1$.

-

Sure, here is an elementary proof: http://planetmath.org/encyclopedia/EigenvaluesOfStochasticMatrix.html

-
Actually the proof there seems to assume (unnecessarily) that the matrix is doubly stochastic. –  Robert Israel May 20 '11 at 17:53
@Robert: I don't see where the proof assumes the matrix is doubly stochastic –  user17762 May 20 '11 at 18:43
@Sivram this is where it says "Now, for a (doubly) stochastic matrix". Without this assumption $\|A\|_1$ won't be bounded by $1$, I don't see how this proof can be rescued. –  yasmar May 20 '11 at 19:27
Yes you are right, if you don't require the colums to add up to 1 or want a proof of existence there is probably no way around Perron-Frobenius. –  Listing May 20 '11 at 20:12
@yasmar, @Listing: But isn't it circumvented by looking at the $\infty$ norm. For some reason I thought $1$ norm, as opposed to the $\infty$ norm, was the maximum of the absolute value of the row sum. –  user17762 May 20 '11 at 22:22