Evaristette, septembre 2018
Chères amies, chers amis de Galois, voici l'evaristette de septembre:
Galois est considéré comme l'initiateur de la théorie des groupes. En
tout cas, le groupe des permutations des racines d'une équation est au
cœur de sa théorie. Soit G le groupe de toutes les permutations des
entiers de 1 à n. On sait qu'il peut être engendré par n-1
transpositions, .... c'est dans tous les livres mais sauriez-vous
montrer qu'il ne peut être engendré par n-2 transpositions. Supplément :
trouver une condition nécessaire et suffisante pour qu'un ensemble de
n-1 transpositions engendre G.
A vos plumes (d'oie)! Ce 26 septembre, un "ami de Galois" [https://www.evaristegalois.org/]
Galois est considéré comme l'initiateur de la théorie des groupes. En
tout cas, le groupe des permutations des racines d'une équation est au
cœur de sa théorie. Soit G le groupe de toutes les permutations des
entiers de 1 à n. On sait qu'il peut être engendré par n-1
transpositions, .... c'est dans tous les livres mais sauriez-vous
montrer qu'il ne peut être engendré par n-2 transpositions. Supplément :
trouver une condition nécessaire et suffisante pour qu'un ensemble de
n-1 transpositions engendre G.
A vos plumes (d'oie)! Ce 26 septembre, un "ami de Galois" [https://www.evaristegalois.org/]
Réponses
-
Bonjour,
on peut procéder en prouvant que dans $S_n$, il existe toujours un élément qui ne peut être écrit comme produit de $n-2$ transpositions: ce sont les $n-$cycles, c'est-à-dire les cycles dont le support est de cardinal $n$.
On peut le démontrer par l'absurde.
Cordialement
... -
Une manière de voir est d'associer à toute permutation $\sigma$, le nombre $C_{\sigma}$ de cycles que contient sa décomposition en cycles à supports disjoints (en incluant les points fixes).
En composant cette permutation avec n'importe quelle transposition $(i,j)$, on constate que ce cardinal augmente ou diminue de $1$ selon que $i$ et $j$ sont dans le même cycle ou dans des cycles différents.
Si on compose $\sigma$ avec $k$ transposition,$C_{\sigma}$ augmente ou diminue d'au plus $k$.
Sachant que le cardinal de la permutation "Identité" est $n$ et que celui d'un cycle d'ordre $n$ est $1$, on voit que le nombre de transpositions nécessaires pour transformer un $n$-cycle en $n$ cycles d'ordre $1$ ne peut-être inférieur à $n-1$.
... -
Merci pour cette jolie démo df. (tu)
-
Bonjour,
Il me semble que l'affirmation initiale est exacte. Par contre la démonstration ne me suffit pas : le groupe engendré par $n-2$ transpositions peut contenir des éléments qui sont composés de plus de ces $n-2$ transpositions, il suffit de faire des répétitions... -
Salut Norbert: En représentant fidèlement le groupe de permutation comme un groupe de symétries hyperplanes tu as (n-2) symétries hyperplanes dans $R^{n-1}$. Les vecteur orthogonaux à tes hyperplans engendrent un sev V de dimension au plus n-2 et donc laisse fixe l'orthogonal soit D (en général une droite). Or le groupe opère transitivement donc il ne peut être engendré par tes $(n-2)$ symétries ;-)
-
Merci pour cette démonstration efficace. Je propose une autre approche : à un ensemble $E$ de transpositions, on peut associer un graphe, les sommets sont les entiers de $1$ à $n$ (qui doivent tous apparaître si on veut engendrer $\mathcal{S}n$), les sommets $i$ et $j$ sont joints par une arête si $(i,j)$ est dans $E$. Pour que $E$ engendre $\mathcal{S}_n$, il faut et suffit que ce graphe soit connexe : si $i$ et $k$ sont reliés par un chemin, il est facile de trouver un produit de tranpositions de $E$ qui donne la transposition $(i,k)$. Or un graphe connexe à $n$ sommets à au moins $n-1$ arêtes. (démonstration par récurrence, par exemple). En prime, si $E$ contient $n-1$ tranpositions, on a une condition pour qu'il engendre $\mathcal{S}_n$. Et si je ne me trompe pas, le graphe devrait être un arbre.
-
Il y a aussi une interprétation en terme de graphes.
On considère un enemble fini $E$ et un ensemble $\mathcal T$ de transpositions de $E$. On représente les éléments de $E$ par des points, et l'on joint deux de ces points si la transposition qui les échange est élément de $\mathcal T$. On obtient ainsi un graphe non orienté. L'ensemble $\mathcal T$ engendre le groupe de toutes les permutations de $E$ si et seulement si l'on peut se rendre de n'importe quel point à n'importe quel autre en suivant les arêtes du graphe, autrement dit si le graphe est connexe. Il n'est pas difficile de démontrer qu'un graphe connexe à $n$ sommets a au moins $n-1$ arêtes.
Si le graphe n'est pas connexe, ses composantes connexes donnent le groupe de permutations engendré par $\mathcal T$.
Qu'on ne se méprenne pas : j'avais vu ça il y a longtemps et je ne connais presque plus rien à la théorie des graphes : encore une chose que je regrette... mais cette vision imagée extraite de ma mémoire me semble très parlante.
Bonne soirée.
Fr. Ch. -
Joli, mais ce que vous écrivez est la même chose non?
M -
Oui, je n'avais pas lu le précédent message, mais j'ai dit un chouïa de plus.
Un graphe à $n$ sommets et $n-1$ arêtes n'est pas forcément un arbre. -
On a deux exemples classiques de générateurs du groupe $\mathcal{S}_n$ par $n-1$ transpositions, qui font généralement l'objet d'un exercice.
Il y a les transpositions $(1,i)$, $2 \le i \le n$, ce qui correspond effectivement à un arbre.
Il y a aussi les transpositions $(i,i+1)$, $1 \le i \le n-1$, ce qui correspond à une « chaîne » pour ainsi dire, je ne sais si ça a un nom en théorie des graphes.
Mais il y a une foule d'autres ensembles de $n-1$ transpositions qui engendrent le groupe symétrique.
Bonne soirée.
Fr. Ch. -
Oups ! J'ai écrit une bêtise. Un graphe connexe à $n$ sommets ayant $n-1$ arêtes est un arbre. Comme j'ai dit, je suis pas mal rouillé en théorie des graphes.
Bonne journée.
Fr. Ch.
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 165.5K Toutes les catégories
- 64 Collège/Lycée
- 22.2K Algèbre
- 37.6K Analyse
- 6.3K Arithmétique
- 61 Catégories et structures
- 1.1K Combinatoire et Graphes
- 13 Sciences des données
- 5.1K Concours et Examens
- 26 CultureMath
- 51 Enseignement à distance
- 2.9K Fondements et Logique
- 10.8K Géométrie
- 86 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 79 Informatique théorique
- 3.9K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 29 Mathématiques et finance
- 343 Mathématiques et Physique
- 5K Mathématiques et Société
- 3.4K Pédagogie, enseignement, orientation
- 10.1K Probabilités, théorie de la mesure
- 804 Shtam
- 4.2K Statistiques
- 3.8K Topologie
- 1.4K Vie du Forum et de ses membres