# How many multiplications do small matrix products need?

Strassen showed in 1969 that two $2 \times 2$ matrices can be multiplied with 7 multiplications instead of 8, and every such saving for a small format becomes a faster algorithm for large matrices. For $3 \times 3$ matrices the answer is still unknown, somewhere between 19 and 23. Sedoglavic's catalogue records the best known schemes for all formats up to $32 \times 32$, and a new scheme is verified exactly in seconds.

## Problem

Multiplying an $n \times m$ matrix by an $m \times p$ matrix is a bilinear map, described by the matrix multiplication tensor $\langle n, m, p \rangle$. Its *rank* $R(\langle n, m, p \rangle)$ is the smallest $r$ such that the product can be computed with $r$ multiplications, each of a linear form in the entries of the first matrix by a linear form in the entries of the second, followed by linear combinations; equivalently, the tensor is a sum of $r$ rank-one tensors. Commutativity of the entries may not be used, so the scheme works for matrices of blocks and can be applied recursively.

**Task:** find schemes with fewer multiplications than the catalogue's entries, or prove better lower bounds, for small formats such as $\langle 3,3,3 \rangle$, $\langle 4,4,4 \rangle$ and $\langle 5,5,5 \rangle$. The coefficient ring matters (integers, rationals, complex numbers or $\mathbb{F}_2$): some records hold only over particular rings.

## Background

A scheme $\langle n, n, n : r \rangle$ applied recursively multiplies $N \times N$ matrices in $O(N^{\log_n r})$ operations, so small-format records feed directly into practical fast algorithms, while the asymptotic exponent of matrix multiplication is studied by other methods. Strassen's 7 multiplications for $2 \times 2$ are optimal (Winograd, 1971). The catalogue gathers 5426 schemes, with explicit coefficients, references and symmetry groups. Since 2022 many entries have been improved by computer search, including reinforcement learning, flip-graph random walks and evolutionary program search.

## What is known

From the catalogue (October 2026):

- $\langle 2,2,2 \rangle$: 7 (Strassen, 1969), optimal.
- $\langle 3,3,3 \rangle$: 23 (Laderman, 1976). The best general lower bound is 19 (Bläser, 2003); over $\mathbb{F}_2$ it was raised to 20 (Wang, March 2026) and then to 21 in two September 2026 preprints, not yet refereed (Wang; Yang et al., whose proof is formalized in Lean).
- $\langle 4,4,4 \rangle$: 49 from applying Strassen's scheme twice; 47 over $\mathbb{F}_2$ (Fawzi et al., 2022); 48 with complex coefficients (Novikov et al., 2025, the catalogue's entry) and then with rational coefficients (Dumas, Pernet and Sedoglavic, 2025).
- Other formats: $\langle 3,4,5 \rangle$: 47 and $\langle 4,5,5 \rangle$: 76 (Fawzi et al., 2022); $\langle 4,4,5 \rangle$: 61 (Novikov et al., 2025); $\langle 5,5,5 \rangle$: 93 and $\langle 6,6,6 \rangle$: 153 (Moosbauer and Poole, 2025); $\langle 5,5,6 \rangle$: 110 (Kauers and Wood, 2025).

## What would count as progress

- A scheme with fewer multiplications for some format and coefficient ring, given as the three factor matrices of a tensor decomposition. Expanding the decomposition and comparing it with the matrix multiplication tensor is an exact computation that takes seconds even for the largest catalogue formats.
- A better lower bound on a small rank, such as $R(\langle 3,3,3 \rangle) \ge 20$ over the rationals, with a proof or a machine-checkable certificate.
- Schemes that match a record with fewer additions or better numerical stability, which the catalogue also tracks for practical use.

## References

1. V. Strassen, "Gaussian elimination is not optimal", *Numerische Mathematik* 13 (1969), 354–356. [doi:10.1007/BF02165411](https://doi.org/10.1007/BF02165411)
2. J. D. Laderman, "A noncommutative algorithm for multiplying 3×3 matrices using 23 multiplications", *Bulletin of the AMS* 82 (1976), 126–128. [doi:10.1090/S0002-9904-1976-13988-2](https://doi.org/10.1090/S0002-9904-1976-13988-2)
3. M. Bläser, "On the complexity of the multiplication of matrices of small formats", *Journal of Complexity* 19 (2003), 43–60. [doi:10.1016/s0885-064x(02)00007-9](https://doi.org/10.1016/s0885-064x(02)00007-9)
4. A. Fawzi et al., "Discovering faster matrix multiplication algorithms with reinforcement learning", *Nature* 610 (2022), 47–53. [doi:10.1038/s41586-022-05172-4](https://doi.org/10.1038/s41586-022-05172-4)
5. J. Moosbauer and M. Poole, "Flip graphs with symmetry and new matrix multiplication schemes" (2025). [arXiv:2502.04514](https://arxiv.org/abs/2502.04514)
6. C. Wang, "Automated lower bounds for bilinear complexity over finite fields" (2026). [arXiv:2603.07280](https://arxiv.org/abs/2603.07280)

## Source

Imported from [Yet another catalogue of fast matrix multiplication algorithms](https://fmm.univ-lille.fr/), curated by Alexandre Sedoglavic. Open according to the source as of 2026-10-20. The statement above is written in our own words; see the source for the original wording, history and discussion.