A Simple Proof that the Largest Eigenvalue of a Stochastic Matrix is 1

A stochastic matrix is a square matrix whose entries are non-negative and whose rows all sum to 1.  The transition matrix for a finite-state Markov chain is a stochastic matrix, and so they are essential for tackling problems that can be modeled as Markov chains.

One of the many interesting properties of a stochastic matrix is that its largest eigenvalue is 1.  I believe this can be proved using the Perron-Frobenius theorem.  However, I found a simple, self-contained proof, thanks in part to an answer to a different question of mine on math.SE.

Theorem: The largest eigenvalue of a stochastic matrix is 1.

Proof: First, if A is a stochastic matrix, then A11, since each row of A sums to 1.  This proves that 1 is an eigenvalue of A.  Second, suppose there exists λ > 1 and nonzero x such that A= λx.  Let xi be a largest element of x.  Since any scalar multiple of x will also satisfy this equation we can assume, without loss of generality, that xi > 0.  Since the rows of A are nonnegative and sum to 1, each entry in λx is a convex combination of the elements of x.  Thus no entry in λx can be larger than xi.  But since λ > 1, λxi > xi.  Contradiction.  Therefore, the largest eigenvalue of A is 1.

Advertisements
This entry was posted in linear algebra, matrices, probability. Bookmark the permalink.

11 Responses to A Simple Proof that the Largest Eigenvalue of a Stochastic Matrix is 1

  1. Samrat Mukhopadhyay says:

    What if \lambda \in \mathbb{C} and \lambda\ge 1?

  2. mzspivey says:

    Good question. If \lambda \in \mathbb{C} and |\lambda| > 1, the proof still goes through, replacing “largest element” with “element with largest modulus” and applying the triangle inequality in one place. Each entry in \lambda {\bf x} is still a convex combination of elements of x, as that claim has to do with the real entries in A. Thus the modulus of each entry in \lambda {\bf x} is, by the triangle inequality, no larger than the convex combination of the moduli of the entries in x. Thus none of the moduli of the entries in \lambda {\bf x} can be larger than |x_i|. But we also have |\lambda x_i| > |x_i| for \lambda > 1, by properties of complex numbers. Contradiction.

  3. shi says:

    I can not understand why, because actually, every entry of in λx is(assume a 3*3 markov matrix A) x1*A11+x2*A21+x3*A31, but what we have is A11+A12+A13 = 1(every row).

  4. Rob Kusner says:

    Is there a good way to decide how many eigenvalues have modulus < 1?

  5. Alex says:

    hey i dont get the point : Thus no entry in λx can be larger than x_i
    but why not?
    Can you explain, please 🙂

    • mzspivey says:

      A convex combination is a weighted average. If you take a weighted average of a set of numbers (where the weights are nonnegative and sum to 1), then that weighted average can’t be larger than the largest number in the set. For example, suppose you have the numbers 1, 3, 6, and 10. There’s no way you can take a weighted average of those four numbers and get something larger than 10.

  6. chundi says:

    This is for right stochastic matrix, can u give proof for left stochastic matrix also ?

  7. raphael says:

    You need that $x_i>0$…

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s