Groupe symétrique

Soit $\mathrm E=\{1, \ldots,n\}$.

Définition :

Une permutation de $\rm E$ est une bijection de $\rm E$ dans $\rm E$.

L’ensemble des permutations de $\rm E$ est noté $\mathrm S_n$. Cet ensemble, muni de la loi de composition des applications est un groupe d’élément neutre l’identité $\rm Id$, appelé groupe symétrique d’ordre $n$ sur l’ensemble $\rm E$.

Propriété : Si $\sigma \in \mathrm S_n$, on note : $\sigma=\left(\begin{matrix} 1 & \ldots & n \\\sigma(1) & \ldots & \sigma(n) \end{matrix}\right)$.

Propriété : $|\mathrm S_n|=n !$

Définition : Soit $\sigma \in \mathrm S_n$. L’ensemble $\mathrm{supp}(\sigma)=\{i/\sigma(i)\neq i\}$ est le support de $\sigma$.

Définition : Soit $\sigma \in \mathrm S_n$. $\sigma$ est un cycle de longueur $\ell\geq 2$ s’il existe $\ell$ éléments distincts $a_1,\ldots, a_\ell$ de $\rm E$ tels que $\sigma(a_1)=a_2,\ldots,\sigma(a_{\ell-1})$ $= a_\ell$, $\sigma(a_\ell)=a_1$ et $\sigma(x)=x$ pour tout $x\in \mathrm E-\{a_1,\ldots, a_\ell\}$.
On peut alors utiliser la notation cyclique $\sigma=(a_1 a_2 \ldots a_\ell)$.

Remarque : un cycle de longueur $2$ est appelé une transposition.

Théorème : Soit $\sigma \in \mathrm S_n$ tel que $\rm \sigma\neq Id$.

Il existe $k\geq 1$ et $c_1,\ldots,c_k$ des cycles à supports deux à deux disjoints tels que $\sigma=c_1\dots c_k$.

Cette décomposition est unique à l’ordre près des facteurs et est appelée décomposition canonique de $\sigma$.

Remarque : en général, on n’indique pas les cycles de longueur $1$ dans l’écriture de $\sigma$ en produit de cycles.

Les cycles de la décomposition commutent deux à deux.

Théorème : Soit $\rm \sigma \in \mathrm S_n-\{\rm id\}$ de décomposition canonique $c_1\dots c_k$.

L’ordre de $\sigma$ est le PPCM des longueurs des cycles $c_i$.

Pour décomposer une permutation en produit de transpositions, on utilise une décomposition en produit de cycles à supports disjoints et on décompose chaque cycle en produit de transpositions.

Par exemple : $\sigma=(a_1 a_2… a_l)=(a_1 a_2)\circ (a_2 a_3)\circ…\circ (a_{l-1}a_l)$.

Définition : Signature : il existe un unique morphisme de groupes de $\mathrm S_n$ dans $\{-1, 1\}$ envoyant toute transposition sur $-1$.

En pratique, on utilise les propriétés suivantes :

Propriété : La signature d’un cycle de longueur $p$ est égale à $(-1)^{p-1}$.

En particulier, la signature d’une transposition est égale à -1.

Propriété : La signature d’un produit de cycles est égale au produit des signatures des cycles.

Définition : Une permutation est paire si sa signature vaut 1 et impaire si sa signature vaut $-1$.