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

Problems and solutions in Linear Algebra

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

 
LoadingAdd to solve later

Sponsored Links


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.


LoadingAdd to solve later

Sponsored Links

More from my site

You may also like...

2 Responses

  1. murat says:

    nice proof thanks

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.

More in Linear Algebra
Linear Algebra Problems and Solutions
Eigenvalues of Squared Matrix and Upper Triangular Matrix

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

Close