Algèbre T1
On va maintenant étudier des permutations particulières, les cycles, qui sont
les constituants élémentaires du groupe symétrique (cf. question 6 ci-dessous).
Un élément σ ∈ S n est un r-cycle, ou cycle de longueur r, s’il existe un
ensemble ordonné de r entiers distincts dans [n], {i 1 , . . . , i r }, tel que
σ(i 1 ) = i 2 , . . . , σ(i j ) = i j+1 , . . . , σ(i r ) = i 1
∀k ∈ {[n] − {i 1 , . . . , i r }}, σ(k) = k.
On remarquera qu’un 1-cycle est nécessairement l’identité et qu’un 2-cycle est une
transposition. Une permutation circulaire d’un ensemble à n éléments est un
n-cycle de S n (i.e. de longueur maximale).
4. Montrer qu’un r-cycle est un élément d’ordre r dans S n .
5. Montrer qu’un élément σ ∈ S n , n > 1, est un r-cycle si et seulement si dans la
décomposition de [n] en σ-orbites, il n’existe qu’une seule σ-orbite non ponctuelle
(i.e. non réduite à un point). Le cardinal de cette orbite est égal à r.
6. Montrer que tout élément σ ∈ S n , σ = id, s’écrit sous la forme
σ = γ 1 ◦ · · · ◦ γ s , s 1
où les γ i sont des cycles à supports disjoints, tous différents de l’identité, et que
cette décomposition est unique à l’ordre près des facteurs.
Cette décomposition s’appelle la décomposition canonique de σ en cycles.
Cette décomposition permet donc de ramener l’étude des permutations à celle
des cycles.
7. Montrer que pour σ ∈ S n , l’ordre de σ est le ppcm des ordres des cycles de sa
décomposition canonique.
8. Montrer que tout σ ∈ S n se décompose, de manière non unique, en un produit
de transpositions.
Nous allons maintenant introduire un invariant des permutations. Soit σ ∈ S n ;
si on note t le nombre de σ-orbites distinctes dans [n], on pose sgn(σ) = (−1) n−t
et on l’appelle signature de σ.
9. Montrer que si γ est un r-cycle, sgn(γ) = (−1) r−1 .
10. Montrer que si τ est une transposition, sgn(σ ◦ τ ) = −sgn(σ). (On considère
la tranposition τ qui échange i et j ; on montre que :
– si Ω σ (k) est une σ-orbite ne contenant ni i ni j, Ω σ◦τ (k) = Ω σ (k) ;
– si i et j sont dans deux σ-orbites distinctes, les termes de ces deux σ-orbites
forment une seule (σ ◦ τ )-orbite ;
26
On va maintenant étudier des permutations particulières, les cycles, qui sont
les constituants élémentaires du groupe symétrique (cf. question 6 ci-dessous).
Un élément σ ∈ S n est un r-cycle, ou cycle de longueur r, s’il existe un
ensemble ordonné de r entiers distincts dans [n], {i 1 , . . . , i r }, tel que
σ(i 1 ) = i 2 , . . . , σ(i j ) = i j+1 , . . . , σ(i r ) = i 1
∀k ∈ {[n] − {i 1 , . . . , i r }}, σ(k) = k.
On remarquera qu’un 1-cycle est nécessairement l’identité et qu’un 2-cycle est une
transposition. Une permutation circulaire d’un ensemble à n éléments est un
n-cycle de S n (i.e. de longueur maximale).
4. Montrer qu’un r-cycle est un élément d’ordre r dans S n .
5. Montrer qu’un élément σ ∈ S n , n > 1, est un r-cycle si et seulement si dans la
décomposition de [n] en σ-orbites, il n’existe qu’une seule σ-orbite non ponctuelle
(i.e. non réduite à un point). Le cardinal de cette orbite est égal à r.
6. Montrer que tout élément σ ∈ S n , σ = id, s’écrit sous la forme
σ = γ 1 ◦ · · · ◦ γ s , s 1
où les γ i sont des cycles à supports disjoints, tous différents de l’identité, et que
cette décomposition est unique à l’ordre près des facteurs.
Cette décomposition s’appelle la décomposition canonique de σ en cycles.
Cette décomposition permet donc de ramener l’étude des permutations à celle
des cycles.
7. Montrer que pour σ ∈ S n , l’ordre de σ est le ppcm des ordres des cycles de sa
décomposition canonique.
8. Montrer que tout σ ∈ S n se décompose, de manière non unique, en un produit
de transpositions.
Nous allons maintenant introduire un invariant des permutations. Soit σ ∈ S n ;
si on note t le nombre de σ-orbites distinctes dans [n], on pose sgn(σ) = (−1) n−t
et on l’appelle signature de σ.
9. Montrer que si γ est un r-cycle, sgn(γ) = (−1) r−1 .
10. Montrer que si τ est une transposition, sgn(σ ◦ τ ) = −sgn(σ). (On considère
la tranposition τ qui échange i et j ; on montre que :
– si Ω σ (k) est une σ-orbite ne contenant ni i ni j, Ω σ◦τ (k) = Ω σ (k) ;
– si i et j sont dans deux σ-orbites distinctes, les termes de ces deux σ-orbites
forment une seule (σ ◦ τ )-orbite ;
26