Permutations, partitions et représentations du groupe symétrique

Permutations, partitions et représentations du groupe symétrique

Groupe symétrique et classes de conjugaison

Le groupe symétrique d’ordre n est le groupe des permutations de [[1, n]], la loi de groupe étant la composition des applications. Ce groupe fini sera noté Sn, et il contient n! = 1 × 2 × · · · × n éléments. Une permutation peut être donnée par son mot — c’est-à-dire la suite de ses valeurs — ou par sa décomposition en cycles à supports disjoints. Ainsi, la permutation σ ∈ S8 dont le mot est 38254761 admet pour décomposition en cycles σ = (1, 3, 2, 8)(4, 5)(6, 7), et cette décomposition est unique à permutation des cycles près. Le type d’une permutation est la suite ordonnée des tailles des orbites de la permutation ; ainsi, σ = 38254761 a pour type t(σ) = (4, 2, 2). D’autre part, deux permutations σ1 et σ2 de même taille n sont dites conjuguées s’il existe une permutation τ ∈ Sn telle que σ2 = τ ◦ σ1 ◦ τ −1 . Proposition 1.1 (Classes de conjugaison du groupe symétrique). Deux permutations de Sn sont conjuguées si et seulement si elles ont même type. Ainsi, les classes de conjugaison de Sn sont paramétrées par les partitions de taille n, c’est-à-dire les suites décroissantes d’entiers positifs λ = (λ1 > λ2 > · · · > λr) telles que |λ| = ∑ r i=1 λi = n. En effet, si τ est une permutation et si c = (a1, a2, . . . , am) est un cycle, alors le conjugué τcτ −1 est le cycle c τ = (τ(a1), τ(a2), . . . , τ(am)). De plus, tout cycle de longueur m est obtenu de la sorte en choisissant convenablement τ. D’autre part, la conjugaison par τ est un morphisme de groupes Sn → Sn. Par suite, si σ est le produit de cycles disjoints de longueurs respectives l1, . . . , lr , alors les conjugués de σ sont toutes les permutations qui sont des produits de cycles disjoints de longueurs l1, . . . , lr . Et à réindexation des cycles près, on peut supposer l1 > l2 > · · · > lr , donc les classes de conjugaison de Sn sont bien indexées par les partitions de taille n. 5 Permutations, partitions et représentations du groupe symétrique Chapitre 1. Permutations, partitions et représentations du groupe symétrique. 

Partitions et fonctions symétriques

Nous noterons Yn l’ensemble des partitions de l’entier n, et Y = F n∈N Yn l’ensemble de toutes les partitions. La longueur d’une partition est son nombre de parts ℓ(λ); son poids ou sa taille est la somme de ses parts |λ|. Nous aurons également besoin de la quantité b(λ) = ℓ(λ) ∑ i=1 (i − 1) λi , qui intervient dans de nombreuses formules pour les algèbres d’Hecke et les groupes linéaires finis. Par exemple, si λ = (5, 4, 2), alors |λ| = 11, ℓ(λ) = 3 et b(λ) = 8. Une partition sera souvent représentée par son diagramme de Young (on parle aussi de diagramme de Ferrers) : c’est le tableau à r lignes avec λ1 cases sur la première ligne, λ2 cases sur la seconde ligne, etc. Par exemple, le diagramme de la partition (5, 4, 2) est : Figure 1.1 – Diagramme de Young de la partition (5, 4, 2) (dessiné à la française, c’est-à-dire du bas vers le haut). La partition conjuguée de λ est la partition de même taille λ ′ obtenue en échangeant les lignes et les colonnes du diagramme ; par exemple, (5, 4, 2) ′ = (3, 3, 2, 2, 1). D’autre part, le contenu d’une case (x, y) du diagramme est la différence c(x, y) = x − y, et le contenu d’un diagramme est la somme c(λ) des contenus des cases. On voit aisément que c(λ) = b(λ ′ ) − b(λ) pour tout diagramme : c(5, 4, 2) = −2 −1 −1 0 1 2 0 1 2 3 4 = 2 2 − 1 1 1 1 1 1 2 3 1 2 3 4 = b(5, 4, 2) ′ − b(5, 4, 2) Enfin, une partition λ pourra être écrite multiplicativement sous la forme λ = 1 m1 2 m2 · · · s ms , où mk = mk(λ) est le nombre de parts égale à k dans λ. Cette écriture permet de déterminer la taille de la classe de conjugaison associée à λ dans Sn : en effet, le centralisateur d’une permutation de type λ a pour cardinal zλ = ∏ k>1 mk ! k mk , et la classe de conjugaison Cλ a donc pour cardinal cλ = n!/zλ. En dehors du contexte précédemment évoqué, la classe combinatoire des partitions d’entiers intervient classiquement dans la théorie des fonctions symétriques. Rappelons qu’un polynôme en m variables p(x1, . . . , xm) est dit symétrique si p(xσ(1) , xσ(2) , . . . , xσ(m) ) = p(x1, x2, . . . , xm)  σ ∈ Sm. L’ensemble ΛR(m) des polynômes symétriques en m variables et à coefficients dans un anneau commutatif R est un anneau gradué par le degré. De plus, la spécialisation xm+1 = 0 fournit un morphisme d’anneaux gradués surjectif ΛR(m + 1) → ΛR(m), d’où une famille dirigée d’anneaux gradués (ΛR(m))m∈N. On appelle fonction symétrique un élément de la limite projective (dans la catégorie des anneaux gradués) : ΛR = lim←−m→∞ ΛR(m). Un tel objet peut être spécialisé en n’importe quel alphabet fini X = {x1, x2, . . . , xm}, et aussi en des alphabets infinis dénombrables. En faisant agir le groupe symétrique Sm sur les monômes, on voit que les polynômes mλ(x1, . . . , xm) = ∑ i16=i26=···6=ir (xi1 ) λ1 (xi2 ) λ2 · · · (xir ) λr avec λ partition de longueur inférieure à m forment une R-base de ΛR(m). La limite projective ôte la restriction ℓ(λ) 6 m, donc ΛR admet une base (mλ)λ∈Y indexée par les partitions — on dit que les mλ(x) sont les fonctions monomiales. Ce résultat implique en particulier l’identité ΛR = ΛZ ⊗Z R pour tout anneau commutatif R ; la plupart des raisonnements de fonctions symétriques pourront donc être effectués dans Λ = ΛZ.

Tableaux et représentations des groupes symétriques

Si G est un groupe (fini), on rappelle qu’une représentation (linéaire, complexe, de dimension finie) de G est la donnée d’un morphisme de groupes ρ : G → GL(V), où V est un espace vectoriel complexe (de dimension finie). Alternativement, une représentation de G est la donnée d’un CG-module V, où CG désigne l’algèbre du groupe G, c’est-à-dire l’espace des combinaisons linéaires formelles f = ∑ g∈G f(g) g d’éléments du groupe. On peut aussi voir CG comme l’algèbre des fonctions complexes sur le groupe, avec pour multiplication le produit de convolution des fonctions : f1 ∗ f2(g) = ∑ hk=g f1(h) f2(k) = ∑ h∈G f1(h) f2(h −1 g). Toute représentation d’un groupe fini G se scinde de manière unique en somme directe de représentations irréductibles (c’est-à-dire des CG-modules simples), et les classes d’isomorphismes de CG-modules simples forment un ensemble Gb fini. D’autre part, une représentation (ρ, V) d’un groupe fini G est déterminée à isomorphisme près par son caractère ς V : g 7→ tr ρ(g), et les caractères irréductibles forment une base orthonormale de la sousalgèbre (CG) G de CG constituée des fonctions centrales (CG) G =  f | ∀g, h, f(gh) = f(hg) =  f | ∀g, h, f(hgh−1 ) = f(g) , 1. Les sommes de puissances ne forment pas une Z-base de Λ, mais en utilisant les relations de Newton, on peut montrer que h· | ·i et m∗ sont correctement définis sur Z (et pas seulement sur Q). En particulier, la base duale de (hλ)λ∈Y est (mλ)λ∈Y , et m∗ (hn) = ∑p+q=n hp ⊗ hq. 8 1.3. Tableaux et représentations des groupes symétriques. le produit scalaire sur CG étant défini par hf1 | f2i = 1 card G ∑ g∈G f1(g) f2(g). Notons qu’alternativement, on peut voir (CG) G comme le centre de l’algèbre CG. Tous ces points sont exposés en détail dans [JL93] ou [Ser77]. Nous aurons essentiellement besoin de l’orthonormalité de la base des caractères irréductibles, qui implique en particulier le point suivant : le nombre de caractères irréductibles d’un groupe fini G est toujours égal au nombre de classes de conjugaison de G. Un autre fait qui mérite d’être précisé ici est la décomposition de la représentation régulière (gauche) en somme de modules irréductibles. Ainsi, pour tout groupe fini G, chaque CG-module irréductible V intervient dim V fois dans CG : CG ≃CG M (ρ,V)∈Gb (dim V) V . Ce résultat peut être vu comme une conséquence du théorème de Wedderburn : en tant qu’algèbre semi-simple sur un corps algébriquement clos, CG est une somme directe d’algèbres de matrices, et la décomposition en blocs de CG est CG ≃ M (ρ,V)∈Gb End(V). Un isomorphisme est donné par la transformée de Fourier abstraite, qui à f = ∑g∈G f(g) g associe fb= M (ρ,V)∈Gb  ∑ g∈G f(g) ρ(g)  . Cette transformée est même une isométrie d’espaces L2 non commutatifs, voir la section 3.2. Ceci motivera l’introduction de la mesure de Plancherel d’un groupe fini, qui est la duale de la mesure de Haar. Détaillons maintenant cette théorie générale dans le cas particulier où G est le groupe symétrique d’ordre n. D’après ce qui précède, les représentations irréductibles de Sn sont en même nombre que les classes de conjugaison de Sn, et il existe donc une indexation de ces représentations par les partitions λ ∈ Yn. Une description explicite des modules simples V λ est due à A. Young, et elle repose sur la combinatoire des tableaux. Si λ est une partition de taille n, on appelle tableau standard de forme λ une numérotation des cases du diagramme λ par les entiers de [[1, n]], les entrées étant strictement croissantes selon les lignes et selon les colonnes