Le groupe symétrique

Plan du chapitre "Déterminants"

Permutations de l’ensemble {E_n=\{1,\ldots,n\}}

Définition (groupe symétrique d'indice n)
Pour tout entier {n\ge1}, on note {E_n=\{1,\ldots,n\}}.
On appelle permutation de {E_n} toute bijection de {E_n} sur lui-même.
On note {\mathcal{S}_n} l’ensemble de toutes les permutations de {E_n}.
L’ensemble {\mathcal{S}_n} est un groupe pour la loi de composition, appelé groupe symétrique d’indice {n}.
Le groupe {\mathcal{S}_n} est d’ordre {n!} et il est non commutatif dès que {n\ge3}.

Remarque : on écrira {\sigma_2\sigma_1} (plutôt que {\sigma_2\circ\sigma_1}) pour désigner la composée de {\sigma_1} par {\sigma_2}.

Un élément {\sigma} de {\mathcal{S}_n} est représenté par {\sigma=\begin{pmatrix}1&2&\ldots&n\cr\sigma(1)&\sigma(2)&\ldots&\sigma(n)\end{pmatrix}}.

En particulier l’application identité, neutre du groupe {\mathcal{S}_n}, se note {\text{Id}=\begin{pmatrix}1&2&\ldots&n\cr1&2&\ldots&n\end{pmatrix}}.

Pour prendre un exemple, {\begin{pmatrix}1&2&3&4&5&6\cr3&5&1&4&6&2\end{pmatrix}} représente l’élément {\sigma} de {\mathcal{S}_6} défini par : {\sigma(1)=3,\ \sigma(2)=5,\ \sigma(3)=1,\ \sigma(4)=4,\ \sigma(5)=6,\ \sigma(6)=2}
On voit facilement que {\sigma^{-1}=\begin{pmatrix}1&2&3&4&5&6\cr 3&6&1&4&2&5\end{pmatrix}} (lire le tableau à partir de la deuxième ligne).

Si {n=1}, le groupe {\mathcal{S}_1} se réduit à l’application identité de {E_1=\{1\}} dans lui-même.

Si {n=2}, {\mathcal{S}_2=\{\text{Id},\sigma\}}, où {\sigma} est définie par : {\sigma(1)=2} et {\sigma(2)=1}.

Si {n=3}, {\mathcal{S}_3} est formé de six éléments : {\begin{array}{rll}\sigma_0=\text{Id}=\begin{pmatrix}1&2&3\cr1&2&3\end{pmatrix},& \sigma_1=\begin{pmatrix}1&2&3\cr1&3&2\end{pmatrix},& \sigma_2=\begin{pmatrix}1&2&3\cr3&2&1\end{pmatrix},\\\\ \sigma_3=\begin{pmatrix}1&2&3\cr2&1&3\end{pmatrix},& \sigma_4=\begin{pmatrix}1&2&3\cr2&3&1\end{pmatrix},& \sigma_5=\begin{pmatrix}1&2&3\cr3&1&2\end{pmatrix}=\sigma_4^2\end{array}}
Le groupe {(\mathcal{S}_3,\circ)} n’est pas commutatif : on vérifie par exemple que {\begin{cases}\sigma_1\,\sigma_3=\sigma_5\\\sigma_3\,\sigma_1=\sigma_4\end{cases}}

Cycles

Définition (les cycles sont des permutations particulières)
Soit {\sigma} un élément de {\mathcal{S}_n}, avec {n\ge2}. Soit {p} un entier de {\{2,\ldots,n\}}.
On dit que {\sigma} est un cycle de longueur {p} s’il existe {a_1,\ldots,a_p} distincts dans {\{1,\ldots,n\}} tels que :
— pour tout {k\in\{1,\ldots,p-1\}} on a {\sigma(a_k)=a_{k+1}}, et de plus {\sigma(a_p)=a_1}.
— pour tout {b} de {E_n\setminus\{a_1,\ldots,a_p\}}, {\sigma(b)=b}.
On dit alors que l’ensemble {\{a_1,\ldots,a_p\}} est le support du cycle {\sigma}.

Remarques

Le support d’un cycle {\sigma} est l’ensemble des éléments qui ne sont pas invariants par {\sigma}.
En général, on représente un cycle {\sigma} en écrivant {\sigma=\begin{pmatrix}a_1&a_2&\ldots&a_p\end{pmatrix}}.
Dans {\mathcal{S}_n}, un cycle de longueur {n} est appelé une permutation circulaire.

Exemples

  • Dans {\mathcal{S}_7}, la permutation {\sigma_1=\begin{pmatrix}1&2&3&4&5&6&7\cr5&6&3&1&2&4&7\end{pmatrix}} est le cycle {\begin{pmatrix}1&5&2&6&4\end{pmatrix}}.

    Cette dernière notation ne dit pas que {\sigma_1} est dans {\mathcal{S}_7}, mais qu’elle est dans {\mathcal{S}_n} pour tout {n\ge6} (en principe le contexte est clair, mais de toutes façons c’est sans grande importance).

    Le support de {\sigma_1} est {\{1,2,4,5,6\}} et ses points fixes sont {3} et {7}.

    On peut aussi écrire {\sigma_1=\begin{pmatrix}5&2&6&4&1\end{pmatrix}}, ou {\sigma_1=\begin{pmatrix}2&6&4&1&5\end{pmatrix}\ldots}, etc.

  • En revanche la permutation {\sigma_2=\begin{pmatrix}1&2&3&4&5&6&7&8\cr6&5&3&8&7&4&2&1\end{pmatrix}} n’est pas un cycle.

    Cependant on a visiblement {\sigma=s\, t=t\, s}, où {s=\begin{pmatrix}1&6&4&8\end{pmatrix}} et {t=\begin{pmatrix}2&5&7\end{pmatrix}}.

  • {\sigma_3=\begin{pmatrix}1&2&3&4&5&6&7\cr7&5&6&1&4&2&3\end{pmatrix}} est la permutation circulaire {\begin{pmatrix}1&7&3&6&2&5&4\end{pmatrix}}.
Proposition (inverse d'un cycle)
Si {\sigma} est le cycle {\begin{pmatrix}a_1&a_2&\ldots&a_p\end{pmatrix}} alors {\sigma^{-1}} est le cycle {\begin{pmatrix}a_p&a_{p-1}&\ldots&a_1\end{pmatrix}}.

Attention, les puissances d’un cycle ne sont pas toujours des cycles.

Si par exemple {\sigma=\begin{pmatrix}1&2&3&4&5&6\end{pmatrix}}, alors : {\sigma^2=\begin{pmatrix}1&3&5\end{pmatrix}\,\begin{pmatrix}2&4&6\end{pmatrix}\;\text{et}\;\sigma^3=\begin{pmatrix} 1&4\end{pmatrix}\,\begin{pmatrix} 2&5\end{pmatrix}\,\begin{pmatrix} 3&6\end{pmatrix}}
En revanche {\sigma^5} est le cycle {\begin{pmatrix}1&6&5&4&3&2\end{pmatrix}}.

On montre que si {\sigma} est un cycle de longueur {p}, alors : {\sigma^k} est un cycle {\Leftrightarrow k\wedge p=1}.

Proposition (calcul des puissances d'un cycle)
Soit {\sigma} un cycle de longueur {p\ge2}.
Alors {\sigma^p=\text{Id}} et, pour tout {k} de {\{1,\ldots,p-1\}}, {\sigma^k\ne\text{Id}}.
Pour tout {m\in\mathbb{Z}}, si {m=qp+r} est la division euclidienne de {m} par {p}, alors {\sigma^m=\sigma^r}.
Proposition (deux cycles à supports disjoints commutent)
Soit {\sigma_1} et {\sigma_2} deux cycles de {\mathcal{S}_n}.
On suppose que les supports de {\sigma_1} et {\sigma_2} sont disjoints. Alors {\sigma_2\,\sigma_1=\sigma_1\,\sigma_2}.

Plus généralement, soit {\sigma_1,\ldots,\sigma_m} une famille de {m} cycles de {\mathcal{S}_n}.
Si leurs supports sont disjoints deux à deux, alors les cycles {\sigma_k} commutent deux à deux.
Dans ce cas, et pour tout entier {k}, on peut alors écrire : {(\sigma_1\,\cdots\,\sigma_m)^k=\sigma_1^k\,\cdots\,\sigma_m^k}.

Transpositions

Définition (les transpositions sont les cycles de longueur 2)
Soit {n} un entier supérieur ou égal à {2}. Soit {\sigma} un élément de {\mathcal{S}_n}.
On dit que {\sigma} de {\mathcal{S}_n} est une transposition si {\sigma} est un cycle {\begin{pmatrix}a&b\end{pmatrix}} de longueur {2}.
Cela signifie qu’il existe {a,b} distincts dans {E_n} tels que {\begin{cases}\sigma(a)=b\;\;\text{et}\;\;\sigma(b)=a\\\forall\, c\notin\{a,b\},\;\sigma(c)=c\end{cases}}

Remarques

Une transposition est donc une permutation qui se contente d’échanger deux éléments.
On ne confondra pas les mots “permutation” et “transposition”.

Si {\tau=\begin{pmatrix} a& b\end{pmatrix}}, on a bien sûr : {\tau=\begin{pmatrix} b& a\end{pmatrix}}, {\;\tau^2=\text{Id}}, {\;\tau^{-1}=\tau}.

Soit {\tau_1=\begin{pmatrix} a& b\end{pmatrix}} et {\tau_2=\begin{pmatrix} c& d\end{pmatrix}} deux transpositions.

On a l’équivalence : {\tau_1\,\tau_2=\tau_2\,\tau_1\Leftrightarrow<br /> \begin{cases}\{a,b\}\cap\{c,d\}=\emptyset\cr\;\text{ou}\;\{a,b\}=\{c,d\}\end{cases}}

Dans {\mathcal{S}_n}, il y a {\displaystyle\binom{n}{2}=\dfrac{n(n-1)}2} transpositions (autant que de paires de {E_n}).

Décomposition en produit de cycles à supports disjoints

Proposition (décomposition en produit de cycles)
Toute permutation de {\mathcal{S}_n} (avec {n\ge2}) se décompose en un produit de cycles à supports deux à deux disjoints. Cette décomposition est unique à l’ordre près des facteurs.

Cette décomposition est dite commutative, car les cycles qui la composent commutent deux à deux.

Étude détaillée d’un exemple

Soit {\sigma=\begin{pmatrix}1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 &14\cr 10 & 5 & 9 & 4 & 14 & 3 & 1 & 11 & 12 & 7 & 13 & 6 & 2 & 8\end{pmatrix}}.
Décomposer {\sigma} en produit de cycles. Calculer {\sigma^{2014}}.
Cliquer ici pour voir (ou cacher) le corrigé
  Pour voir ce contenu, vous devez : 

Décomposition en produit de transpositions

Proposition (décomposition d'une permutation en produit de transpositions)
Tout cycle de {\mathcal{S}_n} peut s’écrire comme un produit de transpositions.
Il en découle que toute permutation de {\mathcal{S}_n} peut s’écrire comme un produit de transpositions.

Remarques

Il n’y a pas unicité de la décomposition d’une permutation en un produit de transpositions.

On observe par exemple que : {\begin{array}{rl}\sigma&=\begin{pmatrix}1&2&3\end{pmatrix}=\begin{pmatrix}1&2\end{pmatrix}\begin{pmatrix}2&3\end{pmatrix}\\\\&=\begin{pmatrix}1&2\end{pmatrix}\begin{pmatrix}1&3\end{pmatrix}\begin{pmatrix}1&2\end{pmatrix}\begin{pmatrix}1&3\end{pmatrix}=\begin{pmatrix}2&3\end{pmatrix}\begin{pmatrix}1&3\end{pmatrix}\end{array}}

Il y a une façon très simple de décomposer un cycle en produit de transpositions. En effet : {\begin{array}{l}\begin{pmatrix}a_1&a_2&a_3&\ldots&a_p\end{pmatrix}\\\\\quad=\begin{pmatrix}a_1&a_2\end{pmatrix}\begin{pmatrix}a_2&a_3\end{pmatrix}\cdots\begin{pmatrix}a_k&a_{k+1}\end{pmatrix}\cdots\begin{pmatrix}a_{p-1}&a_{p}\end{pmatrix}\end{array}}
Pour décomposer une permutation quelconque {\sigma} en un produit de transpositions, il est judicieux d’écrire la permutation {\sigma} comme un produit de cycles {\sigma_k} à supports disjoints, puis d’écrire chaque {\sigma_k} comme un produit de transpositions. Par exemple : {\begin{array}{rl}\sigma&=\begin{pmatrix}1&2&3&4&5&6&7&8\cr 4&7&3&8&6&2&5&1\end{pmatrix}=\begin{pmatrix}1&4&8\end{pmatrix}\begin{pmatrix}2&7&5&6\end{pmatrix}\\\\&=\begin{pmatrix}1&4\end{pmatrix}\begin{pmatrix}4&8\end{pmatrix}\begin{pmatrix}2&7\end{pmatrix}\begin{pmatrix}7&5\end{pmatrix}\begin{pmatrix}5&6\end{pmatrix}\end{array}}

Signature d’une permutation

Définition (signature d'une permutation)
Il existe une et une seule application {\varepsilon} de {\mathcal{S}_n} dans {\{-1,1\}} telle que :
— pour toute transposition {\tau}, on a : {\varepsilon(\tau)=-1}.
— pour toutes permutations {\sigma} et {\sigma'}, on a : {\varepsilon(\sigma \sigma')=\varepsilon(\sigma)\varepsilon(\sigma')}.
L’application {\varepsilon} est appelée signature.

De par la définition (et parce que toute permutation peut s’écrire au moins d’une manière comme un produit de transpositions), il est clair que {\varepsilon(\sigma)} est toujours égal {1} ou à {-1}.

Définition (permutations paires ou impaires)
Soit {\sigma} un élément de {\mathcal{S}_n}, avec {n\ge2}.
On dit que {\sigma} est une permutation paire si {\varepsilon(\sigma)=1}.
On dit que {\sigma} est une permutation impaire si {\varepsilon(\sigma)=-1}.

Propriétés immédiates

  • Par définition de la signature, les transpositions sont des permutations impaires.
  • L’application identité est une permutation paire (elle est le carré d’une transposition quelconque).
  • Une permutation {\sigma} et son inverse {\sigma^{-1}} ont la même signature.
  • La composée de deux permutations de même parité est une permutation paire.
    La composée de deux permutations de parités opposées est une permutation impaire.
  • Si {\sigma} est une permutation paire, alors pour tout {p} de {\mathbb{Z}} la permutation {\sigma^p} est paire.
    Si {\sigma} est une permutation impaire, alors la permutation {\sigma^p} a la parité de l’entier relatif {p}.
Proposition (signature et décompositions en produits de transpositions)
Soit {\sigma} une permutation de l’ensemble {E_n=\{1,2,\ldots,n\}}. La parité de {\sigma} est celle du nombre de facteurs dans toute décomposition de {\sigma} en produit de transpositions.

Dire qu’une permutation {\sigma} est paire (resp. impaire), c’est donc dire que les décompositions de {\sigma} en produits de transpositions comportent un nombre pair (resp. impair) de facteurs.

Proposition (nombre de permutations paires, ou impaires)
Dans {\mathcal{S}_n}, il y a autant de permutations paires que de permutations impaires, c’est-à-dire {\dfrac{1}{2}\,n!}.
Proposition (signature d'un cycle)
La signature d’un cycle {\sigma} de longueur {p} est {\varepsilon(\sigma)=(-1)^{p-1}}. Autrement dit :

  • un cycle de longueur paire est une permutation impaire.
  • un cycle de longueur impaire est une permutation paire.

Pour calculer la signature d’un élément {\sigma} de {\mathcal{S}_n}, le plus simple est souvent de décomposer {\sigma} en cycles à supports disjoints {\sigma=\sigma_1\circ\sigma_2\circ\cdots\circ\sigma_p} et d’écrire {\varepsilon(\sigma)=\varepsilon(\sigma_1)\,\varepsilon(\sigma_2)\cdots\varepsilon(\sigma_p)}.

Par exemple : {\sigma=\begin{pmatrix}1&2&3&4&5&6&7&8\cr 4&7&3&8&6&2&5&1\end{pmatrix}=\sigma_1\circ\sigma_2} avec {\begin{cases}\sigma_1=\begin{pmatrix}1&4&8\end{pmatrix}\\\sigma_2=\begin{pmatrix}2&7&5&6\end{pmatrix}\end{cases}}.

On a {\varepsilon(\sigma_1)=1} et {\varepsilon(\sigma_2)=-1}, donc {\varepsilon(\sigma)=-1} : la permutation {\sigma} est impaire.

Page suivante : formes n-linéaires alternées