Geodesic
The border rank of the multiplication of 2×2 matrices is seven
Landsberg, J.1
1Department of Mathematics, Texas A& M University, College Station, Texas 77843-3368
Journal of the American Mathematical Society, Tome 19 (2006) no. 2, pp. 447-459
Cet article a éte moissonné depuis la source American Mathematical Society

Voir la notice de l'article

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.
DOI : 10.1090/S0894-0347-05-00506-0

Landsberg, J.  1

1 Department of Mathematics, Texas A& M University, College Station, Texas 77843-3368 
@article{10_1090_S0894_0347_05_00506_0,
     author = {Landsberg, J.},
     title = {The border rank of the multiplication of 2{\texttimes}2 matrices is seven},
     journal = {Journal of the American Mathematical Society},
     pages = {447--459},
     year = {2006},
     volume = {19},
     number = {2},
     doi = {10.1090/S0894-0347-05-00506-0},
     url = {http://geodesic.mathdoc.fr/articles/10.1090/S0894-0347-05-00506-0/}
}
TY  - JOUR
AU  - Landsberg, J.
TI  - The border rank of the multiplication of 2×2 matrices is seven
JO  - Journal of the American Mathematical Society
PY  - 2006
SP  - 447
EP  - 459
VL  - 19
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.1090/S0894-0347-05-00506-0/
DO  - 10.1090/S0894-0347-05-00506-0
ID  - 10_1090_S0894_0347_05_00506_0
ER  - 
%0 Journal Article
%A Landsberg, J.
%T The border rank of the multiplication of 2×2 matrices is seven
%J Journal of the American Mathematical Society
%D 2006
%P 447-459
%V 19
%N 2
%U http://geodesic.mathdoc.fr/articles/10.1090/S0894-0347-05-00506-0/
%R 10.1090/S0894-0347-05-00506-0
%F 10_1090_S0894_0347_05_00506_0
Landsberg, J. The border rank of the multiplication of 2×2 matrices is seven. Journal of the American Mathematical Society, Tome 19 (2006) no. 2, pp. 447-459. doi: 10.1090/S0894-0347-05-00506-0

[1] Bini, D. Border rank of a 𝑝×𝑞×2 tensor and the optimal approximation of a pair of bilinear forms 1980 98 108

[2] Bini, D., Capovani, M. Tensor rank and border rank of band Toeplitz matrices SIAM J. Comput. 1987 252 258

[3] Bini, Dario Tensor and border rank of certain classes of matrices and the fast evaluation of determinant inverse matrix and eigenvalues Calcolo 1985 209 228

[4] Bini, Dario Border rank of 𝑚×𝑛×(𝑚𝑛-𝑞) tensors Linear Algebra Appl. 1986 45 51

[5] Bini, Dario, Capovani, Milvio, Romani, Francesco, Lotti, Grazia 𝑂(𝑛^{2.7799}) complexity for 𝑛×𝑛 approximate matrix multiplication Inform. Process. Lett. 1979 234 235

[6] Bini, Dario, Lotti, Grazia, Romani, Francesco Approximate solutions for the bilinear form computational problem SIAM J. Comput. 1980 692 697

[7] Bürgisser, Peter, Clausen, Michael, Shokrollahi, M. Amin Algebraic complexity theory 1997

[8] Coppersmith, Don, Winograd, Shmuel Matrix multiplication via arithmetic progressions J. Symbolic Comput. 1990 251 280

[9] Automata, languages and programming 1980

[10] De Groote, H. F. Lectures on the complexity of bilinear problems 1987

[11] Griesser, B. A lower bound for the border rank of a bilinear map Calcolo 1986

[12] Hopcroft, J. E., Kerr, L. R. On minimizing the number of multiplications necessary for matrix multiplication SIAM J. Appl. Math. 1971 30 36

[13] Ivey, Thomas A., Landsberg, J. M. Cartan for beginners: differential geometry via moving frames and exterior differential systems 2003

[14] Landsberg, Joseph M., Manivel, Laurent Construction and classification of complex simple Lie algebras via projective geometry Selecta Math. (N.S.) 2002 137 159

[15] Lehmkuhl, Thomas, Lickteig, Thomas On the order of approximation in approximative triadic decompositions of tensors Theoret. Comput. Sci. 1989 1 14

[16] Lickteig, Thomas A note on border rank Inform. Process. Lett. 1984 173 178

[17] Lickteig, Thomas Typical tensorial rank Linear Algebra Appl. 1985 95 120

[18] Strassen, V. Rank and optimal computation of generic tensors Linear Algebra Appl. 1983 645 685

[19] Strassen, V. Degeneration and complexity of bilinear maps: some asymptotic spectra J. Reine Angew. Math. 1991 127 180

[20] Strassen, Volker Gaussian elimination is not optimal Numer. Math. 1969 354 356

[21] Strassen, Volker Algebraic complexity theory 1990 633 672

[22] Winograd, S. On multiplication of 2×2 matrices Linear Algebra Appl. 1971 381 388

Cité par Sources :