385. Effet d’une transposition sur la décomposition en cycles d’une permutation

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\comma$ puis $2$ sur $4\comma$ puis $4$ sur $5\comma$ 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, soient $c_1, \dots, c_r$ des cycles à supports disjoints et $\tau$ une transposition. Vous notez $\sigma = c_1\cdots c_r$ et vous vous intéressez à une écriture en produit de cycles à supports disjoints de la permutation $\tau\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 avec le support du cycle $c_i.$ Alors, pour tout $i\in\llbracket 1, r\rrbracket$ la transposition $\tau$ commute avec $c_i.$ Le produit $\tau\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 support du cycle $c_i$ aient au moins un élément en commun.

Premier cas : un seul élément en commun. Le support de $\tau$ a exactement un élément $a\in E$ en commun avec le support du 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$ appartenant à $\llbracket 1, r\rrbracket$ l’élément $b$ n’appartient pas au support du cycle $c_j.$ Autrement dit, $b$ est un point fixe de $\sigma.$

Vous procédez au calcul de $\tau\sigma$ 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 $\tau\sigma$ 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 support du cycle $c_i$ : vous les notez $a$ et $b\comma$ de sorte que $\tau = (a\ b).$ 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,\dots, 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.

Note. Si $p=0\comma$ le « cycle » $(a)$ est l’identité : $a$ devient un point fixe de $\tau\sigma$ et ce facteur disparaît de l’écriture. Il en est de même pour $(b)$ si $q=0.$

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, d’insertion 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. Comme $5$ n’apparaît dans aucun des cycles $(6\ 1)\comma$ $(8\ 4)$ et $(3\ 9)\comma$ vous êtes ici dans le cas d’une insertion. 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. Comme $4$ et $3$ appartiennent à deux cycles différents, vous êtes 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. Comme $3$ et $1$ appartiennent à deux cycles différents, vous êtes encore 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. Comme $1$ et $4$ appartiennent au même cycle, vous êtes cette fois 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.

Pour en savoir davantage, allez lire le contenu rédigé dans l'article 386.