# New lower bounds for matrix multiplication and the 3x3 determinant Academic Article •
• Overview
•
• Research
•
•
• View All
•

### 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