Groupe symétrique

1Le groupe symétrique $\mathfrak{S}_{n}$

Définition. Soit $n\in\N^{*}$. On appelle permutation de $\intent{1}{n}$ toute bijection de $\intent{1}{n}$ sur lui-même. L’ensemble de ces permutations, muni de la composition $\circ$, est noté $\mathfrak{S}_{n}$ : c’est le groupe symétrique d’indice $n$.

Propriété — c’est bien un groupe. $(\mathfrak{S}_{n},\circ)$ est un groupe, de neutre $\mathrm{id}$ ; l’inverse de $\sigma$ est sa bijection réciproque $\sigma^{-1}$. C’est le groupe $\mathfrak{S}_{X}$ du chapitre 12 pour $X=\intent{1}{n}$. De plus $\Card \mathfrak{S}_{n}=n!$, et $\mathfrak{S}_{n}$ n’est pas abélien dès que $n\geq3$.

Notation — les deux écritures. Une permutation $\sigma\in\mathfrak{S}_{n}$ est entièrement déterminée par la liste de ses images. On l’écrit en tableau sur deux lignes, la seconde ligne donnant les images de la première :

C’est la notation $\left[\sigma(1),\dots,\sigma(n)\right]$ du chapitre 12, disposée verticalement. La seconde notation, en produit de cycles, est introduite plus bas.

Méthode — composer, inverser. pour $\sigma\circ\tau$, on remplit la seconde ligne case par case : sous $i$ on écrit $\sigma\bigl(\tau(i)\bigr)$, en lisant d’abord $\tau(i)$ dans le tableau de $\tau$, puis son image par $\sigma$. Pour $\sigma^{-1}$, on échange les deux lignes du tableau de $\sigma$, puis on réordonne les colonnes par ordre croissant de la première ligne.

2Cycles et supports

Définition. Le support de $\sigma\in\mathfrak{S}_{n}$ est $\ \operatorname{Supp}(\sigma)=\ens{i\in\intent{1}{n},\ \sigma(i)\neq i}$. Ses éléments sont les points déplacés par $\sigma$ ; les autres sont les points fixes. Ainsi $\operatorname{Supp}(\sigma)=\varnothing\iff\sigma=\mathrm{id}$.

Propriété. Pour $\sigma\in\mathfrak{S}_{n}$ : $\ \sigma\bigl(\operatorname{Supp}(\sigma)\bigr)=\operatorname{Supp}(\sigma)$ et $\operatorname{Supp}\left(\sigma^{-1}\right)=\operatorname{Supp}(\sigma)$.

Définition. Soient $p\geq2$ et $a_{1},\dots,a_{p}$ des éléments deux à deux distincts de $\intent{1}{n}$. Le cycle $\ c=(a_{1}\ a_{2}\ \dots\ a_{p})$ est la permutation définie par

L’entier $p$ est la longueur du cycle ; on dit que $c$ est un $p$-cycle, et $\operatorname{Supp}(c)=\ens{a_{1},\dots,a_{p}}$ est de cardinal $p$. Un $2$-cycle $(a\ b)$ est appelé transposition : il échange $a$ et $b$ et fixe tout le reste.

Propriété — propriétés d’un $p$-cycle. Soit $c=(a_{1}\ \dots\ a_{p})$.

• La notation n’est pas unique : $(a_{1}\ a_{2}\ \dots\ a_{p})=(a_{2}\ \dots\ a_{p}\ a_{1})=\dots$ — il y a exactement $p$ écritures, obtenues par permutation circulaire. On convient d’écrire le plus petit élément en premier.
• $c^{-1}=(a_{p}\ a_{p-1}\ \dots\ a_{1})$. En particulier, pour une transposition, $(a\ b)^{-1}=(a\ b)$ : une transposition est son propre inverse.
• $c^{k}(a_{j})=a_{j+k}$, les indices étant pris modulo $p$ ; par conséquent $c^{p}=\mathrm{id}$ et $c^{k}\neq\mathrm{id}$ pour $1\leq k\leq p-1$.
• Le nombre de $p$-cycles de $\mathfrak{S}_{n}$ est $\dfrac{n!}{(n-p)!\,p}=\dbinom{n}{p}(p-1)!$ ; en particulier $\mathfrak{S}_{n}$ possède $\dbinom{n}{2}=\dfrac{n(n-1)}{2}$ transpositions.

Théorème — cycles à supports disjoints. Si $\sigma,\sigma'\in\mathfrak{S}_{n}$ ont des supports disjoints, alors $\ \sigma\circ\sigma'=\sigma'\circ\sigma$.

Idée de preuve. Soit $i\in\intent{1}{n}$. Si $i\notin\operatorname{Supp}(\sigma)\cup\operatorname{Supp}(\sigma')$, les deux membres valent $i$. Si $i\in\operatorname{Supp}(\sigma)$, alors $\sigma(i)\in\operatorname{Supp}(\sigma)$ donc $i$ et $\sigma(i)$ sont fixes par $\sigma'$, et les deux membres valent $\sigma(i)$ ; on échange les rôles si $i\in\operatorname{Supp}(\sigma')$.

Méthode — décomposer en cycles. partir du plus petit point non encore rencontré, disons $a$, et écrire la suite $a$, $\sigma(a)$, $\sigma^{2}(a)$, … jusqu’à revenir à $a$ : on obtient un cycle. Reprendre avec le plus petit point restant, et s’arrêter quand tous les points ont été parcourus (les points fixes ne donnent pas de facteur). On vérifie le résultat en comptant : la somme des longueurs des cycles obtenus, augmentée du nombre de points fixes, doit valoir $n$.

3Génération par les transpositions

Théorème — toute permutation est produit de transpositions — exigible. Soit $n\geq2$. Toute permutation $\sigma\in\mathfrak{S}_{n}$ s’écrit comme un produit de transpositions ($\mathrm{id}$ étant, par convention, le produit vide, ou encore $(1\ 2)\circ(1\ 2)$). Autrement dit, les transpositions engendrent $\mathfrak{S}_{n}$. Plus précisément, pour tout $p$-cycle,

produit de $p-1$ transpositions.

Idée de preuve (exigible). On vérifie la formule encadrée en évaluant les deux membres en chaque point : pour $j\leq p-1$, le membre de droite envoie $a_{j}$ sur $a_{1}$ par $(a_{1}\ a_{j})$, puis $a_{1}$ sur $a_{j+1}$ par $(a_{1}\ a_{j+1})$, les autres facteurs ne touchant pas aux points atteints ; et $a_{p}\mapsto a_{1}$ par le dernier facteur appliqué. On conclut en combinant cette formule avec la décomposition en cycles à supports disjoints : tout $\sigma\neq\mathrm{id}$ est produit de cycles, donc produit de transpositions.

Remarque. Les transpositions $(1\ k)$, $k\in\intent{2}{n}$, suffisent déjà à engendrer $\mathfrak{S}_{n}$ : il en va de même des transpositions d’éléments consécutifs $(k\ k+1)$. On le démontre en exercice.

4Signature

Théorème — existence et unicité de la signature — admis. Soit $n\geq2$. Il existe un unique morphisme de groupes

On l’appelle la signature. Une permutation est dite paire si $\varepsilon(\sigma)=1$, impaire si $\varepsilon(\sigma)=-1$. La démonstration de l’existence et de l’unicité n’est pas exigible.

Propriété — règles de calcul. Pour $\sigma,\sigma'\in\mathfrak{S}_{n}$ et $k\in\Z$ :

Le deuxième point justifie l’affirmation précédente : si $\sigma$ est produit de $m$ transpositions et de $m'$ transpositions, alors $(-1)^{m}=(-1)^{m'}$, donc $m\equiv m'\ [2]$.

Théorème — signature d’un cycle — exigible. Un $p$-cycle a pour signature $\ \boxed{(-1)^{p-1}}$. En particulier une transposition est impaire, un $3$-cycle est pair.

Idée de preuve (exigible). Le théorème de génération écrit un $p$-cycle comme produit de $p-1$ transpositions ; comme $\varepsilon$ est un morphisme valant $-1$ sur chaque transposition, $\varepsilon\bigl((a_{1}\ \dots\ a_{p})\bigr)=(-1)^{p-1}$.

Propriété — signature par la décomposition en cycles. Si $\sigma=c_{1}\circ\dots\circ c_{r}$ avec $c_{i}$ un $p_{i}$-cycle (supports disjoints), alors

où $m$ désigne le nombre total d’orbites de $\sigma$ (points fixes compris).

Propriété — signature par les inversions. On appelle inversion de $\sigma$ tout couple $(i,j)$ avec $i<j$ et $\sigma(i)>\sigma(j)$, et l’on note $I(\sigma)$ leur nombre. Alors $\ \varepsilon(\sigma)=(-1)^{I(\sigma)}$. Démonstration faite en exercice ; on peut aussi retenir que $0\leq I(\sigma)\leq\frac{n(n-1)}{2}$, la borne supérieure étant atteinte par la seule permutation $i\mapsto n+1-i$.

Méthode — calculer une signature. trois voies, à choisir selon la forme de l’énoncé.

• Si $\sigma$ est donnée en tableau : décomposer en cycles, puis appliquer $\prod(-1)^{p_{i}-1}$. C’est la méthode la plus rapide et la plus sûre.
• Si $\sigma$ est donnée en produit de transpositions ou de cycles quelconques (supports non nécessairement disjoints) : la signature du produit est le produit des signatures — inutile de réduire le produit.
• Pour un petit $n$, ou si l’énoncé y invite : compter les inversions et conclure par $(-1)^{I(\sigma)}$.

Remarque — le groupe alterné. $\varepsilon$ étant un morphisme de groupes, $\operatorname{Ker}\varepsilon=\ens{\sigma\in\mathfrak{S}_{n},\ \varepsilon(\sigma)=1}$ est un sous-groupe de $\mathfrak{S}_{n}$ (chapitre 12) : c’est l’ensemble des permutations paires. Pour $n\geq2$, il est de cardinal $\frac{n!}{2}$ car $\varepsilon$ est surjectif. On le note $\mathfrak{A}_{n}$ et on l’appelle groupe alterné ; cette terminologie ne figure pas au programme, mais l’objet $\operatorname{Ker}\varepsilon$, lui, se manipule sans difficulté avec le cours du chapitre 12.

5Ordre d’une permutation

Définition. Soit $\sigma\in\mathfrak{S}_{n}$. Comme $\mathfrak{S}_{n}$ est fini, les puissances $\sigma^{k}$ ne peuvent être toutes distinctes et il existe $k\geq1$ tel que $\sigma^{k}=\mathrm{id}$. Le plus petit tel entier est appelé ordre de $\sigma$, noté ici $o(\sigma)$. La notion d’ordre d’un élément d’un groupe ne figure pas explicitement au programme ; elle est introduite ici pour ce chapitre, et son calcul est un exercice classique.

Théorème — ordre et longueurs des cycles. Soit $\sigma\neq\mathrm{id}$, de décomposition en cycles à supports disjoints $c_{1}\circ\dots\circ c_{r}$, de longueurs $p_{1},\dots,p_{r}$. Alors

Idée de preuve. Les $c_{i}$ commutent, donc $\sigma^{k}=c_{1}^{k}\circ\dots\circ c_{r}^{k}$ ; les supports restant disjoints, $\sigma^{k}=\mathrm{id}$ équivaut à $c_{i}^{k}=\mathrm{id}$ pour tout $i$, c’est-à-dire à $p_{i}\mid k$ pour tout $i$ (propriété du $p$-cycle). L’ensemble des tels $k$ est donc l’ensemble des multiples communs des $p_{i}$ : son plus petit élément positif est leur ppcm.

6Les petits cas : $\mathfrak{S}_{3}$, $\mathfrak{S}_{4}$, $\mathfrak{S}_{5}$

Propriété. Deux permutations de même type (c’est-à-dire dont les décompositions en cycles à supports disjoints ont les mêmes longueurs) ont même signature et même ordre. Le tableau ci-dessous recense les types et leurs effectifs ; il sert de contrôle systématique, la somme d’une colonne devant valoir $n!$.

Remarque. Dans $\mathfrak{S}_{3}$ : $\mathrm{id}$, les trois transpositions $(1\ 2)$, $(1\ 3)$, $(2\ 3)$, et les deux $3$-cycles $(1\ 2\ 3)$, $(1\ 3\ 2)$ — soit $6=3!$ éléments. Les permutations paires y sont $\mathrm{id}$, $(1\ 2\ 3)$ et $(1\ 3\ 2)$ : $\operatorname{Ker}\varepsilon$ est de cardinal $3=\frac{3!}{2}$, conformément à la remarque précédente. En reprenant les notations du chapitre 12, $\sigma=[2,3,1]$ est le $3$-cycle $(1\ 2\ 3)$ et $\tau=[2,1,3]$ est la transposition $(1\ 2)$.