Théorie avancée des permutations et applications
Soit n ∈ ℕ*. Le groupe symétrique S_n est l'ensemble de toutes les bijections de {1, 2, ..., n} dans lui-même, muni de la loi de composition des applications.
L'ordre de S_n est |S_n| = n!
| Notation | Description | Exemple |
|---|---|---|
| σ = (i₁ i₂ ... iₖ) | Notation cyclique | (1 3 2) : 1→3, 3→2, 2→1 |
| σ = \begin{pmatrix} 1 & 2 & 3 \\ 3 & 1 & 2 \end{pmatrix} | Notation matricielle | 1→3, 2→1, 3→2 |
| (i j) | Transposition | (1 2) : échange 1 et 2 |
Le groupe S_3 contient 6 éléments :
Entrez une permutation sous forme cyclique (ex: (1 2 3)) :
Soit σ ∈ S_n et k ≥ 1.
Toute permutation σ ∈ S_n se décompose de manière unique (à l'ordre près) en produit de cycles disjoints.
Démonstration :
Existence : Soit σ ∈ S_n. Définissons une relation d'équivalence sur {1, 2, ..., n} par :
Les classes d'équivalence donnent les orbites sous l'action de ⟨σ⟩. Sur chaque orbite de taille > 1, σ agit comme un cycle.
Unicité : Supposons σ = c₁c₂...cₖ = d₁d₂...dₗ avec cᵢ, dⱼ cycles disjoints. Alors les supports des cᵢ forment une partition de supp(σ), de même pour les dⱼ. L'unicité de la partition implique l'unicité de la décomposition. ∎
Considérons σ = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 2 & 4 & 1 & 6 & 5 & 3 \end{pmatrix}
Calcul des orbites :
Résultat : σ = (1 2 4 6 3)
Entrez une permutation en notation matricielle :
Le groupe S_n est engendré par les transpositions. Plus précisément :
La signature (ou parité) d'une permutation σ ∈ S_n est définie par :
On a ε(σ) ∈ {-1, +1}. La permutation σ est :
Propriété 1 : Soit σ, τ ∈ S_n. Alors :
En réindexant et utilisant la bijectivité de τ, on obtient ε(στ) = ε(σ)ε(τ).
Propriété 3 : Pour la transposition (k ℓ) avec k < ℓ :
Les autres termes du produit restent inchangés car (k ℓ) fixe les autres éléments. ∎
Le groupe alterné A_n est le noyau du morphisme signature :
C'est un sous-groupe normal de S_n d'ordre |A_n| = n!/2 pour n ≥ 2.
Calculez la signature des permutations suivantes :
Question 1 : Quelle est la signature de (1 2 3 4 5) ?
Question 2 : Quelle est la signature de (1 2)(3 4 5) ?
Tout groupe fini G d'ordre n est isomorphe à un sous-groupe de S_n.
Démonstration :
Soit G = {g₁, g₂, ..., gₙ} un groupe fini d'ordre n.
Étape 1 : Pour chaque g ∈ G, définissons λ_g : G → G par λ_g(h) = gh (translation à gauche).
Étape 2 : λ_g est bijective car :
Étape 3 : Identifions G avec {1, 2, ..., n} via un ordre fixé. Alors λ_g ∈ S_n.
Étape 4 : L'application φ : G → S_n définie par φ(g) = λ_g est un morphisme injectif :
Donc G ≅ Im(φ) ≤ S_n. ∎
Une action d'un groupe G sur un ensemble X est un morphisme de groupes :
Équivalemment, c'est une application G × X → X notée (g, x) ↦ g·x telle que :
Soit σ, τ ∈ S_n. Le commutateur est [σ, τ] = στσ⁻¹τ⁻¹.
Question : Calculez [(1 2 3), (1 2)] dans S_3.
Solution :
Posons σ = (1 2 3) et τ = (1 2).
Attendez, reprenons le calcul...
[(1 2 3), (1 2)] = (1 2 3)(1 2)(1 3 2)(1 2)
= (1 3)(1 3 2)(1 2) = (2 3)(1 2) = (1 2 3)
Non, erreur ! Le calcul correct donne (2 3).
Déterminez le centre Z(S_n) pour différentes valeurs de n.
Question : Quel est Z(S_n) pour n ≥ 3 ?
Justification :
Pour n ≥ 3, considérons σ ∈ Z(S_n) avec σ ≠ id.
Il existe i tel que σ(i) = j ≠ i. Soit k ≠ i, j (possible car n ≥ 3).
Considérons τ = (i k). Pour que στ = τσ, on doit avoir :
στ(i) = τσ(i), soit σ(k) = τ(j)
Mais τ(j) = j (car j ≠ i, k) et σ(k) = k ou σ(k) ≠ k.
En analysant tous les cas, on trouve une contradiction, donc Z(S_n) = {id}.
Explorez les classes de conjugaison dans S_n :
Utilisant les groupes symétriques, on peut classifier :
La théorie de Galois utilise les groupes symétriques pour étudier la résolvabilité des équations polynomiales :
Problème : Quel est le nombre minimal de générateurs pour S_n ?
Réponse : S_n peut être engendré par exactement 2 éléments pour tout n ≥ 2.
Exemple : S_n = ⟨(1 2), (1 2 3 ... n)⟩
À démontrer : Montrez que ces deux éléments engendrent bien S_n.
Les groupes symétriques constituent un pilier fondamental de l'algèbre moderne. Leurs applications s'étendent à :
Résolvabilité des équations polynomiales, extensions de corps, théorie des nombres algébriques.
Groupes fondamentaux, espaces de recouvrement, théorie des nœuds.
Énumération, fonctions génératrices, théorie de Pólya, arrangements et permutations.
Algorithmes de tri, complexité, cryptographie, codes correcteurs d'erreurs.