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

DOI10.4086/CJTCS.2018.005MaRDI QIDQ4615808zbMATH OpenOpenAlexFDO

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)

Copyright license Creative Commons Attribution 4.0 International

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

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)

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.

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

Cites work

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

Cited in

(1)

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

Describes a project that uses

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)