Permutations

L'ensemble ${\cal S}_n$ des permutations de l'ensemble $\{1,\ldots,n\}$, muni de la composition des applications est le premier exemple de groupe non commutatif que vous ayez rencontré. Vous avez besoin d'en savoir un peu plus pour manipuler des déterminants. La notion importante de cette section est celle de signature. Soit $s\in{\cal S}_n$ une bijection de $\{1,\ldots,n\}$ dans lui-même. Nous la noterons

$$s=\left(\begin{array}{cccc}1 & 2 & \cdots & n\\ s(1) & s(2) & \cdots & s(n)\end{array}\right)$$

Par exemple pour $n=12$ :

$$s=\left(\begin{array}{cccccccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8... ... & 11 & 12\\ 9 & 5 & 3 & 7 & 2 & 12& 11& 10& 4 & 6 & 1 & 8 \end{array}\right)$$

est la bijection qui à $1$ associe $9$, à $2$ associe $5$, etc. On peut se demander pourquoi imposer une notation aussi redondante, puisque les images sont données par la deuxième ligne dans l'ordre de la première. La raison est que l'on réserve une notation plus simple aux cycles. La composition des applications est notée $\circ$, mais nous noterons $s^n$ la composée de $s$ avec elle-même $n$ fois.

Définition 1   Soit $s$ une permutation de ${\cal S}_n$ et $i$ un élément de $\{1,\ldots,n\}$. On appelle orbite de $i$ pour $s$ l'ensemble (fini) $\{s^n(i) ,\;n\in\mathbb{N}\}$.

Dans l'exemple ci-dessus, pour trouver l'orbite de $1$, on calcule l'image de $1$ qui est $9$, puis l'image de $9$ qui est $4$, etc., jusqu'à retrouver $1$ (qui est l'image de $11$). L'orbite de $1$ est donc $\{1,9,4,7,11\}$. L'orbite de $2$ est $\{2,5\}$, celle de $3$ est $\{3\}$ (on dit que $3$ est un point fixe). Observez qu'une orbite est la même pour tous ses éléments : l'orbite de $9$, $4$, $7$ et $11$ est aussi $\{1,9,4,7,11\}$. Le plus petit entier $k$ tel que $s^k(x)=x$ est la longueur de l'orbite $\{x,s(x),s^2(x),\ldots,s^{k-1}(x)\}$. Par définition, un ensemble n'est pas ordonné. Or nous aurons besoin d'un ordre pour écrire des cycles. Nous conviendrons donc d'écrire une orbite comme la liste ordonnée $[x,s(x),\ldots, s^{k-1}(x)]$, où $x$ est le plus petit élément de l'orbite.

Définition 2   On appelle décomposition en orbites de la permutation $s$ la séquence d'orbites disjointes des éléments de $\{1,\ldots,n\}$ pour $s$, écrite par ordre croissant de leurs plus petits éléments.

Un algorithme très simple produit la décomposition en orbites d'une permutation. Tant qu'il reste des éléments de $\{1,\ldots,n\}$ hors des orbites déjà écrites
choisir le plus petit de ces éléments
écrire son orbite
Fin Tant que Dans l'exemple ci-dessus, on commencera donc par écrire l'orbite de $1$ : $[1,9,4,7,11]$. Le premier élément non rangé est $2$. Son orbite est $[2,5]$. L'élément $3$ n'a pas été rangé, son orbite est $[3]$. Le plus petit élément non rangé à ce stade est $6$, dont l'orbite est $[6,12,8,10]$. Tous les éléments ont alors été rangés, et la décomposition en orbites de $s$ est :

$$[1,9,4,7,11],[2,5],[3],[6,12,8,10]$$

Définition 3   Soit $s\in{\cal S}_n$ une permutation et

$$[1,\ldots,s^{k_1-1}(1)],\ldots,[i_h,\ldots,s^{k_h-1}(i_h)]$$

sa décomposition en orbites. On appelle signature de la permutation $s$ et on note $\varepsilon (s)$ :

$$\varepsilon (s) = (-1)^{(k_1-1)+\cdots+(k_h-1)}\;,$$

où $k_1,\ldots,k_h$ sont les longueurs des orbites successives dans la décomposition de $s$.

Toujours sur le même exemple, les longueurs des orbites successives sont $5,2,1,4$, la signature est donc $\varepsilon (s) = (-1)^{4+1+0+3}=+1$. Soyons honnêtes : sachant décomposer une permutation en orbites et en déduire sa signature, vous en savez assez pour calculer des déterminants, ce qui après tout est bien le but de ce chapitre. Il serait dommage de vous en tenir là, car vous perdriez le sel algébrique du groupe des permutations. Voici le résultat principal de cette section.

Théorème 1   L'application signature, de $({\cal S}_n,\circ)$ dans $(\{-1,1\},\times)$ est l'unique homomorphisme surjectif entre ces deux groupes.

La démonstration comporte plusieurs étapes, qui sont autant de résultats intéressants. D'abord, nous allons enrichir les orbites pour donner un sens plus précis à la notion de décomposition.

Définition 4   Soit $k$ un entier supérieur ou égal à $2$, et $i_1,\ldots,i_k$ $k$ éléments tous distincts de $\{1,\ldots,n\}$. On qualifiera de cycle de longueur $k$ et on notera $(i_1,\ldots,i_k)$ la permutation $\sigma$ telle que :

$$\sigma(i_1) = i_2\;,\quad \ldots\;,\quad \sigma(i_{k-1})=i_k \;,\quad \sigma(i_k)=i_1\;,$$

et pour tout $i\notin\{i_1,\ldots,i_k\}$, $\sigma(i)=i$.

L'inconvénient de cette notation est que plusieurs écritures différentes peuvent désigner le même cycle : $(1,2,3)$ et $(2,3,1)$ par exemple. Comme ci-dessus, nous convenons d'écrire en premier le plus petit élément du cycle. Ceci permet d'associer de manière unique un cycle à une orbite. Observez que dans la décomposition en orbites du cycle $(i_1,\ldots,i_k)$ on trouve $[i_1,\ldots,i_k]$, et $n-k$ points fixes. La signature du cycle $(i_1,\ldots,i_k)$ est :

$$\varepsilon ((i_1,\ldots,i_k))= (-1)^{k-1}\;.$$

Proposition 1   Soit $s$ une permutation et

$$[1,\ldots,s^{k_1-1}(1)],\ldots,[i_h,\ldots,s^{k_h-1}(i_h)]$$

sa décomposition en orbites. Alors $s$ est la composée des cycles déduits des orbites de longueur $\geqslant 2$.

$$s=(i_1,\ldots,s^{k'_1-1}(1))\circ\cdots\circ(i_h,\ldots,s^{k'_h-1}(i_h))\;,\quad k'_1,\ldots,k'_h\geqslant 2\;.$$

La vérification est immédiate. Observez que deux cycles commutent si les ensembles d'éléments qu'ils concernent sont disjoints :

$$\{i_1,\ldots,i_k\}\cap\{j_1,\ldots,j_h \} = \emptyset \;\Longrigh... ...; (i_1,\ldots,i_k)\circ(j_1,\ldots,j_h) =(j_1,\ldots,j_h)\circ(i_1,\ldots,i_k)$$

Dans une décomposition en orbites, oubliez les singletons et ne conservez que les orbites de longueur au moins 2, que vous transformez en cycles : si $k_j\geqslant2$, remplacez $[i_j,\ldots,s^{k_j-1}(i_j)]$ par $(i_j,\ldots,s^{k_j-1}(i_j))$. Enfin, remplacez les virgules dans l'énumération des orbites, par le signe de composition : votre permutation $s$ est une composée de cycles.

$$\begin{array}{rcl} s&=&\left(\begin{array}{cccccccccccc} 1 &... ... & 5 & 12& 7& 10& 9 & 6 & 11 & 8 \end{array}\right) \end{array}$$

Les cycles de longueur $2$ jouent un rôle particulier. On les appelle transpositions. Leur signature vaut $-1$. Afin de faciliter la lecture, pour $i\neq j\in\{1,\ldots,n\}$ nous noterons $\tau_{i,j}=(i,j)$ la transposition de $i$ et $j$ :

$$\tau_{i,j}(i)=j\;,\quad \tau_{i,j}(j)=i\;,\quad \tau_{i,j}(k)=k\;,\quad\forall k\neq i,j\;.$$

Proposition 2   Soit $s$ une permutation et

$$[1,\ldots,s^{k_1-1}(1)],\ldots,[i_h,\ldots,s^{k_h-1}(i_h)]$$

sa décomposition en orbites. Alors $s$ est la composée de $(k_1-1)+\cdots+(k_h-1)$ transpositions.

Remarquez que le nombre de transpositions dans cette décomposition est exactement l'exposant de $(-1)$ dans la définition de la signature. Démonstration : Nous avons vu (proposition 1) que toute permutation s'écrit comme une composée de cycles. Il nous suffit de vérifier qu'un cycle de longueur $k$ est composée de $k-1$ transpositions. Voici une manière de décomposer le cycle $(i_1,\ldots,i_k)$ :

$$(i_1,\ldots, i_k) = \tau_{i_1,i_k}\circ\tau_{i_1,i_{k-1}}\circ\cdots\circ\tau_{i_1,i_2}$$

(vérifiez-le, par récurrence sur $k$).$\square$ Toute permutation s'écrit donc comme un produit (au sens de la composition des applications) de transpositions. Une telle écriture n'a rien d'unique : l'ordre de deux cycles disjoints peut être changé, on peut toujours insérer deux fois la même permutation dans le produit sans changer le résultat, etc. Le miracle est que si deux produits de transpositions donnent la même permutation, alors les nombres de permutations dans ces deux produits ont la même parité : c'est une conséquence du théorème 1. Le résultat suivant est l'étape clé dans sa démonstration.

Lemme 1   Soit $s$ une permutation et $\tau$ une transposition. Alors :

$$\varepsilon (\tau\circ s) = -\varepsilon (s)\;.$$

Démonstration : L'idée de la démonstration est de montrer que la composée par une transposition agit sur la décomposition en orbites, soit en cassant une orbite en deux, soit en regroupant deux orbites. Dans les deux cas l'exposant de la signature est soit augmenté, soit diminué de $1$, et la signature est changée en son opposée. Considérons la décomposition en orbites de $s$. Supposons que $\tau$ transpose les deux éléments distincts $i$ et $j$ et examinons la décomposition en orbites de $\tau\circ s$. De deux choses l'une : soit $i$ et $j$ appartiennent à la même orbite de $s$, soit $i$ et $j$ appartiennent à deux orbites distinctes.

$\bullet$

Si $i$ et $j$ appartiennent à la même orbite de $s$. Quitte à réordonner les éléments, nous pouvons supposer sans perte de généralité que l'orbite est $[1,\ldots,k]$, et que les deux éléments à transposer sont $1$ et $j$ avec $1<j\leqslant k$. Pour la permutation $\tau\circ s$, l'image d'un entier $h$ est :

$\star$

$s(h)$ si $h$ est différent de $j-1$ et $k$,

$\star$

$1$ si $h=j-1$,

$\star$

$j$ si $h=k$.

L'orbite $[1,\ldots,k]$ est cassée en $[1,\ldots,j-1]$ et $[j,\ldots,k]$. Le terme $k-1$ dans l'exposant de la signature est remplacé par $(j-2)+(k-j)$. L'exposant de la signature est diminué de $1$, et celle-ci est changée en son opposée.

$\bullet$

Si $i$ et $j$ appartiennent à deux orbites distinctes de $s$. Quitte à réordonner les éléments, nous pouvons supposer sans perte de généralité que les deux orbites sont $[1,\ldots,j-1]$ et $[j,\ldots,k]$, avec $1< j \leqslant k\leqslant n$ et que les deux éléments à transposer sont $1$ et $j$. Pour la permutation $\tau\circ s$, l'image d'un entier $h$ est :

$\star$

$s(h)$ si $h$ est différent de $j-1$ et $k$

$\star$

$j$ si $h=j-1$

$\star$

$1$ si $h=k$

Les deux orbites $[1,\ldots,j-1]$ et $[j,\ldots,k]$ sont regroupées en une seule : $[1,\dots,k]$. Les deux termes $j-2$ et $k-j$ dans l'exposant de la signature sont remplacés par le terme $k-1$. L'exposant de la signature est augmenté de $1$, et celle-ci est encore changée en son opposée.

$\square$ Nous avons maintenant tous les outils pour démontrer le théorème 1. Démonstration : Nous commençons par démontrer que la signature est un homomorphisme de groupes, de $({\cal S}_n,\circ)$ dans $(\{-1,1\},\times)$ :

$$\forall s,s'\in{\cal S}_n\;,\quad \varepsilon (s\circ s') = \varepsilon (s) \times\varepsilon (s')\;.$$

Soient $s$ et $s'$ deux transpositions quelconques. D'après la proposition 2, $s$ est le produit de $(k_1-1)+\cdots+(k_h-1)$ transpositions, où $k_1,\ldots,k_h$ sont les longueurs des orbites de $s$. Or d'après le lemme 1, la composée d'une transposition par une permutation quelconque mutiplie sa signature par $(-1)$. La composée de $s'$ par $(k_1-1)+\cdots+(k_h-1)$ transpositions successives multiplie la signature par $(-1)^{(k_1-1)+\cdots+(k_h-1)}=\varepsilon (s)$, d'où le résultat.

Pour terminer la démonstration du théorème 1, nous devons démontrer l'unicité. Soit $s$ une permutation quelconque : multiplions la transposition $\tau_{1,2}$ à droite par $s^{-1}$ et à gauche par $s$ : on obtient la transposition $\tau_{s(1),s(2)}$. N'importe quelle transposition se déduit donc de $\tau_{1,2}$ par une opération de ce type (on dit que les transpositions sont toutes conjuguées). Considérons maintenant un homomorphisme de groupe $\varphi$ de $({\cal S}_n,\circ)$ dans $(\{-1,1\},\times)$. Comme $\varphi$ est un homomorphisme de groupes,

$$\varphi(\tau_{s(1),s(2)})=\varphi(s\circ\tau_{1,2}\circ s^{-1})= \varphi(s)\varphi(\tau_{1,2})(\varphi(s))^{-1} =\varphi(\tau_{1,2})\;.$$

Toutes les transpositions, puisqu'elles sont conjuguées, doivent avoir la même image par $\varphi$. Supposons que cette image commune soit $1$. Dans la mesure où toute permutation s'écrit commme un produit de transpositions (proposition 2), on obtient $\phi(s)=1$ pour toute permutation $s$. Dans ce cas, l'homomorphisme $\phi$ est constant et donc non surjectif. Si $\varphi$ est supposé surjectif, alors nécessairement l'image de toute transposition doit valoir $-1$. Donc $\varphi$ coïncide avec $\varepsilon$ sur toutes les transpositions. Mais puisque toute permutation est produit de transpositions et que $\varphi$ et $\varepsilon$ sont tous les deux des homorphismes de groupes,

$$\forall s\in {\cal S}_n\;,\quad \varphi(s)=\varepsilon (s)\;.$$

$\square$