Introduction à la Structure des Permutations
En algèbre abstraite, et plus particulièrement en théorie des groupes, le groupe symétrique $\mathcal{S}_n$ est l’un des objets les plus fondamentaux. Il s’agit de l’ensemble de toutes les bijections (ou permutations) d’un ensemble fini à $n$ éléments sur lui-même. Une permutation peut sembler complexe à première vue, surtout lorsqu’elle est écrite sous sa forme matricielle. Cependant, il existe une manière incroyablement puissante et intuitive de la visualiser et de la manipuler : la décomposition en produit de cycles à supports disjoints.
Cette décomposition est la « pierre de Rosette » des permutations. Elle révèle de manière limpide la structure interne d’une permutation, son « ADN ». Grâce à elle, des propriétés essentielles comme l’ordre d’un élément, sa signature (et donc son appartenance au groupe alterné $\mathcal{A}_n$), ou encore sa classe de conjugaison deviennent triviales à calculer. L’objectif de cette page est de démystifier ce concept, de fournir un algorithme clair pour trouver cette décomposition et d’illustrer son immense utilité à travers des exemples détaillés.
Rappels sur les Permutations
Avant de plonger dans le vif du sujet, rappelons quelques notations. Une permutation $\sigma$ du groupe $\mathcal{S}_n$ est une bijection de l’ensemble $\{1, 2, \dots, n\}$ dans lui-même.
La notation la plus courante est la notation matricielle (ou à deux lignes). Sur la première ligne, on écrit les éléments de $1$ à $n$. Sur la seconde ligne, sous chaque élément $k$, on écrit son image $\sigma(k)$. Par exemple, dans $\mathcal{S}_5$, la permutation $\sigma$ telle que $\sigma(1)=3$, $\sigma(2)=5$, $\sigma(3)=4$, $\sigma(4)=1$, et $\sigma(5)=2$ s’écrit : $$ \sigma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 3 & 5 & 4 & 1 & 2 \end{pmatrix} $$ Cette notation est explicite mais peut être lourde et ne met pas en évidence la structure de la permutation.
Soit $k \ge 2$ un entier. Un k-cycle (ou cycle de longueur $k$) est une permutation $\sigma \in \mathcal{S}_n$ pour laquelle il existe des éléments distincts $a_1, a_2, \dots, a_k$ de $\{1, 2, \dots, n\}$ tels que : $$ \sigma(a_1) = a_2, \quad \sigma(a_2) = a_3, \quad \dots, \quad \sigma(a_{k-1}) = a_k, \quad \sigma(a_k) = a_1 $$ et pour tout autre élément $x \notin \{a_1, \dots, a_k\}$, on a $\sigma(x) = x$.
Un tel cycle se note de manière compacte : $(a_1 \ a_2 \ \dots \ a_k)$. L’ensemble $\{a_1, \dots, a_k\}$ est appelé le support du cycle. Les éléments qui ne sont pas dans le support sont des points fixes.
Exemple de cycle
Considérons le cycle $\gamma = (1 \ 3 \ 4)$ dans $\mathcal{S}_5$. Cela signifie que $\gamma(1)=3$, $\gamma(3)=4$, et $\gamma(4)=1$. Le cycle « ferme la boucle ». Les éléments $2$ et $5$ ne sont pas dans le support de $\gamma$, donc ils sont des points fixes : $\gamma(2)=2$ et $\gamma(5)=5$. En notation matricielle, ce cycle s’écrit : $$ \gamma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 3 & 2 & 4 & 1 & 5 \end{pmatrix} $$
Deux cycles $\sigma_1$ et $\sigma_2$ sont dits à supports disjoints si l’intersection de leurs supports est vide. Autrement dit, aucun élément n’est déplacé par les deux cycles à la fois.
Une propriété fondamentale des cycles à supports disjoints est qu’ils commutent : si $c_1$ et $c_2$ sont à supports disjoints, alors $c_1 \circ c_2 = c_2 \circ c_1$. C’est logique : comme ils agissent sur des ensembles d’éléments différents, l’ordre dans lequel on les applique n’a pas d’importance.
Toute permutation $\sigma \in \mathcal{S}_n$ (pour $n \ge 2$) qui n’est pas l’identité se décompose de manière unique (à l’ordre près des facteurs) en un produit (composition) de cycles à supports disjoints de longueur supérieure ou égale à 2.
Cette unicité est la clé. Elle garantit que la décomposition est une caractéristique intrinsèque de la permutation, pas juste un artifice de calcul.
L’Algorithme de Décomposition : Comment faire en pratique ?
La démonstration du théorème est constructive, ce qui signifie qu’elle nous fournit directement un algorithme pour trouver la décomposition. L’idée est de suivre les « orbites » des éléments sous l’action de la permutation.
- Choisissez le plus petit nombre $x$ dans $\{1, 2, \dots, n\}$ qui n’a pas encore été inclus dans un cycle.
- Construisez un cycle en commençant par $x$. Calculez son image $\sigma(x)$, puis l’image de l’image $\sigma(\sigma(x))$, et ainsi de suite. Vous générez la séquence : $x, \sigma(x), \sigma^2(x), \dots$.
- Comme l’ensemble $\{1, \dots, n\}$ est fini, cette séquence doit forcément se répéter. Le premier élément à se répéter sera $x$ lui-même. Au moment où vous retombez sur $x$, vous avez complété un cycle. Notons-le $(x \ \sigma(x) \ \sigma^2(x) \ \dots \ \sigma^{k-1}(x))$.
- Marquez tous les éléments de ce nouveau cycle comme « visités ».
- S’il reste des éléments non visités dans $\{1, \dots, n\}$, retournez à l’étape 1. Sinon, l’algorithme est terminé.
- La permutation $\sigma$ est le produit des cycles que vous avez trouvés.
Exemple 1 : Décomposition d’une permutation dans $\mathcal{S}_8$
Soit la permutation $\sigma \in \mathcal{S}_8$ définie par : $$ \sigma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 3 & 6 & 5 & 8 & 1 & 2 & 7 & 4 \end{pmatrix} $$
- Étape 1 : On commence avec le plus petit élément non visité, 1.
- Étape 2 : On suit son orbite :
- $\sigma(1) = 3$
- $\sigma(3) = 5$
- $\sigma(5) = 1$. On est revenu au début !
- Étape 3 : Les éléments {1, 3, 5} sont maintenant visités.
- Étape 4 : Le plus petit élément non visité est 2.
- Étape 5 : On suit son orbite :
- $\sigma(2) = 6$
- $\sigma(6) = 2$. On est revenu au début !
- Étape 6 : Les éléments {1, 3, 5, 2, 6} sont visités.
- Étape 7 : Le plus petit élément non visité est 4.
- Étape 8 : On suit son orbite :
- $\sigma(4) = 8$
- $\sigma(8) = 4$. On est revenu au début !
- Étape 9 : Les éléments {1, 3, 5, 2, 6, 4, 8} sont visités.
- Étape 10 : Le seul élément non visité est 7. On calcule $\sigma(7) = 7$. C’est un point fixe. Les points fixes correspondent à des cycles de longueur 1, (7), que l’on omet généralement dans la notation finale.
Tous les éléments ont été visités. La décomposition de $\sigma$ est le produit des cycles trouvés : $$ \sigma = (1 \ 3 \ 5) \circ (2 \ 6) \circ (4 \ 8) $$ L’ordre des cycles n’a pas d’importance car leurs supports $\{1,3,5\}$, $\{2,6\}$ et $\{4,8\}$ sont disjoints. On pourrait tout aussi bien écrire $\sigma = (4 \ 8) \circ (1 \ 3 \ 5) \circ (2 \ 6)$.
Applications de la Décomposition en Cycles
Cette décomposition n’est pas qu’une simple réécriture. C’est un outil de calcul extrêmement puissant qui simplifie de nombreuses questions.
1. Calcul de l’Ordre d’une Permutation
L’ordre d’un élément $\sigma$ dans un groupe est le plus petit entier $k > 0$ tel que $\sigma^k = Id$ (l’identité). Calculer les puissances successives d’une permutation sous forme matricielle est fastidieux. Avec la décomposition en cycles, cela devient un jeu d’enfant.
Soit $\sigma$ une permutation qui se décompose en un produit de cycles disjoints $c_1, c_2, \dots, c_m$ de longueurs respectives $l_1, l_2, \dots, l_m$. Alors, l’ordre de $\sigma$ est le Plus Petit Commun Multiple (PPCM) des longueurs de ses cycles : $$ \text{ordre}(\sigma) = \text{PPCM}(l_1, l_2, \dots, l_m) $$
Pourquoi ? Comme les cycles commutent, élever $\sigma$ à la puissance $k$ revient à élever chaque cycle à la puissance $k$ : $\sigma^k = c_1^k \circ c_2^k \circ \dots \circ c_m^k$. Pour que $\sigma^k$ soit l’identité, il faut que chaque $c_i^k$ soit l’identité. L’ordre d’un cycle de longueur $l_i$ est précisément $l_i$. Donc, il faut que $k$ soit un multiple de chaque $l_i$. Le plus petit tel $k$ est, par définition, le PPCM.
Exemple de calcul d’ordre
Reprenons notre permutation $\sigma = (1 \ 3 \ 5) \circ (2 \ 6) \circ (4 \ 8)$. Les longueurs des cycles sont $l_1=3$, $l_2=2$, et $l_3=2$. L’ordre de $\sigma$ est donc : $$ \text{ordre}(\sigma) = \text{PPCM}(3, 2, 2) = 6 $$ Cela signifie que $\sigma^6 = Id$ et qu’aucune puissance inférieure (positive) ne donne l’identité.
2. Calcul de la Signature d’une Permutation
La signature d’une permutation, notée $\varepsilon(\sigma)$, est une valeur qui vaut $+1$ si la permutation est « paire » et $-1$ si elle est « impaire ». Elle est cruciale pour définir le groupe alterné $\mathcal{A}_n$. La décomposition en cycles est, là encore, le moyen le plus simple de la calculer.
- Un cycle de longueur $k$ (un $k$-cycle) peut être décomposé en $k-1$ transpositions (cycles de longueur 2). Sa signature est donc $(-1)^{k-1}$.
- La signature est un morphisme de groupes, c’est-à-dire $\varepsilon(\sigma_1 \circ \sigma_2) = \varepsilon(\sigma_1) \times \varepsilon(\sigma_2)$.
- Par conséquent, la signature d’une permutation $\sigma = c_1 \circ \dots \circ c_m$ (décomposée en cycles disjoints de longueurs $l_1, \dots, l_m$) est le produit des signatures de ses cycles : $$ \varepsilon(\sigma) = \prod_{i=1}^{m} \varepsilon(c_i) = \prod_{i=1}^{m} (-1)^{l_i-1} $$ Une autre façon de l’écrire est $\varepsilon(\sigma) = (-1)^{\sum(l_i – 1)} = (-1)^{n – m’}$, où $n$ est la taille de l’ensemble et $m’$ est le nombre de cycles dans la décomposition (en incluant les points fixes).
Exemple de calcul de signature
Reprenons encore une fois $\sigma = (1 \ 3 \ 5) \circ (2 \ 6) \circ (4 \ 8)$. Les longueurs sont $l_1=3$, $l_2=2$, $l_3=2$.
- Signature de (1 3 5) : $(-1)^{3-1} = (-1)^2 = +1$.
- Signature de (2 6) : $(-1)^{2-1} = (-1)^1 = -1$.
- Signature de (4 8) : $(-1)^{2-1} = (-1)^1 = -1$.
Conclusion : Un Outil Indispensable
La décomposition en cycles disjoints est bien plus qu’une simple notation. C’est une fenêtre ouverte sur la structure intime des permutations. Elle transforme des objets qui peuvent paraître désordonnés en une collection structurée de « rotations » indépendantes sur des sous-ensembles d’éléments.
Grâce à cette vision, des concepts abstraits comme l’ordre et la signature deviennent des calculs arithmétiques simples basés sur les longueurs des cycles. C’est un exemple parfait en mathématiques où une bonne représentation d’un objet simplifie radicalement son étude et révèle ses propriétés les plus profondes. Maîtriser cet algorithme et ses applications est une étape essentielle pour quiconque s’aventure dans le monde fascinant de la théorie des groupes.