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 E² 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 u₀ 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 ²,

est notée f ³, etc. On convient que f ^-k = (f ^k)^-1 et que f ⁰ = 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]

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 ²(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 R_f 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 R_f. Cette orbite, qui est donc un sous-ensemble de {1,2,...,n} est notée O_f (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, O_f (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 O_f (x) = O_f (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 (a₁,a₂,...,a_p) 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 [formule 15]

.

On va décomposer f en transpositions, déterminer sa signature et calculer f ¹⁹⁹⁷ (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 c₁ = (1,3,6) et c₂ = (2,10,9,8,5).

On décompose maintenant c₁ et c₂ en transpositions, en utilisant la formule du théorème 4 :

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 ¹⁹⁹⁷ 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 c₁ et c₂ 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 c₁ et c₂ puis le produit de ces carrés pour obtenir le résultat :

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 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.