Matrix multiplication exponent

Remarks

The bound $\omega \ge 2$ holds because the output has $n^2$ entries, and the schoolbook matrix multiplication gives $\omega \le 3$. The Strassen algorithm gave $\omega \le \log_2 7 \approx 2.807$ in 1969. Coppersmith and Winograd obtained $\omega < 2.376$ in 1990. Refinements of their method by several groups since 2010 have brought the upper bound below $2.372$. The problem is open: no lower bound better than $2$ is known. Strassen showed that $\omega$ can be read off from the tensor rank of the matrix multiplication tensor $\langle n, n, n \rangle$. It is the infimum of the $\tau$ such that this rank is $O(n^\tau)$. Many other problems of linear algebra, such as inverting a matrix or computing a determinant, can be solved with $O(n^{\omega + \varepsilon})$ operations for every $\varepsilon > 0$.