Skip to content
Preprint

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

Sep 2026 · 0 citations · 18 references
Computer Science

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.

View source

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.