Signature

Définition intuitive

La signature mesure la parité d’une permutation : elle vaut $+1$ si on peut la réaliser par un
nombre pair d’échanges de deux éléments, et $-1$ s’il en faut un nombre impair. Le fait
remarquable, et nullement évident a priori, est que cette parité ne dépend pas de la manière
dont on décompose la permutation : deux suites d’échanges menant au même résultat ont
toujours des longueurs de même parité. On dispose ainsi d’un invariant à deux valeurs, le plus
grossier possible, mais aussi le seul : c’est l’unique façon de mesurer une permutation par un
signe multiplicatif. Cette dichotomie pair/impair sépare $\mathfrak{S}_n$ en deux moitiés, dont
l’une, le groupe alterné, est un sous-groupe d’indice $2$. Elle explique le signe alterné dans
le développement du déterminant, l’impossibilité de résoudre certaines configurations du jeu
de taquin, et, via la simplicité de $\mathfrak{A}_n$ pour $n\geqslant 5$, l’insolubilité par
radicaux des équations de degré $\geqslant 5$.

Définition formelle

Soit $n\geqslant 1$ et $\sigma\in\mathfrak{S}_n$. On appelle inversion de $\sigma$ tout couple
$(i,j)$ avec $i<j$ et $\sigma(i)>\sigma(j)$, et l’on note $I(\sigma)$ leur nombre. La
signature de $\sigma$ est
$$\varepsilon(\sigma)=(-1)^{I(\sigma)}=\prod_{1\leqslant i<j\leqslant n}\frac{\sigma(j)-\sigma(i)}{j-i}\ \in\{-1,+1\}.$$

L’application $\varepsilon:\mathfrak{S}_n\to(\{\pm1\},\times)$ est un morphisme de groupes,
surjectif dès que $n\geqslant 2$, et c’est alors l’unique morphisme non trivial de
$\mathfrak{S}_n$ vers $\{\pm 1\}$. Son noyau est le groupe alterné
$$\mathfrak{A}_n=\ker\varepsilon,\qquad [\mathfrak{S}_n:\mathfrak{A}_n]=2,\qquad |\mathfrak{A}_n|=\frac{n!}{2}.$$

Trois caractérisations équivalentes, souvent plus commodes que la définition :
$$\varepsilon(\tau)=-1 \text{ pour toute transposition }\tau; \varepsilon(\sigma)=(-1)^{\ell-1}\text{ pour un cycle de longueur }\ell; \varepsilon(\sigma)=(-1)^{\,n-c(\sigma)},$$où $c(\sigma)$ désigne le nombre d’orbites de $\sigma$ dans $\{1,\dots,n\}$, points fixes
compris. En particulier, si $\sigma$ est produit de $k$ transpositions, alors
$\varepsilon(\sigma)=(-1)^{k}$ : la parité de $k$ est un invariant de $\sigma$.

Remarques

• La formule produit ci-dessus rend la multiplicativité immédiate : les deux applications
  $(i,j)\mapsto(\sigma(i),\sigma(j))$ permutent les paires, et le produit se réindexe sans
  changement de valeur absolue. C’est la démonstration la plus courte du caractère bien défini
  de la parité.
• Formulation par les polynômes : en faisant agir $\mathfrak{S}_n$ sur
  $\mathbb{Z}[X_1,\dots,X_n]$, le polynôme de Vandermonde
  $\Delta=\prod_{i<j}(X_i-X_j)$ vérifie $\sigma\cdot\Delta=\varepsilon(\sigma)\,\Delta$ : la
  signature est le caractère par lequel $\mathfrak{S}_n$ agit sur la droite engendrée par
  $\Delta$.
• Formulation matricielle : si $P_\sigma$ est la matrice de permutation associée, alors
  $\varepsilon(\sigma)=\det P_\sigma$. C’est ce qui fait apparaître la signature dans la
  formule de Leibniz $\det A=\sum_{\sigma}\varepsilon(\sigma)\prod_i a_{i,\sigma(i)}$, et donc
  dans toute la théorie du déterminant et des formes alternées.
• $\mathfrak{A}_n$ est le seul sous-groupe d’indice $2$ de $\mathfrak{S}_n$, et il est simple
  pour $n\geqslant 5$, point de départ de la preuve d’Abel–Galois de l’insolubilité par
  radicaux du degré $5$. Pour $n\geqslant 2$, $\mathfrak{A}_n$ est aussi le groupe dérivé de
  $\mathfrak{S}_n$.
• La signature s’étend au groupe $\mathfrak{S}_{(\infty)}$ des permutations à support fini d’un
  ensemble infini, mais pas au groupe de toutes les permutations d’un ensemble infini : la
  notion de parité y perd tout sens.
• Homonymie à ne pas confondre : la signature d’une forme quadratique réelle est le couple
  $(p,q)$ des nombres de carrés positifs et négatifs dans une décomposition orthogonale, dont
  la loi d’inertie de Sylvester garantit l’invariance. Les deux notions n’ont en commun que le
  nom et le statut d’invariant.

Exemples

1. Pour $\sigma=\begin{pmatrix}1&2&3\\2&3&1\end{pmatrix}$, les inversions sont $(1,3)$ et
   $(2,3)$, donc $\varepsilon(\sigma)=+1$ ; c’est cohérent avec le fait que $\sigma$ est un
   $3$-cycle, de signature $(-1)^{3-1}=+1$.
2. Une transposition est de signature $-1$, un $3$-cycle de signature $+1$, un $4$-cycle de
   signature $-1$. Plus généralement, un cycle est pair si et seulement si sa longueur est
   impaire.
3. Une permutation de type cyclique $\ell_1,\dots,\ell_r$ (partition de $n$) a pour signature
   $\prod_{i}(-1)^{\ell_i-1}=(-1)^{\,n-r}$. Dans $\mathfrak{S}_4$, les doubles transpositions
   comme $(1\,2)(3\,4)$ sont donc paires : avec l’identité elles forment le groupe de Klein,
   distingué dans $\mathfrak{A}_4$.
4. $\mathfrak{A}_3=\{\mathrm{id},(1\,2\,3),(1\,3\,2)\}\simeq\mathbb{Z}/3\mathbb{Z}$, tandis que
   les trois transpositions de $\mathfrak{S}_3$ forment l’autre classe, de signature $-1$.
5. Jeu de taquin. Une configuration du puzzle $4\times 4$ est atteignable si et seulement
   si la signature de la permutation des tuiles est compatible avec la parité de la distance
   de la case vide à sa position finale. La configuration obtenue en échangeant seulement les
   tuiles $14$ et $15$ est donc insoluble.
6. Cube de Rubik. Un quart de tour induit un $4$-cycle sur les sommets et un $4$-cycle sur
   les arêtes, tous deux impairs : le produit des deux signatures vaut $+1$ et reste invariant.
   Il est donc impossible d’échanger deux arêtes en laissant tout le reste en place.
7. Contre-exemple. La signature n’est pas injective ni fidèle : dès que $n\geqslant 3$,
   des permutations très différentes partagent la même signature, c’est un invariant complet
   uniquement pour $n\leqslant 2$.