# Find A^1000 by using Cayley-Hamilton Theorem

I get stuck at the following question:

Consider the matrix $A$ = $\begin{bmatrix} 0 & 2 & 0 \\ 1 & 1 & -1 \\ -1 & 1 & 1\\ \end{bmatrix}$

Find $A^{1000}$ by using the Cayley-Hamilton theorem.

I find the characteristic polynomial by $P(A) = -A^{3} + 2A^2 = 0$ (by Cayley-Hamilton) but I don't see how to find $A^{1000}$ by this characteristic polynomial.

-

Your formula tells you, after you multiply through by $A^{997}$, that $$A^{1000}=2A^{999}.$$ Similarly, $$2A^{999}=4A^{998}.$$

This process can be repeated to find $A^{1000}$ in terms of $A^2$, which you can then compute.

-
Cute! Mathematical Cuteness buys a +1 on my books! –  Robert Lewis Apr 5 '14 at 22:44
Answered my question, thanks a lot! –  surfer1311 Apr 5 '14 at 23:11

There is another way of approaching this.

You could divide $x^{1000}$ by the characteristic polynomial:

$x^{1000} = (-x^3+2x^2)Q+R$ where $R$ is a polynomial of degree less than 3 with unknown coefficients.

write down $R=ax^2+bx+c$ and evaluate $R$ at the roots of the characteristic polynomial.

Meaning, write down $\lambda^{1000}=a\lambda ^2+b\lambda+c$

and

$\xi^{1000} = a\xi ^2+b\xi+c$

and

$\rho^{1000} = a\rho ^2+b\rho+c$

where $\lambda$ and $\xi$ and $\rho$ are roots of the characteristic polynomial. as you can see, $Q$ wont matter because it is multiplied by zero.

Do this to find the coeffiecents of the remainder, $R$.

after you have done that, insert $x=A$ to get $A^{1000}=aA^2+bA+c$ with the coeffiecents $a,b,c$ that you found.

Edit: The problem here, is that you have a double root, so you need to use the derivative as well.

divide $x^{1000}$ by $(-x^3+2x^2)$ to get:

$x^{1000} = (-x^3+2x^2)Q+ax^2+bx+c$ where $Q$ is some polynomial unknown to us.

the roots of the char. polynomial are $0,2$. put $x=0$ to get:

$0^{1000}=0=0*Q+c=c$ so $c=0$.

now derive $x^{1000} = (-x^3+2x^2)Q+ax^2+bx$ to get:

$1000x^{999}=(-3x^2+4x)Q+Q'(-x^3+2x^2)+2ax+b$ and insert $x=0$ again t oget:

$1000*0^{999} = 0 =b$ meaning $b=0$.

Now back to our original formula with $b=c=0$:

$x^{1000} = (-x^3+2x^2)Q+ax^2$

Insert $x=2$ to get:

$2^{1000} = 4a$ meaning $a=2^{998}$.

Now our original formula looks like $x^{1000} = (-x^3+2x^2)Q+2^{998}x^2$

Inserts $x=A$ to get:

$A^{1000} = 2^{998}A^2$

-
Would you like me to write down entire solution for you? or are you fine for now :)? –  Oria Gruber Apr 5 '14 at 22:55
Wrote it down anyway. –  Oria Gruber Apr 5 '14 at 23:07
+1 very nice! :-) –  Ant Apr 6 '14 at 14:11


$$\dot{\alpha}\pars{t} + \dot{\beta}\pars{t}A + \dot{\gamma}\pars{t}A^{2} =A\expo{At} =\alpha\pars{t}A + \beta\pars{t}A^{2} + \gamma\pars{t}\ \overbrace{A^{3}}^{2A^{2}}\,, \quad \left\lbrace% \begin{array}{l} \alpha\pars{0} = 1 \\[1mm] \beta\pars{0} = \gamma\pars{0} = 0 \end{array}\right.$$

$$\dot{\alpha}\pars{t} = 0\,,\quad \dot{\beta}\pars{t} = \alpha\pars{t}\,,\quad \dot{\gamma}\pars{t} = \beta\pars{t} + 2\gamma\pars{t} \quad\imp\quad \left\lbrace% \begin{array}{rcl} \alpha\pars{t} & = & 1 \\[1mm] \beta\pars{t} & = & t \\[1mm] \gamma\pars{t} & = & {\expo{2t} - 2t - 1 \over 4} \end{array}\right.$$

$$\expo{At} = 1 + tA + {\expo{2t} - 2t - 1 \over 4}\,A^{2}$$

\begin{align} A^{1000} &= \left.\totald[1000]{\pars{\expo{At}}}{t}\right\vert_{t = 0} =\left. {A^{2} \over 4}\, \totald[1000]{\bracks{\expo{2t} - 2t - 1}}{t}\right\vert_{t = 0} ={A^{2} \over 4}\,2^{1000} \end{align} $$\boxed{\vphantom{\Huge {A \over B}}\quad\color{#00f}{\large A^{1000} = 2^{998}\ A^{2}}\quad}$$

-
Nice and innovative. Only one query: why $e^{At}=\alpha(t)+\beta(t)A+\gamma(t)A^2$, why not further more terms? @Felix Marin –  Anjan3 Sep 8 '14 at 7:57
@AnjanDebnath Because any term $A^{k}$, with $k>2$, is a linear combination of $A^{0},A$ and $A^{2}$: $A$ satisfies its characteristic equation which is a third degree polynomial in $A$. See Cayley–Hamilton theorem. –  Felix Marin Sep 8 '14 at 12:57
upps !! My bad. didn't noticed –  Anjan3 Sep 8 '14 at 17:07

$$A^{1000}= A(A^3)^{333}=A (-2A^2)^{333}=(-2)^{333}A^{667}=\cdots$$

-