New lower bounds for matrix multiplication and the 3x3 determinant

arXiv1911.07981MaRDI QIDQ6329438FDOQ6329438

Authors: Austin Conner, J. M. Landsberg 

Publication date: 18 November 2019

Abstract: Let $M_{langleu,v,wangle}in{C}^{uv}otimes{C}^{vw}otimes{C}^{wu}$ denote the matrix multiplication tensor (and write $M_n=M_{langlen,n,nangle}$) and let $de{t}_{3}in(C^9{)}^{otimes3}$ denote the determinant polynomial considered as a tensor. For a tensor $T$, let $underlineR(T)$ denote its border rank. We (i) give the first hand-checkable algebraic proof that $underlineR(M_2)=7$,(ii) prove $underlineR(M_{langle223angle})=10$, and $underlineR(M_{langle233angle})=14$, where previously the only nontrivial matrix multiplication tensor whose border rank had been determined was $M_2$,(iii) prove $underlineR(M_3)geq17$, (iv) prove $underlineR(de{t}_3)=17$, improving the previous lower bound of $12$, (v) prove $underlineR(M_{langle2nnangle})geq{n}^2+1.32n$ for all $ngeq25$ (previously only $underlineR(M_{langle2nnangle})geq{n}^2+1$ was known) as well as lower bounds for $4leqnleq25$, and (vi) prove $underlineR(M_{langle3nnangle})geq{n}^2+2n+1$ for all $ngeq21$, where previously only $underlineR(M_{langle3nnangle})geq{n}^2+2$ was known, as well as lower boundsfor $4leqnleq21$. Our results utilize a new technique initiated by Buczy'{n}ska and Buczy'{n}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$.

This page was built for publication: New lower bounds for matrix multiplication and the 3x3 determinant

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6329438)