Groupe de permutation

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.

Sommaire

1 Définition
- 1.1 Origine et importance
2 Propriétés
3 Propriétés issues de l'étude du groupe alterné
4 Propriétés diverses
5 Voir aussi
- 5.1 Articles connexes
- 5.2 Bibliographie
6 Notes et références

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 $\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, \ldots, n\}$ , $n$ étant un entier naturel strictement positif ; on note alors $\mathfrak{S}_n$ ou $\ S_{n}$ ^[1] 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.

Propriétés

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 $\mathfrak{S}_{n-1}$ possède

(n - 1)!

éléments. Considérons l'application

$\varphi : \left\lbrace \begin{array}{ccc} \mathfrak{S}_n &\to &\{1,\ldots,n\}\times \mathfrak{S}_{n-1} \\ \sigma & \mapsto & (\sigma(n), \sigma') \end{array} \right.$

où

σ'

est la restriction à $\{1,\ldots,n-1\}$ de la permutation

(n,σ(n))σ

σ'

appartient bien à $\mathfrak{S}_{n-1}$ car

σ'(n) = n

donc

σ'(i) < n

pour tout $1\leq i < n$ .

On montre la bijectivité de $\varphi$ en exhibant l'application réciproque. On en déduit que le cardinal de $\mathfrak{S}_n$ est égal à celui de $\{1,\ldots,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

$(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 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 \qquad \mbox{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

Article détaillé : Signature d'une permutation.

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 $s g n$ ou $\varepsilon$ et définie par :

$\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.$

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 ${n!\over 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\longmapsto 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 $σ$

$C(\sigma)=\{\tau \circ \sigma\circ \tau^{-1}, \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.

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.

Démonstration

Soient σ et φ deux permutations de ${\mathfrak S}_n$ . L'objectif dans un premier temps est de montrer que σ^-1φσ est une permutation de même nombre de cycles de chaque longueur.

Un résultat précédent montre qu'il est possible de décomposer σ en une suite de transpositions : σ = σ₁σ₂...σ_m. L'objectif revient à montrer que σ_m^-1σ_m-1^-1...σ₁^-1φσ₁σ₂...σ_m a même structure que φ. Ceci revient à montrer que si σ est une transposition, alors σ^-1φσ possède la même structure que φ. Soient a₁ et b₁ les deux éléments du support de σ, c'est à dire que σ(a₁) = b₁ et σ(b₁) = a₁. On peut diviser l'étude en quatre cas différents.

Si ni a₁, ni b₁ ne sont élément du support de φ, φ et σ commutent et σ^-1φσ = φ, ce qui montre le résultat.

Si a₁ est élément du support de φ, mais que b₁ ne l'est pas. Soit (a₁a₂...a_k) le cycle de φ contenant a₁. Les cycles de σ^-1φσ sont exactement les mêmes que ceux de φ, à l'exception de celui contenant a₂, qui devient (b₁a₂a₃...a_k) et qui est un cycle de même longueur. Si b₁ n'est plus invariant par σ^-1φσ, a₁ l'est devenu. Les deux permutations σ^-1φσ et φ ont bien même structure.

Si a₂ et b₂ appartiennent au même cycle, avec les notations précédentes, il existe un entier h, plus petit que k tel que b₂ soit égal à a_h avec h différent de 2. Les différents cycles à supports disjoints composant φ sont les mêmes que ceux de σ^-1φσ à l'exception de celui contenant a₂, qui devient (a₁a_ha₃...a_h-1a₂a_h+1a_h+2...a_k). Une fois encore les structures des cycles sont les mêmes.

Si a₁ et b₁ sont tout deux éléments du support de φ et appartiennent à des cycles différents, on note (b₁b₂...b_l) le cycle de b₁. Tous les cycles de φ restent inchangés, sauf ceux contenant a₁ et b₁, qui deviennent : (a₁b₂...b_l) et (b₁a₂...a_k). Les deux permutations ont encore la même structure.

Soient φ₁ et φ₂ deux permutations ayant même structure. Il s'agit, pour clore la démonstration, de montrer l'existence d'une permutation σ tel que σ^-1φ₁σ = φ₂.

Dans un premier temps, on construit une permutation σ₁σ₂...σ_k tel que σ_k^-1σ_k-1^-1...σ₁^-1φ₁σ₁σ₂...σ_k ait même support que φ₂. Soit b₁, b₂ ... b_j les entiers compris entre 1 et n qui ne sont pas dans le support de φ₂. Si b_i, où i est un entier entre 1 et j, n'est pas dans le support de φ₁ on définit σ_i comme la permutation identité et c_i comme étant égal à b_i. Dans le cas contraire, il existe nécessairement un élément c_i élément de l'ensemble {b₁, b₂ ... b_j} qui est dans le support de φ₁ car φ₁ et φ₂ ont même structure et par conséquent même nombre d'éléments invariants. On peut, de plus choisir c_i différent de c_p pour p variant de 1 à i. Soit σ_i la transposition de support b_i et c_i, la permutation σ_i^-1φ₁σ_i laisse b_i invariant. Par récurrence, on vérifie bien que σ_k^-1σ_k-1^-1...σ₁^-1φ₁σ₁σ₂...σ_k possède le même support que φ₂.

Dans un deuxième temps, on construit une permutation σ₁σ₂...σ_l, où l est un entier plus grand que k, tel que σ_l^-1σ_l-1^-1...σ₁^-1φ₁σ₁σ₂...σ_l ait même support et même élément dans chaque cycle que φ₂. Les différentes permutations σ_p sont définies jusqu'à l'indice k, il faut maintenant les définir jusqu'à l'indice l. Soit (a₁a₂...a_p) un cycle de σ_k^-1σ_k-1^-1...σ₁^-1φ₁σ₁σ₂...σ_k et (b₁b₂...b_p) un autre cycle de même longueur de φ₂. Si a₁ est élément de {b₁, b₂, ..., b_p) on définit σ_m+1 comme la permutation identité, sinon c'est la transposition de support a₁ et b₁. Le premier élément du cycle de longueur p et contenant b₂ est maintenant commun à σ_k+1^-1σ_k^-1...σ₁^-1φ₁σ₁σ₂...σ_k+1. De proche en proche on construit ainsi la permutation ayant même support et même élément dans chaque cycle.

Dans un troisième temps, on construit une permutation σ₁σ₂...σ_m, où m est un entier plus grand que l, tel que σ_m^-1σ_m-1^-1...σ₁^-1φ₁σ₁σ₂...σ_m soit égal à φ₂. Il devient nécessaire d'ordonner les éléments dans les différents cycles. Soit (a₁a₂...a_p) un cycle de σ_l^-1σ_l-1^-1...σ₁^-1φ₁σ₁σ₂...σ_l et (a₁a_ψ(2)...a_ψ(p)) la permutation de même support dans φ₂. Ici ψ désigne une permutation de {2, ..., p}. Si a_ψ(2) est égal à a₂ alors σ_l+1 est la permutation identité. Sinon, σ_l+1 est la transposition de support a₂ et a_ψ(2). L'image de a₁ par la permutation σ_k+1^-1σ_k^-1...σ₁^-1φ₁σ₁σ₂...σ_k+1 est bien celle de φ₂. De proche en proche on construit la permutation recherchée.

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

Article détaillé : Groupe alterné.

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

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

Propriétés diverses

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

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

Voir aussi

Bibliographie

Daniel Perrin, Cours d'algèbre, Éditions de l'École Normale Supérieure de Jeunes Filles, 1981 (ISBN 2-85929-011-7)

Notes et références

↑ 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_{X}$ au lieu de $\mathfrak{S}(E)$ et $\ S_{n}$ au lieu de $\mathfrak{S}_n$ .

Portail des mathématiques

Ce document provient de « Groupe sym%C3%A9trique ».

Catégories : Groupe remarquable | Permutation

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Groupe de permutation de Wikipédia en français (auteurs)

Игры ⚽ Поможем написать курсовую

Regardez d'autres dictionnaires:

Groupe Alterné — En mathématiques, et plus précisément en théorie des groupes, le groupe alterné de degré n, souvent noté An, est un sous groupe distingué du groupe symétrique des permutations d un ensemble fini de cardinal n. Ce sous groupe est composé des… … Wikipédia en Français
Groupe alterne — Groupe alterné En mathématiques, et plus précisément en théorie des groupes, le groupe alterné de degré n, souvent noté An, est un sous groupe distingué du groupe symétrique des permutations d un ensemble fini de cardinal n. Ce sous groupe est… … Wikipédia en Français
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. Sommaire 1… … Wikipédia en Français
Groupe des permutations — 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… … Wikipédia en Français
Groupe symetrique — 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… … Wikipédia en Français
Groupe De Frobenius — En mathématiques, un groupe de Frobenius est un groupe de permutation transitif sur un ensemble fini, tel qu aucun élément non trivial ne fixe plus d un point et tel qu un certain élément fixe un point. Ils ont été nommés en l honneur de F. G.… … Wikipédia en Français
Groupe de frobenius — En mathématiques, un groupe de Frobenius est un groupe de permutation transitif sur un ensemble fini, tel qu aucun élément non trivial ne fixe plus d un point et tel qu un certain élément fixe un point. Ils ont été nommés en l honneur de F. G.… … Wikipédia en Français
Groupe De Mathieu — En mathématiques, les groupes de Mathieu sont cinq groupes simples finis découverts par le mathématicien français Emile Léonard Mathieu. Ils sont habituellement perçus comme des groupes de permutation sur n points (où n peut prendre les valeurs… … Wikipédia en Français
Groupe de mathieu — En mathématiques, les groupes de Mathieu sont cinq groupes simples finis découverts par le mathématicien français Emile Léonard Mathieu. Ils sont habituellement perçus comme des groupes de permutation sur n points (où n peut prendre les valeurs… … Wikipédia en Français
Groupe Sporadique — En mathématiques, un groupe sporadique est l un des 26 groupes exceptionnels dans la classification des groupes simples finis. Un groupe simple est un groupe G qui ne possède aucun sous groupe normal à part le sous groupe trivial réduit à l… … Wikipédia en Français

Dictionnaires et Encyclopédies sur 'Academic'

Groupe de permutation

Groupe symétrique

Sommaire