permutation sgn berechnen

11.11.2006, 23:47

iram

permutation sgn berechnen

hi, ich habe die permutationen $\begin{eqnarray*} p =\begin{pmatrix} 1 & 2 & 3 & 4 & 5\\ 2 & 3 & 4 & 1 & 5 \end{pmatrix} ; o = \begin{pmatrix} 1 & 2 & 3 & 4 & 5\\ 3 & 5 & 4 & 2 & 1 \end{pmatrix} \end{eqnarray*}$ . ich soll jetzt sgn(p) , sgn (o), sgn (o ° p), sgn (p °o) berechnen. ich weiß leider nur nicht was damit gemeint ist.kann mir das bitte jemand erklären?

12.11.2006, 00:02

Shurakai

Auf diesen Beitrag antworten »

Das Signum ist $\begin{eqnarray*} sign( \sigma ) :=(-1)^{a(\sigma)} \end{eqnarray*}$ , wobei $\begin{eqnarray*} a(\sigma) \end{eqnarray*}$ die Anzahl der Fehlstände sein soll. Ein Fehlstand ist ein Paar $\begin{eqnarray*} (i, j), i < j \wedge \sigma(i) > \sigma(j) \end{eqnarray*}$

In deinem Beispiel mit p wäre also (3,4) ein Fehlstand, weil 3 < 4 aber 4 > 1.

Suche also alle diese Fehlstände und dann kannst du das Signum leicht berechnen smile

12.11.2006, 00:02

therisen

Auf diesen Beitrag antworten »

Zitat:

Jede Permutation lässt sich entweder aus einer geraden oder aus einer ungeraden Zahl von Transpositionen, also Vertauschungen von nur zwei Elementen, zusammensetzen. Im ersten Fall hat die Permutation das Signum 1, im zweiten Fall das Signum -1. Dies ist äquivalent dazu, dass die Anzahl der Fehlstände oder Inversionen gerade bzw. ungerade ist.

http://de.wikipedia.org/wiki/Signum_%28Mathematik%29

Jetzt klar?]

12.11.2006, 00:19

iram

Auf diesen Beitrag antworten »

also bei p hab ich dann die 3 fehlstände:
(1,2) , (2,3) , (3,4).

-----kann ich das auch so auffassen das ich "3 - vertauschungen" vornehmen muss um auf die ursprüngliche ordnung zurück zu kommen?------

wäre dann also $\begin{eqnarray*} sgn (p) = (-1)^3 \end{eqnarray*}$

12.11.2006, 00:32

therisen

Auf diesen Beitrag antworten »

Zitat:

Original von iram
also bei p hab ich dann die 3 fehlstände:
(1,2) , (2,3) , (3,4).

Nein. $\begin{eqnarray*} (1,2) \end{eqnarray*}$ ist kein Fehlstand: Es ist $\begin{eqnarray*} 1<2 \end{eqnarray*}$ und $\begin{eqnarray*} p(1) = 2 < 3 = p(2) \end{eqnarray*}$ .

Gruß, therisen

12.11.2006, 00:45

iram

Auf diesen Beitrag antworten »

ja, stimmt. da hab ich nicht aufgepasst.

also habe ich hier nur 2 fehlstellungen, also sign(p)=1.

gilt sign(p°o)=sign(p)°sign(o)?

12.11.2006, 01:02

therisen

Auf diesen Beitrag antworten »

Ja, beides richtig. $\begin{eqnarray*} \mathrm{sgn} \end{eqnarray*}$ ist ja ein Homomorphismus.

12.11.2006, 01:37

iram

Auf diesen Beitrag antworten »

wie schreibe ich das am besten auf? gibt es da eine übliche schreibweise? vielen dank!

12.11.2006, 10:22

therisen

Auf diesen Beitrag antworten »

Wie schreibst du was am besten auf?

Mir ist gerade noch etwas aufgefallen. Du hast geschrieben, dass

Zitat:

sign(p°o)=sign(p)°sign(o)

Was soll denn aber bitte z.B. $\begin{eqnarray*} 4 \circ 3 \end{eqnarray*}$ sein? Richtig müsste es also $\begin{eqnarray*} \mathrm{sgn}(p \circ o)=\mathrm{sgn}(p)\cdot \mathrm{sgn}(o) \end{eqnarray*}$ .

Gruß, therisen

Neue Frage »

Antworten »

permutation sgn berechnen

Verwandte Themen