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.

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

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 […]

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 , […]