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, les permutations peuvent se décomposer en un produit de transpositions, c'est-à-dire en une succession d'échanges d'éléments deux à deux.

  • Une permutation paire est une permutation qui peut être exprimée comme le produit d'un nombre pair de transpositions ;
  • une permutation impaire est une permutation qui peut être exprimée comme le produit d'un nombre impair de transpositions.

La signature d'une permutation vaut 1 si celle-ci est paire, –1 si elle est impaire. L'application signature constitue un morphisme de groupes. Elle intervient en algèbre multilinéaire, notamment pour le calcul des déterminants.

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

Soit une permutation σ. La définition traditionnelle de la parité de σ se fait par le comptage des inversions.

Définition
  • Soient i < j deux éléments distincts compris entre 1 et n. On dit que la paire {i, j} est en inversion pour σ quand σ(i) > σ(j).
  • Une permutation est dite paire quand 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.
Exemple
Soit la permutation\begin{pmatrix} 1&2&3&4&5\\1&3&5&4&2\end{pmatrix},qui 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) est distinct de σ(1) = 1, donc σ(j) > σ(1). La seule paire en inversion contenant 2 est {2, 5} (σ(2) = 3 > 2 = σ(5)). La liste des paires en inversion est {2, 5}, {3, 4}, {3, 5}, {4, 5}. Il y en a quatre, donc la permutation est paire.

Une transposition est impaire[modifier | modifier le code]

Toute transposition est une permutation impaire. En effet en notant i et j, i < j, les termes échangés par la transposition, celle-ci s'écrit

\begin{pmatrix} 1&\dots&i-1&i&i+1&\dots &j-1&j&j+1&\dots\; n\\
1&\dots & i-1&j&i+1&\dots &j-1&i&j+1&\dots\; n\end{pmatrix}.

Les paires en inversion sont les paires de la forme {i, k} avec k compris entre i + 1 et j et celles de la forme {k, j} avec k compris entre i + 1 et j – 1. Au total, il y a un nombre impair d'inversions, et l'imparité de la permutation en découle.

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

On note {\mathcal P} l'ensemble des paires d'éléments compris entre 1 et n (il y en a n(n – 1)/2). Une permutation σ a pour signature

\varepsilon(\sigma)=\prod\limits_{i<j} \frac{\sigma(j)-\sigma(i)}{j-i}
=\prod\limits_{\{i,j\}\in {\mathcal P}} \frac{\sigma(j)-\sigma(i)}{j-i}.

Cette formule a un certain intérêt algébrique mais ne permet pas un calcul efficace de la signature dans la pratique. En effet, par rapport au simple comptage des inversions, la multiplication et la division par un certain nombre d'entiers sont plus coûteuses.

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, 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

\varepsilon(\sigma\circ\tau)=\varepsilon(\sigma)\varepsilon(\tau).

En termes algébriques : la signature est un morphisme de groupes du groupe symétrique (\mathfrak S_n,\circ) dans le groupe à deux éléments ({–1, 1}, ×). Le sous-groupe noyau de ce morphisme forme le groupe alterné des permutations paires. Enfin, la permutation inverse de σ a la même signature que σ.

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

En corollaire des résultats précédents,

  • une permutation est paire si et seulement si elle peut être exprimée comme le produit d'un nombre pair de transpositions ;
  • une permutation est impaire si et seulement si elle peut être exprimée comme le produit d'un nombre impair de transpositions

et ces deux cas s'excluent mutuellement.

Le calcul de la signature par la décomposition en produit de transpositions est beaucoup plus efficace que l'application de la définition initiale ; en effet, pour une permutation de {\mathfrak S}_n, cette décomposition demande au plus n – 1 opérations, contre n(n – 1)/2 pour la définition.

Exemples
l'identité est une permutation paire ;
une transposition est une permutation impaire ;
une permutation circulaire est paire si le nombre d'éléments non fixes est impair ; elle est impaire si ce nombre d'éléments est pair.