Groupe symétrique

1. La composée de deux bijections de $E$ est une bijection de $E$ ; la composition est associative ; $\mathrm{id}_E$ est neutre ; la réciproque d'une bijection est une bijection et vérifie $\sigma\sigma^{-1}=\sigma^{-1}\sigma=\mathrm{id}_E$.

2. Une bijection de $[\![1,n]\!]$ dans lui-même est une injection d'un ensemble à $n$ éléments dans un ensemble à $n$ éléments. Il y a $n$ choix pour $\sigma(1)$, puis $n-1$ pour $\sigma(2)$, etc., soit $n!$ permutations.

3. L'exemple ci-dessous fournit, dans $\mathfrak{S}_3$, deux permutations qui ne commutent pas. Pour $n \geqslant 3$, on les prolonge par $\sigma(k)=k$ pour $k \geqslant 4$ ; elles ne commutent toujours pas.

Si $x \in \mathrm{Supp}(\sigma)$, alors $\sigma(x)\neq x$. Par injectivité, $\sigma(\sigma(x))\neq\sigma(x)$, donc $\sigma(x) \in \mathrm{Supp}(\sigma)$. Ainsi $\sigma(\mathrm{Supp}(\sigma)) \subset \mathrm{Supp}(\sigma)$ ; l'égalité vient de ce que $\sigma$ est injective et que l'ensemble est fini.

Enfin $\sigma(x)=x \iff x=\sigma^{-1}(x)$, d'où l'égalité des supports.

1. La permutation $(a_k\ \cdots\ a_1)$ envoie $a_{j+1}$ sur $a_j$ et $a_1$ sur $a_k$ : elle défait exactement ce que fait $c$, et les deux fixent les mêmes points.

2. Récurrence immédiate sur $m$ : chaque application de $c$ fait avancer l'indice de 1, modulo $k$.

3. D'après 2, $c^m=\mathrm{id}$ si et seulement si $a_{1+m}=a_1$ (les points hors support sont fixes de toute façon, et si $c^m(a_1)=a_1$ alors $c^m(a_j)=c^{j-1}(c^m(a_1))=a_j$). Les $a_j$ étant distincts, cela équivaut à $k \mid m$. Le plus petit $m \geqslant 1$ convenable est $k$.

Notons $S=\mathrm{Supp}(\sigma)$, $T=\mathrm{Supp}(\tau)$, avec $S\cap T=\varnothing$. Soit $x \in [\![1,n]\!]$.

• Si $x \in S$ : $x \notin T$ donc $\tau(x)=x$ et $\sigma\tau(x)=\sigma(x)$. Par stabilité, $\sigma(x) \in S$, donc $\sigma(x)\notin T$ et $\tau\sigma(x)=\sigma(x)$.
• Si $x \in T$ : même raisonnement en échangeant les rôles, $\sigma\tau(x)=\tau\sigma(x)=\tau(x)$.
• Si $x \notin S\cup T$ : $\sigma\tau(x)=\tau\sigma(x)=x$.

Donc $\sigma\tau=\tau\sigma$.

Les $\gamma(a_j)$ sont distincts car $\gamma$ est injective. Pour $j<k$ : $\gamma c\gamma^{-1}(\gamma(a_j))=\gamma(c(a_j))=\gamma(a_{j+1})$, et de même $\gamma(a_k)\mapsto\gamma(a_1)$.

Si $y \notin\{\gamma(a_1),\dots,\gamma(a_k)\}$, alors $\gamma^{-1}(y)\notin\{a_1,\dots,a_k\}$, donc $c(\gamma^{-1}(y))=\gamma^{-1}(y)$ et $\gamma c\gamma^{-1}(y)=y$.

Les deux permutations coïncident en tout point.

Le groupe $\mathfrak{S}_n$ étant fini, $\sigma$ est d'ordre fini $d$, donc $\sigma^d(x)=x$ : l'entier $p$ existe.

Si $0 \leqslant i<j \leqslant p-1$ et $\sigma^i(x)=\sigma^j(x)$, alors $\sigma^{j-i}(x)=x$ avec $1 \leqslant j-i<p$ : contradiction. Les éléments listés sont donc distincts.

Soit $m \in \mathbb{Z}$. La division euclidienne donne $m=qp+r$ avec $0 \leqslant r<p$. Comme $\sigma^p(x)=x$, on a $\sigma^{qp}(x)=x$ pour tout $q\in\mathbb{Z}$, donc $\sigma^m(x)=\sigma^r(x)$. D'où l'égalité d'ensembles.

Existence. Soit $\mathcal{O}_1,\dots,\mathcal{O}_r$ les orbites de $\sigma$ de cardinal au moins 2. Pour chacune, on choisit $x_i \in \mathcal{O}_i$, on note $p_i=|\mathcal{O}_i|$ et $$c_i=(x_i\ \ \sigma(x_i)\ \ \cdots\ \ \sigma^{p_i-1}(x_i)).$$ D'après la forme des orbites, $c_i$ est un $p_i$-cycle de support $\mathcal{O}_i$, et $c_i$ coïncide avec $\sigma$ sur $\mathcal{O}_i$ (l'image de $\sigma^{p_i-1}(x_i)$ est $\sigma^{p_i}(x_i)=x_i$). Les orbites étant disjointes, les $c_i$ commutent.

Vérifions $\sigma=c_1\cdots c_r$. Soit $y$.

• Si $y \in \mathcal{O}_i$ : les $c_j$, $j\neq i$, fixent $y$ et $c_i(y)=\sigma(y)$, qui est encore dans $\mathcal{O}_i$ donc fixé par les $c_j$, $j \neq i$. En plaçant $c_i$ en tête (les facteurs commutent), $c_1\cdots c_r(y)=c_i(y)=\sigma(y)$.
• Si $y$ n'est dans aucun $\mathcal{O}_i$ : son orbite est $\{y\}$, donc $\sigma(y)=y$, et tous les $c_j$ fixent $y$.

Unicité. Supposons $\sigma=c'_1\cdots c'_s$ avec des cycles à supports disjoints. Soit $y \in \mathrm{Supp}(c'_j)$ : comme ci-dessus, $\sigma^m(y)=c'^m_j(y)$ pour tout $m$, donc l'orbite de $y$ sous $\sigma$ est l'orbite de $y$ sous le cycle $c'_j$, c'est-à-dire $\mathrm{Supp}(c'_j)$. Les supports des $c'_j$ sont donc des orbites de $\sigma$ de cardinal au moins 2 ; inversement un point non fixe de $\sigma$ est dans l'un de ces supports. Les supports sont donc exactement $\mathcal{O}_1,\dots,\mathcal{O}_r$, et sur chacun le cycle coïncide avec $\sigma$ : il est entièrement déterminé.

Les $c_i$ commutent, donc pour $m \in \mathbb{N}$, $\sigma^m=c_1^m\cdots c_r^m$. La permutation $c_i^m$ a son support inclus dans $\mathrm{Supp}(c_i)$, et ces ensembles sont stables et disjoints : sur $\mathrm{Supp}(c_i)$, $\sigma^m$ agit comme $c_i^m$.

Ainsi $\sigma^m=\mathrm{id}$ si et seulement si $c_i^m=\mathrm{id}$ pour tout $i$, c'est-à-dire $k_i \mid m$ pour tout $i$ (un $k_i$-cycle est d'ordre $k_i$), c'est-à-dire $\mathrm{ppcm}(k_1,\dots,k_r)\mid m$. Le plus petit $m\geqslant1$ est ce ppcm.

Notons $\pi$ le produit de droite ; on applique les transpositions de droite à gauche.

• Soit $i<k$. Les transpositions $(a_j\ a_{j+1})$ avec $j>i$, appliquées en premier, ne touchent pas $a_i$. Puis $(a_i\ a_{i+1})$ envoie $a_i$ sur $a_{i+1}$. Les suivantes, $(a_j\ a_{j+1})$ avec $j<i$, ne touchent pas $a_{i+1}$. Donc $\pi(a_i)=a_{i+1}$.
• Pour $a_k$ : $(a_{k-1}\ a_k)$ l'envoie sur $a_{k-1}$, puis $(a_{k-2}\ a_{k-1})$ sur $a_{k-2}$, et ainsi de suite jusqu'à $a_1$. Donc $\pi(a_k)=a_1$.
• Un point hors de $\{a_1,\dots,a_k\}$ est fixé par chaque facteur.

Donc $\pi=(a_1\ \cdots\ a_k)$. La seconde formule se vérifie de la même façon.

D'après le théorème de décomposition, $\sigma$ est un produit de cycles ; chaque cycle est un produit de transpositions d'après la propriété précédente. En mettant bout à bout ces écritures, $\sigma$ est un produit de transpositions.

Pour $\sigma=\mathrm{id}$, on écrit $\mathrm{id}=(1\ 2)(1\ 2)$ (ou on accepte le produit vide).

Notons $\mathcal{P}$ l'ensemble des paires $\{i,j\}$ avec $i\neq j$. L'application $\{i,j\}\mapsto\{\sigma(i),\sigma(j)\}$ est une bijection de $\mathcal{P}$ (de réciproque associée à $\sigma^{-1}$). Donc $$\prod_{\{i,j\}\in\mathcal{P}}|\sigma(j)-\sigma(i)|=\prod_{\{k,l\}\in\mathcal{P}}|l-k|,$$ et le produit de l'énoncé est de valeur absolue 1.

Pour $i<j$, le facteur est négatif si et seulement si $\sigma(j)<\sigma(i)$, c'est-à-dire si $(i,j)$ est une inversion. Le produit vaut donc $(-1)^{I(\sigma)}=\varepsilon(\sigma)$.

Pour $\{i,j\}\in\mathcal{P}$, posons $q_\sigma(i,j)=\dfrac{\sigma(j)-\sigma(i)}{j-i}$, symétrique en $i,j$. Comme $\tau(i)\neq\tau(j)$, on peut écrire $$q_{\sigma\tau}(i,j)=\frac{\sigma(\tau(j))-\sigma(\tau(i))}{\tau(j)-\tau(i)}\cdot\frac{\tau(j)-\tau(i)}{j-i}=q_\sigma(\tau(i),\tau(j))\;q_\tau(i,j).$$ En faisant le produit sur $\mathcal{P}$ : $$\varepsilon(\sigma\tau)=\prod_{\{i,j\}\in\mathcal{P}}q_\sigma(\tau(i),\tau(j))\;\cdot\;\varepsilon(\tau).$$ L'application $\{i,j\}\mapsto\{\tau(i),\tau(j)\}$ étant une bijection de $\mathcal{P}$, le premier produit est $\prod_{\{k,l\}\in\mathcal{P}}q_\sigma(k,l)=\varepsilon(\sigma)$.

Enfin $\varepsilon(\mathrm{id})=1$ car $\mathrm{id}$ n'a aucune inversion, et $\varepsilon(\sigma)\varepsilon(\sigma^{-1})=\varepsilon(\mathrm{id})=1$ avec $\varepsilon(\sigma)=\pm1$ donne $\varepsilon(\sigma^{-1})=\varepsilon(\sigma)$.

Pour $(1\ 2)$, la deuxième ligne est $2,1,3,\dots,n$ : la seule inversion est $(1,2)$, donc $\varepsilon((1\ 2))=-1$.

Soit $(a\ b)$ une transposition quelconque. Il existe $\gamma \in \mathfrak{S}_n$ avec $\gamma(1)=a$ et $\gamma(2)=b$ (on complète en une bijection quelconque). Par la formule du conjugué, $(a\ b)=\gamma(1\ 2)\gamma^{-1}$. Comme $\{-1,1\}$ est commutatif : $$\varepsilon((a\ b))=\varepsilon(\gamma)\,\varepsilon((1\ 2))\,\varepsilon(\gamma)^{-1}=-1.$$

Autre preuve directe : pour $i<j$, les inversions de $(i\ j)$ sont $(i,j)$ et les couples $(i,k)$, $(k,j)$ avec $i<k<j$, soit $2(j-i-1)+1$, nombre impair.

Existence : $\varepsilon$ convient d'après les deux résultats précédents.

Unicité : soit $\varphi$ un tel morphisme et $\sigma\in\mathfrak{S}_n$. On écrit $\sigma=t_1\cdots t_r$ avec des transpositions. Alors $\varphi(\sigma)=\varphi(t_1)\cdots\varphi(t_r)=(-1)^r$, et de même $\varepsilon(\sigma)=(-1)^r$. Donc $\varphi=\varepsilon$.

1. Le morphisme donne $\varepsilon(\sigma)=(-1)^r$ ; deux écritures avec $r$ et $r'$ facteurs donnent $(-1)^r=(-1)^{r'}$, donc $r\equiv r' \pmod 2$.

2. Un $k$-cycle est produit de $k-1$ transpositions.

3. Si $\sigma=c_1\cdots c_r$ avec $c_i$ de longueur $k_i$ (orbites non triviales), alors $\varepsilon(\sigma)=\prod(-1)^{k_i-1}=(-1)^{\sum(k_i-1)}$. Une orbite réduite à un point apporte $|\mathcal{O}|-1=0$, donc $\sum_i(k_i-1)=\sum_{\mathcal{O}}(|\mathcal{O}|-1)=n-p$, la somme portant sur toutes les orbites, de cardinaux de somme $n$.

4. Le groupe d'arrivée est commutatif.

1. Le noyau d'un morphisme de groupes est un sous-groupe.

2. Soit $t=(1\ 2)$ (possible car $n\geqslant2$). L'application $f:\sigma\mapsto t\sigma$ envoie $\mathfrak{A}_n$ dans $\mathfrak{S}_n\setminus\mathfrak{A}_n$ car $\varepsilon(t\sigma)=-\varepsilon(\sigma)$. Elle est bijective entre ces deux ensembles : l'application $\sigma\mapsto t\sigma$ de $\mathfrak{S}_n\setminus\mathfrak{A}_n$ dans $\mathfrak{A}_n$ est sa réciproque, puisque $t^2=\mathrm{id}$. Les deux ensembles ont donc le même cardinal ; ils partitionnent $\mathfrak{S}_n$, d'où $|\mathfrak{A}_n|=\dfrac{n!}{2}$.