Proposition - Jede Permutation lässt sich als Produkt von Transpositionen schreiben

• Involvierte Definitionen:
  • Permutation
  • Transposition
  • Definition - Zyklus
• Veranstaltung: AlMa
• Referenz: } AlgoMathe KE1 - Abbildungen, Permutationen, Fakultät

⠀

Proposition: Jede Permutation lässt sich als Produkt von Transpositionen schreiben

Beweis

Sei eine Permutation, dann wissen wir dass sich in endlich viele disjunkte Zyklen zerlegen lässt.

Es ist daher zu zeigen, dass sich Zyklen sich in Transpositionen zerlegen lassen.

Induktionsanfang

Sei ein beliebiger Zyklus mit . Dann ist bereits eine Transposition.

Das heißt, der Induktionsanfang hält.

Induktionsannahme

Sei ein beliebiger Zyklus mit Elementen. Dann lässt sich in Transpositionen zerlegen.

Induktionsschritt

Sei ein beliebiger Zyklus mit Elementen. Dann ist

Dann gilt aber auch

Da gilt, dass , lässt es sich laut Induktionsannahme in Transpositionen als Produkt von Transpositionen zerlegen.

wir haben also gezeigt, dass sich als Produkt von Transpositionen schreiben lässt: