Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
add comment

3 Answers

up vote 11 down vote accepted

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.

share|improve this answer
    
Thank you, simple and self-contained, that is what I had in mind! –  koletenbert May 24 '11 at 6:59
add comment

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

share|improve this answer
add comment

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

share|improve this answer
2  
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
show 1 more comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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