# New lower bounds for matrix multiplication and the 3x3 determinant

Preprint · Austin Conner, Alicia Harper, J. M. Landsberg

- Archive id: arxiv:1911.07981
- Published: 2019-11-18
- arXiv: https://arxiv.org/abs/1911.07981
- Source URL: https://arxiv.org/abs/1911.07981
- PDF: https://arxiv.org/pdf/1911.07981
- Provenance: arxiv

## Abstract

Let $M\_{\\langle u,v,w\\rangle}\\in C^{uv}\\otimes C^{vw}\\otimes C^{wu}$ denote the matrix multiplication tensor (and write $M\_n=M\_{\\langle n,n,n\\rangle}$) and let $det\_3\\in ( C^9)^{\\otimes 3}$ denote the determinant polynomial considered as a tensor. For a tensor $T$, let $\\underline R(T)$ denote its border rank. We (i) give the first hand-checkable algebraic proof that $\\underline R(M\_2)=7$,(ii) prove $\\underline R(M\_{\\langle 223\\rangle})=10$, and $\\underline R(M\_{\\langle 233\\rangle})=14$, where previously the only nontrivial matrix multiplication tensor whose border rank had been determined was $M\_2$,(iii) prove $\\underline R( M\_3)\\geq 17$, (iv) prove $\\underline R( det\_3)=17$, improving the previous lower bound of $12$, (v) prove $\\underline R(M\_{\\langle 2nn\\rangle})\\geq n^2+1.32n$ for all $n\\geq 25$ (previously only $\\underline R(M\_{\\langle 2nn\\rangle})\\geq n^2+1$ was known) as well as lower bounds for $4\\leq n\\leq 25$, and (vi) prove $\\underline R(M\_{\\langle 3nn\\rangle})\\geq n^2+2 n+1$ for all $ n\\geq 21$, where previously only $\\underline R(M\_{\\langle 3nn\\rangle})\\geq n^2+2$ was known, as well as lower boundsfor $4\\leq n\\leq 21$. Our results utilize a new technique initiated by Buczyńska and Buczyński, called border apolarity. The two key ingredients are: (i) the use of a multi-graded ideal associated to a border rank $r$ decomposition of any tensor, and (ii) the exploitation of the large symmetry group of $T$ to restrict to $B\_T$-invariant ideals, where $B\_T$ is a maximal solvable subgroup of the symmetry group of $T$.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.