CommeUnJeu · L1 MPSI

Groupe symétrique

⌚ ~43 min ▢ 5 blocs ✓ 17 exercices ➣ Prérequis : Structures algébriques usuelles

Pourquoi ce chapitre

Le chapitre Structures algébriques usuelles a introduit $\mathfrak{S}_n$ comme l'exemple courant de groupe non abélien. Nous étudions à présent la structure de ce groupe : comment décomposer toute permutation en briques élémentaires (cycles, puis transpositions), et comment lui associer un signe $\pm 1$ --- la signature --- qui capture la parité. La signature est l'invariant clé pour la construction des déterminants au chapitre suivant ; elle intervient en combinatoire, en probabilités et en géométrie chaque fois qu'un argument de parité est nécessaire.
Le chapitre comporte deux courtes sections : (a) généralités sur $\mathfrak{S}_n$ (cycles, transpositions, décomposition en cycles --- dont la preuve est admise), et (b) le morphisme signature (dont la preuve d'existence est admise).

Conventions

Tout au long de ce chapitre, nous adoptons les conventions suivantes, fixées une fois pour toutes.

Composition des permutations (de droite à gauche). Pour $\sigma, \tau \in \mathfrak{S}_n$, le produit $\sigma \tau$ désigne la composée $\sigma \circ \tau$. Autrement dit, $(\sigma \tau)(x) = \sigma(\tau(x))$ pour tout $x$ --- c'est-à-dire $\tau$ agit d'abord, puis $\sigma$.
Identité. L'élément neutre de $\mathfrak{S}_n$ est l'application identité de $\{1, \dots, n\}$, notée $\operatorname{id}$.
Notation des cycles. Les cycles s'écrivent avec une espace fine entre les entrées : $(a_1\ a_2\ \dots\ a_p)$. Nous n'utilisons jamais de virgule à l'intérieur de la notation cyclique dans ce chapitre.
Cadre. Sauf mention contraire, $n \in \mathbb{N}^*$ et nous travaillons dans $\mathfrak{S}_n$.

Ces conventions sont essentielles : toutes les formules sur les cycles et la signature dépendent du sens droite-à-gauche de la composition.

I Généralités sur $\mathfrak{S}_n$

I.1 Le groupe symétrique $\mathfrak{S}_n$

Le groupe symétrique est le groupe des bijections de $\{1, \dots, n\}$ dans lui-même, muni de la composition. On a déjà vu dans Structures algébriques usuelles qu'il est non abélien pour $n \geq 3$ et de cardinal $n!$. On rappelle ici sa définition et on introduit une notation compacte (la notation matricielle à deux lignes) pour décrire une permutation par la liste de ses valeurs.

Définition — Groupe symétrique sur n lettres

Pour $n \in \mathbb{N}^*$, le groupe symétrique sur $n$ lettres est l'ensemble $$ \mathfrak{S}_n = \{\sigma : \{1, \dots, n\} \to \{1, \dots, n\} \mid \sigma \text{ est une bijection}\} $$ muni de la composition $\circ$. Les éléments de $\mathfrak{S}_n$ sont appelés permutations. Le neutre est $\operatorname{id}$ et l'inverse de $\sigma$ est l'application réciproque $\sigma^{-1}$. On note $\sigma \tau$ pour $\sigma \circ \tau$ (rappel : $\tau$ agit d'abord).

Définition — Notation matricielle

Une permutation $\sigma \in \mathfrak{S}_n$ s'écrit en notation matricielle sur deux lignes (sans lien avec le calcul matriciel --- il s'agit simplement d'une liste compacte de valeurs) : $$ \sigma = \begin{pmatrix} 1 & 2 & \cdots & n \\ \sigma(1) & \sigma(2) & \cdots & \sigma(n) \end{pmatrix}. $$ La première ligne donne les antécédents, la seconde leurs images.

Exemple — Les six éléments de $\mathfrak{S}_3$

Le groupe $\mathfrak{S}_3$ comporte $3! = 6$ éléments : $$ \operatorname{id} = \begin{pmatrix} 1 & 2 & 3 \\ 1 & 2 & 3 \end{pmatrix}, \quad \begin{pmatrix} 1 & 2 & 3 \\ 2 & 1 & 3 \end{pmatrix}, \quad \begin{pmatrix} 1 & 2 & 3 \\ 3 & 2 & 1 \end{pmatrix}, \quad \begin{pmatrix} 1 & 2 & 3 \\ 1 & 3 & 2 \end{pmatrix}, $$ $$ \begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix}, \quad \begin{pmatrix} 1 & 2 & 3 \\ 3 & 1 & 2 \end{pmatrix}. $$ La première est l'identité ; les trois suivantes échangent deux entrées (transpositions) ; les deux dernières effectuent une rotation circulaire des trois entrées (3-cycles).

Exemple — Non-commutativité dans $\mathfrak{S}_3$

La convention droite-à-gauche est essentielle pour calculer correctement les produits. Deux produits simples dans $\mathfrak{S}_3$ illustrent le caractère non abélien du groupe : $$ (1\ 2)(2\ 3) = (1\ 2\ 3), \qquad (2\ 3)(1\ 2) = (1\ 3\ 2). $$ Vérification du premier : en appliquant $(2\ 3)$ puis $(1\ 2)$ à chaque entrée, $$ 1 \xmapsto{(2\ 3)} 1 \xmapsto{(1\ 2)} 2, \quad 2 \xmapsto{(2\ 3)} 3 \xmapsto{(1\ 2)} 3, \quad 3 \xmapsto{(2\ 3)} 2 \xmapsto{(1\ 2)} 1. $$ Donc $(1\ 2)(2\ 3)$ envoie $1 \to 2$, $2 \to 3$, $3 \to 1$ --- soit $(1\ 2\ 3)$. Le second produit est similaire ; les deux résultats diffèrent, donc $(1\ 2)$ et $(2\ 3)$ ne commutent pas.

Exemple — Calcul en notation matricielle

Soit $\sigma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 3 & 1 & 5 & 2 & 4 \end{pmatrix} \in \mathfrak{S}_5$. Alors $\sigma(3) = 5$, et :

$\sigma^{-1} = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 2 & 4 & 1 & 5 & 3 \end{pmatrix}$ (on lit la matrice du bas vers le haut) ;
$\sigma \circ \sigma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 5 & 3 & 4 & 1 & 2 \end{pmatrix}$ (appliquer $\sigma$ deux fois : $1 \to 3 \to 5$, $2 \to 1 \to 3$, etc.).

Proposition — Cardinal de $\mathfrak{S}_n$

Pour tout $n \in \mathbb{N}^*$, $|\mathfrak{S}_n| = n!$.

Preuve

Une permutation $\sigma \in \mathfrak{S}_n$ est déterminée par le choix de $\sigma(1), \sigma(2), \dots, \sigma(n)$. Comme $\sigma$ est une bijection, ces valeurs sont des éléments deux à deux distincts de $\{1, \dots, n\}$. Dénombrement :

$\sigma(1)$ : $n$ choix ;
$\sigma(2)$ : $n - 1$ choix (tout élément différent de $\sigma(1)$) ;
$\dots$ ;
$\sigma(n)$ : $1$ choix restant.

Par le principe multiplicatif, $|\mathfrak{S}_n| = n \cdot (n-1) \cdots 1 = n!$.

Compétences à pratiquer

Calculer dans $\mathfrak{S}_n$

I.2 Cycles$\virgule$ support$\virgule$ transpositions

La richesse de $\mathfrak{S}_n$ tient à la manière dont chaque permutation se construit à partir de briques simples, les cycles. Un cycle « fait tourner » un petit sous-ensemble de $\{1, \dots, n\}$ et fixe tout le reste. Les cycles les plus simples, à deux éléments, sont les transpositions : elles échangent deux éléments. Cycles et transpositions sont les briques élémentaires de la suite du chapitre.

Définition — Support d'une permutation

Le support de $\sigma \in \mathfrak{S}_n$ est l'ensemble $$ \operatorname{supp}(\sigma) = \{x \in \{1, \dots, n\} \mid \sigma(x) \neq x\}. $$ Le complémentaire du support est l'ensemble des points fixes de $\sigma$.

Définition — Cycle de longueur $p$

Soient $p \geq 2$ et $a_1, a_2, \dots, a_p \in \{1, \dots, n\}$ deux à deux distincts. Le $p$-cycle $(a_1\ a_2\ \dots\ a_p)$ est la permutation $\sigma \in \mathfrak{S}_n$ définie par : $$ \sigma(a_1) = a_2, \quad \sigma(a_2) = a_3, \quad \dots, \quad \sigma(a_{p-1}) = a_p, \quad \sigma(a_p) = a_1, $$ et $\sigma(x) = x$ pour tout $x \notin \{a_1, \dots, a_p\}$. L'entier $p$ est la longueur du cycle. Son support est $\{a_1, \dots, a_p\}$.

Définition — Transposition

Une transposition est un $2$-cycle, c'est-à-dire une permutation de la forme $(a\ b)$ avec $a, b \in \{1, \dots, n\}$ distincts. Une telle permutation échange $a$ et $b$ et fixe tout autre élément.

Exemple — Le 3-cycle $(1\ 3\ 5)$ dans $\mathfrak{S}_5$

Le cycle $(1\ 3\ 5) \in \mathfrak{S}_5$ envoie $1 \to 3$, $3 \to 5$, $5 \to 1$, et fixe $2$ et $4$. En notation matricielle : $$ (1\ 3\ 5) = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 3 & 2 & 5 & 4 & 1 \end{pmatrix}. $$ Son support est $\{1, 3, 5\}$ ; ses points fixes sont $2$ et $4$.

Exemple — La transposition $(2\ 4)$ est involutive

La transposition $(2\ 4) \in \mathfrak{S}_5$ échange $2$ et $4$ et fixe $1, 3, 5$. En l'appliquant deux fois : $$ \begin{aligned} (2\ 4)\bigl((2\ 4)(2)\bigr) &= (2\ 4)(4) = 2, \\ (2\ 4)\bigl((2\ 4)(4)\bigr) &= (2\ 4)(2) = 4. \end{aligned} $$ Et tout autre élément est fixé par les deux. Donc $(2\ 4) \circ (2\ 4) = \operatorname{id}$.

Proposition — Invariance par rotation cyclique et inverse d'un cycle

Soient $p \geq 2$ et $a_1, \dots, a_p \in \{1, \dots, n\}$ deux à deux distincts.

Rotation cyclique : le $p$-cycle est invariant par rotation cyclique de ses entrées : $$ (a_1\ a_2\ \dots\ a_p) = (a_2\ a_3\ \dots\ a_p\ a_1) = \dots = (a_p\ a_1\ \dots\ a_{p-1}). $$
Inverse : l'inverse d'un cycle renverse l'ordre des entrées (après avoir fixé la première) : $$ (a_1\ a_2\ \dots\ a_p)^{-1} = (a_1\ a_p\ a_{p-1}\ \dots\ a_2). $$

Preuve

Rotation cyclique. Le $p$-cycle $\sigma = (a_1\ a_2\ \dots\ a_p)$ agit par $a_i \mapsto a_{i+1}$ pour $1 \leq i \leq p-1$ et $a_p \mapsto a_1$, et fixe tout autre élément. Le cycle $(a_2\ a_3\ \dots\ a_p\ a_1)$ agit de la même façon : $a_2 \mapsto a_3, \dots, a_{p-1} \mapsto a_p, a_p \mapsto a_1, a_1 \mapsto a_2$, et fixe tout autre élément. Les deux sont donc égaux comme fonctions. Le même argument vaut pour toute rotation cyclique.
Inverse. Posons $\tau = (a_1\ a_p\ a_{p-1}\ \dots\ a_2)$. Alors $\tau$ agit par $a_1 \mapsto a_p \mapsto a_{p-1} \mapsto \dots \mapsto a_2 \mapsto a_1$. Composons avec $\sigma$ : $$ (\sigma \circ \tau)(a_1) = \sigma(a_p) = a_1, \quad (\sigma \circ \tau)(a_p) = \sigma(a_{p-1}) = a_p, \quad \dots, \quad (\sigma \circ \tau)(a_2) = \sigma(a_1) = a_2. $$ Et tout $x$ hors du support est fixé. Donc $\sigma \circ \tau = \operatorname{id}$. La même vérification donne $\tau \circ \sigma = \operatorname{id}$, donc $\tau = \sigma^{-1}$.

Proposition — Les transpositions sont involutives

Toute transposition $\tau = (a\ b)$ vérifie $\tau^{-1} = \tau$, c'est-à-dire $\tau \circ \tau = \operatorname{id}$.

Preuve

On applique $(a\ b)$ deux fois : $a \mapsto b \mapsto a$ et $b \mapsto a \mapsto b$. Tout autre élément est fixé par $(a\ b)$. Donc $(a\ b) \circ (a\ b)$ agit comme $\operatorname{id}$.

Exemple — Trois notations pour le même cycle

Par la règle de rotation cyclique : $$ (1\ 3\ 5) = (3\ 5\ 1) = (5\ 1\ 3). $$ Par la règle d'inverse : $$ (1\ 3\ 5)^{-1} = (1\ 5\ 3). $$ Vérification sur chaque élément du support : $(1\ 3\ 5)(1\ 5\ 3)(1) = (1\ 3\ 5)(5) = 1$, $(1\ 3\ 5)(1\ 5\ 3)(3) = (1\ 3\ 5)(1) = 3$, $(1\ 3\ 5)(1\ 5\ 3)(5) = (1\ 3\ 5)(3) = 5$. La composée fixe donc $1$, $3$, $5$ (et trivialement $2$, $4$). $\checkmark$

Proposition — Nombre de transpositions dans $\mathfrak{S}_n$

Le nombre de transpositions dans $\mathfrak{S}_n$ vaut $$ \binom{n}{2} = \frac{n(n-1)}{2}. $$

Preuve

Une transposition est déterminée par une paire non ordonnée $\{a, b\} \subset \{1, \dots, n\}$ avec $a \neq b$ --- noter que $(a\ b) = (b\ a)$, donc l'ordre est sans importance. Le nombre de telles paires est $\binom{n}{2}$.

Exemple — Comptage des transpositions pour de petits $\mathfrak{S}_n$

Dans $\mathfrak{S}_3$ : $\binom{3}{2} = 3$ transpositions, à savoir $(1\ 2)$, $(1\ 3)$, $(2\ 3)$.
Dans $\mathfrak{S}_4$ : $\binom{4}{2} = 6$ transpositions.
Dans $\mathfrak{S}_5$ : $\binom{5}{2} = 10$ transpositions.

Compétences à pratiquer

Manipuler cycles et transpositions

I.3 Décomposition en cycles disjoints

Deux cycles à supports disjoints commutent (ils agissent sur des parties différentes de $\{1, \dots, n\}$). Le résultat fondamental de cette sous-section est que toute permutation, hormis l'identité, se factorise de façon unique comme produit de cycles à supports deux à deux disjoints. La démonstration est admise par le programme ; on se concentre sur l'utilisation de cette décomposition plutôt que sur sa preuve.

Proposition — Décomposition en cycles disjoints

Toute $\sigma \in \mathfrak{S}_n$ avec $\sigma \neq \operatorname{id}$ se factorise comme produit $$ \sigma = c_1 c_2 \cdots c_k $$ de cycles $c_1, \dots, c_k$ de longueur $\geq 2$ à supports deux à deux disjoints. La décomposition est unique à l'ordre des facteurs près (les cycles disjoints commutent) et à rotation cyclique près à l'intérieur de chaque cycle. Les points fixes sont en général omis de la notation.
Les cycles à supports disjoints commutent : si $c, c'$ ont des supports disjoints, alors $c c' = c' c$.
Par convention, la permutation identité $\operatorname{id}$ est le produit vide de cycles disjoints (elle n'a aucun cycle de longueur $\geq 2$ dans sa décomposition ; tout élément est un point fixe).

Preuve

Admise ; une idée de démonstration est esquissée dans le bloc Texte ci-dessous.

Idée de la démonstration

Pour $\sigma \in \mathfrak{S}_n$, on définit l'orbite de $x$ par $\{x, \sigma(x), \sigma^2(x), \dots\}$. Les orbites partitionnent $\{1, \dots, n\}$. Chaque orbite de taille $\geq 2$ donne un cycle (lu en suivant $\sigma$) ; les orbites de taille $1$ sont les points fixes. La disjonction des supports découle de la disjonction des orbites. L'unicité résulte du fait que les orbites sont déterminées par $\sigma$.

Méthode — Décomposer une permutation en cycles disjoints

Étant donné $\sigma \in \mathfrak{S}_n$ en notation matricielle :

Étape 1. Choisir le plus petit $a \in \{1, \dots, n\}$ tel que $\sigma(a) \neq a$.
Étape 2. Suivre l'orbite : $a \to \sigma(a) \to \sigma^2(a) \to \dots$ jusqu'à retomber sur $a$. Cela donne le premier cycle $(a\ \sigma(a)\ \sigma^2(a)\ \dots)$.
Étape 3. Choisir le plus petit élément non utilisé $b$ avec $\sigma(b) \neq b$ (en sautant les points fixes). Répéter l'étape 2 à partir de $b$ pour obtenir le cycle suivant.
Étape 4. Itérer jusqu'à ce que tout élément non fixé soit utilisé. Le produit des cycles obtenus, dans n'importe quel ordre, vaut $\sigma$.

Exemple — Décomposition d'une permutation dans $\mathfrak{S}_7$

Décomposer $\sigma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 3 & 5 & 7 & 4 & 2 & 6 & 1 \end{pmatrix}$ en cycles disjoints.

Correction

On applique la méthode.

Étape 1. Le plus petit élément non fixé est $1$ (car $\sigma(1) = 3 \neq 1$).
Étape 2. Orbite de $1$ : $1 \to 3 \to 7 \to 1$. Premier cycle : $(1\ 3\ 7)$.
Étape 3. Plus petit non utilisé non fixé : $2$ (car $\sigma(2) = 5 \neq 2$). Orbite : $2 \to 5 \to 2$. Deuxième cycle : $(2\ 5)$.
Étape 4. Éléments restants : $4$ et $6$ sont fixés par $\sigma$ ($\sigma(4) = 4$, $\sigma(6) = 6$). Tous les non-fixés sont utilisés.

Conclusion : $\sigma = (1\ 3\ 7)(2\ 5)$, avec $4$ et $6$ comme points fixes (omis de la notation).

Exemple — De la forme cyclique à la matrice

Retrouver la forme matricielle de $\sigma = (1\ 2\ 3)(4\ 5) \in \mathfrak{S}_5$.

Correction

Les deux cycles ont des supports disjoints $\{1, 2, 3\}$ et $\{4, 5\}$, donc commutent. On applique chacun : $$ 1 \to 2, \quad 2 \to 3, \quad 3 \to 1, \quad 4 \to 5, \quad 5 \to 4. $$ Forme matricielle : $\sigma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 2 & 3 & 1 & 5 & 4 \end{pmatrix}$.

Proposition — Ordre d'un cycle

Un cycle $c$ de longueur $p$ a pour ordre $p$ dans $\mathfrak{S}_n$ : $c^p = \operatorname{id}$ et $p$ est le plus petit entier strictement positif vérifiant cette propriété.

Preuve

On écrit $c = (a_1\ a_2\ \dots\ a_p)$. Pour tout $a_i$ du support et tout $k \in \mathbb{N}$, $$ c^k(a_i) = a_{((i - 1 + k) \bmod p) + 1}, $$ la réduction modulaire étant prise dans le système de résidus $\{0, 1, \dots, p - 1\}$. Donc $c^k(a_i) = a_i$ ssi $(i - 1 + k) \equiv (i - 1) \pmod p$ ssi $p \mid k$. Pour $x$ hors du support, $c^k(x) = x$ trivialement. Donc $c^k = \operatorname{id}$ ssi $p \mid k$. Le plus petit tel $k > 0$ est $p$.

Proposition — Ordre d'une permutation via la décomposition en cycles

Soit $\sigma \in \mathfrak{S}_n$ de décomposition en cycles disjoints $\sigma = c_1 c_2 \cdots c_k$, où $c_i$ est de longueur $p_i \geq 2$. Alors $$ \operatorname{ord}(\sigma) = \operatorname{ppcm}(p_1, p_2, \dots, p_k). $$

Preuve

En utilisant la commutativité admise des cycles disjoints, les cycles $c_1, \dots, c_k$ commutent deux à deux, donc pour tout $m \in \mathbb{N}$, $$ \sigma^m = c_1^m c_2^m \cdots c_k^m. $$ Puis, pour $m \in \mathbb{N}^*$ : $$ \begin{aligned} \sigma^m = \operatorname{id} &\iff c_1^m c_2^m \cdots c_k^m = \operatorname{id} && \text{(puissance de $\sigma$)} \\ &\iff c_i^m = \operatorname{id} \text{ pour tout } i && \text{(supports disjoints)} \\ &\iff p_i \mid m \text{ pour tout } i && \text{(ordre d'un cycle)} \\ &\iff \operatorname{ppcm}(p_1, \dots, p_k) \mid m && \text{(définition du ppcm)}. \end{aligned} $$ Le plus petit tel $m > 0$ est $\operatorname{ppcm}(p_1, \dots, p_k)$.

Exemple — Ordre via le ppcm

La permutation $\sigma = (1\ 3\ 7)(2\ 5) \in \mathfrak{S}_7$ a pour longueurs de cycle $3$ et $2$, donc $\operatorname{ord}(\sigma) = \operatorname{ppcm}(3, 2) = 6$.
La permutation $\rho = (1\ 2\ 3\ 4)(5\ 6\ 7) \in \mathfrak{S}_7$ a pour longueurs de cycle $4$ et $3$, donc $\operatorname{ord}(\rho) = \operatorname{ppcm}(4, 3) = 12$.

Compétences à pratiquer

Décomposer en cycles disjoints

II Signature

II.1 Décomposition en transpositions

Au-delà des cycles, les briques vraiment élémentaires de $\mathfrak{S}_n$ sont les transpositions : toute permutation s'écrit comme produit de transpositions. La décomposition n'est pas unique --- des produits différents peuvent donner la même permutation. On verra dans la sous-section suivante que, malgré cette non-unicité, la parité du nombre de transpositions est un invariant de la permutation. Cette parité est capturée par la signature.

Proposition — Un cycle comme produit de transpositions

Tout cycle est un produit de transpositions. Plus précisément, pour $p \geq 2$ et $a_1, \dots, a_p$ deux à deux distincts, $$ (a_1\ a_2\ \dots\ a_p) = (a_1\ a_2)(a_2\ a_3) \cdots (a_{p-1}\ a_p), $$ produit de $p - 1$ transpositions (avec la convention de composition droite-à-gauche).

Preuve

On applique le membre de droite à chaque $a_i$, en se rappelant que la transposition la plus à droite $(a_{p-1}\ a_p)$ agit la première.

Pour $a_p$ : $(a_{p-1}\ a_p)(a_p) = a_{p-1}$. Puis $(a_{p-2}\ a_{p-1})(a_{p-1}) = a_{p-2}$, et ainsi de suite, finalement $(a_1\ a_2)(a_2) = a_1$. Résultat net : $a_p \mapsto a_1$.
Pour $a_{p-1}$ : $(a_{p-1}\ a_p)(a_{p-1}) = a_p$. La transposition suivante $(a_{p-2}\ a_{p-1})$ ne déplace pas $a_p$. Les transpositions suivantes $(a_i\ a_{i+1})$ pour $i < p - 1$ fixent aussi $a_p$. Résultat net : $a_{p-1} \mapsto a_p$.
Pour $a_i$ avec $1 \leq i \leq p - 2$ : seule $(a_i\ a_{i+1})$ déplace $a_i$ (elle envoie $a_i$ sur $a_{i+1}$) ; les transpositions $(a_j\ a_{j+1})$ avec $j < i$ apparaissent à gauche de $(a_i\ a_{i+1})$ dans le produit écrit et s'appliquent donc après, mais elles fixent toutes $a_{i+1}$ (car $a_{i+1} \notin \{a_j, a_{j+1}\}$ lorsque $j < i$). Résultat net : $a_i \mapsto a_{i+1}$.
Pour $x \notin \{a_1, \dots, a_p\}$ : chaque transposition fixe $x$.

C'est exactement l'action de $(a_1\ a_2\ \dots\ a_p)$.

Formule alternative -- remarque

Une autre décomposition du même cycle est également valable : $$ (a_1\ a_2\ \dots\ a_p) = (a_1\ a_p)(a_1\ a_{p-1}) \cdots (a_1\ a_2), $$ toujours avec $p - 1$ transpositions. On adopte la forme de la proposition précédente comme canonique dans ce chapitre ; la forme alternative est parfois plus commode (par exemple lorsqu'on souhaite que toutes les transpositions partagent une lettre commune).

Proposition — $\mathfrak{S}_n$ est engendré par les transpositions

Toute $\sigma \in \mathfrak{S}_n$ est un produit de transpositions.

Preuve

En admettant la décomposition en cycles disjoints de la sous-section précédente, on écrit $\sigma = c_1 c_2 \cdots c_k$ comme produit de cycles. D'après la proposition précédente, chaque cycle $c_i$ est un produit de transpositions. En concaténant les décompositions, $\sigma$ est un produit de transpositions.
Le cas $\sigma = \operatorname{id}$ se traite par la convention que le produit vide vaut $\operatorname{id}$. Lorsque $n \geq 2$, on peut aussi écrire concrètement $\operatorname{id} = (1\ 2)(1\ 2)$.

Attention -- non-unicité

La décomposition d'une permutation en produit de transpositions n'est pas unique. Par exemple, $$ (1\ 2\ 3) = (1\ 2)(2\ 3) = (1\ 3)(1\ 2), $$ deux produits différents de $2$ transpositions donnant le même $3$-cycle. Nous verrons dans la sous-section Signature que, bien que le nombre de facteurs varie, sa parité est invariante.

Exemple — $(1\ 4)(2\ 5)(3\ 6)$ déjà en forme transposée

La permutation $\sigma = (1\ 4)(2\ 5)(3\ 6) \in \mathfrak{S}_6$ est déjà un produit de $3$ transpositions (à supports disjoints, donc qui commutent). Aucune décomposition supplémentaire n'est nécessaire.

Exemple — Décomposer $(1\ 3\ 5)(2\ 4)$ en transpositions

Soit $\sigma = (1\ 3\ 5)(2\ 4) \in \mathfrak{S}_5$. On applique la formule canonique à chaque cycle : $$ (1\ 3\ 5) = (1\ 3)(3\ 5), \qquad (2\ 4) = (2\ 4). $$ Les deux cycles ont des supports disjoints, donc commutent, et on concatène : $$ \sigma = (1\ 3)(3\ 5)(2\ 4), $$ soit un produit de $3$ transpositions au total.

Compétences à pratiquer

Décomposer en transpositions

II.2 Signature

Différentes décompositions en transpositions d'une même permutation peuvent utiliser des nombres de transpositions différents, mais la parité de ce nombre est fixée par la permutation. La signature est l'application $\mathfrak{S}_n \to \{-1, 1\}$ qui vaut $-1$ pour un nombre impair de transpositions et $+1$ pour un nombre pair. Son existence et son unicité --- qui encodent l'invariance de parité --- sont admises par le programme.

Proposition — Existence et unicité de la signature

Il existe un unique morphisme de groupes, noté plus loin $\varepsilon$, $$ \varepsilon : \mathfrak{S}_n \longrightarrow \{-1, 1\} $$ envoyant toute transposition sur $-1$. De manière équivalente : pour toute $\sigma \in \mathfrak{S}_n$ écrite comme produit de transpositions $\sigma = \tau_1 \tau_2 \cdots \tau_p$, la valeur $(-1)^p$ ne dépend que de $\sigma$ --- pas de la décomposition choisie.

Preuve

Admise ; une idée de démonstration est esquissée dans le bloc Texte ci-dessous.

Idée de la démonstration

Existence. On peut vérifier que la formule explicite $$ \varepsilon(\sigma) = \prod_{1 \leq i < j \leq n} \frac{\sigma(j) - \sigma(i)}{j - i} $$ définit une application multiplicative $\mathfrak{S}_n \to \{-1, 1\}$ qui vaut $-1$ sur toute transposition.
Unicité. Tout morphisme $\mathfrak{S}_n \to \{-1, 1\}$ est déterminé par ses valeurs sur les transpositions, puisque toute $\sigma$ est produit de transpositions. Imposer $-1$ sur chaque transposition fixe le morphisme.

Définition — Signature -- permutations paires et impaires

L'unique morphisme ci-dessus est appelé signature et noté $\varepsilon$ : $$ \varepsilon : \mathfrak{S}_n \to \{-1, 1\}. $$ Une permutation $\sigma$ est dite paire si $\varepsilon(\sigma) = 1$, et impaire si $\varepsilon(\sigma) = -1$.

Proposition — Propriétés de base de $\varepsilon$

La signature vérifie, pour tous $\sigma, \sigma' \in \mathfrak{S}_n$ :

$\varepsilon(\operatorname{id}) = 1$ ;
$\varepsilon(\sigma \sigma') = \varepsilon(\sigma) \varepsilon(\sigma')$ (multiplicativité) ;
$\varepsilon(\sigma^{-1}) = \varepsilon(\sigma)$.

Preuve

Les deux premières propriétés découlent immédiatement du fait que $\varepsilon$ est un morphisme de groupes. Pour la troisième : appliquer le morphisme à $\sigma \sigma^{-1} = \operatorname{id}$ donne $\varepsilon(\sigma) \varepsilon(\sigma^{-1}) = 1$. Comme $\varepsilon$ est à valeurs dans $\{-1, 1\}$, chaque élément est son propre inverse dans $\{-1, 1\}$ pour la multiplication, donc $\varepsilon(\sigma^{-1}) = \varepsilon(\sigma)^{-1} = \varepsilon(\sigma)$.

Exemple — Signatures de $\operatorname{id}$ et d'une transposition

Par définition : $\varepsilon(\operatorname{id}) = 1$, et $\varepsilon(\tau) = -1$ pour toute transposition $\tau$. Donc $\operatorname{id}$ est paire et toute transposition est impaire.

Proposition — Signature d'un p-cycle

Pour $p \geq 2$, la signature d'un $p$-cycle vaut $$ \varepsilon\bigl((a_1\ a_2\ \dots\ a_p)\bigr) = (-1)^{p-1}. $$ En particulier, les transpositions ($p = 2$) ont signature $-1$ (cohérent avec la définition), les $3$-cycles sont pairs, les $4$-cycles sont impairs, etc.

Preuve

D'après la formule canonique de la sous-section Décomposition en transpositions ci-dessus, $(a_1\ a_2\ \dots\ a_p) = (a_1\ a_2)(a_2\ a_3) \cdots (a_{p-1}\ a_p)$, soit un produit de $p - 1$ transpositions. Par multiplicativité de $\varepsilon$ et $\varepsilon(\tau) = -1$ pour toute transposition, $$ \varepsilon\bigl((a_1\ a_2\ \dots\ a_p)\bigr) = (-1)^{p-1}. $$

Méthode — Calculer la signature d'une permutation

Deux approches pratiques.

Par décomposition en cycles (souvent la plus rapide). Décomposer $\sigma$ en cycles disjoints de longueurs $p_1, \dots, p_k$. Alors $$ \varepsilon(\sigma) = (-1)^{(p_1 - 1) + (p_2 - 1) + \cdots + (p_k - 1)}. $$
Par décomposition en transpositions. Écrire $\sigma$ comme produit de $p$ transpositions ; alors $\varepsilon(\sigma) = (-1)^p$.

La formule par longueurs ci-dessus suppose des cycles à supports disjoints. Si $\sigma$ est donnée comme produit de cycles dont les supports se recoupent, deux options sont possibles :

re-décomposer $\sigma$ en cycles disjoints, puis appliquer la formule des longueurs (plus lent en général) ;
ou, souvent plus rapide, utiliser directement la multiplicativité de $\varepsilon$ et multiplier les signatures des cycles donnés : $\varepsilon(c_1 c_2 \cdots c_k) = \varepsilon(c_1) \varepsilon(c_2) \cdots \varepsilon(c_k)$, avec chaque $\varepsilon(c_i) = (-1)^{\ell_i - 1}$ pour $c_i$ de longueur $\ell_i$.

L'exemple détaillé ci-dessous illustre les deux --- la re-décomposition donne la même réponse que la multiplicativité.

Exemple — Cas disjoint -- simple

Calculer $\varepsilon(\sigma)$ pour $\sigma = (1\ 3\ 7)(2\ 5) \in \mathfrak{S}_7$.

Correction

Les cycles $(1\ 3\ 7)$ et $(2\ 5)$ ont des supports disjoints $\{1, 3, 7\}$ et $\{2, 5\}$. Longueurs $p_1 = 3$ et $p_2 = 2$. On applique la formule des longueurs : $$ \varepsilon(\sigma) = (-1)^{(3 - 1) + (2 - 1)} = (-1)^{2 + 1} = (-1)^3 = -1. $$ Vérification par transpositions : $\sigma = (1\ 3)(3\ 7)(2\ 5)$ --- trois transpositions --- donc $\varepsilon(\sigma) = (-1)^3 = -1$. $\checkmark$

Exemple — Cas non disjoint -- entièrement détaillé

Calculer la signature de $\sigma = (1\ 5\ 3)(2\ 4\ 6\ 1) \in \mathfrak{S}_6$.

Correction

Étape 1 -- les cycles partagent un élément. Les supports $\{1, 5, 3\}$ et $\{2, 4, 6, 1\}$ partagent $1$ --- les cycles ne sont pas disjoints. La formule des longueurs ne s'applique donc pas directement ; il faut d'abord ré-exprimer $\sigma$ sous forme cyclique disjointe.
Étape 2 -- calculer la matrice en appliquant le facteur de droite d'abord. Suivant $(\sigma\tau)(x) = \sigma(\tau(x))$, le facteur de droite $(2\ 4\ 6\ 1)$ agit d'abord, puis $(1\ 5\ 3)$. On suit chaque $x \in \{1, \dots, 6\}$ à travers les deux : $$ \begin{aligned} 1 &\overset{(2\ 4\ 6\ 1)}{\longmapsto} 2 \overset{(1\ 5\ 3)}{\longmapsto} 2, \\ 2 &\overset{(2\ 4\ 6\ 1)}{\longmapsto} 4 \overset{(1\ 5\ 3)}{\longmapsto} 4, \\ 3 &\overset{(2\ 4\ 6\ 1)}{\longmapsto} 3 \overset{(1\ 5\ 3)}{\longmapsto} 1, \\ 4 &\overset{(2\ 4\ 6\ 1)}{\longmapsto} 6 \overset{(1\ 5\ 3)}{\longmapsto} 6, \\ 5 &\overset{(2\ 4\ 6\ 1)}{\longmapsto} 5 \overset{(1\ 5\ 3)}{\longmapsto} 3, \\ 6 &\overset{(2\ 4\ 6\ 1)}{\longmapsto} 1 \overset{(1\ 5\ 3)}{\longmapsto} 5. \end{aligned} $$ Forme matricielle : $\sigma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 2 & 4 & 1 & 6 & 3 & 5 \end{pmatrix}$.
Étape 3 -- décomposer en cycles disjoints en suivant les orbites. On part de $1$ : $1 \to 2 \to 4 \to 6 \to 5 \to 3 \to 1$. Les six éléments sont dans cette orbite. Donc $$ \sigma = (1\ 2\ 4\ 6\ 5\ 3), $$ un unique $6$-cycle.
Étape 4 -- appliquer la formule des longueurs. $$ \varepsilon(\sigma) = (-1)^{6 - 1} = (-1)^5 = -1. $$ Vérification par la propriété de morphisme. La forme factorisée donne $\varepsilon\bigl((1\ 5\ 3)\bigr) \cdot \varepsilon\bigl((2\ 4\ 6\ 1)\bigr) = (-1)^{3 - 1} \cdot (-1)^{4 - 1} = 1 \cdot (-1) = -1$. $\checkmark$

Exemple — Le 5-cycle est pair

$\varepsilon\bigl((1\ 2\ 3\ 4\ 5)\bigr) = (-1)^{5 - 1} = (-1)^4 = 1$. Donc $(1\ 2\ 3\ 4\ 5)$ est une permutation paire.
Plus généralement, la parité d'un $p$-cycle est opposée à celle de $p$ : $p$ pair donne un cycle impair, $p$ impair donne un cycle pair.

Hors programme: Le groupe alterné $\mathfrak{A}_n$

La signature $\varepsilon : \mathfrak{S}_n \to \{-1, 1\}$ est un morphisme de groupes, donc son noyau $$ \operatorname{Ker} \varepsilon = \{\sigma \in \mathfrak{S}_n \mid \varepsilon(\sigma) = 1\} $$ est un sous-groupe de $\mathfrak{S}_n$. Il est appelé groupe alterné et noté $\mathfrak{A}_n$. Ses éléments sont les permutations paires.
Pour $n \geq 2$, $\varepsilon$ est surjective (toute transposition est envoyée sur $-1$, $\operatorname{id}$ sur $1$), et on peut montrer que la moitié exactement des permutations sont paires --- soit $|\mathfrak{A}_n| = n!/2$. La preuve est laissée en exercice « Pour aller plus loin ».

Compétences à pratiquer

Calculer la signature