cours/orbites du groupe symétrique.md

aliases

aliases
σ-orbites

up:: groupe symétrique, orbite d'un groupe #s/maths/algèbre

[!definition]+ $\sigma$-orbites Soit \sigma \in \mathfrak{S}_{n}, on considère la relation suivante sur \{ 1,\dots,n \} : i \mathcal{R} j \iff \exists k \in \mathbb{Z},\quad \sigma^{k}(i) = j C'est une relation d'équivalence :

• i \mathcal{R} j \implies j \mathcal{R} i car \sigma est une bijection
• i \mathcal{R} i car \sigma^{0} = \mathrm{id}
• i\mathcal{R}j\mathcal{R}k \implies i \mathcal{R} k Les classes d'équivalence par cette relation sont appelés les $\sigma$-orbites

[!definition] orbites du groupe symétrique Soit \sigma \in \mathfrak{S}_{n} Soit i \in \{ 1 ,\dots, n \} On note \mathrm{Orb}_{\sigma}(i) := \{ \sigma^{k}(i) \mid k \in \mathbb{Z} \} la $\sigma$-orbite contenant i

Propriétés

[!proposition]+ La réunion disjointe des orbites donne [\![1; n]\!] \displaystyle\{ 1,\dots, n \} = \bigsqcup_{\substack{\Omega \text{ est une}\\ \sigma-\text{orbite}}} \Omega

[!proposition]+ Ordre d'une permutation en un point Soient \sigma \in \mathfrak{S}_{n} et i \in \{ 1 ,\dots, n \} Soit N := \min \{ k \in \mathbb{N}^{*} \mid \sigma^{k}(i) = i \} On a :

\mathrm{Orb}_{\sigma} (i) = \{ i, \sigma(i), \sigma^{2}(i), \dots, \sigma^{N-1}(i) \}

et donc \#\mathrm{Orb}_{\sigma}(i) = N

• I N = \#\mathrm{Orb}_{\sigma}(i) est appelé l'ordre de \sigma en $\mathbf{i}$

[!proposition]+ Soient \sigma \in \mathfrak{S}_{n} et i \in \{ 1 ,\dots, n \} Soit N = \#\mathrm{Orb}_{\sigma}(i) l'ordre de \sigma en i Soient 0 \leq k \leq l < N tels que \sigma^{k}(i) = \sigma^{l}(i) Alors \boxed{k = l}

[!démonstration]- Démonstration On a i = \sigma^{l-k}(i) Or, on a l - k \geq 0 donc si l - k > 0, on a l - k \geq N, ce qui est impossible car \begin{cases} l < N\\ k \geq 0 \end{cases} De là suit que l - k = 0, c'est-à-dire l = k

Exemples

[!example] Exemple Soit \sigma = \begin{pmatrix} 1&2&3&4&5&6\\ 2&1&3&6&4&5\end{pmatrix} on a :

• \mathrm{Orb}_{\sigma}(1) = \mathrm{Orb}_{\sigma}(2) = \{ 1, 2 \}
• \mathrm{Orb}_{\sigma}(3) = \{ 3 \}
• \mathrm{Orb}_{\sigma}(4) = \mathrm{Orb}_{\sigma}(5) = \mathrm{Orb}_{\sigma}(6) = \{ \underbracket{4}_{\sigma^{3}(4)}, \underbracket{5}_{\sigma^{2}(4)}, \underbracket{6}_{\sigma(4)}\}