diff options
Diffstat (limited to '')
-rw-r--r-- | buch/chapters/50-permutationen/transpositionen.tex | 219 |
1 files changed, 219 insertions, 0 deletions
diff --git a/buch/chapters/50-permutationen/transpositionen.tex b/buch/chapters/50-permutationen/transpositionen.tex index f27b20a..426ece4 100644 --- a/buch/chapters/50-permutationen/transpositionen.tex +++ b/buch/chapters/50-permutationen/transpositionen.tex @@ -6,3 +6,222 @@ \section{Permutationen und Transpositionen \label{buch:section:permutationen-und-transpositionen}} \rhead{Transpositionen} +Im vorangegangenen Abschnitt haben wir Permutationen durch die +Zyklenzerlegung charakterisiert. +Es zeigt sich aber, dass sich eine Permutation in noch elementarere +Bausteine zerlegen lässt, die Transpositionen. + +\begin{definition} +Einen Transposition $\tau\in S_n$ ist ein Permutation, die genau +zwei Elemente vertauscht. +Die Transposition $\tau_{ij}$ ist definiert durch +\[ +\tau_{ij}(x) += +\begin{cases} +i&\qquad x=j\\ +j&\qquad x=i\\ +x&\qquad\text{sonst.} +\end{cases} +\] +\end{definition} + +Eine Transposition hat genau einen Zyklus der Länge $2$, alle anderen +Zyklen haben die Länge $1$. + +\subsection{Zyklus und Permutationen aus Transpositionen} +Sei $\sigma$ die zyklische Vertauschung der Elemente $1,\dots,k\in [n]$, +also die Permutation, die $1\to2\to3\to\dots\to k-2\to k-1\to k\to 1$ +abbildet. +Dieser Zyklus lässt sich wie folgt aus Transpositionen zusammensetzen: +\begin{center} +\def\kreuz#1#2#3{ + \draw[->] ({(#1)-1},#2) to[out=-90,in=90] ({#1},{#2-1}); + \draw[->] ({#1},#2) to[out=-90,in=90] ({#1-1},{#2-1}); + \node at ({(#1)-0.5+0.2},{#2-0.5}) [right] {$#3$}; +} +\begin{tikzpicture}[>=latex,thick] +\foreach \x in {1,2,3,6,7,8,9}{ + \fill ({\x-1},0) circle[radius=0.05]; +} +\foreach \x in {1,2,3}{ + \node at ({\x-1},0) [above] {$\tiny \x$}; +} +\node at (8,0) [above] {$\tiny k$}; +\node at (7,0) [above] {$\tiny k-1$}; +\node at (6,0) [above] {$\tiny k-2$}; +\node at (5,0) [above] {$\tiny k-3$}; +\foreach \x in {1,2,3,4,7,8,9}{ + \fill ({\x-1},-8) circle[radius=0.05]; +} +\foreach \x in {1,2,3,4}{ + \node at ({\x-1},-8) [below] {$\tiny \x$}; +} +\node at (6,-8) [below] {$k-2$}; +\node at (7,-8) [below] {$k-1$}; +\node at (8,-8) [below] {$k$}; + +\foreach \x in {3,3.2,...,5}{ + \fill (\x,{-8+\x}) circle[radius=0.02]; + \fill ({\x+0.5},-8) circle[radius=0.02]; + \fill ({\x-0.5},0) circle[radius=0.02]; +} + +\kreuz{8}{0}{\tau_{k-1,k}} +\kreuz{7}{-1}{\tau_{k-2,k-1}} +\kreuz{6}{-2}{\tau_{k-3,k-2}} +%\kreuz{5}{-3}{\tau_{56}} +%\kreuz{4}{-4}{\tau_{45}} +\kreuz{3}{-5}{\tau_{34}} +\kreuz{2}{-6}{\tau_{23}} +\kreuz{1}{-7}{\tau_{12}} + +\draw[->,color=gray] (0,0) -- (0,-7); +\draw[->,color=gray] (1,0) -- (1,-6); +\draw[->,color=gray] (2,0) -- (2,-5); +%\draw[->,color=gray] (3,0) -- (3,-4); +%\draw[->,color=gray] (4,0) -- (4,-3); +\draw[->,color=gray] (5,0) -- (5,-2); +\draw[->,color=gray] (6,0) -- (6,-1); + +\draw[->,color=gray] (8,-1) -- (8,-8); +\draw[->,color=gray] (7,-2) -- (7,-8); +\draw[->,color=gray] (6,-3) -- (6,-8); +%\draw[->,color=gray] (5,-4) -- (5,-8); +%\draw[->,color=gray] (4,-5) -- (4,-8); +\draw[->,color=gray] (3,-6) -- (3,-8); +\draw[->,color=gray] (2,-7) -- (2,-8); + +\fill (6,-1) circle[radius=0.05]; +\fill (7,-1) circle[radius=0.05]; +\fill (8,-1) circle[radius=0.05]; + +\fill (5,-2) circle[radius=0.05]; +\fill (6,-2) circle[radius=0.05]; +\fill (7,-2) circle[radius=0.05]; + +%\fill (4,-3) circle[radius=0.05]; +\fill (5,-3) circle[radius=0.05]; +\fill (6,-3) circle[radius=0.05]; + +%\fill (3,-4) circle[radius=0.05]; +%\fill (4,-4) circle[radius=0.05]; +%\fill (5,-4) circle[radius=0.05]; + +\fill (2,-5) circle[radius=0.05]; +\fill (3,-5) circle[radius=0.05]; +%\fill (4,-5) circle[radius=0.05]; + +\fill (1,-6) circle[radius=0.05]; +\fill (2,-6) circle[radius=0.05]; +\fill (3,-6) circle[radius=0.05]; + +\fill (0,-7) circle[radius=0.05]; +\fill (1,-7) circle[radius=0.05]; +\fill (2,-7) circle[radius=0.05]; + +\end{tikzpicture} +\end{center} +Es ist also +\[ +\sigma += +\tau_{12} \tau_{23} \tau_{34} \dots \tau_{k-3,k-2} \tau_{k-2,k-1} \tau_{k-1,k}. +\] +\begin{satz} +Jede Permutation $\sigma\in S_n$ lässt sich als ein Produkt von +Transpositionen schreiben. +Jeder Zyklus der Länge $k$ lässt sich aus $k-1$ Transpositionen +zusammensetzen. +Eine Permutation mit einer Zerlegung in Zyklen der Längen $l_1,\dots,l_p$ +kann als Produkt von $l_1+\dots+l_p-p$ Transpositionen geschrieben werden. +\end{satz} + +\subsection{Signum einer Permutation} +Die Anzahl Transpositionen, die benötigt werden, um eine Permutation +zu beschreiben, ist nicht fest. +Wenn $\sigma$ mit $k$ Transpositionen geschrieben werden kann und +$\gamma$ mit $l$, dann hat $\gamma\sigma\gamma^{-1}$ die gleiche +Zyklenzerlegung, kann aber mit $k+2l$ Transpositionen geschrieben +werden. +Die Anzahl Transpositionen, die zur Darstellung einer Permutation +nötig ist, ändert sich aber immer nur um eine gerade Zahl. +Die Anzahl ist also keine Invariante einer Permutation, aber ob +die Anzahl gerade ist oder nicht, ist sehr wohl eine charkterisierende +Eigenschaft einer Permutation. + +\begin{definition} +Das {\em Vorzeichen} oder {\em Signum} einer Permutation $\sigma$ ist +die Zahl $\operatorname{sgn}(\sigma)=(-1)^k$, wenn $\sigma$ als Produkt +von $k$ Transpositionen geschrieben werden kann. +\end{definition} + +Die inverse Permutation $\sigma^{-1}$ hat das gleiche Signum wie $\sigma$. +Wenn nämlich $\sigma= \tau_1\tau_2\dots\tau_k$ geschrieben werden kann, +dann ist $\sigma^{-1}=\tau_k\dots\tau_2\tau_1$, sowohl $\sigma$ wie +$\sigma^{-1}$ können also mit der gleichen Zahl von Transpositionen +geschrieben werden, sie haben also auch das gleiche Vorzeichen. + +Die Abbildung $S_n\to\{\pm\}$, die einer Permutation das Signum zuordnet, +ist ein Homomorphismus von Gruppen, +d.~h. +\[ +\operatorname{sgn}(\sigma_1\sigma_2) += +\operatorname{sgn}(\sigma_1) +\operatorname{sgn}(\sigma_2) +\] +da ganz offensichtlich $\sigma_1\sigma_2$ mit $k_1+k_2$ Transpositionen +geschrieben kann, wenn $\sigma_i$ mit $k_i$ Transpositionen geschrieben +werden kann. + +Das Signum definiert in der symmetrischen Gruppe eine Teilmenge bestehnd +aus den Permutationen mit Signum $+1$. + +\begin{definition} +Die Teilmenge +\[ +A_n += +\{ +\sigma\in S_n\;|\; \operatorname{sgn}(\sigma)=1 +\} +\subset S_n. +\] +heisst die {\em alternierende Gruppe} der Ordnung $n$ +Die Elemente von $A_n$ heissen auch die {\em geraden} Permutationen, +die +Elemente von $S_n\setminus A_n$ heissen auch die {\em ungeraden} +Permutationen. +\end{definition} + +Die alternierende Gruppe $A_n$ ist tatsächlich eine Untergruppe. +Zunächst ist $\operatorname{sign}(e)=(-1)^0=01$, also ist $e\in A_n$. +Es wurde schon gezeigt, dass mit jedem Element $\sigma\in A_n$ auch +das inverse Element $\sigma^{-1}\in A_n$ ist. +Es muss aber noch sichergestellt sein, dass das Produkt von zwei +geraden Transpositionen wieder gerade ist: +\[ +\begin{aligned} +\sigma_1,\sigma_2&\in A_n +&\Rightarrow&& +\operatorname{sign}(\sigma_1) +&= +\operatorname{sign}(\sigma_2) += +1 +\\ +&&\Rightarrow&& +\operatorname{sign}(\sigma_1\sigma_2) +&= +\operatorname{sign}(\sigma_1) +\operatorname{sign}(\sigma_2) += +1\cdot 1=1 +&&\Rightarrow& +\sigma_1\sigma_2&\in A_n. +\end{aligned} +\] +Damit ist gezeigt, dass die alternierende Gruppe $A_n$ ein Untergruppe von +$S_n$ ist. + |