Démonstration décomposition en cycles à supports disjoints

OShine
Modifié (May 2023) dans Algèbre
Bonsoir,

J'ai quelques blocages dans la preuve. Cette preuve m'a toujours fait peur. 
  • Je ne comprends pas le $\sigma =(x \ \sigma(x) )$.
  • Comment on sait que l'ordre de $\sigma$ existe ? 
  • Je ne comprends pas le cas $Supp \ \rho= \emptyset$, on a $\sigma=c_x$ et en quoi on a démontré le théorème dans ce cas ? 
  • Je ne comprends pas pourquoi si $Supp \ \rho \ne \emptyset$ alors $\# Supp \rho \leq k-1$. 



Réponses

  • NicoLeProf
    Modifié (May 2023)
    Salut OShine, tu as peur pour rien, les questions que tu te poses se gèrent facilement :
    1) que dire d'une permutation dont le support contient seulement $2$ éléments distincts? Commence par prendre des exemples.
    2) Lorsque tu prends une permutation $\sigma$ de $\mathfrak{S}_n$, comment l'ordre de $\sigma$ est-il défini et en quoi est-il fini? Un indice : qu'est-ce que l'ensemble $\langle \sigma \rangle$ et quel théorème utilise-t-on pour conclure?
    3) Je ne comprends pas ce que tu ne comprends pas ici. On est d'accord qu'il y a seulement $2$ cas pour $supp$ $\rho$? Soit il est vide, soit il ne l'est pas. Si $supp$ $\rho$ est vide, $\rho=id$ mais $\rho=\sigma \circ c_x^{-1}$ donc qu'en conclure sur $\sigma$? En quoi avons-nous démontré le théorème ? Bah, c'est quoi $c_x$ ?
    C'est vraiment trivial ce point, tu peux y répondre ! :)
    4) Si le support de $\rho$ n'est pas vide, alors il contient au moins un élément et $supp$ $\rho=supp$ $\sigma$ $\setminus$ $supp$ $c_x$ donc? Tu enlèves au moins $1$ élément au support de $\sigma$ (qui est de cardinal $k$ pour rappel) pour avoir le support de $\rho$ vu que $supp$ $c_x$ ne peut pas être vide (pourquoi?), que dire de $supp$ $\rho$ par rapport à celui de $\sigma$? 
  • Merci ! Parfois je comprends des choses après coup, je stresse devant la démo quand je vois que c'est une démonstration technique et difficile.

    1) Si le support contient deux éléments, c'est une transposition.
    2) $\langle \sigma \rangle$ est le sous-groupe de $\mathfrak{S}_n$ engendré par $\sigma$. D'après le théorème de Lagrange, son cardinal divise $n!$ donc il est fini.
    3) On a $\sigma=c_x$ et $c_x$ est un cycle donc c'est terminé.
    4) On a $Card (Supp \sigma ) \geq 3$. Comme $x \in Supp \sigma$ alors $\sigma (x) \ne x$ et $\sigma(x) \in Supp(\sigma)$ donc $c_x(x)= \sigma(x) \ne x$ donc $Supp \  c_x$ est non vide.
     Si $Supp \  \rho = Supp \ \sigma \backslash Supp \  c_x$ est non vide, il existe au moins un élément dedans.
    De plus, $\# Supp \  \rho  \geq 1$.
    Or $\# Supp \  \rho =\# Supp  \ \sigma - \# Supp \  c_x$ ce qui donne  $\boxed{\# Supp \  \rho \leq k-1}$
  • OShine
    Modifié (May 2023)
    Je n'ai rien compris à la preuve de l'unicité.
    Je n'ai pas compris comment on montre que chaque $c_i$ est l'un des $d_j$ ni d'où sort le $s=t$.

  • NicoLeProf
    Modifié (May 2023)
    Content d'avoir pu t'aider OShine, ravi que tu aies compris l'existence ! :)
    Pour l'unicité, c'est plus délicat en effet, il faut s'y pencher et reformuler la preuve :  
    l'auteure a montré que $supp$ $c_s \subset supp$ $d_t$ . Elle a ensuite affirmé rapidement que les cycles coïncident. Pour t'en convaincre pleinement, considère l'inclusion réciproque : prends $y \in supp$ $d_t$ . Alors, comment s'écrit $y$ ($d_t$ est un cycle pour rappel, donc $y$ est une puissance de ...?)? Sous quelle forme? $y$ peut-il appartenir au support d'un $c_i$ pour $i \neq s$ ? Pourquoi (sinon, il se passe quoi, quel est l'argument ultime ici?)?
    Davantage de détails si tu le souhaites ce soir en rentrant du travail ! ^^' :D
  • NicoLeProf
    Modifié (May 2023)
    J'ai emporté mes codes du forum au collège et j'ai une heure de trou, voici une autre méthode plus générale OShine sous la forme d'un exercice que je te soumets : 
    Exercice : soient $c$ et $d$ deux cycles de $\mathfrak{S}_n$ avec $c \neq id$ tels que $supp$ $c \subset supp$ $d$ . Prouver que $c=d$ . 
    Indication : $c$ est un cycle (disons de longueur $s$) donc il peut s'écrire sous la forme $(x$ $c(x)$ $c^2(x)$ ... $c^{s-1}(x))$ où $s $ est un entier supérieur ou égal à $2$ et $x \in supp $ $c$ . Fais de même pour $d$ et utilise la division euclidienne. 
    Edit : énoncé faux... Ne pas en tenir compte : j'ai écrit n'importe quoi, désolé !!! :*
  • Petite question : pourquoi le théorème 2.6 cité demande-t-il absolument que la permutation ne soit pas l'identité, l'auteur est vidophobe ?
  • Probablement :)
  • Je trouve la preuve de l'unicité incompréhensible et très mal expliquée. 

    @NicoLeProf
    Je n'ai aucun théorème qui dit qu'un cycle $c$ de longueur $s$ peut s'écrire sous la forme $(x \ c(x) \ c^2(x) \ \cdots c^{s-1} (x) )$.
    Je ne sais pas d'où ça sort.
    Je n'ai pas compris ton indication. 


  • NicoLeProf
    Modifié (May 2023)
    Tu n'as pas une définition d'un cycle de longueur $s$? Ou une caractérisation d'un cycle par son support?
    Reprenons.
    Questions préliminaires.
    1) On considère le $3$-cycle $(123)$, quel est son support ?
    2) Même question avec le $5$-cycle $(13425)$ . Que remarques-tu 
    3) Dans le cas général, donne moi la définition d'un cycle (celle de ton bouquin : via une capture d'écran ou en la recopiant mot pour mot.)
    La suite dépend de la réponse que tu me donnes à la question 3).
    Je vais t'aider à comprendre la preuve, je suis motivé : j'adore l'algèbre et le groupe symétrique ! ;):)
  • Merci.
    1) $Supp (1 \ 2 \ 3)  = \{1,2,3 \}$.
    2) $Supp (1 \ 3 \ 4 \ 2 \ 5)= \{1,2,3,4,5)$ donc $Supp (1 \ 2 \ 3)  \subset Supp (1 \ 3 \ 4 \ 2 \ 5)$.
    3) Si $i_1, \cdots, i_k$ sont $k$ éléments deux à deux distincts de $\{1, \cdots, n \}$, la permutation définie comme suit est notée $s=(i_1 \ i_2 \ \cdots \ i_k)$ :  
    • si $1 \leq j \leq k-1$ alors $s(i_j)=i_{j+1}$
    • $s(i_k)=i_1$
    • et $s(i)=i$ si $i$ n'est pas l'un des $i_j$.
    Une telle permutation est appelée un $k$-cycle.

  • NicoLeProf
    Modifié (May 2023)
    Ok merci @OShine, pour la remarque de 2), j'attendais autre chose sur le support mais bon, ce n'est pas le plus essentiel ici.
    Question 4) : soit $s$ un $k$ cycle s'écrivant sous la forme $s=(i_1 \ i_2 \ \cdots \ i_k)$ où $i_1,...,i_k$ sont $k$ éléments deux à deux distincts de $\{1,...,n\}$ .
    a) Quel est le support de $s$?
    b) Exprimer $i_2$ en fonction de $i_1$ et de $s$ puis $i_3$ en fonction de $i_1$ et de $s$ en utilisant la définition.
    c) En déduire une expression de $i_j$ en fonction de $i_1$ et de $s$ pour tout $j \in \{1,...,k\}$ .
    d) En déduire une nouvelle écriture pour $s$.
    Une fois que tu auras fini ces questions, je te réinvite à réfléchir sur mon exercice plus haut contenant une indication. ;):)
  • OShine
    Modifié (May 2023)
    @NicoLeProf
    a) $Supp \ s= \{i_1, \cdots, i_k \}$.
    b) $i_2=s(i_1)$, $i_3=s^2(i_1)$ .
    c) $i_j=s^{j-1} (i_1)$.
    d) $s=(i_1 \ s(i_1) \ s^2(i_1) \ \cdots \ s^{k-1}(i_1) )$

    Soient $c,d$ deux cycles de $\mathfrak{S}_n$ tels que $Supp  \ c \subset Supp \ d$.
    Soit $x \in Supp \ c$.
    $c=(x \ c(x) \ \cdots \ c^{s-1}(x))$. 
    Montrons $c=d$.
    On a $d=(x \ d(x) \ \cdots \ d^{t-1}(x))$. 
    On effectue la division euclidienne de $d$ par $c$ ce qui donne $t=sq+r$ avec $0 \leq r \leq s-1$.
    Par l'absurde si $r >0$, alors...
    Je bloque ici. 


  • bd2017
    Modifié (May 2023)
    @Oshine Quelque chose m'échappe. Je ne vois pas pourquoi  on doit avoir $c=d$  Ensuite c'est affolant  pour moi : je ne sais pas ce qu'est la division euclidienne d'un cycle par un autre.
     
  • @bd2017
    Moi non plus.
    Je n'ai juste rien compris à la preuve d'unicité du livre.
  • NicoLeProf
    Modifié (May 2023)
    Oui on ne peut pas faire la division euclidienne d'un cycle par un autre OShine, dans mon idée, il s'agissait d'effectuer la division euclidienne de $t$ par $s$ (les entiers que tu as définis ci-dessus).
    Mais mon exo est pourri : l'énoncé est complètement faux désolé , je me demande bien comment j'ai pu écrire ça !!!! :|:#:o  
    Il manque une condition sur la longueur des cycles par exemple ! Ce n'est pas parce que $supp$ $c \subset $ $supp$ $d$ que $c=d$. On le voit bien en prenant $c=(123)$ et $d=(12345)$ . Vraiment désolé OShine ! Je fais des boulettes des fois !!! :s:*
    C'est mon idée de base qui était la bonne : reviens à la preuve de l'unicité de l'auteure : prends $y \in supp$ $d_t$. Alors $y$ s'écrit sous la forme $...$ . Donc...
  • OShine
    Modifié (May 2023)
    Je ne sais pas quoi faire je ne comprends rien à la preuve.
    Je ne comprends pas : 
    • $c_s=d_t$
    • $s=t$
    • chaque $c_i$ est l'un seulement des $d_j$.
  • @NicoLeProf si on prend ton énoncé avec c=d dans Sn, supp (c) inclus dans supp (d), c'est faux même avec l'égalité de longueur des cycles : il suffit de prendre (123) et (132)
  • Etienne91, ne t'inquiète pas : je m'en suis fortement rendu compte (voir mon post juste au-dessus) : il s'agit d'une boulette complètement nulle et débile de ma part. J'en suis vraiment confus !!! :s:'(
  • bd2017
    Modifié (May 2023)
    @Oshine
    pour bien démarrer:  $\sigma= c_1...c_s = d_1....d_t.$ On sait que   les cycles ont des longueurs au moins égale  à deux, leurs supports sont disjoints  et que les cycles commutent.
    Soit $k\in supp (\sigma).$  Il est dans le support d'un unique $c_i$  et d'un unique $d_j.$  On peut changer l'ordre de sorte qu'on ait $i\in c_1$ et $i\in d_1.$
    Tu montres alors que $c_1= d_1.$  Une fois que cela sera fait tu prends un "nouveau i"  dans le support de $\sigma$  mais pas dans le support
    de $c_1$  (ou $d_1$).  Tu réordonnes le tout de sorte qu'on puisse supposer que $i\in c_2$  et $i\in d_2$...
     
  • @O'Shine Pour l'unicité, c'est plutôt simple (je n'ai pas regardé l'existence).
    Soit $r$ la longueur de $c_s$. On a $\sigma(x)=c_s(x)=d_t(x)$, donc $\sigma(x)$ est dans le support de $c_s$ et $d_t$. Puis par récurrence, puisque $x, \sigma(x), \cdots , \sigma^{r-1}(x) $ sont dans les supports de $c_s$ et de $d_t$, on a :
    $\sigma^r(x)=c_s(\sigma^{r-1}(x))=c_s^r(x)=x=d_t(\sigma^{r-1}(x))=d_t(d_t^{r-1}(x))=d_t^r(x)$, donc $d_t$ est de longueur $r$, et $c_s=d_t=(x, \sigma(x), \cdots, \sigma^{r-1}(x))$.
    Etc... On a épuisé tous ces éléments, on reprend avec un élément $y$ qui n'est pas dans le support de $c_s=d_t$, jusqu'à épuisement des éléments.
    Le plus dur, c'est de formaliser, c'est évident intuitivement (surtout l'existence).
  • @bd2017
    Ok mais comment on montre $r=s$ ? 

    @Julia Paule
    Ok merci c'est bon pour $c_s=d_t$.

    Ensuite on a $c_1 \circ \cdots \circ c_{s-1} = d_1 \circ \cdots \circ d_{t-1}$.
    Et comment on en déduit par récurrence $r=s$ ? et que chaque $c_i$ est l'un des $d_j$ ? 




  • Récurrence sur $s$ par exemple.
  • Je n'ai pas compris comment faire cette récurrence sur $s$.
    Il y a deux variables $s$ et $t$.

    Sans récurrence, si $s> t$, le cas $s < t$ est symétrique, on aurait après simplification (voir méthode du livre) que $c_{t+1} \circ \cdots \circ c_s= id$ ce qui est absurde car les supports sont disjoints.
    Donc $r=s$.
    Le fait que chaque $c_i$ est l'un des $d_j$ s'explique par la même démonstration que $c_s=d_t$ qu'on itère.
  • Je ne vois pas de récurrence, jamais traité des récurrences aussi bizarres.
  • Pas grave, tu as compris : c'est l'essentiel.
  • @NicoLeProf
    Tu sais faire la récurrence ? 
  • Je ne vois pas pourquoi on aurait $s=r$ . Le nombre $r$ est défini comme étant la longueur du cycle $c_s$. Ce que nous avons prouvé ici est : $c_s=d_t=(x$ $\sigma(x)$ $...$ $\sigma^{r-1}(x))$ donc $s=t$ .
    Contre-exemple dans $\mathfrak{S}_7$ dans le cas $s=2$ : 
    Pour, $\sigma = (1324)(567)$ . On a : $c_1=(1324)$ et $c_2=(567)$ donc $r=3 \neq s$ ici ...
  • Récurrence sur $s$ : on suppose que pour toute permutation se décomposant en un produit de $s-1$ cycles à supports disjoints, cette décomposition est unique, et on montre que pour toute permutation se décomposant en un produit de $s$ cycles à supports disjoints, cette décomposition est unique (ce que l'on vient de faire, en complétant les détails, je te laisse les écrire).
    Il reste à faire l'initialisation, qui est immédiate : si un cycle est un produit de cycles à supports disjoints, alors ce produit se réduit en fait à ce cycle.
  • @NicoLeProf
    Désolé erreur de frappe.

    @Julia Paule
    Si $s=1$ alors $\sigma=c_1$ et $c_1$ est unique. 
    Ok pour l'hérédité c'est immédiat en effet, quand on arrive à $c_1 \cdots c_{s-1} = d_1 \cdots d_{t-1}$ on utilise l'hypothèse de récurrence donc chaque $c_i$ est égal à l'un des $d_j$ et on a aussi $s=t$.



Connectez-vous ou Inscrivez-vous pour répondre.