matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Forenbaum
^ Forenbaum
Status Hochschulmathe
  Status Uni-Analysis
    Status Reelle Analysis
    Status UKomplx
    Status Uni-Kompl. Analysis
    Status Differentialgl.
    Status Maß/Integrat-Theorie
    Status Funktionalanalysis
    Status Transformationen
    Status UAnaSon
  Status Uni-Lin. Algebra
    Status Abbildungen
    Status ULinAGS
    Status Matrizen
    Status Determinanten
    Status Eigenwerte
    Status Skalarprodukte
    Status Moduln/Vektorraum
    Status Sonstiges
  Status Algebra+Zahlentheo.
    Status Algebra
    Status Zahlentheorie
  Status Diskrete Mathematik
    Status Diskrete Optimierung
    Status Graphentheorie
    Status Operations Research
    Status Relationen
  Status Fachdidaktik
  Status Finanz+Versicherung
    Status Uni-Finanzmathematik
    Status Uni-Versicherungsmat
  Status Logik+Mengenlehre
    Status Logik
    Status Mengenlehre
  Status Numerik
    Status Lin. Gleich.-systeme
    Status Nichtlineare Gleich.
    Status Interpol.+Approx.
    Status Integr.+Differenz.
    Status Eigenwertprobleme
    Status DGL
  Status Uni-Stochastik
    Status Kombinatorik
    Status math. Statistik
    Status Statistik (Anwend.)
    Status stoch. Analysis
    Status stoch. Prozesse
    Status Wahrscheinlichkeitstheorie
  Status Topologie+Geometrie
  Status Uni-Sonstiges

Gezeigt werden alle Foren bis zur Tiefe 2

Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenAlgebraKonjugationskl. von S_n Beweis
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Geschichte • Erdkunde • Sozialwissenschaften • Politik/Wirtschaft
Forum "Algebra" - Konjugationskl. von S_n Beweis
Konjugationskl. von S_n Beweis < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Algebra"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Konjugationskl. von S_n Beweis: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 12:33 Mi 10.06.2020
Autor: Andrejtrikolor

Aufgabe
Zeigen Sie:

Die Menge der Konjugationsklassen der [mm] $S_{n}$ [/mm] steht in Bijektion mit der Menge der Partitionen von $n$.


Hinweis: Für alle [mm] $\sigma \in S_{n}$ [/mm] und alle Zykel $t = [mm] (t_{1}, \ldots, t_{k}) \in S_{n}$ [/mm] gilt: [mm] $\sigma [/mm] t [mm] \sigma^{- 1} [/mm] = [mm] (\sigma(t_{1}), \ldots, \sigma(t_{k}))$ [/mm]

Hallo, Matheraum - Community.



Mich interessiert es zu wissen, warum die Menge der Konjugationsklassen der [mm] $S_{n}$ [/mm] in Bijektion mit der Menge der Partitionen von $n$ steht.


Diesen Satz habe ich als Übungsaufgabe im Internet gefunden mit einer Musterlösung, die ich an einigen Stellen nicht verstehe.





Die Hinrichtung habe ich ein bisschen verstanden, daher konnte ich da auch konkrete Fragen formulieren.

Die Rückrichtung habe ich überhaupt nicht verstanden. Das setze ich mich später noch einmal hin und versuche sie zu verstehen. Die lassen wir also erstmal frei.



Der Beweis:




[mm] $\Rightarrow$ [/mm]

Seien [mm] $\sigma$, $\sigma$' [/mm] konjugiert zueinander, d.h. es gibt $t [mm] \in S_{n}$, [/mm] so dass [mm] $\sigma' [/mm] = t [mm] \sigma t^{- 1}$. [/mm]


Nach Lineare Algebra I können wir [mm] $\sigma$ [/mm] als Produkt disjunkter Zykel schreiben: [mm] $\sigma [/mm] = [mm] \sigma_{1} \circ \ldots \circ \sigma_{r}$, [/mm] d.h.  [mm] $\sigma' [/mm] = t [mm] \sigma_{1} t^{- 1} \circ \ldots \circ [/mm] t [mm] \sigma_{r} t^{- 1}$. [/mm]


Nun sind, da $t$ injektiv ist, auch die Zykel $t [mm] \sigma_{i} t^{- 1}$ [/mm] disjunkt.


Das heißt, auch  [mm] $\sigma$' [/mm] besteht aus $r$ disjunkten Zykeln.

Außerdem gilt nach den Hinweis in der Aufgabenstellung: [mm] Zykellänge$(\sigma_{i}) [/mm] = $ Zykellänge$(t [mm] \sigma_{i} t^{- 1})$. [/mm]

Also definiert die Konjugationsklasse von [mm] $\sigma$ [/mm] eine Partition von $n$ via

$n = $ [mm] Zykellänge($\sigma_{1}$) [/mm] $+ [mm] \ldots [/mm] +$  [mm] Zykellänge($\sigma_{r}$). [/mm]






[mm] $\Leftarrow$ [/mm]

Seien nun [mm] $\sigma [/mm] = [mm] \sigma_{1} \circ \ldots \sigma_{r}$, $\sigma' [/mm] = [mm] \sigma_{1}' \circ \ldots \sigma_{r}'$ [/mm] mit [mm] $\sigma_{i}$ [/mm] und [mm] $\sigma_{i}'$ [/mm] jeweils disjunkt.

Ohne Einschränkungen sei [mm] Zykellänge($\sigma_{i}$) [/mm] = [mm] Zykellänge($\sigma_{i}'$) [/mm] (sonst Reihenfolge der Zykel ändern).


Gesucht ist $t [mm] \in S_{n}$ [/mm] mit [mm] $\sigma' [/mm] = t [mm] \sigma t^{- 1}$. [/mm]


Es gilt [mm] $\forall [/mm] j [mm] \in \{ 1,2, \ldots, r \}: \sigma_{j} [/mm] = ( [mm] i_{j_{1}}) \ldots i_{j_{\vert \sigma_{j} \vert}})$ [/mm] und [mm] $\sigma_{j}' [/mm] = ( i'{j{1}}) [mm] \ldots i'{j{\vert \sigma_{j}' \vert}})$für $i_{j_{l}}, [/mm] i'{j{l}} [mm] \in \{ 1, \ldots, n\}$ [/mm] und [mm] $\vert \sigma_{j} \vert= \vert \sigma_{j}' \vert$. [/mm]


Definiere $t$ durch [mm] $t(i_{j_{l}}) [/mm] = [mm] i_{j'_{l}}$ [/mm] für alle $i, l$.


Dann ist $t$ eine Permutation, weil die Zykel jeweils für [mm] $\sigma$ [/mm] und [mm] $\sigma'$ [/mm] disjunkt sind.


Nach behauptung $1$ gilt dann $t [mm] \sigma_{i} t^{- 1} [/mm] = [mm] \sigma_{i}'$, [/mm] also $t  [mm] \sigma t^{- 1} [/mm] = [mm] \sigma [/mm] '$.







Was ich bei [mm] $\Rightarrow$ [/mm] verstanden habe:


Sei [mm] $\sigma \in S_{n}$. [/mm]

Die Konjugationsklasse von [mm] $\sigma$ [/mm] unter [mm] $S_{n}$ [/mm] ist die Menge [mm] $\sigma^{S_{n}} [/mm] = [mm] \{ \gamma \circ \sigma \circ \gamma \; \vert \; \gamma \in S_{n}\}$. [/mm]


Die Menge [mm] $\sigma^{S_{n}}$ [/mm] ist die Bahn von [mm] $\sigma$ [/mm] unter [mm] $S_{n}$ [/mm] bezüglich der Operation

[mm] $\*: S_{n} \times S_{n} \rightarrow S_{n}, (\sigma, \gamma) \mapsto \sigma \* \gamma [/mm] := [mm] \gamma \circ \sigma \circ \gamma^{- 1}$. [/mm]


Sei [mm] $\sigma' \in \sigma^{S_{n}}$. [/mm] Dann existiert ein [mm] $\gamma \in S_{n}$ [/mm] so, dass [mm] $\sigma' [/mm] = [mm] \gamma \circ \sigma' \circ \gamma^{- 1}$ [/mm]


Nach Lineare Algebra I können wir [mm] $\sigma$ [/mm] als Produkt disjunkter Zykel schreiben: [mm] $\sigma [/mm] = [mm] \sigma_{1} \circ \ldots \circ \sigma_{r}$. [/mm]


_________________________________________________________
Warum gilt nun  [mm] $\sigma' [/mm] = [mm] \gamma \sigma_{1} \gamma^{- 1} \circ \ldots \circ \gamma \sigma_{r} \gamma^{- 1}$ [/mm] ?

Und warum ist die Injektivität von $t$ dafür zuständig,
dass die Zykel [mm] $\gamma \sigma_{i} \gamma^{- 1}$ [/mm] disjunkt sind ?


Und wieso folgt aus dem Hinweis in der Aufgabenstellung, dass [mm] Zykellänge($\sigma_{i}$) [/mm] = [mm] Zykellänge($\gamma \sigma_{i} \gamma^{- 1} [/mm] $) gilt ?
_________________________________________________________



Jedenfalls folgt am Ende daraus, dass alle Elemente der Konjugationsklasse [mm] $\sigma^{S_{n}}$ [/mm] die selbe Partition von $n$ liefern wie [mm] $\sigma$. [/mm]

Also liefert jede Konjugationsklasse von [mm] $S_{n}$ [/mm] genau eine Partition von $n$.



Meine Fragen zur Hinrichtung sind in der Box enthalten, die ich versucht habe  darzustellen.


Wäre super, wenn mir jemand die Schritte erklären könnte.

Viele Grüße, Andrej


Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.

        
Bezug
Konjugationskl. von S_n Beweis: Antwort
Status: (Antwort) fertig Status 
Datum: 11:21 Do 11.06.2020
Autor: hippias


> [...]
> _________________________________________________________
>  Warum gilt nun  [mm]\sigma' = \gamma \sigma_{1} \gamma^{- 1} \circ \ldots \circ \gamma \sigma_{r} \gamma^{- 1}[/mm]
> ?

Es gilt in Gruppen ganz allgemein, dass [mm] $\gamma \sigma \tau\gamma^{-1}= \gamma \sigma \gamma^{-1}\gamma \tau \gamma^{-1}$ [/mm] ist.

>  
> Und warum ist die Injektivität von [mm]t[/mm] dafür zuständig,
>   dass die Zykel [mm]\gamma \sigma_{i} \gamma^{- 1}[/mm] disjunkt
> sind ?

Um disjunkte Mengen auf disjunkte Mengen abzubilden, genügt es Injektivität zu fordern.

>  
>
> Und wieso folgt aus dem Hinweis in der Aufgabenstellung,
> dass Zykellänge([mm]\sigma_{i}[/mm]) = Zykellänge([mm]\gamma \sigma_{i} \gamma^{- 1} [/mm])
> gilt ?

Hinweis: Für alle [mm]\sigma \in S_{n}[/mm] und alle Zykel [mm]t = (t_{1}, \ldots, t_{k}) \in S_{n}[/mm]
gilt: [mm]\sigma t \sigma^{- 1} = (\sigma(t_{1}), \ldots, \sigma(t_{k}))[/mm]

Welche Zykellänge hat $t= [mm] (t_{1}, \ldots, t_{k})$, [/mm] welche [mm] $\sigma [/mm] t [mm] \sigma^{- 1} =(\sigma(t_{1}), \ldots, \sigma(t_{k}))$? [/mm] Begründung?

>  _________________________________________________________
>  
>
>
> Jedenfalls folgt am Ende daraus, dass alle Elemente der
> Konjugationsklasse [mm]\sigma^{S_{n}}[/mm] die selbe Partition von [mm]n[/mm]
> liefern wie [mm]\sigma[/mm].
>  
> Also liefert jede Konjugationsklasse von [mm]S_{n}[/mm] genau eine
> Partition von [mm]n[/mm].
>  
>
>
> Meine Fragen zur Hinrichtung sind in der Box enthalten, die
> ich versucht habe  darzustellen.
>  
>
> Wäre super, wenn mir jemand die Schritte erklären
> könnte.
>  
> Viele Grüße, Andrej
>  
>
> Ich habe diese Frage in keinem Forum auf anderen
> Internetseiten gestellt.


Bezug
                
Bezug
Konjugationskl. von S_n Beweis: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 08:18 So 14.06.2020
Autor: Andrejtrikolor

Morgen. Sorry für die verspätete Antwort, konnte erst jetzt.


>  Es gilt in Gruppen ganz allgemein, dass [mm]\gamma \sigma \tau\gamma^{-1}= \gamma \sigma \gamma^{-1}\gamma \tau \gamma^{-1}[/mm]
> ist.

Mensch, jetzt sehe ich es auch. Das war richtig billig. Ich danke dir.



>  
> >  

> > Und warum ist die Injektivität von [mm]t[/mm] dafür zuständig,
>  >   dass die Zykel [mm]\gamma \sigma_{i} \gamma^{- 1}[/mm] disjunkt
> > sind ?
>  Um disjunkte Mengen auf disjunkte Mengen abzubilden,
> genügt es Injektivität zu fordern.


Genau. Das ist auch der Grund, warum man ein Zykel aus [mm] $S_{n}$ [/mm] als Produkt disjunkter Zykeln schreiben kann, weil jedes Element aus [mm] $S_{n}$ [/mm] bijektiv und damit auch injektiv ist.


[mm] $\sigma' [/mm] = [mm] \gamma\circ \sigma \circ \gamma^{- 1}$ [/mm] ist auch bijektiv und damit injektiv.  Also kann man [mm] $\sigma'$ [/mm] auch in disjunkten Zykeln zerlegen.

Aber ich sehe leider immer noch nicht, warum diese disjunkten Zykeln von [mm] $\sigma'$ [/mm] gerade die Zykeln [mm] $\gamma \circ \sigma_{i} \circ \gamma^{- 1}$ [/mm]  sind.

Ich habe an der Stelle echt eine miese Blockade.


Hättest du an dieser Stelle noch einen Tipp für mich ?

> >  

> >
> > Und wieso folgt aus dem Hinweis in der Aufgabenstellung,
> > dass Zykellänge([mm]\sigma_{i}[/mm]) = Zykellänge([mm]\gamma \sigma_{i} \gamma^{- 1} [/mm])
> > gilt ?
>  Hinweis: Für alle [mm]\sigma \in S_{n}[/mm] und alle Zykel [mm]t = (t_{1}, \ldots, t_{k}) \in S_{n}[/mm]
> gilt: [mm]\sigma t \sigma^{- 1} = (\sigma(t_{1}), \ldots, \sigma(t_{k}))[/mm]
>  
> Welche Zykellänge hat [mm]t= (t_{1}, \ldots, t_{k})[/mm], welche
> [mm]\sigma t \sigma^{- 1} =(\sigma(t_{1}), \ldots, \sigma(t_{k}))[/mm]?
> Begründung?

Die Zykellänge von $t$ ist $k$.  Und die Zykellänge von [mm] $\sigma [/mm] t [mm] \sigma^{- 1}$ [/mm] ist auch $k$, da [mm] $\sigma [/mm] t [mm] \sigma^{- 1}$ [/mm] $k$ Einträge hat.

Das macht Sinn. Ich habe irgendwie in eine ganz andere Richtung gedacht.


Freue mich auf eine Antwort.

Lg und einen schönen Sonntag,

Andrej

Bezug
                        
Bezug
Konjugationskl. von S_n Beweis: Antwort
Status: (Antwort) fertig Status 
Datum: 14:30 Mo 15.06.2020
Autor: hippias


> Morgen. Sorry für die verspätete Antwort, konnte erst
> jetzt.
>  
>
> >  Es gilt in Gruppen ganz allgemein, dass [mm]\gamma \sigma \tau\gamma^{-1}= \gamma \sigma \gamma^{-1}\gamma \tau \gamma^{-1}[/mm]

> > ist.
>  
> Mensch, jetzt sehe ich es auch. Das war richtig billig. Ich
> danke dir.
>  
>
>
> >  

> > >  

> > > Und warum ist die Injektivität von [mm]t[/mm] dafür zuständig,
>  >  >   dass die Zykel [mm]\gamma \sigma_{i} \gamma^{- 1}[/mm]
> disjunkt
> > > sind ?
>  >  Um disjunkte Mengen auf disjunkte Mengen abzubilden,
> > genügt es Injektivität zu fordern.
>  
>
> Genau. Das ist auch der Grund, warum man ein Zykel aus
> [mm]S_{n}[/mm] als Produkt disjunkter Zykeln schreiben kann, weil
> jedes Element aus [mm]S_{n}[/mm] bijektiv und damit auch injektiv
> ist.
>  
>
> [mm]\sigma' = \gamma\circ \sigma \circ \gamma^{- 1}[/mm] ist auch
> bijektiv und damit injektiv.  Also kann man [mm]\sigma'[/mm] auch in
> disjunkten Zykeln zerlegen.
>  
> Aber ich sehe leider immer noch nicht, warum diese
> disjunkten Zykeln von [mm]\sigma'[/mm] gerade die Zykeln [mm]\gamma \circ \sigma_{i} \circ \gamma^{- 1}[/mm]
>  sind.
>  
> Ich habe an der Stelle echt eine miese Blockade.
>  
>
> Hättest du an dieser Stelle noch einen Tipp für mich ?
>  

Rechne es nach: Sei [mm] $\zeta= (i_{1},\ldots, i_{k})\in S_{n}$ [/mm] ein $k$-Zykel und [mm] $\sigma\in S_{n}$. [/mm] Setze [mm] $\zeta'= \zeta^{\sigma}$. [/mm] Wohin wird [mm] $i_{1}^{\sigma}$ [/mm] von $zeta'$ abgebildet? Wohin dieses Element? Usw.

> > >  

> > >
> > > Und wieso folgt aus dem Hinweis in der Aufgabenstellung,
> > > dass Zykellänge([mm]\sigma_{i}[/mm]) = Zykellänge([mm]\gamma \sigma_{i} \gamma^{- 1} [/mm])
> > > gilt ?
>  >  Hinweis: Für alle [mm]\sigma \in S_{n}[/mm] und alle Zykel [mm]t = (t_{1}, \ldots, t_{k}) \in S_{n}[/mm]
> > gilt: [mm]\sigma t \sigma^{- 1} = (\sigma(t_{1}), \ldots, \sigma(t_{k}))[/mm]
>  
> >  

> > Welche Zykellänge hat [mm]t= (t_{1}, \ldots, t_{k})[/mm], welche
> > [mm]\sigma t \sigma^{- 1} =(\sigma(t_{1}), \ldots, \sigma(t_{k}))[/mm]?
> > Begründung?
>  
> Die Zykellänge von [mm]t[/mm] ist [mm]k[/mm].  Und die Zykellänge von
> [mm]\sigma t \sigma^{- 1}[/mm] ist auch [mm]k[/mm], da [mm]\sigma t \sigma^{- 1}[/mm]
> [mm]k[/mm] Einträge hat.

Auch hier geht Injektivität ein.

>
> Das macht Sinn. Ich habe irgendwie in eine ganz andere
> Richtung gedacht.
>  
>
> Freue mich auf eine Antwort.
>  
> Lg und einen schönen Sonntag,
>
> Andrej


Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Algebra"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.unimatheforum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]