Chap. 1. Algèbre générale
Illustrons tout ceci par un exemple : la permutation s dont la décomposition en cycles est (1, 2, 3) (4, 5, 6) (7, 8, 9, 10) (11, 12, 13, 14) peut s’écrire
c
2 avec c = (1, 3, 2) (4, 6, 5) (7, 11, 8, 12, 9, 13, 10, 14), ou encore c
2 avec
c
= (1, 4, 2, 5, 3, 6) (7, 11, 8, 12, 9, 13, 10, 14).
2) • On remarque que si les entiers i 1 , . . . , i p , j 1 , . . . , j p sont deux à deux distincts,
alors (i 1 , i 2 , . . . , i p ) ( j 1 , j 2 , . . . , j p ) = c
2 = c
2 , avec c = (i 1 , j 1 , i 2 , j 2 , . . . , i p , j p )
et c
= (i 1 , j 2 , i 2 , j 3 , . . . , i p , j 1 ). Par conséquent, l’équation s ◦ s = s n’admet
pas une solution unique lorsque s contient au moins deux cycles de même
longueur, ou deux points fixes (car Id
2 = (i, j)
2 = Id).
• On suppose désormais que s est composée de cycles de longueurs impaires
deux à deux distinctes. On écrit s = s ◦ s et on décompose s en cycles
disjoints. Par unicité de la décomposition, s ne contient pas de cycle de longueur paire (car s
2 contiendrait deux cycles de même longueur), donc s est
produit de cycles de mêmes supports que s. Tout revient à examiner si dans S p
(avec p impair), l’équation s ◦ s = (1, 2, . . . , p), où s est un p-cycle, admet
une solution unique. D’après les calculs précédents, s est forcément le cycle
(1, s(1), 2, s(1) + 1, 3, s(1) + 2, . . .). Comme s est de longueur p, ceci n’est possible que si s(1) =
p + 1
2
, donc il y a bien unicité.
En conclusion, les permutations s telles que l’équation s ◦ s = s possède une
solution unique sont les composées de cycles disjoints de longueurs impaires deux
à deux distinctes ayant au plus un point fixe.
3) • Démontrons pour commencer le lemme suivant : dans S p , l’équation s
k = c où
c est le cycle (1, 2, . . . , p) a une solution si et seulement si p ∧ k = 1.
Si p ∧ k = 1, alors il existe d’après la formule de Bézout deux entiers u et v
tels que vk − up = 1, auquel cas s = c
v convient car s
k = c
vk = c
1+up = c.
Si p ∧ k = d > 1 et s
k = c, alors s est forcément un p-cycle (unicité de la
décomposition), et en écrivant p = dp
, k = dk
, on a :
(s
k )
p
(1) = s
pk
(1) = (s
p )
k
(1) = 1,
car s
p (1) = 1, alors que c
p
(1) = 1.
• Soit s un cycle de longueur p. Si d divise p, alors s
d est un produit de d cycles
de longueur
p
d
.
Si k n’est pas premier avec p, soit d leur PGCD, alors p = dp
, k = dk
avec
p
∧ k
= 1, donc s
k = (s
d )
k
. Comme k
est premier avec p
, s
k est produit de
d cycles de longueur
p
d
.
En conclusion, l’équation s
k = s admet des solutions dans S n si et seulement
si pour toute longueur r de cycle intervenant dans la décomposition en cycles
disjoints de s, on trouve un nombre de cycles de longueur r qui soit un multiple
du pgcd de k et r .
Illustrons tout ceci par un exemple : la permutation s dont la décomposition en cycles est (1, 2, 3) (4, 5, 6) (7, 8, 9, 10) (11, 12, 13, 14) peut s’écrire
c
2 avec c = (1, 3, 2) (4, 6, 5) (7, 11, 8, 12, 9, 13, 10, 14), ou encore c
2 avec
c
= (1, 4, 2, 5, 3, 6) (7, 11, 8, 12, 9, 13, 10, 14).
2) • On remarque que si les entiers i 1 , . . . , i p , j 1 , . . . , j p sont deux à deux distincts,
alors (i 1 , i 2 , . . . , i p ) ( j 1 , j 2 , . . . , j p ) = c
2 = c
2 , avec c = (i 1 , j 1 , i 2 , j 2 , . . . , i p , j p )
et c
= (i 1 , j 2 , i 2 , j 3 , . . . , i p , j 1 ). Par conséquent, l’équation s ◦ s = s n’admet
pas une solution unique lorsque s contient au moins deux cycles de même
longueur, ou deux points fixes (car Id
2 = (i, j)
2 = Id).
• On suppose désormais que s est composée de cycles de longueurs impaires
deux à deux distinctes. On écrit s = s ◦ s et on décompose s en cycles
disjoints. Par unicité de la décomposition, s ne contient pas de cycle de longueur paire (car s
2 contiendrait deux cycles de même longueur), donc s est
produit de cycles de mêmes supports que s. Tout revient à examiner si dans S p
(avec p impair), l’équation s ◦ s = (1, 2, . . . , p), où s est un p-cycle, admet
une solution unique. D’après les calculs précédents, s est forcément le cycle
(1, s(1), 2, s(1) + 1, 3, s(1) + 2, . . .). Comme s est de longueur p, ceci n’est possible que si s(1) =
p + 1
2
, donc il y a bien unicité.
En conclusion, les permutations s telles que l’équation s ◦ s = s possède une
solution unique sont les composées de cycles disjoints de longueurs impaires deux
à deux distinctes ayant au plus un point fixe.
3) • Démontrons pour commencer le lemme suivant : dans S p , l’équation s
k = c où
c est le cycle (1, 2, . . . , p) a une solution si et seulement si p ∧ k = 1.
Si p ∧ k = 1, alors il existe d’après la formule de Bézout deux entiers u et v
tels que vk − up = 1, auquel cas s = c
v convient car s
k = c
vk = c
1+up = c.
Si p ∧ k = d > 1 et s
k = c, alors s est forcément un p-cycle (unicité de la
décomposition), et en écrivant p = dp
, k = dk
, on a :
(s
k )
p
(1) = s
pk
(1) = (s
p )
k
(1) = 1,
car s
p (1) = 1, alors que c
p
(1) = 1.
• Soit s un cycle de longueur p. Si d divise p, alors s
d est un produit de d cycles
de longueur
p
d
.
Si k n’est pas premier avec p, soit d leur PGCD, alors p = dp
, k = dk
avec
p
∧ k
= 1, donc s
k = (s
d )
k
. Comme k
est premier avec p
, s
k est produit de
d cycles de longueur
p
d
.
En conclusion, l’équation s
k = s admet des solutions dans S n si et seulement
si pour toute longueur r de cycle intervenant dans la décomposition en cycles
disjoints de s, on trouve un nombre de cycles de longueur r qui soit un multiple
du pgcd de k et r .