<p>In answer to the "Update": yes, for any $c$, the existence of an $O(n^c)$ non-commutative algorithm for matrix multiplication is <em>equivalent</em> to the existence of an $O(n^c)$ commutative algorithm for matrix multiplication (I am assuming, here, that all algorithms are algebraic, in the sense of algebraic circuits). This is because any algebraic circuit computing a bilinear map can be converted into a bilinear circuit at the expense of at most a factor of 2 in the size.</p>

CC BY-SA 3.0
2015-05-20T17:25:52.533Z
It is interesting that commutative algorithm can give rise to a non-commutative algorithm.
Turbo
CC BY-SA 3.0
2015-05-20T18:34:08.157Z
It is interesting, but it is a simple consequence of the fact that the algorithms are bilinear.
Greg Kuperberg
CC BY-SA 3.0
2015-05-20T15:21:13.183Z
2015-05-20T15:21:13.183Z
Joshua Grochow
<p>Commutative algorithms
are not studied that much, because you cannot use them
recursively by cutting larger matrices into smaller blocks like you do in Strassen's algorithm. </p>

<p>Since every noncommutative algorithm is a commutative one, commutative algorithms can be trivially as efficient as noncommutative ones.</p>

CC BY-SA 3.0
2013-06-17T07:46:08.250Z
2013-06-17T07:46:08.250Z
Markus Bläser
<p>What is known about commutative algorithms like Winograd algorithm and its variants for Matrix Multiplication? Why is there not much study on them? Can they be asymptotically as efficient as Non-commutative algorithms?</p>

<p><strong>Update</strong></p>

<p>Existence of $O(n^\omega)$ non-commutative algorithms for matrix multiplication implies existence of $O(n^\omega)$ commutative algorithms. Does converse statement hold truth?</p>

<algebraic-complexity><matrix-product>
Commutative matrix multiplication algorithms
Turbo
# Commutative matrix multiplication algorithms

(Asked by: username_0 on 2013-06-16)

What is known about commutative algorithms like Winograd algorithm and its variants for Matrix Multiplication? Why is there not much study on them? Can they be asymptotically as efficient as Non-commutative algorithms?

**Update**

Existence of $O(n^\omega)$ non-commutative algorithms for matrix multiplication implies existence of $O(n^\omega)$ commutative algorithms. Does converse statement hold truth?

**Tags:** algebraic-complexity, matrix-product

---

## 2 answers

### Answer by username_1 on 2015-05-20. Score: 7 | Accepted answer

In answer to the "Update": yes, for any $c$, the existence of an $O(n^c)$ non-commutative algorithm for matrix multiplication is *equivalent* to the existence of an $O(n^c)$ commutative algorithm for matrix multiplication (I am assuming, here, that all algorithms are algebraic, in the sense of algebraic circuits). This is because any algebraic circuit computing a bilinear map can be converted into a bilinear circuit at the expense of at most a factor of 2 in the size.

> **Comments:**
> **username_0**: It is interesting that commutative algorithm can give rise to a non-commutative algorithm.  
> **username_2**: It is interesting, but it is a simple consequence of the fact that the algorithms are bilinear.  

---

### Answer by username_3 on 2013-06-17. Score: 5

Commutative algorithms
are not studied that much, because you cannot use them
recursively by cutting larger matrices into smaller blocks like you do in Strassen's algorithm.

Since every noncommutative algorithm is a commutative one, commutative algorithms can be trivially as efficient as noncommutative ones.


---

