New lower bounds for the border rank of matrix multiplication

Abstract

The border rank of the matrix multiplication operator for n by n matrices is a standard measure of its complexity. Using techniques from algebraic geometry and representation theory, we show the border rank is at least 2n^2-n. Our bounds are better than the previous lower bound (due to Lickteig in 1985) of 3/2 n^2+ n/2 -1 for all n>2. 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.

9 pages. Version 1 contained an error in the proof of its main theorem and in the course of fixing it we proved a stronger statement. v3: proof of main theorem moved up

References in corpus (3)

• Equations for secant varieties of Veronese and other varieties
• Explicit tensors of border rank at least 2n-1
• Explicit Lower Bounds via Geometric Complexity Theory

Cited by in corpus (11)

• Four lectures on secant varieties
• Unifying and generalizing known lower bounds via geometric complexity theory
• On the rank of $n\times n$ matrix multiplication
• Rank and border rank of Kronecker powers of tensors and Strassen's laser method
• Computations and Equations for Segre-Grassmann hypersurfaces
• New lower bounds for the rank of matrix multiplication
• Explicit tensors of border rank at least 2n-1
• Geometric Complexity Theory: an introduction for geometers
• Explicit Lower Bounds via Geometric Complexity Theory
• Plethysm and fast matrix multiplication
• Equations for lower bounds on border rank