New lower bounds for matrix multiplication and the 3x3 determinant Academic Article uri icon

abstract

  • Let $M_{langle u,v,w
    angle}in C^{uv}otimes C^{vw}otimes C^{wu}$ denote the matrix multiplication tensor (and write $M_n=M_{langle n,n,n
    angle}$) and let $det_3in ( 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
    angle})=10$, and $underline R(M_{langle 233
    angle})=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
    angle})geq n^2+1.32n$ for all $ngeq 25$ (previously only $underline R(M_{langle 2nn
    angle})geq n^2+1$ was known) as well as lower bounds for $4leq nleq 25$, and (vi) prove $underline R(M_{langle 3nn
    angle})geq n^2+2 n+1$ for all $ ngeq 21$, where previously only $underline R(M_{langle 3nn
    angle})geq n^2+2$ was known, as well as lower boundsfor $4leq nleq 21$. 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$.

author list (cited authors)

  • Conner, A., Harper, A., & Landsberg, J. M.

publication date

  • January 1, 2019 11:11 AM