Permutations de l'ensemble à $n$ éléments (2) : décomposition d'une permutations en cycles à supports disjoints et en produit de transpositions

 Cet article fait suite à 

• (0) Ensemble des bijections d'un ensemble
• (1) Permutation de l'ensemble à $n$ éléments (1) : le groupe symétrique $\mathfrak S_n $

Dans (1), nous avons défini le groupe symétrique $\mathfrak S_n $ et vu quelques propriétés concernant les permutations de l'ensemble $E_n=\left\{1,2,\ldots,n\right\} $ qui le composent. Nous avons défini les cycles et les transpositions. Ce sont les éléments générateurs de $\mathfrak S_n $ dans le sens où toute permutation s'écrit comme un produit de cycles. 

Nous verrons dans cet article que 

• chaque permutation peut se décomposer en produit de cycles de supports disjoints, et nous verons un algorithme permettant de décomposer une permutation en un tel produit
• chaque permutation peut se décomposer en produit de transpositions

Support d'une permutation

On appelle support d'un cycle $c$ élément de $\mathfrak{S_n} $, l'ensemble des éléments de $E_n $ qui ne sont pas égaux à leur image par $c$.

Autrement dit, si $c=(\begin{array}{ccccc} a_1 & a_2 & \ldots & a_{k-1} & a_k \end{array}) $, le support de $c$ est $S(c)=\left\{a_1,a_2,\ldots,a_k \right\} $.

Plus généralement, le support d'une permutation $\sigma\in\mathfrak{S_n} $ est défini comme étant l'ensemble des $x\in E_n $, tels que $\sigma(x)\neq x $.

Remarques. 

(1) Le support d'une permutation, s'il n'est pas vide, contient au moins deux éléments. En effet si $x\in S(\sigma)$, alors $s(x)\neq x $. Alors $\sigma(x)\in S(\sigma)$ aussi car sinon, on aurait $\sigma(x)=\sigma(\sigma(x)) $, d'où en appliquant $\sigma^{-1}$, $x=\sigma(x)$ ce qui contredirait $x\in S(\sigma) $.  

(2) Par définition $S(\sigma)=\emptyset $ si et seulement si $\sigma$ est l'identité.  

Propriété 1. 

 Si pour un certain entier $r\geq 2$, $\sigma=\sigma_1 \cdot \sigma_2 \cdot \ldots \sigma_r $ est un produit de $r$ permutations à supports deux à deux disjoints, alors le support de $\sigma $ est la réunion des supports de $\sigma_1,\sigma_2,\ldots,\sigma_r $.

Démonstration.

 Notons $S=S(\sigma)$, et pour tout $i$, $S_i=S\left(\sigma_i\right) $. 

Si $x\in S_1$, alors $\sigma_1(x)\neq x $. Par définition, $\sigma_1(x)\in S_1 $ donc $\sigma_1(x)\not\in S_2 $ et $\sigma_2 \cdot \sigma_1(x)=\sigma_1(x)\neq x$ donc $x\in S$. 

Si $x\in S_2$, alors $x\not\in S_1 $, donc $\sigma_1(x)=x $. Ainsi $\sigma_2\cdot \sigma_1 (x)=\sigma_2(x)\neq x $ car $x\in S_2 $. Donc $x\in S $.

On en déduit que $S_1\cup S_2 \subset S $.

Réciproquement, si $x\not\in (S_1\cup S_2) $, alors $x$ n'est ni dans le support de $\sigma_1 $ ni dans celui de $\sigma_2 $ et $\sigma(x)=\sigma_2\cdot\sigma_1(x)=\sigma_2(x)=x $ donc $x\not\in S $. On en deduit que $S\subset S_1\cup S_2 $.

Le cas particulier $r=2$ est donc démontré.

Supposons la propriété vraie pour un certain $r$, et soit $\sigma=\sigma_1 \cdot \sigma_2 \cdot \ldots \sigma_r\cdot \sigma_{r+1} $. 

Nous avons $\sigma=\sigma'\cdot \sigma_{r+1} $, avec $\sigma'=\sigma_1 \cdot \sigma_2 \cdot \ldots \sigma_r $. Notons $S'=S(\sigma') $.

Par hypothèse de récurrence, $S'=\cup_{i=1}^r S_i $. D'après le cas $r=2$, on a aussi $S=S'\cup S_{r+1} $.

Donc $S=\bigcup_{i=1}^{r+1} S_i $ ce qui termine la démonstration.

Propriété 2. (commutativité des permutations à supports disjoints)

 Soient $\sigma, \sigma'\in\mathfrak S_n$ deux permutations dont les supports sont disjoints. 

 

 Alors $\sigma\cdot \sigma'=\sigma'\cdot\sigma $.

Démostration. 

Notons $S$ et $S'$ les supports respectifs de $\sigma$ et $\sigma ' $. 

Soit $x\in E_n$.

Si $x\in S $, alors $\sigma'(x)=x $ car $S\cap S'=\emptyset$, donc $\sigma\cdot \sigma'(x)=\sigma(x) $. Comme $x\in S $, nous avons $\sigma(x)\in S$ (voir le point (1) de la remarque plus haut). Donc $x\not\in S' $ et $\sigma'(x)=x $ d'où $\sigma'\cdot\sigma(x)=\sigma(x)$. 

De même si $x\in S' $, on a $\sigma\cdot \sigma'(x)=\sigma\cdot \sigma'(x)=\sigma'(x) $.

Enfin si $x$ n'est ni dans $S$ ni dans $S'$, nous avons $\sigma\cdot \sigma'(x)=\sigma(x)=x=\sigma'(x)=\sigma'(\sigma(x))=\sigma'\cdot\sigma(x) $.

Pour tout $x\in E_n$, $\sigma\cdot \sigma'(x)=\sigma'\cdot\sigma(x) $, donc $\sigma\cdot \sigma'=\sigma'\cdot \sigma$. 

Décomposition d'une permutation en produit de cycles de supports disjoints

Propriété 3. 

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

Alors il existe un entier $r$ strictement positif, et $r$ cycles dont les supports sont disjoints deux à deux $\gamma_1,\ldots,\gamma_r $ tels que 

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

Nous allons comme annoncé précédemment donner une démonstration algorithmique qui permettra de calculer à la main (ou à l'aide d'un programme) les cycles à support disjoints dans la décomposition d'une permutation.

Commeçons par un lemme.

Lemme. 

Soit $\sigma\in\mathfrak S_n $ différent de l'identité.

Si $\sigma(x)\neq x $, alors il existe un plus petit entier $k$ tel que $\sigma^k(x)=x$. 

Preuve du lemme.

Un tel $k$ existe car les $\sigma^i(x)$ pour $1\leq i \leq n $ forment un sous-ensemble de $E_n$. 

Ce sous-ensemble contient au plus $n$ éléments, et si $m$ est le nombre d'élément de cet ensemble, alors $k=m-1$. En effet cela signifie que $x,\sigma(x),\ldots,\sigma^k(x) $ sont distincts et que $\sigma^{k+1}(x) $ est dans $\left\{x,\sigma(x),\ldots,\sigma^k(x)  \right\} $. 

Autrement dit, $\sigma^{k+1}(x)=\sigma^i(x) $ pour un certain $i$ ($1\leq i \leq k$). 

D'où, $\sigma^{k+1-i}(x)=x $. 

Si $i\geq 1$, alors $k+1-i<k+1 $ ce qui contredit la minimalité de $k$.

Démonstration de la propriété 3.

 Soit pour un entier $n\geq 2 $ donné, $\sigma \in \mathfrak S_n$ une permutation. 

Nous allons faire une récurrence pour montrer la propriété suivante pour tout entier $m$ tel que  $n\geq m\geq 2 $ :

 

$\mathcal P_m\  : \  \forall \sigma \in \mathfrak S_n $ dont le support contient au plus $m$ éléments, et tel que $\sigma\neq \textrm{id}$,  $\exists c_1,\ldots,c_r\in\mathfrak S_n$  à supports 2 à 2 disjoints tels que  $\sigma=c_r\cdot\ldots\cdot c_1 $ 

 

Supposons pour un certain entier naturel $m$, la propriété $\mathcal P_m$ et montrons $\mathcal P_{m+1}$. 

Soit $\sigma\in \mathfrak{S}_{n}$ une permutation de $E_{n}$. On note $m$ le nombre d'éléments du support de $\sigma $. 

Commençons par le cas $m=2$. Ce cas correspond au cas où $\sigma$ est une transposition $\left(\begin{array}{cc} a & b \end{array}\right )$ car exactement deux éléments sont changés par $\sigma$. Dans ce cas $\sigma$ est déjà un cycle et on a bien $\mathcal P_2 $.

Supposons pour un certain $m\geq 2$ : $\mathcal P_m $.

Comme $\sigma\neq\textrm{id} $, le support $S$ de $\sigma $ contient au moins 2 éléments. Soit $x\in S$. Par définition $\sigma(x)\neq x$. 

On construit le cycle  

$$c=\left(\begin{array}{ccccc} x & \sigma(x) & \ldots & \sigma^{k-1}(x) & \sigma^{k}(x) \end{array}\right ) $$ 

où $k$ est le plus petit entier tel que $\sigma^k(x)=x $ (voir lemme).

Le support de $c$ contient $k$ éléments avec $k\geq 2$. En effet, $c(x)$ est aussi un élément du support de $x$. 

Soit $\sigma'=\sigma\cdot c^{-1} $, et notons $S'$ son support. 

Remarquons tout d'abord que $c^{-1} $ est le cycle 

$$c^{-1}=\left(\begin{array}{ccccc} \sigma^k(x) & \sigma^{k-1}(x) & \ldots & \sigma(x) & x \end{array}\right ) $$

Il a le même support que $c$ : $$S\left(c^{-1}\right)=S(c)=\left\{\sigma^{i}(x),\ 0\leq i \leq k \right\}$$

On a par construction, $\sigma=\sigma'\cdot c $. Or $\sigma' $ et $c$ ont des supports disjoints. En effet si $y\not \in S(c)$, alors $\sigma(y)=\sigma'\cdot c^{-1}\cdot c(y)=\sigma'(y) $, et puisque  $y\neq \sigma(y)=\sigma'(y) $, donc $y\in S'$. Ainsi $S(c)\cap S'=\emptyset$.

Utilisons maintenant notre hypothèse de récurrence pour $\sigma'$ dont le nombre d'éléments du support est strictement inférieur à $m $, le nombre d'éléments du support de $\sigma $. On a ainsi une décomposition de $\sigma' $ en produit de cycles $(c_i)$ de supports 2 à 2 disjoints : $$\sigma' = c_r\cdot \ldots\cdot c_1 $$

D'après la propriété précédente,

$$\bigcup_{i=1}^r S(c_i)=S(c')=S' $$

Ainsi chaque $S(c_i)$ est inclus dans $S'$ et est par conséquent disjoints de $S(c)$$

On obtient donc une décomposition de $\sigma$ en produit de cycles de supports disjoints

$$\sigma = c_r\cdot \ldots\cdot c_1 \cdot c  $$

Ceci achève notre récurrence.

La démonstration précédente nous permet d'obtenir l'algorithme qui suit.

Algorithme de décomposition d'une permutation $\sigma $ en produit de cycles disjoints :

• (0) On pose $r=0$ et $S_0=S(\sigma)$.
• (1) Tant que $S_r$ n'est pas vide, on note $x$ le plus petit élément de $S_r$
• (a) $r$ augmente de 1
• (b) Soit $k_r$ le plus petit entier tel que $\sigma^{k_r}(x)=x$. On note $\gamma_r=\left(\begin{array}{ccccc} x & \sigma(x) & \ldots & \sigma^{k_r-1}(x) & \sigma^{k_r}(x) \end{array}\right ) $
• (c) On note $S_r=S_{r-1}\setminus S(\gamma_r)$
• (2) On a la décomposition en cycles à supports disjoints : 
  $$\sigma= \gamma_r\cdot \ldots \cdot \gamma_1$$

Exemple. 

Par exemple considérons la permutation 

$$\sigma =\left(\begin{array}{ccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 1 & 4 & 6 & 5 & 7 & 3 & 2 \end{array} \right)  $$

Le support de $\sigma $ est 

$$S_0=\left\{ 2, 3, 4, 5, 6, 7, \right\} $$

car seul $1$ est fixé par $\sigma $.

Le plus petit élément de $S_0$ est $2$. On a $\sigma(2)=4 $, $\sigma(4)=5 $, $\sigma(5)=7 $ et $\sigma(7)=2 $. Cela nous donne un cycle 

$c_1=\left(\begin{array}{cccc} 2& 4 & 5 & 7 \end{array}\right) $

Maintenant retirons des éléments de $S_0$ les éléments du support de $c_1$. On obtient l'ensemble $S_1=\left\{ 3, 6 \right\} $ dont le plus petit élément est $3$. On a $\sigma(3)=6 $ et $\sigma(6)=3 $. Cela nous donne un cycle $c_2=\left(\begin{array}{cc} 3& 6 \end{array}\right) $ 

 

L'ensemble $S_1$ privé des éléments du support de $c_1$ étant vide, on en déduit que $\sigma = c_2\cdot c_1 $. 

Dans un article ultérieur, je présenterai un code python permettant d'effectuer ce travail.

Décomposition d'une permutation en produit de transpositions

Propriété 4.

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

Alors il existe un entier $r$ strictement positif, et $r$ transpositions $\tau_1,\ldots,\tau_r $ tels que 

$$\sigma=\tau_r\cdot \ldots \cdot \tau_1 $$ 

Démonstration. 

(1) Supposons dans un premier temps que $\sigma $ est un cycle. 

Alors $\sigma=(\begin{array}{ccccc} a_1 & a_2 & \ldots & a_{k-1} & a_k \end{array}) $ où les $a_i $ sont des éléments de $E_n $. $k\geq 2$ car $\sigma $ n'est pas l'identité.

Si $k=2$, $\sigma$ est une transposition donc le résultat est démontré.

Supposons que pour un $k$ donné, toute cycle d'ordre $k$ se décompose en un produit de $m$ transpositions, et montrons que si un cycle est d'ordre $k+1$, il se décompose encore en cycle.

Prenons $\sigma=(\begin{array}{ccccc} a_1 & a_2 & \ldots & a_{k} & a_{k+1} \end{array}) $. Notons $\sigma'=\sigma \cdot (\begin{array}{cc} a_k & a_{k+1} \end{array})$. 

Alors 

• $\sigma'(a_k)=\sigma(a_{k+1})=a_{1} $ 
• $\sigma'(a_i)=\sigma(a_i)=a_{i+1} $ si $1\leq i \leq k-1$ 
• $\sigma'(a_{k+1})=\sigma(a_k)=a_{k+1}$ 
• $\sigma'(x)=\sigma(x)=x $ si $x\not \in\left\{a_1,\ldots,a_r \right\} $

On en déduit que $\sigma'=(\begin{array}{ccccc} a_1 & a_2 & \ldots & a_{k-1} & a_k \end{array}) $. C'est un cycle d'ordre $k$ donc d'après notre hypothèse de récurrence, il existe $m$ transpositions $t_1,\ldots,t_m $ tels que 

$$\sigma'=t_m\cdot \ldots \cdot t_1 $$

Ainsi $$\sigma=t_m\cdot \ldots \cdot t_1\cdot (\begin{array}{cc} a_k & a_{k+1} \end{array})^{-1}=c_m\cdot \ldots \cdot c_1\cdot (\begin{array}{cc} a_k & a_{k+1} \end{array}) $$

est un produit de transpositions.

On a montré par récurrence que tout cycle se décompose en un produit de transpositions.

(2) Supposons maintenant que $\sigma$ n'est pas un cycle. D'après la propriété précédente, $\sigma$ peut s'écrire 

$$\sigma = c_r\cdot \ldots \cdot c_1 $$

où $c_1,\ldots,c_r $ sont des cycles. 

En faisant une récurrence sur $r$, on obtient que $\sigma$ est bien un produit de transpositions.

Et après

Remarques. 

(1) La décomposition en transposition n'est pas unique. Par exemple : $(\begin{array}{cc} 1 & 2  \end{array})\cdot (\begin{array}{cc} 1 & 2  \end{array})\cdot (\begin{array}{cc} 1 & 2  \end{array}) = (\begin{array}{cc} 1 & 2  \end{array})$

(2) Nous verrons dans un prochain article  que la parité du nombre de transpositions dans la décomposition d'une permutation est un inavriant, c'est la signature de la permutation.