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.

• Unlike Perron-Frobenius, however, this does not show that $\lambda=1$ is a simple eigenvalue (that is, having a 1-dimensional eigenspace) in case the matrix in question is irreducible. Right?
– Bach
Feb 14 '16 at 14:33
• @Bach: Right; this does not show that 1 is a simple eigenvalue. Mar 10 '16 at 22:56

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 a circle with its center in $$a_{kk} \in [0,1]$$, and a radius of $$\sum_{i \neq k} a_{ki} = 1-a_{kk}$$. So this circle will have $$1$$ on its perimeter. This is true for all Gershgorin circles for this matrix (since $$k$$ was taken arbitrarily). Thus, since all eigenvalues lie in the union of the Gershgorin circles, all eigenvalues $$\lambda_i$$ satisfy $$|\lambda_i| \leq 1$$.

If we can show that $A$ doesn't increase the 1-norm, i.e., $$\|Ax\|_1\leq\|x\|_1$$ Then $$\|Ax\|_1=\|\lambda x\|_1=|\lambda|\|x\|_1\leq\|x\|_1$$ which is $|\lambda|\leq 1$, we are done, but how to show above inequality? For convenience, let's set stochastic matrix $$A=\begin{pmatrix}a_{11}& a_{12}\\a_{21}& a_{22}\end{pmatrix}$$ Then \begin{eqnarray*}\|Ax\|_1&=&|a_{11}x_1+a_{12}x_2|+|a_{21}x_1+a_{22}x_2|\\&\leq& a_{11}|x_1|+a_{12}|x_2|+a_{21}|x_1|+a_{22}|x_2|\\&=&|x_1|+|x_2|\\&=&\|x\|_1\end{eqnarray*} For n-dimensional matrix, it can be shown in same manner.

Call A a $$n \times n$$ stochastic matrix and denote with $$(\lambda,\textbf{x})$$ one of its eigenpair.

Obviously $$1$$ is an eigenvalue for $$A$$, indeed follow directly from the definition of row-stochastic [column-stochastic] matrix that $$\textbf e$$ $$=(1\dots1)^{T}$$ is a right [left] eigenvector associated with $$1$$.

Using induced matrix norm $$\parallel\parallel_{1}$$ or $$\parallel\parallel_{\infty}$$ , it's easy to prove that the spectral radius $$\rho(A)\leq 1$$ :

$$|\lambda|= \frac{||A x||}{||x||} \leq max_{||x||=1} ||Ax||= ||A||$$ Now, since $$||A||_{1}$$ [respectively $$||A||_{\infty}$$ ] is the maximum absolute column [row] sum of the matrix, we have

$$||A||_{1}=1$$ if $$A$$ is a column-stochastic matrix and

$$||A||_{\infty}=1$$ if $$A$$ is a row-stochastic matrix,

and then in any case $$|\lambda|\leq 1$$.

It is an elementary exercise that a matrix $$A \in \textsf{M}_n (\mathbb{C})$$ has row sums equal to one if and only if $$Ae = e$$ (here, $$e$$ denotes the all-ones column vector of size $$n$$). Thus, if $$A$$ is stochastic, then $$1 \in \sigma(A)$$.

Now, let $$(\lambda,v)$$ be an eigenpair of $$A$$, in which $$A$$ is stochastic. Without loss of generality, we may assume that

$$\vert \vert v \vert \vert_\infty := \max_{1 \le k \le n} \{ \vert v_k \vert \} = 1.$$

Thus, there is a positive integer $$i$$, $$1 \le i \le n$$, such that $$\vert v_i \vert = 1$$. Since $$Av = \lambda v$$, by the mechanics of matrix multiplication and the above, we have

$$\vert \lambda \vert = \vert \lambda \vert\cdot 1 = \vert \lambda \vert \cdot \vert v_i \vert = \vert \lambda v_i \vert = \left\vert \sum_{j=1}^n a_{ij} v_j \right \vert \le \sum_{j=1}^n a_{ij} \vert v_j \vert \le \sum_{j=1}^n a_{ij} = 1,$$ i.e., $$\vert \lambda \vert \le 1$$.

If $$A \in \textsf{M}_n (\mathbb{C})$$, then $$\begin{Vmatrix} A \end{Vmatrix}_\infty := \max\limits_{1\le i \le n} \sum_{j=1}^n \vert a_{ij} \vert$$ is a matrix norm. Furthermore, $$\rho(A) \le \begin{Vmatrix} A \end{Vmatrix}$$ for any matrix norm $$\vert \vert \cdot \vert\vert$$ (e.g., Theorem 5.6.9 in the first-edition of Horn and Johnson's Matrix Analysis). If $$A$$ is stochastic, then $$\begin{Vmatrix} A \end{Vmatrix}_\infty = 1$$ so that $$\vert \lambda \vert \le \rho(A) \le 1$$.