Support et Ordre d’une Permutation
Deux notions clés pour comprendre la structure d’une permutation sont son support (les éléments qu’elle déplace effectivement) et son ordre (le nombre de fois qu’il faut l’appliquer pour revenir à l’état initial). La décomposition en cycles disjoints est l’outil idéal pour déterminer ces deux propriétés.
Le support d’une permutation $\sigma \in \mathcal{S}_n$ est l’ensemble des éléments de $\{1, \dots, n\}$ qui ne sont pas des points fixes de $\sigma$. C’est l’ensemble des points qui sont effectivement déplacés par la permutation. $$ \text{supp}(\sigma) = \{ k \in \{1, \dots, n\} \mid \sigma(k) \neq k \} $$
L’ordre d’une permutation $\sigma$, noté $o(\sigma)$, est l’ordre de $\sigma$ en tant qu’élément du groupe $(\mathcal{S}_n, \circ)$. C’est le plus petit entier $k \ge 1$ tel que $\sigma^k = Id$, où $Id$ est la permutation identité.
L’ordre d’une permutation est le PPCM (Plus Petit Commun Multiple) des longueurs de ses cycles dans sa décomposition en cycles à supports disjoints.
Exemple d’Application
Reprenons la permutation $\sigma \in \mathcal{S}_8$ définie par : $$ \sigma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 3 & 8 & 6 & 1 & 5 & 7 & 4 & 2 \end{pmatrix} $$ Sa décomposition en cycles à supports disjoints est $\sigma = (1 \ 3 \ 6 \ 7 \ 4) \circ (2 \ 8)$.
-
Support : Le seul point fixe est 5. Le support de $\sigma$ est donc l’ensemble des points qui bougent :
$\text{supp}(\sigma) = \{1, 2, 3, 4, 6, 7, 8\}$. -
Ordre : Le premier cycle est de longueur 5, le second est de longueur 2. L’ordre de $\sigma$ est donc :
$o(\sigma) = \text{ppcm}(5, 2) = 10$.
Cela signifie qu’il faut appliquer $\sigma$ 10 fois de suite pour que chaque élément retrouve sa place initiale.
Autre exemple : Soit $\tau = (1 \ 4 \ 5) \circ (2 \ 9) \circ (3 \ 7 \ 8 \ 6) \in \mathcal{S}_9$.
Les longueurs des cycles sont 3, 2 et 4. L’ordre de $\tau$ est $o(\tau) = \text{ppcm}(3, 2, 4) = 12$.