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

Contents

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

Add to solve later