# Find large power of a non-diagonalisable matrix

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?

• You can use the Cayley-Hamilton theorem to obtain constants $a,\,b,\,c$ with $A^3=aA^2+bA+cI$, so $A^{n+3}=aA^{n+2}+bA^{n+1}+cA^n$. You can then find $A^{30}$ by recurrence. In fact, you can combine with this the technique in mathematician's answer, e.g. get $A^4$ in terms of $I,\,A,\,A^2$, square to get $A^8$ etc. – J.G. Aug 21 '16 at 7:05
• You can write the matrix in Jordan form, $A=PJP^{-1}$, and then use standard results about powers of Jordan matrices. – symplectomorphic Aug 21 '16 at 7:09

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

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.

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.

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

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.