Comptes Rendus
Lie algebras/Computer science
Plethysm and fast matrix multiplication
Comptes Rendus. Mathématique, Volume 356 (2018) no. 1, pp. 52-55.

Motivated by the symmetric version of matrix multiplication we study the plethysm Sk(sln) of the adjoint representation sln of the Lie group SLn. In particular, we describe the decomposition of this representation into irreducible components for k=3, and find highest-weight vectors for all irreducible components. Relations to fast matrix multiplication, in particular the Coppersmith–Winograd tensor, are presented.

Motivés par la version symétrique de la multiplication des matrices, nous étudions le pléthysme Sk(sln) de la représentation adjointe sln du groupe de Lie SLn. En particulier, pour k=3, nous décrivons la décomposition de cette représentation en composantes irréductibles, et nous trouvons les vecteurs de plus grand poids pour toutes ces dernières. Nous présentons les liens avec la multipliction rapide des matrices, notamment le tenseur de Coppersmith–Winograd.

Published online:
DOI: 10.1016/j.crma.2017.11.012

Tim Seynnaeve 1

1 Max Planck Institute for Mathematics in the Sciences, Inselstrasse 22, 04103, Leipzig, Germany
     author = {Tim Seynnaeve},
     title = {Plethysm and fast matrix multiplication},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {52--55},
     publisher = {Elsevier},
     volume = {356},
     number = {1},
     year = {2018},
     doi = {10.1016/j.crma.2017.11.012},
     language = {en},
AU  - Tim Seynnaeve
TI  - Plethysm and fast matrix multiplication
JO  - Comptes Rendus. Mathématique
PY  - 2018
SP  - 52
EP  - 55
VL  - 356
IS  - 1
PB  - Elsevier
DO  - 10.1016/j.crma.2017.11.012
LA  - en
ID  - CRMATH_2018__356_1_52_0
ER  - 
%0 Journal Article
%A Tim Seynnaeve
%T Plethysm and fast matrix multiplication
%J Comptes Rendus. Mathématique
%D 2018
%P 52-55
%V 356
%N 1
%I Elsevier
%R 10.1016/j.crma.2017.11.012
%G en
%F CRMATH_2018__356_1_52_0
Tim Seynnaeve. Plethysm and fast matrix multiplication. Comptes Rendus. Mathématique, Volume 356 (2018) no. 1, pp. 52-55. doi : 10.1016/j.crma.2017.11.012.

[1] P. Bürgisser; M. Clausen; M.A. 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)

[2] L. Chiantini; J.D. Hauenstein; C. Ikenmeyer; J.M. Landsberg; G. Ottaviani Polynomials and the exponent of matrix multiplication, 2017 (arXiv preprint) | arXiv

[3] H. Cohn; C. Umans A group-theoretic approach to fast matrix multiplication, Foundations of Computer Science, 2003. Proceedings. 44th Annual IEEE Symposium on, IEEE, 2003, pp. 438-449

[4] D. Coppersmith; S. Winograd Matrix multiplication via arithmetic progressions, J. Symb. Comput., Volume 9 (1990) no. 3, pp. 251-280

[5] W. Fulton; J. Harris Representation Theory: A First Course, vol. 129, Springer Science & Business Media, 2013

[6] R. Howe (GLn,GLm)-duality and symmetric plethysm, Proc. Indian Acad. Sci. Math. Sci., Volume 97 (1988) no. 1–3, pp. 85-109 (1987)

[7] T. Kahle; M. Michałek Plethysm and lattice point counting, Found. Comput. Math., Volume 16 (2016) no. 5, pp. 1241-1261

[8] J.M. Landsberg Tensors: Geometry and Applications, Graduate Studies in Mathematics, vol. 128, American Mathematical Society, Providence, RI, 2012

[9] J.M. Landsberg Geometry and Complexity Theory, Cambridge Studies in Advanced Mathematics, Cambridge University Press, 2017

[10] J.M. Landsberg; M. Michałek On the geometry of border rank decompositions for matrix multiplication and other tensors with symmetry, SIAM J. Appl. Algebra Geom., Volume 1 (2017) no. 1, pp. 2-19

[11] J.M. Landsberg; M. Michałek Abelian tensors, J. Math. Pures Appl., Volume 108 (2017) no. 3, pp. 333-371

[12] J.M. Landsberg; M. Michałek A lower bound for the border rank of matrix multiplication, Int. Math. Res. Not. (2017) (rnx025)

[13] J.M. Landsberg; G. Ottaviani New lower bounds for the border rank of matrix multiplication, Theory Comput., Volume 11 (2015), pp. 285-298

[14] F. Le Gall Powers of tensors and fast matrix multiplication, ISSAC 2014—Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation, ACM, New York, 2014, pp. 296-303

[15] I.G. Macdonald Symmetric Functions and Hall Polynomials, Oxford University Press, 1998

[16] L. Manivel; M. Michałek Secants of minuscule and cominuscule minimal orbits, Linear Algebra Appl., Volume 481 (2015), pp. 288-312

[17] S.P.O. Plunkett On the plethysm of S-functions, Can. J. Math., Volume 24 (1972), pp. 541-552

[18] V. Strassen Gaussian elimination is not optimal, Numer. Math., Volume 13 (1969) no. 4, pp. 354-356

[19] R.M. Thrall On symmetrized Kronecker powers and the structure of the free Lie ring, Amer. J. Math., Volume 64 (1942), pp. 371-388

[20] V.V. Williams Multiplying matrices faster than Coppersmith–Winograd [extended abstract], STOC'12—Proceedings of the 2012 ACM Symposium on Theory of Computing, ACM, New York, 2012, pp. 887-898

Cited by Sources:

Comments - Policy