Matrix to power 30 using eigen values issue

Question

$$ \text{If matrix } A = \begin{bmatrix} 1 & 0 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 0 \end{bmatrix} \text{ then find } A^{30}.$$

I tried to approach through diagonalization using eigen values method.

I got eigen values as $-1, 1, 1$

As per diagonalization $ A = P*D*P^{-1}.$ So $ A^{30} = P*D^{30}*P^{-1}. $ But $ D^30 = I.$

So, $ A^{30} = P*I*P^{-1} = I $

But $ A^{30} $ is not equal to I. If we do general multiplication without all these.

Where is the mistake in my approach?

Answer 1

You have computed the eigenvalues of $A$ to be $\{-1, 1, 1\}$. The repeated eigenvalue may be an obstacle to diagonalization. In this case, the geometric and algebraic multiplicities of the eigenvalue $1$ are different, so A is not diagonalizable. You continued as if $A$ were diagonalizable, so this is the mistake in your approach.

You have added a follow-on question in comments (instead of to your question, so you should not be surprised if other answers do not address it). I see that others have demonstrated Jordan normal form and induction. Another method is binary decomposition of the exponent and repeated squaring to get power-of-$2$ powers of $A$: \begin{align*} A^1 &= \begin{pmatrix} 1 & 0 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 0 \end{pmatrix} \text{,} \\ A^2 &= A^1 \cdot A^1 = \begin{pmatrix} 1 & 0 & 0 \\ 1 & 1 & 0 \\ 1 & 0 & 1 \end{pmatrix} \text{,} \\ A^4 &= A^2 \cdot A^2 = \begin{pmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ 2 & 0 & 1 \end{pmatrix} \text{,} \\ A^8 &= A^4 \cdot A^4 = \begin{pmatrix} 1 & 0 & 0 \\ 4 & 1 & 0 \\ 4 & 0 & 1 \end{pmatrix} \text{,} \\ A^{16} &= A^8 \cdot A^8 = \begin{pmatrix} 1 & 0 & 0 \\ 8 & 1 & 0 \\ 8 & 0 & 1 \end{pmatrix} \text{,} \\ A^{30} = A^{11110_{\,2}} &= A^{16}\cdot A^8 \cdot A^4 \cdot A^2 = \begin{pmatrix} 1 & 0 & 0 \\ 15 & 1 & 0 \\ 15 & 0 & 1 \end{pmatrix} \text{.} \end{align*} Of course, after computing $A^4$ or $A^8$, perhaps one would notice the pattern...

There is a slightly faster way to get there using the above method. $A^{-1}$ is easy enough to compute (using the minors method, for example). $$ A^{-1} = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 0 & 1 \\ -1 & 1 & 0 \end{pmatrix} $$ Then, $A^{30} = (A^{15})^2 = (A^{16} \cdot A^{-1})^2$. This replaces three multiplies with a multiply and an inverse. Continuing to think about this leads to the computationally intractable problem of optimal addition chains.

Answer 2

Since $A$ is not diagonalizable we can use Jordan form

\begin{align} A^{30} &= \begin{pmatrix} 0 & 2 & 0 \\ -1 & 1 & 1 \\ 1 & 0 & 1 \end{pmatrix} \begin{pmatrix} -1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 1 & 1 \end{pmatrix}^{30} \begin{pmatrix} 1/4 & -1/2 & 1/2 \\ 1/2 & 0 & 0 \\ -1/4 & 1/2 & 1/2 \end{pmatrix} \\ &= \begin{pmatrix} 0 & 2 & 0 \\ -1 & 1 & 1 \\ 1 & 0 & 1 \end{pmatrix} \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 30 & 1 \end{pmatrix} \begin{pmatrix} 1/4 & -1/2 & 1/2 \\ 1/2 & 0 & 0 \\ -1/4 & 1/2 & 1/2 \end{pmatrix} \\ &= \begin{pmatrix} 1 & 0 & 0 \\ 15 & 1 & 0 \\ 15 & 0 & 1 \end{pmatrix} \end{align}

Answer 3

In another way

$$ \eqalign{ & A = \left( {\matrix{ 1 & 0 & 0 \cr 1 & 0 & 1 \cr 0 & 1 & 0 \cr } } \right)\quad A^{\,2} = \left( {\matrix{ 1 & 0 & 0 \cr 1 & 1 & 0 \cr 1 & 0 & 1 \cr } } \right)\quad A^{\,2n} = \left( {\matrix{ 1 & 0 & 0 \cr n & 1 & 0 \cr n & 0 & 1 \cr } } \right) \cr & A^{\,30} = \left( {\matrix{ 1 & 0 & 0 \cr {15} & 1 & 0 \cr {15} & 0 & 1 \cr } } \right) \cr} $$