The rank of n n matrix multiplication is at least 3n^2 - 22n^32 - 3n

DOI10.1016/J.LAA.2013.01.031zbMATH Open1284.68301arXiv1211.6320OpenAlexW1737655677MaRDI QIDQ389730FDOQ389730

Authors: Alex Massarenti, Emanuele Raviolo 

Publication date: 21 January 2014

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

Abstract: For every $pleqn$ positive integer we obtain the lower bound $$ for the rank of the $nimesn$ matrix multiplication. This bound improves the previous one $$ due to Landsberg. Furthermore our bound improves the classic bound $frac52n^2-3n$, due to Bl"aser, for every $ngeq132$. Finally, for $p=2$, with a sligtly different strategy we menage to obtain the lower bound $frac83n^2-7n$ which improves Bl"aser's bound for any $ngeq24$.

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

Recommendations

• New lower bounds for the rank of matrix multiplication
• A \(2\mathbf{n}^2-\log_2(\mathbf{n})-1\) lower bound for the border rank of matrix multiplication
• New lower bounds for the border rank of matrix multiplication
• scientific article; zbMATH DE number 1689048
• The border rank of the multiplication of $2\times 2$ matrices is seven

zbMATH Keywords

tensorscomplexity theorymatrix multiplication

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) 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)

Cites Work

• Gaussian elimination is not optimal
• Title not available (Why is that?)
• New Lower Bounds for the Rank of Matrix Multiplication
• Rank and optimal computation of generic tensors
• New lower bounds for the border rank of matrix multiplication

Cited In (15)

• Effective identifiability criteria for tensors and polynomials
• Corrigendum to ``The rank of \(n{\times}n\) matrix multiplication is at least \(3n^2 - 2\sqrt{2}n^{\frac{3}{2}} - 3n\)
• On the nuclear norm and the singular value decomposition of tensors
• An introduction to the computational complexity of matrix multiplication
• On Comon's and Strassen's conjectures
• Lower bound for ranks of invariant forms
• Unifying known lower bounds via geometric complexity theory
• New lower bounds for the border rank of matrix multiplication
• Codimension one Fano distributions on Fano manifolds
• On secant dimensions and identifiability of flag varieties
• Geometric complexity theory: an introduction for geometers
• On non-commutative rank and tensor rank
• Decomposition Algorithms for Tensors and Polynomials
• On secant defectiveness and identifiability of Segre-Veronese varieties
• Generalized varieties of sums of powers

This page was built for publication: The rank of \(n \times n\) matrix multiplication is at least \(3n^2 - 2\sqrt{2}n^{\frac{3}{2}} - 3n\)

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