Théorème 5.1.1.
Le groupe symétrique sur \(n\) lettres, \(S_n\text{,}\) est un groupe à \(n!\) éléments, où la loi de composition interne est la composition des applications.
Section 5.1 Définitions et notation
En général, les permutations d’un ensemble \(X\) forment un groupe \(S_X\text{.}\) Si \(X\) est un ensemble fini, on peut supposer \(X=\{ 1, 2, \ldots, n\}\text{.}\) Dans ce cas, on écrit \(S_n\) au lieu de \(S_X\text{.}\) Le théorème suivant affirme que \(S_n\) est un groupe. On appelle ce groupe le groupe symétrique sur \(n\) lettres.
Démonstration.
L’élément neutre de \(S_n\) est simplement l’application identité qui envoie \(1\) sur \(1\text{,}\) \(2\) sur \(2\text{,}\) \(\ldots\text{,}\) \(n\) sur \(n\text{.}\) Si \(f : S_n \rightarrow S_n\) est une permutation, alors \(f^{-1}\) existe, puisque \(f\) est bijective ; ainsi, toute permutation possède un inverse. La composition des applications est associative, ce qui rend l’opération de groupe associative. Nous laissons la démonstration que \(|S_n|= n!\) en exercice.
Un sous-groupe de \(S_n\) est appelé un groupe de permutations.
Exemple 5.1.2.
Considérons le sous-groupe \(G\) de \(S_5\) constitué de la permutation identité \(\identity\) et des permutations
\begin{align*}
\sigma
& =
\begin{pmatrix}
1 & 2 & 3 & 4 & 5 \\
1 & 2 & 3 & 5 & 4
\end{pmatrix}\\
\tau
& =
\begin{pmatrix}
1 & 2 & 3 & 4 & 5 \\
3 & 2 & 1 & 4 & 5
\end{pmatrix}\\
\mu
& =
\begin{pmatrix}
1 & 2 & 3 & 4 & 5 \\
3 & 2 & 1 & 5 & 4
\end{pmatrix}\text{.}
\end{align*}
Le tableau suivant indique comment multiplier les éléments dans le groupe de permutations \(G\text{.}\)
\begin{equation*}
\begin{array}{c|cccc}
\circ & \identity & \sigma & \tau & \mu \\ \hline
\identity & \identity & \sigma & \tau & \mu \\
\sigma & \sigma & \identity & \mu & \tau \\
\tau & \tau & \mu & \identity & \sigma \\
\mu & \mu & \tau & \sigma & \identity
\end{array}
\end{equation*}
Remarque 5.1.3.
Bien qu’il soit naturel de multiplier les éléments d’un groupe de gauche à droite, les fonctions se composent de droite à gauche. Soient \(\sigma\) et \(\tau\) des permutations sur un ensemble \(X\text{.}\) Pour composer \(\sigma\) et \(\tau\) comme des fonctions, on calcule \((\sigma \circ \tau)(x) = \sigma( \tau(x))\text{.}\) C’est-à-dire que l’on applique d’abord \(\tau\text{,}\) puis \(\sigma\text{.}\) Il existe plusieurs façons d’aborder cette incohérence. Nous adopterons la convention de multiplier les permutations de droite à gauche. Pour calculer \(\sigma \tau\text{,}\) on applique d’abord \(\tau\text{,}\) puis \(\sigma\text{.}\) C’est-à-dire que par \(\sigma \tau (x)\) on entend \(\sigma( \tau( x))\text{.}\) (Une autre façon de résoudre ce problème serait d’écrire les fonctions à droite ; c’est-à-dire qu’au lieu d’écrire \(\sigma(x)\text{,}\) on pourrait écrire \((x)\sigma\text{.}\) On pourrait également multiplier les permutations de gauche à droite pour s’accorder avec la façon habituelle de multiplier les éléments dans un groupe. Certes, toutes ces méthodes ont été utilisées.
Exemple 5.1.4.
La multiplication des permutations n’est généralement pas commutative. Posons
\begin{align*}
\sigma
& =
\begin{pmatrix}
1 & 2 & 3 & 4 \\
4 & 1 & 2 & 3
\end{pmatrix}\\
\tau
& =
\begin{pmatrix}
1 & 2 & 3 & 4 \\
2 & 1 & 4 & 3
\end{pmatrix}\text{.}
\end{align*}
Alors
\begin{equation*}
\sigma \tau
=
\begin{pmatrix}
1 & 2 & 3 & 4 \\
1 & 4 & 3 & 2
\end{pmatrix}\text{,}
\end{equation*}
mais
\begin{equation*}
\tau \sigma
=
\begin{pmatrix}
1 & 2 & 3 & 4 \\
3 & 2 & 1 & 4
\end{pmatrix}\text{.}
\end{equation*}
Sous-section 5.1.1 Notation cyclique
La notation que nous avons utilisée jusqu’à présent pour représenter les permutations est, pour le moins, fastidieuse. Pour travailler efficacement avec les groupes de permutations, nous avons besoin d’une méthode plus simple pour écrire et manipuler les permutations.
Une permutation \(\sigma \in S_X\) est un cycle de longueur \(k\) s’il existe des éléments \(a_1, a_2, \ldots,
a_k \in X\) tels que
\begin{align*}
\sigma( a_1 ) & = a_2\\
\sigma( a_2 ) & = a_3\\
& \vdots\\
\sigma( a_k ) & = a_1
\end{align*}
et \(\sigma( x) = x\) pour tout autre élément \(x \in X\text{.}\) On notera \((a_1, a_2, \ldots,
a_k )\) le cycle \(\sigma\text{.}\) Les cycles sont les éléments constitutifs de toutes les permutations.
Exemple 5.1.5.
La permutation
\begin{equation*}
\sigma =
\begin{pmatrix}
1 & 2 & 3 & 4 & 5 & 6 & 7\\
6 & 3 & 5 & 1 & 4 & 2 & 7
\end{pmatrix}
=
(1\, 6\, 2\, 3\, 5\, 4 )
\end{equation*}
est un cycle de longueur \(6\text{,}\) tandis que
\begin{equation*}
\tau =
\begin{pmatrix}
1 & 2 & 3 & 4 & 5 & 6 \\
1 & 4 & 2 & 3 & 5 & 6
\end{pmatrix}
=
(2\, 4\, 3)
\end{equation*}
est un cycle de longueur \(3\text{.}\)
Toute permutation n’est pas un cycle. Considérons la permutation
\begin{equation*}
\begin{pmatrix}
1 & 2 & 3 & 4 & 5 & 6 \\
2 & 4 & 1 & 3 & 6 & 5
\end{pmatrix}
= (1\, 2\, 4\, 3)(5\, 6)\text{.}
\end{equation*}
Cette permutation contient en réalité un cycle de longueur 2 et un cycle de longueur \(4\text{.}\)
Exemple 5.1.6.
Il est très facile de calculer des produits de cycles. Supposons que
\begin{equation*}
\sigma = (1\, 3\, 5\, 2 ) \quad \text{et} \quad \tau = (2\, 5\, 6)\text{.}
\end{equation*}
Si l’on pense à \(\sigma\) comme
\begin{equation*}
1 \mapsto 3, \qquad
3 \mapsto 5, \qquad
5 \mapsto 2, \qquad
2 \mapsto 1\text{,}
\end{equation*}
et à \(\tau\) comme
\begin{equation*}
2 \mapsto 5, \qquad
5 \mapsto 6, \qquad
6 \mapsto 2\text{,}
\end{equation*}
alors pour \(\sigma \tau\text{,}\) en se rappelant qu’on applique d’abord \(\tau\) puis \(\sigma\text{,}\) on doit avoir
\begin{equation*}
1 \mapsto 3, \qquad
3 \mapsto 5, \qquad
5 \mapsto 6, \qquad
6 \mapsto 2 \mapsto 1\text{,}
\end{equation*}
soit \(\sigma \tau = (1 \, 3 \, 5 \, 6 )\text{.}\) Si \(\mu = (1 \, 6 \, 3 \, 4)\text{,}\) alors \(\sigma \mu = (1\, 6\, 5\, 2)(3\, 4)\text{.}\)
Deux cycles dans \(S_X\text{,}\) \(\sigma = (a_1, a_2, \ldots,
a_k )\) et \(\tau = (b_1, b_2, \ldots,
b_l )\text{,}\) sont disjoints si \(a_i \neq b_j\) pour tout \(i\) et \(j\text{.}\)
Exemple 5.1.7.
Les cycles \((1\, 3\, 5)\) et \((2\, 7 )\) sont disjoints ; en revanche, les cycles \((1\, 3\, 5)\) et \((3\, 4\, 7 )\) ne le sont pas. En calculant leurs produits, on trouve que
\begin{align*}
(1\, 3\, 5)(2\, 7 ) & = (1\, 3\, 5)(2\, 7 )\\
(1\, 3\, 5)(3\, 4\, 7 ) & = (1\, 3\, 4\, 7\, 5)\text{.}
\end{align*}
Le produit de deux cycles non disjoints peut se réduire à quelque chose de plus simple ; le produit de cycles disjoints ne peut pas être simplifié.
Proposition 5.1.8.
Soient \(\sigma\) et \(\tau\) deux cycles disjoints dans \(S_X\text{.}\) Alors \(\sigma \tau = \tau \sigma\text{.}\)
Démonstration.
Soient \(\sigma = (a_1, a_2, \ldots,
a_k )\) et \(\tau = (b_1, b_2, \ldots, b_l )\text{.}\) Nous devons montrer que \(\sigma \tau(x) = \tau \sigma(x)\) pour tout \(x \in X\text{.}\) Si \(x\) n’appartient ni à \(\{ a_1, a_2, \ldots,
a_k \}\) ni à \(\{b_1, b_2, \ldots, b_l \}\text{,}\) alors \(\sigma\) et \(\tau\) fixent tous deux \(x\text{.}\) C’est-à-dire que \(\sigma(x)=x\) et \(\tau(x)=x\text{.}\) Donc,
\begin{equation*}
\sigma \tau(x) = \sigma( \tau(x)) = \sigma(x) = x = \tau(x) = \tau( \sigma(x)) = \tau \sigma(x)\text{.}
\end{equation*}
N’oublions pas que nous multiplions les permutations de droite à gauche, ce qui est l’ordre inverse de celui dans lequel nous multiplions habituellement les éléments d’un groupe. Supposons maintenant que \(x \in \{ a_1, a_2, \ldots, a_k \}\text{.}\) Alors \(\sigma( a_i ) = a_{(i \bmod k) + 1}\) ; c’est-à-dire,
\begin{align*}
a_1 & \mapsto a_2\\
a_2 & \mapsto a_3\\
& \vdots\\
a_{k-1} & \mapsto a_k\\
a_k & \mapsto a_1\text{.}
\end{align*}
Cependant, \(\tau(a_i) = a_i\) puisque \(\sigma\) et \(\tau\) sont disjoints. Par conséquent,
\begin{align*}
\sigma \tau(a_i) & = \sigma( \tau(a_i))\\
& = \sigma(a_i)\\
& = a_{(i \bmod k)+1}\\
& = \tau( a_{(i \bmod k)+1} )\\
& = \tau( \sigma(a_i) )\\
& = \tau \sigma(a_i)\text{.}
\end{align*}
De même, si \(x \in \{b_1, b_2, \ldots,
b_l \}\text{,}\) alors \(\sigma\) et \(\tau\) commutent également.
Théorème 5.1.9.
Toute permutation de \(S_n\) peut s’écrire comme le produit de cycles disjoints.
Démonstration.
On peut supposer que \(X = \{ 1, 2, \ldots, n \}\text{.}\) Si \(\sigma \in S_n\) et que l’on définit \(X_1\) comme étant \(\{ \sigma(1), \sigma^2(1), \ldots \}\text{,}\) alors l’ensemble \(X_1\) est fini puisque \(X\) est fini. Soit maintenant \(i\) le premier entier de \(X\) n’appartenant pas à \(X_1\) et définissons \(X_2\) par \(\{ \sigma(i), \sigma^2(i), \ldots \}\text{.}\) Là encore, \(X_2\) est un ensemble fini. En poursuivant ainsi, on peut définir des ensembles finis disjoints \(X_3, X_4, \ldots\text{.}\) Comme \(X\) est un ensemble fini, nous sommes assurés que ce processus se terminera et qu’il n’y aura qu’un nombre fini de ces ensembles, disons \(r\text{.}\) Si \(\sigma_i\) est le cycle défini par
\begin{equation*}
\sigma_i( x ) =
\begin{cases}
\sigma( x ) & x \in X_i \\
x & x \notin X_i
\text{,}\end{cases}
\end{equation*}
alors \(\sigma = \sigma_1 \sigma_2 \cdots \sigma_r\text{.}\) Puisque les ensembles \(X_1, X_2, \ldots, X_r\) sont disjoints, les cycles \(\sigma_1, \sigma_2, \ldots, \sigma_r\) sont également disjoints.
Exemple 5.1.10.
Posons
\begin{align*}
\sigma & =
\begin{pmatrix}
1 & 2 & 3 & 4 & 5 & 6 \\
6 & 4 & 3 & 1 & 5 & 2
\end{pmatrix}\\
\tau & =
\begin{pmatrix}
1 & 2 & 3 & 4 & 5 & 6 \\
3 & 2 & 1 & 5 & 6 & 4
\end{pmatrix}\text{.}
\end{align*}
En utilisant la notation cyclique, on peut écrire
\begin{align*}
\sigma & = (1 \, 6 \, 2 \, 4)\\
\tau & = (1 \, 3)(4 \, 5 \,6)\\
\sigma \tau & = (1 \, 3\, 6) ( 2\, 4\, 5)\\
\tau \sigma & = (1 \, 4\, 3 )(2 \, 5 \, 6)\text{.}
\end{align*}
Remarque 5.1.11.
À partir de ce point, il nous sera commode d’utiliser la notation cyclique pour représenter les permutations. Lorsqu’on utilise la notation cyclique, on désigne souvent la permutation identité par \((1)\text{.}\)
Sous-section 5.1.2 Transpositions
La permutation la plus simple est un cycle de longueur \(2\text{.}\) De tels cycles sont appelés transpositions. Puisque
\begin{equation*}
(a_1, a_2, \ldots, a_n ) = (a_1, a_n ) (a_1, a_{n-1} ) \cdots ( a_1, a_3 ) (a_1, a_2 )\text{,}
\end{equation*}
tout cycle peut s’écrire comme le produit de transpositions, ce qui conduit à la proposition suivante.
Proposition 5.1.12.
Toute permutation d’un ensemble fini contenant au moins deux éléments peut s’écrire comme le produit de transpositions.
Exemple 5.1.13.
Considérons la permutation
\begin{equation*}
( 1 \, 6 ) (2 \, 5\, 3) = (1 \, 6 )( 2 \, 3 )( 2 \, 5 ) = (1 \, 6 )( 4 \, 5 )(2 \, 3 )( 4 \, 5 )(2 \, 5 )\text{.}
\end{equation*}
Comme on peut le voir, il n’existe pas de façon unique de représenter une permutation comme le produit de transpositions. Par exemple, on peut écrire la permutation identité comme \((1 \, 2 )(1 \, 2 )\text{,}\) comme \((1 \, 3 )(2 \, 4 )(1 \, 3 )( 2 \, 4 )\text{,}\) et de bien d’autres façons. Cependant, il s’avère qu’aucune permutation ne peut s’écrire à la fois comme le produit d’un nombre pair de transpositions et d’un nombre impair de transpositions. Par exemple, on pourrait représenter la permutation \((1 \, 6)\) par
\begin{equation*}
(2 \, 3 )(1 \, 6)( 2 \, 3)
\end{equation*}
ou par
\begin{equation*}
(3 \, 5) (1 \, 6) (1 \, 3) (1 \, 6) (1 \, 3) (3 \, 5) (5 \, 6)\text{,}
\end{equation*}
mais \((1 \, 6)\) sera toujours le produit d’un nombre impair de transpositions.
Lemme 5.1.14.
Si l’identité s’écrit comme le produit de \(r\) transpositions,
\begin{equation*}
\identity = \tau_1 \tau_2 \cdots \tau_r\text{,}
\end{equation*}
alors \(r\) est un nombre pair.
Démonstration.
Nous allons procéder par récurrence sur \(r\text{.}\) Une transposition ne peut pas être l’identité ; donc \(r \gt 1\text{.}\) Si \(r=2\text{,}\) c’est terminé. Supposons que \(r \gt 2\text{.}\) Dans ce cas, le produit des deux dernières transpositions, \(\tau_{r-1} \tau_r\text{,}\) doit être l’un des cas suivants :
\begin{align*}
(a, b)(a, b) & = \identity\\
(b, c)(a, b) & = (a, c)(b, c)\\
(c, d)(a, b) & = (a, b)(c, d)\\
(a, c)(a, b) & = (a, b)(b, c)\text{,}
\end{align*}
où \(a\text{,}\) \(b\text{,}\) \(c\) et \(d\) sont distincts.
La première équation dit simplement qu’une transposition est son propre inverse. Si ce cas se présente, supprimer \(\tau_{r-1} \tau_r\) du produit pour obtenir
\begin{equation*}
\identity = \tau_1 \tau_2 \cdots \tau_{r - 3} \tau_{r - 2}\text{.}
\end{equation*}
Par hypothèse de récurrence, \(r - 2\) est pair ; donc \(r\) est pair.
Dans chacun des trois autres cas, on peut remplacer \(\tau_{r - 1} \tau_r\) par le membre droit de l’équation correspondante pour obtenir un nouveau produit de \(r\) transpositions pour l’identité. Dans ce nouveau produit, la dernière occurrence de \(a\) sera dans l’avant-dernière transposition. On peut poursuivre ce processus avec \(\tau_{r - 2} \tau_{r - 1}\) pour obtenir soit un produit de \(r - 2\) transpositions, soit un nouveau produit de \(r\) transpositions où la dernière occurrence de \(a\) est dans \(\tau_{r - 2}\text{.}\) Si l’identité est le produit de \(r - 2\) transpositions, alors, de nouveau, c’est terminé par hypothèse de récurrence ; sinon, on répète la procédure avec \(\tau_{r - 3} \tau_{r - 2}\text{.}\)
À un certain moment, soit deux transpositions adjacentes et identiques s’annuleront, soit \(a\) sera décalé de sorte qu’il n’apparaîtra plus que dans la première transposition. Cependant, ce dernier cas ne peut pas se produire, car l’identité ne fixerait pas \(a\) dans cette situation. Par conséquent, la permutation identité doit être le produit de \(r-2\) transpositions et, de nouveau par hypothèse de récurrence, c’est terminé.
Théorème 5.1.15.
Si une permutation \(\sigma\) peut s’exprimer comme le produit d’un nombre pair de transpositions, alors tout autre produit de transpositions égal à \(\sigma\) doit également contenir un nombre pair de transpositions. De même, si \(\sigma\) peut s’exprimer comme le produit d’un nombre impair de transpositions, alors tout autre produit de transpositions égal à \(\sigma\) doit également contenir un nombre impair de transpositions.
Démonstration.
Supposons que
\begin{equation*}
\sigma = \sigma_1 \sigma_2 \cdots \sigma_m = \tau_1 \tau_2 \cdots \tau_n\text{,}
\end{equation*}
où \(m\) est pair. Nous devons montrer que \(n\) est également un nombre pair. L’inverse de \(\sigma\) est \(\sigma_m \cdots \sigma_1\text{.}\) Puisque
\begin{equation*}
\identity = \sigma \sigma_m \cdots \sigma_1 = \tau_1 \cdots \tau_n \sigma_m \cdots \sigma_1\text{,}
\end{equation*}
\(n\) doit être pair d’après le Lemme 5.1.14. La démonstration du cas où \(\sigma\) peut s’exprimer comme un nombre impair de transpositions est laissée en exercice.
À la lumière du Théorème 5.1.15, on définit une permutation comme étant paire si elle peut s’exprimer comme un nombre pair de transpositions, et impaire si elle peut s’exprimer comme un nombre impair de transpositions.
Sous-section 5.1.3 Les groupes alternés
L’un des sous-groupes les plus importants de \(S_n\) est l’ensemble de toutes les permutations paires, \(A_n\text{.}\) Le groupe \(A_n\) est appelé le groupe alterné sur \(n\) lettres.
Théorème 5.1.16.
Démonstration.
Puisque le produit de deux permutations paires est également une permutation paire, \(A_n\) est stable. L’identité est une permutation paire et appartient donc à \(A_n\text{.}\) Si \(\sigma\) est une permutation paire, alors
\begin{equation*}
\sigma = \sigma_1 \sigma_2 \cdots \sigma_r\text{,}
\end{equation*}
où \(\sigma_i\) est une transposition et \(r\) est pair. Puisque l’inverse de toute transposition est elle-même,
\begin{equation*}
\sigma^{-1} = \sigma_r \sigma_{r-1} \cdots \sigma_1
\end{equation*}
appartient également à \(A_n\text{.}\)
Proposition 5.1.17.
Le nombre de permutations paires dans \(S_n\text{,}\) \(n \geq 2\text{,}\) est égal au nombre de permutations impaires ; ainsi, l’ordre de \(A_n\) est \(n!/2\text{.}\)
Démonstration.
Soit \(A_n\) l’ensemble des permutations paires de \(S_n\) et \(B_n\) l’ensemble des permutations impaires. Si l’on peut montrer qu’il existe une bijection entre ces ensembles, ils doivent contenir le même nombre d’éléments. Fixons une transposition \(\sigma\) dans \(S_n\text{.}\) Puisque \(n \geq 2\text{,}\) une telle \(\sigma\) existe. Définissons
\begin{equation*}
\lambda_{\sigma} : A_n \rightarrow B_n
\end{equation*}
par
\begin{equation*}
\lambda_{\sigma} ( \tau ) = \sigma \tau \text{.}
\end{equation*}
Supposons que \(\lambda_{\sigma} ( \tau ) = \lambda_{\sigma} ( \mu )\text{.}\) Alors \(\sigma \tau = \sigma \mu\text{,}\) et donc
\begin{equation*}
\tau = \sigma^{-1} \sigma \tau = \sigma^{-1} \sigma \mu = \mu\text{.}
\end{equation*}
Par conséquent, \(\lambda_{\sigma}\) est injective. Nous laisserons la démonstration que \(\lambda_{\sigma}\) est surjective au lecteur.
Exemple 5.1.18.
Le groupe \(A_4\) est le sous-groupe de \(S_4\) constitué des permutations paires. Il y a douze éléments dans \(A_4\) :
\begin{align*}
& (1) && (1 \, 2)(3 \, 4) && (1 \, 3)(2 \, 4) && (1 \, 4)(2 \, 3)\\
& (1 \, 2 \, 3) && (1 \, 3 \, 2) && (1 \, 2 \, 4) && (1 \, 4 \, 2)\\
& (1 \, 3 \, 4) && (1 \, 4 \, 3) && (2 \, 3 \, 4) && (2 \, 4 \, 3)\text{.}
\end{align*}
L’un des exercices de fin de chapitre consistera à écrire tous les sous-groupes de \(A_4\text{.}\) Vous constaterez qu’il n’existe aucun sous-groupe d’ordre 6. Cela vous surprend-il ?
Sous-section 5.1.4 Note historique
Lagrange fut le premier à concevoir les permutations comme des fonctions d’un ensemble dans lui-même, mais c’est Cauchy qui développa les théorèmes fondamentaux et la notation pour les permutations. Il fut le premier à utiliser la notation cyclique. Augustin-Louis Cauchy (1789–1857) est né à Paris au cœur de la Révolution française. Sa famille quitta bientôt Paris pour le village d’Arcueil afin d’échapper à la Terreur. L’un des voisins de la famille à Arcueil était Pierre-Simon Laplace (1749–1827), qui l’encouragea à poursuivre une carrière en mathématiques. Cauchy commença sa carrière de mathématicien en résolvant un problème de géométrie que lui avait soumis Lagrange. Cauchy rédigea plus de 800 articles sur des sujets aussi divers que les équations différentielles, les groupes finis, les mathématiques appliquées et l’analyse complexe. Il fut l’un des mathématiciens responsables de la rigueur introduite dans le calcul infinitésimal. Peut-être plus de théorèmes et de concepts mathématiques portent-ils le nom de Cauchy que celui de tout autre mathématicien.
