Math Conjectures

Matrix Multiplication Exponent ω=2\omega=2

OPENLandmarkConjectureProposed c. 1969 · Standard version

Canonical statement

Over the concrete field Q\mathbb Q, let
ω=inf⁡{τ:two n×n matrices can be multiplied using O(nτ+ε) field operations for every ε>0}. \omega=\inf\{\tau:\text{two }n\times n\text{ matrices can be multiplied using }O(n^{\tau+\varepsilon})\text{ field operations for every } \varepsilon>0\}.
Then
ω=2. \omega=2.
View source LaTeX
Over the concrete field \(\mathbb Q\), let
\[
  \omega=\inf\{\tau:\text{two }n\times n\text{ matrices can be multiplied
  using }O(n^{\tau+\varepsilon})\text{ field operations for every }
  \varepsilon>0\}.
\]
Then
\[
  \omega=2.
\]
TCS-018:[Strassen1969][AlmanVW2021][AlmanEtAl2024Asymmetry]
Theoretical computer scienceAlgebra and representation theory

Notes

The conjecture states that the exponent of matrix multiplication equals two: over Q\mathbb Q, two n×nn\times n matrices can be multiplied in O(n2+ε)O(n^{2+\varepsilon}) arithmetic operations for every ε>0\varepsilon>0. The question dates from around 1969, when Strassen showed that the classical cubic algorithm is not optimal, multiplying matrices with exponent log⁡27\log_2 7 [Strassen1969].

Since the input and output consist of n2n^2 entries, ω≥2\omega\geq 2 trivially, and no lower bound above this is known. On the other side, a long line of tensor-based constructions has driven the upper bound down: the refined laser method [AlmanVW2021] and subsequent asymmetric refinements [AlmanEtAl2024Asymmetry] yield ω<2.371339\omega<2.371339, but the successive improvements have become small, and no known method approaches the conjectured value.

The conjecture remains open. A proof requires constructions of a fundamentally new kind reaching exponent arbitrarily close to 22; a refutation would require the first nontrivial lower bound on ω\omega.

References (3)

The boxed statement is the canonical open formulation — not a stronger variant or a related research program. The status reflects the catalog's last review; do your own literature search before investing serious effort.