Find large power of a non-diagonalisable matrix

Question

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

The problem here is that it has only two eigenvectors, $\begin{bmatrix}0\\1\\1\end{bmatrix}$ corresponding to eigenvalue $1$ and $\begin{bmatrix}0\\1\\-1\end{bmatrix}$ corresponding to eigenvalue $-1$. So, it is not diagonalizable.

Is there any other way to compute the power?

Answer 1

Notice the characteristic polynomial of $A$ is $$\chi_A(\lambda) \stackrel{def}{=}\det(\lambda I_3 - A) = \lambda^3-\lambda^2-\lambda+1 = (\lambda^2-1)(\lambda-1)$$ By Cayley-Hamilton theorem, we have

$$\chi_A(A) = (A^2 - I)(A-I) = 0 \quad\implies (A^2-I)^2 = (A^2-I)(A-I)(A+I) = 0$$

This means $A^2-I$ is nilpotent. In following binary expansion of $A^{30}$

$$A^{30} = (I + (A^2 - I))^{15} = \sum_{k=0}^{15} \binom{15}{k}(A^2-I)^k$$

only the term $k = 0$ and $1$ contributes. i.e.

$$A^{30} = I + 15 (A^2-I) = \begin{bmatrix} 1 & 0 & 0\\ 15 & 1 & 0\\ 15 & 0 & 1 \end{bmatrix} $$

Answer 2

You can use repeated squaring to efficiently compute large powers.

$$ A^{30} = A^{16} \cdot A^8 \cdot A^4 \cdot A^2$$

where $A^4 = {A^2} ^2$, $A^8= {A^4}^2$, etc.

Answer 3

Generalized eigenvector $\;u_1=\begin{pmatrix}a\\b\\c\end{pmatrix}\;$for $\;\lambda=1\;$ :

$$Au_1=1\cdot u_1+v_1\iff \begin{pmatrix}a\\a+c\\b\end{pmatrix}=\begin{pmatrix}a\\b\\c\end{pmatrix}+\begin{pmatrix}0\\1\\1\end{pmatrix}\implies \begin{cases}b=c+1\\{}\\a+c=b+1\end{cases}\implies \begin{cases}a=2\\{}\\b=1\\{}\\c=0\end{cases}$$

$$\implies u_1=\begin{pmatrix}2\\1\\0\end{pmatrix}\;,\;\;\text{so define}\;\;P:=\begin{pmatrix}0&2&0\\1&1&1\\1&0&\!\!-1\end{pmatrix}\implies P^{-1}=\frac14\begin{pmatrix}\!\!-1&2&2\\2&0&0\\\!\!-1&2&\!\!-2\end{pmatrix}$$

and now:

$$P^{-1}AP=\frac14\begin{pmatrix}\!\!-1&2&2\\2&0&0\\\!\!-1&2&\!\!-2\end{pmatrix}\begin{pmatrix}1 & 0 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 0 \end{pmatrix}\begin{pmatrix}0&2&0\\1&1&1\\1&0&\!\!-1\end{pmatrix}=\begin{pmatrix}1&1&0\\0&1&0\\0&0&\!\!-1\end{pmatrix}\implies$$

$$A^{30}=P\begin{pmatrix}1&1&0\\0&1&0\\0&0&\!\!-1\end{pmatrix}P^{-1}$$

You can now check that taking powers of the above quasi-diagonal matrix ( i.e., the Jordan Canonical Form for $\;A\;$) is very easy, though not as easy as with diagonal matrices, of course.

Answer 4

Since the given matrix is rather simple, you could also compute a few powers:

\begin{align*} A^1&= \begin{pmatrix} 1 & 0 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 0 \end{pmatrix}\\ A^2&= \begin{pmatrix} 1 & 0 & 0 \\ 1 & 1 & 0 \\ 1 & 0 & 1 \end{pmatrix}\\ A^3&= \begin{pmatrix} 1 & 0 & 0 \\ 2 & 0 & 1 \\ 1 & 1 & 0 \end{pmatrix}\\ A^4&= \begin{pmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ 2 & 0 & 1 \end{pmatrix}\\ A^5&= \begin{pmatrix} 1 & 0 & 0 \\ 3 & 0 & 1 \\ 2 & 1 & 0 \end{pmatrix}\\ A^6&= \begin{pmatrix} 1 & 0 & 0 \\ 3 & 1 & 0 \\ 3 & 0 & 1 \end{pmatrix}\\ \end{align*}

Can you notice some kind of pattern and prove it by induction? (Or, if you prefer, you can do the same thing with $B=A^2$ and try to find general form of $B^n$.)

---

Of course, this is "naive" approach - without using any theory you have learned about matrices. For more complicated matrices it would be rather difficult to spot some kind of pattern. That's why methods which work for arbitrary matrices are more useful.

Answer 5

Given $\mathrm A$, we compute one Jordan decomposition, $\mathrm A = \mathrm P \mathrm J \mathrm P^{-1}$, where

$$\mathrm J = \begin{bmatrix} -1 & 0 & 0\\ 0 & 1 & 1\\ 0 & 0 & 1\end{bmatrix}$$

Note that $\mathrm A^{30} = \mathrm P \mathrm J^{30} \mathrm P^{-1}$. Since $(-1)^{30} = 1$ and $\begin{bmatrix} 1 & 1\\ 0 & 1\end{bmatrix}^{30} = \begin{bmatrix} 1 & 30\\ 0 & 1\end{bmatrix}$, we have

$$\mathrm J^{30} = \begin{bmatrix} 1 & 0 & 0\\ 0 & 1 & 30\\ 0 & 0 & 1\end{bmatrix}$$

Thus,

$$\mathrm A^{30} = \mathrm P \mathrm J^{30} \mathrm P^{-1} = \cdots = \begin{bmatrix} 1 & 0 & 0\\ 15 & 1 & 0\\ 15 & 0 & 1\end{bmatrix}$$