70
$\begingroup$

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.

$\endgroup$

7 Answers 7

84
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ 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? $\endgroup$
    – Bach
    Commented Feb 14, 2016 at 14:33
  • $\begingroup$ @Bach: Right; this does not show that 1 is a simple eigenvalue. $\endgroup$ Commented Mar 10, 2016 at 22:56
  • $\begingroup$ Can the vector $x$ be complex? I think the argument still largely works for complex vectors, but requires minor adjustments. $\endgroup$
    – Sinusx
    Commented Apr 23, 2022 at 10:41
  • $\begingroup$ This is (essentially) a proof of the Gershgorin circle theorem in disguise, I think. $\endgroup$
    – awllower
    Commented May 5, 2023 at 0:49
  • $\begingroup$ Very nice! If you apply the same reasoning to $A^2 x = \lambda^2 x$, you can conclude that $\lambda \geq -1$ as well. (One can use the elementary fact that the rows of $A^2$ still sum to 1, or just use the above estimate twice.) And this is the best inequality possible, since permutation matrices can have eigenvalue $-1$. $\endgroup$
    – Dan Ramras
    Commented Jun 6, 2023 at 19:45
38
$\begingroup$

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

$\endgroup$
13
$\begingroup$

For $A$ left stochastic, 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.

For a right stochastic matrix, $x$ should be multiplied on the left: $\|xA\|_1\leq\|x\|_1$, where $x$ is a row-vector.

$\endgroup$
1
  • $\begingroup$ Why $a_{11} |x_1|+a_{21}|x_1|=|x_1|$? $A$ has a row sum of $1$, but not a column sum of $1$. $\endgroup$
    – Sam Wong
    Commented Jul 18, 2023 at 10:47
7
$\begingroup$

It is an elementary exercise to show 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, $1 \in \sigma(A)$ whenever $A$ is stochastic.

Now, if $(\lambda,v)$ is an eigenpair of $A$, in which $A$ is stochastic, then, without loss of generality, it may be assumed 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$.

$\endgroup$
4
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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

$\endgroup$
1
$\begingroup$

Here's a very elegant proof that utilizes the Perron–Frobenius theorem: let $y$ be the left Perron vector normalized so that $y^\top e = 1$. By the PFT, $y^\top A = \rho(A) y^\top$ since $A^\top \ge 0$. Because $Ae = e$, we have $$1 = y^\top e = y^\top (Ae) = (y^\top A) e = (\rho(A) y^\top) e = \rho(A) (y^\top e) = \rho(A)\cdot 1 = \rho(A).$$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .