New lower bounds for matrix multiplication and the 3x3 determinant

Abstract

Let $M_{⟨u,v,w⟩}\in C^{uv}\otimes C^{vw}\otimes C^{wu}$ denote the matrix multiplication tensor (and write $M_n=M_{⟨n,n,n⟩}$) and let $de{t}_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_{⟨223⟩})=10$, and $\underline{R}(M_{⟨233⟩})=14$, where previously the only nontrivial matrix multiplication tensor whose border rank had been determined was $M_2$,(iii) prove $\underline{R}(M_3)\ge 17$, (iv) prove $\underline{R}(de{t}_3)=17$, improving the previous lower bound of $12$, (v) prove $\underline{R}(M_{⟨2nn⟩})\ge n^2+1.32n$ for all $n\ge 25$ (previously only $\underline{R}(M_{⟨2nn⟩})\ge n^2+1$ was known) as well as lower bounds for $4\le n\le 25$, and (vi) prove $\underline{R}(M_{⟨3nn⟩})\ge n^2+2n+1$ for all $n\ge 21$, where previously only $\underline{R}(M_{⟨3nn⟩})\ge n^2+2$ was known, as well as lower boundsfor $4\le n\le 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$.

23 pages

References in corpus (1)

• Geometric lower bounds for generalized ranks

Cited by in corpus (1)

• Bad and good news for Strassen's laser method: Border rank of the 3x3 permanent and strict submultiplicativity