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 [formule 1]. 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 [formule 2]. Si f et g sont deux permutations de {1,2,...,n}, la permutation composée [formule 3] est définie par [formule 4]. Cette loi n'est pas commutative, les permutations [formule 5] 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 à [formule 6]. Comme Id(x) = x, on a f[Id(x)] = f(x) mais comme on a aussi Id[f(x)] = f(x), on a donc [formule 7]. Id est donc l'élément neutre de la loi [formule 2].

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 [formule 8] et donc g est la permutation symétrique de f. On écrit g = f -1.

Plus généralement, la permutation [formule 8b] est notée f 2, [formule 8c] 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 [formule 2] devient donc un groupe. C'est le fameux groupe symétrique d'ordre n, que l'on note [Sn].

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 [Sn]. 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, [Sn] 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 [Sn], 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]

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]

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 à [Sn] : 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 [Sn].

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 [formule 11]. 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 [formule 12], 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 [Sn].

Théorème 1 : une permutation f de [Sn] 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 [formule 13] 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 [Sn] 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 [Sn]
Théorème 5 (signature) : il existe un et un seul morphisme non trivial de [(Sn, o)] sur [({-1,1},x)]. Il est donné par [formule 14]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 [epsilon], ensemble des permutations de signature égale à 1 est donc un groupe [An] appelé groupe alterné d'ordre n. C'est un sous-groupe de [Sn] 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 [Sn]. 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 [S10] définie par [formule 15].

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 [formule 16] 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]
[formule 18]
On en déduit alors que [formule 19].
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 [formule 21].
Mais la décomposition en cycles fournit aussi [formule 20]. On remarque que f est une permutation de [A10].

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 [formule 22]. 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 [formule 23].
De même [formule 24].
On vient de montrer que [formule 25]. 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]
[formule 27]
Tous calculs faits, on trouve [formule 28]

Applications du groupe symétrique

J'avais initialement prévu de ne faire qu'une seule page sur [Sn] 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 [Sn].
  • Page de garde : Introduction à [Sn] (cette même page)
  • Rassemblement de résultats divers relatifs à [Sn] (autres théorèmes et propriétés)
  • Applications de [Sn] en mathématiques
Les deux dernières pages seront en ligne plus tard.
[Revue][Mangas][Internet][Maths][Amiga][Windows NT][Amis]

Site créé le 16 janvier 1997
©1997 by TheRaphit

[www.theraphit.com]