CS Paper Radar

The rank of 3x3 matrix multiplication over F2 is 23

Tejasvi Singh Tomar

cs.CC math.RA ·submitted 2026-10-08 12:24 UTC · v3
theorycode/data

Abstract

The rank of the tensor of $3\times 3$ matrix multiplication over the field with two elements is at most $23$ by Laderman's algorithm, and Rudich and Rousseau recently proved that it is at least $22$. We prove that it equals $23$. Hence Laderman's algorithm uses the fewest multiplications among all bilinear algorithms over $\mathbb{F}_2$ and among all bilinear algorithms with integer coefficients. The proof uses the substitution method in the form developed by D'Ambrosio, Wang and Yang et al., which bounds the number of first factors of a decomposition that lie in a given subspace of the space of first factors. We sharpen these bounds for $111$ of Wang's $496$ classes of subspaces, constrain the ranks of the first factors through a $27\times 27$ flattening of the tensor, and list, up to symmetry, all sets of $22$ first factors that satisfy these constraints. An exact completion search shows that none of them is the set of first factors of a decomposition. The computation emits certificates, which are checked in the Lean 4 proof assistant. In one formal proof the largest checks are evaluated as compiled code, and in a second one the kernel evaluates every check, so that its final theorem depends only on the three standard axioms of Lean. The Lean proofs build on the formalization of Rudich and Rousseau and import their table of bounds and their reduction for block algorithms.

Comment
18 pages. Kernel-only Lean proof: https://github.com/tejasvi/rank333-f2-kernel (archived at https://doi.org/10.5281/zenodo.23304899). Lean proof with compiled checks, programs and data: https://github.com/tejasvi/rank333-f2 (archived at https://doi.org/10.5281/zenodo.23236154). The paper is also deposited, with the data of Section 3.4, at https://doi.org/10.5281/zenodo.23484413

Closest papers

Nearest neighbours by meaning across the whole index.

A Lower Bound of 21 for $3\times3$ Matrix Multiplication over $\mathbb{F}_2$

cs.CC cs.DS ·2026-09-06 ·Chengu Wang
theory similarity 0.82
Abstract

We prove that $3\times3$ matrix multiplication over $\mathbb{F}_2$ has bilinear complexity at least $21$, improving the previous lower bound of $20$. Lower bounds for restrictions of the first input constrain how many first factors of a decomposition can lie in each subspace. For a hypothetical $20$-term decomposition, the strengthened restriction bounds force all first factors of matrix rank at least two into a single coset of a three-dimensional rank-one subspace. An exhaustive computation finds no admissible first-factor profile with $20$ terms. We also prove that $2\times3$ by $3\times3$ matrix multiplication over $\mathbb{F}_3$ has rank exactly $15$: three profiles with $14$ terms survive the corresponding computation up to symmetry, and short restriction arguments exclude them. We combine Wang's automated framework for tensor-rank lower bounds with D'Ambrosio's capacity-and-profile strategy. Our computational contributions are rank-one-span searches that strengthen the subspace lower-bound table and a direct, symmetry-reduced profile enumerator that enforces all subspace capacities simultaneously.

0.28

A Structural Proof of the Lower Bound 21 for $3\times3$ Matrix Multiplication over $\mathbb F_2$

cs.CC cs.DScs.SC ·2026-09-16 ·Shuxing Yang, Rui Zhao, Junyao Wu, Yize Wang, Wenhao Li +11 more
theorycode/data similarity 0.70
Abstract · 27 pages. Complete Lean formalization, finite certificates, source code, and reproducibility materials are available in the accompanying pub…

We prove that the tensor rank of $3\times3$ matrix multiplication over $\mathbb F_2$ is at least $21$. The structural proof, independently developed by Qiushi Engine, converts occupation constraints on a single tensor factor into algebraic relations coupling all three factors. Certified quotient-rank bounds and finite geometry force any hypothetical $20$-term decomposition to have first-factor matrix-rank profile $(16,1,3)$. The ranks of the corresponding split-flattened summands therefore sum to $27$, exactly the rank of the full split flattening. Equality in rank subadditivity forces their images to form a direct sum; normalization by the inverse flattening then makes the summands pairwise annihilating idempotents. An explicit product identity for matrix multiplication implies that at most one first factor can be invertible, contradicting the three forced by the profile. The same obstruction constrains $22$-term decompositions attaining the split-rank bound. The complete proof, including the finite quotient bounds, is formalized in Lean. The accompanying research trajectory records Qiushi Engine's long-horizon autonomous research, from numerical experiments and quotient constructions to the structural proof.

0.24

Lower Bound of 22 for 3x3 Matrix Multiplication over the Integers

cs.CC ·2026-10-01 ·Isaac Rudich, Louis-Martin Rousseau
publishedtheory similarity 0.70
Abstract

Strassen showed that two 2x2 matrices can be multiplied with 7 multiplications instead of 8. Applied recursively, his algorithm multiplies two nxn matrices with O(n^2.807) multiplications, beating the naive O(n^3). The best known 3x3 recursive matrix multiplication algorithm uses 23 multiplications O(n^2.854). The best published lower bound of 21 (on algorithms with integer constants) leaves room for an algorithm with O(n^2.771) multiplications, and thus does not rule out the possibility of an algorithm that would beat Strassen's. We prove a lower bound of 22 multiplications for any 3x3 recursive algorithm with integer constants, proving that no such algorithm can do better than O(n^2.814) multiplications, and eliminating the possibility of a 3x3 algorithm that beats Strassen's 2x2 method. The proof builds on a recent decomposition method from Wang, who approached the problem by turning it into 496 subproblems. We provide exact solutions for 359 of them. The proof is in Lean; verification requires auditing only a few short files. The Lean formalization directly encodes statements about the limitations of recursive algorithms for matrix multiplication, as opposed to just a statement about the rank of the problem.

0.19

51 Additions per Recursive Step for Rank-23 $3\times3$ Matrix Multiplication, Machine-Checked over Arbitrary Rings

cs.MS cs.CCcs.DScs.SC ·2026-10-17 ·Greg Sidebottom
code/data similarity 0.69
Abstract · 14 pages. Artifacts (certificates, exact searcher, Lean 4 proofs): https://doi.org/10.5281/zenodo.23305910; source: https://github.com/gside…

We present a rank-23 bilinear scheme for $3\times3$ matrix multiplication that uses 51 additions per recursive step in the alternative-basis (Karstadt-Schwartz) cost model, one below Nielsen's 52 (arXiv:2609.06588). The count 51 itself was first posted, on a different scheme, by Stapleton and Perminov (arXiv:2609.32388), found by heuristic sparse-basis search; the present work is independent and complementary: exactness and breadth rather than a single construction. The scheme is valid over every ring, so it recurses on block matrices, and its correctness is machine-checked in Lean 4/Mathlib. The count is exactly optimal for the scheme's equivalence class: we introduce an exact free-basis minimization procedure whose negative answers are exhaustion proofs, and use it to show that 51 is the minimum for this class, that 52 is exactly optimal both for Nielsen's class and for the class of the current flat-model record, and to sweep the complete Heule-Kauers-Seidl database of rank-23 classes. The sweep is complete: exactly four classes attain 51, all in a single HKS invariant family. We machine-check Stapleton and Perminov's scheme as well, and prove in Lean that their 51 is optimal for its class. Separately, we document a systematic gap between $\mathbb{F}_2$ and signed optima: the $\mathbb{F}_2$-optimal chains of a class typically admit no sign assignment under most of the class's integer sign models, and certificate lifting fails where a direct signed search succeeds.

0.35

A lower bound for $\langle 3,2,m \rangle$ matrix multiplication

cs.CC cs.DS ·2026-09-18 ·Askar Tsyganov, Uliana Parkina, Sergey Samsonov, Maxim Rakhuba
theorycode/data similarity 0.68
Abstract

We prove that, over any field, the bilinear complexity of multiplying a $3\times 2$ matrix by a $2\times m$ matrix is strictly greater than $24m/5$. In particular, every exact bilinear algorithm for multiplying a $3\times 2$ matrix by a $2\times 5$ matrix requires at least $25$ multiplications. Together with the Hopcroft-Kerr upper bound, this proves that the $\langle 3,2,5\rangle$ matrix multiplication tensor has rank exactly $25$. The proof has been formally verified in Lean 4, with the formalization available at https://github.com/fallnlove/mm325_proof.

0.25

Certified local rank and uniqueness barriers for a 48-term matrix-multiplication decomposition

cs.SC cs.CC ·2026-09-11 ·Abhinav Agarwal
theoryhot direction similarity 0.65
Abstract

We study replacements in fixed bilinear tensor decompositions, counting changes to complete rank-one summands, including output factors. The shortening frontier records the maximum rank defect of a fixed-size subset and determines the minimum length attainable within a change budget. For the rational 48-term Li--Wang--Hu decomposition \(D(2)\) of \(4\times4\) matrix multiplication over \(\mathbb{C}\), we prove rank radius at least 12, strong radius exactly 11, and border radius at least 8. Every shorter complex decomposition therefore changes at least thirteen original summands. An exact rational twelve-term replacement attains the equal-length barrier. The proofs combine exhaustive support reductions with saturated projected kernels and zero-corner completion arguments controlling arbitrary minimal competitors. A reduced-incidence argument transfers kernel certificates to tensor-space neighborhoods. A Laurent normal form gives strong radius exactly 11 for the sixteen-term core at every nonzero complex parameter. On a nonempty Zariski-open subset of the actual parameter curve, the rank radius is at least 12, the strong radius exactly 11, and the border radius at least 8. We also prove incomparability of the full Kothari--Moitra--Wein sufficient criterion and the Sylvester-equipped kernel criterion. These results describe local decomposition structure rather than a new rank bound for full matrix multiplication.

0.25

A 51-Addition Alternative-Basis Kernel for Rank-23 $3\times3$ Matrix Multiplication

cs.DS cs.CCcs.SC ·2026-09-26 ·Joshua Stapleton, Andrew Perminov
code/data similarity 0.63
Abstract · 7 pages. Certificate and verification code: https://github.com/Joshua-Stapleton/51-addition-alt-basis-3x3-rank23

We give a rank-23 algorithm for $3\times3$ matrix multiplication using 51 additions and subtractions in alternative bases. The input and output conversions require five further additions, giving 56 additions in ordinary coordinates. The construction combines linear-program reduction with a search over sparse basis changes, and the resulting programs are distributed as a machine-checkable certificate. We verify correctness by exact coefficient expansion and distinguish the kernel cost from the cost of a complete multiplication.

0.24

Factorisability of Low Dimensional Non-Negative Integer Matrices

cs.DM cs.DScs.IT ·2026-09-22 ·Paul C. Bell, Eva Foster, Daniel Reidenbach, Pavel Semukhin
published similarity 0.62
Abstract · Accepted for publication at 20th International Conference on Reachability Problems, RP 2026

We consider the problem of determining if a given two-dimensional nonnegative integer matrix $M$ is the product of two such matrices, excluding trivial units. A matrix $M$ with no such factorisation is called prime and therefore belongs to the minimal (infinite rank) generator of $2 \times 2$ matrices over the natural numbers, otherwise it is called composite. We also consider the problem of finding a (non-unique) factorisation of a composite matrix. Our results have applications in computational group theory and the theory of codes, where such matrices are called incidence matrices. We analyse the complexity of primality and finding a factorisation for a composite matrix, providing a first efficient algorithm.

0.42