Algèbre

Le groupe symétrique Sₙ

Toutes les façons de réordonner n objets forment un groupe, le groupe symétrique Sₙ, avec n! éléments. Il est partout : dans le déterminant, qui est une somme sur Sₙ, dans la théorie de Galois, qui permute les racines, et dans chaque symétrie d'un objet, qui permute ses morceaux. Cinq planches pour composer des permutations, les découper en cycles, calculer leur signature, retrouver le déterminant et voir un groupe agir.

Vue d'ensemble : qu'est-ce qu'une permutation ?

Une permutation de {1, 2, …, n} est une bijection de cet ensemble dans lui-même : chaque élément est envoyé sur un élément, et chaque élément est atteint une fois exactement. On l'écrit souvent sur deux lignes, en mettant sous chaque nombre son image :

σ = ( 1 2 3 4 5 / 3 5 4 1 2 ) signifie σ(1) = 3, σ(2) = 5, σ(3) = 4, σ(4) = 1, σ(5) = 2.

Composer deux permutations donne une permutation, l'identité ne change rien, et chaque permutation se défait par sa réciproque : c'est un groupe, noté Sₙ. Il a n! = 1 × 2 × … × n éléments : 6 pour n = 3, 120 pour n = 5, déjà 3 628 800 pour n = 10.

Cinq jetons réordonnés par une permutation, toujours la même, appliquée encore et encore. Au bout de quelques coups, l'ordre de départ revient : c'est l'ordre de la permutation, lu sur ses cycles (planche 2).

Notion	Ce qu'elle dit	Où elle sert	Planche
composition	faire une permutation, puis une autre	structure de groupe, non commutative dès n = 3	1
cycles	découper une permutation en boucles disjointes	ordre, classes de conjugaison, mélanges de cartes	2
signature	+1 ou −1 selon la parité du nombre d'échanges	déterminant, groupe alterné Aₙ, taquin	3
déterminant	somme sur les n! permutations, signée	volumes, systèmes linéaires, valeurs propres	4
action de groupe	un groupe qui permute les éléments d'un ensemble	symétries, dénombrement, théorie de Galois	5

Composer des permutations : l'ordre compte

Faire τ puis σ, est-ce la même chose que faire σ puis τ ?

On note σ ∘ τ la permutation « d'abord τ, puis σ » : (σ ∘ τ)(i) = σ(τ(i)). Pour modifier σ ou τ, cliquez sur deux cases de la ligne du bas : leurs images s'échangent, et la permutation reste une bijection. Les jetons descendent ensuite à travers les deux étages.

τ (premier étage)

σ (second étage)

σ ∘ τ

τ ∘ σ

σ ∘ τ = τ ∘ σ ?

σ⁻¹ et contrôle σ ∘ σ⁻¹ = id

Couples (σ, τ) qui commutent dans Sₙ · n!·p(n)

Trois rangées de places. Les jetons partent de la rangée du haut, passent par la première permutation, puis par la seconde. Chaque jeton garde sa couleur et son numéro.

Non commutatif. Dans S₃ déjà, σ ∘ τ et τ ∘ σ diffèrent en général. Combien de couples commutent ? La page les compte un par un : 4 sur 4 pour n = 2, 18 sur 36, 120 sur 576, 840 sur 14 400, 7 920 sur 518 400 pour n = 6. C'est exactement n! fois p(n), le nombre de façons d'écrire n comme somme d'entiers. Ce n'est pas un hasard : p(n) est le nombre de types de cycles (planche 2).

Les cycles : chaque permutation est une réunion de boucles

Si l'on suit les flèches i → σ(i) → σ(σ(i)) → …, où va-t-on ?

En partant de 1 et en suivant les flèches, on revient forcément à 1 : on a parcouru un cycle. On repart d'un élément non encore visité, et ainsi de suite. Toute permutation se découpe ainsi, de façon unique, en cycles disjoints : σ = (1 3 4)(2 5) signifie 1 → 3 → 4 → 1 et 2 → 5 → 2. La liste des longueurs, rangée par ordre décroissant, s'appelle le type de σ, et l'ordre de σ (le nombre de fois qu'il faut l'appliquer pour revenir au départ) est le PPCM de ces longueurs.

Les n éléments sur un cercle et les flèches i → σ(i). Chaque cycle reçoit sa couleur quand on le parcourt ; les points fixes sont des boucles sur place.

σ sur deux lignes

Décomposition en cycles

Type

Ordre : PPCM des longueurs · mesuré

Permutations de ce type

Nombre de permutations de chaque type dans Sₘ (barres, comptées une à une) et formule m! / Π k^mₖ mₖ! (points verts).

Énumération = formule ?

Plus grand ordre dans Sₘ (Landau)

Combien de mélanges parfaits pour revenir au départ ?

Un mélange parfait coupe le paquet en deux moitiés égales et intercale les cartes une à une. Dans le mélange « extérieur », la carte du dessus reste au-dessus ; dans le mélange « intérieur », elle passe en deuxième position. C'est une permutation fixe des places, et l'ordre de cette permutation donne le nombre de mélanges qui ramènent le paquet à son état initial.

cartes mélange

Le paquet, une couleur par carte (dégradé de la première à la dernière). Le paquet est rangé quand le dégradé redevient régulier.

Mélanges effectués

Type de la permutation du mélange

Ordre par les cycles · par simulation

Le tour des magiciens. Avec 52 cartes, huit mélanges extérieurs parfaits remettent le jeu dans l'ordre exact. Les cycles de cette permutation ont des longueurs 1, 2 et 8, dont le PPCM vaut 8. Le mélange intérieur, lui, forme un seul grand cycle de longueur 52 : il en faut 52. Plus haut, le plus grand ordre possible dans Sₘ (fonction de Landau) se lit aussi sur les types : 6 dans S₅ avec le type 3 + 2, 15 dans S₈ avec 5 + 3.

La signature : pair ou impair ?

On peut toujours ranger une permutation par des échanges de deux éléments. Le nombre d'échanges change selon la méthode, mais pas sa parité. Pourquoi ?

Une inversion de σ est un couple i < j tel que σ(i) > σ(j). Sur le dessin, chaque fil relie i (en haut) à σ(i) (en bas), et chaque croisement de deux fils est une inversion. La signature ε(σ) vaut +1 si le nombre d'inversions est pair, −1 s'il est impair. Le tri à bulles échange deux voisins mal rangés : chaque échange supprime exactement un croisement, donc il faut autant d'échanges voisins que d'inversions.

Diagramme de fils : i en haut est relié à σ(i) en bas. Les points rouges marquent les croisements, c'est-à-dire les inversions. Pendant le tri, les fils se démêlent un croisement à la fois.

Inversions (croisements)

Échanges voisins faits par le tri

ε par les inversions · par les cycles · par le produit

Décomposition en transpositions (par les cycles)

Contrôle exhaustif

Trois définitions indépendantes de la signature se recoupent :

par les inversions : ε(σ) = (−1)^{nombre d'inversions} ;
par les cycles : un cycle de longueur k s'écrit avec k − 1 échanges, donc ε(σ) = (−1)^{n − nombre de cycles} ;
par un produit : ε(σ) = Π_i<j (σ(j) − σ(i)) / (j − i). Le numérateur contient les mêmes différences que le dénominateur, au signe près, et chaque inversion apporte un signe moins.

Pourquoi c'est capital. La signature est un morphisme : ε(σ ∘ τ) = ε(σ) × ε(τ), contrôlé ici sur les 14 400 couples de S₅. Son noyau, les permutations paires, est le groupe alterné Aₙ, avec n!/2 éléments. C'est le signe qui entre dans chaque terme du déterminant (planche 4), et c'est Aₙ, simple dès n = 5, qui bloque toute formule par radicaux en théorie de Galois.

Le déterminant : une somme sur Sₙ

D'où vient la formule du déterminant, et pourquoi a-t-elle des signes ?

La formule de Leibniz définit le déterminant d'une matrice A de taille n comme une somme de n! termes, un par permutation :

det A = Σ_{σ ∈ Sₙ} ε(σ) · a_1,σ(1) · a_2,σ(2) · … · a_n,σ(n)

Chaque terme choisit une case par ligne et par colonne, comme n tours d'échecs qui ne se menacent pas, et la permutation dit dans quelle colonne tombe la case de chaque ligne. Échanger deux lignes de A revient à composer chaque σ par une transposition, ce qui change tous les signes : le déterminant change de signe. Deux lignes égales donnent donc un déterminant nul.

taille n matrice

La matrice, avec en couleur les n cases du terme courant (bleu si ε = +1, rouge si ε = −1). En dessous, la somme partielle avance terme à terme.

Terme courant

Permutation · signature

Valeur du terme

Somme partielle

det par Leibniz (n! termes)

det par élimination de Gauss (Bareiss)

Termes positifs · négatifs

Coût comparé (multiplications)

Belle formule, mauvais algorithme. Pour n = 3, les six termes sont ceux de la règle de Sarrus, trois positifs et trois négatifs. Mais n! grandit trop vite. Pour n = 20, la formule de Leibniz demande 19 × 20! ≈ 4,6·10¹⁹ multiplications, soit environ 1 500 ans à un milliard d'opérations par seconde. L'élimination de Gauss en demande environ n³/3, soit 2 700 : elle donne le même nombre, et c'est elle qu'on utilise en pratique.

Signature : quand un groupe agit

Un groupe ne fait pas que se multiplier : il agit, il déplace les éléments d'un ensemble. Que peut-on en tirer ?

Un groupe G agit sur un ensemble X quand chaque élément g de G permute les éléments de X, de façon compatible avec la composition. L'orbite de x est l'ensemble des endroits où G peut l'envoyer, et son stabilisateur l'ensemble des g qui le laissent en place. Deux théorèmes simples gouvernent tout :

orbite-stabilisateur : |orbite de x| × |stabilisateur de x| = |G| ;
formule de Burnside : le nombre d'orbites est la moyenne, sur les g de G, du nombre de points fixés par g.

Combien de colliers différents peut-on faire avec n perles de k couleurs ? Deux colliers sont les mêmes si l'on passe de l'un à l'autre en tournant (groupe cyclique Cₙ, n éléments), ou en tournant et en retournant (groupe diédral Dₙ, 2n éléments). On compte les orbites de deux façons : en rangeant un à un les kⁿ coloriages, et par la formule de Burnside.

perles n couleurs k groupe

Un représentant par orbite (cliquez sur un collier). Le nombre sous chaque collier est la taille de son orbite.

Coloriages kⁿ · |G|

Orbites comptées une à une

Formule de Burnside

Collier choisi : orbite × stabilisateur = |G|

Lire la formule. Une rotation de r crans découpe les n perles en pgcd(n, r) cycles, et un coloriage est fixé par elle exactement quand chaque cycle est d'une seule couleur : il y en a k^{pgcd(n, r)}. Burnside fait la moyenne de ces nombres. Avec 6 perles et 2 couleurs : 14 colliers à rotation près, 13 si l'on autorise aussi le retournement. Ce sont encore les cycles de la planche 2 qui font le calcul.

Le cube a 24 rotations qui le ramènent sur lui-même : l'identité, 9 rotations autour des axes des faces (90°, 180°, 270°), 8 autour des grandes diagonales (120°, 240°) et 6 autour des axes passant par les milieux d'arêtes opposées (180°). Chacune permute les quatre grandes diagonales du cube. On obtient ainsi une action du groupe des rotations sur un ensemble à 4 éléments, donc une application vers S₄. La page vérifie qu'elle est bijective.

rotation

Le cube et ses quatre grandes diagonales colorées. Les numéros 1 à 4 restent fixes dans l'espace ; après la rotation, on lit quelle diagonale occupe chaque place.

Permutation des diagonales

Type de rotation · type de cycle

24 rotations → permutations distinctes

Produits de deux rotations (stabilité)

Correspondance des types

Cubes à faces coloriées (k couleurs) : Burnside · comptage

Le groupe des rotations du cube est S₄. Les 24 rotations donnent 24 permutations différentes des diagonales, donc toutes celles de S₄. Les 90° deviennent des 4-cycles (6), les 180° autour des faces des doubles transpositions (3), les 120° des 3-cycles (8), et les demi-tours autour des arêtes des transpositions (6). C'est ainsi qu'agit le groupe de Galois : il permute les racines d'une équation comme les rotations permutent les diagonales. Les orbites sont alors les ensembles de racines d'un même facteur irréductible.

Une brève histoire

1693Leibniz, dans une lettre à L'Hôpital, écrit des déterminants pour éliminer les inconnues d'un système.

1750Cramer publie sa règle de résolution des systèmes, avec les signes fixés par le nombre de « dérangements ».

1770–1771Lagrange et Vandermonde étudient les permutations des racines d'une équation.

1815Cauchy fonde la théorie des permutations (« substitutions ») et du déterminant par la signature ; il introduit en 1844 la notation en cycles.

1830–1832Galois associe à chaque équation son groupe de permutations des racines.

1854–1878Cayley montre que tout groupe fini est un groupe de permutations.

1887–1897Frobenius, puis Burnside, énoncent la formule de comptage des orbites, déjà connue de Cauchy.

1937Pólya en tire une méthode générale de dénombrement des objets à symétrie près (molécules, colliers, graphes).

En résumé

Composer et découper

Sₙ a n! éléments et n'est pas commutatif. Chaque permutation se découpe en cycles disjoints. Le type de cycles donne l'ordre (PPCM) et la classe de conjugaison.

Un signe bien défini

La parité du nombre d'échanges ne dépend pas de la méthode. La signature est un morphisme vers {±1}, et c'est le signe de chaque terme du déterminant.

Agir pour compter

Les groupes agissent sur des ensembles. Orbite-stabilisateur et Burnside comptent les objets à symétrie près, et le groupe de Galois agit de la même façon sur les racines.

Pour aller plus loin

Théorème de Cayley. Tout groupe G agit sur lui-même par translation (g agit par x ↦ gx) : il s'identifie ainsi à un sous-groupe de S_|G|. Les groupes symétriques contiennent donc tous les groupes finis.

Classes de conjugaison. Deux permutations sont conjuguées (τ = ρσρ⁻¹) exactement quand elles ont le même type de cycles. Sₙ a donc p(n) classes, ce qui explique le comptage n!·p(n) de la planche 1.

Générateurs. Sₙ est engendré par les transpositions voisines (i i+1), comme le montre le tri à bulles, ou même par seulement deux éléments : (1 2) et (1 2 … n).

Liens. Le déterminant (VIII.24), la théorie de Galois (groupe de l'équation, résolubilité), le dénombrement (dérangements, page de combinatoire) et le taquin (page sur l'algèbre et les ensembles) reposent tous sur Sₙ.