New lower bounds for matrix multiplication and $operatorname {det}_3$ Academic Article uri icon

abstract

  • Abstract Let $M_{langle mathbf {u},mathbf {v},mathbf {w}
    angle }in mathbb C^{mathbf {u}mathbf {v}}{mathord { otimes } } mathbb C^{mathbf {v}mathbf {w}}{mathord { otimes } } mathbb C^{mathbf {w}mathbf {u}}$     denote the matrix multiplication tensor (and write $M_{langle mathbf {n}
    angle }=M_{langle mathbf {n},mathbf {n},mathbf {n}
    angle }$     ), and let $operatorname {det}_3in (mathbb C^9)^{{mathord { otimes } } 3}$ denote the determinant polynomial considered as a tensor. For a tensor T, let $underline {mathbf {R}}(T)$ denote its border rank. We (i) give the first hand-checkable algebraic proof that $underline {mathbf {R}}(M_{langle 2
    angle })=7$     , (ii) prove $underline {mathbf {R}}(M_{langle 223
    angle })=10$     and $underline {mathbf {R}}(M_{langle 233
    angle })=14$     , where previously the only nontrivial matrix multiplication tensor whose border rank had been determined was $M_{langle 2
    angle }$     , (iii) prove $underline {mathbf {R}}( M_{langle 3
    angle })geq 17$     , (iv) prove $underline {mathbf {R}}(operatorname {det}_3)=17$ , improving the previous lower bound of $12$ , (v) prove $underline {mathbf {R}}(M_{langle 2mathbf {n}mathbf {n}
    angle })geq mathbf {n}^2+1.32mathbf {n}$     for all $mathbf {n}geq 25$ , where previously only $underline {mathbf {R}}(M_{langle 2mathbf {n}mathbf {n}
    angle })geq mathbf {n}^2+1$     was known, as well as lower bounds for $4leq mathbf {n}leq 25$ , and (vi) prove $underline {mathbf {R}}(M_{langle 3mathbf {n}mathbf {n}
    angle })geq mathbf {n}^2+1.6mathbf {n}$     for all

published proceedings

  • FORUM OF MATHEMATICS PI

author list (cited authors)

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

complete list of authors

  • Conner, Austin||Harper, Alicia||Landsberg, JM

publication date

  • 2023