jede bijektive Abbildung als Komposition endlich vieler, paarweise vertauschender Zykel

Question

Aufgabe:

Sei n ∈ N mit n > 0 und M := {1, . . . , n}. Für k ∈ N mit k > 0 nennen wir eine Abbildung
f : M → M ein k-Zykel (kurz: Zykel), falls es paarweise verschiedene, a₁, . . . , a_k ∈ M gibt mit
f(x) =   a_i+1  falls x = a_i und i < k,
           a₁    falls x = a_k
           x      sonst

Zeigen Sie, dass sich jede bijektive Abbildung f : M → M als Komposition endlich vieler, paarweise
vertauschender Zykel schreiben lässt, d.h. es existiert ein r ∈ N mit r > 0 und Zykel f₁, . . . , f_r mit
(i) f = f₁ ◦ . . . ◦ f_r und
(ii) f_i ◦ f_j = f_j ◦ f_i für alle i, j ∈ {1, . . . , r}.

Problem/Ansatz:

Hallo, ich hänge ein bisschen am Verständnis. Also der erste Teil definiert einfach nur Zykel. Ok, das verstehe ich alles (außer dass k nach Aufgabenstellung größer als n sein kann und das macht keinen Sinn, aber gut).

Jetzt zum Aufgabenteil: Mir ist nicht ganz geläufig, was "paarweise vertausender Zykel" bedeuten soll. Ich dachte zunächst damit wäre das Aufbrechen des Zykels in viele 2-Zykel gemeint, dann wäre r = k-1. Aber dann macht der Teil (ii) ja keinen Sinn, da diese 2-Zykel, wenn sie direkt hintereinander sind, im Allgemienen nicht kommutativ sind (1 2) (2 3) =/= (2 3) (1 2).

Das heißt wohl, dass mit paarweise vertauschender Zykel etwas anderes gemeint ist, allerdings weiß ich nicht genau, was. Wäre sehr dankbar über Tipps, Hinweise, wie man auf die Lösung kommen kann.

Comments

Kleiner Nachtrag: Habe nochmal drüber geschaut und was ich mir vielleicht vorstellen könnte, ist, dass damit die Anzahl disjunkter Zykel gemeint ist. Allerdings wüsste ich dann nicht, wie man das r bestimmen kann.

Answer 1

Hallo,

so wie ich die Aufgabe verstehe, ist nach der Zerlegung einer bijektiven Abbildung in disjunkt Zyklen gefragt.

Die Konstruktion ergibt sich aus der Definition der Zyklen:

Wähle ein \(a_1 \in M\) mit \(f(a_1) \neq a_1\) (Fixpunkte von f können bei der Konstruktion außer Acht gelassen werden oder als 1-Zykel notiert werden.). Definiere dann rekursiv: \(a_{i+1}:=f(a_i)\) und zwar solange bis für das erste i gilt: \(f(a_i)=a_1\), dieses i definiert dann das k, also die Länge des Zykels, diesen nenne wir \(f_1\).

1. Die Konstruktion ist ok; denn die Werte \(f(a_i)\) sind alle verschieden, weil f bijektiv ist, und sie liegen alle in der endlichen Menge M, also muss für ein i gelten: \(f(a_i)=a_1\), d.h. das Zykel ist endlich.

2. Es gilt \(f(x)=f_1(x)\) für \(x=a_1, \ldots a_k\)

Dann wiederholen wir die Konstruktion, sofern es noch ein NEUES \(a_1 \in M\) mit \(f(a_1) \neq a_1\) gibt. Wenn nicht sind wir fertig.

Auf diese Weise konstruiert man die Zykel \(f_1, ..., f_r\).....

Gruß Mathhilf

Comments

Danke dir. Das war ja schon meine Vermutung im Nachtrag und mit der Kommutativität bleibt ja eigentlich nichts anderes übrig.

Hätte noch eine Frage, aber weiß natürlich nicht, ob du mir da helfen kannst.

Ich soll aus dem kartesischen Produkt Ι M x N Ι =  Ι M Ι *  Ι N Ι mit M, N endliche Mengen folgern, dass Ι S(M) Ι =  Ι S(M ohne {a}) Ι *  Ι M Ι ist, wie M eine endliche Menge und S(M) bezeichne die symmetrische Gruppe.

Da hatte ich die Idee, dass S(M ohne {a}) ja alle Permutationen bei einem Element weniger sind. Und all diese Permutationen α ∈ S(M ohne {a}) verknüpft mit der Menge N = {(a₁ a₂ ... a_n)^k Ι k ∈ ℕ} mit β ∈ N wobei n = Ι M Ι = Ι N Ι ist. Dann wäre α ° β ja sowas ähnliches wie das kartesische Produkt nur diesmal nicht als Paar dargestellt sondern als eine Permutation verknüpft. Aber weiß nicht, ob das Sinn macht.

---

Hallo,

es ist besser, Du stellst diese neue Aufgabe auch als neue Aufgabe ein, dann bekommst Du mehr Resonanz.

Gruß Mathhilf