Groupe symétrique

Une transposition est un 2-cycle, c'est-à-dire une permutation qui échange deux éléments et laisse les autres inchangés. On note (i, j) la transposition qui échange l'élément i avec l'élément j.

Il existe un algorithme permettant de décomposer une permutation en produit de transpositions. Ainsi l'ensemble des transpositions forme un système de générateurs de ${\displaystyle {\mathfrak {S}}_{n}}$.

On peut se limiter aux transpositions de la forme τ_i = (i, i + 1) puisque, pour i < j, il est possible de décomposer ${\displaystyle (i,j)=(i,i+1)(i+1,i+2)\dots (j-2,j-1)(j-1,j)(j-2,j-1)\dots (i+1,i+2)(i,i+1).}$

Ces n – 1 générateurs permettent de donner une présentation du groupe symétrique, avec les n(n + 1)/2 relations[3] :

• ${\displaystyle {\tau _{i}}^{2}=1,}$
• ${\displaystyle \tau _{i}\tau _{j}=\tau _{j}\tau _{i}\qquad {\mbox{si }}|j-i|>1,}$
• ${\displaystyle {(\tau _{i}\tau _{i+1}})^{3}=1.}$

Il s'agit donc d'un cas particulier de groupe de Coxeter et même d'un groupe de réflexions (en) (ce qui, pour un groupe fini, est en fait équivalent).

Il est possible également de prendre n – 1 générateurs — les transpositions s_i = (i, n) pour i < n — et (n – 1)² relations[4] :

${\displaystyle s_{i}^{2}=(s_{i}s_{i+1})^{3}=(s_{i}s_{i+1}s_{i}s_{j})^{2}=1\quad (1\leq i,j\leq n-1,\quad j\neq i,i+1,\quad s_{n}:=s_{1}).}$

Enfin, on peut se contenter de 2 générateurs — la transposition τ₁ = (1, 2) et le cycle r = (1, 2, … , n) — et n + 1 relations[5] :

${\displaystyle r^{n}=\tau _{1}^{2}=(r\tau _{1})^{n-1}=(\tau _{1}r^{-1}\tau _{1}r)^{3}=(\tau _{1}r^{-j}\tau _{1}r^{j})^{2}=1\quad (2\leq j\leq n-2).}$

On suppose dans cette section que l'entier n est supérieur ou égal à 2.

Toute permutation se décompose en un produit de transpositions. Ce produit n'est pas unique, mais la parité du nombre de termes d'un tel produit ne dépend que de la permutation. On parle alors de permutation paire ou impaire.

La signature d'une permutation σ, notée sgn(σ) ou ε(σ), est définie par :

${\displaystyle \operatorname {sgn} (\sigma )=\varepsilon (\sigma )=\left\{{\begin{array}{cl}+1&{\mbox{si }}\sigma {\mbox{ est paire }}\\-1&{\mbox{si }}\sigma {\mbox{ est impaire }}\end{array}}\right.}$

L'application signature est un morphisme de groupes de ${\displaystyle ({\mathfrak {S}}_{n},\circ )}$ dans ({–1, 1}, ×). Le noyau de ce morphisme, c’est-à-dire l'ensemble des permutations paires, est appelé le groupe alterné de degré n, noté ${\displaystyle {\mathfrak {A}}_{n}}$ (ce caractère est un A gothique). ${\displaystyle {\mathfrak {A}}_{n}}$ est donc un sous-groupe normal de ${\displaystyle {\mathfrak {S}}_{n}}$ et le groupe quotient ${\displaystyle {\mathfrak {S}}_{n}/{\mathfrak {A}}_{n}}$ est isomorphe à l'image {–1, 1} du morphisme signature. Par conséquent, ${\displaystyle {\mathfrak {A}}_{n}}$ est d'indice 2 dans ${\displaystyle {\mathfrak {S}}_{n}}$, donc d'ordre n!/2. (Ou plus concrètement : ${\displaystyle {\mathfrak {A}}_{n}}$ et son complémentaire dans ${\displaystyle {\mathfrak {S}}_{n}}$ sont de même cardinal car pour t transposition de ${\displaystyle {\mathfrak {S}}_{n}}$, l'application σ ↦ t∘σ est une bijection de ${\displaystyle {\mathfrak {A}}_{n}}$ dans son complémentaire.)

De plus, la suite exacte courte

${\displaystyle 1\to {\mathfrak {A}}_{n}\to {\mathfrak {S}}_{n}\to \{-1,1\}\to 1}$

est scindée à droite, donc ${\displaystyle {\mathfrak {S}}_{n}}$ est un produit semi-direct de ${\displaystyle {\mathfrak {A}}_{n}}$ par le groupe cyclique à deux éléments.

La classe de conjugaison d'une permutation σ est l'ensemble de ses conjuguées : ${\displaystyle C(\sigma )=\{\tau \circ \sigma \circ \tau ^{-1}\mid \tau \in {\mathfrak {S}}_{n}\}.}$

Les conjuguées de σ sont les permutations dont la décomposition en produit de cycles à supports disjoints a la même structure que celle de σ : même nombre de cycles de chaque longueur[6].

Exemple

Si l'on considère dans ${\displaystyle {\mathfrak {S}}_{5}}$ les différentes classes de conjugaison, on trouve celle de l'identité, des transpositions (ab), les permutations composées de deux transpositions de supports disjoints (ab)(cd), les cycles d'ordre 3 (abc), les permutations composées d'un cycle d'ordre 3 et d'un d'ordre 2 : (abc)(de), puis les cycles d'ordres 4 : (abcd) et 5 : (abcde).

Les permutations (1 2 3)(4 5) et (1 3 4)(2 5) sont dans la même classe de conjugaison contrairement à la permutation (1 3)(2 5).

Le nombre de classes de conjugaison est donc égal au nombre de « partages » de l'entier n, et si la décomposition d'une permutation contient k₁ « 1-cycles » (les points fixes), k₂ 2-cycles, … , k_m m-cycles, alors le nombre de ses conjuguées vaut[7] :

${\displaystyle {\frac {n!}{1^{k_{1}}k_{1}!\ldots m^{k_{m}}k_{m}!}}.}$

(On voit apparaître un coefficient multinomial.)

• Automorphismes des groupes symétriques et alternés (en)
• Fonction de Landau
• Groupe symétrique généralisé (en)
• Groupe de tresses
• Matrice de permutation
• Permutation
• Permutation aléatoire
• Représentations du groupe symétrique
• Tableau de Young

Daniel Perrin, Cours d'algèbre [détail des éditions]