Journal of the American Mathematical Society
Published by the American Mathematical Society, the Journal of the American Mathematical Society (JAMS) is devoted to research articles of the highest quality in all areas of pure and applied mathematics.
The 2020 MCQ for Journal of the American Mathematical Society is 4.79.
Journals Home eContent Search About JAMS Editorial Board Author and Submission Information Journal Policies Subscription Information
The border rank of the multiplication of $2\times 2$ matrices is seven
by J. M. Landsberg PDF
J. Amer. Math. Soc. 19 (2006), 447-459 Request permission
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.
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
Retrieve articles in Journal of the American Mathematical Society with MSC (2000): 68Q17
Retrieve articles in all journals with MSC (2000): 68Q17
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
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