Permutation, Transposition Beweis

Neue Frage »

RedSunset Auf diesen Beitrag antworten »
Permutation, Transposition Beweis
Hallo erstmal an alle Wink ,
Bin ganz neu hier und hab bei einer Aufgabe ein Problem:
Mir fehlt jeglicher Ansatz leider bei folgender Aufgabenstellung:

Zeigen Sie:
Es gibt zu jedem Sn (Menge aller Permutationen) Transpositionen t1,...,tk Sn mit

Weis da jmd. Rat?
Schonmal Danke im Vorraus!

lg RedSunset
therisen Auf diesen Beitrag antworten »

Hallo,

die Behauptung erscheint einem intuitiv völlig klar, aber das exakt aufzuschreiben, ist nicht ganz einfach. Für die identische Abbildung gilt: (vgl. Zykelschreibweise). Sei nun . Ist , also z.B. mit , dann multipliziere von links mit . Dieses Verfahren wiederholt man nun solange bis ... gilt.
Das ist die Beweisidee. Mach dir das mal klar, dann weißt du auch, was an die Stelle mit den Pünktchen kommt.

Gruß, therisen
 
 
RedSunset Auf diesen Beitrag antworten »

was bezeichnet denn in deinem Beweisansatz das a und die jeweils . Mir ist zumindest schonmal klar dass die Permutation id ja sich selbst abbildet und somit ausgeschlossen werden muss, da ja sonst keine Transpositionen vorliegen ...
therisen Auf diesen Beitrag antworten »

Ah, sorry, das habe ich vergessen zu schreiben:

(...) habe also eine Darstellung (...)


Gruß, therisen
RedSunset Auf diesen Beitrag antworten »

okay dank dir
noch ein paar Fragen dazu:
1.) wie multipliziere ich jetzt eine permutation f mit einer transposition t1 ?
2.) Warum ist : ?
Bzw. die Schreibweise verstehe ich nicht so ganz ...
therisen Auf diesen Beitrag antworten »

ad 1) Die Frage macht so, wie du sie formuliert hast, keinen Sinn. Du meinst wohl, wie man zwei Permutationen multipliziert, wenn eine in Matrixdarstellung und eine in Zykeldarstellung gegeben ist. Das macht man, indem man die Zykelschreibweise in eine Matrixdarstellung umwandelt. Im Falle von Transpositionen ist das aber trivial und deswegen spart man sich das meistens Augenzwinkern

ad 2) Wenn gilt, dann muss es eine Stelle geben, sodass ist (). Wäre nämlich stets , dann wäre Augenzwinkern


Gruß, therisen
RedSunset Auf diesen Beitrag antworten »

wenn ich nun von links mit t1 multipliziere dann ordne ich doch damit via permutation dem m sein am zu so dass ich doch im prinzip dann in dem fall dass nur am != m ist mein f wieder bekomme! somit müsste ich dann in dem beispiel das ganze nur 1 mal vollziehen oder?
therisen Auf diesen Beitrag antworten »

Du musst dich klarer ausdrücken, ich verstehe dich nicht. Die Multiplikation mit bewirkt nur, dass an der Stelle gilt: . Dann schaust du eben wieder, ob es eine Stelle mit gibt, sodass . Falls ja, multiplizierst du wieder mit einer geeigneten Transposition . Das machst du solange, bis du die Identität erhältst. Und jetzt fang mal an, selbst etwas zu denken. Der Beweis ist dann nämlich schon fast fertig.


Gruß, therisen
RedSunset Auf diesen Beitrag antworten »

ah okay wunderbar ... jetzt ist mir gerade ein Licht aufgegangen Freude !
Nochmals vielen Dank !
RedSunset Auf diesen Beitrag antworten »

Ist es denn jetzt richtig dass ich das ganze (n-1)-lampda mal maximal multiplizieren muss?
und wenn ich jetzt k=(n-1)-lampda setze,
gilt dann schon mein ?

lg RedSunset
therisen Auf diesen Beitrag antworten »

Zitat:
Original von RedSunset
Ist es denn jetzt richtig dass ich das ganze (n-1)-lampda mal maximal multiplizieren muss?


Ja.

Zitat:
Original von RedSunset
und wenn ich jetzt k=(n-1)-lampda setze,
gilt dann schon mein ?


Mit dem Formalismus hast du es wohl nicht so ganz Augenzwinkern Am Schluss hast du Transpositionen, so dass gilt . Du musst jetzt schon noch zeigen, dass dann auch wirklich gilt.


Gruß, therisen
RedSunset Auf diesen Beitrag antworten »

wie zeige ich den letzten schritt denn?
Es ist doch klar dass wenn ich f mit t1 bis tk permutationen auf id zurückführen kann dass ich dann auch f durch t1 bis tk permutationen darstellen kann...
therisen Auf diesen Beitrag antworten »

Zitat:
Original von RedSunset
Es ist doch klar...


Eine solche Argumentation ist an dieser Stelle unangebracht Augenzwinkern Setze ein und verwende . Nachrechnen ergibt eine wahre Aussage.


Gruß, therisen
RedSunset Auf diesen Beitrag antworten »

also du meinst ich soll in einsetzen ? Wie rechne ich denn damit dann? Und was mache ich mit ? Was ist überhaupt? Und woher weisst du das dies gilt?
therisen Auf diesen Beitrag antworten »

Ist wohl doch nicht so klar Augenzwinkern Ein Grund mehr, diesen Schritt nicht wegzulassen.

Zitat:
Original von RedSunset
also du meinst ich soll in einsetzen ?


Richtig.

Zitat:
Original von RedSunset
Wie rechne ich denn damit dann? Und was mache ich mit ? Was ist überhaupt? Und woher weisst du das dies gilt?


Die Fragen zeigen, dass du eigentlich gar nicht so recht weißt, was du da tust Augenzwinkern
Wie schon weiter oben gesagt, schreibt man in der Algebra gerne jede Verknüpfung in einer (meist) nicht abelschen Gruppe mit dem Malzeichen, also . Der Bequemlichkeit halber lässt man dann den Malpunkt einfach weg (wie in der Analysis auch, z.B. ). Man weiß aber was gemeint ist. Gewöhne dich daran! Dann ist also . Dass dies gleich der Identität ist, ist trivial.



Gruß, therisen
RedSunset Auf diesen Beitrag antworten »

Zitat:
Dann ist also . Dass dies gleich der Identität ist, ist trivial.


stimmt ist wirklich trivial wenn man sich es ausschreibt in die Form !

OKay also setze ich mal ein:
in einsetzen ergibt:






qed

passt das so?
therisen Auf diesen Beitrag antworten »

Zitat:
Original von RedSunset





qed

passt das so?


Gefällt mir nicht, wie du das aufgeschrieben hast.




Gruß, therisen
RedSunset Auf diesen Beitrag antworten »

Zitat:
Original von therisen
Gefällt mir nicht, wie du das aufgeschrieben hast...




wie begründest du denn dieses Gleichheitszeichen dann?
therisen Auf diesen Beitrag antworten »

Zitat:
Original von RedSunset
Zitat:
Original von therisen
Gefällt mir nicht, wie du das aufgeschrieben hast...




wie begründest du denn dieses Gleichheitszeichen dann?




Folgt alles aus dem Assoziativgesetz.

Wie kommst du eigentlich darauf, dass in der vorletzten Zeile steht?
RedSunset Auf diesen Beitrag antworten »

genau so wie du es jetzt aufgeschrieben hast dachte ich es mir auch und hab ich es auch auf meinem zettel stehen ... ! weis auch nicht was die aufreihung von id sollte verwirrt .... vielen dank für die super erklärung!
therisen Auf diesen Beitrag antworten »

Zum Abschluss kannst du dir ja noch Gedanken über die Eindeutigkeit dieser Darstellung machen (modulo 2). Einen weiterführenden Beitrag dazu habe ich hier verfasst: sign(pi) eindeutig


Gruß, therisen
RedSunset Auf diesen Beitrag antworten »

ja denke ist eine gute weiterführende Übung, danke ... werd ich mal angehen das Problem!
RedSunset Auf diesen Beitrag antworten »

ich verstehe aber gerade nicht was die eindeutigkeit mit der restklasse 2 zu tun hat (modulo 2) ?
therisen Auf diesen Beitrag antworten »

Das modulo 2 bezieht sich auf die Länge, d.h. die Gesamtzahl deiner Transpositionen, die du verwendest, um darzustellen.


Gruß, therisen
RedSunset Auf diesen Beitrag antworten »

und warum ist das modulo 2 ?
therisen Auf diesen Beitrag antworten »

Weißt du überhaupt was das bedeutet, wenn man die Länge modulo 2 betrachten soll? So wie du deine Frage gestellt hast offenbar nicht.
RedSunset Auf diesen Beitrag antworten »

naja unter der "Gesamtzahl deiner Transpositionen" kann ich mir schon was vorstellen aber in wieweit das jetzt mit modulo 2 zusammenhängt ... nein
therisen Auf diesen Beitrag antworten »

Gilt und , dann ist nicht notwendigerweise , aber es gilt .
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »