AlgèbreNotion · Glossaire
Permutation paire
Une permutation est dite paire si elle peut s'écrire comme un produit d'un nombre pair de transpositions. La signature d'une permutation est +1 si elle est paire et -1 si elle est impaire. Les permutations paires d'un ensemble à n éléments forment un groupe, le groupe alterné An, qui est un sous-groupe d'indice 2 du groupe symétrique Sn. Pour n supérieur ou égal à 5, le groupe alterné An est simple, ce qui est un résultat fondamental en théorie des groupes.
Sommaire
Ce que vous allez apprendre
- Reconnaître une permutation paire à partir d'une décomposition en transpositions.
- Contrôler la parité en comptant les inversions.
- Relier la signature +1 à l'appartenance au groupe alterné A_n.
- Distinguer parité de la permutation, longueur d'un cycle et nombre d'éléments déplacés.
En clair
Imaginez quatre cartes numérotées que l'on réorganise. Échanger seulement deux cartes est une transposition. Une permutation est paire lorsque la réorganisation peut être obtenue par deux échanges, quatre échanges, ou tout autre nombre pair d'échanges de deux cartes.
Le nombre précis d'échanges peut varier selon la manière de procéder, mais sa parité ne change jamais. La signature résume ce résultat : elle vaut +1 pour une permutation paire et −1 pour une permutation impaire.
Définition
Une permutation d'un ensemble fini est une bijection de cet ensemble sur lui-même. Une transposition est une permutation qui échange exactement deux éléments et laisse les autres fixes. Une permutation est paire si elle est le produit d'un nombre pair de transpositions. Elle est impaire si ce nombre est impair. Bien qu'une même permutation admette plusieurs décompositions en transpositions, toutes ces décompositions ont la même parité.
La signature, notée sgn, encode cette parité. Pour une permutation notée σ, le critère s'écrit lorsqu'elle est paire, et lorsqu'elle est impaire. La signature d'un produit est le produit des signatures : composer deux permutations de même parité donne une permutation paire, tandis que des parités différentes donnent une permutation impaire.
Sur un ensemble de n éléments, le groupe symétrique Sn réunit toutes les permutations. Les permutations paires forment le groupe alterné An. Il est d'indice 2 dans Sn, donc il contient la moitié des permutations lorsque n est au moins 2. Pour n ≥ 5, An est simple : ses seuls sous-groupes normaux sont le sous-groupe réduit à l'identité et An lui-même.
Un exemple, pas à pas
Considérons l'ensemble {1, 2, 3, 4}. La permutation σ envoie 1 sur 3, 3 sur 4 et 4 sur 1, tandis que 2 reste fixe. Elle s'écrit comme le cycle (1 3 4). Le schéma rend visibles ces trois déplacements et l'élément fixe.
Données.
Ensemble : {1, 2, 3, 4}.
Cycle : (1 3 4).
Convention : dans un produit, la transposition située à droite agit la première.
Ensemble : {1, 2, 3, 4}.
Cycle : (1 3 4).
Convention : dans un produit, la transposition située à droite agit la première.
Étape 1. Échangeons d'abord 1 et 3, puis 1 et 4. La décomposition obtenue est :
Étape 2. La décomposition comporte exactement deux transpositions. Ce nombre est pair, donc σ est une permutation paire et sa signature vaut +1.
Contrôle. L'écriture en ligne est [3, 2, 4, 1]. Elle possède quatre inversions : (3, 2), (3, 1), (2, 1) et (4, 1). Quatre étant pair, ce second critère confirme le résultat.
En pratique
Pour tester une permutation donnée par une suite de valeurs, on peut compter ses inversions. Un total pair donne une permutation paire. Ce critère est souvent plus direct qu'une recherche manuelle de transpositions lorsque l'écriture en ligne est déjà disponible.
Pour une permutation écrite en cycles disjoints, on décompose chaque cycle. Un cycle de longueur k utilise k − 1 transpositions : un cycle de longueur impaire est donc pair, et un cycle de longueur paire est impair.
Lors d'une composition, les signatures évitent de redécomposer tout le produit. Il suffit de multiplier les valeurs +1 et −1 des facteurs pour connaître la parité du résultat.
À ne pas confondre
Permutation paire et cycle de longueur paire. La parité porte sur le nombre de transpositions, pas sur la longueur du cycle. Le cycle (1 3 4), de longueur 3, est pair car il se décompose en deux transpositions. Un cycle de longueur 4 se décompose en trois transpositions et est impair.
Permutation paire et nombre pair d'éléments déplacés. Déplacer un nombre pair d'éléments ne suffit pas. Une transposition déplace exactement deux éléments, mais elle est impaire puisqu'elle contient une seule transposition.
Parité d'une permutation et parité d'un entier. Le mot « paire » qualifie ici une bijection selon ses décompositions. Il ne signifie pas que les images des éléments sont des nombres pairs.
Limites et pièges
Une décomposition n'est pas unique. Ajouter deux fois la même transposition ne change pas la permutation, mais allonge la décomposition de deux facteurs. Il faut donc examiner la parité du nombre de facteurs, jamais chercher un nombre d'échanges prétendument unique.
L'ordre de composition doit être annoncé. Selon les ouvrages, les facteurs agissent de droite à gauche ou de gauche à droite. Cette convention peut changer la permutation décrite par une écriture donnée. Il faut appliquer une convention constante et vérifier les images des éléments.
L'identité est paire. Elle est le produit de zéro transposition, et zéro est pair. Elle appartient donc à tout groupe alterné An, même lorsqu'aucun élément n'est déplacé.
Le seuil n ≥ 5 est une hypothèse du théorème de simplicité cité. Il ne faut pas appliquer automatiquement cette conclusion aux petits degrés. Ceux-ci s'étudient séparément à partir de la structure de chaque An.
Pour aller plus loin
La signature peut être vue comme une application du groupe symétrique Sn vers le groupe multiplicatif {−1, +1}. Elle respecte la composition, et son noyau est précisément le groupe alterné An. Cette lecture explique simultanément pourquoi les permutations paires sont stables par composition, pourquoi les inverses restent pairs et pourquoi An a l'indice 2 dans Sn.
La simplicité de An pour n ≥ 5 prolonge cette étude : elle affirme qu'à ces degrés, le groupe alterné ne possède aucun sous-groupe normal intermédiaire entre l'identité et le groupe entier.
Explorez les mathématiques autrement
Retrouvez nos magazines, podcasts et jeux pour explorer les mathématiques autrement.
Découvrir les offres