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.