Groupe symétrique

Cette notion est différente de celle de groupe de symétrie.

En mathématiques, plus particulièrement en algèbre, le groupe symétrique d'un ensemble E est le groupe des permutations de E, c'est-à-dire des bijections de E sur lui-même.

Soit E un ensemble. On appelle groupe symétrique de E l'ensemble des applications bijectives de E sur E muni de la composition d'applications (la loi $\circ$). On le note $\mathfrak{S}(E)$ (ce caractère est un S gothique).

Un cas particulier courant est le cas où E est l'ensemble fini $\{1,2,\dots ,n\}$, n étant un entier naturel strictement positif ; on note alors ${\mathfrak{S}}_n$ ou $S_n$ le groupe symétrique de cet ensemble. Les éléments de ${\mathfrak{S}}_n$ sont appelés permutations et ${\mathfrak{S}}_n$ est appelé groupe des permutations de degré n ou groupe symétrique d'indice n.

Maintenant, si $E$ est un ensemble à n éléments, alors on sait que ${\mathfrak{S}}_n$ est isomorphe à $\mathfrak{S}(E)$. En conséquence, il suffit de connaître les propriétés du groupe ${\mathfrak{S}}_n$ pour en déduire celles du groupe $\mathfrak{S}(E)$. C'est pourquoi la suite de cet article ne portera que sur ${\mathfrak{S}}_n$.

Origine et importance

Historiquement, l'étude du groupe des permutations des racines d'un polynôme par Évariste Galois est à l'origine du concept de groupe.

Un théorème de Cayley assure que tout groupe peut être considéré comme sous-groupe d'un groupe symétrique.

Le groupe ${\mathfrak{S}}_n$ est d'ordre n!.

Cette propriété peut être prouvée en dénombrant les permutations. Il est également possible de faire une démonstration par récurrence, en donnant ainsi un lien entre les groupes symétriques d'ordre n-1 et n.

Démonstration par récurrence sur n.

${\mathfrak{S}}_1$ possède un seul élément.

Supposons que possède (n − 1)! éléments. Considérons l'application

où σ' est la restriction à $\{1,\dots ,n-1\}$ de la permutation (n,σ(n))σ. σ' appartient bien à car σ'(n) = n donc σ'(i) < n pour tout $1\le i<n$.

On montre la bijectivité de $\phi$ en exhibant l'application réciproque. On en déduit que le cardinal de ${\mathfrak{S}}_n$ est égal à celui de $\{1,\dots ,n\}\times {\mathfrak{S}}_{n-1}$ c'est-à-dire n.(n − 1)! = n!.

Le groupe symétrique est isomorphe au groupe formé par les matrices de permutation muni de la loi produit : ce sont les matrices ayant un unique coefficient 1 dans chaque ligne et chaque colonne, tous les autres étant nuls.

Générateurs du groupe symétrique

Une transposition est une permutation qui échange deux éléments et laisse les autres inchangés. On note par (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 ${\mathfrak{S}}_n$

Il est possible de se limiter aux transpositions de la forme τ_i = (i,i + 1) puisque, pour i<j, il est possible de décomposer

Ces générateurs permettent de donner une présentation du groupe symétrique, avec les relations

• ${{\tau }_i}^2=1$,
• ${\tau }_i{\tau }_j={\tau }_j{\tau }_i\text{si }|j-i|>1$,
• $({\tau }_i{\tau }_{i+1}{)}^3=1.$

Il s'agit donc d'un cas particulier de groupe de Coxeter.

Il est possible également de prendre pour système de générateurs les transpositions de la forme (1,i) pour i>1. Enfin on peut se contenter de deux générateurs : la transposition σ=(1,2) et le cycle c=(1,2,...,n).

Signature

Toute permutation se décompose en un produit de transpositions. Ce produit n'est pas unique, mais le nombre de transpositions nécessaire pour représenter une permutation est toujours soit pair, soit impair. On parle alors de permutation paire ou impaire.

La signature d'une permutation σ est l'application notée sg**n ou $\epsilon$ et définie par :

Avec cette définition, la signature est un homomorphisme de groupes $({\mathfrak{S}}_n,\circ )$ dans $\left(\{-1,1\},\times \right)$. Le noyau de cet homomorphisme, c’est-à-dire l'ensemble des permutations paires, est appelé le groupe alterné d'ordre n, noté ${\mathfrak{A}}_n$ (ce caractère est un A). ${\mathfrak{A}}_n$ est un sous-groupe distingué de ${\mathfrak{S}}_n$ et possède $\frac{n!}{2}$ éléments. En effet, ${\mathfrak{A}}_n$ et son complémentaire dans ${\mathfrak{S}}_n$ sont de même cardinal (pour t transposition de ${\mathfrak{S}}_n$, $f:\sigma ⟼t\circ \sigma$ est une bijection de ${\mathfrak{A}}_n$ dans son complémentaire)

Classes de conjugaison

Si σ est une permutation, sa classe de conjugaison est l'ensemble des conjuguées de σ

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.

Ainsi, si on considère dans ${\mathfrak{S}}_5$ les différentes classes de conjugaison, on trouve celle de l'identité, des transpositions (ab), les permutations composées de 2 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 et la permutation (1,3)(2,5) non.

Le résultat fondamental dans l'étude du groupe alterné ${\mathfrak{A}}_n$ est que celui-ci est un groupe simple pour $n\ne 4$.

Il en résulte notamment que le groupe dérivé de ${\mathfrak{S}}_n$ est ${\mathfrak{A}}_n$ pour $n\ne 4$. Pour $n\ge 5$, c'est là le seul sous-groupe distingué propre de ${\mathfrak{S}}_n$.

• Si $n\ne 6$, tout automorphisme de S_n est intérieur. Par ailleurs, il existe un automorphisme extérieur de S₆.

• Tout sous-groupe d'indice n de S_n est isomorphe à S_{n − 1}. Si $n\ne 6$, un tel sous-groupe est forcément le stabilisteur d'un élément de $\{1,\dots ,n\}$. Par ailleurs, S₆ possède un sous-groupe d'indice 6 qui n'est pas le stabilisateur d'un point.