From c4468301f6dab4099c485349a3fd97bd1baf3282 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Andreas=20M=C3=BCller?= Date: Thu, 9 Sep 2021 09:11:54 +0200 Subject: typos --- buch/chapters/40-eigenwerte/grundlagen.tex | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'buch/chapters') diff --git a/buch/chapters/40-eigenwerte/grundlagen.tex b/buch/chapters/40-eigenwerte/grundlagen.tex index 91294f1..08f2105 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} -- cgit v1.2.1 From 29472595454b829e40e430f533dddf9ae21308cb Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Andreas=20M=C3=BCller?= Date: Thu, 9 Sep 2021 09:38:50 +0200 Subject: typo --- buch/chapters/30-endlichekoerper/wurzeln.tex | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'buch/chapters') 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} -- cgit v1.2.1 From 15b6405261f267d24c509ed8f356d4eaffda1794 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Andreas=20M=C3=BCller?= Date: Thu, 9 Sep 2021 16:25:47 +0200 Subject: Kapitel 7 --- buch/chapters/10-vektorenmatrizen/ringe.tex | 2 +- buch/chapters/40-eigenwerte/eigenwerte.tex | 2 +- buch/chapters/40-eigenwerte/grundlagen.tex | 2 +- buch/chapters/60-gruppen/chapter.tex | 26 ++- buch/chapters/60-gruppen/images/Makefile | 8 +- buch/chapters/60-gruppen/images/c60.jpg | Bin 0 -> 142174 bytes buch/chapters/60-gruppen/images/nichtkomm.pdf | Bin 0 -> 157193 bytes buch/chapters/60-gruppen/images/nichtkomm.tex | 68 ++++++ buch/chapters/60-gruppen/images/rodriguez.jpg | Bin 0 -> 168776 bytes buch/chapters/60-gruppen/images/rodriguez.pdf | Bin 0 -> 181775 bytes buch/chapters/60-gruppen/images/rodriguez.tex | 45 ++++ buch/chapters/60-gruppen/lie-algebren.tex | 289 ++++++++++++++++---------- buch/chapters/60-gruppen/lie-gruppen.tex | 287 +++++++++++++++++-------- buch/chapters/60-gruppen/symmetrien.tex | 104 +++++---- 14 files changed, 590 insertions(+), 243 deletions(-) create mode 100644 buch/chapters/60-gruppen/images/c60.jpg create mode 100644 buch/chapters/60-gruppen/images/nichtkomm.pdf create mode 100644 buch/chapters/60-gruppen/images/nichtkomm.tex create mode 100644 buch/chapters/60-gruppen/images/rodriguez.jpg create mode 100644 buch/chapters/60-gruppen/images/rodriguez.pdf create mode 100644 buch/chapters/60-gruppen/images/rodriguez.tex (limited to 'buch/chapters') 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/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 08f2105..b41da1d 100644 --- a/buch/chapters/40-eigenwerte/grundlagen.tex +++ b/buch/chapters/40-eigenwerte/grundlagen.tex @@ -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/chapter.tex b/buch/chapters/60-gruppen/chapter.tex index 3b1abc1..872a241 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. 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 new file mode 100644 index 0000000..2bc77e7 Binary files /dev/null and b/buch/chapters/60-gruppen/images/c60.jpg differ diff --git a/buch/chapters/60-gruppen/images/nichtkomm.pdf b/buch/chapters/60-gruppen/images/nichtkomm.pdf new file mode 100644 index 0000000..8b66ea3 Binary files /dev/null and b/buch/chapters/60-gruppen/images/nichtkomm.pdf differ 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 new file mode 100644 index 0000000..5c49700 Binary files /dev/null and b/buch/chapters/60-gruppen/images/rodriguez.jpg differ diff --git a/buch/chapters/60-gruppen/images/rodriguez.pdf b/buch/chapters/60-gruppen/images/rodriguez.pdf new file mode 100644 index 0000000..d947fe1 Binary files /dev/null and b/buch/chapters/60-gruppen/images/rodriguez.pdf differ 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..860f27d 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} = @@ -184,7 +188,7 @@ $\operatorname{SO}(2)\subset \operatorname{GL}_2(\mathbb{R})$} Drehungen der Ebene können in einer orthonormierten Basis durch Matrizen der Form \[ -D_{\alpha} +R_{\alpha} = \begin{pmatrix} \cos\alpha&-\sin\alpha\\ @@ -196,36 +200,39 @@ 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 +246,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 +278,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 +313,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 +346,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 +387,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 +419,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 +458,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 Date: Fri, 10 Sep 2021 11:34:57 +0200 Subject: =?UTF-8?q?neue=20=C3=9Cbungsaufgabe=20hinzugef=C3=BCgt?= MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit --- buch/chapters/60-gruppen/Makefile.inc | 3 + buch/chapters/60-gruppen/chapter.tex | 1 + buch/chapters/60-gruppen/lie-gruppen.tex | 5 +- buch/chapters/60-gruppen/uebungsaufgaben/6003.tex | 134 ++++++++++++++++++++++ 4 files changed, 141 insertions(+), 2 deletions(-) create mode 100644 buch/chapters/60-gruppen/uebungsaufgaben/6003.tex (limited to 'buch/chapters') 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 872a241..4f2fb5a 100644 --- a/buch/chapters/60-gruppen/chapter.tex +++ b/buch/chapters/60-gruppen/chapter.tex @@ -61,5 +61,6 @@ Zusammenhangs darzustellen. \begin{uebungsaufgaben} \uebungsaufgabe{6002} \uebungsaufgabe{6001} +\uebungsaufgabe{6003} \end{uebungsaufgaben} diff --git a/buch/chapters/60-gruppen/lie-gruppen.tex b/buch/chapters/60-gruppen/lie-gruppen.tex index 860f27d..94df38e 100644 --- a/buch/chapters/60-gruppen/lie-gruppen.tex +++ b/buch/chapters/60-gruppen/lie-gruppen.tex @@ -187,14 +187,15 @@ 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 -\[ +\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})$. 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} -- cgit v1.2.1 From fcfcc3740ba9ed56ae4f371d06ae09ebc6a38fc6 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Andreas=20M=C3=BCller?= Date: Fri, 10 Sep 2021 15:32:38 +0200 Subject: Kapitel 8.1-8.3 --- buch/chapters/70-graphen/beschreibung.tex | 321 +++++++++++++++----------- buch/chapters/70-graphen/chapter.tex | 25 +- buch/chapters/70-graphen/images/adjazenzd.pdf | Bin 23490 -> 23517 bytes buch/chapters/70-graphen/images/adjazenzd.tex | 13 +- buch/chapters/70-graphen/images/adjazenzu.pdf | Bin 21744 -> 21744 bytes buch/chapters/70-graphen/spektral.tex | 73 ++++-- buch/chapters/70-graphen/wavelets.tex | 2 +- buch/chapters/references.bib | 10 + 8 files changed, 272 insertions(+), 172 deletions(-) (limited to 'buch/chapters') 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 index dc3dd8f..146856c 100644 Binary files a/buch/chapters/70-graphen/images/adjazenzd.pdf and b/buch/chapters/70-graphen/images/adjazenzd.pdf differ 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 index d3f255e..6002cbf 100644 Binary files a/buch/chapters/70-graphen/images/adjazenzu.pdf and b/buch/chapters/70-graphen/images/adjazenzu.pdf differ 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} +} -- cgit v1.2.1