Dans l’intégralité de cet article, vous travaillez sur des permutations d’un ensemble fini $E$ qui contient au moins deux éléments.
Comment décomposer une permutation en produit de transpositions ?
Soit $\sigma$ la permutation suivante de l’ensemble $E=\llbracket 1, 9\rrbracket$ :
\sigma = \begin{pmatrix}
1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9\\
2 & 4 & 7 & 5 & 8 & 6 & 9 & 1 & 3
\end{pmatrix}.Décomposez d’abord la permutation en produit de cycles à supports disjoints
Vous constatez que $\sigma$ envoie $1$ sur $2$ puis $2$ sur $4$ puis $4$ sur $5$ puis $5$ sur $8$ et $8$ sur $1$ cela forme le premier cycle noté $(1\ 2\ 4\ 5\ 8).$
Ensuite, $\sigma$ envoie $3$ sur $7$ puis $7$ sur $9$ et $9$ sur $3$ ce qui forme un second cycle $(3\ 7\ 9).$
Vous constatez que $6$ est le seul élément fixé par $\sigma$ puisque $\sigma(6)=6.$
Vous déduisez de cette analyse que :
\boxed{\sigma = (1\ 2\ 4\ 5\ 8)(3\ 7\ 9).}Décomposez chaque cycle en produit de transpositions
D’une part :
(1\ 2\ 4\ 5\ 8) = (1\ 2)(2\ 4)(4\ 5)(5\ 8).
D’autre part :
(3\ 7\ 9) = (3\ 7)(7\ 9).
Vous déduisez que $\sigma$ peut s’écrire comme un produit de six transpositions :
\boxed{\sigma = (1\ 2)(2\ 4)(4\ 5)(5\ 8)(3\ 7)(7\ 9).}Sur les effets de la multiplication à gauche d’une permutation par une transposition
Dans le cas général, une permutation s’écrit comme un produit de cycles à supports disjoints.
Note. Dans le cas de l’identité, elle est écrite comme un produit vide de cycles à supports disjoints.
Soit $r$ un entier naturel et soient $c_1, \dots, c_r$ des cycles à supports disjoints et $\tau$ une transposition. Vous vous intéressez à déterminer une écriture en produit de cycles à supports disjoints de la permutation $\sigma = \tau c_1\cdots c_r.$
Note. Dans le cas où $r=0$ le produit $c_1\cdots c_r$ est vide et il est égal à l’identité.
Cas n°1 : supports totalement disjoints et commutation
Vous supposez que, pour tout $i\in\llbracket 1, r\rrbracket$ le support de $\tau$ n’a aucun élément en commun le support du cycle $c_i.$ Alors, pour tout $i\in\llbracket 1, r\rrbracket$ la transposition $\tau$ commute avec $c_i.$ Le produit $\sigma = \tau c_1\cdots c_r$ est déjà un produit de cycles à supports disjoints, la transposition $\tau$ étant un cycle de longueur $2.$
Cas n°2 : fusion/insertion ou rupture de cycle
Supposez qu’il existe un entier $i\in\llbracket 1, r\rrbracket$ tel que le support de $\tau$ et le cycle $c_i$ aient au moins un élément en commun.
Premier cas : fusion. Le support de $\tau$ a exactement un élément $a\in E$ en commun avec le cycle $c_i.$ Il existe un élément $b$ de $E$ distinct de $a$ tel que $\tau = (a\ b).$ Le cycle $c_i$ peut s’écrire en commençant par $a$ et son support ne contient pas $b.$ En notant $p$ la longueur du cycle $c_i$ il existe $(d_1,\dots, d_{p-1})\in E^{p-1}$ tel que $c_i = (a\ d_1 \cdots d_{p-1}).$
Comme les supports des cycles $c_1,\dots,c_r$ sont deux à deux disjoints, deux sous-cas peuvent se présenter.
Premier sous-cas (fusion) : il existe un unique entier $j\neq i$ compris entre $1$ et $r$ tel que l’élément $b$ appartienne au support du cycle $c_j.$ Le cycle $c_j$ peut s’écrire en commençant par $b$ et son support ne contient pas $a.$ En notant $q$ la longueur du cycle $c_j$ il existe $(e_1,\dots,e_{q-1})\in E^{q-1}$ tel que $c_j = (b\ e_1 \cdots e_{q-1}).$
Vous passez au calcul de $\tau \sigma$ en utilisant la commutation des cycles $c_i$ et $c_j$ avec les autres, ce qui fournit :
\begin{align*}
\tau \sigma &= \tau c_1 \cdots c_r \\
&= \tau c_i c_j \prod_{k\notin \{i, j\}} c_k\\
&= (a\ b) (a\ d_1 \cdots d_{p-1}) (b\ e_1 \cdots e_{q-1}) \prod_{k\notin \{i, j\}} c_k\\
&= (b\ a)(a\ d_1 \cdots d_{p-1}) (b\ e_1 \cdots e_{q-1}) \prod_{k\notin \{i, j\}} c_k\\
&= (b\ a\ d_1 \cdots d_{p-1}) (b\ e_1 \cdots e_{q-1}) \prod_{k\notin \{i, j\}} c_k\\
&= (a\ d_1 \cdots d_{p-1}\ b) (b\ e_1 \cdots e_{q-1}) \prod_{k\notin \{i, j\}} c_k\\
&= (a\ d_1 \cdots d_{p-1}\ b\ e_1 \cdots e_{q-1}) \prod_{k\notin \{i, j\}} c_k\\
\end{align*}Les cycles $c_i$ et $c_j$ ont fusionné et l’écriture obtenue de $\tau\sigma$ est bien un produit de cycles à supports disjoints.
Second sous-cas (insertion) : pour tout entier $j\neq i$ compris appartenant à $\llbracket 1, r\rrbracket$ l’élément $b$ n’appartient pas au support du cycle $c_j.$
Vous procédez au calcul de $\sigma\tau$ comme précédemment. Cette fois-ci, vous allez commuter $c_i$ avec les autres cycles et le positionner à droite de la transposition $\tau$ ce qui donne :
\begin{align*}
\tau \sigma &= \tau c_1 \cdots c_r \\
&= \tau c_i \prod_{j\neq i} c_j\\
&= (a\ b) (a\ d_1 \cdots d_{p-1}) \prod_{j\neq i} c_j\\
&= (b\ a) (a\ d_1 \cdots d_{p-1}) \prod_{j\neq i} c_j\\
&= (b\ a\ d_1 \cdots d_{p-1}) \prod_{j\neq i} c_j.
\end{align*}L’élément $b$ a été inséré dans le cycle $c_i$ et l’écriture obtenue de $\sigma\tau$ est bien un produit de cycles à supports disjoints.
Second cas : rupture de cycle. Le support de $\tau$ a exactement deux éléments en commun avec le cycle $c_i.$ Vous effectuez la commutation du cycle $c_i$ avec les autres cycles et positionnez $c_i$ immédiatement à droite de la transposition $\tau.$
\begin{align*}
\tau \sigma &= \tau c_1 \cdots c_r \\
&= \tau c_i \prod_{j\neq i} c_j.
\end{align*}Il existe deux entiers naturels $p$ et $q$ de sorte qu’il existe $p+q$ éléments de $E$ notés $d_1,\cdots, d_p, e_1, \dots, e_q$ qui vérifient $c_i = (a\ d_1\ \cdots d_p\ b\ e_1\ \cdots e_q)$ et ainsi :
\begin{align*}
\tau \sigma &= \tau c_1 \cdots c_r \\
&= \tau c_i \prod_{j\neq i} c_j\\
&= (a\ b)(a\ d_1\ \cdots d_p\ b\ e_1\ \cdots e_q) \prod_{j\neq i} c_j\\
&= (a\ b)(a\ d_1\ \cdots d_p\ b)(b\ e_1\ \cdots e_q) \prod_{j\neq i} c_j\\
&= (a\ b)(b\ a\ d_1\ \cdots d_p)(b\ e_1\ \cdots e_q) \prod_{j\neq i} c_j\\
&= (a\ b)(b\ a)(a\ d_1\ \cdots d_p)(b\ e_1\ \cdots e_q) \prod_{j\neq i} c_j\\
&= (a\ b)(a\ b)(a\ d_1\ \cdots d_p)(b\ e_1\ \cdots e_q) \prod_{j\neq i} c_j\\
&=(a\ d_1\ \cdots d_p)(b\ e_1\ \cdots e_q) \prod_{j\neq i} c_j.
\end{align*}Il y a eu rupture du cycle $c_i$ et l’écriture obtenue de $\tau\sigma$ est encore un produit de cycles à supports disjoints.
Comment, à partir d’un produit de transpositions, obtenir une écriture en produit de cycles à supports disjoints ?
Vous partez de la droite et vous multipliez à gauche par les transpositions qui apparaissent, en traitant les cas de fusion ou de rupture.
Soit $\sigma = (1\ 4)(3\ 1)(4\ 3)(5\ 3)(6\ 1)(8\ 4)(3\ 9).$
Le produit des trois transpositions $(6\ 1)(8\ 4)(3\ 9)$ est un produit de cycles à supports disjoints.
Cependant, le produit $(5\ 3)(6\ 1)(8\ 4)(3\ 9)$ ne l’est pas puisque $3$ apparaît deux fois. Vous êtes dans le cas ici d’une fusion. En effet :
\begin{align*}
(5\ 3)(6\ 1)(8\ 4)(3\ 9) &= (5\ 3)(6\ 1)(3\ 9)(8\ 4)\\
&= (5\ 3)(3\ 9)(6\ 1)(8\ 4)\\
&= (5\ 3\ 9)(6\ 1)(8\ 4).
\end{align*}La permutation $(5\ 3\ 9)(6\ 1)(8\ 4)$ est un produit de cycles à supports disjoints mais $(4\ 3)(5\ 3\ 9)(6\ 1)(8\ 4)$ ne l’est pas puisque $3$ et $4$ sont répétés. Vous êtes encore dans un cas de fusion. En effet :
\begin{align*}
(4\ 3)(5\ 3\ 9)(6\ 1)(8\ 4) &= (4\ 3)(5\ 3\ 9)(8\ 4)(6\ 1) \\
&= (4\ 3)(3\ 9\ 5)(4\ 8)(6\ 1) \\
&= (4\ 3\ 9\ 5)(4\ 8)(6\ 1) \\
&= (3\ 9\ 5\ 4)(4\ 8)(6\ 1) \\
&= (3\ 9\ 5\ 4\ 8)(6\ 1).
\end{align*}La permutation $(3\ 9\ 5\ 4\ 8)(6\ 1)$ est un produit de cycles à supports disjoints mais $(3\ 1)(3\ 9\ 5\ 4\ 8)(6\ 1)$ ne l’est pas puisque $3$ et $1$ sont répétés. Vous êtes dans un cas de fusion. En effet :
\begin{align*}
(3\ 1)(3\ 9\ 5\ 4\ 8)(6\ 1) &= (3\ 1)(3\ 9\ 5\ 4\ 8)(1\ 6) \\
&= (1\ 3)(3\ 9\ 5\ 4\ 8)(1\ 6) \\
&= (1\ 3\ 9\ 5\ 4\ 8)(1\ 6) \\
&= (3\ 9\ 5\ 4\ 8\ 1)(1\ 6) \\
&= (3\ 9\ 5\ 4\ 8\ 1\ 6).
\end{align*}Enfin, la permutation $(3\ 9\ 5\ 4\ 8\ 1\ 6)$ est bien considérée comme un produit de cycles à supports disjoints (avec un seul cycle) mais $ (1\ 4)(3\ 9\ 5\ 4\ 8\ 1\ 6)$ ne l’est pas puisque $1$ et $4$ sont répétés. Cette fois, vous êtes dans un cas de rupture de cycle :
\begin{align*}
(1\ 4)(3\ 9\ 5\ 4\ 8\ 1\ 6) &= (1\ 4)(4\ 8\ 1\ 6\ 3\ 9\ 5) \\
&= (1\ 4)(4\ 8\ 1)(1\ 6\ 3\ 9\ 5) \\
&= (1\ 4)(1\ 4\ 8)(1\ 6\ 3\ 9\ 5) \\
&= (1\ 4)(1\ 4)(4\ 8)(1\ 6\ 3\ 9\ 5) \\
&= (4\ 8)(1\ 6\ 3\ 9\ 5).
\end{align*}Finalement vous obtenez $\sigma$ en produit de cycles à supports disjoints :
\boxed{\sigma = (1\ 4)(3\ 1)(4\ 3)(5\ 3)(6\ 1)(8\ 4)(3\ 9) = (4\ 8)(1\ 6\ 3\ 9\ 5).}Prolongement
Vous souhaitez voir comment l’effet de la multiplication à gauche par une transposition sur une permutation quelconque permet de trouver une définition de la signature d’une permutation, puis de montrer que la signature est un morphisme de groupes allant de l’ensemble des permutations de $E$ (muni de la composition) vers l’ensemble $\{-1,1\}$ muni de la multiplication dans les entiers relatifs ? Allez lire le contenu rédigé dans l'article 386.
Partagez maintenant !
Aidez vos amis à découvrir cet article et à mieux comprendre le sujet.
Aidez-moi sur Facebook !
Vous appréciez cet article et souhaitez témoigner du temps que j'y ai passé pour le mettre en œuvre. C'est rapide à faire pour vous et c'est important pour moi, déposez un j'aime sur ma page Facebook. Je vous en remercie par avance.
Lisez d'autres articles !
Parcourez tous les articles qui ont été rédigés. Vous en trouverez sûrement un qui vous plaira !