Chapitre 29  Groupes de permutations

29.1  Les théorèmes

Soit J_n=[0,1..n-1]. Une permutation p de n éléments est une application bijective de J_n dans lui même et induit une application π_p de ℤⁿ dans lui même (π_p(x_i)=x_p(i)).
Les permutations forment un groupe pour la composition des applications.
Un cycle c est une permutation telle qu’il existe un enter k (0 ≤ k ≤ n−1) vérifiant :
pour j=0...k−1 c(a_j)=a_j+1 et c(a_k)=a₀
pour j=k+1...n−1 c(a_j)=a_j
k est appelé l’ordre du cycle c (c^k=id).
Un cycle d’ordre k est aussi appelé une permutation circulaire d’ordre k.
Une transposition t est un cycle d’ordre 2 (t²=id).
Théorème 1
Toute permutation peut s’exprimer comme produit de cycles disjoints.
L’ordre d’une permutation p est le plus petit commun multiple k des ordres des cycles disjoints obtenus (p^k=id).
Théorème 2
Toute permutation peut s’exprimer comme produit de transpositions.

29.2  Notations

Une permutation p sera notée :
[p(0),p(1),...,p(n-1)]

Un cycle c d’ordre k sera noté :
[a₀,a₁,...,a_k] si c(a₀)=a₁...c(a_k)=a₀

Attention :
[0,2,1] représente la permutation p telle que :
p(0)=0, p(1)=2, p(2)=1
mais représente aussi le cycle c tel que :
c(0)=2, c(2)=1, c(1)=0

29.3  Exercices

Exercice 1
Exprimer les permutations suivantes comme produit de cycles disjoints et déterminer leurs signatures, leurs ordres et leurs inverses:
[1,2,0]
[2,0,1]
[2,1,0]
[1,2,0,3]
[1,0,3,2]
[2,1,3,0]
[2,4,5,0,1,3]
[5,0,4,2,3,1]
[5,3,4,6,2,0,1]
Exercice 2
Ecrire les produits de cycles suivants sous la forme :
1/ d’une permutation
2/ d’un produit de cycles disjoints
[[0,1,2,3,4],[0,4,5],[1,3,5]]
[[0,1,2,3],[1,2,3,4],[2,3,4,0]]
[[0,1],[1,2],[2,3],[3,4],[4,0]]
[[1,5][4,5],[5,6]]
Exercice 3
Calculer p¹⁰⁰⁰ pour les permutations p suivantes :
[2,5,7,8,3,4,1,0,6]
[2,5,0,3,1,4]
Exercice 4
Déterminer le groupe engendré par les permutations suivantes :
[2,1,0,3] et [3,1,2,0]

29.4  Corrections des exercices

Exercice 1
On tape :
p:=[1,2,0]
On tape :
permu2cycles(p)
On obtient :
[[0,1,2]]
On tape :
signature(p)
On obtient :
1
On tape :
permuorder(p)
On obtient :
3
On tape :
perminv(p)
On obtient :
[2,0,1]
Exercice 2
On tape :
cl:=[[0,1,2,3,4],[0,4,5],[1,3,5]]
On tape :
cycles2permu(cl)
On obtient :
[0,4,3,1,5,2]
Exercice 3
On tape :
permu2cycles([2,5,7,8,3,4,1,0,6])
On obtient :
[[0,2,7],[1,5,4,3,8,6]]
On tape :
p:=[2,5,7,8,3,4,1,0,6]
p est décomposable en un cycle d”orde 3 et un cycle d’ordre 6, p est donc d’ordre 6 puisque ppcm(3,6)=6 (lcm(3,6)=6).
Donc p⁶=id. On a irem(1000,6)=4 donc :
p¹⁰⁰⁰=p⁴
On tape :
p2:=p1op2(p,p)
p4:=p1op2(p2,p2)
On obtient :
[2,8,7,5,1,6,3,0,4]
Donc p¹⁰⁰⁰=p⁴= [2,8,7,5,1,6,3,0,4]
On vérifie que p⁶=id :
p6:=p1op2(p2,p4)
On obtient bien :
[0,1,2,3,4,5,6,7,8]
On procède de la même façon pour l’autre permutation, on tape :
p:=[2,5,0,3,1,4]
On tape :
permu2cycles(p)
On obtient :
[[0,2],[1,5,4]]
p est décomposable en un cycle d”orde 2 et un cycle d’ordre 3, p est donc d’ordre 6 puisque lcm(2,3)=6.
Donc p⁶=id. On a irem(1000,6)=4 donc :
p¹⁰⁰⁰=p⁴
On tape :
p2:=p1op2(p,p)
p4:=p1op2(p2,p2)
On obtient :
[0,5,2,3,1,4]
Donc p¹⁰⁰⁰=p⁴=[0,5,2,3,1,4]
On vérifie que p⁶=id :
p6:=p1op2(p2,p4)
On obtient bien :
[0,1,2,3,4,5]
Exercice 4
On tape :
groupermu([2,1,0,3],[3,1,2,0])
On obtient :
[[2,1,0,3],[3,1,2,0],[0,1,2,3],[2,1,3,0],[3,1,0,2],[0,1,3,2]]
qui sont :
a,b,a∘ a,b∘ a,a∘ b,a∘ b∘ a avec a:=[2,1,0,3] et b:=[3,1,2,0]
On peut vérifier par exemple que :
a∘ a=p1op2(a,a)=b∘ b=p1op2(b,b)=[0,1,2,3]=id et que
a∘ b∘ a=p1op2(a,p1op2(b,a))=b∘ a∘ b=p1op2(b,p1op2(a,b))=[0,1,3,2]