[DAS] Produkt von Transpositionen?

Neue Frage »

Remington Steele Auf diesen Beitrag antworten »
[DAS] Produkt von Transpositionen?
Sorry ich weiß nicht, ob ich jetzt da im richtigen Forum bin... das Problem ist jedenfalls aus DAS (Diskrete Algebraische Strukturen).

Wenn ich ein Produkt von (1 3) ° (3 2) bilden muß, wie mache ich das? verwirrt

Komme einfach nicht darauf...

... daß alles immer so kompliziert sein muß X( Augenzwinkern

Danke...
Leopold Auf diesen Beitrag antworten »

Dann machen wir es gleich noch etwas komplizierter.
Hier handelt es sich um die Zykelschreibweise (Zyklus=Kreis). Nehmen wir ein Beispiel: Wenn man p = ( 3 6 4 5 1 ) schreibt, so muß man sich diese Zahlen im Kreis vorstellen: die 3, dann die 6, dann die 4, dann die 5, dann die 1, dann die 3, dann die 6, dann ...
Die Schreibweise ist also eigentlich schlecht, aber Kreise malen wäre halt ein bißchen umständlich. In einem Kreis ist es natürlich egal, wo man anfängt, d.h. es gilt
( 3 6 4 5 1 ) = ( 6 4 5 1 3 ) = ( 4 5 1 3 6 ) = ...
Allerdings kommt es uns hier auf die Richtung an, d.h. ( 1 5 4 6 3 ) ist nicht dasselbe wie die obigen Permutationen.

Und was bedeutet p = ( 3 6 4 5 1 ) nun?
Dies ist eine Abbildung, die jede vorkommende Zahl auf die nächste im Kreis abbildet. Man könnte p also auch so schreiben:
3 -> 6
6 -> 4
4 -> 5
5 -> 1
1 -> 3
Und was ist mit der 2? Die kommt im Zykel nicht vor, wird also auf sich selber abgebildet. Ebenso alle anderen nicht erwähnten Zahlen, sofern sie relevant sind.
2 -> 2

Und der Kringel ° bedeutet nun hier die Verkettung der Abbildungen. Jetzt kommt es darauf an, wie das in deiner Vorlesung oder in deinem Buch festgelegt wurde. Da sind sich die Mathematiker nämlich nicht einig. Meistens liest man Verkettungen von rechts (das kommt aus der Analysis wegen der f(x)-Schreibweise). Algebraiker lesen in diesem Zusammenhang Verkettungen aber auch gerne von links.
Ich nehme hier die Leserichtung von rechts.
Nehmen wir also einen zweiten Zykel q = ( 4 2 3 1 ) :
4 -> 2
2 -> 3
3 -> 1
1 -> 4

Zu bestimmen ist nun p°q = ( 3 6 4 5 1 ) ° ( 4 2 3 1 ) .
Wir beginnen also mit q ("von rechts": erst q, dann p).
1 -> 4 -> 5 (q bildet die 1 auf die 4 ab, p bildet die 4 auf die 5 ab)
2 -> 3 -> 6 (usw.)
3 -> 1 -> 3
4 -> 2 -> 2
5 -> 5 -> 1
6 -> 6 -> 4

Und jetzt läßt du die mittlere Spalte weg und bekommst p°q
1 -> 5
2 -> 6
3 -> 3
4 -> 2
5 -> 1
6 -> 4
Die 1 wird also auf die 5 abgebildet, dann schauen wir nach, was mit der 5 passiert. Die wird wieder auf die 1 abgebildet.
Das gibt den ersten Zykel: ( 1 5 )
Dann nehmen wir die 2. Sie wird auf die 6 abgebildet, die 6 wird auf die 4 abgebildet und die 4 wieder auf die 2.
Das gibt den zweiten Zykel: ( 2 6 4 )
Und die 3 wird auf sich selber abgebildet, braucht also nicht erwähnt zu werden.

Damit gilt p°q = ( 1 5 ) ° ( 2 6 4) = ( 2 6 4 ) ° ( 1 5 )
Normalerweise kommt es auf die Reihenfolge an, es gilt kein Kommutativgesetz bei °. Hier ist es aber egal, da die Zykel elementfremd sind (die beiden Kreise haben keine gemeinsamen Zahlen).
 
 
kurellajunior Auf diesen Beitrag antworten »

Total coole Sache, sogar nach Deiner Erklärung verstanden, aber Wozu das ganze? Hast Du mal eine praktische Anwendung dafür? Ein Rätsel oder so verwirrt
Remington Steele Auf diesen Beitrag antworten »

Cool - vielen Dank!

Praktische Anwendung: Studies an der Uni den letzten Nerv rauben :P smile :]
Remington Steele Auf diesen Beitrag antworten »

Hm, hätte da doch noch 'mal ne Frage dazu. Konkretes Bsp.:

"Schreiben Sie die Permutation

(1 2 3 4 5 6)
(2 3 1 4 6 5)

(das soll insgesamt eine große Klammer darstellen oben)

als Produkt von elementfremden Zyklen (ergibt (1 2 3) (4) (5 6), das ist klar)

und auch als Produkt von Transpositionen.
Lösungsweg ist
= (1 3) (1 3) (1 2 3) (4) (5 6) = (1 3) (1 2) (3) (4) (5 6)

Aber wie zum T... kommt man darauf? Und eine Transposition ist doch immer ein Zyklus der Länge 2, oder? Was hat es eigentlich sonst mit "Transposition" auf sich? Thx...
Remington Steele Auf diesen Beitrag antworten »

Ach und noch eine Frage: Warum fängst Du bei Deinem Bsp. in q ganz hinten an (4 auf die 1) - könnte man in q nicht auch vorne anfangen??

Zudem habe ich nochmal ein Bsp., das ich nicht kapiere:

(1) (2 3) ° (1 2) (3) = (1 3 2)

und

(1 2) (3) ° (1) (2 3) = (1 2 3)

Konnte es trotz Deiner Erklärung nicht nachvollziehen unglücklich .
Leopold Auf diesen Beitrag antworten »

Stimmt. Eine Transposition ist ein Zykel der Länge 2.
Jeden Zykel kannst du in Transpositionen zerlegen:
( a b c d e ... x y z ) = ( a b ) ° ( b c ) ° ( c d ) ° ( d e ) ° ... ° ( x y) ° ( y z).
Um das zu sehen, nehmen wir z.B. c. Wir arbeiten die Kringel von rechts ab. Da kommt zunächst c gar nicht vor. Erst bei ( c d ) taucht c zum ersten Mal auf: c -> d. Jetzt gehen wir weiter nach links und schauen, ob sich d noch verändert. d kommt links von ( c d ) aber gar nicht mehr vor. Insgesamt gilt also: c -> d, genau wie es der gegebene Zykel vorsieht. Und so kannst du das mit allen machen bis auf z. Und mit z geht es so: ( y z ) ganz rechts sagt: z wird auf y abgebildet, ( x y ) davor sagt, daß jetzt y auf x abzubilden ist. Und so geht das weiter:
z -> y -> x -> ... -> e -> d -> c -> b -> a. Insgesamt gilt also: z -> a. Und eben dies sagt auch der Zykel.

Und nun zu deinem letzten Beispiel. Zykel der Länge 1 kannst du schlichtweg ignorieren (im Beispiel sind das ( 1 ) und ( 3 ) ):

(1) ° ( 2 3 ) ° ( 1 2 ) ° ( 3 ) = ( 2 3 ) ° ( 1 2 )

Wir fangen mit der 1 an: 1 -> 2 (Transposition rechts). Und für die 2 gilt dann gemäß der Transposition davor: 2 -> 3. Insgesamt: 1 -> 2 -> 3, also (Zwischenschritte weglassen) 1 -> 3 (I)
Und was passiert mit der 2? Rechts: 2 -> 1 (II). Und wird sind schon fertig, da die 1 in der linken Transposition nicht mehr vorkommt.
Und zum Schluß noch die 3. Die kommt in der rechten Transposition nicht vor. Und die linke sagt: 3 -> 2 (II).
Damit ist das Ergebnis:
(I) 1 -> 3
(II) 2 -> 1
(III) 3 -> 2
Das ist aber nichts anderes als der Zykel ( 1 3 2 ) .
Remington Steele Auf diesen Beitrag antworten »

Danke Leopold... hm, ich bin ehrlich gesagt immer noch nicht ganz dahintergestiegen... könntest Du mir vielleicht noch das erwähnte Problem erklären - das wäre nett:
Zitat:
Original von Remington Steele
Hm, hätte da doch noch 'mal ne Frage dazu. Konkretes Bsp.:

"Schreiben Sie die Permutation

(1 2 3 4 5 6)
(2 3 1 4 6 5)

(das soll insgesamt eine große Klammer darstellen oben)

als Produkt von elementfremden Zyklen (ergibt (1 2 3) (4) (5 6), das ist klar)

und auch als Produkt von Transpositionen.
Lösungsweg ist
= (1 3) (1 3) (1 2 3) (4) (5 6) = (1 3) (1 2) (3) (4) (5 6)

Aber wie zum T... kommt man darauf? Und eine Transposition ist doch immer ein Zyklus der Länge 2, oder? Was hat es eigentlich sonst mit "Transposition" auf sich? Thx...


Vielen Dank...

MfG
Stefan
Leopold Auf diesen Beitrag antworten »

Genau das, was du fragst, habe ich im Eingang meines vorigen Beitrags erklärt. Arbeite diesen erst einmal genau durch.
Remington Steele Auf diesen Beitrag antworten »

Habe ich, kapiere dennoch nicht, wie man auf

(1 3) (1 3) (1 2 3) (4) (5 6) = (1 3) (1 2) (3) (4) (5 6)

kommt, besonders wo Du doch auch sagtest, die Zykel mit einem Element kann man weglassen... und wie die 3 dann auf einmal einzeln "herumsteht" ist mir auch schleierhaft... unglücklich . Sorry vielleicht bin ich schwer von Begriff, aber ich bin Deinen Beitrag mehrmals durchgegangen...
Leopold Auf diesen Beitrag antworten »

Wie man auf (123)°(4)°(56) kommt, hast du gesagt, ist klar.
Zunächst ist (4) hier vollkommen überflüssig (siehe meinen alten Beitrag; denn Zykeln der Länge 1 sind gleich der identischen Permutation).

Damit vereinfacht sich die Gleichung: (123)°(4)°(56) = (123)°(56).

Und (123) = (12)°(23) (siehe meinen alten Beitrag ganz am Anfang; dort ausführlich erklärt).

Damit geht es weiter: (123)°(4)°(56) = (123)°(56) = (12)°(23)°(56)

Fertig!

Und wenn es dich stört, daß deine Musterlösung etwas anders lautet, so überlege selbst, warum (12)°(23) = (13)°(12) ist.
Die Darstellung einer Permutation als Produkt von Transpositionen ist halt nicht eindeutig.
Remington Steele Auf diesen Beitrag antworten »

ok - danke... werde mir das dann noch mehrmals durchlesen... einiges ist klar, einiges noch nicht.

Aber vielen Dank für Deine Mühe...
frodo Auf diesen Beitrag antworten »
[DAS] Produkt von Transpositionen?
ich lese mit! Beifall! Tanzen
rounty Auf diesen Beitrag antworten »

Danke!

Nachdem ich eigentlich immer sicher war, dieses in-Transpositionen-umschreiben verstanden zu haben war ich kurz vor dem Verzweifeln, als es jetzt, 2 Tage vor der Klausur, nicht mehr geklappt hat.

Aber der Weg, der hier steht ist ja noch einfacher (oder besser erklärt?) als der aus Skript und Übung.

Dickes Lob!
schneiderisabel Auf diesen Beitrag antworten »
ich habe eine dringende frage
Hallo

ich habe mit Begeisterung die Erklärung zur Permutation gelesen.
Wirklich sehr gut und voll gut zu verstehen.

Aber ich habe da noch eine Frage zu einem beispiel.

ich soll (13) mit (1234567) verketten.
(3146725)
(soll eine große Klammer sein)

Das Ergebnis soll dann (1234567) sein.Wie kommt man darauf?
(1346725)
Wie macht man das? Danach soll man dann das Ergebnis (wieder in Zweizeilenform) mit (23) verketten...

Ich komme einfach trotz deiner super Erklärungen nicht darauf.

schon mal danke für die Hilfe
Hannoversch Auf diesen Beitrag antworten »

Hallo,

der Thread hat mir schon enorm geholfen.
Was passiert nun aber, wenn ich 3 Permuationen verkette?

So z.B. (1,2,3)(2,3,4)(3,4,5,6)

Ich habe zuerst die rechten beiden verkettet.
Für die hätte ich (23)(4,5,6).
Was passiert jetzt mit (1,2,3)?
Hannoversch Auf diesen Beitrag antworten »

Zitat:
Original von Hannoversch
Hallo,

der Thread hat mir schon enorm geholfen.
Was passiert nun aber, wenn ich 3 Permuationen verkette?

So z.B. (1,2,3)(2,3,4)(3,4,5,6)

Ich habe zuerst die rechten beiden verkettet.
Für die hätte ich (23)(4,5,6).
Was passiert jetzt mit (1,2,3)?


Oder muss man das einfach um eine Spalte erweitern:
Also:

1 -> 1 -> 1 -> 2
2 -> 2 -> 3 -> 1
3 -> 4 -> 2 -> 3
4 -> 5 -> 5 -> 5
5 -> 6 -> 6 -> 6
6 -> 3 -> 4 -> 4

Woraus dann folgt:
(12)(3)(456)
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »