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

Landsberg, J.

doi:10.1090/S0894-0347-05-00506-0

The border rank of the multiplication of $2\times 2$ matrices is seven
HTML articles powered by AMS MathViewer

by J. M. Landsberg

J. Amer. Math. Soc. 19 (2006), 447-459

DOI: https://doi.org/10.1090/S0894-0347-05-00506-0

Published electronically: September 26, 2005

PDF | Request permission

Abstract:

We prove that the bilinear map corresponding to matrix multiplication of $2 \times 2$ matrices is not the limit of a sequence of bilinear maps that can be executed by performing six multiplications. This solves a longstanding problem dating back to Strassen’s discovery in 1968 that the map could be executed by performing seven multiplications.

References

D. Bini, Border rank of a $p\times q\times 2$ tensor and the optimal approximation of a pair of bilinear forms, Automata, languages and programming (Proc. Seventh Internat. Colloq., Noordwijkerhout, 1980) Lecture Notes in Comput. Sci., vol. 85, Springer, Berlin-New York, 1980, pp. 98–108. MR 588996
D. Bini and M. Capovani, Tensor rank and border rank of band Toeplitz matrices, SIAM J. Comput. 16 (1987), no. 2, 252–258. MR 882531, DOI 10.1137/0216021
Dario Bini, Tensor and border rank of certain classes of matrices and the fast evaluation of determinant inverse matrix and eigenvalues, Calcolo 22 (1985), no. 1, 209–228. MR 817042, DOI 10.1007/BF02576204
Dario Bini, Border rank of $m\times n\times (mn-q)$ tensors, Linear Algebra Appl. 79 (1986), 45–51. MR 847189, DOI 10.1016/0024-3795(86)90291-0
Dario Bini, Milvio Capovani, Francesco Romani, and Grazia Lotti, $O(n^{2.7799})$ complexity for $n\times n$ approximate matrix multiplication, Inform. Process. Lett. 8 (1979), no. 5, 234–235. MR 534068, DOI 10.1016/0020-0190(79)90113-3
Dario Bini, Grazia Lotti, and Francesco Romani, Approximate solutions for the bilinear form computational problem, SIAM J. Comput. 9 (1980), no. 4, 692–697. MR 592760, DOI 10.1137/0209053
Peter Bürgisser, Michael Clausen, and M. Amin Shokrollahi, Algebraic complexity theory, Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 315, Springer-Verlag, Berlin, 1997. With the collaboration of Thomas Lickteig. MR 1440179, DOI 10.1007/978-3-662-03338-8
Don Coppersmith and Shmuel Winograd, Matrix multiplication via arithmetic progressions, J. Symbolic Comput. 9 (1990), no. 3, 251–280. MR 1056627, DOI 10.1016/S0747-7171(08)80013-2
J. W. de Bakker and J. van Leeuwen (eds.), Automata, languages and programming, Lecture Notes in Computer Science, vol. 85, Springer-Verlag, Berlin-New York, 1980. MR 588986
H. F. de Groote, Lectures on the complexity of bilinear problems, Lecture Notes in Computer Science, vol. 245, Springer-Verlag, Berlin, 1987. MR 880703, DOI 10.1007/BFb0020719
B. Griesser, A lower bound for the border rank of a bilinear map, Calcolo 23 (1986), no. 2, 105–114 (1987). MR 897622, DOI 10.1007/BF02579423
J. E. Hopcroft and L. R. Kerr, On minimizing the number of multiplications necessary for matrix multiplication, SIAM J. Appl. Math. 20 (1971), 30–36. MR 274293, DOI 10.1137/0120004
Thomas A. Ivey and J. M. Landsberg, Cartan for beginners: differential geometry via moving frames and exterior differential systems, Graduate Studies in Mathematics, vol. 61, American Mathematical Society, Providence, RI, 2003. MR 2003610, DOI 10.1090/gsm/061
Joseph M. Landsberg and Laurent Manivel, Construction and classification of complex simple Lie algebras via projective geometry, Selecta Math. (N.S.) 8 (2002), no. 1, 137–159. MR 1890196, DOI 10.1007/s00029-002-8103-5
Thomas Lehmkuhl and Thomas Lickteig, On the order of approximation in approximative triadic decompositions of tensors, Theoret. Comput. Sci. 66 (1989), no. 1, 1–14. MR 1018840, DOI 10.1016/0304-3975(89)90141-2
Thomas Lickteig, A note on border rank, Inform. Process. Lett. 18 (1984), no. 3, 173–178. MR 760371, DOI 10.1016/0020-0190(84)90023-1
Thomas Lickteig, Typical tensorial rank, Linear Algebra Appl. 69 (1985), 95–120. MR 798367, DOI 10.1016/0024-3795(85)90070-9
V. Strassen, Rank and optimal computation of generic tensors, Linear Algebra Appl. 52/53 (1983), 645–685. MR 709378, DOI 10.1016/0024-3795(83)80041-X
V. Strassen, Degeneration and complexity of bilinear maps: some asymptotic spectra, J. Reine Angew. Math. 413 (1991), 127–180. MR 1089800, DOI 10.1515/crll.1991.413.127
Volker Strassen, Gaussian elimination is not optimal, Numer. Math. 13 (1969), 354–356. MR 248973, DOI 10.1007/BF02165411
Volker Strassen, Algebraic complexity theory, Handbook of theoretical computer science, Vol. A, Elsevier, Amsterdam, 1990, pp. 633–672. MR 1127177
S. Winograd, On multiplication of $2\times 2$ matrices, Linear Algebra Appl. 4 (1971), 381–388. MR 297115, DOI 10.1016/0024-3795(71)90009-7