The border support rank of two-by-two matrix multiplication is seven

DOI10.4086/CJTCS.2018.005zbMATH Open1473.15029arXiv1705.09652OpenAlexW2617690415MaRDI QIDQ4615808FDOQ4615808

Authors: Markus Bläser, Matthias Christandl, Jeroen Zuiddam 

Publication date: 29 January 2019

Published in: Chicago Journal of Theoretical Computer Science (Search for Journal in Brave)

Abstract: We show that the border support rank of the tensor corresponding to two-by-two matrix multiplication is seven over the complex numbers. We do this by constructing two polynomials that vanish on all complex tensors with format four-by-four-by-four and border rank at most six, but that do not vanish simultaneously on any tensor with the same support as the two-by-two matrix multiplication tensor. This extends the work of Hauenstein, Ikenmeyer, and Landsberg. We also give two proofs that the support rank of the two-by-two matrix multiplication tensor is seven over any field: one proof using a result of De Groote saying that the decomposition of this tensor is unique up to sandwiching, and another proof via the substitution method. These results answer a question asked by Cohn and Umans. Studying the border support rank of the matrix multiplication tensor is relevant for the design of matrix multiplication algorithms, because upper bounds on the border support rank of the matrix multiplication tensor lead to upper bounds on the computational complexity of matrix multiplication, via a construction of Cohn and Umans. Moreover, support rank has applications in quantum communication complexity.

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

Recommendations

• The border rank of the multiplication of $2\times 2$ matrices is seven
• On the Geometry of Border Rank Algorithms for n × 2 by 2 × 2 Matrix Multiplication
• New lower bounds for the border rank of matrix multiplication
• The rank of rank-2 modified matrix
• A bilinear algorithm of length \(22\) for approximate multiplication of \(2\times 7\) and \(7\times 2\) matrices
• A \(2\mathbf{n}^2-\log_2(\mathbf{n})-1\) lower bound for the border rank of matrix multiplication
• A simultaneous decomposition for seven matrices with applications
• The integer cp-rank of \(2 \times 2\) matrices
• Structural and sparsity properties of symmetric 7-matrices
• Border rank of m\(\times n\times (mn-q)\) tensors

zbMATH Keywords

algebraic complexity theorymatrix multiplicationborder support rank

Mathematics Subject Classification ID

Multilinear algebra, tensor calculus (15A69) Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30)

Cites Work

• Gaussian elimination is not optimal
• Secant varieties of Segre-Veronese varieties
• On multiplication of 2 \(\times\) 2 matrices
• Tensor rank is NP-complete
• Nondeterministic Quantum Query and Communication Complexities
• On Minimizing the Number of Multiplications Necessary for Matrix Multiplication
• On varieties of optimal algorithms for the computation of bilinear mappings. II. Optimal algorithms for \(2\times 2\)-matrix multiplication
• Lie Groups, Lie Algebras, and Representations
• Fast matrix multiplication using coherent configurations

Cited In (1)

• The border rank of the multiplication of $2\times 2$ matrices is seven

Uses Software

• SageMath
• Schurfunctors

This page was built for publication: The border support rank of two-by-two matrix multiplication is seven

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