Ordnung Permutationsgruppen < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 23:05 So 16.05.2004 | | Autor: | nevinpol |
Hallo ich bins nochmal,
@Marc: Vielen Dank für deine Antworten
 ![[happy]](/images/smileys/happy.gif "[happy]")
(A)Wie kann ich beweisen, dass die
Ordnung einer Zyklus gleich seiner Länge ist?
(B)Wie bestimme ich die Ordnung eines
Produktes zweier elementfremder Zyklen?
Vielleicht schreibe ich mal erst die Aufgabenstellung
an bevor ich meine Idee dazu schreibe:
Sei G eine Gruppe mit neutralem Element [mm]e[/mm]. Die Ordnung [mm]ord(g)[/mm]
eines Gruppenelements [mm]g \in G[/mm] ist definiert als das
kleinste [mm]m \in \IN[/mm] mit [mm]g^m=e[/mm], sofern ein solches
[mm]m[/mm] existiert; gibt es kein derartiges [mm]m[/mm], setzt man [mm]ord(g) = \infty [/mm].
(Dieser Fall tritt zum Beispiel für von 0 verschiedene Elemente von [mm](\IZ,+) [/mm]ein.)
zu (A): Also ich habe mir gedacht:
Die Ordnung der [mm]S_n[/mm] (Permutationsgruppe) möge endlich sein.
Dann ist [mm]\pi[/mm] ein endlicher Zyklus. Sei m die Anzahl der Elemente von [mm]\pi[/mm].
Dann ist nach Definition m dir Ordnung von [mm]\pi[/mm].
Sei k die kleinste positive ganze Zahl k mit [mm]\pi^k=e[/mm].
Dann ist zu zeigen, dass k=m ist:
[mm]"k\le m":[/mm]
Ich zeige, dass [mm] e = \pi^0(i), \pi^1(i),\pi^2(i), ... , \pi^(k-1)(i)[/mm] verschieden sind.
Annahme:
[mm] \pi^i = \pi^j [/mm] mit [mm] 0 \le i < j < k[/mm] , so wäre
[mm] \pi^(j-i) = \pi^j \cdot (\pi^i)^1 = e [/mm] mit [mm]j-k
Dies ergibt ein Widerspruch!
Also hat [mm]\pi[/mm] mindestens die verschiedenen Elemente
[mm]\pi^0,\pi^1,\pi^2, ... , \pi^{k-1}[/mm]; damit hat [mm]\pi[/mm]
mindestens k Elemente, also ist [mm]m \ge k [/mm]
"[mm]m \le k":[/mm]
Ich zeige, dass [mm]S_n" :={\pi^0,\pi^1,\pi^2, ... , \pi^(k-1)}[/mm]
eine Untergruppe bildet.
Untergruppenkriterium:
Sicher ist [mm]S_n" \ne \emptyset [/mm].
Das Inverse eines Elements [mm]\pi" \in S_n [/mm] ist das Element
[mm]\pi^{k-i}[/mm], denn [mm]\pi^i \cdot \pi^{k-i} = \pi^k = e[/mm].
Da k-i eine nichtnegative ganze Zahl < (kleiner) k ist, ist auch
[mm]\pi^{k-i}[/mm] in [mm]S_n"[/mm].
Seien schliesslich [mm]\pi^i[/mm] und [mm]\pi^j[/mm] Elemente
von [mm]S_n"[/mm]. Es ist zu zeigen, dass
[mm]\pi^i \cdot \pi^j = \pi^{i+j}[/mm] in [mm]S_n"[/mm] ist.
Wenn i+j<k, ist es klar.
Wenn [mm]i+j \ge k[/mm] ist;
ist [mm]i+j=k+i"[/mm] mit [mm]0 \le i" [/mm]<[mm] k[/mm].
In diesem Fall ergibt sich:
[mm]\pi^{i+j}=\pi^{k+i"} = \pi^{k} \cdot \pi^{i"} = e\cdot \pi^{i"} = \pi^{i"} [/mm]
[mm]\pi^{i"} [/mm][mm] \in[/mm] [mm]S_n"[/mm]
Somit ist [mm]S_n"[/mm] eine Untergruppe von [mm]S_n[/mm],
die [mm]\pi[/mm] enthält.
Nach Definition von [mm]\pi[/mm] ist [mm]\pi[/mm] in [mm]S_n"[/mm] enthalten.
Also ist die Anzahl der Elemente von [mm]\pi[/mm] höchstens so gross wie die
Anzahl k der Elemente von [mm]S_n[/mm].
Okay... Puuuuuuh
zu (B) habe ich noch kein Idee.. ich hoffe jemand hat es
Vielen Dank und schöne Grüsse
nevinpol
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 01:22 Mo 17.05.2004 | | Autor: | Marc |
Hallo nevinpol,
> @Marc: Vielen Dank für deine Antworten
Gern geschehen
> (A)Wie kann ich beweisen, dass die
> Ordnung einer Zyklus gleich seiner Länge ist?
>
> (B)Wie bestimme ich die Ordnung eines
> Produktes zweier elementfremder Zyklen?
>
> Vielleicht schreibe ich mal erst die Aufgabenstellung
> an bevor ich meine Idee dazu schreibe:
>
>
> Sei G eine Gruppe mit neutralem Element [mm]e[/mm]. Die Ordnung
> [mm]ord(g)[/mm]
> eines Gruppenelements [mm]g \in G[/mm] ist definiert als das
> kleinste [mm]m \in \IN[/mm] mit [mm]g^m=e[/mm], sofern ein solches
> [mm]m[/mm] existiert; gibt es kein derartiges [mm]m[/mm], setzt man [mm]ord(g) = \infty [/mm].
>
> (Dieser Fall tritt zum Beispiel für von 0 verschiedene
> Elemente von [mm](\IZ,+) [/mm]ein.)
>
>
> zu (A): Also ich habe mir gedacht:
>
> Die Ordnung der [mm]S_n[/mm] (Permutationsgruppe) möge endlich sein.
Die Ordnung einer Gruppe ist ja einfach die Anzahl ihrer Elemente (und hat nichts mit der obigen Ordnung eines Gruppenelements zu tun) (das sage ich nur zur Sicherheit ). Da [mm] \operatorname{ord}S_n=2^n [/mm] ist sie immer endlich.
> Dann ist [mm]\pi[/mm] ein endlicher Zyklus. Sei m die Anzahl der
> Elemente von [mm]\pi[/mm].
Was ist denn die Anzahl der Elemente von [mm] $\pi$? [/mm] Meinst du damit die Länge des Zyklus?
> Dann ist nach Definition m dir Ordnung von [mm]\pi[/mm].
Das ist doch zu zeigen?!
> Sei k die kleinste positive ganze Zahl k mit [mm]\pi^k=e[/mm].
> Dann ist zu zeigen, dass k=m ist:
> [mm]"k\le m":[/mm]
> Ich zeige, dass [mm]e = \pi^0(i), \pi^1(i),\pi^2(i), ... , \pi^(k-1)(i)[/mm]
> verschieden sind.
Wenn du das zeigst, sagst du doch nichts über [mm] $k\le [/mm] m$ aus.
> Annahme:
> [mm]\pi^i = \pi^j[/mm] mit [mm]0 \le i < j < k[/mm] , so wäre
> [mm]\pi^(j-i) = \pi^j \cdot (\pi^i)^1 = e[/mm] mit [mm]j-k
>
> Dies ergibt ein Widerspruch!
> Also hat [mm]\pi[/mm] mindestens die verschiedenen Elemente
> [mm]\pi^0,\pi^1,\pi^2, ... , \pi^{k-1}[/mm]; damit hat [mm]\pi[/mm]
> mindestens k Elemente, also ist [mm]m \ge k[/mm]
Diesen Schluß verstehe ich nicht, s.o.
>
> "[mm]m \le k":[/mm]
> Ich zeige, dass [mm]S_n" :={\pi^0,\pi^1,\pi^2, ... , \pi^(k-1)}[/mm]
>
> eine Untergruppe bildet.
>
> Untergruppenkriterium:
> Sicher ist [mm]S_n" \ne \emptyset [/mm].
>
> Das Inverse eines Elements [mm]\pi" \in S_n[/mm] ist das Element
> [mm]\pi^{k-i}[/mm], denn [mm]\pi^i \cdot \pi^{k-i} = \pi^k = e[/mm].
>
> Da k-i eine nichtnegative ganze Zahl < (kleiner) k ist, ist
> auch
> [mm]\pi^{k-i}[/mm] in [mm]S_n"[/mm].
>
> Seien schliesslich [mm]\pi^i[/mm] und [mm]\pi^j[/mm] Elemente
> von [mm]S_n"[/mm]. Es ist zu zeigen, dass
> [mm]\pi^i \cdot \pi^j = \pi^{i+j}[/mm] in [mm]S_n"[/mm] ist.
>
> Wenn i+j<k, ist es klar.
>
> Wenn [mm]i+j \ge k[/mm] ist;
> ist [mm]i+j=k+i"[/mm] mit [mm]0 \le i" [/mm]<[mm] k[/mm].
>
> In diesem Fall ergibt sich:
>
> [mm]\pi^{i+j}=\pi^{k+i"} = \pi^{k} \cdot \pi^{i"} = e\cdot \pi^{i"} = \pi^{i"}[/mm]
>
> [mm]\pi^{i"} [/mm][mm] \in[/mm] [mm]S_n"[/mm]
>
> Somit ist [mm]S_n"[/mm] eine Untergruppe von [mm]S_n[/mm],
> die [mm]\pi[/mm] enthält.
> Nach Definition von [mm]\pi[/mm] ist [mm]\pi[/mm] in [mm]S_n"[/mm] enthalten.
> Also ist die Anzahl der Elemente von [mm]\pi[/mm] höchstens so
> gross wie die
> Anzahl k der Elemente von [mm]S_n[/mm].
>
>
> Okay... Puuuuuuh
Das muß ich mir nochmal in Ruhe ansehen, ich weiß noch nicht, ob man das so zeigen kann. Dein ganzer Beweis kommt mir aber ganz ähnlich dem Beweis der Wohldefiniertheit der Ordnung von [mm] $\pi$ [/mm] vor (also dass es tatsächlich ein kleinstes $k$ mit den Ordnungseigenschaften gibt.)
Ich meine jedenfalls, dass es viel einfacher zu zeigen ist:
Sei [mm] $\sigma\in S_n$ [/mm] ein Zyklus der Länge k, also [mm] $\sigma=$
[/mm]
Zu zeigen ist nun, dass [mm] $\sigma^k=\operatorname{id}$
[/mm]
Sei also [mm] $i\in\{1,\ldots,n\}$.
[/mm]
Falls [mm] $i\not\in\{i_0,\ldots,i_{k-1}\}$, [/mm] dann ist [mm] $\sigma(i)=i$, [/mm] also auch [mm] $\sigma^k(i)=i$.
[/mm]
Falls [mm] $i\not\in\{i_0,\ldots,i_{k-1}\}$, [/mm] dann ist [mm] $i=i_j$ [/mm] für ein $j$ mit [mm] $1\le j\le [/mm] k-1$.
OBdA sei $j=0$, also [mm] $i=i_0$ [/mm] (weil [mm] $=$)
[/mm]
Dann ist [mm] $\sigma(i)=\sigma(i_0)=i_1$, $\sigma(i)^2=i_2$, $\ldots$, $\sigma(i)^{k-1}=i_{k-1}$, $\sigma(i)^k=i_0=i$.
[/mm]
Zusammenfassend gilt also für alle [mm] $i\in\{1,\ldots,n\}$: $\sigma(i)^k=i$, [/mm] also [mm] $\sigma^k=\operatorname{id}$. [/mm]
Es bleibt noch zu zeigen, dass $k$ die kleinste natürliche Zahl ist mit [mm] $\sigma^k=\operatorname{id}$.
[/mm]
Angenommen, es gibt ein $m$ mit $m<k$ und [mm] $\sigma^m=\operatorname{id}$.
[/mm]
Dann gibt es auch ein [mm] $i\in\{i_0,\ldots,i_{k-1}\}$ [/mm] so dass [mm] $\sigma^m(i)=i$. [/mm] Das ist dann ein Widerspruch dazu, dass die Länge von [mm] $L(\sigma)=k$ [/mm] ist. [mm] $\Box$
[/mm]
> zu (B) habe ich noch kein Idee.. ich hoffe jemand hat
> es
Das würde ich ganz ähnlich meinem obigen Beweis machen.
Und zwar so (nur skizzenhaft):
Seien [mm] $\sigma,\tau \in S_n$ [/mm] zwei elementfremde Zyklen mit [mm] $L(\sigma)=k$ [/mm] und [mm] $L(\tau)=m$, [/mm] also [mm] $\sigma=$ [/mm] und [mm] $\tau=$.
[/mm]
Sei [mm] $i\in\{i_0,\ldots,i_{k-1}\}$ [/mm] und [mm] $j\in\{j_0,\ldots,j_{m-1}\}$.
[/mm]
Dann gilt [mm] $\sigma^k(i)=i$ [/mm] und [mm] $\tau^m(j)=j$.
[/mm]
Meine Behauptung ist nun, dass [mm] $\operatorname{ord}(\sigma\circ\tau)=\kgV(\operatorname{ord}\sigma,\operatorname{ord}\tau)$ [/mm] bzw. mit (A) [mm] $\operatorname{ord}(\sigma\circ\tau)=\kgV(k,m)$.
[/mm]
[mm] "$\operatorname{ord}(\sigma\circ\tau)\le \kgV(k,m)$":
[/mm]
Offenbar ist [mm] $\sigma^{\kgV(k,m)}(i)=i$ [/mm] und [mm] $\tau^{\kgV(k,m)}(j)=j$
[/mm]
[mm] "$\operatorname{ord}(\sigma\circ\tau)\ge \kgV(k,m)$":
[/mm]
Eine Gegenannahme führt auf den Widerspruch, dass dann Element $i$ existiert, dessen Ordnung nicht $k$ bzw. $m$ unter [mm] $\sigma$ [/mm] bzw. [mm] $\tau$ [/mm] ist.
Das müßtest du noch ausformulieren...
Viele Grüße,
Marc
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 01:36 Mo 17.05.2004 | | Autor: | nevinpol |
Eine gute Nacht wünsche ich Allen!!
Okay die Aufgabe überfordert mich ein bisschen aber ich setze
mich jetzt nochmal ran.. Wozu braucht der Mensch Schlaf??? hehe
Ich melde mich bestimmt noch öfter hier...
Leider sind wenige Fragen zu Schule und Oberstufe, so dass ich
auch mal was beantworten kann :((
Man möchte ja was zurückgeben. Okay dieses Kommentar gehört jetzt bestimmt nicht
in die Kategorie: [mm] Hochschule\Lineare [/mm] Algebra:)
Bis denn
nevinpol
|
|
|
|
