Remote Access Journal of the American Mathematical Society
Green Open Access

Journal of the American Mathematical Society

ISSN 1088-6834(online) ISSN 0894-0347(print)

 
 

 

The border rank of the multiplication of $ 2\times 2$ matrices is seven


Author: J. M. Landsberg
Journal: J. Amer. Math. Soc. 19 (2006), 447-459
MSC (2000): Primary 68Q17
DOI: https://doi.org/10.1090/S0894-0347-05-00506-0
Published electronically: September 26, 2005
MathSciNet review: 2188132
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • 1. 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, 1980, pp. 98-108. MR 0588996 (82e:68037)
  • 2. D. Bini and M. Capovani, Tensor rank and border rank of band Toeplitz matrices, SIAM J. Comput. 16 (1987), no. 2, 252-258. MR 0882531 (88g:68048)
  • 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. MR 0817042 (87g:65053)
  • 4. -, Border rank of $ m\times n\times (mn-q)$ tensors, Linear Algebra Appl. 79 (1986), 45-51. MR 0847189 (87j:15055)
  • 5. Dario Bini, Milvio Capovani, Francesco Romani, and Grazia Lotti, $ O(n\sp{2.7799})$ complexity for $ n\times n$ approximate matrix multiplication, Inform. Process. Lett. 8 (1979), no. 5, 234-235. MR 0534068 (80h:68024)
  • 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. MR 0592760 (82a:68065)
  • 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. MR 1440179 (99c:68002)
  • 8. Don Coppersmith and Shmuel Winograd, Matrix multiplication via arithmetic progressions, J. Symbolic Comput. 9 (1990), no. 3, 251-280. MR 1056627 (91i:68058)
  • 9. J. W. de Bakker and J. van Leeuwen (eds.), Automata, languages and programming, Lecture Notes in Computer Science, vol. 85, Berlin, Springer-Verlag, 1980. MR 0588986 (81i:68004)
  • 10. H. F. de Groote, Lectures on the complexity of bilinear problems, Lecture Notes in Computer Science, vol. 245, Springer-Verlag, Berlin, 1987. MR 0880703 (88d:68020)
  • 11. B. Griesser, A lower bound for the border rank of a bilinear map, Calcolo 23 (1986), no. 2, 105-114. MR 0897622 (88g:15021)
  • 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. MR 0274293 (43:58)
  • 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. MR 2003610 (2004g:53002)
  • 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. MR 1890196 (2002m:17006)
  • 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. MR 1018840 (91f:68099)
  • 16. Thomas Lickteig, A note on border rank, Inform. Process. Lett. 18 (1984), no. 3, 173-178. MR 0760371 (86c:68040)
  • 17. -, Typical tensorial rank, Linear Algebra Appl. 69 (1985), 95-120. MR 0798367 (87f:15017)
  • 18. V. Strassen, Rank and optimal computation of generic tensors, Linear Algebra Appl. 52/53 (1983), 645-685. MR 85b:15039
  • 19. -, Degeneration and complexity of bilinear maps: some asymptotic spectra, J. Reine Angew. Math. 413 (1991), 127-180. MR 1089800 (92m:11038)
  • 20. Volker Strassen, Gaussian elimination is not optimal, Numer. Math. 13 (1969), 354-356. MR 0248973 (40:2223)
  • 21. -, Algebraic complexity theory, Handbook of theoretical computer science, Vol. A, Elsevier, Amsterdam, 1990, pp. 633-672. MR 1127177
  • 22. S. Winograd, On multiplication of $ 2\times 2$ matrices, Linear Algebra and Appl. 4 (1971), 381-388. MR 0297115 (45:6173)

Similar Articles

Retrieve articles in Journal of the American Mathematical Society with MSC (2000): 68Q17

Retrieve articles in all journals with MSC (2000): 68Q17


Additional Information

J. M. Landsberg
Affiliation: Department of Mathematics, Texas A& M University, College Station, Texas 77843-3368
Email: jml@math.tamu.edu

DOI: https://doi.org/10.1090/S0894-0347-05-00506-0
Keywords: Border rank, complexity of matrix multiplication, secant varieties
Received by editor(s): August 23, 2004
Published electronically: September 26, 2005
Article copyright: © Copyright 2005 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society