Le Groupe Symétrique

I. Permutations d'un ensemble fini

II. Etude des groupes symétriques

III. Signature d'une permutation

I. Permutations d'un ensemble fini

• Soit X un ensemble fini.
  Soit B(X) l'ensemble des bijections de X dans X, c'est-à-dire l'ensemble des permutations de X.
  On note o la loi de composition entre deux permutations; c'est une loi de composition interne.

• Proposition I.1

  (B(X), o) est un groupe.
  

  Voir démonstration
  

• Soient X et Y deux ensembles de même cardinal.
  

  Proposition I.2

  B(X) et B(Y) sont isomorphes.
  

  Voir démonstration
  

  On en déduit que si X est un ensemble fini de cardinal n, B(X) est alors isomorphe à B({1, 2, ..., n}).
  Ce dernier résultat nous permet de nous restreindre à l'étude de ces ensembles B({1, 2,..., n}), appelés groupes symétriques d'ordre n et notés S_n.
  

II. Etude des groupes symétriques

- Généralités

• Proposition II.1

  Le cardinal de S_n est n!

  Voir démonstration
  

• Proposition II.2
  

  (S_n, o) est un groupe non commutatif pour n > 2
  

  Soit s S_n. On note usuellement s =
  

- Décomposition d'une permutation en cycles

• Définitions

  Soient a₁, .., a_k, k éléments distincts de [1..n].

  On appelle c, cycle de S_n de support S = {a₁,...,a_k}, la permutation qui vérifie :

  " x Ï S_n , c(x) = x

  x S_n , i [1..k] / x = a_i.

  Si i = k, on pose c(x) = a₁.

  Sinon on pose c(x) = a_i+1.

  On le note c = {a₁, ..., a_k}.
  

  Le cardinal de son support est appelé la longueur du cycle.
  

• Propriétés des cycles
  

  Proposition II.3
  Deux cycles de supports disjoints commutent.
  

  Voir démonstration
  

  Orbite d'un élément

  Soit p S_n.

  Soit a {1, ..., n}

  On appelle orbite de a suivant p l'ensemble O_p(a) = {p^k(a), k Z}.

  Il vient qu'une permutation est un cycle si et seulement si elle ne possède au plus qu'une seule orbite non réduite à un seul élément.

  Considérons la relation binaire suivante :

  x R_py m Z / p^m(x) = y

  C'est une relation d'équivalence.

  Voir démonstration.
  

  On s'aperçoit alors que la classe d'un élément a est son orbite suivant p.

  Soit m l'ordre de a.

  On a alors :

  O_p(a) = {a, p(a), ..., p^k-1(a) }
  

  Voir démonstration
  

  D'après l'étude menée sur les relations d'équivalence, on sait que les classes d'équivalence, c'est à dire ici les orbites, forment alors une partition de {1..n}.

  {1..n} est donc partitionné en k orbites O₁, ..., O_k.

  On pose c_i le cycle de support O_i, tel que

  x O_i, c(x) = p(x).

  ( C'est-à-dire c_i = (a_i, p(a_i), ..., (a_i) ). )

  Note : Si l'orbite O_i est réduite à un singleton, on a c_i = Id.
  

  Comme O₁, ..., O_k sont disjoints, les supports de c₁, ..., c_k sont disjoints deux à deux et c₁, ..., c_k commutent donc entre eux d'après la proposition II.3.

  Posons f = c₁ o c₂ o ... o c_k.

  Soit x [1..n].

  D'après la caractérisation des orbites comme classes d'équivalence, il existe un unique j [1..k] tel que x O_j.

  Comme les c₁, ..., c_k commutent on peut écrire f = c_j o c₁ o ... o c_k.

  Par construction des c_i, si i j alors c_i(x) = x.

  On a alors f(x) = c_j(x) = p(x).

  Comme cette égalité est vraie quelque soit x appartenant à [1..n], il vient :

  f = p.

  La permutation p peut donc se décomposer en produit des cycles c₁, ..., c_k.
  

  Supposons qu'il existe une autre décomposition en produit de cycles à supports disjoints : p = c'₁o ...o c'_k. Comme cette décomposition est différente de la première, il existe un élément x de [1..n] et deux cycles c_h et c'_k telles que

  x O_h

  x O_k'

  c_h c'_k donc Oh O'k

  Il existe donc y appartenant à O'k et non à Oh.

  Comme c'k est un cycle de support O'k, il existe d N tel que (c'k)d(x) = y.

  Comme les c'₁, ..., c'_k sont à support disjoints,

  p^d(x) = (c'₁ o ...o c'_k)^d(x) = (c'_k)^d(x) = y O_h

  et p^d(x) = (c₁o ...o c_k)^d(x) = (c_h)^d(x) O_h

  On aboutit donc à une absurdité : la décomposition est unique.

  D'où :
  

  Théorème :

  Toute permutation se décompose en un produit de cycles à supports disjoints. Cette décomposition est alors unique à l'ordre près.

- Décomposition d'une permutation en produit de transpositions.

Définition

On appelle transposition tout cycle de longueur 2.

Cela correspond à la permutation permutation de deux éléments.

t_i,j =


Proposition II.4

Soit c un cycle de longueur k.

Tout cycle se décompose en produit de (k-1) transpositions.


Voir démonstration


D'après le théorème de la partie b, toute permutation se décompose en produit

de cycles qui, d'après la proposition précédente, se décomposent en produit de transpositions. Il vient donc,


Théorème :

Toute permutation se décompose en un produit de transpositions.

- Ordre d'une permutation

Rappel

On rappelle que, d'après le cours sur les groupes, l'ordre d'une permutation p sera le plus petit entier d strictement positif tel que :

p^d = Id.


Ouvrir le cours sur les groupes.


Ordre d'un cycle


Proposition II.5


Soit c un cycle de support S.

Alors l'ordre de c est le cardinal de S.


Voir démonstration


• Ordre d'une permutation
  

  Proposition II.6
  

  Soit p S_n. L'ordre de p est le P.P.C.M. des longueurs des cycles de sa décomposition (en produit de cycles à supports disjoints).
  

  Voir démonstration
  

III. Signature d'une permutation

a. Inversion

On dit qu'une permutation p présente en (i, j), avec i < j, une inversion si

p(j) < p(i).

Comme j i, on a p(j) p(i), et il vient :

Un permutation p présente en (i, j), avec i < j, une inversion si et seulement si

< 0

Exemples :

p = Id.

Il n'y a aucune inversion.


p = .

Il y a inversions. C'est le maximum que l'on puisse obtenir car, par construction, si i < j, p(i) > p(j) : Tous les couples présentent une inversion.


p = t_jk (avec j<k). Il y a 2k - 2j -1 inversions.

Voir démonstration


b. Définition

Soit p Sn.

On appelle signature de p, notée e(p), le produit :




c. Propriétés

Signe de e(p).

Comme j i, p(j) p(i) donc aucun des termes du produit n'est nul.

D'autre part, si on étudie le signe de chaque facteur, on s'aperçoit qu'il est négatif lorsqu'il y a une inversion et positif sinon.

Finalement, il vient :


Proposition III.1


Soit p une permutation.

Soit m le nombre d'inversions de p.

Alors, le signe de e(p) est celui de (-1)^m.


Maintenant que nous connaissons son signe, nous pouvons calculer la valeur absolue de e(p).


Proposition III.2


|e(p)| = 1


Voir démonstration

Nous venons donc de voir que la signature d'une permutation était un élément de {-1; 1}. Nous allons maintenant chercher à en calculer sa valeur exacte (c'est à dire son signe). Pour cela nous allons dégager une propriété fondamentale de cette application.


Proposition III.3


La signature est un morphisme de groupe de (S_n, o) dans ({-1; 1}, x).


Voir démonstration


Comme la signature est un morphisme de groupe, un moyen de calculer la signature d'une permutation est de calculer celles des cycles de sa décomposition (Voir théorème du II.b).

D'après la proposition II.4, nous savons que tout cycle se décompose en produit de transpositions.

L'étude des exemples dans la partie III.a nous a montré qu'une transposition présentait un nombre impair d'inversions, donc, d'après la proposition III.1, sa signature vaut -1.


Proposition III.4


La signature d'une transposition est -1.


On a alors immédiatement la signature d'un cycle de longueur k, car on sait qu'il peut se décomposer en un produit de k-1 transposition. Comme la signature est un morphisme, il vient :


Proposition III.5


Soit c un cycle de longueur k.

La signature de c vaut (-1)^k-1.

La signature d'une permutation quelconque de S_n est alors le produit des signatures des cycles de sa décomposition (en produit de cycles).

Soit k le nombre d'orbites (y compris celles réduites à un singleton), de cardinal m_j.

Il vient alors :

e(p) = =

Comme = n, on a:


Proposition III.6


Soit p S_n.

Soit k le nombre d'orbites de p.

Alors e(p) = (-1)^{n - k}.


d. Etude de A_n.

Définition

On appelle groupe alterné d'indice n le noyau de la signature dans S_n, et on le note A_n. C'est-à-dire A_n = e^-1({1}) = Ker e.


Comme c'est le noyau d'un morphisme de groupe, A_n est un sous-groupe distingué.


Voir démonstration.


Proposition III.7

Card A_n = .

Voir démonstration


Proposition III.8


Soit n > 2.

A_n est engendré par les cycles de longueur 3.


Voir démonstration

---

Première version : 01/12/96
Auteur : Pascal Audoux
Sources :  Cours de Mathématiques Supérieures de M. Coulet (Saint-Louis, HX5 94-95).
Relecteurs :