12
$\begingroup$

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.

$\endgroup$
32
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Cute! Mathematical Cuteness buys a +1 on my books! $\endgroup$ – Robert Lewis Apr 5 '14 at 22:44
  • $\begingroup$ Answered my question, thanks a lot! $\endgroup$ – surfer1311 Apr 5 '14 at 23:11
  • $\begingroup$ 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. $\endgroup$ – Takide May 6 at 15:08
13
$\begingroup$

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.

Full answer:

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$

$\endgroup$
  • $\begingroup$ Would you like me to write down entire solution for you? or are you fine for now :)? $\endgroup$ – Oria Gruber Apr 5 '14 at 22:55
  • 2
    $\begingroup$ Wrote it down anyway. $\endgroup$ – Oria Gruber Apr 5 '14 at 23:07
  • 1
    $\begingroup$ OP Should accept this answer instead $\endgroup$ – Takide May 6 at 15:11
6
$\begingroup$

$\newcommand{\+}{^{\dagger}} \newcommand{\angles}[1]{\left\langle\, #1 \,\right\rangle} \newcommand{\braces}[1]{\left\lbrace\, #1 \,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\, #1 \,\right\rbrack} \newcommand{\ceil}[1]{\,\left\lceil\, #1 \,\right\rceil\,} \newcommand{\dd}{{\rm d}} \newcommand{\down}{\downarrow} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,{\rm e}^{#1}\,} \newcommand{\fermi}{\,{\rm f}} \newcommand{\floor}[1]{\,\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}[1]{\left\vert #1\right\rangle} \newcommand{\ol}[1]{\overline{#1}} \newcommand{\pars}[1]{\left(\, #1 \,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\pp}{{\cal P}} \newcommand{\root}[2][]{\,\sqrt[#1]{\vphantom{\large A}\,#2\,}\,} \newcommand{\sech}{\,{\rm sech}} \newcommand{\sgn}{\,{\rm sgn}} \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}} \newcommand{\ul}[1]{\underline{#1}} \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert} \newcommand{\wt}[1]{\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[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} $$

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – Anjan3 Sep 8 '14 at 7:57
  • 1
    $\begingroup$ @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. $\endgroup$ – Felix Marin Sep 8 '14 at 12:57
  • $\begingroup$ upps !! My bad. didn't noticed $\endgroup$ – Anjan3 Sep 8 '14 at 17:07
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.