Research Notes

Chasing zeros: a rank-23 scheme for 3×3 matrix multiplication with support 138

September 30, 2026 · Chandragupt Sharma

We give an exact rank-23 scheme for 3×3 matrix multiplication with 138 nonzero coefficients. The sparsest scheme known before it is Smirnov's of 2013, with 139. The new scheme was found by a support-capped local search over GF(3) with the pairing of Smirnov's scheme planted, and then lifted to exact rationals. Its coefficients are all of the form ±2k with −4 ≤ k ≤ 4. Before finding it we spent two days showing that nothing with coefficients ±1 goes below 139, and those negative results, in the end, explain why the 138 was so hard to see.

This note continues our earlier post, which ended at 139.

The problem

The schoolbook method multiplies two 3×3 matrices with 27 scalar multiplications; Laderman (1976) needs 23. Whether 22 suffice has been open for fifty years, and the best lower bound over the rationals is 19 (Bläser, 2003). Rank 23 is not one algorithm but a large and poorly understood space of them, and two schemes of rank 23 can differ widely in the additions they need.

Let a scheme of rank r be three r×9 matrices U, V and W. Product t is

Mt = (Σi Ut,i Ai) (Σj Vt,j Bj),   Ck = Σt Wt,k Mt

and the scheme is correct exactly when the 93 = 729 Brent equations Σt Ut,a Vt,b Wt,c = Tabc hold, T being the matrix multiplication tensor. The support of the scheme is the number of nonzero entries of U, V and W, and evaluating it naively costs support − 55 additions. Rank and correctness are unchanged by cycling the three factors, by transposition, by the sandwich action X → PXQ−1, Y → QYR−1, Z → RZP−1 and by rescaling each product. Support is not, so one equivalence class can have forms of very different sparsity.

We worked against the public matrix-multiplication-tensor-3x3 hill on AutoLab. It accepts exact rational coefficients, checks all 729 identities exactly together with hidden replay tests, and scores rank first and support second. Its starting solution is Laderman's, at support 153. A submission improves on the state of the art only at rank 22, or at rank 23 with support 138 or less.

Prior work

No rank-23 scheme with support below 139 had been published, and nobody has published a lower bound, or even a conjecture, on the minimum. Every method since 2013 stops at 139 or above, and only Smirnov's class reaches 139. We downloaded and checked exactly 17,387 published rank-23 schemes (the Heule–Kauers–Seidl collection, Perminov's database and AlphaTensor); their minimum support is 139, and it is Smirnov's scheme. A literature search on 30 September 2026, in English, Russian and Chinese and back to Laderman, found nothing at or below 138. Records for the number of additions (51 to 61) count shared sums after common-subexpression elimination and come from dense schemes, so they do not bear on support.

WorkMethodBest support at rank 23
Laderman 1976By hand153
Smirnov 2013Numerical least squares, then rounding139
Benson and Ballard 2015Alternating least squares142
Heule, Kauers and Seidl 2019SAT over GF(2), lifted to ±1139 (measured by us)
AlphaEvolve 2025LLM-guided evolution150
Perminov 2025Ternary flip graph with an addition objective143

Official scores

Each submission below, over four days, set a new best. Every one passed the exact 729-identity check and the hidden tests.

How the scheme was foundRankSupport
Laderman's scheme, the hill's starting solution23153
Our symmetric numerical search, from random starts23147
Flip-graph walk in Python, rented machine23141
Flip-graph walk in C with sign lifting, 25 s on a laptop23139
Support-capped walk over GF(3) with Smirnov's core planted, then exact repair23138

To 139

Our own continuous method imposed a cyclic symmetry on the scheme, solved the Brent equations by Levenberg–Marquardt from random starts, pushed small coefficients to zero by reweighted L1 and repaired the result exactly: round U and V, then solve for W over the rationals, which is linear once U and V are fixed. It reached 147 in 27 of 120 starts and never went lower. The zero pattern is decided early by where the solver lands, and with the pattern fixed the solutions form a torus, along which coefficients only rescale.

A teammate then reported 142 with a mod-2 flip-graph walk in the style of Kauers and Moosbauer, and we rebuilt that idea with a sparsity bias. A flip rewrites two products that share a factor,

(x, p, q) + (x, p′, q′) → (x, p+p′, q) + (x, p′, q+q′),

and moves that lower support are always kept while moves that raise it are kept with a small probability. A mod-2 scheme records only which coefficients are nonzero. Writing each sign as (−1)y and reading each Brent equation mod 4 gives a linear system over GF(2) in the sign bits, which is solved and then checked over the integers. In C the walker makes about 1.4 million flips per second per core, and from the schoolbook algorithm it reaches rank 23 and support 139 in 25 seconds on a laptop. This is a rediscovery: the 139 is Smirnov's scheme mod 2, and the 33 exact 139s we hold differ from it only in their signs.

Closing the ±1 world

Over the next two days we attacked 139 from every direction we could think of, and every search that reached 141 or less ended at one of the same nine classes: one at 139, two at 140 and six at 141. Tens of billions of further flips, walks from 160 published seeds, alternating exact descents and a mod-3 flip walk all came back to them. The exact checks below turn “we did not find 138” into a statement about where a 138 cannot be.

CheckScopeResult
Replace any k products of the 139 by a sparser set (SAT, mod 2)k ≤ 5: all 33,649 subsetsAll impossible
Replace 6 products, perfect-pairing class, support ≤ 138All 100,947 subsets around each of the 9 known classesAll impossible
Sparsest form under every basis change mod 2 (168³ = 4.74 million)All 17,376 Heule–Kauers–Seidl and 15,316 Hell's Bells schemesBoth collections bottom out at the same 9 classes
Fix one factor table, re-solve the other two with at most 138 nonzerosU, V or W fixed; our 139 and Smirnov'sImpossible in all six cases
Support-capped walk with each possible core planted, cap 145All 1,811 cores of four index-disjoint pairsOnly 4 cores admit a scheme; only Smirnov's goes below 142

The mod-2 checks are sound for more than ±1 schemes. Reducing an integer, or an odd-denominator rational, scheme mod 2 gives a valid GF(2) scheme with no more nonzeros, so an impossibility over GF(2) rules out all of them. Three independent generators — SAT neighbourhood walks, a neural network trained with a sparsity loss (the Hell's Bells collection) and our flip walks — each find the 139 hundreds of times and nothing else below 142. A ±1 scheme at 138 would have to be rarer than every known class under all three.

The shape of the sparse schemes

Expand each product of three linear forms into monomials aijbjkcki. In the 139, each of the 27 needed monomials is produced by exactly one product, and each of the 68 unwanted ones appears in exactly two products and cancels. We call this a perfect pairing. All nine classes at 141 or below have it, and a pattern of this shape is automatically a valid scheme mod 2. The 139's zero pattern also has an order-2 symmetry of transpose type that fixes 3 products and swaps 10 pairs, though no choice of signs respects it. A core records which needed monomials share a product; every known scheme at 141 or below has the same core as Smirnov's, four index-disjoint pairs and 19 singles.

The decisive observation is the first. A pattern that is not a valid scheme mod 2 must cover some monomial an even number of times, or some unwanted one an odd number of times, with coefficients that cancel over the rationals but not mod 2, as in ½ + ½ = 1. Every GF(2) method, and every ±1 collection, is blind to such patterns by construction.

Breaking 139 over GF(3)

A rational scheme whose coefficients are 3-adic units (±1, ±2, ±½, ±4, …) reduces mod 3 to a valid GF(3) scheme with the same support. GF(3) therefore sees the powers-of-2 class that GF(2) cannot. Our earlier GF(3) flip walk moved only between valid schemes and found ½-type patterns only at 141 and above. What changed was the search: we planted Smirnov's core and let a capped local search move through invalid states.

The state is 23 × 3 × 9 entries in {0, 1, 2}; a move changes one entry; the score is the number of the 729 identities violated mod 3; the 81 entries of the core are fixed to 1; and the number of nonzeros may never exceed the cap. This follows Palladinos' semantic walk over GF(2). At cap 139 the walk finds the 139 in 6 of 30 seeds. At cap 138, seed 3158 of 316 reached zero violations with 138 nonzeros, 29 of them equal to 2, in a pattern that is not a valid scheme mod 2. At cap 137 nothing was found in 300 seeds.

A GF(3) pattern is only a hint, and three steps made it a rational scheme. Least squares on the Brent equations with the zero pattern fixed converged from several of 64 random starts to a residual of 5×10−15, so the pattern is feasible over the reals. Fixing the rescaling of each product left a 7-parameter family; unlike the 139, the new scheme is not rigid. Greedy snapping of entries to 0, ±1, ±½ and ±2 while a solution survives, followed by an exact solve for W, gave the scheme below.

Verification

Five independent checks pass: all 729 identities in exact rational arithmetic from a fresh implementation; the hill's evaluation formula run literally on 300 random rational matrices; the same with 2×2 integer matrices as entries, so that the order of factors is kept and the scheme is valid over noncommutative rings; the hill's own checking functions on 500 random cases; and the official AutoLab evaluation with its hidden replays. The scheme was scored on 30 September 2026 at rank 23 and support 138, first on the public leaderboard, with five other climbers at 139.

The scheme

Here aij, bij and cij are the (i, j) entries of A, B and C = AB. Each line is one product, and the arrow gives the entries of C it is added into, with their coefficients.

m1  = (a11 + a22) * (b11 - 16 b22 - 4 b31)           ->  c11 - 1/16 c22
m2  = (a11 + a23) * (b13 + 2 b31 - 8 b32)            ->  -1/8 c22 + c13
m3  = (a12 - 8 a23 + 16 a33) * (b23 - 1/4 b31)       ->  -1/4 c31 + c13
m4  = (a22 - a23 - 8 a31) * (b11 - 16 b23)           ->  -1/8 c31 - 1/16 c23
m5  = (a11) * (b12 - 8 b22 - 8 b32)                  ->  c12 + 1/8 c22
m6  = (a12 - 8 a22) * (b21 - 2 b22 + 1/2 b31)        ->  c11 - 1/8 c31
m7  = (a11 + 1/8 a12) * (b22)                        ->  16 c11 + 8 c12
m8  = (a11 - 1/8 a12 + 1/4 a13) * (b31)              ->  4 c11 - 2 c13
m9  = (a11 + 1/8 a13) * (b32)                        ->  8 c12 + 8 c13
m10 = (a13 - 8 a23 + 8 a33) * (b31 - 2 b32 + 2 b33)  ->  1/2 c13
m11 = (a21 - 1/8 a22 + 1/4 a23) * (b11)              ->  c21 - 1/2 c23
m12 = (a11 - 8 a21 + 8 a31) * (b11 - 2 b12 + 2 b13)  ->  1/16 c22
m13 = (a21 + 1/8 a23 - a31) * (b11 + 2 b13)          ->  1/2 c22 + 1/2 c23
m14 = (a22) * (b11 - 8 b21 - 8 b31)                  ->  -c11 - 1/8 c21
m15 = (a22 - a23) * (b11 - 4 b31)                    ->  1/4 c21 + 1/8 c31 + 1/16 c22
m16 = (a23) * (b13 - 8 b23 - 8 b33)                  ->  -c13 - 1/8 c23
m17 = (a31) * (b12)                                  ->  c22 + c32
m18 = (a31) * (b13 + 8 b23)                          ->  c23 + c33
m19 = (a12 - 8 a22 + 8 a32) * (b21 - 2 b22 + 2 b23)  ->  1/8 c31
m20 = (a32) * (b22)                                  ->  2 c31 + c32
m21 = (a31 - 1/8 a32 + 1/4 a33) * (b23)              ->  16 c31 - 8 c33
m22 = (a33) * (b32)                                  ->  c32 + 8 c13
m23 = (a33) * (b23 + 1/2 b33)                        ->  -16 c13 + 2 c33

What is left

The question has moved by one: is 138 the minimum support of a rank-23 scheme over the rationals? No technique for a lower bound on support exists. The ±1 world looks closed at 139 by every test we can run, while the powers-of-2 class has one known point below it, found once in about 300 seeds.

Route to 137Why it might workStatus
More seeds at cap 137 on Smirnov's core, and split-cell variants (½ + ½)The 138 came at one hit in about 300; 137 may simply be rarer300 seeds and 27 variants × 100 seeds, nothing yet
The same walk over GF(5) and GF(7)These fields see thirds and other units that GF(3) cannotUntried
Cores with one shared index, about 14,500 classesThe census covered only index-disjoint coresUntried
Search inside the 138's own 7-parameter familyThe 138 is not rigid the way the 139 isUntried

On rank, the lower bound over GF(2) rose to 21 in September 2026 in two independent papers, and no rank-22 scheme has been claimed. A realistic contribution there is exclusion rather than discovery, for instance a proof that no rank-22 scheme shares 18 or more products with any known rank-23 scheme, which is the analogue for rank of the certificates above.

References

  • J. D. Laderman, A noncommutative algorithm for multiplying 3×3 matrices using 23 multiplications, Bull. AMS 82 (1976).
  • A. V. Smirnov, The bilinear complexity and practical algorithms for matrix multiplication, Comput. Math. Math. Phys. 53 (2013).
  • M. Bläser, On the complexity of the multiplication of matrices of small formats, J. Complexity 19 (2003).
  • A. R. Benson and G. Ballard, A framework for practical parallel fast matrix multiplication (2015).
  • M. J. H. Heule, M. Kauers and M. Seidl, New ways to multiply 3×3 matrices (2019).
  • M. Kauers and J. Moosbauer, Flip graphs for matrix multiplication (2022).
  • D. Perminov, ternary flip graph and scheme database (2025).
  • N. Palladinos, Solving the Heule–Kauers–Seidl SAT challenges: a semantic local search on factor bits (2026).
  • E. Mårtensson, E. Stankovski Wagner and A. Stapleton, Hell's Bells: a neural network pipeline for ternary fast matrix multiplication algorithms, IACR ePrint 2026/1688.
  • C. Wang, A lower bound of 21 for 3×3 matrix multiplication over F2 (2026).
  • Y. Yang et al., A structural proof of the lower bound 21 for 3×3 matrix multiplication over F2 (2026).

← All posts