Déterminants

On construit une bijection de ${\mathfrak{S}}_n$ sur l'ensemble des suites $(\sigma (1),\sigma (2),\dots ,\sigma (n))$ d'entiers deux à deux distincts de $[[1,n]]$.

Pour $\sigma (1)$, on dispose de $n$ choix. Pour $\sigma (2)$, puisque $\sigma$ est injective, on dispose de $n-1$ choix (tous les éléments de $[[1,n]]$ sauf $\sigma (1)$). Plus généralement, pour $\sigma (k)$, on dispose de $n-(k-1)=n-k+1$ choix.

Par le principe multiplicatif, le nombre total de telles suites est :$$n\times (n-1)\times \cdots \times 2\times 1=n!$$Donc $|{\mathfrak{S}}_n|=n!$.

On fixe $n\ge 1$. Pour $n=1$, ${\mathfrak{S}}_1=\{\mathrm{Id}\}$ et il n'existe aucun morphisme non trivial sur $\{-1,1\}$ ; l'énoncé concerne donc le cas $n\ge 2$, que l'on suppose désormais. Rappelons qu'un morphisme de groupes $\phi :({\mathfrak{S}}_n,\circ )\to (\{-1,1\},\times )$ est une application vérifiant $\phi (\sigma \circ {\sigma }^{\prime })=\phi (\sigma )\phi ({\sigma }^{\prime })$ pour tous $\sigma ,{\sigma }^{\prime }\in {\mathfrak{S}}_n$, et l'on cherche un tel morphisme qui soit non constant.

1. Existence.

On construit explicitement un morphisme non trivial à l'aide du nombre d'inversions. Pour $\sigma \in {\mathfrak{S}}_n$, on appelle inversion de $\sigma$ toute paire $\{i,j\}$ d'éléments distincts de $[[1,n]]$ telle que $i-j$ et $\sigma (i)-\sigma (j)$ soient de signes opposés. On note $I(\sigma )$ le nombre d'inversions de $\sigma$ et l'on pose$$\epsilon (\sigma )=(-1{)}^{I(\sigma )}.$$Cette quantité s'exprime commodément à l'aide d'un produit. Pour $\sigma \in {\mathfrak{S}}_n$, considérons$$P(\sigma )=\prod _{1\le i<j\le n}\frac{\sigma (j)-\sigma (i)}{j-i}.$$Ce produit porte sur toutes les paires $\{i,j\}$ avec $i<j$. Comme $\sigma$ est une bijection de $[[1,n]]$, l'application $\{i,j\}\mapsto \{\sigma (i),\sigma (j)\}$ est une bijection de l'ensemble des paires d'éléments distincts de $[[1,n]]$ sur lui-même. Par conséquent, l'ensemble des facteurs $|\sigma (j)-\sigma (i)|$ (pour $i<j$) est, à l'ordre près, exactement l'ensemble des $j-i$ (pour $i<j$) : les valeurs absolues du numérateur et du dénominateur de $P(\sigma )$ sont les mêmes à permutation près, donc $|P(\sigma )|=1$. Le signe de $P(\sigma )$ est, lui, $(-1)$ élevé au nombre de facteurs négatifs, c'est-à-dire au nombre de paires $\{i,j\}$ telles que $\sigma (j)-\sigma (i)$ et $j-i$ soient de signes opposés. Ce nombre est précisément $I(\sigma )$. On a donc l'égalité$$P(\sigma )=(-1{)}^{I(\sigma )}=\epsilon (\sigma )\in \{-1,1\}.$$Montrons maintenant que $\epsilon$ est un morphisme. Soient $\sigma ,{\sigma }^{\prime }\in {\mathfrak{S}}_n$. Calculons $P(\sigma \circ {\sigma }^{\prime })$ :$$P(\sigma \circ {\sigma }^{\prime })=\prod _{i<j}\frac{\sigma ({\sigma }^{\prime }(j))-\sigma ({\sigma }^{\prime }(i))}{j-i}=\prod _{i<j}\frac{\sigma ({\sigma }^{\prime }(j))-\sigma ({\sigma }^{\prime }(i))}{{\sigma }^{\prime }(j)-{\sigma }^{\prime }(i)}\times \prod _{i<j}\frac{{\sigma }^{\prime }(j)-{\sigma }^{\prime }(i)}{j-i}.$$Le second produit vaut $P({\sigma }^{\prime })=\epsilon ({\sigma }^{\prime })$. Dans le premier produit, lorsque $\{i,j\}$ décrit l'ensemble des paires d'éléments distincts (avec $i<j$), la paire $\{{\sigma }^{\prime }(i),{\sigma }^{\prime }(j)\}$ décrit, par bijectivité de ${\sigma }^{\prime }$, le même ensemble de paires. Or chaque facteur$$\frac{\sigma ({\sigma }^{\prime }(j))-\sigma ({\sigma }^{\prime }(i))}{{\sigma }^{\prime }(j)-{\sigma }^{\prime }(i)}$$est invariant si l'on échange $i$ et $j$ (numérateur et dénominateur changent simultanément de signe). Ce facteur ne dépend donc que de la paire $\{{\sigma }^{\prime }(i),{\sigma }^{\prime }(j)\}$, et le premier produit est égal à$$\prod _{1\le k<l\le n}\frac{\sigma (l)-\sigma (k)}{l-k}=P(\sigma )=\epsilon (\sigma ).$$On obtient ainsi$$\epsilon (\sigma \circ {\sigma }^{\prime })=P(\sigma \circ {\sigma }^{\prime })=P(\sigma )P({\sigma }^{\prime })=\epsilon (\sigma )\epsilon ({\sigma }^{\prime }).$$Comme de plus $\epsilon (\sigma )\in \{-1,1\}$ pour tout $\sigma$, l'application $\epsilon$ est bien un morphisme de $({\mathfrak{S}}_n,\circ )$ dans $(\{-1,1\},\times )$.

Il reste à vérifier que $\epsilon$ est non trivial. Comme $n\ge 2$, considérons la transposition $\tau =(1,2)$. Elle échange $1$ et $2$ et fixe tous les autres entiers. La seule paire $\{i,j\}$ pour laquelle $\tau (i)-\tau (j)$ et $i-j$ sont de signes opposés est $\{1,2\}$ ; toutes les autres paires sont préservées dans leur ordre. Donc $I(\tau )=1$ et$$\epsilon (\tau )=(-1{)}^1=-1\ne 1.$$Ainsi $\epsilon$ n'est pas constant : c'est un morphisme non trivial. Ceci établit l'existence.

2. Unicité.

Soit $\phi :({\mathfrak{S}}_n,\circ )\to (\{-1,1\},\times )$ un morphisme non trivial quelconque. Montrons que $\phi =\epsilon$.

Première étape : déterminons la valeur de $\phi$ sur les transpositions. Soit $\tau$ une transposition. D'après une remarque du paragraphe 1.2, on a ${\tau }^2={\mathrm{Id}}_{[[1,n]]}$. Comme $\phi$ est un morphisme, $\phi (\mathrm{Id})=1$ (l'image du neutre est le neutre), donc$$\phi (\tau {)}^2=\phi (\tau \circ \tau )=\phi (\mathrm{Id})=1.$$Comme $\phi (\tau )\in \{-1,1\}$, ceci ne fournit pas immédiatement sa valeur ; montrons que $\phi (\tau )=-1$. Supposons par l'absurde que $\phi$ prenne la valeur $1$ sur au moins une transposition. Toutes les transpositions de ${\mathfrak{S}}_n$ sont en réalité conjuguées entre elles : si $\tau =(a,b)$ et ${\tau }^{\prime }=(c,d)$ sont deux transpositions, et si $\rho \in {\mathfrak{S}}_n$ est une permutation telle que $\rho (a)=c$ et $\rho (b)=d$ (une telle $\rho$ existe car il suffit d'envoyer $a$ sur $c$ et $b$ sur $d$), alors un calcul direct donne $\rho \circ \tau \circ {\rho }^{-1}={\tau }^{\prime }$. En effet, $\rho \circ \tau \circ {\rho }^{-1}$ échange $\rho (a)=c$ et $\rho (b)=d$ et fixe tous les autres éléments. En appliquant le morphisme $\phi$ et en utilisant $\phi ({\rho }^{-1})=\phi (\rho {)}^{-1}=\phi (\rho )$ (car $\phi (\rho )\in \{-1,1\}$), on obtient$$\phi ({\tau }^{\prime })=\phi (\rho )\phi (\tau )\phi (\rho {)}^{-1}=\phi (\tau ).$$Ainsi $\phi$ prend la même valeur sur toutes les transpositions. Si cette valeur commune était $1$, alors, d'après le Théorème 1.2, toute permutation $\sigma$ s'écrivant comme une composée de transpositions $\sigma ={\tau }_1\circ \cdots \circ {\tau }_k$, on aurait$$\phi (\sigma )=\phi ({\tau }_1)\cdots \phi ({\tau }_k)=1,$$et $\phi$ serait le morphisme constant égal à $1$, contredisant l'hypothèse que $\phi$ est non trivial. La valeur commune de $\phi$ sur les transpositions est donc $-1$ : pour toute transposition $\tau$, $\phi (\tau )=-1$.

Seconde étape : on conclut grâce au Théorème 1.2. Soit $\sigma \in {\mathfrak{S}}_n$ une permutation quelconque. D'après le Théorème 1.2, $\sigma$ s'écrit comme une composée de transpositions :$$\sigma ={\tau }_1\circ {\tau }_2\circ \cdots \circ {\tau }_k.$$En appliquant le morphisme $\phi$ et en utilisant $\phi ({\tau }_i)=-1$ pour chaque $i$, il vient$$\phi (\sigma )=\phi ({\tau }_1)\phi ({\tau }_2)\cdots \phi ({\tau }_k)=(-1{)}^k.$$Le même raisonnement appliqué au morphisme $\epsilon$ construit ci-dessus, pour lequel on a aussi $\epsilon ({\tau }_i)=-1$ pour toute transposition (puisque toutes les transpositions sont conjuguées et que $\epsilon ((1,2))=-1$, ou directement car le calcul d'inversions ci-dessus s'adapte), donne $\epsilon (\sigma )=(-1{)}^k$ pour la même décomposition. Par conséquent $\phi (\sigma )=\epsilon (\sigma )$.

Comme ceci vaut pour toute permutation $\sigma \in {\mathfrak{S}}_n$, on conclut $\phi =\epsilon$. Le morphisme non trivial est donc unique.

Conclusion. Il existe un unique morphisme non trivial $\epsilon :({\mathfrak{S}}_n,\circ )\to (\{-1,1\},\times )$, donné par $\epsilon (\sigma )=(-1{)}^{I(\sigma )}$, ou encore par $\epsilon (\sigma )=(-1{)}^k$ si $\sigma$ se décompose en un produit de $k$ transpositions (la parité de $k$ ne dépendant que de $\sigma$). On l'appelle la signature.

Remarque. Cette démonstration montre au passage que, pour toute décomposition de $\sigma$ en produit de transpositions $\sigma ={\tau }_1\circ \cdots \circ {\tau }_k$, la parité de l'entier $k$ est indépendante de la décomposition choisie (elle vaut celle de $I(\sigma )$) : c'est ce qui donne un sens à la notion de permutation paire ou impaire, malgré la non-unicité de la décomposition en transpositions soulignée au paragraphe 1.2.