Leçons de niveau 14

Théorie des groupes/Groupes symétriques finis

Une page de Wikiversité.
Sauter à la navigation Sauter à la recherche
Début de la boite de navigation du chapitre
Groupes symétriques finis
Icône de la faculté
Chapitre no 12
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
Icon falscher Titel.svg
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 | modifier le wikicode]

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 | modifier le wikicode]


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.

Cycles[modifier | modifier le wikicode]

Définition[modifier | modifier le wikicode]


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 | modifier le wikicode]

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 | modifier le wikicode]


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 | modifier le wikicode]

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 | modifier le wikicode]


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).

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 | modifier le wikicode]

  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.