Le groupe symétrique (1/2)

Exercice 1.
On considère la permutation \sigma suivante de {S_{12}} : {\sigma=\begin{pmatrix}1&2&3&4&5&6&7&8&9&10&11&12\cr6&12&1&10&9&11&4&3&2&7&8&5\end{pmatrix}}

  1. Décomposer {\sigma} en produits de cycles à supports disjoints.
  2. Décomposer {\sigma} en produits de transpositions.
  3. Quelle est la parité de {\sigma}?
  4. Calculer l’entier minimum {n} tel que {\sigma^n=\text{Id}}. Calculer {\sigma^{1999}}.

Cliquer ici pour voir (ou cacher) le corrigé

  1. On suit les “orbites” des éléments de {\{1,\ldots,12\}}, jusqu’à les avoir tous passé en revue.

    Ainsi {1} est envoyé sur {6}, qui est envoyé sur {11}, lui-même sur {8}, lui-même sur {3}, qui est enfin envoyé sur {1} : on obtient ainsi un premier cycle {(1,6,11,8,3)}.

    On passe ensuite à l’orbite de {2} et on trouve le cycle {(2,12,5,9)}.

    On vérifie enfin l’orbite de {4}, qui nous donne le cycle {(4,10,7)}.

    Ainsi {\sigma=\sigma_1\circ\sigma_2\circ\sigma_3}, avec {\begin{cases}\sigma_1=(1,6,11,8,3)\cr \sigma_2=(2,12,5,9)\cr \sigma_3=(4,10,7)\end{cases}}

  2. Il suffit de décomposer {\sigma_1,\sigma_2,\sigma_3} en produits de transpositions :{\begin{array}{rl}\sigma_1&=(1,6,11,8,3)=(1,6)\circ(6,11)\circ(11,8)\circ(8,3)\phantom{\biggl(}\\\sigma_2&=(2,12,5,9)=(2,12)\circ(12,5)\circ(5,9)\phantom{\biggl(}\\\sigma_3&=(4,10,7)=(4,10)\circ(10,7)\end{array}}On obtient une décomposition de {\sigma} : {\begin{array}{rl}\sigma=&(1,6)\circ(6,11)\circ(11,8)\circ(8,3)\circ(2,12)\\\\&\circ(12,5)\circ(5,9)\circ(4,10)\circ(10,7)\end{array}}
  3. {\sigma} est impaire (car décomposée en un nombre impair de transpositions).

    Une autre méthode consiste à écrire que la signature de la permutation {\sigma} est le produit de celles des cycles {\sigma_1}, {\sigma_2} et {\sigma_3}. Or la signature d’un cycle de longueur {m} est {(-1)^{m+1}}.

    Ainsi {\begin{cases}\varepsilon(\sigma_1)=(-1)^6=1\\\varepsilon(\sigma_2)=(-1)^5=-1\\\varepsilon(\sigma_3)=(-1)^4=1\end{cases}} puis {\varepsilon(\sigma)=\varepsilon(\sigma_1)\varepsilon(\sigma_2)\varepsilon(\sigma_3)=-1}.

  4. Pour tout entier {k}, on a {\sigma^k=\sigma_1^k\circ\sigma_2^k\circ\sigma_3^k}.

    Or un cycle {s} de longueur {m} est d’ordre {m} : il vérifie {s^n=\text{Id}\Leftrightarrow m\,|\,n}.

    Ainsi {\sigma^n=\text{Id}\Leftrightarrow\begin{cases}\sigma_1^n=\text{Id}\\\sigma_2^n=\text{Id}\\\sigma_3^n=\text{Id}\end{cases}\Leftrightarrow\begin{cases}5\,|\,n\\4\,|\,n\\3\,|\,n\end{cases}\Leftrightarrow 60\,|\,n}.

    Le plus petit entier {n} tel que {\sigma_n=\text{Id}} est donc {n=60}.

    On a {1999=60\cdot33+19}. On en déduit : {\sigma^{1999}=\sigma^{19}=\sigma_1^{19}\circ\sigma_2^{19}\circ\sigma_3^{19}}On simplifie grâce aux ordres respectifs de {\sigma_1,\sigma_2,\sigma_3} : {\begin{array}{rl}\sigma_1^{19}&=\sigma_1^{5\cdot3+4}=\sigma_1^4=(1,6,11,8,3)^4=(1,3,8,11,6)\\\\\sigma_2^{19}&=\sigma_1^{4\cdot4+3}=\sigma_1^3=(2,12,5,9)^3=(2,9,5,12)\\\\\sigma_3^{19}&=\sigma_1^{3\cdot6+1}=\sigma_1=(4,10,7)\end{array}}On en déduit finalement : {\sigma^{1999}=(1,3,8,11,6)\circ(2,9,5,12)\circ(4,10,7)}En d’autres termes : {\sigma^{1999}=\begin{pmatrix}1&2&3&4&5&6&7&8&9&10&11&12\cr3&9&8&10&12&1&4&11&5&7&6&2\end{pmatrix}}

Exercice 2.

  1. Quand une permutation {\sigma} commute-t-elle avec une tranposition {\tau=(i,j)} ?
  2. En déduire que si {n\ge3}, seule {\text{Id}} commute avec tous les éléments de {S_n}.
  3. Montrer que si {n\ge4}, seule {\text{Id}} commute avec toutes les permutations paires.

Cliquer ici pour voir (ou cacher) le corrigé

  1. On va montrer que : {\sigma\circ\tau=\tau\circ\sigma\Leftrightarrow\{\sigma(i),\sigma(j)\}=\{i,j\}}.

    • On suppose que {\sigma\circ\tau=\tau\circ\sigma}.

      Ainsi {\begin{cases}\sigma\circ\tau(i)=\tau\circ\sigma(i)\\\sigma\circ\tau(j)=\tau\circ\sigma(j)\end{cases}} donc {\begin{cases}\sigma(j)=\tau(\sigma(i))\\\sigma(i)=\tau(\sigma(j))\end{cases}}

      Les éléments {\sigma(i)\neq\sigma(j)} sont donc échangés par {\tau}.

      Cela signifie que {\{\sigma(i),\sigma(j)\}=\{i,j\}}.

    • Inversement, supposons {\{\sigma(i),\sigma(j)\}=\{i,j\}}.

      On a donc {\begin{cases}\sigma(i)=i\\\sigma(j)=j\end{cases}} ou {\begin{cases}\sigma(i)=j\\\sigma(j)=i\end{cases}}

      Ainsi {\begin{cases}\sigma(j)=\tau(\sigma(i))\\\sigma(i)=\tau(\sigma(j))\end{cases}} donc {\begin{cases}\sigma\circ\tau(i)=\tau\circ\sigma(i)\\\sigma\circ\tau(j)=\tau\circ\sigma(j)\end{cases}}

      De plus, soit {k\in\{1,2,\ldots,n\}\setminus\{i,j\}} donc invariant par {\tau}.

      On a {\sigma(k)\notin\{\sigma(i),\sigma(j)\}} donc {\sigma(k)} est invariant par {\tau}.

      Pour cet élément, on a alors : {\sigma\circ\tau(k)=\sigma(k)=\tau\circ\sigma(k)}.

      Ainsi {\sigma\circ\tau} et {\tau\circ\sigma} sont égales sur tout élément de {\{1,2,\ldots,n\}}.

  2. Dans cette question, on suppose {n\ge4}.

    Bien sûr {\text{Id}} commute avec tous les éléments de {S_n}.

    Inversement soit {\sigma\in S_n} telle que : {\forall\, s\in S_n,\sigma\circ s=s\circ\sigma}.

    Soient {i,j,k} distincts dans {\{1,2,\ldots,n\}} (possible car {n\ge3}).

    Par hypothèse {\sigma} commute avec les {\tau=(i,j)} et {\tau'=(i,k)}.

    D’après la question {(1)}, on a donc : {\begin{cases}\{\sigma(i),\sigma(j)\}=\{i,j\}\\ \{\sigma(i),\sigma(k)\}=\{i,k\}\end{cases}}

    Mais ce double résultat implique {\sigma(i)=i}.

    Comme {i} est quelconque, cela signifie que {\sigma=\text{Id}}.

  3. Bien sûr {\text{Id}} commute avec toutes les permutations paires.

    Réciproquement soit {\sigma} commutant avec les permutations paires de {\{1,2,\ldots,n\}}.

    En particulier {\sigma} commute avec tous les cycles de longueur {3}.

    Soit {c=(i,j,k)} un tel cycle, et soit {x\in\{\{1,2,\ldots,n\}\setminus\{i,j,k\}}.

    L’élément {x} est invariant par le cycle {c}.

    On a {\sigma\circ c(x)=c\circ\sigma(x)} donc {\sigma(x)=c(\sigma(x))}.

    Ainsi {\sigma(x)} est invariant par {c}, donc est distinct de {i,j,k}.

    Autrement dit l’ensemble des éléments invariants par {c} (c’est-à-dire le complémentaire de {\{i,j,k\}} dans {\{1,2,\ldots,n\}}) est stable par {\sigma}.

    Par passage au complémentaire, on en déduit que {\{i,j,k\}} est stable par {\sigma}.

    Donnons-nous maintenant {x,y,z,t} distincts dans {\{1,2,\ldots,n\}}.

    D’après ce qui précède, les ensembles {\{x,y,z\}}, {\{x,y,t\}} et {\{x,z,t\}} sont stables par {\sigma}.

    Il en est donc de même de leur intersection, c’est-à-dire de {\{x\}}.

    Ainsi {\sigma(x)=x} pour tout {x} de {\{1,2,\ldots,n\}}.

    En d’autres termes, {\sigma} est la permutation identité.

Exercice 3.
Soit n un entier supérieur ou égal à 2.

  1. Montrer que {S_n} est engendré par les transpositions {\tau_j=(1,j)} avec {2\le j\le n}.
  2. Décomposer {\sigma=\begin{pmatrix}1&2&3&4&5\cr4&5&2&1&3\end{pmatrix}} en produit de telles transpositions.
  3. Passer de {MERCI} à {CRIME} par échanges de deux lettres dont la première.

Cliquer ici pour voir (ou cacher) le corrigé

  1. Il s’agit de montrer que toute permutation {\sigma} de {\{1,2,\ldots,n\}} peut s’écrire au moins d’une manière comme un produit de transpositions {\tau_j}. Il suffit de le montrer quand {\sigma} est une transposition (car toute permutation est un produit de transpositions quelconques).

    On se donne {i\lt j} dans {\{1,2,\ldots,n\}}, et {\sigma=(i,j)}.

    Il n’y a rien à démontrer si {i=1}. On suppose donc {2\le i\lt j}.

    On constate effectivement que : {\begin{array}{rl}\sigma&=(i,j)=(1,j)\circ(1,i)\circ(1,j)\\\\&=(1,i)\circ(1,j)\circ(1,i)\end{array}}Le fait qu’il y ait deux manières différentes d’écrire {\sigma} peut s’avérer utile pour simplifier la décomposition d’une permutation (on en voit un exemple dans la question suivante).

  2. On a la décomposition : {\begin{array}{rl}\sigma&=\begin{pmatrix}1&2&3&4&5\cr4&5&2&1&3\end{pmatrix}=(1,4)\circ(2,5,3)\\\\&=(1,4)\circ(2,5)\circ(3,5)\end{array}}On décompose les deux dernières transpositions comme vu dans la question {(1)}, et en écrivant au mieux ces décompositions pour avoir la simplification {(1,5)\circ(1,5)=\text{Id}} : {\begin{array}{rl}\sigma&=(1,4)\circ(1,5)\circ(1,2)\circ(1,5)\circ(1,5)\circ(1,3)\circ(1,5)\\\\&=(1,4)\circ(1,5)\circ(1,2)\circ(1,3)\circ(1,5)\end{array}}
  3. On passe du mot {MERCI} au mot {CRIME} par la permutation {\sigma} appliquée à la liste ordonnée des cinq lettres du mot initial.

    Voici les étapes (on a souligné la lettre à échanger avec la première lettre) : {\begin{matrix}MERC\underline{I} & IE\underline{R}CM & R\underline{E}ICM & ERIC\underline{M} & MRI\underline{C}E & CRIME\end{matrix}}

Exercice 4.
Soit n un entier supérieur ou égal à 2.

  1. Montrer que {S_n} est engendré par les transpositions {\tau_j=(j,j+1)}.
  2. Décomposer {\sigma=\begin{pmatrix}1&2&3&4&5\cr4&5&2&1&3\end{pmatrix}} en produit de telles transpositions.
  3. Passer de {MERCI} au mot {CRIME} par des échanges de lettres contiguës :

    • Par une méthode s’appuyant sur la question précédente.
    • Par une méthode directe. En déduire une nouvelle réponse à la question {(2)}.

Cliquer ici pour voir (ou cacher) le corrigé

  1. Il s’agit de montrer que toute permutation {\sigma} de {\{1,2,\ldots,n\}} peut s’écrire au moins d’une manière comme un produit de transpositions {\tau_j}. Il suffit de le montrer quand {\sigma} est une transposition (car toute permutation est un produit de transpositions quelconques).

    On se donne donc {i\lt j} de {\{1,2,\ldots,n\}}, et {\sigma=(i,j)}.

    Si {j=i+1}, il n’y a rien à démontrer. On suppose donc {j\ge i+2}.

    On constate effectivement que : {\begin{array}{rl}\sigma&=(i,i+1)\circ(i+1,i+2)\circ\cdots\circ(j-2,j-1)\circ(j-1,j)\\\\&\qquad\circ(j-2,j-1)\cdots\circ(i+1,i+2)\circ(i,i+1)\\\\&=\tau_{i}\circ\tau_{i+1}\circ\cdots\circ\tau_{j-2}\circ\tau_{j-1}\circ\tau_{j-2}\circ\cdots\tau_{i+1}\circ\tau_{i}\end{array}}

  2. On décompose d’abord {\sigma} en produits de cycles à supports disjoints : {\begin{array}{rl}\sigma&=\begin{pmatrix}1&2&3&4&5\cr4&5&2&1&3\end{pmatrix}\\\\&=(1,4)\circ(2,5,3)=(1,4)\circ(5,3,2)\end{array}} On décompose le deuxième cycle en deux transpositions : {\sigma=(1,4)\circ(3,5)\circ(2,3)}On décompose alors chaque transposition comme vu dans la question {(1)} : {\begin{array}{rl}\sigma&=(1,2)\circ(2,3)\circ(3,4)\circ(2,3)\circ(1,2)\\\\&\circ(3,4)\circ(4,5)\circ(3,4)\circ(2,3)\end{array}}Remarque : on a remplacé le cycle {(2,5,3)} par son écriture équivalente {(5,3,2)} pour minimiser les écarts entre éléments à échanger donc le nombre final de transpositions.
    • On passe de {MERCI} à {CRIME} par la permutation {\sigma} sur les cinq lettres du mot initial.

      Voici donc les différentes étapes (on a souligné à chaque fois les deux lettres à échanger) :
      {\begin{matrix}M\underline{ER}CI & MR\underline{EC}I & MRC\underline{EI} & MR\underline{CI}E & \underline{MR}ICE\\\Rightarrow&R\underline{MI}CE & RI\underline{MC}E & R\underline{IC}ME & \underline{RC}IME & CRIME\end{matrix}}

    • Il est possible de le faire en {7} étapes au lieu de {9} : {\begin{matrix}ME\underline{RC}I & M\underline{EC}RI & \underline{MC}ERI & CM\underline{ER}I\\\Rightarrow & C\underline{MR}EI & CRM\underline{EI} & CR\underline{MI}E & CRIME<br /> \end{matrix}}Cette méthode, qui “remonte” {C}, {R}, puis {I} vers le début est beaucoup plus naturelle.

      Pour ce qui est de notre exemple, elle montre qu’une autre décomposition de {\sigma} est :{\begin{array}{rl}\sigma=&(3,4)\circ(4,5)\circ(2,3)\circ(3,4)\\\\&\circ(1,2)\circ(2,3)\circ(3,4)\end{array}}

Exercice 5.
Soit n un entier supérieur ou égal à 3.

  1. On note {c} la permutation circulaire définie par : {c=\begin{pmatrix}1&2&\cdots&n-1&n\\ 2&3&\cdots&n&1\end{pmatrix}}Montrer que {S_n} est engendré par {c} et par la transposition {\tau=(1,2)}.
    Indication: on utilisera le résultat de la question {(1)} de l’exercice précédent.
  2. On veut passer du mot {MERCI} au mot {CRIME} uniquement
    par des rotations du mot à droite ou des échanges des deux premières lettres.

    • Donner une solution utilisant le résultat la question {(2)} de l’exercice précédent.
    • Imaginer une solution directe, nécessitant beaucoup moins d’étapes. Commenter.

Cliquer ici pour voir (ou cacher) le corrigé

  1. Comme l’indication le suggère, il suffit de prouver que toute transposition {(i,i+1)} de deux éléments consécutifs s’écrit comme une composition utilisant exclusivement le cycle {c} (et ses puissances) et la transposition {\tau=(1,2)}.

    On note que {s=c^{1-i}=c^{n+1-i}} commence par envoyer {i} et {j} sur {1} et {2}.

    Cette permutation décale en effet de {n+1-i} positions “vers la droite” : {s=c^{1-i}=\begin{pmatrix}1&2&\cdots&i-1&i&i+1&\cdots&n\cr n+2-i&n+3-i&\cdots&n&1&2&\cdots&n+1-i\end{pmatrix}}On applique {\tau} pour échanger {1} et {2} : {\tau\,\circ\,c^{n+1-i}=\begin{pmatrix}1&\cdots&i-1&i&i+1&i+2&\cdots&n\cr n+2-i&\cdots&n&2&1&3&\cdots&n+1-i\end{pmatrix}}On applique alors {s^{-1}=c^{i-1}} pour ramener les éléments dans leurs positions initiales (sauf les éléments {i} et {i+1} qui sont donc échangés).

    Voici tout d’abord {s^{-1}} (décalage de {i-1} positions “vers la droite”) : {s^{-1}=c^{i-1}=\begin{pmatrix}1&2&\cdots&n+1-i&n+2-i&\cdots&n-1&n\cr i&i+1&\cdots&n&1&\cdots&i-2&i-1\end{pmatrix}}On en déduit effectivement :{\begin{array}{rl}s^{-1}\circ\,\tau\,\circ s&=\begin{pmatrix}1&\cdots&i-1&i&i+1&i+2&\cdots&n\cr1&\cdots&i-1&i+1&i&i+2&\cdots&n\end{pmatrix}\\\\&=(i,i+1)\end{array}}

  2. On reprend les notations de l’exercice précédent.

    • On rappelle l’égalité : {\begin{array}{rl}\sigma=&(1,2)\circ(2,3)\circ(3,4)\circ(2,3)\circ(1,2)\\\\&\circ(3,4)\circ(4,5)\circ(3,4)\circ(2,3)\end{array}}On note encore {\tau=(1,2)} et : {s=\begin{pmatrix}1&2&3&4&5\cr2&3&4&5&1\end{pmatrix}=(1,2,3,4,5)}On sait maintenant que, pour tout {i} : {(i,i+1)=\sigma^{i-1}\circ\tau\circ\sigma^{6-i}}On en déduit, compte tenu de {\sigma^5=\text{Id}} :
      {\begin{array}{rl}\sigma&=\tau\circ\sigma\circ\tau\circ\sigma^{4}\circ\sigma^{2}\circ\tau\circ\sigma^{3}\circ\sigma\circ\tau\circ\sigma^{4}\\\\&\qquad\circ\tau\circ\sigma^{2}\circ\tau\circ\sigma^{3}\circ\sigma^{3}\circ\tau\circ\sigma^{2}\circ\sigma^{2}\circ\tau\circ\sigma^{3}\circ\sigma\circ\tau\circ\sigma^{4}\\\\&=\tau\circ\sigma\circ\tau\circ\sigma\circ\tau\circ\sigma^{4}\circ\tau\circ\sigma^{4}\circ\tau\circ\sigma^{2}\circ\tau\circ\sigma\circ\tau\circ\sigma^{4}\\\\&\circ\tau\circ\sigma^{4}\circ\tau\circ\sigma^{4}\end{array}}Voici donc les étapes pour passer de {MERCI} à {CRIME}. On a groupé les étapes consistant en plusieurs rotations vers la droite, en précisant le nombre de rotations simultanées, et on a représenté l’échange des deux premières lettres par le symbole {\leftrightarrow} :
      {\begin{matrix}MERCI &\underset{\rightarrow}4& ERCIM &\leftrightarrow& RECIM &\underset{\rightarrow}4& ECIMR &\leftrightarrow& CEIMR\\\\&\underset{\rightarrow}4& EIMRC &\leftrightarrow& IEMRC&\underset{\rightarrow}1& CIEMR &\leftrightarrow& ICEMR\\\\&\underset{\rightarrow}2& MRICE &\leftrightarrow& RMICE &\underset{\rightarrow}4& MICER &\leftrightarrow& IMCER\\\\&\underset{\rightarrow}4& MCERI &\leftrightarrow& CMERI &\underset{\rightarrow}1& ICMER &\leftrightarrow& CIMER\\\\&\underset{\rightarrow}1& RCIME &\leftrightarrow& CRIME\end{matrix}}
    • On peut en fait effectuer la transformation beaucoup plus rapidement : {\begin{matrix}MERCI&\underset{\rightarrow}3&RCIME&\leftrightarrow&CRIME\end{matrix}}Sur cet exemple, on voit que la méthode générale de décomposition (obtenue par application de la démonstration prouvant qu’une permutation quelconque est une composée de {s} et {\tau}) peut être très inefficace dans tel ou tel cas particulier (là où des astuces sont possibles.)