<p>As you note, computing $A^m$ can be done in $O(\log m)$ times the number of operations for matrix multiplication on $N \times N$ matrices. The answer to your second question is no, at least for asymptotic complexity -- matrix squaring and matrix multiplication have equivalent time/arithmetic complexity (up to constant factors). Reducing squaring to matrix multiplication is obvious. To reduce multiplication to squaring, suppose we wish to compute the product of $A$ and $B$. Form the $2n \times 2n$ matrix $C$ with the block structure:</p>

<p>$[0~~A]$</p>

<p>$[B~~0]$</p>

<p>That is, $C$ has an $n \times n$ all-zeroes matrix in its upper-left quadrant and lower-right quadrant. Note that $C^2$ contains $A\cdot B$ in its upper-left quadrant.</p>

CC BY-SA 3.0
2012-04-14T13:32:40.987Z
I had recently asked a [question](http://cs.stackexchange.com/questions/1147/complexity-of-computing-matrix-powers) at cs.SE about the complexity of computing $A^m$ in the special case where m=$\mathcal O(n)$. It is easy to give a $\mathcal O(M(n)\log(n))$ upper bound, but the best lower bound I can give is $\mathcal \Omega (M(n))$. Do you have any comments about this problem? I think a lot of interesting problems reduce to this special case.
Shitikanth
CC BY-SA 3.0
2012-04-13T00:34:16.463Z
2012-04-13T00:34:16.463Z
Ryan Williams
<p>Suppose we are given a matrix $A \in \mathbb R^{N\times N}$, and let $m \in \mathbb N_0$. How fast can we compute the power $A^m$ of that matrix?</p>

<p>The next best thing in comparison to computing $m$-products is to utilize fast exponentation, that requires $\mathcal O(\log m )$ matrix products.</p>

<p>For diagonalizable matrices, the eigenvalue decomposition can be used. It's natural generalization, Jordan decomposition, is unstable under pertubation and therefore does not count (afaik).</p>

<p><em>Can matrix exponentiation in the general case be sped up?</em></p>

<p>Fast exponentation suggest a variation of this question is useful, too:</p>

<p><em>Can the square of a general matrix $A$ be computed faster than by known matrix multiplication algorithms?</em></p>

CC BY-SA 3.0
2012-04-12T19:08:07.330Z
If you care about stability under perturbations, fast exponentiation doesn't seem safe, either.
Mahdi Cheraghchi
CC BY-SA 3.0
2012-04-12T19:57:11.103Z
Well, I assume it is no less safe than repeated multiplication, which is as safe as scalar exponentation, isn't it?
shuhalo
<ds.algorithms><matrices><na.numerical-analysis>
How to compute powers of square matrices?
shuhalo
# How to compute powers of square matrices?

(Asked by: username_0 on 2012-04-12)

Suppose we are given a matrix $A \in \mathbb R^{N\times N}$, and let $m \in \mathbb N\_0$. How fast can we compute the power $A^m$ of that matrix?

The next best thing in comparison to computing $m$-products is to utilize fast exponentation, that requires $\mathcal O(\log m )$ matrix products.

For diagonalizable matrices, the eigenvalue decomposition can be used. It's natural generalization, Jordan decomposition, is unstable under pertubation and therefore does not count (afaik).

*Can matrix exponentiation in the general case be sped up?*

Fast exponentation suggest a variation of this question is useful, too:

*Can the square of a general matrix $A$ be computed faster than by known matrix multiplication algorithms?*

**Tags:** ds.algorithms, matrices, na.numerical-analysis

> **Comments:**
> **username_1**: If you care about stability under perturbations, fast exponentiation doesn't seem safe, either.  
> **username_0**: Well, I assume it is no less safe than repeated multiplication, which is as safe as scalar exponentation, isn't it?  

---

## 1 answers

### Answer by username_2 on 2012-04-13. Score: 20

As you note, computing $A^m$ can be done in $O(\log m)$ times the number of operations for matrix multiplication on $N \times N$ matrices. The answer to your second question is no, at least for asymptotic complexity -- matrix squaring and matrix multiplication have equivalent time/arithmetic complexity (up to constant factors). Reducing squaring to matrix multiplication is obvious. To reduce multiplication to squaring, suppose we wish to compute the product of $A$ and $B$. Form the $2n \times 2n$ matrix $C$ with the block structure:

$[0~~A]$

$[B~~0]$

That is, $C$ has an $n \times n$ all-zeroes matrix in its upper-left quadrant and lower-right quadrant. Note that $C^2$ contains $A\cdot B$ in its upper-left quadrant.

> **Comments:**
> **username_3**: I had recently asked a [question](http://cs.stackexchange.com/questions/1147/complexity-of-computing-matrix-powers) at cs.SE about the complexity of computing $A^m$ in the special case where m=$\mathcal O(n)$. It is easy to give a $\mathcal O(M(n)\log(n))$ upper bound, but the best lower bound I can give is $\mathcal \Omega (M(n))$. Do you have any comments about this problem? I think a lot of interesting problems reduce to this special case.  

---

