Skip to main content
3 votes
Accepted

Compute matrix inversion / multiplication using a black box

It was shown in 1969, by Strassen, that matrix multiplication and matrix inversion have the same computational complexity. Details can be found on Wikipedia.
Nathaniel's user avatar
  • 15.7k
1 vote

Complexity of multiplying 3 matrices

No. If you can multiply two $n \times n$ matrices in time $O(f(n))$ then you can also multiply three matrices $A,B,C$ in the same asymptotic running time by first computing $M=AB$ and then $MC$. ...
Steven's user avatar
  • 29.5k

Only top scored, non community-wiki answers of a minimum length are eligible