Groupe symétrique

Modèle:Confusion 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. N'est traité dans le présent article, à la suite de la définition générale, que le cas E fini.

Définition

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 ∘). On le note S(E) ou <math>\mathfrak S(E)</math> (ce caractère est un S gothique).

Un cas particulier courant est le cas où E est l'ensemble fini {1, 2, … , n}, n étant un entier naturel ; on note alors <math>\mathfrak S_n</math> ou Modèle:Mvar<ref>R. Goblot, Algèbre linéaire, Paris, 2005, p. 58, utilise la notation S_n. Les auteurs anglo-saxons écrivent en général S_E plutôt que <math>\mathfrak S(E)</math> et S_n plutôt que <math>\mathfrak S_n</math>.</ref> le groupe symétrique de cet ensemble. Les éléments de <math>\mathfrak S_n</math> sont appelés permutations et <math>\mathfrak S_n</math> est appelé groupe des permutations de degré n ou groupe symétrique d'indice n (un sous-groupe du groupe symétrique est appelé un groupe de permutations).

Si deux ensembles sont équipotents alors leurs groupes symétriques sont isomorphes. En effet, si f est une bijection de E dans F, alors l'application de S(E) dans S(F) qui à σ associe f∘σ∘fModèle:-1 est un isomorphisme. En particulier si E est un ensemble fini à n éléments, alors <math>\mathfrak S(E)</math> est isomorphe à <math>\mathfrak S_n</math>. En conséquence, il suffit de connaître les propriétés du groupe <math>\mathfrak S_n</math> pour en déduire celles du groupe <math>\mathfrak S(E)</math>. C'est pourquoi la suite de cet article ne portera que sur <math>\mathfrak S_n</math>.

Exemple

Fichier:Triangle équilatéral et ses médianes.png

Triangle équilatéral et ses médianes <math>d_x, d_y, d_z</math>

Les six isométries du groupe de symétrie d'un triangle équilatéral ABC sont les trois symétries par rapport aux médianes <math>d_x</math>, <math>d_y</math> et <math>d_z</math> issues de respectivement les sommets A, B et C, deux rotations d'un tiers de tour dans le sens horaire ou anti-horaire et l'application identité. Elles se restreignent en six permutations des trois sommets, constituant le groupe S({A, B, C}) :

id, x = (B C), y = (A C), z = (A B), r = (A B C) et rModèle:-1 = (C B A).

La table de Cayley de ce groupe est :

<math>\circ</math>	id	r	rModèle:-1	x	y	z
id	id	r	rModèle:-1	x	y	z
r	r	rModèle:-1	id	z	x	y
rModèle:-1	rModèle:-1	id	r	y	z	x
x	x	y	z	id	r	rModèle:-1
y	y	z	x	rModèle:-1	id	r
z	z	x	y	r	rModèle:-1	id

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 est isomorphe à un sous-groupe d'un groupe symétrique.

Propriétés

Le groupe <math>\mathfrak S_n</math> est d'ordre [[Factorielle|Modèle:Math]]<ref>La preuve standard figure dans « Permutation#Dénombrement des permutations ».</ref>.

Générateurs du 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 <math>\mathfrak S_n</math>.

On peut se limiter aux transpositions de la forme Modèle:Math puisque, pour Modèle:Math, il est possible de décomposer Modèle:Retrait

Ces Modèle:Math générateurs permettent de donner une présentation du groupe symétrique, avec les Modèle:Sfrac relations<ref>Modèle:Ouvrage (6.22).</ref> :

• <math>{\tau_i}^2 = 1,</math>
• <math>\tau_i\tau_j = \tau_j\tau_i \qquad \mbox{si } |j-i| > 1,</math>
• <math>{(\tau_i\tau_{i+1}})^3=1.</math>

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

Il est possible également de prendre Modèle:Math générateurs — les transpositions Modèle:Math pour Modèle:Math — et Modèle:Math relations<ref>Modèle:Harvsp (6.28).</ref> :

<math>s_i^2=(s_is_{i+1})^3=(s_is_{i+1}s_is_j)^2=1\quad(1\le i,j\le n-1,\quad j\ne i,i+1,\quad s_n:=s_1).</math>

Enfin, on peut se contenter de Modèle:Math générateurs — la transposition Modèle:Math et le cycle Modèle:Math — et Modèle:Math relations<ref>Modèle:Harvsp (6.21).</ref> :

<math>r^n=\tau_1^2=(r\tau_1)^{n-1}=(\tau_1r^{-1}\tau_1r)^3=(\tau_1r^{-j}\tau_1r^j)^2=1\quad(2\le j\le n-2).

</math>

Signature

On suppose dans cette section que l'entier n est supérieur ou égal à 2. Modèle:Article détaillé

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 Modèle:Math, notée Modèle:Math ou Modèle:Math, est définie par :

<math>\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.</math>

L'application signature est un morphisme de groupes de <math>(\mathfrak S_n,\circ)</math> 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é <math>\mathfrak A_n</math> (ce caractère est un A gothique). <math>\mathfrak A_n</math> est donc un sous-groupe normal de <math>\mathfrak S_n</math> et le groupe quotient <math>\mathfrak S_n/\mathfrak A_n</math> est isomorphe à l'image {–1, 1} du morphisme signature. Par conséquent, <math>\mathfrak A_n</math> est d'indice 2 dans <math>\mathfrak S_n</math>, donc d'ordre n!/2. (Ou plus concrètement : <math>\mathfrak A_n</math> et son complémentaire dans <math>\mathfrak S_n</math> sont de même cardinal car pour t transposition de <math>\mathfrak S_n</math>, l'application σ ↦ t∘σ est une bijection de <math>\mathfrak A_n</math> dans son complémentaire.)

De plus, la suite exacte courte

<math>1\to\mathfrak A_n\to\mathfrak S_n\to\{-1,1\}\to 1</math>

est scindée à droite, donc <math>\mathfrak S_n</math> est un produit semi-direct de <math>\mathfrak A_n</math> par le groupe cyclique à deux éléments.

Classes de conjugaison

La classe de conjugaison d'une permutation Modèle:Math est l'ensemble de ses conjuguées : <math>C(\sigma)=\{\tau \circ \sigma\circ \tau^{-1}\mid\tau \in\mathfrak S_n\}.</math>

Exemple

Si l'on considère dans <math>\mathfrak S_5</math> 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 [[Partition d'un entier#Dénombrement|nombre de « partages » de l'entier Modèle:Math]], et si la décomposition d'une permutation contient Modèle:Math « 1-cycles » (les points fixes), Modèle:Math 2-cycles, … , Modèle:Math Modèle:Math-cycles, alors le nombre de ses conjuguées vaut<ref>Modèle:Fulton-Harris, Modèle:P., Modèle:Google Livres.</ref> :

<math>\frac{n!}{1^{k_1}k_1!\ldots m^{k_m}k_m!}.</math>

(On voit apparaître un coefficient multinomial.)

Propriétés issues de l'étude du groupe alterné

Le résultat fondamental dans l'étude du groupe alterné <math>\mathfrak A_n</math> est que celui-ci est un groupe simple pour n différent de 4.

D'autre part, le groupe dérivé de <math>\mathfrak S_n</math> est <math>\mathfrak A_n</math><ref>P. Tauvel, Algèbre, 2^e édition, Paris, Dunod, 2010, p. 70. Modèle:Note autre projet</ref>. Pour n ≥ 5, c'est là le seul sous-groupe distingué propre de <math>\mathfrak S_n</math>.

<math>\mathfrak S_n</math> est résoluble si et seulement si n ≤ 4, ce qui a d'importantes conséquences sur la résolubilité par radicaux des équations polynomiales.

Propriétés diverses

• Si n > 4, <math>\mathfrak S_n</math> n'a aucun sous-groupe d'indice strictement compris entre 2 et n<ref>Modèle:Ouvrage.</ref>.
• Tout sous-groupe d'indice n de <math>\mathfrak S_n</math> est isomorphe à <math>\mathfrak S_{n-1}</math><ref>Modèle:Note autre projet</ref>. Si n est différent de 6, un tel sous-groupe est forcément le stabilisateur d'un élément de {1, … , n}.
• En revanche, <math>\mathfrak S_6</math> possède un sous-groupe d'indice 6 transitif donc sans point fixe<ref>Voir par exemple Modèle:Ouvrage, ou Modèle:Note autre projet</ref>.
• <math>\mathfrak S_n</math> est complet pour tout n différent de 2 et de 6. En effet :
  • le centre de <math>\mathfrak S_n</math> est trivial si n ≠ 2 ;
  • <math>\mathfrak S_6</math> est le seul groupe symétrique dont le groupe d'automorphismes extérieurs est non trivial<ref>Voir par exemple Modèle:Harvsp, ou Modèle:Note autre projet</ref> : il est<ref>Modèle:Harvsp.</ref> d'ordre 2.
• <math>\mathfrak S_n</math> se plonge dans <math>\mathfrak A_{n+2}</math>, mais pas dans <math>\mathfrak A_{n+1}</math> si n ≥ 2<ref>Modèle:Rotman1, Modèle:P., exercice 2.8.</ref>.

Notes et références

<references/>

Voir aussi

Articles connexes

• Modèle:Lien
• Fonction de Landau
• Modèle:Lien
• Groupe de tresses
• Matrice de permutation
• Permutation
• Permutation aléatoire
• Représentations du groupe symétrique
• Tableau de Young