Chapitre 2

Groupes de permutations

Ce court chapitre a pour but de rappeler les notions de base sur les groupes de
permutations et, en particulier, d’établir les propriétés de la signature (la signature
d’une permutation est un signe ±1 décrivant sa parité).

1. Dénitions et premières propriétés

1.1. Groupe des permutations d'un ensemble

1.1.1. Définition. Soit A un ensemble. On note SA l’ensemble des applications

bijectives σ : A → A (qu’on appelle aussi permutations de A). Pour la composition
des applications ◦, on a une structure de groupe (SA , ◦), non commutatif si
card A > 3.

L’élément neutre du groupe est IdA et le symétrique d’un élément σ ∈ SA est

la bijection inverse σ −1 (l’associativité étant toujours vraie pour la composition
des applications). On s’intéressera ici surtout au cas où A est un ensemble fini,
noté A = {a1 , . . . , an }.

1.1.2. Notation. Une permutation σ ∈ SA pourra être définie en donnant la

liste des images successives σ(ai ) des éléments ai ∈ A. On notera ainsi
 
a1 a2 ... an
σ=
b1 b2 ... bn

la permutation σ telle que σ(ai ) = bi .

1.1.3. Définition. Le support d’une paermutation σ ∈ SA est par définition la

partie
Supp σ = {x ∈ A / σ(x) 6= x}.
C’est donc le complémentaire dans A de l’ensemble des éléments invariants, soit

Inv σ = {x ∈ A / σ(x) = x}.

1.1.4. Définition. On désigne par Sn l’ensemble des permutations de {1, 2, ..., n}.
On a card Sn = n!.
2 J.-P. Demailly, Arithmétique et algèbre linéaire approfondie

En effet, une telle permutation est obtenue en choisissant σ(1) dans {1, . . . , n}
(n choix possibles), puis σ(2) dans {1, . . . , n} r {σ(1)} (n − 1 choix possibles), puis
σ(3) dans {1, . . . , n} r {σ(1), σ(2)} (n − 2 choix possibles), etc, ce qui donne

card Sn = n × (n − 1) × (n − 2) × · · · × 2 × 1 = n!

(il ne reste plus qu’un choix pour le dernier élément σ(n), les autres ayant déjà
été choisis).

1.2. Transpositions et y les

Les exemples fondamentaux de permutations sont les transpositions et les cycles :

1.2.1. Transpositions. Si a, b sont des éléments distincts de A, on note τa,b ∈ SA
la permutation définie par

τa,b (a) = b, τa,b (b) = a, τa,b (x) = x, si x ∈ A r {a, b}.

La permutation τa,b correspond donc à faire l’échange des éléments a, b sans

“toucher” aux autres éléments, par suite Supp τa,b = {a, b}. Il est clair que τa,b
2
est une involution, c’est-à-dire que τa,b = IdA (ou encore que c’est un élément
d’ordre 2 du groupe SA ).
1.2.2. Rappel. Dans un groupe (G, ∗), un élément x est dit d’ordre fini s’il existe
un entier k ∈ N∗ tel que xk = x ∗ x ∗ · · · ∗ x = 1G , et on appelle ordre de x, noté
ordre(x), le plus petit entier k ∈ N∗ tel que xk = 1G .

1.2.3. Cycle de longueur ℓ. Soit a1 , a2 , . . . , aℓ des éléments 2 à 2 distincts de

l’ensemble A. on considère la permutation c définie par
 
a1 a2 . . . aℓ−1 aℓ b1 b2 . . . bn−ℓ
c=
a2 a3 . . . aℓ a1 b1 b2 . . . bn−ℓ

où A r {a1 , . . . , aℓ } = {b1 , . . . , bn−ℓ }, en d’autres termes c est telle que

c : a1 7→ a2 7→ a3 7→ · · · 7→ aℓ−2 7→ aℓ−1 7→ aℓ 7→ a1

et c(x) = x pour x ∈
/ {a1 , . . . , aℓ }. Un tel cycle est noté en abrégé

c = (a1 a2 . . . aℓ ).

Le support du cycle c est donc la partie Supp c = {a1 , . . . , aℓ }, et une transposition

τa,b n’est pas autre chose qu’un cycle (a b) de longueur 2. En général, il est facile
de voir que ck (ai ) = ak+i mod ℓ , c’est-à-dire
 
k a1 a2 . . . aℓ−k aℓ−k+1 . . . aℓ−1 aℓ b1 b2 . . . bn−ℓ
c =
ak+1 ak+2 ... aℓ a1 . . . ak−1 ak b1 b2 . . . bn−ℓ
 Chap. 2 : groupes de permutations 3

pour k 6 ℓ − 1 et cℓ = IdA , par conséquent ordre(c) = ℓ. Il est facile de voir que

l’on a pour tout i = 0, 1, . . . , ℓ − 1 l’égalité

c = (a1 a2 . . . aℓ ) = (ai+1 ai+2 . . . aℓ a1 a2 . . . ai ),

par exemple (1 2 3 4 5) = (4 5 1 2 3), c’est-à-dire que le cycle ne dépend pas de

son point de départ, si “l’ordre cyclique” des éléments est préservé. En revanche,
le cycle (1 2 3 4 5) n’est pas égal au cycle (1 3 2 4 5).

1.2.4. Exemple. Le groupe S3 est constitué des 6 éléments

S3 = {Id, c, c2 , τ1,2 , τ2,3 , τ1,3 } où c = (1 2 3), c2 = (1 3 2), c3 = Id .

On calcule aisément la table de Pythagore du groupe S3 :

v c2
u\ Id c τ1,2 τ2,3 τ1,3

Id Id c c2 τ1,2 τ2,3 τ2,3

c c c2 Id τ1,3 τ1,2 τ2,3

(u, v) 7→ u ◦ v c2 c2 Id c τ2,3 τ1,3 τ1,2

τ1,2 τ1,2 τ2,3 τ1,3 Id c c2

τ2,3 τ2,3 τ1,3 τ1,2 c2 Id c

τ1,3 τ1,3 τ1,2 τ2,3 c c2 Id

On voit en particulier que le groupe (S3 , ◦) est non commutatif, et donc Sn est
non commutatif pour n > 3 (mais S1 = {Id} et S2 = {Id, τ1,2 } sont commutatifs).

1.3. Dé omposition en y les à supports disjoints

Prenons d’abord l’exemple de la permutation σ ∈ S8 telle que

 
1 2 3 4 5 6 7 8
σ= .
6 1 7 8 5 2 3 4

On a Inv σ = {5} et Supp σ = {1, 2, 3, 4, 6, 7, 8}. Considérons les images des

éléments successifs du support :

1 7→ 6 7→ 2 7→ 1
3 7→ 7 7→ 3
4 7→ 8 7→ 4

Pour chaque ligne, on prend les images successives et on s’arrête lorsqu’on retombe
sur l’élément de départ. On considère ensuite à chaque ligne le premier élément du
4 J.-P. Demailly, Arithmétique et algèbre linéaire approfondie

support qui n’a pas encore été pris en compte. On voit alors que σ est la composée
d’un cycle de longueur 3 et de deux cycles de longueur 2 (transpositions) :

σ = (1 6 2) ◦ (3 7) ◦ (4 8),

avec l’élément 5 qui n’intervient pas (car invariant). L’ordre des composées importe
peu, car on a le résultat évident suivant.

1.3.1. Lemme. Si c et c′ sont des cycles dont les supports Supp c et Supp c′ sont
disjoints (Supp c ∩ Supp c′ = ∅), alors c′ ◦ c = c ◦ c′ .

Quel que soit l’ordre de composition, l’image σ(x) de la composée σ coïncide

en effet avec c(x) si x ∈ Supp c, avec c′ (x) si x ∈ Supp c′ , tandis que σ(x) = x si
x∈/ Supp c ∪ Supp c′ .

En considérant les itérés successifs σ k (x) des éléments du support d’une

permutation σ quelconque, on obtient de même le résultat général suivant.

1.3.2. Théorème. Toute permuation σ ∈ SA d’un ensemble fini A se décompose

en un produit commutatif de cycles, c’est-à-dire que

σ = c1 ◦ c2 ◦ · · · ◦ cp

avec des cycles cj dont les supports Supp cj sont 2 à 2 disjoints. Une telle
décomposition est unique à l’ordre près des cj et on a

Supp σ = Supp c1 ∪ . . . ∪ Supp cp .

Démonstration. Il faut d’abord voir que si on prend les itérés d’un élément
x0 ∈ Supp σ quelconque, soit

x0 , x1 = σ(x0 ), . . . , xi = σ(xi−1 ) = σ i (x0 ),

il y nécessairement un indice m ∈ [2, card A] minimal tel que xm ∈ {x0 , . . . , xm−1 }

(sinon on aurait card{x0 , . . . , xi−1 } > i pour tout i, ce qui contredit la finitude
de A). D’autre part, on a nécessairement xm = σ m (x0 ) = x0 , sinon on
“retomberait” sur xm = σ m (x0 ) = xi = σ i (x0 ) avec i > 0, et ceci impliquerait
xm−i = σ m−i (x0 ) = x0 , contredisant la minimalité de m. Enfin , si on prend
y0 ∈ Supp σ en dehors de “l’orbite” {x0 , . . . , xm−1 } de x0 , alors tous les itérés
yi = σ i (y0 ) sont également en dehors de cette orbite (vérification évidente :
σ i (y0 ) = σ j (x0 ) impliquerait y0 = σ j−i (x0 ) ou y0 = σ j+m−i (x0 ) suivant que
j > i ou j < i). Les orbites qui constituent les supports des cycles sont donc
disjointes.
 Chap. 2 : groupes de permutations 5

1.4. Ordre d'une permutation

Soit σ ∈ SA une permutation d’un ensemble fini A, et écrivons

σ = c1 ◦ c2 ◦ · · · ◦ cp

avec les cycles de longueurs respectives ℓ1 , ℓ2 , . . . , ℓp . Comme les cycles commutent,

on trouve pour tout k ∈ N∗

σ k = ck1 ◦ ck2 ◦ · · · ◦ ckp

(on remarquera que dans un groupe non commutatif (G, ·), on a en général
(xy)2 = xyxy, ce qui ne coïncide avec x2 y 2 = xxyy que si x et y commutent).
On a ckj = Id si et seulement si k est multiple de la longeur ℓj du cycle cj . Or,
pour x ∈ Supp cj , on a σ k (x) = ckj (x), donc on voit que σ k = Id si et seulement si
k est simultanément multiple de ℓ1 , ℓ2 , . . . , ℓp . Le plus petit entier k ∈ N∗ tel que
σ k = Id est donc le plus petit commun multiple des ℓj . On peut énoncer :
1.4.1. Théorème. Pour trouver l’ordre d’une permutation σ, on cherche une
décomposition en cycles, et alors l’ordre

ordre(σ) = ppcm(ℓ1 , ℓ2 , . . . , ℓp )

est le ppcm des longueurs des cycles c1 , c2 , . . . , cp à supports disjoints qui com-
posent σ.

On trouve ainsi par exemple

ordre((1 6 2) ◦ (3 7) ◦ (4 8)) = ppcm(3, 2, 2) = 6.

2. Signature d'une permutation

2.1. Nombre d'inversions et signature

On désigne par Pn l’ensembles des paires {i, j} (non ordonnées, i 6= j)

d’éléments de {1, 2, . . . , n}. On a
 
n n(n − 1)
card Pn = = .
2 2

Si σ ∈ Sn , alors σ induit une application σ

b : Pn → Pn définie par

b({i, j}) = {σ(i), σ(j)},

σ

et il est clair que c’est une bijection de Pn dans Pn , d’inverse σd

−1 . On dit que la

paire {i, j} est inversée par σ (resp. non inversée) si

σ(j) − σ(i) σ(j) − σ(i)

< 0, resp. > 0,
j−1 j−1
6 J.-P. Demailly, Arithmétique et algèbre linéaire approfondie

autrement dit, si σ(i), σ(j) sont en ordre inverse (ou non) de i, j.

2.1.1. Définition. Le nombre d’inversions d’une permutation σ ∈ Sn est, comme

son nom l’indique, le nombre de paires {i, j} inversées par σ :
n σ(j) − σ(i) o
N (σ) = card {i, j} ∈ Pn / <0 .
j−i

On a donc N (σ) ∈ {0, 1, . . . , n(n−1)

2 }. La signature ε(σ) de la permutation σ est
la valeur ±1 définie par
ε(σ) = (−1)N(σ) .

2.1.2. Examples.
(a) L’application identique σ = Id n’a pas d’inversions, par conséquent N (Id) = 0,
ε(Id) = +1.
(b) La transposition τa,b (avec disons a < b) s’écrit
 
1 2 ... a−1 a a+1 ... b−1 b b+1 ...n
τa,b =
1 2 ... a−1 b a+1 ... b−1 a b+1 ...n

donne lieu aux paires inversées {a, b} et

{a, i} 7→ {b, i}, a + 1 6 i 6 b − 1,

{i, b} 7→ {i, a}, a + 1 6 i 6 b − 1,

soit 2p + 1 paires inversées avec p = (b − 1) − (a + 1) + 1 = b − a − 1. On a

donc ε(τa,b ) = −1.
(c) Le cycle c = (1 2 · · · ℓ) de longueur ℓ
 
1 2 ... ℓ−1 ℓ ℓ+1 ... n
c=
2 3 ... ℓ 1 ℓ+1 ... n

donne lieu aux paires inversées {i, ℓ} 7→ {i + 1, 1} pour 1 6 i 6 ℓ − 1. On

obtient par conséquent

N (c) = ℓ − 1, ε(c) = (−1)ℓ−1 .

(d) La permutation σ correspondant au renversement de l’ordre

 
1 2 ... n−1 n
c=
n n−1 ... 2 1

n(n−1)
admet le nombre maximum N (σ) = 2
d’inversions, et on a par conséquent
ε(σ) = (−1)n(n−1)/2 .

On a la formule importante suivante

 Chap. 2 : groupes de permutations 7

2.1.3. Formule de la signature. Pour tout σ ∈ Sn , on a

Y σ(j) − σ(i)
ε(σ) = .
j−i
{i,j}∈Pn

Démonstration. Posons
Y σ(j) − σ(i)
εe(σ) = ∈ Q∗ .
j−i
{i,j}∈Pn

Il est clair que le signe de εe(σ) est (−1)N(σ) . Mais si on fait le changement de
variable bijectif {u, v} = σ
b({i, j}) = {σ(i), σ(j)}, on voit que le numérateur et le
démoninateur de εe(σ) sont tous les deux égaux en valeur absolue à

Y Y Y Y Y n−1
Y
|v − u| = (v − u) = (v − 1)! = i! = in−i .
{u,v}∈Pn 26v6n 16u6v−1 26v6n 16i6n−1 i=1

Il en résulte que |e
ε(σ)| = 1 et donc εe(σ) = ε(σ).

2.2. Propriété d'homomorphisme de la signature

On va voir que ε : Sn → {+1, −1} est un homomorphisme du groupe (Sn , ◦)

dans le groupe multiplicatif ({+1, −1}, ×), autrement dit :
2.2.1. Théorème. Pour toutes permutations σ, τ ∈ Sn , on a

ε(σ ◦ τ ) = ε(σ)ε(τ ).

Rappelons qu’un homomorphisme ϕ : G → H entre deux groupes (G, ∗), (H, ∗′ )

est une application telle que, pour tous x, y ∈ G, on ait ϕ(x ∗ y) = ϕ(x) ∗′ ϕ(y).
Dans ce cas

Ker ϕ = {x ∈ G / ϕ(x) = 1H }, Im ϕ = {u = ϕ(x) ∈ H / x ∈ G}

sont des sous-groupes de G et H respectivement.

Démonstration. Pour toutes permutations σ, τ ∈ Sn , il vient

Y σ(τ (j)) − σ(τ (i)) Y σ(τ (j)) − σ(τ (i)) Y τ (j) − τ (i)
ε(σ ◦τ ) = = .
j−i τ (j) − τ (i) j−i
{i,j}∈Pn {i,j}∈Pn {i,j}∈Pn

Dans le premier produit du membre de droite, faisons le changement de variable

bijectif {u, v} = τb({i, j}) = {τ (i), τ (j)}. Ceci donne
Y σ(τ (j)) − σ(τ (i)) Y σ(v) − σ(u)
= .
τ (j) − τ (i) v−u
{i,j}∈Pn {u,v}∈Pn
8 J.-P. Demailly, Arithmétique et algèbre linéaire approfondie

Par conséquent
Y σ(v) − σ(u) Y τ (j) − τ (i)
ε(σ ◦ τ ) = = ε(σ)ε(τ ).
v−u j−i
{u,v}∈Pn {i,j}∈Pn

2.2.2. Corollaire. Soit A = {a1 , . . . , an } un ensemble fini. Une permutation

σ ∈ SA est définie à l’aide d’une permutation α ∈ Sn par la correspondance
bijective
α ∈ Sn 7−→ σ ∈ SA , σ(ai ) = aα(i) .
Alors la signature de σ définie par ε(σ) := ε(α) ne dépend pas de la numérotation
des éléments de A, autrement dit, si A = {a′1 , . . . , a′n } avec une autre numérotation
des éléments, et si β ∈ Sn est telle que σ(a′i ) = a′β(i) , on a bien ε(α) = ε(β).

Démonstration. Le changement de numérotation est donné par a′i = aγ(i) avec une
certaine permutation γ ∈ Sn . Posant j = γ(i) et i = γ −1 (j), il vient a′γ −1 (j) = aj ,
donc
σ(a′i ) = σ(aγ(i) ) = aα(γ(i) = a′γ −1 (α(γ(i))) = a′β(i) ,
ce qui montre que les permutations α, β ∈ Sn sont liées par β = γ −1 ◦ α ◦ γ. Mais
on a alors
ε(β) = ε(γ)−1 ε(α)ε(γ) = ε(α).

2.2.3. Corollaire. Pour tout ensemble fini A, il existe un homomorphisme

signature ε : SA → {+1, −1} défini indépendamment de la numérotation des
éléments.

2.3. Cal ul de la signature d'une permutation quel onque

2.3.1. Proposition. Si c = (a1 a2 . . . aℓ ) est un cycle de longueur ℓ dans un

ensemble fini A, alors ε(c) = (−1)ℓ−1 .

Démonstration. Il suffit de numéroter les éléments en sorte que a1 , a2 , . . . , aℓ soient

précisément les ℓ premiers éléments de A, et d’observer que le nombre d’inversions
de (1 2 . . . ℓ) est alors exactement ℓ − 1 (on applique ici le corollaire 2.2.3).

2.3.2. Corollaire. Pour une permutation σ ∈ SA décomposée comme

σ = c1 ◦ c2 ◦ . . . ◦ cp

avec des cycles cj à supports disjoints de longueurs respectives ℓ1 , ℓ2 , . . . , ℓp , on a

ε(σ) = (−1)(ℓ1 −1)+(ℓ2 −1)+···+(ℓp −1) .

On observera qu’il est algorithmiquement beaucoup plus efficace de calculer la

signature à l’aide d’une décomposition en cycles qu’en examinant les inversions
 Chap. 2 : groupes de permutations 9

de toutes les paires {i, j} ∈ Pn . En effet, dans le premier cas, on fait un nombre
d’opérations d’un ordre de grandeur égal à n, alors que dans le deuxième cas, c’est
de l’ordre de n(n−1)
2 ∼ 12 n2 .
2.3.3. Remarque. Pour {a1 , a2 , . . . , aℓ } ⊂ {1, 2, , . . . , n}, une façon équivalente
de démontrer la proposition 2.3.1 est d’observer que le cycle c = (a1 a2 . . . aℓ ) est
le conjugué du cycle cℓ = (1 2 . . . ℓ) par la permutation
 
1 2 ... ℓ ℓ+1 ... n
γ=
a1 a2 . . . aℓ b1 . . . bn−ℓ

où {b1 , . . . , bn−ℓ } est le complémentaire de {a1 a2 . . . aℓ } dans {1, 2, . . . , n}, c’est-

à-dire que c = γ ◦ cℓ ◦ γ −1 (exercice !)
Plus généralement, on voit facilement que deux permutations σ, σ ′ ∈ Sn sont
conjuguées, i.e. σ ′ = γ ◦ σ ◦ γ −1 pour un certain élément γ ∈ Sn , si et seulement
si elles ont des décompositions en cycles disjoints

σ = c1 ◦ c2 ◦ . . . ◦ cp , σ ′ = c′1 ◦ c′2 ◦ . . . ◦ c′p

formées du même nombre p de cycles, avec des longueurs identiques ℓ′j = ℓj

(après avoir éventuellement réordonné les composées). Il suffit pour cela de
prendre γ qui envoie Supp cj sur Supp c′j en respectant S l’ordre cyclique des
éléments dans ces S cycles, et qui envoie {1, 2, . . . , n} r Supp cj bijectivement sur
{1, 2, . . . , n} r Supp c′j .

2.4. Le sous-groupe alterné An

2.4.1. Définition. On pose

An = ker ε = {σ ∈ Sn / ε(σ) = +1}.

C’est un sous-groupe de Sn .

2.4.2. Proposition. On a A1 = S1 = {Id}, et pour n > 2, card An = 12 n!.

Démonstration. Posons

S+
n = {σ ∈ Sn / ε(σ) = +1} = An , S−
n = {σ ∈ Sn / ε(σ) = −1}.

Alors on a la réunion disjointe Sn = S+ −

n ∪ Sn , et pour n > 2, on a une bijection

S+ −
n −→ Sn , σ 7−→ σ ◦ τ1,2 .
1
Par conséquent card S+ −
n = card Sn = card An = 2 n!.

2.4.3. Complément historique. Pour n > 5, on peut démontrer que An est

un groupe simple, c’est-à-dire que An n’a aucun sous-groupe distingué H autre
10 J.-P. Demailly, Arithmétique et algèbre linéaire approfondie

que H = {Id} et H = An (un sous-groupe distingué H d’un groupe G est un

sous-groupe invariant par conjugaison : ∀γ ∈ G, γHγ −1 = H) ; d’autre part,
An est non commutatif si n > 5. Vers 1830, Évariste Galois a déduit de ce
résultat que les racines complexes z1 , . . . , zn d’un polynôme général P ∈ Q[X]
de degré n ne peuvent s’exprimer par radicaux à partir de Q, à savoir comme
combinaisons de racines p-ièmes “enchevêtrées” en partant des rationnels – c’était
une question ouverte depuis la découverte des formules de résolution des équations
de degré 3 et 4 par Tartaglia et Ferrari au 16e siècle. On vérifie en effet que
le corps K = Q[z1 , . . . , zn ] engendré par les racines de P admet un groupe
d’automorphismes Aut(K) de permutation des racines égal à Sn si P est général.
Or, Sn ne peut se “dévisser” à l’aide de groupes abéliens, alors que ce serait le cas
pour Aut(K) si les racines étaient résolubles par radicaux. É. Galois a découvert
ces résultats alors qu’il avait à peine 20 ans, et les a consignés fébrilement dans un
testament écrit à la veille de son duel. Ils sont restés incompris de la communauté
mathématique pendant au moins 20 ans. C’est d’ailleurs à cette occasion qu’il a
introduit la notion fondamentale de groupe !

3. Générateurs du groupe des permutations

3.1. Génération par transpositions

3.1.1. Théorème. Toute permutation σ ∈ Sn s’écrit comme un produit d’au plus

n(n−1)
2
transpositions τi,i+1 portant sur des éléments consécutifs, 1 6 i 6 n − 1,
c’est-à-dire

n(n − 1)
σ = τi1 ,i1 +1 ◦ τi2 ,i2 +1 ◦ · · · ◦ τik ,ik +1 , k6 .
2

Démonstration. On raisonne par récurrence sur N (σ). Pour N (σ) = 0, on a

σ = Id, et le résutat est vrai avec k = 0 (produit vide, égal à Id par convention).
Supposons maintenant que N = N (σ) > 1 et que le résultat ait déjà été
démontré pour les permutations σ ′ telles que N (σ ′ ) = N − 1. Il existe alors
j ∈ {1, 2, . . . , n − 1} tel que σ(j) > σ(j + 1), sinon σ serait strictement croissante
(donc σ = Id et N (σ) = 0 contrairement à notre hypothèse). Posons

σ ′ = σ ◦ τj,j+1
 
1 2 ... j−1 j j+1 j+2 ... n
= .
σ(1) σ(2) . . . σ(j − 1) σ(j + 1) σ(j) σ(j + 2) . . . σ(n)

Alors l’inversion σ(j + 1) < σ(j) n’est plus une inversion pour σ ′ . On a donc
N (σ ′ ) = N (σ) − 1 = N − 1, et par hypothèse de récurrence, il existe une
décomposition
σ ′ = τi1 ,i1 +1 ◦ τi2 ,i2 +1 ◦ · · · ◦ τiℓ ,iℓ +1 ,
d’où
σ = σ ′ ◦ τj,j+1 = τi1 ,i1 +1 ◦ τi2 ,i2 +1 ◦ · · · ◦ τiℓ ,iℓ +1 ◦ τj,j+1 .
 Chap. 2 : groupes de permutations 11

Par récurrence, ce raisonnement fournit une décomposition ayant exactement

k = N (σ) transpositions τi,i+1 , de sorte que k 6 N(N−1)
2
.

3.1.2. Corollaire. En particulier, toute permutation σ ∈ Sn est une composée

σ = τa1 ,b1 ◦ τa2 ,b2 ◦ · · · ◦ τak ,bk

de transpositions, et la signature ε(σ) = (−1)k est déterminée par la parité du

nombre de transpositions nécessaires (et inversement).

3.2. Génération par une transposition et un y le

Si c = (1 2 . . . n) est le cycle 1 7→ 2 7→ · · · 7→ (n − 1) 7→ n 7→ 1 de longueur n,

on a cj−1 (i) = i + j − 1 modulo n, et on voit facilement que

τj,j+1 = cj−1 ◦ τ1,2 ◦ c−(j−1)

puisque c−(j−1) “ramène” {j, j + 1} sur {1, 2}, tandis que cj−1 “renvoie” {2, 1} sur
{j + 1, j}. Ceci montre que les transpositions τj,j+1 sont toutes conjuguées de τ1,2
par des puissances de c. Le théorème 3.1.1 implique alors
3.2.1. Théorème. Le groupe Sn est engendré par le cycle c = (1 2 . . . n) et
la permutation τ = τ1,2 , c’est-à-dire que toute permutation σ peut s’écrire comme
une composée (non commutative) de τ et de puissances ci entremêlées :

σ = cj0 ◦ τ ◦ cj1 ◦ τ ◦ · · · ◦ cjk−1 ◦ τ ◦ cjk , 0 6 jℓ 6 n − 1.

3.2.2. Exercice. On peut démontrer que pour n > 3 le groupe alterné An est
engendré par les cycles (a1 a2 a3 ) de longueur 3. Exercice pour le lecteur !