Signature d'une permutation

Un article de Wikipédia, l'encyclopédie libre.
(Redirigé depuis Permutation impaire)
Aller à : navigation, rechercher
Page d'aide sur l'homonymie Pour les articles homonymes, voir Signature (homonymie).

En mathématiques, toute permutation de support fini se décompose en un produit de transpositions, de plusieurs façons, mais la parité du nombre de transpositions ne dépend pas de la décomposition choisie. La parité d'une permutation est la parité de ce nombre. La signature d'une permutation vaut 1 si celle-ci est paire, –1 si elle est impaire.

L'application signature, du groupe symétrique dans le groupe ({–1, 1}, ×), est un morphisme, c'est-à-dire qu'elle vérifie une propriété analogue à la règle des signes.

Tout morphisme de dans un groupe abélien se factorise par le morphisme signature.

La signature intervient notamment en algèbre linéaire, dans la formule de Leibniz qui est une façon de définir le déterminant d'une matrice carrée.

Définition de la signature[modifier | modifier le code]

L'une des définitions de la parité d'une permutation σ se fait par le comptage des inversions (en).

Définition
  • Soient i < j deux entiers compris entre 1 et n. On dit que la paire {i, j} est en inversion pour σ si σ(i) > σ(j).
  • Une permutation est dite paire si elle présente un nombre pair d'inversions, impaire sinon.
  • La signature d'une permutation paire est 1 ; celle d'une permutation impaire est –1.

Dans la suite de cet article, la signature d'une permutation σ sera notée ε(σ).

Exemples
  1. Considérons la permutationqui fixe 1 et 4 et envoie 2 sur 3, 3 sur 5 et 5 sur 2.
    Aucune paire contenant 1 n'est en inversion puisque pour tout j > 1, σ(j) > σ(1) ; la seule paire en inversion contenant 2 est {2, 5} (σ(2) = 3 > 2 = σ(5)) ; etc. La liste des paires en inversion est {2, 5}, {3, 4}, {3, 5}, {4, 5}.
    Il y en a quatre, donc est paire et .
  2. Considérons le k-cyclequi envoie 1 sur 2, 2 sur 3, … , k – 1 sur k, k sur 1 et qui fixe tous les autres entiers.
    Ses paires en inversion sont {i, k}, pour i < k.
    Il y en a k – 1 donc , et est paire si et seulement k est impair.

Une formule pour la signature[modifier | modifier le code]

Une permutation a pour signature :

,

désigne l'ensemble des paires d'entiers compris entre et

Signature d'un produit[modifier | modifier le code]

Les permutations vérifient une règle des signes pour le produit :

  • le produit de deux permutations paires est pair ;
  • le produit de deux permutations impaires est pair ;
  • le produit d'une permutation paire et d'une impaire est impair.

En utilisant la signature, cela se résume par la formule :

.

En termes algébriques : la signature est un morphisme du groupe symétrique dans le groupe à deux éléments ({–1, 1}, ×).

En particulier, toute permutation conjuguée de σ a même signature que σ (car ).

Une transposition est impaire[modifier | modifier le code]

La signature d'un k-cycle est . En particulier, la signature d'une transposition (un 2-cycle) est .

D'après la dernière propriété ci-dessus et le fait que deux cycles de même longueur sont conjugués, il suffit de le vérifier pour un seul cycle par longueur, ce qui a été fait dans l'exemple 2 ci-dessus.

Calcul d'une signature[modifier | modifier le code]

D'après les deux sections précédentes et la décomposition en produit de transpositions, il vient que toute permutation est soit paire, soit impaire, avec :

  • est paire (autrement dit : ) si et seulement si elle est décomposable en un nombre pair de transpositions ;
  • est impaire (autrement dit : ) si et seulement si elle est décomposable en un nombre impair de transpositions.

Cela permet de déterminer la parité (ou la signature) d'une permutation plus efficacement que par un simple comptage des inversions ; en effet, pour une permutation de , une telle décomposition demande au plus n – 1 opérations, contre n(n – 1)/2 si l'on applique directement la définition (voir supra).

Exemples

Cette dernière observation permet de calculer la signature d'une permutation décomposée en cycles. La signature d'une permutation de vaut , où m est le nombre de cycles de la décomposition (en comptant les points fixes comme cycles de longueur 1) dans et p le nombre de cycles de longueur paire dans cette même décomposition.

Morphisme[modifier | modifier le code]

étant le groupe trivial, supposons .

D'après la formule pour un produit et l'imparité des transpositions, la signature est alors un morphisme surjectif de dans ({–1, 1}, ×), et son noyau est le groupe alterné des permutations paires.

Ce sous-groupe étant le groupe dérivé de , la signature est donc une réalisation du morphisme canonique de dans son abélianisé, le groupe quotient . Cela signifie que tout morphisme f de dans un groupe abélien se factorise par ε, ou encore : si l'image de f n'est pas le groupe trivial alors c'est un groupe d'ordre 2 et f coïncide, via l'unique isomorphisme entre ce groupe et ({–1, 1}, ×), avec ε.

Exemple
Le seul caractère complexe (de degré 1) non trivial de est le morphisme signature.

Voir aussi[modifier | modifier le code]

Sur les autres projets Wikimedia :