New lower bounds for the border rank of matrix multiplication Academic Article uri icon

abstract

  • 2015 Joseph M. Landsberg and Giorgio Ottaviani. The border rank of the matrix multiplication operator for nn matrices is a standard measure of its complexity. Using techniques from algebraic geometry and representation theory, we show the border rank is at least 2n2 n. Our bounds are better than the previous lower bound (due to Lickteig in 1985) of 3n2/2+n/2 1 for all n 3. The bounds are obtained by finding new equations that bilinear maps of small border rank must satisfy, i. e., new equations for secant varieties of triple Segre products, that matrix multiplication fails to satisfy.

published proceedings

  • Theory of Computing

author list (cited authors)

  • Landsberg, J. M., & Ottaviani, G.

complete list of authors

  • Landsberg, Joseph M||Ottaviani, Giorgio

publication date

  • August 2015