New Lower Bounds for the Rank of Matrix Multiplication

DOI10.1137/120880276zbMATH Open1298.68100arXiv1206.1530OpenAlexW2964247109MaRDI QIDQ5419033FDOQ5419033

J. M. Landsberg

Publication date: 4 June 2014

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Abstract: The rank of the matrix multiplication operator for nxn matrices is one of the most studied quantities in algebraic complexity theory. I prove that the rank is at least n^2-o(n^2). More precisely, for any integer pleq n -1, the rank is at least (3- 1/(p+1))n^2-(1+2p�inom{2p}{p-1})n. The previous lower bound, due to Blaser, was 5n^2/2-3n (the case p=1). The new bounds improve Blaser's bound for all n>84. I also prove lower bounds for rectangular matrices significantly better than the the previous bound.

Full work available at URL: https://arxiv.org/abs/1206.1530

zbMATH Keywords

rankmatrix multiplication

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Effectivity, complexity and computational aspects of algebraic geometry (14Q20) Computational aspects and applications of commutative rings (13P99)

Cited In (22)

• On bilinear complexity of multiplying \(2 \times 2\)-matrix by \(2 \times m\)-matrix over finite field
• Nontriviality of equations and explicit tensors in \(\mathbb{C}^m \otimes \mathbb{C}^m \otimes \mathbb{C}^m\) of border rank at least \(2m - 2\)
• Fast matrix multiplication and its algebraic neighbourhood
• Corrigendum to ``The rank of \(n{\times}n\) matrix multiplication is at least \(3n^2 - 2\sqrt{2}n^{\frac{3}{2}} - 3n\)
• Universal points in the asymptotic spectrum of tensors
• Small-depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication, with Applications.
• Breaking the k ² barrier for explicit RIP matrices
• A refined laser method and faster matrix multiplication
• On the nuclear norm and the singular value decomposition of tensors
• An introduction to the computational complexity of matrix multiplication
• The rank of \(n \times n\) matrix multiplication is at least \(3n^2 - 2\sqrt{2}n^{\frac{3}{2}} - 3n\)
• New applications of the polynomial method: The cap set conjecture and beyond
• Lower bound for ranks of invariant forms
• Unifying known lower bounds via geometric complexity theory
• Abelian tensors
• A New Algorithm for Computing the Rank of a Matrix
• On the Geometry of Border Rank Decompositions for Matrix Multiplication and Other Tensors with Symmetry
• On non-commutative rank and tensor rank
• Improving the numerical stability of fast matrix multiplication
• Improved bound for rank revealing LU factorizations
• A Lower Bound for Matrix Multiplication
• A lower bound for bilinear complexity of matrix multiplication over a finite field

This page was built for publication: New Lower Bounds for the Rank of Matrix Multiplication

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5419033)