Exact bilinear rank of the 3×3 matrix product
Let $M_3 = \sum_{i,j,k=1}^{3} e_{ij} \otimes e_{jk} \otimes e_{ki} \in \mathbb{C}^9 \otimes \mathbb{C}^9 \otimes \mathbb{C}^9$ be the tensor of $3 \times 3$ matrix multiplication, and let $R$ denote tensor rank over $\mathbb{C}$. Equivalently, $R(M_3)$ is the least $r$ for which there are complex coefficients $u_{t,ab}$, $v_{t,cd}$, $w_{ij,t}$ with $$(AB)_{ij} = \sum_{t=1}^{r} w_{ij,t} \left(\sum_{a,b=1}^{3} u_{t,ab} A_{ab}\right) \left(\sum_{c,d=1}^{3} v_{t,cd} B_{cd}\right)$$ for all $A, B \in \mathbb{C}^{3 \times 3}$ and all $i, j$: the least number of multiplications in a bilinear algorithm for $3 \times 3$ matrices. Laderman found such an algorithm with $r = 23$, and Bläser proved $R(M_3) \ge 19$.
Problem. Determine $R(M_3)$.
Source: Classical, with no single originator; Laderman (1976) gave the upper bound 23 and Bläser (2003) the lower bound 19. See Bläser (2013), Example 5.10, and Alman and Li (2026), Section 1.
Imported from github.com/ajt60gaibb/OpenProblemsInNLA.
Classification
- Primary
- AG — Algebraic Geometry
- Secondary
- NA
- Keywords
- bilinear complexity, matrix multiplication, OpenProblemsInNLA, tensor rank
- Literature checked
- Oct. 8, 2026 by clemens-admin
References
@article{laderman1976,
author = {Laderman, Julian D.},
title = {A noncommutative algorithm for multiplying $3\times 3$ matrices using 23 multiplications},
journal = {Bull. Amer. Math. Soc.},
volume = {82},
number = {1},
year = {1976},
pages = {126--128},
doi = {10.1090/S0002-9904-1976-13988-2},
}
@article{blaser2003,
author = {Bl{\"a}ser, Markus},
title = {On the complexity of the multiplication of matrices of small formats},
journal = {J. Complexity},
volume = {19},
number = {1},
year = {2003},
pages = {43--60},
doi = {10.1016/S0885-064X(02)00007-9},
}
@book{blaser2013,
author = {Bl{\"a}ser, Markus},
title = {Fast Matrix Multiplication},
series = {Theory of Computing Library, Graduate Surveys},
number = {5},
publisher = {Theory of Computing Library},
year = {2013},
pages = {1--60},
doi = {10.4086/toc.gs.2013.005},
}
@inproceedings{alman2026,
author = {Alman, Josh and Li, Baitian},
title = {Asymptotic Rank Speedup Theorems, Revisited},
booktitle = {41st Computational Complexity Conference (CCC 2026)},
editor = {Moshkovitz, Dana},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
volume = {383},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
year = {2026},
pages = {36:1--36:42},
doi = {10.4230/LIPIcs.CCC.2026.36},
eprint = {2605.21738},
archivePrefix = {arXiv},
}
@misc{openproblemsinnla-ac02,
author = {Townsend, Alex},
title = {{AC-02}: Exact bilinear rank of the $3\times3$ matrix product},
howpublished = {Open Problems in Numerical Linear Algebra, GitHub repository},
year = {2026},
url = {https://github.com/ajt60gaibb/OpenProblemsInNLA/blob/main/arithmetic-and-complexity/AC-02/README.md},
note = {Read at commit b8c7852, 2026-10-07},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00180, "Exact bilinear rank of the 3×3 matrix product", clopen.solutions.