Produit de transpositions

OShine

Bonjour
Un exercice qui me semble très difficile. 
Il n'y a pas un problème dans la 3ème décomposition ? Les $(1 \ 2)$ vont ensemble non ? 
Je ne comprends pas la démonstration qui dit qu'$\alpha$ ne peut pas être décomposé en produit de $5$ transpositions.
Je ne comprends pas le raisonnement avec l'union des supports des transpositions. 
Je ne comprends pas non plus pourquoi si $\alpha$ est le produit de $k <5$ transpositions alors le support de $\alpha$ aurait au maximum $2k$ éléments...
Et c'est quoi la contradiction ?

Traversin

Bonjour Oshine, c'est de l'application de cours.

- Je ne comprends pas ta première question. Tu sembles avoir un problème avec le fait de rajouter un élément et son inverse alors qu'on procède déjà de cette façon à la deuxième égalité. On utilise que deux permutations à supports disjoints commutent.

- Deuxième question : on ne peut pas t'aider si tu ne dis pas précisément ce qui te tracasse (ne dis pas "tout", ce serait exagéré).

- Troisième question : raisonne sur les supports de ces transpositions, comment se comportent-ils les uns envers les autres (meilleur des cas, pire des cas etc...).

- Quatrième question : tout est écrit. En supposant par l'absurde une décomposition en 5 transpositions, on montre que la permutation au carré possède au moins un point fixe. Il suffit de calculer $\alpha^2$ pour voir que c'est impossible.

OShine

Je ne trouve pas que cet exercice soit une application du cours. Le raisonnement avec les unions de supports de transposition n'est pas dans le cours. Je n'ai jamais vu ces raisonnements.

Je pense avoir compris finalement.
On a écrit $\alpha= \tau_1 \circ \tau_2 \circ \tau_3 \circ \tau_4 \circ \tau_5$.
Avec $\text{Supp} \ \alpha = \displaystyle\bigcup_{i=1}^9 \text{Supp} \ \tau_i$
On a $\text{card} \ (\text{Supp} \ \alpha )=9= \text{card} \ \left( \displaystyle\bigcup_{i=1}^9 \text{Supp} \ \tau_i \right)$
Comme le support des $\tau_i$ est de cardinal $2$, si toutes les transpositions étaient disjointes on aurait $9=10$ ce qui est absurde.
Donc il existe un élément $b \in [|1,9|]$ tel que $b$ qui n'appartient à aucune des deux transpositions que l'on peut noter $\tau_1$, $\tau_4$. 
Donc toutes les transpositions commutent sauf $\tau_1$ et $\tau_4$ qui ont un élément en commun. 

Notons $t=\tau_3$ par exemple. On a $t^2(b)=id(b)=b$
Et $\alpha^2 = \tau_1 \circ \tau_2 \circ t \circ \tau_4 \circ \tau_5 \circ  \tau_1 \circ \tau_2 \circ t \circ \tau_4 \circ \tau_5$
En réorganisant les permutations on obtient :  $\alpha^2=\tau_1 \tau_4 \tau_1 \tau_4$
Ainsi $\boxed{\alpha^2= (\tau_1 \circ \tau_4)^2}$ et comme $b$ n'appartient au support d'aucune des deux $\alpha^2(b)=b$.

Traversin

C'est vraiment pas mal sauf la fin, j'ai quelques remarques. Il y a une coquille lorsque tu décris le support de $\alpha$ avec une union (rien de grave). Lorsque tu dis "(...) n'appartient à aucune des deux transpositions (...)", on ne sait pas de qui tu parles. Je me doute bien que tu as travaillé avec ton bouquin à côté et que celui-ci détaille, mais tu dois faire de même pour avoir une rédaction irréprochable. Le fait que $t^2 = id$ est évident puisque $t$ est une transposition, ça n'apporte rien. Cette ligne est inutile et doit être remplacée par celle du livre stipulant "$\alpha^2(b) = t^2(b) = b$" (c'est surtout la première égalité qui mérite une justification).  Je dois m'absenter quelques semaines, bon courage.

OShine

J'essaie de faire la question $2$.

2) On a : $\beta=(2 \ 5)(5 \ 7) (7 \ 8)  (3 \ 9)$ est une décomposition en produit de $4$ transpositions.
On a $\boxed{\text{Supp} \ \alpha= \{ 2,3,5,7,8,9 \}}$.
$\beta= (1 \ 4) (2 \ 5)(1 \ 4) (5 \ 7) (7 \ 8)  (3 \ 9)$ est une décomposition en produit de $6$ transpositions. 
$\beta=(7 \ 8) (1 \ 4) (7 \ 8) (2 \ 5)(1 \ 4) (5 \ 7) (7 \ 8)  (3 \ 9)$ est une décomposition en produit de $8$ transpositions. 
$\beta=(1 \ 2](7 \ 8) (1 \ 2)  (1 \ 4) (7 \ 8) (2 \ 5)(1 \ 4) (5 \ 7) (7 \ 8)  (3 \ 9)$ est une décomposition en produit de $10$ transpositions. 

Montrons que $\beta$ ne peut s'écrire en produit de $2$ transpositions.
Par l'absurde, si $\beta$ s'écrit comme produit de $2$ transpositions, on peut noter $\beta=\tau_1 \circ \tau_2$.
Donc $\text{Supp} \ \beta= \text{Supp} \ \tau_1 \cup \text{Supp} \  \tau_2=6$
Le support de $\beta$ aurait au maximum $4$ éléments, ce qui est absurde.

La fin est plus facile. 
3) Soit $n$ impair $n>5$ et $t$ une transposition. La différence de deux entiers impairs et paire donc $n-7$ est pair et $t^{n-7}=id$.
On a $\boxed{\alpha=t^{n-7} (1 \ 2) (2 \ 3) (4 \ 5) (5 \ 6)(6 \ 7) (7 \ 8) (8 \ 9)}$

4) Soit $m$ pair $m>2$. La différence de deux nombres pairs est paire donc $m-4$ est pair et : 
$\boxed{\beta=t^{m-4} (2 \ 5) (5 \ 7)(7 \ 8)(3 \ 9) }$.

OShine

@Traversin merci.
Mon problème est que je n'ai pas ça dans le cours : le lien entre le support d'une union de permutation et la permutation de l'union. 
Quel lien a-t-on entre $\text{Supp} \displaystyle\bigcup_{i=1}^n \tau_i$ et $ \displaystyle\bigcup_{i=1}^n \ \text{Supp}  (\tau_i)$ ? 

Heuristique

Comme disait un de mes profs : "Le cours, c'est l'ensemble des choses que tu as vues en maths dans ta vie."

Qu'est-ce que l'union des $\tau_i$ ?

bisam

L'union des transpositions, ça n'existe pas !

gai requin

Comme tout est ensemble, on peut bien trouver quelque chose non ? 😉

OShine

Oui, je voulais dire quelle relation on a entre : 
$Supp \ (\tau_1 \circ \tau_2 \circ \cdots \circ \tau_n)$ et $\displaystyle\bigcup_{i=1}^n Supp ( \tau_i)$ ? 
Posons $\sigma =\tau_1 \circ \tau_2 \circ \cdots \circ \tau_n$.

Supposons que $Supp \ \sigma=\{ x_1, \cdots, x_k \}$ où $x_1, \cdots, x_n \in [|1,n|]$.

@gai requin
Oui il faut regarder les inclusions, mais ici je n'arrive à en faire aucune. 

OShine

Le corrigé affirme qu'il y a égalité mais ne le démontre pas, et ceci n'est pas expliqué dans la partie cours.

OShine

$Supp \ (\tau_1 \circ \tau_2 \circ \cdots \circ \tau_n) =\displaystyle\bigcup_{i=1}^n Supp ( \tau_i)$.

AD

Que dire du support de $(1 2)\circ(1 2)$ comparativement à $Supp(1 2) \cup Supp(1 2)$ ?

Alain

OShine

$Supp ( (1\ 2) \circ (1 \ 2))= \emptyset \subset Supp (1 \ 2) \cup Supp (1 \ 2) = \{1,2\}$

noobey

Non.

OShine

J'ai rectifié mais je pense que je n'ai toujours pas compris la solution de la question 1 avec les unions de supports.

JLapin

Qu'est-ce que tu ne comprends pas ? C'est écrit en assez bon français.

NicoLeProf

OShine a dit :

Le corrigé affirme qu'il y a égalité mais ne le démontre pas, et ceci n'est pas expliqué dans la partie cours.

Le corrigé ne dit pas ça je crois, il dit seulement : $Supp \ (\tau_1 \circ \tau_2 \circ \cdots \circ \tau_n) \subset \displaystyle\bigcup_{i=1}^n Supp ( \tau_i)$ et tu vois bien avec la question d'AD qu'il n'y a pas forcément égalité.

L'inclusion me semble facile à prouver en raisonnant par contraposée : soit $k \notin \displaystyle\bigcup_{i=1}^n Supp ( \tau_i)$ alors pour tout $\ell \in \{1,...,n\}$, $\tau_{\ell}(k)=k$ ($k$ n'appartient à aucun des supports en question). Donc $\tau_1 \circ \tau_2 \circ \cdots \circ \tau_n(k)=k$ et $k \notin Supp \ (\tau_1 \circ \tau_2 \circ \cdots \circ \tau_n)$ et on a le résultat souhaité par contraposée.

Pour le reste, qu'est-ce qui te gêne exactement? Essaie de reformuler la preuve avec tes mots au brouillon peut-être !

OShine

@NicoLeProf
Merci, en effet la contraposée est plus facile ici.

Je ne comprends pas le passage suivant, je l'ai relu 20 fois mais je bloque toujours  : 
"Le cardinal du support de ce produit a 9 éléments, or il est contenu dans l'union du support des transpositions utilisées, chacun étant de cardinal 2. Cette union a ainsi 9 éléments, donc il existe un un unique élément $a$ appartenant à la fois au support de deux de ces transpositions."

Je n'ai pas compris pourquoi cette union a $9$ éléments. 

OShine

Je crois que la phrase du corrigé est mal formulée.

@NicoLeProf
J'essaie de faire sans. Supposons que $\alpha= \tau_1 \circ \tau_2 \circ \tau_3 \circ \tau_4$. 
On a $card (Supp \ \alpha )=9$. On a $9  \leq card \left( Supp \ (\tau_1) \cup Supp \ (\tau_2) \cup  Supp \ (\tau_3) \cup  Supp \ (\tau_4)  \right)$
Mais le support de chaque transposition est égal à $2$, ce qui donne l'inégalité : 
$9  \leq card \left( Supp \ (\tau_1) \cup Supp \ (\tau_2) \cup  Supp \ (\tau_3) \cup  Supp \ (\tau_4)  \right) \leq 10$
Il est impossible d'avoir tous les supports disjoints, car il n'y a que $9$ éléments dans $[|1,9|]$.
Donc $\boxed{card \left( Supp \ (\tau_1) \cup Supp \ (\tau_2) \cup  Supp \ (\tau_3) \cup  Supp \ (\tau_4)  \right) =9}$.
Finalement, il existe un entier $a$ dans $[|1,9|]$ qui appartient au support de deux transpositions.

NicoLeProf

Bah voilà tout simplement tu as compris sauf qu'il faut ajouter à ta décomposition une autre transposition : $\tau_5$ ici. On cherche à savoir si l'on peut décomposer $\alpha$ en un produit de $5$ transpositions dans cette question.

OShine

Oui en effet c'est une coquille.

OShine

Si les supports sont disjoints, l'union des supports des transpositions qui engendrent la permutation est égale au support de la permutation.