Calculating the nth power of a matrix

[PainterGuy]

Homework Statement

I'm trying to find the nth power of a matric.

Relevant Equations

I've presented my work below.

Mentor note: Since the technique used here involves differentiation, I moved this to the Calculus section.
Hi,

I was trying to do the problem below. I was following the approach presented in this answer. I assume the approach is correct. The answer I ended up with is clearly wrong. Where am I going wrong? Thanks for your help, in advance!

 

[haruspex]

You say the roots are 1,0,0. That would have a factor x².
You lost me after finding c=0. Why not substitute the other root value to get another equation relating a, b, c? Then differentiate and substitute the repeated root again (because the Q term will vanish again).

 

[Mark44]

You say the roots are 1,0,0. That would have a factor x2.

No, the roots of the equation $x(x^2 - 2x + 1) = 0$ are 0, 1, 1, so A and A - I would be roots of the characteristic equation. This error also occurs in the OP.

 

[SammyS]

Homework Statement:: I'm trying to find the nth power of a matric.
Relevant Equations:: I've presented my work below.

Hi,

I was trying to do the problem below. I was following the approach presented in this answer. I assume the approach is correct. The answer I ended up with is clearly wrong. Where am I going wrong? Thanks for your help, in advance!

Is it necessary for you to use Cayley-Hamilton?

There is a much easier way in the case of the matrix you are working with.

 

[Mark44]

Homework Statement:: I'm trying to find the nth power of a matric.
Relevant Equations:: I've presented my work below.

Hi,

I was trying to do the problem below. I was following the approach presented in this answer. I assume the approach is correct. The answer I ended up with is clearly wrong. Where am I going wrong? Thanks for your help, in advance!

View attachment 279972
View attachment 279973

If you can take the time to write this all up in Word or whatever, and then post it as an image, you certainly would have time to make life easier for us by writing it up in LaTeX. Everything you have done here could have been done using LaTeX. At the lower left corner there's a link to our tutorial.

The colors and boxes in your image are nice, but posting your work as an image makes it impossible for us to pinpoint the exact line where you have made a mistake.

In any case, in the remainder polynomial $ax^2 + bx + c$, your value for c is correct (c = 0), but your values for a and b are incorrect.

For arbitrary n, I get a = n - 1 and b = 2 - n. If n = 10, I get a = 9 and b = -8. I checked my work by calculating $A^4$. Here n = 4, so a = 3 and b = -2.
I compared my answers by calculating $A^4$ directly and by using the formula $A^4 = aA^2 + bA = 4A^2 - 2A$, with both producing exactly the same result.

 

[Fred Wright]

To avoid complicated algebra let's look at $\mathbf {A}^2$
$$

\begin{pmatrix}
1 & 1 & 0 \\
0 & 0 & 1 \\
0 & 0 & 1
\end{pmatrix}
\begin{pmatrix}
1 & 1 & 0 \\
0 & 0 & 1 \\
0 & 0 & 1
\end{pmatrix}

=
\begin{pmatrix}
1 & 1 & 1 \\
0 & 0 & 1 \\
0 & 0 & 1
\end{pmatrix}

$$
Now evaluate $\mathbf {A}^3$
$$
\begin{pmatrix}
1 & 1 & 0 \\
0 & 0 & 1 \\
0 & 0 & 1
\end{pmatrix}
\begin{pmatrix}
1 & 1 & 1 \\
0 & 0 & 1 \\
0 & 0 & 1
\end{pmatrix}

=
\begin{pmatrix}
1 & 1 & 2 \\
0 & 0 & 1 \\
0 & 0 & 1
\end{pmatrix}

$$
Now $\mathbf {A}^4$
$$
\begin{pmatrix}
1 & 1 & 0 \\
0 & 0 & 1 \\
0 & 0 & 1
\end{pmatrix}
\begin{pmatrix}
1 & 1 & 2 \\
0 & 0 & 1 \\
0 & 0 & 1
\end{pmatrix}

=
\begin{pmatrix}
1 & 1 & 3 \\
0 & 0 & 1 \\
0 & 0 & 1
\end{pmatrix}

$$
Do you see a pattern?

 

[haruspex]

No, the roots of the equation $x(x^2 - 2x + 1) = 0$ are 0, 1, 1, so A and A - I would be roots of the characteristic equation. This error also occurs in the OP.

Which is the error I was drawing attention to ("you say...").
As you note, posting as an image, with no equation numbers, makes it hard to point to the error, so I quoted the first incorrect statement.
Correcting that and using the corresponding three substitutions (repeated root in the derivative) finds the right a and b quickly. Is that what you did?

 

[haruspex]

To avoid complicated algebra let's look at $\mathbf {A}^2$
$$

\begin{pmatrix}
1 & 1 & 0 \\
0 & 0 & 1 \\
0 & 0 & 1
\end{pmatrix}
\begin{pmatrix}
1 & 1 & 0 \\
0 & 0 & 1 \\
0 & 0 & 1
\end{pmatrix}

=
\begin{pmatrix}
1 & 1 & 1 \\
0 & 0 & 1 \\
0 & 0 & 1
\end{pmatrix}

$$
Now evaluate $\mathbf {A}^3$
$$
\begin{pmatrix}
1 & 1 & 0 \\
0 & 0 & 1 \\
0 & 0 & 1
\end{pmatrix}
\begin{pmatrix}
1 & 1 & 1 \\
0 & 0 & 1 \\
0 & 0 & 1
\end{pmatrix}

=
\begin{pmatrix}
1 & 1 & 2 \\
0 & 0 & 1 \\
0 & 0 & 1
\end{pmatrix}

$$
Now $\mathbf {A}^4$
$$
\begin{pmatrix}
1 & 1 & 0 \\
0 & 0 & 1 \\
0 & 0 & 1
\end{pmatrix}
\begin{pmatrix}
1 & 1 & 2 \\
0 & 0 & 1 \\
0 & 0 & 1
\end{pmatrix}

=
\begin{pmatrix}
1 & 1 & 3 \\
0 & 0 & 1 \\
0 & 0 & 1
\end{pmatrix}

$$
Do you see a pattern?

That works, but the OP wouldn’t have learned much. The method used should have worked, and the OP needs to learn how to use it.

 

[Mark44]

Correcting that and using the corresponding three substitutions (repeated root in the derivative) finds the right a and b quickly. Is that what you did?

No, not really. I found it easier to follow the SE article, in which there were a couple of techniques. The first one shown is IMO more straightforward, but the OP seems to have been attempting the second technique.

By Cayley-Hamilton, every matrix is a root of its characteristic polynomial, which in this case is $P(x) = x^3 - 2x^2 + x$. (I verified that this char. polynomial is correct.) Hence $P(A ) = A^3 - 2A^2 + A = 0$.
From this we have $A^3 = 2A^2 - A$.

To find, say, $A^5$, multiply both sides of the equation above by $A^2$, which yields $A^5 = 2A^4 - A^2$. The right side simplifies to $2A\cdot A^3 - A^2$, which can be simplified further by replacing the $A^3$ factor. After all simplifications have been made, you end up with a final expression in terms of only $A^2$ and $A$.
So $A^5 = 4A^2 - 3A$ or ##\begin{bmatrix} 1 & 1 & 4 \\ 0 & 0 & 1 \\ 0 & 0 & 1\end{bmatrix}

 

[haruspex]

No, not really. I found it easier to follow the SE article, in which there were a couple of techniques. The first one shown is IMO more straightforward, but the OP seems to have been attempting the second technique.

By Cayley-Hamilton, every matrix is a root of its characteristic polynomial, which in this case is $P(x) = x^3 - 2x^2 + x$. (I verified that this char. polynomial is correct.) Hence $P(A ) = A^3 - 2A^2 + A = 0$.
From this we have $A^3 = 2A^2 - A$.

To find, say, $A^5$, multiply both sides of the equation above by $A^2$, which yields $A^5 = 2A^4 - A^2$. The right side simplifies to $2A\cdot A^3 - A^2$, which can be simplified further by replacing the $A^3$ factor. After all simplifications have been made, you end up with a final expression in terms of only $A^2$ and $A$.
So $A^5 = 4A^2 - 3A$ or ##\begin{bmatrix} 1 & 1 & 4 \\ 0 & 0 & 1 \\ 0 & 0 & 1\end{bmatrix}

I really meant, is the method I outlined in post #7 how you obtained a and b?
Having found them, we have $A^{10}=9A^2-8A$, so only one matrix multiplication to do.
All the other methods in this thread are rather ad hoc.

 

[Mark44]

I really meant, is the method I outlined in post #7 how you obtained a and b?

Yes, pretty much.

 

[PainterGuy]

Thank you very much, everyone!

My first error was my 'assumption' that the roots are 1,0,0. The roots are actually, 0,1,1.

The second error occurred toward the end when I said "evaluating at x=2". I don't know why I was evaluating it at x=2.

I started with the correct roots and was able to get the correct answer.

If you can take the time to write this all up in Word or whatever, and then post it as an image, you certainly would have time to make life easier for us by writing it up in LaTeX. Everything you have done here could have been done using LaTeX. At the lower left corner there's a link to our tutorial.

The colors and boxes in your image are nice, but posting your work as an image makes it impossible for us to pinpoint the exact line where you have made a mistake.

I agree with you and have tried to address this issue in the past. Unfortunately, the LaTeX code generated by my program always has formatting issues when tried to compile on PF. Please check this: https://www.physicsforums.com/threads/sharing-latex-code.926251/ . Thank you!

 

[vela]

I was trying to do the problem below. I was following the approach presented in this answer. I assume the approach is correct. The answer I ended up with is clearly wrong. Where am I going wrong? Thanks for your help, in advance!

You didn't seem to grasp some of the reasoning behind the solution method.

Suppose $p(x)$ is the characteristic polynomial with $r$ a root. When divide $p$ into $x^n$, you get
$$x^n = p(x) Q(x) + R(x),$$ where $Q(x)$ is unknown. If you set $x=r$, you get
$$r^n = p(r) Q(r) + R(r) = R(r)$$ since $p(r)=0$. So now you have an equation that relates the coefficients of $R(x)$. If, however, you plug in some other value $\beta$ which is not a root of $p$, you get
$$\beta^n = p(\beta)Q(\beta) + R(\beta),$$ which is not very useful as you have no idea what $Q(\beta)$ is equal to. You can't just ignore it as you did in your attempt.

In the example on Stackexchange, the value $x=2$ was used because it was a root of the characteristic polynomial. For your problem, it wasn't a root, so using that value doesn't make sense.

If you have a repeated root $r$, plugging in the same root is obviously going to just give you the same equation, which isn't helpful. To get another independent equation, you can differentiate and then plug in $r$. This works because $r$ is also a root of $p'(x)$. You should be able to convince yourself that if the multiplicity of the root is $m$, then it's a root of $p$, $p'$, ..., $p^{(m-1)}$.

 

[WWGD]

I thought the/a standard method was to test whether the matrix M could be diagonalized into D as :

$M=SDS^{-1}$ so that $M^n= SD^nS^{-1}$

 

[haruspex]

I thought the/a standard method was to test whether the matrix M could be diagonalized into D as :

$M=SDS^{-1}$ so that $M^n= SD^nS^{-1}$

I don’t think that's very different. It still involves finding the eigenvalues, i.e, roots of the characteristic polynomial.

 

[Mark44]

Unfortunately, the LaTeX code generated by my program always has formatting issues when tried to compile on PF.

I don't use any program for the LaTeX I write. Everything I did, with the exception of the matrix, is very simple to do in TeX here at PF. Even the matrix wasn't all that complicated.
Here's my script, which I just typed in. I've modified it slightly so that it won't render in the browser, so you can see what I wrote.
\begin{bmatrix} 1 & 1 & 0 \\\ 0 & 0 & 1 \\\ 0 & 0 & 1 \end{bmatrix}

And here is the same script as it would normally render in the browser.
$\begin{bmatrix} 1 & 1 & 0 \\ 0 & 0 & 1 \\ 0 & 0 & 1 \end{bmatrix}$