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

Markus Bläser; Matthias Christandl; Jeroen Zuiddam

doi:10.4086/cjtcs.2018.005

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

Markus Bläser, Matthias Christandl, Jeroen Zuiddam

Department of Mathematical Sciences

95 Downloads (Pure)

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 may be interpreted as a quantum communication complexity measure.

Original language	English
Article number	5
Journal	Chicago Journal of Theoretical Computer Science
Volume	2018
Pages (from-to)	1-16
ISSN	1073-0486
DOIs	https://doi.org/10.4086/cjtcs.2018.005
Publication status	Published - 2018

Access to Document

10.4086/cjtcs.2018.005

ArticleOAFinal published version, 250 KBLicence: CC BY

Cite this

@article{a0c8a3cc92ac4138804ecc486fefffc1,

title = "The border support rank of two-by-two matrix multiplication is seven",

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 may be interpreted as a quantum communication complexity measure.",

author = "Markus Bl{\"a}ser and Matthias Christandl and Jeroen Zuiddam",

year = "2018",

doi = "10.4086/cjtcs.2018.005",

language = "English",

volume = "2018",

pages = "1--16",

journal = "Chicago Journal of Theoretical Computer Science",

issn = "1073-0486",

publisher = "Department of Computer Science, The University of Chicago ",

}

TY - JOUR

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

AU - Bläser, Markus

AU - Christandl, Matthias

AU - Zuiddam, Jeroen

PY - 2018

Y1 - 2018

N2 - 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 may be interpreted as a quantum communication complexity measure.

AB - 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 may be interpreted as a quantum communication complexity measure.

U2 - 10.4086/cjtcs.2018.005

DO - 10.4086/cjtcs.2018.005

M3 - Journal article

SN - 1073-0486

VL - 2018

SP - 1

EP - 16

JO - Chicago Journal of Theoretical Computer Science

JF - Chicago Journal of Theoretical Computer Science

M1 - 5

ER -