Il est nécessaire de bien comprendre ce groupe pour introduire la notion de déterminant, c’est pourquoi nous faisons cet article dans un premier temps.
Prérequis
Définition
Soit E un ensemble. On appelle permutation une bijection \sigma : E \to E . On note S(E) l’ensemble des permutations de E. (S(E) , \circ ) est un groupe pour la composition.
Lorsque E = \{1 , \ldots, n \} , on appelle ce groupe, groupe symétrique et c’est surtout celui-ci que nous allons étudier. Le groupe symétrique d’ordre. nest noté S_n.
Le groupe des permutations est un groupe
Tout d’abord, nous allons montrer que le groupe des permutations est bien un groupe.
En effet,
- Le neutre est l’identité
- La bijection est bien associative : \forall \sigma_1, \sigma_2, \sigma_3 \in S(E) : (\sigma_1 \circ \sigma_2) \circ \sigma_3 = \sigma_1 \circ (\sigma_2 \circ \sigma_3)
- Toute bijection a un inverse : \sigma \circ \sigma^{-1} = \sigma^{-1} \circ \sigma
Celui-ci n’est pas abélien par contre.
Vocabulaire et propriétés
Le groupe symétrique est de cardinal n!
On note une permutation sous cette forme-là :
\sigma = \begin{pmatrix} 1 & 2 & \ldots & n \\ \sigma(1) & \sigma(2) & \ldots & \sigma (n)\end{pmatrix}Par exemple, si on définit
\sigma = \begin{pmatrix} 1 & 2 & 3& 4 & 5 \\ 4 & 1 & 2 & 3 & 5\end{pmatrix}cela signifie que
\left\{ \begin{array}{rl}
\sigma(1)& = 4\\
\sigma(2)& = 1\\
\sigma(3)& = 2\\
\sigma(4)& = 3\\
\sigma(5)& = 5\\
\end{array}\right.Support d’une permutation : On appelle support d’une permutation l’ensemble des éléments qui ne sont pas des points fixes. Par exemple, pour
\sigma = \begin{pmatrix} 1 & 2 & 3& 4 & 5 \\ 4 & 1 & 2 & 3 & 5\end{pmatrix} Le support de \sigma est \{1,2,3,4\} .
On appelle cycle, de longueur k s’il existe a_1, \ldots, a_k 2 à 2 distincts tels que a_1 est envoyé sur a_2 lui-même envoyé sur a_3 jusqu’à a_k et tel qu’ensuite a_k est envoyé sur a_1. Donc, on revient à la case départ. Un cycle pourra être noté (a_1 \ldots a_k). Attention, ne pas mettre de virgules, ce n’est pas un vecteur.
Toute permutation peut s’écrire comme un produit de cycles à support disjoints. C’est assez évident par construction. On prend un élément, on itère par \sigma jusqu’à retomber sur cet élément. C’est un premier cycle. Si le cycle est de longueur n, on s’arrête. SInon, on prend ensuite un autre élément qui n’était pas dans ce premier cycle et on refait pareil. On s’arrête lorsqu’on a parcouru tous les éléments.
Une permutation est dite circulaire si elle admet un cycle de longueur n. Une telle permutation pourra être notée (a_1 \ldots a_n).
Comme tout élément d’un groupe, on peut parler de l’ordre d’une permutation : o(\sigma ) = \min \{ k \in \N^* | \sigma^k = Id \} . Propriété : L’ordre de \sigma est égal au PPCM de l’ordre des cycles.
Une transposition est un cycle de longueur 2. On notre \tau_{ab} la transposition qui échange a et b. Notons que \tau_{ab} = \tau_{ba}.
Question : Combien il y a-t-il de transpositions dans S_n ?
Toute permutation est produit de transpositions. En effet, tout cycle de longueur k s’écrit comme un produit de k-1 transpositions. En effet, on a (a_1 \ldots a_k) = \tau_{a_1a_2} \ldots \tau_{a_{k-1}a_k}. Je vous laisse vérifier par vous-même !
Signature
Cette notion-là va être importante pour définir le déterminant. Un couple i< j est une inversion lorsque \sigma(i) > \sigma(j) . Notons I(\sigma) le nombre d’inversion d’une permutation \sigma.
On définit la signature d’une permutation, notée \varepsilon comme \varepsilon(\sigma) = (-1)^{I (\sigma)}. Une définition équivalente est
\varepsilon(\sigma) = \prod_{1\leq i < j \leq n } \dfrac{\sigma(i)-\sigma(j)}{i-j}Si \varepsilon(\sigma) = 1 on dit qu’une permutation est paire. Sinon, on dit qu’elle est impaire.
Remarque : L’ensemble des permutations paires est un sous-groupe des permutations. On l’appele groupe alterné.
Notons que les transpositions sont de signature -1. Notons aussi que \forall \sigma_1, \sigma_2 \in S_n , \varepsilon( \sigma_1 \circ \sigma_2) = \varepsilon(\sigma_1) \times \varepsilon( \sigma_2) . Cela se démontre bien par exemple avec l’écriture sous la forme d’un produit écrite ci-dessus.
On a alors, par récurrence et comme \sigma = \tau_1 \circ \ldots \circ \tau_n
\varepsilon(\sigma) = \varepsilon (\tau_1) \times \ldots \times \varepsilon(\tau_n) = (-1)^{n}Il suffit donc de compter le nombre de transpositions et la signature vaudra donc 1 si ce nombre est pair, 0 sinon. Les plus malins d’entre vous auront repéré que la décomposition en transpositions n’est pas unique, le cardinal de cette décomposition non plus. Par contre, la parité du cardinal ne change pas. La signature est donc bien définie en raisonnant de cette manière.
