I've found the following method to compute $M^p$ for $M\in\mathscr M_n(\mathbb K)$:
Let us suppose that $M$ has $n$ distinct eigenvalues $a_1, \dots, a_n$. We compute the characteristic polynomial $\chi_M$ and its roots. Then we compute the rest $R_p$ of the Euclidean division of $X^p$ by $\chi_M$. Thanks to Lagrange's polynomials, we have: $R_p = \sum_i a_i^p L_i$ where $L_i = \prod_{j, j\ne i}\dfrac{X-a_j}{a_i-a_j}$.
The matrices $L_i(M)$ are independent of $p$ and can be pre-computed. Once these matrices are know, we can easily compute $M^p = R_p(M)$, without any matrix multiplication.
However, the pre-computation cost seems huge: $n(n-2)$ matrix multiplications to compute all the $L_i(M)$.
So here are my questions:
- can we improve the cost of the pre-computation?
- is this method (or approaching) used/studied/known somewhere?