Éléments remarquables de Sn

Définition:

Soient $i,j\in \{1;2;\cdots;n\}$ tels que $i\neq j$ . On appelle transposition associé à $i$ et $j$ la permutation notée $T_{ij}$ ou $(ij)$ de $\textsl{S}_{n}$ définie par

$\begin{array}{rccl}T_{ij}:&\{1;2;\cdots;n\}&\rightarrow& \{1;2;\cdots;n\}\\&x&\mapsto& T_{ij}(x)=\left\{\begin{array}{ll}j, & \hbox{\text{ si } }x=i; \\i, & \hbox{\text{ si } } x=j;\\x, & \hbox{\text{ sinon. } }\end{array}\right.\end{array}$

Remarque: $T_{ij}= T_{ji}$ . Le nombre de transposition de $\textsl{S}_{n}$ est $\complement^{2}_{n}=\frac{n!}{2!(n-2)!}$

Propriété:

[ $\mathbf{P3.}$ ] $T_{ij}\circ T_{ji}=Id_{n}$
[ $\mathbf{P4.}$ ] $T_{ij}\circ T_{kl}=T_{kl}\circ T_{ij}\Leftrightarrow (\{i;j\}\cap\{k;l\}=\emptyset \text{ ou } (i,j)=(k,l))$

Preuve:
Soit $x\in \{1;2;\cdots;n\}$

si $x=i$ alors $T_{ij}\circ T_{ji}(i)=T_{ij}(T_{ji}(i))=i=Id_{n}(i)$
si $x=j$ alors $T_{ij}\circ T_{ji}(j)=T_{ij}(T_{ji}(j))=j=Id_{n}(j)$
si $x\notin \{i;j\}$ alors $T_{ij}\circ T_{ji}(x)=T_{ij}(T_{ji}(x))=x=Id_{n}(x)$
$\box$

Théorème:

l’ensemble des transpositions est une partie génératrice de $\textsl{S}_{n}$ .

Preuve:

pour $n=2$ , $\textsl{S}_{2}={Id_{2};T_{12}}$ ; $\textsl{S}_{2}=<{T_{12}}>$

Pour $n=3$

$\begin{eqnarray*}\textsl{S}_{3} &=& \{Id_{3};T_{12};T_{13};T_{23};T_{12}\circ T_{13};T_{12}\circ T_{23}\} \\\textsl{S}_{3} &=& <\{T_{12};T_{13};T_{23}\}>\end{eqnarray*}$

Par conjecture on obtient le résultat qui nécessite une preuve plus rigoureuse. $\box$

Définition:

soit $\sigma\in \textsl{S}_{n}$ On appelle orbite d’un élément $x\in \{1;2;\cdots;n\}$ pour $\sigma$ l’ensemble $\{\sigma^{k}(x)/ k\in \mathbb{N}\}$ .

Il est noté $\omega(x)$ ; mais pour faire simple on notera $orbite(x)$ .

Exemple: Dans $\textsl{S}_{5}$ déterminer toutes les orbites de $\sigma=\left(\begin{array}{ccccc}1 & 2 & 3 & 4 & 5 \\4 & 5 & 3 & 1 & 2 \end{array}\right)$

Proposition:

Soit $\sigma\in \textsl{S}_{n}$ , la relation $R_{\sigma}$ définie sur $\{1;2;\cdots;n\}$ par

$\forall x,y\in \{1;2;\cdots;n\} xR_{\sigma} y \Leftrightarrow orbite(x)=orbite(y)$

est une relation d’équivalence sur $\{1;2;\cdots;n\}$ .

Preuve: TD $\box$

Définition:

Soit $p\in \{2;3;\cdots;n\}$ on appelle $p$ -cycle de $\textsl{S}_{n}$ toute permutation $\sigma\in \textsl{S}_{n}$ dont toutes les orbites sont des singletons sauf une qui est de cardinal $p.$

Exemple:

Les transpositions sont des $2$ -cycles

La permutation $\left(\begin{array}{ccccc}1 & 2 & . & . & n-1 \\2 & 3 & . & . & 1 \end{array}\right)$ est un $n-1$ -cycle.

Dans $\textsl{S}_{5}$ $\sigma=\left(\begin{array}{ccccc}1 & 2 & 3 & 4 & 5 \\2 & 4 & 3 & 1 & 5 \end{array}\right)$ est un $3$ -cycle.

Définition:

On appelle support d’une permutation l’ensemble des éléments non invariants.

$\forall\sigma \in \ \textsl{S}_{n}, Supp(\sigma)=\{k\in \{1;2;\cdots;n\} \text{ tel que } \sigma (k)\neq k\}$

Propriété:

[ $\mathbf{P5.}$ ] L’ordre d’un $p$ -cycle $(a_{1}a_{2}\ldots a_{p})$ est exactement sa longueur ‘ $p$ ‘.
[ $\mathbf{P6.}$ ] Si $\sigma=(a_{1}a_{2}...a_{p})$ est un $p$ -cycle alors $\sigma=(a_{1}a_{2})\circ(a_{2}a_{3})\circ\ldots\circ(a_{P-1}a_{P}).$ C’est à dire que $\sigma$ se décompose en produit de $p-1$
transpositions.

Théorème:

Toute permutation différente de $Id_{n}$ se décompose de manière unique à l’ordre près en produit de cycles disjoints.

Preuve: TD(Bien utiliser les orbites) $\box$

Exemple: On donne

$\sigma_{1}=\left(\begin{array}{ccccccc}1 & 2 & 3 & 4 & 5 & 6 & 7 \\4 & 6 & 3 & 5 &1 & 2 & 7 \end{array}\right)\in \textsl{S}_{7}.$

$\begin{eqnarray*}Orbite(1) &=& \{1;4;5\}=Orbite(4) \\Orbite(6) &=& \{2;6\}=Orbite(2) \\Orbite(7) &=& \{7\} \\Orbite(3) &=& \{3\} \\Supp(\sigma) &=& \{1;2;4;5;6\}\end{eqnarray*}$

Décomposition de $\sigma_{1}$ en produit de cycles.

$\sigma_{1}=(145)(62)$ ou $\sigma_{1}=(26)(514)$

En produit de transpositions on a: $\sigma_{1}=(26)(51)(14)$

Déterminer l’ordre de $\sigma_{1}$

Remarque: L’ordre d’une permutation quelconque de $\textsl{S}_{n}$ est le ppcm des ordres des cycles disjoints qui apparaissent dans sa décomposition(ces cycles sont des longueurs $\geq2$ )