Signum der Permutation < Sonstiges < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
Status: |
(Frage) beantwortet | Datum: | 12:45 Mo 07.12.2009 | Autor: | JanW1989 |
Aufgabe | Berechnen Sie das Signum [mm] sgn(\sigma) [/mm] der Permutation
[mm] \sigma [/mm] = [mm] \pmat{ 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 4 & 3 & 5 & 1 & 8 & 2 & 7 & 6} [/mm] |
Das Signum einer Permutation bezieht sich ja auf die Anzahl der Fehlstände, das heißt die Fälle in denen i < j und [mm] \sigma [/mm] (i) > [mm] \sigma [/mm] (j) ist.
Wenn ich jetzt in meinem Fall durchzähle komme ich auf 2 Fehlstände, in Spalte 1 und 5.
Nach Definition ist für eine gerade Anzahl an Fehlständen [mm] sgn(\sigma)=1, [/mm] also positiv. Nun ist es nur leider so, dass [mm] sgn(\sigma)=-1 [/mm] als Lösung angegeben ist.
Wo liegt mein Denkfehler, oder sollte es wirklich das erste Mal vorgekommen sein, dass die angegebene Lösung falsch ist ;)
Gruß,
Jan
|
|
|
|
Status: |
(Antwort) fertig | Datum: | 13:04 Mo 07.12.2009 | Autor: | statler |
Mahlzeit!
> Berechnen Sie das Signum [mm]sgn(\sigma)[/mm] der Permutation
> [mm]\sigma[/mm] = [mm]\pmat{ 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 4 & 3 & 5 & 1 & 8 & 2 & 7 & 6}[/mm]
>
> Das Signum einer Permutation bezieht sich ja auf die Anzahl
> der Fehlstände, das heißt die Fälle in denen i < j und
> [mm]\sigma[/mm] (i) > [mm]\sigma[/mm] (j) ist.
> Wenn ich jetzt in meinem Fall durchzähle komme ich auf 2
> Fehlstände, in Spalte 1 und 5.
Ich komme auf viel mehr. Mach einfach eine Liste für alle Paare i < j und markier die, bei denen ein Fehlstand vorliegt.
> Nach Definition ist für eine gerade Anzahl an
> Fehlständen [mm]sgn(\sigma)=1,[/mm] also positiv. Nun ist es nur
> leider so, dass [mm]sgn(\sigma)=-1[/mm] als Lösung angegeben ist.
> Wo liegt mein Denkfehler, oder sollte es wirklich das
> erste Mal vorgekommen sein, dass die angegebene Lösung
> falsch ist ;)
Nach meiner Überschlagsrechnung ist die Lösung richtig. Ich kriege 28 Paare mit 11 Fehlständen (o. G.).
Gruß aus HH-Harburg
Dieter
|
|
|
|
|
Status: |
(Mitteilung) Reaktion unnötig | Datum: | 17:56 Mi 09.12.2009 | Autor: | JanW1989 |
Hi,
danke für deine Antwort.
Ich hatte da was falsch verstanden, aber jetzt ist's mir klar ;)
Gruß, Jan
|
|
|
|
|
Status: |
(Mitteilung) Reaktion unnötig | Datum: | 18:14 Mi 09.12.2009 | Autor: | ms2008de |
Hallo,
> Berechnen Sie das Signum [mm]sgn(\sigma)[/mm] der Permutation
> [mm]\sigma[/mm] = [mm]\pmat{ 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 4 & 3 & 5 & 1 & 8 & 2 & 7 & 6}[/mm]
>
Man kann das Signum übrigens auch berechnen indem man die Permutation umschreibt als Verkettung von Transpositionen: So ist [mm] \sigma [/mm] = (1 4) (2 3)(3 5)(5 8)(8 6). Da jede Transposition Signum -1 hat, ist [mm] sgn(\sigma) [/mm] = [mm] (-1)^5 [/mm] =-1
Viele Grüße
|
|
|
|