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.

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.

Groupes (0) : Définitions et exemples

Dans ce billet, nous introduisons les groupes à l'aide de quelques exemples simples.

Définitions

Définition 1. 

Soit $E$ un ensemble. Soit $\ast $ une application de $E\times E $ vers $E$, c'est-à-dire telle que $(x,y)\mapsto x\ast y $ avec $x\ast y\in E $.

Alors on dit que $\ast$ est une loi interne sur $E$.

Exemple 1. L'addition $+$ est une  loi interne sur $\mathbb N$ car la somme $x+y$ de deux entiers positifs ou nuls $x$ et $y$ est un entier positif ou nul.

Exemple 2. Si $\overrightarrow u$ et  $\overrightarrow v$ sont des vecteurs de l'espace, c'est-à-dire des élément de $\mathbb R^3 $, alors leur produit vectoriel $\overrightarrow u \wedge \overrightarrow v $ est un élément de $\mathbb R^3 $ défini par

$$\begin{pmatrix} u_1\\ u_2 \\ u_3  \end{pmatrix} \wedge \begin{pmatrix} v_1\\ v_2 \\ v_3 \end{pmatrix} = \begin{pmatrix} u_2v_3 -u_3v_2\\ u_3v_1-u_1v_3 \\ u_1v_2-u_2v_1 \end{pmatrix}$$

Le produit vectoriel $\wedge $ définit une loi interne sur $\mathbb R^3 $.

Définition 2.

Soit $G$ un ensemble sur lequel il existe une loi interne $\ast$ sur $G$. 

$(G,\ast)$ est appelé groupe si les 3 conditions suivantes sont vérifiées :

1.  [existence de l'élément neutre] Il exite un élément $e$ dans $G$ tel que pour tout élément $g $ de $G$ : $e\ast g = g \ast e = g$. $e$ est appelé un élément neutre de $G$.
2. [existence de l'inverse] Tout élément de $g$ posssède un inverse pour la loi $\ast $ : pour tout $g\in G$, il existe un élément $h$ tel que $gh=hg=e $
3. [associativité] $\ast$ est une loi associative, c'est-à-dire : pour tous $g,h,k$ dans $G$, on a l'égalité $g(hk)=(gh)k $. On notera sans confusion possible $ghk$ ce produit.
   
   Si de plus,
4. [commutativité] Pour tous $g,h$ dans $G$, on a $gh=hg$,

  alors on dit que $G$ est un groupe commutatif.

Remarque. Il ne peut y avoir qu'un seul élément neutre $e$ dans un groupe. 

En effet, pour tout élément neutre $e'$, on a $e'=ee' $ car $e$ est neutre et $ee'=e $ car $e'$ est neutre, donc $e=e' $. 

Exemples simples

Le groupe $\mathbb Z$

$(\mathbb N,+)$ n'est pas un groupe car à part $0$ qui est l'élément neutre, aucun élément n'a d'inverse pour l'opération $+$. Attention, ici l'inverse pour $+$ signifie l'opposé.  

L'axiome (1) et (3) sont vérifiés, mais pas l'axiome (2) donc $\mathbb N $ n'est pas un groupe.

$(\mathbb Z, +)$ est un groupe car maintenant tous les axiomes sont vérifiés. L'axiome (4) en fait un groupe commutatif.

On peut aussi regarder $\mathbb Z$ muni de la loi $\times $. $1$ est l'élément neutre pour la multiplication. Mais par exemple le nombre $2$ n'a pas d'inverse dans $\mathbb Z $ pour la multiplication : il n'existe pas d'entier relatif $a$ tel que $2a=1$. 

Donc $(\mathbb Z,\times) $ n'est pas un groupe. 

$\mathbb Q$

$\mathbb Q $ muni de la loi $+$ est un groupe commutatif.

Muni de la loi $\times$, $\mathbb Q $ n'est pas un groupe car $0$ n'a pas d'inverse.

Si l'on retire de $\mathbb Q $ le seul élément  $0$ non inversible pour $\times $, on obtient l'ensemble que l'on note souvent $\mathbb Q^\ast=\{x\in \mathbb Q | x\neq 0 \}=\mathbb Q\setminus \{0\} $. Alors $(\mathbb Q^\ast,\times) $ est un groupe commutatif.

Rotations de centre $O$

Etant donné un plan orienté et un point $O$, notons $\mathcal R_O $ l'ensemble des rotations de centre $O$.

Un élément de $\mathcal R_O $ est caractérisé par un réel $\theta $ (l'angle de la rotation), on peut le noter $r_\theta $. Ainsi $\mathcal R_O=\left\{r_\theta | \theta\in\mathbb R \right\} $.

La composée de deux rotations $r_\theta $ et $r_\phi $ est la rotation : $r_\theta\circ r_\phi=r_{\theta+\phi} $ est un élément de $\mathcal R_O $ aussi égal à $r_\phi\circ r_\theta $. $\circ $ est donc une loi interne commutative.

La rotation d'angle $0$, $r_0$ est un élément neutre pour $(\mathcal R_O,\circ) $, et tout $r_\theta $, possède un inverse $r_{-\theta} $.

Enfin l'associativité de $(\mathcal R_O,\circ) $ découle de celle de $(\mathbb R,+) $

$$(r_\psi \circ r_\phi) \circ r_\theta=r_{\psi+\phi}\circ r_\theta =r_{(\psi+\phi)+\theta}=r_{\psi+(\phi+\theta)}=r_{\psi}\circ(r_{\phi+\theta})=r_{\psi}\circ(r_{\phi}\circ r_\theta) $$

On en déduit que $(\mathcal R_O,\circ) $ est un groupe commutatif.

$\mathbb U $

Notons $\mathbb U $ l'ensemble des nombres complexes de module 1.

Alors $(\mathbb U,\times) $ est un groupe commutatif. 

Nous utiliseraons la propriété suivante.

Propriété A.

Si $z$ et $w$ sont des nombres complexes, alors $\left| zw \right|=|w| \times |z| $.

Ainsi si deux nombres ont pour module 1, alors leur produit est aussi de module 1.

 $\times  $ définit donc une loi interne sur  $\mathbb U$.

Les axiomes (1), (3) et (4) qui sont vrais sur $\mathbb C $ restent vrais sur $\mathbb U $. 

Montrons que l'axiome (2) est vérifié également. Pour commencer, tous les éléments $z$ de $\mathbb U  $ possèdent un inverse $\frac 1 z $ dans $\mathbb C $ car le module de 0 est 0 (et seul 0 n'est pas inversible pour la multiplication dans $\mathbb C $). De plus l'inverse d'un élément de module 1 est aussi de module 1. Cela provient aussi de la propriété A avec $w=\frac 1 z$, on a en effet :

$$\left| z \times \frac 1 z\right| =|z|\times  \left| \frac 1 z \right| $$

d'où $1=1\times \left| \frac 1 z \right|  $, qui donne $1= \left| \frac 1 z \right|$. 

L'inverse $\frac  1 z$ de $z$ est donc dans  $\mathbb S^1  $  si $z$ ets dans $\mathbb S^1  $.

$z$ est inversible pour la multiplication dans $\mathbb C $ si $z\neq 0$. 

On peut en déduire que $\left( \mathcal U,\times\right)$ est un groupe. C'est en fait un sous-groupe de $(\mathbb C,\times) $ (nous verrons cette notion plus tard).

 

Le groupe $GL_n$

On notera $GL_n$ l'ensemble des matrices $n\times n $ de déterminant non-nul. C'est le groupe linéaire. On pourra supposer dans cet article que les coeeficients des matrices sont rééls. (Nous parlerons donc du groupe linéaire réel).

Alors si $\cdot $ dénote le produit matriciel, $(GL_n ,\cdot) $ forme un groupe appelé groupe linéaire. Ce groupe n'est pas commutatif.

La démonstration de ce résultat se fait de manière analogue à la démonstration de l'exemple précédent sur $\mathbb S^1 $. On peut reprendre exactement la même démonstration en remplaçant le module par le déterminant. 

En effet, on a la propriété suivante :

Propriété B. 

(B1) Une matrice carrée A est inversible si son déterminant est non-nul

(B2) Si A et B sont deux matrices de tailles $n\times n $, alors 

$$\det(A\cdot B)=\det(A)\times \det(B) $$

Une conséquence directe de (B2) est que $\det\left(A\cdot A^{-1}\right)=\det(A)\times \det\left(A^{-1}\right) $.

Comme $A\cdot A^{-1}=I_n$ (la matrice identité $n\times n$), et comme $\det(I_n)=1 $, on a $\det\left(A^{-1}\right)\neq 0 $ et en particulier

$$(1)\ \ \ \frac{1}{\det A}=\det\left(A^{-1}\right)  $$

L'ensemble $O(n)=\left\{A\in GL_n  | \det(A)=1 \textrm{ou}\ -1\right\} $ est appelé groupe orthogonale. C'est un sous-groupe de $GL_n$ pour la loi $\cdot $ autrement dit un groupe inclus dans $GL_n$ (qui est lui-même un groupe pour $\cdot$). 

En effet, il suffit pour cela de vérifier que tout élément de $O(n)$ a son inverse dans $O(n)$. D'après l'égalité (1), c'est clair car 1 et -1 sont leur propres inverses.

Le groupe des bijections 

L'ensemble des bijections d'un ensemble dans lui-même est un groupe. Pour l'ensemble à $n$ élément $\left\{1,2,\ldots,n\right\}$, ce groupe est l'ensemble des permutations de $n$ éléments. 

Ensuite

Pour continuer la série d'articles sur les groupes, on pourra lire [(G1) : Sous-groupes (Définitions et exemples)].