Permutationen und symmetrische Gruppe - Skript, falsch oder falsch verstanden

08.07.2011, 14:50

Pascal95

Permutationen und symmetrische Gruppe - Skript, falsch oder falsch verstanden

Hallo,

in diesem Skript über Permutationen und symmetrische Gruppen lese ich (auf Seite 2) folgendes:

Zitat:

Verfährt man nach diesem Algorithmus weiter, erhält man:
$\begin{eqnarray*} \sigma = \begin{pmatrix} 1 & 2 & 3&4&5&6&7 \\ 7&5&2&4&3&1&6 \end{pmatrix} =(176)(253)(4) \end{eqnarray*}$

Diese Zykelschreibweise ist natürlich keinesfalls eindeutig, ebenso können wir $\begin{eqnarray*} (253)(176)(4) \end{eqnarray*}$ oder aber auch $\begin{eqnarray*} (671)(532)(4) \end{eqnarray*}$ schreiben.

Allerdings meine ich, dass man das nicht kann.

Das Problem sehe ich bei $\begin{eqnarray*} (176)=(671) \end{eqnarray*}$ .

Das ist ja falsch, denn $\begin{eqnarray*} (671) \end{eqnarray*}$ ist keine zyklische Vertauschung von $\begin{eqnarray*} (176) \end{eqnarray*}$ sondern einfach umgedreht.

6 wird ja schließlich nicht auf 7 abgebildet.
7 wird auch nicht auf 1 abgebildet.
1 auch nicht auf 6.

Bitte um Korrektur smile

Vielen Dank

08.07.2011, 15:02

jester.

Auf diesen Beitrag antworten »

Es ist zwar richtig, dass man disjunkte Zykel vertauschen kann, aber in der Tat ist $\begin{eqnarray*} (1,7,6)=(6,1,7)=(7,6,1) \neq (6,7,1) = (1,7,6)^{-1} \end{eqnarray*}$ .

08.07.2011, 15:06

Pascal95

Auf diesen Beitrag antworten »

Ok, danke,

aber sind zwei Zykel denn nicht immer disjunkt ?

Wenn zwei Zykel nicht disjunkt wären, also mindestens ein Element gemeinsam haben, würde das ja auf 2 andere Elemente abgebildet werden, und dann wäre die Zuordnung doch keine Funktion mehr?

Also z.B. $\begin{eqnarray*} (1,2,3)(1,4) \end{eqnarray*}$ würde ja bedeuten, dass die 1 auf 2 und auf 4 abgebildet wird?

08.07.2011, 15:25

jester.

Auf diesen Beitrag antworten »

Nein, $\begin{eqnarray*} (1,2,3)(1,4) \end{eqnarray*}$ meint die Hintereinanderausführung von Permutationen (die die sogenannte symmetrische Gruppe bilden). Je nach Konvention der Vorlesung/des Buches/... wird diese Hintereinanderausführung jedoch unterschiedlich verstanden.

Ich arbeite persönlich lieber mit der Konvention " $\begin{eqnarray*} (1,2,3)(1,4) \end{eqnarray*}$ entspricht $\begin{eqnarray*} (1,2,3) \end{eqnarray*}$ [u]nach[/l] $\begin{eqnarray*} (1,4) \end{eqnarray*}$ ", denn dies entspricht der Hintereinanderausführung von Abbildungen (und nichts anderes sind Permutationen).
Viele populäre Computeralgebrasysteme machen es jedoch andersherum.

08.07.2011, 15:38

Pascal95

Auf diesen Beitrag antworten »

Leider ist mir das nicht ganz klar.

Meinst du sowas hier?
wiki/Permutation#Beispiele_zur_Komposition_von_Permutationen

Dann wäre im Beispiel ja in der Zykelschreibweise:
$\begin{eqnarray*} (1,2,3)(1,4) \end{eqnarray*}$
das gleiche in der Matrixschreibweise:
$\begin{eqnarray*} (1,2,3)= \begin{pmatrix} 1 & 2 & 3 \\ 2&3&1 \end{pmatrix} \end{eqnarray*}$
$\begin{eqnarray*} (1,4)= \begin{pmatrix} 1 & 4 \\ 4&1 \end{pmatrix} \end{eqnarray*}$

Stimmt das soweit?

Dann wäre die Verkettung ja folgendermaßen:
$\begin{eqnarray*} (1,2,3)(1,4)=(1,2,3)\circ (1,4)=\begin{pmatrix} 1 & 2 & 3 \\ 2&3&1 \end{pmatrix}\circ \begin{pmatrix} 1 & 4 \\ 4&1 \end{pmatrix} \end{eqnarray*}$

Aber wie soll man das weiterführen?

Momentan bin ich leider verwirrt..

08.07.2011, 16:05

jester.

Auf diesen Beitrag antworten »

Wenn man mit Permutationen auf 4 Puntken arbeitet, sollte man in dieser Matrixdarstellung schon 4 Spalten haben, also $\begin{eqnarray*} (1,2,3)(1,4)=(1,2,3)\circ (1,4)=\begin{pmatrix} 1 & 2 & 3 & 4 \\ 2&3&1&4 \end{pmatrix}\circ \begin{pmatrix} 1&2&3 & 4 \\ 4&2&3&1 \end{pmatrix} \end{eqnarray*}$ .
Dies liest man dann wie die Hintereinanderausführung einer Abbildung, indem man spaltenweise die neue Matrix aufschreibt.
1. Spalte: auf was wird 1 abgebildet? Erst die rechte Abbildung, 1 auf 4. Dann die linke Abbildung, 4 auf 4. Also insgesamt 1 auf 4.
2. Spalte: rechts 2 auf 2, links 2 auf 3, also insgesamt 2 auf 3.
3. Spalte: 3 auf 3, 3 auf 1, also 3 auf 1
4. Spalte: 4 auf 1, 1 auf 2, also 4 auf 2.
Ergebnis $\begin{eqnarray*} \begin{pmatrix}1&2&3&4 \\ 4&3&1&2\end{pmatrix} \end{eqnarray*}$ .

Die gleiche Überlegung "1 geht auf, ... " führt natürlich auch auf die passende Zykelschreibweise, hier $\begin{eqnarray*} (1,4,2,3) \end{eqnarray*}$ .

08.07.2011, 16:57

Pascal95

Auf diesen Beitrag antworten »

Ok,

das ist mir nun klar.

Man geht also davon aus, dass die anderen, nicht aufgeführten Elemente identisch abgebildet werden.

Stimmt es auch, dass du hier nur eine andere Schreibweise benutzt und $\begin{eqnarray*} (1,2,3) \end{eqnarray*}$ dasselbe wie $\begin{eqnarray*} (123) \end{eqnarray*}$ ist?

Leider ist mir aber der Zusammenhang zwischen der Schreibweise aus dem Skript mit der der Verkettung von Permutationen noch nicht ganz klar.

Im Skript kommt ja folgendes vor:
$\begin{eqnarray*} \sigma = \begin{pmatrix} 1 & 2 & 3&4&5&6&7 \\ 7&5&2&4&3&1&6 \end{pmatrix} =(176)(253)(4) \end{eqnarray*}$
Hier gibt es ja 2 3-er Zykel und die 4 bleibt fest.

Wenn man aber $\begin{eqnarray*} (176)(253)(4) \end{eqnarray*}$ in die Matrixschreibweise umformen will, kann man ja nicht einfach $\begin{eqnarray*} (176)\circ(253)\circ(4) \end{eqnarray*}$ rechen, das wäre ja was anderes, oder ?

Das nehme ich mal als kleine Übung, voilà:
[attach]20488[/attach]

Da komm ich ja wieder auf das selbe geschockt

Allmählich versteh ich das besser...

Aber wenn man eine beliebige Permutation in Matrix-Schreibweise hat,
$\begin{eqnarray*} \sigma = \begin{pmatrix} 1 & 2 & \cdots & n \\ \sigma\left(1\right) & \sigma\left(2\right) & \cdots & \sigma\left(n\right) \end{pmatrix} \end{eqnarray*}$
und das in Zykle Schreibweise umformt
$\begin{eqnarray*} (..,..,..)(..,..)(..,..,..,..,..)(..)..... \end{eqnarray*}$ wird ja niemals sowas rauskommen $\begin{eqnarray*} (1,7)(1,2,3) \end{eqnarray*}$ , weil (1,7) ja ein Zykel ist, d.h. 1 & 7 werden getauscht, dann kann ja in der Matrix Schreibweise unter der 1 nur die 7 stehen, unter der 7 steht 1. Aber Dann müsste unter der 3 auch eine 1 stehen, unter der 1 müsste ebenfalls eine 2 stehen (nach dem anderen 3er Zykel) verwirrt

Vielen Dank für deine Hilfe

10.07.2011, 08:21

jester.

Auf diesen Beitrag antworten »

Zitat:

Original von Pascal95
Man geht also davon aus, dass die anderen, nicht aufgeführten Elemente identisch abgebildet werden.

Ja.

Zitat:

Stimmt es auch, dass du hier nur eine andere Schreibweise benutzt und $\begin{eqnarray*} (1,2,3) \end{eqnarray*}$ dasselbe wie $\begin{eqnarray*} (123) \end{eqnarray*}$ ist?

Ja.

Zitat:

Im Skript kommt ja folgendes vor:
$\begin{eqnarray*} \sigma = \begin{pmatrix} 1 & 2 & 3&4&5&6&7 \\ 7&5&2&4&3&1&6 \end{pmatrix} =(176)(253)(4) \end{eqnarray*}$
Hier gibt es ja 2 3-er Zykel und die 4 bleibt fest.

Wenn man aber $\begin{eqnarray*} (176)(253)(4) \end{eqnarray*}$ in die Matrixschreibweise umformen will, kann man ja nicht einfach $\begin{eqnarray*} (176)\circ(253)\circ(4) \end{eqnarray*}$ rechen, das wäre ja was anderes, oder ?

Nein, man kann das genau so ausrechnen. Da wir in einer Gruppe sind, ist $\begin{eqnarray*} (1,7,6)(2,5,3)(4) \end{eqnarray*}$ sowohl ein Gruppenelement, als auch eine Verknüpfung aus 3 Gruppenelementen.
Übrigens kann man $\begin{eqnarray*} (4) \end{eqnarray*}$ weglassen, es handelt sich ja um die Identität.

Zitat:

Aber wenn man eine beliebige Permutation in Matrix-Schreibweise hat,
$\begin{eqnarray*} \sigma = \begin{pmatrix} 1 & 2 & \cdots & n \\ \sigma\left(1\right) & \sigma\left(2\right) & \cdots & \sigma\left(n\right) \end{pmatrix} \end{eqnarray*}$
und das in Zykle Schreibweise umformt
$\begin{eqnarray*} (..,..,..)(..,..)(..,..,..,..,..)(..)..... \end{eqnarray*}$ wird ja niemals sowas rauskommen $\begin{eqnarray*} (1,7)(1,2,3) \end{eqnarray*}$ , weil (1,7) ja ein Zykel ist, d.h. 1 & 7 werden getauscht, dann kann ja in der Matrix Schreibweise unter der 1 nur die 7 stehen, unter der 7 steht 1. Aber Dann müsste unter der 3 auch eine 1 stehen, unter der 1 müsste ebenfalls eine 2 stehen (nach dem anderen 3er Zykel) verwirrt

Mit dem vorgeschlagenen Verfahren erstellt man direkt eine disjunkte Zykeldarstellung. Außerdem kann auch, wenn man eine nicht-disjunkte Zykeldarstellung in Matrixschreibweise übersetzt, niemals etwas mit mehr als zwei Einsen in der unteren Zeile o.Ä. vorkommen, denn auch nicht-disjunkte Darstellungen stehen für Bijektionen.

Vielleicht noch ein Beispiel? $\begin{eqnarray*} \sigma=\begin{pmatrix} 1&2&3&4&5&6&7 \\ 5&4&2&1&3&7&6\end{pmatrix} \end{eqnarray*}$
1 geht auf 5, also haben wir $\begin{eqnarray*} \sigma=(1,5 \end{eqnarray*}$ . Dann geht 5 auf 3, also $\begin{eqnarray*} \sigma=(1,5,3 \end{eqnarray*}$ .
3 geht auf 2, $\begin{eqnarray*} \sigma=(1,5,3,2 \end{eqnarray*}$ .
2 geht auf 4, $\begin{eqnarray*} \sigma=(1,5,3,2,4 \end{eqnarray*}$ .
4 geht auf 1, $\begin{eqnarray*} \sigma=(1,5,3,2,4) \end{eqnarray*}$ .
Dann bleiben noch 6 und 7. 6 geht auf 7, also $\begin{eqnarray*} \sigma=(1,5,3,2,4)(6,7 \end{eqnarray*}$ . Da 7 wieder auf 6 geht schließen wir auch diesen zweiten Zykel und haben die Permutation umgeschrieben.
$\begin{eqnarray*} \begin{pmatrix} 1&2&3&4&5&6&7 \\ 5&4&2&1&3&7&6\end{pmatrix}=(1,5,3,2,4)(6,7) \end{eqnarray*}$

Neue Frage »

Antworten »

Permutationen und symmetrische Gruppe - Skript, falsch oder falsch verstanden

Verwandte Themen