Linear Algebra

Find the Formula for the Power of a Matrix Using Linear Recurrence Relation

Problem 323

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.

Add to solve later

Solution.

Since $-1, 3$ are eigenvalues of the matrix $A$, the characteristic polynomial of $A$ is
\[(t+1)(t-3)=t^2-2t-3.\] By Cayley-Hamilton theorem, we have
\[A^2-2A-3I=O,\] where $O$ is the $2\times 2$ zero matrix.
Thus we have
\[A^2=2A+3I, \tag{*}\] and hence $a_1=2, b_1=3$.

Multiplying (*) by $A$, we have
\begin{align*}
A^3&=AA^2=2A^2+3A\\
&=2(2A+3I)+3A\\
&=7A+6I.
\end{align*}
Thus, $a_2=7, b_2=6$.

In general, we have
\begin{align*}
A^{n+2}&=AA^{n+1}\\
&=A(a_nA+b_nI)\\
&=a_nA^2+b_nA\\
&=a_n(2A+3I)+b_n A\\
&=(2a_n+b_n)A+(3a_n)I.
\end{align*}
Thus we obtain
\begin{align*}
a_{n+1}&=2a_n+b_n\\
b_{n+1}&=3a_n.
\end{align*}

This yields the linear recurrence relation
\[a_{n+2}=2a_{n+1}+3a_{n}\] with initial values $a_1=2, a_2=7$.

The general term $a_n$ of the sequence $(a_n)_{i=n}^{\infty}$ is obtained in the previous post Solve a linear recurrence relation using vector space technique:
\[a_n=\frac{1}{4} \big( (-1)^n+3^{n+1} \big).\] (You may alternatively find this using an elementary technique.)

Then we also have
\[b_n=3a_{n-1}=\frac{3}{4} \big( (-1)^{n-1}+3^{n} \big).\] (This formula is true for $n=1$ as well.)

In conclusion, we have obtained
\begin{align*}
A^n=\frac{1}{4} \big( (-1)^n+3^{n+1} \big)A+\frac{3}{4} \big( (-1)^{n-1}+3^{n} \big)I
\end{align*}
for any positive integer $n$.

Add to solve later

More from my site

Solve a Linear Recurrence Relation Using Vector Space Technique Let $V$ be a real vector space of all real sequences \[(a_i)_{i=1}^{\infty}=(a_1, a_2, \dots).\] Let $U$ be a subspace of $V$ defined by \[U=\{(a_i)_{i=1}^{\infty}\in V \mid a_{n+2}=2a_{n+1}+3a_{n} \text{ for } n=1, 2,\dots \}.\] Let $T$ be the linear transformation from […]
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 […]
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 […]
Matrix Representation of a Linear Transformation of Subspace of Sequences Satisfying Recurrence Relation 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$. (a) […]
Given All Eigenvalues and Eigenspaces, Compute a Matrix Product Let $C$ be a $4 \times 4$ matrix with all eigenvalues $\lambda=2, -1$ and eigensapces \[E_2=\Span\left \{\quad \begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \end{bmatrix} \quad\right \} \text{ and } E_{-1}=\Span\left \{ \quad\begin{bmatrix} 1 \\ 2 \\ 1 \\ 1 […]
Sequences Satisfying Linear Recurrence Relation Form a Subspace Let $V$ be a real vector space of all real sequences \[(a_i)_{i=1}^{\infty}=(a_1, a_2, \cdots).\] Let $U$ be the subset of $V$ defined by \[U=\{ (a_i)_{i=1}^{\infty} \in V \mid a_{k+2}-5a_{k+1}+3a_{k}=0, k=1, 2, \dots \}.\] Prove that $U$ is a subspace of […]
Given the Data of Eigenvalues, Determine if the Matrix is Invertible In each of the following cases, can we conclude that $A$ is invertible? If so, find an expression for $A^{-1}$ as a linear combination of positive powers of $A$. If $A$ is not invertible, explain why not. (a) The matrix $A$ is a $3 \times 3$ matrix with eigenvalues $\lambda=i , […]