Find the $n$-th power of a $3{\times}3$ matrix using the Cayley-Hamilton theorem.

Question

I need to find $A^n$ of the matrix $A=\begin{pmatrix} 2&0 & 2\\ 0& 2 & 1\\ 0& 0 & 3 \end{pmatrix}$ using Cayley-Hamilton theorem.

I found the characteristic polynomial $P(A)=(2-A)^2(3-A)$ from which I got $A^3=7A^2-16A+12$. How to continue?

Answer 1

One approach: let $p(x) = x^3 - 7x^2 + 16x - 12$. Calculate the remainder upon dividing $x^n$ by $x^3 - 7x^2 + 16x - 12$. That is, find a polynomial $r(x)$ with degree at most $2$ such that $$ x^n = q(x) p(x) + r(x). $$ It follows that $A^n = q(A)p(A) + r(A) = 0 + r(A) = r(A)$.

Another approach: we see that $A^k$ satisfies the recurrence relation $$ A^k = 7A^{k-1} - 16A^{k-2} + 12A^{k-3}, \qquad k \geq 3. $$ We can calculate the powers of $A$ recursively using this formula.

If you're looking for a direct formula that gives you the entries of $A^n$, then the quickest approach is not to use the Cayley Hamilton theorem. Rather, it is faster to use diagonalization, noting that the eigenvalues of $A$ are $2,2,3$.

Answer 2

We can compute $A^2$ directly: $$ A^2 = \left( \begin{array}{ccc} 2 & 0 & 2 \\ 0 & 2 & 1 \\ 0 & 0 & 3 \\ \end{array} \right)\left( \begin{array}{ccc} 2 & 0 & 2 \\ 0 & 2 & 1 \\ 0 & 0 & 3 \\ \end{array} \right) = \left( \begin{array}{ccc} 4 & 0 & 10 \\ 0 & 4 & 5 \\ 0 & 0 & 9 \\ \end{array} \right). $$ From the Cayley-Hamilton theorem, it follows that \begin{align} A^3 &= 7A^2 -16A + 12I\\ &= 7\left( \begin{array}{ccc} 4 & 0 & 10 \\ 0 & 4 & 5 \\ 0 & 0 & 9 \\ \end{array} \right) - 16\left( \begin{array}{ccc} 2 & 0 & 2 \\ 0 & 2 & 1 \\ 0 & 0 & 3 \\ \end{array} \right) + 12\left( \begin{array}{ccc} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ \end{array} \right)\\ &= \left( \begin{array}{ccc} 8 & 0 & 38 \\ 0 & 8 & 19 \\ 0 & 0 & 27 \\ \end{array} \right). \end{align} Observe the pattern $$ A^n = \left( \begin{array}{ccc} 2^n & 0 & -2 \left(2^n-3^n\right) \\ 0 & 2^n & -2^n+3^n \\ 0 & 0 & 3^n \\ \end{array} \right). $$ Clearly this holds for $n=1$. Assume that it holds for some $n\geqslant 1$, then \begin{align} A^{n+1} &= AA^{n}\\ &= \left( \begin{array}{ccc} 2 & 0 & 2 \\ 0 & 2 & 1 \\ 0 & 0 & 3 \\ \end{array} \right)\left( \begin{array}{ccc} 2^n & 0 & -2 \left(2^n-3^n\right) \\ 0 & 2^n & -2^n+3^n \\ 0 & 0 & 3^n \\ \end{array} \right)\\ &= \left( \begin{array}{ccc} 2^{n+1} & 0 & -2 \left(2^{n+1}-3^{n+1}\right) \\ 0 & 2^{n+1} & -2^{n+1}+3^{n+1} \\ 0 & 0 & 3^{n+1}. \\ \end{array} \right) \end{align} So by induction, this formula holds for all positive integers $n$.

Answer 3

A consequence of the Cayley-Hamilton theorem is that $$A^n=aI+bA+cA^2\tag 1$$ for some scalar coefficients $a$, $b$ and $c$. The above equation also holds for the eigenvalues of $A$: $$a+b\lambda+c\lambda^2=\lambda^n\tag2.$$ Since the eigenvalues of $A$ are $2$, $2$ and $3$ (which you can read directly from the main diagonal as $A$ is triangular—no need to compute the characteristic polynomial), this gives you two independent linear equations in the unknown coefficients: $$a+2b+4c=2^n \\ a+3b+9c=3^n.$$ You need one more for a unique solution. Another independent equation can be generated by differentiating (2) and setting $\lambda=2$, since that eigenvalue has multiplicity $\gt1$, to get $b+4c=n2^{n-1}$. Solve for the unknown coefficients (the solution isn’t exactly “pretty”) and plug them into (1).

Diagonalization seems like it would be less work in this case, especially since eigenvectors can be found pretty much by inspection, but I expect that this problem was meant as an exercise in applying Cayley-Hamilton rather than working out an expression for $A^n$ per se.

An interesting way to come up with an expression for $A^n$ for this particular matrix is to observe that $B=A-2I$ is idempotent and, of course, commutes with $2I$. Expanding $A^n$ with the binomial theorem produces $$(B+2I)^n = \sum_{k=0}^n \binom nk 2^{n-k} B^k = 2^n I + \left(\sum_{k=0}^{n-1} \binom nk 2^{n-k}\right)B = 2^n I + (3^n-2^n)B.$$

Answer 4

Since $p(A)=0$ where $p(x)=(2-x)^2(3-x)$, if we divide $x^n$ by $p(x)$ to get $x^n=p(x)q(x)+r(x)$, then $A^n=p(A)q(A)+r(A)=0q(A)+r(A)=r(A)$, so it suffices to figure out $r$. However, if $n$ is large, actually doing division will not be effective.

Since $p(2)=p(3)=0$, we have that $r(2)=2^n$ and $r(3)=3^n$. However, since all we know about the degree of $r$ is that it is less than $3$, we need another value to specify it. However, if we differentiate

$$x^n=p(x)q(x)+r(x)$$ to get $$nx^{n-1}=p'(x)q(x)+p(x)q'(x)+r'(x)$$ and use the fact that, because $2$ is a double root of $p(x)$, $p(2)=p'(2)=0$, then we get $n2^{n-1}=r'(2)$.

If we write $r(x)=a_nx^2+b_nx+c_n$, then we get the system of equations:

$$\begin{align} 2^n &=4a_n+2b_n+c_n \\ 3^n&=9a_n+3b_n+c_n \\ n2^{n-1}&=4a_n+b_n \end{align}.$$

Then we can solve

$$\pmatrix{a_n \\ b_n \\ c_n}=\pmatrix{4&2&1\\9&3&1\\4&1&0}^{-1}\pmatrix{2^n\\3^n\\n2^{n-1}}=\pmatrix{3^n-2^n-n2^{n-1}\\4\cdot 2^n+5n\cdot 2^n-3^n\\4\cdot 3^n-3\cdot 2^n-6n\cdot 2^n}.$$

However, we can simplify things if we note that $A$ actually satisfies the quadratic equation $(A-2I)(A-3I)=0$ (the minimal polynomial will always divide the characteristic polynomial and has the same roots but with potentially smaller multiplicities, so there aren't many combos to check here), so we can use this quadratic polynomial instead of the characteristic polynomial to obtain that $A^n=a_nA+b_nI$ for some $a_n,b_n$. If $r_n(x)=a_nx+b_n$ is the remainder polynomial, we have (using the exact same proceedure as before) $$2^n=2a_n+b_n, \quad 3^n=3a_n+b_n,$$ so $$a_n=3^n-2^n, \quad b_n=-2\cdot 3^n-3\cdot 2^n.$$