×

The border rank of the multiplication of \( 2\times 2\) matrices is seven. (English) Zbl 1088.68069

Summary: 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 long-standing problem dating back to Strassen’s discovery in 1968 that the map could be executed by performing seven multiplications.

MSC:

68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] D. Bini, Border rank of a \?\times \?\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. · Zbl 0445.68028
[2] D. Bini and M. Capovani, Tensor rank and border rank of band Toeplitz matrices, SIAM J. Comput. 16 (1987), no. 2, 252 – 258. · Zbl 0615.15014 · doi:10.1137/0216021
[3] 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. · Zbl 0608.65018 · doi:10.1007/BF02576204
[4] Dario Bini, Border rank of \?\times \?\times (\?\?-\?) tensors, Linear Algebra Appl. 79 (1986), 45 – 51. · Zbl 0598.15026 · doi:10.1016/0024-3795(86)90291-0
[5] Dario Bini, Milvio Capovani, Francesco Romani, and Grazia Lotti, \?(\?^{2.7799}) complexity for \?\times \? approximate matrix multiplication, Inform. Process. Lett. 8 (1979), no. 5, 234 – 235. · Zbl 0395.68048 · doi:10.1016/0020-0190(79)90113-3
[6] Dario Bini, Grazia Lotti, and Francesco Romani, Approximate solutions for the bilinear form computational problem, SIAM J. Comput. 9 (1980), no. 4, 692 – 697. · Zbl 0446.68035 · doi:10.1137/0209053
[7] 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. · Zbl 1087.68568
[8] Don Coppersmith and Shmuel Winograd, Matrix multiplication via arithmetic progressions, J. Symbolic Comput. 9 (1990), no. 3, 251 – 280. · Zbl 0702.65046 · doi:10.1016/S0747-7171(08)80013-2
[9] J. W. de Bakker and J. van Leeuwen , Automata, languages and programming, Lecture Notes in Computer Science, vol. 85, Springer-Verlag, Berlin-New York, 1980. · Zbl 0426.00014
[10] H. F. de Groote, Lectures on the complexity of bilinear problems, Lecture Notes in Computer Science, vol. 245, Springer-Verlag, Berlin, 1987. · Zbl 0609.68032
[11] B. Griesser, A lower bound for the border rank of a bilinear map, Calcolo 23 (1986), no. 2, 105 – 114 (1987). · Zbl 0613.15024 · doi:10.1007/BF02579423
[12] 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. · Zbl 0215.55501 · doi:10.1137/0120004
[13] 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. · Zbl 1105.53001
[14] 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. · Zbl 1073.14551 · doi:10.1007/s00029-002-8103-5
[15] 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. · Zbl 0678.15024 · doi:10.1016/0304-3975(89)90141-2
[16] Thomas Lickteig, A note on border rank, Inform. Process. Lett. 18 (1984), no. 3, 173 – 178. · Zbl 0539.68029 · doi:10.1016/0020-0190(84)90023-1
[17] Thomas Lickteig, Typical tensorial rank, Linear Algebra Appl. 69 (1985), 95 – 120. · Zbl 0575.15013 · doi:10.1016/0024-3795(85)90070-9
[18] V. Strassen, Rank and optimal computation of generic tensors, Linear Algebra Appl. 52/53 (1983), 645 – 685. · Zbl 0514.15018 · doi:10.1016/0024-3795(83)80041-X
[19] V. Strassen, Degeneration and complexity of bilinear maps: some asymptotic spectra, J. Reine Angew. Math. 413 (1991), 127 – 180. · Zbl 0746.65049 · doi:10.1515/crll.1991.413.127
[20] Volker Strassen, Gaussian elimination is not optimal, Numer. Math. 13 (1969), 354 – 356. · Zbl 0185.40101 · doi:10.1007/BF02165411
[21] Volker Strassen, Algebraic complexity theory, Handbook of theoretical computer science, Vol. A, Elsevier, Amsterdam, 1990, pp. 633 – 672. · Zbl 0900.68247
[22] S. Winograd, On multiplication of 2\times 2 matrices, Linear Algebra and Appl. 4 (1971), 381 – 388. · Zbl 0225.68018
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.