105 Groupe des permutations d’un ensemble fini. Applications.

Groupe des permutations d’un ensemble fini. Applications.

algebra

Pour toute cette leçon, on fixe un entier $n \geq 1$ .

Généralités

Définitions

Définition 1

Soit $E$ un ensemble. On appelle groupe des permutations de $E$ le groupe des bijections de $E$ dans lui-même. On le note $S (E)$ .

Notation 2

Si $E = [[1, n]]$ , on note $S (E) = S_{n}$ , le groupe symétrique à $n$ éléments.

Notation 3

Soit $σ \in S_{n}$ . On note : $σ = (1 σ (1) 2 σ (2) \dots \dots n σ (n))$ pour signifier que $σ$ est la bijection $σ : k \mapsto σ (k)$ .

Le théorème suivant justifie que, pour un ensemble à $n$ éléments, on peut se contenter d’étudier $S_{n}$ en lieu et place de $S (E)$ .

Théorème 4

Soient $E$ et $F$ deux ensembles en bijection. Alors $S (E)$ et $S (F)$ sont isomorphes.
$∣ S_{n} ∣ = n!$

p. 53

Théorème 5

Théorème de CayleyTout groupe $G$ est isomorphe à un sous-groupe de $S (G)$ .

Orbites et cycles

p. 41

Définition 6

Soit $σ \in [[1, n]]$ . On a une action naturelle de $H = ⟨ σ ⟩$ sur $[[1, n]]$ définie par $\forall k \in Z, \forall j \in [[1, n]], σ^{k} \cdot j = σ^{k} (j)$ Les orbites pour cette action sont les $H \cdot j = {σ (j) ∣ j \in [[1, n]]}$ . On les note $O_{σ} (j)$ .

Remarque 7

Les orbites selon $σ$ sont décrites par la relation $x \sim y ⟺ \exists k \in Z tel que y = σ^{k} (x)$
Une orbite $O_{σ} (j)$ est réduite à un point si et seulement si $σ (j) = j$ .

p. 37

Définition 8

Soient $l \leq n$ et $i_{1}, \dots, i_{l} \in [[1, n]]$ des éléments distincts. La permutation $γ \in S_{n}$ définie par $γ (j) = ⎩ ⎨ ⎧ j i_{k + 1} i_{1} si j \in / {i_{1}, \dots, i_{l}} si j = i_{k} avec k < l si j = i_{l}$ et notée $(i_{1} \dots i_{l})$ est appelée cycle de longueur $l$ et de support ${i_{1}, \dots, i_{l}}$ . Un cycle de longueur $2$ est une transposition.

p. 42

Proposition 9

Une permutation $σ$ est cycle si et seulement s’il n’y a qu’une seule orbite $O_{σ} (j)$ non réduite à un point.

Remarque 10

La composée de deux cycles n’est pas un cycle en général.

Exemple 11

Avec $σ = (1234) \in S_{4}$ , on a $σ^{2} = (13243142)$ qui n’est pas un cycle.

Proposition 12

L’ordre d’un cycle est égal à sa longueur.

[ULM21]
p. 56

Proposition 13

Soient $σ$ et $τ$ deux cycles de $S_{n}$ dont on note respectivement $Supp (σ)$ et $Supp (τ)$ les supports. Si $Supp (σ) \cap Supp (τ) = \emptyset$ , alors $Supp (σ τ) = Supp (σ) \cup Supp (τ)$ et dans ce cas :

$σ τ = τ σ$ .
$σ τ = id ⟹ σ = τ = id$ .

Théorème 14

Toute permutation de $S_{n}$ s’écrit de manière unique (à l’ordre près) comme produit de cycles dont les supports sont deux à deux disjoints.

Exemple 15

$(122435415366) = (124) (35)$

Définition 16

On appelle type d’une permutation $σ \in S_{n}$ et on note $[l_{1}, \dots, l_{m}]$ la liste des cardinaux $l_{i}$ des orbites dans $[[1, n]]$ de l’action du groupe $⟨ σ ⟩$ sur $[[1, n]]$ , rangée dans l’ordre croissant.

Proposition 17

Une permutation de type $[l_{1}, \dots, l_{m}]$ a pour ordre $ppcm (l_{1}, \dots, l_{m})$ .

Exemple 18

La permutation de l’15 est d’ordre $6$ .

Signature

Définition 19

Soit $σ \in S_{n}$ . On appelle signature de $σ$ , notée $ϵ (σ)$ le nombre rationnel $ϵ (σ) = i \neq = j \prod \frac{σ ( i ) - σ ( j )}{i - j}$

Exemple 20

$ϵ ((12)) = - 1$

Proposition 21

$ϵ : S_{n} \to Q^{*}$ est un morphisme de groupes. Pour une permutation $σ \in S_{n}$ , on a les propriétés suivantes :

Si $σ$ est un transposition, $ϵ (σ) = - 1$ .
Si $l$ est le nombre de transpositions qui apparaît dans une décomposition de $σ$ en produit de transpositions, alors $ϵ (σ) = (- 1)^{l}$ .
Si $σ$ est de type $[l_{1}, \dots, l_{m}]$ , alors $ϵ (σ) = (- 1)^{l_{1} + \dots + l_{m} - m}$ .

En particulier, si $n \geq 2$ , l’image de $ϵ$ est le sous-groupe ${\pm 1}$ de $Q^{*}$ .

[PEY]
p. 20

Proposition 22

Le seul morphisme non trivial de $S_{n}$ dans $C^{*}$ est $ϵ$ .

[ULM21]
p. 64

Définition 23

Soit $σ \in S_{n}$ . Si $ϵ (σ) = 1$ , on dit que $σ$ est paire. Sinon, on dit qu’elle est impaire.
Le noyau de $ϵ$ (constitué donc des permutations paires) est un sous-groupe distingué de $S_{n}$ appelé groupe alterné et noté $A_{n}$ .

Proposition 24

Pour $n \geq 2$ , $∣ A_{n} ∣ = \frac{n !}{2}$

Structure

Conjugaison

p. 60

Proposition 25

Deux permutations $σ$ et $τ$ de $S_{n}$ sont conjuguées si et seulement si elles sont du même type. En particulier, pour $ω \in S_{n}$ et tout cycle $(i_{1} \dots i_{l}) \in S_{n}$ , on a : $ω (i_{1} \dots i_{l}) ω^{- 1} = (ω (i_{1}) \dots ω (i_{l}))$

Exemple 26

Les types possibles d’une permutation de $S_{4}$ sont $[1]$ (l’identité), $[2]$ (les transpositions), $[2, 2]$ (les doubles transpositions), $[3]$ (les $3$ -cycles) et $[4]$ (les $4$ -cycles) : on a $5$ classes de conjugaison de tailles respectives $1$ , $6$ , $3$ , $8$ et $6$ .

[PER]
p. 13

Proposition 27

Pour tout $n \geq 3$ , $Z (S_{n}) = {σ \in S_{n} ∣ \forall τ \in S_{n}, σ τ = τ σ} = {id}$ .

p. 15

Lemme 28

Les $3$ -cycles sont conjugués dans $A_{n}$ pour $n \geq 5$ .

Générateurs

[ROM21]
p. 44

Proposition 29

$S_{n}$ est engendré par les transpositions. On peut même se limiter aux transpositions de la forme $(1 k)$ ou encore $(k k + 1)$ (pour $k \leq n$ ).
$S_{n}$ est engendré par $(12)$ et $(1 \dots n)$ .

Exemple 30

Pour $σ = (12345) (67)$ , on a $σ = (12) (23) (34) (45) (67)$ .

Proposition 31

$A_{n}$ est engendré par les $3$ -cycles pour $n \geq 3$ .

Simplicité

[PER]
p. 15

Lemme 32

Les $3$ -cycles sont conjugués dans $A_{n}$ pour $n \geq 5$ .

[ROM21]
p. 49

Lemme 33

Le produit de deux transpositions est un produit de $3$ -cycles.

[PER]
p. 28

simplicite-du-groupe-alterne

Théorème 34

$A_{n}$ est simple pour $n \geq 5$ .

Corollaire 35

Le groupe dérivé de $A_{n}$ est $A_{n}$ pour $n \geq 5$ , et le groupe dérivé de $S_{n}$ est $A_{n}$ pour $n \geq 2$ .

Corollaire 36

Pour $n \geq 5$ , les sous-groupes distingués de $S_{n}$ sont $S_{n}$ , $A_{n}$ et ${id}$ .

Corollaire 37

Soit $H$ un sous-groupe d’indice $n$ de $S_{n}$ . Alors, $H$ est isomorphe à $S_{n - 1}$ .

Applications

Déterminant

[GOU21]
p. 140

Soit $K$ un corps et soit $E$ un espace vectoriel de dimension $n$ sur $K$ .

Définition 38

Soient $E_{1}, \dots, E_{p}$ et $F$ des espaces vectoriels sur $K$ et $f : E_{1}, \dots, E_{p} \to F$ .

$f$ est dite $p$ -linéaire si en tout point les $p$ applications partielles sont linéaires.
Si $f$ est $p$ -linéaire et si $E_{1} = \dots = E_{p}$ ainsi que $F = K$ , $f$ est une forme $p$ -linéaire. On note $L_{p} (E, K)$ l’ensemble des formes $p$ -linéaires sur $E$ .
Si de plus $f (x_{1}, \dots, x_{p}) = 0$ dès que deux vecteurs parmi les $x_{i}$ sont égaux, alors $f$ est dite alternée.

Exemple 39

En reprenant les notations précédentes, pour $p = 2$ , $f$ est bilinéaire.

Proposition 40

$L_{p} (E, K)$ est un espace vectoriel et, $dim (L_{p} (E, K)) = ∣ dim (E) ∣^{p}$ .

Théorème 41

L’ensemble des formes $p$ -linéaires alternées sur $E$ est un $K$ -espace vectoriel de dimension $1$ . De plus, il existe une unique forme $p$ -linéaire alternée $f$ prenant la valeur $1$ sur une base $B$ de $E$ . On note $f = det_{B}$ .

Définition 42

$det_{B}$ est l’application déterminant dans la base $B$ . En l’absence d’ambiguïté, on s’autorise à noter $det = det_{B}$ .

Proposition 43

Soit $B = (e_{1}, \dots, e_{n})$ une base de $E$ . Si $x_{1}, \dots, x_{n} \in E$ ( $\forall i \in [[1, n]]$ , on peut écrire $x_{i} = \sum_{j = 1}^{n} x_{i, j} e_{j}$ ), on a la formule $det_{B} (x_{1}, \dots, x_{n}) = \sum_{σ \in S_{n}} ϵ (σ) \prod_{i = 1}^{n} x_{i, σ (i)}$ .

Corollaire 44

Soit $B$ une base de $E$ .

Si $B^{'}$ est une autre base de $E$ , alors $det_{B^{'}} = det_{B^{'}} (B) det_{B}$ .
Une famille de vecteurs est liée si et seulement si son déterminant est nul dans une base quelconque de $E$ .
Soient $A, B \in M_{n} (K)$ , alors $det_{B} (A B) = det_{B} (A) det_{B} (B)$ .
Soit $A \in M_{n} (K)$ , alors $det_{B} (A) = det_{B} ((^{t} A)$ et pour tout $λ \in K$ , $det_{B} (λ A) = λ^{n} det_{B} (A)$ .
Si on effectue une permutation $σ \in S_{n}$ sur les colonnes d’une matrice $A$ , alors le déterminant de $A$ est multiplié par $ϵ (σ)$ .

[I-P]
p. 203

Notation 45

Soit $a \in F_{p}$ . On note $(\frac{a}{p})$ le symbole de Legendre de $a$ modulo $p$ .

Lemme 46

Soient $p \geq 3$ un nombre premier et $V$ un espace vectoriel sur $F_{p}$ de dimension finie. Les dilatations engendrent $GL (V)$ .

theoreme-de-frobenius-zolotarev

Théorème 47

Théorème de Frobenius-Zolotarev. Soient $p \geq 3$ un nombre premier et $V$ un espace vectoriel sur $F_{p}$ de dimension finie. $\forall u \in GL (V), ϵ (u) = (\frac{det ( u )}{p})$ où $u$ est vu comme une permutation des éléments de $V$ .

Matrices de permutation

[ROM21]
p. 54

Soit $K$ un corps et soit $E$ un espace vectoriel de dimension $n$ sur $K$ .

Définition 48

À tout $σ \in S_{n}$ on associe la matrice de passage de la base canonique $(e_{i})_{i \in [[1, n]]}$ à la base $(e_{σ} (i))_{i \in [[1, n]]}$ que l’on note $P_{σ}$ : c’est la matrice de permutation associée à $σ$ .

Remarque 49

En reprenant les notations précédentes, $\forall j \in [[1, n]]$ , $P_{σ} e_{j} = σ (e_{j})$ .

Proposition 50

$σ \mapsto P_{σ}$ est un morphisme de groupes injectif de $S_{n}$ dans $GL_{n} (K)$ . De plus, on a $det (P_{σ}) = ϵ (σ)$

Corollaire 51

Tout groupe fini d’ordre $n$ est isomorphe à un sous groupe de $GL_{n} (F_{p})$ pour un premier $p \geq 2$ .

Polynômes symétriques

[GOU21]
p. 83

Soit $K$ un corps de caractéristique différente de $2$ .

Définition 52

Soit $P \in K [X_{1}, \dots, X_{n}]$ . On dit que $P$ est symétrique si $\forall σ \in S_{n}, P (X_{σ (1)}, \dots, X_{σ (n)}) = P (X_{1}, \dots, X_{n})$

Exemple 53

Dans $R [X]$ , le polynôme $X Y + Y Z + Z X$ est symétrique.

Définition 54

On appelle polynômes symétriques élémentaires de $A [X_{1}, \dots, X_{n}]$ les polynômes noté $Σ_{p}$ où $p \in [[1, n]]$ définis par $Σ_{p} = 1 \leq i_{1} < \dots < i_{p} \leq n \sum X_{i_{1}} \dots X_{i_{p}}$

Exemple 55

$Σ_{1} = X_{1} + \dots + X_{n}$ .
$Σ_{2} = \sum_{1 \leq i < j \leq n} X_{i} X_{j}$ .
$Σ_{n} = X_{1} \dots X_{n}$ .

Remarque 56

Si $P \in A [X_{1}, \dots, X_{n}]$ , alors $P (Σ_{1} (X_{1}, \dots, X_{n}), \dots, Σ_{n} (X_{1}, \dots, X_{n}))$ est symétrique. Et la réciproque est vraie.

Théorème 57

Théorème fondamental des polynômes symétriquesSoit $P \in A [X_{1}, \dots, X_{n}]$ un polynôme symétrique. Alors, $\exists! Φ \in A [X_{1}, \dots, X_{n}] tel que Φ (Σ_{1}, \dots, Σ_{n})$

Exemple 58

$P = X^{3} + Y^{3} + Z^{3}$ s’écrit $P = Σ_{1}^{3} - 3 Σ_{1} Σ_{2} + 3 Σ_{3}$ .

p. 64

Application 59

Relations coefficients - racines. Soit $P = a_{0} X^{n} + \dots + a_{n} \in K [X]$ avec $a_{0} \neq = 0$ scindé sur $K$ , dont les racines (comptées avec leur ordre de multiplicité) sont $x_{1}, \dots, x_{n}$ . Alors $\forall p \in [[1, n]], Σ_{p} (x_{1}, \dots, x_{n}) = (- 1)^{p} \frac{a _{p}}{a _{0}}$ En particulier,

$Σ_{1} (x_{1}, \dots, x_{n}) = \sum_{i = 1}^{n} x_{i} = - \frac{a _{1}}{a _{0}}$ .
$Σ_{n} (x_{1}, \dots, x_{n}) = \prod_{i = 1}^{n} x_{i} = (- 1)^{n} \frac{a _{n}}{a _{0}}$ .

[I-P]
p. 279

Application 60

Théorème de KroneckerSoit $P \in Z [X]$ unitaire tel que toutes ses racines complexes appartiennent au disque unité épointé en l’origine (que l’on note $D$ ). Alors toutes ses racines sont des racines de l’unité.

Corollaire 61

Soit $P \in Z [X]$ unitaire et irréductible sur $Q$ tel que toutes ses racines complexes soient de module inférieur ou égal à $1$ . Alors $P = X$ ou $P$ est un polynôme cyclotomique.