Journal of the American Mathematical Society

Author(s): J. M. Landsberg
Journal: J. Amer. Math. Soc. 19 (2006), 447-459.
MSC (2000): Primary 68Q17
Posted: September 26, 2005
Retrieve article in: PDF

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.

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)

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

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

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

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

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues Previous Article \| Next Article


	Comments: webmaster@ams.org © Copyright 2009, American Mathematical Society Privacy Statement		Search the AMS