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 *A***1** = **1**, 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 **= λ**x**. Let *x*_{i} 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 *x*_{i} > 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 *x*_{i}. But since λ > 1, λ*x*_{i} > *x*_{i}. Contradiction. Therefore, the largest eigenvalue of *A* is 1.

What if and ?

Good question. If and , the proof still goes through, replacing “largest element” with “element with largest modulus” and applying the triangle inequality in one place. Each entry in is still a convex combination of elements of

x, as that claim has to do with the real entries inA. Thus the modulus of each entry in is, by the triangle inequality, no larger than the convex combination of the moduli of the entries inx. Thus none of the moduli of the entries in can be larger than . But we also have for , by properties of complex numbers. Contradiction.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).

Your example is left-multiplying

Aby a row vectorx. In my argument I’m right-multiplyingAby a column vectorx.Is there a good way to decide how many eigenvalues have modulus < 1?

Not that I know of.

hey i dont get the point : Thus no entry in λx can be larger than x_i

but why not?

Can you explain, please 🙂

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.

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

The eigenvalues of the transpose of a matrix are the same, so the proof holds for a left stochastic matrix too.

You need that $x_i>0$…

That’s true. It looks like I need to edit my proof. Nice catch!