Prove that $A^{10}$ is equal to linear combination of $A^k, k = 1,...,9$ and identity matrix. Let $A=\begin{bmatrix}2&0&1\\0&1&0\\1&0&1\end{bmatrix}$. 
I did this with brute force and it was messy, is there a more theoretical way?  
 A: Using the Cayley Hamilton Theorem, there is a polynomial $\rho$ such that $\rho(A)=0$. Where it is understood that the RHS is the $3\times 3$ zero matrix. This polynomial is:
$$
\rho(t) = \det (A-t\cdot I) = (1-t)(t^2-3t+1)=-t^3+4t^2-4t+1
$$
This gives that $$\rho(A) =-A^3+4A^2-4A+I = 0$$
In particular,
$$
A^3 = 4A^2-4A+I \; \; \; \; (1)
$$
Thus,
$$
A^{10}=4A^9-4A^8+A^7
$$
In fact, we can write $A^{10}$ as a linear combination of $A$, $A^2$, and $I$ by using equation $(1)$, many times. 
For example, Equation $(1)$ gives:
$$
A^4 = 4A^3-4A^2+A = 4(4A^2-4A+I)-4A^2+I
$$
A: Note that $\chi_A(x) = x^3-4 x^2+4 x -1$, and each eigenvalue $\lambda$ of $A$ satisfies $\chi_A(\lambda) = 0$. In particular, we have
$\lambda^3 = 4 \lambda^2-4 \lambda +1$ for each eigenvalue. It follows from this that we can write $\lambda^{10} = p(\lambda)$, where $p$ is a polynomial of degree at most 2.
It is not hard to show that $A$ has distinct eigenvalues ($\lambda=1$ is straightforward), so we have some $V$ such that
$V^{-1} A V = \Lambda$, where $\Lambda$ is a diagonal matrix of eigenvalues.
It follows that $\Lambda^{10} = p(\Lambda)$, and so
$V \Lambda^{10} V^{-1} = V p(\Lambda^{10}) V^{-1} = p(V \Lambda^{10} V^{-1})$, which gives $A^{10} = p(A)$.
A: The characteristic polynomial of $A$ is 
$$P_A(t)= \det (t I_3 - A) = t^3- 4 t^2 + 4 t  -1$$
The matrix $A$ satisfies the polynomial equality
$$P_A(A) = A^3 - 4A^2 + 4A - 1 =0$$
and therefore $A^3 = 4A^2 - 4A + 1$ and so $A^{10} = A^7(2A-1)^2$, a polynomial of degree $9$. 
We can find a unique polynomial $R(t)$ of degree $2$ that satisfies $A^{10}= R(A)$; $R(t)$ is the remainder of the division of $t^{10}$ by $P_A(t)$. We have 
$$t^{10} = ( t^3- 4 t^2 + 4 t  -1) ( t^7+4 t^6+12 t^5+33 t^4+88 t^3+232 t^2+609 t+1596)+\\ +\,4180 t^2-5775 t+1596$$ 
and so 
$$A^{10} = 4180\, A^2-5775\, A+1596$$
Obs: $4180 t^2-5775 t+1596$ is the unique polynomial of degree $\le 2$ that coincides with $t^{10}$ on the set of zeroes $\{1, \frac{3 + \sqrt{5}}{2}, \frac{3 - \sqrt{5}}{2}\}$ of the polynomial $P_A(t)$ -- the eigevalues of $A$.
