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.

Received:
Accepted:
Published online:
DOI: 10.1016/j.crma.2017.11.012
Seynnaeve, Tim 1

1 Max Planck Institute for Mathematics in the Sciences, Inselstrasse 22, 04103, Leipzig, Germany
@article{CRMATH_2018__356_1_52_0,
     author = {Seynnaeve, Tim},
     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},
     url = {http://www.numdam.org/articles/10.1016/j.crma.2017.11.012/}
}
TY  - JOUR
AU  - Seynnaeve, Tim
TI  - Plethysm and fast matrix multiplication
JO  - Comptes Rendus. Mathématique
PY  - 2018
SP  - 52
EP  - 55
VL  - 356
IS  - 1
PB  - Elsevier
UR  - http://www.numdam.org/articles/10.1016/j.crma.2017.11.012/
DO  - 10.1016/j.crma.2017.11.012
LA  - en
ID  - CRMATH_2018__356_1_52_0
ER  - 
%0 Journal Article
%A Seynnaeve, Tim
%T Plethysm and fast matrix multiplication
%J Comptes Rendus. Mathématique
%D 2018
%P 52-55
%V 356
%N 1
%I Elsevier
%U http://www.numdam.org/articles/10.1016/j.crma.2017.11.012/
%R 10.1016/j.crma.2017.11.012
%G en
%F CRMATH_2018__356_1_52_0
Seynnaeve, Tim. 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. http://www.numdam.org/articles/10.1016/j.crma.2017.11.012/

[1] Bürgisser, P.; Clausen, M.; Shokrollahi, M.A. 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] Chiantini, L.; Hauenstein, J.D.; Ikenmeyer, C.; Landsberg, J.M.; Ottaviani, G. Polynomials and the exponent of matrix multiplication, 2017 (arXiv preprint) | arXiv

[3] Cohn, H.; Umans, C. 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] Coppersmith, D.; Winograd, S. Matrix multiplication via arithmetic progressions, J. Symb. Comput., Volume 9 (1990) no. 3, pp. 251-280

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

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

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

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

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

[10] Landsberg, J.M.; Michałek, M. 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] Landsberg, J.M.; Michałek, M. Abelian tensors, J. Math. Pures Appl., Volume 108 (2017) no. 3, pp. 333-371

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

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

[14] Le Gall, F. 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] Macdonald, I.G. Symmetric Functions and Hall Polynomials, Oxford University Press, 1998

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

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

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

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

[20] Williams, V.V. 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: