Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Permutation Prod. von Transpos. benachbarter El.

Permutation Prod. von Transpos. benachbarter El.

Universität / Fachhochschule

angewandte lineare Algebra

Lineare Abbildungen

Tags: Angewandte Lineare Algebra, Linear Abbildung, permutation, produkt, Transposition

anjula aktiv_icon

09:46 Uhr, 31.05.2018

Hallo!

Ich hätte eine folgende Aufgabe zu lösen:

"Zeige: Jede Permutation

σ \in S_{n}

ist als Produkt von Permutationen

π_{i, i + 1}

benachbarter Elemente darstellbar."

Das heißt nun das

σ = π_{1, 2} \cdot π_{2,3} \cdot .

\cdot π_{(m - 1), m}

.

Aber ich verstehe nicht ganz wie ich das zeigen soll. Denn ich finde im Buch keine genaue Definition von

σ

.
Das einzige was ich gefunden habe:

"Die Identität id_(

{

2, . ., n})

kann stets als leeres Produkt geschrieben werden. Sein nun

σ \neq

id_(

{

2, . ., n})

und daher

n \geq 2

. Dann gibt es genau ein kleinstes

i_{1} \in {1, 2, . ., n}

mit

σ (i_{1}) = j_{1} \neq i_{1}

. Sei

σ_{1} := π_{i_{1}, j_{1}} \circ σ

. Bei

σ_{1} =

id_(

{

2, . ., n})

sind wir fertig. Andernfalls gibt es genau ein kleinstes

i_{2}

mit

σ_{1} (i_{2}) = j_{2} \neq i_{2}

. Wir setzen

σ_{2} := π_{i_{2}, j_{2}} \circ σ_{1}

und so weiter. Das Verfahren muss bei einem

σ_{k}

mit

k \leq n

abbrechen. Dann gilt id_(

{

2, . ., n}) = π_{i_{k}, j_{k}} \circ .

\circ π_{i_{1}, j_{1}} \circ σ

bzw.

σ = π_{i_{1}, j_{1}} \circ .

\circ π_{i_{k},}

j_(k))."

Das ist der Beweis zum Satz: "Jede Permutation

σ \in S_{n}

ist als Produkt von höchstens

n

Transpositionen darstellbar."

Ich habe mir zur Veranschaulichung folgendes aufgeschrieben:

π_{1,2} \cdot π_{2,3} \cdot π_{3,4} = (\begin{matrix} 1 & 2 & 3 & 4 \\ 2 & 1 & 3 & 4 \end{matrix}) \cdot (\begin{matrix} 1 & 2 & 3 & 4 \\ 1 & 3 & 2 & 4 \end{matrix}) \cdot (\begin{matrix} 1 & 2 & 3 & 4 \\ 1 & 2 & 4 & 3 \end{matrix}) = (\begin{matrix} 1 & 2 & 3 & 4 \\ 2 & 3 & 4 & 1 \end{matrix})

Stimmt das oder liege ich komplett daneben?

Lg
Anjula

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich bräuchte bitte einen kompletten Lösungsweg." (setzt voraus, dass der Fragesteller alle seine Lösungsversuche zur Frage hinzufügt und sich aktiv an der Problemlösung beteiligt.)

Hierzu passend bei OnlineMathe:

Zu diesem Thema passende Musteraufgaben einblenden

michaL aktiv_icon

12:22 Uhr, 31.05.2018

Hallo,

das ist eine Frage der Strategie.
Und dies kann man auch an Beispielen gut erkennen.

Eine wäre, mit benachbarten Transpositionen so zu multiplizieren, dass die Produkte

σ_{i}

die Eigenschaft

σ_{i} (k) = k

für gewisse

i

und

k

gilt.

Etwas konkreter: Wir nehmen mal die Permutation

σ := (\begin{array}{ccccc} 1 & 2 & 3 & 4 & 5 \\ 3 & 5 & 4 & 1 & 2 \end{array})

her.

Für sie gilt NICHT:

σ (5) = 5

. (Stattdessen gilt

σ (5) = 2

.)

Nun "bubblen" wir 5 von

σ (2) = 5

"hoch" durch Multiplikation mit "Nachbartranspositionen", sodass

σ^{*} (4) = 5

gilt. Dann brauchen wir schließlich (im Sinne von Etappenziel) nur mit der Nachbartransposition

(4 5)

zu multiplizieren und erhalten ...

Also los:

(2 3) \circ (\begin{array}{ccccc} 1 & 2 & 3 & 4 & 5 \\ 3 & 5 & 4 & 1 & 2 \end{array}) = (\begin{array}{ccccc} 1 & 2 & 3 & 4 & 5 \\ 2 & 5 & 4 & 1 & 3 \end{array})

(Achtung: Mischung der Schreibweisen!)

Erkennst du, inwiefern dieses Produkt näher dran am Etappenziel ist?
Erkennst du, wie wir das von

σ

ausgehend erreicht haben?
MaW: Erkennst du den Algorithmus?

Er ginge hier so weiter:

(3 4) \circ (\begin{array}{ccccc} 1 & 2 & 3 & 4 & 5 \\ 2 & 5 & 4 & 1 & 3 \end{array}) = (\begin{array}{ccccc} 1 & 2 & 3 & 4 & 5 \\ 2 & 5 & 3 & 1 & 4 \end{array})

Dies entspricht

σ^{*}

, denn es gilt

σ * (5) = 4

.
Nun multiplizieren wir noch mit

(4 5)

, um das Etappenziel zu erreichen:

(4 5) \circ (\begin{array}{ccccc} 1 & 2 & 3 & 4 & 5 \\ 2 & 5 & 3 & 1 & 4 \end{array}) = (\begin{array}{ccccc} 1 & 2 & 3 & 4 & 5 \\ 2 & 4 & 3 & 1 & 5 \end{array}) = : σ_{5}

Etappenziel erreicht: Wenn wir es jetzt nicht falsch anstellen, gilt für alle weiteren Produkte:

σ_{k} (5) = 5

(Zur Formalisierung: Ich habe diese Numerierung gewählt, damit ich

σ_{k} (x) = x

für alle

x \geq k

sicherstellen kann. Dann wird

σ_{1}

die Identität sein, womit ich dann rückwärts

σ

als ausschließliches Produkt von Nachbartranspositionen dargestellt haben werden.)

Ist dir klar, mit welchen Nachbartranspositionen jetzt multipliziert werden muss?

Mfg Michael

anjula aktiv_icon

14:24 Uhr, 31.05.2018

Hallo!

Danke für deine Antwort. :-)

Ich habe mal das von dir angegebene Beispiel selbst probiert zu rechnen. Hat auch prima funktioniert. Ich habe noch weiter gerechnet um die Identität herauszubekommen:

(\begin{matrix} 1 & 2 & 3 & 4 & 5 \\ 2 & 4 & 3 & 1 & 5 \end{matrix}) \circ (12) = (\begin{matrix} 1 & 2 & 3 & 4 & 5 \\ 1 & 4 & 3 & 2 & 5 \end{matrix})

(\begin{matrix} 1 & 2 & 3 & 4 & 5 \\ 1 & 4 & 3 & 2 & 5 \end{matrix}) \circ (23) = (\begin{matrix} 1 & 2 & 3 & 4 & 5 \\ 1 & 4 & 2 & 3 & 5 \end{matrix})

(\begin{matrix} 1 & 2 & 3 & 4 & 5 \\ 1 & 4 & 2 & 3 & 5 \end{matrix}) \circ (34) = (\begin{matrix} 1 & 2 & 3 & 4 & 5 \\ 1 & 3 & 2 & 4 & 5 \end{matrix})

(\begin{matrix} 1 & 2 & 3 & 4 & 5 \\ 1 & 3 & 2 & 4 & 5 \end{matrix}) \circ (23) = (\begin{matrix} 1 & 2 & 3 & 4 & 5 \\ 1 & 2 & 3 & 4 & 5 \end{matrix})

Passt das so?

Bei meinem Beispiel das ich vorher versucht habe zu lösen gehe ich von der Identität aus und berechne eine beliebige Permutation

(\begin{matrix} 1 & 2 & 3 & 4 \\ 4 & 1 & 2 & 3 \end{matrix})

(\begin{matrix} 1 & 2 & 3 & 4 \\ 1 & 2 & 3 & 4 \end{matrix}) \circ (12) = (\begin{matrix} 1 & 2 & 3 & 4 \\ 2 & 1 & 3 & 4 \end{matrix}) \circ (23) = (\begin{matrix} 1 & 2 & 3 & 4 \\ 3 & 1 & 2 & 4 \end{matrix}) \circ (34) = (\begin{matrix} 1 & 2 & 3 & 4 \\ 4 & 1 & 2 & 3 \end{matrix})

Jetzt habe ich es zwar anhand von Beispielen verstanden. Aber wie kann man dass formal zeigen?

Sei

σ \in S_{n}

.

Für die Identität ist nichts zu tun denn

σ (i) = i

Für ein beliebiges

σ (i) \neq i .

σ

lässt sich darstellen als:

π_{1,2} \cdot π_{2, 3} \cdot .

\cdot π_{(m - 1), m}

(Aber dadurch berechne ich nur eine neue Permutation.)

Wenn ich

σ = π_{(m - 1), m} \cdot .

\cdot π_{2, 3} \cdot π_{1,2} \cdot π_{2, 3} \cdot .

\cdot π_{(m - 1), m}

rechne, dann kommt man wieder auf die Identität, oder?

Lg

michaL aktiv_icon

15:15 Uhr, 31.05.2018

Hallo,

zunächst habe ich die Schwierigkeit, deine Notation zu verstehen.
Ich habe "

\circ

" im Zusammenhang mit Permutationen (was ja bijektive Abbildungen sind) als Hintereinaderausführung verwendet und kennen gelernt.
Du scheinst das nicht zu tun, jedenfalls stimmt sonst deine Rechnung nicht.
Verwendest du "

\circ

" in diesem Kontext als Multiplikation?
Soll

σ \circ τ = τ (σ)

sein?

Dann jedenfalls stimmt dein Vorgehen mit meiner Idee überein.

> Jetzt habe ich es zwar anhand von Beispielen verstanden. Aber wie kann man dass formal zeigen?

Klar, Formalisierung ist der nächste Schritt.

Die erste Frage, die du dir in diesem Zusammenhang stellen musst, ist folgende:
Wie wähle ich abhängig von meinem gerade aktuellen

σ_{x}

(also am Start dem

σ

oder nach Erreichen des nächsten Etappenziels das

σ_{k}

) die erste Nachbarstransposition aus.

Konkret, wieso multipliziere ich ausgehend von

σ = (\begin{array}{cccc} 1 & 2 & 3 & 4 & 5 \\ 3 & 5 & 4 & 1 & 2 \end{array})

mit

(2 3)

?
Wieso - ausgehend von

σ_{5} = (\begin{array}{cccc} 1 & 2 & 3 & 4 & 5 \\ 2 & 4 & 3 & 1 & 5 \end{array})

mit

(1 2)

?

Mfg Michael

anjula aktiv_icon

15:40 Uhr, 31.05.2018

Hallo,

Mit dem

' \circ'

ist die Multiplikation gemeint.
Aber wieso wäre es falsch? Meinst du vielleicht, dass ich

(12) \circ (\begin{matrix} 1 & 2 & 3 & 4 \\ 1 & 2 & 3 & 4 \end{matrix})

statt

(\begin{matrix} 1 & 2 & 3 & 4 \\ 1 & 2 & 3 & 4 \end{matrix}) \circ (12)

schreiben soll?

Mit dieser Rechnung ist ja lediglich gemeint, dass in der 2. Zeile die 1 und die 2 vertauscht werden. Das habe ich aber auch nicht aus dem Buch, sondern von dir abgeschaut und gerade erst gelernt.

Sorry falls es falsch ist, aber in meinem Buch steh grad mal knapp 2 ½ Seiten lang etwas über Symmetrische Gruppen, das war's. Deshalb tue ich mir gerade ziemlich schwer mit den Aufgaben.

>

Konkret, wieso multipliziere ich ausgehend von

σ = (\begin{matrix} 1 & 2 & 3 & 4 & 5 \\ 3 & 5 & 4 & 2 & 1 \end{matrix})

mit

(23)

?

Weil ich als Ergebnis die Identität herausbekommen möchte, und wenn man zuerst mit

(23)

dann kommt man auf

(\begin{matrix} 1 & 2 & 3 & 4 & 5 \\ 2 & 5 & 4 & 3 & 1 \end{matrix})

Wenn ich mit

(12)

multiplizieren würde

: (\begin{matrix} 1 & 2 & 3 & 4 & 5 \\ 3 & 5 & 4 & 1 & 2 \end{matrix}) - \to

da komme ich meinem Ergebnis nicht großartig näher. Also müsste ich mehr Regenschirme machen damit ich auf das richtige Ergebnis komme, und wenn ich gleich mit

(23)

rechne, weniger.

>

Wieso - ausgehend von

σ_{5} = (\begin{matrix} 1 & 2 & 3 & 4 & 5 \\ 2 & 4 & 3 & 1 & 5 \end{matrix})

mit

(12)

?

Da ich dem Ergebnis etwas näher komme

- \to (\begin{matrix} 1 & 2 & 3 & 4 & 5 \\ 1 & 4 & 3 & 2 & 5 \end{matrix})

und nicht wie beim vorherigen, dass die Multiplikation keinen gravierenden unterschied macht.

Lg

michaL aktiv_icon

16:42 Uhr, 31.05.2018

Hallo,

> Aber wieso wäre es falsch? Meinst du vielleicht, dass ich (12)∘(12341234) statt (12341234)∘(12) schreiben
> soll?

Ok, wenn du es noch nicht in der Vorlesung hattest, dann lass dir gesagt sein, dass zu einer Gruppe immer eine binäre Verknüpfung gehört.
Im Falle der symmetrischen Gruppe kann man dafür entweder die Hintereinanderausführung "

\circ

" nehmen, wobei

f \circ g

wie folgt definiert ist:

(f \circ g) (x) = f (g (x))

.
Zwar steht das

f

"vorn, de facto wird es aber "erst" als zweites angewendet.
Mit Hintereinanderausführung "

\circ

" muss man demnach von rechts nach links lesen.

Als Link sei de.wikipedia.org/wiki/Permutation#Komposition genannt.

Oder du verwendest eine Multiplikation "

\cdot

", wobei man dann

σ \cdot τ

wieder elementweise definiert als

(σ \cdot τ) (x) = τ (σ (x))

.
Jedenfalls meine ich, das mal so in einem Buch gesehen zu haben. (Habe als Link etwa www3.mathematik.tu-darmstadt.de/evs/e/32.html?evsver=833&evsdir=862&evsfile=LA4.pdf )
Da diese Schreibweise aber hochgradig missverständlich ist, würde ich immer die Komposition "

\circ

" bevorzugen.

> Sorry falls es falsch ist

Kein Grund, sich dafür zu entschuldigen.
Es ist eher so, dass ich nicht sicher war, ob ich dich verstanden hatte.

Zu meinen Fragen:

> Weil ich als Ergebnis die Identität herausbekommen möchte

Das ist zu wenig genau? Wieso die 2? (Dass 3 als Nachbar dabei ist, ist dann wenigstens zu 50 % logisch.)

Da müsstest du noch einmal eine Antwort darauf finden.

Mfg Michael

anjula aktiv_icon

20:19 Uhr, 31.05.2018

Hallo,

Achso okee jetzt verstehe ich es. Dann verwenden wir lieber

' \circ'

um Missverständnisse zu vermeiden.

Oke :-)

Zu den Fragen:

Wir wollen am Ende eine 'geordnete' Permutation. Also schauen wir, wie wir am besten die kleinsten Zahlen an den vordersten Stellen haben, und die größeren hinten. Deswegen wird nicht mit

(12)

multipliziert, da dann 1 und 2 weiterhin an den hintersten Stellen verbleiben. Wenn man

(23)

multipliziert kommt man dem Ergebnis schon etwas näher.

Ist es so vielleicht besser? Irgendwie kann ich mir nicht anderes vorstellen.

: |

michaL aktiv_icon

20:42 Uhr, 31.05.2018

Hallo,

wenn du dir

σ

anschaust, dann siehst du, dass

σ (5) = 2

ist.
Deshalb multiplizieren wir der Reihe nach mit

(σ (5) σ (5) + 1)

(σ (5) + 1 σ (5) + 2)

und

(σ (5) + 2 5)

Du musst versuchen, bei beliebigem

σ \in S_{n}

zu zeigen, dass für

k := σ (n) \neq n

und

σ_{n} := (n - 1 n) \circ (n - 2 n - 1) \circ \dots \circ (k k + 1) \circ σ

gilt:

σ_{n} (n) = n

.

Dann beginnst du für

σ_{n}

mit dem

l := max {m \in {1; \dots; n} ∣ σ_{n} (m) \neq m}

"von vorn". Gemäß obigem muss nämlich

l < n

gelten.

Mit diesem Verfahren erzeugst du eine Reihe von Permutationen

σ, σ_{n_{1}}, \dots, σ_{n_{k}}

mit

σ_{n_{i}} (x) = x

für alle

x \geq n_{i}

(

i = 1, \dots, k

). Insbesondere muss

n_{k} = 1

gelten, womit

σ_{n_{k}} = σ_{1} = {id}_{S_{n}}

gilt und

σ_{n_{i}}^{- 1} \circ σ_{n_{i + 1}}

stets ein Produkt aus Nachbarstranspositionen ist.

Ich will nicht verhehlen, dass es auch andere Möglichkeiten für den Beweis gäbe.
Wenn ihr schon einen Satz hättet, der z. b. besagt, dass

S_{n}

aus allen Transpositionen

(x y)

erzeugt wird, dann könntest du versuchen, allgemein zu zeigen, wie man mit Nachbarstranspositionen jede Transposition

(x y)

erzeugt.

Der Beweis ist vom Grundsatz her "einfacher" im Sinne von leichter zu durchschauen. Allerdings ist er "fummelig".

Der andere (obige) ist kognitiv schwieriger, technisch aber wohl insgesamt einfacher. (Liegt aber im Auge des Betrachters!)

Mfg Michael

anjula aktiv_icon

21:04 Uhr, 01.06.2018

Hallo!

Wir haben in der Vorlesung den Satz "Jede Permutation

σ \in S_{n}

ist als Produkt von höchstens

n

Transpositionen darstellbar." gemacht.

Beweis dazu:

Die Identität kann stets als leeres Produkt geschrieben werden.
Sei nun

σ \neq

id und daher

n \geq 2

. Dann gibt es genau ein kleinstes

i_{1} \in {1, 2, . ., n}

mit

σ (i_{1}) = j_{1} \neq i_{1}

.
Sei

σ_{1} := π_{i_{1} j_{1}} \circ σ

. Bei

σ_{1} =

id sind wir fertig. Andernfalls gibt es genau ein kleinstes

i_{2}

mit

σ_{1} (i_{2}) = j_{2} \neq i_{2}

. Wir setzen

σ_{2} := π_{i_{2} j_{2}} \circ σ_{1}

und so weiter. Das Verfahren muss bei einem

k \leq n

abbrechen. Dann gilt id

= π_{i_{k} j_{k}} \circ .

\circ π_{i_{1} j_{1}} \circ σ

.

Aber ich würde gerne den Ansatz von dir verwenden, auch wenn er schwieriger ist. Ich glaube nämlich, dass es einen größeren Lerneffekt hat wenn ich den schwierigen Beweis mache, und dafür korrekt, als einen einfachen der schwammig ist. Denn letztendlich möchte ich die Aufgabe ja verstehen.

Zum Beweis:

Wähle bel.

σ \in S_{n}

so, dass für

k := σ (n) \neq n

und

σ_{n} := (n - 1 n) \circ (n - 2 n) \circ .

\circ (k k + 1) \circ σ

gilt:

σ_{n} (n) = n

l := max {m \in {1, .

, n} | σ_{n} (m) \neq m}

. Dadurch beginnen wir den obigen Prozess von vorne und es gilt

l < n

.

Dadurch wird eine Reihe von Permutationen

σ, σ_{n_{1}}, .

, σ_{n_{k}}

mit

σ_{n_{i}} (x) = x

für alle

x \geq n_{i}

mit

i \in {1, .

k}

erzeugt.
Für

n_{k} = 1

gilt

σ_{n_{k}} = σ_{1} =

σ_{n_{i}}^{- 1} \circ σ_{n + 1}

ist stets ein Produkt aus Nachbartranspositionen.

- -

Ich mit der Notation nicht ganz klar

σ (n) \neq n

ist klar.(zB beim vorigen Bsp

σ (5) = 2 \neq 5

σ_{n} := (n - 1 n) \circ (n - 2 n) \circ .

\circ (k k + 1) \circ σ \to

Das geht auch noch,

σ_{n}

wird durch Multiplikation verschiedener Permutationen benachbarter Elemente erzeugt.

σ_{n} (n) = n \to

Das heißt ein bestimmtes

σ_{n}

ergibt an der stelle (n)

= n

. Das heißt das will ich zeigen, denn ich will ja das am Ende die Identität herauskommt.

l := max {m \in {1, .

, n} | σ_{n} (m) \neq m} \to

ich nehme mir das größte

m

her, dass

σ_{n} (m) \neq m

ist. Dh ich nehme mir immer die größte Zahl her, die mit der Zahl über sich nicht übereinstimmt und beginne den Prozess von vorne, also dass

σ_{n} := (n - 1 n) \circ (n - 2 n) \circ .

\circ (k k + 1) \circ σ

gilt, damit wieder

σ_{n} (n) = n

gilt.
Warum gilt

l < n

? denn

m

lauft ja von

1, . ., n

also kann

m = n

sein und das größte

m = l

. Irgendwas verstehe ich da nicht.

Ich verstehe nicht wie man auf

σ_{n_{i}}^{- 1}

kommt. Was ist

σ_{n_{i}}^{- 1}

? ist es im Fall

σ (5) = 2 \to σ_{n_{i}}^{- 1} = 5

?

Lg

michaL aktiv_icon

21:17 Uhr, 02.06.2018

Hallo,

ich hatte gehofft, du habest erkannt, dass der von mir vorgestellte Beweis dem von dir angegebenem sehr ähnlich ist.
Was ist anders?
Ich spreche nicht von dem kleinsten

i_{1}

mit

σ_{1} (i_{1}) \neq i_{1}

, bei mir ist es das größte.
Dieses Detail kann man auf einfache Weise abändern!

Ich kann in meinem Beweis nicht mit einer beliebigen Transposition multiplizieren, ich kann nur Nachbarstranspositionen verwenden. Daher benötige ich auch mehr.

Versuche doch bitte die Analogien des Beweises zum von dir zitierten Satz und meines Beweises zur Aufgabe zu entdecken.

Und nun noch die "Vereinfachung": Offenbar arbeitet der Beweis, den du zitierst, mit einer beliebigen Transposition

(i_{1} j_{1})

. Es muss nicht

∣ i_{1} - j 1 ∣ = 1

gelten (wie bei einer Nachbarstransposition).

Du könntest also beinahe den von dir angegebenen Beweis für die Aufgabe verwenden, wenn es dir gelingt, jedwede Transposition

k \ l

als Produkt von Nachbarstranspositionen darzustellen.

Mache dir klar, dass dies im Prinzip der wesentliche Teil dafür ist, dass der von dir zitierte Beweis auch für die Aufgabe verwendet werden kann.

Ich hoffe, dies rückt so einiges gerade.
Wenn nicht, melde dich noch mal.

Mfg Michael

anjula aktiv_icon

14:31 Uhr, 10.06.2018

Hallo!

Sorry das ich mich erst jetzt melde. Mir ging's die letzten Tage leider nicht so gut.

Ich habe nun folgendes probiert:

Beweis:

Die Identität kann stets als leeres Produkt geschrieben werden. Sei nun

σ \neq

id und daher

n \geq 2

. Dann gibt es genau ein größtes

i_{1} \in {1, . ., n}

mit

σ_{1} (i_{1}) = j_{1} \neq i_{1},

wobei

j_{1} = i_{1} + 1

Sei

σ_{1} := π_{i_{1} j_{1}} \circ σ

. Bei

σ_{1} =

id sind wir fertig.

Andernfalls gibt es genau ein größtes

i_{2}

mit

σ_{1} (i_{2}) = j_{2} \neq i_{2},

wobei

j_{2} = i_{2} + 1

Wählen wir nun ein

σ \in s_{n}

so dass:

k := σ (n) \neq n

und

σ (n) = (n - 1, n) \circ .

\circ (k, k + 1) \circ σ

. Dann gilt

σ (n) = n

Wähle nun ein

l := max {m \in {1, . ., n} | σ_{n} (m) \neq m}

. Dieses

l

sucht das größte

m

bei dem gilt

σ_{n} (m) \neq m

und beginnt wieder von vorne, bis

σ_{n} (m) = m

gilt.

Dadurch wird eine Reihe von Permutationen

σ, σ_{n_{1}}, . ., σ_{n_{k}}

mit

σ_{n_{i}} (x) = x

für alle

x \geq n_{1} (i \in {1, . ., k}

.

Für

n_{k} = 1

gilt:

σ_{n_{k} = σ_{1} =}

id

Wir setzen

σ_{2} := π_{i_{2}, j_{2}} \circ σ_{1}

(wobei

j_{2} = i_{2} + 1)

und so weiter. Das Verfahren muss kein einem

σ_{k}

mit

k \leq n

abbrechen.
Dann gilt id

= π_{i_{k} j_{k}} \circ .

\circ π_{i_{1} j_{1}} \circ σ

bzw

σ = π_{j_{1} i_{1}} \circ .

\circ π_{j_{k} i_{k}}

(wobei

j = i + 1)

Passt das halbwegs?

Lg

Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.

1430186

1428964

	Status: nicht eingeloggt	Noch nicht registriert?