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

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

Authors Alex Massarenti, Emanuele Raviolo

Publication date 21 January 2014

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

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

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)

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$.

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

Cites work

• scientific article; zbMATH DE number 5968745 (Why is no real title available?)
• Gaussian elimination is not optimal
• New lower bounds for the border rank of matrix multiplication
• New lower bounds for the rank of matrix multiplication
• Rank and optimal computation of generic tensors

Cited in

(17)

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

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)