Permutation

09.01.2013, 20:43

MatheNoobii

Permutation

Meine Aufgabe lautet:

a) Geben Sie alle Elemente von $\begin{eqnarray*} S_3 \end{eqnarray*}$ an.
b) Es sei
$\begin{eqnarray*} \sigma= \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 4 & 3 & 2 & 5 & 1 \end{pmatrix} \end{eqnarray*}$

eine Permutation. Berechnen Sie $\begin{eqnarray*} \sigma^2, \sigma^3 \end{eqnarray*}$ und $\begin{eqnarray*} \sigma^{-1} \end{eqnarray*}$ , das Signum von $\begin{eqnarray*} \sigma \end{eqnarray*}$ und schreiben
Sie $\begin{eqnarray*} \sigma \end{eqnarray*}$ als endliche Komposition von Transpositionen. Gibt es ein $\begin{eqnarray*} n \in N \end{eqnarray*}$ , so dass $\begin{eqnarray*} \sigma^n = \sigma \end{eqnarray*}$ ?
Wenn ja, geben Sie das kleinstmögliche $\begin{eqnarray*} n \geq 2 \end{eqnarray*}$ an.

Meine Ideen:

a) Hier würde ich vorschlagen:
$\begin{eqnarray*} S_3=\{(123),(132),(213),(231),(312),(321)\} \end{eqnarray*}$

b) $\begin{eqnarray*} \sigma^2 = \sigma \circ \sigma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 4 & 3 & 2 & 5 & 1 \end{pmatrix} \circ \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 4 & 3 & 2 & 5 & 1 \end{pmatrix} = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 5 & 2 & 3 & 1 & 4 \end{pmatrix} \end{eqnarray*}$

$\begin{eqnarray*} \sigma^3 = \sigma \circ \sigma \circ \sigma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 4 & 3 & 2 & 5 & 1 \end{pmatrix} \circ \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 4 & 3 & 2 & 5 & 1 \end{pmatrix} \circ \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 4 & 3 & 2 & 5 & 1 \end{pmatrix}= \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 1 & 3 & 2 & 4 & 5 \end{pmatrix} \end{eqnarray*}$

Wie sieht es bei $\begin{eqnarray*} \sigma^{-1} \end{eqnarray*}$ aus?

$\begin{eqnarray*} \sigma^{-1} \end{eqnarray*}$ = ??? (Hier weiß ich nicht wie ich vorgehen muss)

Signum von $\begin{eqnarray*} \sigma \end{eqnarray*}$ berechnen:

Das Signum ist $\begin{eqnarray*} sign( \sigma ) :=(-1)^{a(\sigma)} \end{eqnarray*}$ , wobei $\begin{eqnarray*} a(\sigma) \end{eqnarray*}$ die Anzahl der Fehlstände ist. Also kommt je nachdem ob es eine gerade oder ungerade Anzahl von Fehlständen ist entweder $\begin{eqnarray*} 1 \end{eqnarray*}$ oder $\begin{eqnarray*} -1 \end{eqnarray*}$ heraus.
Ein Fehlstand ist ein Paar $\begin{eqnarray*} (i, j), i < j \wedge \sigma(i) > \sigma(j) \end{eqnarray*}$
Demnach wäre (2,3) ein Fehlstand! Wäre (3,2) dann auch ein Fehlstand? Oder kann das Paar sobald i > j ist kein Fehlstand mehr sein?
(4,5) ist definitiv auch ein Fehlstand!
(5,1) wäre dann je nach dem auch (k)ein Fehlstand!

Ich denke mal (3,2) und (5,1) sind keine Fehlstände.
Daraus folgt: $\begin{eqnarray*} sign( \sigma ) :=(-1)^{2} = 1 \end{eqnarray*}$

$\begin{eqnarray*} n \in N \end{eqnarray*}$ , so dass $\begin{eqnarray*} \sigma^n = \sigma \end{eqnarray*}$ :

n=8, da die Zahlen 2 und 3 für n=3 und die Zahlen 1,4 und 5 für n=4 wieder in die Ausgangslage gehen: 3*4=12

$\begin{eqnarray*} \sigma^{12} = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 4 & 3 & 2 & 5 & 1 \end{pmatrix} \end{eqnarray*}$

Würde das mit der endlichen Komposition von Transpositionen so funktionieren?

$\begin{eqnarray*} \sigma= \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 1 & 2 & 3 & 4 & 5 \end{pmatrix}= id = gerade \end{eqnarray*}$

$\begin{eqnarray*} \sigma= \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 4 & 2 & 3 & 1 & 5 \end{pmatrix}= (1 4) = ungerade \end{eqnarray*}$

$\begin{eqnarray*} \sigma= \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 4 & 2 & 3 & 5 & 1 \end{pmatrix}= (1 4) \circ (4 5) = gerade \end{eqnarray*}$

$\begin{eqnarray*} \sigma= \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 4 & 3 & 2 & 5 & 1 \end{pmatrix}= (1 4) \circ (4 5) \circ (2 3) = ungerade \end{eqnarray*}$

10.01.2013, 17:12

Math1986

Auf diesen Beitrag antworten »

RE: Permutation

Zitat:

Original von MatheNoobii

a) Hier würde ich vorschlagen:
$\begin{eqnarray*} S_3=\{(123),(132),(213),(231),(312),(321)\} \end{eqnarray*}$

In Tupelschreibweise ist das korrekt, in Zykelschreibweise nicht. So wie du es schreibst sieht es eher nach Zykelschreibweise aus, denk daran, Kommas zwischen die Einträge zu setzen, da es sonst sehr leicht zu Missverständnissen kommt.

Zitat:

Original von MatheNoobii
b) $\begin{eqnarray*} \sigma^2 = \sigma \circ \sigma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 4 & 3 & 2 & 5 & 1 \end{pmatrix} \circ \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 4 & 3 & 2 & 5 & 1 \end{pmatrix} = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 5 & 2 & 3 & 1 & 4 \end{pmatrix} \end{eqnarray*}$

Korrekt.

Zitat:

Original von MatheNoobii
$\begin{eqnarray*} \sigma^3 = \sigma \circ \sigma \circ \sigma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 4 & 3 & 2 & 5 & 1 \end{pmatrix} \circ \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 4 & 3 & 2 & 5 & 1 \end{pmatrix} \circ \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 4 & 3 & 2 & 5 & 1 \end{pmatrix}= \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 1 & 3 & 2 & 4 & 5 \end{pmatrix} \end{eqnarray*}$

Korrekt. Du kannst hier $\begin{eqnarray*} \sigma^3=\sigma^2\circ\sigma \end{eqnarray*}$ schreiben und mit dem Ergebnis von oben weiterrechnen.

Zitat:

Original von MatheNoobii
Wie sieht es bei $\begin{eqnarray*} \sigma^{-1} \end{eqnarray*}$ aus?

$\begin{eqnarray*} \sigma^{-1} \end{eqnarray*}$ = ??? (Hier weiß ich nicht wie ich vorgehen muss)

Hier bildest du einfach nur die Umkehrabbildung von $\begin{eqnarray*} \sigma \end{eqnarray*}$ , am Besten zeichnest du dir einmal, welches Element worauf abgebildet wird, und bildest dann "andersrum" ab.

Zitat:

Original von MatheNoobii
Signum von $\begin{eqnarray*} \sigma \end{eqnarray*}$ berechnen:

Das Signum ist $\begin{eqnarray*} sign( \sigma ) :=(-1)^{a(\sigma)} \end{eqnarray*}$ , wobei $\begin{eqnarray*} a(\sigma) \end{eqnarray*}$ die Anzahl der Fehlstände ist. Also kommt je nachdem ob es eine gerade oder ungerade Anzahl von Fehlständen ist entweder $\begin{eqnarray*} 1 \end{eqnarray*}$ oder $\begin{eqnarray*} -1 \end{eqnarray*}$ heraus.
Ein Fehlstand ist ein Paar $\begin{eqnarray*} (i, j), i < j \wedge \sigma(i) > \sigma(j) \end{eqnarray*}$
Demnach wäre (2,3) ein Fehlstand! Wäre (3,2) dann auch ein Fehlstand? Oder kann das Paar sobald i > j ist kein Fehlstand mehr sein?
(4,5) ist definitiv auch ein Fehlstand!
(5,1) wäre dann je nach dem auch (k)ein Fehlstand!

Ich denke mal (3,2) und (5,1) sind keine Fehlstände.
Daraus folgt: $\begin{eqnarray*} sign( \sigma ) :=(-1)^{2} = 1 \end{eqnarray*}$

Jeder Fehlstand wird nur einmal gezählt.
Du zählst nur Paare $\begin{eqnarray*} (i,j) \end{eqnarray*}$ mit $\begin{eqnarray*} i<j \end{eqnarray*}$ .
(2,3) und (4,5) sind Fehlstände, es gibt aber noch mehr, zB Fehlstände mit 1.
Liste mal alle auf.

Zitat:

Original von MatheNoobii
$\begin{eqnarray*} n \in N \end{eqnarray*}$ , so dass $\begin{eqnarray*} \sigma^n = \sigma \end{eqnarray*}$ :

n=8, da die Zahlen 2 und 3 für n=3 und die Zahlen 1,4 und 5 für n=4 wieder in die Ausgangslage gehen: 3*4=12

$\begin{eqnarray*} \sigma^{12} = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 4 & 3 & 2 & 5 & 1 \end{pmatrix} \end{eqnarray*}$

Was denn nun, n=8 oder n=12? verwirrt

Offensichtlich ist $\begin{eqnarray*} \sigma^{12}= \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 4 & 3 & 2 & 5 & 1 \end{pmatrix}\neq\id \end{eqnarray*}$

Zitat:

Original von MatheNoobii
Würde das mit der endlichen Komposition von Transpositionen so funktionieren?

$\begin{eqnarray*} \sigma= \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 1 & 2 & 3 & 4 & 5 \end{pmatrix}= id = gerade \end{eqnarray*}$

$\begin{eqnarray*} \sigma= \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 4 & 2 & 3 & 1 & 5 \end{pmatrix}= (1 4) = ungerade \end{eqnarray*}$

$\begin{eqnarray*} \sigma= \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 4 & 2 & 3 & 5 & 1 \end{pmatrix}= (1 4) \circ (4 5) = gerade \end{eqnarray*}$

$\begin{eqnarray*} \sigma= \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 4 & 3 & 2 & 5 & 1 \end{pmatrix}= (1 4) \circ (4 5) \circ (2 3) = ungerade \end{eqnarray*}$

Ich weiß nicht ganz, was du meinst, aber du setzt Gleichheitszeichen an Stellen, die überhaupt nicht gleich sind.

Es gilt die Gleichheit
[latex]\sigma= \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 1 & 2 & 3 & 4 & 5 \end{pmatrix}=\left(1 4\right)\cdot\left(4,5\right)(5,1)[/l]

10.01.2013, 17:35

MatheNoobii

Auf diesen Beitrag antworten »

RE: Permutation
a) Okay werd ich machen!

b) Also so: $\begin{eqnarray*} \sigma^{-1}= \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 5 & 3 & 2 & 1 & 4 \end{pmatrix} \end{eqnarray*}$

Fehlstände: Das hab ich noch nicht verstanden, bin jetzt ziemlich verwirrt!

Sorry n=12 ist gemeint! Wenn ich n=3 setze, also $\begin{eqnarray*} \sigma^3 \end{eqnarray*}$ nehme, sind die Zahlen an der 2. und 3. Stelle, wieder in der Ausgangsposition, quasi jedes 2. mal... für n=1,3,5,7...
die Zahlen an 1. 4. und 5. Stelle sind für n=1,4,7,10... wieder in der Ausgangslage. Nun braucht man den kleinsten gemeinsamen Teiler und für $\begin{eqnarray*} n \geq 2 \end{eqnarray*}$ wäre dies 3*4= 12

Komposition von Transpositionen:

Hier war ich mir überhaupt nicht sicher, ob ich auf dem rechten Weg bin.
$\begin{eqnarray*} \sigma= \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 1 & 2 & 3 & 4 & 5 \end{pmatrix}=\left(1 4\right)\cdot\left(4,5\right)(5,1) \end{eqnarray*}$

Das versteh ich jetzt nun nicht :/

10.01.2013, 21:52

Math1986

Auf diesen Beitrag antworten »

RE: Permutation

Zitat:

Original von MatheNoobii
a) Okay werd ich machen!

b) Also so: $\begin{eqnarray*} \sigma^{-1}= \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 5 & 3 & 2 & 1 & 4 \end{pmatrix} \end{eqnarray*}$

Richtig.

Zitat:

Original von MatheNoobii
Fehlstände: Das hab ich noch nicht verstanden, bin jetzt ziemlich verwirrt!

Hm, hast du dir die Erklärung auf Wikipedia mal durchgelesen?

Zitat:

Original von MatheNoobii
Sorry n=12 ist gemeint! Wenn ich n=3 setze, also $\begin{eqnarray*} \sigma^3 \end{eqnarray*}$ nehme, sind die Zahlen an der 2. und 3. Stelle, wieder in der Ausgangsposition, quasi jedes 2. mal... für n=1,3,5,7...
die Zahlen an 1. 4. und 5. Stelle sind für n=1,4,7,10... wieder in der Ausgangslage. Nun braucht man den kleinsten gemeinsamen Teiler und für $\begin{eqnarray*} n \geq 2 \end{eqnarray*}$ wäre dies 3*4= 12

Das wäre der kleinste gemeinsameVielfache, aber ja.

Zitat:

Original von MatheNoobii
Komposition von Transpositionen:

Hier war ich mir überhaupt nicht sicher, ob ich auf dem rechten Weg bin.
$\begin{eqnarray*} \sigma= \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 1 & 2 & 3 & 4 & 5 \end{pmatrix}=\left(1 4\right)\cdot\left(4,5\right)(5,1) \end{eqnarray*}$

Das versteh ich jetzt nun nicht :/

Sorry, musste vorhin etwas überhastet weg, daher war das auch nicht korrekt unglücklich

$\begin{eqnarray*} \sigma= \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 1 & 2 & 3 & 4 & 5 \end{pmatrix}=\left(1\,4\right)\circ\left(4\,5\right)\circ\left(5\,1\right) \end{eqnarray*}$
Das ist eine Komposition von Transpositionen.

Hierraus kannst du auch direkt das Signum ablesen, hattet ihr das schon?

11.01.2013, 00:38

MatheNoobii

Auf diesen Beitrag antworten »

RE: Permutation
Ich denke jetzt habe ich das mit den Fehlständen verstanden:

$\begin{eqnarray*} \sigma= \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 4 & 3 & 2 & 5 & 1 \end{pmatrix} \end{eqnarray*}$

Fehlstände sind: $\begin{eqnarray*} (1,2),(1,3),(1,5),(2,3),(2,5)(3,5),(4,5) \Rightarrow \end{eqnarray*}$ 7 Fehlstände: $\begin{eqnarray*} sign( \sigma ) :=(-1)^{7} = -1 \end{eqnarray*}$

Zitat:

Sorry, musste vorhin etwas überhastet weg, daher war das auch nicht korrekt unglücklich

$\begin{eqnarray*} \sigma= \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 1 & 2 & 3 & 4 & 5 \end{pmatrix}=\left(1\,4\right)\circ\left(4\,5\right)\circ\left(5\,1\right) \end{eqnarray*}$
Das ist eine Komposition von Transpositionen.

Hierraus kannst du auch direkt das Signum ablesen, hattet ihr das schon?

Haha

Kein Problem smile

Nicht, dass ich wüsste? Wie liest man da das Signum heraus?

Aber zur Aufgabe:

Also ich muss die Permutation $\begin{eqnarray*} \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \end{pmatrix} \end{eqnarray*}$ aus $\begin{eqnarray*} \begin{pmatrix} 4 & 3 & 2 & 5 & 1 \end{pmatrix} \end{eqnarray*}$ mit endlich vielen Transpositionen erzeugen?

Wäre das nicht so?

$\begin{eqnarray*} \sigma= \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 1 & 2 & 3 & 4 & 5 \end{pmatrix}=\left(1\,4\right)\circ\left(4\,5\right)\circ\left(2\,3\right) \end{eqnarray*}$

Aber eigentlich dachte ich:

$\begin{eqnarray*} \sigma= \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 1 & 2 & 3 & 4 & 5 \end{pmatrix}= id \end{eqnarray*}$

Und

$\begin{eqnarray*} \sigma= \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 4 & 3 & 2 & 5 & 1 \end{pmatrix}=\left(1\,4\right)\circ\left(1\,5\right)\circ\left(2\,3\right) \end{eqnarray*}$

11.01.2013, 13:22

Math1986

Auf diesen Beitrag antworten »

RE: Permutation

Zitat:

Original von MatheNoobii
Ich denke jetzt habe ich das mit den Fehlständen verstanden:

$\begin{eqnarray*} \sigma= \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 4 & 3 & 2 & 5 & 1 \end{pmatrix} \end{eqnarray*}$

Fehlstände sind: $\begin{eqnarray*} (1,2),(1,3),(1,5),(2,3),(2,5)(3,5),(4,5) \Rightarrow \end{eqnarray*}$ 7 Fehlstände: $\begin{eqnarray*} sign( \sigma ) :=(-1)^{7} = -1 \end{eqnarray*}$

Achte auf die unterscheidung zwischen Zykel- und Tupelschreibweise, sonst ist es korrekt.

Zitat:

Sorry, musste vorhin etwas überhastet weg, daher war das auch nicht korrekt unglücklich

Zitat:

Original von MatheNoobii
$\begin{eqnarray*} \sigma= \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 1 & 2 & 3 & 4 & 5 \end{pmatrix}=\left(1\,4\right)\circ\left(4\,5\right)\circ\left(5\,1\right) \end{eqnarray*}$
Das ist eine Komposition von Transpositionen.

Hierraus kannst du auch direkt das Signum ablesen, hattet ihr das schon?

Haha

Kein Problem smile

Nicht, dass ich wüsste? Wie liest man da das Signum heraus?

Na, jede Transposition entspricht genau einem Fehlstand, so erhältst du das Signum.

Zitat:

Original von MatheNoobii
Aber zur Aufgabe:

Also ich muss die Permutation $\begin{eqnarray*} \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \end{pmatrix} \end{eqnarray*}$ aus $\begin{eqnarray*} \begin{pmatrix} 4 & 3 & 2 & 5 & 1 \end{pmatrix} \end{eqnarray*}$ mit endlich vielen Transpositionen erzeugen?

Wo steht das? Was ist die original Aufgabe?
So wie du es schreibst ist einfach nur die inverse Abbildung gesucht, diese hast du oben bestimmt.

Zitat:

Original von MatheNoobii
Wäre das nicht so?

$\begin{eqnarray*} \sigma= \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 1 & 2 & 3 & 4 & 5 \end{pmatrix}=\left(1\,4\right)\circ\left(4\,5\right)\circ\left(2\,3\right) \end{eqnarray*}$

Richtig, das schrieb ich ja oben schon.

Zitat:

Original von MatheNoobii
Aber eigentlich dachte ich:

$\begin{eqnarray*} \sigma= \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 1 & 2 & 3 & 4 & 5 \end{pmatrix}= id \end{eqnarray*}$

Richtig, das ist die identische Abbildung,

Zitat:

Original von MatheNoobii
Und

$\begin{eqnarray*} \sigma= \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 4 & 3 & 2 & 5 & 1 \end{pmatrix}=\left(1\,4\right)\circ\left(1\,5\right)\circ\left(2\,3\right) \end{eqnarray*}$

Falsch, richtig wäre
$\begin{eqnarray*} \sigma= \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 4 & 3 & 2 & 5 & 1 \end{pmatrix}=\left(1\,4\right)\circ\left(4\,5\right)\circ\left(2\,3\right) \end{eqnarray*}$

Neue Frage »

Antworten »

Permutation

Verwandte Themen