From 45794fb198c8fac02b5c82b6ac3f1e17bac1075e Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Andreas=20M=C3=BCller?= Date: Tue, 19 Jan 2021 22:08:40 +0100 Subject: =?UTF-8?q?Permutationen=20hinzugef=C3=BCgt?= MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit --- buch/chapters/40-eigenwerte/beispiele/jp.maxima | 19 ++ buch/chapters/40-eigenwerte/beispiele/n.m | 55 ++++ buch/chapters/40-eigenwerte/beispiele/n.maxima | 20 ++ buch/chapters/40-eigenwerte/spektralradius.tex | 351 +++++++++++++++++++++ buch/chapters/50-permutationen/beispiele/perm.m | 44 +++ buch/chapters/50-permutationen/chapter.tex | 15 + buch/chapters/50-permutationen/endlich.tex | 288 +++++++++++++++++ buch/chapters/50-permutationen/matrizen.tex | 187 +++++++++++ buch/chapters/50-permutationen/transpositionen.tex | 219 +++++++++++++ .../50-permutationen/uebungsaufgaben/5001.tex | 121 +++++++ 10 files changed, 1319 insertions(+) create mode 100644 buch/chapters/40-eigenwerte/beispiele/jp.maxima create mode 100644 buch/chapters/40-eigenwerte/beispiele/n.m create mode 100644 buch/chapters/40-eigenwerte/beispiele/n.maxima create mode 100644 buch/chapters/50-permutationen/beispiele/perm.m create mode 100644 buch/chapters/50-permutationen/uebungsaufgaben/5001.tex (limited to 'buch') diff --git a/buch/chapters/40-eigenwerte/beispiele/jp.maxima b/buch/chapters/40-eigenwerte/beispiele/jp.maxima new file mode 100644 index 0000000..a80a0a2 --- /dev/null +++ b/buch/chapters/40-eigenwerte/beispiele/jp.maxima @@ -0,0 +1,19 @@ +/* + * jp.maxima -- potenzen von Jordan-Blöcken + * + * (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule + */ + +A: matrix( +[lambda, 1, 0, 0, 0, 0 ], +[ 0,lambda, 1, 0, 0, 0 ], +[ 0, 0,lambda, 1, 0, 0 ], +[ 0, 0, 0,lambda, 1, 0 ], +[ 0, 0, 0, 0,lambda, 1 ], +[ 0, 0, 0, 0, 0,lambda ] +); +B: A.A; +B: B.A; +B: B.A; +B: B.A; +B: B.A; diff --git a/buch/chapters/40-eigenwerte/beispiele/n.m b/buch/chapters/40-eigenwerte/beispiele/n.m new file mode 100644 index 0000000..af0219b --- /dev/null +++ b/buch/chapters/40-eigenwerte/beispiele/n.m @@ -0,0 +1,55 @@ +# +# n.m -- Polynome mit dem gleichen Wert von p(A) +# +# (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +# + +A0 = [ + 2, 1, 0; + 0, 2, 0; + 0, 0, 3 +]; + +# find a 3x3 matrix in SL(3,Z) + +function retval = zufallswert() + x = round(rand() * 10) - 2; + if (x >= 0) + x = x + 1; + endif + retval = x; +end + +function retval = zufallsmatrix(n) + retval = zeros(n, n); + for i = (1:n) + for j = (1:n) + retval(i,j) = zufallswert(); + end + end +end + +function retval = regulaer(n) + d = 0; + do + retval = zufallsmatrix(2); + d = det(retval); + until (d == 1); +end + +function retval = eingebettet(n,k) + retval = eye(n); + retval(k:k+1,k:k+1) = regulaer(2); +end + +format long + +B = eye(3); +B = B * eingebettet(3,2) +B = B * eingebettet(3,1) + +B +inverse(B) + +A = round(B * A0 * inverse(B)) + diff --git a/buch/chapters/40-eigenwerte/beispiele/n.maxima b/buch/chapters/40-eigenwerte/beispiele/n.maxima new file mode 100644 index 0000000..9ed83b6 --- /dev/null +++ b/buch/chapters/40-eigenwerte/beispiele/n.maxima @@ -0,0 +1,20 @@ +/* + * n.maxima + * + * (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule + */ +A: matrix( + [ 1, 9, -4 ], + [ -1, 3, 0 ], + [ -2, 0, 3 ] +); + +p: expand(charpoly(A,x)); +factor(p); + +A.A; +A.A.A; + +A.A - 5*A; + +A.A.A -7*A.A +16 *A; diff --git a/buch/chapters/40-eigenwerte/spektralradius.tex b/buch/chapters/40-eigenwerte/spektralradius.tex index 0c99106..3afac18 100644 --- a/buch/chapters/40-eigenwerte/spektralradius.tex +++ b/buch/chapters/40-eigenwerte/spektralradius.tex @@ -6,19 +6,365 @@ \section{Funktionen einer Matrix \label{buch:section:funktionen-einer-matrix}} \rhead{Funktionen einer Matrix} +Eine zentrale Motivation in der Entwicklung der Eigenwerttheorie +war das Bestreben, Potenzen $A^k$ auch für grosse $k$ effizient +zu berechnen. +Mit der Jordan-Normalform ist dies auch gelungen, wenigstens über +einem Körper, in dem das charakteristische Polynom in Linearfaktoren +zerfällt. +Die Berechnung von Potenzen war aber nur der erste Schritt, das Ziel +in diesem Abschnitt ist, $f(A)$ für eine genügend grosse Klasse von +Funktionen $f$ berechnen zu können. % % Polynom-Funktionen von Matrizen % \subsection{Polynom-Funktionen \label{buch:subsection:polynom-funktionen}} +In diesem Abschnitt ist $B\in M_n(\Bbbk)$ und $\Bbbk'\supset\Bbbk$ ein +Körper, über dem das charakteristische Polynome $\chi_A(x)$ in +Linearfaktoren +\[ +\chi_A(x) += +(\lambda_1-x)^{m_1}(\lambda_2-x)^{m_2}\cdot\ldots\cdot(\lambda_p-x)^{m_p} +\] +zerfällt. + +Für jedes beliebige Polynome $p(X)=\Bbbk[X]$ der Form +\[ +p(X) = a_nX^n + a_{n-1}X^{n-1} + \dots a_1x + a_0 +\] +kann man auch +\[ +p(A) = a_nA^n + a_{n-1}A^{n-1} + \dots a_1A + a_0E +\] +berechnen. +In der Jordan-Normalform können die Potenzen $A^k$ leicht zusammengstellt +werden, sobald man die Potenzen von Jordan-Blöcken berechnet hat. +\begin{satz} +Die $k$-te Potenz von $J_n(\lambda)$ ist die Matrix mit +\begin{equation} +J_n(\lambda)^k += +\begin{pmatrix} +\lambda^k + & \binom{k}{1}\lambda^{k-1} + & \binom{k}{2} \lambda^{k-2} + & \binom{k}{3} \lambda^{k-3} + & \dots + &\binom{k}{n-1}\lambda^{k-n+1} +\\ +0 + & \lambda^k + & \binom{k}{1}\lambda^{k-1} + & \binom{k}{2} \lambda^{k-2} + & \dots + &\binom{k}{n-2}\lambda^{k-n+2} +\\ +0 + & 0 + & \lambda^k + & \binom{k}{1}\lambda^{k-1} + & \dots + &\binom{k}{n-3}\lambda^{k-n+3} +\\ +\vdots &\vdots &\vdots &\vdots &\ddots & \vdots +\\ +0 & 0 & 0 & 0 & \dots & \lambda^k +\end{pmatrix} +\label{buch:eigenwerte:eqn:Jnkpotenz} +\end{equation} +mit den Matrixelementen +\[ +(J_n(\lambda)^k)_{ij} += +\binom{k}{j-i}\lambda^{k-j+i} +\] +Die Binomialkoeffizienten verschwinden für $ji+k$. +\end{satz} + +\begin{proof}[Beweis] +Die Herkunft der Binomialkoeffizienten wird klar, wenn man +\[ +J_n(\lambda) = \lambda E + N_n +\] +schreibt, wobei $N_n$ die Matrix \eqref{buch:eigenwerte:eqn:nnilpotent} ist. +Die Potenzen von $N_n$ haben die Matrix-Elemente +\[ +(N_n^k)_{ij} += +\delta_{i,j-k} += +\begin{cases} +1&\qquad j-i=k\\ +0&\qquad\text{sonst,} +\end{cases} +\] +sie haben also Einsen genau dort, wo in der +\label{buch:eigenwerte:eqn:Jnkpotenz} die Potenz $\lambda^{k}$ steht. +Die $kt$-te Potenz von $J_n(\lambda)$ kann dann mit dem binomischen +Satz berechnet werden: +\[ +J_n(\lambda)^k += +\sum_{l=0}^k \binom{k}{l}\lambda^l N_n^{k-l}, +\] +dies ist genau die Form \eqref{buch:eigenwerte:eqn:Jnkpotenz}. +\end{proof} + +Wir haben bereits gesehen, dass $\chi_A(A)=0$, ersetzt man also das +Polynom $p(X)$ durch $p(X)+\chi_A(X)$, dann ändert sich am Wert +\[ +(p+\chi_A)(A) += +p(A) + \chi_A(A) += +p(A) +\] +nichts. +Man kann also nicht erwarten, dass verschiedene Polynome +$p(X)$ zu verschiedenen Matrizen $p(A)$ führen. +Doch welche Unterschiede zwischen Polynomen wirken sich genau aus? + +\begin{satz} +Für zwei Polynome $p(X)$ und $q(X)$ ist genau dann $p(A)=q(A)$, wenn +das Minimalpolynom von $A$ die Differenz $p-q$ teilt. +\end{satz} + +\begin{proof}[Beweis] +Wenn $p(A)=q(A)$, dann ist $h(X)=p(X)-q(X)$ ein Polynom mit $h(A)=0$, +daher muss $h(X)$ vom Minimalpolynom geteilt werden. +Ist andererseits $p(X)-q(X)=m(X)t(X)$, dann ist +$p(A)-q(A)=m(A)t(A)=0\cdot t(A) = 0$, also $p(A)=q(A)$. +\end{proof} + +Über einem Körper $\Bbbk'\supset\Bbbk$, über dem das charakteristische +Polynom in Linearfaktoren zerfällt, kann man das Minimalpolynom aus +der Jordanschen Normalform ableiten. +Es ist +\[ +m(X) += +(\lambda_1-X)^{q_1} +(\lambda_2-X)^{q_2} +\cdot\ldots +\cdot +(\lambda_p-X)^{q_p}, +\] +wobei $q_i$ die Dimension des grössten Jordan-Blocks ist, der in der +Jordan-Normalform vorkommt. +Zwei Polynome $p_1(X)$ und $p_2(X)$ haben genau dann den gleichen Wert, +wenn die Differenz $p_1(X)-p_2(X)$ genau die Nullstellen +$\lambda_1,\dots,\lambda_p$ mit Vielfachheiten $q_1,\dots,q_p$ hat. + +\begin{beispiel} +Wir betrachten die Matrix +\[ +A += +\begin{pmatrix} + 1& 9& -4\\ + -1& 3& 0\\ + -2& 0& 3 +\end{pmatrix} +\] +mit dem charakteristischen Polynom +\[ +\chi_A(x) += +-x^3+7x^2-16 x+12 += +-(x-3)(x-2)^2. +\] +Daraus kann man bereits ablesen, dass das Minimalpolynom $m(X)$ von $A$ +entweder $(X-2)(X-3)$ oder $(X-2)^2(X-3)$ ist. +Es genügt also nachzuprüfen, ob $p(A)=0$ für das Polynom +$p(X)=(X-2)(X-3) = X^2-5X+6$ ist. +Tatsächlich sind die Potenzen von $A$: +\[ +A^2= +\begin{pmatrix} + 0& 36& -16 \\ + -4& 0& 4 \\ + -8& -18& 17 +\end{pmatrix} +,\qquad +A^3= +\begin{pmatrix} + -4& 108& -48\\ +-12& -36& 28\\ +-24&-126& 83 +\end{pmatrix} +\] +und daraus kann man jetzt $P(A)$ berechnen: +\begin{equation} +p(A) += +\begin{pmatrix} + 0& 36& -16 \\ + -4& 0& 4 \\ + -8& -18& 17 +\end{pmatrix} +-5 +\begin{pmatrix} + 1& 9& -4\\ + -1& 3& 0\\ + -2& 0& 3 +\end{pmatrix} ++ +6 +\begin{pmatrix} +1&0&0\\ +0&1&0\\ +0&0&1 +\end{pmatrix} += +\begin{pmatrix} + 1& -9& 4\\ + 1& -9& 4\\ + 2&-18& 8 +\end{pmatrix} += +\begin{pmatrix}1\\1\\2\end{pmatrix} +\begin{pmatrix}1&-9&4\end{pmatrix} +\label{buch:eigenwerte:eqn:nichtminimalpolynom} +\end{equation} +Also ist tatsächlich $(X-2)^2(X-3)$ das Minimalpolynom. + +Das Quadrat des Polynoms $p(X)$ ist $p(X)^2 = (X-2)^2(X-3)^2$, es hat +das Minimalpolynom als Teiler, also muss $p(A)^2=0$ sein. +Die Gleichung \eqref{buch:eigenwerte:eqn:nichtminimalpolynom} ermöglicht, +das Quaddrat $p(A)^2$ leichter zu berechnen: +\[ +p(A)^2 += +\begin{pmatrix}1\\1\\2\end{pmatrix} +\underbrace{ +\begin{pmatrix}1&-9&4\end{pmatrix} +\begin{pmatrix}1\\1\\2\end{pmatrix} +}_{\displaystyle = 0} +\begin{pmatrix}1&-9&4\end{pmatrix} += +0 +, +\] +wie zu erwarten war. + +Wenn sich zwei Polynome nur um das charakteristische Polynom unterscheiden, +dann haben sie den gleichen Wert auf $A$. +Das Polynom $p_1(X)=X^3$ unterschiedet sich vom Polynom $p_2(X)=7X^2-16X+12$ +um das charakteristische Polynom, welches wir bereits als das Minimalpolynom +von $A$ erkannt haben. +Die dritte Potenz $A^3$ von $A$ muss sich daher auch mit $p_2(X)$ berechnen +lassen: +\[ +7 +\begin{pmatrix} + 0& 36& -16 \\ + -4& 0& 4 \\ + -8& -18& 17 +\end{pmatrix} +-16 +\begin{pmatrix} + 1& 9& -4\\ + -1& 3& 0\\ + -2& 0& 3 +\end{pmatrix} ++12 +\begin{pmatrix} +1&0&0\\ +0&1&0\\ +0&0&1 +\end{pmatrix} += +\begin{pmatrix} + -4& 108& -48\\ +-12& -36& 28\\ +-24&-126& 83 +\end{pmatrix} += +A^3. +\qedhere +\] +\end{beispiel} + +\begin{satz} +Wenn $A$ diagonalisierbar ist über einem geeignet erweiterten Körper $\Bbbk'$, +dann haben zwei Polynome $p(X)$ und $q(X)$ in $\Bbbk[X]$ genau dann +den gleichen Wert auf $A$, also $p(A)=q(A)$, wenn $p(\lambda) = q(\lambda)$ +für alle Eigenwerte $\lambda$ von $A$. +\end{satz} + +Über dem Körper der komplexen Zahlen ist die Bedingung, dass die Differenz +$d(X)=p_1(X)-p_2(X)$ vom Minimalpolynom geteilt werden muss, gleichbedeutend +damit, dass $p_1(X)$ und $p_2(X)$ den gleichen Wert und gleiche Ableitungen +bis zur Ordnung $q_i-1$ haben in allen Eigenwerten $\lambda_i$, wobei +$q_i$ der Exponent von $\lambda_i-X$ im Minimalpolynom von $A$ ist. + +Das Beispiel illustriert auch noch ein weiteres wichtiges Prinzip. +Schreiben wir das Minimalpolynom von $A$ in der Form +\[ +m(X) += +X^k + a_{k-1}X^{k-1} + \dots + a_1X + a_0, +\] +dann kann man wegen $m(A)=0$ die Potenzen $A^i$ mit $i\ge k$ mit der +Rekursionsformel +\[ +A^i += +A^{i-k}A^k += +A^{i-k}(-a_{k-1}A^{k-1}+ \dots + a_1 A + a_0E) +\] +in einer Linearkombination kleinerer Potenzen reduzieren. +Jedes Polynom vom Grad $\ge k$ kann also reduizert werden in +ein Polynom vom Grad $=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} -- cgit v1.2.1