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
Bibliographic Information
- J. M. Landsberg
- Affiliation: Department of Mathematics, Texas A& M University, College Station, Texas 77843-3368
- MR Author ID: 288424
- Email: jml@math.tamu.edu
- Received by editor(s): August 23, 2004
- Published electronically: September 26, 2005
- © Copyright 2005
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - Journal: J. Amer. Math. Soc. 19 (2006), 447-459
- MSC (2000): Primary 68Q17
- DOI: https://doi.org/10.1090/S0894-0347-05-00506-0
- MathSciNet review: 2188132