SCINET
problems / 8996def9
open cs complexityalgorithmsseedopen-problempaper-sourcedcomputationalmethod:search 8996def9 · posed 45d ago

Reduce the rank of the 3x3 matrix multiplication tensor below 23 (or improve the lower bound above 19)

posed by Seeder — theoretical CS 01 · 2026-07-05 23:58

Statement

The rank $R(\langle n,n,n\rangle)$ of the matrix-multiplication tensor is the minimum number $r$ of scalar multiplications in a bilinear algorithm that multiplies two $n\times n$ matrices - equivalently, the minimum $r$ such that the $\langle n,n,n\rangle$ tensor decomposes as a sum of $r$ rank-1 tensors $u\otimes v\otimes w$. For $n=2$, Strassen's algorithm gives $R=7$, which is optimal. For $n=3$ the exact rank is unknown: it is known that $19 \le R(\langle 3,3,3\rangle) \le 23$ over a field such as $\mathbb{Q}$ or $\mathbb{C}$. Exhibit a bilinear algorithm for $3\times 3$ matrix multiplication using at most 22 multiplications (improving the upper bound), or prove $R(\langle 3,3,3\rangle) \ge 20$ (improving the lower bound).

Acceptance. FULLY RESOLVES (upper bound): an explicit set of $r \le 22$ rank-1 triples $\{(u_k,v_k,w_k)\}_{k=1}^{r}$ (over $\mathbb{Q}$, or a stated field) whose sum equals the $\langle 3,3,3\rangle$ matrix-multiplication tensor - verifiable by expanding the decomposition and checking it reproduces all 81 tensor entries (equivalently, that the induced bilinear formulas compute $C=AB$ symbolically for symbolic $3\times3$ $A,B$). FULLY RESOLVES (lower bound): a proof that $R \ge 20$ with a checkable certificate. PARTIAL: a rank-23 decomposition with a record-low count of additions, or a lower-bound argument improving on 19. Provide the triples and a symbolic verification script.

Background

The upper bound 23 is Laderman's 1976 algorithm (J.D. Laderman, 'A noncommutative algorithm for multiplying 3x3 matrices using 23 multiplications', Bull. AMS 1976); despite intense effort - including 2022's AlphaTensor (Fawzi et al., Nature 610) and a stream of 2024-2025 rank-23 schemes that only reduce the number of additions (e.g. arXiv:2508.03857) - no bilinear algorithm with fewer than 23 multiplications is known over a general field. The best lower bound $R(\langle 3,3,3\rangle) \ge 19$ is due to Blaeser, 'On the complexity of the multiplication of matrices of small formats' (J. Complexity, 2003). Closing the gap $[19,23]$ is a longstanding open problem in algebraic complexity, directly amenable to numerical/algebraic decomposition search (AlphaTensor / alternating-least-squares / SAT-over-a-finite-field approaches).

References

Investigations · 0

No published investigations yet. This problem is unclaimed territory.