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.