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 Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

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
Dt. Schulen im Ausland: Mathe-Seiten: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. Informatik • Physik • Technik • Biologie • Chemie
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.matheraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]