diff options
Diffstat (limited to 'buch/chapters/50-permutationen')
| -rw-r--r-- | buch/chapters/50-permutationen/beispiele/perm.m | 44 | ||||
| -rw-r--r-- | buch/chapters/50-permutationen/chapter.tex | 15 | ||||
| -rw-r--r-- | buch/chapters/50-permutationen/endlich.tex | 288 | ||||
| -rw-r--r-- | buch/chapters/50-permutationen/matrizen.tex | 187 | ||||
| -rw-r--r-- | buch/chapters/50-permutationen/transpositionen.tex | 219 | ||||
| -rw-r--r-- | buch/chapters/50-permutationen/uebungsaufgaben/5001.tex | 121 |
6 files changed, 874 insertions, 0 deletions
diff --git a/buch/chapters/50-permutationen/beispiele/perm.m b/buch/chapters/50-permutationen/beispiele/perm.m new file mode 100644 index 0000000..2e837ef --- /dev/null +++ b/buch/chapters/50-permutationen/beispiele/perm.m @@ -0,0 +1,44 @@ +# +# perm.m -- find a random permutation +# +# (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +# +N = 8 +M = N+1 + +function retval = permutation(n) + p = (1:n); + for i = (1:(n-1)) + j = i + 1 + floor(rand() * (n-i)); + s = p(i); + p(i) = p(j); + p(j) = s; + endfor + retval = p; +end + +function retval = compose(p,q) + n = size(p)(1,2); + retval = zeros(1,n); + for i = (1:n) + retval(i) = q(p(i)); + end +end + +sigma = permutation(N) +sigma = compose(sigma, permutation(N)) +sigma = compose(sigma, permutation(N)) +sigma = compose(sigma, permutation(N)) +sigma = compose(sigma, permutation(N)) +sigma = compose(sigma, permutation(N)) +sigma = compose(sigma, permutation(N)) + +s = zeros(M,N); +s(1,:) = sigma; +for i = (2:M) + s(i,:) = compose(s(i-1,:), sigma); +end + +s + +compose(sigma, permutation(N)) diff --git a/buch/chapters/50-permutationen/chapter.tex b/buch/chapters/50-permutationen/chapter.tex index c9514b8..842051b 100644 --- a/buch/chapters/50-permutationen/chapter.tex +++ b/buch/chapters/50-permutationen/chapter.tex @@ -7,9 +7,24 @@ \label{buch:chapter:permutationen}} \lhead{Permutationen} \rhead{} +Die Berechnung der Determinante einer Matrix macht ausgedehnten +Gebrauch von der Tatsache, dass die Vertauschung von zwei Zeilen +oder Spalten das Vorzeichen des Wertes der Determinanten bewirkt. +In diesem Kapitel sollen die Permutationen der Zeilen abstrakt +untersucht werden. +Wir erhalten so eine abstrakte Gruppe, die Permutationsgruppe. +Ihre Elemente lassen sich auch durch spezielle Matrizen beschreiben, +eine Darstellung der Gruppe, die auch unmittelbar zu einer +Formel für die Determinante einer Matrix führt. \input{chapters/50-permutationen/endlich.tex} \input{chapters/50-permutationen/transpositionen.tex} \input{chapters/50-permutationen/matrizen.tex} \input{chapters/50-permutationen/determinante.tex} +\section*{Übungsaufgaben} +\aufgabetoplevel{chapters/50-permutationen/uebungsaufgaben} +\begin{uebungsaufgaben} +\uebungsaufgabe{5001} +\end{uebungsaufgaben} + diff --git a/buch/chapters/50-permutationen/endlich.tex b/buch/chapters/50-permutationen/endlich.tex index 71cc991..9514f88 100644 --- a/buch/chapters/50-permutationen/endlich.tex +++ b/buch/chapters/50-permutationen/endlich.tex @@ -6,3 +6,291 @@ \section{Permutationen einer endlichen Menge \label{buch:section:permutationen-einer-endlichen-menge}} \rhead{Permutationen} +Eine endliche Anzahl $n$ von Objekten können auf $n!$ Arten angeordnet +werden. +Als Objektmenge nehmen wir $[n] = \{ 1,\dots,n\}$. +Die Operation, die die Objekte in eine bestimmte Reihenfolge bringt, +ist eine Abbildung $\sigma\colon[n]\to[n]$. +Eine Permutation ist eine umkehrbare Abbildung $[n]\to[n]$. +Die Menge $S_n$ aller umkehrbaren Abbildungen $[n]\to[n]$ +mit der Verknüpfung von Abbildungen als Operation heisst die +die {\em symmetrische Gruppe}. +Die identische Abbildung $\sigma(x)=x$ ist das {\em neutrale +Element} der Gruppe $S_n$ und wir auch mit $e$ bezeichnet. + +\subsection{Permutationen als $2\times n$-Matrizen} +Eine Permutation kann als $2\times n$-Matrix geschrieben werden: +\begin{center} +\begin{tikzpicture}[>=latex,thick] +\def\sx{0.8} +\def\sy{1} +\begin{scope}[xshift=-3cm] +\foreach \x in {1,...,6}{ + \node at ({(\x-1)*\sx},\sy) [above] {$\tiny\x$}; + \fill ({(\x-1)*\sx},\sy) circle[radius=0.05]; + \fill ({(\x-1)*\sx},0) circle[radius=0.05]; +} +\draw[->] (0,\sy) to[out=-70,in=110] (\sx,0); +\draw[<-] (0,0) to[out=70,in=-110] (\sx,\sy); +\draw[->] ({2*\sx},\sy) -- ({2*\sx},0); +\draw[->] ({3*\sx},\sy) to[out=-70,in=110] ({4*\sx},0); +\draw[->] ({4*\sx},\sy) to[out=-70,in=110] ({5*\sx},0); +\draw[->] ({5*\sx},\sy) to[out=-110,in=70] ({3*\sx},0); +\end{scope} +\node at (2.4,{\sy/2}) {$\mathstrut=\mathstrut$}; +\node at (5,{\sy/2}) {$\displaystyle +\renewcommand{\arraystretch}{1.4} +\begin{pmatrix} +1&2&3&4&5&6\\ +2&1&3&5&6&4 +\end{pmatrix} +$}; +\end{tikzpicture} +\end{center} +Das neutrale Element hat die Matrix +\[ +e = \begin{pmatrix} +1&2&3&4&5&6\\ +1&2&3&4&5&6 +\end{pmatrix} +\] +aus zwei identischen Zeilen. + +Die Verknüpfung zweier solcher Permutationen kann leicht graphisch +dargestellt werden: dazu werden die beiden Permutationen +untereinander geschrieben und Spalten der zweiten Permutation +in der Reihen folge der Zahlen in der zweiten Zeile der ersten +Permutation angeordnet. +Die zusammengesetzte Permutation kann dann in der zweiten Zeile +der zweiten Permutation abgelesen werden: +\begin{center} +\begin{tikzpicture}[>=latex,thick] +\begin{scope}[xshift=-4.5cm] +\node at (0,0) {$\displaystyle +\sigma_1=\begin{pmatrix} +1&2&3&4&5&6\\ +2&1&3&5&6&4 +\end{pmatrix}$}; +\node at (0,-1) {$\displaystyle +\sigma_2=\begin{pmatrix} +1&2&3&4&5&6\\ +3&4&5&6&1&2 +\end{pmatrix} +$}; +\end{scope} +\begin{scope} +\node at (0,0) {$\displaystyle +\begin{pmatrix} +1&2&3&4&5&6\\ +2&1&3&5&6&4 +\end{pmatrix}$}; +\node at (0,-1) {$\displaystyle +\begin{pmatrix} +2&1&3&5&6&4\\ +4&3&5&1&2&6 +\end{pmatrix} +$}; + +\end{scope} +\begin{scope}[xshift=4.5cm] +\node at (0,-0.5) {$\displaystyle +\sigma_2\sigma_1=\begin{pmatrix} +1&2&3&4&5&6\\ +4&3&5&1&2&6 +\end{pmatrix} +$}; +\end{scope} +\end{tikzpicture} +\end{center} +Die Inverse einer Permutation kann erhalten werden, indem die beiden +Zeilen vertauscht werden und dann die Spalten wieder so angeordnet werden, +dass die Zahlen in der ersten Zeile ansteigend sind: +\[ +\sigma = \begin{pmatrix} +1&2&3&4&5&6\\ +2&1&3&5&6&4 +\end{pmatrix} +\qquad\Rightarrow\qquad +\sigma^{-1} += +\begin{pmatrix} +2&1&3&5&6&4\\ +1&2&3&4&5&6 +\end{pmatrix} += +\begin{pmatrix} +1&2&3&4&5&6\\ +2&1&3&6&4&5 +\end{pmatrix}. +\] + +\subsection{Zyklenzerlegung} +Eine Permutation $\sigma\in S_n$ kann auch mit sogenanten Zyklenzerlegung +analysiert werden. +Zum Beispiel: +\begin{center} +\begin{tikzpicture}[>=latex,thick] +\begin{scope}[xshift=-3cm] +\node at (0,0) {$\displaystyle +\sigma=\begin{pmatrix} +{\color{red}1}&{\color{red}2}&{\color{darkgreen}3}&{\color{blue}4}&{\color{blue}5}&{\color{blue}6}\\ +{\color{red}2}&{\color{red}1}&{\color{darkgreen}3}&{\color{blue}5}&{\color{blue}6}&{\color{blue}4} +\end{pmatrix}$}; +\end{scope} +\node at (0,0) {$\mathstrut=\mathstrut$}; +\begin{scope}[xshift=1.5cm] +\coordinate (A) at (0,0.5); +\coordinate (B) at (0,-0.5); +\draw[->,color=red] (A) to[out=-20,in=20] (0,-0.5); +\draw[->,color=red] (B) to[out=160,in=-160] (0,0.5); +\node at (A) [above] {$\tiny 1$}; +\node at (B) [below] {$\tiny 2$}; +\fill (A) circle[radius=0.05]; +\fill (B) circle[radius=0.05]; + +\coordinate (C) at (1.5,0.25); +\node at (C) [above] {$\tiny 3$}; +\draw[->,color=darkgreen] ({1.5+0.01},0.25) to[out=-10,in=-170] ({1.5-0.01},0.25); +\draw[color=darkgreen] (1.5,{0.25-0.3}) circle[radius=0.3]; +\fill (C) circle[radius=0.05]; + +\def\r{0.5} +\coordinate (D) at ({3.5+\r*cos(90)},{0+\r*sin(90)}); +\coordinate (E) at ({3.5+\r*cos(210)},{0+\r*sin(210)}); +\coordinate (F) at ({3.5+\r*cos(330)},{0+\r*sin(330)}); +\node at (D) [above] {$\tiny 4$}; +\node at (E) [below left] {$\tiny 5$}; +\node at (F) [below right] {$\tiny 6$}; +\draw[->,color=blue] (D) to[out=180,in=120] (E); +\draw[->,color=blue] (E) to[out=-60,in=-120] (F); +\draw[->,color=blue] (F) to[out=60,in=0] (D); +\fill (D) circle[radius=0.05]; +\fill (E) circle[radius=0.05]; +\fill (F) circle[radius=0.05]; + +\end{scope} +\end{tikzpicture} +\end{center} + +\begin{definition} +Ein Zyklus $Z$ ist eine unter $\sigma$ invariante Teilmenge von $[n]$ +minimaler Grösse. +Die Zyklenzerlegung ist eine Zerlegung von $[n]$ in Zyklen +\[ +[n] += +\cup_{i=1}^k Z_i, +\] +wobei jede Menge $Z_i$ ein Zyklus ist. +\end{definition} + +Der folgende Algorithmus findet die Zyklenzerlegung einer Permutation. + +\begin{satz} +Sei $\sigma\in S_n$ eine Permutation. Der folgende Algorithmus findet +die Zyklenzerlegung von $\sigma$: +\begin{enumerate} +\item +$i=1$ +\item +Wähle das erste noch nicht verwendete Element +\[ +s_i=\min\biggl( [n] \setminus \bigcup_{j< i} Z_j\biggr) +\] +\item +Bestimme alle Elemente, die aus $s_i$ durch Anwendung von $\sigma$ +entstehen: +\[ +Z_i += +\{ s_i, \sigma(s_i), \sigma(\sigma(s_i)), \dots \} += +\{\sigma^k(s_i)\;|\; k\ge 0\}. +\] +\item +Falls $\bigcup_{j\le i} Z_j\ne [n]$, erhöhe $i$ um $1$ und fahre +weiter bei 2. +\end{enumerate} +\end{satz} + +Mit Hilfe der Zyklenzerlegung von $\sigma$ lassen sich auch +gewisse Eigenschaften von $\sigma$ ableiten. +Sei also $[n] = Z_1\cup\dots\cup Z_k$ die Zyklenzerlegung. +Für jedes Element $x\in S_i$ gilt $\sigma^{|S_i|}(x) = x$. +Die kleinste Zahl $m$, für die $\sigma^m=e$ ist, das kleinste +gemeinsame Vielfache der Zyklenlängen: +\[ +m = \operatorname{kgV} (|Z_1|,|Z_2|,\dots,|Z_k|). +\] + +\subsection{Konjugierte Elemente in $S_n$} +Zwei Elemente $g_1,g_2\in G$ einer Gruppe heissen konjugiert, wenn +es ein Element $c\in G$ gibt derart, dass $cg_1c^{-1}=g_2$. +Bei Matrizen hat dies bedeutet, dass die beiden Matrizen durch +Basiswechsel auseinander hervorgehen. +Dasselbe lässt sich auch im Kontext der symmetrischen Gruppe sagen. + +Seien $\sigma_1$ und $\sigma_2$ zwei konjugierte Permutationen in $S_n$. +Es gibt also eine Permutation $\gamma\in S_n$ derat, dass +$\sigma_1=\gamma\sigma_2\sigma^{-1}$ oder $\gamma^{-1}\sigma_1\gamma=\sigma_2$. +Dann gilt auch für die Potenzen +\begin{equation} +\sigma_1^k = \gamma\sigma_2^k\gamma^{-1}. +\label{buch:permutationen:eqn:konjpot} +\end{equation} +Ist $Z_i$ ein Zyklus von $\sigma_2$ und $x\in Z_i$, dann ist +$Z_i = \{ x,\sigma_2(x),\sigma_2^2(x),\dots\}$. +Die Menge $\gamma(Z_i)$ besteht dann aus dem Elementen +$\gamma(Z_i)=\{\gamma(x),\gamma(\sigma_2(x)),\gamma(\sigma_2^2(x)),\dots\}$. +Aus der Formel~\eqref{buch:permutationen:eqn:konjpot} folgt +$\sigma_1^k\gamma = \gamma\sigma_2^k$, also +\[ +\gamma(Z_i) += +\{\gamma(x),\sigma_1(\gamma(x)),\sigma_1^2(\gamma(x)),\dots\}, +\] +Also ist $\gamma(Z_i)$ ein Zyklus von $\sigma_1$. +Die Permutation $\gamma$ bildet also Zyklen von $\sigma_2$ auf Zyklen +von $\sigma_1$ ab. +Es folgt daher der folgende Satz: + +\begin{satz} +Sind $\sigma_1,\sigma_2\in S_n$ konjugiert $\sigma_1=\gamma\sigma_2\gamma^{-1}$ +mit dem $\gamma\in S_n$. +Wenn $Z_1,\dots,Z_k$ die Zyklen von $\sigma_2$ sind, dann sind +$\gamma(Z_1),\dots,\gamma(Z_k)$ die Zyklen von $\sigma_1$. +\end{satz} + +Die Zyklenzerlegung kann mit der Jordan-Normalform \ref{XXX} +einer Matrix verglichen werden. +Durch einen Basiswechsel, welcher durch eine ``Konjugation'' +von Matrizen ausgedrückt wir, kann die Matrix in eine besonders +übersichtliche Form gebracht werden. +Wenn $\sigma$ die Zyklenzerlegung $Z_1,\dots,Z_k$ mit Zyklenlängen +$l_i=|Z_i|$, dann kann man die Menge $[n]$ wie folgt in Teilmengen +\begin{align*} +X_1 &= \{1,\dots, l_1\}, +\\ +X_2 &= \{l_1+1,\dots,l_1+l_2\}, +\\ +X_i &= \{l_1+\dots+l_{i-1}+1,\dots, l_1+\dots+l_i\} +\\ +X_k &= \{l_1+\dots+l_{k-1}+1,\dots n\} +\end{align*} +zerlegen. +Sei $\sigma_2$ die Permutation, die in jeder der Mengen $X_i$ durch +zyklische Vertauschung der Elemente wirkt. +Indem man die Elemente von $Z_i$ in der Reihenfolge, in der sie durch +$\sigma_1$ erreicht werden, auf die Elemente $X_i$ abbildet, findet +man eine Permutation, die Zyklen von $\sigma_1$ in Zyklen von $\sigma_2$ +überführt. + +\begin{satz} +Wenn zwei Elemente $\sigma_1,\sigma_2\in S_n$ Zyklenzerlegungen mit den +gleichen Zyklenlängen haben, dann sind sie konjugiert. +\end{satz} + +Ein Element $\sigma\in S_n$ ist also bis auf eine Permutation +vollständig durch die Länge der Zyklen von $\sigma$ charakterisiert. + + diff --git a/buch/chapters/50-permutationen/matrizen.tex b/buch/chapters/50-permutationen/matrizen.tex index 3d06b0a..14aba7a 100644 --- a/buch/chapters/50-permutationen/matrizen.tex +++ b/buch/chapters/50-permutationen/matrizen.tex @@ -6,4 +6,191 @@ \section{Permutationsmatrizen \label{buch:section:permutationsmatrizen}} \rhead{Permutationsmatrizen} +Die Eigenschaft, dass eine Vertauschung das Vorzeichen kehrt, ist +eine wohlebekannte Eigenschaft der Determinanten. +In diesem Abschnitt soll daher eine Darstellung von Permutationen +als Matrizen gezeigt werden und die Verbindung zwischen dem +Vorzeichen einer Permutation und der Determinanten hergestellt +werden. + +\subsection{Matrizen} +Gegeben sei jetzt eine Permutation $\sigma\in S_n$. +Aus $\sigma$ lässt sich eine lineare Abbildung $\Bbbk^n\to\Bbbk^n$ +konstruieren, die die Standardbasisvektoren permutiert, also +\[ +f_{\sigma}\colon +\Bbbk^n \to \Bbbk^n +: +\left\{ +\begin{aligned} +e_1&\mapsto e_{\sigma(1)} \\ +e_2&\mapsto e_{\sigma(2)} \\ +\vdots&\\ +e_n&\mapsto e_{\sigma(n)} +\end{aligned} +\right. +\] +Die Matrix $P_\sigma$ der linearen Abbildung $f_{\sigma}$ hat in Spalte $i$ +genau eine $1$ in der Zeile $\sigma(i)$, also +\[ +(P_\sigma)_{ij} = \delta_{j\sigma(i)}. +\] + +\begin{beispiel} +Die zur Permutation +\[ +\begin{pmatrix} +1&2&3&4&5&6\\ +2&1&3&5&6&4 +\end{pmatrix} +\] +gehörige lineare Abbildung $f_\sigma$ hat die Matrix +\[ +A_\sigma += +\begin{pmatrix} +0&1&0&0&0&0\\ +1&0&0&0&0&0\\ +0&0&1&0&0&0\\ +0&0&0&0&0&1\\ +0&0&0&1&0&0\\ +0&0&0&0&1&0 +\end{pmatrix} +\qedhere +\] +\end{beispiel} + +\begin{definition} +Eine Permutationsmatrix ist eine Matrix $P\in M_n(\Bbbk)$ +derart, die in jeder Zeile und Spalte genau eine $1$ enhalten, +während alle anderen Matrixelemente $0$ sind. +\end{definition} + +Es ist klar, dass aus einer Permutationsmatrix auch die Permutation +der Standardbasisvektoren abgelesen werden kann. +Die Verknüpfung von Permutationen wird zur Matrixmultiplikation +von Permutationsmatrizen, die Zuordnung $\sigma\mapsto P_\sigma$ +ist also ein Homomorphismus +$ +S_n \to M_n(\Bbbk^n), +$ +es ist $P_{\sigma_1\sigma_2}=P_{\sigma_1}P_{\sigma_2}$. + +\subsection{Transpositionen} +Transpositionen sind Permutationen, die genau zwei Elemente von $[n]$ +vertauschen. +Wir ermitteln jetzt die Permutationsmatrix der Transposition $\tau=\tau_{ij}$ +\[ +P_{\tau_{ij}} += +\begin{pmatrix} +1& & & & & & & & \\ + &\ddots& & & & & & & \\ + & &1& & & & & & \\ + & & &0 &\dots&1 & & & \\ + & & &\vdots& &\vdots& & & \\ + & & &1 &\dots&0 & & & \\ + & & & & & &1& & \\ + & & & & & & &\ddots& \\ + & & & & & & & &1 +\end{pmatrix} +\qedhere +\] + +Die Permutation $\sigma$ mit dem Zyklus $1\to 2\to\dots\to l-1\to l\to 1$ +der Länge $l$ kann aus aufeinanderfolgenden Transpositionen zusammengesetzt +werden, die zugehörigen Permutationsmatrizen sind +\begin{align*} +P_\sigma +&= +P_{\tau_{12}} +P_{\tau_{23}} +P_{\tau_{34}}\dots +P_{\tau_{l-2,l-1}} +P_{\tau_{l-1,l}} +\\ +&= +\begin{pmatrix} +0&1&0&0&\dots\\ +1&0&0&0&\dots\\ +0&0&1&0&\dots\\ +0&0&0&1&\dots\\ +\vdots&\vdots&\vdots&\vdots&\ddots +\end{pmatrix} +\begin{pmatrix} +1&0&0&0&\dots\\ +0&0&1&0&\dots\\ +0&1&0&0&\dots\\ +0&0&0&1&\dots\\ +\vdots&\vdots&\vdots&\vdots&\ddots +\end{pmatrix} +\begin{pmatrix} +1&0&0&0&\dots\\ +0&1&0&0&\dots\\ +0&0&0&1&\dots\\ +0&0&1&0&\dots\\ +\vdots&\vdots&\vdots&\vdots&\ddots +\end{pmatrix} +\dots +\\ +&= +\begin{pmatrix} +0&0&1&0&\dots\\ +1&0&0&0&\dots\\ +0&1&0&0&\dots\\ +0&0&0&1&\dots\\ +\vdots&\vdots&\vdots&\vdots&\ddots +\end{pmatrix} +\begin{pmatrix} +1&0&0&0&\dots\\ +0&1&0&0&\dots\\ +0&0&0&1&\dots\\ +0&0&1&0&\dots\\ +\vdots&\vdots&\vdots&\vdots&\ddots +\end{pmatrix} +\dots +\\ +&= +\begin{pmatrix} +0&0&0&1&\dots\\ +1&0&0&0&\dots\\ +0&1&0&0&\dots\\ +0&0&1&0&\dots\\ +\vdots&\vdots&\vdots&\vdots&\ddots +\end{pmatrix} +\\ +&\vdots\\ +&= +\begin{pmatrix} +0&0&0&0&\dots&0&1\\ +1&0&0&0&\dots&0&0\\ +0&1&0&0&\dots&0&0\\ +0&0&1&0&\dots&0&0\\ +\vdots&\vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\ +0&0&0&0&\dots&1&0 +\end{pmatrix} +\end{align*} + +\subsection{Determinante und Vorzeichen} +Die Transpositionen haben Permutationsmatrizen, die aus der Einheitsmatrix +entstehen, indem genau zwei Zeilen vertauscht werden. +Die Determinante einer solchen Permutationsmatrix ist +\[ +\det P_{\tau} = - \det E = -1 = \operatorname{sgn}(\tau). +\] +Nach der Produktregel für die Determinante folgt für eine Darstellung +der Permutation $\sigma=\tau_1\dots\tau_l$ als Produkt von Transpositionen, +dass +\[ +\det P_{\sigma} += +\det P_{\tau_1} \dots \det P_{\tau_l} += +(-1)^l += +\operatorname{sgn}(\sigma). +\] +Das Vorzeichen einer Permutation ist also identisch mit der Determinante +der zugehörigen Permutationsmatrix. + 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. + diff --git a/buch/chapters/50-permutationen/uebungsaufgaben/5001.tex b/buch/chapters/50-permutationen/uebungsaufgaben/5001.tex new file mode 100644 index 0000000..2893adf --- /dev/null +++ b/buch/chapters/50-permutationen/uebungsaufgaben/5001.tex @@ -0,0 +1,121 @@ +Sind die beiden Permutationen +\[ +\sigma_1 += +\begin{pmatrix} +1& 2& 3& 4& 5& 6& 7& 8\\ +8& 6& 5& 7& 2& 3& 4& 1 +\end{pmatrix} +\qquad\text{und}\qquad +\sigma_2 += +\begin{pmatrix} +1& 2& 3& 4& 5& 6& 7& 8\\ +8& 7& 5& 6& 3& 4& 1& 2 +\end{pmatrix} +\] +konjugiert in $S_8$? +Wenn ja, finden Sie eine Permutation $\gamma$ derart, dass +$\gamma\sigma_1\gamma^{-1}=\sigma_2$ + +\begin{loesung} +Die Zyklenzerlegungen von $\sigma_1$ und $\sigma_2$ sind +\begin{center} +\begin{tikzpicture}[>=latex,thick] +\begin{scope}[xshift=-3.3cm] +\node at (-0.25,1.7) {$\sigma_1$}; +\draw (-3.3,-1.3) rectangle (2.8,1.3); +\coordinate (A) at (-2.4,0.5); +\coordinate (B) at (-2.4,-0.5); +\coordinate (C) at (-0.8,0.5); +\coordinate (D) at (-0.8,-0.5); +\coordinate (E) at (0.8,0.5); +\coordinate (F) at (0.8,-0.5); +\coordinate (G) at (1.8,0.5); +\coordinate (H) at (1.8,-0.5); + +\draw[->] (E) to[out=-135,in=135] (F); +\draw[->] (F) to[out=-45,in=-135] (H); +\draw[->] (H) to[out=45,in=-45] (G); +\draw[->] (G) to[out=135,in=45] (E); + +\draw[->] (A) to[out=-180,in=-180] (B); +\draw[->] (B) to[out=0,in=0] (A); + +\draw[->] (C) to[out=-180,in=-180] (D); +\draw[->] (D) to[out=0,in=0] (C); + +\node at (A) [above] {$1$}; +\node at (B) [below] {$8$}; +\node at (C) [above] {$4$}; +\node at (D) [below] {$7$}; +\node at (E) [above left] {$2$}; +\node at (F) [below left] {$6$}; +\node at (H) [below right] {$3$}; +\node at (G) [above right] {$5$}; + +\fill (A) circle[radius=0.05]; +\fill (B) circle[radius=0.05]; +\fill (C) circle[radius=0.05]; +\fill (D) circle[radius=0.05]; +\fill (E) circle[radius=0.05]; +\fill (F) circle[radius=0.05]; +\fill (G) circle[radius=0.05]; +\fill (H) circle[radius=0.05]; +\end{scope} +\begin{scope}[xshift=3.3cm] +\node at (-0.25,1.7) {$\sigma_2$}; +\draw (-3.3,-1.3) rectangle (2.8,1.3); +\coordinate (A) at (-2.4,0.5); +\coordinate (B) at (-2.4,-0.5); +\coordinate (C) at (-0.8,0.5); +\coordinate (D) at (-0.8,-0.5); +\coordinate (E) at (0.8,0.5); +\coordinate (F) at (0.8,-0.5); +\coordinate (G) at (1.8,0.5); +\coordinate (H) at (1.8,-0.5); + +\draw[->] (E) to[out=-135,in=135] (F); +\draw[->] (F) to[out=-45,in=-135] (H); +\draw[->] (H) to[out=45,in=-45] (G); +\draw[->] (G) to[out=135,in=45] (E); + +\draw[->] (A) to[out=-180,in=-180] (B); +\draw[->] (B) to[out=0,in=0] (A); + +\draw[->] (C) to[out=-180,in=-180] (D); +\draw[->] (D) to[out=0,in=0] (C); + +\node at (A) [above] {$3$}; +\node at (B) [below] {$5$}; +\node at (C) [above] {$4$}; +\node at (D) [below] {$6$}; +\node at (E) [above left] {$7$}; +\node at (F) [below left] {$1$}; +\node at (H) [below right] {$8$}; +\node at (G) [above right] {$2$}; + +\fill (A) circle[radius=0.05]; +\fill (B) circle[radius=0.05]; +\fill (C) circle[radius=0.05]; +\fill (D) circle[radius=0.05]; +\fill (E) circle[radius=0.05]; +\fill (F) circle[radius=0.05]; +\fill (G) circle[radius=0.05]; +\fill (H) circle[radius=0.05]; +\end{scope} +\end{tikzpicture} +\end{center} +Da die beiden Permutationen die gleiche Zyklenzerlegung haben, müssen +sie konjugiert sein. +Die Permutation +\[ +\gamma += +\begin{pmatrix} +1&2&3&4&5&6&7&8\\ +6&5&1&4&8&7&2&3 +\end{pmatrix} +\] +bildet die Zyklenzerlegung ab, also ist $\gamma\sigma_1\gamma^{-1}=\sigma_2$. +\end{loesung} |