Stochastic Matrix (Markov Matrix) and its Eigenvalues and Eigenvectors

Problem 34

(a) Let

\[A=\begin{bmatrix}
a_{11} & a_{12}\\
a_{21}& a_{22}
\end{bmatrix}\]
be a matrix such that $a_{11}+a_{12}=1$ and $a_{21}+a_{22}=1$. Namely, the sum of the entries in each row is $1$.

(Such a matrix is called (right) stochastic matrix (also termed probability matrix, transition matrix, substitution matrix, or Markov matrix).)

Then prove that the matrix $A$ has an eigenvalue $1$.

(b) Find all the eigenvalues of the matrix
\[B=\begin{bmatrix}
0.3 & 0.7\\
0.6& 0.4
\end{bmatrix}.\]

(c) For each eigenvalue of $B$, find the corresponding eigenvectors.

(a) Prove that the matrix $A$ has an eigenvalue $1$.

Let $\mathbf{x}=\begin{bmatrix}
1 \\
1
\end{bmatrix}$ and we compute
\begin{align*}
A \mathbf{x}=\begin{bmatrix}
a_{11} & a_{12}\\
a_{21}& a_{22}
\end{bmatrix}
\begin{bmatrix}
1 \\
1
\end{bmatrix}
=\begin{bmatrix}
a_{11}+a_{12} \\
a_{21}+a_{22}
\end{bmatrix}
=\begin{bmatrix}
1 \\
1
\end{bmatrix}
=1\cdot \mathbf{x}.
\end{align*}
This shows that $A$ has the eigenvalue $1$.

(b) Find all the eigenvalues of the matrix $B$.

Note that the matrix $B$ is of the type of the matrix in (a).
Thus the matrix $B$ has the eigenvalue $1$. Since $B$ is $2$ by $2$ matrix, it has two eigenvalues counting multiplicities. To find the other eigenvalue, we note that the trace is the sum of the eigenvalues.

Thus we have
\[\tr(B)=0.3+0.4=1+\lambda,\]
where $\lambda$ is the second eigenvalue. Hence another eigenvalue is $\lambda=-0.3$.

(c) For each eigenvalue of $B$, find the corresponding eigenvectors.

By solving $(B-I)\mathbf{x}=\mathbf{0}$ and $(B+0.3I)\mathbf{x}=\mathbf{0}$, we find that
\[\begin{bmatrix}
1 \\
1
\end{bmatrix}t \quad \text{ and } \quad \begin{bmatrix}
-7 \\
6
\end{bmatrix}t\]
for any nonzero scalar $t$ are eigenvectors corresponding to eigenvalues $1$ and $-0.3$, respectively.

Comment.

For some specific matrices, we can find eigenvalues without solving the characteristic polynomials like we did in part (b).

Eigenvalues of a Stochastic Matrix is Always Less than or Equal to 1
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 […]

Find the Limit of a Matrix
Let
\[A=\begin{bmatrix}
\frac{1}{7} & \frac{3}{7} & \frac{3}{7} \\
\frac{3}{7} &\frac{1}{7} &\frac{3}{7} \\
\frac{3}{7} & \frac{3}{7} & \frac{1}{7}
\end{bmatrix}\]
be $3 \times 3$ matrix. Find
\[\lim_{n \to \infty} A^n.\]
(Nagoya University Linear […]

Matrices Satisfying $HF-FH=-2F$
Let $F$ and $H$ be an $n\times n$ matrices satisfying the relation
\[HF-FH=-2F.\]
(a) Find the trace of the matrix $F$.
(b) Let $\lambda$ be an eigenvalue of $H$ and let $\mathbf{v}$ be an eigenvector corresponding to $\lambda$. Show that there exists an positive integer $N$ […]

Trace of the Inverse Matrix of a Finite Order Matrix
Let $A$ be an $n\times n$ matrix such that $A^k=I_n$, where $k\in \N$ and $I_n$ is the $n \times n$ identity matrix.
Show that the trace of $(A^{-1})^{\trans}$ is the conjugate of the trace of $A$. That is, show that […]

Transpose of a Matrix and Eigenvalues and Related Questions
Let $A$ be an $n \times n$ real matrix. Prove the followings.
(a) The matrix $AA^{\trans}$ is a symmetric matrix.
(b) The set of eigenvalues of $A$ and the set of eigenvalues of $A^{\trans}$ are equal.
(c) The matrix $AA^{\trans}$ is non-negative definite.
(An $n\times n$ […]

Find the Formula for the Power of a Matrix Using Linear Recurrence Relation
Suppose that $A$ is $2\times 2$ matrix that has eigenvalues $-1$ and $3$.
Then for each positive integer $n$ find $a_n$ and $b_n$ such that
\[A^{n+1}=a_nA+b_nI,\]
where $I$ is the $2\times 2$ identity matrix.
Solution.
Since $-1, 3$ are eigenvalues of the […]

Solve Linear Recurrence Relation Using Linear Algebra (Eigenvalues and Eigenvectors)
Let $V$ be a real vector space of all real sequences
\[(a_i)_{i=1}^{\infty}=(a_1, a_2, \dots).\]
Let $U$ be the subspace of $V$ consisting of all real sequences that satisfy the linear recurrence relation
\[a_{k+2}-5a_{k+1}+3a_{k}=0\]
for $k=1, 2, \dots$.
Let $T$ be […]

Maximize the Dimension of the Null Space of $A-aI$
Let
\[ A=\begin{bmatrix}
5 & 2 & -1 \\
2 &2 &2 \\
-1 & 2 & 5
\end{bmatrix}.\]
Pick your favorite number $a$. Find the dimension of the null space of the matrix $A-aI$, where $I$ is the $3\times 3$ identity matrix.
Your score of this problem is equal to that […]

[…] The matrix $A$ is called a stochastic matrix (or Markov matrix, probability matrix). For the definition of these terminology and a similar problem, see problem Stochastic matrix (Markov matrix) and its eigenvalues and eigenvectors. […]

## 1 Response

[…] The matrix $A$ is called a stochastic matrix (or Markov matrix, probability matrix). For the definition of these terminology and a similar problem, see problem Stochastic matrix (Markov matrix) and its eigenvalues and eigenvectors. […]