Eigenvalues of a Stochastic Matrix is Always Less than or Equal to 1

Problem 185

Let $A=(a_{ij})$ be an $n \times n$ matrix.
We say that $A=(a_{ij})$ is a right stochastic matrix if each entry $a_{ij}$ is nonnegative and the sum of the entries of each row is $1$. That is, we have
$a_{ij}\geq 0 \quad \text{ and } \quad a_{i1}+a_{i2}+\cdots+a_{in}=1$ for $1 \leq i, j \leq n$.

Let $A=(a_{ij})$ be an $n\times n$ right stochastic matrix. Then show the following statements.

(a)The stochastic matrix $A$ has an eigenvalue $1$.

(b) The absolute value of any eigenvalue of the stochastic matrix $A$ is less than or equal to $1$.

Proof.

(a) The stochastic matrix $A$ has an eigenvalue $1$.

We compute that
$\begin{bmatrix} a_{11} & a_{12} & \dots & a_{1n} \\ a_{21} &a_{22} & \dots & a_{2n} \\ \vdots & \vdots & \dots & \vdots \\ a_{n1} & a_{n2} & \dots & a_{nn} \end{bmatrix} \begin{bmatrix} 1 \\ 1 \\ \vdots \\ 1 \end{bmatrix} = \begin{bmatrix} a_{11}+a_{12}+\cdots+a_{1n} \\ a_{21}+a_{22}+\cdots+a_{2n} \\ \vdots \\ a_{n1}+a_{n2}\cdots+a_{nn} \end{bmatrix} =1\cdot \begin{bmatrix} 1 \\ 1 \\ \vdots \\ 1 \end{bmatrix}.$ Here the second equality follows from the definition of a right stochastic matrix.
(Each row sums up to $1$.)
This computation shows that $1$ is an eigenvector of $A$ and $\begin{bmatrix} 1 \\ \vdots \\ 1 \end{bmatrix}$ is an eigenvector corresponding to the eigenvalue $1$.

(b) The absolute value of any eigenvalue of the stochastic matrix $A$ is less than or equal to $1$.

Let $\lambda$ be an eigenvalue of the stochastic matrix $A$ and let $\mathbf{v}$ be a corresponding eigenvector.
That is, we have
$A\mathbf{v}=\lambda \mathbf{v}.$

Comparing the $i$-th row of the both sides, we obtain
$a_{i1}v_1+a_{i2}v_2+\cdots+a_{in}v_n=\lambda v_i \tag{*}$ for $i=1, \dots, n$.
Let
$|v_k|=\max\{|v_1|, |v_2|, \dots, |v_n|\},$ namely $v_k$ is the entry of $\mathbf{v}$ that has the maximal absolute value.

Note that $|v_k|>0$ since otherwise we have $\mathbf{v}=\mathbf{0}$ and this contradicts that an eigenvector is a nonzero vector.
Then from (*) with $i=k$, we have
\begin{align*}
|\lambda|\cdot |v_k| &= |a_{k1}v_1+a_{k2}v_2+\cdots+a_{kn}v_n|\\
& \leq a_{k1}|v_1|+a_2|v_2|+\cdots+ a_{kn}|v_{n}| &&(\text{by the triangle inequality and } a_{ij} \geq 0)\\
&\leq a_{k1}|v_k|+a_2|v_k|+\cdots+ a_{kn}|v_{k}| && (\text{since } |v_k| \text{ is maximal})\\
&=(a_{k1}+a_{k2}+\cdots+a_{kn})|v_k|=|v_k|.
\end{align*}

Since $|v_k|>0$, it follows that
$\lambda \leq 1$ as required.

Remark.

A stochastic matrix is also called probability matrix, transition matrix, substitution matrix, or Markov matrix.

2 Responses

1. murat says:

nice proof thanks

• Yu says:

Dear murat,

Suppose that $A$ and $P$ are $3 \times 3$ matrices and $P$ is invertible matrix. If \[P^{-1}AP=\begin{bmatrix} 1 & 2...