Permutationen als Produkt elementfremder Zyklen darstellen

21.11.2012, 14:43

maho12

Permutationen als Produkt elementfremder Zyklen darstellen

Meine Frage:
Hallo.

Folgende Aufgabe soll ich lösen:
Stellen Sie die folgenden Permutaionen als Produkt elementefremder Zyklen dar und bestimmen Sie, welche der Permutationen gerade Permutationen sind.
$\begin{eqnarray*} \pi _{1}=(1,3,5)*(2,5,6)*(1,2,3,4,5,6,7) \end{eqnarray*}$
$\begin{eqnarray*} \pi _{2}=(1,2,3,5)*[(1,2,7)*(4,5,6)]^{-1} \end{eqnarray*}$
$\begin{eqnarray*} \pi _{3}\in S(Z13) \end{eqnarray*}$ mit $\begin{eqnarray*} \pi _{3}([n])=[2*n] \end{eqnarray*}$
$\begin{eqnarray*} \pi _{4}\in S(Z13) \end{eqnarray*}$ mit $\begin{eqnarray*} \pi _{4}([n])=[3*n] \end{eqnarray*}$

Meine Ideen:
Die ersten beide habe ich versucht zu lösen:

$\begin{eqnarray*} \pi _{1}=\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7\\ 3 & 2 & 5 & 4 & 1 & 6 & 7 \ \end{pmatrix} * \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7\\ 1 & 5 & 3 & 4 & 6 & 2 & 7 \ \end{pmatrix} * \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7\\ 2 & 3 & 4 & 5 & 6 & 7 & 1 \ \end{pmatrix}=\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7\\ 4 & 6 & 7 & 5 & 2 & 3 & 1 \ \end{pmatrix}=(1452637) \end{eqnarray*}$
Die Permutation ist ungerade, weil ungerade*ungerade = gerade und gerade*ungerade=ungerade.

$\begin{eqnarray*} \pi _{2}=\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7\\ 2 & 3 & 5 & 4 & 1 & 6 & 7 \ \end{pmatrix} * \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7\\ 7 & 1 & 3 & 6 & 4 & 5 & 2 \ \end{pmatrix} =\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7\\ 1 & 3 & 4 & 6 & 7 & 5 & 2 \ \end{pmatrix}=(1)(234657) \end{eqnarray*}$
Das ist gerade, weil gerade*gerade=gerade.

Stimmen die beiden so?

Bei den anderen beiden, komme ich nicht wirklich vorwärts.
Ich weiß, das S(Z13)=Z13! ist, aber wie nun weiter?
Hoffe ihr könnt mir helfen.

Danke.

21.11.2012, 15:29

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von maho12
Die Permutation ist ungerade, weil ungerade*ungerade = gerade und gerade*ungerade=ungerade.

Irgendwie hast du dir da die falsche Merkregel eingeprägt. unglücklich

Jedes Zykel der Länge $\begin{eqnarray*} L \end{eqnarray*}$ kann durch eine Verkettung von $\begin{eqnarray*} L-1 \end{eqnarray*}$ Transpositionen ersetzt werden. Man nimmt also alle jeweils um Eins verminderte Zykellängen, summiert diese, und je nachdem, ob die Summe gerade/ungerade ist, so ist dies auch die Permutation.

Die berechneten Zykeldarstellungen für $\begin{eqnarray*} \pi_1 \end{eqnarray*}$ und $\begin{eqnarray*} \pi_2 \end{eqnarray*}$ an sich scheinen aber richtig zu sein.

Zu $\begin{eqnarray*} \pi_3 \end{eqnarray*}$ und $\begin{eqnarray*} \pi_4 \end{eqnarray*}$ :

So gänzlich unvertraut im Rechnen mit Restklassen? Ich nenne mal den Beginn der Zykeldarstellung von $\begin{eqnarray*} \pi_3 \end{eqnarray*}$ :

$\begin{eqnarray*} \pi_3 = (1,2,4,8,3,\ldots \end{eqnarray*}$

letzteres, weil $\begin{eqnarray*} 2\cdot 8 = 16\equiv 3\bmod 13 \end{eqnarray*}$ ist.

21.11.2012, 16:46

maho12

Auf diesen Beitrag antworten »

Eine Transposition hat doch die Länge 2 oder?
Wie kann ich dann, wenn mein $\begin{eqnarray*} L \end{eqnarray*}$ bei $\begin{eqnarray*} \pi _{1} \end{eqnarray*}$ auf 2 bringen, wenn die Länge 7 ist?
Oder heißt das: (14) hat die Länge 2, das -1 und ich komme auf 1. Und da ich noch (26)(37)(45)(52)(63)(71) habe, komme ich dann auf 7 (wenn ich das, was ich bei (14) gemacht habe, bei den anderen analog so mache) und damit wäre das ungerade.

Zitat:

So gänzlich unvertraut im Rechnen mit Restklassen?

Allerdings.

Bei $\begin{eqnarray*} \pi _{3} \end{eqnarray*}$ muss ich bis zur 13 gehen oder?
Wie kommst auf (1,2,4,8,...)? Du hast als n=Z13 genommen und dann?
(Sorry, für die doofen Fragen.)

21.11.2012, 17:43

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von maho12
Wie kommst auf (1,2,4,8,...)? Du hast als n=Z13 genommen und dann?

Es ist ja $\begin{eqnarray*} \pi _{3}([n])=[2*n] \end{eqnarray*}$ , d.h. Restklasse $\begin{eqnarray*} [n] \end{eqnarray*}$ wird auf die Restklasse $\begin{eqnarray*} [2*n] \end{eqnarray*}$ abgebildet: Also [1] auf [2], [2] dann auf [4] usw. was ich gleich in die Zykeldarstellung überführt habe (unter "Weglassung" der Restklassenklammern) - mehr passiert hier nicht. Natürlich ist modulo 13 dann [16]=[3] .

21.11.2012, 18:11

maho12

Auf diesen Beitrag antworten »

Ja, klar.

Zitat:

Was ist damit?

21.11.2012, 18:23

HAL 9000

Auf diesen Beitrag antworten »

Du scheinst die Permutation in ihrer Funktionswertdarstellung mit der Zykeldarstellung zu verwechseln:

Dein $\begin{eqnarray*} \pi_1 \end{eqnarray*}$ hat doch NICHT die Zykeldarstellung $\begin{eqnarray*} (14)(26)(37)(45)(52)(63)(71) \end{eqnarray*}$ , sondern - wie du selbst oben noch richtig ausgerechnet hast - einfach $\begin{eqnarray*} (1452637) \end{eqnarray*}$ . Das ist ein einziger Zykel der Länge $\begin{eqnarray*} L=7 \end{eqnarray*}$ , daher ist $\begin{eqnarray*} L-1=6 \end{eqnarray*}$ gerade, und so ist auch die Permutation gerade.

Hättest du alternativ auch aus der Anfangsdarstellung $\begin{eqnarray*} \pi _{1}=(1,3,5)*(2,5,6)*(1,2,3,4,5,6,7) \end{eqnarray*}$ gewinnen können:

Hier ergibt die Summe der jeweils um Eins verminderten Zykellängen

$\begin{eqnarray*} (3-1) + (3-1) + (7-1) = 10 \end{eqnarray*}$

auch gerade.

21.11.2012, 18:27

maho12

Auf diesen Beitrag antworten »

Achso. Hab's verstanden.
Mich hatte das Wort Transposition dort verunsichern lassen.
Danke für deine Hilfe.

Neue Frage »

Antworten »

Permutationen als Produkt elementfremder Zyklen darstellen

Verwandte Themen