Find the $2013$th power of a given $3\times 3$ matrix Question from my linear algebra homework I'm struggling with:
Let $D = \begin{bmatrix} -2 & 5 & 4 \\-1 & 0 & 0 \\0 & 4 & 3 \end{bmatrix}$
We are asked:


*

*Find $D^5+3D^2-D+I$

*Find $D^{2013}$

*Write $D^{-1}$ as a polynomial of $D$
I solved questions 1) and 3) but can't solve 2)...
 A: Although $D$ is not diagonalizable, it has the Jordan decomposition (courtesy of Wolfram Alpha):
$$D = SJS^{-1}$$
where
$$S = \begin{bmatrix} -1 & 1 & \frac12 \\-1 & -1 & \frac12 \\1 & 2 & 0 \end{bmatrix}$$
and
$$J = \begin{bmatrix} -1 & 0 & 0 \\0 & 1 & 1 \\0 & 0 & 1 \end{bmatrix}$$
There is a simple closed-form expression for $J^n$, which you should be able to find and prove yourself.
A: The characteristic polynomial of $D$ is given by
$$\chi_D(\lambda) = \det(\lambda I_3 - D) = \lambda^3 - \lambda^2 - \lambda + 1 = (\lambda - 1)^2 (\lambda+1)$$
By Cayley Hamilton theorem, we have
$$\chi_D(D) = D^3 - D^2 - D + I_3 = (D - I_3)^2(D + I_3) = (D^2 - I_3)(D - I_3) = 0$$
Since $(\lambda + 1)\chi_D(\lambda) = (\lambda^2 - 1)^2$, we have
$(D^2 - I_3)^2 = 0$ and hence
$$\begin{align}
D^{2013} 
= & (I_3 + (D^2 - I_3))^{1006} D\\
= & (I_3 + 1006 (D^2 - I_3)) D\quad\color{blue}{\longleftarrow \text{throwing away terms}\propto (D^2 - I_3)^2}\\
= & D + 1006 (D^2 - I_3)((D - I_3) + I_3)\\
= & D + 1006 (D^2 - I_3)\quad\color{blue}{\longleftarrow \text{throwing away terms}\propto (D^2 - I_3)(D-I_3)}\\
= & \left[\begin{array}{rrr}
-2014  & 6041 & 4028 \\
2011 & -6036  &  -4024 \\
-4024  & 12076  & 8051
\end{array}\right]
\end{align}
$$
A: Bull headed approach. 2013 written in binary form is 11111011101.
Therefore, repeatedly square D 10 times which gives you $D$, $D^2$, $D^4$, $D^8$, $D^{16}$, $D^{32}$, $D^{64}$, $D^{128}$, $D^{256}$, $D^{512}$ and $D^{1024}$.
Then multiply $D^{1024} \times D^{512} \times D^{256} \times D^{128} \times D^{64} \times D^{16} \times D^{8} \times D^4$.
So, you will have to perform 17 multiplications, which is doable.
A: Here is how I would attack such a question. You need to find a polynomial equation satisfied by$~D$ first. You could use the characteristic polynomial for that (by the Cayley-Hamilton theorem), but knowing that such a polynomial of degree at most$~3$ exists, you can also just try to find a relation between some powers of$~D$. The sparse second line suggests right-multiplying powers of $D$ to $(0~1~0)$, giving the sequence $(0~1~0),(-1~0~0),(2~{-}5~{-}4),(3~{-}6~{-}4)$. The first three are clearly linearly independent, and the fourth one gives the relation $(0~1~0)-(-1~0~0)-(2~{-}5~{-}4)+(3~{-}6~{-}4)=(0~0~0)$, so your polynomial equation should be $I-D^1-D^2+D^3=0$, which you can check to be true. Now $X^3-X^2-X+1=(X-1)(X^2-1)=(X-1)^2(X+1)$. Indeed your matrix is not diagonalisable because of the double root.
To compute $X^{2013}$ you can take its remainder$~R$ after division by $P=(X-1)(X^2+1)$, so that $X^{2013}=PQ+R$ for some (quotient)$~Q$. For finding the remainder after division by a polynomial with such easy (complex) roots as $P$ has, the standard trick to avoid doing a (very) long division of polynomials is write the remainder as a polynomial of degree${}<\deg P=3$ with unknown coefficients: $R=aX^2+bX+c$, and evaluate the equation $X^{2013}=PQ+R$ at the roots of$~P$; since these substitutions annihilate the term $PQ$ regardless of$~Q$, they give you linear equations in $a,b,c$. The problem here is that you have only two roots $1,-1$ to substitute, although $1$ is a double root of the minimal polynomial. There is another trick to solve this shortage of equations: since $1$ is also a root of the derivative $P'$ of$~P$, you can take the derivative of the equation (being an identity of polynomials in$~X$, this gives an equation that must still hold) giving $2013X^{2012}=P'Q+PQ'+R'$. Now substitute $X=1$ into that to get a third equation that will let you solve $a,b,c$. The answer is $aD^2+bD+cI$.
A: Ok, I found the way to answer this, but I've still run into some trouble.
Basically the Idea is this:
you take the polynomial $t^{2013}$ and you divide it by the characteristic polynomial which is $-t^3+t^2+t-1$ and you get:
$t^{2013} = (-t^3+t^2+t-1)*q(t)+r(t)$ where $deg(r(t)) \leq deg(-t^3+t^2+t-1)-1 = 2$
$t=1$ and $t=-1$ are roots of $-t^3+t^2+t-1$ so if $r(x)=ax^2+bx+c$:
$1^{2013} = a+b+c$ and $(-1)^{2013} = a-b+c$
If we find a b c then we solved the question. But how do we find a b c?
