Produit de cycles
Bonsoir à tous,
Je réfléchis à l'exercice suivant :
Dans $(\mathcal{S}_n, \circ)$, on considère $\tau =(1 \; 2)$ et $\sigma=(1 \; 2 \; \ldots \; n)$.
a) Calculer $\sigma^{k} \circ \tau \circ \sigma^{-k}$ pour $0 \leq k \leq n-1$.
b) En déduire que tout élément de $\mathcal{S}_n$ peut s'écrire comme produit de transpositions de la forme $(k \; k+1)$.
Pour le a), il vient simplement $\sigma^{0} \circ \tau \circ \sigma^{0}=\tau =(1 \; 2)$. Ensuite, on pose $k=1$. J'ai trouvé que $\sigma^{-1}=(n \; n-1 \; \ldots \; 2 \; 1)$. On en tire $$$\sigma \circ \tau \circ \sigma^{-1}=(1 \; 2 \; \ldots \; n) \circ (1 \; 2) \circ (n \; n-1 \; \ldots \; 2 \; 1).$$
J'ai réussi à trouver que ceci était égal à $(2 \; 3)$ mais en repassant par la forme "matricielle", je ne sais pas trop comment elle s'appelle...
Une question me vient donc à l'esprit, est-on obligé de repasser par cette forme lorsque l'on compose des cycles ou bien peut-on faire sans et donc procéder directement ?
Concernant cet exercice, comment montrer que la propriété est vrai pour tout $k$ de l'ensemble proposé, de proches en proches ?
Merci d'avance
Je réfléchis à l'exercice suivant :
Dans $(\mathcal{S}_n, \circ)$, on considère $\tau =(1 \; 2)$ et $\sigma=(1 \; 2 \; \ldots \; n)$.
a) Calculer $\sigma^{k} \circ \tau \circ \sigma^{-k}$ pour $0 \leq k \leq n-1$.
b) En déduire que tout élément de $\mathcal{S}_n$ peut s'écrire comme produit de transpositions de la forme $(k \; k+1)$.
Pour le a), il vient simplement $\sigma^{0} \circ \tau \circ \sigma^{0}=\tau =(1 \; 2)$. Ensuite, on pose $k=1$. J'ai trouvé que $\sigma^{-1}=(n \; n-1 \; \ldots \; 2 \; 1)$. On en tire $$$\sigma \circ \tau \circ \sigma^{-1}=(1 \; 2 \; \ldots \; n) \circ (1 \; 2) \circ (n \; n-1 \; \ldots \; 2 \; 1).$$
J'ai réussi à trouver que ceci était égal à $(2 \; 3)$ mais en repassant par la forme "matricielle", je ne sais pas trop comment elle s'appelle...
Une question me vient donc à l'esprit, est-on obligé de repasser par cette forme lorsque l'on compose des cycles ou bien peut-on faire sans et donc procéder directement ?
Concernant cet exercice, comment montrer que la propriété est vrai pour tout $k$ de l'ensemble proposé, de proches en proches ?
Merci d'avance
Réponses
-
Bonsoir Bati
En ce qui concerne la composition des permutations décrites sous forme de cycles à support disjoints, regarde ce message que j'avais écris il y a quelques temps :
\lien{http://www.les-mathematiques.net/phorum/read.php?f=2&i=161879&t=161265#reply_161879}
Ainsi on écrit plutôt $\sigma^{-1} = (1,n,n-1,\ldots,2)$
Ensuite tu as remarqué que $ \sigma^{0} \circ \tau \circ \sigma^{0}=\tau =(1 , 2)$ et que $ \sigma^{1} \circ \tau \circ \sigma^{-1}=( 2,3)$.
En calculant $ \sigma^{2} \circ \tau \circ \sigma^{-2}=(3,4)$, tu peux raisonnablement conjecturer :
$ \sigma^{k} \circ \tau \circ \sigma^{-k}=(k+1 ,k+ 2)$, ce que tu vérifies immédiatement par récurrence.
Pour le b), Tu calcules $(1,2)(2,3)=(1,2,3)$
puis $(1,2)(2,3)(3,4)=(1,2,3,4)$ et ainsi de suite, tu reconstruis certains cycles de longueur quelconque ... je te laisse terminer
Alain -
Merci beaucoup Alain, c'est exactement les explications qu'il me fallait, je pense avoir bien compris.
J'ai cependant toujours un souci, pourquoi n'est-ce pas correct ou bien peu intéressant d'écrire dans le présent exercice $\sigma^{-1}=(n \; n-1 \; \ldots \; 2 \; 1)$ plutôt que $\sigma^{-1}=(1 \; n \; n-1 \; \ldots \; 2)$.
Encore merci pour ton lien -
Bonsoir Bati
Je me suis mal exprimé, ce n'est pas incorrect d'écrire l'inverse d'un cycle comme tu l'écris.
Seulement, pour avoir unicité de décomposition d'une permutation en cycles disjoints, il est convenu de commencer tout cycle par le plus petit élément du cycle, et d'ordonner les cycles (qui commutent entre eux puisque de supports disjoints) dans l'ordre croissant de leur 1er élément (mais ce n'est qu'une convention).
Alain -
Merci pour la précision !
-
Je fais remonter ce fil.
Alain a dit :
"{\it Tu calcules $(1,2)(2,3)=(1,2,3)$ puis $(1,2)(2,3)(3,4)=(1,2,3,4)$ et ainsi de suite, tu reconstruis certains cycles de longueur quelconque... je te laisse terminer}".
Pour la question b, je ne vois pas ce qu'il y a de plus à dire. De proche en proche, on peut donc dire que toute permutation peut s'écrire comme un produit de transpositions de la forme $(k \; k+1)$.
Entendais-tu quelquechose d'autres par "je te laisse continuer". Attend-on peut être une démonstration plus rigoureuse ? -
Tiens ça me rappelle vaguement ce fil : \{http://www.les-mathematiques.net/phorum/read.php?f=2&i=291736&t=290329} où notre Alain national avait déchaîné ses talents de groupiste.
Je pense que "je te laisse terminer" veut dire que tu peux à présent construire pour tout $k$ un cycle de longueur $k$ ; en conjuguant judicieusement tu peux alors obtenir tous les cycles de longueur $k$. Et puisque toute permutation s'écrit comme un produit de cycles.. je te laisse terminer. -
Merci pour ta réponse egoroff, on peut générer à partir des transpositions de la forme $(k\; k+1)$ tout cycle de longueur $k$, et comme toute permutation peut s'écrire comme un produit de cycle, on peut donc générer toute permutation de $\mathcal{S}_n$.
D'après 1, toute transposition de la forme $(k\; k+1)$ s'écrit comme un produit de $\tau$ et $\sigma$, alors tout élément de $\mathcal{S}_n$ peut s'écrire comme un produit $\tau$ et $\sigma$.
Je pense que c'est ca, merci -
Bonsoir Bati
Ce que tu construis ainsi ce sont des cycles de longueur quelconque MAIS dont les éléments se suivent : $(1,2,3,\ldots, k-1,k)$
Ainsi pour avoir par exemple le cycle $(1,3,2,4)$ il faut, comme dit Egoroff, faire appel à une conjugaison bien choisie : $$(1,3,2,4) = (2,3)(1,2,3,4)(2,3)$$ et ici, ça tombe bien, ce par quoi on conjugue : $(2,3)$, est bien de la forme $(i,i+1)$, bref pour trouver tous les cycles, il va falloir faire une récurrence sur la longueur $k$ du cycle, c'est assez pénible.
Je pense qu'il vaut mieux montrer qu'à partir des transpositions $(i,i+1)$ on peut construire toute les transpositions $(j,k)$ qui c'est bien connu engendrent $\frak{S}_n$
Ca se fait en 2 temps :
$(1,k)=(k-1,k)(k-2,k-1)\ldots(2,3)\,\cdot\,(1,2)\,\cdot\,(2,3)\ldots(k-2,k-1)(k-1,k)$
puis $(j,k)=(1,j)(1,k)(1,j)$
Si on ne sait pas que $\frak{S}_n$ est engendré par les transpositions, on peut, en s'inspirant de ce que je t'avais dit, construire tout les cycles,
par exemple $(1,3,5,2,4) = (1,3)(3,5)(5,2)(2,4)$
Alain -
Merci beaucoup Alain pour tes explications, je pense avoir compris
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 163.1K Toutes les catégories
- 7 Collège/Lycée
- 21.8K Algèbre
- 37.1K Analyse
- 6.2K Arithmétique
- 52 Catégories et structures
- 1K Combinatoire et Graphes
- 11 Sciences des données
- 5K Concours et Examens
- 11 CultureMath
- 47 Enseignement à distance
- 2.9K Fondements et Logique
- 10.3K Géométrie
- 62 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 68 Informatique théorique
- 3.8K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 312 Mathématiques et Physique
- 4.9K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10K Probabilités, théorie de la mesure
- 772 Shtam
- 4.2K Statistiques
- 3.7K Topologie
- 1.4K Vie du Forum et de ses membres