← All papers
First page of The rank of $3\times 3$ matrix multiplication over $\mathbb{F}_2$ is 23

The rank of $3\times 3$ matrix multiplication over $\mathbb{F}_2$ is 23

Tejasvi Singh Tomar

math.RA Oct 8, 2026 · v1 cs.CC
Search certificates are checked in Lean 4 by checkers proved sound in Lean, giving a Lean theorem that the 3x3 matrix multiplication rank over F2 is 23.
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 in recent work of D'Ambrosio, Wang and Yang et al.: a subspace $S$ of the space of first factors contains at most $r-R(S)$ first factors of a decomposition of length $r$, where $R(S)$ is the rank of the tensor modulo $S$. We raise the known lower bounds on $R(S)$ for $111$ of Wang's $496$ symmetry classes of subspaces. One of these bounds, $R(S)\ge 21$ for a point spanned by a matrix of rank one, forces the $22$ first factors of a decomposition of length $22$ to be distinct. A $27\times 27$ flattening of the tensor gives further constraints on the ranks of the first factors, and a separate enumeration shows that, when at least $14$ first factors have rank one, no line in a certain orbit of lines contains two first factors. A computer search then lists, up to symmetry, all sets of $22$ matrices that satisfy these constraints, and 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 by checkers whose soundness is proved in Lean. The largest checks are evaluated as compiled code, so the proof relies on the Lean compiler in addition to its kernel.

Laderman's algorithm shows the rank of the 3x3 matrix multiplication tensor over F2 is at most 23, and Rudich and Rousseau proved it is at least 22. The open question was whether 22 multiplications suffice over F2.

The substitution method bounds how many first factors of a decomposition lie in a subspace S, and the authors raise the lower bounds on R(S) for 111 of Wang's 496 symmetry classes. A 27x27 flattening constrains the ranks of the first factors, and a lifting criterion limits first factors on certain lines. An exhaustive computer search lists all admissible sets of 22 first factors up to symmetry, and an exact completion search refutes each one. The searches emit certificates that are verified by Lean checkers whose soundness is proved in Lean, with the largest checks run as compiled code.

The rank equals 23, and Lean contains this as a theorem, including a check that Laderman's algorithm is a decomposition of length 23. Through Rudich and Rousseau's Lean reduction, bilinear algorithms with integer coefficients for 3x3 matrices also need at least 23 multiplications.