Groupe symétrique - Définition

Soient σ et φ deux permutations de . L'objectif dans un premier temps est de montrer que σ^-1φσ est une permutation de même nombre de cycles de chaque longueur.

Un résultat précédent montre qu'il est possible de décomposer σ en une suite de transpositions : σ = σ₁σ₂...σ_m. L'objectif revient à montrer que σ_m^-1σ_m-1^-1...σ₁^-1φσ₁σ₂...σ_m a même structure que φ. Ceci revient à montrer que si σ est une transposition, alors σ^-1φσ possède la même structure que φ. Soient a₁ et b₁ les deux éléments du support de σ, c'est-à-dire que σ(a₁) = b₁ et σ(b₁) = a₁. On peut diviser l'étude en quatre cas différents.

Si ni a₁, ni b₁ ne sont élément du support de φ, φ et σ commutent et σ^-1φσ = φ, ce qui montre le résultat.

Si a₁ est élément du support de φ, mais que b₁ ne l'est pas. Soit (a₁a₂...a_k) le cycle de φ contenant a₁. Les cycles de σ^-1φσ sont exactement les mêmes que ceux de φ, à l'exception de celui contenant a₂, qui devient (b₁a₂a₃...a_k) et qui est un cycle de même longueur. Si b₁ n'est plus invariant par σ^-1φσ, a₁ l'est devenu. Les deux permutations σ^-1φσ et φ ont bien même structure.

Si a₂ et b₂ appartiennent au même cycle, avec les notations précédentes, il existe un entier h, plus petit que k tel que b₂ soit égal à a_h avec h différent de 2. Les différents cycles à supports disjoints composant φ sont les mêmes que ceux de σ^-1φσ à l'exception de celui contenant a₂, qui devient (a₁a_ha₃...a_h-1a₂a_h+1a_h+2...a_k). Une fois encore les structures des cycles sont les mêmes.

Si a₁ et b₁ sont tout deux éléments du support de φ et appartiennent à des cycles différents, on note (b₁b₂...b_l) le cycle de b₁. Tous les cycles de φ restent inchangés, sauf ceux contenant a₁ et b₁, qui deviennent : (a₁b₂...b_l) et (b₁a₂...a_k). Les deux permutations ont encore la même structure.

Soient φ₁ et φ₂ deux permutations ayant même structure. Il s'agit, pour clore la démonstration, de montrer l'existence d'une permutation σ tel que σ^-1φ₁σ = φ₂.

Dans un premier temps, on construit une permutation σ₁σ₂...σ_k tel que σ_k^-1σ_k-1^-1...σ₁^-1φ₁σ₁σ₂...σ_k ait même support que φ₂. Soit b₁, b₂ ... b_j les entiers compris entre 1 et n qui ne sont pas dans le support de φ₂. Si b_i, où i est un entier entre 1 et j, n'est pas dans le support de φ₁ on définit σ_i comme la permutation identité et c_i comme étant égal à b_i. Dans le cas contraire, il existe nécessairement un élément c_i élément de l'ensemble {b₁, b₂ ... b_j} qui est dans le support de φ₁ car φ₁ et φ₂ ont même structure et par conséquent même nombre d'éléments invariants. On peut, de plus choisir c_i différent de c_p pour p variant de 1 à i. Soit σ_i la transposition de support b_i et c_i, la permutation σ_i^-1φ₁σ_i laisse b_i invariant. Par récurrence, on vérifie bien que σ_k^-1σ_k-1^-1...σ₁^-1φ₁σ₁σ₂...σ_k possède le même support que φ₂.

Dans un deuxième temps, on construit une permutation σ₁σ₂...σ_l, où l est un entier plus grand que k, tel que σ_l^-1σ_l-1^-1...σ₁^-1φ₁σ₁σ₂...σ_l ait même support et même élément dans chaque cycle que φ₂. Les différentes permutations σ_p sont définies jusqu'à l'indice k, il faut maintenant les définir jusqu'à l'indice l. Soit (a₁a₂...a_p) un cycle de σ_k^-1σ_k-1^-1...σ₁^-1φ₁σ₁σ₂...σ_k et (b₁b₂...b_p) un autre cycle de même longueur de φ₂. Si a₁ est élément de {b₁, b₂, ..., b_p) on définit σ_m+1 comme la permutation identité, sinon c'est la transposition de support a₁ et b₁. Le premier élément du cycle de longueur p et contenant b₂ est maintenant commun à σ_k+1^-1σ_k^-1...σ₁^-1φ₁σ₁σ₂...σ_k+1. De proche en proche on construit ainsi la permutation ayant même support et même élément dans chaque cycle.

Dans un troisième temps, on construit une permutation σ₁σ₂...σ_m, où m est un entier plus grand que l, tel que σ_m^-1σ_m-1^-1...σ₁^-1φ₁σ₁σ₂...σ_m soit égal à φ₂. Il devient nécessaire d'ordonner les éléments dans les différents cycles. Soit (a₁a₂...a_p) un cycle de σ_l^-1σ_l-1^-1...σ₁^-1φ₁σ₁σ₂...σ_l et (a₁a_ψ(2)...a_ψ(p)) la permutation de même support dans φ₂. Ici ψ désigne une permutation de {2, ..., p}. Si a_ψ(2) est égal à a₂ alors σ_l+1 est la permutation identité. Sinon, σ_l+1 est la transposition de support a₂ et a_ψ(2). L'image de a₁ par la permutation σ_k+1^-1σ_k^-1...σ₁^-1φ₁σ₁σ₂...σ_k+1 est bien celle de φ₂. De proche en proche on construit la permutation recherchée.