Linear Algebra

Find the Limit of a Matrix

Nagoya University Linear Algebra Exam Problems and Solutions

Problem 50

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 Algebra Exam)

Add to solve later

Hint.

The matrix $A$ is symmetric, hence diagonalizable.
Diagonalize $A$.
You may want to find eigenvalues
without computing the characteristic polynomial for $A$.

Solution.

Note that the matrix $A$ is symmetric, hence it is diagonalizable.
We observe several things to simplify the computation.

First, note that the sum of the entries in each row is $1$.
(Such a matrix is call a stochastic matrix. See the comment below.)
Thus the matrix $A$ has eigenvalue $1$ and $\begin{bmatrix}
1 \\
1 \\
1
\end{bmatrix}$ is an eigenvector.

Also note that if we add $2/7(=-\lambda)$ to diagonal entries, then every entry becomes $3/7$.
That is,
\[A+\frac{2}{7}I=\begin{bmatrix}
\frac{3}{7} & \frac{3}{7} & \frac{3}{7} \\
\frac{3}{7} &\frac{3}{7} &\frac{3}{7} \\
\frac{3}{7} & \frac{3}{7} & \frac{3}{7}
\end{bmatrix},\] which is clearly singular.

From this observation, we notice that $-2/7$ is an eigenvalue of $A$ and eigenvectors are nonzero solution of $x_1+x_2+x_3=0$. Therefore $\begin{bmatrix}
1 \\
-1 \\
0
\end{bmatrix}$ and $\begin{bmatrix}
0 \\
1 \\
-1
\end{bmatrix}$ are linearly independent eigenvectors for the eigenvalue $-2/7$.

Hence the geometric (and hence algebraic) multiplicity of the eigenvalue $-2/7$ is $2$.
(Note that we found all eigenvalues of $A$ without actually computing the characteristic polynomial.)

Now the invertible matix $P=\begin{bmatrix}
1 & 1 & 0 \\
1 &-1 &1 \\
1 & 0 & -1
\end{bmatrix}$ diagonalize $A$. Namely we have
\[P^{-1}AP=\begin{bmatrix}
1 & 0 & 0 \\
0 &-2/7 &0 \\
0 & 0 & -2/7
\end{bmatrix}.\] Hence
\[A=P\begin{bmatrix}
1 & 0 & 0 \\
0 &-2/7 &0 \\
0 & 0 & -2/7
\end{bmatrix}P^{-1}.\] Therefore we have
\[ A^n=P\begin{bmatrix}
1^n & 0 & 0 \\
0 & (-2/7)^n &0 \\
0 & 0 & (-2/7)^n
\end{bmatrix}P^{-1}
\text{ and } \lim_{n \to \infty} A^n=P\begin{bmatrix}
1 & 0 & 0 \\
0 & 0 &0 \\
0 & 0 & 0
\end{bmatrix}P^{-1}. \] Find the inverse $P^{-1}$ by your favorite method
\[P^{-1}=\begin{bmatrix}
\frac{1}{3} & \frac{1}{3} & \frac{1}{3} \\[6pt] \frac{2}{3} &\frac{-1}{3} &\frac{-1}{3} \\[6pt] \frac{1}{3} & \frac{1}{3} & \frac{-2}{3}
\end{bmatrix}.\] Then the answer is
\[\lim_{n \to \infty} A^n=\begin{bmatrix}
\frac{1}{3} & \frac{1}{3} & \frac{1}{3} \\[6pt] \frac{1}{3} &\frac{1}{3} &\frac{1}{3} \\[6pt] \frac{1}{3} & \frac{1}{3} & \frac{1}{3}
\end{bmatrix}.\]

Comment.

You might come up with the idea to use the diagonalization as it is an exam problem in linear algebra.
But you soon realize that computing the characteristic polynomial for $A$ is a bit messy.
So sometimes it is important to find eigenvalues without finding the roots of the characteristic polynomial.

We observed that

the sum of row entries of $A$ is $1$
if we add $(2/7)I$ to $A$ then we obtain a matrix whose entries are all identical.

These observation yields the eigenvalues of $A$ without using the characteristic polynomial.

If the sum of entries of each row of a matrix is $1$, then the matrix is called called a stochastic matrix (or Markov matrix, probability matrix).
The matrix $A$ in the problem is an example of a stochastic matrix.

Stochastic matrices have always $1$ as an eigenvalue.
see the post
Stochastic matrix (Markov matrix) and its eigenvalues and eigenvectors
for an example of a $2\times 2$ stochastic matrix.

Add to solve later

More from my site

Find the Eigenvalues and Eigenvectors of the Matrix $A^4-3A^3+3A^2-2A+8E$. Let \[A=\begin{bmatrix} 1 & -1\\ 2& 3 \end{bmatrix}.\] Find the eigenvalues and the eigenvectors of the matrix \[B=A^4-3A^3+3A^2-2A+8E.\] (Nagoya University Linear Algebra Exam Problem) Hint. Apply the Cayley-Hamilton theorem. That is if $p_A(t)$ is the […]
Determine the Values of $a$ such that the 2 by 2 Matrix is Diagonalizable Let \[A=\begin{bmatrix} 1-a & a\\ -a& 1+a \end{bmatrix}\] be a $2\times 2$ matrix, where $a$ is a complex number. Determine the values of $a$ such that the matrix $A$ is diagonalizable. (Nagoya University, Linear Algebra Exam Problem) Proof. To […]
Orthogonality of Eigenvectors of a Symmetric Matrix Corresponding to Distinct Eigenvalues Suppose that a real symmetric matrix $A$ has two distinct eigenvalues $\alpha$ and $\beta$. Show that any eigenvector corresponding to $\alpha$ is orthogonal to any eigenvector corresponding to $\beta$. (Nagoya University, Linear Algebra Final Exam Problem) Hint. Two […]
Stochastic Matrix (Markov Matrix) and its Eigenvalues and Eigenvectors (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 […]
Characteristic Polynomial, Eigenvalues, Diagonalization Problem (Princeton University Exam) Let \[\begin{bmatrix} 0 & 0 & 1 \\ 1 &0 &0 \\ 0 & 1 & 0 \end{bmatrix}.\] (a) Find the characteristic polynomial and all the eigenvalues (real and complex) of $A$. Is $A$ diagonalizable over the complex numbers? (b) Calculate $A^{2009}$. (Princeton University, […]
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 […]
How to Diagonalize a Matrix. Step by Step Explanation. In this post, we explain how to diagonalize a matrix if it is diagonalizable. As an example, we solve the following problem. Diagonalize the matrix \[A=\begin{bmatrix} 4 & -3 & -3 \\ 3 &-2 &-3 \\ -1 & 1 & 2 \end{bmatrix}\] by finding a nonsingular […]
Characteristic Polynomials of $AB$ and $BA$ are the Same Let $A$ and $B$ be $n \times n$ matrices. Prove that the characteristic polynomials for the matrices $AB$ and $BA$ are the same. Hint. Consider the case when the matrix $A$ is invertible. Even if $A$ is not invertible, note that $A-\epsilon I$ is invertible matrix […]