4 ms·
Yes, see the Cayley-Hamilton Theorem[1], which changes matrix powering into the powering of scalers in the characteristic polynomial. -- [1] - http://en.wikip
by zheng 15y ago
Yes, see the Cayley-Hamilton Theorem[1], which changes matrix powering into the powering of scalers in the characteristic polynomial.
--
[1] - http://en.wikipedia.org/wiki/Cayley%E2%80%93Hamilton_theorem http://en.wikipedia.org/wiki/Cayley%E2%80%93Hamilton_theorem
- wbhart 15y agoAh yes, one can compute P(x) a polynomial such that P(A) = 0. If you wish to compute A^n for n much bigger than the degree of P you can compute S(x) = x^n mod P(x) and then just compute S(A). However, algorithms that do actually improve the complexity of powering when this technique isn't applicable do exist. Here is a paper on a recent one: http://marco.bodrato.it/papers/Bodrato2010-StrassenLikeMatrixMultiplicationForSquares.pdf http://marco.bodrato.it/papers/Bodrato2010-StrassenLikeMatri...