- Permutationsgruppen
Zu einer Menge
nennt man die Menge
-
![{\displaystyle {}\operatorname {Aut} \,(M)=\operatorname {Perm} \,(M)={\left\{\varphi :M\longrightarrow M\mid \varphi {\text{ bijektiv}}\right\}}\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d1ada7686b5cef890167b98db00ff60d8bb191bc)
der bijektiven Selbstabbildungen die Automorphismengruppe oder die Permutationsgruppe zu
.
Eine bijektive Selbstabbildung
nennt man auch eine Permutation. Für eine endliche Menge
schreibt man
. Eine endliche Permutation kann man beispielsweise mit einer
(vollständigen)
Wertetabelle oder mit einem Pfeildiagramm beschreiben.
![{\displaystyle \Box }](https://wikimedia.org/api/rest_v1/media/math/render/svg/029b77f09ebeaf7528fc831fe57848be51f2240b)
![{\displaystyle \Box }](https://wikimedia.org/api/rest_v1/media/math/render/svg/029b77f09ebeaf7528fc831fe57848be51f2240b)
- Zykeldarstellung für Permutationen
Sei
eine endliche Menge,
eine Permutation und
.
Dann kann man die Folge
-
betrachten. Da
endlich ist, gibt es eine Wiederholung
mit
. Durch Multiplikation mit
sieht man, dass es ein minimales
gibt mit
, und dass alle
für
,
, verschieden sind. Ist
, so durchläuft auch
dieselbe Teilmenge aus
.
Es sei
eine endliche Menge und
eine
Permutation
auf
. Man nennt
einen Zykel der Ordnung
, wenn es eine
-elementige Teilmenge
derart gibt, dass
auf
die Identität ist und
die Elemente aus
zyklisch vertauscht. Wenn
ist, so schreibt man einfach
-
![{\displaystyle {}\pi =\langle z,\pi (z),\,\pi ^{2}(z),\ldots ,\pi ^{r-1}(z)\rangle \,.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a0b892f3fbd91fd40eef44ecfc21568c2597af08)
Dabei kann man statt
jedes andere Element aus
als Anfangsglied nehmen. Die Menge
heißt auch der Wirkungsbereich des Zykels, und die (geordnete) Auflistung heißt die Wirkungsfolge des Zykels.
Eine Transposition auf einer endlichen Menge
ist eine
Permutation
auf
, die genau zwei Elemente miteinander vertauscht und alle anderen Elemente unverändert lässt.
Eine Transposition ist also ein besonders einfacher Zykel mit der Zyklendarstellung
, wenn die Transposition die Punkte
und
vertauscht.
![{\displaystyle \Box }](https://wikimedia.org/api/rest_v1/media/math/render/svg/029b77f09ebeaf7528fc831fe57848be51f2240b)
Es sei
eine endliche Menge und
eine Permutation auf
.
Dann gibt es eine Darstellung
-
![{\displaystyle {}\sigma =\sigma _{1}\cdots \sigma _{k}\,,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/484841ef9bbf7af2610706499b40fb59d099d1a3)
wobei die
Zykel
der Ordnung
sind mit disjunkten Wirkungsbereichen.
Dabei ist die Darstellung bis auf die Reihenfolge eindeutig.
Es sei
die Fixpunktmenge von
und es seien
diejenigen Teilmengen von
mit mindestens zwei Elementen derart, dass
die Elemente aus jedem
zyklisch vertauscht. Dann ist
die disjunkte Vereinigung aus
und den
. Zu
,
, sei
der
Zykel
auf
, der auf
die Identität ist und auf
mit
übereinstimmt. Wir behaupten
-
![{\displaystyle {}\sigma =\sigma _{1}\cdots \sigma _{k}\,.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/63131d1f53030a63e64b3078ac974cb2cd72ca8e)
Um dies einzusehen, sei
beliebig. Bei
ist
ein Fixpunkt für alle
und daher kommt links und rechts wieder
raus. Es sei also
kein Fixpunkt der Permutation. Dann gehört
für genau ein
. Für alle
ist
ein Fixpunkt von
. Da
-
![{\displaystyle {}y=\sigma (x)\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/07381e896178710bef69fa0a6d1d394f803409cd)
ebenfalls zu
gehört, ist auch
ein Fixpunkt von
für alle
.
Wendet man daher die rechte Seite auf
an, so wird
auf
abgebildet bis man zu
kommt. Dieses bildet
auf
ab und die folgenden
bilden
auf
ab, sodass die rechte Seite insgesamt
auf
schickt und daher mit
übereinstimmt.
![{\displaystyle \Box }](https://wikimedia.org/api/rest_v1/media/math/render/svg/029b77f09ebeaf7528fc831fe57848be51f2240b)
Aufgrund von diesem Satz können wir allgemein eine Zyklendarstellung für eine beliebige Permutation definieren.
Es sei
eine endliche Menge und
eine
Permutation
auf
. Es seien
die Wirkungsbereiche der
Zyklen
von
mit
.
Es sei
und
.
Dann nennt man
-
die Zyklendarstellung von
.
- Das Signum einer Permutation
Das Signum ist
oder
,
da im Zähler und im Nenner die positive oder die negative Differenz
steht. Es gibt für das Signum also nur zwei mögliche Werte. Bei
spricht man von einer geraden Permutation und bei
von einer ungeraden Permutation.
Wir schreiben
![{\displaystyle {}{\begin{aligned}\operatorname {sgn} (\pi )&=\prod _{i<j}{\frac {\pi (j)-\pi (i)}{j-i}}\\&=\prod _{(i,j)\in F}{\frac {\pi (j)-\pi (i)}{j-i}}\prod _{(i,j)\not \in F}{\frac {\pi (j)-\pi (i)}{j-i}}\\&=(-1)^{k}\prod _{(i,j)\in F}{\frac {\pi (i)-\pi (j)}{j-i}}\prod _{(i,j)\not \in F}{\frac {\pi (j)-\pi (i)}{j-i}}\\&=(-1)^{k},\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b15abb771c34adff60383caf1a7dd08624eecf49)
da nach dieser Umordnung sowohl im Zähler als auch im Nenner das Produkt aller positiven Differenzen steht.
![{\displaystyle \Box }](https://wikimedia.org/api/rest_v1/media/math/render/svg/029b77f09ebeaf7528fc831fe57848be51f2240b)
Die durch das
Signum
gegebene Zuordnung
-
ist ein
Gruppenhomomorphismus.
Es seien zwei Permutationen
und
gegeben. Dann ist
![{\displaystyle {}{\begin{aligned}\operatorname {sgn} (\pi \circ \rho )&=\prod _{i<j}{\frac {(\pi \circ \rho )(j)-(\pi \circ \rho )(i)}{j-i}}\\&={\left(\prod _{i<j}{\frac {(\pi \circ \rho )(j)-(\pi \circ \rho )(i)}{\rho (j)-\rho (i)}}\right)}\prod _{i<j}{\frac {\rho (j)-\rho (i)}{j-i}}\\&={\left(\prod _{i<j,\,\rho (i)<\rho (j)}{\frac {\pi (\rho (j))-\pi (\rho (i))}{\rho (j)-\rho (i)}}\right)}{\left(\prod _{i<j,\,\rho (i)>\rho (j)}{\frac {\pi (\rho (j))-\pi (\rho (i))}{\rho (j)-\rho (i)}}\right)}\,\operatorname {sgn} (\rho )\\&={\left(\prod _{i<j,\,\rho (i)<\rho (j)}{\frac {\pi (\rho (j))-\pi (\rho (i))}{\rho (j)-\rho (i)}}\right)}{\left(\prod _{i<j,\,\rho (i)>\rho (j)}{\frac {\pi (\rho (i))-\pi (\rho (j))}{\rho (i)-\rho (j)}}\right)}\,\operatorname {sgn} (\rho )\\&=\prod _{k<\ell }{\frac {\pi (\ell )-\pi (k)}{\ell -k}}\operatorname {sgn} (\rho )\\&=\operatorname {sgn} (\pi )\operatorname {sgn} (\rho ).\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a5e30872e3d862c15a6618e04d323bbfc02e4ac5)
![{\displaystyle \Box }](https://wikimedia.org/api/rest_v1/media/math/render/svg/029b77f09ebeaf7528fc831fe57848be51f2240b)
Die Transposition
vertausche die beiden Zahlen
.
Dann ist
![{\displaystyle {}{\begin{aligned}\operatorname {sgn} (\tau )&=\prod _{i<j}{\frac {\tau (j)-\tau (i)}{j-i}}\\&=\prod _{i<j,\,i,j\neq k,\ell }{\frac {\tau (j)-\tau (i)}{j-i}}\cdot \prod _{i<j,\,i=k,j\neq \ell }{\frac {\tau (j)-\tau (i)}{j-i}}\cdot \prod _{i<j,\,i\neq k,j=\ell }{\frac {\tau (j)-\tau (i)}{j-i}}\cdot \prod _{i<j,\,i=k,j=\ell }{\frac {\tau (j)-\tau (i)}{j-i}}\\&=\prod _{j>k,\,j\neq \ell }{\frac {j-\ell }{j-k}}\cdot \prod _{i\neq k,\,i<\ell }{\frac {k-i}{\ell -i}}\cdot {\frac {k-\ell }{\ell -k}}\\&=\prod _{j>\ell }{\frac {j-\ell }{j-k}}\cdot \prod _{i<k}{\frac {k-i}{\ell -i}}\cdot \prod _{k<j<\ell }{\frac {j-\ell }{j-k}}\cdot \prod _{k<i<\ell }{\frac {k-i}{\ell -i}}\cdot (-1)\\&=-1.\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b260155cb2e63ad58af7e92497dd226157a09108)
Die letzte Gleichung ergibt sich daraus, dass im ersten und im zweiten Produkt alle Zähler und Nenner positiv sind und dass im dritten und im vierten Produkt die Zähler negativ und die Nenner positiv sind, sodass sich diese
(wegen der gleichen Indexmenge)
Minuszeichen wegkürzen.
Die Aussage folgt dann aus
der Homomorphieeigenschaft.
![{\displaystyle \Box }](https://wikimedia.org/api/rest_v1/media/math/render/svg/029b77f09ebeaf7528fc831fe57848be51f2240b)
Pdf-Version