Darstellung Permutation < Determinanten < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 02:11 Mi 18.07.2012 | | Autor: | FroschQuak |
| Aufgabe | | Zeigen Sie: Jede Permutation ist das Produkt von Transpositionen der Form (i, i+1) |
Hi,
wir haben bereits gezeigt, dass jede Permutation das Produkt von Transpositionen ist. Daher genügt es zu zeigen, dass jede Transposition das Produkt von Transposition der Form (i,i+1) ist. Ich nehme an man kommt hier mit einer Induktion weiter, komm aber grad nicht drauf wie diese im einzelnen durchzuführen ist.
Ich würd mich freuend wenn mir das jeman helfen könnt. Danke :)
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
Du wolltest einen Tipp. Der beste Weg ist wohl es erst an einem Beispiel zu machen.
Probier doch mal in S7
(24),(25),(26) als Produkt von Transpositionen darzustellen.
|
|
|
| |
|
Danke für die Antwort :). Warum das ganze funktioniert ist mir klar. Ich zeigs aber nochmal an Deinem Beispiel um zu zeigen, dass ich mir auch damit ausseinandergesetzt habe:
(2,6) kann man zum beispiel schreiben als (2,3), (3,4),(4,5),(5,6),(4,5),(3,4),(2,3).
Mir ist aber noch nicht klar wie man das formal schön zeigen kann. Hab wie gesagt schon ein bisschen mit Induktion probiert aber ich weiß nicht genau wie diese Durchzuführen ist. Mein Anatz war dafür bisher
Sei Sn die Permutationsgruppe zum Index n. Sei (i,i+k) eine Transposition , [mm] k\in{1,..,n-i}. [/mm] Wir zeigen die Beh durch Induktion über k.
IA:(k=1): Ist klar, denn die Transposition hat selber diese Form
IV:(für ein k) Die Beh. sei für k-1 bereits gezeigt.
IS: Wir betrachten (i,i+k). Jetzt komm ich nicht weiter. Wenn ich etwa eine Transposition der Form (i,i+1) damit multipliziere erhalte ich eine Permutation die keine Transposition ist und somit kann ich die IV nicht benutzen.
Sorry das ich erst jetzt mit dem Ansatz rausrücke :)
Ps. Ich möchte eigentlich wirklich nur einen Tip. Die Aufgabe ist zur Klausurvorbereitung, aber wahrscheinlich ist ein Tip schon fast die Lösung :P
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 11:24 Do 19.07.2012 | | Autor: | FroschQuak |
Die Zeit ist jetzt bald abgelaufen. Bis zum 25.07.12 bin ich immernoch an einer Antwort interessiert und werde regelmäßig nachschauen ob mir jemand geantwortet hat. Danke.
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 11:41 Do 19.07.2012 | | Autor: | felixf |
Moin!
> Danke für die Antwort :). Warum das ganze funktioniert ist
> mir klar. Ich zeigs aber nochmal an Deinem Beispiel um zu
> zeigen, dass ich mir auch damit ausseinandergesetzt habe:
>
> (2,6) kann man zum beispiel schreiben als (2,3),
> (3,4),(4,5),(5,6),(4,5),(3,4),(2,3).
Etwas systematischer: du hast ja 1 2 3 4 5 6 7 ...
Du willst 2 mit 6 tauschen.
Dazu hast du erst die 2 zur 5 geschoben indem du sie immer mit dem Nachbarn getauscht hast:
1 2 3 4 5 6 7 ...
1 3 2 4 5 6 7 ...
1 3 4 2 5 6 7 ...
1 3 4 5 2 6 7 ...
Dann hast du 2 und 6 getauscht:
1 3 4 5 2 6 7 ...
1 3 4 5 6 2 7 ...
Und dann die 6 wieder dorthin geschoben wo vorher die 2 war:
1 3 4 5 6 2 7 ...
1 3 4 6 5 2 7 ...
1 3 6 4 5 2 7 ...
1 6 3 4 5 2 7 ...
Diesen Prozess musst du jetzt etwas formalisieren, also formaler aufschreiben. Welche Transpositionen hast du zwischen zwei der obigen Schritten?
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:32 Do 19.07.2012 | | Autor: | FroschQuak |
Hier nochmal Deine andere Lösung in formalisierter Form:
Sei (i,j) eine Transposition. Wir betrachten id [mm] \in [/mm] Sn und multiplizieren diese Permutation für k = i,...,j von recht mit (k,k+1). Wir erhalten eine Permutation [mm] \pi [/mm] die sozusagen i an Position j schiebt. Nun multiplizieren wir [mm] \pi [/mm] für k = j-1, ... , i von rechts mit (k,k+1) und erhalten die Trasposition (i,j).
So etwa? Ist das denn auch ein formaler Beweis der in einer Klausur Gültigkeit fänd?
lg der Frosch
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 11:46 Do 19.07.2012 | | Autor: | felixf |
Moin!
Per Induktion geht's auch:
> Sei Sn die Permutationsgruppe zum Index n. Sei (i,i+k) eine
> Transposition , [mm]k\in{1,..,n-i}.[/mm] Wir zeigen die Beh durch
> Induktion über k.
>
> IA:(k=1): Ist klar, denn die Transposition hat selber diese
> Form
>
> IV:(für ein k) Die Beh. sei für k-1 bereits gezeigt.
>
> IS: Wir betrachten (i,i+k). Jetzt komm ich nicht weiter.
> Wenn ich etwa eine Transposition der Form (i,i+1) damit
> multipliziere erhalte ich eine Permutation die keine
> Transposition ist und somit kann ich die IV nicht benutzen.
Nicht direkt. Aber schreibe doch $(i, i+k) = (i+k-1, i+k) (i, i+k-1) (i+k-1, i+k)$.
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:04 Do 19.07.2012 | | Autor: | FroschQuak |
Hil Felix,
danke für die Antwort. Mir war nicht direkt klar, dass
> (i, i+k) = (i+k-1, i+k) (i, i+k-1) (i+k-1, i+k)
gilt, hab das dann aber nochmal im Detail aufgeschrieben :). Für Interessierte hier nochmal der Induktionsschritt:
IS: Wir betrachten (i,i+k). Nun gilt
(*) (i, i+k) = (i+k-1, i+k) (i, i+k-1) (i+k-1, i+k)
wobei sich (i,i+k-1) nach IV eine Darstellung als Produkt von Transpositionen der gewünschten Form besitzt und (i+k-1, i+k) selbst eine Transposition der form (j,j+1) ist.
Um zu Zeigen dass (*) gilt schreiben wir das Produkt
(i+k-1, i+k) (i, i+k-1) (i+k-1, i+k) genauer auf.
(... (i+k-1) (i+k) ...) * (... i ... (i+k-1)...) * (i+k,i+k-1)
(... (i+k) (i+k-1)...) (...(i+k-1) ... i ...)
= (... i ... (i+k-1) (i+k) ...) * (i+k,i+k-1)
(... (i+k) ... (i) (i+k-1) ...)
= (i,i+k)
Ich hoffe meine Schreibweise ist klar. Die Klammern an den Ränder die übereinandern sind sollen durchgezogen sein.
|
|
|
|
