The border rank of the multiplication of 2×2 matrices is seven

By J. M. Landsberg. 2005

78 citations recorded by the source corpus.

One of the leading problems of algebraic complexity theory is matrix multiplication. The naive multiplication of two n× n matrices uses n multiplications. In 1969, Strassen [20] presented an explicit algorithm for multiplying 2 × 2 matrices using seven multiplications. In the opposite direction, Hopcroft and Kerr [12] and Winograd [22] proved independently that there is no algorithm for multiplying 2×2 matrices using only six multiplications. The precise number of multiplications needed to execute matrix multiplication (or any given bilinear map) is called the rank of the bilinear map. A related problem is to determine the border rank of matrix multiplication (or any given bilinear map), first introduced in [6, 5]. Roughly speaking, some bilinear maps may be approximated with arbitrary precision by less complicated bilinear maps and the border rank of a bilinear map is the complexity of arbitrarily small “good” perturbations of the map. These perturbed maps can give rise to fast exact algorithms for matrix multiplication; see [7]. The border rank made appearances in the literature in the 1980s and early 1990s (see, e.g., [6, 5, 19, 8, 15, 2, 10, 11, 4, 3, 17, 16, 18, 1, 9, 21]), but to our knowledge there has not been much progress on the question since then. More precisely, for any complex projective variety X ⊂ CP = PV and point p ∈ PV , define the X-rank of p to be the smallest number r such that p is in the linear span of r points of X. Define σr(X), the r-th secant variety of X, to be the Zariski closure of the set of points of X-rank r, and define the X-border rank of p to be the smallest r such that p ∈ σr(X). The terminology is motivated by the case X = Seg(Pa−1 × Pb−1) ⊂ P(C ⊗ C), the Segre variety of rank one matrices. Then the X-rank of a matrix is just its usual rank. Let A∗, B∗, C be vector spaces and let f : A∗ ×B∗ → C be a bilinear map, i.e., an element of A⊗B⊗C. Let X = Seg(PA×PB×PC) ⊂ P(A⊗B⊗C) denote the Segre variety of decomposable tensors in A⊗B⊗C. The border rank of a bilinear map is its X-border rank. While for the Segre product of two projective spaces, border rank coincides with rank, here they can be quite different. In this paper we prove the theorem stated in the title. Let MMult ∈ C ⊗C ⊗ C denote the matrix multiplication operator for 2 × 2 matrices. Strassen [18] showed that MMult / ∈ σ5(P × P × P). Our method of proof is to decompose

Subfields: Computational Mathematics, Computational Theory and Mathematics, Geometry and Topology

View Paper: https://www.semanticscholar.org/paper/8157c948dcb8095c37fe8d5adea30cb617c33c6a

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mathematics

In Computational Theory and Mathematics

In Geometry and Topology

Citations in the corpus

Structure of the Hessian matrix and an economical implementation of Newton’s method in the problem of canonical approximation of tensors (2010, methodology): “It is called the canonical rank of the tensor S. An algorithm using seven multiplications for 2 × 2 matrices was first proposed in [22]; thus, rankS ≤ 7. In [ 23 ], it was proved that rankS ≥ 7. Consequently, the algorithm with seven multiplications is, in general, optimal in terms of active multipl”
Tensors and Hypermatrices (2013, unknown): “4) of M2 is 7 [Lan06].”
Bounded-rank tensors are defined in bounded degree (2011, background): “Tensor rank is an important notion in such diverse areas as multilinear algebra and algebraic geometry [10, 11, 25]; algebraic statistics [1, 17], in particular with applications to phylogenetics [2, 9, 8, 30], and complexity theory [6, 7, 14, 21, 22, 23, 28, 29].”
Tensor Rank and the Ill-Posedness of the Best Low-Rank Approximation Problem (2006, unknown): “Our definition differs slightly from the usual definition of border rank in the algebraic computational complexity literature [5, 6, 12, 48, 54], which uses the Zariski topology (and is normally defined for tensors over C).”
Tensor Decompositions and Applications (2009, methodology): “, [147]).”