New lower bounds for the border rank of matrix multiplication

2011/12/27 by J. M. Landsberg, Giorgio Ottaviani, Landsberg, J. M. +1 · 7 citations
Mathematics · Computer Science · #Tensor decomposition and applications #Coding theory and cryptography #Mathematical Approximation and Integration

paper · pdf · doi:10.48550/arxiv.1112.6007

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²-n. Our bounds are better than the previous lower bound (due to Lickteig in 1985) of 3/2 n²+ 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.

Citations

• Asymptotic Formulaae in Combinatory Analysis

Cited by

• Waring decompositions of the product of two quadrics: the small rank cases
• New lower bounds for the rank of matrix multiplication
• Generalized Additive Decompositions of Symmetric Tensors
• Border rank lower bounds for families of GL(V)-invariant tensors
• Explicit tensors of border rank at least 2n-1
• Explicit Lower Bounds via Geometric Complexity Theory
• On the construction of a counterexample to Strassen's rank additivity conjecture

Related

• New lower bounds for the rank of matrix multiplication
• On the geometry of border rank algorithms for n x 2 by 2 x 2 matrix multiplication
• Equations for lower bounds on border rank
• Explicit Lower Bounds via Geometric Complexity Theory
• A 2n²-log(n)-1 lower bound for the border rank of matrix multiplication