Signum, ein Beweis |
15.06.2004, 17:59 | Mazze | Auf diesen Beitrag antworten » |
Signum, ein Beweis Zu zeigen ist: So, ich hab mir gedacht, man kann doch jede Permutation als Produkt von transpositionen schreiben. Eine transposition ändert das Vorzeichen , das heißt ich könnte doch theoretisch die beiden permutationen als Transpositionen schreiben und dann einfach die Vorzeichen "zählen". mir ist klar das man in dem theoretischen beweis nicht zählen kann aber man kann eine Aussage über n treffen. Die Frage die ich habe ist, was ist das maximum an "sinnvollen" transpositionen um eine permutation zu erreichen? Mit sinnvoll erachte ich nichts doppelt zu machen so ich probiers mal wenn wer ne Idee hat melden ; ) |
||
15.06.2004, 18:30 | SirJective | Auf diesen Beitrag antworten » |
Jede n-stellige Permutation ist in höchstens n Transpositionen zu erreichen. Allerdings brauchst du das nicht. Es kommt nur darauf an, dass die Anzahl der Transpositionen für eine Permutation stets entweder gerade oder ungerade ist, egal wieviele man verwendet. D.h. z.B. die identische Permutation kann man mit 0 Transpositionen bekommen, oder mit 2, oder mit 4, aber niemals mit 3 Transpositionen. Und in dem theoretischen Beweis kannst du schon zählen - wenn du wirklich weisst (wissen darfst), dass jede Transposition das Vorzeichen ändert, und dass sich jede Permutation als Produkt von Transpositionen darstellen lässt. Gruss, SirJective |
||
15.06.2004, 18:44 | Mazze | Auf diesen Beitrag antworten » |
also meine Idee ist jetzt folgende und sind permutationen, wobei sich mit n transpositionen darstellen lässt und mit m transpositionen wobei m und n entwede rgenau gerade oder genau und gerade sind Sei C die Permutation also pi angewendet auf pi'. Dann ließe sich doch C mit n+m transpositionen darstellen sehe ich das richtig? Das heißt doch für das signum : So nun kommt die fall unterscheidung, wenn beide gerade permutationen sind dann ist das signum das ist gleich sgn(pi) *sgn(pi') <=> 1*1 usw. wäre der beweis damit abgeschlossen? |
||
15.06.2004, 18:50 | Poff | Auf diesen Beitrag antworten » |
@SirJective, Edit: ... du hast recht *gg* |
||
15.06.2004, 18:59 | SirJective | Auf diesen Beitrag antworten » |
Der Beweis wird dadurch erbracht, dass du feststellst, - dass die Permutation pi(pi') sich durch n+m Transpositionen darstellen lässt (was sofort klar ist, wenn pi und pi' durch n bzw. m Transpositionen dargestellt sind), - und dass sgn(pi) = (-1)^n richtig ist (das hängt nun von deiner Definition des Vorzeichens ab). Denn wegen (-1)^(n+m) = (-1)^n * (-1)^m folgt daraus sofort die Gleichung für das Signum, ohne Fallunterscheidung. @Poff: Ich versteh die Frage nicht. Was genau willst du tun? Stell deine Frage mal als eigenen Thread. |
||
15.06.2004, 19:01 | Mazze | Auf diesen Beitrag antworten » |
wunderbar, das schaut dann doch gleich eleganter aus dank dir :] |
||
Anzeige | ||
|
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |
|