Journal of the American Mathematical Society

			Journals Home Search Author Info Subscribe Tech Support My Subscriptions Help
ISSN 1088-6834(e) ISSN 0894-0347(p)

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
Posted: September 26, 2005
MathSciNet review: 2188132
Full-text PDF Free Access

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

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)

	Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
\|