Groupe (mathématiques)/Groupes symétriques finis/Cycles

Une page de Wikiversité.

< Groupe (mathématiques) | Groupes symétriques finis

**Cycles**
Leçon : Groupes symétriques finis

Chapitre 3
Chap. préc. :	Support d'une permutation
Chap. suiv. :	Transpositions

En raison de limitations techniques, la typographie souhaitable du titre, « Groupes symétriques finis : Cycles
Groupe (mathématiques)/Groupes symétriques finis/Cycles », n'a pu être restituée correctement ci-dessus.

Sommaire

1 Définition
2 Décomposition d'une permutation en cycles
3 Notation d'un cycle
4 Effet d'une conjugaison sur un cycle
5 Notes et références

[modifier] Définition

Cycles

Soit E un ensemble fini. On dit qu'une permutation $γ$ de E est un cycle si l'opération du groupe $< γ >$ sur E admet une et une seule orbite non ponctuelle.

Remarques.
1° D'après cette définition, la permutation identique de E n'est pas un cycle, puisque le sous-groupe de $\ S_{E}$ 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 $\ \gamma$ est la seule orbite non ponctuelle pour l'opération de $\ <\gamma>$ .
3° Une description des cycles qui fait mieux comprendre leur nom sera donnée plus loin.

[modifier] Décomposition d'une permutation en cycles

Soient $\ \sigma$ une permutation de E et $\ \omega$ une orbite relative à l'opération de $\ <\sigma>$ sur E; $\ \sigma$ permute les points de $\ \omega$ , donc il existe une et une seule permutation $\ \gamma$ de E qui coïncide avec $\ \sigma$ en tout point de $\ \omega$ et qui laisse fixe tout point de E qui n'appartient pas à $\ \omega$ ; pour tout entier rationnel n et pour tout élément x de $\ \omega$ , nous avons $\ \gamma^{n}(x) = \sigma^{n}(x)$ , donc $\ \omega$ est une orbite de $\ \gamma$ . Il est clair que si $\ \omega$ n'est pas ponctuelle, $\ \gamma$ est un cycle de support $\ \omega$ .

Lemme

Soient E un ensemble fini et C un ensemble (fini) de cycles $\in S_{E}$ à supports deux à deux disjoints; désignons par $\ \sigma$ le produit $\prod _{\gamma \in C}\gamma$ (correctement défini puisque les éléments de C commutent deux à deux). L'application $f : \gamma \mapsto \mathrm{supp}(\gamma)$ est une bijection de C sur l'ensemble des orbites non ponctuelles pour l'opération de $\ <\sigma>$ . Si $\ \omega$ est une de ces orbites non ponctuelles, $\ f^{-1}(\omega)$ est l'unique cycle qui coïncide avec $\ \sigma$ dans $\ \omega$ et laisse fixes les points de E qui n'appartiennent pas à $\ \omega$ .

Démonstration. Soit x un élément de E. D'après le lemme précédent, nous avons $\ \sigma(x) = x$ si x n'appartient au support d'aucun des cycles $\gamma \in C$ et, dans le cas contraire, $\ \sigma(x) = \gamma(x)$ , où $\ \gamma$ désigne le seul élément de C dont le support comprenne x.
Première conséquence : soit $\ \gamma$ un cycle appartenant à C; $\ \sigma$ coïncide avec $\ \gamma$ en tout point de $\ \mathrm{supp}(\gamma)$ , donc, pour tout entier rationnel n, $\ \sigma^{n}$ coïncide avec $\ \gamma^{n}$ en tout point de $\ \mathrm{supp}(\gamma)$ , donc $\ \mathrm{supp}(\gamma)$ est une orbite, évidemment non ponctuelle, relative à l'opération de $\ <\sigma>$ .
Seconde conséquence : tout élément du support de $\ \sigma$ est contenu dans le support d'un élément de C; cela revient à dire que pour toute orbite non ponctuelle $\ \omega$ de l'opération de $\ <\sigma>$ , tout élément x de $\ \omega$ 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 $\ \sigma$ ; comme une orbite ne peut être contenue dans une autre que si elle lui est égale, $\ \omega = \mathrm{supp}(\gamma)$ .
Nous avons donc prouvé que l'application $\gamma \mapsto \mathrm{supp}(\gamma)$ est une surjection de C sur l'ensemble des orbites non ponctuelles pour l'opération de $\ <\sigma>$ . C'est une injection, car si $\ \gamma_{1}$ et $\ \gamma_{2}$ 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 à $\ f^{-1}$ résulte clairement du reste de l'énoncé.

Proposition

Soit E un ensemble fini. Pour toute permutation $\ \varphi$ de E, il existe un et un seul ensemble (fini) L de cycles $\in S_{E}$ à supports deux à deux disjoints tel que $\varphi = \prod _{\lambda \in L}\lambda$ .

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

$\sigma = \prod _{\lambda \in L}\lambda$ ;

ceci peut encore s'écrire

$\sigma = \prod _{\omega \in \Omega}\omega$ ,

où $\ \Omega$ désigne l'ensemble des orbites non ponctuelles pour l'opération de $\ <\varphi>$ (car à deux orbites non ponctuelles distinctes $\ \omega_{1}, \omega_{2}$ correspondent deux cycles $\ \omega_{1}, \omega_{2}$ distincts).
Soit x un point de E. D'après le lemme qui précède,

a) $\ \sigma(x) = x$ 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 $\ <\varphi>$ sur E, c'est-à-dire si x n'appartient pas au support de $\ \varphi$ ;

b) si x appartient au support $\ \omega$ de l'élément $\ \gamma_{\omega}$ de L, $\ \sigma(x) = \gamma_{\omega}(x) = \varphi(x)$ .

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

$\ \varphi = \sigma = \prod _{\lambda \in L}\lambda$ ,

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

$\ \varphi = \prod _{\mu \in M}\mu$ .

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

On dit que l'écriture $\varphi = \prod _{\lambda \in L}\lambda$ est la décomposition canonique de $\varphi$ en produits de cycles.

Corollaire

Soient E un ensemble fini et $\ \sigma$ une permutation de E. L'ordre de $\ \sigma$ dans $\ S_{E}$ est le ppcm des ordres des cycles qui apparaissent dans la décomposition canonique de $\ \sigma$ .

Démonstration. Soit $\ \sigma = \gamma_{1} \ldots \gamma_{r}$ , où $\gamma_{1}, \ldots , \gamma_{r}$ sont des cycles à supports deux à deux disjoints. Désignons par $\ m$ le ppcm des ordres de $\ \gamma_{i}$ . Pour tout nombre entier $\ t$ , le support de $\ \gamma_{i}^{t}$ est contenu dans celui de $\ \gamma_{i}$ , donc les supports de $\gamma_{1}^{t}, \ldots ,\gamma_{r}^{t}$ sont deux à deux disjoints. Nous avons vu que des permutations à supports deux à deux disjoints commutent, donc, pour tout nombre entier $\ t$ ,

$\sigma^{t} = \gamma_{1}^{t} \ldots \gamma_{r}^{t}$ .

Faisons d'abord t = m. Chaque facteur $\gamma_{i}^{t}$ du second membre est alors égal à $\ \mathrm{id}_{E}$ , donc il en est de même du premier membre, donc $\ m$ est multiple de l'ordre de $\ \sigma$ .
Faisons maintenant $\ t = s$ , où $\ s$ est l'ordre de $\ \sigma$ . Nous trouvons

$\mathrm{id}_{E} = \gamma_{1}^{s} \ldots \gamma_{r}^{s}$ .

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

[modifier] Notation d'un cycle

Proposition

Soient E un ensemble fini et $\ \gamma$ un cycle $\in S_{E}$ , soit $\ \Omega$ le support de $\ \gamma$ . Le cardinal de $\ \Omega$ est égal à l'ordre de $\ \gamma$ dans le groupe $\ S_{E}$ . Si k désigne ce cardinal, si x est un élément de $\ \Omega$ , les k éléments $x, \gamma(x), \gamma^{2}(x), \ldots , \gamma^{k-1}(x)$ sont deux à deux distincts et représentent $\ \Omega$ tout entier.

Démonstration. Voici tout d'abord une démonstration qui fait une assez large part aux calculs. Soit x un élément de $\ \Omega$ . Il existe au moins un nombre naturel s > 0 tel que $γ s (x) = x$ , par exemple l'ordre de $\ \gamma$ . Désignons par $\ s_{x}$ le plus petit des nombres naturels s > 0 tels que $γ s (x) = x$ . (La suite montrera que $\ s_{x}$ ne dépend pas de x.) Puisque $\ \Omega$ est l'orbite de x pour l'opération du groupe $\ <\gamma>$ sur E, tout élément de $\ \Omega$ est de la forme $\ y = \gamma^{t}(x)$ , avec $t \in \mathbb{Z}$ . (Puisque $\ \gamma$ est d'ordre fini, on peut même supposer t naturel.) Si r désigne le reste euclidien de t par $\ s_{x}$ , nous avons alors $y = γ r (x)$ , ce qui montre que $x, \gamma(x), \gamma^{2}(x), \ldots , \gamma^{s_{x}-1}(x)$ représentent tous les éléments de $\ \Omega$ . Si nous avions $\ \gamma^{u}(x) = \gamma^{v}(x)$ avec $0 \leq u < v \leq s_{x}-1$ , nous aurions $\ \gamma^{v-u}(x) = x$ avec $\ 0 < v-u < s_{x}$ , ce qui contredit la minimalité de $\ s_{x}$ . Donc $x, \gamma(x), \gamma^{2}(x), \ldots , \gamma^{s_{x}-1}(x)$ sont deux à deux distincts, donc $s x = Card(Ω)$ , donc $s x$ est le nombre k de l'énoncé et, en particulier, est indépendant de x. Donc, pour tout $x \in \Omega$ , $γ k (x) = x$ . Puisque $γ$ coïncide avec l'identité hors de $\ \Omega$ , nous avons donc $γ k = id E$ , donc k est supérieur ou égal à l'ordre de $γ$ . D'autre part, il est clair que, par minimalité de $\ s_{x}$ dans l'ensemble des s > 0 tels que $γ s (x) = x$ , $\ s_{x}$ , 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 $\ \Omega$ est une orbite pour l'opération du groupe $\ <\gamma>$ sur E, le groupe $\ <\gamma>$ opère transitivement sur $\ \Omega$ . Prouvons que cette opération est fidèle. Soit $\ \sigma$ un élément du groupe $\ <\gamma>$ qui fixe tout point de $\ \Omega$ ; il s'agit de prouver que $\ \sigma$ est l'élément neutre de $\ S_{E}$ . Puisque la permutation $\ \sigma$ est une puissance de $\ \gamma$ et que $\ \gamma$ fixe tout point n'appartenant pas à $\ \Omega$ , $\ \sigma$ fixe tout point n'appartenant pas à $\ \Omega$ . Nous supposons de plus que $\ \sigma$ fixe tout point de $\ \Omega$ , donc $\ \sigma$ fixe tout point de E, donc est bien l'élément neutre de $\ S_{E}$ . Ainsi, l'opération du groupe $\ <\gamma>$ sur $\ \Omega$ 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 $\ <\gamma>$ sur $\ \Omega$ est simplement transitive, donc, pour tout élément x de $\ \Omega$ , l'application orbitale $f_{x} : <\gamma> \rightarrow \Omega : \sigma \mapsto \sigma(x)$ est une bijection. D'autre part, désignons par r l'ordre du groupe $\ <\gamma>$ ; puisque ce groupe est cyclique avec $\ \gamma$ pour générateur, l'application de $\{0, 1, \ldots , r-1\}$ dans $\ <\gamma>$ qui applique i sur $\ \gamma^{i}$ est une bijection. En composant les deux bijections trouvées, nous voyons que l'application de $\{0, 1, \ldots , r-1\}$ dans $\ \Omega$ qui applique i sur $\ \gamma^{i}(x)$ est une bijection, d'où l'énoncé.

Longueur d'un cycle

Soit $\ \gamma$ un cycle $\in S_{E}$ . On appelle longueur de $\ \gamma$ l'ordre de $\ \gamma$ comme élément du groupe $\ S_{E}$ , ou, ce qui revient au même, le cardinal du support de $\ \gamma$ . Un cycle de longueur s est appelé s-cycle.

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

$(x_{1} \ldots x_{n})$ (sans virgules^[1]);

réciproquement, tout cycle est de cette forme, et plus précisément, si $\gamma \in S_{E}$ est un cycle de longueur n, si x est un élément du support de $\ \gamma$ , il existe un et un seul n-uplet $(x_{1}, \ldots , x_{n})$ de points de E tel que $\ x_{1} = x$ et $\ \gamma = (x_{1} \ldots x_{n})$ .

Il est clair que la permutation inverse du n-cycle $\ (x_{1} \ldots x_{n})$ est le n-cycle $\ (x_{n} \ldots x_{1})$ .

Si E est un ensemble fini et $\ \sigma$ une permutation de E, on peut écrire $\ \sigma$ comme produit de cycles à supports disjoints de la façon suivante : si $\ \sigma$ n'est pas la permutation identique, on choisit un élément $\ a_{1}$ de son support et on construit comme suit un premier cycle $(x_{1,1} \ldots x_{1,r_{1}})$ de la décomposition de $\ \sigma$ : on pose

$\ x_{1,1} = a_{1}$

et on calcule

$\ x_{1,2} = \sigma(x_{1,1}), \ldots , x_{1,r_{1}} = \sigma(x_{1,r_{1}-1})$

en s'arrêtant au premier nombre $\ r_{1}$ tel que $\ x_{1,r_{1}+1} = \sigma(x_{1,1})$ . On obtient ainsi un premier cycle $(x_{1,1} \ldots x_{1,r_{1}})$ de la décomposition de $\ \sigma$ , correspondant à une première $\ <\sigma>$ -orbite non ponctuelle $\{x_{1,1}, \ldots , x_{1,r_{1}}\}$ . Si cette orbite n'est pas le support de $\ \sigma$ tout entier, on choisit un élément $\ a_{2}$ du support n'appartenant pas à l'orbite et, comme à partir de $\ a_{1}$ , on construit à partir de $\ a_{2}$ un second cycle $(x_{2,1} \ldots x_{2,r_{2}})$ , correspondant à une seconde orbite non ponctuelle de $\ \sigma$ . 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 $\ \sigma$ . On obtient ainsi la décomposition canonique de $\ \sigma$ en produit de cycles :

$\sigma = (x_{1,1} \ldots x_{1,r_{1}}) \ (x_{2,1} \ldots x_{2,r_{2}}) \ (x_{s,1} \ldots x_{s,r_{s}})$ .

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^[2].

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

$\ (1 \ 3 \ 2) \ (4 \ 8) \ (5 \ 9 \ 6)$

de l'ensemble $\ \{1, 2, 3, 4, 5, 6, 7, 8, 9\}$ a pour structure cyclique 2, 3, 3.

[modifier] Effet d'une conjugaison sur un cycle

Soient E et F deux ensembles équipotents, f une bijection de E sur F. Nous avons vu que l'application $\Gamma_{f} : S_{E} \rightarrow S_{F} : \sigma \mapsto f \circ \sigma \circ f^{-1}$ définit un isomorphisme du groupe $S E$ sur le groupe $S F$ .
On vérifie facilement que si $\gamma \in S_{E}$ est le cycle $(a_{1} \ a_{2}\ldots \ a_{r})$ , alors $\ \Gamma_{f}(\gamma)$ est le cycle $(f(a_{1}) \ f(a_{2}) \ldots \ f(a_{r})) \in S_{F}$ .
Puisque $Γ f$ est un isomorphisme, $Γ f$ applique donc le produit de cycles $\in S_{E}$

$(a_{1,1} \ a_{1,2}\ldots \ a_{1,r_{1}}) \ \ldots (a_{s,1} \ a_{s,2}\ldots \ a_{s,r_{s}})$

sur

$(f(a_{1,1)} \ f(a_{1,2}) \ldots \ f(a_{1,r_{1}})) \ \ldots (f(a_{s,1}) \ f(a_{s,2}) \ldots \ f(a_{s,r_{s}}))$ .

En particulier, si F = E, si f est la permutation $\ \sigma$ de E, nous trouvons que le conjugué $\sigma \circ (a_{1} \ a_{2}\ldots \ a_{r}) \circ \sigma^{-1}$ du cycle $(a_{1} \ a_{2}\ldots \ a_{r}) \in S_{E}$ est le cycle $(\sigma(a_{1}) \ \sigma(a_{2}) \ldots \ \sigma(a_{r})) \in S_{E}$ .
De même, le produit de cycles

$(a_{1,1} \ a_{1,2}\ldots \ a_{1,r_{1}}) \ \ldots (a_{s,1} \ a_{s,2}\ldots \ a_{s,r_{s}})$

a pour conjugué par $\ \sigma$

$(\sigma(a_{1,1)} \ \sigma(a_{1,2}) \ldots \ \sigma(a_{1,r_{1}})) \ \ldots (\sigma(a_{s,1}) \ \sigma(a_{s,2}) \ldots \ \sigma(a_{s,r_{s}}))$ .

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 $\ S_{E}$ 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.

[modifier] Notes et références

↑ 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, 4^e é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, 2^e éd., Paris, 2005, p. 60...
↑ J.J. Rotman, An Introduction to the Theory of Groups, 4^e édition, tirage de 1999, p. 6.

[0] 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, 4^e é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, 2^e éd., Paris, 2005, p. 60...

[1] J.J. Rotman, An Introduction to the Theory of Groups, 4^e édition, tirage de 1999, p. 6.

[1]

[2]

Groupe (mathématiques)/Groupes symétriques finis/Cycles

Une page de Wikiversité.

Sommaire

[modifier] Définition

[modifier] Décomposition d'une permutation en cycles

[modifier] Notation d'un cycle

[modifier] Effet d'une conjugaison sur un cycle

[modifier] Notes et références

Affichages

Outils personnels

Rechercher

Navigation

Contribuer

Imprimer / exporter

Boîte à outils