Les transpositions engendrent le groupe symétrique : énoncé (MPSI)
Les transpositions engendrent le groupe symétrique
Toute permutation de $\mathcal S_n$ est un produit de transpositions (l'identité étant le produit vide, ou $(1\ 2)^2$ si $n\geqslant 2$).
Démonstration : Les transpositions engendrent le groupe symétrique
Par récurrence sur n
Pour $n=1$, $\mathcal S_1=\{\mathrm{id}\}$ et il n'y a rien à démontrer. Supposons le résultat vrai dans $\mathcal S_{n-1}$ et soit $\sigma\in\mathcal S_n$.
- Si $\sigma(n)=n$, la restriction de $\sigma$ à $\llbracket 1,n-1\rrbracket$ est une permutation de $\llbracket 1,n-1\rrbracket$ ; par hypothèse de récurrence, c'est un produit de transpositions de $\llbracket 1,n-1\rrbracket$, que l'on prolonge en fixant $n$. Ce produit est égal à $\sigma$.
- Si $\sigma(n)=k\neq n$, on pose $\tau=(n\ k)$. Alors $\tau\sigma(n)=\tau(k)=n$. D'après le premier cas, $\tau\sigma=\tau_1\cdots\tau_r$ avec des transpositions $\tau_i$, et comme $\tau^{-1}=\tau$, on obtient $\sigma=\tau\tau_1\cdots\tau_r$.
Le résultat est donc vrai au rang $n$.
Un cycle comme produit de transpositions
Pour un cycle de longueur $p$ : $$(a_1\ a_2\ \cdots\ a_p)=(a_1\ a_2)(a_2\ a_3)\cdots(a_{p-1}\ a_p).$$ C'est un produit de $p-1$ transpositions. Vérification pour $p=3$ : avec $(a_1\ a_2)(a_2\ a_3)$, $a_1\mapsto a_1\mapsto a_2$, $a_2\mapsto a_3\mapsto a_3$, $a_3\mapsto a_2\mapsto a_1$. On retrouve bien $(a_1\ a_2\ a_3)$. Le cas général se vérifie de même en suivant chaque $a_k$.
S’entraîner
Dans le cours
Déterminants : Les transpositions engendrent le groupe symétrique