首页    期刊浏览 2024年11月28日 星期四
登录注册

文章基本信息

  • 标题:The border support rank of two-by-two matrix multiplication is seven
  • 本地全文:下载
  • 作者:Markus Bläser ; Matthias Christandl ; Jeroen Zuiddam
  • 期刊名称:Chicago Journal of Theoretical Computer Science
  • 印刷版ISSN:1073-0486
  • 出版年度:2018
  • 卷号:2018
  • 出版社:MIT Press ; University of Chicago, Department of Computer Science
  • 摘要:

    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.

国家哲学社会科学文献中心版权所有