Konjugationskl. von S_n Beweis < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| 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.
|
|
| |
|
| Status: |
(Antwort) fertig  | | 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.
|
|
|
| |
|
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
|
|
|
| |
|
| Status: |
(Antwort) fertig | | 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
|
|
|
|
