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

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?

• I would diagonalize $A$: you know its eigenvalues are 2, 2 and 3. You can easily find eigenvectors. Otherwise, you could try by induction: wolframalpha.com/input/…
– Surb
Jan 21, 2020 at 22:25
• The relation is really $A^3=7A^2-16A+12\color{red}I$. Jan 21, 2020 at 22:39
• @Surb That’s not “using Cayley-Hamilton,” though.
– amd
Jan 22, 2020 at 1:25

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

• This is finding a pattern and using induction, not using Cayley-Hamilton, except in the sense that you computed $A^3$ that way. A perfectly valid technique for finding powers of a matrix when it works, but not really in the spirit of the question. Moreover, it wouldn't really work if the matrix weren't so simple that a pattern could be spotted by inspection. Jan 22, 2020 at 9:56
• As pointed out in @Omnomnomnom's answer, Cayley-Hamilton is not the most efficient way to compute $A^n$ anyway. Jan 22, 2020 at 10:09

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

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

• Nice observations + 1.
– Moo
Jan 22, 2020 at 18:21

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