Complexity Lower Bounds of Small Matrix Multiplication over Finite Fields via Backtracking and Substitution
This work provides an incremental improvement to a fundamental problem in algebraic complexity theory, specifically for researchers working on the theoretical limits of matrix multiplication algorithms.
This paper establishes a new lower bound for the bilinear complexity of multiplying two 3x3 matrices over the finite field F2, proving it to be at least 20. This improves upon the previous longstanding lower bound of 19.
We introduce a new method for proving bilinear complexity lower bounds for matrix multiplication over finite fields. The approach combines the substitution method with a systematic backtracking search over linear restrictions on the first matrix $A$ in the product $AB = C^T$. We enumerate restriction classes up to symmetry; for each class we either obtain a rank lower bound by classical arguments or branch further via the substitution method. The search is organized by dynamic programming on the restricted matrix $A$. As an application we prove that the bilinear complexity of multiplying two $3 \times 3$ matrices over $\mathbb{F}_2$ is at least $20$, improving the longstanding lower bound of $19$ (Bläser 2003). The proof is found automatically within 1.5 hours on a laptop and verified in seconds.