# fast multiplication of power of a matrix by a vector

I'm interested in computing of the product $$M^n v$$, where $$M$$ is an $$m\times m$$ matrix (over a semiring) and $$v$$ is column-vector, with the smallest number of multiplications in the underlying semiring and in the regime of $$n=\Theta(m)$$.

If we first compute $$M^n$$ using fast exponentiation, this would take $$\Theta(\log n)$$ matrix multiplications, totaling in $$\Theta(m^3\log n)$$ semiring multiplications (assuming naive matrix multiplication).

On the other hand, if we just iteratively compute $$M^k v$$ for $$k=1,2,\dots,n$$, each time multiplying a vector by $$M$$, then it'd take us $$\Theta(m^2n)$$ semiring multiplications.

So, fast exponentiation appears to be useless. Is there any other way to speed up things here?

• Is $M$ a diagonalizable matrix? Or maybe can be converted to Jordan normal form? In that case, this might help you. Commented Jan 20, 2022 at 22:31
• @nirshahar: Diagonalizable matrices exist over fields, in my case matrix is over a semiring, which in fact contains no invertible elements except the multiplicative identity. Commented Jan 20, 2022 at 23:40