$A^m = r_m(A)?$ Power of a matrix! In my Linear Algebra textbook we are reading, the following is stated for computing the power of a matrix in one of the advanced chapters as an exercise, $A^m = r_m(A)$. $r_m (A)$ is the remainder from the division algorithm given by the polynomial $x^m =q_m(x)p(x) +r_m(x)$. 
Since this is exercise, no details are given. I am highly interested in how exactly this is suppose to work because computing $A^2,A^3,...,$ can be tiresome. So I was wondering if anyone knew of any articles that discusses the details of how this works in depth?
 A: The result is simply that when $A$ satisfies a polynomial relation $p[A]=0$, then for any other polynomial in$~A$, for instance for $x^m[A]=A^m$, the result does not change if you modify the polynomial (here $x^m$) by a multiple of $p$; therefore if $r$ is the remainder after dividing your polynomial $x^m$ by $p$ (which by definition differs from $x^m$ by a multiple of$~p$), then one has $A^m=x^m[A]=r[A]$.
Moreover, such a polynomial $p$ exists for every square matrix$~A$. The monic polynomial $p$ of smallest degree with $p[A]=0$ is called the minimal polynomial of$~A$, and it can be found by computing $I,A,A^2,\ldots$ until one of them is a linear combination of the previous powers, which is bound to happen for $A^n$ or before. (There are somewhat faster ways to find it too.) For almost all matrices the first relation is for $A^n$, in which case $p$ will coincide with the characteristic polynomial$~\chi_A$ by the Cayley-Hamilton theorem, which says that $\chi_A[A]=0$ in all cases, so one could use $p=\chi_A$ in the computation, even in the rare cases where it is not minimal.
All in all the computation of $A^m$ is reduced to the computation of $p$ (independently of$~m$), the computation of the remainder of $x^m$ in polynomial division by$~p$, and the computation of $r[A]$ which involves at most the powers $A^0,A,A^2,\ldots,A^{n-1}$ of$~A$, which can also be computed independently of$~m$. The polynomial division is what takes most time, though it is quite fast when $m$ is moderately large (since $A^m$ grows exponentially with $m$, there will probably be serious problems in representing it in the first place if $m$ is really large). One can still apply powering by repeated squaring here: to compute the remainder molulo$~p$ of $x^{2k}$ or of $x^{2k+1}$, first (recursively) compute the remainder $r_k$ of $x^k$, and then reduce $r_k^2$ respectively $xr_k^2$ modulo$~p$ by another (short) polynomial division.
A: If I remember correctly, it is the Cayley-Hamilton theorem.
