Exercices corrigés - Groupe symétrique

1. On cherche l'image de chaque élément. Les éléments différents de $a,b,c,d$ ne sont pas modifiés. Pour $a,b,c$ et $d$, on a : $$ \begin{array}{ccccccc} a&\mapsto_{(d\ a)}&d&\mapsto_{(c\ d)}&c&\mapsto_{(a\ b)}&c\\ b&\mapsto_{(d\ a)}&b&\mapsto_{(c\ d)}&b&\mapsto_{(a\ b)}&a\\ c&\mapsto_{(d\ a)}&c&\mapsto_{(c\ d)}&d&\mapsto_{(a\ b)}&d\\ d&\mapsto_{(d\ a)}&a&\mapsto_{(c\ d)}&a&\mapsto_{(a\ b)}&b.\\ \end{array}$$ La permutation est donc un cycle de longueur 4, $(a\ c\ d\ b)$.
2. Une permutation étant une bijection, le dernier élément de $\{1,\dots,n\}$ ne peut être envoyé que sur lui-même. Une telle permutation est donc nécessairement l'identité.
3. Non, du moins si $n\geq 4$. En effet, la composée de deux transpositions à support disjoint vérifie elle-même que $s^2=Id$.
4. Pour énumérer tous les éléments de $\mathcal S_4$, on peut partir du fait qu'une permutation se décompose de manière unique en produit de cycles à supports disjoints. On trouve alors que les permutations sont
   • l'identité (correspond à des produits de cycle de longueur 1);
   • les 4 cycles, ce sont : $$(1\ 2\ 3\ 4),\ (1\ 2\ 4\ 3),\ (1\ 3\ 2\ 4),\ (1\ 3\ 4\ 2),\ (1\ 4\ 2\ 3),\ (1\ 4\ 3\ 2);$$
   • les 3 cycles (qui correspondent à un produit d'un cycle de longueur 3 par un cycle de longueur 1); ces 3 cycles sont $$(1\ 2\ 3),\ (1\ 3\ 2),\ (1\ 2\ 4),\ (1\ 4\ 2),\ (1\ 3\ 4),\ (1\ 4\ 3),\ (2\ 3\ 4),\ (2\ 4\ 3).$$
   • les transpositions (qui correspondent à un produit d'un cycle de longueur 2 et de deux cycles de longueur 1), ces transpositions sont : $$(1\ 2),\ (1\ 3),\ (1\ 4),\ (2\ 3),\ (2\ 4),\ (3\ 4)$$
   • les produits de deux transpositions à support disjoint (produit de deux cycles de longueur 2). Ces produits sont : $$(1\ 2)\circ (3\ 4),\ (1\ 3)\circ(2\ 4),\ (1\ 4)\circ(2\ 3).$$
   On a ainsi énuméré les 24 éléments de $\mathcal S_4$.

1. On commence par étudier les images successives de $1$. Ce sont 3,4,6. On étudie ensuite les images successives de 2. On trouve 5 (ensuite on revient à 2). On a épuisé tous les éléments de $1,\dots,6$. La décomposition canonique de $\sigma_1$ en produits de cycles disjoints est $$\sigma_1=(1,3,4,6)\circ(2,5).$$ Pour décomposer $\sigma_1$ en produit de transpositions, il suffit de décomposer chacun des cycles en produits de transposition. Pour le second, c'est facile car il s'agit déjà d'une transposition. Pour le premier, on écrit $$(1,3,4,6)=(1,3)\circ (3,4)\circ (4,6)$$ et donc $$\sigma_1=(1,3)\circ (3,4)\circ (4,6)\circ(2,5).$$ L'ordre du cycle $(1,3,4,6)$ est 4, l'ordre du cycle $(2,5)$ est 2, l'ordre de la permutation est donc le ppcm de 2 et 4, à savoir 4. En particulier, puisque $4|100$, on en déduit que $\sigma_1^{100}=Id$. Enfin, puisqu'on a décomposé $\sigma_1$ en produit de transpositions, il est facile de déterminer sa signature. Elle vaut $$\veps(\sigma_1)=(-1)^4=1.$$
2. Par la même méthode, on trouve $$\sigma_2=(1,4,7,8)\circ(2,6,5)\circ(3,9),$$ $$\sigma_2=(1,4)\circ (4,7)\circ (7,8)\circ (2,6)\circ (6,5)\circ (3,9).$$ L'ordre de $\sigma_2$ est le ppcm de 4,3 et 2, soit 12. La signature de $\sigma_2$ est $(-1)^6=1$. Enfin, puisque $100\equiv 0[2]$, $100\equiv 1[3]$ et $100\equiv 0[4]$, on en déduit que $$\sigma_2^{100}=(2,6,5)^1=(2,6,5).$$

On introduit sur $\{1,\dots,n\}$ la relation $x\sim y\iff \exists k\in\mathbb Z, y=\sigma^k(x)$. On vérifie très facilement que l'on définit ainsi une relation d'équivalence. Ainsi, les classes d'équivalence pour cette partition forment une partition de $\{1,\dots,n\}$. Soit $x\in\{1,\dots,n\}$ qui n'est pas un point fixe de $\sigma$. Alors sa classe d'équivalence pour $\sim$ est $\{x,\sigma(x)\}$. En effet, puisque $\sigma^{2}(x)=x$, on a $\sigma^{2k}(x)=x$ et $\sigma^{2k+1}(x)=\sigma(x)$ pour tout $k\in\mathbb Z$. Ainsi, si $\sigma$ n'a pas de points fixes, on a trouvé une partition de $\{1,\dots,n\}$ avec des ensembles contenant chacun deux éléments. Ceci contredit que $n$ est impair.

Un $k$-cycle s'écrit $(a_1\ a_2\ \dots\ a_k)$. On doit donc choisir dans $\{1,\dots,n\}$ $k$ élements ordonnés parmi $n$. Mais l'écriture $(a_1\ a_2\ \dots\ a_k)$ n'est pas unique. Il y a en effet $k$ façons d'écrire le même $k$-cycle, suivant le choix que l'on fait pour le premier terme - par exemple, $(a_2\ a_3\dots a_k\ a_1)$ représente le même $k$-cycle que $(a_1\ a_2\ \dots\ a_k)$. On conclut finalement que le nombre de cycles de longueur $k$ est égal à $$\frac{A_n^k}{k}=\frac{n(n-1)\dots (n-k+1)}{k}.$$

Notons $\veps_n$ la signature de $\sigma_n$. Pour $n\geq 3$, on peut décomposer $\sigma_n$ en $\tau_n\circ s_n$ où $\tau_n$ est la transposition $(1\ n)$ et $s_n$ est la permutation $$s_n=\left(\begin{array}{ccccc} 2&3&\dots&n-2&n-1\\ n-1&n-2&\dots&3&2 \end{array}\right).$$ Mais il est clair que la signature de $s_n$ vaut celle de $\sigma_{n-2}$ (il s'agit de la même permutation, mais en renumérotant les éléments). On obtient donc la formule de récurrence $$\veps_n=-\veps_{n-2}.$$ En particulier, $\veps_n=\veps_{n-4}$ pour $n\geq 4$, et il suffit donc de regarder la congruence modulo 4 de $n$ pour trouver la valeur de $\veps_n$. On en déduit que $$\left\{ \begin{array}{rcl} \veps_{4k+1}&=&\veps_1=1\\ \veps_{4k+2}&=&\veps_2=-1\\ \veps_{4k+3}&=&\veps_3=-1\\ \veps_{4k+4}&=&\veps_4=1\\ \end{array}\right. $$ Une autre façon de procéder est de remarquer que $\sigma_n$ est le produit des transpositions suivantes : $(1\ \ n)$, $(2\ \ n-1)$, etc... Il suffit alors de compter le nombre de transpositions pour déterminer la signature.

1. Puisque les transpositions engendrent $S_n$, il suffit de démontrer que toute transposition $(i\quad j)$, avec $i<j$, s'écrit comme produit des transpositions $(1\quad k)$. Mais si $i=1$, c'est déjà fait, et si $1<i$, on a $(i\quad j)=(1\quad i)\circ (1\quad j)\circ (1\quad i)$.
2. On va utiliser la question précédente et démontrer que toute transposition $(1\quad k)$ s'écrit comme produit de transpositions de la forme $(i\quad i+1)$. On procède par récurrence finie sur $k\in\{2,\dots,n\}$, la propriété étant vraie si $k=2$. Supposons la propriété vraie au rang $k$. Pour la prouver au rang $k+1$, il suffit d'écrire que $$(1\quad k+1)=(k\quad k+1)\circ (1\quad k)\circ (k\quad k+1).$$
3. 1. On va prouver par récurrence finie sur $k\in\{0,\dots,n-2\}$ que $c^k \circ t\circ c^{-k}=(k+1\quad k+2)$. La propriété est vraie si $k=0$. Supposons la prouvée au rang $k$. Alors $$c^{k+1} \circ t\circ c^{-(k+1)}=c\circ (k+1\quad k+2)\circ c^{-1}=(k+2\quad k+3).$$
   2. D'après la question précédente, toute transposition de la forme $(k\quad k+1)$ s'écrit en fonction de $c$ et de $t$. De plus, ces transpositions engendrent $S_n$. Ainsi, $c$ et $t$ engendrent $S_n$.

Lorsqu'on réalise un déplacement horizontal d'un jeton, on ne change par l'ordre des numéros, et la permutation correspondante est simplement l'identité. Lorsqu'on réalise un déplacement vertical d'un jeton, que ce soit vers le haut ou vers le bas, on produit un cycle de longueur 3, donc une permutation de signature égale à 1. La position finale étant obtenue comme suite de déplacements horizontaux ou verticaux, la permutation obtenue correspond à un produit de cycles de longueur 3, donc à un produit de permutations de signature égale à 1. C'est donc aussi une permutation de signature égale à 1.
Ces jeux de taquin sont souvent utilisés pour réaliser des puzzles. Cet exercice prouve que toutes les positions possibles des jetons ne sont pas atteignables.

Une permutation paire est produit d'un nombre pair de transpositions. Il suffit donc de prouver que le produit de deux transpositions est aussi produit de 3-cycles. On distingue deux cas :

1. les transpositions sont à supports disjoints : on écrit alors $$(i\ j)\circ (k\ l)=(i\ k\ j)\circ (k\ l\ i).$$
2. les supports des deux transpositions ont un élément en commun : on écrit alors $$(i\ j)\circ (i\ k)=(i\ k\ j).$$

On va commencer par s'intéresser à l'existence d'une telle décomposition, et on va prouver son existence par récurrence sur $n$. Le résultat est clair si $n=2$, supposons le prouvé au rang $n-1$ et prouvons-le au rang $n\geq 3$. L'idée est de se ramener à une permutation de $\{1,\dots,n-1\}$ en utilisant $\sigma_n$. Pour cela, notons $p$ tel que $s(n)=p$. Alors, $\sigma_n^{n-p}(p)=n$, et donc $\sigma_n^{n-p}\circ s(n)=n$. Ainsi, $\sigma_n^{n-p}\circ s$ peut être vu comme une permutation de $\{1,\dots,n-1\}$. Ainsi, par hypothèse de récurrence, il existe $k_1,\dots,k_{n-1}$ avec $k_j\in \{0,\dots,j-1\}$ tels que $$\sigma_n^{n-p}\circ s=\sigma_{n-1}^{k_{n-1}}\circ\dots\circ\sigma_3^{k_3}\circ \sigma_2^{k_2}.$$ On en déduit que $$s=\sigma_n^p\circ \sigma_{n-1}^{k_{n-1}}\circ\dots\circ\sigma_3^{k_3}\circ \sigma_2^{k_2}$$ ce qui donne le résultat avec $k_n=p$ si $p\neq n$, $k_n=0$ sinon.
Prouvons maintenant l'unicité d'une telle décomposition et supposons que l'on ait deux décompositions différentes $$s=\sigma_{n}^{k_{n}}\circ\dots\circ\sigma_3^{k_3}\circ \sigma_2^{k_2}=\sigma_{n}^{j_{n}}\circ\dots\circ\sigma_3^{j_3}\circ \sigma_2^{j_2}.$$ Soit $r$ le plus grand entier tel que $k_r\neq j_r$. Alors $$s_1=\sigma_{r}^{k_{r}}\circ\dots\circ\sigma_3^{k_3}\circ \sigma_2^{k_2}=\sigma_{r}^{j_{r}}\circ\dots\circ\sigma_3^{j_3}\circ \sigma_2^{j_2}.$$ Mais $s_1(r)=\sigma_r^{k_r}(r)=\sigma_r^{j_r}(r)$, et donc $k_r=j_r$, ce qui contredit l'existence de deux décompositions différentes.