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é
 Vous devez être abonné(e) et connecté(e) au site pour voir ce contenu 

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