Groupes
\(\def\Rel#1#2{\,{\mathscr#1}_{#2}\,}\)

Introduction, le taquin

Nous allons consacrer ce chapitre à l'étude du jeu du taquin. Ce casse-tête solitaire a été inventé par Sam Loyd aux États-Unis à la fin du 19ème siècle. Il se présente sous la forme d'un plateau carré constitué de \(4\) lignes et \(4\) colonnes formant \(16\) cases sur lesquelles sont placées \(15\) pièces carrées numérotées de \(1\) à \(15\) con­for­mé­ment à la figure ci-dessous. L'une des cases est toujours vide pour permettre à une pièce adjacente d'y cou­lis­ser, comme la pièce 12 ou la pièce 14 dans la configuration proposée par Loyd.

Configuration* du taquin(*) Vous pouvez la modifier à vo­tre gui­se. La ca­se vide est codée 16 :

Jeu du taquin. Cliquez sur une pièce pour la pousser vers la case vide (elle entraîne les pièces sur son chemin).

Le but du jeu est de ranger les 15 pièces dans l'ordre croissant de \(1\) à \(15\) en faisant coulisser les pièces le long des lignes et des colonnes. Sam Loyd proposa la somme de $1.000 au premier qui trouverait une solution. Vous pouvez essayer vous-même avec le simulateur ci-dessus qui vous permet de faire glisser jusqu'à trois pièces alignées vers la case vide d'un seul coup plutôt que les déplacer les unes après les autres.

Ce jeu a été décliné de très nombreuses façons, par exemple en remplaçant les nombres par des portions d'une image à reconstituer à la manière d'un puzzle. Le célèbre Rubik's Cube est en quelque sorte une extension à trois dimensions de ce pro­blè­me. L'objectif de ce chapitre est de comprendre pourquoi Sam Loyd ne risquait pas de perdre ses $1.000 et de trouver comment résoudre d'autres configurations, quand elles admettent une solution.

Nous avons étudié aux chapitres précédents, les ensembles puis les relations qui pouvaient les lier et leur cardinalité. Nous allons à présent les animer en les équipant de quelques rouages.

Lois de composition et structures

On équipe à présent les ensembles de lois de composition et on en étudie leurs propriétés. Il s'agit de généraliser à des ensembles quelconques les opérations usuelles sur les ensembles de nombres (addition, multiplication, etc.) en mettant l'accent sur les propriétés qu'elles partagent plutôt que leurs particularités, et d'en tirer des résultats universels susceptibles d'être appliqués à toutes sortes de situations.

Lois de composition internes, magmas

On appelle loi de composition interne sur un ensemble \(X\) toute application \(\diamond\) de \(X\times X\) dans \(X\). Le couple \((X,\diamond)\) est appelé un magma.

On note généralement une loi de composition de manière infixe, soit \(x\;{\color{#FF8}\diamond}\;y\) plutôt que préfixe \({\color{#88F}\,\diamond}\,(x,y)\). L'ad­di­tion et la multiplication définies sur l'ensemble des entiers naturels \(\N\) au cha­pi­tre Combinatoire sont donc des lois de com­po­si­tion internes faisant de \((\N,+)\) et \((\N,\times)\) deux magmas. La réunion \(\cup\) et l'intersection \(\cap\) sur \({\mathscr P}(X)\) l'ensemble des parties d'un ensemble \(X\) sont des lois de composition internes faisant de \(({\mathscr P}(X),\cup)\) et \(({\mathscr P}(X),\cap)\) deux magmas. La composition des applications \(\circ\) d'un ensemble \(X\) dans lui-même, définit une loi de com­po­si­tion interne sur \(X^X\) faisant de \((X^X,\circ)\) un magma. La concaténation \(\cdot\) est une loi de composition interne sur l'ensemble \(\Sigma^*\) des mots définis sur un alphabet fini \(\Sigma\) faisant de \((\Sigma^+,\cdot)\) un magma.

Dans la suite, \((X,\diamond)\) désignera un magma.

Partie stable. Une partie \(A\) de \(X\) est dite stable pour la loi \(\diamond\) si et seulement si tous les composés d'éléments de \(A\) sont eux aussi des éléments de \(A\) :

\begin{equation} \forall (x,y)\in A \times A\quad x\diamond y \in A. \end{equation}

Dans ce cas, la restriction de la loi de com­po­si­tion \(\diamond\) aux éléments de \(A\times A\) est une loi de composition in­ter­ne sur \(A\), appelée loi induite par \(\diamond\) sur \(A\), et on conserve la même notation pour le magma \((A,\diamond)\). L'ensemble \(2\,\N\) des entiers pairs est une partie stable pour la loi d'addition \(+\) sur l'ensemble des entiers naturels \(\N\) faisant de \((2\,\N,+)\) un magma. L'ensemble \(S(X)\) des bijections d'un ensemble \(X\) sur lui-même est une partie stable de \(X^X\) pour la loi de composition des applications \(\circ\).

Associativité. Une loi de composition interne \(\diamond\) est dite associative si et seulement si

\begin{equation} \forall (x,y,z)\in X^\quad x\diamond(y\diamond z)= (x\diamond y)\diamond z. \end{equation}

Dans ce cas le magma est dit magma associatif. L'addition et de la multiplication sur les entiers na­tu­rels sont deux lois associatives, c'est cette propriété qui nous permet de nous affranchir des pa­ren­thè­ses dans l'expression \(x+y+z\) et l'ex­pres­sion \(x\times y\times z\). Ces expressions n'auraient pas de sens si ces lois n'étaient pas associatives. Le magma \((X^X,\circ)\) est associatif (cf. exercice). La loi puissance est bien une loi de composition interne sur \(\N\), mais n'est pas associative, par exemple \(2^{(2^3)}=256\) alors que \((2^2)^3=64\).

Commutativité. On dit que deux éléments \(x\) et \(y\) de \(X\) commutent si et seulement si

\begin{equation} x\diamond y = y \diamond x. \end{equation}

On appelle centre d'un magma, le sous-ensemble \(Z_X\) des éléments de \(X\) qui commutent avec n'im­por­te quel élément de \(X\). Si \(Z_X=X\), le magma est dit magma commutatif, c'est le cas de l'ensemble \(\N\) pour la loi additive ainsi que pour la loi multiplicative. En revanche la loi de composition des applications \(\circ\) n'est en gé­né­ral pas com­mu­ta­ti­ve pour le magma \((X^X,\circ)\), on peut s'en convaincre en composant les applications \(n\mapsto n+1\) et \(n\mapsto 2n\) de \(\N^\N.\)

Élément neutre. On appelle élément neutre pour la loi \(\diamond\) tout élément \(e\in X\) tel que

\begin{equation} \label{eq:egelemneutre} \forall x\in X\quad x\diamond e = e \diamond x=x. \end{equation}

S'il existe un élément neutre, celui-ci est nécessairement unique (preuve en exercice). Un magma dont la loi possède un élément neutre est dit magma uni­fè­re. L'entier \(0\) est l'élément neutre pour l'addition dans \(\N\) et l'entier \(1\) est l'élé­ment neutre pour la mul­ti­pli­ca­tion dans \(\N\). L'ensemble \(X\) est l'élément neutre pour l'intersection sur l'ensemble \({\mathscr P}(X)\) des parties de \(X\). Le magma \((X^X,\circ)\) est uni­fère d'élément neutre l'application iden­ti­que \({\Id}_X\).

Distributivité. Si un ensemble \(X\) est muni de deux lois de composition internes \(\star\) et \(\diamond\), on dit que \(\star\) est distributive à gauche (resp. distributive à droite) sur \(\diamond\) si et seulement si

\begin{align} \forall (x,y,z)\in X^3\ \ x\star(y\diamond z) &= (x\star y)\diamond(x\star z),\\ \text{resp.}\ \ \forall (x,y,z)\in X^3\ \ (x\diamond y)\star z &= (x\star z)\diamond(y\star z). \end{align}

Si la loi est à la fois distributive à gauche et à droite, on dit simplement qu'elle est distributive. La mul­ti­pli­ca­tion \(\times\) est distributive sur l'addition \(+\) dans \(\N.\)

\[\forall (a,b,c)\in\N^3\quad a\times(b+c)=(a\times b)+(a\times c).\]

L'intersection \(\cap\) est distributive par rapport à la réunion \(\cup\) sur l'ensemble \({\mathscr P}(X)\) des parties d'un en­semb­le \(X\) et réciproquement : \begin{align*} \forall (A,B,C)\in{\mathscr P}(X)^3\quad A\cap(B\cup C)&=(A\cap B)\cup(A\cap C),\\ \forall (A,B,C)\in{\mathscr P}(X)^3\quad A\cup(B\cap C)&=(A\cup B)\cap(A\cup C). \end{align*}

Vérifiez que les applications de \(\N^\N\) définies par \(f:n\mapsto n+1\) et \(g:n\mapsto 2n\) ne commutent pas pour la loi de composition des applications.
On vérifie aisément que \(f\circ g:n\mapsto 2n+1\) alors que \(g\circ f:n\mapsto 2n+2\).
Soit \(X\) un ensemble. Quel est l'élément neutre pour le magma \(({\mathscr P}(X),\cup)\) ?
Il s'agit bien sûr de l'ensemble vide \(\varnothing\) puisque \[\forall Y\in{\mathscr P}(X)\quad Y\cup\varnothing=\varnothing\cup Y=Y.\]
Démontrez qu'un élément neutre d'un magma unifère est nécessairement unique.
Par l'absurde, supposons qu'il existe deux éléments neutres \(e\) et \(e'\). On applique \((\ref{eq:egelemneutre})\) pour l'élé­ment neutre \(e\) avec \(x:=e'\) puis pour l'élément neutre \(e'\) avec \(x:=e\) pour obtenir res­pec­ti­ve­ment : \begin{align*} e'\diamond e &= e\diamond e' = e'\\ e\diamond e' &= e'\diamond e = e \end{align*} et par transitivité de l'égalité, on en déduit \(e=e'\).
Démontrez que l'intersection est distributive sur la réunion et réciproquement sur l'ensemble \({\mathscr P}(X)\) des parties d'un en­semb­le \(X\).
C'est la conséquence directe de la distributivité du connecteur logique de conjonction sur le connecteur logique de disjonction (et réciproquement). Nous ne montrerons que la distributivité de \(\cap\) sur \(\cup\), la preuve de la distributivité de \(\cup\) sur \(\cap\) étant similaire. Montrons que \[\forall x\quad x\in A\cap(B\cup C)\iff x\in(A\cap B)\cup(A\cap C).\] On a \begin{align*} x\in A\cap(B\cup C) &\ \iff\ (x\in A)\wedge (x\in (B\cup C))\\ &\ \iff\ (x\in A)\wedge \big((x\in B)\vee (x\in C)\big)\\ &\ \iff\ \big((x\in A)\wedge (x\in B)\big) \vee\big((x\in A)\wedge (x\in C)\big)\\ &\ \iff\ (x\in A\cap B)\vee(x\in A\cap C)\\ &\ \iff\ x\in (A\cap B)\cup (A\cap C) \end{align*}

Éléments réguliers. On appelle élément régulier à gauche (resp. élément régulier à droite) tout élé­ment \(r\in X\) tel que

\begin{align} \forall (x,y)\in X\times X\quad r\diamond x&=r\diamond y\ \Rightarrow\ x=y,\\ \text{resp.}\ \ \forall (x,y)\in X\times X\quad x\diamond r&=y\diamond r\ \Rightarrow\ x=y. \end{align}

Ces identités expriment que l'on peut simplifier une équation à gauche et/ou à droite par un élément régulier à gauche et/ou à droite. Un élément qui est la fois régulier à gauche et à droite est dit élément ré­gu­lier. L'élément neutre pour une loi de composition est nécessairement régulier. Dans \(\N\), tout élément est régulier pour l'addition et tout élément non-nul est régulier pour la multiplication. Dans \({\mathscr P}(X)\) le seul élément régulier pour l'in­ter­sec­tion est l'élément neutre \(X\).

Éléments symétrisables. Supposons à présent que le magma \((X,\diamond)\) soit unifère d'élément neutre \(e.\) On dit qu'un élément \(x\in X\) est symétrisable à gauche (resp. symétrisable à droite) s'il existe (au moins) un élément \(x'\in X\) tel que

\begin{align} x'\diamond x&=e,\\ \text{resp.}\ \ x\diamond x'&=e. \end{align}

On dit alors que \(x'\) est un symétrique à gauche (resp. symétrique à droite) de \(x\). On dit que \(x\) est symétrisable s'il est à la fois symétrisable à gauche et à droite.

Les différentes combinaisons de propriétés que peut satisfaire la loi de composition d'un magma \((X,\diamond)\) définissent de nouveaux objets très utilisés en mathématiques et en in­for­ma­ti­que. Un magma associatif est appelé un semi-groupe. Un semi-groupe unifère est appelé un mo­noï­de, c'est donc un magma associatif muni d'un élément neutre. Un monoïde dont tous les éléments sont symétrisables est appelé un groupe et nous y reviendrons plus loin tant cette structure est importante.

Soit \((X,\diamond)\) un monoïde. Alors
  1. Tout élément symétrisable à gauche (resp. à droite) est régulier à gauche (resp. à droite).
  2. Si un élément est symétrisable, son symétrique à gauche est égal à son symétrique à droite.
  3. Si un élément est symétrisable, son symétrique est unique.
  4. Le composé de deux éléments symétrisables est symétrisable.
Dans la suite on note \(e\) l'élément neutre du monoïde \((X,\diamond)\).

1. Notons \(x'\) le symétrique à gauche de \(x\). Soit \((s,t)\in X^2\) tels que \(x\diamond s=x\diamond t\). On a \begin{align*} x'\diamond(x\diamond s)&=x'\diamond (x\diamond t)\\ (x'\diamond x)\diamond s&=(x'\diamond x)\diamond t&\ &\text{car \(\diamond\) est associative}\\ e\diamond s&=e\diamond t&\ &\text{car \(x'\) symétrique à gauche de \(x\)}.\\ s&=t&\ &\text{car \(e\) est l'élément neutre pour \(\diamond\)}.\\ \end{align*} Preuve symétrique pour la régularité à droite.

2. Notons \(x'\) (resp. \(x''\)) le symétrique à gauche (resp. à droite) de \(x\). Par définition : \begin{equation} \label{eq:proofpropsym} {\color{#FF8}(x'\diamond x)} = {\color{#88F}(x\diamond x'')}=e. \end{equation} On en déduit \begin{align*} x' &= x'\diamond e&\ &\text{car \(e\) est l'élément neutre pour \(\diamond\)}\\ &= x'\diamond {\color{#88F}(x\diamond x'')}&\ &\text{d'après \((\ref{eq:proofpropsym})\)}\\ &={\color{#FF8}(x'\diamond x)}\diamond x''&\ &\text{car \(\diamond\) est associative}\\ &=e\diamond x''&\ &\text{d'après \((\ref{eq:proofpropsym})\)}\\ &= x''&\ &\text{car \(e\) est l'élément neutre pour \(\diamond\)}\\ \end{align*} 3. Si \(x\) et \(x'\) sont deux symétriques de \(x\), ils satisfont \((\ref{eq:proofpropsym})\) et sont par conséquent égaux.

4. Soit \(x_1\) et \(x_2\) deux éléments de \(X\) de symétriques respectifs (uniques d'après 3.) \(x_1'\) et \(x_2'\), alors \begin{align*} (x_1\diamond x_2)\diamond(x_2'\diamond x_1') &=(x_1\diamond (x_2 \diamond x_2'))\diamond x_1'&\ &\text{car \(\diamond\) est associative}\\ &=(x_1\diamond e)\diamond x_1'&\ &\text{car \(x_2'\) est le symétrique de \(x_2\)}\\ &=x_1 \diamond x_1'&\ &\text{car \(e\) est l'élément neutre pour \(\diamond\)}\\ &=e&\ &\text{car \(x_1'\) est le symétrique de \(x_1\)} \end{align*} On procède de la même manière pour montrer que \[ (x_2'\diamond x_1')\diamond(x_1\diamond x_2)=e. \] Ce qui prouve que \(x_1\diamond x_2\) admet \(x_2'\diamond x_1'\) pour symétrique.

L'entier naturel 0 est le seul élément qui admet un symétrique (lui-même) pour l'addition dans \(\N\), et \(1\) est le seul élément qui admet un symétrique (lui-même à nouveau) pour la mul­ti­pli­ca­tion dans \(\N\). L'ensemble des entiers relatifs \(\Z\) contient par construction, en sus des entiers naturels, tous leurs symétriques pour l'addition. En revanche pour la multiplication, seuls deux éléments de \(\Z\) admettent un symétrique, ce sont \(-1\) et \(1\). Les éléments symétrisables à gauche (resp. à droite) du magma \((X^X,\circ)\) sont les injections (resp. surjections). Les éléments sy­mé­tri­sa­bles du magma \((X^X,\circ)\) pour la loi de composition des ap­pli­ca­tions \(\circ\) sont donc les bijections.

Solutions d'une équation. C'est l'existence de symétriques qui permet de résoudre une équation. En effet, soit \((X,\diamond)\) un monoïde et \(a\) et \(b\) deux éléments de \(X\). Considérons l'équa­tion

\begin{equation} \label{eq:eqmonoide} a\diamond x=b \end{equation}

Si \(a\) admet un symétrique à gauche \(a'\), alors il existe une unique solution. En effet en composant \(a'\) aux membres gauches et droits de l'identité \((\ref{eq:eqmonoide})\), on a :

\begin{align*} a'\diamond(a\diamond x)&=a'\diamond b\\ (a'\diamond a)\diamond x&=a'\diamond b\quad\text{par associativité},\\ e\diamond x&=a'\diamond b\quad\text{par symétrique à gauche},\\ x&={\color{#88F}a'\diamond b}\quad\text{car \(e\) est l'élément neutre}. \end{align*}

Si \(a\) admet un symétrique à droite \(a''\), alors \(x={\color{#FC0}a''\diamond b}\) est une solution, en effet

\begin{align*} a\diamond({\color{#FF8}a''\diamond b})&=(a\diamond a'')\diamond b\quad\text{par associativité},\\ &=e\diamond b\quad\text{par symétrique à droite},\\ &=b\quad\text{car \(e\) est l'élément neutre}. \end{align*}

D'après la proposition précédente, on sait que si \(a\) est symétrisable, \(a'=a''\) et dans ce cas \(a'\diamond b\) est l'unique solution de l'équation \((\ref{eq:eqmonoide}).\) L'étude est symétrique pour l'équation \(x\diamond a=b\) pour laquelle \(b\diamond a'\) est l'unique solution.

Les notions abstraites et les manipulations formelles que nous venons d'étudier semblent s'adresser exclusivement à un public de ma­thé­ma­ti­ciens et peuvent paraître dénuées de tout intérêt pratique. Elles sont très utiles en in­for­ma­ti­que et en particulier en théorie des langages qui fournit un cadre scientifique pour l'étude des langages de programmation.

Lois de composition externes

Soit \(\Omega\) un ensemble. On appelle loi de com­po­si­tion externe sur un ensemble \(X\) à domaine d'opé­ra­teurs \(\Omega\) toute application \(\star\) de \(\Omega\times X\) dans \(X\).

Partie stable. De la même manière que pour une loi de composition interne, on dit qu'une partie \(A\) d'un ensemble \(X\) muni d'une loi de composition externe \(\star\) est stable pour cette loi si et seulement si

\begin{equation} \forall(\alpha,x)\in\Omega\times A\quad \alpha\star x\in A. \end{equation}

Dans ce cas en restreignant la loi aux éléments de \(A\), il s'agit encore d'une loi externe, appelée loi induite par \(\star\) sur \(A\).

Si l'on dispose d'un monoïde \((X,\diamond)\) d'élément neutre \(e\), on peut par exemple cons­trui­re une loi de composition externe \(\cdot\) sur \(X\) à domaine d'opérateur \(\N\) en itérant la loi interne : c'est l'application puissance \(\N\times X\rightarrow X\) définie par

\begin{equation} (n,x)\mapsto n\cdot x:=\begin{cases} e&\text{si}\ n=0,\\ \overbrace{x\diamond x\diamond\cdots\diamond x}^{n\ \text{fois}\ x}&\text{si}\ n > 0. \end{cases} \end{equation}

Quand la loi interne \(\diamond\) est notée comme une loi multiplicative, on utilise souvent l'écriture ex­po­nen­tiel­le \(x^n\) plutôt que \(n\cdot x\) pour désigner l'élément \(x\diamond x\diamond\cdots\diamond x\) et on en déduit im­mé­dia­te­ment que \begin{equation} \label{eq:additivitéexp} x^n\diamond x^m=x^{n+m}. \end{equation} Nous étudierons d'autres lois de composition externes dans les prochains chapitres.

Morphismes

Une relation binaire, une loi de composition interne ou externe sur un en­semb­le \(X\), définissent une structure sur cet ensemble. Si deux ensembles \(X\) et \(Y\) sont chacun munis d'une structure de même nature (relation binaire ou loi de composition), il est naturel de s'intéresser aux applications \(f:X\rightarrow Y\) qui ne perturbent pas les structures res­pec­tives sur ces deux ensembles. S'il s'agit de relations binaires, les images de deux éléments en relation doivent rester en relation et s'il s'agit de lois de compositions, l'image de la composition de deux éléments doit être la composition de leurs images :

Soit \(f:X\rightarrow Y\) une application. Si \(X\) et \(Y\) sont munis res­pec­ti­ve­ment des re­la­tions binaires \(\Rel{R}{X}\) et \(\Rel{R}{Y}\), on dit que \(f\) est un morphisme si et seulement si \begin{equation} x\,{\Rel{R}{X}}\,x'\Rightarrow f(x)\,{\Rel{R}{Y}}\,f(x'). \end{equation} Si \((X,\diamond)\) et \((Y,\star)\) sont deux magmas, on dit que \(f\) est un morphisme si et seulement si \begin{equation} f(x\diamond x')=f(x)\star f(x'). \end{equation}

Nous avons déjà rencontré un morphisme au chapitre Combinatoire. Une application croissante en­tre deux ensembles ordonnés respecte la relation d'ordre, c'est un morphisme d'ensembles or­don­nés.

La notation exponentielle introduite en \((\ref{eq:additivitéexp}\)) définit le morphisme

\begin{align*} p_x:(\N,+)&\longrightarrow(X,\diamond)\\ n&\longmapsto x^n \end{align*}

La fonc­tion exponentielle étudiée dans le cours d'analyse est également un morphisme de \((\R,+)\) dans \((\R,\times)\), en effet \(\text{exp}(x+y)=\text{exp}(x).\text{exp}(y)\).

Vocabulaire. Si \(f:X\rightarrow Y\) est un morphisme injectif, on dit que c'est mo­no­mor­phis­me, s'il est surjectif on dit que c'est un épi­mor­phis­me. Si \(Y=X\), on dit que \(f\) est un en­do­mor­phis­me. Si \(f\) est bijective et que la bijection ré­ci­pro­que \(f^{-1}\) est encore un mor­phis­me on dit que \(f\) est un iso­mor­phis­me. Un isomorphisme de \(X\) dans lui-même est appelé un au­to­mor­phis­me. On précise souvent la nature du mor­phis­me, c'est-à-dire la structure qui équipe les ensembles reliés par le mor­phis­me, on parlera donc de mor­phis­me d'ensembles ordonnés, ou de mor­phis­me de semi-groupes ou de mor­phis­mes de grou­pes, etc.

Il faut retenir que si deux ensembles structurés sont isomorphes, ils sont en quelque sorte jumeaux, on peut étudier les propriétés structurelles de l'un ou l'autre indifféremment. Établir un isomorphisme entre deux ensembles structurés dont la gémellité ne saute pas aux yeux, permet de partager immédiatement toutes les propriétés structurelles que l'on a pu établir pour l'un ou l'autre.
Démontrez que si \(X\) et \(Y\) sont deux magmas, alors la bijection réciproque \(f^{-1}\) d'un mor­phis­me bi­jec­tif \(f:X\rightarrow Y\) est nécessairement un morphisme. Démontrez que si \(X\) et \(Y\) sont munis de deux relations binaires, alors la bijection réciproque \(f^{-1}\) d'un mor­phis­me bi­jec­tif \(f:X\rightarrow Y\) n'est pas né­ces­sai­re­ment un morphisme. Indication : choisir une application croissante.
Notons \((X,\star)\) et \((Y,\diamond)\) ces deux magmas. Il faut donc montrer que \[ \forall(y_1,y_2)\in Y\times Y\quad f^{-1}(y_1)\star f^{-1}(y_2)= f^{-1}(y_1\diamond y_2). \] Soit \(y_1\) et \(y_2\) deux éléments de \(Y\), on note \(x_1:=f^{-1}(y_1)\) et \(x_2:=f^{-1}(y_2)\). Com­me \(f\) est bijective, on a \(f^{-1}\circ f={\Id}_X\) (cf. ce théorème) et on en déduit que \begin{align*} x_1\star x_2 &=(f^{-1}\circ f)\,\big(x_1\star x_2\big)\\ &=f^{-1}\big(f(x_1\star x_2)\big)\\ &=f^{-1}\big(f(x_1)\diamond f(x_2)\big)\quad\text{car \(f\) est un morphisme}\\ &=f^{-1}\big(y_1\diamond y_2\big) \end{align*} La bijection réciproque \(f^{-1}\) est donc bien un morphisme.

L'égalité est une relation d'ordre sur tout ensemble \(X\), on considère donc \((X,=)\) et \((Y,\leq)\) où \(\leq\) désigne une relation d'ordre sur \(Y\). Si \(f:X\rightarrow Y\) est une application bijective et croissante, on a \(x=y\Rightarrow f(x)\leq f(y)\) mais pas toujours \(f^{-1}(x)\leq f^{-1}(y)\Rightarrow x=y\), prendre par exemple l'ap­pli­ca­tion de \(\Z^\Z\) définie par \(n\mapsto n+1\).

Soit \(X\), \(Y\) et \(Z\) trois ensembles structurés et \(f:X\rightarrow Y\) et \(g:Y\rightarrow Z\) deux morphismes. Démontrez que l'application \(g\circ f\) est un morphisme de \(X\rightarrow Z\). Démontrez que si de plus les structures sont des lois de compositions et que \(f\) et \(g\) sont des isomorphismes, alors \(g\circ f\) est un isomorphisme.
Montrons le pour des relations binaires \(\Rel{R}{X}\), \(\Rel{R}{Y}\) et \(\Rel{R}{Z}\) sur ces ensembles res­pec­ti­ve­ment. On a par hypothèse \begin{align} \label{exo:eq1} \forall (x_1,x_2)\in X^2\quad x_1\Rel{R}{X} x_2 &\then f(x_1)\Rel{R}{Y} f(x_2)\\ \label{exo:eq2} \forall (y_1,y_2)\in Y^2\quad y_1\Rel{R}{Y} y_2 &\then g(y_1)\Rel{R}{Z} g(y_2) \end{align} Soit \((x_1,x_2)\in X^2\) tel que \(x_1\Rel{R}{X} x_2\). D'après \((\ref{exo:eq1})\) on a \(f(x_1)\,\Rel{R}{Y} f(x_2)\) et on peut appliquer \((\ref{exo:eq2})\) au couple \((f(x_1),f(x_2))\) pour obtenir \begin{align*} \forall (x_1,x_2)\in X^2\quad x_1\,\Rel{R}{X} x_2 &\then g(f(x_1))\,\Rel{R}{Z} g(f(x_2))\\ &\then (g\circ f)(x_1)\,\Rel{R}{Z} (g\circ f)(x_2)\\ \end{align*} Montrons le à présent pour des lois de composition internes \(+\), \(\times\) et \(\diamond\) respectivement. On a par hypothèse \begin{align} \label{exo:eq11} \forall (x_1,x_2)\in X^2\quad f(x_1+x_2) &= f(x_1)\times f(x_2)\\ \label{exo:eq22} \forall (y_1,y_2)\in Y^2\quad g(y_1\times y_2) &= g(y_1)\diamond g(y_2) \end{align} Et pour tout couple \((x_1,x_2)\in X^2\), on a \begin{align*} (g\circ f)(x_1 + x_2) &= g(f(x_1 + x_2))&&\\ &= g(f(x_1)\times f(x_2))&\ &\text{d'après \((\ref{exo:eq11})\)}\\ &=g(f(x_1))\diamond g(f(x_2))&\ &\text{on applique \((\ref{exo:eq22})\) à \(f(x_1)\times f(x_2)\)}\\ &=(g\circ f)(x_1)\diamond(g\circ f)(x_2).&& \end{align*} Supposons à présent que \(f\) et \(g\) soient des isomorphismes. Si \(f\) et \(g\) sont des bijections, nous savons que \(g\circ f\) est une bijection et nous savons d'une part que \((g\circ f)^{-1} = f^{-1}\circ g^{-1}\) d'après cet exercice) et que \(f^{-1}\circ g^{-1}\) est un morphisme d'après l'exercice précédent, c'est donc bien un isomorphisme.

Transport d'une structure. Soit \(X\) un ensemble muni d'une structure et \(Y\) un ensemble quel­con­que. Quand on dispose d'une bijection \(f:X\rightarrow Y\), on transporte facilement la structure de \(X\) à \(Y.\) Par exemple si \(\Rel{R}{X}\) est une relation binaire définie sur \(X\), il suffit de définir la relation \(\Rel{R}{Y}\) sur \(Y\) par \[y\;\Rel{R}{Y}\;y'\Leftrightarrow f^{-1}(y)\;\Rel{R}{X}\;f^{-1}(y').\]

En vous inspirant du transport d'une structure d'ensemble ordonné ci-dessus, explicitez comment transporter une loi de composition interne et une loi de com­po­si­tion externe.
Soit \(f\) un morphisme surjectif d'un magma \((X,\diamond)\) dans un magma \((Y,\star)\). Démontrez que
  1. Si \(\diamond\) est associative alors \(\star\) l'est aussi.
  2. Si \(\diamond\) est commutative alors \(\star\) l'est aussi.
  3. Si \(\diamond\) admet un élément neutre \(e\) alors \(\star\) aussi et \(f(e)\) est son élément.
  4. Si \(x'\) est le symétrique de \(x\) dans \(X\), alors \(f(x')\) est le symétrique de \(f(x)\) dans \(Y\).

Compatibilité. Si plusieurs structures équipent un même ensemble, il est naturel de s'intéresser à leur cohabitation. L'omniprésence des relations d'équivalence et des lois de composition sur les ensembles justifie que l'on se questionne sur l'articulation d'une relation d'équivalence avec une loi de composition interne \(\diamond\) d'un magma \((X,\diamond)\).

Si l'on dispose d'une relation d'équivalence \(\rel\) et d'une loi de composition interne \(\diamond\) sur un ensemble \(X,\) on souhaite pouvoir équiper l'ensemble quotient \(X/\rel\) d'une loi de composition \(\overline{\diamond}\) héritée de \(\diamond\). Plus précisément, si \(A\) et \(B\) désignent deux classes d'équivalence pour \(\rel\), on veut définir la composition \(A\overline{\diamond} B\) comme la classe d'équi­va­len­ce de \(a\diamond b\) si \(a\) et \(b\) désignent des représentants quel­con­ques de \(A\) et de \(B\) respectivement. Ceci n'est possible bien sûr que si \(\overline{a\diamond b}\) ne dépend pas du choix des représentants \(a\) et \(b\), ce qui va imposer certaines conditions sur la relation \(\rel\). C'est l'objectif qu'il faut garder à l'esprit pour ne pas se perdre dans les méandres des cons­truc­tions algébriques qui vont suivre.

Soit \((X,\diamond)\) un magma muni d'une relation d'équivalence \(\rel\). On dit que \(\rel\) est com­pa­tib­le à gauche (resp. à droite) avec la loi \(\diamond\) si et seulement si \begin{align} \forall(x,y,z)\in X^3\quad (x{\rel}y)&\Rightarrow ({\color{#FF8}z}\diamond x) \rel({\color{#FF8}z}\diamond y).\\ \text{resp.}\ \ \forall(x,y,z)\in X^3\quad (x{\rel}y)&\Rightarrow (x\diamond {\color{#88F}z}){\rel}(y\diamond {\color{#88F}z}).\\ \end{align} On dit que \(\rel\) est com­pa­tib­le avec \(\diamond\) si elle l'est à la fois à gauche et à droite.

Trivialement, si la loi \(\diamond\) est commutative, la compatibilité à gauche est équivalente à la compatibilité à droite.

Montrez que si \((X,\diamond)\) est un magma et que \(\rel\) est une relation d'équivalence compatible à gauche et à droite avec \(\diamond\) alors \begin{equation} \forall(x,y,x',y')\in X^4\quad (x{\rel}y)\wedge(x'{\rel}y')\ \Rightarrow (x\diamond x'){\rel}(y\diamond y'). \end{equation}
Soit \((x,y,x',y')\in G^4\) et supposons que \((x{\rel} y)\wedge(x'{\rel} y')\). Par compatibilité à gauche on en déduit que \(({\color{#FF8}x}\diamond x'){\rel}({\color{#FF8}x}\diamond y')\) et à droite que \((x\diamond{\color{blue}y'}){\rel}(y\diamond{\color{blue}y'})\). On conclut grâce à la transitivité de \({\rel}\).

Supposons que \({\rel}\) soit compatible avec \(\diamond\) et soit \((\overline{a},\overline{b})\in (X/{\rel})^2\). Montrons que si \(a_1\) et \(a_2\) (resp. \(b_1\) et \(b_2\)) sont deux représentants quelconques de la classe \(\overline{a}\) (resp. de la classe \(\overline{b}\)), alors \(\overline{a_1\diamond b_1}=\overline{a_2\diamond b_2}.\) On a d'une part \begin{align*} a_1&{\rel}a_2,\\ b_1&{\rel}b_2. \end{align*} et la compatibilité à droite et à gauche de \(\rel\) sur \(\diamond\) permet d'en déduire que \begin{align*} (a_1\diamond{\color{blue}b_1})&{\rel}(a_2\diamond{\color{blue}b_1})\\ ({\color{#FF8}a_2}\diamond b_1)&{\rel}({\color{#FF8}a_2}\diamond b_2). \end{align*} La transitivité de \(\rel\) nous donne \((a_1\diamond{\color{blue}b_1}){\rel}({\color{#FF8}a_2}\diamond b_2)\) soit \(\overline{a_1\diamond b_1}=\overline{a_2\diamond b_2}\) d'après cet exercice. La loi de composition \(*\) sur le quotient peut donc être définie par \begin{equation} \label{eq:loiquotient} \overline{a}\,*\,\overline{b}:=\overline{a\diamond b}. \end{equation} puisqu'elle ne dépend pas du choix des représentants \(a\) et \(b\) des classes \(\overline{a}\) et \(\overline{b}\). Grâce à la compatibilité de \({\rel}\) avec \(\diamond\), le quotient \(X/{\rel}\) peut donc hériter de la même loi que celle qui équipe \(X\) :

Soit \((X,\diamond)\) un magma muni d'une relation d'équivalence \({\rel}\) com­pa­tib­le avec \(\diamond\) et \(\varphi: X\rightarrow X/{\rel}\) la surjection canonique. Alors il existe une unique loi de com­po­si­tion interne sur l'ensemble quotient \(X/{\rel}\) telle que \(\varphi\) soit un morphisme. Elle est ap­pe­lée loi quotient de \(\diamond\) par \({\rel}\).
Si cette loi quotient \(*\) existe et que la surjection canonique \(\varphi\) est un morphisme, alors elle doit vérifier la proposition \begin{equation} \label{eq:morph} \forall(a,b)\in X^2\quad \varphi(a\diamond b) = \varphi(a)*\varphi(b). \end{equation} Mais \(X/{\rel}\) est une partition de \(X\), la proposition (\ref{eq:morph}) entraîne donc que \begin{equation*} \forall (\overline{a},\overline{b})\in (X/{\rel})^2\ \forall (a_1,b_1)\in A\times B\quad \overline{a}*\overline{b} = \varphi(a_1\diamond b_1). \end{equation*} La loi \(*\) est donc la loi \(\overline{\diamond}\) définie en \((\ref{eq:loiquotient})\).

Par abus de langage, la loi quotient sur l'ensemble quotient est généralement notée comme la loi qui équipe l'ensemble sous-jacent.

On numérote les jours à l'aide des entiers relatifs, le jour \(0\) étant fixé (arbitrairement) au dimanche 4 mars 1962. On définit une relation binaire \({\rel}\) sur \(\Z\) par \begin{equation} \label{eqmod7} x{\rel}y\iff 7\mid (y-x). \end{equation}
  1. Démontrez que \({\rel}\) est une relation d'équivalence sur \(\Z\).
  2. Quelles sont les différentes classes d'équivalence pour cette relation ?
Soit \(\varphi\) la surjection canonique de \(\Z\) dans \(\Z/{\rel}\). On note \(\text{dim}:=\varphi(0)\), \(\text{lun}:=\varphi(1)\),…, \(\text{sam}:=\varphi(6).\)
  1. Démontrez que \({\rel}\) est compatible avec l'addition de \(\Z\).
  2. Dressez la table d'addition de \(\Z/{\rel}\) pour la loi induite \(+\).
1. La relation \({\rel}\) est réflexive puisque \(7\mid 0\). Soit \((x,y)\in\Z^2\), si \(7\mid (y-x)\) alors \(7\mid (x-y)\), la relation \({\rel}\) est donc symétrique. Soit \((x,y,z)\in\Z^3\), si \(7\mid (y-x)\) et \(7\mid (z-y)\) on en déduit l'existence de deux entiers \(a\) et \(b\) tels que \(7a=y-x\) et \(7b=z-y\) puis l'égalité \begin{align*} 7b+7a&=(z-y)+(y-x)\\ 7(b+a)&=z+((-y)+y)-x\quad\text{car l'addition est associative dans}\ \Z\\ 7(b+a)&=z-x. \end{align*} Autrement dit que \(7\mid(z-x)\), ce qui prouve que \(x\,{\rel}\,z\).

2. Les éléments de la classe de \(0\) sont les entiers relatifs \(x\) tels que \(x\,{\rel}\,0\), c'est-à-dire ceux qui sont divisibles par \(7\) ou pour paraphraser les multiples de \(7\) : \[\overline{0}=\{7z\mid z\in\Z\}.\] On a plus généralement pour \(k\in\llbracket 0,\,6\rrbracket\) \[\overline{k}=\{7z+k\mid z\in\Z\}.\] Ces \(7\) ensembles sont deux-à-disjoints, en effet \(7z+k=7z+l\) entraîne \(k=l\). D'autre part, en anticipant sur l'étude de la division euclidienne, il existe un unique \(z\in\Z\setminus\{0\}\) et un unique \(k\in\llbracket 0,\,6\rrbracket \) tels que \(x=7z+k\). Par conséquent, les ensembles \(\overline{0},\overline{1},\ldots,\overline{6}\) sont toutes les classes d'équivalence de \(\Z\) pour la relation \({\rel}\).

3. Il faut donc prouver que \begin{equation*} \forall(x,x',y,y')\in X^4\quad (x{{\rel}}x')\wedge(y{{\rel}}y')\ \Rightarrow (x\diamond y){{\rel}}(x'\diamond y'). \end{equation*} Ce qui se traduit ici par \begin{equation*} \forall(x,x',y,y')\in X^4\quad (7\mid (x'-x))\wedge(7\mid (y'-y))\ \Rightarrow 7\mid\big((x'+y')-(x+y)\big). \end{equation*} Si \(7\mid (x'-x)\) et \(7\mid (y'-y)\), il existe \((k,l)\in\N^2\) tel que \begin{align*} 7k&=x'-x\\ 7l&=y'-y \end{align*} Et en sommant : \begin{equation*} 7(k+l)=x'+y'-(x+y). \end{equation*} Ce qui permet de conclure que la relation \({\rel}\) est compatible avec l'addition dans \(\Z\). L'ensemble quotient \(\Z/{\rel}\) peut donc être muni de la loi quotient additive héritée de celle de \(\Z\).

4. La table d'addition de \(\Z/{\rel}\) est la suivante :

+dimlunmar merjeuvensam
dimdimlunmar merjeuvensam
lunlunmarmer jeuvensamdim
marmarmerjeu vensamdimlun
mermerjeuven samdimlunmar
jeujeuvensam dimlunmarmer
venvensamdim lunmarmerjeu
samsamdimlun marmerjeuven

La construction abstraite de l'ensemble \(\Z\) des entiers relatifs dans la section suivante est une occasion d'appliquer ces différents résultats et de mieux les com­pren­dre.

Construction de \({\mathbb Z}\)

La construction de l'ensemble des entiers relatifs est un cas particulier de symétrisation. C'est un procédé général qui a pour objectif de rajouter les éléments qui manquent à un ensemble muni d'une loi de composition afin qu'une équation du type \((\ref{eq:eqmonoide})\) admette une solution.

Considérons le monoïde \((\N,+)\). Il est commutatif par définition de l'addition dans \(\N\), la réunion ensembliste étant commutative. Soit \((n,m)\) un couple d'entiers naturels, l'équation

\begin{equation} \label{eq:symetrisation} x+n=m \end{equation}

n'admet de solution dans \(\N\) que si \(m\geq n\). Le cas échéant, on a bien sûr envie d'écrire que cette solution est égale à \(m-n\), mais nous n'avons pas encore défini la loi soustractive \(-\), c'est précisément l'objet de cette construction. Soit \(x\) une solution de \((\ref{eq:symetrisation})\), quand elle existe. Dans ce cas, pour tout \({\color{#FF8}k}\in\N\), \(x\) est également so­lu­tion de l'équation

\begin{align*} x+(n+{\color{#FF8}k})&=(m+{\color{#FF8}k}). \end{align*}

Ainsi, pour \(n\) et \(m\) fixés, tous les couples de la forme \((n+{\color{#FF8}k},m+{\color{#FF8}k})\) définissent des équations \((\ref{eq:symetrisation})\) qui admettent la même solution. Il est tentant de définir la relation qui lie tous ces couples par la proposition \((n,m){{\rel}}(n',m')\Leftrightarrow n-n'=m-m'\), mais il faut l'écrire sans soustraction :

\begin{equation} \label{eq:relbin} \forall (n,m,n',m')\in\N^4\quad (n,m){{\rel}}(n',m')\Leftrightarrow n+m'=m+n', \end{equation}

On définit alors l'addition sur \(\N\times\N\) qui est une loi de composition interne en conservant la même notation que pour l'addition dans \(\N\) :

\begin{equation} \label{eq:addZ} \forall (n,m,n',m')\in\N^4\quad (n,m)+(n',m') := (n+n',m+m'). \end{equation}
Démontrez que la relation binaire définie sur l'ensemble \(\N\times\N\) par la pro­po­si­tion \((\ref{eq:relbin})\) est une relation d'équivalence de surcroît compatible avec l'addition \(+\) définie en \((\ref{eq:addZ})\) sur \(\N\times\N.\)

On définit \(\Z:=(\N\times\N)\,/{\rel}\) qui, d'après le théorème sur la loi quotient, est muni de la loi additive quotient puisque la relation est compatible. On montre facilement que \((0,0)\) est l'élément neutre pour cette loi et qu'elle est associative et commutative. D'autre part, tout couple \((n,m)\) admet un symétrique, il s'agit du couple \((m,n)\), en effet

\begin{align*} (n,m)+(m,n)&=(n+m,m+n)\\ &=(n+m,n+m)\\ \text{et}\ \ (n+m,n+m)\;& {\mathscr R}\;(0,0). \end{align*}

On vérifie aisément que les couples \((n,0)\) avec \(n \geq 0\) et les couples \((0,m)\) avec \(m > 0\) représentent des classes deux-à-deux distinctes et que ces couples représentent toutes les classes. D'autre part les classes \((0,n)\) sont les classes opposées des classes \((n,0)\) pour l'addition définie ci-dessus. On montre que le sous-ensemble de \((\Z,+)\) cons­ti­tué des couples \((n,0)\) est isomorphe à \((\N,+)\), cela justifie de noter \(n\) le couple \((n,0)\). Sy­mé­tri­que­ment, on note \((-n)\) le couple \((0,n)\).

Si l'on représente le produit cartésien \(\N\times\N\) dans un repère, les représentants de type \((n,0)\) dé­cri­vent l'axe des abscisses et les représentants du type \((0,m)\) dé­cri­vent l'axe des ordonnées. La figure ci-dessous permet de visualiser les classes d'équi­va­len­ce de ces couples d'entiers qui re­pré­sen­tent les entiers relatifs de l'intervalle \([-10,10]\).

Construction de \(\Z\) comme classes d'équivalence de l'ensemble \(\N\times\N\) pour la relation \({\rel}\).

Saisissez la valeur de l'entier relatif \(\color{#FF8}n=\;\) pour voir les éléments de sa classe d'équivalence.

Pour achever la construction de \(\Z\), nous ne donnerons que les grandes lignes. La multiplication est définie comme suit : \[ (n,n')\times (m,m')=(nm+n'm',nm'+mn'). \] Elle a pour élément neutre \(1=(1,0)\), elle est associative et commutative et compatible avec la relation d'équivalence \({\rel}\). On vérifie que \((n,0)\times(m,0)=(nm,0)\), que \((n,0)\times(0,m)=(0,nm)\) et que \((0,n)\times(0,m)=(nm,0)\), ce qui permet de retrouver les écritures condensées usuelles puisque l'on a noté \(n\) le couple \((n,0)\) et \(-n\) le couple \((0,n)\). Pour la relation d'ordre, on peut montrer qu'il existe une seule relation d'ordre total sur \(\Z\), c'est la relation définie par \[x\leq y\Leftrightarrow y-x\in\N,\] qui prolonge la relation d'ordre sur les entiers naturels. On démontre que toute partie non-vide et minorée de \(\Z\) admet un plus petit élément.

Notons pour conclure cette section que le procédé de construction du corps des fractions de \(\Z\), à savoir \(\Q\) est tout à fait similaire en partant cette fois de l'équation

\begin{equation} q\times x=p. \end{equation}
En vous inspirant de la construction de \(\Z\), trouvez la relation d'équivalence \({\rel}\) entre couples de \(\Z\times\Z\) et la loi de composition sur \(\Z\times\Z\) pour construire l'ensemble \(\Q\) comme le quotient \((\Z\times\Z)\,/{\rel}\).

Groupes

Généralités

Nous allons aborder une dernière structure dans ce chapitre. Nous aurons besoin de la structure de groupe pour étudier le problème du taquin. D'autres structures seront abordées dans le chapitre Arithmétique. Les groupes sont omniprésents en mathématiques et font l'objet d'une attention toute particulière au point qu'une théorie à part entière leur est consacrée. Cette théorie est très utile pour résoudre de nombreux problèmes de combinatoire, de géométrie, etc. Les chimistes en font grand usage dans l'étude des structures moléculaires et leurs symétries.

Un magma \((X,\diamond)\) unifère, associatif et où tout élément est symétrisable est appelé un groupe. Si l'ensemble \(X\) est fini, le groupe \((X,\diamond)\) est appelé groupe fini d'ordre \(|X|\).

L'ensemble des entiers relatifs \(\Z\) muni de l'addition est un groupe, de surcroît commutatif (on dit aussi groupe abélien*(*) Niels Henrik Abel fut un mathématicien nor­végien qui a dé­mon­tré, en­tre autres, que l'on ne pou­vait pas ré­sou­dre une équation de degré \(\geq 5\) par radicaux.). Nous reviendrons en détail sur ce groupe en arithmétique. Le sous-ensemble \(\{-1,1\}\) de \(\Z\) muni de la multiplication est un groupe commutatif.

Par analogie avec l'addition dans \(\Z\), quand la loi de groupe est notée ad­di­ti­ve­ment, on note souvent \(0\) l'élément neutre au lieu de \(e\) et on parle d'opposé d'un élément \(x\) plutôt que de symétrique que l'on note généralement \((-x)\). De même quand la loi de groupe est notée multiplicativement, on note souvent \(1\) l'élément neutre au lieu de \(e\) et on parle d'inverse d'un élément \(x\) plutôt que de symétrique que l'on note généralement \(x^{-1}\). Par abus de langage, nous parlerons souvent du groupe \(G\) pour signifier \((G,\diamond)\), confondant ainsi groupe et ensemble sous-jacent.

Soit \((G,\diamond)\) et \((G',\star)\) deux groupes notés multiplicativement et \(f:G\rightarrow G'\) un morphisme de grou­pes. On vérifie que l'image de l'élément neutre \(e\) de \((X,\diamond)\) est l'élément neutre \(e'\) de \((X',\star)\), i.e.

\begin{equation} \label{eq:imneutre} f(e)=e'. \end{equation}

On vérifie que l'image du symétrique \(x^{-1}\) de \(x\) est le symétrique de l'image de \(x\), i.e.

\begin{equation} \label{eq:iminverse} f(x^{-1})={f(x)}^{-1}. \end{equation}

D'autre part, pour tout entier relatif \(n\in\Z\), on a

\begin{equation} f(x^n)=(f(x))^{n}. \end{equation}

L'ensemble des entiers relatifs \(\Z\) est un groupe commutatif pour l'addition, et \(\Z\setminus\{0\}\) n'est pas un groupe pour la multiplication. En revanche l'ensemble des réels \(\R\) est un groupe commutatif pour l'addition et \(\R\setminus\{0\}\) est un groupe commutatif pour la multiplication.

On considère une famille \((G_i,\diamond_i)_{i\in I}\) de groupes et on note \(G\) le produit de la famille \((G_i)_{i\in I}.\) On définit la loi produit \(\diamond\) sur \(G\) par \begin{equation} x\diamond y = (x_i\diamond_i y_i)_{i\in I}. \end{equation} Montrez que chaque projection \(p_i:G\rightarrow G_i\) est un morphisme surjectif de groupes. Montrez que le groupe produit \((G,\diamond)\) est commutatif si et seulement si chacun des groupes \((G_i,\diamond_i)\) est commutatif.

Application : définissez l'addition sur des \(n\)-uplets de \(\R^n\).

Sous-groupes

On appelle sous-groupe d'un groupe \((G,\diamond)\), tout groupe \((H,\diamond)\) où \(H\) est une partie stable de \(G\) munie de la loi induite par celle de \(G\). On note alors \(H \leq G\) ou \(H < G\) si de plus \(H\neq G\).

Le sous-ensemble \(\{-1,1\}\) de \(\Z\) muni de la multiplication induite est un sous-groupe de \((\Z,\times)\). L'ensemble \(3\Z:=\{3k\mid k\in\Z\}\) des multiples de \(3\) muni de l'addition est un sous-groupe de \((\Z,+)\).

Si \(H\) est un sous-groupe de \(G\), l'injection canonique \(j:H\rightarrow G\) vérifie \(j(x\diamond y)=j(x)\diamond j(y)\), c'est donc un morphisme de groupes. Et d'après \((\ref{eq:imneutre})\) et \((\ref{eq:iminverse})\), l'élément neutre de \(H\) est celui de \(G\) et le symétrique d'un élément de \(H\) est le même que son symétrique dans \(G\) ce qui prouve la proposition suivante :

Un groupe et ses sous-groupes ont le même élément neutre. Le symétrique d'un élément d'un sous-groupe est identique à celui qu'il a dans le groupe.

Le théorème suivant est particulièrement utile, il fournit plusieurs caractérisations d'un sous-groupe, soit autant de pistes pour démontrer qu'un sous-ensemble \(H\subseteq G\) muni de la loi induite par celle du groupe \((G,\diamond)\) est bien un de ses sous-groupes.

Soit \((G,\diamond)\) un groupe d'élément neutre \(e\) et \(H\) une partie de \(G\). Les quatre assertions suivantes sont équivalentes :
  1. \(H\) est un sous-groupe de \(G\) ;
  2. \(H\) est stable, \(e\in H\) et \(\forall x\in H\ \ x^{-1}\in H\) ;
  3. \(H\) est stable, \(H\not=\varnothing\) et \(\forall x\in H\ \ x^{-1}\in H\) ;
  4. \(H\not=\varnothing\) et \(\forall (x,y)\in H^2\ \ x\diamond y^{-1}\in H\).
Montrons que \((1)\then(2)\). Par définition \(H\) est stable pour \(\diamond\) et la proposition précédente permet de conclure.

Montrons que \((2)\then(3)\). C'est évident puisque \(e\in H\).

Montrons que \((3)\then(4)\). C'est évident puisque \(y^{-1}\in H\) et que \(H\) est stable.

Montrons que \((4)\then(2)\). Puisque \(H\) n'est pas vide, il existe au moins un \(x\in H\), on peut donc appliquer la deuxième partie de l'hypothèse sur le couple \((x,x)\), soit \(x\diamond x^{-1}=e\in H\). On peut à présent appliquer la deuxième partie de l'hypothèse au couple \((e,x)\), soit \(e\diamond x^{-1}=x^{-1}\in H\). Pour la stabilité, \(x\diamond y=x\diamond(y^{-1})^{-1}\).

On conclut avec \((2)\then(1)\). \(H\) étant stable la loi \(\diamond\) induite sur \(H\) est associative et admet \(e\) pour élément neutre et tout \(x\in H\) admet pour symétrique \(x^{-1}\).

Si \((G,\diamond)\) est un groupe, \((G,\diamond)\) est évidemment un sous-groupe de \((G,\diamond)\), c'est le plus grand élément pour la relation \(\subseteq.\) Pour cette même relation d'ordre, le plus petit sous-groupe de \(G\) est le sous-groupe \((\{e\},\diamond)\) où \(e\) est l'élément neutre de \(G\) pour la loi \(\diamond\). On vérifie aisément que si \(H\) est un sous-groupe de \(G\) qui est lui même un sous-groupe de \(K\), alors \(H\) est un sous-groupe de \(K\).

Soit \((G,\diamond)\) un groupe. Vérifiez que l'ensemble noté \({S}(G)\) des bijections de l'ensemble \(G\) dans lui-même muni de la loi de composition des applications est un groupe. Montrez que le sous-ensemble des au­to­mor­phis­mes muni de la loi induite \(\circ\), noté \((\text{Aut}(G),\circ)\) est un sous-groupe de \(({S}(G),\circ)\).

L'intersection d'une famille de sous-groupes d'un groupe \(G\) est un sous-groupe de \(G\). Soit \(A\subseteq G\) une partie d'un groupe \(G\), l'intersection de tous les sous-groupes de \(G\) qui contiennent \(A\) n'est jamais vide puisque \(G\) est un sous-groupe de \(G\) et contient \(A\).

Soit \(G\) un groupe et \(A\subseteq G\). On appelle sous-groupe engendré par \(A,\) noté \(\text{gr}(A),\) le plus petit (au sens de l'inclusion) sous-groupe de \(G\) qui contient \(A\). C'est l'intersection de tous les sous-groupes de \(G\) qui contiennent \(A\). On dit que \(A\) est une partie génératrice de \(G\).

On admettra le théorème suivant :

Soit \((G,\diamond)\) un groupe noté multiplicativement d'élément neutre \(e\) et \(A\) une partie de \(G\). Si \(x^1\) désigne \(x\) et \(x^{-1}\) le symétrique de \(x\), alors le sous-ensemble \(H\) des produits quelconques d'éléments \(a\) ou \(a^{-1}\) de \(A\), i.e de la forme \begin{equation} a_1^{\epsilon_1}\diamond a_2^{\epsilon_2}\diamond\cdots\diamond a_n^{\epsilon_n}\quad\text{où}\ \ \epsilon_i\in\{-1,1\}. \end{equation} avec par convention \(H=\{e\}\) si \(A=\varnothing\), est le sous-groupe de \(G\) engendré par \(A\).
On appelle groupe monogène tout groupe engendré par un singleton. Un grou­pe monogène et fini est appelé groupe cyclique.
Soit \(f:G\rightarrow G'\) un morphisme de groupes. Alors l'image directe d'un sous-groupe \(H\) de \(G\) est un sous-groupe de \(G'\) pour la loi induite et l'image réciproque d'un sous-groupe \(H'\) de \(G'\) est un sous-groupe de \(G\) pour la loi induite.
Démontrez cette proposition.
L'image du groupe \(G\) tout entier et l'image réciproque du singleton \(\{e'\}\) constitué de l'élément neutre de \(G'\) sont donc des sous-groupes de \(G'\) et \(G\) respectivement.
Soit \(f:G\rightarrow G'\) un morphisme de groupes. Alors \(f(G)\) est un sous-­groupe de \(G'\) appelé image de \(G\) et noté \(\text{Im}(G)\). Si \(e'\) est l'élément neutre de \(G'\), alors \(f^{-1}(\{e'\})\) est un sous-groupe de \(G\) appelé noyau de \(f\) et noté \(\text{Ker}(f)\).

L'image et le noyau d'un morphisme fournissent des critères simples pour décider s'il est surjectif ou injectif, ce qui s'avère très utile en pratique :

Un morphisme de groupes \(f:G\rightarrow G'\) est une surjection si et seulement si \(\text{Im}(f)=G'\) et une injection si et seulement si \(\text{Ker}(f)=\{e\}\) où \(e\) est l'élément neutre pour la loi de groupe de \(G\).
On désignera par \(\diamond\) et \(\star\) les lois de composition internes respectives des groupes \(G\) et \(G'\) notée mul­ti­pli­ca­ti­ve­ment et \(e\) et \(e'\) leurs éléments neutres respectifs.

Le résultat est évident pour la surjection par définition. Pour l'autre partie, on sait que l'image de \(e\) est \(e'\), que \(f\) soit injective ou non, mais si c'est cas \(e\) est l'unique élément dont l'image est \(e'\), autrement dit \(\text{Ker}(f)=\{e\}\). Réciproquement, supposons que \(\text{Ker}(f)=\{e\}\). On veut prouver que \[\forall (x,y)\in G\times G\ \ f(x)=f(y)\Rightarrow x=y.\] L'élément \(f(y)\) admet un symétrique \(f(y)^{-1}\) (notation multiplicative) dans \(G'\) puisqu'il s'agit d'un groupe, donc si \(f(x)=f(y)\), \begin{align*} f(x)\star f(y)^{-1}&=f(y)\star f(y)^{-1}\\ f(x)\star f(y)^{-1}&=e'\\ f(x\diamond y^{-1})&=e' \end{align*} Autrement dit, \(x\diamond y^{-1}\in\text{Ker}(f)\), soit : \begin{align*} x\diamond y^{-1}&=e\\ (x\diamond y^{-1})\diamond y&=e\diamond y\\ x\diamond (y^{-1})\diamond y)&=y\\ x\diamond e&=y\\ x&=y. \end{align*}
Justifiez chaque égalité de la preuve ci-dessus en identifiant les propriétés des lois de grou­pe qui ont été appliquées.

On rappelle que le centre de \(G\) est la partie \(Z_G\) des éléments de \(G\) qui com­mu­tent avec tous les élé­ments du groupe, i.e.

\[Z_G=\{a\in G\mid\forall x\in G\ \ x\diamond a=a\diamond x\}\]

Soit \(a\in Z_G\), on a donc \(\forall x\in G\ \ x\diamond a = a \diamond x\) et en composant à droite par le symétrique de \(a\) noté \(a^{-1}\), on a nécessairement

\[\forall x\in G\ \ x=a\diamond x\diamond a^{-1}.\]
Soit \((G,\diamond)\) un groupe.
  1. Démontrez que l'application \(\varphi_a:G\rightarrow G\) définie par \(x\mapsto\ a\diamond x\diamond a^{-1}\) est un automorphisme du groupe (dit automorphisme intérieur de \(G\)).
  2. Quel est l'automorphisme réciproque de \(\varphi_a\) ?
  3. Démontrez que l'application \(\varphi:a\mapsto \varphi_a\) est un morphisme du groupe \((G,\diamond)\) dans le groupe \((\text{Aut}(G),\circ)\).
  4. Vérifiez que \(\text{Ker}(\varphi)=Z(G).\)
1. C'est un morphisme, en effet en notant \(e\) l'élément neutre pour \(\diamond\), on a \(a\diamond a^{-1}=e\) et on en déduit \begin{align*} \varphi_a(x\diamond y) &=a\diamond x\diamond y\diamond a^{-1}\\ &=a\diamond x\diamond (a^{-1}\diamond a)\diamond y\diamond a^{-1}\\ &=(a\diamond x\diamond a^{-1})\diamond (a\diamond y\diamond a^{-1})\\ &=\varphi_a(x)\diamond\varphi_a(y). \end{align*} Il est injectif, en effet \begin{equation*} \varphi_a(x)=\varphi_a(y)\iff a\diamond x\diamond y\diamond a^{-1} = a\diamond y\diamond y\diamond a^{-1} \end{equation*} Il suffit de composer les deux membres de l'égalité à gauche par \(a^{-1}\) et à droite par \(a\) pour obtenir \(x=y\). Il est également surjectif, soit \(y\in G\), l'élément \(x:=\varphi_{a^{-1}}(y)=a^{-1}\diamond y\diamond a\) est un an­té­cé­dent de \(y\) : \begin{align*} \varphi_a(x)&=a\diamond(a^{-1}\diamond y \diamond a)\diamond a^{-1}\\ &=(a\diamond a^{-1})\diamond y \diamond (a\diamond a^{-1})\\ &=y. \end{align*} Et nous savons que pour une loi de composition, un morphisme bijectif est un isomorphisme.

2. On a \(\varphi_a\circ\varphi_{a^{-1}}=\varphi_{a^{-1}}\circ\varphi_a={\Id}_G\), donc \(\varphi_a^{-1}=\varphi_{a^{-1}}\).

3. Soit \((a,b)\in G^2\). On a \(\varphi(a\diamond b)=\varphi_{a\diamond b}\), or \(\forall x\in G\), \begin{align*} \varphi_{a\diamond b}(x) &= (a\diamond b)\diamond x \diamond (a\diamond b)^{-1}\\ &= (a\diamond b)\diamond x \diamond (b^{-1}\diamond a^{-1})\\ &= a\diamond(b\diamond x\diamond b^{-1})\diamond a^{-1}\\ &= \varphi_a(b\diamond x\diamond b^{-1})\\ &= \varphi_a(\varphi_b(x))\\ &= (\varphi_a\circ\varphi_b)(x) \end{align*} Donc \(\varphi(a\diamond b)=\varphi_a\circ\varphi_b\).

4. Par définition \(\text{Ker}(\varphi)=\{a\in G\mid \varphi_a={\Id}_G\}.\) Mais \(\varphi_a={\Id}_G\) est équivalent à \begin{equation*} \forall x\in G\ \varphi_a(x)=x\ \iff\ \forall x\in G\ a\diamond x\diamond a^{-1}=x \iff\ \forall x\in\ G\ a\diamond x=x\diamond a. \end{equation*} Ce qui prouve que \(\text{Ker}(\varphi)=Z(G)\).

Sous-groupes normaux

On dit que deux éléments \(x\) et \(x'\) d'un groupe \((G,\diamond)\) sont conjugués si et seu­le­ment s'il existe \({\color{lightblue}a}\in G\) tel que \begin{equation} x'= {\color{lightblue}a}\diamond x\diamond {\color{lightblue}a^{-1}}. \end{equation}
Vérifiez que la relation de conjugaison sur un groupe \(G\) est une relation d'équi­va­len­ce. Soit \(x\in Z(G)\), montrez que la classe de conjugaison de \(x\) est réduite à \(\{x\}\).
Elle est réflexive puisque \(x\) est conjugué avec lui même \(x = e\diamond x\diamond e\). Elle est sy­mé­tri­que puisque si \(x'= a\diamond x\diamond a^{-1}\) alors \(x= {\color{lightblue}a^{-1}}\diamond x'\diamond ({\color{lightblue}a^{-1}})^{-1}\). Elle est éga­lement tran­si­ti­ve puisque si \(y={\color{#FF8}a\diamond x\diamond a^{-1}}\) et \(z= b\diamond{\color{#FF8}y}\diamond b^{-1}\), alors \begin{align*} z&= b\diamond ({\color{#FF8}a\diamond x\diamond a^{-1}})\diamond b^{-1}\\ &= (b\diamond a)\diamond x\diamond (a^{-1}\diamond b^{-1})\quad\text{car la loi est associative}\\ &= (b\diamond a)\diamond x\diamond (a^{-1}\diamond b^{-1})\\ &= (b\diamond a)\diamond x\diamond (b\diamond a)^{-1}\\ \end{align*} Il suffit de constater que la classe de conjugaison d'un élément \(x\in G\) est l'ensemble \[\overline{x}:=\{a\diamond x\diamond a^{-1}\such a\in G\}\] et comme \(x\in Z(G)\), il commute avec tous les éléments de \(G\), donc \(a\diamond x\diamond a^{-1}=a\diamond a^{-1}\diamond x=x\).

Soit \(G\) un groupe, \(a\in G\) et \(H\) et \(H'\) deux sous-groupes de \(G\). On dit que \(H\) et \(H'\) sont conjugués par \(a\) si et seulement si \(H'=aHa^{-1}\).

On appelle sous-groupe normal (ou distingué) d'un groupe \((G,\diamond)\) tout sous-groupe \(H\) de \(G\) qui est invariant par tout automorphisme intérieur de \(G\), i.e. \begin{equation} \forall a\in G\quad a\diamond H=H\diamond a. \end{equation} où \(a\diamond H:=\{a\diamond x\mid x\in H\}\) et \(H\diamond a:=\{x\diamond a\mid x\in H\}\). On note alors \(H\trianglelefteq G\) ou \(H\triangleleft G\) si de plus \(H\neq G\).

Autrement dit, un sous-groupe est normal s'il est égal à tous ses conjugués. Si \((G,\diamond)\) est un groupe d'élément neutre \(e\), alors \((\{e\},\diamond)\) et \((G,\diamond)\) sont deux sous-groupes normaux de \((G,\diamond)\), dits triviaux et s'il n'y en a pas d'autres, alors \((G,\diamond)\) est appelé un groupe simple. Les groupes simples et finis jouent un rôle majeur dans l'étude générale des groupes finis, car ces derniers sont tous construits à partir de ces groupes simples. Leur très difficile classification a demandé des dizaines d'années de recherche et s'est achevée au début des années 1980.

Si un groupe \(G\) est commutatif, tous ses sous-groupes sont normaux, cette notion a donc surtout un intérêt dans l'étude des groupes non-commutatifs. On sait déjà que l'image ou l'image réciproque d'un sous-groupe par un morphisme de groupe est un sous-groupe et on peut montrer que l'image et l'image réciproque d'un sous-groupe normal par un morphisme de groupe sont des sous-groupes normaux. En corollaire, le noyau d'un morphisme de groupe est toujours un sous-groupe normal.

L'étude des sous-groupes normaux est motivée par la caractérisation des relations d'équivalence qui sont compatibles avec une loi de groupe. En effet, il faut se souvenir que l'on ne peut transporter la loi de composition qui équipe l'ensemble sur ll'ensemble quotient, qu'à la condition que la relation d'équivalence soit com­pa­tib­le avec sa loi de composition. Dans le cas particulier où le magma est un groupe, les seules relations d'équivalence compatibles avec sa loi sont en­tiè­re­ment ca­rac­té­ri­sées par les sous-groupes normaux de \(G\).

Soit \((G,\diamond)\) un groupe. Une relation d'équivalence \({\rel}\) sur \(G\) est compatible à gauche (resp. à droite) avec la loi \(\diamond\) si et seulement si elle est de la forme \begin{equation} \label{eq:rgrd} x{\color{orange}{\rel}}y\Leftrightarrow x^{-1}\diamond y\in H\qquad\text{resp.}\ \ x{\color{lightblue}{\rel}}y\Leftrightarrow y\diamond x^{-1}\in H, \end{equation} où \(H\) est un sous-groupe de \(G\).
Nous ne faisons la preuve que pour la compatibilité à gauche, elle est similaire pour la com­pa­ti­bi­li­té à droite. On se donne une relation d'équivalence \({\rel}\) sur \(G\) compatible à gauche, autrement dit \[ \forall(x,y,z)\in G^3\ \ x{{\rel}}y\Rightarrow ({\color{#88F}z}\diamond x){{\rel}}({\color{#88F}z}\diamond y). \] On note \(H\) la classe d'équivalence de l'élément neutre \(e\) pour \({\rel}\). Soit \((x,y)\in G^2\) tels que \(x{{\rel}}y.\) Comme \({\rel}\) est compatible à gauche avec la loi \(\diamond\), on a \((x^{-1}\diamond x){{\rel}}(x^{-1}\diamond y)\), soit \(e{{\rel}}(x^{-1}\diamond y)\) et donc \(x^{-1}\diamond y\in H.\) Inversement si \(x^{-1}\diamond y\in H\) alors \((x^{-1}\diamond y){{\rel}}e\) et donc \(x\diamond(x^{-1}\diamond y){{\rel}}x\) soit \((x\diamond x^{-1})\diamond y{{\rel}}x\) par associativité et finalement \(y{{\rel}}x\) ou encore \(x{{\rel}}y\) puisque la relation est symétrique. Donc \[ \forall(x,y)\in G\times G\quad x{{\rel}}y\Leftrightarrow x^{-1}\diamond y\in H. \] Montrons que \(H\) est un sous-groupe de \(G\). Soit \(x\) et \(y\) deux éléments quelconques de \(H\). Comme \(e\in H\), \(x{{\rel}}e\) et \(e{{\rel}}y\) et par transitivité de la relation, \(x{{\rel}}y\) soit \(x^{-1}\diamond y\in H\).

Réciproquement soit \(H\leqslant G\). La relation \({\rel}\) définie par \(x{{\rel}}y\Leftrightarrow x^{-1}\diamond y\in H\) est réflexive puisque pour tout \(x\in G\), \(x^{-1}\diamond x=e\) et \(e\in H\). Elle est symétrique car si \(x^{-1}\diamond y\in H\), son inverse \((x^{-1}\diamond y)^{-1}=y^{-1}\diamond x\) appartient à \(H\) puisque \(H\) est un sous-groupe de \(G\) et donc \(y{\rel}x\). Soit \((x,y,z)\in G^3\), si \(x{\rel}y\) et \(y{\rel}z\) soit \(x^{-1}\diamond y\in H\) et \(y^{-1}\diamond z\in H\), alors leur composé \((x^{-1}\diamond y)\diamond(y^{-1}\diamond z)=x^{-1}\diamond z\) appartient à \(H\) puisque \(H\) est un groupe, et donc \(x{\rel}z\) ce qui prouve que \({\rel}\) est transitive.

La relation est également compatible à gauche. En effet, soit \((x,y,z)\in G^3\) tel que \(x{\rel}y\), i.e. \({\color{orange}x^{-1}\diamond y}\in H\). On a \begin{align*} {\color{orange}(z\diamond x)^{-1}\diamond(z\diamond y)}&=(x^{-1}\diamond z^{-1})\diamond(z\diamond y)\quad\text{inverse d'un produit}\\ &=x^{-1}\diamond(z^{-1}\diamond z)\diamond y\quad\text{associativité}\\ &=x^{-1}\diamond e\diamond y\quad\text{symétrique}\\ &={\color{orange}x^{-1}\diamond y}\quad\text{neutre}. \end{align*} Ce qui prouve que \((z\diamond x){\rel}(z\diamond y)\).

Les classes d'équivalence des relations \(\color{orange}{\mathscr R}_g\) et \(\color{lightblue}{\mathscr R}_d\) définies en \((\ref{eq:rgrd})\) sont respectivement les ensembles \begin{equation} a\diamond H:=\{a\diamond h\mid h\in H\}\quad\text{et}\quad H\diamond a:=\{h\diamond a\mid h\in H\}, \end{equation} appelés classes à gauche et classes à droite suivant \(H\). L'application \(x\mapsto x^{-1}\) de \(G\) dans \(G\) définit une bijection entre \(a\diamond H\) et \(H\diamond a^{-1}\), autrement dit l'ensemble des inverses des éléments de \(a\diamond H\) est l'ensemble \(H\diamond a^{-1}\). Par conséquent, les deux ensembles quotients \(G/{\mathscr R}_g\) et \(G/{\mathscr R}_d\) sont équipotents et s'ils sont finis leur cardinal est appelé indice de \(H\) dans \(G\), on le note \((G:H)\) ou \([G:H]\) ou encore \(|G:H|\). Le théorème de Lagrange qui va suivre est un résultat fondamental, il est omniprésent dans les raisonnements qui concernent les groupes finis.

L'ordre d'un sous-groupe \(H\) d'un groupe fini \(G\) divise l'ordre du groupe \(G\) et \(|G|\,/\,|H|=(G:H)\).
L'application \(x\mapsto a\diamond x\) définit une bijection de \(H\) dans \(a\diamond H\), les différentes classes à gauche sont donc équipotentes et comme elles forment une partition de \(G\), le principe des bergers permet de conclure.

Soit \({\rel}\) une relation d'équivalence compatible avec la loi \(\diamond\), autrement dit compatible à gauche et à droi­te. Soit \(H\) la classe d'équivalence de l'élément neutre \(e\). On sait que \(H\) est un sous-groupe de \(G\) et que \(\forall x\in G\), \(x{{\rel}}y\) si et seulement si \(y\in x\diamond H\) et \(y\in H\diamond x\), soit

\begin{equation*} \forall x\in G\quad x\diamond H=H\diamond x, \end{equation*}

soit \(H\trianglelefteq G\). Réciproquement si \(H\trianglelefteq G\), la relation \({\rel}\) définie par \(x{{\rel}}y\) si et seulement si \(x^{-1}\diamond y\in H\) qui équivaut à \(y\diamond x^{-1}\in H\) est compatible avec la loi \(\diamond\). Par conséquent :

Une relation d'équivalence \({\rel}\) définie sur un groupe \((G,\diamond)\) est compatible avec la loi \(\diamond\) si et seulement s'il existe un sous-groupe normal \(H\trianglelefteq G\) tel que \(x{{\rel}}y\Leftrightarrow x^{-1}\diamond y\in H\).

Puisque les relations d'équivalence compatibles avec une loi de groupe sont complètement caractérisées par les sous-groupes normaux du groupe, le groupe quotient est noté \(G\,/\,H\) plutôt que \(G\,/\,{\rel}\). D'autre part, la surjection canonique \(\varphi:G\rightarrow G\,/\,H\) est un morphisme de groupes.

Nous savons déjà que tout sous-groupe d'un groupe commutatif est normal. \((\Z,+)\) est un groupe com­mu­ta­tif, les relations d'équivalence compatibles avec l'addition sur \(\Z\) sont donc du type \[x{{\rel}}y\Leftrightarrow y-x\in H\] où \(H\) est un sous-groupe de \(\Z\). L'étude de ce groupe particulier est le point de départ de l'ari­thmé­ti­que, ce que nous aborderons au chapitre éponyme Arithmétique.

Les groupes sont souvent notés multiplicativement mais ne sont pas toujours commutatifs, et donc si \((x_i)_{i\in I}\) est une famille d'éléments d'un groupe non-commutatif, on ne peut pas définir son produit en général. Néanmoins si la loi est associative et que l'ensemble d'indexation est l'intervalle \(\llbracket 1,\,n\rrbracket \) de \(\N\), on définit les produits dans l'ordre croissant (resp. décroissant) des indices : \begin{align*} \prod_{i=1}^n x_i&:=x_1.x_2\,\ldots\,x_{n-1}.x_n,\\ \prod_{i=n}^1 x_i&:=x_n.x_{n-1}\,\ldots\,x_2.x_1. \end{align*}

Le groupe symétrique

L'ensemble des permutations des éléments d'un ensemble joue un rôle très important en in­for­ma­ti­que. Par exemple, tous les algorithmes de tri sont intimement reliés à l'étude de cet ensemble. Nous verrons d'ailleurs que beaucoup de résultats mathématiques de cette section ne sont rien d'autres que des algorithmes déjà connus du lecteur sans avoir pour autant étudié le groupe symétrique.

L'ensemble des bijections d'un ensemble \(X\) dans lui-même est noté \(S(X)\) ou \({\mathfrak S}(X)\) et ses élements sont appelés permutations de \(X\).
L'ensemble \(\def\Sn{{S}}S(X)\) muni de la loi \(\circ\) de composition des applications est un groupe appelé groupe symétrique de \(X\). Si \(X=\ab{1}{n}\), on l'appelle groupe symétrique de degré n et on le note \(S_{n}\) ou \({\mathfrak S}_n\).
Nous avons vu en exercice que la composée de deux bijections est une bijection, le sous-ensemble \(\Sn(X)\) de \(X^X\) constitué des bijections est donc une partie stable pour la loi de composition \(\circ\) faisant de \((\Sn(X),\circ)\) un magma. L'associativité de la loi de composition a été acquise en exercice. L'application identique est bijective et constitue l'élément neutre pour la composition des bijections. Chaque bijection \(f\) admet sa bijection réciproque \(f^{-1}\) qui est son symétrique pour la loi de composition, ce qui permet de conclure que \((\Sn(X),\circ)\) est un groupe.

Si deux ensembles \(X\) et \(Y\) sont équipotents, étudier le groupe symétrique de l'un est équivalent à étudier celui de l'autre. En effet si \(f:X\rightarrow Y\) est une bijection alors l'application \(\varphi:{S}(X)\rightarrow{S}(Y)\) définie par \(\sigma\mapsto f\circ \sigma\circ f^{-1}\) est un iso­mor­phis­me de groupes. En particulier, si un ensemble est fini de cardinal \(n\), l'étude de son groupe symétrique peut toujours se ramener à l'étude du groupe symétrique \(S_n\) de degré \(n\). Ceci montre que l'étude du groupe symétrique \({S}_n\) de degré \(n\) ne se limite pas à l'étude des permutations des éléments de l'ensemble \(\llbracket 1,\,n\rrbracket \) mais concerne tous les ensembles finis de car­di­nal \(n\).

Le théorème de Cayley ci-dessous va plus loin et affirme que n'importe quel groupe peut être assimilé à un sous-groupe du groupe symétrique, justifiant l'intérêt que l'on accorde à ce groupe.

Arthur Cayley était un ma­thématicien anglaisTout groupe \((G,\diamond)\) est isomorphe à un sous-groupe de \(({S}(G),\circ)\).
Montrons que l'application \(\sigma:G\rightarrow S(G)\) définie par \(\sigma:g\mapsto\sigma_g\) qui associe à un élement du groupe \(g\) l'application \(\sigma_g:G\rg G\) dé­fi­nie par \(x\mapsto g\diamond x\), est un isomorphisme de \((G,\diamond)\) dans \((\text{Im}(\sigma),\circ)\). Assurons nous tout d'abord que \(\sigma\) est bien une permutation du groupe symétrique \(S(G)\). Soit \(h\in G\), l'équation \(g\diamond x=h\) admettant l'unique solution \(g^{-1}\diamond h\), l'application \(\sigma_g\) est bijective et appartient donc à \(S(G)\). La loi \(\diamond\) étant associative, on a pour tout \((g,h,x)\in G^3\) \begin{align*} \sigma_{g\diamond h}(x) &=(g\diamond h)\diamond x\\ &=g\diamond (h\diamond x)\\ &=g\diamond \sigma_h(x)\\ &=\sigma_g(\sigma_h(x))\\ &=(\sigma_g\circ\sigma_h)(x) \end{align*} Autrement dit \(\sigma_{g\diamond h}=\sigma_g\circ\sigma_h\), ce qui fait de l'application \(\sigma\) un morphisme de groupes surjectif sur son image \(\text{Im}(\sigma)\) qui est un sous-groupe de \(S(G)\). Reste à montrer qu'il est injectif. Son noyau \(\text{Ker}(\sigma):=f^{-1}({\Id}_G)\), autrement dit \begin{align*} \text{Ker}(\sigma)&=\{a\in G\mid \forall x\in G\ \ \sigma_a(x)=x\},\\ &=\{a\in G\mid \forall x\in G\ \ a\diamond x=x\}. \end{align*} Or \(\forall x\in G\ \ a\diamond x=x\) si et seulement si \(a=e\), le noyau est donc réduit au singleton \(\{e\}\) ce qui prouve l'injectivité. Finalement l'application \(\sigma\) est un isomorphisme.

Nous allons nous concentrer sur le groupe symétrique d'un ensemble fini et par­ti­cu­liè­re­ment sur le groupe \(\Sn_{n}\) de degré \(n\). On représente gé­né­ra­le­ment le graphe d'une per­mu­ta­tion \(\sigma\in{S}_n\) sous la forme d'une matrice de 2 lignes de \(n\) entiers dont la première ligne contient tous les entiers de \(1\) à \(n\) dans l'ordre croissant et la seconde leurs images en vis-à-vis :

\begin{equation} \sigma=\begin{pmatrix} 1&2&3&\cdots&n\\ \sigma(1)&\sigma(2)&\sigma(3)&\cdots&\sigma(n) \end{pmatrix} \end{equation}
Décrivez toutes les permutations des groupes \(\Sn_{1}\) et \(\Sn_{2}\). En déduire que ces groupes sont com­mu­ta­tifs.
Le groupe \(\Sn_{1}\) ne contient que l'application identité, il est évidemment commutatif. Le groupe \(\Sn_{2}\) contient l'identité et la permutation \(\tau\) définie par \(\tau(1)=2\) et \(\tau(2)=1\). Par définition l'identité commute avec toutes les permutations, et toute permutation commute avec elle-même, \(\Sn_{2}\) est donc commutatif.
Pour tout entier \(n\geq 3\), le groupe \(\Sn_{n}\) n'est pas commutatif.
Comme \(n\geq 3\), il existe trois entiers distincts \(a\), \(b\) et \(c\) dans \(\llbracket 1,\,n\rrbracket \). On considère la permutation \(\sigma\) définie par \(\sigma(a):=b\), \(\sigma(b):=a\) et invariante en toute autre valeur, et la permutation \(\tau\) définie par \(\tau(a):=c\), \(\tau(c):=a\) et invariante en tout autre valeur. On a \begin{align*} \sigma\circ\tau(a)&=\sigma(c)=c\\ \tau\circ\sigma(a)&=\tau(b)=b. \end{align*} et par conséquent \(\sigma\circ\tau\not=\tau\circ\sigma\).

C'est un résultat à ne pas perdre de vue. Le fait que ce groupe ne soit pas commutatif en général lui donne un intérêt tout particulier et le théorème de Cayley montre que l'étude du groupe symétrique et de ses sous-groupes permet indirectement d'étudier tous les groupes.

Soit \(\sigma\in S_n\) avec \(n\geq 3\) et \(a\) et \(b\) deux entiers distincts de \(\ab{1}{n}\). On note \(\tau_{a,b}\) la permutation qui échange les deux valeurs \(a\) et \(b\) et laisse les autres valeurs fixes. Montrez que \begin{equation} \label{eq:compotau} \sigma\circ\tau_{a,b}\circ\sigma^{-1}=\tau_{\sigma(a),\sigma(b)}. \end{equation} En déduire que le centre \(Z(\Sn_{n})\) du groupe \(\Sn_n\) est réduit au singleton \(\{{\Id}_n\}\) dès que \(n\geq 3\). Indications : si \(\sigma\in Z(\Sn_n)\), \(\sigma\) commute avec toutes les permutations de \(\Sn_n\), et en particulier avec celles du type \(\tau_{a,b}\), quelles que soient les valeurs de \(a\) et \(b\) avec \(a\neq b\).
Calculons l'image de \(\sigma(a)\) par la permutation \(\rho:=\sigma\circ\tau_{a,b}\circ\sigma^{-1}\). On a \begin{align*} (\sigma\circ\tau_{a,b}\circ\sigma^{-1})(\sigma(a)) &=\sigma\circ\tau_{a,b}(\sigma^{-1}(\sigma(a))\\ &=\sigma\circ\tau_{a,b}((\sigma^{-1}\circ\sigma)(a))\\ &=\sigma\circ\tau_{a,b}(a)\\ &=\sigma(b) \end{align*} Avec le même raisonnement, on montre que \((\sigma\circ\tau_{a,b}\circ\sigma^{-1})(\sigma(b))=\sigma(a)\). Si \(x\not\in\{a,b\}\), il est facile de voir que \((\sigma\circ\tau_{a,b}\circ\sigma^{-1})(x)=x\), ce qui achève de prouver \((\ref{eq:compotau})\).

Si \(\sigma\in Z(S_n)\), on peut appliquer \((\ref{eq:compotau})\) à n'importe quel couple de valeurs \((a,b)\) distinctes de l'intervalle \(\ab{1}{n}\), en particulier \((1,2)\) :

La loi de composition des applications se comporte de manière similaire à un produit, ainsi pour al­lé­ger les écritures, le symbole de composition des applications \(\circ\) sera écrit comme un produit et très souvent omis dans les ex­pres­sions. On parlera donc du produit \(\sigma\tau\) au lieu de la composition \(\sigma\circ\tau\) de \(\sigma\) et \(\tau\).

Orbites

Soit \(k\in\N\). Si \(k\geq 0\), la notation \(\sigma^k\) désigne la \(k\)-ème itérée de \(\sigma\), i.e. la composition de \(k\) termes \(\sigma\) et la notation \(\sigma^{-k}\) la \(k\)-ème itérée de la permutation inverse \(\sigma^{-1}\).

On appelle ordre d'une permutation \(\sigma\in\Sn_n\) le plus petit entier naturel non-nul \(p\) tel que \(\sigma^p={\Id}\).
Considérons l'ensemble \(\{k\in\N\setminus\{0\}\mid \sigma^k={\Id}\}\). Montrons que c'est une partie non-vide de \(\N.\) L'ensemble \(\{\sigma^k\mid k\in\N\}\) des itérés de \(\sigma\) est fini puisque c'est une partie de l'en­semb­le fini \(\Sn_n\). Ainsi la suite définie par \(k\mapsto \sigma^k\) n'est pas injective, i.e. il existe deux entiers \(k\) et \(l\) tels que \(k < l\) et \(\sigma^l=\sigma^k\) soit \(\sigma^{l-k}={\Id}\) avec \(l-k > 0\). On sait que toute partie non-vide de \(\N\) admet un plus petit élément ce qui achève la preuve de ce théorème.
Quelle est l'ordre de la permutation \(\sigma\) suivante ? \begin{equation} \sigma=\begin{pmatrix} 1 & 2 & 3 & 4 & 5\\ 2 & 5 & 4 & 1 & 3 \end{pmatrix} \end{equation}
Soit \(\sigma\in\Sn_n\). La relation binaire \(\Rel{R}{\sigma}\) dé­fi­nie sur \(\llbracket 1,\,n\rrbracket \) par \begin{equation} x\Rel{R}{\sigma}y\ \iff\ \exists k\in\Z\quad y=\sigma^k(x). \end{equation} est une relation d'équivalence. La classe d'équivalence d'un élément \(x\in \llbracket 1,\,n\rrbracket \) est appelée orbite de \(x\) suivant \(\sigma\), on la note \(\def\orb{{\mathscr O}}\orb_\sigma(x)\).
Démontrez ce théorème. Quelles sont les différentes orbites pour la permutation identité ?
Soit \(\sigma\in\Sn_n\) et \(\orb\) une orbite suivant \(\sigma\). Démontrez que l'application induite par \(\sigma\) sur \(\orb\) est une bijection.

La proposition suivante va nous permettre d'élaborer un algorithme pour construire l'orbite \(\orb_\sigma(x)\) d'un élément \(x\) de \(\llbracket 1,\,n\rrbracket \) suivant une permutation \(\sigma\in\Sn_n\).

Soit \(\sigma\in\Sn_n\) et \(\orb\) une orbite de cardinal \(p > 1\) suivant \(\sigma\). Alors \begin{equation} \label{eq:calculorb} \forall x\in\orb\quad \orb=\{x,\sigma(x),\sigma^2(x),\ldots,\sigma^{p-1}(x)\}\quad\text{et}\ \ \sigma^p(x)=x. \end{equation}
Soit \(x\in\llbracket 1,\,n\rrbracket \) tel que \(\orb=\orb_\sigma(x)\). Par définition \(\orb_\sigma(x)=\{\sigma^k(x)\mid k\in\Z\}\), c'est une partie de \(\llbracket 1,\,n\rrbracket \) donc finie elle aussi. Ainsi l'application définie par \(k\mapsto \sigma^k(x)\) n'est pas injective, i.e. il existe deux entiers relatifs \(k\) et \(l\) tels que \(k < l\) et \(\sigma^k(x)=\sigma^l(x)\), soit \(\sigma^{l-k}(x)=x\). L'ensemble \(\{e\in\N\mid \sigma^{e}(x)=x\}\) n'est donc pas vide et admet un plus petit élément \(p\). Soit \(k\) un entier quelconque. Si \(q\) et \(r\) désignent respectivement le quotient et le reste de la division euc­li­dien­ne de \(k\) par \(p\), i.e. \(k=qp+r\) avec \(0\leq r < p\), on a \begin{align*} \sigma^k(x) &=\sigma^{r+qp}(x)\\ &=\sigma^{r+(q-1)p}(\sigma^p(x))\\ &=\sigma^{r+(q-1)p}(x)\\ &=\sigma^{r+(q-2)p}(\sigma^p(x))\\ &\ \ \vdots\\ &=\sigma^r(x) \end{align*} Tous les restes possibles étant compris entre \(0\) et \(p-1\), on a donc \[\orb=\{\sigma^r(x)\mid 0\leq r < p\}.\] Reste à montrer que \(|\orb|=p\), autrement dit que les \(\sigma^r(x)\) pour \(r\in[0,p[\) sont deux-­à-­deux distincts. Soit \(r\) et \(r'\) tels que \( 0\leq r\leq r' < p \) et \(s^r(x)=s^{r'}(x)\). On en déduit que \(\sigma^{r'-r}(x)=x\) et comme \(0\leq r'-r < p\) ceci impose que \(r'=r\).

Cette proposition montre que pour construire l'orbite d'un élément \(x\), il suffit d'itérer ses images par \(\sigma\) tant que la nouvelle image obtenue est différente de \(x\). Considérons par exemple la permutation \(\sigma\in\Sn_{9}\) sui­van­te :

\begin{align} \label{def:perm1} \sigma=\begin{pmatrix} \color{#FF8}1&\color{#F44}2&\color{#FF8}3&\color{#FF8}4&\color{#AAF}5&\color{#AAF}6&\color{#8DF}7&\color{#FF8}8&\color{#AAF}9\\ \color{#FF8}3&\color{#F44}2&\color{#FF8}8&\color{#FF8}1&\color{#AAF}6&\color{#AAF}9&\color{#8DF}7&\color{#FF8}4&\color{#AAF}5 \end{pmatrix}. \end{align}

Calculons l'orbite de \(\color{#FF8}1\). On a \(\sigma({\color{#FF8}1})=3\), puis \(\sigma({\color{#FF8}3})=8\), puis \(\sigma({\color{#FF8}8})=4\) et finalement \(\sigma(4)=1.\) On ob­tient de cette façon quatre orbites pour cette permutation :

\begin{align*} \orb_\sigma({\color{#FF8}1})&=\{{\color{#FF8}1,3,8,4}\},\\ \orb_\sigma({\color{#F44}2})&=\{{\color{#F44}2}\},\\ \orb_\sigma({\color{#AAF}5})&=\{{\color{#AAF}5,6,9}\},\\ \orb_\sigma({\color{#8DF}7})&=\{{\color{#8DF}7}\}.\\ \end{align*}

La représentation sagittale du graphe de cette permutation permet de mieux visualiser les différentes orbites et l'origine du vocabulaire employé :

Les différentes orbites suivant la permutation \(\sigma\).
On appelle support d'une permutation \(\sigma\in\Sn_n\), le sous-ensemble de \(\llbracket 1,\,n\rrbracket \) noté \(\text{supp}(\sigma)\) des éléments de \(\llbracket 1,\,n\rrbracket \) qui ne sont pas fixés par \(\sigma\), i.e. \begin{equation} \text{supp}(\sigma):=\{x\in \llbracket 1,\,n\rrbracket \mid\sigma(x)\not=x\}. \end{equation}

Le support de la permutation \(\sigma\) définie en \((\ref{def:perm1})\) est \(\text{supp}(\sigma)=\{{\color{#FF8}1},{\color{#FF8}3},{\color{#FF8}8},{\color{#FF8}4},{\color{#AAF}5},{\color{#AAF}6},{\color{#AAF}9}\}\). Le support de la permutation iden­tique est l'ensemble vide.

Soit \(n\) un entier tel que \(n\geq 2\). Calculez le support de la permutation \(\sigma\in\Sn_{n}\) définie par \(\sigma(k):=k+1\) si \(k < n\) et \(\sigma(n):=1\). Soit \(a\) et \(b\) deux éléments distincts de \(\llbracket 1,\,n\rrbracket \). Calculez le support de la permutation \(\sigma\in\Sn_{n}\) définie par \(\sigma(a):=b\) et \(\sigma(b):=a\) et qui laisse fixe tous les autres entiers.

Cycles

On appelle cycle toute permutation \(\sigma\in\Sn_n\) telle qu'il existe une unique orbite \(\orb\) qui n'est pas un singleton. Dans ce cas, \(\text{supp}(\sigma)=\orb\) et \(\#\orb\) est appelé la longueur du cycle. Un cycle de longueur \(p\) est appelé un p-cycle et un 2-cycle est appelé une trans­po­si­tion.

La permutation \(\sigma\) définie \((\ref{def:perm1})\) contient donc un \(4\)-cycle et un \(3\)-cycle mais aucune transposition.

Démontrez que toute transposition \(\tau\) est une involution, c'est-à-dire vérifie \(\tau^2={\Id}.\)

À ce stade, nous savons que la restriction d'une permutation \(\sigma\) à une orbite \(\orb{}\) est une bijection (cf. exercice), c'est donc une permutation définie sur l'ensemble \(\orb{}\). En notant \(x_1\) un représentant de \(\orb{}\) et en définissant par récurrence \(x_{k+1}:=\sigma(x_k)\), l'assertion \((\ref{eq:calculorb})\) montre que cette restriction est de la forme

\begin{equation} \label{eq:circulante} \sigma=\begin{pmatrix} x_1&x_2&\cdots&x_{p-1}&x_p\\ x_2&x_3&\cdots&x_{p}&x_1 \end{pmatrix} \end{equation}

Ceci explique pourquoi on a qualifié de cycle une telle permutation (on déplace tous les étudiants d'une rangée d'une place sur leur gauche et le dernier étudiant se place en première position sur la rangée). On en déduit qu'un \(p\)-cycle opère un décalage circulaire sur les éléments de son orbite et laisse fixes les \(n-p\) éléments restants. Ceci justifie que l'on note un \(p\)-cycle \(\sigma\) par le \(p\)-uplet \[(x_1,x_2,\ldots,x_p)\] qui le caractérise puisque \(\sigma(x_i)=x_{i+1}\) pour \(i\in\ab{1}{p-1}\) et \(\sigma(x_p)=x_1\). Une transposition \((x_i,x_j)\) est par­fois notée \(\tau_{x_i,x_j}\).

Soit \((\sigma_i)_{i\in I}\) une famille de cycles d'un ensemble fini \(X\) de supports \(Y_i\) deux-­à-­deux disjoints et de réunion \(Y\). Alors
  1. Les \(\sigma_i\) commutent deux-­à-­deux ce qui permet de définir leur produit \[\sigma:=\prod_{i\in I}\sigma_i.\]
  2. Le produit \(\sigma\) coïncide avec \(\sigma_i\) sur \(Y_i\) et avec l'identité \({\Id}_X\) sur \(X\setminus Y.\)
  3. Les \(Y_i\) sont les orbites suivant \(\sigma\) qui ne sont pas réduites à un élément.

On déduit de l'étude menée le théorème suivant :

Toute permutation \(\sigma\) non identique d'un ensemble fini \(X\) se décompose de manière unique, à l'ordre près des facteurs, en produit de cycles à supports deux-­à-­deux disjoints.
Ce théorème est l'équivalent du théorème fondamental de l'arithmétique qui dit que tout entier naturel se décompose de manière unique, à l'ordre près des facteurs, en produit de facteurs premiers.
La première propriété du lemme ci-dessus est très importante. L'ana­lo­gie permanente entre le calcul sur les nombres et sur les permutations (produit, décomposition, etc.) peut nous conduire à l'erreur car le produit sur les nombres est commutatif alors qu'il ne l'est pas pour les permutations ! Il est en effet tentant d'écrire par réflexe \({\color{red}(\sigma\,\tau)^2=\sigma^2\,\tau^2}\) où \(\sigma\) et \(\tau\) sont deux permutations, alors que \begin{align*} (\sigma\,\tau)^2 &=(\sigma\,\tau)\,(\sigma\,\tau)\\ &=\sigma\,({\color{orange}\tau\,\sigma})\,\tau \end{align*} et qu'en général \({\color{orange}\tau\,\sigma\neq\sigma\,\tau}\), sauf précisément si les supports de \(\tau\) et \(\sigma\) sont disjoints.

Les différents résultats obtenus montrent que l'algorithme que nous avons appliqué pour calculer les différentes orbites détermine également les différents cycles puisque nous avons calculé chaque orbite en itérant la permutation \(\sigma\).

Les cycles d'une décomposition d'une permutation en produit de cycle permutent-ils né­ces­sai­re­ment ?
La réponse est non, considérons le contre-exemple suivant : \[ \sigma= \begin{pmatrix} 1 & 2 & 3\\ 1 & 3 & 2 \end{pmatrix} \] On vérifie aisément que \(\sigma=(1,2)(2,3,1)=(2,3)\) alors que \((2,3,1)(1,2)=(1,3)\).

Vous pouvez voir la décomposition en produit de cycles d'une permutation \(\sigma\) obtenue avec cet al­go­ri­thme en sai­sis­sant la liste des images \(\sigma(i),\ i\in\llbracket 1,\,n\rrbracket \) d'une permutation \(\sigma\) de votre choix dans l'ordre crois­sant des valeurs de \(i\) en les séparant par un espace puis en validant. La signature, l'ordre et le type de la permutation \(\sigma\) sont étudiés un peu plus bas mais sont affichés ici pour regrouper toutes les informations sur \(\sigma\).

\(\sigma:=\,\big(\)\(\big)\).

Soit sous forme matricielle :

\(\sigma=\Big(\)\(\Big)\)
Il y a et on obtient la décomposition en produit de cycles à supports deux-­à-­deux disjoints suivante :
\(\sigma=\,\)

La sig­na­tu­re de cet­te per­mu­ta­tion est égale à

\(\epsilon(\sigma)=(-1)\).

L'ordre de cette permutation est égal à

\(\text{ordre}(\sigma)=\,\),

et son type est égal à

\(\text{type}(\sigma)=\,\)

Le théorème suivant est un résultat bien connu du lecteur, il est simplement mas­qué par le vo­ca­bu­lai­re des permutations. Il dit en substance que l'on peut réorganiser les livres de sa bibliothèque comme on le souhaite en ne permutant jamais plus de deux livres à la fois, ce qui est bien pra­ti­que quand on n'a que deux mains.

Tout \(p\)-cycle \((x_1,x_2,\ldots,x_p)\) sur un ensemble \(X\) se décompose en produit de transpositions, par exemple \begin{equation} \label{eq:prodtrans} (x_1,x_2,\ldots,x_p)=\prod_{i=1}^{p-1}(x_i,x_{i+1}). \end{equation}
Notons \(\sigma:=(x_1,x_2,\ldots,x_p)\) et \(\rho\) le produit des transpositions \((x_i,x_{i+1})\) défini en \((\ref{eq:prodtrans})\). Montrons que \(\sigma=\rho\). Trivialement tout élément \(x\in X\) qui n'appartient pas au support \(\{x_1,\ldots,x_p\}\) de \(\sigma\) est laissé fixe par \(\sigma\) et \(\rho\). Reste à traiter les éléments \(x_i\) dans le support de \(\sigma\). Si \(i < p\), on a \(\sigma(x_i)=x_{i+1}\), mais \begin{align*} \rho(x_i)&=\left(\prod_{j=1}^{i}(x_j,x_{j+1})\right) (x_{i-1},x_{i}){\color{#FF8}(x_i,x_{i+1})}\left(\prod_{j=i+1}^{p}(x_j,x_{j+1})\right)(x_i) \\ \rho(x_i)&=\left(\prod_{j=1}^{i}(x_j,x_{j+1})\right) (x_{i-1},x_{i}){\color{#FF8}(x_i,x_{i+1})}(x_i) \\ \rho(x_i)&=\left(\prod_{j=1}^{i}(x_j,x_{j+1})\right) (x_{i-1},x_{i})(x_{i+1}) \\ &=x_{i+1} \\ \end{align*} Si \(i=p\) alors \(\sigma(x_p)=x_1\), mais (la preuve suivante est informelle, formalisez là avec une récurrence finie) \begin{align*} \rho(x_p)&=\left(\prod_{i=1}^{p-2}(x_i,x_{i+1})\right) {\color{#FF8}(x_{p-1},x_{p})}(x_p) \\ &=\left(\prod_{i=1}^{p-3}(x_i,x_{i+1})\right) {\color{#FF8}(x_{p-2},x_{p-1})}(x_{p-1}) \\ &=\left(\prod_{i=1}^{p-4}(x_i,x_{i+1})\right) {\color{#FF8}(x_{p-3},x_{p-2})}(x_{p-2}) \\ &=\qquad\vdots\\ &={\color{#FF8}(x_1,x_2)}(x_2)\\ &=x_1 \\ \end{align*}
Toute permutation d'un ensemble fini \(X\) de cardinal \(n\geq 2\) se décompose en produit de transpositions.
C'est vrai pour la permutation identité \(\Id_X\) puisque si \(n\geq 2\), on peut trouver deux éléments distincts \(a\) et \(b\) de \(X\) et écrire \(\Id_X=(a,b)(a,b)\). Pour toute autre permutation, nous savons qu'elle se décompose en produit de cycles et le lemme précédent permet de conclure.

Notons que la décomposition en produit de transpositions n'est pas unique. En revanche la parité du nombre de transpositions est constant (en exercice). En reprenant la permutation que vous avez saisie plus haut et en appliquant le lemme ci-dessus pour un cycle quelconque, on obtient la décomposition en produit de transpositions suivante :

\(\sigma=\,\)
Démontrez que si \(\sigma\) est un \(p\)-cycle, alors \(\sigma^p={\Id}\). Quelle est l'inverse d'un \(p\)-cycle ?

Le théorème précédent affirmait que l'on pouvait réorganiser sa bibliothèque en ne permutant que deux livres à la fois, le théorème suivant affirme que l'on peut encore y arriver si ces deux livres sont toujours côte à côte.

Le groupe des permutations \(\Sn_n\) est engendré par la famille de trans­po­si­tions \(\{(i,i+1)\}_{i\in\ab{1}{n-1}}.\)
D'après ce théorème, il faut montrer que toute permutation est un produit de transpositions du type \((i,i+1)\). Nous savons déjà qu'une permutation se décompose en produit de transpositions d'après ce théorème, il suffit donc de montrer que toute transposition \(\tau\) s'écrit comme un produit de trans­po­si­tions du type \((i,i+1)\). Soit \(i\) et \(j\) dans \(\llbracket 1,\,n\rrbracket \) avec \(i < j\) et \(\tau=(i,j).\) Si \(i+1=j\), la per­mu­ta­tion \((i,j)\) est la transposition \((i,i+1)\) et le résultat est vrai. Si \(i+1 < j\), montrons que \begin{equation*} (i,j)={\color{#88F}(j-1,j)}{\color{#FFF}(i,j-1)}{\color{#88F}(j-1,j)} \end{equation*} Calculons l'image de \(i\) et de \(j\) par la permutation produit notée \(\pi\) à droite de l'égalité ci-dessus : \begin{align*} \pi(i)&={\color{#88F}(j-1,j)}{\color{#FFF}(i,j-1)}{\color{#88F}(j-1,j)}(i)\\ &={\color{#88F}(j-1,j)}{\color{#FFF}(i,j-1)}(i)\\ &={\color{#88F}(j-1,j)}(j-1)\\ &=j \end{align*} On obtient de façon similaire \(\pi(j)=i\). Il suffit de recommencer la même décomposition pour \((i,j-1)\) et de proche en proche pour conclure.
Démontrez que l'ordre d'une permutation est le plus petit multiple commun des longueurs des cycles à supports disjoints de cette permutation.
Peut-on réorganiser sa commode (un empilement de tiroirs) comme on le souhaite en ne réalisant que des échanges entre le contenu de tiroirs adjacents ?
Soit \(n\) et \(p\) deux entiers naturels tels que \(0\leq p\leq n\). Combien le groupe \({S}_n\) possède-t-il de \(p\)-cycles ?

Permutations et tris

On se donne une liste*(*) Ce n'est rien d'autre qu'une séquence. \(L\) de \(n\) valeurs dans un ensemble totalement ordonné \((X,\preceq)\) et on veut trier les \(n\) valeurs de cette liste dans l'ordre croissant.

Pour écrire un algorithme basé sur des comparaisons entre éléments de \(X\), on peut toujours supposer que \(X=\ab{1}{n}\) et qu'il est muni de l'ordre naturel \(\leq\). En effet, l'ordre sur \(X\) étant total, on peut toujours numéroter les \(n\) éléments \(x_1,x_2,\ldots,x_n\) de la liste \(L\) de sorte que \[ \forall (i,j)\in\ab{1}{n}^2 \quad (i \leq j)\ \then\ (x_i \preceq x_j). \] ce qui définit un mor­phis­me d'ensembles ordonnés entre \((\ab{1}{n} ,\leq)\) et \((L(\ab{1}{n}),\preceq)\) où \(L(\ab{1}{n})\) est l'ensemble des valeurs de la liste \(L\) (l'image de l'application \(L\)). En triant les valeurs entières, on trie donc les éléments de la liste.

On suppose dorénavant que la liste \(L\) de longueur \(n\) contient exactement les \(n\) entiers de \(1\) à \(n\), autrement dit \(L\) définit explicitement une permutation du groupe symétrique \(\Sn_n\) :

\begin{equation} L=\begin{pmatrix} 1&2&3&\ldots&n\\ L[1]&L[2]&L[3]&\ldots&L[n] \end{pmatrix}. \end{equation}

où \(L[i]\) désigne la \(i\)-ème valeur dans la liste. Pour trier \(L\), on dispose d'une opération notée \(i\overset{L}{\rightleftharpoons} j\) qui échange le contenu des cellules d'indices \(i\) et \(j\) de la liste \(L\). Cette opération est réalisée par l'algorithme suivant :

Echanger(@L,i,j):
   aux ← L[i]
   L[i] ← L[j]
   L[j] ← aux

On connaît évidemment le résultat des courses puisque la liste triée est la liste \([1,2,\ldots,n]\), c'est-à-dire la permutation identité. Mais ce n'est pas tant le résultat du tri qui nous motive que la manière de le réaliser. L'échange \(i\overset{L}{\rightleftharpoons} j\) définit implicitement la transposition \((L[i],L[j])\) et un algorithme de tri comparatif opère en une suite finie d'échanges. Notons \((\tau_k)_{k\in\ab{1}{t}}\) les \(t\) échanges réalisés pour trier la liste \(L\). On vient de mon­trer que \begin{align*} \tau_t\,\tau_{t-1}\,\ldots\,\tau_2\,\tau_1\, L &= {\Id},\\ L &= {\Id}\,(\tau_t\,\tau_{t-1}\,\ldots\,\tau_2\,\tau_1)^{-1},\\ L &= \tau_1\,\tau_2\,\ldots\,\tau_{t-1}\,\tau_t \quad\text{car}\ (s\,t)^{-1}=t^{-1}\,s^{-1}\ \text{et}\ \tau_i=\tau_i^{-1}. \end{align*} Et nous venons donc de décomposer la permutation \(L\) en produit de transpositions. Chaque algo­ri­thme de tri comparatif in situ*(*) qui échan­ge les va­leurs dans la liste est donc une preuve constructive que toute permutation se dé­com­po­se en produit de transpositions. Et on comprend mieux à présent pourquoi la décomposition d'une permutation en produit de transpositions n'a rien d'uni­que vu la diversité des algorithmes de tris com­pa­ra­tifs.

L'algorithme du tri par propagation également appelé tri à bulles, réalise le tri d'une liste uniquement avec des échanges du type \(i\rightleftharpoons i+1\). Le principe est simple, pour toutes les valeurs \(k\) allant de \(n\) à \(2\), on balaie la liste \(L\) de \(i\leftarrow 1\) à \(k\) en faisant l'échange \(i\rightleftharpoons i+1\) si \(L[i+1] \preceq L[i]\).

La grande variété des preuves/algorithmes de tris est due à la recherche d'une décomposition en pro­duit de transpositions qui minimise le nombre de comparaisons et/ou d'échanges entre éléments de la liste.

Signature

Dans la suite \(X\) désigne un ensemble fini de cardinal \(n\).

On appelle signature d'une permutation \(\sigma\in\Sn(X)\) l'entier \begin{equation} \epsilon(\sigma):=(-1)^{n-m} \end{equation} où \(m\) est le nombre d'orbites suivant \(\sigma\). Si \(\epsilon(\sigma)=+1\), on dit que \(\sigma\) est une paire et im­pai­re si \(\epsilon(\sigma)=-1\).

La permutation identité génère \(n\) orbites puisque tous les points sont fixes, donc \(\epsilon({\Id}_X)=n-n=0\). Une transposition \(\tau\) laisse \(n-2\) points fixes et crée une orbite de cardinal \(2\), il y a donc au total \(n-1\) or­bi­tes, d'où \(\epsilon(\tau)=(-1)^{n-(n-1)}=-1\). Un \(p\)-cycle \(\sigma\) laisse \(n-p\) points fixes et crée une unique orbite de taille \(p\), il y a donc \(n-p+1\) orbites, donc \(\epsilon(\sigma)=(-1)^{n-(n-p+1)}=(-1)^{p-1}\).

Soit \(\sigma\) une permutation et \(\tau\) une transposition de \(S(X)\), alors \begin{equation} \epsilon(\sigma\,\tau)=-\epsilon(\sigma). \end{equation}
Notons \(\tau_{a,b}\) cette transposition et \(\sigma':=\sigma\tau_{a,b}\). On cherche à savoir comment les orbites suivant \(\sigma\) vont être perturbées par la transposition \(\tau_{a,b}\). La restriction de \(\tau_{a,b}\) aux orbites qui ne contiennent ni \(a\) ni \(b\) est l'identité, les seules orbites qui sont perturbées par \(\tau_{a,b}\) sont donc uniquement celles qui contiennent \(a\) ou \(b\). Deux cas de figure se présentent, soient \(a\) et \(b\) sont sur la même orbite \(\orb\), soit sur deux orbites distinctes \(\orb\) et \(\orb'\) puisque les orbites suivant \(\sigma\) constituent une partition de l'ensemble \(X\) :
     
À gauche : \(a\) et \(b\) sont sur la même orbite \(\orb\). À droite : \(a\) et \(b\) sont sur deux orbites \(\orb\) et \(\orb'\) distinctes.

Supposons dans un premier temps que \(\{a,b\}\subseteq\orb\) et notons \(p:=|\orb|\geq 2\). Dans ce cas \(a\) (et \(b\)) est un représentant de l'orbite \(\orb\) donc \[\orb=\orb(a)=\{a,\sigma(a),\ldots,\sigma^{p-1}(a)\}\quad\text{et}\ \ \sigma^p(a)=a. \] Puisque \(b\in\orb(a)\), \(b=\sigma^q(a)\) avec \(0 < q\leq p\). Calculons les itérés successifs de \(a\) par la permutation \(\sigma'\). On a \begin{align*} \sigma'(a) &=\sigma(\tau(a)),\\ &=\sigma(b),\\ &=\sigma^{q+1}(a). \end{align*} et \(\sigma'(\sigma^{q+1}(a))=\sigma(\tau(\sigma^{q+1}(a)))\), mais \(\sigma^{q+1}(a)\not\in\{a,b\}\), or la restriction de la transposition \(\tau_{a,b}\) à \(X\setminus\{a,b\}\) est l'identité, donc \[\sigma'(\sigma^{q+1}(a))=\sigma^{q+2}(a)\] et de proche en proche on obtient montre que l'orbite de \(a\) selon \(\sigma'\) est \[a,\;\sigma^{q+1}(a),\;\sigma^{q+2}(a),\;\ldots,\;\sigma^{p-2}(a),\;\sigma^{p-1}(a),\; a.\] Tandis que les itérés de \(b\) selon \(\sigma'\) sont \[b,\;\sigma(b),\;\sigma^2(b),\;\ldots,\;\sigma^{q-1}(b),\;b.\] Autrement dit, l'orbite \(\orb\) a été séparée en deux orbites.

Dans l'autre cas (à droite sur la figure), on a \begin{align*} \orb&=\{a,\sigma(a),\sigma^2(a),\ldots,\sigma^{p-1}(a)\},\\ \orb'&=\{b,\sigma(b),\sigma^2(b),\ldots,\sigma^{q-1}(b)\}.\\ \end{align*} Si on calcule les itérés de \(a\) pour \(\sigma'\), on obtient \[a,\;\sigma(b),\;\sigma^2(b),\;\ldots,\sigma^{q-1}(b),\;b,\;\sigma(a),\;\sigma^2(a),\;\ldots,\;\sigma^{p-1}(a),\;a.\] Autrement dit les orbites \(\orb\) et \(\orb'\) ont fusionné. Dans les deux cas le nombre d'orbites suivant \(\sigma'\) est différent du nombre d'orbites suivant \(\sigma\) d'une unité ce qui change donc le signe de la signature et permet de conclure.

Si \(\sigma\in\Sn(X)\) est le produit de \(k\) transpositions, alors \(\epsilon(\sigma)=(-1)^k\).
L'application signature \(\epsilon:\Sn(X)\rightarrow\{-1,1\}\) est un morphisme du groupe sy­mé­tri­que \((\Sn(X),\circ)\) dans le groupe multiplicatif \((\{-1,1\},\times)\).

Il faut donc déduire de ce corollaire que la signature d'un produit (au sens de la composition des applications) de permutations est le produit (au sens des nombres entiers) de leurs signatures.

Le noyau du morphisme \(\epsilon\) est un sous-groupe normal de \(\Sn(X)\) ap­pe­lé groupe alterné. On le note \(A(X)\) ou parfois \({\mathfrak A}(X)\def\A{{A}}\).

Soit \(\tau\) une transposition. L'application de \(\A(X)\) dans \(\Sn(X)\setminus\A(X)\) définie par \(\sigma\mapsto\tau\sigma\) est une bijection et comme ces deux ensembles constituent une partition de \(\Sn(X)\) qui est de cardinal \(n!\), on a né­ces­sai­re­ment

\begin{equation} |A(X)|=|\Sn(X)\setminus A(X)|=\frac{n!}{2}. \end{equation}

Autrement dit il y a autant de permutations paires que de permutations impaires. Dans le cas où \(\Sn(X)=\Sn_{n}\), le sous groupe alterné est noté \(A_n\) ou \(\A_n\) et on l'appelle groupe alterné de degré n.

Soit \(\sigma\in\Sn_n\). Démontrez que \begin{equation} \epsilon(\sigma)=\prod_{\{i,j\}\in {\mathscr P}_2(\ab{1}{n} )}\frac {\sigma (j)-\sigma (i)}{j-i} \end{equation} où \({\mathscr P}_2(\ab{1}{n} )\) désigne l'ensemble des paires d'éléments de \(\ab{1}{n} \).

Indication : l'application définie par \(\{i,j\}\mapsto\{\sigma(i),\sigma(j)\}\) est une permutation sur \({\mathscr P}_2(\ab{1}{n} )\).

Conjugaison

On rappelle que deux permutations \(\sigma\) et \(\sigma'\) sont conjuguées s'il existe une permutation \(\rho\) telle que \(\sigma'= \rho\,\sigma\,\rho^{-1}\). Cela signifie que l'on peut réaliser la permutation \(\sigma'\) à travers la permutation \(\sigma\) au prix d'une traduction. Métaphoriquement pour calculer \(\sigma'(x)\) on code \(x\) pour \(\sigma\) avec \(\rho^{-1}\), on fait le calcul avec \(\sigma\) et on décode le résultat avec \(\rho\). Nous savons qu'il s'agit d'une relation d'équivalence.

Montrez que la classe de conjugaison de la permutation identique \({\Id}\) est réduite à \({\Id}\) quel que soit le groupe symétrique.
Montrez que les transpositions \((1,2)\) et \((1,3)\) sont conjuguées dans \(\Sn_3\).
Soit \(\sigma=(x_1,x_2,\ldots,x_p)\) un \(p\)-cycle et \(\rho\) une permutation. La permutation con­ju­guée \(\rho\,\sigma\,\rho^{-1}\) de \(\sigma\) par \(\rho\) est le \(p\)-cycle  : \begin{equation} \label{eq:conjuguecycle} (\rho(x_1),\rho(x_2),\ldots,\rho(x_p)). \end{equation} appelé cycle conjugué de \(\sigma\).
On va calculer l'image de chaque élément de \(X\) par les deux applications à gauche et droite de l'égalité (\ref{eq:conjuguecycle}). Pour cela on va partitionner l'ensemble \(X\) en deux classes, l'ensemble \(Y:=\{\rho(x_i)\such i\in\ab{1}{p}\}\) et son complémentaire \(X\setminus Y\).

Calculons tout d'abord l'image des éléments \(\rho(x_i)\), \(i\in\llbracket 1,\,p\rrbracket \) par les deux permutations de part et d'au­tre de l'égalité \((\ref{eq:conjuguecycle})\) : \begin{align} \rho(x_1,x_2,\ldots,x_p)\rho^{-1}(\rho(x_i)) &=\rho(x_1,x_2,\ldots,x_p)(x_i)\\ &=\begin{cases} \rho(x_{i+1})&\text{si}\ i < p,\\ \rho(x_1)&\text{si}\ i = p. \end{cases} \end{align} D'autre part, \begin{align} (\rho(x_1),\rho(x_2),\ldots,\rho(x_p))(\rho(x_i)) &=\begin{cases} \rho(x_{i+1})&\text{si}\ i < p,\\ \rho(x_1)&\text{si}\ i = p. \end{cases} \end{align} On passe aux éléments \(x\in X\setminus Y\). On remarque que \(\forall i\in\llbracket 1,\,p\rrbracket \ \rho^{-1}(x)\not=x_i\) sans quoi \(x=\rho(x_i)\) ce qui contredit \(x\in X\setminus Y\), donc \(\rho^{-1}(x)\) n'appartient pas au support du cycle \((x_1,x_2,\ldots,x_p)\), il est donc un point fixe de ce cycle : \begin{align*} \rho(x_1,x_2,\ldots,x_p)\rho^{-1}(x)=\rho(\rho^{-1}(x))=x. \end{align*} D'autre part \(x\) est fixe pour le cycle \((\rho(x_1),\rho(x_2),\ldots,\rho(x_p))\) puisque \(x\not\in Y\), donc \begin{align*} (\rho(x_1),\rho(x_2),\ldots,\rho(x_p))(x)=x \end{align*}

Soit \(\sigma\) et \(\rho\) deux permutations. La décomposition en produits de cyc­les à supports disjoints de la conjuguée \(\rho\,\sigma\,\rho^{-1}\) de \(\sigma\) est le produit des cycles conjugués de la décomposition en produit de cycles à supports disjoints de \(\sigma\).
En effet, notons \((c_i)_{i\in\llbracket 1,\,k\rrbracket }\) les \(k\) cycles de la décomposition de \(\sigma\). Alors \begin{align*} \rho\sigma\rho^{-1}&=\rho\,{\color{#88F}c_1\,c_2\,c_3\,\ldots\,c_{k-1}\,c_k}\,\rho^{-1}\\ &=\rho\,{\color{#88F}c_1}\,(\rho^{-1}\,\rho)\,{\color{#88F}c_2}\,(\rho^{-1}\,\rho)\,{\color{#88F}c_3}\,\rho^{-1}\ldots\rho\,{\color{#88F}c_{k-1}}\,(\rho^{-1}\,\rho)\,{\color{#88F}c_k}\,\rho^{-1}\\ &=(\rho\,{\color{#88F}c_1}\,\rho^{-1})\,(\rho\,{\color{#88F}c_2}\,\rho^{-1})\,(\rho\,{\color{#88F}c_3}\,\rho^{-1})\ldots(\rho\,{\color{#88F}c_{k-1}}\,\rho^{-1})\,(\rho\,{\color{#88F}c_k}\,\rho^{-1})\\ \end{align*}
Soit \(\sigma\) une permutation et \(c_1\,c_2\ldots\,c_k\) sa décomposition en produit de cyc­les à supports disjoints de longueurs respectives \(p_i:=|c_i|\) croissantes. Le \(k\)-uplet \((p_1,p_2,\ldots,p_k)\) est appelé type de la permutation \(\sigma\).

Notons \(n_i\) le nombre d'orbites de cardinal \(i\in\ab{1}{n} \) suivant la permutation \(\sigma\in\Sn_n\). Les orbites for­mant une partition de \(\ab{1}{n} \), la formule de sommation nous donne

\begin{equation} n=\sum_{i=1}^nn_i. \end{equation}

D'autre part, le type \((p_1,p_2,\ldots,p_k)\) de la permutation \(\sigma\) contient la taille de chaque orbite qui n'est pas réduite à un élément. Autrement dit le nombre \(n_1\) de points fixes de la permutation \(\sigma\), c'est-à-dire le nombre d'orbites réduites à un singleton est donné par

\begin{equation} n_1=n-\sum_{i=1}^k p_i. \end{equation}

Ceci justifie que le type d'une permutation se dispense de faire apparaître les longueurs 1 des orbites réduites à un élément.

Nous avons vu que la permutation conjuguée d'un cycle par une permutation \(\rho\) est le cycle constitué des images des éléments du cycle par \(\rho\), cf. \((\ref{eq:conjuguecycle})\). Par conséquent :

Deux permutations sont conjuguées si et seulement si elles ont même type.

On en déduit immédiatement que le nombre de types de permutations du groupe \(\Sn_n\) distincts est égal au nombre de façons possibles d'écrire l'entier \(n\) comme la somme d'une suite croissante d'en­tiers non-nuls. Une telle somme est qua­li­fiée de par­ti­tion d'un en­tier. Par exemple, pour \(n=4\), on vé­ri­fie aisément que l'on a exactement les \(5\) par­ti­tions sui­van­tes :

\begin{align*} 4 &=1+1+1+1\quad\text{type vide}\ (\,)\\ &=1+1+2\quad\text{type}\ (2)\\ &=2+2\quad\text{type}\ (2,2)\\ &=1+3\quad\text{type}\ (3)\\ &=4\quad\text{type}\ (4) \end{align*}

Le type vide est celui de la permutation identité.

Le nombre de classes de conjugaison du groupe \({S}_n\) est égal au nombre de partitions de l'entier \(n\).
Combien y-a-t-il de partitions de l'entier \(n=5\) ?
Déterminez les classes de conjugaison des groupes \(\Sn_3\) et \(\Sn_4\).
Soit \(n\) et \(k\) deux entiers naturels non-nuls. Le nombre \(p(n,k)\) de par­ti­tions de l'entier \(n\) en \(k\) parties est \begin{equation} \label{rec:pnk} p(n,k):=\begin{cases} p(n–1, k–1) + p(n–k, k) &\text{si}\ 1 < k < n,\\ 1&\text{si}\ k=1\ \text{ou}\ k=n,\\ 0&\text{si}\ k > n. \end{cases} \end{equation}

En corollaire, on sait à présent que le nombre de partitions \(p(n)\) d'un entier \(n > 0\), c'est-à-dire le nombre de type différents de permutations est égal à \begin{equation} p(n)=\sum_{k=1}^np(n,k). \end{equation}

Soit \(\sigma\in\Sn_n\) une permutation. Tout couple \((i,j)\in\ab{1}{n}^2\) tel que \begin{equation} (i < j)\ \wedge\ (\sigma(i) > \sigma(j)) \end{equation} est appelé inversion de \(\sigma\in\Sn_n\).
Le nombre total d'inversions du groupe \(S_n\) est égal à \begin{equation} n!\ \frac{n(n-1)}{4} \end{equation}
Soit \(\sigma\) une permutation de \({\frak S}_n\). Notons \(\overline{\sigma}\) la permutation miroir de \(\sigma\) définie par \[ \forall i\in\ab{1}{n} ,\quad\overline{\sigma}(i):=\sigma(n-i+1). \] Par construction, \((i,j)\) est une inversion de \(\sigma\) si et seulement \((n-j+1,n-i+1)\) n'est pas une inversion de \(\overline{\sigma}\). Autrement dit, en parcourant tous les couples \((i,j)\) tels que \(i < j\), on peut les partitionner selon qu'il s'agit d'une inversion de \(\sigma\) ou de \(\overline{\sigma}\), et la formule de sommation nous permet d'affirmer que le nombre total d'inversions de ces deux permutations est égal au nombre de couples \((i,j)\) tels que \(i < j\), à savoir \(\frac{n(n-1)}{2}\). En décrivant tous ces couples, chaque permutation du groupe symétrique \(S_n\) a été considérée deux fois, il y a donc \[n!\ \frac{n(n-1)}{4}.\] inversions au total.

Ces résultats seront utiles dans l'analyse de la complexité des algorithmes de tri en particulier.

Soit \(\sigma\in{S}_n\) une permutation, \(k_1\) le nombre de ses orbites de taille \(1\) et \(k_p,\ \ {p\in\ab{2}{n}}\) le nombre de \(p\)-cycles dans sa décomposition en produit de cycles à supports disjoints. Montrez que \(\sigma\) a \[\frac{n!}{\displaystyle\prod_{p=1}^{n}\left(p^{k_p}k_p!\right)}\] conjugués.

Étude du taquin

Nous pouvons à présent étudier le problème du taquin et répondre à la question initiale. On nu­mé­ro­te les cases du taquin dans l'or­dre de lecture (cf. tableau à gauche ci-dessous), et on numérote éga­le­ment les 15 pièces du taquin de \(1\) à \(15\). Le numéro \(16\) est attribué à une pièce virtuelle, la pièce vide.

1234
5678
9101112
13141516
  
1234
5678
9101112
131514
À gauche : numérotation des cases du taquin. À droi­te : positions des pièces en configuration de Loyd.

En associant à chaque numéro de case du taquin le numéro de la pièce qui y est placée, la disposition des \(16\) pièces sur le taquin définit une permutation \(\sigma\in\Sn_{16}\). On l'appelera dans la suite la con­fi­gu­ra­tion du taquin. La con­fi­gu­ra­tion du taquin proposée par Loyd est la permutation :

\begin{equation} \sigma=\begin{pmatrix} 1&2&3&4&5&6&7&8&9&10&11&12&13&\color{#88F}14&\color{#88F}15&16\\ 1&2&3&4&5&6&7&8&9&10&11&12&13&\color{#88F}15&\color{#88F}14&16\\ \end{pmatrix} \end{equation}

Elle ne contient qu'un seul cycle d'ordre 2, c'est la transposition \({\color{#88F}(14,15)}\).

Comment se traduit le déplacement d'une pièce \(k\) sur le taquin ? Compte tenu de la règle du jeu, on ne peut échanger la pièce \(k\) qu'avec la pièce vide numérotée \(16\). Autrement dit, un mouvement, quand il est possible, est nécessairement une transposition de la forme \((k,16)\) mais cette condition n'est pas suffisante. Pour qu'une transposition \((k,16)\) soit possible, il faut également que les pièces \(k\) et \(16\) soient ad­ja­cen­tes, c'est-à-dire qu'elles aient un côté com­mun.

Soit \(\sigma\) la permutation associée à une configuration du taquin. Nous dirons qu'une transposition \(\tau\) est compatible avec la configuration \(\sigma\) si et seulement si elle est de la forme \(\tau=(16,k)\) et que les pièces \(k\) et \(16\) sont ad­ja­cen­tes sur le taquin. Dans ce cas, \(\tau\sigma\) est une nouvelle configuration du taquin, on dira donc plus généralement qu'une permutation \(\pi\) est com­pa­ti­ble avec la configuration \(\sigma\) si \(\pi\) est dé­com­po­sa­ble en un produit de \(n\) transpositions \[\pi=\tau_{n}\,\tau_{n-1}\,\ldots\tau_2\,\tau_1.\] telles que \(\forall i\in\ab{1}{n} \), \(\tau_i\) est compatible avec le produit \[\tau_{i-1}\tau_{i-2}\ldots\tau_{1}\sigma.\] Ce qui signifie ni plus ni moins qu'en partant de la configuration \(\sigma\), les transpositions \(\tau_1\) puis \(\tau_2\), etc. sont possibles dans cet ordre.

Pour résoudre une configuration \(\sigma\) du taquin, et celle de Loyd en particulier, il faut donc remettre toutes les pièces dans l'ordre, c'est-à-dire trouver une suite finie \(({\color{#FF8}\tau_i})_{i\in\ab{1}{n} }\) de trans­po­si­tions com­pa­ti­bles avec \(\sigma\) telle que son produit à gauche avec \(\sigma\) est la permutation iden­ti­té, soit :

\begin{equation} \label{eq:sigmataquin} {\color{#FF8}\tau_n\,\tau_{n-1}\,\ldots\,\tau_2\,\tau_1}\sigma={\Id}. \end{equation}

Isolons \(\sigma\) dans l'équation \((\ref{eq:sigmataquin})\). L'inverse d'un produit de bijections est le produit inverse des bi­jec­tions réciproques (cf. exercice) et toute transposition \(\tau\) est une involution donc \(\tau^{-1}=\tau\), d'où \begin{equation} \label{eq:isolesigma} \sigma={\color{#FF8}\tau_1\,\tau_{2}\,\ldots\,\tau_{n-1}\,\tau_n}. \end{equation}

Nous dirons donc dans la suite qu'une configuration \(\sigma\) du taquin est résoluble s'il existe un produit de transpositions compatibles avec \(\sigma\) satisfaisant \((\ref{eq:isolesigma})\), insoluble sinon. Si une configuration est ré­so­lu­ble, les mouvements à réaliser effectivement sur le taquin sont les transpositions \(\tau_i\) dans l'ordre croissant des indices. Si un tel produit existe, sa signature doit bien sûr être égale à celle de \(\sigma\) :

\begin{align} \notag\epsilon(\sigma)&=\epsilon({\color{#FF8}\tau_1\,\tau_{2}\,\ldots\,\tau_{n-1}\,\tau_n}),\\ \notag\epsilon(\sigma)&=\prod_{i=1}^n\epsilon({\color{#FF8}\tau_i}),\\ \label{eq:lastloyd}\epsilon(\sigma)&=(-1)^n. \end{align}

Ces deux dernières égalités sont justifiées par le fait que la signature d'une transposition est égale à \(-1\) et que la signature d'un produit de permutations est égal au produit des signatures de ces per­mu­ta­tions (cf. corollaire).

La signature de la configuration de Loyd \(\sigma=(14,15)\) est égale à \(-1\) puisqu'il s'agit d'une trans­po­si­tion. On déduit de \((\ref{eq:lastloyd})\) que l'on doit avoir \(-1=(-1)^n,\) autrement dit que le nombre \(n\) de trans­po­si­tions dans le produit \(\color{#FF8}\pi\) doit être impair. Colorions les cases du taquin pour en faire un damier noir et blanc. La con­fi­gu­ra­tion initiale de Loyd est :

1234
5678
9101112
131514
Configuration de Loyd sur un taquin en damier.

Une transposition de la forme \((16,k)\) fait passer alternativement la pièce vide d'une case noire à une case blanche. Pour que la pièce vide retrouve sa position initiale 16 sur le damier, le produit \({\color{#FF8}\pi}\) doit donc nécessairement contenir un nombre pair de transpositions, la configuration de Loyd est par conséquent insoluble. Nous venons de démontrer le théorème suivant :

Une configuration du taquin \(\sigma\) résoluble est paire.

Une condition nécessaire pour que taquin soit résoluble est que la configuration ini­tia­le définisse une permutation \(\sigma\) du groupe alterné \(\A_{15}\), si l'on suppose que la pièce vide est en position \(16\).

Cette condition est-elle suffisante ? Il faut garder à l'esprit que pour résoudre le taquin, il faut disposer d'un produit de transpositions compatible avec la permutation \(\sigma\) associée à la configuration initiale du taquin. Par exemple, seules les transpositions \((16,12)\) et \((16,15)\) sont compatibles avec la configuration de Loyd.

Nous allons montrer dans un premier temps que le groupe alterné \(\A_n\) est engendré par les \(3\)-cycles du type \((1,2,s)\) et dans un deuxième temps que tous les trois cycles de ce type sont décomposables en produit de trans­po­si­tions compatibles avec l'identité.

Le groupe alterné \(\A_n\) est engendré par les \(3\)-cycles.
Montrons que le sous-groupe \(G\) de \(\Sn_n\) engendré par les \(3\)-cycles est contenu dans \(\A_n\). Soit \((x,y,z)\) un \(3\)-cycle, on peut le décomposer en le produit des deux transpositions \((x,y)(y,z)\). Sa signature est donc \(+1\), il appartient bien à \(\A_n\). Évidemment la composition de \(3\)-cycles conserve la parité, le groupe \(G\) est donc un sous-groupe de \(\A_n\). Réciproquement, montrons que tout élément de \(\A_n\) appartient à \(G.\) Soit \(\sigma\in\A_n\), elle admet une décomposition en un produit de \(2k\) transpositions \((\tau_i)_{i\in\ab{1}{2k}}\) que l'on peut apparier comme suit : \[ \sigma=(\tau_1\tau_2)\,(\tau_3\tau_4)\,\ldots\,(\tau_{2k-1}\tau_{2k}). \] Observons un seul appariement \(\tau_i\tau_{i+1}\), il y a quatre situations possibles :
  1. \((i,j)\,(i,j)={\Id}\),
  2. \((i,j)\,(i,k)=(i,k,j)\),
  3. \((i,j)\,(j,k)=(i,j,k)\),
  4. \((i,j)\,(k,l)=(i,j)\,{\color{#88F}(j,k)\,(j,k)}\,(k,l)=(i,j,k)\,(j,k,l)\).
et dans tous les cas, on peut l'écrire comme un produit de \(3\)-cycles.
Le groupe alterné \(\A_n\) est engendré par les \(3\)-cycles de la forme \((1,2,s)\) avec \(s\in\llbracket 3,\,n\rrbracket \).
D'après le théorème précédent, il suffit de montrer que tout \(3\)-cycle \((i,j,k)\) peut se décomposer en produit de \(3\)-cycles de la forme \((1,2,r)\). Puisque \((i,j,k)=(j,k,i)=(k,i,j)\), on peut toujours supposer que \(i\) est le plus petit des trois. Il y quatre cas de figure : \begin{align*} (1,j,2) &= (1,2,j)^{-1},\\ (1,j,k) &= (1,2,k)\;(1,2,j)^{-1},\\ (2,j,k) &= (1,2,k)^{-1}\;(1,2,j),\\ (i,j,k) &= (1,2,k)\;(1,2,j)^{-1}\;(1,2,i)\;(1,2,k)^{-1}. \end{align*}

Les \(3\)-cycles du type \((1,2,s)\) pour \(\A_{15}\) sont au nombre de \(13\) :

\begin{equation} \label{troiscycles} (1,2,{\color{#88F}3}),\ (1,2,{\color{#88F}4}),\ (1,2,{\color{#88F}5}),\ldots,\ (1,2,{\color{#88F}14}),\ \text{et}\ (1,2,{\color{#88F}15}). \end{equation}

Et nous allons prouver que l'on peut réaliser n'importe lequel de ces \(3\)-cycles sur le taquin.

Soit \(k\in\N\) tel que \(k\geq 2\). On ap­pel­le circuit de longueur \(k\) toute séquence \((c_i)_{i\in\llbracket 1,\,k\rrbracket }\) de cases distinctes du taquin telles que deux cases con­sé­cu­ti­ves de cette suite sont toujours adjacentes et telle que \(\def\vide{{\color{#C22}16}}c_k\) est adjacente à \(c_1\). La suite des cases numéro 2, 3, 4, 8, 12, 16, 15, 14, 13, 9, 5, 6, ma­té­ria­li­sée en rouge dans le taquin ci-dessous est un circuit de longueur \(12\) :

1234
5678
9101112
13141516
Un circuit de longueur 12 dans le taquin.
Démontrez qu'en coloriant les cases du taquin en damier, deux cases adjacentes d'un circuit sont de couleurs différentes. Démontrez que la longueur d'un cir­cuit est toujours paire. Quelle est la longueur des circuits les plus courts ?

Dorénavant nous noterons \(\def\tua{{\color{#F44}\tau}}\tua_i:=(16,i)\), \(i\in\ab{1}{15}\) les 15 transpositions possibles sur le taquin. Soit \(\sigma\) la permutation associée à une configuration du taquin. Si on note \(p_i\) les pièces qui sont placées sur les cases \(c_i\) d'un circuit \((c_i)_{i\in\ab{1}{k}}\) respectivement, on a donc \[\forall i\in\ab{1}{k}\quad \sigma(c_i)=p_i.\]

Soit \(\sigma\) une configuration du taquin et \((c_i)_{i\in\ab{1}{k+1}}\) un circuit de longueur \(k+1\) contenant res­pec­ti­ve­ment les pièces \(p_i\) avec \(p_{k+1}=16\) la pièce vide. Alors le produit des \(k+1\) transpositions \begin{equation} \label{eq:permcirc} \pi:=\tua_{p_1}\;\tua_{p_k}\;\tua_{p_{k-1}}\;\ldots\;\tua_{p_3}\;\tua_{p_2}\;\tua_{p_1}\; \end{equation} est compatible avec \(\sigma\). D'autre part, \(\pi\,\sigma\) réalise un décalage circulaire des éléments \(p_i\) dans les \(k\) pre­miè­res cases du circuit \(c_i\).
Dans les grandes lignes : il faut généraliser l'exemple qui suit en partant d'un circuit quelconque et montrer que le contenu d'une case n'est modifié que par une seule trans­po­si­tion (ce qui explique la définition d'un circuit ici qui ne repasse jamais deux fois par la même case, le vocabulaire de la théorie des graphes parle de circuit hamiltonien) et que ce contenu après la transposition est bien le contenu de la case adjacente avant la transposition.

Exemple. On considère une configuration \(\sigma\) du taquin et le circuit \(c:=(2,3,7,11,10,9,5,1)\) de lon­gueur 8 sur lequel sont placées les pièces \(a,\) \(b,\) \(c,\) \(d,\) \(e,\) \(f,\) \(g\) et \(\vide\) respectivement. Calculons \(\pi\sigma\) avec le produit \(\pi\) défini par \[\pi:=\tua_a\,\tua_g\,\tua_f\,\tua_e\,\tua_d\,\tua_c\,\tua_b\,\tua_a.\] La pièce vide et la pièce adjacente \(k\) de la trans­po­si­tion \(\tau_k\) ont leur côté commun en poin­til­lés :

 
\(a\)\(b\)
\(g\)\(c\)
\(f\)\(e\)\(d\)
 
\(\tua_{a}\)
\(a\)\(b\)
\(g\)\(c\)
\(f\)\(e\)\(d\)
 
\(\tua_{b}\)
\(a\)\(b\)
\(g\)\(c\)
\(f\)\(e\)\(d\)
 
\(\tua_{c}\)
\(a\)\(b\)\(c\)
\(g\)
\(f\)\(e\)\(d\)
 
\(\tua_{d}\)
\(a\)\(b\)\(c\)
\(g\)\(d\)
\(f\)\(e\)
\(\tua_{e}\)
\(a\)\(b\)\(c\)
\(g\)\(d\)
\(f\)\(e\)
 
\(\tua_{f}\)
\(a\)\(b\)\(c\)
\(g\)\(d\)
\(f\)\(e\)
 
\(\tua_{g}\)
\(a\)\(b\)\(c\)
\(d\)
\(g\)\(f\)\(e\)
 
\(\tua_{a}\)
\(b\)\(c\)
\(a\)\(d\)
\(g\)\(f\)\(e\)
Rotation des pièces autour d'un circuit sur le taquin.

On a montré que le produit \(\pi:=\tua_a\,\tua_g\,\tua_f\,\tua_e\,\tua_d\,\tua_c\,\tua_b\,\tua_a\) est compatible avec la permutation \(\sigma\) et en cal­cu­lant \(\pi\,\sigma\), on a remplacé la séquence \(\color{#AAF}(a,b,c,d,e,f,g)\) par la séquence \(\color{#AAF}(b,c,d,e,f,g,a)\) sur ce circuit et il suffit d'itérer \(\pi\) pour faire tourner ces pièces autour du circuit en laissant toutes les autres fixes.

Dans le cas particulier où le circuit est un carré \(2\times 2\), on a le produit suivant (on ne représente plus les autres pièces qui sont fixes) :

 
\(a\)
\(c\)\(b\)
 
\(\tua_{a}\)
\(a\)
\(c\)\(b\)
 
\(\tua_{b}\)
\(a\)\(b\)
\(c\)
 
\(\tua_{c}\)
\(a\)\(b\)
\(c\)
 
\(\tua_{a}\)
\(b\)
\(a\)\(c\)
Création d'un \(3\)-cycle sur le taquin.

Ce qui réalise une rotation des trois valeurs \(\color{#AAF}(a,b,c)\). Par exemple, en partant de la configuration iden­ti­té \(\sigma:={\Id}\), on obtient le \(3\)-cycle \((11,12,15)\) à l'aide des quatre transpositions : \[\tua_{15}\,\tua_{12}\,\tua_{11}\,\tua_{15}.\]

1234
5678
9101112
131415
  
1234
5678
9101215
131411
Création du \(3\)-cycle \((11,12,15)\) sur le taquin.

Mais nous cherchons à construire les \(3\)-cycles particuliers de \((\ref{troiscycles})\) pour en­gen­drer le groupe \(\A_{15}\). Le lemme suivant est évident mais important.

On peut déplacer la pièce vide sur n'importe quelle case \(i\in\ab{1}{16}\) du taquin et il faut au plus \(6\) transpositions \(\tua_{k}\) pour ce faire.
Quelle que soit la position initiale de la pièce vide sur le taquin, il y a au plus trois colonnes et trois lignes à parcourir pour arriver à la case \(i\).

Nous allons montrer comment obtenir le cycle \(\color{#AAF}(9,10,13)\) avec les techniques de trans­po­si­tion pré­sen­tées. On note \(\sigma:=\tua_{14}\tua_{15}\) la permutation qui déplace la pièce vide à la case 14. On fait alors tourner \(9,\) \(10\) et \(13\) autour du circuit grâce au produit \(\tua_{13}\,\tua_{10}\,\tua_{9}\,\tua_{13}\) et on ramène la pièce vide en case 16 :

 
1234
5678
9101112
131415
 
\(\sigma\)
1234
5678
9101112
131415
 
\(\tua_{13}\,\tua_{9}\,\tua_{10}\,\tua_{13}\)
1234
5678
10131112
91415
   
\(\sigma^{-1}\)
1234
5678
10131112
91415
Réalisation du \(3\)-cycle \((9,10,13)\) sur le taquin.

On a donc montré à l'aide d'une conjugaison que : \begin{align*} (9,10,13)&=\sigma^{-1}\,\tua_{13}\,\tua_{9}\,\tua_{10}\,\tua_{13}\,\sigma,\\ &=(\tua_{15}\,\tua_{14})\,\tua_{13}\,\tua_{9}\,\tua_{10}\,\tua_{13}\,(\tua_{14}\,\tua_{15}). \end{align*}

Le programme que vous avez pu utiliser en début de chapitre et qui résout le problème du taquin dans le cas où la permutation \(\sigma\in\A_{16}\) applique exactement la stratégie que nous venons de déployer. Résumons :

  1. On décompose \(\sigma\) en produit de cycles (cf. théorème),
  2. On décompose chaque cycle du produit en produit de transpositions (cf. théorème),
  3. On construit un produit de \(3\)-cycles en appariant ces transpositions (cf. théorème),
  4. On décompose ces \(3\)-cycles en \(3\)-cycles du type \((1,2,s)\) (cf. proposition),
  5. On calcule l'inverse de ce produit,
  6. Pour chaque élément du produit inverse, on exécute la séquence de déplacements appropriés sur le taquin.

Vous pouvez voir ces étapes en faisant apparaître la console javascript dans votre na­vi­ga­teur (sous Chromium, il suffit de cliquer sur \(\boldsymbol\vdots\) en haut à droite, puis de sélectionner "Plus d'outils" et "Outils de développement").

Vous avez pu constater que le nombre de mouvements pour remettre les pièces dans l'ordre est con­sé­quent, quel est le nombre minimum de déplacements nécessaires pour résoudre une configuration ? Peut-on simplifier les produits de \(3\)-cycles ?

Construisez le \(3\)-cycle \((1,2,3)\) à l'aide de transpositions compatibles. Indication : considérez le circuit formé par les \(12\) cases en bordure du taquin en configuration identité et faites tourner les \(11\) pièces autres que la pièce vide d'une position dans le sens anti-horaire. Déplacez la pièce vide sur la case numéro \(6\) et faites tourner les pièces \((1,2,3)\) puis ramenez la pièce vide en position \(16\). Vérifiez que \((1,2,4)\) est le conjugué de \((1,2,3)\) par \((3,4,8,12,15,11,7)\).
En vous inspirant de cet exemple, construisez les \(3\)-cycles suivants : \begin{align*} &(1,2,5),&\quad&(6,11,7),&\quad&(3,6,7),\\ &(5,9,6),&\quad&(6,10,7),&\quad&(3,8,4),\\ &(11,15,12),&\quad&(10,14,11),&\quad&(9,13,10).\\ \end{align*} Calculer le conjugué de \((1,6,2)\) avec \((5,9,6)\). Avec d'autres conjugaisons, trouvez tous les \(3\)-cycles man­quants.

Travaux pratiques

En séance

Dans toute la suite, une permutation \(\sigma\) de \({S}_n\) est codée par le \(n\)-uplet \((\sigma(1),\sigma(2),\ldots,\sigma(n))\) sous forme de tuple Python. Comme les indices des types énumérés commencent à 0 et pas à 1 on décrémentera la valeur des images. Autrement dit la permutation \begin{pmatrix} 1&2&3&4\\ \color{#FF8}3&\color{#FF8}2&\color{#FF8}1&\color{#FF8}4 \end{pmatrix} sera codée par le tuple (2,1,0,3). La saisie d'une permutation et son affichage resteront en revanche conformes aux notations mathématiques usuelles. Ainsi, pour lire et afficher une permutation, vous utiliserez la fonction et la procédure suivantes, la première renvoie un tuple de valeurs entières à partir de la chaîne de caractère correspondante lue au clavier :

def Lire():
   chaine = input("Permutation = ")
   return tuple([int(x)-1 for x in chaine.split()])

def Ecrire(s):
    print('(',end='')
    for i in range(len(s) - 1):
        print(s[i] + 1, end=',')
    print(s[len(s) - 1] + 1,end=')\n')
Écrivez une fonction EstPermutation(s) qui décide (renvoie True ou False) si le tuple code une permutation ou non. Indications : Utilisez une liste B de booléens de même longueur que s tous initialisés à False qui permettra de marquer les valeurs rencontrées en parcourant s.
Écrivez une fonction Inverser(s) qui renvoie le tuple codant la permutation inverse de la permutation codée par le tuple \(s\).
Écrivez une fonction Composer(s,t) qui renvoie le tuple codant la composition \(s\circ t\) des permutations codées par les tuples \(s\) et \(t\). Vérifiez votre fonction en composant une permuation avec son inverse calculée à l'ade de la fonction précédente.
Écrivez une fonction Orbite(k,s) qui renvoie le tuple correspondant à l'orbite de \(k\) pour la permutation codée par le tuple \(s\).
Écrivez une fonction Cycles(s) qui décompose une permutation s en produit de cycles à supports disjoints. Cette décomposition sera représentée par un tuple de tuples. Indication : On utilisera une liste B de \(n\) booléens initialisés à True telle que \(B[i]\) est vrai si et seulement si l'orbite de \(i+1\) n'a pas encore été calculée. Vous écrirez une fonction auxiliaire Suivant(B,i).
Écrivez une fonction Transpositions(s) qui décompose une permutation s en produit de trans­po­si­tions.
Écrivez en Python une fonction Signature(s) qui calcule la signature de la permutation s passée en paramètre. NB. Vous pouvez calculer la signature avec la formule du cours \((-1)^{n-m}\) où \(m\) est le nombre d'orbites (attention, ce n'est pas le nombre de cycles, aucune valeur fixe pour la permutation n'est un cycle, mais constitue pourtant une orbite de taille \(1\)), ou utiliser la décomposition de la permutation en produit de cycles. En effet, un \(p\)-cycle se décompose en produit de \(p-1\) transposition dont la signature est donc \((-1)^{p-1}\).

Compléments hors séance

Après avoir étudié le chapitre sur l'arithmétique, démontrez que le plus petit commun multiple des deux entiers naturels \(a\) et \(b\) (noté \([a,b]\)) est égal au quotient

\[[a,b]=\frac{a\, b}{(a,b)}\]

où \((a,b)\) désigne le pgcd de \(a\) et \(b\). Soit \(n\) un entier \(n\geq 3\). Démontrez par récurrence que pour une séquence d'entiers naturels \(a_1,a_2,\ldots, a_n\) on a

\begin{equation} \label{eq:ppcm} [a_1,a_2,\ldots,a_n]= [a_1,[a_2,a_3,\ldots,a_n]]. \end{equation}
Écrivez une fonction Python PGCD(a,b) qui calcule le pgcd des deux entiers naturels \(a\) et \(b\).
Utilisez la propriété \((\ref{eq:ppcm})\) pour écrire une fonction (itérative) Python PGCD(tuple) qui calcule le ppcm des entiers contenus dans le tuple passé en paramètre.
Utilisez les résultats ci-dessus pour écrire une fonction Python ordre(s) qui calcule l'ordre de la permutation passée en paramètre.
Écrivez une fonction Python type(s) qui calcule le type de la permutation passée en paramètre.
Écrivez une fonction Python Conjuguer(s,r) qui calcule la conjuguée de la permutation \(s\) par \(r\).