permutation group

Imaginez quatre cartes numérotées 1, 2, 3 et 4. Une permutation réattribue chaque position à une carte, sans doublon ni oubli. On peut ensuite effectuer un second réarrangement : la composition décrit l’effet des deux gestes successifs.

Toutes les réorganisations possibles forment un groupe. Il contient le geste qui ne change rien, et chaque réorganisation peut être annulée par le réarrangement inverse. Avec quatre cartes, il existe 24 permutations.

Soit E un ensemble. Une permutation de E est une bijection de E sur lui-même : chaque élément a une image unique et chaque élément est atteint. L’ensemble de ces bijections, noté S(E), est stable par composition. La composition est associative, l’application identité est l’élément neutre et la bijection réciproque de chaque permutation est son inverse. Ces propriétés font de S(E) un groupe, appelé groupe de permutations ou groupe symétrique de E.

Si E contient n éléments, ce groupe se note S_n. Son ordre, c’est-à-dire son nombre d’éléments, vaut n!. Pour E formé des nombres 1, 2, 3 et 4, S₄ contient donc 4! = 24 permutations. Dès que n ≥ 3, l’ordre des compositions peut changer le résultat : S_n n’est pas commutatif.

Toute permutation d’un ensemble fini se décompose en cycles. Sa signature vaut +1 si elle est paire et −1 si elle est impaire ; la signature respecte la composition et définit donc un homomorphisme de S_n vers {−1, +1}. Son noyau est le groupe alterné A_n, formé des permutations paires. Enfin, le théorème de Cayley affirme que tout groupe fini est isomorphe à un sous-groupe d’un groupe symétrique.

La structure comporte cinq éléments essentiels. L’ensemble E fournit les objets à réarranger. Les permutations sont toutes les bijections de E vers E. La composition combine deux permutations en appliquant celle de droite, puis celle de gauche. L’identité laisse chaque élément fixe. Enfin, l’inverse d’une permutation ramène chaque image à son élément de départ.

Le choix de E détermine les permutations disponibles ; la composition détermine leur organisation en groupe. L’identité et les inverses dépendent donc de cette même opération. Sur un ensemble fini, la notation en cycles décrit les déplacements sans changer la permutation elle-même. Ces données suffisent à composer des permutations, retrouver leurs inverses et compter n! éléments dans S_n.

Prenons E = {1, 2, 3, 4}. La permutation σ envoie 1 sur 2, 2 sur 3, 3 sur 1 et fixe 4 ; elle s’écrit par le cycle (1 2 3). La permutation τ échange 3 et 4 et fixe 1 et 2 ; elle s’écrit (3 4).

Étape 1. Pour calculer τ ∘ σ, appliquez d’abord σ, puis τ. L’élément 1 devient 2, et 2 reste 2 sous τ : l’image finale de 1 est 2.

Étape 2. Le même calcul donne 2 ↦ 4, 3 ↦ 1 et 4 ↦ 3. Ainsi, $\tau \circ \sigma =(1243)\backslash tau\backslash circ\backslash sigma=(1\backslash \; 2\backslash \; 4\backslash \; 3)$.

Étape 3. Inversez maintenant l’ordre. Pour σ ∘ τ, appliquez d’abord τ, puis σ. On obtient 1 ↦ 2, 2 ↦ 3, 3 ↦ 4 et 4 ↦ 1, donc $\sigma \circ \tau =(1234)\backslash sigma\backslash circ\backslash tau=(1\backslash \; 2\backslash \; 3\backslash \; 4)$.

Étape 4. Les deux cycles diffèrent, donc $\tau \circ \sigma \mathrm{\ne }\sigma \circ \tau \backslash tau\backslash circ\backslash sigma\backslash neq\backslash sigma\backslash circ\backslash tau$. Ce calcul vérifie concrètement que S₄ n’est pas commutatif.

Le contrôle consiste à suivre séparément les quatre éléments. Dans chaque ordre, les images finales sont toutes différentes et couvrent encore E : chaque résultat est bien une permutation.

Pour décrire un réarrangement fini, la liste des images convient quand on veut vérifier chaque élément. La notation en cycles est préférable lorsque l’on veut voir immédiatement les éléments déplacés et ceux qui reviennent en boucle.

Pour enchaîner deux réarrangements, on utilise la composition. Le critère décisif est l’ordre d’exécution : dans τ ∘ σ, σ agit avant τ. Si l’ordre importe, les deux compositions doivent être calculées séparément.

Pour annuler un réarrangement, on emploie sa permutation inverse plutôt que de recommencer au hasard. Elle renvoie chaque image vers son élément de départ.

Pour étudier un groupe fini abstrait, le théorème de Cayley permet de le représenter comme un sous-groupe d’un groupe symétrique. Les éléments du groupe deviennent alors des permutations, et sa loi devient une composition.

Une permutation et le groupe de permutations. Une permutation est une seule bijection de E sur E ; S(E) est l’ensemble de toutes ces bijections muni de la composition. Sur quatre éléments, (1 2 3) est un élément parmi les 24 éléments de S₄.

Groupe symétrique et groupe alterné. S_n contient toutes les permutations de n éléments, tandis que A_n ne contient que les permutations paires. Le test est la signature : +1 place la permutation dans A_n, −1 l’en exclut.

Petites valeurs de n. S₀ et S₁ ne contiennent chacun que l’identité ; S₂ contient deux permutations. Ces groupes sont commutatifs. La non-commutativité annoncée commence exactement à n = 3.

Ordre de lecture. Lire τ ∘ σ de gauche à droite produit généralement le mauvais résultat. Avec la composition usuelle des applications, il faut appliquer σ d’abord, puis τ, et suivre chaque élément jusqu’à son image finale.

Points fixes omis. L’écriture cyclique n’affiche souvent pas les éléments inchangés. Dans E = {1, 2, 3, 4}, le cycle (1 2 3) fixe pourtant 4 ; il faut connaître l’ensemble E pour reconstituer toute la bijection.

Signature et appartenance à A_n. La signature n’est pas une nouvelle permutation : elle vaut seulement +1 ou −1. Une valeur +1 place la permutation dans le noyau A_n ; une valeur −1 l’en exclut.

bijection — Revoir la condition qui garantit qu’un réarrangement n’oublie et ne répète aucun élément.

Permutation paire — Approfondir la parité qui définit le sous-groupe alterné A_n.

théorème de Cayley — Voir comment un groupe se représente par des permutations.