We show that the bilinear complexity of multiplying two $3\times3$ matrices over the finite field $\mathbb{F}_2$ is at least $21$, improving the previous lower bound of $20$. The core argument refines restriction bounds on how many first‑factor terms of a decomposition can lie in each subspace: assuming a $20$‑term decomposition, the strengthened bounds force every first factor of matrix rank at least two into a single coset of a three‑dimensional rank‑one subspace. An exhaustive search then confirms that no admissible $20$‑term profile exists.
We also establish that the tensor rank of $2\times3$ by $3\times3$ matrix multiplication over $\mathbb{F}_3$ equals $15$. After symmetry‑reduced enumeration, only three $14$‑term profiles survive, and short restriction arguments rule them out.
Methodologically, 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;
- A direct, symmetry‑reduced profile enumerator that enforces all subspace capacities simultaneously.
These innovations advance both the theoretical lower‑bound landscape and the practical tools for tensor analysis.
Review