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

Markus Bläser, Matthias Christandl, Jeroen Zuiddam

TL;DR

This paper proves that the "border support rank" of two-by-two matrix multiplication is exactly seven. This is a significant result in algebraic complexity theory, as it provides an upper bound on the computational complexity of matrix multiplication algorithms and has implications for quantum communication complexity.

What Problem Does This Paper Address?

The paper tackles a fundamental question in algebraic complexity theory: what is the minimum number of "simple tensors" needed to represent the operation of multiplying two 2x2 matrices? This is related to the "tensor rank" and "border rank" of the matrix multiplication tensor. However, this paper focuses on a related but distinct concept: the "border support rank." The support of a tensor refers to the set of its non-zero entries. The support rank is the minimum rank of a tensor with the same support pattern. The border support rank is the minimum border rank of a tensor with the same support pattern.

Previously, it was known that the border support rank of 2x2 matrix multiplication is at least six. This paper establishes that it is exactly seven, answering a question posed by Cohn and Umans. This is important because upper bounds on the border support rank translate to upper bounds on the computational complexity of matrix multiplication algorithms.

Methods

The paper presents two main approaches to prove the support rank of the 2x2 matrix multiplication tensor is seven over any field (Theorem 1) and then uses a more advanced technique to prove the border support rank is seven over complex numbers (Theorem 2).

For Theorem 1, the authors employ two proofs:

  1. Uniqueness Argument (De Groote's Result): This proof leverages a result by De Groote on the uniqueness of optimal decompositions of the 2x2 matrix multiplication tensor. By perturbing the tensor slightly, they show that if its rank were less than seven, it would lead to a contradiction with the uniqueness property.
  2. Substitution Method: This method involves defining a function that represents the matrix multiplication operation and then systematically substituting variables. By analyzing the rank of the resulting functions after these substitutions, they deduce the minimum rank.

For Theorem 2 (border support rank), the authors utilize a sophisticated method involving highest-weight vectors and polynomials vanishing on secant varieties. This approach, developed in prior work, involves:

  1. Defining Secant Varieties: They consider the variety of tensors with border rank at most r (denoted σr).
  2. Lower Bounds via Polynomials: They leverage the fact that if a tensor t has border rank greater than r, there must exist a homogeneous polynomial that vanishes on σr but not on t.
  3. Highest-Weight Vectors: They use the theory of highest-weight vectors from representation theory to construct specific polynomials that are candidates for vanishing on σr.
  4. Kronecker Coefficients: The construction of these polynomials relies on computing Kronecker coefficients, which relate to the dimensions of certain tensor product representations.
  5. Evaluation: Finally, they evaluate these constructed polynomials on the 2x2 matrix multiplication tensor (or a perturbed version of it) to show that they do not vanish, thus establishing a lower bound on the border support rank.

Datasets

Not discussed in the paper. The paper focuses on theoretical results concerning the structure of a specific mathematical object (the matrix multiplication tensor) rather than empirical evaluation on datasets.

Key Insights and Ideas

  • Support Rank vs. Border Rank: The paper clearly distinguishes between "support rank" and "border support rank," showing that for the 2x2 matrix multiplication tensor, both are equal to seven. This highlights that the structure of non-zero entries (support) is as crucial as the overall complexity (rank) in some contexts.
  • Power of Representation Theory: The use of highest-weight vectors and representation theory provides a powerful framework for constructing specific polynomials that can be used to prove lower bounds on tensor ranks and border ranks. This demonstrates the deep connections between abstract algebra and computational complexity.
  • Perturbation as a Tool: The technique of slightly perturbing the matrix multiplication tensor to analyze its properties (e.g., using De Groote's uniqueness result) is a clever way to circumvent difficulties associated with the exact tensor.
  • Implications for Algorithm Design: The paper explicitly states that upper bounds on the border support rank directly lead to upper bounds on the computational complexity of matrix multiplication algorithms, underscoring the practical relevance of these theoretical findings.

Key Results

  • Theorem 1: The support rank of the 2x2 matrix multiplication tensor is seven over any field F.
  • Theorem 2: The border support rank of the 2x2 matrix multiplication tensor is seven over the complex numbers C.
  • Answering a Question: The paper resolves a question posed by Cohn and Umans regarding the border support rank of 2x2 matrix multiplication.
  • Lower Bound Established: The paper establishes a lower bound of seven for the border support rank, building upon previous work that showed a lower bound of at least six.

Limitations and Future Work

  • Field Dependence: While Theorem 1 holds for any field, Theorem 2 specifically addresses the complex numbers. Extending the border support rank result to arbitrary fields would be a natural next step.
  • Generalization to n x n: The paper focuses on the 2x2 case. A significant open problem is to determine the border support rank for the general n x n matrix multiplication tensor. The current results for n x n are much weaker.
  • Algorithmic Implications: While the paper provides theoretical bounds, translating these into practical, faster matrix multiplication algorithms remains a challenging area of research. The authors mention that their results are relevant for designing such algorithms.
  • Quantum Communication Complexity: The paper highlights the connection to quantum communication complexity. Further exploration of these connections and potential applications in that domain is a promising avenue.

Summary updated

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.
BibTeX
@article{blaser2018border,
  author = {Markus Bläser and Matthias Christandl and Jeroen Zuiddam},
  title = {{The border support rank of two-by-two matrix multiplication is seven}},
  journal = {Chic. J. Theor. Comput. Sci.},
  year = {2018},
  url = {https://openreview.net/forum?id=3P5qZuvtG8},
}
Figure