Find large power of a non-diagonalisable matrix

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

Solution 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.