2.1 • Le groupe symétrique
37
1 er cas : σ (n + 1) = n + 1.
Comme σ est bijective, {1,. . . ,n} est alors stable par σ et l'application induite
σ
: {1,. . . ,n} −→ {1,. . . ,n}
k −→σ (k)
est une permutation de {1,. . . ,n}. D'après l'hypothèse de récurrence, il
existe N ∈ N
∗ et des transpositions t
1 ,. . . ,t
N de {1,. . . ,n} telles que :
σ
= t
1 ◦ . . . ◦ t
N .
En notant, pour chaque r de {1,. . . ,N }, t r : {1,. . . ,n + 1} −→ {1,. . . ,n + 1} l'application définie
par : t r (k) =
t
r (k) si 1 k n
n + 1 si k = n + 1 ,
il est clair que t 1 ,. . . ,t N sont des transpositions de
{1,. . . ,n + 1}, et que σ = t 1 ◦ . . . ◦ t N .
2 ème cas : σ (n + 1) = n + 1.
Considérons ρ = τ n+1,σ (n+1) ◦ σ.
On a ρ ∈ S n+1 et ρ(n + 1) = τ n+1,σ (n+1) (σ (n + 1)) = n + 1. D'après l'étude du 1
er cas, il existe
N ∈ N
∗ et des transpositions t 1 ,. . . ,t N de {1,. . . ,n + 1} telles que ρ = t 1 ◦ . . . ◦ t N . Alors
σ = τ n+1,σ (n+1) ◦ t 1 ◦ . . . ◦ t N et donc σ est un produit de transpositions de {1,. . . ,n + 1}.
᭿
La preuve précédente fournit un algorithme permettant de décomposer une permutation quelconque en un produit de transpositions : on remet les éléments 1,. . . ,n dans l'ordre, en en mettant un à sa place (au moins) à chaque étape.
Par exemple, soit σ =
1 2 3 4 5 6 7 8
6 3 7 4 8 1 5 2
1
2
3 4 5
6
7 8
σ
6
3
7 4 8
1
5 2
τ 2, 8
6
3
7 4 2
1
5 8
τ 5, 7
6
3
5 4 2
1
7 8
τ 1, 6
1
3
5 4 2
6
7 8
τ 2, 5
1
3
2 4 5
6
7 8
τ 2, 3
1
2
3 4 5
6
7 8
Dans chaque ligne, on a encadré les deux éléments qui vont être échangés pour obtenir la ligne
suivante.
On a donc τ 2, 3 ◦ τ 2, 5 ◦ τ 1, 6 ◦ τ 5, 7 ◦ τ 2, 8 ◦ σ = e,
d'où σ = τ 2, 8 ◦ τ 5, 7 ◦ τ 1, 6 ◦ τ 2, 5 ◦ τ 2, 3 .
Remarque :
L'algorithme précédent montre que toute permutation de {1,. . . ,n} est décomposable, d'au
moins une façon, en un produit d'au plus n transpositions.
Définition 2
Soit σ ∈ S n .
On dit qu'un couple (σ (i),σ ( j)) présente une inversion pour σ (ou : est une inversion de σ) si et seulement si : i < j et σ (i) > σ( j).
On note I(σ ) le nombre d'inversions de σ, et on appelle signature de σ le nombre,
noté ε(σ ), défini par : ε(σ ) = (−1)
I(σ ) .
On dit que σ est paire (resp. impaire) si et seulement si ε(σ ) = 1 (resp. ε(σ ) = −1).
t r est obtenue en prolongeant t
r en
n + 1
Monie r Algèbre Monier
Géométrie
Moni er Algèbre Monier
Mon ier Algèbre Géomé
Gé
ométrie Monier
On applique le résultat du 1 er cas à ρ.
Monie r Algèbre Monier
Géométrie
Moni er Algèbre Monier
Mon ier Algèbre Géomé
Gé
ométrie Monier
On met 8 à sa place, en dernier.
Monie r Algèbre Monier
Géométrie
Moni er Algèbre Monier
Mon ier Algèbre Géomé
Gé
ométrie Monier
On met 7 à sa place, en avant-dernier.
Monie r Algèbre Monier
Géométrie
Moni er Algèbre Monier
Mon ier Algèbre Géomé
Gé
ométrie Monier
Rappelons que toute transposition est
involutive.
Monie r Algèbre Monier
Géométrie
Moni er Algèbre Monier
Mon ier Algèbre Géomé
Gé
ométrie Monier
Ainsi :
• σ paire ⇐⇒ ε(σ ) = 1
⇐⇒ I (σ ) pair
• σ impaire ⇐⇒ ε(σ ) = −1
⇐⇒ I (σ ) impair.
Monie r Algèbre Monier
Géométrie
Moni er Algèbre Monier
Mon ier Algèbre Géomé
Gé
ométrie Monier
Exercices 2.1.2, 2.1.3.