Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Signature d'une permutation
Résumé
En mathématiques, une permutation de support fini est dite paire si elle présente un nombre pair d'inversions, impaire sinon. 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.
Toute permutation se décompose en un produit de transpositions. Une transposition étant impaire, il vient de cette règle des signes que la parité du nombre de transpositions d'une telle décomposition coïncide avec la parité de la permutation (et ne dépend donc pas de la décomposition choisie).
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.
Nous définissons dans cet article la parité d'une permutation par le comptage de ses .
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.
Autrement dit, la signature d'une permutation σ, notée dans la suite de cet article ε(σ), vérifie si l'on note sgn la fonction signe :
Exemples
Considérons la permutationqui fixe 1 et 4 et envoie 2 sur 3, 3 sur 5 et 5 sur 2.Compter le nombre d'inversions revient à compter le nombre de désordres dans la seconde ligne. On en dénombre quatre : 3 est avant 2, 5 avant 4, 5 avant 2, et 4 avant 2. Cela signifie que les paires formées de leurs antécédents sont, selon la définition, des inversions, soit les paires {2,5}, {3,4}, {3,5}, {4,5}.Puisqu'il y en a quatre, σ est paire et ε(σ) = 1.
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.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.