From 1843428795ae9005da7d54cad51450de9b7d298f Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Andreas=20M=C3=BCller?= Date: Thu, 2 Sep 2021 19:50:27 +0200 Subject: Chapter 5, permutations --- buch/chapters/05-zahlen/natuerlich.tex | 18 +++++++ buch/chapters/10-vektorenmatrizen/gruppen.tex | 1 + buch/chapters/10-vektorenmatrizen/linear.tex | 1 + buch/chapters/40-eigenwerte/spektraltheorie.tex | 6 +-- buch/chapters/50-permutationen/chapter.tex | 4 ++ buch/chapters/50-permutationen/determinante.tex | 25 +++++---- buch/chapters/50-permutationen/endlich.tex | 57 ++++++++++++++++----- .../50-permutationen/images/komposition.pdf | Bin 13951 -> 15776 bytes .../50-permutationen/images/komposition.tex | 56 +++++++++++++++----- buch/chapters/50-permutationen/matrizen.tex | 42 +++++++++------ buch/chapters/50-permutationen/transpositionen.tex | 31 +++++++---- 11 files changed, 178 insertions(+), 63 deletions(-) diff --git a/buch/chapters/05-zahlen/natuerlich.tex b/buch/chapters/05-zahlen/natuerlich.tex index 4036327..53e7295 100644 --- a/buch/chapters/05-zahlen/natuerlich.tex +++ b/buch/chapters/05-zahlen/natuerlich.tex @@ -242,6 +242,24 @@ n+1&= n \cup \{n\} = \{0,\dots,n-1\} \cup \{n\} = \{0,1,\dots,n\} \\ &\phantom{n}\vdots \end{align*} +Die Menge $n+1$ besteht also aus den $n+1$ Zahlen von $0$ bis $n$. + +Für spätere Verwendung in Kapitel~\ref{buch:chapter:permutationen} +definieren wir hier auch noch eine weiter Art von Standardteilmengen +von $\mathbb{N}$. + +\begin{definition} +\label{buch:zahlen:def:[n]} +Die Menge $[n]\subset \mathbb{N}$ ist definiert durch +\[ +[n] = \begin{cases} +\{1,2,\dots,n\}&\qquad \text{für $n>0$}\\ +\emptyset&\qquad\text{für $n=0$} +\end{cases} +\] +\end{definition} + +Jede der Mengen $[n]$ hat genau $n$ Elemente: $|[n]|=n$. \subsubsection{Natürliche Zahlen als Äquivalenzklassen} Im vorangegangenen Abschnitt haben wir die natürlichen Zahlen aus diff --git a/buch/chapters/10-vektorenmatrizen/gruppen.tex b/buch/chapters/10-vektorenmatrizen/gruppen.tex index febf726..741a871 100644 --- a/buch/chapters/10-vektorenmatrizen/gruppen.tex +++ b/buch/chapters/10-vektorenmatrizen/gruppen.tex @@ -205,6 +205,7 @@ Für eine Abbildung zwischen Gruppen heisst dies, dass die Verknüpfung, das neutrale Element und die Inverse respektiert werden müssen. \begin{definition} +\label{buch:gruppen:def:homomorphismus} Ein Abbildung $\varphi\colon G\to H$ zwischen Gruppen heisst ein {\em Homomorphismus}, wenn $\varphi(g_1g_2)=\varphi(g_1)\varphi(g_2)$ für alle $g_1,g_2\in G$ gilt. diff --git a/buch/chapters/10-vektorenmatrizen/linear.tex b/buch/chapters/10-vektorenmatrizen/linear.tex index ba89266..70c1f9c 100755 --- a/buch/chapters/10-vektorenmatrizen/linear.tex +++ b/buch/chapters/10-vektorenmatrizen/linear.tex @@ -974,6 +974,7 @@ berechnet werden, wobei die $(n-1)\times(n-1)$-Matrix $A_{i\!j}$ die Matrix $A$ ist, aus der man Zeile $i$ und Spalte $j$ entfernt hat. $A_{i\!j}$ heisst ein {\em Minor} der Matrix $A$. +\label{buch:linear:def:minor} \index{Minor einer Matrix}% \end{enumerate} diff --git a/buch/chapters/40-eigenwerte/spektraltheorie.tex b/buch/chapters/40-eigenwerte/spektraltheorie.tex index 06a063c..db1315a 100644 --- a/buch/chapters/40-eigenwerte/spektraltheorie.tex +++ b/buch/chapters/40-eigenwerte/spektraltheorie.tex @@ -108,9 +108,9 @@ Gleichungssystems finden, man kann aber auch direkt eine Lösung konstruieren. Dazu bildet man erst die Polynome \begin{align*} -l(z) &= (z-z_0)(z-z_1)\dots (z-z_n) \qquad\text{und} +l(z) &= (z-z_0)(z-z_1)\cdots (z-z_n) \qquad\text{und} \\ -l_i(z) &= (z-z_0)\dots \widehat{(z-z_i)}\dots (z-z_n). +l_i(z) &= (z-z_0)\cdots \widehat{(z-z_i)}\cdots (z-z_n). \end{align*} Darin bedeutet der Hut, dass dieser Term weggelassen werden soll. Für $z\ne z_i$ ist $l_i(z)=l(z)/(z-z_i)$. @@ -120,7 +120,7 @@ k_i(z) = \frac{l_i(z)}{l_i(z_i)} = -\frac{(z-z_0)\dots \widehat{(z-z_i)}\dots (z-z_n)}{(z_i-z_0)\dots \widehat{(z_i-z_i)}\dots (z_i-z_n)} +\frac{(z-z_0)\cdots \widehat{(z-z_i)}\cdots (z-z_n)}{(z_i-z_0)\cdots \widehat{(z_i-z_i)}\cdots (z_i-z_n)} \] haben die Eigenschaft $k_i(z_j)=\delta_{i\!j}$. diff --git a/buch/chapters/50-permutationen/chapter.tex b/buch/chapters/50-permutationen/chapter.tex index cf3f2ab..e3b6742 100644 --- a/buch/chapters/50-permutationen/chapter.tex +++ b/buch/chapters/50-permutationen/chapter.tex @@ -8,13 +8,17 @@ \lhead{Permutationen} \rhead{} Die Berechnung der Determinante einer Matrix macht ausgedehnten +\index{Determinante}% Gebrauch von der Tatsache, dass die Vertauschung von zwei Zeilen oder Spalten das Vorzeichen des Wertes der Determinanten dreht. In diesem Kapitel sollen die Permutationen der Zeilen abstrakt +\index{Permutation}% untersucht werden. Wir erhalten so eine abstrakte Permutationsgruppe. +\index{Permutationsgruppe}% Ihre Elemente lassen sich auch durch spezielle Matrizen beschreiben, eine Darstellung dieser Gruppe, die auch unmittelbar zu einer +\index{Darstellung}% Formel für die Determinante einer Matrix führt. \input{chapters/50-permutationen/endlich.tex} diff --git a/buch/chapters/50-permutationen/determinante.tex b/buch/chapters/50-permutationen/determinante.tex index 805235d..b30f9a2 100644 --- a/buch/chapters/50-permutationen/determinante.tex +++ b/buch/chapters/50-permutationen/determinante.tex @@ -17,12 +17,16 @@ Entwicklungssatz \begin{equation} \det(A) = -\sum_{i=1}^n (-1)^{i+j} a_{ij} \cdot \det(A_{ij}) +\sum_{i=1}^n (-1)^{i+j} a_{i\!j} \cdot \det(A_{i\!j}) \label{buch:permutationen:entwicklungssatz} \end{equation} von Laplace für die Determinante. -In den Produkten $a_{ij}\cdot\det(A_{ij})$ enthält -die Untermatrix $A_{ij}$ weder Elemente der Zeile $i$ noch der +\index{Entwicklungssatz}% +\index{Laplace, Entwicklungssatz von}% +Die Matrizen $A_{i\!j}$ sind die Minoren der Matrix $A$ +(siehe auch Seite~\pageref{buch:linear:def:minor}). +In den Produkten $a_{i\!j}\cdot\det(A_{i\!j})$ enthält +die Untermatrix $A_{i\!j}$ weder Elemente der Zeile $i$ noch der Zeile $j$. Die Summanden auf der rechten Seite von \eqref{buch:permutationen:entwicklungssatz} @@ -31,7 +35,7 @@ sind daher Produkte der Form a_{1i_1} a_{2i_2} a_{3i_3} -\dots +\cdots a_{ni_n}, \] in denen nur Faktoren aus verschiedenen Spalten der Matrix $A$ @@ -55,9 +59,10 @@ in der Form = \sum_{\sigma\in S_n} c(\sigma) +\, a_{1\sigma(1)} a_{2\sigma(2)} -\dots +\cdots a_{n\sigma(n)} \label{buch:permutationen:cformel} \end{equation} @@ -73,13 +78,15 @@ also = \sum_{\sigma \in S_n} c(\sigma) +\, (P_\tau)_{1\sigma(1)} (P_\tau)_{2\sigma(2)} -\dots +\cdots (P_\tau)_{n\sigma(n)} = c(\tau) -1\cdot 1\cdot\dots\cdot 1 +\, +1\cdot 1\cdots 1 = c(\tau). \] @@ -96,14 +103,14 @@ Die Determinante einer $n\times n$-Matrix $A$ kann berechnet werden als \operatorname{sgn}(\sigma) a_{1\sigma(1)} a_{2\sigma(2)} -\dots +\cdots a_{n\sigma(n)} = \sum_{\tau\in S_n} \operatorname{sgn}(\tau) a_{\tau(1)1} a_{\tau(2)2} -\dots +\cdots a_{\tau(n)n}. \] Insbesondere folgt auch $\det(A)=\det(A^t)$. diff --git a/buch/chapters/50-permutationen/endlich.tex b/buch/chapters/50-permutationen/endlich.tex index 35284ff..2577b48 100644 --- a/buch/chapters/50-permutationen/endlich.tex +++ b/buch/chapters/50-permutationen/endlich.tex @@ -8,15 +8,24 @@ \rhead{Permutationen} Eine endliche Anzahl $n$ von Objekten können auf $n!$ Arten angeordnet werden. -Als Objektmenge nehmen wir $[n] = \{ 1,\dots,n\}$. +Da es in dieser Diskussion nicht auf die Art der Objekte ankommt, +nehmen wir als Objektmenge die Zahlen $[n] = \{ 1,\dots,n\}$ +(siehe auch Definition~\ref{buch:zahlen:def:[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]$. + +\begin{definition} +\label{buch:permutationen:def:permutation} +Eine {\em Permutation} ist eine umkehrbare Abbildung $[n]\to[n]$. +\index{Permutation} Die Menge $S_n$ aller umkehrbaren Abbildungen $[n]\to[n]$ mit der Verknüpfung von Abbildungen als Operation heisst die die {\em symmetrische Gruppe}. +\index{symmetrische Gruppe}% Die identische Abbildung $\sigma(x)=x$ ist das {\em neutrale Element} der Gruppe $S_n$ und wir auch mit $e$ bezeichnet. +\index{neutrales Element}% +\end{definition} \subsection{Permutationen als $2\times n$-Matrizen} Eine Permutation kann als $2\times n$-Matrix geschrieben werden: @@ -67,24 +76,28 @@ dass die Zahlen in der ersten Zeile ansteigend sind: \subsection{Zyklenzerlegung \label{buch:subsection:zyklenzerlegung}} Eine Permutation $\sigma\in S_n$ kann auch mit sogenanten Zyklenzerlegung +\index{Zyklenzerlegung}% analysiert werden. -Zum Beispiel: -\begin{center} -\includegraphics{chapters/50-permutationen/images/zyklenzerlegung.pdf} -\end{center} \begin{definition} Ein Zyklus $Z$ ist eine unter $\sigma$ invariante Teilmenge von $[n]$ minimaler Grösse. +\index{Zyklus}% +\index{invariante Teilmenge}% +\index{minimale Grösse}% Die Zyklenzerlegung ist eine Zerlegung von $[n]$ in Zyklen \[ [n] = -\cup_{i=1}^k Z_i, +\bigcup_{i=1}^k Z_i, \] wobei jede Menge $Z_i$ ein Zyklus ist. \end{definition} +Zum Beispiel: +\begin{center} +\includegraphics{chapters/50-permutationen/images/zyklenzerlegung.pdf} +\end{center} Der folgende Algorithmus findet die Zyklenzerlegung einer Permutation. \begin{satz} @@ -116,18 +129,21 @@ weiter bei 2. 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$. +Sei also $[n] = Z_1\cup\dots\cup Z_k$ die Zyklenzerlegung von $\sigma$. +Für jedes Element $x\in Z_i$ gilt $\sigma^{|Z_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|). \] +\index{kgV} +\index{kleinstes gemeinsames Vielfaches} \subsection{Konjugierte Elemente in $S_n$} -Zwei Elemente $g_1,g_2\in G$ einer Gruppe heissen konjugiert, wenn +Zwei Elemente $g_1,g_2\in G$ einer Gruppe heissen {\em konjugiert}, wenn +\index{konjugiert} es ein Element $c\in G$ gibt derart, dass $cg_1c^{-1}=g_2$. -Bei Matrizen hat dies bedeutet, dass die beiden Matrizen durch +Bei Matrizen bedeutet dies bedeutet, dass die beiden Matrizen durch Basiswechsel auseinander hervorgehen. Dasselbe lässt sich auch im Kontext der symmetrischen Gruppe sagen. @@ -136,7 +152,18 @@ Es gibt also eine Permutation $\gamma\in S_n$ derart, dass $\sigma_1=\gamma\sigma_2\gamma^{-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}. +\sigma_1^k += +(\gamma\sigma_2\gamma^{-1})^k += +\gamma\sigma_2\underbrace{\gamma^{-1} +\gamma}_{\displaystyle=e}\sigma_2\underbrace{\gamma^{-1} +\gamma}_{\displaystyle=e}\sigma_2\underbrace{\gamma^{-1}\gamma}_{\displaystyle=e} +\cdots +\underbrace{\gamma^{-1} +\gamma}_{\displaystyle=e}\sigma_2\gamma^{-1} += +\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 @@ -156,19 +183,21 @@ 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}$ +Seien $\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 +\index{Jordan-Normalform}% (Abschnitt~\ref{buch:subsection:jordan-normalform}) einer Matrix verglichen werden. Durch einen Basiswechsel, welcher durch eine ``Konjugation'' +\index{Basiswechsel}% 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 +Wenn $\sigma$ die Zyklenzerlegung $Z_1,\dots,Z_k$ hat 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\}, diff --git a/buch/chapters/50-permutationen/images/komposition.pdf b/buch/chapters/50-permutationen/images/komposition.pdf index 9e532bf..3922096 100644 Binary files a/buch/chapters/50-permutationen/images/komposition.pdf and b/buch/chapters/50-permutationen/images/komposition.pdf differ diff --git a/buch/chapters/50-permutationen/images/komposition.tex b/buch/chapters/50-permutationen/images/komposition.tex index ef3ec65..2b73227 100644 --- a/buch/chapters/50-permutationen/images/komposition.tex +++ b/buch/chapters/50-permutationen/images/komposition.tex @@ -10,39 +10,71 @@ \usepackage{pgfplots} \usepackage{csvsimple} \usetikzlibrary{arrows,intersections,math} +\usetikzlibrary{decorations.pathreplacing} \begin{document} \def\skala{1} \begin{tikzpicture}[>=latex,thick,scale=\skala] -\begin{scope}[xshift=-4.5cm] +\begin{scope}[xshift=-4.0cm] + +\def\s{0.527} +\def\o{0.133} + +\def\verbindung#1{ +\fill[color=red!20] ({\o+(#1*\s)},-1.0) rectangle ({\o+(#1*\s)+0.3},0.0); +} + +\verbindung{1} +\verbindung{2} +\verbindung{3} +\verbindung{4} +\verbindung{5} +\verbindung{6} + + \node at (0,0) {$\displaystyle \sigma_1=\begin{pmatrix} 1&2&3&4&5&6\\ 2&1&3&5&6&4 +\end{pmatrix} +%$}; +=\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] + +%\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} + +\draw[decorate,decoration={brace,amplitude=4pt}] +(0,0.4) -- (0,-1.4); + +\begin{scope}[xshift=3.1cm] \node at (0,-0.5) {$\displaystyle +\Rightarrow\quad \sigma_2\sigma_1=\begin{pmatrix} 1&2&3&4&5&6\\ 4&3&5&1&2&6 diff --git a/buch/chapters/50-permutationen/matrizen.tex b/buch/chapters/50-permutationen/matrizen.tex index f7e9e31..037c441 100644 --- a/buch/chapters/50-permutationen/matrizen.tex +++ b/buch/chapters/50-permutationen/matrizen.tex @@ -7,11 +7,12 @@ \label{buch:section:permutationsmatrizen}} \rhead{Permutationsmatrizen} Die Eigenschaft, dass eine Vertauschung das Vorzeichen kehrt, ist -eine wohlebekannte Eigenschaft der Determinanten. +eine wohlbekannte 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. +\index{Determinante}% \subsection{Matrizen} Gegeben sei jetzt eine Permutation $\sigma\in S_n$. @@ -33,7 +34,7 @@ e_n&\mapsto e_{\sigma(n)} 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)}. +(P_\sigma)_{i\!j} = \delta_{j\sigma(i)}. \] \begin{beispiel} @@ -61,27 +62,35 @@ A_\sigma \end{beispiel} \begin{definition} -Eine Permutationsmatrix ist eine Matrix $P\in M_n(\Bbbk)$ +\label{buch:permutationen:def:permutationsmatrix} +\index{Permutationsmatrix}% +Eine {\em Permutationsmatrix} ist eine Matrix $P\in M_n(\Bbbk)$ derart, die in jeder Zeile und Spalte genau eine $1$ enthalten ist, während alle anderen Matrixelemente $0$ sind. \end{definition} Es ist klar, dass aus einer Permutationsmatrix auch die Permutation der Standardbasisvektoren abgelesen werden kann. +\index{Standardbasisvektor}% Die Verknüpfung von Permutationen wird zur Matrixmultiplikation +\index{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}$. +\index{Homomorphismus}% +$S_n \to M_n(\Bbbk^n)$, +es ist +$P_{\sigma_1\sigma_2}=P_{\sigma_1}P_{\sigma_2}$. +$\sigma$ heisst gemäss Definition~\ref{buch:vektorenmatrizen:def:darstellung} +auch Darstellung der Gruppe $S_n$. +\index{Darstellung}% \subsection{Transpositionen} Transpositionen sind Permutationen, die genau zwei Elemente von $[n]$ vertauschen. -Wir ermitteln jetzt die Permutationsmatrix der Transposition $\tau=\tau_{ij}$ +Wir ermitteln jetzt die Permutationsmatrix der Transposition $\tau=\tau_{i\!j}$. +Sie ist \[ -P_{\tau_{ij}} +P_{\tau_{i\!j}} = \begin{pmatrix} 1& & & & & & & & \\ @@ -93,8 +102,7 @@ P_{\tau_{ij}} & & & & & &1& & \\ & & & & & & &\ddots& \\ & & & & & & & &1 -\end{pmatrix} -\qedhere +\end{pmatrix}. \] Die Permutation $\sigma$ mit dem Zyklus $1\to 2\to\dots\to l-1\to l\to 1$ @@ -148,7 +156,7 @@ P_{\tau_{l-1,l}} 0&0&1&0&\dots\\ \vdots&\vdots&\vdots&\vdots&\ddots \end{pmatrix} -\dots +\cdots \\ &= \begin{pmatrix} @@ -159,7 +167,7 @@ P_{\tau_{l-1,l}} \vdots&\vdots&\vdots&\vdots&\ddots \end{pmatrix} \\ -&\vdots\\ +&\quad\vdots\\ &= \begin{pmatrix} 0&0&0&0&\dots&0&1\\ @@ -168,15 +176,17 @@ P_{\tau_{l-1,l}} 0&0&1&0&\dots&0&0\\ \vdots&\vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\ 0&0&0&0&\dots&1&0 -\end{pmatrix} +\end{pmatrix}. \end{align*} \subsection{Determinante und Vorzeichen} Die Transpositionen haben Permutationsmatrizen, die aus der Einheitsmatrix +\index{Einheitsmatrix}% +\index{Determinante}% entstehen, indem genau zwei Zeilen vertauscht werden. Die Determinante einer solchen Permutationsmatrix ist \[ -\det P_{\tau} = - \det E = -1 = \operatorname{sgn}(\tau). +\det P_{\tau} = - \det I = -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, @@ -184,7 +194,7 @@ dass \begin{equation} \det P_{\sigma} = -\det P_{\tau_1} \dots \det P_{\tau_l} +\det P_{\tau_1} \cdots \det P_{\tau_l} = (-1)^l = diff --git a/buch/chapters/50-permutationen/transpositionen.tex b/buch/chapters/50-permutationen/transpositionen.tex index 748b2e9..b8f3d41 100644 --- a/buch/chapters/50-permutationen/transpositionen.tex +++ b/buch/chapters/50-permutationen/transpositionen.tex @@ -12,11 +12,12 @@ 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 +Eine {\em Transposition} $\tau\in S_n$ ist ein Permutation, die genau zwei Elemente vertauscht. -Die Transposition $\tau_{ij}$ ist definiert durch +\index{Transposition}% +Die Transposition $\tau_{i\!j}$ ist definiert durch \[ -\tau_{ij}(x) +\tau_{i\!j}(x) = \begin{cases} i&\qquad x=j\\ @@ -41,7 +42,7 @@ 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}. +\tau_{12} \tau_{23} \tau_{34} \cdots \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 @@ -66,6 +67,8 @@ die Anzahl gerade ist oder nicht, ist sehr wohl eine charkterisierende Eigenschaft einer Permutation. \begin{definition} +\index{Vorzeichen}% +\index{Signum}% 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. @@ -77,16 +80,18 @@ 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, +Die Abbildung $S_n\to\{\pm1\}$, die einer Permutation das Signum zuordnet, +ist ein Homomorphismus von Gruppen +(siehe Definition~\ref{buch:gruppen:def:homomorphismus}), +\index{Homomorphismus}% d.~h. \[ \operatorname{sgn}(\sigma_1\sigma_2) = \operatorname{sgn}(\sigma_1) -\operatorname{sgn}(\sigma_2) +\operatorname{sgn}(\sigma_2). \] -da ganz offensichtlich $\sigma_1\sigma_2$ mit $k_1+k_2$ Transpositionen +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. @@ -101,16 +106,24 @@ A_n \{ \sigma\in S_n\;|\; \operatorname{sgn}(\sigma)=1 \} -\subset S_n. += +\ker \operatorname{sgn} +\subset +S_n. \] +\index{Kern}% +\index{alterniernde Gruppe}% heisst die {\em alternierende Gruppe} der Ordnung $n$ Die Elemente von $A_n$ heissen auch die {\em geraden} Permutationen, +\index{gerade Permutation}% +\index{ungerade Permutation}% 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. +\index{Untergruppe}% Zunächst ist $\operatorname{sgn}(e)=(-1)^0=1$, 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. -- cgit v1.2.1