Groupes Monogenes Et Symetriques Corrige

Télécharger au format pdf ou txt
Télécharger au format pdf ou txt
Vous êtes sur la page 1sur 12

Prépa CAPES UPMC 2008 Emmanuel Ferrand, Laurent Koelblen, Matthieu Romagny

Lundi 3 novembre 2008


Groupes monogènes, groupes
symétriques
Groupes monogènes et cycliques

Exercice 1 On dit qu’un groupe est monogène s’il peut être engendré par un seul élément.
(1) Montrer qu’un groupe monogène est isomorphe, soit à Z, soit à Z/nZ pour un entier
n ≥ 1.
(2) Montrez que le groupe G = Z × Z n’est pas monogène.

Corrigé exercice 1
(1) On commence par décrire explicitement le sous-groupe hxi engendré par un élément x
dans un groupe G. Il est clair que toutes les puissances xk de x sont dans le sous-groupe
engendré par x ; comme x−1 est dans le sous-groupe engendré par x, on a les puissances avec
k < 0 aussi bien que les puissances avec k ≥ 0. Comme {xk , k ∈ Z} est un sous-groupe de
G, finalement hxi = {xk , k ∈ Z}.
Revenons à la question. Soit G un groupe monogène, il peut donc être engendré par un
élément x. Ceci signifie que {xk , k ∈ Z} = G, ou encore, que le morphisme f : Z → G défini
par f (k) = xk est surjectif. Son noyau est un sous-groupe de Z, donc de la forme nZ pour
un n ≥ 0. Si n = 0 le morphisme f est un isomorphisme et G ' Z, et si n ≥ 1 le morphisme
f induit un isomorphisme f : Z/nZ → G.
(2) Nous allons aboutir à une contradiction en supposant que G = Z × Z est monogène.
Soit x un générateur, on peut écrire x = (a, b) avec a et b dans Z. Comme G est un groupe
abélien, on utilise naturellement une notation additive, en particulier on parle de multiples
kx au lieu de puissances xk . Comme x engendre G, les éléments (0, 1) et (1, 0) sont des
multiples de x :

(0, 1) = (ka, kb) et (1, 0) = (`a, `b) avec (k, `) ∈ Z2 .

Comme `a = 1 l’entier a est non nul, donc ka = 0 entraîne k = 0. Mais alors l’égalité kb = 1
est impossible. Par contraposée, G n’est pas monogène.

Exercice 2 (1) Montrez que l’ordre de k dans Z/nZ est n/ pgcd(k, n).
(2) Calculez l’ordre de (k, `) dans Z/nZ × Z/mZ.

Rappel sur le pgcd : avant de s’attaquer à la question (1), il est utile de commencer par
un bref rappel sur le pgcd de deux entiers relatifs a et b. Le pgcd est bien défini lorsque a
ou b n’est pas nul.
Une façon de le définir est de considérer l’ensemble des entiers naturels e ∈ N qui divisent
a et b, c’est-à-dire tels qu’il existe des entiers relatifs u et v tels que a = eu et b = ev. (On
note alors e|a et e|b.) Comme on a supposé que a ou b n’est pas nul, disons, par exemple
a 6= 0, alors e ≤ |a| et donc cet ensemble d’entiers e est majoré. Donc il possède un plus
grand élément que l’on note d et que l’on appelle le plus grand commun diviseur, ou pgcd,
de a et b. On note d = pgcd(a, b) ou parfois d = a ∧ b.
Une autre façon de définir le pgcd est de considérer l’ensemble des entiers relatifs n ∈ Z
qui sont somme d’un multiple de a et d’un multiple de b, ou plus formellement, l’ensemble

{n ∈ Z , ∃(k, l) ∈ Z2 , n = ka + lb} .

Cet ensemble est un sous-groupe de Z, donc de la forme dZ pour un certain d ≥ 1 (d ne peut


pas être nul car on a supposé que a ou b n’est pas nul). On montre que cet entier naturel d
est le même entier que dans la définition qui précède, c’est le pgcd de a et b.
Lorsque pgcd(a, b) = 1 on dit aussi que a et b sont premiers entre eux. Rappelons-nous
un résultat important concernant les entier premiers entre eux : le lemme de Gauss, qui dit
que si a divise bc et si a et b sont premiers entre eux, alors a divise c.
Pour calculer le pgcd, la méthode la plus systématique (et bien souvent la meilleure)
est d’utiliser l’algorithme d’Euclide, que je ne décris pas ici (je vous envoie à un livre de
cours d’Arithmétique). Une autre méthode est d’écrire les nombres a et b comme produits
de facteurs premiers. Supposons que a et b sont positifs pour simplifier (sinon, on met les
signes −1 où il le faut). On peut écrire a = (p1 )α1 . . . (p1 )αr et b = (p1 )β1 . . . (p1 )βr , où les pi
sont des nombres premiers distincts, avec des exposants éventuellement nuls. On fera bien
attention au fait qu’il ne s’agit pas des décompositions en facteurs premiers de a et b, car
dans la décomposition en facteurs premiers n’interviennent que des exposants > 0. On a
alors
pgcd(a, b) = (p1 )min(α1 ,β1 ) . . . (p1 )min(αr ,βr ) .
Voici un dernier commentaire sur le pgcd. Soient a et b deux entiers non tous deux nuls,
et d = pgcd(a, b). Comme d|a et d|b, il existe des entiers relatifs a0 , b0 tels que a = da0 et
b = db0 , et de plus pgcd(a0 , b0 ) = 1. L’existence des écritures

a = da0 , b = db0 avec pgcd(a0 , b0 ) = 1

caractérise le pgcd de a et b, et est souvent extrêmement utile pour le manipuler.

Corrigé exercice 2, question (1)


Posons d = pgcd(k, n) avec k = dk 0 , n = dn0 et pgcd(k 0 , n0 ) = 1. Il s’agit de montrer
que l’ordre de k dans Z/nZ est n0 . Soit u un entier positif tel que uk = 0 dans Z/nZ. Ceci
signifie qu’il existe v tel que uk = vn, ou encore udk 0 = vdn0 . On en déduit uk 0 = vn0 .
En particulier n0 divise uk 0 , et comme n0 et k 0 sont premiers entre eux, d’après le lemme de
Gauss n0 divise u, c’est-à-dire qu’il existe un entier w tel que u = wn0 . En particulier u ≥ n0 ,
et comme n0 k = n0 dk 0 = nk 0 est nul dans Z/nZ, on a bien montré que n0 est le plus petit
entier u tel que uk = 0 dans Z/nZ, c’est-à-dire, c’est l’ordre de k dans Z/nZ.
Rappel sur le ppcm : la question (2) est l’occasion de faire des rappels sur le ppcm,
parallèles à ceux sur le pgcd. Ici on n’a pas besoin de supposer que a ou b est non nul. On
considère l’ensemble des entiers naturels e ∈ N qui sont multiples à la fois de a et de b. C’est
un sous-ensemble non vide de N, donc il possède un plus petit élément noté m et appelé plus
petit commun multiple, ou ppcm, de a et b. On note m = ppcm(a, b) ou parfois m = a ∨ b.
On peut aussi considérer l’ensemble des entiers relatifs n ∈ Z qui sont multiples de a et
de b, qui n’est autre que l’ensemble aZ ∩ bZ. Cet ensemble est un sous-groupe de Z, donc
de la forme mZ pour un certain m ≥ 1. Cet entier naturel m est le même entier que dans la
définition qui précède, c’est le ppcm de a et b.
Pour calculer le ppcm, la méthode consistant à écrire les nombres a et b comme produits de
facteurs premiers a = (p1 )α1 . . . (p1 )αr et b = (p1 )β1 . . . (p1 )βr fonctionne aussi. (On suppose
ici aussi que a et b sont positifs pour simplifier.) Le résultat est :
ppcm(a, b) = (p1 )max(α1 ,β1 ) . . . (p1 )max(αr ,βr ) .
Il n’y a pas véritablement de méthode analogue à celle de l’algorithme d’Euclide pour le
pgcd, mais on peut s’y ramener toutefois, comme je l’explique dans quelques lignes.
Une propriété importante qui relie les nombres d = pgcd(a, b) et m = ppcm(a, b) est la
relation dm = |ab|. Notez que si a et b sont positifs on a plus simplement dm = ab, mais
pour définir le pgcd et le ppcm nous n’avons pas supposé que a et b étaient positifs ; en
revanche d et m ont été définis comme étant positifs. Pour démontrer que dm = ab lorsque
a et b sont positifs, on utilise les écritures
d = (p1 )min(α1 ,β1 ) . . . (p1 )min(αr ,βr ) et m = (p1 )max(α1 ,β1 ) . . . (p1 )max(αr ,βr ) .
Je vous laisse faire cette petite démonstration à titre d’exercice.
Je vous ai annoncé juste au-dessus qu’on peut se ramener à une méthode utilisant
l’algorithme d’Euclide pour calculer le ppcm : en effet, commencez par calculer le pgcd
en utilisant l’algorithme d’Euclide, puis utilisez la formule dm = |ab|. Sauf dans le cas où
les nombres a et b ont des décompositions en facteurs premiers faciles à trouver (ce qui n’est
pas le cas pour des entiers quelconques !!), cette méthode sera plus rapide.
Corrigé exercice 2, question (2)
Soit n0 = n/ pgcd(k, n) l’ordre de k dans Z/nZ = et m0 = m/pgcd(`, m) l’ordre de `
dans Z/mZ. On va montrer que l’ordre de (k, `) dans Z/nZ × Z/mZ est le ppcm de n0 et
de m0 . En fait, ceci est très général : si G et H sont deux groupes, x ∈ G est un élément
d’ordre a et y ∈ H est un élément d’ordre b, alors l’élément (x, y) du groupe produit direct
G × H est d’ordre ppcm(a, b). Nous allons démontrer cela. Soit u ≥ 0 un entier tel que
(x, y)u = (xu , y u ) = 1 dans G × H. Alors xu = 1 dans G donc u est multiple de a (c’est
une propriété de l’ordre a), et y u = 1 dans H donc u est multiple de b. Ainsi u est un
multiple commun de a et b. De plus, clairement pour tout multiple commun u de a et b on
a (x, y)u = 1. Donc l’ordre de (x, y) est le plus petit multiple commun, c’est-à-dire le ppcm,
de a et b.
Exercice 3 Soit n ≥ 1 un entier. On note ϕ(n) le nombre d’entiers 1 ≤ k ≤ n premiers
avec n (la fonction ϕ : N∗ → N est appelée fonction indicatrice d’Euler).
(1) Montrer que pour tout entier relatif non nul a ∈ Z, premier avec n, on a aϕ(n) ≡ 1 (n).
(2) Soit p un nombre premier et a ∈ Z. Montrer qu’on a ap ≡ a (p).

Corrigé exercice 3
(1) On sait que dans un groupe fini d’ordre d, tout élément x vérifie xd = 1. On va interpréter
la question demandée comme étant le reflet d’une relation dans un groupe d’ordre ϕ(n),
le groupe G des éléments inversibles de l’anneau Z/nZ. Pour être complets, nous allons
démontrer que, pour un entier relatif k dont on note k la classe modulo n, on a les conditions
équivalentes suivantes :
(i) k est premier avec n,
(ii) k est inversible dans l’anneau Z/nZ,
(iii) k engendre le groupe additif Z/nZ.
Pour répondre à la question de l’exercice, l’équivalence de (i) et (ii) suffit car elle montre
que les éléments du groupe G des inversibles de l’anneau Z/nZ sont les classes, modulo n,
des entiers 1 ≤ k ≤ n premiers avec n. Donc le cardinal de G est égal à ϕ(n). Il s’ensuit
que pour tout a ∈ G on a aϕ(n) = 1 dans G. Cela signifie exactement que pour tout entier
relatif a premier avec n, on a aϕ(n) ≡ 1 (n).
Montrons maintenant que (i) et (ii) sont équivalentes. D’après le théorème de Bézout, k
et n sont premiers entre eux ssi il existe des entiers relatifs u, v tels que uk + vn = 1, ssi il
existe un entier relatif u tel que uk = 1 dans Z/nZ, ssi k est inversible dans Z/nZ.
Pour finir on montre que (ii) et (iii) sont équivalentes. Si k est inversible dans l’anneau
Z/nZ, alors il existe un entier relatif u tel que uk = 1, donc pour tout m ∈ Z/nZ on a
m = muk. Ceci montre que tout élément de Z/nZ est un multiple de k, donc k engendre
le groupe additif Z/nZ. Réciproquement, si k engendre le groupe additif Z/nZ, alors en
particulier 1 est un multiple de k, donc il existe u tel que uk = 1, ce qui montre que k est
inversible dans Z/nZ.
Notons que l’équivalence entre (i) et (iii) peut aussi se voir directement, puisque k en-
gendre le groupe additif Z/nZ ssi son ordre est égal à n. Or on a montré dans un exercice
précédent que l’ordre de k est n/ pgcd(k, n), d’où la conclusion.
(2) Si p est premier, tous les entiers 1 ≤ k ≤ p − 1 sont premiers avec p et donc ϕ(p) = p − 1.
D’après la question précédente, pour tout a ∈ Z premier avec p, on obtient ap−1 ≡ 1 (p). En
multipliant par a ceci donne ap ≡ a (p). De plus, si a n’est pas premier avec p, c’est-à-dire
si p|a, alors ap et a sont tous les deux nuls modulo p donc la relation ap ≡ a (p) est encore
vérifiée. Finalement, pour tout a ∈ Z on a ap ≡ a (p).

Exercice 4 (1) Montrer que le groupe additif Q n’est pas monogène.


(2) En déduire que le groupe additif R n’est pas monogène.
(3) Montrer que Q est engendré par l’ensemble { n!1 }n≥1 .
(4) Montrer que tout sous-groupe monogène non nul de Q est infini.
(5) Montrer que tout sous-groupe de type fini, non nul, de Q est isomorphe à Z.
Corrigé exercice 4
(1) Supposons que Q soit monogène, engendré par un rationnel x = m/n écrit sous forme
de fraction irréductible, c’est-à-dire que m et n sont premiers entre eux. Alors 1/(2n) est un
multiple de x, i.e. il existe k ∈ Z tel que 1/(2n) = km/n. On en déduit l’égalité 2km = 1
dans Z, ce qui est impossible car 2km est pair. Donc Q n’est pas monogène.
(2) Supposons que R soit monogène. Comme il est infini, il est donc isomorphe à Z. Alors
le sous-groupe Q est isomorphe à un sous-groupe de Z, donc un groupe de la forme nZ. Or
nZ est isomorphe à Z, précisément on a un isomorphisme évident f : Z → nZ défini par
f (a) = na. Finalement Q est isomorphe à Z, donc monogène, ce qui est une contradiction
avec la question précédente.
(3) Soit un rationnel x = m/n. Alors x = m(n−1)!/n! ce qui montre que x est un multiple de
1/n!. Donc tout élément de Q est multiple d’un des nombres 1/n!, et a fortiori, les nombres
1/n! engendrent Q.
(4) Soit H ⊂ Q un sous-groupe monogène non nul. Il est isomorphe soit à Z, soit à Z/nZ
pour un entier n ≥ 1. Dans le deuxième cas, il existe dans H un élément x 6= 0 tel que
nx = 0. Mais comme Q est un corps, ceci implique x = 0, en contradiction avec l’hypothèse
sur x. Donc H est infini isomorphe à Z.
(5) On va montrer par récurrence sur k ≥ 1 qu’un sous-groupe de Q engendré par k éléments
est isomorphe à Z.
Initialisation de la récurrence : le cas k = 1 est simplement la question précédente.
Hérédité de la proposition : on suppose que tout sous-groupe engendré par k éléments
est isomorphe à Z. Soit H un sous-groupe engendré par k + 1 éléments notés x1 , . . . , xk , y.
D’après l’hypothèse de récurrence, le sous-groupe engendré par x1 , . . . , xk est isomorphe à
Z, donc engendré par un élément x = m/n (fraction irréductible). On est ainsi ramené au
cas k = 2 avec deux générateurs x, y où y = p/q (fraction irréductible). On a donc
 
2 amq + bpn 2
H = {ax + by , (a, b) ∈ Z } = , (a, b) ∈ Z .
nq

L’ensemble des nombres amq + bpn, avec (a, b) variable, est un sous-groupe de Z qui est de
la forme dZ, avec pour d le pgcd de mq et de pn : c’est une des définitions du pgcd. Il
s’ensuit que H est l’ensemble des multiples de d/(nq), il est donc monogène, comme on le
souhaitait.

Exercice 5 Montrez que si m et n sont deux entiers premiers entre eux, on a un isomor-
phisme Z/mnZ ' Z/mZ × Z/nZ. Est-ce vrai lorsque m et n ne sont pas premiers entre
eux ?

Corrigé exercice 5 De manière générale, si H, K sont deux sous-groupes distingués de G


avec H ⊂ K, on a un morphisme surjectif G/H → G/K. On le justifie ainsi : on part
du morphisme π : G → G/K. Le sous-groupe H est inclus dans K, qui est le noyau de π,
donc par le théorème fondamental sur le quotient G/H (aussi appelé propriété universelle
de G/H), le morphisme π induit un morphisme G/H → G/K. Le fait que ce morphisme
soit surjectif découle du fait analogue pour G → G/K.
Dans le cas des quotients de Z, comme mnZ ⊂ mZ et mnZ ⊂ nZ on a des morphismes
Z/mnZ → Z/mZ et Z/mnZ → Z/nZ, d’où un morphisme Z/mnZ → Z/mZ × Z/nZ. Si
l’on note a, e
a, b
a les classes modulo mn, m et n (respectivement), alors on peut écrire ce
morphisme sous la forme :

Z/mnZ → Z/mZ × Z/nZ


a 7→ (e
a, b
a)

Comme Z/mnZ et Z/mZ × Z/nZ ont le même cardinal égal à mn, pour montrer que ce
morphisme est un isomorphisme il suffit de montrer qu’il est injectif, ou surjectif, au choix.
Montrons que ce morphisme est injectif, ce qui est assez facile. Si a est dans le noyau, alors
a est multiple de m et de n. Donc il existe a0 ∈ Z tel que a = ma0 . Comme n divise a il
divise ma0 , et comme n est premier avec m, par le lemme de Gauss on obtient que n divise
a0 . Ainsi mn divise a, donc a = 0 dans Z/mnZ. On obtient l’injectivité recherchée.
Si m et n ne sont pas premiers entre eux, le résultat n’est plus vrai, et d’ailleurs on voit
ce qui pêche dans l’argument précédent. Il est facile de donner un contre-exemple : on prend
m = n > 1 et le morphisme est le morphisme Z/n2 Z → Z/nZ × Z/nZ. Ce morphisme n’est
certainement pas un isomorphisme, puisque le groupe de gauche possède un élément d’ordre
n2 alors que dans le groupe de droite, tous les éléments sont d’ordre ≤ n.

Groupes symétriques
Avant de passer à l’exercice 6, on a besoin de quelques éléments de cours sur les actions
de groupes et la structure du groupe symétrique.

Quelques notions sur les actions de groupes :

Dans l’étude du groupe symétrique, le vocabulaire des actions de groupes est extrêmement
pratique. Faisons quelques rappels.
Soit G un groupe et X un ensemble. Une action de G sur X est un morphisme de groupes
ρ : G → SX du groupe G vers le groupe des bijections de X. C’est la même chose de se
donner, pour tout élément g ∈ G, une bijection ρg : X → X, de telle façon que
(i) ρ1 = idX .
(ii) ρgg0 = ρg ◦ ρg0 pour tous g, g 0 dans G.
Par souci de concision, en général on note simplement g au lieu de ρg , et gx ou g.x au lieu
de ρg (x).
Le vocabulaire des actions de groupes permet d’utiliser l’intuition d’un problème géométrique
dans lequel G est un groupe de transformations et X est un espace géométrique (en un
sens volontairement un peu flou), par exemple un espace affine, ou euclidien, ou un espace
topologique. À cause de cela, on appelle souvent les éléments de X des points.
L’orbite d’un point x ∈ X sous le groupe G, ou G-orbite de x, est la partie de X définie
par
OG (x) = {gx , g ∈ G} .
La relation binaire sur X définie par x ∼ y ssi il existe g ∈ G tel que y = gx est une relation
d’équivalence. On a évidemment :

x ∼ y ⇐⇒ y ∈ OG (x) ⇐⇒ OG (x) = OG (y) .

Les classes d’équivalence pour cette relation sont les orbites de l’action de G sur X, et elles
forment la partition en orbites de X. Le stabilisateur du point x ∈ X est le sous-groupe de
G défini par Gx = {g ∈ G , gx = x}. La vérification du fait qu’il s’agit d’un sous-groupe est
un exercice facile. Ce sous-groupe n’est pas distingué en général ; je vous invite fortement à
chercher un contre-exemple pour illustrer cela avant de poursuivre la lecture.
L’action de G sur X est dite transitive s’il n’y a qu’une orbite. Ceci signifie que pour
tous x, y dans X il existe g ∈ G tel que y = gx, ou encore, que l’application evx : G → X
définie par g 7→ gx est surjective. (Je note cette application evx car il s’agit de l’évaluation
en x.) Par exemple, partant d’une action quelconque de G sur un ensemble X, et d’un point
x ∈ X, il y a une action de G sur l’orbite Y := OG (x) et cette action est transitive par
définition.
L’extrême opposé des « grosses » orbites (actions transitives) est le cas d’orbites réduites à
un seul élément : OG (x) = {x}. Dans ce cas, on parle d’orbite ponctuelle, ou d’orbite réduite
à un point, ou parfois d’orbite triviale. On dit aussi que x est un point fixe sous G. Par
définition, x est toujours un point fixe sous son stabilisateur Gx , c’est-à-dire OGx (x) = {x}.
Pour x ∈ X, nous introduisons maintenant l’application evx : G → X qui envoie g ∈ G
sur g(x). Nous l’appellerons l’application d’évaluation en x.
Théorème : L’application d’évaluation en x induit une bijection G/Gx → OG (x).
Démontrons ce résultat. Par définition de l’orbite, l’image de evx est l’orbite OG (x) donc
evx induit une application surjective G → OG (x). Pour cette application, deux éléments g, h
ont la même image ssi g −1 h ∈ Gx . Il s’ensuit, d’après la définition de l’ensemble quotient
G/Gx , ensemble des classes à gauche de G modulo Gx , que f induit une application bijective
G/Gx → OG (x). En particulier, si G est fini (mais sans supposer que X est fini), alors on
voit que les orbites de X sous G sont finies et le cardinal de l’orbite de x est égal à l’ordre
de son stabilisateur.

Quelques notions sur le groupe symétrique :

Le groupe symétrique agit naturellement (par sa définition même) sur l’ensemble des n
premiers entiers {1, . . . , n}. Lorsqu’on l’étudie, cette action est toujours en toile de fond
et on utilise naturellement le vocabulaire des actions de groupes. Par exemple, chaque
permutation σ a des orbites (les σ-orbites), qui sont les orbites de {1, . . . , n} sous G = hσi.
Cycles. Les permutations les plus simples (mise à part l’identité) du point de vue de cette
action sont celles qui ont une et une seule orbite non ponctuelle. On les appelle les cycles.
Une autre façon de les définir est de dire qu’un cycle est une permutation dont le support
est non vide et est une orbite. Notez que, par cette définition, l’identité n’est pas un cycle.
Si l’on note r le cardinal de l’orbite non ponctuelle, on dit aussi que σ est un r-cycle. Un
petit exercice facile montre que l’ordre d’un r-cycle est r. Les cycles les plus simples sont
les 2-cycles, que l’on appelle aussi transpositions. Un fait classique, que nous ne ferons pas
en exercice, mais que vous pouvez démontrer très facilement par récurrence sur n, est que le
groupe Sn est engendré par les transpositions.
Support. Soit σ une permutation du groupe symétrique Sn . On appelle support de σ
l’ensemble des points x ∈ Sn tels que σ(x) 6= x. C’est donc le complémentaire de l’ensemble
des points fixes de σ. On le note Supp(σ).
Si σ et τ sont deux permutations à supports disjoints, elles commutent. Voici la démon-
stration. Il s’agit de démontrer que pour tout i ∈ {1, . . . , n} on a (στ )(i) = (τ σ)(i). Si i n’est
ni dans le support de σ ni dans celui de τ , on a σ(i) = τ (i) = i donc (στ )(i) = (τ σ)(i) = i
et on a fini. Il reste à traiter le cas où i est dans le support de σ et le cas où i est dans
le support de τ . Clairement le raisonnement sera le même dans les deux cas, en changeant
σ en τ , donc il suffit de regarder le premier cas : i ∈ Supp(σ). Nous faisons l’observation
que comme l’ensemble des points fixes est stable sous σ, son complémentaire, c’est-à-dire le
support de σ, l’est aussi. Ainsi i et σ(i) sont dans le support de σ. Comme σ et τ sont à
supports disjoints, i et τ (i) ne sont pas dans le support de τ , en d’autres termes τ (i) = i et
τ (σ(i)) = σ(i). Donc τ (σ(i)) = σ(i) = σ(τ (i)) et on a fini.
Décomposition en cycles à supports disjoints. Le résultat de base pour manipuler les
permutations est le théorème suivant :
Théorème : toute permutation s’écrit de manière unique, à l’ordre près des facteurs, comme
un produit de cycles à supports disjoints.
Pour démontrer ceci, on raisonne par condition nécessaire, ce qui démontrera l’unicité de
la décomposition. On note que si σ = τ1 . . . τs est un produit de cycles à supports disjoints
notés O1 , . . . , Os , alors sur la partie Oi on a σ = τi . Il s’ensuit que Oi est stable sous σ, et
comme c’est une orbite de τi , c’est une orbite de σ. Ainsi O1 , . . . , Os sont toutes les orbites
non ponctuelles de σ, et de plus :

σ(x) si x ∈ Oi ,

τi (x) =
x si x 6∈ Oi .

Ceci montre que τi est entièrement déterminé par σ, donc la décomposition recherchée est
unique. Pour l’existence, on appelle O1 , . . . , Os les orbites non ponctuelles de σ et on définit
τi comme ci-dessus. Il est immédiat de vérifier que σ = τ1 . . . τs .

Exercice 6 (1) Soit σ un r-cycle dans le groupe symétrique Sn , n ≥ 2. Pour quelles valeurs
de k entier, 1 ≤ k ≤ r − 1, la permutation σ k est-elle un cycle ?
(2) On note σ = (i1 i2 . . . ir ). Étant donné τ ∈ Sn , montrez que τ στ −1 est le cycle

(τ (i1 )τ (i2 ) . . . τ (ir )) .

(3) Soit σ1 = (12 . . . n) la permutation circulaire et τ1 = (12). Pour k entier, calculez σ1k puis
σ1k τ1 σ1−k . En déduire que les permutations σ1 et τ1 engendrent Sn .
Corrigé exercice 6
(1) Comme l’ordre d’un r-cycle est r, le groupe G ⊂ Sn engendré par σ est isomorphe à
Z/rZ. Notons O le support de σ, qui est son unique orbite non ponctuelle, de la forme
O = {x, σ(x), . . . , σ r−1 (x)}. Cette orbite est de cardinal r, de même que G, ce qui montre
que l’application evx : G → O est une bijection (le stabilisateur Gx est réduit à {1}.
Nous devons dire pour quels entiers 1 ≤ k ≤ r − 1, la permutation σ k est un cycle.
Clairement, ce qui se passe en dehors du support O n’a aucune importance. Pour relier
ce qu’il se passe dans G = hσi et ce qu’il se passe dans O, nous allons utiliser la bijection
evx : G → O. La permutation σ k engendre un sous-groupe H de G, donc un groupe cyclique
d’ordre égal à l’ordre de k dans Z/rZ. Les orbites de H dans O correspondent, via la bijection
evx , aux classes de H à droite modulo G ; elles sont toutes de même cardinal égal à l’ordre
de H. En particulier, il n’y a qu’une orbite non ponctuelle ssi il n’y a qu’une orbite (dans
O), ssi H = G. Donc σ k est un cycle ssi c’est un r-cycle, ssi σ k engendre G, ssi k est premier
avec r.
(2) Soit σ = (i1 i2 . . . ir ) et vérifions que τ στ −1 = (τ (i1 )τ (i2 ) . . . τ (ir )). Notons γ = τ στ −1
et soit j ∈ {1, . . . , n}. Si j = τ (ik ) pour un k tel que 1 ≤ k ≤ r, alors il est clair que
γ(j) = γ(τ (ik )) = τ σ(ik ) = τ (ik+1 ). Si j n’est pas de la forme τ (ik ), c’est-à-dire si τ −1 (j)
n’est pas dans le support de σ, alors σ(τ −1 (j)) = τ −1 (j) donc γ(j) = j.
(3) Pour exprimer σ1 il est commode d’identifier {1, . . . , n} à Z/nZ, alors il est clair que
σ1 (j) = j +1 modulo n. Donc σ1k (j) = j +k modulo n. Ainsi, d’après la question précédente,
σ1k τ1 σ1−k = (σ1k (1) σ1k (2)) = (k + 1 k + 2) .
Pour conclure que les permutations σ1 et τ1 engendrent Sn , il y a plusieurs façons de faire.
Voici par exemple une solution par récurrence sur n.
Pour n = 1, il n’y a rien à dire.
Supposons maintenant que pour un n ≥ 2, les permutations (12 . . . n − 1) et (12) engen-
drent Sn−1 ; notons H le sous-groupe de Sn engendré par (12 . . . n) et (12) ; nous devons
montrer que toute permutation γ est dans H.
Notons j = γ(n). La permutation ϕ = σ1n−j γ vérifie ϕ(n) = n, donc son support est dans
{1, . . . , n − 1}. D’après l’hypothèse de récurrence, ϕ est dans le sous-groupe engendré par
(12 . . . n − 1) et (12). Or
−(n−1) −(n−1)
(12 . . . n − 1) = (1n)(12 . . . n) = σ1n−1 τ1 σ1 (12 . . . n) = σ1n−1 τ1 σ1 σ1 ∈ H .
Donc ϕ ∈ H, puis γ = σ1j−n ϕ ∈ H. Ceci conclut la démonstration par récurrence.

Exercice 7 Calculez la décomposition en cycles à supports disjoints et la signature des


permutations suivantes :
(1) La multiplication par 3 dans Z/8Z ;
(2) La multiplication par 2 dans Z/11Z ;
(3) La multiplication par 5 dans Z/11Z ;

On sait donner les décompositions en cycles, mais certains ne savent peut-être pas ce
qu’est la signature. Je commence par dire ce qu’est la signature, et je donne le corrigé de
l’exercice. Je vous invite à ne lire que les notions sur la signature, et a poser ensuite le
corrigé pour faire l’exercice (vous pouvez d’ailleurs d’ores et déjà calculer les décompositions
en cycles).

Quelques notions sur la signature :


Soit n ≥ 2 et Sn le groupe symétrique. Le groupe à 2 éléments, qui est unique à
isomorphisme près, peut être représenté par le groupe additif Z/2Z mais aussi par le groupe
multiplicatif {±1}.
Théorème : il existe un unique morphisme de groupes surjectif  : Sn → {±1}, que l’on
appelle la signature.
Nous allons d’abord démontrer l’existence. Pour cela, étant donnée une permutation σ,
nous définissons une inversion pour σ comme étant un couple d’entiers (i, j) dans {1, . . . , n}
tels que i < j et σ(i) > σ(j). C’est donc un couple dont l’ordre est renversé par σ. On note
nσ le nombre d’inversions pour σ, et on pose (σ) = (−1)nσ . Par exemple, si σ = 1, il n’y a
pas d’inversion, donc (σ) = 1, et si σ = (12), la seule inversion est le couple (1, 2) et donc
(σ) = −1. Ainsi  : Sn → {±1} est surjectif.
Pour démontrer qu’on a bien défini un morphisme, on va utiliser l’ensemble C[X1 , . . . , Xn ]
des polynômes en n indéterminées X1 , . . . , Xn (nous aurons besoin de très peu de choses sur
lui) et l’action de Sn sur C[X1 , . . . , Xn ] par permutation des variables. Cette action est
définie ainsi : étant donnés P = P (X1 , . . . , Xn ) et σ ∈ Sn , on note σP le polynôme

(σP )(X1 , . . . , Xn ) = P (Xσ(1) , . . . , Xσ(n) ) .

La variable Xi se trouve donc à la place d’indice σ −1 (i). Vérifions qu’il s’agit bien d’une
action : il est clair que 1P = P , et il reste à vérifier que (τ σ)P = τ (σP ). Or

(τ (σP ))(X1 , . . . , Xn ) = (σP )(Xτ (1) , . . . , Xτ (n) )


= P (. . . , Xτ (i) , . . . ) (la variable Xτ (i) est à la place d’indice σ −1 (i))
= P (Xτ σ(1) , . . . , Xτ σ(n) )
= ((τ σ)P )(X1 , . . . , Xn ) .

Nous pouvons passer à la démonstration proprement dite. Considérons le polynôme de


Vandermonde défini par Y
V (X1 , . . . , Xn ) = (Xj − Xi ) .
i<j

Par exemple, pour n = 3, on a V (X1 , X2 , X3 ) = (X3 −X2 )(X3 −X1 )(X2 −X1 ). Nous voulons
calculer σV , pour cela on va réordonner les facteurs dans l’expression
Y
σV (X1 , . . . , Xn ) = (Xσ(j) − Xσ(i) ) .
i<j

Si l’on prend un couple (i, j) avec i < j, il peut se passer deux choses :
- soit (i, j) est une inversion pour σ, auquel cas on pose i0 = σ(j), j 0 = σ(i) et on a i0 < j 0 .
- soit (i, j) n’est pas une inversion, alors on pose i0 = σ(i), j 0 = σ(j) et on a i0 < j 0 .
Avec ces notations, on a donc Xσ(j) − Xσ(i) = (±1)(Xj 0 − Xi0 ) avec i0 < j 0 , où le signe ±1
vaut −1 lorsque i, j est une inversion et 1 sinon. En conclusion, lorsqu’on multiplie tous ces
facteurs il apparaît un produit de signes −1 dont le nombre est égal au nombre d’inversions
de σ, c’est-à-dire que :
Y
σV (X1 , . . . , Xn ) = (σ) (Xj 0 − Xi0 ) = (σ)V (X1 , . . . , Xn ) .
i0 <j 0

Pour deux permutations σ, τ on a


(∗)
(στ )V = στ V = σ(τ V ) = σ((τ )V ) = (τ )σV = (τ )(σ)V .

On a utilisé, à l’endroit où il y a une étoile (∗), le fait que l’action de Sn sur C[X1 , . . . , Xn ] est
une action par automorphismes de C-espace vectoriel, donc en particulier σ(λP ) = λσ(P ).
Il résulte de ce calcul que (στ ) = (σ)(τ ), donc  est bien un morphisme de groupes.
Démontrons que ce morphisme est unique. Soit δ : Sn → {±1} un morphisme surjectif
de groupes. Pour démontrer que δ est unique, il suffit de démontrer que sa valeur est
−1 sur toutes les transpositions, car comme Sn est engendré par les transpositions, toute
permutation σ est produit de transpositions : σ = τ1 . . . τk , et alors δ(σ) = δ(τ1 ) . . . δ(τk ) =
(−1)k .
Comme deux quelconques permutations τ, τ 0 sont conjuguées : τ 0 = γτ γ −1 , on a δ(τ 0 ) =
δ(γτ γ −1 ) = δ(γ)δ(τ )δ(γ)−1 = δ(τ ). La valeur de δ est donc la même sur toutes les transpo-
sitions. Si cette valeur est 1, alors δ(τ ) = 1 pour toute transposition τ , donc δ(σ) = 1 pour
toute permutation σ (encore car Sn est engendré par les transpositions). Or on a supposé
que δ est surjectif, donc ceci est impossible et finalement la valeur de δ sur les transpositions
est −1.
Ceci termine la preuve du théorème sur la signature.
On dit qu’une permutation est paire si sa signature est +1 et impaire si sa signature
est −1. Le noyau de la signature, ensemble des permutations paires, est un sous-groupe
distingué de Sn appelé le groupe alterné et noté An .

Pour finir donnons diverses façons de calculer la signature :


1 (σ) = (−1)nσ où nσ est le nombre d’inversions de σ. En général, ceci est peu pratique
pour calculer (σ).
2 (σ) = (−1)k lorsque σ est produit de k transpositions.
3 (σ) = (−1)r−1 lorsque σ est un r-cycle, car un r-cyle est produit de r −1 transpositions :
σ = (1 . . . r) = (2 3)(3 4) . . . (r − 1 r)(r 1) et tous les cycles sont conjugués à celui-ci (exercice
6, question 2).
4 (σ) = (−1)n−s où s est le nombre d’orbites de σ (le nombre total, incluant les orbites
ponctuelles). Je vous suggère de démontrer ceci en exercice, en utilisant la décomposition
en cycles à support disjoint de σ.
Corrigé exercice 7
Commençons par les décompositions en cycles. Le calcul donne :
Multiplication par 3 dans Z/8Z = (1 3)(2 6)(5 7).
Multiplication par 2 dans Z/11Z = (1 2 4 8 5 10 9 7 3 6).
Multiplication par 5 dans Z/11Z = (1 5 3 4 9)(2 10 6 8 7).
Pour calculer les signatures, on utilise la décomposition en cycles et la formule (σ) =
(−1)r−1 lorsque σ est un r-cycle. On trouve :
Si σ est la multiplication par 3 dans Z/8Z, (σ) = (−1)3 = −1.
Si σ est la multiplication par 2 dans Z/11Z, (σ) = (−1)10−1 = −1.
Si σ est la multiplication par 5 dans Z/11Z, (σ) = (−1)5−1 (−1)5−1 = 1.

Vous aimerez peut-être aussi