Théorie des groupes/Groupes symétriques finis

Début de la boite de navigation du chapitre
Groupes symétriques finis
Icône de la faculté
Chapitre no 13
Leçon : Théorie des groupes
Chap. préc. :Sous-groupes caractéristiques
Chap. suiv. :Groupes alternés

Annexe :

Représentations du groupe symétrique d'indice trois
Exercices :Groupes symétriques finis
fin de la boite de navigation du chapitre
En raison de limitations techniques, la typographie souhaitable du titre, « Théorie des groupes : Groupes symétriques finis
Théorie des groupes/Groupes symétriques finis
 », n'a pu être restituée correctement ci-dessus.

Groupe symétrique comme groupe opérant

modifier

Rappelons la définition, donnée au chapitre 2 :


Nous noterons souvent le groupe symétrique multiplicativement, par juxtaposition. Ainsi, nous écrirons   au lieu de   pour désigner la composée de deux permutations. De même, n étant un nombre naturel, nous désignerons par   la composée de n permutations égales à   et par   la permutation réciproque de  . Nous dirons aussi « produit de permutations » plutôt que « composée de permutations » etc.

Si E et F sont deux ensembles équipotents, les groupes   et   sont isomorphes. En effet, soit f une bijection f de E sur F; à toute permutation   de E, faisons correspondre la permutation   de F; on vérifie facilement que nous définissons ainsi un isomorphisme de   sur  .

Dans le cas particulier où E est l’ensemble   pour un certain nombre naturel n, on écrit   plutôt que  . D'après la remarque précédente, le groupe symétrique de tout ensemble fini à n éléments est isomorphe à  .

L'application   est une action du groupe   sur l’ensemble E, dite action naturelle de   sur E. Nous avons vu qu’à toute action d'un groupe G sur un ensemble X correspond un homomorphisme de G dans  . Dans le cas présent, cet homomorphisme est l'identité (homomorphisme identique de   sur lui-même).

Plus généralement, si H est un sous-groupe de  , nous dirons que l'action de H sur E induite par celle de   est l'action naturelle de H sur E.

Support d'une permutation

modifier


De façon générale, si G est un groupe opérant sur un ensemble X, nous avons vu que les points fixes d'un élément g de G sont identiques aux points fixes de g⁻¹, que le stabilisateur d'un élément x de X est un sous-groupe de G et qu'un élément x de X est point fixe d'un élément g de G si et seulement s'il est point fixe pour l'opération du sous-groupe <g> de G sur X. Donc

1° Soient   des permutations d'un même ensemble E; alors

 

(en effet, un élément de E qui n'appartient pas au second membre est point fixe de chacune des permutations   et est donc point fixe de leur composée); en particulier, si   est une permutation de E, si k est un nombre naturel  , le support de   est contenu dans celui de  .

2° Le support de   est égal à celui de  .

3° Les points fixes de   sont les points fixes pour l'opération de   sur E, donc le support de   est la réunion des orbites non ponctuelles de cette opération (et ne peut donc pas être un ensemble à un élément).

Puisque le support   de   est une réunion de  -orbites,   et   opère sur  ; en particulier, si un élément   appartient au support de  , l'élément   appartient lui aussi à ce support (on peut évidemment le prouver plus directement). Puisque   et   sont distincts, ceci montre de nouveau que si le support n’est pas vide, il comporte au moins deux éléments.

Début d'un lemme
Fin du lemme


Démonstration. Nous savons déjà que le support de   est contenu dans la réunion des supports des  , donc si x n'appartient à aucun des supports  , il est point fixe de  . Dans le cas contraire, il existe un et un seul i tel que  . Puisque x n'appartient pas aux supports de  , nous avons

 ,

d'où, en appliquant   aux deux membres,

 .

D'après ce que nous avons vu,   appartient au support de   et n'appartient donc à aucun des supports   et est donc point fixe de  . En passant aux valeurs par   dans la précédente égalité, nous trouvons donc   comme annoncé.
Il résulte de ce qui précède que le support de   est la réunion des supports des  .
En appliquant l'explicitation trouvée de   au nombre n = 2, à la composée   et à la composée  , nous trouvons que deux permutations de E à supports disjoints commutent.

Définition

modifier


Remarques.
1° D'après cette définition, la permutation identique de E n’est pas un cycle, puisque le sous-groupe de   qu'elle engendre, à savoir le sous-groupe réduit à elle-même, agit trivialement, c'est-à-dire que toutes les orbites de cette action sont ponctuelles.
2° Puisque le support d'une permutation est toujours la réunion de ses orbites non ponctuelles, le support d'un cycle   est la seule orbite non ponctuelle pour l'opération de  .
3° Une description des cycles qui fait mieux comprendre leur nom sera donnée plus loin.

Décomposition d'une permutation en cycles

modifier

Soient   une permutation de E et   une orbite relative à l'opération de   sur E;   permute les points de  , donc il existe une et une seule permutation   de E qui coïncide avec   en tout point de   et qui laisse fixe tout point de E qui n'appartient pas à  ; pour tout entier rationnel n et pour tout élément x de  , nous avons  , donc   est une orbite de  . Il est clair que si   n’est pas ponctuelle,   est un cycle de support  .

Début d'un lemme
Fin du lemme


Démonstration. Soit x un élément de E. D'après le lemme précédent, nous avons   si x n'appartient au support d'aucun des cycles   et, dans le cas contraire,  , où   désigne le seul élément de C dont le support comprenne x.
Première conséquence : soit   un cycle appartenant à C;   coïncide avec   en tout point de  , donc, pour tout entier rationnel n,   coïncide avec   en tout point de  , donc   est une orbite, évidemment non ponctuelle, relative à l'opération de  .
Seconde conséquence : tout élément du support de   est contenu dans le support d'un élément de C; cela revient à dire que pour toute orbite non ponctuelle   de l'opération de  , tout élément x de   appartient au support d'un élément de C; d’après la première partie de la démonstration, ce support est une orbite de  ; comme une orbite ne peut être contenue dans une autre que si elle lui est égale,  .
Nous avons donc prouvé que l’application   est une surjection de C sur l’ensemble des orbites non ponctuelles pour l'opération de  . C'est une injection, car si   et   sont deux éléments distincts de C, leurs supports sont disjoints et ne peuvent donc être égaux que s'ils sont vides, ce qui contredit la définition d'un cycle.
La partie de l'énoncé relative à   résulte clairement du reste de l'énoncé.


Soit   une permutation de E. Pour toute orbite non ponctuelle   relative à l'opération de   sur E, désignons par   l'unique cycle   qui coïncide avec   en tout point de   et laisse fixes tous les points de E qui n'appartiennent pas à  . (Nous avons noté que ce cycle existe et admet   pour support.) Désignons par L l’ensemble des cycles  , où   parcourt les orbites non ponctuelles relatives à l'opération de   sur E. Puisque les orbites en question sont deux à deux disjointes, les éléments de L sont des cycles à supports deux à deux disjoints. Posons

 ;

ceci peut encore s'écrire

 ,

  désigne l’ensemble des orbites non ponctuelles pour l'opération de   (car à deux orbites non ponctuelles distinctes   correspondent deux cycles   distincts).
Soit x un point de E. D'après le lemme qui précède,

a)   si x n'appartient au support d'aucun élément de L, c'est-à-dire si x n'appartient à aucune orbite non ponctuelle de l'opération de   sur E, c'est-à-dire si x n'appartient pas au support de  ;
b) si x appartient au support   de l'élément   de L,  .

Il résulte des points a) et b) que

 ,

d'où l’existence d'un ensemble L tel que dans l'énoncé. Prouvons l'unicité de L. Supposons qu'un ensemble M de cycles à supports deux à deux disjoints soit tel que

 .

D'après la dernière partie du lemme qui précède, les éléments de M sont les   définis plus haut, c'est-à-dire les éléments de L.

On dit que l'écriture   est la décomposition canonique de   en produits de cycles.


Démonstration. Soit  , où   sont des cycles à supports deux à deux disjoints. Désignons par   le ppcm des ordres de  . Pour tout nombre entier  , le support de   est contenu dans celui de  , donc les supports de   sont deux à deux disjoints. Nous avons vu que des permutations à supports deux à deux disjoints commutent, donc, pour tout nombre entier  ,

 .

Faisons d’abord t = m. Chaque facteur   du second membre est alors égal à  , donc il en est de même du premier membre, donc   est multiple de l’ordre de  .
Faisons maintenant  , où   est l’ordre de  . Nous trouvons

 .

D'après un précédent lemme, il en résulte que le support de  , c'est-à-dire l’ensemble vide, est la réunion des supports des  , donc ces supports sont vides. Donc, pour chaque i,  , donc s est multiple de l’ordre de chaque  , donc s est multiple de m. On a donc bien s = m.

Notation d'un cycle

modifier


Démonstration. Voici tout d’abord une démonstration qui fait une assez large part aux calculs. Soit x un élément de  . Il existe au moins un nombre naturel s > 0 tel que  , par exemple l’ordre de  . Désignons par   le plus petit des nombres naturels s > 0 tels que  . (La suite montrera que   ne dépend pas de x.) Puisque   est l'orbite de x pour l'opération du groupe   sur E, tout élément de   est de la forme  , avec  . (Puisque   est d'ordre fini, on peut même supposer t naturel.) Si r désigne le reste euclidien de t par  , nous avons alors  , ce qui montre que   représentent tous les éléments de  . Si nous avions   avec  , nous aurions   avec  , ce qui contredit la minimalité de  . Donc   sont deux à deux distincts, donc  , donc   est le nombre k de l'énoncé et, en particulier, est indépendant de x. Donc, pour tout  ,  . Puisque   coïncide avec l'identité hors de  , nous avons donc  , donc k est supérieur ou égal à l’ordre de  . D'autre part, il est clair que, par minimalité de   dans l’ensemble des s > 0 tels que  ,  , c'est-à-dire k, est inférieur ou égal à l’ordre de  . (D'ailleurs, nous savons que le cardinal d'une orbite divise l’ordre du groupe opérant.) Nos deux derniers résultats prouvent que l’ordre de   est égal à k.

Voici maintenant une démonstration plus «bourbakiste». Puisque   est une orbite pour l'opération du groupe   sur E, le groupe   opère transitivement sur  . Prouvons que cette opération est fidèle. Soit   un élément du groupe   qui fixe tout point de  ; il s'agit de prouver que   est l'élément neutre de  . Puisque la permutation   est une puissance de   et que   fixe tout point n'appartenant pas à  ,   fixe tout point n'appartenant pas à  . Nous supposons de plus que   fixe tout point de  , donc   fixe tout point de E, donc est bien l'élément neutre de  . Ainsi, l'opération du groupe   sur   est transitive et fidèle. Puisque ce groupe est cyclique, il est commutatif, donc, d’après un exercice sur les actions de groupe, l'action de   sur   est simplement transitive, donc, pour tout élément x de  , l’application orbitale   est une bijection. D'autre part, désignons par r l’ordre du groupe  ; puisque ce groupe est cyclique avec   pour générateur, l’application de   dans   qui applique i sur   est une bijection. En composant les deux bijections trouvées, nous voyons que l’application de   dans   qui applique i sur   est une bijection, d'où l'énoncé.


La précédente proposition permet de caractériser les cycles comme suit : soient E un ensemble fini et   des points de E deux à deux distincts, avec  ; l'unique permutation de E qui applique   sur   pour chaque   et   sur   et laisse fixes tous les autres points de E est un cycle de support   et de longueur n, cycle que nous noterons

  (sans virgules[2]);

réciproquement, tout cycle est de cette forme, et plus précisément, si   est un cycle de longueur n, si x est un élément du support de  , il existe un et un seul n-uplet   de points de E tel que   et  .

Il est clair que la permutation inverse du n-cycle   est le n-cycle  .

Si E est un ensemble fini et   une permutation de E, on peut écrire   comme produit de cycles à supports disjoints de la façon suivante : si   n’est pas la permutation identique, on choisit un élément   de son support et on construit comme suit un premier cycle   de la décomposition de   : on pose

 

et on calcule

 

en s'arrêtant au premier nombre   tel que  . On obtient ainsi un premier cycle   de la décomposition de  , correspondant à une première  -orbite non ponctuelle  . Si cette orbite n’est pas le support de   tout entier, on choisit un élément   du support n'appartenant pas à l'orbite et, comme à partir de  , on construit à partir de   un second cycle  , correspondant à une seconde orbite non ponctuelle de  . Si la réunion des deux orbites trouvées n’est pas le support tout entier, on poursuit jusqu'à ce qu'on ait trouvé toutes les orbites non ponctuelles de  . On obtient ainsi la décomposition canonique de   en produit de cycles :

 .

D'après ce qui précède, cette écriture est unique à l’ordre des facteurs près et, pour chaque facteur, au choix près du point de départ de l'énumération des éléments du support du cycle.

Il est parfois intéressant d'ajouter à la décomposition canonique d'une permutation la liste de ses points fixes; on parle alors de décomposition complète[3].

Nous appellerons structure cyclique d'une permutation l'énumération des longueurs des cycles intervenant dans sa décomposition canonique, chaque longueur apparaissant dans l'énumération autant de fois qu’il y a de cycles de cette longueur dans la décomposition. Par exemple, la permutation

 

de l’ensemble   a pour structure cyclique 2, 3, 3.

Effet d'une conjugaison sur un cycle

modifier

Soient E et F deux ensembles équipotents, f une bijection de E sur F. Nous avons vu que l’application   définit un isomorphisme du groupe   sur le groupe  .
On vérifie facilement que si   est le cycle  , alors   est le cycle  .
Puisque   est un isomorphisme,   applique donc le produit de cycles  

 

sur

 .

En particulier, si F = E, si f est la permutation   de E, nous trouvons que le conjugué   du cycle   est le cycle  .
De même, le produit de cycles

 

a pour conjugué par  

 .

Si les facteurs du premier produit ont des supports deux à deux disjoints, il en est de même des facteurs du second produit. On en tire facilement que deux permutations d'un même ensemble fini E sont conjuguées dans   si et seulement si elles ont la même structure cyclique. En particulier, puisque l'inverse d'un cycle est un cycle de même longueur et de même support, une permutation et son inverse sont toujours conjuguées.

Transpositions

modifier


La transposition   est donc l'unique transposition   qui échange a et b.

Début d'un lemme
Fin du lemme


Démonstration. On vérifie facilement que le cycle   est égal à

 .
Début d’un théorème
Fin du théorème


Démonstration. Nous avons vu qu'une telle permutation est un produit de cycles et nous venons de voir qu'un cycle est un produit de transpositions.

Remarque. Voici une démonstration qui n'utilise pas la décomposition en cycles. Soit   une permutation d'un ensemble fini E ; nous allons prouver que   est décomposable en transpositions, en raisonnant par récurrence sur le cardinal du support de  . Si ce cardinal est nul,   est la permutation identique et est donc le produit de la famille vide de transpositions. Sinon, le support de   n’est pas vide. Choisissons un élément   de ce support et posons  . Comme déjà noté,   appartient aussi au support de  . Tout point fixe de   est distinct de   et de  , donc est point fixe de   ; de plus, il est clair que   est également point fixe de  . Donc   a strictement plus de points fixes que  , autrement dit, le support de   a strictement moins d'éléments que celui de  . Par hypothèse de récurrence,   est décomposable en produit de permutations, donc  , qui peut s'écrire  , l'est aussi. (On aurait aussi pu raisonner par récurrence sur le cardinal de E.)

Notons maintenant que la multiplication dans Z induit sur la partie   de Z une loi de composition interne qui en fait un groupe cyclique d'ordre 2 dont –1 est générateur ; pour tout entier rationnel u, la condition   équivaut à ce que u soit pair ; pour tous entiers rationnels u et v, la condition   équivaut à ce que u et v aient la même parité (c'est-à-dire soient ou bien tous deux pairs ou bien tous deux impairs).

Quand on parlera du groupe  , il s'agira du groupe qu'on vient de considérer, qui peut aussi être défini comme le sous-groupe   du groupe multiplicatif des nombres rationnels non nuls.

Début d’un théorème
Fin du théorème


Supposons d’abord   pour un certain nombre naturel n. Pour toute permutation   de  , nous dirons qu'une paire d'éléments de   est une inversion de   si, i désignant le plus petit élément de cette paire et j le plus grand,  . Soient   et   deux permutations de   et   une paire d'éléments de  . Il est clair que   est une inversion de   si et seulement si une des deux conditions suivantes est satisfaite :

  est une inversion de   et   n’est pas une inversion de   ;
  n’est pas une inversion de   et   est une inversion de  .

Nous allons définir un homomorphisme de   dans le groupe  .

Pour toute permutation   de E et toute paire P d'éléments de E, définissons   comme égal à –1 si P est une inversion de   et à 1 dans le cas contraire. D'après ce qui précède, nous avons toujours

 ,

  désigne la paire formée par les images par   des deux éléments de P.

En prenant le produit sur l’ensemble   des paires d'éléments de P, nous trouvons

 .

L'application   est une permutation de l'index  , donc le produit   peut s'écrire  , d'où

 .

Ceci montre que l'application

 

est un homomorphisme de   dans  .

Il est clair que cet homomorphisme peut s'écrire

 ,

  désigne le nombre d'inversions de  . Montrons maintenant que cet homomorphisme applique toute transposition sur -1. Il s'agit de prouver que le nombre d'inversions d'une transposition est toujours impair. Soit (a b) une transposition, avec a < b. Les inversions de cette permutation sont la paire {a, b}, les paires   avec  , et les paires  , avec  . Le nombre des inversions de (a b) est donc  , qui est bien impair.

Nous avons donc prouvé qu’il existe un homomorphisme de   dans   qui applique toute transposition sur -1. Un tel homomorphisme est unique, puisque les transpositions engendrent  . Pour toute permutation  , désignons par   l'image de   par cet homomorphisme.

Passons maintenant au cas général d'un ensemble fini E. Soit n le cardinal de E. Choisissons une bijection f de E sur  . Nous avons vu que l'application

 

est un isomorphisme de groupes qui applique tout cycle sur un cycle de même longueur et, en particulier, applique donc toute transposition sur une transposition. Le composé   est donc un homomorphisme de   dans   qui applique toute transposition sur –1. Ici encore, puisque les transpositions engendrent  , un tel homomorphisme est unique. Nous désignerons encore par   l'image de   par cet homomorphisme.

Si une permutation   de E peut s'écrire

 

et

 ,

les   et les   étant des transpositions, le passage aux valeurs par   donne  , donc r et s ont même parité.



Un cycle est une permutation paire si et seulement si sa longueur est impaire ; en effet, nous avons vu qu'un cycle de longueur r est le produit de r – 1 transpositions.

Si   est un élément d'ordre impair du groupe  , c’est une permutation paire ; en effet, puisque   définit un homomorphisme de   dans  , l’ordre de   divise celui de   et est donc impair ; or le seul élément d'ordre impair dans   est 1, donc  , donc   est une permutation paire.

La converse n’est pas vraie : un élément d'ordre pair du groupe   n’est pas forcément une permutation impaire. Par exemple, si E comprend aux moins quatre éléments différents a, b, c, d, la permutation   de E a pour ordre le ppcm des ordres de   et de  , autrement dit est d'ordre 2 et donc pair, et pourtant c’est une permutation paire.

Ce qui précède montre que pour calculer  , il n’est pas nécessaire de faire un long relevé d'inversions. Tout d’abord, si on connaît une décomposition de   en produit de transpositions,   est égal à 1 ou à –1 selon que le nombre de facteurs est pair ou impair.

Il suffit même de trouver la décomposition de   en produit de cycles à supports disjoints : la signature de   est le produit des signatures de ces cycles, et, d’après un résultat précédent, la signature d'un cycle   est  , où   désigne la longueur de  . Il est clair qu'on peut même se contenter de connaître les cardinaux des  -orbites. Enfin, si   désigne l’ensemble des  -orbites non ponctuelles,

  =  ,

  désigne l’ensemble de toutes les orbites, y compris les orbites ponctuelles ; le second membre est égal à nt, où n = Card(E) et où t est le nombre des  -orbites, y compris les  -orbites ponctuelles. On a donc

 .

(Ceci fournit d'ailleurs une définition alternative de la signature d'une permutation.)

La notion de signature d'une permutation intervient en algèbre linéaire, dans l'étude des déterminants.

Notes et références

modifier
  1. N. Bourbaki, Algèbre, ch. I, § 5, no 7, Paris, 1970, p. 59, ne définit le support d'une permutation que si cette permutation est un cycle. J. Calais, Éléments de théorie des groupes, Paris, 1984, p. 106, définit le support pour n’importe quelle permutation.
  2. Pas de virgules dans N. Bourbaki, Algèbre, ch. I, § 5, exerc. 12, b, Paris, 1970, p. 131; dans J.J. Rotman, An Introduction to the Theory of Groups, 4e éd., New York, tirage de 1999, p. 3; virgules dans J. Calais, Éléments de théorie des groupes, Paris, 1984, p. 108; dans P. Tauvel, Algèbre, 2e éd., Paris, 2005, p. 60...
  3. J.J. Rotman, An Introduction to the Theory of Groups, 4e édition, tirage de 1999, p. 6.