The matrix multiplication exponent equals two

An arithmetic program over $\mathbb C$ with inputs $x_1,\dots,x_m$ is a finite sequence of registers $r_1,\dots,r_s$. Each register is either a constant $c\in\mathbb C$, an input $x_i$, or $r_a\circ r_b$ for earlier registers $r_a,r_b$ and an operation $\circ\in\{+,-,\times\}$. Its cost is the number of registers of the third kind, that is, the number of arithmetic operations. A program multiplies $n\times n$ matrices if its inputs are the $2n^2$ entries of $A,B\in\mathbb C^{n\times n}$ and, for each $(i,k)$, some register equals $(AB)_{ik}$ for all $A,B$.

Let $M(n)$ be the least cost of such a program. The matrix multiplication exponent is

$$\omega=\inf\bigl\{\tau\in\mathbb R:\ M(n)=O(n^\tau)\ \text{as } n\to\infty\bigr\}.$$

The $n^2$ entries of $AB$ are distinct polynomials of degree $2$, so each occupies its own operation register. Hence $M(n)\ge n^2$ and $\omega\ge 2$. The schoolbook algorithm gives $\omega\le 3$.

Conjecture. $\omega=2$. Equivalently, for every $\varepsilon>0$ there is a constant $C_\varepsilon$ such that for every $n\ge1$ some arithmetic program multiplies $n\times n$ complex matrices with cost at most

$$C_\varepsilon\, n^{2+\varepsilon}.$$

A solution must prove this equality. Allowing division gates does not change $\omega$ [2]. The value of $\omega$ depends only on the characteristic of the field, so the same question over $\mathbb Q$ or $\mathbb R$ is equivalent [10]. $\omega$ also equals the exponent of the border rank of the matrix multiplication tensor $\langle n,n,n\rangle$ [3, 10].

Background

Strassen's 1969 algorithm multiplies $2\times2$ matrices with $7$ multiplications and, applied recursively, gives $\omega\le\log_2 7<2.81$ [1]. The question of the true exponent has driven algebraic complexity theory since then [18]. Many problems in linear algebra share the exponent $\omega$, among them matrix inversion, determinants and solving linear systems. Many graph algorithms reduce to matrix multiplication as well.

All improvements since 1987 use Strassen's laser method [4]. It extracts many disjoint copies of matrix multiplication from a power of an auxiliary tensor, usually the Coppersmith–Winograd tensor [5]. Schönhage's asymptotic sum inequality [3] then converts these copies into a bound on $\omega$. The algorithms are galactic: their constants make them impractical. The theoretical interest lies in the exponent. Bürgisser, Clausen and Shokrollahi give a standard account [10].