Tensor rank of 3×3 matrix multiplication: 19 ≤ R ≤ 23, find rank 22 or raise the lower bound
Difficulty 72: the 23 upper bound has stood since 1976 against SAT, flip-graph and reinforcement-learning searches, and the lower bound over Q and C has been 19 since 2003; below the exponent ω itself (82). Application value 6: a rank-22 scheme would not beat Strassen asymptotically and small kernels are bound by additions and memory. Leverage 30: the smallest open matrix multiplication tensor and a test for lower-bound methods, far less than ω (72).
The problem
Multiplying two 3 by 3 tables needs 27 products by the school method; 23 suffice, and 22 is unknown.
- 1School method: 27 multiplications
- 2Laderman 1976: 23 multiplications
- 3Lower bound known: 19
- 422 would be checkable in seconds
The question. Multiplying two matrices the school way computes each of the 9 entries as a sum of 3 products, so 27 multiplications. Can it be done with fewer? An algorithm here is a list of products, each of the form (a linear combination of entries of ) × (a linear combination of entries of ), such that every entry of is a linear combination of those products. The smallest possible is the .
Path to understanding
foundations → problemThe research entries this problem rests on, in the order to read them. Each links to its explainer.
- Start with
- Step 2
- Step 3
- Fast matrix multiplicationAlgorithm · host
- Then
- Tensor rank of 3×3 matrix multiplication: 19 ≤ R ≤ 23, find rank 22 or raise the lower boundThe problem
State of the art
Over the rationals, reals and complex numbers the bounds remain 19 ≤ R(3) ≤ 23: Laderman's 23-product algorithm (1976) and Bläser's lower bound of 19 (2003), which holds over every field. Large computer searches (flip graphs, reinforcement learning, SAT) have found many inequivalent rank-23 schemes and none of rank 22. Over the two-element field F2 the lower bound moved quickly in 2026, all in preprints: 20 (Chengu Wang, arXiv:2603.07280, March), 21 (Wang, arXiv:2609.06725, September; a structural proof by Yang and co-authors, arXiv:2609.18722), 22 (attributed to Rudich and Rousseau in the next preprint; no public source was found), and a claim that the F2 rank is exactly 23 (Tejasvi Singh Tomar, arXiv:2610.11823, 8 October 2026, revised 12 October, with Lean 4 certificates including a kernel-only build). If the F2 claim holds, no rank-22 scheme exists with integer coefficients (reduce it mod 2); a rank-22 scheme over the rationals would then need coefficients with even denominators. None of these preprints is refereed.
Realistic applications
Little practical value: a rank-22 scheme gives an exponent of log₃22 ≈ 2.81, worse than Strassen's log₂7 ≈ 2.807, and small-matrix kernels are limited by additions and memory traffic rather than by multiplications. The value is structural: the 3×3 tensor is the smallest open case, and methods that settle it (lower-bound techniques, exhaustive certified search) are tests for the larger tensors behind ω.
What counts as solved
Upper bound: 22 rank-one tensors (explicit coefficient vectors over the rationals) that sum to the 3×3 matrix multiplication tensor, verified by exact arithmetic. Lower bound: a proof, ideally formal, that R(3) ≥ 20 over the rationals or the complex numbers.
How it gets verified
Bound / recordA numeric bound or record checked from a certificate or recomputation.
Quantity: tensor rank of the 3×3 matrix multiplication tensor over Q (or R, C); current bounds 19 ≤ R ≤ 23. An upper-bound improvement is a list of 22 triples of 3×3 coefficient matrices with rational entries; the check expands in exact rational arithmetic and compares it entry by entry with the matrix multiplication tensor (the Brent equations), a short script. A lower-bound improvement over Q or C needs a proof reviewed by experts or checked in Lean 4; for F2, the preprint arXiv:2610.11823 supplies Lean artefacts (GitHub tejasvi/rank333-f2-kernel, kernel-only) that anyone can rebuild. Report the field, coefficient ring and verification script.
Claims under verification
+ add a claimWhere the work is
Lower bounds need new algebraic geometry or substitution arguments; upper bounds are large exact searches, which have not found 22.
Bottlenecks
ranked by votes- #1TheoryLower bound techniques stall near 19
Substitution and flattening methods give 19 over general fields; the 2026 finite-field progress relies on exhaustive search over F2 subspaces, which does not transfer to infinite fields such as Q or C.
Community grades
Sign in to add your own grade.
Connected problems
Progress
- Oct 8, 2026Rank over F2 claimed to be 23 (preprint)source
Tomar submitted a preprint claiming rank 23 over F2 with Lean-checked certificates; revised on 12 October 2026.
- Sep 6, 2026F2 lower bound 21 (preprint)source
Wang raised the F2 lower bound to 21.
- Mar 7, 2026F2 lower bound 20 (preprint)source
Wang's automated framework gave R ≥ 20 over F2.
- Feb 1, 2003Rank at least 19source
Bläser proved the lower bound 19 over every field; month of the journal issue.
- Jan 1, 1976Rank at most 23
Laderman gave a 23-multiplication algorithm for 3×3 matrices; year only.