54
$\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$
66
$\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$
2
  • $\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
    Feb 14 '16 at 14:33
  • $\begingroup$ @Bach: Right; this does not show that 1 is a simple eigenvalue. $\endgroup$ Mar 10 '16 at 22:56
30
$\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$
7
$\begingroup$

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.

$\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$
2
$\begingroup$

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

$\endgroup$
2
$\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. 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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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