Écrire une permutation comme produit de transpositions : méthode (MPSI)
Écrire une permutation comme produit de transpositions
- Décomposer $\sigma$ en cycles à supports disjoints.
- Remplacer chaque cycle $(a_1\ \cdots\ a_k)$ par $(a_1\ a_2)(a_2\ a_3)\cdots(a_{k-1}\ a_k)$.
- Si on veut vérifier, calculer l'image de chaque élément en appliquant les facteurs de droite à gauche.
Application
Pour $\sigma=(1\ 3\ 7)(2\ 5)(4\ 8)$, on obtient $\sigma=(1\ 3)(3\ 7)(2\ 5)(4\ 8)$ : 4 transpositions.
Pour $(1\ 2\ 3\ 4\ 5)=(1\ 2)(2\ 3)(3\ 4)(4\ 5)$ : 4 transpositions.
Non-unicité, autres familles génératrices
L'écriture en produit de transpositions n'est pas unique, ni même son nombre de facteurs : $(1\ 2\ 3)=(1\ 2)(2\ 3)=(1\ 3)(1\ 2)=(1\ 2)(2\ 3)(1\ 2)(1\ 2)$. On verra que seule la parité du nombre de facteurs est fixée.
D'autres familles engendrent $\mathfrak{S}_n$ : par exemple les $(1\ i)$, $2\leqslant i\leqslant n$, car pour $i\neq j$ distincts de 1, $(i\ j)=(1\ i)(1\ j)(1\ i)$ (formule du conjugué). Les transpositions $(i\ i+1)$ de deux éléments consécutifs engendrent aussi $\mathfrak{S}_n$ ; ces résultats relèvent des exercices.
S’entraîner
- Composer et inverser dans $\mathfrak{S}_5$
- Décomposition, ordre et puissance d'une permutation de $\mathfrak{S}_9$
- Produits de cycles non disjoints
- Signature du battage parfait
- Familles génératrices de transpositions
Dans le cours
Groupe symétrique : Écrire une permutation comme produit de transpositions