diff options
Diffstat (limited to 'buch/chapters')
25 files changed, 1005 insertions, 419 deletions
diff --git a/buch/chapters/10-vektorenmatrizen/ringe.tex b/buch/chapters/10-vektorenmatrizen/ringe.tex index 1149e29..433f1e9 100644 --- a/buch/chapters/10-vektorenmatrizen/ringe.tex +++ b/buch/chapters/10-vektorenmatrizen/ringe.tex @@ -57,7 +57,7 @@ in denen die Multiplikation nicht kommutativ ist, die Multiplikation kein neutrales Element hat oder beides. \begin{definition} -\index{Ring mit Eins}% +\index{Ring!mit Eins}% Ein Ring $R$ heisst ein {\em Ring mit Eins}, wenn die Multiplikation ein neutrales Element hat. \index{Ring mit Eins}% diff --git a/buch/chapters/30-endlichekoerper/wurzeln.tex b/buch/chapters/30-endlichekoerper/wurzeln.tex index b066969..e3731d5 100644 --- a/buch/chapters/30-endlichekoerper/wurzeln.tex +++ b/buch/chapters/30-endlichekoerper/wurzeln.tex @@ -164,7 +164,7 @@ X^2+8X+15 X^2+X+1\mod 7. \] Das Polynom $X^2+X+1$ ist daher über $\mathbb{F}_7$ reduzibel und -das Polynom $X^3-1\in\mathbb{F}_7$ zerfällt daher in Linearfaktoren +das Polynom $X^3-1\in\mathbb{F}_7$ zerfällt in Linearfaktoren $X^3-1=(X+6)(X+3)(X+5)$. \end{beispiel} diff --git a/buch/chapters/40-eigenwerte/eigenwerte.tex b/buch/chapters/40-eigenwerte/eigenwerte.tex index 563b58a..1af91f8 100644 --- a/buch/chapters/40-eigenwerte/eigenwerte.tex +++ b/buch/chapters/40-eigenwerte/eigenwerte.tex @@ -19,7 +19,7 @@ Eigenschaften der Matrix $A$ abzuleiten. \label{buch:eigenwerte:def:spektrum} Ein Vektor $v\in V$ heisst {\em Eigenvektor} von $A$ zum {\em Eigenwert} \index{Eigenwert}% -\index{Eigenvekor}% +\index{Eigenvektor}% $\lambda\in\Bbbk$, wenn $v\ne 0$ und $Av=\lambda v$ gilt. Die Menge \[ diff --git a/buch/chapters/40-eigenwerte/grundlagen.tex b/buch/chapters/40-eigenwerte/grundlagen.tex index 91294f1..b41da1d 100644 --- a/buch/chapters/40-eigenwerte/grundlagen.tex +++ b/buch/chapters/40-eigenwerte/grundlagen.tex @@ -27,7 +27,7 @@ bereits eine Normalform für nilpotente Matrizen. \caption{Iterierte Kerne und Bilder einer $3\times 3$-Matrix mit Rang~2. Die abnehmend geschachtelten iterierten Bilder $\mathcal{J}^1(A) \subset \mathcal{J}^2(A)$ -sind links dargestellt, die zunehmen geschachtelten iterierten Kerne +sind links dargestellt, die zunehmend geschachtelten iterierten Kerne $\mathcal{K}^1(A) \subset \mathcal{K}^2(A)$ rechts. \label{buch:eigenwerte:img:kernbild}} \end{figure} @@ -387,7 +387,7 @@ $A^k=0$. \begin{beispiel} Obere (oder untere) Dreiecksmatrizen mit Nullen auf der Diagonalen sind nilpotent. -\index{Dreicksmatrix}% +\index{Dreiecksmatrix}% Wir rechnen dies wie folgt nach. Die Matrix $A$ mit Einträgen $a_{i\!j}$ \[ diff --git a/buch/chapters/60-gruppen/Makefile.inc b/buch/chapters/60-gruppen/Makefile.inc index 8b3d974..fe327a9 100644 --- a/buch/chapters/60-gruppen/Makefile.inc +++ b/buch/chapters/60-gruppen/Makefile.inc @@ -9,4 +9,7 @@ CHAPTERFILES = $(CHAPTERFILES) \ chapters/60-gruppen/lie-gruppen.tex \ chapters/60-gruppen/lie-algebren.tex \ chapters/60-gruppen/homogen.tex \ + chapters/60-gruppen/uebungsaufgaben/6001.tex \ + chapters/60-gruppen/uebungsaufgaben/6002.tex \ + chapters/60-gruppen/uebungsaufgaben/6003.tex \ chapters/60-gruppen/chapter.tex diff --git a/buch/chapters/60-gruppen/chapter.tex b/buch/chapters/60-gruppen/chapter.tex index 3b1abc1..4f2fb5a 100644 --- a/buch/chapters/60-gruppen/chapter.tex +++ b/buch/chapters/60-gruppen/chapter.tex @@ -9,22 +9,40 @@ \rhead{} Matrizen können dazu verwendet werden, Symmetrien von geometrischen oder physikalischen Systemen zu beschreiben. +\index{Symmetrie}% +\index{physikalisches System}% Neben diskreten Symmetrien wie zum Beispiel Spiegelungen gehören dazu +\index{diskrete Symmetrie}% +\index{Symmetrie!diskret}% +\index{Spiegelung}% auch kontinuierliche Symmetrien wie Translationen oder Invarianz einer -phyisikalischen Grösse über die Zeit. +\index{kontinuierliche Symmetrie}% +\index{Symmetrie!kontinuierlich}% +\index{Translation}% +physikalischen Grösse über die Zeit. Solche Symmetrien müssen durch Matrizen beschrieben werden können, die auf stetige oder sogar differenzierbare Art von der Zeit abhängen. Die Menge der Matrizen, die zur Beschreibung solcher Symmetrien benutzt werden, muss also eine zusätzliche Struktur haben, die ermöglicht, sinnvoll über Stetigkeit und Differenzierbarkeit bei Matrizen +\index{Stetigkeit}% +\index{Differenzierbarkeit}% zu sprechen. Die Menge der Matrizen bilden zunächst eine Gruppe, -die zusätzliche differenziarbare Struktur macht daraus +die zusätzliche differenzierbare Struktur macht daraus eine sogenannte Lie-Gruppe. -Die Ableitungen nach einem Parameter liegen in der sogenannten -Lie-Algebra, einer Matrizen-Algebra mit dem antisymmetrischen +\index{Lie-Gruppe}% +Die Ableitungen nach einem Parameter sind nicht mehr Gruppenelemente, +wie man nach allem, was man in der Analysis-Grundvorlesung +gelernt hat, vielleicht erwarten würde. +Sie liegen in der sogenannten Lie-Algebra, +einer Matrizen-Algebra mit dem antisymmetrischen +\index{Lie-Algebra}% +\index{antisymmetrisch}% Lie-Klammer-Produkt $[A,B]=AB-BA$, auch Kommutator genannt. +\index{Lie-Klammer}% +\index{Kommutator}% Lie-Gruppe und Lie-Algebra sind eng miteinander verknüpft, so eng, dass sich die meisten Eigenschaften der Gruppe aus den Eigenschaften der Lie-Gruppe aus der Lie-Algebra ableiten lassen. @@ -43,5 +61,6 @@ Zusammenhangs darzustellen. \begin{uebungsaufgaben} \uebungsaufgabe{6002} \uebungsaufgabe{6001} +\uebungsaufgabe{6003} \end{uebungsaufgaben} diff --git a/buch/chapters/60-gruppen/images/Makefile b/buch/chapters/60-gruppen/images/Makefile index 3ed39e5..294ecfa 100644 --- a/buch/chapters/60-gruppen/images/Makefile +++ b/buch/chapters/60-gruppen/images/Makefile @@ -3,7 +3,8 @@ # # (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule # -all: phasenraum.pdf kartenkreis.pdf karten.pdf sl2.pdf scherungen.pdf +all: phasenraum.pdf kartenkreis.pdf karten.pdf sl2.pdf scherungen.pdf \ + rodriguez.pdf nichtkomm.pdf phasenraum.pdf: phasenraum.tex pdflatex phasenraum.tex @@ -23,3 +24,8 @@ sl2.pdf: sl2.tex scherungen.pdf: scherungen.tex pdflatex scherungen.tex +rodriguez.pdf: rodriguez.tex rodriguez.jpg + pdflatex rodriguez.tex + +nichtkomm.pdf: nichtkomm.tex c60.jpg + pdflatex nichtkomm.tex diff --git a/buch/chapters/60-gruppen/images/c60.jpg b/buch/chapters/60-gruppen/images/c60.jpg Binary files differnew file mode 100644 index 0000000..2bc77e7 --- /dev/null +++ b/buch/chapters/60-gruppen/images/c60.jpg diff --git a/buch/chapters/60-gruppen/images/nichtkomm.pdf b/buch/chapters/60-gruppen/images/nichtkomm.pdf Binary files differnew file mode 100644 index 0000000..8b66ea3 --- /dev/null +++ b/buch/chapters/60-gruppen/images/nichtkomm.pdf diff --git a/buch/chapters/60-gruppen/images/nichtkomm.tex b/buch/chapters/60-gruppen/images/nichtkomm.tex new file mode 100644 index 0000000..53cf87a --- /dev/null +++ b/buch/chapters/60-gruppen/images/nichtkomm.tex @@ -0,0 +1,68 @@ +% +% nichtkomm.tex +% +% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +% +\documentclass[tikz]{standalone} +\usepackage{times} +\usepackage{amsmath} +\usepackage{txfonts} +\usepackage[utf8]{inputenc} +\usepackage{graphics} +\usetikzlibrary{arrows,intersections,math} +\usepackage{ifthen} +\begin{document} + +\definecolor{darkgreen}{rgb}{0,0.6,0} + +\newboolean{showgrid} +\setboolean{showgrid}{false} +\def\breite{7} +\def\hoehe{4} + +\begin{tikzpicture}[>=latex,thick] + +% Povray Bild +\node at (0,0) {\includegraphics[width=14cm]{c60.jpg}}; + +% Gitter +\ifthenelse{\boolean{showgrid}}{ +\draw[step=0.1,line width=0.1pt] (-\breite,-\hoehe) grid (\breite, \hoehe); +\draw[step=0.5,line width=0.4pt] (-\breite,-\hoehe) grid (\breite, \hoehe); +\draw (-\breite,-\hoehe) grid (\breite, \hoehe); +\fill (0,0) circle[radius=0.05]; +}{} + +\coordinate (A) at (-0.3,3); +\coordinate (B) at (-1.1,2); +\coordinate (C) at (-2.1,-1.2); +\draw[->,color=red,line width=1.4pt] + (A) + to[out=-143,in=60] + (B) + to[out=-120,in=80] + (C); +%\fill[color=red] (B) circle[radius=0.08]; +\node[color=red] at (-1.2,1.5) [above left] {$R_{x_1,\alpha}$}; +\coordinate (D) at (0.3,3.2); +\coordinate (E) at (1.8,2.8); +\coordinate (F) at (5.2,-0.3); +\draw[->,color=blue,line width=1.4pt] + (D) + to[out=-10,in=157] + (E) + to[out=-23,in=120] + (F); +%\fill[color=blue] (E) circle[radius=0.08]; +\node[color=blue] at (2.4,2.4) [above right] {$R_{x_2,\beta}$}; +\draw[->,color=darkgreen,line width=1.4pt] + (0.7,-3.1) to[out=1,in=-160] (3.9,-2.6); +\node[color=darkgreen] at (2.5,-3.4) {$R_{x_3,\gamma}$}; + +\node at (6.4,-2.9) {$x_1$}; +\node at (-0.2,3.8) {$x_3$}; + +\end{tikzpicture} + +\end{document} + diff --git a/buch/chapters/60-gruppen/images/rodriguez.jpg b/buch/chapters/60-gruppen/images/rodriguez.jpg Binary files differnew file mode 100644 index 0000000..5c49700 --- /dev/null +++ b/buch/chapters/60-gruppen/images/rodriguez.jpg diff --git a/buch/chapters/60-gruppen/images/rodriguez.pdf b/buch/chapters/60-gruppen/images/rodriguez.pdf Binary files differnew file mode 100644 index 0000000..d947fe1 --- /dev/null +++ b/buch/chapters/60-gruppen/images/rodriguez.pdf diff --git a/buch/chapters/60-gruppen/images/rodriguez.tex b/buch/chapters/60-gruppen/images/rodriguez.tex new file mode 100644 index 0000000..8544739 --- /dev/null +++ b/buch/chapters/60-gruppen/images/rodriguez.tex @@ -0,0 +1,45 @@ +% +% 3dimagetemplate.tex +% +% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +% +\documentclass[tikz]{standalone} +\usepackage{times} +\usepackage{amsmath} +\usepackage{txfonts} +\usepackage[utf8]{inputenc} +\usepackage{graphics} +\usetikzlibrary{arrows,intersections,math} +\usepackage{ifthen} +\begin{document} + +\definecolor{darkgreen}{rgb}{0,0.6,0} + +\newboolean{showgrid} +\setboolean{showgrid}{false} +\def\breite{7} +\def\hoehe{4} + +\begin{tikzpicture}[>=latex,thick] + +% Povray Bild +\node at (0,0) {\includegraphics[width=10cm]{rodriguez.jpg}}; + +% Gitter +\ifthenelse{\boolean{showgrid}}{ +\draw[step=0.1,line width=0.1pt] (-\breite,-\hoehe) grid (\breite, \hoehe); +\draw[step=0.5,line width=0.4pt] (-\breite,-\hoehe) grid (\breite, \hoehe); +\draw (-\breite,-\hoehe) grid (\breite, \hoehe); +\fill (0,0) circle[radius=0.05]; +}{} + +\node[color=blue] at (0.6,3.0) {$\vec{k}\mathstrut$}; +\node[color=red] at (1.8,-1.0) [below right] {$\vec{x}\mathstrut$}; +\node[color=darkgreen] at (-4.5,1.0) [below left] + {$\vec{x}\times\vec{k}\mathstrut$}; +\node[color=yellow] at (1.9,-0.5) [right] {$\vec{x}-(\vec{x}\cdot\vec{k})\vec{k}$}; + +\end{tikzpicture} + +\end{document} + diff --git a/buch/chapters/60-gruppen/lie-algebren.tex b/buch/chapters/60-gruppen/lie-algebren.tex index cee8510..0f6429f 100644 --- a/buch/chapters/60-gruppen/lie-algebren.tex +++ b/buch/chapters/60-gruppen/lie-algebren.tex @@ -8,7 +8,7 @@ \rhead{Lie-Algebren} Im vorangegangenen Abschnitt wurde gezeigt, dass alle beschriebenen Matrizengruppen als Untermannigfaltigkeiten im $n^2$-dimensionalen -Vektorraum $M_n(\mathbb{R}9$ betrachtet werden können. +Vektorraum $M_n(\mathbb{R})$ betrachtet werden können. Die Gruppen haben damit nicht nur die algebraische Struktur einer Matrixgruppe, sie haben auch die geometrische Struktur einer Mannigfaltigkeit. @@ -27,6 +27,7 @@ Insbesondere werden wir sehen, wie die Gruppen $\operatorname{SO}(3)$ und $\operatorname{SU}(2)$ die gleich Lie-Algebra haben und dass die Lie-Algebra von $\operatorname{SO}(3)$ mit dem Vektorprodukt in $\mathbb{R}^3$ übereinstimmt. +\index{Vektorprodukt}% % % Die Lie-Algebra einer Matrizengruppe @@ -78,12 +79,12 @@ I+(B+A)t + \biggl(\frac{B^2}{2!}+BA+\frac{A^2}{2!}\biggr)t^2 +\dots \intertext{% Die beiden Kurven $e^{At}e^{Bt}$ und $e^{Bt}e^{At}$ haben zwar den gleichen Tangentialvektor für $t=0$, sie unterscheiden -sich aber untereinander, und sie unterscheiden sich von der -Einparameteruntergruppe von $A+B$} +sich aber für $t>0$ und sie unterscheiden sich von der +Einparameteruntergruppe} e^{(A+B)t} &= I + (A+B)t + \frac{t^2}{2}(A^2 + AB + BA + B^2) + \ldots -\intertext{Für die Unterschiede finden wir} +\intertext{von $A+B$. Für die Unterschiede finden wir} e^{At}e^{Bt} - e^{(A+B)t} &= \biggl(AB-\frac{AB+BA}2\biggr)t^2 @@ -110,15 +111,19 @@ e^{At}e^{Bt}-e^{Bt}e^{At} = \phantom{-}[A,B]t^2+\ldots \end{align*} -wobei mit $[A,B]=AB-BA$ abgekürzt wird. +wobei $[A,B]=AB-BA$ abgekürzt wird. \begin{definition} \label{buch:gruppen:def:kommutator} -Der Kommutator zweier Matrizen $A,B\in M_n(\mathbb{R})$ ist die Matrix +Der {\em Kommutator} zweier Matrizen $A,B\in M_n(\mathbb{R})$ ist die Matrix $[A,B]=AB-BA$. +\index{Kommutator}% +\index{Lie-Klammer}% \end{definition} Der Kommutator ist bilinear und antisymmetrisch, da +\index{bilinear}% +\index{antisymmetrisch}% \begin{align*} [\lambda A+\mu B,C] &= @@ -139,11 +144,13 @@ AB-BA = -(BA-AB) = -[B,A]. Aus der letzten Bedingung folgt insbesodnere $[A,A]=0$ Der Kommutator $[A,B]$ misst in niedrigster Ordnung den Unterschied -zwischen den $e^{At}$ und $e^{Bt}$. +zwischen den +$ e^{At} e^{Bt} $ +und +$ e^{Bt} e^{At} $. Der Kommutator der Tangentialvektoren $A$ und $B$ bildet also die Nichtkommutativität der Matrizen $e^{At}$ und $e^{Bt}$ ab. - \subsubsection{Die Jacobi-Identität} Der Kommutator hat die folgende zusätzliche algebraische Eigenschaft: \begin{align*} @@ -182,6 +189,7 @@ Identität. \label{buch:gruppen:def:jacobi} Ein bilineares Produkt $[\;,\;]\colon V\times V\to V$ auf dem Vektorraum erfüllt die {\em Jacobi-Identität}, wenn +\index{Jacobi-Identität}% \[ [u,[v,w]] + [v,[w,u]] + [w,[u,v]]=0 \] @@ -199,23 +207,26 @@ Ein Vektorraum $V$ mit einem bilinearen, Produkt \] welches zusätzlich die Jacobi-Identität~\ref{buch:gruppen:def:jacobi} erfüllt, heisst eine {\em Lie-Algebra}. +\index{Lie-Algebra}% \end{definition} Die Lie-Algebra einer Lie-Gruppe $G$ wird mit $LG$ bezeichnet. $LG$ besteht aus den Tangentialvektoren im Punkt $I$. -Die Exponentialabbildung $\exp\colon LG\to G:A\mapsto e^A$ +Die {\em Exponentialabbildung} $\exp\colon LG\to G:A\mapsto e^A$ +\index{Exponentialabbildung}% ist eine differenzierbare Abbildung von $LG$ in die Gruppe $G$. Insbesondere kann die Inverse der Exponentialabbildung als eine Karte in einer Umgebung von $I$ verwendet werden. Für die Lie-Algebren der Matrizengruppen, die früher definiert worden -sind, verwenden wir die als Notationskonvention, dass der Name der +sind, verwenden wir die Notationskonvention, dass der Name der Lie-Algebra der mit kleinen Buchstaben geschrieben Name der Lie-Gruppe ist. Die Lie-Algebra von $\operatorname{SO}(n)$ ist also -$L\operatorname{SO}(n) = \operatorname{os}(n)$, +$L\operatorname{SO}(n) = \operatorname{so}(n)$, +\index{so(n)@$\operatorname{so}(n)$}% die Lie-Algebra von $\operatorname{SL}_n(\mathbb{R})$ ist $L\operatorname{SL}_n(\mathbb{R})=\operatorname{sl}_n(\mathbb{R})$. - +\index{sln(r)@$\operatorname{sl}_n(\mathbb{R})$}% % % Die Lie-Algebra von SO(3) @@ -229,34 +240,126 @@ Solche Matrizen haben die Form \Omega = \begin{pmatrix} - 0 & \omega_3&-\omega_2\\ --\omega_3& 0 & \omega_1\\ - \omega_2&-\omega_1& 0 + 0 &-\omega_3& \omega_2\\ + \omega_3& 0 &-\omega_1\\ +-\omega_2& \omega_1& 0 \end{pmatrix} \] +Die antisymmetrischen Matrizen +\[ +\omega_{23} += +\begin{pmatrix} 0&0&0\\0&0&-1\\0&1&0\end{pmatrix}, +\quad +\omega_{31} += +\begin{pmatrix} 0&0&1\\0&0&0\\-1&0&0\end{pmatrix}, +\quad +\omega_{12} += +\begin{pmatrix} 0&1&0\\-1&0&0\\0&0&0\end{pmatrix} +\] +bilden eine Basis für $\operatorname{so}(3)$, man kann +\[ +\Omega += +\omega_1\omega_{23} ++ +\omega_2\omega_{31} ++ +\omega_3\omega_{12} +\] +schreiben. Der Vektorraum $\operatorname{so}(3)$ ist also dreidimensional. -Die Wirkung von $I+t\Omega$ auf einem Vektor $x$ ist +Die Kommutatoren der Basisvektoren sind +\begin{equation} +\setlength\arraycolsep{4pt} +\begin{aligned} +[\omega_{23},\omega_{31}] +&= +\begin{pmatrix} +0&-1&0\\ +1&0&0\\ +0&0&0 +\end{pmatrix} += +\omega_{12}, +%\\ +& +[\omega_{31},\omega_{12}] +&= +\begin{pmatrix} +0&0&0\\ +0&0&-1\\ +0&1&0 +\end{pmatrix} += +\omega_{23}, +%\\ +& +[\omega_{12},\omega_{23}] +&= +\begin{pmatrix} +0&0&1\\ +0&0&0\\ +-1&0&0 +\end{pmatrix} += +\omega_{31}, +\end{aligned} +\label{buch:gruppen:eqn:so3-kommutatoren} +\end{equation} +wie man durch direkte Rechnung bestätigt. +Diese Regeln stimmen mit den Vektorprodukten der Standardbasisvektoren +in $\mathbb{R}^3$ überein. + +\begin{figure} +\centering +\includegraphics{chapters/60-gruppen/images/nichtkomm.pdf} +\caption{Der Kommutator zweier Drehungen um die $x_1$ und $x_2$ +Achse ist eine Drehung um die $x_3$-Achse. +\label{buch:lie:fig:kommutator}} +\end{figure} +Abbildung~\ref{buch:lie:fig:kommutator} illustriert, wie der +Kommutator die Nichtkommutativität der Gruppe $\operatorname{SO}(3)$ +wiedergibt. +Die Matrix $\omega_{23}$ erzeugt eine Drehung $R_{x_1,\alpha}$ +um die $x_1$-Achse, +die Matrix $\omega_{31}$ eine Drehung $R_{x_2,\beta}$ um die $x_2$ Achse. +Der Kommutator $[\omega_{23},\omega_{31}]=\omega_{12}$ beschreibt in +niedrigster Ordnung den Unterschied, der entsteht, wenn man die +beiden Drehungen in verschiedenen Reihenfolgen ausführt. +Dies ist eine Drehung $R_{x_3,\gamma}$ um die $x_3$-Achse. + +Aus der Rodriguez-Formel~\ref{buch:lie:eqn:rodrigues} wissen wir +bereits, dass die Ableitung der Drehung das Vektorprodukt +$\vec{\omega}\times\vec{x}$ ist. +Dieses kann jedoch auch als +$\Omega\vec{x} = \vec{omega}\times\vec{x}$ +ausgedrückt werden. + +Die Wirkung von $I+t\Omega$ auf einem Vektor $\vec{x}$ ist \[ (I+t\Omega) \begin{pmatrix}x_1\\x_2\\x_3\end{pmatrix} = \begin{pmatrix} - 1 & t\omega_3&-t\omega_2\\ --t\omega_3& 1 & t\omega_1\\ - t\omega_2&-t\omega_1& 1 + 1 &-t\omega_3& t\omega_2\\ + t\omega_3& 1 &-t\omega_1\\ +-t\omega_2& t\omega_1& 1 \end{pmatrix} \begin{pmatrix}x_1\\x_2\\x_3\end{pmatrix} = \begin{pmatrix} -x_1-t(-\omega_3x_2+\omega_2x_3)\\ -x_2-t( \omega_3x_1-\omega_1x_3)\\ -x_3-t(-\omega_2x_1+\omega_1x_2) +x_1+t(-\omega_3x_2+\omega_2x_3)\\ +x_2+t( \omega_3x_1-\omega_1x_3)\\ +x_3+t(-\omega_2x_1+\omega_1x_2) \end{pmatrix} = -x- t\begin{pmatrix}\omega_1\\\omega_2\\\omega_3\end{pmatrix}\times x +\vec{x}+ t\begin{pmatrix}\omega_1\\\omega_2\\\omega_3\end{pmatrix}\times x = -x+ tx\times \omega. +\vec{x}+ t\vec{\omega}\times \vec{x}. \] Die Matrix $\Omega$ ist als die infinitesimale Version einer Drehung um die Achse $\omega$. @@ -271,9 +374,9 @@ mit Hilfe der Abbildung \begin{pmatrix}v_1\\v_2\\v_3\end{pmatrix} \mapsto \begin{pmatrix} - 0 & v_3&-v_1\\ --v_3& 0 & v_2\\ - v_1&-v_2& 0 + 0 &-v_3& v_2\\ + v_3& 0 &-v_1\\ +-v_2& v_1& 0 \end{pmatrix}. \] Der Kommutator von zwei so aus Vektoren $\vec u$ und $\vec v$ @@ -285,56 +388,56 @@ UV-VU \\ &= \begin{pmatrix} - 0 & u_3&-u_1\\ --u_3& 0 & u_2\\ - u_1&-u_2& 0 + 0 &-u_3& u_2\\ + u_3& 0 &-u_1\\ +-u_2& u_1& 0 \end{pmatrix} \begin{pmatrix} - 0 & v_3&-v_1\\ --v_3& 0 & v_2\\ - v_1&-v_2& 0 + 0 &-v_3& v_2\\ + v_3& 0 &-v_1\\ +-v_2& v_1& 0 \end{pmatrix} - \begin{pmatrix} - 0 & v_3&-v_1\\ --v_3& 0 & v_2\\ - v_1&-v_2& 0 + 0 &-v_3& v_2\\ + v_3& 0 &-v_1\\ +-v_2& v_1& 0 \end{pmatrix} \begin{pmatrix} - 0 & u_3&-u_1\\ --u_3& 0 & u_2\\ - u_1&-u_2& 0 + 0 &-u_3& u_2\\ + u_3& 0 &-u_1\\ +-u_2& u_1& 0 \end{pmatrix} \\ &= \begin{pmatrix} -u_3v_3+u_1v_1 - u_3v_3 - u_1v_1 - & u_1v_2 - u_2v_1 - & u_3v_2 - u_2v_3 -\\ -u_2v_1 - u_1v_2 - & -u_3v_3-u_2v_2 + u_3v_3+u_2v_2 +-u_3v_3-u_2v_2 + u_3v_3 + u_2v_2 + & u_2v_1 - u_1v_2 & u_3v_1 - u_1v_3 \\ -u_2v_3 - u_3v_2 - & u_1v_3 - u_3v_1 - &-u_1v_1-u_2v_2 u_1v_1+u_2v_2 +u_1v_2 - u_2v_1 + & -u_3v_3-u_1v_1 + u_3v_3+u_1v_1 + & u_3v_2 - u_2v_3 +\\ +u_1v_3 - u_3v_1 + & u_2v_3 - u_3v_2 + &-u_2v_2-u_1v_1+ u_2v_2+u_1v_1 \end{pmatrix} \\ &= \begin{pmatrix} 0 - & u_1v_2 - u_2v_1 - &-(u_2v_3-u_3v_2) + &-(u_1v_2 - u_2v_1) + &u_3v_1-u_1v_3 \\ --( u_1v_2 - u_2v_1) +u_1v_2 - u_2v_1 & 0 - & u_3v_1 - u_1v_3 + &-(u_2v_3 - u_3v_2) \\ -u_2v_3 - u_3v_2 - &-( u_3v_1 - u_1v_3) +-(u_3v_1 - u_1v_3) + & u_3v_2 - u_2v_3 & 0 -\end{pmatrix} +\end{pmatrix}. \end{align*} Die Matrix $[U,V]$ gehört zum Vektor $\vec u\times\vec v$. Damit können wir aus der Jacobi-Identität jetzt folgern, dass @@ -349,10 +452,10 @@ Damit können wir aus der Jacobi-Identität jetzt folgern, dass für drei beliebige Vektoren $\vec u$, $\vec v$ und $\vec w$ ist. Dies bedeutet, dass der dreidimensionale Vektorraum $\mathbb R^3$ mit dem Vektorprodukt zu einer Lie-Algebra wird. -In der Tat verwenden einige Bücher statt der vertrauten Notation +In der Tat verwenden einige Lehrbücher statt der vertrauten Notation $\vec u\times \vec v$ für das Vektorprodukt die aus der Theorie der Lie-Algebren entlehnte Notation $[\vec u,\vec v]$, zum Beispiel -das Lehrbuch der Theoretischen Physik \cite{skript:landaulifschitz1} +auch das Lehrbuch der Theoretischen Physik \cite{skript:landaulifschitz1} von Landau und Lifschitz. Die Lie-Algebren sind vollständig klassifiziert worden, es gibt @@ -361,56 +464,6 @@ Unser dreidimensionaler Raum ist also auch in dieser Hinsicht speziell: es ist der kleinste Vektorraum, in dem eine nichttriviale Lie-Algebra-Struktur möglich ist. -Die antisymmetrischen Matrizen -\[ -\omega_{23} -= -\begin{pmatrix} 0&1&0\\-1&0&0\\0&0&0\end{pmatrix} -\quad -\omega_{31} -= -\begin{pmatrix} 0&0&-1\\0&0&0\\1&0&0\end{pmatrix} -\quad -\omega_{12} -= -\begin{pmatrix} 0&0&0\\0&0&1\\0&-1&0\end{pmatrix} -\] -haben die Kommutatoren -\begin{equation} -\begin{aligned} -[\omega_{23},\omega_{31}] -&= -\begin{pmatrix} -0&0&0\\ -0&0&1\\ -0&-1&0 -\end{pmatrix} -= -\omega_{12} -\\ -[\omega_{31},\omega_{12}] -&= -\begin{pmatrix} -0&1&0\\ --1&0&0\\ -0&0&0 -\end{pmatrix} -= -\omega_{23} -\\ -[\omega_{12},\omega_{23}] -&= -\begin{pmatrix} -0&0&-1\\ -0&0&0\\ -1&0&0 -\end{pmatrix} -= -\omega_{31} -\end{aligned} -\label{buch:gruppen:eqn:so3-kommutatoren} -\end{equation} - \subsection{Die Lie-Algebra von $\operatorname{SL}_n(\mathbb{R})$} Die Lie-Algebra von $\operatorname{SL}_n(\mathbb{R})$ besteht aus den spurlosen Matrizen in $M_n(\mathbb{R})$. @@ -448,13 +501,16 @@ A\in M_n(\mathbb{C} AA^*=I \} \] +\index{unitäre Gruppe}% +\index{Gruppe, unitär}% +\index{U(n)@$\operatorname{U}(n)$}% heisst die unitäre Gruppe, sie besteht aus den Matrizen, die das sesquilineare Standardskalarprodukt auf dem komplexen Vektorraum $\mathbb{C}^n$ invariant lassen. Sei eine $\gamma(t)$ ein differenzierbare Kurve in $\operatorname{U}(n)$ derart, dass $\gamma(0)=I$. Die Ableitung der Identität $AA^*=I$ führt dann auf -\begin{align*} +\begin{equation*} 0 = \frac{d}{dt} @@ -469,14 +525,17 @@ Die Ableitung der Identität $AA^*=I$ führt dann auf + \dot{\gamma}(0)^* \quad\Rightarrow\quad -\dot{\gamma}(0)&=-\dot{\gamma}(0)^*. -A&=-A^* -\end{align*} +\dot{\gamma}(0)=-\dot{\gamma}(0)^* +\quad\Rightarrow\quad +A=-A^* +\end{equation*} Die Lie-Algebra $\operatorname{u}(n)$ besteht daher aus den antihermiteschen Matrizen. +\index{u(n)@$\operatorname{u}(n)$}% Wir sollten noch verifizieren, dass der Kommutator zweier antihermiteschen Matrizen wieder anithermitesch ist: +\index{antihermitesch}% \begin{align*} [A,B]^* &= @@ -489,7 +548,7 @@ BA - AB -[B,A]. \end{align*} -Eine antihermitesche Matrix erfüllt $a_{ij}=-\overline{a}_{ji}$, +Eine antihermitesche Matrix erfüllt $a_{i\!j}=-\overline{a}_{ji}$, für die Diagonalelemente folgt daher $a_{ii} = -\overline{a}_{ii}$ oder $\overline{a}_{ii}=-a_{ii}$. Der Realteil von $a_{ii}$ ist @@ -510,6 +569,7 @@ imaginär. \subsection{Die Lie-Algebra von $\operatorname{SU}(2)$} Die Lie-Algebra $\operatorname{su}(n)$ besteht aus den spurlosen antihermiteschen Matrizen. +\index{su(n)@$\operatorname{su}(n)$}% Sie erfüllen daher die folgenden Bedingungen: \[ A=\begin{pmatrix}a&b\\c&d\end{pmatrix} @@ -557,6 +617,7 @@ iu\underbrace{\begin{pmatrix}0&-i\\i&0\end{pmatrix}}_{\displaystyle=\sigma_2} is\underbrace{\begin{pmatrix}1&0\\0&-1\end{pmatrix}}_{\displaystyle=\sigma_3} \end{align*} Diese Matrizen heissen die {\em Pauli-Matrizen}, sie haben die Kommutatoren +\index{Pauli-Matriizen}% \begin{align*} [\sigma_1,\sigma_2] &= @@ -623,7 +684,7 @@ Die Matrizen $-\frac12i\sigma_j$ haben die Kommutatorprodukte = -{\textstyle\frac14}\cdot 2i\sigma_2 = --{\textstyle\frac12}i\sigma_2 +-{\textstyle\frac12}i\sigma_2. \end{align*} Die lineare Abbildung, die \begin{align*} @@ -631,7 +692,7 @@ Die lineare Abbildung, die \omega_{31}&\mapsto -{\textstyle\frac12}i\sigma_2\\ \omega_{12}&\mapsto -{\textstyle\frac12}i\sigma_3 \end{align*} -abbildet ist daher ein Isomorphismus der Lie-Algebra $\operatorname{so}(3)$ +abbildet, ist daher ein Isomorphismus der Lie-Algebra $\operatorname{so}(3)$ auf die Lie-Algebra $\operatorname{su}(2)$. Die Lie-Gruppen $\operatorname{SO}(3)$ und $\operatorname{SU}(2)$ haben also die gleiche Lie-Algebra. diff --git a/buch/chapters/60-gruppen/lie-gruppen.tex b/buch/chapters/60-gruppen/lie-gruppen.tex index e92c254..94df38e 100644 --- a/buch/chapters/60-gruppen/lie-gruppen.tex +++ b/buch/chapters/60-gruppen/lie-gruppen.tex @@ -16,11 +16,13 @@ Die Gruppe \] besteht aus den Matrizen, deren Determinante nicht $0$ ist. Da die Menge der Matrizen mit $\det A=0$ eine abgeschlossene Menge -in $M_n(\mathbb{R}) \simeq \mathbb{R}^{n^2}$ ist, ist +in $M_n(\mathbb{R}) \cong \mathbb{R}^{n^2}$ ist, ist $\operatorname{GL}_n(\mathbb{R})$ eine offene Teilmenge in $\mathbb{R}^{n^2}$, sie besitzt also automatisch die Struktur einer $n^2$-Mannigfaltigkeit. -Dies gilt jedoch auch für alle anderen Matrizengruppen, die in diesem -Abschnitt genauer untersucht werden sollen. +Doch auch alle anderen Matrizengruppen, +die in diesem Abschnitt genauer untersucht werden sollen, +stellens ich als Untermannigfaltigkeiten von +$\operatorname{GL}_n(\mathbb{R})$ heraus. \subsection{Mannigfaltigkeitsstruktur der Matrizengruppen \label{buch:subsection:mannigfaltigkeitsstruktur-der-matrizengruppen}} @@ -74,8 +76,9 @@ Die Abbildung $l_{g_1^{-1}g_2}$ ist aber nur die Multiplikation mit einer Matrix, also eine lineare Abbildung, so dass der Kartenwechsel nichts anderes ist als die Darstellung der Matrix der Linksmultiplikation $l_{g_1^{-1}g_2}$ im Koordinatensystem der Karte $U_e$ ist. -Differenzierbarkeit der Kartenwechsel ist damit sichergestellt, -die Matrizengruppen sind automatisch differenzierbare Mannigfaltigkeiten. +Differenzierbarkeit der Kartenwechsel ist damit sichergestellt. +Somit sind +die Matrizengruppen automatisch differenzierbare Mannigfaltigkeiten. Die Konstruktion aller Karten aus einer einzigen Karte für eine Umgebung des neutralen Elements zeigt auch, dass es für die Matrizengruppen @@ -115,7 +118,7 @@ enthalten. Diffferenzierbare Kurven $\gamma(t)$ in $\operatorname{GL}_n(\mathbb{R})$ haben daher in jedem Punkt Tangentialvektoren, die als Matrizen in $M_n(\mathbb{R})$ betrachtet werden können. -Wenn $\gamma(t)$ die Matrixelemente $\gamma_{ij}(t)$ hat, dann ist der +Wenn $\gamma(t)$ die Matrixelemente $\gamma_{i\!j}(t)$ hat, dann ist der Tangentialvektor im Punkt $\gamma(t)$ durch \[ \frac{d}{dt} @@ -152,7 +155,8 @@ Eine solche Kurve muss die Differentialgleichung erfüllen, wobei $A\in M_n(\mathbb{R})$ der gegebene Tangentialvektor in $e=I$ ist. -Die Matrixexponentialfunktion +Die {\em Matrixexponentialfunktion} +\index{Matrixexponentialfunktion}% \[ e^{At} = @@ -183,49 +187,53 @@ beschrieben werden kann. $\operatorname{SO}(2)\subset \operatorname{GL}_2(\mathbb{R})$} Drehungen der Ebene können in einer orthonormierten Basis durch Matrizen der Form -\[ -D_{\alpha} +\begin{equation} +R_{\alpha} = \begin{pmatrix} \cos\alpha&-\sin\alpha\\ \sin\alpha& \cos\alpha \end{pmatrix} -\] +\label{buch:lie:eqn:ralphadefinition} +\end{equation} dargestellt werden. Wir bezeichnen die Menge der Drehmatrizen in der Ebene mit $\operatorname{SO}(2)\subset\operatorname{GL}_2(\mathbb{R})$. Die Abbildung \[ -D_{\bullet} +R_{\bullet} \colon \mathbb{R}\to \operatorname{SO}(2) : -\alpha \mapsto D_{\alpha} +\alpha \mapsto R_{\alpha} \] hat die Eigenschaften -\begin{align*} -D_{\alpha+\beta}&= D_{\alpha}D_{\beta} +\begin{equation} +\begin{aligned} +R_{\alpha+\beta}&= R_{\alpha}R_{\beta} \\ -D_0&=I +R_0&=I \\ -D_{2k\pi}&=I\qquad \forall k\in\mathbb{Z}. -\end{align*} -Daraus folgt zum Beispiel, dass $D_{\bullet}$ eine $2\pi$-periodische +R_{2k\pi}&=I\qquad \forall k\in\mathbb{Z}. +\end{aligned} +\label{buch:lie:so2matrizen} +\end{equation} +Daraus folgt zum Beispiel, dass $R_{\bullet}$ eine $2\pi$-periodische Funktion ist. -$D_{\bullet}$ bildet die Menge der Winkel $[0,2\pi)$ bijektiv auf +$R_{\bullet}$ bildet die Menge der Winkel $[0,2\pi)$ bijektiv auf die Menge der Drehmatrizen in der Ebene ab. Für jedes Intervall $(a,b)\subset\mathbb{R}$ mit Länge -$b-a < 2\pi$ ist die Abbildung $\alpha\mapsto D_{\alpha}$ umkehrbar, +$b-a < 2\pi$ ist die Abbildung $\alpha\mapsto R_{\alpha}$ umkehrbar, die Umkehrung kann als Karte verwendet werden. Zwei verschiedene Karten $\alpha_1\colon U_1\to\mathbb{R}$ und $\alpha_2\colon U_2\to\mathbb{R}$ bilden die Elemente $g\in U_1\cap U_2$ in Winkel $\alpha_1(g)$ und $\alpha_2(g)$ ab, für die -$D_{\alpha_1(g)}=D_{\alpha_2(g)}$ gilt. +$R_{\alpha_1(g)}=R_{\alpha_2(g)}$ gilt. Dies ist gleichbedeutend damit, dass $\alpha_1(g)=\alpha_2(g)+2\pi k$ mit $k\in \mathbb{Z}$. In einem Intervall in $U_1\cap U_2$ muss $k$ konstant sein. -Die Kartenwechselabblidung ist also nur die Addition eines Vielfachen +Die Kartenwechselabbildung ist also nur die Addition eines Vielfachen von $2\pi$, mit der identischen Abbildung als Ableitung. Diese Karten führen also auf besonders einfache Kartenwechselabbildungen. @@ -239,22 +247,27 @@ Die Zahlen der Form $e^{i\alpha}$ haben den Betrag $1$ und die Abbildung f\colon \mathbb{R}\to \mathbb{C}:\alpha \mapsto e^{i\alpha} \] hat die Eigenschaften -\begin{align*} +\begin{equation} +\begin{aligned} f(\alpha+\beta) &= f(\alpha)f(\beta) \\ f(0)&=1 \\ f(2\pi k)&=1\qquad\forall k\in\mathbb{Z}, -\end{align*} -die zu den Eigenschaften der Abbildung $\alpha\mapsto D_{\alpha}$ +\end{aligned} +\label{buch:lie:so2komplex} +\end{equation} +die zu den Eigenschaften +\eqref{buch:lie:so2matrizen} der Abbildung $\alpha\mapsto R_{\alpha}$ analog sind. Jede komplexe Zahl $z$ vom Betrag $1$ kann geschrieben werden in der Form -$z=e^{i\alpha}$, die Abbildung $f$ ist also eine Parametrisierung des +$z=e^{i\alpha}$. +Die Abbildung $f$ ist also eine Parametrisierung des Einheitskreises in der Ebene. Wir bezeichen $S^1=\{z\in\mathbb{C}\;|\; |z|=1\}$ die komplexen Zahlen vom Betrag $1$. -$S^1$ ist eine Gruppe bezüglich der Multiplikation, da für jede Zahl +$S^1$ ist eine Gruppe bezüglich der Multiplikation, da für alle Zahlen $z,w\in S^1$ gilt $|z^{-1}|=1$ und $|zw|=1$ und damit $z^{-1}\in S^1$ und $zw\in S^1$. @@ -266,32 +279,32 @@ Damit kann man jetzt die Abbildung \colon S^1\to \operatorname{SO}(2) : -z\mapsto D_{\alpha(z)} +z\mapsto R_{\alpha(z)} \] konstruieren. -Da $D_{\alpha}$ $2\pi$-periodisch ist, geben um Vielfache +Da $R_{\alpha}$ $2\pi$-periodisch ist, geben um Vielfache von $2\pi$ verschiedene Wahlen von $\alpha(z)$ die gleiche -Matrix $D_{\alpha(z)}$, die Abbildung $\varphi$ ist daher +Matrix $R_{\alpha(z)}$, die Abbildung $\varphi$ ist daher wohldefiniert. $\varphi$ erfüllt ausserdem die Bedingungen \begin{align*} \varphi(z_1z_2) &= -D_{\alpha(z_1z_2)} +R_{\alpha(z_1z_2)} = -D_{\alpha(z_1)+\alpha(z_2)} +R_{\alpha(z_1)+\alpha(z_2)} = -D_{\alpha(z_1)}D_{\alpha(z_2)} +R_{\alpha(z_1)}R_{\alpha(z_2)} = -\varphi(z_1)\varphi(z_2) +\varphi(z_1)\varphi(z_2), \\ \varphi(1) &= -D_{\alpha(1)} +R_{\alpha(1)} = -D_0 +R_0 = -I +I. \end{align*} Die Abbildung $\varphi$ ist ein Homomorphismus der Gruppe $S^1$ in die Gruppe $\operatorname{SO}(2)$. @@ -301,7 +314,7 @@ in der komplexen Ebene identifiziert werden. \subsubsection{Tangentialvektoren von $\operatorname{SO}(2)$} Da die Gruppe $\operatorname{SO}(2)$ eine eindimensionale Gruppe ist, kann jede Kurve $\gamma(t)$ durch den Drehwinkel $\alpha(t)$ -mit $\gamma(t) = D_{\alpha(t)}$ beschrieben werden. +mit $\gamma(t) = R_{\alpha(t)}$ beschrieben werden. Die Ableitung in $M_2(\mathbb{R})$ ist \begin{align*} \frac{d}{dt} \gamma(t) @@ -334,24 +347,27 @@ Die Ableitung in $M_2(\mathbb{R})$ ist \cdot \dot{\alpha}(t) = -D_{\alpha(t)}J\cdot\dot{\alpha}(t). +R_{\alpha(t)}J\cdot\dot{\alpha}(t). \end{align*} -Alle Tangentialvektoren von $\operatorname{SO}(2)$ im Punkt $D_\alpha$ -entstehen aus $J$ durch Drehung mit der Matrix $D_\alpha$ und Skalierung -mit $\dot{\alpha}(t)$. +Alle Tangentialvektoren von $\operatorname{SO}(2)$ im Punkt $R_\alpha$ +entstehen aus $J$ durch Drehung mit der Matrix $R_\alpha$ und Skalierung +mit der Winkelgeschwindigkeit $\dot{\alpha}(t)$. +\index{Winkelgeschwindigkeit}% % % Isometrien von R^n % \subsection{Isometrien von $\mathbb{R}^n$ \label{buch:gruppen:isometrien}} +Isometrien von $\mathbb{R}^n$ führen automatisch auf eine interessante +Lie-Gruppe. \subsubsection{Skalarprodukt} Lineare Abbildungen des Raumes $\mathbb{R}^n$ können durch $n\times n$-Matrizen beschrieben werden. Die Matrizen, die das Standardskalarprodukt $\mathbb{R}^n$ erhalten, bilden eine Gruppe, die in diesem Abschnitt genauer untersucht werden soll. -Eine Matrix $A\in M_{n}(\mathbb{R})$ ändert das Skalarprodukt, wenn +Eine Matrix $A\in M_{n}(\mathbb{R})$ ändert das Skalarprodukt nicht, wenn für jedes beliebige Paar $x,y$ von Vektoren gilt $\langle Ax,Ay\rangle = \langle x,y\rangle$. Das Standardskalarprodukt kann mit dem Matrixprodukt ausgedrückt werden: @@ -372,17 +388,20 @@ Mit dem Skalarprodukt kann man auch die Matrixelemente einer Matrix einer Abbildung $f$ in der Standardbasis bestimmen. Das Skalarprodukt $\langle e_i, v\rangle$ ist die Länge der Projektion des Vektors $v$ auf die Richtung $e_i$. -Die Komponenten von $Ae_j$ sind daher $a_{ij}=\langle e_i,f(e_j)\rangle$. -Die Matrix $A$ der Abbildung $f$ hat also die Matrixelemente -$a_{ij}=e_i^tAe_j$. +Die Komponenten von $Ae_j$ sind daher $a_{i\!j}=\langle e_i,f(e_j)\rangle$. +Die Matrix $A$ der Abbildung $f$ hat folglich die Matrixelemente +$a_{i\!j}=e_i^tAe_j$. \subsubsection{Die orthogonale Gruppe $\operatorname{O}(n)$} Die Matrixelemente von $A^tA$ sind -$\langle A^tAe_i, e_j\rangle =\langle e_i,e_j\rangle = \delta_{ij}$ -sind diejenigen der Einheitsmatrix, -die Matrix $A$ erfüllt $AA^t=I$ oder $A^{-1}=A^t$. +$\langle A^tAe_i, e_j\rangle =\langle e_i,e_j\rangle = \delta_{i\!j}$ +also die der Einheitsmatrix. +Die Matrix $A$ erfüllt $AA^t=I$ oder $A^{-1}=A^t$. Dies sind die {\em orthogonalen} Matrizen. -Die Menge $\operatorname{O}(n)$ der isometrischen Abbildungen besteht +\index{orthogonale Matrix}% +Die Menge $\operatorname{O}(n)$ der isometrischen Abbildungen +\index{O(n)@$\operatorname{O}(n)$}% +von $\mathbb{R}^n$ besteht daher aus den Matrizen \[ \operatorname{O}(n) @@ -401,7 +420,7 @@ n^2 - \frac{n(n+1)}{2} = \frac{n(n-1)}2. \] -Im Spezialfall $n=2$ ist die Gruppe $O(2)$ eindimensional. +Im Spezialfall $n=2$ ist die Gruppe $\operatorname{O}(2)$ eindimensional. \subsubsection{Tangentialvektoren} Die orthogonalen Matrizen bilden eine abgeschlossene Untermannigfaltigkeit @@ -440,16 +459,17 @@ A^t&=-A \] Die Tangentialvektoren von $\operatorname{O}(n)$ sind also genau die antisymmetrischen Matrizen. +\index{antisymmetrisch}% Für $n=2$ sind alle antisymmetrischen Matrizen Vielfache der Matrix $J$, wie in Abschnitt~\ref{buch:gruppen:drehungen2d} gezeigt wurde. -Für jedes Paar $i<j$ ist die Matrix $A_{ij}$ mit den Matrixelementen -$(A_{ij})_{ij}=-1$ und $(A_{ij})_{ji}=1$ +Für jedes Paar $i<j$ ist die Matrix $A_{i\!j}$ mit den Matrixelementen +$(A_{i\!j})_{i\!j}=-1$ und $(A_{i\!j})_{ji}=1$ antisymmetrisch. Für $n=2$ ist $A_{12}=J$. -Die $n(n-1)/2$ Matrizen $A_{ij}$ bilden eine Basis des +Die $n(n-1)/2$ Matrizen $A_{i\!j}$ bilden eine Basis des $n(n-1)/2$-dimensionale Tangentialraumes von $\operatorname{O}(n)$. Tangentialvektoren in einem anderen Punkt $g\in\operatorname{O}(n)$ @@ -464,6 +484,7 @@ Wegen $\det (AA^t)=\det A\det A^t = (\det A)^2=1$ kann die Determinante einer orthogonalen Matrix nur $\pm 1$ sein. Orientierungserhaltende Isometrien haben Determinante $1$. +\begin{definition} Die Gruppe \[ \operatorname{SO}(n) @@ -471,7 +492,13 @@ Die Gruppe \{A\in\operatorname{O}(n)\;|\; \det A=1\} \] heisst die {\em spezielle orthogonale Gruppe}. -Die Dimension der Gruppe $\operatorname{O}(n)$ ist $n(n-1)/2$. +\index{spezielle orthogonale Gruppe}% +\index{orthogonale Gruppe, speziell}% +\index{Gruppe, spezielle orthogonale}% +\index{SO(n)@$\operatorname{SO}(n)$}% +\end{definition} + +%Die Dimension der Gruppe $\operatorname{SO}(n)$ ist $n(n-1)/2$. \subsubsection{Die Gruppe $\operatorname{SO}(3)$} Die Gruppe $\operatorname{SO}(3)$ der Drehungen des dreidimensionalen @@ -485,7 +512,7 @@ Der Drehwinkel ist der dritte Parameter. Drehungen mit kleinen Drehwinkeln können zusammengesetzt werden aus den Matrizen \begin{align*} -D_{x,\alpha} +R_{x,\alpha} &= \begin{pmatrix} 1&0&0\\ @@ -493,7 +520,7 @@ D_{x,\alpha} 0&\sin\alpha& \cos\alpha \end{pmatrix}, & -D_{y,\beta} +R_{y,\beta} &= \begin{pmatrix} \cos\beta&0&\sin\beta\\ @@ -501,7 +528,7 @@ D_{y,\beta} -\sin\beta&0&\cos\beta \end{pmatrix}, & -D_{z,\gamma} +R_{z,\gamma} &= \begin{pmatrix} \cos\gamma&-\sin\gamma&0\\ @@ -524,16 +551,73 @@ Auch die Winkel $\alpha$, $\beta$ und $\gamma$ können als die drei Koordinaten der Mannigkfaltigkeit $\operatorname{SO}(3)$ angesehen werden. +\begin{figure} +\centering +\includegraphics{chapters/60-gruppen/images/rodriguez.pdf} +\caption{Herleitung der Rodrigues-Formel~\eqref{buch:lie:eqn:rodrigues} +für die Beschreibung einer +Drehung mit Drehachse $\vec{k}$. +\label{buch:lie:fig:rodrigues}} +\end{figure} +Die Drehung des Vektors $\vec{x}$ um die Achse mit Richtung $\vec{k}$, +$|\vec{k}|=1$, kann man mit dem Vektorprodukt und dem Skalarprodukt +beschreiben. +Die Vektoren $\vec{x}-(\vec{x}\cdot\vec{k})\vec{k}$, $-\vec{x}\times\vec{k}$ +und $\vec{k}$ bilden ein Rechtssystem im Punkt $\vec{x}$, dessen zweite +Achse tangential an die Bahn von $\vec{x}$ unter der Drehung ist. + +Die Komponente $(\vec{k}\cdot\vec{x})\vec{k}$ parallel zu $\vec{k}$ +ändert sich bei der Drehung nicht. +In der Ebene mit der orthogonalen Basis aus den Vektoren +$\vec{x}-(\vec{x}\cdot\vec{k})\vec{k}$ und $-\vec{x}\times\vec{k}$ +kann man die Drehung $R_\alpha$ um den Winkel $\alpha$ mit den +trigonometrischen Funktionen beschreiben +(siehe Abbildung~\ref{buch:lie:fig:rodrigues}): +\begin{align} +\vec{x} +\mapsto +R_\alpha\vec{x} +&= +(\vec{x}-(\vec{x}\cdot\vec{k})\vec{k}) +\cos\alpha +- +\vec{x}\times\vec{k} +\sin\alpha ++ +(\vec{k}\cdot\vec{x})\vec{k} +\notag +\\ +&= +\vec{x}\cos\alpha ++ +(1-\cos\alpha)(\vec{x}\cdot\vec{k})\vec{k} ++ +\vec{k}\times\vec{x}\sin\alpha. +\label{buch:lie:eqn:rodrigues} +\end{align} +Dies ist bekannt als die {\em Formel von Rodrigues} +\index{Formel von Rodrigues}% +\index{Rodrigues-Formel}% +Wir halten noch fest, dass die Ableitung an der Stelle $\alpha=0$ +der Tangentialvektor +\begin{equation} +\frac{d}{d\alpha}R_\alpha\vec{x}\,\bigg|_{\alpha=0} += +\vec{k}\times\vec{x} +\label{buch:lie:eqn:so3tangentialvektor} +\end{equation} +ist. + % % Spezielle lineare Gruppe % \subsection{Volumenerhaltende Abbildungen und die Gruppe $\operatorname{SL}_n(\mathbb{R})$ \label{buch:gruppen:sl}} -Die Elemente der Gruppe $SO(n)$ erhalten Längen, Winkel und die +Die Elemente der Gruppe $\operatorname{SO}(n)$ erhalten Längen, Winkel und die Orientierung, also auch das Volumen. Es gibt aber volumenerhaltende Abbildungen, die Längen oder Winkel -nicht notwendigerweise erhalten. +nicht notwendigerweise erhalten, zum Beispiel Scherungen. Matrizen $A\in M_n(\mathbb{R})$, die das Volumen erhalten, haben die Determinante $\det A=1$. Wegen $\det(AB)=\det A\det B$ ist das Produkt zweier Matrizen mit @@ -541,6 +625,7 @@ Determinante $1$ wieder eine solche, sie bilden daher eine Gruppe. \begin{definition} Die volumenerhaltenden Abbildungen bilden die Gruppe +\index{volumenerhaltend}% \[ \operatorname{SL}_n(\mathbb{R}) = @@ -551,6 +636,9 @@ A\in M_n(\mathbb{R}) \} \] sie heisst die {\em spezielle lineare Gruppe}. +\index{spezielle lineare Gruppe}% +\index{Gruppe, spezielle lineare}% +\index{SLn(R)@$\operatorname{SL}_n(\mathbb{R})$}% \end{definition} Wir wollen jetzt die Tangentialvektoren von $\operatorname{SL}_n(\mathbb{R})$ @@ -576,6 +664,10 @@ c(t)&d(t) \frac{d}{dt} \det A(t)\bigg|_{t=0} &= +\frac{d}{dt}\bigl(a(t)d(t)-b(t)c(t)\bigr)\bigg|_{t=0} +\\ +&&&& +&= \dot{a}(0) d(0)+a(0)\dot{d}(0) - \dot{b}(0) c(0)-b(0)\dot{c}(0) @@ -592,7 +684,7 @@ Dies gilt nicht nur im Falle $n=2$, sondern ganz allgemein für beliebige $n\times n$-Matrizen. \begin{satz} -Ist $A(t)$ eine differenzierbare Kurve in $\operatorname{SL}_n(\mathbb{B})$ +Ist $A(t)$ eine differenzierbare Kurve in $\operatorname{SL}_n(\mathbb{R})$ mit $A(0)=I$, dann ist $\operatorname{Spur}\dot{A}(0)=0$. \end{satz} @@ -626,8 +718,8 @@ jenes für $i=1$, somit ist die Ableitung von $\det A(t)$ \frac{d}{dt}\det A_{11}(t). \label{buch:gruppen:eqn:detspur} \end{equation} -Die Beziehung \eqref{buch:gruppen:eqn:detspur} kann für einen Beweis mit -vollständiger Induktion verwendet werden. +Die Beziehung \eqref{buch:gruppen:eqn:detspur} kann wie folgt +für einen Beweis mit vollständiger Induktion verwendet werden. Die Induktionsverankerung für $n=1$ besagt, dass $\det A(t)=a_{11}(t)$ genau dann konstant $=1$ ist, wenn $\dot{a}_{11}(0)=\operatorname{Spur}A(0)$ @@ -668,6 +760,19 @@ A=\begin{pmatrix}a&b\\c&d\end{pmatrix} A=\begin{pmatrix}a&b\\c&-a\end{pmatrix}. \] Der Tangentialraum ist also dreidimensional. +\begin{figure} +\centering +\includegraphics{chapters/60-gruppen/images/sl2.pdf} +\caption{Tangentialvektoren und die davon erzeugen Einparameteruntergruppen +für die Lie-Gruppe $\operatorname{SL}_2(\mathbb{R})$ der flächenerhaltenden +linearen Abbildungen von $\mathbb{R}^2$. +In allen drei Fällen wird das blaue Quadrat mit den Ecken in den +Standardbasisvektoren von einer Matrix der Einparameteruntergruppe zu +zum roten Viereck verzerrt, der Flächeninhalt bleibt aber erhalten. +In den beiden Fällen $B$ und $C$ stellen die grünen Kurven die Bahnen +der Bilder der Standardbasisvektoren dar. +\label{buch:gruppen:fig:sl2}} +\end{figure}% Als Basis könnte man die folgenden Vektoren verwenden: \begin{align*} A @@ -714,8 +819,10 @@ I\cosh t + C \sinh t \end{align*} wobei in der Auswertung der Potenzreihe für $e^{Ct}$ verwendet wurde, dass $C^2=I$. +Die von $A$, $B$ und $C$ erzeugten Einparameteruntergruppen sind in +Abbildung~\ref{buch:gruppen:fig:sl2} visualisiert. -Die Matrizen $e^{At}$ Streckungen der einen Koordinatenachse und +Die Matrizen $e^{At}$ sind Streckungen der einen Koordinatenachse und Stauchungen der anderen derart, dass das Volumen erhalten bleibt. Die Matrizen $e^{Bt}$ sind Drehmatrizen, die Längen und Winkel und damit erst recht den Flächeninhalt erhalten. @@ -764,25 +871,26 @@ Dies ist die gegenüber $e^{At}$ um $45^\circ$ verdrehte Situation, auch diese Matrizen sind flächenerhaltend. \begin{figure} \centering -\includegraphics{chapters/60-gruppen/images/sl2.pdf} -\caption{Tangentialvektoren und die davon erzeugen Einparameteruntergruppen -für die Lie-Gruppe $\operatorname{SL}_2(\mathbb{R})$ der flächenerhaltenden -linearen Abbildungen von $\mathbb{R}^2$. -In allen drei Fällen wird ein blauer Rhombus mit den Ecken in den -Standardbasisvektoren von einer Matrix der Einparameteruntergruppe zu -zum roten Viereck verzerrt, der Flächeninhalt bleibt aber erhalten. -In den beiden Fällen $B$ und $C$ stellen die grünen Kurven die Bahnen -der Bilder der Standardbasisvektoren dar. -\label{buch:gruppen:fig:sl2}} -\end{figure}% -\begin{figure} -\centering \includegraphics{chapters/60-gruppen/images/scherungen.pdf} -\caption{Weitere Matrizen mit Spur $0$ und ihre Wirkung -Die inken beiden Beispiele $M$ und $N$ sind nilpotente Matrizen, -die zugehörigen Einparameter-Untergruppen beschreiben Schwerungen. +\caption{Weitere Matrizen mit Spur $0$ und ihre Wirkung. +Die linken beiden Beispiele $M$ und $N$ sind nilpotente Matrizen, +die zugehörigen Einparameteruntergruppen beschreiben Scherungen. \label{buch:gruppen:fig:scherungen}} \end{figure} + +Die Gruppe $\operatorname{SL}_2(\mathbb{R})$ hat aber auch die +Tangentialvektoren +\begin{align*} +M&=\begin{pmatrix}0&1\\0&0\end{pmatrix}=\frac12(B+C) +&&\text{und}& +N&=\begin{pmatrix}0&0\\1&0\end{pmatrix}=\frac12(-B+C), +\intertext{die die Scherungen} +e^{Mt}&= \begin{pmatrix}1&0\\t&0\end{pmatrix} +&& +e^{NT}&=\begin{pmatrix}1&t\\0&1\end{pmatrix} +\end{align*} +als Einparameteruntergruppen haben. +Diese sind in Abbildung~\ref{buch:gruppen:fig:scherungen} dargestellt. \end{beispiel} % @@ -802,9 +910,20 @@ a,b,c,d\in\mathbb{C},\det(A)=1, AA^*=I \right\} \] heisst die {\em spezielle unitäre Gruppe}. +\index{spezielle unitäre Gruppe}% +\index{unitäre Gruppe, speziell}% +\index{Gruppe, speziell unitäre}% +\index{SU(n)@$\operatorname{SU}(n)$}% Wegen $\det(AB)=\det(A)\det(B)=1$ und $(AB)^*AB=B^*A^*AB=B^*B=I$ ist $\operatorname{SU}(2)$ eine Untergruppe von $\operatorname{GL}_2(\mathbb{C})$. -Die Bedingungen $\det A=1$ und $AA^*=I$ schränken die möglichen Werte +Die Bedingungen +\begin{equation} +\det A=1 +\qquad\text{und}\qquad +AA^*=I +\label{buch:lie:eqn:su2bed} +\end{equation} +schränken die möglichen Werte von $a$ und $b$ weiter ein. Aus \[ @@ -815,7 +934,7 @@ A^* \overline{b}&\overline{d} \end{pmatrix} \] -und den Bedingungen führen die Gleichungen +und den Bedingungen~\eqref{buch:lie:eqn:su2bed} folgen die Gleichungen \[ \begin{aligned} a\overline{a}+b\overline{b}&=1 @@ -831,7 +950,7 @@ c\overline{a}+d\overline{b}&=0 \\ c\overline{c}+d\overline{d}&=1&&\Rightarrow&|c|^2+|d|^2&=1 \\ -ad-bc&=1 +ad-bc&=1. \end{aligned} \] Aus der zweiten Gleichung kann man ableiten, dass es eine Zahl $t\in\mathbb{C}$ @@ -846,7 +965,7 @@ t(|a|^2+|b|^2) = t, \] -also muss die Matrix $A$ die Form haben +also muss die Matrix $A$ die Form \[ A = @@ -854,10 +973,11 @@ A a&b\\ -\overline{b}&\overline{a} \end{pmatrix} -\qquad\text{mit}\quad |a|^2+|b|^2=1. +\qquad\text{mit}\quad |a|^2+|b|^2=1 \] +haben. Schreibt man $a=a_1+ia_2$ und $b=b_1+ib_2$ mit rellen $a_i$ und $b_i$, -dann besteht $SU(2)$ aus den Matrizen der Form +dann besteht $\operatorname{SU}(2)$ aus den Matrizen der Form \[ A= \begin{pmatrix} diff --git a/buch/chapters/60-gruppen/symmetrien.tex b/buch/chapters/60-gruppen/symmetrien.tex index aee3b41..252fdca 100644 --- a/buch/chapters/60-gruppen/symmetrien.tex +++ b/buch/chapters/60-gruppen/symmetrien.tex @@ -15,7 +15,7 @@ bedeutet. Spiegelsymmetrische Objekte zeichnen sich zum Beispiel dadurch aus, dass Messungen von Strecken die gleichen Werte ergeben wie die Messungen der entsprechenden gespiegelten Strecken (siehe auch -Abbildung~\ref{buch:lie:bild:castlehoward}, was die Herkunft des +Abbildung~\ref{buch:lie:bild:castlehoward}), was die Herkunft des Begriffs verständlich macht. \begin{figure} \centering @@ -31,8 +31,8 @@ In der Physik wird dem Begriff der Symmetrie daher auch eine erweiterte Bedeutung gegeben. Jede Transformation eines Systems, welche bestimmte Grössen nicht verändert, wird als Symmetrie bezeichnet. -Die Gesetze der Physik sind typischerweise unabhängig davon, wo man den -den Nullpunkt der Zeit oder das räumlichen Koordinatensystems ansetzt, +Die Gesetze der Physik sind typischerweise unabhängig davon, wo man +den Nullpunkt der Zeit oder des räumlichen Koordinatensystems ansetzt, eine Transformation des Zeitnullpunktes oder des Ursprungs des Koordinatensystems ändert daher die Bewegungsgleichungen nicht, sie ist eine Symmetrie des Systems. @@ -52,8 +52,8 @@ zusätzliche geometrische Struktur, man nennt sie eine differenzierbare Mannigfaltigkeit. Dieser Begriff wird im Abschnitt~\ref{buch:subsection:mannigfaltigkeit} eingeführt. -Es wird sich zum Beispiel zeigen, dass die Menge der Drehungen der -Ebene mit den Punkten eines Kreises parametrisieren lassen, +Es wird sich zum Beispiel zeigen, dass sich die Menge der Drehungen der +Ebene mit den Punkten eines Kreises parametrisieren lässt, die Lösungen der Gleichung $x^2+y^2=1$ sind. Eine Lie-Gruppe ist eine Gruppe, die gleichzeitig eine differenzierbare @@ -94,10 +94,10 @@ Die folgenden Beispiele sollen zeigen, wie solche Symmetriedefinitionen auf algebraische Bedingungen an die Matrixelemente führen. Zu jeder Abbildung $f\colon\mathbb{R}^n\to\mathbb{R}^n$, unter der -ein geometrisches Objekt in $\mathbb{R}^n$ symmetrisch ist, können wir +ein geometrisches Objekt in $\mathbb{R}^n$ unveränder bleibt, können wir sofort weitere Abbildungen angeben, die ebenfalls Symmetrien sind. Zum Beispiel sind die iterierten Abbildungen $f\circ f$, $f\circ f\circ f$ -u.~s.~w., die wir auch $f^n$ mit $n\in\mathbb{N}$ schreiben werden, +usw., die wir auch $f^n$ mit $n\in\mathbb{N}$ schreiben werden, ebenfalls Symmetrien. Wenn die Symmetrie auch umkehrbar ist, dann gilt dies sogar für alle $n\in\mathbb{Z}$. @@ -105,7 +105,9 @@ Wir erhalten so eine Abbildung $\varphi\colon \mathbb{Z}\to \operatorname{GL}_n(\mathbb{R}):n\mapsto f^n$ mit den Eigenschaften $\varphi(0)=f^0 = I$ und $\varphi(n+m)=f^{n+m}=f^n\circ f^m = \varphi(n)\circ\varphi(m)$. -$\varphi$ ist ein Homomorphismus der Gruppe $\mathbb{Z}$ in die Gruppe +$\varphi$ ist ein Homomorphismus (siehe +Definition~\ref{buch:gruppen:def:homomorphismus}) +der Gruppe $\mathbb{Z}$ in die Gruppe $\operatorname{GL}_n(\mathbb{R})$. Wir nennen dies eine {\em diskrete Symmetrie}. @@ -114,10 +116,10 @@ Wir nennen dies eine {\em diskrete Symmetrie}. Von besonderem Interesse sind kontinuierliche Symmetrien. Dies sind Abbildungen eines Systems, die von einem Parameter abhängen. -Zum Beispiel können wir Drehungen der Ebene $\mathbb{R}^2$ um den -Winkel $\alpha$ durch Matrizen +Zum Beispiel können Drehungen der Ebene $\mathbb{R}^2$ um den +Winkel $\alpha$ durch die Matrizen \[ -D_{\alpha} +R_{\alpha} = \begin{pmatrix} \cos\alpha&-\sin\alpha\\ @@ -126,18 +128,20 @@ D_{\alpha} \] beschrieben werden. Ein Kreis um den Nullpunkt bleibt unter jeder dieser Drehungen invariant. -Im Gegensatz dazu sind alle $3n$-Ecke mit Schwerpunkt $0$ nur invariant -unter der einen Drehung $D_{\frac{2\pi}3}$ invariant. -Die kleinste Menge, die einen vorgegebenen Punkt enthält und unter -allen Drehungen $D_\alpha$ invariant ist, ist immer ein Kreis um +Im Gegensatz dazu sind alle gleichseitigen Dreiecke mit Schwerpunkt $0$ +nur unter der einen Drehung $R_{\frac{2\pi}3}$ invariant. +Eine minimale Menge, die einen vorgegebenen Punkt enthält und unter +allen Drehungen $R_\alpha$ invariant ist, ist immer ein Kreis um den Nullpunkt. \begin{definition} +\label{buch:lie:def:einparameteruntergruppe} Ein Homomorphismus $\varphi\colon\mathbb{R}\to\operatorname{GL}_n(\mathbb{R})$ von der additiven Gruppe $\mathbb{R}$ in die allgemeine lineare Gruppe -heisst eine {\em Einparameter-Untergruppe} von +heisst eine {\em Einparameteruntergruppe} von $\operatorname{GL}_n(\mathbb{R})$. \end{definition} +\index{Einparameteruntergruppe} Die Abbildung \[ @@ -146,16 +150,18 @@ Die Abbildung \mathbb{R}\to\operatorname{GL}_n(\mathbb{R}) : \alpha \mapsto -D_{\alpha} +R_{\alpha} = \begin{pmatrix} \cos\alpha&-\sin\alpha\\ \sin\alpha& \cos\alpha \end{pmatrix} \] -ist also eine Einparameter-Untergruppe von $\operatorname{GL}_2(\mathbb{R})$. +ist also eine Einparameteruntergruppe von $\operatorname{GL}_2(\mathbb{R})$. \subsubsection{Der harmonische Oszillator} +\index{harmonischer Oszillator}% +\index{Oszillator}% \begin{figure} \centering \includegraphics{chapters/60-gruppen/images/phasenraum.pdf} @@ -165,17 +171,21 @@ im Phasenraum sind Ellipsen mit Halbachsenverhältnis $\omega^{-1}$. \label{chapter:gruppen:fig:phasenraum}} \end{figure} Eine Masse $m$ verbunden mit einer Feder mit der Federkonstanten $K$ +\index{Federkonstante}% schwingt um die Ruhelage $x=0$ entsprechend der Differentialgleichung \[ m\frac{d^2}{dt^2} x(t) = -Kx(t). \] Die Kreisfrequenz der Schwingung ist +\index{Kreisfrequenz}% +\index{Schwingung}% \[ \omega = \sqrt{\frac{K}{m}}. \] Das System kann als zweidimensionales System im Phasenraum mit den Koordinaten $x_1=x$ und $x_2=p=m\dot{x}$ beschrieben werden. Die zweidimensionale Differentialgleichung ist +\index{zweidimensionale Differentialgleichung}% \begin{equation} \left. \begin{aligned} @@ -230,7 +240,7 @@ p(t) \label{buch:gruppen:eqn:phi} \end{equation} schreiben. -Die Matrizen $\Phi_t$ bilden eine Einparameter-Untergruppe von +Die Matrizen $\Phi_t$ bilden eine Einparameteruntergruppe von $\operatorname{GL}_n(\mathbb{R})$, da \begin{align*} \Phi_s\Phi_t @@ -265,11 +275,13 @@ gilt. Die Lösungen der Differentialgleichung~\eqref{chapter:gruppen:eqn:phasenraumdgl} sind in Abbildung~\ref{chapter:gruppen:fig:phasenraum} +dargestellt. Die Matrizen $\Phi_t$ beschreiben eine kontinuierliche Symmetrie des Differentialgleichungssystems, welches den harmonischen Oszillator beschreibt. \subsubsection{Fluss einer Differentialgleichung} +\index{Fluss}% Die Abbildungen $\Phi_t$ von \eqref{buch:gruppen:eqn:phi} sind jeweils Matrizen in $\operatorname{GL}_n(\mathbb{R})$. Der Grund dafür ist, dass die @@ -333,9 +345,10 @@ Die Abbildung \[ \Phi\colon \mathbb{R}\times\mathbb{R}^n\to\mathbb{R}^n : -(t,x_0) \mapsto \Phi_t(x_0) = x(t,x_0) +(t,x_0) \mapsto \Phi_t(x_0) := x(t,x_0) \] heisst der {\em Fluss} der Differentialgleichung +\index{Fluss}% \eqref{buch:gruppen:eqn:dgl}, wenn für jedes $x_0\in\mathbb{R}^n$ die Kurve $t\mapsto \Phi_t(x_0)$ eine Lösung der Differentialgleichung ist mit Anfangsbedingung $x_0$. @@ -358,10 +371,10 @@ Das funktioniert auch, weil $f(t_0,x_0)$ selbst ein Vektor von $\mathbb{R}^n$ ist, in dem die Bahnkurve verläuft. Diese Idee funktioniert nicht mehr zum Beispiel für eine -Differentialgleichung auf einer Kugeloberfläche, weil alle Punkte +Differentialgleichung auf einer Kugel\-oberfläche, weil alle Punkte $x(t_0)+hf(t_0,x_0)$ für alle $h\ne 0$ nicht mehr auf der Kugeloberfläche liegen. -Physikalisch äussert sich das ein einer zusätzlichen Kraft, die nötig +Physikalisch äussert sich das in einer zusätzlichen Kraft, die nötig ist, die Bahn auf der Kugeloberfläche zu halten. Diese Kraft stellt zum Beispiel sicher, dass die Vektoren $f(t,x)$ für Punkte $x$ auf der Kugeloberfläche immer tangential an die Kugel sind. @@ -370,12 +383,13 @@ nicht mehr ein Objekt, welches als Teil der Kugeloberfläche definiert werden kann, er kann nur definiert werden, wenn man sich die Kugel als in einen höherdimensionalen Raum eingebettet vorstellen kann. -Um die Idee der Differentialgleichung auf einer beliebigen Fläche -konsistent zu machen ist daher notwendig, die Idee einer Tagentialrichtung +Um die Idee einer Differentialgleichung auf einer beliebigen Fläche +konsistent zu machen, ist daher notwendig, die Idee einer Tagentialrichtung auf eine Art zu definieren, die nicht von der Einbettung der Fläche in den $n$-dimensionalen Raum abhängig ist. Das in diesem Abschnitt entwickelte Konzept der {\em Mannigfaltigkeit} löst dieses Problem. +\index{Mannigfaltigkeit}% \subsubsection{Karten} Die Navigation auf der Erdoberfläche verwendet das Koordinatensystem @@ -385,6 +399,11 @@ den geographischen Polen befindet, denn deren Koordinaten sind nicht mehr eindeutig. Alle Punkte mit geographischer Breite $90^\circ$ und beliebiger geographischer Länge beschreiben den Nordpol. +\index{geographische Länge}% +\index{geographische Breite}% +\index{Nordpol}% +\index{Länge, geographisch}% +\index{Breite, geographisch}% Auch die Ableitung funktioniert dort nicht mehr. Bewegt man sich mit konstanter Geschwindigkeit über den Nordpol, springt die Ableitung der geographischen Breite von einem positiven @@ -412,6 +431,7 @@ verschiedenen Koordinatensystemen versehen werden kann. Ein Koordinatensystem ist eine umkehrbare Abbildung einer offenen Teilmenge $U\subset M$ in den Raum $\mathbb{R}^n$. Die Komponenten dieser Abbildung heissen die {\em Koordinaten}. +\index{Koordinaten}% \begin{figure} \centering @@ -429,12 +449,13 @@ entstehen soll. \end{figure} \begin{definition} -Eine Karte auf $M$ ist eine umkehrbare Abbildung -$\varphi\colon U\to \mathbb{R}^n$ (siehe auch -Abbildung~\ref{buch:gruppen:fig:karten}). -Ein differenzierbarer Atlas ist eine Familie von Karten $\varphi_\alpha$ +\index{Karte}% +Eine {\em Karte} auf $M$ ist eine umkehrbare Abbildung +$\varphi\colon U\to \mathbb{R}^n$ einer offenen Menge $U_\alpha\subset M$ +(siehe auch Abbildung~\ref{buch:gruppen:fig:karten}). +Ein {\em differenzierbarer Atlas} ist eine Familie von Karten $\varphi_\alpha$ derart, dass die Definitionsgebiete $U_\alpha$ die ganze Menge $M$ -überdecken, und dass die Kartenwechsel Abbildungen +überdecken, und dass die Kartenwechselabbildungen \[ \varphi_{\beta\alpha}=\varphi_\beta\circ\varphi_\alpha^{-1} \colon @@ -444,8 +465,9 @@ derart, dass die Definitionsgebiete $U_\alpha$ die ganze Menge $M$ \] als Abbildung von offenen Teilmengen von $\mathbb{R}^n$ differenzierbar ist. -Eine {$n$-dimensionale differenzierbare Mannigfaltigkeit} ist eine +Eine {\em $n$-dimensionale differenzierbare Mannigfaltigkeit} ist eine Menge $M$ mit einem differenzierbaren Atlas. +\index{Atlas}% \end{definition} Karten und Atlanten regeln also nur, wie sich verschiedene lokale @@ -569,7 +591,7 @@ konstruieren, der $S^n$ zu einer $n$-dimensionalen Mannigfaltigkeit macht. \subsubsection{Tangentialraum} Mit Hilfe einer Karte $\varphi_\alpha\colon U_\alpha\to\mathbb{R}^n$ kann das Geschehen in einer Mannigfaltigkeit in den vertrauten -$n$-dimensionalen Raum $\mathbb{B}^n$ transportiert werden. +$n$-dimensionalen Raum $\mathbb{R}^n$ transportiert werden. Eine Kurve $\gamma\colon \mathbb{R}\to M$, die so parametrisiert sein soll, dass $\gamma(t)\in U_\alpha$ für $t$ in einer Umgebung $I$ von $0$ ist, wird von der Karte in eine Kurve @@ -606,7 +628,8 @@ Aus = \varphi_{\beta\alpha}\circ\gamma_\alpha \] -folgt durch Ableitung nach dem Kurvenparameter $t$, dass +folgt durch Ableitung nach dem Kurvenparameter $t$ mit Hilfe der +Kettenregel, dass \[ \frac{d}{dt}\gamma_\beta(t) = @@ -624,7 +647,7 @@ $\varphi_{\beta\alpha}$ stellt also nur sicher, dass die Beschreibung eines Systemes mit Differentialgleichungen in verschiedenen Koordinatensystemen auf die gleichen Lösungskurven in der Mannigfaltigkeit führt. -Insbesondere ist die Verwendung von Karten ist also nur ein Werkzeug, +Insbesondere ist die Verwendung von Karten also nur ein Werkzeug, mit dem die Unmöglichkeit einer globalen Besschreibung einer Mannigfaltigkeit $M$ mit einem einzigen globalen Koordinatensystem ohne Singularitäten umgangen werden kann. @@ -658,9 +681,9 @@ Die Koordinatenumrechnung ist gegeben durch \dot{x}(t) = D\varphi_{31}(\gamma(t)) -\dot{y}(t) +\dot{y}(t). \] -wird für die spezielle Kurve $\gamma(t)=(\cos t,\sin t)$ wird dies zu +Für die spezielle Kurve $\gamma(t)=(\cos t,\sin t)$ wird dies zu \[ D\varphi_{31}(\gamma(t)) \cdot @@ -690,7 +713,7 @@ Darüber hinweg hilft auch die Tatsache nicht, dass die Kreislinie in den Vektorraum $\mathbb{R}^2$ eingebettet sind, wo sich Vektoren durch Translation miteinander vergleichen lassen. Ein nichtverschwindender Tangentialvektor im Punkt $(1,0)$ hat, -betrachtet als Vektor in $\mathbb{R}^2$ verschwindende $x$-Komponente, +betrachtet als Vektor in $\mathbb{R}^2$, verschwindende $x$-Komponente, für Tangentialvektoren im Inneren eines Quadranten ist dies nicht der Fall. @@ -701,18 +724,25 @@ Dies ist möglich, weil die Kreislinie eine kontinuierliche Symmetrie, nämlich die Drehung um den Winkel $t$ hat, die es erlaubt, den Punkt $(1,0)$ in den Punkt $(\cos t,\sin t)$ abzubilden. Erst diese Symmetrie ermöglicht den Vergleich. -Dieser Ansatz ist für alle Matrizen erfolgreich, wie wir später sehen werden. +Dieser Ansatz ist für alle Matrizengruppen erfolgreich, +wie wir später sehen werden. Ein weiterer Ansatz, Tangentialvektoren zu vergleichen, ist die Idee, einen sogenannten Zusammenhang zu definieren, eine Vorschrift, wie +\index{Zusammenhang}% +\index{Paralleltransport}% Tangentialvektoren infinitesimal entlang von Kurven in der Mannigfaltigkeit transportiert werden können. Auf einer sogenannten {\em Riemannschen Mannigfaltigkeit} ist zusätzlich zur Mannigfaltigkeitsstruktur die Längenmessung definiert. +\index{Riemannsche Mannigfaltigkeit}% +\index{Mannigfaltigkeit!Riemannsche}% Sie kann dazu verwendet werden, den Transport von Vektoren entlang einer Kurve so zu definieren, dass dabei Längen und Winkel erhalten bleiben. +\index{Längenmessung}% Dieser Ansatz ist die Basis der Theorie der Krümmung sogenannter Riemannscher Mannigfaltigkeiten. +\index{Krümmung}% %\subsection{Der Satz von Noether %\label{buch:subsection:noether}} diff --git a/buch/chapters/60-gruppen/uebungsaufgaben/6003.tex b/buch/chapters/60-gruppen/uebungsaufgaben/6003.tex new file mode 100644 index 0000000..663b1a0 --- /dev/null +++ b/buch/chapters/60-gruppen/uebungsaufgaben/6003.tex @@ -0,0 +1,134 @@ +Für die Lie-Algebra $\operatorname{sl}_2(\mathbb{R})$ wurde die Basis +\[ +A=\begin{pmatrix} 1&0\\0&-1 \end{pmatrix}, +\qquad +N=\begin{pmatrix} 0&1\\0&0\end{pmatrix}, +\qquad +N=\begin{pmatrix} 0&0\\1&0\end{pmatrix} +\] +gefunden. +Dies bedeutet, dass die Elemente +der Gruppe $\operatorname{SL}_2(\mathbb{R})$ nahe der Einheitsmatrix +als ein Produkt von Matrizen der Form +\[ +D=e^{At}=\begin{pmatrix}e^t&0\\0&e^{-1}\end{pmatrix}, +\quad +S=e^{Ns} = \begin{pmatrix}1&s\\0&1\end{pmatrix}, +\quad +T=e^{Mt} = \begin{pmatrix}1&0\\t&1\end{pmatrix} +\] +geschrieben werden können. +\begin{teilaufgaben} +\item +Finden Sie zur Drehung $R_\alpha\in\operatorname{SO}(2)$ +aus \eqref{buch:lie:eqn:ralphadefinition} eine solche Zerlegung +$R_\alpha=DST$. +\item +Schreiben Sie die Matrix +\[ +A=\begin{pmatrix} +\frac12&-\frac{\sqrt{3}}2\\ +\frac{\sqrt{3}}2&\frac12 +\end{pmatrix} +\] +als Produkt $A=DST$. +\end{teilaufgaben} + +\begin{loesung} +\begin{teilaufgaben} +\item +Zunächst schreiben wir etwas einfacher +\[ +D=\begin{pmatrix}c&0\\0&c^{-1}\end{pmatrix}. +\] +Dann multiplizeren wir +\begin{align*} +DST +&= +\begin{pmatrix}c&0\\0&c^{-1}\end{pmatrix} +\begin{pmatrix}1&s\\0&1\end{pmatrix} +\begin{pmatrix}1&0\\t&1\end{pmatrix} +\\ +&= +\begin{pmatrix}c&0\\0&c^{-1}\end{pmatrix} +\begin{pmatrix}1+st&s\\t&1\end{pmatrix} +\\ +&= +\begin{pmatrix} +(1+st)c&sc\\ +c^{-1}t&c^{-1} +\end{pmatrix}. +\end{align*} +Der Vergleich mit +\[ +R_\alpha += +\begin{pmatrix} +\cos\alpha&-\sin\alpha\\ +\sin\alpha& \cos\alpha +\end{pmatrix} += +\begin{pmatrix} +(1+st)c&sc\\ +c^{-1}t&c^{-1} +\end{pmatrix} +\] +erlaubt jetzt, die Parameter, $c$, $s$ und $t$ abzulesen. +Zunächst folgt aus dem Eintrag rechts unten, dass +\[ +c=\frac{1}{\cos\alpha} +\] +sein muss. +Aus dem Eintrag links unten in der Matrix folgt dann +\[ +c^{-1}t = t\cos\alpha = \sin\alpha +\quad\Rightarrow\quad +t=\frac{\sin\alpha}{\cos\alpha}=\tan\alpha. +\] +Der Eintrag rechts oben führt schliesslich auf die Gleichung +\[ +sc=\frac{s}{\cos\alpha}=-\sin\alpha +\quad\Rightarrow\quad +s=-\sin\alpha\cos\alpha +\] +für $s$. +Damit sind zwar die Parameter bestimmt, es ist aber noch nachzuprüfen, +dass sich damit auch der korrekte Eintrag oben links in der Matrix +ergibt. +Es ist +\[ +(1+st)c += +\frac{1-\sin\alpha\cos\alpha\tan\alpha}{\cos\alpha} += +\frac{1-\sin^2\alpha}{\cos\alpha} += +\frac{\cos^2\alpha}{\cos\alpha}=\cos\alpha, +\] +somit ist +\[ +c=\frac{1}{\cos\alpha},\; t=\tan\alpha,\; s=-\sin\alpha\cos\alpha=-\frac12\sin2\alpha +\] +tatsächlich die gesuchte Lösung. +\item +Die Matrix $A$ ist die Drehung $A=R_{60^\circ}$, daher können wir nach +a) folgern: +\begin{align*} +c&=\frac{1}{\cos 60^\circ}= 2\\ +s&=-\frac12\sin120^\circ =-\frac{\sqrt{3}}4\\ +t&=\tan 60^\circ = \sqrt{3}. +\end{align*} +Daher gilt +\[ +DST += +\begin{pmatrix}2&0\\0&\frac12\end{pmatrix} +\begin{pmatrix}1&-\frac{\sqrt{3}}4\\0&1\end{pmatrix} +\begin{pmatrix}1&0\\ \sqrt{3}&1\end{pmatrix} += +A, +\] +wie man mit einem Computeralgebraprogramm leicht nachprüfen kann. +\qedhere +\end{teilaufgaben} +\end{loesung} diff --git a/buch/chapters/70-graphen/beschreibung.tex b/buch/chapters/70-graphen/beschreibung.tex index a0f46da..918594d 100644 --- a/buch/chapters/70-graphen/beschreibung.tex +++ b/buch/chapters/70-graphen/beschreibung.tex @@ -6,16 +6,21 @@ \section{Beschreibung von Graphen mit Matrizen \label{buch:section:beschreibung-von-graphen-mit-matrizen}} \rhead{Beschreibung mit Matrizen} -Ein Graph ist eine Menge von Knoten, die untereinander mit Kanten -verbunden sind. -Graphen können zum Beispiel verwendet werden um Netzwerke zu beschreiben, -aber auch viele andere Datenstrukturen. -Die Knoten können einzelne Objekte beschreiben, die Kanten beschreiben -dann Beziehungen zwischen diesen Objekten. +Als universelles kombinatorisches Modell sind Graphen für eine +Vielzahl von Problemlösungen interessant. +Zum Beispiel zeigt Kapitel~\ref{chapter:munkres}, wie man +ein Zuordnungsproblem als Graphenproblem formulieren kann. +Die Lösung erfolgt dann allerdings zweckmässigerweise unter +Verwendung einer Matrix. +Ziel dieses Abschnitts ist, Graphen und ihre zugehörige Matrizen +zu definieren und erste Eigenschaften des Graphen mit algebraischen +Mitteln abzuleiten. +Die Präsentation ist allerdings nur ein erster Einstieg, tiefer +gehende Information kann in \cite{skript:brualdi} gefunden werden. \subsection{Definition von Graphen \label{subsection:definition-von-graphen}} -In der Einleitung zu diesem Abschnitt wurde bereits eine informelle +In der Einleitung wurde bereits eine informelle Beschreibung des Konzeptes eines Graphen gegeben. Um zu einer Beschreibung mit Hilfe von Matrizen zu kommen, wird eine exakte Definition benötigt. @@ -25,7 +30,7 @@ sind und sich in Unterschieden in der Definition der zugehörigen Matrix \subsubsection{Ungerichtete Graphen} Die Grundlage für alle Arten von Graphen ist eine Menge $V$ von {\em Knoten}, -auch {\em Vertices} genannt. +auch {\em Vertizes} genannt. \index{Knoten}% \index{Vertex}% Die Unterschiede zeigen sich in der Art und Weise, wie die Knoten @@ -35,7 +40,7 @@ verbunden werden. Bei einen ungerichteten Graphen sind die beiden Endpunkte einer Kante gleichwertig, es gibt keine bevorzugte Reihenfolge oder Richtung der Kante. -Eine Kante wird daher vollständig spezifiziert, wenn wir die +Eine Kante ist daher vollständig spezifiziert, wenn wir die Menge der Endpunkte kennen. Dies führt auf die folgende Definition eines ungerichteten Graphen. @@ -48,14 +53,16 @@ und eine Menge $E$ von zweielementigen Teilmengen \[ E \subset \{\, \{a,b\}\subset V\,|\, a\ne b\}. \] -Die Elemente von $E$ heissen {\em Kanten} ({\em edges}). +Die Elemente von $E$ heissen {\em Kanten} (edges). \end{definition} Man beachte, dass es keine Kante gibt, die einen Knoten $a\in V$ mit sich selbst verbindet, da die zugehörige Menge $\{a,a\}=\{a\}$ nicht aus zwei verschiedenen Elementen besteht, wie die Definition~\ref{buch:def:ungerichteter-graph} dies verlangt. +Es gibt also keine Schleifen an einem Knoten. +\begin{beispiel} Ein elektrisches Netzwerk von ohmschen Widerständen kann mit Hilfe eines ungerichteten Graphen beschrieben werden. Ohmsche Widerstände hängen nicht von der Richtung des Stromflusses @@ -67,6 +74,7 @@ Die Endpunkte solcher Widerstände wären immer auf dem gleichen Potential. Folglich würde kein Strom fliessen und sie hätten keinen Einfluss auf das Verhalten des Netzwerkes. Sie können einfach weggelassen werden. +\end{beispiel} \subsubsection{Gerichtete Graphen} In vielen Anwendungen sind die Endpunkte einer Kante nicht austauschbar. @@ -95,15 +103,15 @@ Der Knoten $a(k)$ heisst der {\em Anfangspunkt} der Kante $k\in E$, $e(k)$ heisst der {\em Endpunkt}. \end{definition} -In einem gerichteten Graphen gehört also zu jeder Kante auch eine Richtung -und die Unterscheidung von Anfangs- und Endpunkt einer Kante ist sinnvoll +In einem gerichteten Graphen gehört also zu jeder Kante auch eine Richtung. +Die Unterscheidung von Anfangs- und Endpunkt einer Kante ist sinnvoll geworden. Ausderdem ist eine Kante $(a,a)$ wohldefiniert, also eine Kante, die vom -Knoten $a$ wieder zu $a$ zurückführt. +Knoten $a$ wieder zu $a$ zurück führt. Man kann einen ungerichteten Graphen in einen gerichteten Graphen -verwandeln, indem wir jede Kante $\{a,b\}$ durch zwei Kanten -$(a,b)$ und $(b,a)$ ersetzen. +verwandeln, indem jede Kante $\{a,b\}$ durch zwei Kanten +$(a,b)$ und $(b,a)$ ersetzt wird. Aus dem ungerichteten Graphen $(V,E)$ mit Knotenmenge $V$ und Kantenmenge $E$ wird so der gerichtete Graph $(V,E')$ mit der Kantenmenge @@ -130,12 +138,12 @@ Dies bedeutet, dass der Endpunkt jeder Kante mit dem Anfangspunkt der nachfolgenden Kante übereinstimmt. Die {\em Länge} des Pfades $\gamma=(k_1,\dots,k_r)$ ist $|\gamma|=r$. -\subsubsection{Adjazenzmatrix} +\subsection{Adjazenzmatrix} \begin{figure} \centering \includegraphics{chapters/70-graphen/images/adjazenzu.pdf} \caption{Adjazenz-, Inzidenz- und Gradmatrix eines ungerichteten -Graphen mit $5$ Knoten und $7$ Kanten. +Graphen mit fünf Knoten und sieben Kanten. \label{buch:graphen:fig:adjazenzu}} \end{figure} Eine naheliegende Beschreibung eines Graphen mit Hilfe einer @@ -146,13 +154,13 @@ Diese Zahlen werden dann als Zeilen- uns Spaltenindizes interpretiert. Die zum Graphen gehörige sogenannte {\em Adjazenzmatrix} $A(G)$ enthält die Einträge \begin{equation} -a_{ij} +a_{i\!j} = \begin{cases} 1&\qquad \{j,i\} \in E\\ 0&\qquad \text{sonst.} \end{cases} -\label{buch:graphen:eqn:linkmatrix} +\label{buch:graphen:eqn:adjazenzmatrix} \end{equation} Die Matrix hat also genau dann einen von Null verschiedenen Eintrag in Zeile $i$ und Spalte $j$, wenn die beiden Knoten $i$ und $j$ @@ -165,24 +173,27 @@ dargestellt. \centering \includegraphics{chapters/70-graphen/images/adjazenzd.pdf} \caption{Adjazenz-, Inzidenz- und Gradmatrix eines gerichteten -Graphen mit $5$ Knoten und $7$ Kanten. +Graphen mit fünf Knoten und sieben Kanten. +Die roten Einträge in der Adjazenzmatrix $A(G)$ heben die +Unterschiede zur Adjazenzmatrix des gerichteten Graphen +von Abbildung~\ref{buch:graphen:fig:adjazenzu} hervor. \label{buch:graphen:fig:adjazenzd}} \end{figure} Die Adjazenzmatrix kann auch für einen gerichteten Graphen definiert -werden wie dies in in Abbildung~\ref{buch:graphen:fig:adjazenzu} +werden wie dies in in Abbildung~\ref{buch:graphen:fig:adjazenzd} illustriert ist. Ihre Einträge sind in diesem Fall definiert mit Hilfe der gerichteten Kanten als \begin{equation} -A(G)_{ij} +A(G)_{i\!j} = -a_{ij} +a_{i\!j} = \begin{cases} 1&\qquad (j,i) \in E\\ 0&\qquad \text{sonst.} \end{cases} -\label{buch:graphen:eqn:linkmatrix} +\label{buch:graphen:eqn:adjazenzmatrix} \end{equation} Die Matrix $A(G)$ hat also genau dann einen nicht verschwindenden Matrixeintrag in Zeile $i$ und Spalte $j$, wenn es eine Verbindung @@ -192,31 +203,36 @@ von Knoten $j$ zu Knoten $i$ gibt. \subsubsection{Adjazenzmatrix und die Anzahl der Pfade} Die Beschreibung des Graphen mit der Adjazenzmatrix $A=A(G)$ nach -\eqref{buch:graphen:eqn:linkmatrix} ermöglicht bereits, eine interessante -Aufgabe zu lösen. +\eqref{buch:graphen:eqn:adjazenzmatrix} ermöglicht bereits, eine +interessante Aufgabe zu lösen. \begin{satz} \label{buch:graphen:pfade-der-laenge-n} Der gerichtete Graph $G=([n],E)$ werde beschrieben durch die Adjazenzmatrix $A=A(G)$. -Dann gibt das Element in Zeile $j$ und Spalte $i$ von $A^n$ die Anzahl -der Wege der Länge $n$ an, die von Knoten $i$ zu Knoten $j$ führen. -Insbesondere kann man die Definition~\eqref{buch:graphen:eqn:linkmatrix} +Dann gibt das Element $(A^n)_{ji}$ in Zeile $j$ und Spalte $i$ von $A^n$ +die Anzahl der Wege der Länge $n$ an, die von Knoten $i$ zu Knoten $j$ führen. +Insbesondere kann man die Definition~\eqref{buch:graphen:eqn:adjazenzmatrix} formulieren als: In Zeile $j$ und Spalte $i$ der Matrix steht die Anzahl der Pfade der Länge $1$, die $i$ mit $j$ verbinden. \end{satz} +\index{Anzahl der Pfade}% \begin{proof}[Beweis] -Es ist klar, dass $A^1$ die genannte Eigenschaft hat. -Wir beweisen, dass $A^n$ Pfade der Länge $n$ zählt, mit Hilfe von -vollständiger Induktion. -Zur Unterscheidung schreiben wir $A^{(n)}$ für die Matrix, die in Zeile +Zur Unterscheidung der Matrix der Wegzahlen von $A^n$ schreiben wir +$A^{(n)}$ für die Matrix, die in Zeile $j$ und Spalte $i$ die Anzahl der Pfade der Länge $n$ von $i$ nach $j$ enhält. Die zugehörigen Matrixelemente schreiben wir $a_{ji}^{n}$ bzw.~$a_{ji}^{(n)}$. Wir haben also zu zeigen, dass $A^n = A^{(n)}$. -Wir nehmen daher an, dass bereits bewiesen ist, dass das Element in Zeile +Wir beweisen, dass $A^n$ Pfade der Länge $n$ zählt, mit Hilfe von +vollständiger Induktion. +Es ist klar, dass $A^1$ die genannte Eigenschaft hat. +Der Fall $A^1$ dient daher als Induktionsverankerung. + +Wir nehmen daher im Sinne einer Induktionsannahme an, dass bereits +bewiesen ist, dass das Element in Zeile $j$ und Spalte $i$ von $A^{n-1}$ die Anzahl der Pfade der Länge $n-1$ zählt, dass also $A^{n-1}=A^{(n-1)}$. Dies ist die Induktionsannahme. @@ -225,16 +241,16 @@ Wir bilden jetzt alle Pfade der Länge $n$ von $i$ nach $k$. Ein Pfad der Länge besteht aus einem Pfad der Länge $n-1$, der von $i$ zu einem beliebigen Knoten $j$ führt, gefolgt von einer einzelnen Kante, die von $j$ nach $k$ führt. -Ob es eine solche Kante gibt, zeigt das Matrixelement $a_{kj}$ an. +Ob es eine solche Kante gibt, zeigt das Matrixelement $a_{k\!j}$ an. Das Element in Zeile $j$ und Spalte $i$ der Matrix $A^{(n-1)}$ gibt die Anzahl der Wege von $i$ nach $j$ an. -Es gibt also $a_{kj}\cdot a_{ji}^{(n-1)}$ Wege der Länge $n$, die von $i$ +Es gibt also $a_{k\!j}\cdot a_{ji}^{(n-1)}$ Wege der Länge $n$, die von $i$ nach $k$ führen, aber als zweitletzten Knoten über den Knoten $j$ führen. Die Gesamtzahl der Wege der Länge $n$ von $i$ nach $k$ ist daher \[ a_{ki}^{(n)} = -\sum_{j=1}^n a_{kj} a_{ji}^{(n-1)}. +\sum_{j=1}^n a_{k\!j} a_{ji}^{(n-1)}. \] In Matrixschreibweise bedeutet dies \[ @@ -248,8 +264,13 @@ A^n. \] Beim zweiten Gleichheitszeichen haben wir die Induktionsannahme verwendet. +Damit ist der Induktionsschritt vollzogen und der Satz bewiesen. \end{proof} +Speziell geben die Diagonalelemente von $A^n$ die Zahl der geschlossenen +Pfade an. +$(A^n)_{ii}$ ist die Anzahl der geschlossenen Pfade, die $i$ enthalten. + Der Satz~\ref{buch:graphen:pfade-der-laenge-n} ermöglicht auch, einen Algorithmus für den sogenannten Durchmesser eines Graphen zu formulieren. @@ -291,7 +312,7 @@ G 0& 0& 1& 0& 0& 0& 1& 0& 1& 0\\ % 8 0& 0& 0& 1& 0& 0& 0& 1& 0& 1\\ % 9 0& 0& 0& 0& 1& 1& 0& 0& 1& 0 % 10 -\end{pmatrix} +\end{pmatrix}. \] Durch Nachrechnen kann man bestätigen, dass $G^3$ keine Ausserdiagonalelemente $0$ enthält: @@ -310,13 +331,15 @@ G^3 2& 2& 2& 5& 2& 2& 2& 5& 0& 5\\ 2& 2& 2& 2& 5& 5& 2& 2& 5& 0 \end{pmatrix} += +2(U-I) + 3G. \] Daraus kann man jetzt ablesen, dass der Durchmesser des Petersongraphen -$d=5$ ist. -Man kann aber auch mehr ablesen: +$d=3$ ist. +Man kann aber noch mehr ablesen: \begin{itemize} \item -Es gibt keine geschlossenen Pfade der Länge $\le 3$. +Es gibt keine geschlossenen Pfade der Länge $3$. \item Zwischen benachbarten Knoten gibt es jeweils $5$ Pfade der Länge $3$, zwischen nicht benachbarten Knoten gibt es genau $2$ Pfade der Länge $3$. @@ -332,18 +355,6 @@ Für den Peterson-Graphen können die gefundenen Aussagen über die Anzahl von Pfaden durch Ausnützung der Symmetrien des Graphen leichter direkt gefunden werden. -\subsubsection{Beschriftete Graphen} -Bei der Beschreibung eines elektrischen Netzwerkes mit Hilfe eines -ungerichteten Graphen muss jeder Kante zusätzlich ein Widerstandswert -zugeordnet werden. -Dies ist, was eine Beschriftung einer Kante bewerkstelligt. - -\begin{definition} -Eine Beschriftung mit Elementen der Menge $L$ -eines gerichteten oder ungerichteten Graphen $G=(V,E)$ -ist eine Abbildung $l\colon E\to L$. -\index{Beschriftung}% -\end{definition} \subsection{Inzidenzmatrix} Die Adjazenzmatrix kann zusätzliche Information, die möglicherweise @@ -352,27 +363,27 @@ Dies tritt zum Beispiel in der Informatik bei der Beschreibung endlicher Automaten auf, wo zu jeder gerichteten Kante auch noch Buchstaben gehören, für die der Übergang entlang dieser Kante möglich ist. - -Die {\em Inzidenzmatrix} löst dieses Problem. -\index{Inzidenzmatrix}% -Dazu werden zunächst die Kanten numeriert $1,\dots,m$ -numeriert. -Die Matrixeinträge -\[ -a_{ij} = \begin{cases} -1\qquad&\text{Knoten $i$ ist ein Endpunkt von Kante $j$} -\\ -0\qquad&\text{sonst} -\end{cases} -\] -stellen die Beziehung zwischen Kanten und Knoten her. +Oder in der Elektrotechnik, wo jedes Bauteil in einem elektrischen +Netzwerk eine Impedanz hat. \subsubsection{Beschriftete Graphen} -Die Inzidenzmatrix kann auch einen erweiterten Graphenbegriff abbilden, -in dem zwischen zwei Kanten mehrere Verbindungen möglich sind. -Graphen mit beschrifteten Kanten gehören dazu. +Ein beschrifteter Graph löst dieses Problem. \begin{definition} +Eine {\em Beschriftung} +eines gerichteten oder ungerichteten Graphen $G=(V,E)$ +mit Elementen der Menge $L$, den Labels, +ist eine Abbildung $l\colon E\to L$. +\index{Beschriftung}% +\end{definition} + +Einen gerichteten, beschrifteten Graphen können wir gleichwertig +statt mit einer Beschriftungsabbildung $l$ auch dadurch erhalten, +dass wir Kanten als Tripel betrachten, die ausser den Knoten auch +noch den Wert der Beschriftung enthalten. + +\begin{definition} +\label{buch:graphen:def:beschriftetergraphgerichtet} Ein gerichteter Graph mit beschrifteten Kanten ist eine Menge $V$ von Knoten und eine Menge von beschrifteten Kanten der Form \[ @@ -381,63 +392,104 @@ E \{ (a,b,l)\in V^2\times L\;|\; \text{Eine Kante mit Beschriftung $l$ führt vo Die Menge $L$ enthält die möglichen Beschriftungen der Kanten. \end{definition} +Diese Definition gestattet, dass zwischen zwei Knoten $a$ und $e$ +mehrere Kanten vorhanden sind, die sich durch die Beschriftung +unterscheiden. + +\subsubsection{Inzidenzmatrix} +Die Adjazenzmatrix bildet nur die Nachbarschaftsbeziehung ab, +sie sagt nichts aus über die ``Qualität'' der Verbindung, die durch +die Beschriftung einer Kante angezeigt wird. +Nach Definition~\ref{buch:graphen:def:beschriftetergraphgerichtet} +ist es auch möglich, dass mehrere Kanten von $a$ nach $e$ führen, +die Adjazenzmatrix kann diese ebenfalls nicht unterscheiden. +Die {\em Inzidenzmatrix} +löst dieses Problem. +\index{Inzidenzmatrix}% +Dazu werden zunächst zusätzlich die Kanten $1,\dots,m$ +numeriert, wobei Kanten mit verschiedenen Beschriftungen separat +gezählt werden. +Die Matrixeinträge +\[ +b_{i\!j} = \begin{cases} +1\qquad&\text{Knoten $i$ ist ein Endpunkt von Kante $j$} +\\ +0\qquad&\text{sonst} +\end{cases} +\] +der Inzidenzmatrix $B(G)$ +stellen die Beziehung zwischen Kanten und Knoten her. Für einen gerichteten Graphen wird in der Inzidenzmatrix für den Anfangspunkt einer Kante $-1$ eingetragen und für den Endpunkt $+1$. -% XXX Beispiel +Die Inzidenzmatrizen $B(G)$ für die Graphen der beiden Beispiele +in den Abbildungen~\ref{buch:graphen:fig:adjazenzu} und +\ref{buch:graphen:fig:adjazenzd} ist ebendort angegeben. \subsubsection{Inzidenzmatrix und Adjazenzmatrix} -Sei $B(G)$ die Inzidenzmatrix eines Graphen $G$. +Sei $B(G)$ die Inzidenzmatrix eines ungerichteten Graphen $G$. Die Spalten von $B(G)$ sind mit den Kanten des Graphen indiziert. Die Matrix $B(G)B(G)^t$ ist eine quadratische Matrix, deren Zeilen und Spalten mit den Knoten des Graphen indiziert sind. -In dieser Matrix geht die Informatione über die individuellen +In dieser Matrix geht die Information über die individuellen Kanten wieder verloren. Sie hat für $i\ne j$ die Einträge \begin{align*} -(B(G)B(G)^t)_{ij} +(B(G)B(G)^t)_{i\!j} &= \sum_{\text{$k$ Kante}} b_{ik}b_{jk} \\ &=\text{Anzahl der Kanten, die $i$ mit $j$ verbinden} \\ -&=a_{ij}. +&=a_{i\!j}. \end{align*} Die Adjazenzmatrix eines Graphen lässt sich also aus der Inzidenzmatrix berechnen. \subsubsection{Gradmatrix} \index{Gradmatrix}% -Die Diagonale von $B(G)B(G)^t$ enthält die Werte -\begin{align*} +Die Diagonale von $B(G)B(G)^t$ eines ungerichteten Graphen $G$ +enthält die Werte +\begin{align} (B(G)B(G)^t)_{ii} &= \sum_{\text{$k$ Kante}} b_{ik}^2 = \text{Anzahl Kanten, die im Knoten $i$ enden} -\end{align*} +\label{buch:graphen:eqn:gradmatrix} +\end{align} Der {\em Grad} eines Knoten eines Graphen ist die Anzahl der \index{Grad eines Knotens}% Kanten, die in diesem Knoten enden. -Die Diagonalmatrix die aus den Graden der Knoten besteht, heisst die +Die Diagonalmatrix, die aus den Graden der Knoten besteht, heisst die Gradmatrix $D(G)$ des Graphen. Es gilt daher $B(G)B(G)^t = A(G) + D(G)$. +Für Beispiele siehe die Abbildungen~\ref{buch:graphen:fig:adjazenzu} und +\ref{buch:graphen:fig:adjazenzd}. \subsubsection{Gerichtete Graphen} Für einen gerichteten Graphen ändert sich an der Diagonalen der Matrix $B(G)B(G)^t$ nichts. -Da es in einem gerichteten Graphen nur eine einzige Kante $k$ gibt, die zwei -Knoten $i$ und $j$ verbinden kann, muss das zugehörige -Ausserdiagonalelement -\[ -a_{ij} -=b_{ik}b_{jk} +Sei $k$ die Kante, die vom Knoten $j$ zum Knoten $i$ führt. +Die Einträge in der Inzidenzmatrix sind daher $b_{ik}=1$ und $b_{jk}=-1$. +Da es nur eine solche Kante gibt (der Graph ist nicht beschriftet), +ist $b_{ik}b_{jk}$ der einzige Term in der Summe, mit der das +Matrixelement +\begin{equation} +a_{i\!j} += +(B(G)B(G)^t)_{i\!j} += +\sum_{\kappa} b_{i\kappa}b_{j\kappa} += +b_{ik}b_{jk} = -1 -\] -sein. +\label{buch:graphen:eqn:ausserdiagonal} +\end{equation} +berechnet wird. Für einen gerichteten Graphen sind daher alle Ausserdiagonalelemente -negativ und es gilt $B(G)B(G)^t = D(G)-A(G)$. +negativ. \subsubsection{Anwendung: Netlist} Eine natürliche Anwendung eines gerichteten und beschrifteten Graphen @@ -451,52 +503,61 @@ welchen Nets verbunden werden müssen. Die Informationen in der Inzidenzmatrix werden also in einer Applikation zum Schaltungsentwurf in ganz natürlicher Weise erhoben. -\subsection{Die Adjazenzmatrix und Laplace-Matrix -\label{subsection:adjazenz-und-laplace-matrix}} -Die Beschreibung mit der Matrix~\eqref{buch:graphen:eqn:linkmatrix} -``vergisst'' den ``Namen'' der Kante, die eine Verbindung zwischen zwei -Knoten herstellt. -Damit ist sie keine geeignete Grundlage, um beschriftete Graphen einer -Matrixbeschreibung zuzuführen. -Eine solche muss eine Matrix verwenden, die nicht nur das Vorhandensein einer -Verbindung wiedergibt, sondern ausdrückt, welche Kante welche beiden -Knoten miteinander verbindet. -Dies führt zur sogenannten Adjazenzmatrix. +\subsection{Die Laplace-Matrix +\label{subsection:laplace-matrix}} +Will man ein elektrisches Netzwerk modellieren oder den Transport +von Wärme durch eine Gitterstruktur berechnen, dann muss man zwar den +Kanten des Netzwerks eine ``Stromrichtung'' geben um ausdrücken zu können, +in welche Richtung der Strom oder die Wärmeenergie fliesst. +Trotzdem gestattet man natürlich auch den Stromfluss in Gegenrichtung. + +Wir gehen also aus von einem ungerichteten Graphen $G$, aus dem +wir einen gerichteten Graphen $G'$ machen. +Zu jeder Kante $\{a,b\}$ von $G$ wählen wir genau eine der möglichen +Orientierungen $(a,b)$ oder $(b,a)$ im Graphen $G'$. +Aus der Inzidenzmatrix $B(G')$ lässt sich jetzt ein Operator konstruieren, +der für die Anwendungen besonders gut geeignet ist. \begin{definition} -\label{buch:def:adjazenz-matrix} -Ist $G=(V,E)$ ein gerichteter Graph mit $n=|G|$ Vertizes und $m=|E|$ Kanten, -dann ist die zugehörige {\em Adjazenzmatrix} $A=A(G)$ eine $n\times m$-Matrix. -In der Spalte $k$ wird der Anfangspunkt der Kante $k$ mit $-1$, der Endpunkt -mit $+1$ angezeigt, die übrigen Einträge sind $0$. -$A$ hat also die Matrixelemente +\label{buch:graphen:def:laplace-matrix} +Die {\em Laplace-Matrix} des Graphen $G$ ist +\[ +L(G) = B(G')B(G')^t, +\] +wobei $G'$ ein wie oben konstruierter gerichteter Graph ist. +\end{definition} + +Wir müssen uns davon überzeugen, dass diese Definition sinnvoll ist +und nicht etwa von der Wahl von $G'$ abhängt. +Diese klärt der folgende Satz. + +\begin{satz} +Die Laplace-Matrix eines ungerichteten Graphen $G$ ist \begin{equation} -a_{ik} -= -\begin{cases} --1&\qquad i=a(k)\\ -+1&\qquad i=e(k)\\ -\phantom{+}0&\qquad\text{sonst} -\end{cases} -\label{buch:eqn:ajazenz-matrix} +L(G) = D(G) - A(G) +\label{buch:graphen:eqn:laplace-definition} \end{equation} -\end{definition} +und somit insbesondere unabhängig von der Wahl des Graphen $G'$, +der für die Definition von $L(G)$ verwendet wurde. +\end{satz} -Der wesentliche Unterschied dieser Definition von der Matrix $G$ -liegt in der Bedeutung der Einträge. -Für $G$ drückt ein nicht verschwindendes Matrixelement das Vorhandensein -einer Kante aus, in $A$ ist es die Tatsache, dass in diesem Knoten -eine Kante beginnt oder endet. - -Es ist natürlich möglich, aus der Adjazenzmatrix auch die Link-Matrix -zu rekonstruieren. -Dazu muss für jedes Paar $(j,i)$ von Knoten festgestellt werden, -ob die Adjazenzmatrix eine entsprechende Verbindung enthält, also ob der -Vektor -\[ -k_{ji} = e_i - e_j -\] -als Spaltenvektor vorkommt, wobei die $e_i$ die $n$-dimensionalen -Standardbasisvektoren sind. +\begin{proof}[Beweis] +Aufgrund der Konstruktion des Graphen $G'$ sind die Diagonalelemente +der Laplace-Matrix +$L(G)=B(G')B(G')^t$ nach \eqref{buch:graphen:eqn:gradmatrix} genau +die Elemente der Gradmatrix $D(G)$. +Die ausserdiagonalen Elemente sind nach +\eqref{buch:graphen:eqn:ausserdiagonal} +genau dann, wenn es in $G$ eine Verbindung zwischen den beiden Knoten +gibt. +Dies sind die Elemente von $-A(G)$. +Damit ist die Formel +\eqref{buch:graphen:eqn:laplace-definition} +nachgewiesen. +\end{proof} +Die Laplace-Matrix tritt zum Beispiel als Diskretisation des Laplace-Operators +in partiellen Differentialgleichungen auf. +Sie ist die Basis für die Untersuchungen der spektralen Graphentheorie +in Abschnitt~\ref{buch:section:spektrale-graphentheorie}. diff --git a/buch/chapters/70-graphen/chapter.tex b/buch/chapters/70-graphen/chapter.tex index 530d96c..1fb61b6 100644 --- a/buch/chapters/70-graphen/chapter.tex +++ b/buch/chapters/70-graphen/chapter.tex @@ -9,41 +9,44 @@ \rhead{} Ein Graph ist eine Menge von Knoten, die untereinander mit Kanten verbunden sind. -Graphen können zum Beispiel verwendet werden um Netzwerke zu beschreiben, +\index{Graph}% +Graphen können zum Beispiel verwendet werden, um Netzwerke zu beschreiben, aber auch viele andere Datenstrukturen. \index{Graph}% -Die Knoten können einzelne Objekte beschreiben, die Kanten beschreiben +Die Knoten können einzelne Objekte darstellen, die Kanten entsprechen dann Beziehungen zwischen diesen Objekten. Graphen haben zwar nur eine eindimensionale Geometrie, sie können aber auch als -erste Approximation dreidimensionaler Objekte dienen. +erste Approximation höherdimensionaler geometrischer Strukturen dienen. Die Bedeutung des Graphenkozeptes wird unterstrichen von der Vielzahl -von Fragestellungen, die über Graphen gestellt, und der +von Fragestellungen, die über Graphen gestellt worden sind, und der zugehörigen Lösungsalgorithmen, die zu ihrer Beantwortung gefunden worden sind. Die Komplexitätstheorie hat sogar gezeigt, dass sich jedes diskrete +\index{Komplexitätstheorie}% Problem in ein Graphenproblem umformulieren lässt. \index{Komplexitätstheorie}% Das Problem, einen Stundenplan zu finden, der sicherstellt, dass +\index{Stundenplan}% alle Studierenden jedes Fach besuchen können, für die sie sich angemeldet haben, lässt sich zum Beispiel wie folgt als ein Graphenproblem formulieren. Die Fächer betrachten wir als Knoten des Graphen. -Für jedes Paar von Fächern ziehen wir eine Kante des Graphen, wenn +Für jedes Paar von Fächern ziehen wir eine Kante, wenn sich mindestens ein Studierender für beide Fächer angemeldet hat. Die Kante drückt aus, dass die beiden Fächer nicht zur gleichen Zeit geplant werden dürfen. Das Problem, einen Stundenplan zu finden, besteht jetzt darin, für -jedes Fach ein Zeitintervall zu finden, während dem es durchgeführt +jedes Fach ein Zeit\-intervall zu finden, während dem es durchgeführt werden soll. -\index{Stundenplan}% -Natürlich steht nur eine beschränkte Anzahl Zeitintervalle zur Verfügung -und benachbarte Knoten dürfen nicht ins gleiche Zeitintervall geplant -werden. +Natürlich steht nur eine beschränkte Anzahl Zeitintervalle zur Verfügung. +Benachbarte, also mit einer Kante verbundene Knoten dürfen nicht +ins gleiche Zeitintervall geplant werden. Das zugehörige abstrakte Graphenproblem heisst das Färbeproblem: \index{Färbeproblem}% -ist es möglich, mit einer beschränkten Anzahl von Farben die Knoten +ist es möglich, mit einer beschränkten Anzahl von Farben, oder im +vorliegenden Fall Zeitintervalle, die Knoten des Graphen so einzufärben, dass benachbarte Knoten niemals die gleiche Farbe haben. diff --git a/buch/chapters/70-graphen/images/adjazenzd.pdf b/buch/chapters/70-graphen/images/adjazenzd.pdf Binary files differindex dc3dd8f..146856c 100644 --- a/buch/chapters/70-graphen/images/adjazenzd.pdf +++ b/buch/chapters/70-graphen/images/adjazenzd.pdf diff --git a/buch/chapters/70-graphen/images/adjazenzd.tex b/buch/chapters/70-graphen/images/adjazenzd.tex index 5cef18e..81801d3 100644 --- a/buch/chapters/70-graphen/images/adjazenzd.tex +++ b/buch/chapters/70-graphen/images/adjazenzd.tex @@ -10,12 +10,14 @@ \usepackage{txfonts} \usepackage{pgfplots} \usepackage{csvsimple} +\usepackage{color} \usetikzlibrary{arrows,intersections,math,calc} \begin{document} \def\skala{1} \begin{tikzpicture}[>=latex,thick,scale=\skala] \def\r{1.8} +\def\R{\bgroup\color{red}0\egroup} \begin{scope} \coordinate (A) at ({\r*cos(0*72)},{\r*sin(0*72)}); @@ -71,15 +73,16 @@ B(G) \end{pmatrix*}$}; \end{scope} + \begin{scope}[xshift=3cm,yshift=1.1cm] \node at (0,0) [right] {$\displaystyle A(G) = \begin{pmatrix*}[r] - 0& 1& 1& 0& 1\\ - 1& 0& 1& 1& 0\\ - 1& 1& 0& 1& 0\\ - 0& 1& 1& 0& 1\\ + 0&\R&\R& 0&\R\\ + 1& 0&\R&\R& 0\\ + 1& 1& 0&\R& 0\\ + 0& 1& 1& 0&\R\\ 1& 0& 0& 1& 0 \end{pmatrix*}, \quad @@ -90,7 +93,7 @@ D(G) 0&3&0&0&0\\ 0&0&3&0&0\\ 0&0&0&3&0\\ -0&0&0&0&1 +0&0&0&0&2 \end{pmatrix*} $}; \end{scope} diff --git a/buch/chapters/70-graphen/images/adjazenzu.pdf b/buch/chapters/70-graphen/images/adjazenzu.pdf Binary files differindex d3f255e..6002cbf 100644 --- a/buch/chapters/70-graphen/images/adjazenzu.pdf +++ b/buch/chapters/70-graphen/images/adjazenzu.pdf diff --git a/buch/chapters/70-graphen/spektral.tex b/buch/chapters/70-graphen/spektral.tex index 5fb3056..b718b65 100644 --- a/buch/chapters/70-graphen/spektral.tex +++ b/buch/chapters/70-graphen/spektral.tex @@ -6,7 +6,7 @@ \section{Spektrale Graphentheorie \label{buch:section:spektrale-graphentheorie}} \rhead{Spektrale Graphentheorie} -Die Adjazenz-Matrix, die Grad-Matrix und damit natürlich auch +Die Adjazenzmatrix, die Gradmatrix und damit natürlich auch die Laplace-Matrix codieren alle wesentliche Information eines ungerichteten Graphen. Sie operiert auf Vektoren, die für jeden Knoten des Graphen eine @@ -18,11 +18,11 @@ der chromatischen Zahl eines Graphen illustrieren. \subsection{Chromatische Zahl und Unabhängigkeitszahl \label{buch:subsection:chromatische-zahl}} -Der Grad eines Knotens ist ein mass dafür, wie stark ein Graph +Der Grad eines Knotens ist ein Mass dafür, wie stark ein Graph ``vernetzt'' ist. Je höher der Grad, desto mehr direkte Verbindungen zwischen Knoten gibt es. -Noch etwas präziser können diese Idee die beiden mit Hilfe der -chromatischen zahl und der Unabhängigkeitszahl erfasst werden. +Noch etwas präziser kann diese Idee die mit Hilfe der +chromatischen Zahl und der Unabhängigkeitszahl erfasst werden. \begin{definition} Die {\em chromatische Zahl} $\operatorname{chr}G$ eines Graphen $G$ ist @@ -39,9 +39,14 @@ ist die maximale Anzahl Knoten einer unabhängigen Menge. \index{Unabhängigkeitszahl} \end{definition} +\begin{beispiel} +Abbildung~\ref{buch:graphen:fig:chrindpeterson} bestimmt die chromatische +Zahl und die Unabhängigkeitszahl im Beispiel des Peterson-Graphen. +\end{beispiel} + Zwischen der chromatischen Zahl und der Unabhängigkeitszahl eines Graphen muss es einen Zusammenhang geben. -Je mehr Verbingungen es im Graphen gibt, desto grösser wird die chromatische +Je mehr Verbindungen es im Graphen gibt, desto grösser wird die chromatische Zahl. Gleichzeitig wird es schwieriger für Mengen von Knoten, unabhängig zu sein. @@ -53,7 +58,7 @@ $\operatorname{chr}G\cdot\operatorname{ind}G\ge n$. \begin{proof}[Beweis] Eine minimale Färbung des Graphen mit $\operatorname{chr}G$ Farben -teilt die Knoten in $\operatorname{chr}G$ Mengen $V_f$ von Knoten mit +teilt die Knoten in $\operatorname{chr}G$ disjunkte Mengen $V_f$ von Knoten mit gleicher Farbe $f$ ein. Da diese Mengen einfarbig sind, sind sie unabhängig, enthalten also höchstens so viele Knoten, wie die Unabhängigkeitszahl erlaubt, @@ -109,16 +114,17 @@ der grossen Knoten, mit denen sie verbunden sind. \begin{beispiel} Der Peterson-Graph $P$ von Abbildung~\ref{buch:graphen:fig:chrindpeterson} -hat chromatische Zahl $\operatorname{chr}P=3$ und unabhängigkeitszahl +hat chromatische Zahl $\operatorname{chr}P=3$ und Unabhängigkeitszahl $\operatorname{ind}P=4$. Die Ungleichung von Satz~\ref{buch:satz:chrind} ist erfüllt, sogar als Ungleichung: $\operatorname{chr}P\cdot\operatorname{ind}P=3\cdot 4=12>10=n$. \end{beispiel} -Nach Definition ist Unabhängigkeitszahl ein Mass für die Grösse einer +Nach Definition ist die Unabhängigkeitszahl ein Mass für die Grösse einer unabhängigen Menge von Punkten. Der Beweis von Satz~\ref{buch:satz:chrind} zeigt, dass man sich die -chromatische Zahl als ein Mass dafür, wieviele solche anabhängige +chromatische Zahl als ein Mass dafür vorstellen kann, +wieviele solche unabhängige Mengen in einem Graphen untergebracht werden können. % @@ -133,11 +139,13 @@ Einfärbung des ganzen Graphen reichen. Genau dies garantiert jedoch der folgende Satz. \begin{definition} -Der maximale Grad +Der {\em maximale Grad} \( \max_{v\in V} \deg(v) \) +eines ungerichteten Graphen wird mit $d$ bezeichnet. +\index{maximaler Grad}% \end{definition} \begin{satz} @@ -153,11 +161,11 @@ Ein Graph mit nur einem Knoten hat keine Kanten, der maximale Grad ist daher $0$ und $d+1=1$ Farbe reicht auch tatsächlich zur Einfärbung des einen Knotens. -Wir nehmen jetzt an, die Behaupt sei für Graphen mit $n-1$ Knoten bereits +Wir nehmen jetzt an, die Behauptung sei für Graphen mit $n-1$ Knoten bereits bewiesen, ein Graph $G'$ mit $n-1$ Knoten und maximalem Grad $d'$ erfüllt also die Ungleichung $\operatorname{chr}G'\le d'+1$. -Wir wählen jetzt einen beleibigen Knoten $v$ des Graphen $G$ und bilden +Wir wählen jetzt einen beliebigen Knoten $v$ des Graphen $G$ und bilden den Graphen $G'$, der aus $G$ entsteht, indem man den Knoten $v$ entfernt: $G'=G\setminus\{v\}$. Der maximale Grad $d'$ von $G'$ kann dabei nicht grösser werden, es ist @@ -177,7 +185,7 @@ ist für alle Begriffe anwendbar, die sich bei der Bildung eines Untergraphen auf ``monotone'' Art ändern. Die chromatische Zahl eines Untergraphen ist höchstens so gross wie die des ganzen Graphen. -Dann kann man eine Ungleichung für grosse Graphen schrittweise aus +Daher kann man eine Ungleichung für grosse Graphen schrittweise aus entsprechenden Ungleichungen für die kleineren Teilgraphen gewinnen. Ziel der folgenden Abschnitte ist zu zeigen, dass sich eine Grösse mit ähnlichen Eigenschaften aus dem Eigenwertspektrum der Adjazenzmatrix @@ -210,7 +218,14 @@ Somit ist \frac{1}{n}(d_1+\dots+d_n) \label{buch:graphen:eqn:AUdavg} \end{equation} -der mittlere Grad, der mit $\overline{d}$ bezeichnet werden soll. +der {\em mittlere Grad}, der mit $\overline{d}$ bezeichnet werden soll. +Da die Kanten eines Graphen zusammen $2\cdot|E|$ Enden haben, kann +er kann auch als +\[ +\overline{d}=\frac{2\cdot|E|}{|V|} +\] +berechnet werden. +\index{mittlerer Grad}% Da $A(G)$ eine symmetrische Matrix ist, ist $A(G)$ diagonalisierbar, die Eigenwerte sind also alle reell. @@ -232,20 +247,23 @@ ist. In Abschnitt~\ref{buch:section:positive-vektoren-und-matrizen} des nächsten Kapitels wird die Perron-Frobenius-Theorie positiver +\index{Perron-Frobenius-Theorie}% +\index{positive Matrix}% Matrizen vorgestellt, welche einer Reihe interessanter Aussagen über den betragsgrössten Eigenwert und den zugehörigen Eigenvektor macht. -Die Adjazenz-Matrix ist eine nichtnegative Matrix und $\alpha_{\text{max}}$ +Die Adjazenzmatrix ist eine nichtnegative Matrix und $\alpha_{\text{max}}$ ist der grösste Eigenwert, also genau die Grösse, auf die die Sätze~\ref{buch:wahrscheinlichkeit:satz:perron-frobenius} -und \label{buch:wahrscheinlichkeit:satz:perron-frobenius2} +und \ref{buch:wahrscheinlichkeit:satz:perron-frobenius2} anwendbar sind. Dazu muss die Matrix allerdings primitiv sein, was gleichbedeutend +\index{primitive Matrix}% ist damit, dass der Graph zusammenhängend ist. Im folgenden soll dies daher jeweils angenommen werden. \begin{satz} -Ist $G$ ein zusammenhänger Graph mit $n$ Knoten und maximalem Grad $d$, +Ist $G$ ein zusammenhängender Graph mit $n$ Knoten und maximalem Grad $d$, dann gilt \[ \frac1n\sum_{v\in V} \deg(v) @@ -266,8 +284,8 @@ ist $f$ ein positiver Vektor mit der Eigenschaft $A(G)f=\alpha_{\text{max}}f$. Der Eigenvektor $f$ ist eine Funktion auf den Knoten des Graphen, die $v$-Komponente des Vektors $f$ für einen Vertex $v\in V$ ist $f(v)$. Die Eigenvektoreigenschaft bedeutet $(A(G)f)(v)=\alpha_{\text{max}} f(v)$. -Die Adjazenzmatrix $A(G)$ enthält in Zeile $v$ Einsen genau für diejenigen -Knoten $u\in V$, die zu $v$ benachbart sind. +Die Adjazenzmatrix $A(G)$ enthält in Zeile $v$ genau für diejenigen +Knoten $u\in V$ Einsen, die zu $v$ benachbart sind. Schreiben wir $u\sim v$ für die Nachbarschaftsrelation, dann ist \[ (A(G)f)(v) @@ -278,9 +296,10 @@ Die Summe der Komponenten $A(G)f$ kann man erhalten durch Multiplikation von $A(G)f$ mit einem Zeilenvektor $U^t$ aus lauter Einsen, also \begin{equation} \begin{aligned} -\sum_{v\in V}\sum_{u\sim v}f(v) +{\color{red} +\sum_{v\in V}}\sum_{u\sim v}f(v) &= -U^tA(G)f +{\color{red}U^t}A(G)f = (U^tA(G))f = @@ -356,7 +375,7 @@ f'(v)&\qquad v\in V'\\ \] konstruieren, der auf ganz $V$ definiert ist. -Die Vektoren $f'$ und $g$ haben die gleichen Komponenten, also ist auch +Die Vektoren $f'$ und $g$ haben auf $V'$ die gleichen Komponenten, also ist auch $\langle f',f'\rangle = \langle g,g\rangle$. Die Matrixelemente von $A(G')$ und $A(G)$ auf gemeinsamen Knoten $u,v\in V'$ erfüllen $A(G')_{uv}\le A(G)_{uv}$, da jede Kante von $G'$ auch in $G$ ist. @@ -385,6 +404,8 @@ $\langle A(G)h,h\rangle/\langle h,h\rangle$ für alle Vektoren $h\ne 0$ ist. % \subsection{Chromatische Zahl und $\alpha_{\text{max}}$: Der Satz von Wilf \label{buch:subsection:chr-und-alpha-max}} +\index{Satz von Wilf}% +\index{Wilf, Satz von}% Die in Satz~\ref{buch:graphen:satz:amaxuntergraph} beschriebene Eigenschaft von $\alpha_{\text{max}}$ beim Übergang zu einem Untergraphen ermöglich jetzt, eine besser Abschätzung für die chromatische Zahl @@ -407,13 +428,15 @@ bewiesen werden. Ein Graph mit nur einem Knoten hat die $0$-Matrix als Adjazenzmatrix, der maximale Eigenwert ist $\alpha_{\text{max}}=0$, und tatsächlich reicht $\alpha_{\text{max}}+1=1$ Farbe, um den einen Knoten einzufärben. +Dies ist die Induktionsverankerung. -Wir nehmen jetzt an, der Satz sei für Graphen mit $n-1$ Knoten bereits +Im Sinne der Induktionsannahme +nehmen wir jetzt an, der Satz sei für Graphen mit $n-1$ Knoten bereits beweisen. Wir müssen dann zeigen, dass der Satz dann auch für Graphen mit $n$ Knoten gilt. -Sei $v\in V$ ein Knoten minimalen Grades und $G'=G\setminus{v}$ der +Sei $v\in V$ ein Knoten minimalen Grades und $G'=G\setminus\{v\}$ der Untergraph, der entsteht, wenn der Knoten $v$ entfernt wird. Da $G'$ genau $n-1$ Knoten hat, gilt der Satz von Wilf für $G'$ und daher kann $G'$ mit höchstens @@ -443,7 +466,7 @@ maximale Grad. \end{figure} \begin{beispiel} -Der Graph in Abbildung~\ref{buch:graphen:fig:wilfexample} 12 Kanten und 9 +Der Graph in Abbildung~\ref{buch:graphen:fig:wilfexample} hat 12 Kanten und 9 Knoten, daher ist $\overline{d}\le \frac{24}{9}$. Der maximale Grad ist $4$ und durch explizite Rechnung mit Hilfe zum Beispiel von Octave ergibt, dass $\alpha_{\text{max}}\approx 2.9565$. diff --git a/buch/chapters/70-graphen/wavelets.tex b/buch/chapters/70-graphen/wavelets.tex index 8baa88c..2b9f29b 100644 --- a/buch/chapters/70-graphen/wavelets.tex +++ b/buch/chapters/70-graphen/wavelets.tex @@ -270,7 +270,7 @@ $\lambda_k$, $k=1,\dots,n$ h(\lambda_k) + \sum_ig(a_i\lambda_k)=1 \] gilt. -Für beleibige Funktionen $g$ und $h$ kann man nicht davon ausgehen, +Für beliebige Funktionen $g$ und $h$ kann man nicht davon ausgehen, aber man kann erwarten. Man muss daher zusätzlich verlangen, dass \[ diff --git a/buch/chapters/references.bib b/buch/chapters/references.bib index 977bf81..fb88d09 100644 --- a/buch/chapters/references.bib +++ b/buch/chapters/references.bib @@ -152,3 +152,13 @@ abstract = "In this paper, we present Google, a prototype of a large-scale searc language = {german}, } +@buch{skript:brualdi, + title = {The mutually beneficial relationships of graphs and matrices}, + author = {Richard A. Brualdi}, + series = {CBMS Regionals conference series in mathematics}, + number = {115}, + publisher = {American Mathematical Society}, + isbn = {978-0-8218-5315-3}, + year = 2011, + language = {english} +} |
