Signature d'une permutation

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 ${\mathfrak {S}}_{n}$ 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 ${\mathfrak {S}}_{n}$ 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

Nous définissons dans cet article la parité d'une permutation par le comptage de ses 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.

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 :

$\varepsilon (\sigma )=\prod _{1\leq i<j\leq n}\operatorname {sgn}(\sigma (j)-\sigma (i))$

Étant donné que tout anneau possède un neutre multiplicatif et son opposé, la fonction signe, et donc la signature, peuvent être définies à valeur dans un anneau quelconque. Cela permet notamment de définir, via la formule de Leibniz, le déterminant d'une matrice carrée à coefficients dans un anneau commutatif quelconque. Si la signature est à valeur dans un anneau de caractéristique 2 (c'est-à-dire où -1=1), elle vaut constamment 1 et n'apporte aucune information sur la parité d'une permutation. On écartera ce cas dans la suite de cet article.

Exemples

1. Considérons la permutation$\sigma :={\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.
   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 quatre, σ est paire et ε(σ) = 1.
2. Considérons le k-cycle

$\sigma :={\begin{pmatrix}1&2&\dots &k-1&k&k+1&\dots &n\\2&3&\dots &k&1&k+1&\dots &n\end{pmatrix}}$qui 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 ε(σ) = (–1)^k–1, et σ est paire si et seulement si k est impair.

Signature d'un produit

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 :

$\varepsilon (\sigma _{1}\circ \sigma _{2})=\varepsilon (\sigma _{1})\varepsilon (\sigma _{2})$.

Démonstration

Soit ${\mathcal {P}}=\{\{i,\,j\}:1\leq i\leq n{\mbox{ et }}1\leq j\leq n{\mbox{ et }}i\neq {j}\}$ l'ensemble des paires d'entiers compris entre 1 et n.

En utilisant la définition de ε (voir supra) et la bijectivité de σ₂, il vient que :

${\begin{alignedat}{2}&\varepsilon (\sigma _{1}\circ \sigma _{2})\varepsilon (\sigma _{2})&&=\prod _{1\leq i<j\leq n}\operatorname {sgn}(\sigma _{1}\circ \sigma _{2}(j)-\sigma _{1}\circ \sigma _{2}(i))\prod _{1\leq i<j\leq n}\operatorname {sgn}(\sigma _{2}(j)-\sigma _{2}(i))\\&&&=\prod _{\{i,j\}\in {\mathcal {P}}}\operatorname {sgn}(\sigma _{1}(\sigma _{2}(j))-\sigma _{1}(\sigma _{2}(i)))\operatorname {sgn}(\sigma _{2}(j)-\sigma _{2}(i))\\&&&=\prod _{\{k,l\}\in {\mathcal {P}}}\operatorname {sgn}(\sigma _{1}(l)-\sigma _{1}(k))\operatorname {sgn}(l-k)\\&&&=\prod _{1\leq k<l\leq n}\operatorname {sgn}(\sigma _{1}(l)-\sigma _{1}(k))\\&&&=\varepsilon (\sigma _{1})\end{alignedat}}$

Or $\varepsilon (\sigma _{2})\in \{-1,1\}$, donc $\varepsilon (\sigma _{1}\circ \sigma _{2})=\varepsilon (\sigma _{1})\varepsilon (\sigma _{2})$.

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

En particulier, toute permutation conjuguée de σ a même signature que σ (car $\varepsilon (\rho \sigma \rho ^{-1})=\varepsilon (\rho )\varepsilon (\sigma )\varepsilon (\rho )^{-1}=\varepsilon (\sigma )$).

Une transposition est impaire

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

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

D'après les deux sections précédentes et la décomposition en produit de transpositions :

• une permutation est paire si et seulement si elle est décomposable en un nombre pair de transpositions ;
• une permutation est impaire 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 ${\mathfrak {S}}_{n}$, 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

• L'identité de {1, … , n} est paire.
• La permutation inverse de σ a même parité que σ.
• Une permutation circulaire est paire si et seulement si son support contient un nombre impair d'éléments (voir supra).

Cette dernière observation permet de calculer la signature d'une permutation décomposée en cycles. La signature d'une permutation $\sigma$ de ${\mathfrak {S}}_{n}$ vaut $(-1)^{n-m}=(-1)^{p}$, où m est le nombre de cycles de la décomposition (en comptant les points fixes comme cycles de longueur 1) dans $\sigma$ et p le nombre de cycles de longueur paire dans cette même décomposition.

Morphisme

${\mathfrak {S}}_{1}$ étant le groupe trivial, supposons $n\geq 2$.

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

Ce sous-groupe ${\mathfrak {A}}_{n}$ étant le groupe dérivé de ${\mathfrak {S}}_{n}$, la signature est donc une réalisation du morphisme canonique de ${\mathfrak {S}}_{n}$ dans son abélianisé, le groupe quotient ${\mathfrak {S}}_{n}/{\mathfrak {A}}_{n}\simeq (\{-1,1\},\times )$. Cela signifie que tout morphisme f de ${\mathfrak {S}}_{n}$ 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 ε.

Démonstration directe

Cette démonstration utilise ce qui précède et la décomposition des permutations en produit de transpositions.

Soit f un morphisme non trivial de ${\mathfrak {S}}_{n}$ dans un groupe abélien G, noté multiplicativement.

Il existe une permutation $\sigma$ telle que $f(\sigma )\neq 1$, et comme $\sigma$ est un produit de transpositions, il existe une transposition $\tau _{0}$ telle que $\lambda :=f(\tau _{0})\neq 1$.

Le raisonnement fait ci-dessus pour ε s'applique aussi à f : toutes les transpositions étant conjuguées, elles ont même image par f. Pour toute transposition $\tau$, on a donc $f(\tau )=f(\tau _{0})=\lambda$.

Ainsi, toute permutation $\sigma$, se décomposant en en produit $\tau _{1}\tau _{2}\dots \tau _{m}$ de m de transpositions, vérifie : $f(\sigma )=f(\tau _{1})f(\tau _{2})\dots f(\tau _{m})=\lambda ^{m}$.

En particulier, $\lambda$ est d'ordre 2 car $\mathrm {Id} =\tau _{0}^{2}$ donc $\lambda ^{2}=f(\mathrm {Id} )=1$.

Ainsi, selon la parité de m :

$f(\sigma )=\lambda ^{m}={\begin{cases}\lambda &{\text{si }}\varepsilon (\sigma )=-1\\1&{\text{si }}\varepsilon (\sigma )=1.\end{cases}}$

Une formule pour la signature

Dans le cas où la signature est définie à valeur dans l'anneau des entiers relatifs, toute permutation $\sigma \in {\mathfrak {S}}_{n}$ a pour signature :

$\varepsilon (\sigma )=\prod _{1\leq i<j\leq n}{\frac {\sigma (j)-\sigma (i)}{j-i}}=\prod _{\{i,j\}\in {\mathcal {P}}}{\frac {\sigma (j)-\sigma (i)}{j-i}}$,

où ${\mathcal {P}}$ désigne l'ensemble des paires d'entiers distincts compris entre 1 et n.

Démonstration

En utilisant la définition de ε (voir supra), il vient que :

$\varepsilon (\sigma )=\prod _{1\leq i<j\leq n}\operatorname {sgn}(\sigma (j)-\sigma (i))=\prod _{1\leq i<j\leq n}{\frac {\sigma (j)-\sigma (i)}{\left|\sigma (j)-\sigma (i)\right|}}={\frac {\prod _{1\leq i<j\leq n}{\left(\sigma (j)-\sigma (i)\right)}}{\prod _{1\leq i<j\leq n}{\left|\sigma (j)-\sigma (i)\right|}}}$

Et l'on peut transformer le dénominateur en utilisant la bijectivité de σ :

$\prod _{1\leq i<j\leq n}\left|\sigma (j)-\sigma (i)\right|=\prod _{\{i,j\}\in {\mathcal {P}}}\left|\sigma (j)-\sigma (i)\right|=\prod _{\{k,l\}\in {\mathcal {P}}}\left|k-l\right|=\prod _{1\leq i<j\leq n}{j-i}$