signature d'une permutation

Imaginez quatre cartes numérotées que l’on remet dans un nouvel ordre. On peut obtenir ce rangement par une suite d’échanges, chaque échange ne portant que sur deux cartes. Le nombre exact d’échanges dépend de la suite choisie, mais son caractère pair ou impair ne change jamais.

La signature résume cette parité par un signe : 1 pour un nombre pair d’échanges et −1 pour un nombre impair. Elle conserve ainsi une information stable, même lorsque plusieurs suites d’échanges réalisent le même rangement.

Une permutation réordonne les éléments d’un ensemble fini. Une transposition est une permutation qui échange exactement deux éléments et laisse les autres en place. Toute permutation se décompose en un produit de transpositions. Cette écriture n’est pas unique, mais toutes ses décompositions contiennent des nombres de transpositions de même parité.

Pour une permutation notée σ et une décomposition comportant m transpositions, sa signature, notée sgn(σ), est définie par $sgn(\sigma )=(-1{)}^{m}sgn(\backslash sigma)=(-1)^m$. Ainsi, sgn(σ) vaut 1 lorsque m est pair : σ est alors paire. Elle vaut −1 lorsque m est impair : σ est alors impaire. La valeur ne dépend donc pas de la décomposition retenue.

Le groupe de toutes les permutations de n éléments est noté S_n. La signature respecte la composition : pour deux permutations σ et τ, $sgn(\sigma \tau )=sgn(\sigma )sgn(\tau )sgn(\backslash sigma\backslash tau)=sgn(\backslash sigma)sgn(\backslash tau)$. Elle définit ainsi un homomorphisme de S_n vers le groupe multiplicatif {−1, 1}. Son noyau, formé exactement des permutations de signature 1, est le groupe alterné A_n.

Considérons la permutation σ des nombres 1, 2, 3 et 4 qui les place dans l’ordre [3, 1, 4, 2]. Autrement dit, 1 a pour image 3, 2 a pour image 1, 3 a pour image 4 et 4 a pour image 2.

1. Repérer les inversions : une inversion est une paire placée dans l’ordre contraire à l’ordre croissant. Ici, ce sont (3, 1), (3, 2) et (4, 2).

2. Compter ces inversions donne 3, un nombre impair. Le schéma matérialise les quatre images et les trois croisements correspondants.

3. Retrouver le même verdict par transpositions : en composant de droite à gauche, le cycle (1 3 4 2) s’écrit $(1342)=(12)(14)(13)(1\backslash \; 3\backslash \; 4\backslash \; 2)=(1\backslash \; 2)(1\backslash \; 4)(1\backslash \; 3)$. Il comporte trois transpositions.

4. Les deux contrôles donnent une parité impaire. La signature de σ est donc −1.

Pour une permutation écrite comme une liste d’images, on peut compter les inversions au lieu de chercher une décomposition en transpositions. Seule la parité du total importe : un total pair donne la signature 1, un total impair la signature −1.

Pour une permutation déjà écrite comme produit de transpositions, on compte directement les facteurs. Une autre décomposition peut être plus longue ou plus courte, mais elle conduit au même caractère pair ou impair.

Lorsqu’on compose plusieurs permutations, la propriété multiplicative évite de tout redécomposer. On multiplie leurs signatures : le produit est impair lorsque le nombre de facteurs de signature −1 est impair, et pair lorsque ce nombre est pair.

Signature et nombre d’éléments déplacés. La parité porte sur le nombre de transpositions d’une décomposition, pas sur le nombre de points qui changent de place. Une transposition déplace deux éléments, nombre pair, mais sa signature vaut −1.

Signature et signe des nombres permutés. La signature dépend uniquement du réordonnement. Remplacer les objets par des nombres positifs ou négatifs sans changer la permutation ne modifie pas sa signature.

La longueur d’une décomposition n’est pas un invariant. Deux transpositions identiques successives s’annulent. On peut donc ajouter deux facteurs à une décomposition sans changer la permutation ; il faut retenir la parité, jamais la longueur précise.

L’identité utilise le produit vide. Elle se décompose avec zéro transposition. Comme zéro est pair, sa signature vaut 1, y compris lorsque l’ensemble possède zéro ou un élément.

L’ordre de composition doit être annoncé. Dans l’exemple, les facteurs agissent de droite à gauche. Une convention opposée change la lecture du produit écrit ; elle ne change pas la signature de la permutation effectivement obtenue.

Un dessin de fils exige un ordre fixé aux deux extrémités. Avec cet ordre, la parité des croisements traduit celle des inversions. Déplacer arbitrairement les points rend le nombre de croisements illisible comme critère.

La fiche Permutation paire approfondit la classe des permutations de signature 1 et son lien avec la composition.