Groupe (mathématiques)/Groupes symétriques finis/Transpositions

Une page de Wikiversité.

< Groupe (mathématiques) | Groupes symétriques finis

**Transpositions**
Leçon : Groupes symétriques finis

Chapitre 4
Chap. préc. :	Cycles
Chap. suiv. :	Groupe alterné

En raison de limitations techniques, la typographie souhaitable du titre, « Groupes symétriques finis : Transpositions
Groupe (mathématiques)/Groupes symétriques finis/Transpositions », n'a pu être restituée correctement ci-dessus.

Définition

Une permutation d'un ensemble E est dite transposition si c'est un cycle de longueur 2. Autrement dit, une permutation $\ \tau$ de E est une transposition si et seulement s'il existe deux éléments distincts a, b de E tels que $\ \tau(a) = b, \tau(b) = a$ et que $\ \tau$ laisse fixes tous les autres éléments de E.

La transposition $\ (a \ b)$ est donc l'unique transposition $\in S_{E}$ qui échange a et b.

Lemme

Tout cycle de longueur r est le produit de r - 1 transpositions.

Démonstration. On vérifie facilement que le cycle $(a_{1} \ldots a_{r})$ est égal à

$(a_{1} \ a_{r}) (a_{1} \ a_{r-1}) \ldots (a_{1} \ a_{2})$ .

Théorème

Toute permutation d'un ensemble fini est un produit de transpositions.

Démonstration. Nous avons vu qu'une telle permutation est un produit de cycles et nous venons de voir qu'un cycle est un produit de transpositions.
Remarque. Voici une démonstration qui n'utilise pas la décomposition en cycles. Soit $\ \sigma$ une permutation d'un ensemble fini E; nous allons prouver que $\ \sigma$ est décomposable en transpositions, en raisonnant par récurrence sur le cardinal du support de $\ \sigma$ . Si ce cardinal est nul, $\ \sigma$ est la permutation identique et est donc le produit de la famille vide de transpositions. Sinon, le support de $\ \sigma$ n'est pas vide. Choisissons un élément $\ a$ de ce support et posons $\ b = \sigma(a)$ . Comme déjà noté, $\ b$ appartient aussi au support de $\ \sigma$ . Tout point fixe de $\ \sigma$ est distinct de $\ a$ et de $\ b$ , donc est point fixe de $\ (a \ b) \circ \sigma$ ; de plus, il est clair que $\ a$ est également point fixe de $\ (a \ b) \circ \sigma$ . Donc $\ (a \ b) \circ \sigma$ a strictement plus de points fixes que $\ \sigma$ , autrement dit, le support de $\ (a \ b) \circ \sigma$ a strictement moins d'éléments que celui de $\ \sigma$ . Par hypothèse de récurrence, $\ (a \ b) \circ \sigma$ est décomposable en produit de permutations, donc $\ \sigma$ , qui peut s'écrire $\ (a \ b) \circ ((a \ b) \circ \sigma)$ , l'est aussi. (On aurait aussi pu raisonner par récurrence sur le cardinal de E.)

Notons maintenant que la multiplication dans Z induit sur la partie $\ \{1, -1\}$ de Z une loi de composition interne qui en fait un groupe cyclique d'ordre 2 dont -1 est générateur; pour tout entier rationnel u, la condition $\ (-1)^{u} = 1$ équivaut à ce que u soit pair; pour tous entiers rationnels u et v, la condition $\ (-1)^{u} = (-1)^{v}$ équivaut à ce que u et v aient la même parité (c'est-à-dire soient ou bien tous deux pairs ou bien tous deux impairs).

Théorème

Soit E un ensemble fini. Il existe un et un seul homomorphisme du groupe $S E$ dans le groupe $\ \{1, -1\}$ qui applique toute transposition sur -1. Dans différentes décompositions d'une même permutation en produit de transpositions, le nombre de facteurs a toujours la même parité.

Supposons d'abord $\ E = \{1, 2, \ldots , n \}$ pour un certain nombre naturel n. Pour toute permutation $\ \sigma$ de $\{1, 2, \ldots , n \}$ , nous dirons qu'une paire d'éléments de $\{1, 2, \ldots , n \}$ est une inversion de $\ \sigma$ si, i désignant le plus petit élément de cette paire et j le plus grand, $\ \sigma_{i} > \sigma_{j}$ . Soient $\ \sigma$ et $\ \tau$ deux permutations de $\{1, 2, \ldots , n \}$ et $\ \{i, j\}$ une paire d'éléments de $\{1, 2, \ldots , n \}$ . Il est clair que $\ \{i, j\}$ est une inversion de $\ \sigma \circ \tau$ si et seulement si une des deux conditions suivantes est satisfaite :

1° $\ \{i, j\}$ est une inversion de $\ \tau$ et $\ \{\tau(i, \tau(j))\}$ n'est pas une inversion de $\ \sigma$ ;

2° $\ \{i, j\}$ n'est pas une inversion de $\ \tau$ et $\ \{\tau(i, \tau(j))\}$ est une inversion de $\ \sigma$ .

Nous allons définir un homomorphisme de $\ S_{E}$ dans le groupe $\ \{1, -1\}$ .
Pour toute permutation $\ \sigma$ de E et toute paire P d'éléments de E, définissons $\ \nu_{\sigma}(P)$ comme égal à - 1 si P est une inversion de $\ \sigma$ et à 1 dans le cas contraire. D'après ce qui précède, nous avons toujours

$\ \nu_{\sigma \circ \tau}(P) = \nu_{\sigma} (\tau(P)) \nu_{\tau} (P)$ ,

où $\ \tau(P)$ désigne la paire formée par les images par $\ \tau$ des deux éléments de P.
En prenant le produit sur l'ensemble $\mathcal{P}$ des paires d'éléments de P, nous trouvons

$\prod_{P \in \mathcal{P}}\nu_{\sigma \circ \tau}(P) = \prod_{P \in \mathcal{P}}\nu_{\sigma} (\tau(P)) \prod_{P \in \mathcal{P}} \nu_{\tau} (P)$ .

L'application $P \mapsto \tau(P)$ est une permutation de l'index $\mathcal{P}$ , donc le produit $\prod_{P \in \mathcal{P}}\nu_{\sigma} (\tau(P))$ peut s'écrire $\prod_{P \in \mathcal{P}}\nu_{\sigma} (P)$ , d'où

$\prod_{P \in \mathcal{P}}\nu_{\sigma \circ \tau}(P) = \prod_{P \in \mathcal{P}}\nu_{\sigma} (P) \prod_{P \in \mathcal{P}} \nu_{\tau} (P)$ .

Ceci montre que l'application

$\sigma \mapsto \prod_{P \in \mathcal{P}}\nu_{\sigma} (P)$

est un homomorphisme de $\ S_{n}$ dans $\ \{1, -1\}$ .
Il est clair que cet homomorphisme peut s'écrire

$\sigma \mapsto (-1)^{\mathrm{inv}(\sigma)}$ ,

où $\ \mathrm{inv}(\sigma)$ désigne le nombre d'inversions de $\ \sigma$ . Montrons maintenant que cet homomorphisme applique toute transposition sur -1. Il s'agit de prouver que le nombre d'inversions d'une transposition est toujours impair. Soit (a b) une transposition, avec a < b. Les inversions de cette permutation sont la paire {a, b}, les paires $\ \{a, i\}$ avec $\ a < i < b$ , et les paires $\ \{i, b\}$ , avec $\ a < i < b$ . Le nombre des inversions de (a b) est donc $\ 1 + 2(b-1-a)$ , qui est bien impair.
Nous avons donc prouvé qu'il existe un homomorphisme de $\ S_{n}$ dans $\ \{1, -1\}$ qui applique toute transposition sur -1. Un tel homomorphisme est unique, puisque les transpositions engendrent $\ S_{n}$ . Pour toute permutation $\ \sigma \in S_{n}$ , désignons par $\ \epsilon (\sigma)$ l'image de $\ \sigma$ par cet homomorphisme.
Passons maintenant au cas général d'un ensemble fini E. Soit n le cardinal de E. Choisissons une bijection f de E sur $\{1, 2, \ldots , n \}$ . Nous avons vu que l'application

$\Gamma_{f} : S_{E} \rightarrow S_{n} : \sigma \mapsto f \circ \sigma \circ f^{-1}$

est un isomorphisme de groupes qui applique tout cycle sur un cycle de même longueur et, en particulier, applique donc toute transposition sur une transposition. Le composé $\epsilon \circ \Gamma_{f}$ est donc un homomorphisme de $\ S_{E}$ dans $\ \{1, -1\}$ qui applique toute transposition sur - 1. Ici encore, puisque les transpositions engendrent $\ S_{E}$ , un tel homomorphisme est unique. Nous désignerons encore par $\ \epsilon (\sigma)$ l'image de $\ \sigma$ par cet homomorphisme.
Si une permutation $\ \sigma$ de E peut s'écrire

$\sigma = \tau_{1} \circ \ldots \circ \tau_{r1}$

et

$\sigma = \varphi_{1} \circ \ldots \circ \varphi_{s}$ ,

les $\ \tau_{i}$ et les $\ \varphi_{j}$ étant des transpositions, le passage aux valeurs par $\ \epsilon$ donne $\ (-1)^{r} = (-1)^{s}$ , donc r et s ont même parité.

Remarque. L'essentiel de la démonstration revient à dire que si $\ \sigma$ et $\ \tau$ sont des permutations de $\{1, 2, \ldots , n\}$ , le nombre d'inversions de $\sigma \circ \tau$ est congru modulo 2 à la somme du nombre d'inversion de $\ \sigma$ et du nombre d'inversion de $\ \tau$ . On trouvera dans les exercices une relation plus explicite entre ces trois nombres d'inversions.

Définitions

Pour toute permutation $\ \sigma$ d'un ensemble fini E, on appelle signature de $\ \sigma$ et on note $\ \epsilon(\sigma)$ la valeur de $\ \sigma$ par l'unique homomorphisme de $\ S_{E}$ dans $\ \{1, -1\}$ qui applique toutes les transpositions sur - 1. Une permutation de E est dite paire si sa signature est 1 et impaire dans le cas contraire.

Un cycle est une permutation paire si et seulement si sa longueur est impaire; en effet, nous avons vu qu'un cycle de longueur r est le produit de r - 1 transpositions.
Si $σ$ est un élément d'ordre impair du groupe $\ S_{E}$ , c'est une permutation paire; en effet, puisque $\ \epsilon$ définit un homomorphisme de $\ S_{E}$ dans $\ \{1, -1\}$ , l'ordre de $\ \epsilon(\sigma)$ divise celui de $σ$ et est donc impair; or le seul élément d'ordre impair dans $\ \{1, -1\}$ est 1, donc $\ \epsilon(\sigma) = 1$ , donc $σ$ est une permutation paire.
La converse n'est pas vraie : un élément d'ordre pair du groupe $\ S_{E}$ n'est pas forcément une permutation impaire. Par exemple, si E comprend aux moins quatre éléments différents a, b, c, d, la permutation $(a\ b)\ (c\ d)$ de E a pour ordre le ppcm des ordres de $(a\ b)$ et de $(c\ d)$ , autrement dit est d'ordre 2 et donc pair, et pourtant c'est une permutation paire.

Ce qui précède montre que pour calculer $\ \epsilon(\sigma)$ , il n'est pas nécessaire de faire un long relevé d'inversions. Tout d'abord, si on connaît une décomposition de $\ \sigma$ en produit de transpositions, $\ \epsilon(\sigma)$ est égal à 1 ou à - 1 selon que le nombre de facteurs est pair ou impair.
Il suffit même de trouver la décomposition de $\ \sigma$ en produit de cycles à supports disjoints : la signature de $\ \sigma$ est le produit des signatures de ces cycles, et, d'après un résultat précédent, la signature d'un cycle $\ \gamma$ est $\ (-1)^{l(\gamma) - 1}$ , où $\ l(\gamma)$ désigne la longueur de $\ \gamma$ . Il est clair qu'on peut même se contenter de connaître les cardinaux des $\ <\sigma>$ -orbites. Enfin, si $\ \Omega^{\prime}$ désigne l'ensemble des $\ <\sigma>$ -orbites non ponctuelles,

$\sum_{\omega \in \Omega^{\prime}}(\mathrm{Card}(\omega)-1)$ = $\sum_{\omega \in \Omega}(\mathrm{Card}(\omega)-1)$ ,

où $\ \Omega$ désigne l'ensemble de toutes les orbites, y compris les orbites ponctuelles; le second membre est égal à n - t, où n = Card(E) et où t est le nombre des $\ <\sigma>$ -orbites, y compris les $\ <\sigma>$ -orbites ponctuelles. On a donc

$\ \epsilon(\sigma) = (-1)^{n-t}$ .

(Ceci fournit d'ailleurs une définition alternative de la signature d'une permutation.)

La notion de signature d'une permutation intervient en algèbre linéaire, dans l'étude des déterminants.

Groupe (mathématiques)/Groupes symétriques finis/Transpositions

Une page de Wikiversité.

Affichages

Outils personnels

Rechercher

Navigation

Contribuer

Imprimer / exporter

Boîte à outils