Permutations de l'ensemble à $n$ éléments (1) : Groupe symétrique $\mathfrak S_n $

 Soit $n$ un entier naturel strictement positif. 

Considérons l'ensemble $E_n=\{1,2,\ldots,n\}$

Permutations 

On dit qu'une fonction $\sigma$ de $E_n$ dans $E_n$ est une permutation de $E_n$ si $\sigma$ est une bijection.

Autrement dit : $\sigma$ est telle que pour tout $y\in E$, il existe un unique $x\in E$ tel que $\sigma(x)=y $.

On note $\mathfrak S_n $ l'ensemble des permutations de $E$. On munit $\mathfrak S_n $ de la loi de composition notée ici $\cdot $. 

Ainsi $\tau \cdot \sigma$ est définie pour tout $x\in E$ par $$\tau\cdot \sigma (x)=\tau(\sigma(x)) $$

Nous avons vu dans l'article Groupe des bijections que l'ensemble des permutations de $E_n $ forme un groupe pour l'opération $\cdot$. Le groupe $\mathfrak S_n $ est appelé le groupe symétrique.

Quelques notations

Permutations cycliques

Pour tout $n\in\mathbb N $, on note $\left(\begin{array}{cc} a & b \end{array}\right)$  la permutation de $E $ définie par :

• $\left(\begin{array}{cc} a & b \end{array}\right)(x)=x $ si $x\not \in\left\{a,b \right\}  $
• $(\begin{array}{cc} a & b \end{array})(a)=b $
•  $(\begin{array}{cc} a & b \end{array})(b)=a $

Une telle permutation est appelée une transposition.

Plus généralement, si $a_1,a_2,\ldots, a_{r-1},a_r $ sont $r$ éléments de $E_n$, on note

$$(\begin{array}{ccccc} a_1 & a_2 & \ldots & a_{r-1} & a_r \end{array}) $$

la permutation $\sigma $ de $E$ définie par : 

• $\sigma (x)=x $ si $x\not \in\left\{a_1,a_2,\ldots, a_{r-1},a_r \right\}  $
• $\sigma(a_i)=a_{i+1} $ si $i\in\left\{1,2,\ldots,r-1 \right\}$
• $\sigma(a_r)=a_{1} $ 

On dira que $\sigma $ ainsi définie est un cycle.

$r$ est appelé l'ordre du cycle $\sigma $. Un cycle d'ordre 2 est une transposition.

Notation matricielle d'une permutation

Si $\sigma$ est une permutation, on peut la noter sous forme matricielle : 

$$\sigma=\left(\begin{array}{ccccc} 1 & 2 & \ldots & n-1 & n\\ \sigma(1) & \sigma(2) & \ldots & \sigma(n-1) & \sigma(n) \\ \end{array}\right)$$

Exemple. 

Dans  $\mathfrak S_2 $, on a $$\left(\begin{array}{cc} 1 &2  \end{array}\right)=\left(\begin{array}{ccc} 1 & 2 & 3\\ 2 & 1 & 3 \\ \end{array}\right)$$ 

Commutativité ?

En général les permutations $E_n $ ne commutent pas, $\mathfrak S_n $ n'est pas abélien.

Par exemple, pour $n\geq 3$, on a 

$$ (\begin{array}{cc} 1 & 2 \end{array})\cdot(\begin{array}{cc} 1 & 3 \end{array})= (\begin{array}{ccc}1& 3 & 2 \end{array})$$ 

En effet, si on note $\sigma= (\begin{array}{cc} 1 & 2 \end{array})\cdot(\begin{array}{cc} 1 & 3 \end{array}) $, alors $\sigma $ effectue les transformations suivantes :

• $1\mapsto 3 \mapsto 3$
• $2\mapsto 2\mapsto 1$
• $3\mapsto 1 \mapsto 2$ 

Si on note $\tau= (\begin{array}{cc} 1 & 3 \end{array})\cdot(\begin{array}{cc} 1 & 2 \end{array}) $, alors $\tau $ effectue les transformations suivantes :

• $1\mapsto 2 \mapsto 2$
• $2\mapsto 1\mapsto 3$
• $3\mapsto 3 \mapsto 1$ 

On en déduit que $\tau= (\begin{array}{cc} 1 & 3 \end{array})\cdot(\begin{array}{cc} 1 & 2 \end{array})=(\begin{array}{ccc}1& 2 & 3 \end{array}) $ 

Donc $(\begin{array}{cc} 1 & 2 \end{array})\cdot(\begin{array}{cc} 1 & 3 \end{array})\neq  (\begin{array}{cc} 1 & 3 \end{array})\cdot(\begin{array}{cc} 1 & 2 \end{array})$

Propriétés de décomposition des permutations

Décomposition en cycle

Propriété 1. (Existence d'une décomposition en cycles)

Soit $\sigma$ une permutation de $\mathfrak S_n $ différente de l'identité. 

Alors il existe un entier $r$ strictement positif, et $r$ cycles $\gamma_1,\ldots,\gamma_r $ tels que 

$$\sigma=\gamma_r\cdot \ldots \cdot \gamma_1 $$

 

Démonstration.

On peut faire une récurrence sur $n$, pour $n\geq 2$.

Dans $\mathfrak S_2 $, il y a exactement deux permutations : $\textrm{id}$ et $\left(\begin{array}{cc} 1 & 2 \end{array}\right)$.

Supposons que dans $\mathfrak S_n $, chaque élément s'écrit comme un produit de cycles. Pour montrer le résultat, il suffit de montrer que cela implique que chaque élément de $\mathfrak S_{n+1} $ s'écrit comme un produit de cycles.

Soit $\sigma $ une permutation de $E_{n+1}$. 

Deux cas sont possibles :

• (cas 1). Si $\sigma(n+1)=n+1 $, alors la restriction $\sigma' $ en tant que fonction de $\sigma $ aux $n$ premiers entiers naturel donne une permutation de $E_n$. En effet, l'injectivité de $\sigma' $ provient de cellle de $\sigma $. 
  
  Pour la surjectivité, soit un quelconque $y\in E_n $, montrons que $y$ possède un antécédent par $\sigma $. Comme $E_n\subset E_{n+1} $, il existe par surjectivité de $\sigma $, $x\in E_{n+1}$ tel que $\sigma(x)=y $. Mais $x\neq n+1 $ car l'image de $n+1$ par $\sigma $ est $n+1$. Par conséquent, $\sigma'(x)=y$, ce qui prouve que $y$ a un antécédent par $\sigma' $. $\sigma' $ est donc une permutation de $E_n $.  
  
  Dans ce cas, d'après notre hypothèse de récurrence, on peut écrire :
  $$\sigma'=c_s\cdot c_{s-1}\cdot\ldots\cdot c_1 $$
  où $c_1,\ldots,c_s $ sont de cycles appartenant à $\mathfrak S_n $.
  
  On peut prologer les $c_i$ en tant que fonction sur $E_{n+1}$, on pose pour cela : $\gamma_i(x)=c_i(x) $ si $x\in E_n $
  $\gamma_i(n+1)=\gamma(n+1) $
  
  Les $c_i $ étant des cycles de $\mathfrak S_n $, les $\gamma_i $ sont des cycles de  $\mathfrak S_{n+1} $. 
  
  De plus on a
  $$\sigma=\gamma_s\cdot \gamma_{s-1}\cdot\ldots\cdot \gamma_1 $$
  En effet, on voit facilement, avec une récurrence sur $s$, que si $x\in E_n $,
  $$\gamma_s\cdot \gamma_{s-1}\cdot\ldots\cdot \gamma_1(x)=c_s\cdot c_{s-1}\cdot\ldots\cdot c_1(x)=\sigma'(x)=\sigma(x) $$
  
  
• (cas 2). Maintenant si $\sigma(n+1)\neq n+1 $. Notons $a=\sigma^{-1}(n+1) $ (autrement dit $\sigma(a)=n+1 $). On a nécessairement $1\leq a \leq n $.
  
  On note $\tau=\left(\begin{array}{cc} n+1 & a\end{array}\right)  $.
  
  Notons $\widetilde{\sigma}= \sigma\cdot   \tau $. On a $\widetilde{\sigma}(n+1)=\sigma\cdot   \tau(n+1)= \sigma(a)=n+1 $.
  
  Comme $\widetilde{\sigma} $ est une permutation, et que $\widetilde{\sigma}(n+1)=n+1 $, on est ramené au cas précédent. Donc il existe un entier naturel $s$ et $s$ cycles $\gamma_1,\ldots,\gamma_s $ éléments de $\mathfrak S_{n+1} $ tels que $$\widetilde{\sigma}=\gamma_s\cdot \gamma_{s-1}\cdot\ldots\cdot \gamma_1  $$
  
  Comme $\widetilde{\sigma}=\sigma\cdot   \tau $, on a $\widetilde{\sigma}\cdot \tau^{-1}=\sigma$, d'où
  $$\sigma=\gamma_s\cdot \gamma_{s-1}\cdot\ldots\cdot \gamma_1\cdot   \tau^{-1} $$
  
  Mais $\tau^{-1}=\left(\begin{array}{cc} n+1 & a\end{array}\right) =\tau $ est aussi un cycle d'ordre 2, donc la propriété est démontrée.

A suivre 

Nous verrons dans un prochain article que la décomposition en cycles peut être réalisée avec une contrainte supplémentaire : les cycles apparaissant dans la décomposition peuvent avoir des supports 2 à 2 disjoints, c'est-à-dire ne pas agir sur les mêmes éléments de $E_n$. 

Aussi, nous verrons qu'il est possible de décomposer toute permutation en produit de transpositions. Les transpositions permettent à elles seules de générer toutes les permutations.