Théorie des groupes/Groupes symétriques finis

Début de la boite de navigation du chapitre

fin de la boite de navigation du chapitre

Groupe symétrique comme groupe opérant

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

Groupe symétrique d'un ensemble

Soit E un ensemble. On désigne par $\ S_{E}$ ou ${\mathfrak {S}}(E)$ l’ensemble des permutations de E, muni de la loi de groupe $\circ$ définie par $f\circ g(x)=f(g(x))$ pour toutes permutations f et g de E et pour tout élément x de E. Ce groupe est dit groupe symétrique de E.

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

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

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

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

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

Support d'une permutation

Support d'une permutation

Soient E un ensemble et $\sigma$ une permutation de E. On appelle support de $\sigma$, et on note supp($\sigma$), l’ensemble des éléments de E qui ne sont pas points fixes de $\sigma$, autrement dit l’ensemble des éléments x de E tels que $\sigma (x)\not =x$.

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 $\sigma _{1},\ldots ,\sigma _{n}$ des permutations d'un même ensemble E; alors

$\mathrm {supp} (\sigma _{1}\circ \ldots \circ \sigma _{n})\subseteq \mathrm {supp} (\sigma _{1})\cup \ldots \cup \mathrm {supp} (\sigma _{n})$

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

2° Le support de $\sigma ^{-1}$ est égal à celui de $\sigma$.

3° Les points fixes de $\sigma$ sont les points fixes pour l'opération de $<\sigma >$ sur E, donc le support de $\sigma$ 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 $\ \mathrm {supp} (\sigma )$ de $\ \sigma$ est une réunion de $\ <\sigma >$-orbites, $\ <\sigma >{\rm {{supp}(\sigma )={\rm {{supp}(\sigma )}}}}$ et $\ <\sigma >$ opère sur $\ \mathrm {supp} (\sigma )$; en particulier, si un élément $\ x$ appartient au support de $\ \sigma$, l'élément $\ \sigma (x)$ appartient lui aussi à ce support (on peut évidemment le prouver plus directement). Puisque $\ x$ et $\ \sigma (x)$ 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

Lemme

Soient E un ensemble et $\sigma _{1},\ldots ,\sigma _{n}$ des permutations de E à supports deux à deux disjoints (c'est-à-dire que $\mathrm {supp} (\sigma _{i})\cap \mathrm {supp} (\sigma _{j})=\emptyset$ pour tout couple (i, j) d'indices distincts). Posons $\sigma =\sigma _{1}\sigma _{2}\ldots \sigma _{n}$. Soit x un élément de E. Si x n'appartient à aucun des supports $\ \mathrm {supp} (\sigma _{i})$, $\ \sigma (x)$ est égal à x, sinon, il est égal à $\ \sigma _{i}(x)$, où i désigne le seul indice tel que $x\in \mathrm {supp} (\sigma _{i})$. Le support de $\sigma$ est la réunion des supports des $\ \sigma _{i}$. Deux permutations de E à supports disjoints commutent.

Fin du lemme

Démonstration. Nous savons déjà que le support de $\ \sigma$ est contenu dans la réunion des supports des $\ \sigma _{i}$, donc si x n'appartient à aucun des supports $\ \mathrm {supp} (\sigma _{i})$, il est point fixe de $\ \sigma$. Dans le cas contraire, il existe un et un seul i tel que $x\in \mathrm {supp} (\sigma _{i})$. Puisque x n'appartient pas aux supports de $\sigma _{i+1},\ldots ,\sigma _{n}$, nous avons

$\sigma _{i+1}\ldots \sigma _{n}(x)=x$,

d'où, en appliquant $\sigma _{i}$ aux deux membres,

$\sigma _{i}\sigma _{i+1}\ldots \sigma _{n}(x)=\sigma _{i}(x)$.

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

Cycles

Définition

Cycles

Soit E un ensemble fini. On dit qu'une permutation $\gamma$ de E est un cycle si l'opération du groupe $<\gamma >$ 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.

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

Début d'un lemme

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

Fin du lemme

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 }\gamma _{\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 $\ \gamma _{\omega _{1}},\gamma _{\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.

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 $\gamma ^{s}(x)=x$, par exemple l’ordre de $\ \gamma$. Désignons par $\ s_{x}$ le plus petit des nombres naturels s > 0 tels que $\gamma ^{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=\gamma ^{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}=\mathrm {Card} (\Omega )$, donc $s_{x}$ est le nombre k de l'énoncé et, en particulier, est indépendant de x. Donc, pour tout $x\in \Omega$, $\gamma ^{k}(x)=x$. Puisque $\gamma$ coïncide avec l'identité hors de $\ \Omega$, nous avons donc $\gamma ^{k}=\mathrm {id} _{E}$, donc k est supérieur ou égal à l’ordre de $\gamma$. D'autre part, il est clair que, par minimalité de $\ s_{x}$ dans l’ensemble des s > 0 tels que $\gamma ^{s}(x)=x$, $\ s_{x}$, c'est-à-dire k, est inférieur ou égal à l’ordre de $\gamma$. (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 $\gamma$ 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);

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.

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.

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 $\Gamma _{f}$ est un isomorphisme, $\Gamma _{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.

Transpositions

Définition

Une permutation d'un ensemble E est dite transposition si c’est un cycle de longueur 2. Autrement dit, une permutation $\tau$ de E est une transposition si et seulement s'il existe deux éléments distincts a, b de E tels que $\tau (a)=b,\tau (b)=a$ et que $\tau$ laisse fixes tous les autres éléments de E.

La transposition $(a\ b)$ est donc l'unique transposition $\in S_{E}$ qui échange a et b.

Début d'un lemme

Lemme

Tout cycle de longueur r est le produit de r - 1 transpositions.

Fin du lemme

Démonstration. On vérifie facilement que le cycle $(a_{1}\ldots a_{r})$ est égal à

$(a_{1}\ a_{r})(a_{1}\ a_{r-1})\ldots (a_{1}\ a_{2})$.

Début d’un théorème

Théorème

Toute permutation d'un ensemble fini est un produit de transpositions.

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 $\sigma$ une permutation d'un ensemble fini E ; nous allons prouver que $\sigma$ est décomposable en transpositions, en raisonnant par récurrence sur le cardinal du support de $\sigma$. Si ce cardinal est nul, $\sigma$ est la permutation identique et est donc le produit de la famille vide de transpositions. Sinon, le support de $\sigma$ n’est pas vide. Choisissons un élément $a$ de ce support et posons $b=\sigma (a)$. Comme déjà noté, $b$ appartient aussi au support de $\sigma$. Tout point fixe de $\sigma$ est distinct de $a$ et de $b$, donc est point fixe de $(a\ b)\circ \sigma$ ; de plus, il est clair que $a$ est également point fixe de $(a\ b)\circ \sigma$. Donc $(a\ b)\circ \sigma$ a strictement plus de points fixes que $\sigma$, autrement dit, le support de $(a\ b)\circ \sigma$ a strictement moins d'éléments que celui de $\sigma$. Par hypothèse de récurrence, $(a\ b)\circ \sigma$ est décomposable en produit de permutations, donc $\sigma$, qui peut s'écrire $(a\ b)\circ ((a\ b)\circ \sigma )$, 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 $\{1,-1\}$ 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 $(-1)^{u}=1$ équivaut à ce que u soit pair ; pour tous entiers rationnels u et v, la condition $(-1)^{u}=(-1)^{v}$ é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 $\{1,-1\}$, il s'agira du groupe qu'on vient de considérer, qui peut aussi être défini comme le sous-groupe $\{1,-1\}$ du groupe multiplicatif des nombres rationnels non nuls.

Début d’un théorème

Théorème

Soit E un ensemble fini. Il existe un et un seul homomorphisme du groupe $S_{E}$ dans le groupe $\{1,-1\}$ qui applique toute transposition sur -1. Dans différentes décompositions d'une même permutation en produit de transpositions, le nombre de facteurs a toujours la même parité.

Fin du théorème

Supposons d’abord $E=\{1,2,\ldots ,n\}$ pour un certain nombre naturel n. Pour toute permutation $\sigma$ de $\{1,2,\ldots ,n\}$, nous dirons qu'une paire d'éléments de $\{1,2,\ldots ,n\}$ est une inversion de $\sigma$ si, i désignant le plus petit élément de cette paire et j le plus grand, $\sigma _{i}>\sigma _{j}$. Soient $\sigma$ et $\tau$ deux permutations de $\{1,2,\ldots ,n\}$ et $\{i,j\}$ une paire d'éléments de $\{1,2,\ldots ,n\}$. Il est clair que $\{i,j\}$ est une inversion de $\sigma \circ \tau$ si et seulement si une des deux conditions suivantes est satisfaite :

1° $\{i,j\}$ est une inversion de $\tau$ et $\{\tau (i,\tau (j))\}$ n’est pas une inversion de $\sigma$ ;

2° $\{i,j\}$ n’est pas une inversion de $\tau$ et $\{\tau (i,\tau (j))\}$ est une inversion de $\sigma$.

Nous allons définir un homomorphisme de $S_{E}$ dans le groupe $\{1,-1\}$.

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

$\nu _{\sigma \circ \tau }(P)=\nu _{\sigma }(\tau (P))\nu _{\tau }(P)$,

où $\tau (P)$ désigne la paire formée par les images par $\tau$ des deux éléments de P.

En prenant le produit sur l’ensemble ${\mathcal {P}}$ des paires d'éléments de P, nous trouvons

$\prod _{P\in {\mathcal {P}}}\nu _{\sigma \circ \tau }(P)=\prod _{P\in {\mathcal {P}}}\nu _{\sigma }(\tau (P))\prod _{P\in {\mathcal {P}}}\nu _{\tau }(P)$.

L'application $P\mapsto \tau (P)$ est une permutation de l'index ${\mathcal {P}}$, donc le produit $\prod _{P\in {\mathcal {P}}}\nu _{\sigma }(\tau (P))$ peut s'écrire $\prod _{P\in {\mathcal {P}}}\nu _{\sigma }(P)$, d'où

$\prod _{P\in {\mathcal {P}}}\nu _{\sigma \circ \tau }(P)=\prod _{P\in {\mathcal {P}}}\nu _{\sigma }(P)\prod _{P\in {\mathcal {P}}}\nu _{\tau }(P)$.

Ceci montre que l'application

$\sigma \mapsto \prod _{P\in {\mathcal {P}}}\nu _{\sigma }(P)$

est un homomorphisme de $S_{n}$ dans $\{1,-1\}$.

Il est clair que cet homomorphisme peut s'écrire

$\sigma \mapsto (-1)^{\mathrm {inv} (\sigma )}$,

où $\mathrm {inv} (\sigma )$ désigne le nombre d'inversions de $\sigma$. 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 $\{a,i\}$ avec $a<i<b$, et les paires $\{i,b\}$, avec $a<i<b$. Le nombre des inversions de (a b) est donc $1+2(b-1-a)$, qui est bien impair.

Nous avons donc prouvé qu’il existe un homomorphisme de $S_{n}$ dans $\{1,-1\}$ qui applique toute transposition sur -1. Un tel homomorphisme est unique, puisque les transpositions engendrent $S_{n}$. Pour toute permutation $\sigma \in S_{n}$, désignons par $\epsilon (\sigma )$ l'image de $\sigma$ 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 $\{1,2,\ldots ,n\}$. Nous avons vu que l'application

$\Gamma _{f}:S_{E}\to S_{n}:\sigma \mapsto f\circ \sigma \circ f^{-1}$

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é $\epsilon \circ \Gamma _{f}$ est donc un homomorphisme de $S_{E}$ dans $\{1,-1\}$ qui applique toute transposition sur –1. Ici encore, puisque les transpositions engendrent $S_{E}$, un tel homomorphisme est unique. Nous désignerons encore par $\epsilon (\sigma )$ l'image de $\sigma$ par cet homomorphisme.

Si une permutation $\sigma$ de E peut s'écrire

$\sigma =\tau _{1}\circ \ldots \circ \tau _{r1}$

et

$\sigma =\varphi _{1}\circ \ldots \circ \varphi _{s}$,

les $\tau _{i}$ et les $\varphi _{j}$ étant des transpositions, le passage aux valeurs par $\epsilon$ donne $(-1)^{r}=(-1)^{s}$, donc r et s ont même parité.

Remarque

L'essentiel de la démonstration revient à dire que si $\sigma$ et$\tau$ sont des permutations de $\{1,2,\ldots ,n\}$, le nombre d'inversions de $\sigma \circ \tau$ est congru modulo 2 à la somme du nombre d'inversions de $\sigma$ et du nombre d'inversions de $\tau$. On trouvera dans les exercices une relation plus explicite entre ces trois nombres d'inversions.

Définitions

Pour toute permutation $\sigma$ d'un ensemble fini E, on appelle signature de $\sigma$ et on note $\epsilon (\sigma )$ la valeur de $\sigma$ par l'unique homomorphisme de $S_{E}$ dans $\{1,-1\}$ qui applique toutes les transpositions sur –1. Une permutation de E est dite paire si sa signature est 1 et impaire dans le cas contraire.

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 $\sigma$ est un élément d'ordre impair du groupe $S_{E}$, c’est une permutation paire ; en effet, puisque $\epsilon$ définit un homomorphisme de $S_{E}$ dans $\{1,-1\}$, l’ordre de $\epsilon (\sigma )$ divise celui de $\sigma$ et est donc impair ; or le seul élément d'ordre impair dans $\{1,-1\}$ est 1, donc $\epsilon (\sigma )=1$, donc $\sigma$ est une permutation paire.

La converse n’est pas vraie : un élément d'ordre pair du groupe $S_{E}$ 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 $(a\ b)\ (c\ d)$ de E a pour ordre le ppcm des ordres de $(a\ b)$ et de $(c\ d)$, 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 $\epsilon (\sigma )$, il n’est pas nécessaire de faire un long relevé d'inversions. Tout d’abord, si on connaît une décomposition de $\sigma$ en produit de transpositions, $\epsilon (\sigma )$ 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 $\sigma$ en produit de cycles à supports disjoints : la signature de $\sigma$ est le produit des signatures de ces cycles, et, d’après un résultat précédent, la signature d'un cycle $\gamma$ est $(-1)^{l(\gamma )-1}$, où $l(\gamma )$ désigne la longueur de $\gamma$. Il est clair qu'on peut même se contenter de connaître les cardinaux des $\langle \sigma \rangle$-orbites. Enfin, si $\Omega ^{\prime }$ désigne l’ensemble des $\langle \sigma \rangle$-orbites non ponctuelles,

$\sum _{\omega \in \Omega ^{\prime }}(\mathrm {Card} (\omega )-1)$ = $\sum _{\omega \in \Omega }(\mathrm {Card} (\omega )-1)$,

où $\Omega$ désigne l’ensemble de toutes les orbites, y compris les orbites ponctuelles ; le second membre est égal à n – t, où n = Card(E) et où t est le nombre des $<\sigma >$-orbites, y compris les $\langle \sigma \rangle$-orbites ponctuelles. On a donc

$\epsilon (\sigma )=(-1)^{n-t}$.

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