|
Le groupe symétrique d'ordre n
Pendant longtemps, cette page a été la seule du Web dédiée
au groupe symétrique d'ordre n. Mais je ne pensais
pas qu'un jour il en existerait
une
autre (et francophone, en plus) !!!
Très utile en mathématiques, le groupe symétrique et la théorie
qui est attachée apparaît souvent mais de façon relativement
discrète. Il intervient par exemple en théorie du déterminant,
dont les plus matheux d'entre vous connaissent la grande importance.
Une autre raison pour laquelle j'ai créé cette page est que j'ai
remarqué que le groupe symétrique passe pour quelque chose de difficile
aux yeux de plein d'élèves de mathématiques spéciales (où l'on étudie
la chose) et alors qu'en fait, c'est simple.
Et si vous êtes dans ce cas, j'espère que cette page vous sera utile.
Généralités sur les groupes
Quelques notions générales sur les lois internes, les groupes, et autres
petits hors d'oeuvres avant d'attaquer le vif du sujet.
- Une loi interne sur un ensemble E est une
application * de E2 dans E. L'image du couple
(x,y) par * est notée x*y au lieu de *(x,y).
- Une loi * est associative si pour tout a, b, c
de E on a (a*b)*c = a*(b*c).
- Une loi * admet un élément neutre s'il existe un élément e
tel que pour tout x de E, e*x = x*e = x. L'élément
neutre est e.
- Si * est une loi qui admet un élément neutre e, on dit alors
que l'élément x de E admet un symétrique
ou est symétrisable s'il existe un élément y de
E qui vérifie x*y = y*x = e. Le
symétrique de x est y et on le note x-1.
- Enfin, un ensemble G muni d'une loi *, ce que l'on note
(G,*), est un groupe lorque * est :
- Associative,
- Admet un élément neutre,
- Telle que tout élément de G admet par * un symétrique.
Les ensembles de nombres classiques, tels que l'ensemble des entiers
relatifs ou l'ensemble des nombres réels deviennent des groupes
lorsqu'on les munit de la loi +.
Mais cette loi + est commutative, c'est à dire
que a+b = b+a. Une telle propriété de
commutativité n'existe pas dans le groupe symétrique d'ordre n (sauf
le cas particulier n = 2), ce qui donne des règles de calcul
différentes.
Une autre notion fondamentale en théorie des groupes est celle de
morphisme. Si (G,*) et (H,¤) sont deux
groupes et u une application de G dans H, on
dit que u est un morphisme lorsque
u(x*y) = u(x)¤u(y)
pour tout x et y de G. Notons que si e' désigne
l'élément neutre de H, l'application u0 qui prend la valeur
e' en tout x de G est un morphisme, que l'on appelle
morphisme trivial.
Si u est un morphisme, le sous ensemble u-1({e'}) de G, constitué des
éléments x de G tels que
u(x) = e' est appelé
noyau du morphisme u. Le noyau d'un morphisme est
toujours un groupe inclus dans G : on dit que c'est un
sous-groupe de G. Le noyau du
morphisme trivial est égal à G.
Définition du groupe symétrique
L'étude du groupe symétrique est fondée sur l'ensemble {1,2,...,n}. On
va en effet considérer des fonctions f de cet ensemble dans lui même qui
ont une propriété particulière : elle sont injectives,
c'est à dire que . De telles fonctions f sont
appelées permutations de {1,2,...,n} parce qu'en
effet elles changent l'ordre des éléments de {1,2,...,n} en leur
associant à chacun une nouvelle "place" dans l'ensemble.
On définit sur l'ensemble de ces permutations une loi interne
.
Si f et g sont deux permutations de {1,2,...,n},
la permutation composée est définie par
.
Cette loi n'est pas commutative, les permutations
n'étant pas toujours les mêmes. Cependant si c'est le cas,
on dit que les permutations f et g commutent.
La composition des permutations est une loi associative.
Il existe une permutation un peu particulière, c'est celle qui ne permute
rien du tout ! On l'appelle la permutation identique et
on la note Id. On a donc Id(x) = x pour tout x
de {1,2,...,n}.
Prenons maintenant une permutation f quelconque, et intéressons
nous à . Comme Id(x) = x,
on a f[Id(x)] = f(x) mais comme
on a aussi Id[f(x)] = f(x), on
a donc . Id est donc l'élément neutre de la loi
.
Enfin à toute permutation f on peut associer la permutation
réciproque, qui "remet" les éléments de {1,2,...,n} à leur
place, si l'on veut. Si on note g cette réciproque et que
y = f(x) alors on aura g(y) = x
autrement dit et donc g est la permutation symétrique de f.
On écrit g = f -1.
Plus généralement, la permutation est notée
f 2, est notée
f 3, etc. On convient que
f -k = (f k)-1
et que f 0 = Id.
L'ensemble des permutations de {1,2,...,n}, quand
on le munit de la loi devient donc un groupe. C'est le
fameux groupe symétrique d'ordre n, que l'on
note .
Une remarque au passage : il n'y a qu'un nombre fini de permutations
de {1,2,...,n}, qui est n!. C'est donc aussi le nombre d'éléments de
. On appelle
généralement ordre d'un groupe le nombre d'éléments de ce
groupe. Bien qu'on l'appelle groupe symétrique d'ordre n,
n'est donc pas d'ordre n mais d'ordre n!.
Notations des éléments
du groupe symétrique
Pour travailler de manière commode avec , il faut mettre en place une
notation pratique pour ses éléments. On note alors une permutation sous
la forme d'un tableau à deux lignes. La première ligne contient les
éléments de {1,2,...,n} écrits dans l'ordre usuel et la seconde
leur image par la permutation.
Plus précisément, ![[formule 9]](grsym9.gif)
Il s'agit là de la notation la plus générale. Certaines permutations, très
importantes, vérifient la propriété suivante : il existe un entier p
tel que pour tout x, f(x) = x ou bien
f p(x) = x.
Ce sont les permutations circulaires que l'on appelle
aussi des cycles. Les éléments tels que
f(x) = x sont les points fixes du cycle et l'entier
p est la longueur du cycle. Pour travailler plus commodément
avec une telle permutation (et on le fait très souvent), on a plûtot
envie de la noter en mettant les points fixes de côté pour mieux percevoir
le côté "circulaire".
Par exemple on pourrait écrire ![[formule 10]](grsym10.gif)
Mais cette notation n'est pas cohérente avec la précédente car les éléments
a,f(a),..., f p-1(a)
ne sont pas forcément égaux à 1,2,..., x-1. De plus on écrit
plein de trucs inutiles comme les images des points fixes. On adopte alors un
notation particulière :
f = (a,f(a),f 2(a),..., f p-1(a)). On a bien allégé l'écriture
et tout y est. Pour connaître l'image d'un élément, il suffit
de le chercher dans la liste et de prendre celui qui le suit (ou le premier
élément de la liste si on est au bout). Si on ne le trouve pas dans la
liste, c'est que c'est un point fixe : il est sa propre image. L'ensemble
des éléments non invarients par le cycle f se nomme support du
cycle.
Une dernière définition avant de se lancer dans les premiers éléments
de théorie propre à :
un cycle de longeur 2 est appelé une transposition.
On la note bien sûr f = (a,f(a)).
Orbite suivant une permutation
Voici maintenant une notion fondamentale pour étudier
.
Pour f, permutation donnée et x, y deux
éléments de {1,2,...,n}, on considère la relation binaire
Rf définie par . On démontre alors
que celle relation binaire est une relation d'équivalence.
On appelle alors orbite de x suivant f
la classe d'équivalence de x suivant Rf.
Cette orbite, qui est donc un sous-ensemble de {1,2,...,n} est
notée Of (x) ou plus simplement
O(x) s'il n'y a pas d'ambiguïté.
De manière pratique, pour obtenir l'orbite d'un élément, on calcule
ses images par f jusqu'à ce qu'on revienne à x (ce qui
finit toujours par arriver). Lorsque x est un point fixe
de f, Of (x) = {x}. Une
telle orbite est appelée orbite triviale. Autre chose : dans
la suite, on va être amené de nombreuses fois à compter le nombre
d'orbites distinctes suivant une permutation. Si
,
on a alors Of (x) = Of (y)
mais ces deux orbites ne "comptent" que pour une seule seule. On
dit que x et y représentent une même orbite.
Théorèmes relatifs au groupe
symétrique
Munis de toutes les notions précédentes, nous sommes maintenant en mesure
de formuler les théorèmes fondamentaux sur .
Théorème 1 : une permutation f de est un cycle si et
seulement si il n'existe qu'une seule orbite non triviale suivant f.
Le support de f est alors cette orbite non triviale, et la longueur
de f son cardinal.
Théorème 2 : deux cycles de supports disjoints
commutent.
Théorème 3 (décomposition en cycles) : toute
permutation autre que l'identité se décompose en un produit,
unique et commutatif, de cycles de supports
disjoints. Les supports de ces cycles coïncident avec les orbites
non triviales suivant f.
Théorème 4 (décomposition d'un cycle en
transpositions) : tout cycle de longueur p s'écrivant
(a1,a2,...,ap)
se décompose en un produit de p-1 transpositions, mais ce produit
n'est ni unique ni commutatif.
On peut par exemple écrire mais d'autres décompositions sont
possibles. Elles comprendront cependant toujours p-1 transpositions.
Corollaire 1 (conséquence des
théorèmes 3 et 4) : toute permutation de peut se décomposer en
un produit de transpositions. Ce produit n'est donc ni unique ni commutatif
mais il comprend toujours le même nombre de transpositions. On dit
que les transpositions engendrent le groupe
Théorème 5 (signature) : il existe un
et un seul morphisme non trivial de sur . Il est donné
par
où p est le nombre total d'orbites, y compris les triviales. Ce morphisme
se nomme signature de la permutation f.
Corollaire 2 (calcul de la
signature) : une transposition admet n-2 points fixes donc
n-1 orbites. Sa signature est (-1)n-(n-1) c'est
à dire -1. Il en résulte que la signature d'un cycle de longueur p
est (-1)p-1 par application du théorème 4 et du théorème
précédent. De la même façon, une permutation se décomposant en produit
de s transpositions a pour signature (-1)s.
Corollaire 3 (groupe alterné) : le noyau
du morphisme ,
ensemble des permutations de signature égale à 1 est donc un groupe
appelé
groupe alterné d'ordre n. C'est un sous-groupe
de qui
a moitié moins d'éléments que lui.
Armé de ces théorèmes, on peut alors étudier facilement n'importe quelle
permutation de .
Et d'ailleurs, je vais terminer cette cette page en vous montrant, sur un
exemple, comment on s'y prend.
Exemple d'étude d'une
permutation
On considère la permutation f de définie par
.
On va décomposer f en transpositions, déterminer sa signature
et calculer f 1997 (non, je ne suis pas tombé sur la tête,
vous allez voir, c'est facile).
Pour la décomposition en transpositions, on va utiliser les théorèmes 3
et 4 puis le corollaire 1. Pour cela, il nous faut connaître les orbites
des éléments de {1,2,...,10} suivant f.
On a f(1) = 3, f(3) = 6, f(6) = 1. Donc
O(1) = {1,3,6}. On détermine de la même façon les autres orbites
et on trouve O(2) = {2,10,9,8,5}, O(4) = {4},
O(7) = {7}.
D'après le théorème 3, on a alors avec c1 = (1,3,6)
et c2 = (2,10,9,8,5).
On décompose maintenant c1 et c2 en
transpositions, en utilisant la formule du théorème 4 :
![[formule 17]](grsym17.gif)
![[formule 18]](grsym18.gif)
On en déduit alors que .
Remarque : cette décomposition en transpositions a moins
d'intérêt que la décomposition en cycles car cette dernière est unique et
surtout, les cycles commutent. On utilise donc principalement la décomposition
en cycles.
Pour calculer la signature, on peut remarquer que f est le produit
de 6 transpositions et que donc .
Mais la décomposition en cycles
fournit aussi . On remarque que f est une permutation
de .
Le calcul de f 1997 va utiliser le fait que si c
est un cycle de longueur p alors c p = Id
(cela découle de la définition d'un cycle : p est
tel que pour tout x, c(x) = x ou bien
c p(x) = x).
et aussi le fait que comme les cycles c1 et c2
commutent, on a . Attention, le fait que les deux cycles commutent est
ici primordial pour pouvoir écrire cela. Ce serait totalement
faux avec des permutations quelconques. On commence donc par déterminer la
1997ème puissance des cycles composant f :
On a .
De même .
On vient de montrer que . Il ne nous reste donc plus qu'à calculer le carré
des deux cycles c1 et c2 puis le
produit de ces carrés pour obtenir le résultat :
![[formule 26]](grsym26.gif)
Tous calculs faits, on trouve ![[formule 28]](grsym28.gif)
Applications du groupe
symétrique
J'avais initialement prévu de ne faire qu'une seule page
sur
regroupant l'étude de ses permutations et de ses applications. Mais
cette page aurait été beaucoup plus grosse que je ne l'avait prévu (et m'aurai
pris beaucoup de temps à faire) ! J'ai donc finalement choisi de faire
plusieurs pages sur .
- Page de garde : Introduction à
(cette même page)
- Rassemblement de résultats divers relatifs à
(autres théorèmes et propriétés)
- Applications de
en mathématiques
Les deux dernières pages seront en ligne plus tard.
![[Revue]](/img-shared/nav-revue.gif) ![[Mangas]](/img-shared/nav-mangas.gif) ![[Internet]](/img-shared/nav-internet.gif) ![[Maths]](/img-shared/nav-math.gif) ![[Amiga]](/img-shared/nav-amiga.gif) ![[Windows NT]](/img-shared/nav-winnt.gif) ![[Amis]](/img-shared/nav-amis.gif)
Site créé le 16 janvier 1997
©1997 by TheRaphit
[www.theraphit.com]
|