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
• This is not the optimal method to do this - You should instead find a polynomial that agrees with the characteristic polynomial over the domain of interest. Such a polynomial only has terms with a maximum power being A^3. – Takide May 6 at 15:08

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
• OP Should accept this answer instead – Takide May 6 at 15:11

$\newcommand{\+}{^{\dagger}} \newcommand{\angles}{\left\langle\, #1 \,\right\rangle} \newcommand{\braces}{\left\lbrace\, #1 \,\right\rbrace} \newcommand{\bracks}{\left\lbrack\, #1 \,\right\rbrack} \newcommand{\ceil}{\,\left\lceil\, #1 \,\right\rceil\,} \newcommand{\dd}{{\rm d}} \newcommand{\down}{\downarrow} \newcommand{\ds}{\displaystyle{#1}} \newcommand{\expo}{\,{\rm e}^{#1}\,} \newcommand{\fermi}{\,{\rm f}} \newcommand{\floor}{\,\left\lfloor #1 \right\rfloor\,} \newcommand{\half}{{1 \over 2}} \newcommand{\ic}{{\rm i}} \newcommand{\iff}{\Longleftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\isdiv}{\,\left.\right\vert\,} \newcommand{\ket}{\left\vert #1\right\rangle} \newcommand{\ol}{\overline{#1}} \newcommand{\pars}{\left(\, #1 \,\right)} \newcommand{\partiald}[]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\pp}{{\cal P}} \newcommand{\root}[]{\,\sqrt[#1]{\vphantom{\large A}\,#2\,}\,} \newcommand{\sech}{\,{\rm sech}} \newcommand{\sgn}{\,{\rm sgn}} \newcommand{\totald}[]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}} \newcommand{\ul}{\underline{#1}} \newcommand{\verts}{\left\vert\, #1 \,\right\vert} \newcommand{\wt}{\widetilde{#1}}$ $$\expo{At}=\alpha\pars{t} + \beta\pars{t}A + \gamma\pars{t}A^{2}$$

$$\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{\pars{\expo{At}}}{t}\right\vert_{t = 0} =\left. {A^{2} \over 4}\, \totald{\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$$

Set $X_n=A^n$ since, $A^3 =2A^2$ then, we have $$X_{n+3} = A^{n+3} = 2A^2A^n = 2X_{n+2}$$ Hence, $(X_n)_n$ is geometric and $$X_n =2^{n-2}X_2\Longleftrightarrow A^n =2^{n-2} A^2$$ that is for $n=1000$ we get $$A^{1000} = 2^{998}A^2$$