École AVOSZ

Connectez-vous

386. Existence et unicité de la signature pour les permutations

Yannis TRIANTAPHYLIDES

Soit $E$ un ensemble fini contenant au moins deux éléments. La notation $\mathfrak{S}_E$ désigne l’ensemble des permutations de $E$ muni de la composition.

Unicité de la signature

Supposez qu’il existe une application $\varepsilon$ qui va de $\mathfrak{S}_E$ dans $\{-1,1\}$ et telle que :

\left\{\begin{align*} &\forall (\sigma_1, \sigma_2)\in (\mathfrak{S}_E)^2, \quad \varepsilon(\sigma_1 \sigma_2) = \varepsilon(\sigma_1) \varepsilon(\sigma_2)\\ &\exists \sigma_0 \in \mathfrak{S}_E, \quad \varepsilon(\sigma_0) \neq 1. \end{align*} \right.

L’existence de la permutation $\sigma_0$ permet d’affirmer que $\varepsilon(\sigma_0) = -1.$

Montrez qu’il existe une transposition $\tau_0$ telle que $\varepsilon(\tau_0) = -1$

Vous raisonnez par l’absurde et vous supposez que, pour toute transposition $\tau \in \mathfrak{S}_E$ vous avez $\varepsilon(\tau) = 1.$

Si $\sigma_0$ est l’application identité de $E\comma$ choisissez une transposition $\tau$ quelconque, ce qui est possible puisque $E$ contient au moins deux éléments. Vous avez $\sigma_0 = \tau \tau$ et donc $\varepsilon(\sigma_0) = \varepsilon(\tau)\varepsilon(\tau) = 1\times 1 = 1$ ce qui est impossible.

Donc la permutation $\sigma_0$ n’est pas l’application identité. Elle s’écrit donc comme un produit non vide de cycles à supports disjoints. Or, tout cycle s’écrit comme un produit de transpositions. En effet, si $c$ est un cycle, il existe un entier $r\geq 2$ et $(e_1,\dots, e_r)\in E^r$ tels que $c = (e_1 \cdots e_r).$ Vous avez alors $c = \prod_{k=1}^{r-1} (e_k\ e_{k+1}).$ Du coup, $\varepsilon(c) = \prod_{k=1}^{r-1} \varepsilon((e_k\ e_{k+1})) = \prod_{k=1}^{r-1} 1 =1.$ Or, il existe un entier $m\geq 1$ et des cycles $c_1,\dots,c_m$ tels que $\sigma_0 = \prod_{k=1}^m c_k.$ Il vient $\varepsilon(\sigma_0) = \prod_{k=1}^m \varepsilon(c_k) = \prod_{k=1}^m 1 = 1$ ce qui est absurde.

Donc il existe une transposition $\tau_0$ telle que $\varepsilon(\tau_0) = -1.$

Montrez que pour toute transposition $\tau$ vous avez $\varepsilon(\tau) = -1$

Le support de $\tau_0$ contient exactement deux éléments distincts de $E.$ Vous les notez $a$ et $b$ et donc $\tau_0 = (a\ b).$

Soit maintenant $\tau\in \mathfrak{S}_E$ une transposition. Le support de $\tau$ contient exactement deux éléments distincts de $E$ que vous notez $i$ et $j$ de sorte que $\tau = (i\ j).$

Comme $E\setminus \{a, b\}$ et $E\setminus \{i, j\}$ ont exactement le même nombre d’éléments, il existe une bijection $f$ qui va de $E\setminus \{a, b\}$ vers $E\setminus \{i, j\}.$

Vous définissez maintenant une application $\sigma$ qui va de $E$ dans $E$ par :

\left\{ \begin{align*} &\sigma(a) = i\\ &\sigma(b) = j\\ &\forall x\in E\setminus \{a, b\}, \sigma(x) = f(x). \end{align*} \right.

Vous montrez tout d’abord que $\sigma$ est une permutation de $E.$

Comme $\sigma$ est une application qui va de $E$ dans $E$ (avec $E$ qui est un ensemble fini), elle est bijective, si et seulement si, elle est surjective.

Soit maintenant $y$ un élément de $E.$ Si $y\in\{i, j\}$ alors soit $y = \sigma(a)$ soit $y = \sigma(b)$ donc $y$ admet au moins un antécédent par $\sigma.$ Si $y\notin \{i, j\}$ alors $y\in E\setminus \{i, j\}.$ Or $f$ est une bijection de $E\setminus \{a, b\}$ vers $E\setminus \{i, j\}$ en particulier $f$ est surjective donc il existe $x\in E\setminus \{a, b\}$ tel que $y = f(x).$ Comme $x\in E\setminus \{a, b\}$ vous avez $\sigma(x) = f(x)$ donc $y = \sigma(x)$ et $y$ admet au moins un antécédent par la fonction $\sigma$ puisque $x\in E.$

De cette analyse, $\sigma$ est surjective, donc bijective.

Vous allez maintenant montrer que $\sigma^{-1}\tau \sigma = \tau_0.$

Soit $x\in E.$ Trois cas se présentent.

Si $x= a$ alors :

\begin{align*} (\sigma^{-1}\tau \sigma)(a) &= (\sigma^{-1}\tau)(\sigma(a)) \\ &= (\sigma^{-1}\tau)(i) \\ &= \sigma^{-1}(\tau (i)) \\ &= \sigma^{-1}(j) \\ &= b\\ &= \tau_0(a). \end{align*}

Si $x=b$ alors :

\begin{align*} (\sigma^{-1}\tau \sigma)(b) &= (\sigma^{-1}\tau)(\sigma(b)) \\ &= (\sigma^{-1}\tau)(j) \\ &= \sigma^{-1}(\tau (j)) \\ &= \sigma^{-1}(i) \\ &= a\\ &= \tau_0(b). \end{align*}

Si $x\notin \{a, b\}$ alors :

\begin{align*} (\sigma^{-1}\tau \sigma)(x) &= (\sigma^{-1}\tau)(\sigma(x)) \\ &= \sigma^{-1}(\tau (\sigma(x)))\\ &= \sigma^{-1}(\tau (f(x))). \end{align*}

Or, $f(x) \in E\setminus \{i, j\}.$ Donc $f(x)$ n’appartient pas au support de $\tau$ donc $\tau ( f(x) ) = f(x).$ Ainsi :

\begin{align*} (\sigma^{-1}\tau \sigma)(x) &= \sigma^{-1}(\tau (f(x))) \\ &= \sigma^{-1}( \sigma(x)) \\ &= x. \end{align*}

Vous remarquez que $x$ n’appartient pas au support de $\tau_0$ donc $\tau_0(x) = x.$ Du coup :

(\sigma^{-1}\tau \sigma)(x) = \tau_0(x).

Il a été démontré que :

\sigma^{-1}\tau \sigma = \tau_0.

En appliquant $\varepsilon$ vous déduisez :

\varepsilon(\sigma^{-1}) \varepsilon(\tau) \varepsilon(\sigma) = \varepsilon(\tau_0) = -1.

Or en notant $\id$ l’application identité de $E$ vous avez :

\begin{align*} \varepsilon(\id) &= \varepsilon(\id\ \id)\\ &= \varepsilon(\id) \varepsilon(\id)\\ &= (\varepsilon(\id) )^2. \end{align*}

Comme $\varepsilon(\id) \neq 0$ vous déduisez :

\varepsilon(\id) = 1.

Du coup :

\varepsilon(\sigma^{-1}) \varepsilon(\sigma) = \varepsilon(\sigma^{-1}\sigma) = \varepsilon(\id) = 1.

Et vous concluez :

\begin{align*} \varepsilon(\tau) &= \varepsilon(\tau) \times 1 \\ &= \varepsilon(\tau) \varepsilon(\sigma^{-1}) \varepsilon(\sigma) \\ &= \varepsilon(\sigma^{-1}) \varepsilon(\tau) \varepsilon(\sigma) \\ &= \varepsilon(\tau_0) \\ &= -1. \end{align*}

Ainsi, pour toute transposition $\tau$ vous avez $\varepsilon(\tau) = -1.$

Déduisez-en une expression de $\varepsilon$

Cas d’une permutation qui n’est pas l’identité

Soit $\sigma \in \mathfrak{S}_E$ une permutation de $E$ différente de l’identité.

Il existe un entier $k\geq 1$ et des cycles à supports disjoints $c_1,\dots,c_k$ tels que $\sigma = \prod_{i=1}^{k} c_i.$

Pour tout $i\in\llbracket 1, k\rrbracket$ notez $\ell_i$ la longueur du cycle $c_i.$ Par définition d’un cycle, vous avez $\ell_i \geq 2.$ Il a été vu plus haut que $c_i$ s’écrit comme un produit de $\ell_i-1$ transpositions.

Vous en déduisez que $\sigma$ s’écrit comme un produit de $\sum_{i=1}^{k} (\ell_i-1)$ transpositions. Comme la signature de chaque transposition est égale à $-1$ il s’ensuit que la signature de $\sigma$ est égale à :

\varepsilon(\sigma) = (-1)^{\sum_{i=1}^{k} (\ell_i-1)}.

Notez $\vert E \vert$ le nombre d’éléments de l’ensemble $E.$ Le support de $\sigma$ possède exactement $\sum_{i=1}^{k} \ell_i$ éléments. Si $m$ désigne le nombre de points fixes de $\sigma$ alors $\sum_{i=1}^{k} \ell_i + m = \vert E \vert$ d’où :

\begin{align*} \sum_{i=1}^{k} (\ell_i-1) &= \left(\sum_{i=1}^{k} \ell_i\right)-k \\ &= \vert E \vert – m-k. \end{align*}

Or, comme la décomposition de $\sigma$ en produit de cycles à supports disjoints est unique à l’ordre près des facteurs, le nombre $k$ ne dépend que de $\sigma$ ce qui donne :

\varepsilon(\sigma) = (-1)^{\vert E \vert – m-k}.

Cas de l’identité

Quand $\sigma$ est l’identité, vous convenez de l’écrire comme un produit vide de cycles à supports disjoints. Ainsi $k=0.$ Le nombre de points fixes de l’identité est $m = \vert E \vert.$ Ainsi $(-1)^{\vert E \vert – m-k} = 1 = \varepsilon(\id).$

Concluez

Vous avez donc établi le résultat suivant. Pour toute permutation $\sigma$ notez $k\in\N$ le nombre de cycles à supports disjoints intervenant dans sa décomposition et $m$ le nombre de points fixes de $\sigma.$ Alors :

\boxed{\varepsilon(\sigma) = (-1)^{\vert E \vert – m-k}.}

Existence de la signature

Pour toute permutation $\sigma \in \mathfrak{S}_E$ vous notez $m$ le nombre de points fixes de $\sigma$ et $k\in\N$ son nombre de cycles à supports disjoints.

Vous définissez l’application $\varepsilon$ qui va de $\mathfrak{S}_E$ dans $\{-1,1\}$ en posant :

\varepsilon(\sigma) = (-1)^{\vert E \vert – m-k}.

Soit $\tau$ une transposition. Celle-ci est composée d’un seul cycle donc $k=1$ et d’autre part son nombre de points fixes est $m = \vert E \vert – 2$ ce qui fournit $\vert E \vert – m=2.$ Ainsi :

\begin{align*} \varepsilon(\tau) &= (-1)^{\vert E \vert – m-k} \\ &= (-1)^{2-k}\\ & = (-1)^{k}\\ & = (-1)^{1}\\ &=-1. \end{align*}

Toutes les transpositions ont une image égale à $-1$ par l’application $\varepsilon.$

Comme $E$ possède au moins deux éléments distincts $a$ et $b$ vous considérez la transposition $\tau_0 = (a\ b)$ et vous avez bien $\exists \tau_0\in\mathfrak{S}_E, \varepsilon(\tau_0)\neq 1.$

Soit maintenant $\tau$ une transposition et $\sigma$ une permutation. Vous notez $m$ le nombre de points fixes de $\sigma$ et $k\in\N$ son nombre de cycles à supports disjoints.

Si $k=0$ alors $\sigma$ est l’identité. Il vient :

\begin{align*} \varepsilon(\tau \sigma) &= \varepsilon(\tau\ \id) \\ &= \varepsilon(\tau) \\ &= -1\\ &=-1\times 1\\ &= \varepsilon(\tau)\varepsilon(\id)\\ &= \varepsilon(\tau)\varepsilon(\sigma). \end{align*}

Si $k\geq 1$ alors $\sigma$ s’écrit comme un produit non vide de $k$ cycles à supports disjoints. Vous notez $m’$ le nombre de points fixes de $\tau \sigma$ et $k’$ le nombre de cycles de $\tau \sigma$ dans sa décomposition de cycles à supports disjoints. Comme il a été vu dans l’article 385, quatre cas se présentent. Pour les traiter tous de la même façon, remarquez que $\vert E \vert – m-k = \sum_{i=1}^{k} (\ell_i-1)$ (voir plus haut), où un « cycle » de longueur $1$ n’est autre qu’un point fixe, qui ne contribue pas à cette somme.

Pour en savoir davantage, allez lire le contenu rédigé dans l'article 385.

  • supports totalement disjoints et commutation : les supports de $\tau$ et de $\sigma$ sont disjoints. Ainsi $m’ = m-2$ et $k’ = k+1.$ Du coup $\varepsilon(\tau \sigma) = (-1)^{\vert E \vert – m’-k’} = (-1)^{\vert E \vert – m-k+1} = – \varepsilon(\sigma).$ Or $\varepsilon(\tau) = -1$ d’où $\varepsilon(\tau \sigma) = \varepsilon(\tau)\varepsilon(\sigma).$
  • fusion : deux cycles de $\sigma$ fusionnent et dans ce cas $m’ = m$ et $k’ = k-1$ et ainsi $\varepsilon(\tau \sigma) = (-1)^{\vert E \vert – m’-k’} = (-1)^{\vert E \vert – m-k+1} = – \varepsilon(\sigma) = \varepsilon(\tau)\varepsilon(\sigma).$
  • insertion : il se peut qu’un élément de $\tau$ soit inséré dans un des cycles de $\sigma.$ Dans ce cas $m’ = m-1$ et $k’=k$ et donc $\varepsilon(\tau \sigma) = (-1)^{\vert E \vert – m’-k’} = (-1)^{\vert E \vert – m-k+1} = – \varepsilon(\sigma) = \varepsilon(\tau)\varepsilon(\sigma).$
  • rupture de cycle : les deux éléments de $\tau$ appartiennent au support de l’un des cycles de $\sigma\comma$ de longueur $\ell.$ Ce cycle est remplacé par deux cycles de longueurs $\ell_1$ et $\ell_2$ telles que $\ell_1+\ell_2=\ell\comma$ un cycle de longueur $1$ étant en fait un point fixe. Si $\ell_1\geq 2$ et $\ell_2\geq 2\comma$ alors $m’=m$ et $k’ = k+1$ ; si une seule des deux longueurs vaut $1\comma$ alors $m’=m+1$ et $k’=k$ ; si $\ell_1=\ell_2=1\comma$ c’est-à-dire si $\ell = 2\comma$ alors $m’=m+2$ et $k’=k-1.$ Dans les trois situations, $\vert E \vert – m’-k’ = \vert E \vert – m-k-1.$ D’où $\varepsilon(\tau \sigma) = (-1)^{\vert E \vert – m’-k’} = (-1)^{\vert E \vert – m-k-1} = – \varepsilon(\sigma) = \varepsilon(\tau)\varepsilon(\sigma).$

Vous venez de démontrer que, pour toute transposition $\tau$ et pour toute permutation $\sigma$, $\varepsilon(\tau \sigma) = \varepsilon(\tau)\varepsilon(\sigma).$

Soient maintenant $\sigma$ et $\sigma’$ deux permutations quelconques. $\sigma’$ peut toujours s’écrire comme un produit non vide de transpositions. Il existe $s\geq 1$ et des transpositions $\tau_1,\dots,\tau_s$ telles que $\sigma’ = \tau_1\cdots \tau_s.$ En vertu de ce qui précède :

\begin{align*} \varepsilon(\sigma' \sigma) &= \varepsilon\left( \tau_1\left( \left[\prod_{i=2}^s\tau_i\right] \sigma\right) \right)\\ &= \varepsilon(\tau_1)\varepsilon\left( \left[\prod_{i=2}^s\tau_i\right] \sigma\right)\\ &=\dots \\ &=\varepsilon(\tau_1)\cdots \varepsilon(\tau_s)\varepsilon(\sigma). \end{align*}

Or :

\begin{align*} \varepsilon(\sigma')\varepsilon(\sigma) &= \varepsilon\left( \left[\prod_{i=1}^s\tau_i\right] \right)\varepsilon(\sigma)\\ &= \varepsilon(\tau_1)\varepsilon\left( \left[\prod_{i=2}^s\tau_i\right] \right) \varepsilon(\sigma)\\ &=\dots \\ &=\varepsilon(\tau_1)\cdots \varepsilon(\tau_s)\varepsilon(\sigma). \end{align*}

Note. Par convention, un produit vide d’éléments de $\mathfrak{S}_E$ est égal à l’application identité de $E.$

Note. Les pointillés devraient être rédigés en utilisant des récurrences finies. Pour des raisons de longueur, il a été choisi d’omettre les détails correspondants.

Il a été démontré que :

\boxed{\forall (\sigma', \sigma)\in (\mathfrak{S}_E)^2, \quad \varepsilon(\sigma' \sigma) = \varepsilon(\sigma') \varepsilon(\sigma).}

Concluez

Il existe exactement deux morphismes de groupes qui vont de $\mathfrak{S}_E$ muni de la composition dans $\{-1,1\}$ muni de la multiplication. Ce sont la signature $\varepsilon$ précédemment définie et l’application constante égale à $1$ sur toutes les permutations de $E.$

La signature est ainsi l’unique morphisme de groupes non trivial de $\mathfrak{S}_E$ dans $\{-1,1\}.$