Transpositionen

Eine Transposition ist ein Zyklus der Länge 2, wie z.B. (24)(2 4). Die Transpositionen sind für die Permutationen das, was die Primzahlen für die natürlichen Zahlen sind, denn es gilt:

Satz 5325E

Jede Permutation lässt sich als Produkt von Transpositionen darstellen.

Beweis

Wenn die Permutation π\pi in Zyklenschreibweise gegeben ist, und z=(π1π2πn)z=(\pi_1\pi_2\ldots\pi_n) ein Zyklus der Länge nn, dann kann man sich einfach überzeugen, dass z=(π1πn)(π1πn1)(π1π2)z=(\pi_1\pi_n)(\pi_1\pi_{n-1})\ldots(\pi_1\pi_2) die gesuchte Zerlegung. \qed
Im Gegensatz zur Primzahlzerlegung ist die Zerlegung einer Permutation in ein Produkt von Transpositionen nicht eindeutig. Jedes solches Produkt kann durch Multiplikation mit einem Transpositionspaar der Form (πkπl)(πlπk)(\pi_k\pi_l)(\pi_l\pi_k) in ein weiteres Produkt überführt werden. Andererseits kann man sich überlegen, dass die Multiplikation einer Permutation mit einer einzelnen Transposition niemals die Permutation selbst ergeben kann.
 
 

In der Mathematik gibt es keine Autoritäten. Das einzige Argument für die Wahrheit ist der Beweis.

K. Urbanik

Copyright- und Lizenzinformationen: Diese Seite ist urheberrechtlich geschützt und darf ohne Genehmigung des Autors nicht weiterverwendet werden.
Anbieterkеnnzeichnung: Mathеpеdιa von Тhοmas Stеιnfеld  • Dοrfplatz 25  •  17237 Blankеnsее  • Tel.: 01734332309 (Vodafone/D2)  •  Email: cο@maτhepedιa.dе