diff options
Diffstat (limited to '')
23 files changed, 1319 insertions, 853 deletions
diff --git a/buch/chapters/05-zahlen/ganz.tex b/buch/chapters/05-zahlen/ganz.tex index d86e225..7e0ec8c 100644 --- a/buch/chapters/05-zahlen/ganz.tex +++ b/buch/chapters/05-zahlen/ganz.tex @@ -67,7 +67,7 @@ Zahlen mit der Eigenschaft a+b' = a'+b. \] Man nennt eine solche Menge eine {\em Äquivalenzklasse} der Relation $\sim$. -\index{Äquivalenzklasse} +\index{Aquivalenzklasse@Äquivalenzklasse} Die Menge $\mathbb{Z}$ der {\em ganzen Zahlen} ist die Menge aller solchen \index{ganze Zahlen}% Äquivalenzklassen. diff --git a/buch/chapters/05-zahlen/komplex.tex b/buch/chapters/05-zahlen/komplex.tex index 0f7e7f7..17f6e16 100644 --- a/buch/chapters/05-zahlen/komplex.tex +++ b/buch/chapters/05-zahlen/komplex.tex @@ -287,6 +287,7 @@ beliebige algebraische Gleichung lösbar geworden ist. Dies ist der Inhalt des Fundamentalsatzes der Algebra. \begin{satz}[Fundamentalsatz der Algebra] +\label{buch:zahlen:satz:fundamentalsatz} \index{Fundamentalsatz der Algebra}% Jede algebraische Gleichung der Form \[ diff --git a/buch/chapters/05-zahlen/natuerlich.tex b/buch/chapters/05-zahlen/natuerlich.tex index 4036327..8c51346 100644 --- a/buch/chapters/05-zahlen/natuerlich.tex +++ b/buch/chapters/05-zahlen/natuerlich.tex @@ -242,6 +242,24 @@ n+1&= n \cup \{n\} = \{0,\dots,n-1\} \cup \{n\} = \{0,1,\dots,n\} \\ &\phantom{n}\vdots \end{align*} +Die Menge $n+1$ besteht also aus den $n+1$ Zahlen von $0$ bis $n$. + +Für spätere Verwendung in Kapitel~\ref{buch:chapter:permutationen} +definieren wir hier auch noch eine weiter Art von Standardteilmengen +von $\mathbb{N}$. + +\begin{definition} +\label{buch:zahlen:def:[n]} +Die Menge $[n]\subset \mathbb{N}$ ist definiert durch +\[ +[n] = \begin{cases} +\{1,2,\dots,n\}&\qquad \text{für $n>0$}\\ +\emptyset&\qquad\text{für $n=0$} +\end{cases} +\] +\end{definition} + +Jede der Mengen $[n]$ hat genau $n$ Elemente: $|[n]|=n$. \subsubsection{Natürliche Zahlen als Äquivalenzklassen} Im vorangegangenen Abschnitt haben wir die natürlichen Zahlen aus @@ -264,7 +282,7 @@ Der Vorteil dieser Definition ist, dass sie die früher definierten natürlichen Zahlen nicht braucht, diese werden jetzt erst konstruiert. Dazu fassen wir in der Menge aller endlichen Mengen die gleich mächtigen Mengen zusammen, bilden also die Äquivalenzklassen der Relation $\sim$. -\index{Äquivalenzklasse}% +\index{Aquivalenzklasse@Äquivalenzklasse}% Der Vorteil dieser Sichtweise ist, dass die natürlichen Zahlen ganz explizit als die Anzahlen von Elementen einer endlichen Menge entstehen. diff --git a/buch/chapters/10-vektorenmatrizen/gruppen.tex b/buch/chapters/10-vektorenmatrizen/gruppen.tex index febf726..741a871 100644 --- a/buch/chapters/10-vektorenmatrizen/gruppen.tex +++ b/buch/chapters/10-vektorenmatrizen/gruppen.tex @@ -205,6 +205,7 @@ Für eine Abbildung zwischen Gruppen heisst dies, dass die Verknüpfung, das neutrale Element und die Inverse respektiert werden müssen. \begin{definition} +\label{buch:gruppen:def:homomorphismus} Ein Abbildung $\varphi\colon G\to H$ zwischen Gruppen heisst ein {\em Homomorphismus}, wenn $\varphi(g_1g_2)=\varphi(g_1)\varphi(g_2)$ für alle $g_1,g_2\in G$ gilt. diff --git a/buch/chapters/10-vektorenmatrizen/linear.tex b/buch/chapters/10-vektorenmatrizen/linear.tex index ba89266..70c1f9c 100755 --- a/buch/chapters/10-vektorenmatrizen/linear.tex +++ b/buch/chapters/10-vektorenmatrizen/linear.tex @@ -974,6 +974,7 @@ berechnet werden, wobei die $(n-1)\times(n-1)$-Matrix $A_{i\!j}$ die Matrix $A$ ist, aus der man Zeile $i$ und Spalte $j$ entfernt hat. $A_{i\!j}$ heisst ein {\em Minor} der Matrix $A$. +\label{buch:linear:def:minor} \index{Minor einer Matrix}% \end{enumerate} diff --git a/buch/chapters/10-vektorenmatrizen/ringe.tex b/buch/chapters/10-vektorenmatrizen/ringe.tex index 3b2780a..1149e29 100644 --- a/buch/chapters/10-vektorenmatrizen/ringe.tex +++ b/buch/chapters/10-vektorenmatrizen/ringe.tex @@ -173,9 +173,9 @@ $M_2(\mathbb{Z})$. \subsubsection{Einheiten} In einem Ring mit Eins sind normalerweise nicht alle von $0$ verschiedenen Elemente intertierbar. -Die Menge der von $0$ verschiedenen Elemente in $R$ wir mit $R^*$ +Die Menge der von $0$ verschiedenen Elemente in $R$ wir mit $R^*=R\setminus\{0\}$ bezeichnet. -\index{$R^*$}% +\index{R*@$R^*$}% Die Menge der invertierbaren Elemente verdient einen besonderen Namen. \begin{definition} diff --git a/buch/chapters/10-vektorenmatrizen/skalarprodukt.tex b/buch/chapters/10-vektorenmatrizen/skalarprodukt.tex index b249d0d..f89da33 100644 --- a/buch/chapters/10-vektorenmatrizen/skalarprodukt.tex +++ b/buch/chapters/10-vektorenmatrizen/skalarprodukt.tex @@ -505,35 +505,36 @@ g_{i\!j} \overline{g}_{ji} \quad 1\le i,j\le n. \] -Sie ist nicht mehr symmetrisch, aber selbstadjungiert, gemäss +Sie ist nicht mehr symmetrisch, aber hermitesch, gemäss der folgenden Definition. \begin{definition} -\label{buch:grundlagen:definition:selstadjungiert} +\label{buch:grundlagen:definition:hermitesch} Sei $A$ eine komplexe Matrix mit Einträgen $a_{i\!j}$, dann ist $\overline{A}$ die Matrix mit komplex konjugierten Elementen $\overline{a}_{i\!j}$. Die {\em adjungierte} Matrix ist $A^*=\overline{A}^t$. \index{adjungiert}% -Eine Matrix heisst {\em selbstadjungiert}, wenn $A^*=A$. -\index{selbstadjungiert}% +Eine Matrix heisst {\em hermitesch}, wenn $A^*=A$. +\index{hermitesch}% +Sie heisst {\em antihermitesch}, wenn $A^*=-A$. \end{definition} -\subsection{Symmetrische und selbstadjungierte Abbilungen -\label{buch:subsection:symmetrisch-und-selbstadjungiert}} -In Definition~\ref{buch:grundlagen:definition:selstadjungiert} -wurde der Begriff der selbstadjungierten Matrix basierend +\subsection{Selbstadjungierte Abbilungen +\label{buch:subsection:selbstadjungiert}} +In Definition~\ref{buch:grundlagen:definition:hermitesch} +wurde der Begriff der hermiteschen Matrix basierend eingeführt. Als Eigenschaft einer Matrix ist diese Definition notwendigerweise abhängig von der Wahl der Basis. Es ist nicht unbedingt klar, dass derart definierte Eigenschaften als von der Basis unabhängige Eigenschaften betrachtet werden können. Ziel dieses Abschnitts ist, Eigenschaften wie Symmetrie oder -Selbstadjungiertheit auf basisunabhängige Eigenschaften von +hermitesch auf basisunabhängige Eigenschaften von linearen Abbildungen in einem Vektorraum $V$ mit Skalarprodukt $\langle\;,\;\rangle$ zu verstehen. -\subsubsection{Symmetrische Abbildungen} +\subsubsection{Reelle selbstadjungierte Abbildungen} Sei $f\colon V\to V$ eine lineare Abbildung. In einer Basis $\{b_1,\dots,b_n\}\subset V$ wird $f$ durch eine Matrix $A$ beschrieben. @@ -553,17 +554,17 @@ a_{ji} \] ist. Daraus leitet sich jetzt die basisunabhängige Definition einer -symmetrischen Abbildung ab. +selbstadjungierten Abbildung ab. \begin{definition} -Eine lineare Abbildung $f\colon V\to V$ heisst {\em symmetrisch}, wenn +Eine lineare Abbildung $f\colon V\to V$ heisst {\em selbstadjungiert}, wenn $\langle x,Ay\rangle=\langle Ax,y\rangle$ gilt für beliebige Vektoren $x,y\in V$. -\index{symmetrische Abbildung}% +\index{selbstadjungierte Abbildung}% \end{definition} Für $V=\mathbb{R}^n$ und das Skalarprodukt $\langle x,y\rangle=x^ty$ -erfüllt eine symmetrische Abbildung mit der Matrix $A$ die Gleichung +erfüllt eine selbstadjungierte Abbildung mit der Matrix $A$ die Gleichung \[ \left. \begin{aligned} @@ -580,15 +581,16 @@ x^tAy x^tA^ty = x^tAy\quad\forall x,y\in\mathbb{R}^n, \] was gleichbedeutend ist mit $A^t=A$. -Der Begriff der symmetrischen Abbildung ist also eine natürliche +Der Begriff der selbstadjungierten Abbildung ist also eine natürliche Verallgemeinerung des Begriffs der symmetrischen Matrix. -\subsubsection{Selbstadjungierte Abbildungen} +\subsubsection{Selbstadjungierte komplexe Abbildungen} In einem komplexen Vektorraum ist das Skalarprodukt nicht mehr bilinear und symmetrisch, sondern sesquilinear und konjugiert symmetrisch. \begin{definition} -Eine lineare Abbildung $f\colon V\to V$ heisst {\em selbstadjungiert}, +Eine lineare Selbstabbildung $f\colon V\to V$ eines komplexen +Vektorraumes heisst {\em selbstadjungiert}, wenn $\langle x,fy\rangle=\langle fx,y\rangle$ für alle $x,y\in\mathbb{C}$. \index{selbstadjungiert}% \end{definition} diff --git a/buch/chapters/30-endlichekoerper/galois.tex b/buch/chapters/30-endlichekoerper/galois.tex index 5189dec..7ffef0b 100644 --- a/buch/chapters/30-endlichekoerper/galois.tex +++ b/buch/chapters/30-endlichekoerper/galois.tex @@ -295,7 +295,7 @@ Perlenketten, die sich nicht nur um eine Drehung unterscheiden. Die Abbildung $s_i\colon G\to A$ in Abbildung~\ref{buch:endliche-koerper:satz:fermat} schneidet die Perlenkette in $G$ an der Stelle $i$ auf. -Diese Abbildungen sond ganz offensichtlich injektiv. +Diese Abbildungen sind ganz offensichtlich injektiv. Die Bildmengen $A_i = s_i(G)$ haben daher alle gleich viele Elemente wie $G$: $|A_i|=|G|$. diff --git a/buch/chapters/40-eigenwerte/Makefile.inc b/buch/chapters/40-eigenwerte/Makefile.inc index 5f30ab5..9ca0a97 100644 --- a/buch/chapters/40-eigenwerte/Makefile.inc +++ b/buch/chapters/40-eigenwerte/Makefile.inc @@ -8,6 +8,7 @@ CHAPTERFILES = $(CHAPTERFILES) \ chapters/40-eigenwerte/numerisch.tex \ chapters/40-eigenwerte/normalformen.tex \ chapters/40-eigenwerte/grundlagen.tex \ + chapters/40-eigenwerte/eigenwerte.tex \ chapters/40-eigenwerte/spektralradius.tex \ chapters/40-eigenwerte/spektraltheorie.tex \ chapters/40-eigenwerte/uebungsaufgaben/4001.tex \ diff --git a/buch/chapters/40-eigenwerte/chapter.tex b/buch/chapters/40-eigenwerte/chapter.tex index 24ea57d..65cf608 100644 --- a/buch/chapters/40-eigenwerte/chapter.tex +++ b/buch/chapters/40-eigenwerte/chapter.tex @@ -8,30 +8,56 @@ \lhead{Eigenwerte und Eigenvektoren} \rhead{} Die algebraischen Eigenschaften einer Matrix $A$ sind eng mit der -Frage nach linearen Beziehungen unter den Potenzen von $A^k$ verbunden. +Frage nach linearen Beziehungen zwischen den Potenzen $A^k$ von $A$ verbunden. Im Allgemeinen ist die Berechnung dieser Potenzen eher unübersichtlich, es sei denn, die Matrix hat eine spezielle Form. Die Potenzen einer Diagonalmatrix erhält man, indem man die Diagonalelemente potenziert. +\index{Diagonalmatrix}% Auch für Dreiecksmatrizen ist mindestens die Berechnung der Diagonalelemente von $A^k$ einfach. +\index{Dreiecksmatrix}% Die Theorie der Eigenwerte und Eigenvektoren ermöglicht, Matrizen in -eine solche besonders einfache Form zu bringen. +\index{Eigenwert}% +\index{Eigenvektor} +eine solche besonders einfache sogenannte Normalform zu bringen. +\index{Normalform}% +Ziel ist, einen Algorithmus zu finden, mit dem sich für jede lineare +Abbildung eine Basis finden lässt, in der ihre Matrix eine besonders +einfach Form hat, in der auch die Berechnung von Potenzen leicht +möglich ist. -In Abschnitt~\ref{buch:section:grundlagen} werden die grundlegenden -Definitionen der Eigenwerttheorie in Erinnerung gerufen. +Die Untersuchungen beginnen in +Abschnitt~\ref{buch:section:grundlagen} mit Betrachtungen über +Potenzen von Matrizen und ihren invarianten Unterräumen. +\index{Matrixpotenz}% +\index{invarianter Unterraum}% +\index{Unterraum, invarianter}% +Es ergibt sich bereits eine Normalform für nilpotente Matrizen. +\index{nilpotent}% +In Abschnitt~\ref{buch:section:eigenwerte-eigenvektoren} wird daraus die +allgemeine Eigenwerttheorie entwickelt. Damit kann dann in Abschnitt~\ref{buch:section:normalformen} -gezeigt werden, wie Matrizen in besonders einfache Form gebracht -werden können. -Die Eigenwerte bestimmen auch die Eigenschaften von numerischen -Algorithmen, wie in den Abschnitten~\ref{buch:section:spektralradius} -und \ref{buch:section:numerisch} dargestellt wird. -Für viele Funktionen kann man auch den Wert $f(A)$ berechnen, unter -geeigneten Voraussetzungen an den Spektralradius. -Dies wird in Abschnitt~\ref{buch:section:spektraltheorie} beschrieben. +gezeigt werden, wie Matrizen in Normalform gebracht werden können. +Für viele Funktionen kann man auch den Wert $f(A)$ berechnen. +In Abschnitt~\ref{buch:section:analytische-funktionen-einer-matrix} wird +gezeigt, wie dies für analytische Funktionen und für Funktionen möglich +\index{analytische Funktion}% +ist, die durch Polynome approximiert werden. +Es zeigt sich, dass dazu geeigneten Voraussetzungen an den sogenannten +Spektralradius gestelltw erden müssen. +\index{Spektralradius}% +Es stellt sich heraus, dass man nicht für alle Matrizen $A$ eine +sinnvolle Definition von $f(A)$ für beliebige stetige Funktionen $f$ +erwarten kann. +Möglich ist dies nur für sogenannte normale Matrizen, wie in +der Spektraltheorie in +Abschnitt~\ref{buch:section:spektraltheorie} dargestellt wird. +\index{Spektraltheorie} \input{chapters/40-eigenwerte/grundlagen.tex} +\input{chapters/40-eigenwerte/eigenwerte.tex} \input{chapters/40-eigenwerte/normalformen.tex} \input{chapters/40-eigenwerte/spektralradius.tex} \input{chapters/40-eigenwerte/spektraltheorie.tex} diff --git a/buch/chapters/40-eigenwerte/eigenwerte.tex b/buch/chapters/40-eigenwerte/eigenwerte.tex new file mode 100644 index 0000000..563b58a --- /dev/null +++ b/buch/chapters/40-eigenwerte/eigenwerte.tex @@ -0,0 +1,593 @@ +% +% eigenwerte.tex +% +% Begriff des Eigenwertes und Eigenvektors +% +\section{Eigenwerte und Eigenvektoren +\label{buch:section:eigenwerte-und-eigenvektoren}} +In diesem Abschnitt betrachten wir Vektorräume $V=\Bbbk^n$ über einem +beliebigen Körper $\Bbbk$ und quadratische Matrizen +$A\in M_n(\Bbbk)$. +In den meisten Anwendungen wird $\Bbbk=\mathbb{R}$ sein. +Da aber in $\mathbb{R}$ nicht alle algebraischen Gleichungen lösbar sind, +ist es manchmal notwendig, den Vektorraum zu erweitern um zum Beispiel +auf dem Umweg über komplexe Zahlen +Eigenschaften der Matrix $A$ abzuleiten. + +\begin{definition} +\label{buch:eigenwerte:def:evew} +\label{buch:eigenwerte:def:spektrum} +Ein Vektor $v\in V$ heisst {\em Eigenvektor} von $A$ zum {\em Eigenwert} +\index{Eigenwert}% +\index{Eigenvekor}% +$\lambda\in\Bbbk$, wenn $v\ne 0$ und $Av=\lambda v$ gilt. +Die Menge +\[ +\operatorname{Sp}(A) += +\{\lambda\in\mathbb{C}\,|\, \text{$\lambda$ ist Eigenwert von $A$}\} +\] +heisst das {\em Spektrum} von $A$. +\index{Spektrum}% +\end{definition} + +Die Bedingung $v\ne 0$ dient dazu, pathologische Situationen auszuschliessen. +Für den Nullvektor gilt $A0=\lambda 0$ für jeden beliebigen Wert von +$\lambda\in\Bbbk$. +Würde man $v=0$ zulassen, wäre jede Zahl in $\Bbbk$ ein Eigenwert, +ein Eigenwert von $A$ wäre nichts besonderes. +Ausserdem wäre $0$ ein Eigenvektor zu jedem beliebigen Eigenwert. + +Eigenvektoren sind nicht eindeutig bestimmt, jedes von $0$ verschiedene +Vielfache von $v$ ist ebenfalls ein Eigenvektor. +Zu einem Eigenwert kann man also einen Eigenvektor mit +geeigneten Eigenschaften finden, zum Beispiel kann man für $\Bbbk = \mathbb{R}$ +Eigenvektoren auf Länge $1$ normieren. +Im Folgenden werden wir oft die abkürzend linear unabhängige Eigenvektoren +einfach als ``verschiedene'' Eigenvektoren bezeichnen. + +Wenn $v$ ein Eigenvektor von $A$ zum Eigenwert $\lambda$ ist, dann kann +man ihn mit zusätzlichen Vektoren $v_2,\dots,v_n$ zu einer Basis +$\mathcal{B}=\{v,v_2,\dots,v_n\}$ +von $V$ ergänzen. +Die Vektoren $v_k$ mit $k=2,\dots,n$ werden von $A$ natürlich auch +in den Vektorraum $V$ abgebildet, können also als Linearkombinationen +\[ +Av = a_{1k}v + a_{2k}v_2 + a_{3k}v_3 + \dots a_{nk}v_n +\] +dargestellt werden. +In der Basis $\mathcal{B}$ bekommt die Matrix $A$ daher die Form +\[ +A' += +\begin{pmatrix} +\lambda&a_{12}&a_{13}&\dots &a_{1n}\\ + 0 &a_{22}&a_{23}&\dots &a_{2n}\\ + 0 &a_{32}&a_{33}&\dots &a_{3n}\\ +\vdots &\vdots&\vdots&\ddots&\vdots\\ + 0 &a_{n2}&a_{n3}&\dots &a_{nn} +\end{pmatrix}. +\] +Bereits ein einzelner Eigenwert und ein zugehöriger Eigenvektor +ermöglichen uns also, die Matrix in eine etwas einfachere Form +zu bringen. + +\begin{definition} +Für $\lambda\in\Bbbk$ heisst +\[ +E_\lambda += +\{ v\;|\; Av=\lambda v\} +\] +der {\em Eigenraum} zum Eigenwert $\lambda$. +\index{Eigenraum}% +\end{definition} + +Der Eigenraum $E_\lambda$ ist ein Unterraum von $V$, denn wenn +$u,v\in E_\lambda$, dann ist +\[ +A(su+tv) += +sAu+tAv += +s\lambda u + t\lambda v += +\lambda(su+tv), +\] +also ist auch $su+tv\in E_\lambda$. +Der Spezialfall $E_\lambda = \{0\}=0$ bedeutet natürlich, dass $\lambda$ gar kein +Eigenwert ist. + +\begin{satz} +Wenn $\dim E_\lambda=n$ ist, dann ist $A=\lambda I$. +\end{satz} + +\begin{proof}[Beweis] +Da $V$ ein $n$-dimensionaler Vektoraum ist, ist $E_\lambda=V$. +Jeder Vektor $v\in V$ erfüllt also die Bedingung $Av=\lambda v$, +oder $A=\lambda I$. +\end{proof} + +Wenn man die Eigenräume von $A$ kennt, dann kann man auch die Eigenräume +von $A+\mu E$ berechnen. +Ein Vektor $v\in E_\lambda$ erfüllt +\[ +Av=\lambda v +\qquad\Rightarrow\qquad +(A+\mu)v = \lambda v + \mu v += +(\lambda+\mu)v, +\] +somit ist $v$ ein Eigenvektor von $A+\mu I$ zum Eigenwert $\lambda+\mu$. +Insbesondere können wir statt die Eigenvektoren von $A$ zum Eigenwert $\lambda$ +zu studieren, auch die Eigenvektoren zum Eigenwert $0$ von $A-\lambda I$ +untersuchen. + +% +% Invariante Räume +% +\subsection{Verallgemeinerte Eigenräume +\label{buch:subsection:verallgemeinerte-eigenraeume}} +Wenn $\lambda$ ein Eigenwert der Matrix $A$ ist, dann ist +ist $A-\lambda I$ injektiv und $\ker(A-\lambda I)\ne 0$. +Man kann daher die invarianten Unterräume $\mathcal{K}(A-\lambda I)$ +und $\mathcal{J}(A-\lambda I)$ bilden. + +\begin{beispiel} +Wir untersuchen die Matrix +\[ +A += +\begin{pmatrix} +1&1&-1&0\\ +0&3&-1&1\\ +0&2& 0&1\\ +0&0& 0&2 +\end{pmatrix} +\] +Man kann zeigen, dass $\lambda=1$ ein Eigenwert ist. +Wir suchen die Zerlegung des Vektorraums $\mathbb{R}^4$ in invariante +Unterräume $\mathcal{K}(A-I)$ und $\mathcal{J}(A-I)$. +Die Matrix $B=A-I$ ist +\[ +B += +\begin{pmatrix} +0&1&-1&0\\ +0&2&-1&1\\ +0&2&-1&1\\ +0&0& 0&2 +\end{pmatrix} +\] +und wir berechnen davon die vierte Potenz +\[ +D=B^4=(A-E)^4 += +\begin{pmatrix} +0&0& 0&0\\ +0&2&-1&4\\ +0&2&-1&4\\ +0&0& 0&1 +\end{pmatrix}. +\] +Daraus kann man ablesen, dass das Bild $\operatorname{im}D$ +von $D$ die Basis +\[ +b_1 += +\begin{pmatrix} +0\\0\\0\\1 +\end{pmatrix} +, \qquad +b_2 += +\begin{pmatrix} +0\\1\\1\\0 +\end{pmatrix} +\] +hat. +Für den Kern von $D$ können wir zum Beispiel die Basisvektoren +\[ +b_3 += +\begin{pmatrix} +0\\1\\2\\0 +\end{pmatrix} +,\qquad +b_4 += +\begin{pmatrix} +1\\0\\0\\0 +\end{pmatrix} +\] +verwenden. + +Als erstes überprüfen wir, ob diese Basisvektoren tatsächlich invariante +Unterräume sind. +Für $\mathcal{J}(A-I) = \langle b_1,b_2\rangle$ +berechnen wir +\begin{align*} +(A-I)b_1 +&= +\begin{pmatrix} 0\\4\\4\\1 \end{pmatrix} += +4b_2+b_1, +\\ +(A-I)b_2 +&= +\begin{pmatrix} 0\\1\\1\\0 \end{pmatrix} += +b_2. +\end{align*} +Dies beweist, dass $\mathcal{J}(A-I)$ invariant ist. +In dieser Basis hat die von $A-I$ beschriebene lineare Abbildung +auf $\mathcal{J}(A-I)$ die Matrix +\[ +A_{\mathcal{J}(A-I)} += +\begin{pmatrix} +1&4\\ +0&1 +\end{pmatrix}. +\] + +Für den Kern $\mathcal{K}(A-I)$ findet man analog +\[ +\left. +\begin{aligned} +Ab_3 +&= +-b_4 +\\ +Ab_4 +&=0 +\end{aligned} +\quad\right\} +\qquad\Rightarrow\qquad +A_{\mathcal{K}(A-I)} += +\begin{pmatrix} +0&-1\\ +0& 0 +\end{pmatrix}. +\] +In der Basis $\mathcal{B}=\{b_1,b_2,b_3,b_4\}$ hat $A$ die Matrix +in Blockform +\[ +A' += +\left( +\begin{array}{cc|cr} +2&4& & \\ +0&2& & \\ +\hline + & &1&-1\\ + & &0& 1 +\end{array}\right), +\] +die Blöcke gehören zu den invarianten Unterräumen $\mathcal{K}(A-I)$ +und $\mathcal{K}(A-I)$. +Die aus $A-E$ gewonnen invarianten Unterräume sind offenbar auch invariante +Unterräume für $A$. +\end{beispiel} + +\begin{definition} +Ist $A$ eine Matrix mit Eigenwert $\lambda$, dann heisst der invariante +Unterraum +\[ +\mathcal{E}_{\lambda}(A) += +\mathcal{K}(A-\lambda I) +\] +der {\em verallgemeinerte Eigenraum} von $A$. +\index{verallgemeinerter Eigenraum}% +\index{Eigenraum, verallgemeinerter}% +\end{definition} + +Es ist klar, dass +$E_\lambda(A)=\ker (A-\lambda I)\subset\mathcal{E}_{\lambda}(A)$. + +\subsection{Zerlegung in invariante Unterräume +\label{buch:subsection:zerlegung-in-invariante-unterraeume}} +Wenn $\lambda$ kein Eigenwert von $A$ ist, dann ist $A-\lambda I$ +injektiv und damit $\ker(A-\lambda I)=0$. +Es folgt, dass $\mathcal{K}^i(A-\lambda I)=0$ und daher auch +$\mathcal{J}^i(A-\lambda I)=V$. +Die Zerlegung in invariante Unterräume $\mathcal{J}(A-\lambda I)$ und +$\mathcal{E}_\lambda(A)=\mathcal{K}(A-\lambda I)$ liefert in diesem Falle also nichts Neues. + +Für einen Eigenwert $\lambda_1$ von $A$ dagegen erhalten wir die Zerlegung +\[ +V += +\mathcal{E}_{\lambda_1}(A) +\oplus +\underbrace{\mathcal{J}(A-\lambda_1 I)}_{\displaystyle =V_2}, +\] +wobei $\mathcal{E}_{\lambda_1}(A)\ne 0$ ist. +Die Matrix $A-\lambda_1 I$ eingeschränkt auf $\mathcal{E}_{\lambda_1}(A)$ ist +nilpotent. +Man kann sagen, auf dem Unterraum $\mathcal{E}_{\lambda_i}(A)$ hat +$A$ die Form $\lambda_1 I + N$, wobei $N$ nilpotent ist. + +Die Zerlegung in invariante Unterräume ist zwar mit Hilfe von $A-\lambda_1I$ +gewonnen worden, ist aber natürlich auch eine Zerlegung in invariante +Unterräume für $A$. +Wir können daher das Problem auf $V_2$ einschränken und nach einem weiteren +Eigenwert $\lambda_2$ von $A$ in $V_2$ suchen. +Dieser neue Eigenwert liefert eine Zerlegung von $V_2$ +in invariante Unterräume. +Indem wir so weiterarbeiten, bis wir den ganzen Raum ausgeschöpft haben, +können wir eine Zerlegung des ganzen Raumes $V$ finden, so dass $A$ auf +jedem einzelnen Summanden die sehr einfach Form +``$\lambda I + \text{nilpotent}$'' hat: + +\begin{satz} +\label{buch:eigenwerte:satz:zerlegung-in-eigenraeume} +Sei $V$ ein $\Bbbk$-Vektorraum und $f$ eine lineare Abbildung mit Matrix +$A$ derart, dass alle Eigenwerte $\lambda_1,\dots,\lambda_l$ von $A$ +in $\Bbbk$ sind. +Dann gibt es eine Zerlegung von $V$ in verallgemeinerte Eigenräume +\[ +V += +\mathcal{E}_{\lambda_1}(A) +\oplus +\mathcal{E}_{\lambda_2}(A) +\oplus +\dots +\oplus +\mathcal{E}_{\lambda_l}(A). +\] +Die Einschränkung von $A-\lambda_{i}I$ auf den Eigenraum +$\mathcal{E}_{\lambda_i}(A)$ ist nilpotent. +\end{satz} + +\subsection{Das charakteristische Polynom +\label{buch:subsection:das-charakteristische-polynom}} +Ein Eigenvektor von $A$ erfüllt $Av=\lambda v$ oder gleichbedeutend +$(A-\lambda I)v=0$, er ist also eine nichttriviale Lösung des homogenen +Gleichungssystems mit Koeffizientenmatrix $A-\lambda I$. +Ein Eigenwert ist also ein Skalar derart, dass $A-\lambda I$ +singulär ist. +Ob eine Matrix singulär ist, kann mit der Determinante festgestellt +werden. +Die Eigenwerte einer Matrix $A$ sind daher die Nullstellen +von $\det(A-\lambda I)$. + +\begin{definition} +Das {\em charakteristische Polynom} +\[ +\chi_A(x) += +\det (A-x I) += +\left| +\begin{matrix} +a_{11}-x & a_{12} & \dots & a_{1n} \\ +a_{21} & a_{22}-x & \dots & a_{2n} \\ +\vdots &\vdots &\ddots & \vdots \\ +a_{n1} & a_{n2} &\dots & a_{nn}-x +\end{matrix} +\right|. +\] +der Matrix $A$ ist ein Polynom vom Grad $n$ mit Koeffizienten in $\Bbbk$. +\index{charakteristisches Polynom}% +\index{Polynome, charakteristisches}% +\end{definition} + +Findet man eine Nullstelle $\lambda\in\Bbbk$ von $\chi_A(x)$, +dann ist die Matrix $A-\lambda I\in M_n(\Bbbk)$ und mit dem Gauss-Algorithmus +kann man auch mindestens einen Vektor $v\in \Bbbk^n$ finden, +der $Av=\lambda v$ erfüllt. +Eine Dreiecksmatrix der Form +\[ +A=\begin{pmatrix} +\lambda& * & * & * &\dots &*\\ + 0 &\lambda& * & * &\dots &*\\ + 0 & 0 &\lambda& * &\dots &*\\ + 0 & 0 & 0 &\lambda&\dots &*\\ +\vdots &\vdots &\vdots & &\ddots&\vdots\\ + 0 & 0 & 0 & 0 &\dots &\lambda +\end{pmatrix} +\] +hat +\[ +\chi_A(x) += +\left| +\begin{matrix} +\lambda-x & * & * & & * & * \\ + & \lambda-x & * & & * & * \\ + & & \lambda-x & & * & * \\ + & & &\ddots& * & * \\ + & & & &\lambda-x& * \\ + & & & & &\lambda-x +\end{matrix} +\right| += +(\lambda-x)^n += +(-1)^n (x-\lambda)^n +\] +als charakteristisches Polynom, welches $\lambda$ als einzige +Nullstelle hat. +Wenn die Einträge oberhalb der Diagonalen nicht alle 0 sind, +dann hat der Eigenraum der Matrix Dimension, die keiner ist als +$n$. +Man kann also im Allgemeinen für jede Nullstelle des charakteristischen +Polynoms nicht mehr als einen Eigenvektor (d.~h.~einen eindimensionalen +Eigenraum) erwarten. + +Wenn das charakteristische Polynom von $A$ keine Nullstellen in $\Bbbk$ hat, +dann kann es auch keine Eigenvektoren in $\Bbbk^n$ geben. +Gäbe es nämlich einen solchen Vektor, dann müsste eine der Komponenten +des Vektors von $0$ verschieden sein. +Wir nehmen an, dass es die Komponente in Zeile $k$ ist. +Die Komponente $v_k$ kann man auf zwei Arten berechnen, einmal als +die $k$-Komponenten von $Av$ und einmal als $k$-Komponente von $\lambda v$: +\[ +a_{k1}v_1+\dots+a_{kn}v_n = \lambda v_k. +\] +Da $v_k\ne 0$ kann man nach $\lambda$ auflösen und erhält +\[ +\lambda = \frac{a_{k1}v_1+\dots + a_{kn}v_n}{v_k}. +\] +Alle Terme auf der rechten Seite sind in $\Bbbk$ und werden nur mit +Körperoperationen in $\Bbbk$ verknüpft, also muss auch $\lambda\in\Bbbk$ +sein, im Widerspruch zur Annahme. + +Durch Hinzufügen von geeigneten Elementen können wir immer zu einem +Körper $\Bbbk'$ übergehen, in dem das charakteristische Polynom +in Linearfaktoren zerfällt. +\index{Linearfaktor}% +Für reelle Matrizen kann man zum Beispiel zu $\mathbb{C}$ übergehen, +da ein reelles Polynom alle Nullstellen in $\mathbb{C}$ hat. +In diesem Körper $\Bbbk'$ kann man jetzt das homogene lineare Gleichungssystem +mit Koeffizientenmatrix $A-\lambda I$ lösen und damit mindestens +einen Eigenvektor $v$ für jeden Eigenwert finden. +Die Komponenten von $v$ liegen in $\Bbbk'$, und mindestens eine davon kann +nicht in $\Bbbk$ liegen. +Das bedeutet aber nicht, dass man diese Vektoren nicht für theoretische +Überlegungen über von $\Bbbk'$ unabhängige Eigenschaften der Matrix $A$ machen. +Das folgende Beispiel soll diese Idee illustrieren. + +\begin{beispiel} +Wir arbeiten in diesem Beispiel über dem Körper $\Bbbk=\mathbb{Q}$. +Die Matrix +\[ +A=\begin{pmatrix} +-4&7\\ +-2&4 +\end{pmatrix} +\in +M_2(\mathbb{Q}) +\] +hat das charakteristische Polynom +\[ +\chi_A(x) += +\left| +\begin{matrix} +-4-x&7\\-2&4-x +\end{matrix} +\right| += +(-4-x)(4-x)-7\cdot(-2) += +-16+x^2+14 += +x^2-2. +\] +Die Nullstellen sind $\pm\sqrt{2}$ und damit nicht in $\mathbb{Q}$. +Wir gehen daher über zum Körper $\mathbb{Q}(\!\sqrt{2})$, in dem +sich zwei Nullstellen $\lambda=\pm\sqrt{2}$ finden lassen. +Zu jedem Eigenwert lässt sich auch ein Eigenvektor +$v_{\pm\sqrt{2}}\in \mathbb{Q}(\!\sqrt{2})^2$, und unter Verwendung dieser +Basis bekommt die Matrix $A'=TAT^{-1}$ Diagonalform. +Die Transformationsmatrix $T$ enthält Matrixelemente aus +$\mathbb{Q}(\!\sqrt{2})$, die nicht in $\mathbb{Q}$ liegen. +Die Matrix $A$ lässt sich also über dem Körper $\mathbb{Q}(\!\sqrt{2})$ +diagonalisieren, nicht aber über dem Körper $\mathbb{Q}$. + +Da $A'$ Diagonalform hat mit $\pm\sqrt{2}$ auf der Diagonalen, folgt +$A^{\prime 2} = 2I$, die Matrix $A'$ erfüllt also die Gleichung +\begin{equation} +A^{\prime 2}-I= \chi_{A}(A) = 0. +\label{buch:grundlagen:eqn:cayley-hamilton-beispiel} +\end{equation} +Die Gleichung~\ref{buch:grundlagen:eqn:cayley-hamilton-beispiel} +wurde zwar in $\mathbb{Q}(\!\sqrt{2})$ hergeleitet, aber in ihr kommen +keine Koeffizienten aus $\mathbb{Q}(\!\sqrt{2})$ vor, die man nicht auch +in $\mathbb{Q}$ berechnen könnte. +Sie gilt daher ganz allgemein, also $A^2-I=0$. +Dies is ein Spezialfall des Satzes von Cayley-Hamilton +\index{Cayley-Hamilton, Satz von}% +\index{Satz von Cayley-Hamilton}% +(Satz~\ref{buch:normalformen:satz:cayley-hamilton}) +welcher besagt, dass jede Matrix $A$ eine Nullstelle ihres +charakteristischen Polynoms ist: $\chi_A(A)=0$. +\end{beispiel} + +\begin{beispiel} +Die Matrix +\[ +A=\begin{pmatrix} +32&-41\\ +24&-32 +\end{pmatrix} +\in +M_2(\mathbb{R}) +\] +über dem Körper $\Bbbk = \mathbb{R}$ +hat das charakteristische Polynom +\[ +\det(A-xI) += +\left| +\begin{matrix} +32-x&-41 \\ +25 &-32-x +\end{matrix} +\right| += +(32-x)(-32-x)-25\cdot(-41) += +x^2-32^2 + 1025 += +x^2+1. +\] +Die charakteristische Gleichung $\chi_A(x)=0$ hat in $\mathbb{R}$ +keine Lösungen, daher gehen wir zum Körper $\Bbbk'=\mathbb{C}$ über, +in dem dank dem Fundamentalsatz \ref{buch:zahlen:satz:fundamentalsatz} +der Algebra alle Nullstellen zu finden sind, sie sind $\pm i$. +In $\mathbb C$ lassen sich dann auch Eigenvektoren finden, man muss dazu die +folgenden homogenen linearen Gleichungssyteme in Tableauform lösen: +\begin{align*} +\begin{tabular}{|>{$}c<{$}>{$}c<{$}|} +\hline +32-i&-41\\ +25 &-32-i\\ +\hline +\end{tabular} +& +\rightarrow +\begin{tabular}{|>{$}c<{$}>{$}c<{$}|} +\hline +1 & t\\ +0 & 0 \\ +\hline +\end{tabular} +& +\begin{tabular}{|>{$}c<{$}>{$}c<{$}|} +\hline +32+i&-41\\ +25 &-32+i\\ +\hline +\end{tabular} +& +\rightarrow +\begin{tabular}{|>{$}c<{$}>{$}c<{$}|} +\hline +1 & \overline{t}\\ +0 & 0 \\ +\hline +\end{tabular}, +\intertext{wobei wir $t=-41/(32-i) =-41(32+i)/1025= -1.28 -0.04i = (64-1)/50$ +abgekürzt haben. +Die zugehörigen Eigenvektoren sind} +v_i&=\begin{pmatrix}t\\-1\end{pmatrix} +& +v_{-i}&=\begin{pmatrix}\overline{t}\\-1\end{pmatrix}. +\end{align*} +Mit den Vektoren $v_i$ und $v_{-i}$ als Basis kann die Matrix $A$ als +komplexe Matrix, also mit komplexem $T$ in die komplexe Diagonalmatrix +$A'=\operatorname{diag}(i,-i)$ transformiert werden. +Wieder kann man sofort ablesen, dass $A^{\prime2}+I=0$, und wieder kann +man schliessen, dass für die relle Matrix $A$ ebenfalls $\chi_A(A)=0$ +gelten muss. +\end{beispiel} + + + + diff --git a/buch/chapters/40-eigenwerte/grundlagen.tex b/buch/chapters/40-eigenwerte/grundlagen.tex index 69618a9..91294f1 100644 --- a/buch/chapters/40-eigenwerte/grundlagen.tex +++ b/buch/chapters/40-eigenwerte/grundlagen.tex @@ -3,18 +3,23 @@ % % (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule % -\section{Grundlagen +\section{Matrixpotenzen \label{buch:section:grundlagen}} -\rhead{Grundlagen} -Die Potenzen $A^k$ sind besonders einfach zu berechnen, wenn die Matrix -Diagonalform hat, wenn also $A=\operatorname{diag}(\lambda_1,\dots,\lambda_n)$ -ist. -In diesem Fall ist $Ae_k=\lambda_k e_k$ für jeden Standardbasisvektor $e_k$. -Statt sich auf Diagonalmatrizen zu beschränken könnten man also auch -Vektoren $v$ suchen, für die gilt $Av=\lambda v$, die also von $A$ nur -gestreckt werden. -Gelingt es, eine Basis aus solchen sogenanten {\em Eigenvektoren} zu finden, -dann kann man die Matrix $A$ durch Basiswechsel in diese Form bringen. +\rhead{Matrixpotenzen} +Die Zerlegung einer Matrix in einfachere Blöcke ist gleichbedeutend +damit, Basen für Unterräume zu finden, die sich unter der Abbildung +nicht ändern. +Im Allgemeinen wird der ganze Raum $\Bbbk^n$ kein solcher invarianter +Unterraum sein. +In diesem Abschnitt soll gezeigt werden, wie man durch Iteration +der Abbildung, also durch Betrachtung von Matrixpotenzen, immer zu +\index{Matrixpotenz}% +einer Zerlegung in invariante Unterräume kommen kann. +\index{invarianter Unterraum}% +\index{Unterraum, invarianter}% +Daraus ergibt sich dann in Abschnitt~\ref{buch:subsection:nilpotente-matrizen} +bereits eine Normalform für nilpotente Matrizen. +\index{nilpotent}% \begin{figure} \centering @@ -53,8 +58,7 @@ ist. \label{buch:subsection:kern-und-bild}} In diesem Abschnitt ist $A\in M_n(\Bbbk)$, $A$ beschreibt eine lineare Abbildung $f\colon\Bbbk^n\to \Bbbk^n$. -In diesem Abschnitt sollen Kern und Bild der Potenzen $A^k$ untersucht -werden. +Im Folgenden sollen Kern und Bild der Potenzen $A^k$ untersucht werden. \begin{definition} Wir bezeichnen Kern und Bild der iterierten Abbildung $A^k$ mit \[ @@ -66,6 +70,8 @@ Wir bezeichnen Kern und Bild der iterierten Abbildung $A^k$ mit = \operatorname{im} A^k. \] +\index{KkA@$\mathcal{K}^k(A)$}% +\index{JkA@$\mathcal{J}^k(A)$}% \end{definition} Durch Iteration wird das Bild immer kleiner. @@ -106,7 +112,7 @@ folgt \{0\}. \label{buch:eigenwerte:eqn:Jkchain} \end{equation} -Für die Kerne gilt etwas Ähnliches. +Für die Kerne gilt etwas Ähnliches, sie werden immer grösser. Ein Vektor $x\in \mathcal{K}^k(A)$ erfüllt $A^kx=0$. Dann erfüllt er aber erst recht auch \[ @@ -181,7 +187,7 @@ bestimmten $\mathcal{J}^{i+2}(A)$. $\mathcal{J}^{i+2}(A)$ besteht aus all jenen Vektoren, die als $Ax$ mit $x\in\mathcal{J}^{i+1}(A)=\mathcal{J}^i(A)$ erhalten werden können. -Es gibt also insbesondere ein $y\in\Bbbk^i$ mit $x=A^iy$. +Es gibt also insbesondere ein $y\in\Bbbk^n$ mit $x=A^iy$. Dann ist $Ax=A^{i+1}y\in\mathcal{J}^{i+1}(A)$. Insbesondere besteht $\mathcal{J}^{i+2}(A)$ genau aus den Vektoren von $\mathcal{J}^{i+1}(A)$. @@ -238,11 +244,13 @@ $\mathcal{K}^i(A)$ für $i\ge k$ und die identischen Unterräume $\mathcal{J}^i(A)$ für $i\ge k$ werden mit \[ \begin{aligned} -\mathcal{K} &= \mathcal{K}^i(A)&&\forall i\ge k \qquad\text{und} +\mathcal{K}(A) &= \mathcal{K}^i(A)&&\forall i\ge k \qquad\text{und} \\ -\mathcal{J} &= \mathcal{J}^i(A)&&\forall i\ge k +\mathcal{J}(A) &= \mathcal{J}^i(A)&&\forall i\ge k \end{aligned} \] +\index{KA@$\mathcal{K}(A)$} +\index{JA@$\mathcal{J}(A)$} bezeichnet. \end{definition} @@ -259,6 +267,7 @@ Abbildungen zwischen ``kleineren'' Räumen zu zerlegen, wo sie leichter analysiert werden können. \begin{definition} +\label{buch:eigenwerte:def:invarianter-unterraum} Sei $f\colon V\to V$ eine lineare Abbildung eines Vektorraums in sich selbst. Ein Unterraum $U\subset V$ heisst {\em invarianter Unterraum}, @@ -267,6 +276,8 @@ wenn f(U) = \{ f(x)\;|\; x\in U\} \subset U \] gilt. +\index{invarianter Unterraum}% +\index{Unterraum, invarianter}% \end{definition} Der Kern $\ker A$ einer linearen Abbildung ist trivialerweise ein @@ -337,11 +348,11 @@ A' \left( \begin{array}{ccc|ccc} &&&&&\\ -&A_{\mathcal{K}'}&&&&\\ +&A'_{\mathcal{K}}&&&&\\ &&&&&\\ \hline &&&&&\\ -&&&&A_{\mathcal{J}'}&\\ +&&&&A'_{\mathcal{J}}&\\ &&&&&\\ \end{array} \right) @@ -361,21 +372,24 @@ und $\mathcal{K}(A)$ reduziert die lineare Abbildung auf zwei Abbildungen mit speziellen Eigenschaften. Es wurde bereits in Satz~\label{buch:eigenwerte:satz:fJinj} gezeigt, dass die Einschränkung auf $\mathcal{J}(A)$ injektiv ist. -Die Einschränkung auf $\mathcal{K}(A)$ bildet nach Definition alle +Die Einschränkung auf $\mathcal{K}(A)$ bildet nach +Definition~\ref{buch:eigenwerte:def:KundJ} alle Vektoren nach $k$-facher Iteration auf $0$ ab, $A^k\mathcal{K}(A)=0$. Solche Abbildungen haben eine speziellen Namen. \begin{definition} \label{buch:eigenwerte:def:nilpotent} -Eine Matrix $A$ heisst nilpotent, wenn es eine Zahl $k$ gibt, so dass +Eine Matrix $A$ heisst {\em nilpotent}, wenn es eine Zahl $k$ gibt, so dass $A^k=0$. +\index{nilpotent}% \end{definition} \begin{beispiel} Obere (oder untere) Dreiecksmatrizen mit Nullen auf der Diagonalen sind nilpotent. +\index{Dreicksmatrix}% Wir rechnen dies wie folgt nach. -Die Matrix $A$ mit Einträgen $a_{ij}$ +Die Matrix $A$ mit Einträgen $a_{i\!j}$ \[ A=\begin{pmatrix} 0 &a_{12}&a_{13}&\dots &a_{1,n-1}&a_{1n} \\ @@ -386,35 +400,35 @@ A=\begin{pmatrix} 0 & 0 & 0 &\dots & 0 & 0 \end{pmatrix} \] -erfüllt $a_{ij}=0$ für $i\ge j$. +erfüllt $a_{i\!j}=0$ für $i\ge j$. Wir zeigen jetzt, dass sich bei der Multiplikation die nicht verschwinden Elemente bei der Multiplikation noch rechts oben verschieben. Dazu multiplizieren wir zwei Matrizen $B$ und $C$ mit -$b_{ij}=0$ für $i+k>j$ und $c_{ij}=0$ für $i+l>j$. +$b_{i\!j}=0$ für $i+k>j$ und $c_{i\!j}=0$ für $i+l>j$. In der folgenden graphischen Darstellung der Matrizen sind die Bereiche, wo die Matrixelemente verschwinden, weiss. \begin{center} \includegraphics{chapters/40-eigenwerte/images/nilpotent.pdf} \end{center} -Bei der Berechnung des Elementes $d_{ij}$ wird die Zeile $i$ von $B$ +Bei der Berechnung des Elementes $d_{i\!j}$ wird die Zeile $i$ von $B$ mit der Spalte $j$ von $C$ multipliziert. Die blau eingefärbten Elemente in dieser Zeile und Spalte sind $0$. Aus der Darstellung ist abzulesen, dass das Produkt verschwindet, -die roten, von $0$ verschiedenen Elemente von den blauen Elementen -annihiliert werden. +wenn die roten, von $0$ verschiedenen Elemente von den blauen +Elementen annihiliert werden. Dies passiert immer, wenn $i+k>j-l$ ist, oder $i+(k+l)> j$. Wir wenden diese Beobachtung jetzt auf die Potenzen $A^s$ an. -Für die Matrixelemente von $A^s$ schreiben wir $a^s_{ij}$. -Wir behaupten, dass die Matrixelemente $A^s$ die Bedingung -$a_{ij}^s=0$ für $i+s>j$ erfüllen. +Für die Matrixelemente von $A^s$ schreiben wir $a^s_{i\!j}$. +Wir behaupten, dass die Matrixelemente von $A^s$ die Bedingung +$a_{i\!j}^s=0$ für $i+s>j$ erfüllen. Dies ist für $s=1$ nach Voraussetzung richtig, dies ist die -Induktionsvoraussetzung. -Nehmen wir jetzt an, dass $a_{ij}^s=0$ für $i+s>j$, dann folgt -aus obiger Rechnung, dass $a_{ij}^{s+1}=0$ für $i+s+1>j$, so +Induktionsverankerung. +Nehmen wir jetzt an, dass $a_{i\!j}^s=0$ für $i+s>j$, dann folgt +aus obiger Rechnung, dass $a_{i\!j}^{s+1}=0$ für $i+s+1>j$, so dass die Bedingung auch für $A^s$ gilt (Induktionsschritt). -Mit vollständiger Induktion folgt, dass $a_{ij}^s=0$ für $i+s>j$. +Mit vollständiger Induktion folgt, dass $a_{i\!j}^s=0$ für $i+s>j$. Insbesondere ist $A^n=0$, die Matrix $A$ ist nilpotent. \end{beispiel} @@ -468,6 +482,9 @@ Wir bezeichnen mit $N_n$ eine Matrix der Form Mit etwas mehr Sorgfalt kann man auch die Bedingung, dass $A^{n-1}\ne 0$ sein muss, im Satz~\ref{buch:eigenwerte:satz:nnilpotent} loswerden. +Sie bedeutet nämlich dass sich die Matrix in mehrere kleinere Blöcke +der Form~\eqref{buch:eigenwerte:eqn:nnilpotent} zerlegen lässt, wie +der folgende Satz zeigt. \begin{satz} \label{buch:eigenwerte:satz:allgnilpotent} @@ -492,11 +509,18 @@ A' & & &\multicolumn{1}{|c|}{\raisebox{0pt}[17pt][12pt]{\phantom{x}$N_{k_l}$}\phantom{x}}\\ \cline{4-4} \end{array} -\right) +\right). \label{buch:eigenwerte:eqn:allgnilpotent} \end{equation} \end{satz} +Im Abschnitt~\ref{buch:subsection:normalform-einer-nilpotenten-matrix} +wird ein Algorithmus zur Bestimmung einer geeigneten Basis für die +Normalform~\eqref{buch:eigenwerte:eqn:allgnilpotent} in etwas mehr +Detail dargestellt. + +Aus Satz lässt sich für eine beliebige lineare Abbildung auch bereits eine +partielle Normalform finden. Die Einschränkung von $f$ auf den invarianten Unterraum $\mathcal{K}(A)$ ist nilpotent. Die Zerlegung $V=\mathcal{J}(A)\oplus \mathcal{K}(A)$ führt also zu einer @@ -508,7 +532,6 @@ $\mathcal{K}(A)$ eine Basis so wählen, dass die Matrix die Blockform \eqref{buch:eigenwerte:eqn:allgnilpotent} erhält. - \begin{figure} \centering \includegraphics[width=\textwidth]{chapters/40-eigenwerte/images/jknilp.pdf} @@ -602,7 +625,7 @@ ist ein Block der Form $N_k$. Für $0\le k\le l-1$ sind die Vektoren $A^kb_i$, solange sie von $0$ verschieden sind, alle nach Konstruktion linear unabhängig, sie bilden eine Basis -von $\mathcal{K}^l(A)=\mathbb{R}^n$. +von $\mathcal{K}^l(A)=\Bbbk^n$. \begin{beispiel} Die Basis für die Zerlegung der Matrix @@ -618,7 +641,7 @@ A in Blockform soll nach der oben beschriebenen Methode ermittelt werden. Zunächst kann man nachrechnen, dass $A^2=0$ ist. Der Kern von $A$ ist der Lösungsraum der Gleichung $Ax=0$, da alle Zeilen -Vielfache der ersten Zeile sind, recht es zu verlangen, dass die +Vielfache der ersten Zeile sind, reicht es zu verlangen, dass die Komponenten $x_i$ der Lösung die Gleichung \[ 3x_1+x_2-2x_3=0 @@ -631,9 +654,10 @@ Wir verwenden daher die beiden Vektoren \[ b_3=e_1=\begin{pmatrix} 1\\0\\0 \end{pmatrix} ,\qquad -b_2=Ab_3=\begin{pmatrix*}[r] 3\\-21\\-6 \end{pmatrix*}, +b_2=Ab_3=\begin{pmatrix*}[r] 3\\-21\\-6 \end{pmatrix*}. \] -in dieser Basis hat $A$ die Matrix $N_2$. +In einem Unterraum mit +dieser Basis hat $A$ die Matrix $N_2$. Jetzt muss noch ein Basisvektor $b_1$ gefunden werden, der in $\ker A=\mathbb{L}$ liegt und so, dass $b_1$ und $b_2$ linear unabhängig sind. @@ -641,7 +665,7 @@ Die zweite Bedingung kann leicht dadurch sichergestellt werden, dass man die erste Komponente von $b_1$ als $0$ wählt. Eine mögliche Lösung ist dann \[ -b_1=\begin{pmatrix}0\\2\\1\end{pmatrix} +b_1=\begin{pmatrix}0\\2\\1\end{pmatrix}. \] Die Matrix \[ @@ -668,557 +692,17 @@ B^{-1}\begin{pmatrix*}[r] 0&0& -6 \end{pmatrix*} = -\begin{pmatrix} -0&0&0\\ -0&0&1\\ -0&0&0 -\end{pmatrix} -= -N_3. -\qedhere -\] -\end{beispiel} - -% -% Begriff des Eigenwertes und Eigenvektors -% -\subsection{Eigenwerte und Eigenvektoren -\label{buch:subsection:eigenwerte-und-eigenvektoren}} -In diesem Abschnitt betrachten wir Vektorräume $V=\Bbbk^n$ über einem -beliebigen Körper $\Bbbk$ und quadratische Matrizen -$A\in M_n(\Bbbk)$. -In den meisten Anwendungen wird $\Bbbk=\mathbb{R}$ sein. -Da aber in $\mathbb{R}$ nicht alle algebraischen Gleichungen lösbar sind, -ist es manchmal notwendig, den Vektorraum zu erweitern um zum Beispiel -Eigenschaften der Matrix $A$ abzuleiten. - -\begin{definition} -Ein Vektor $v\in V$ heisst {\em Eigenvektor} von $A$ zum Eigenwert -$\lambda\in\Bbbk$, wenn $v\ne 0$ und $Av=\lambda v$ gilt. -\end{definition} - -Die Bedingung $v\ne 0$ dient dazu, pathologische Situationen auszuschliessen. -Für den Nullvektor gilt $A0=\lambda 0$ für jeden beliebigen Wert von -$\lambda\in\Bbbk$. -Würde man $v=0$ zulassen, wäre jede Zahl in $\Bbbk$ ein Eigenwert, -ein Eigenwert von $A$ wäre nichts besonderes. -Ausserdem wäre $0$ ein Eigenvektor zu jedem beliebigen Eigenwert. - -Eigenvektoren sind nicht eindeutig bestimmt, jedes von $0$ verschiedene -Vielfache von $v$ ist ebenfalls ein Eigenvektor. -Zu einem Eigenwert kann man also einen Eigenvektor jeweils mit -geeigneten Eigenschaften finden, zum Beispiel kann man für $\Bbbk = \mathbb{R}$ -Eigenvektoren auf Länge $1$ normieren. -Im Folgenden werden wir oft die abkürzend linear unabhängige Eigenvektoren -einfach als ``verschiedene'' Eigenvektoren bezeichnen. - -Wenn $v$ ein Eigenvektor von $A$ zum Eigenwert $\lambda$ ist, dann kann -man ihn mit zusätzlichen Vektoren $v_2,\dots,v_n$ zu einer Basis -$\mathcal{B}=\{v,v_2,\dots,v_n\}$ -von $V$ ergänzen. -Die Vektoren $v_k$ mit $k=2,\dots,n$ werden von $A$ natürlich auch -in den Vektorraum $V$ abgebildet, können also als Linearkombinationen -\[ -Av = a_{1k}v + a_{2k}v_2 + a_{3k}v_3 + \dots a_{nk}v_n -\] -dargestellt werden. -In der Basis $\mathcal{B}$ bekommt die Matrix $A$ daher die Form -\[ -A' -= -\begin{pmatrix} -\lambda&a_{12}&a_{13}&\dots &a_{1n}\\ - 0 &a_{22}&a_{23}&\dots &a_{2n}\\ - 0 &a_{32}&a_{33}&\dots &a_{3n}\\ -\vdots &\vdots&\vdots&\ddots&\vdots\\ - 0 &a_{n2}&a_{n3}&\dots &a_{nn} -\end{pmatrix}. -\] -Bereits ein einzelner Eigenwert und ein zugehöriger Eigenvektor -ermöglichen uns also, die Matrix in eine etwas einfachere Form -zu bringen. - -\begin{definition} -Für $\lambda\in\Bbbk$ heisst -\[ -E_\lambda -= -\{ v\;|\; Av=\lambda v\} -\] -der {\em Eigenraum} zum Eigenwert $\lambda$. -\index{Eigenraum}% -\end{definition} - -Der Eigenraum $E_\lambda$ ist ein Unterraum von $V$, denn wenn -$u,v\in E_\lambda$, dann ist -\[ -A(su+tv) -= -sAu+tAv -= -s\lambda u + t\lambda v -= -\lambda(su+tv), -\] -also ist auch $su+tv\in E_\lambda$. -Der Fall $E_\lambda = \{0\}=0$ bedeutet natürlich, dass $\lambda$ gar kein -Eigenwert ist. - -\begin{satz} -Wenn $\dim E_\lambda=n$, dann ist $A=\lambda E$. -\end{satz} - -\begin{proof}[Beweis] -Da $V$ ein $n$-dimensionaler Vektoraum ist, ist $E_\lambda=V$. -Jeder Vektor $v\in V$ erfüllt also die Bedingung $Av=\lambda v$, -oder $A=\lambda E$. -\end{proof} - -Wenn man die Eigenräume von $A$ kennt, dann kann man auch die Eigenräume -von $A+\mu E$ berechnen. -Ein Vektor $v\in E_\lambda$ erfüllt -\[ -Av=\lambda v -\qquad\Rightarrow\qquad -(A+\mu)v = \lambda v + \mu v -= -(\lambda+\mu)v, -\] -somit ist $v$ ein Eigenvektor von $A+\mu E$ zum Eigenwert $\lambda+\mu$. -Insbesondere können wir statt die Eigenvektoren von $A$ zum Eigenwert $\lambda$ -zu studieren, auch die Eigenvektoren zum Eigenwert $0$ von $A-\lambda E$ -untersuchen. - -% -% Invariante Räume -% -\subsection{Verallgemeinerte Eigenräume -\label{buch:subsection:verallgemeinerte-eigenraeume}} -Wenn $\lambda$ ein Eigenwert der Matrix $A$ ist, dann ist -ist $A-\lambda E$ injektiv und $\ker(A-\lambda E)\ne 0$. -Man kann daher die invarianten Unterräume $\mathcal{K}(A-\lambda E)$ -und $\mathcal{J}(A-\lambda E)$. - -\begin{beispiel} -Wir untersuchen die Matrix -\[ -A -= -\begin{pmatrix} -1&1&-1&0\\ -0&3&-1&1\\ -0&2& 0&1\\ -0&0& 0&2 -\end{pmatrix} -\] -Man kann zeigen, dass $\lambda=1$ ein Eigenwert ist. -Wir suchen die Zerlegung des Vektorraums $\mathbb{R}^4$ in invariante -Unterräume $\mathcal{K}(A-E)$ und $\mathcal{J}(A-E)$. -Die Matrix $B=A-E$ ist -\[ -B -= -\begin{pmatrix} -0&1&-1&0\\ -0&2&-1&1\\ -0&2&-1&1\\ -0&0& 0&2 -\end{pmatrix} -\] -und wir berechnen davon die Potenz -\[ -D=B^4=(A-E)^4 -= -\begin{pmatrix} -0&0& 0&0\\ -0&2&-1&4\\ -0&2&-1&4\\ -0&0& 0&1 -\end{pmatrix}. -\] -Daraus kann man ablesen, dass das Bild $\operatorname{im}D$ -von $D$ die Basis -\[ -b_1 -= -\begin{pmatrix} -0\\0\\0\\1 -\end{pmatrix} -, \qquad -b_2 -= -\begin{pmatrix} -0\\1\\1\\0 -\end{pmatrix} -\] -hat. -Für den Kern von $D$ können wir zum Beispiel die Basisvektoren -\[ -b_3 -= -\begin{pmatrix} -0\\1\\2\\0 -\end{pmatrix} -,\qquad -b_4 -= -\begin{pmatrix} -1\\0\\0\\0 -\end{pmatrix} -\] -verwenden. - -Als erstes überprüfen wir, ob diese Basisvektoren tatsächlich invariante -Unterräume sind. -Für $\mathcal{J}(A-E) = \langle b_1,b_2\rangle$ -berechnen wir -\begin{align*} -(A-E)b_1 -&= -\begin{pmatrix} 0\\4\\4\\1 \end{pmatrix} -= -4b_2+b_1, -\\ -(A-E)b_2 -&= -\begin{pmatrix} 0\\1\\1\\0 \end{pmatrix} -= -b_2. -\end{align*} -Dies beweist, dass $\mathcal{J}(A-E)$ invariant ist. -In dieser Basis hat die von $A-E$ beschriebene lineare Abbildung -auf $\mathcal{J}(A-E)$ die Matrix -\[ -A_{\mathcal{J}(A-E)} -= -\begin{pmatrix} -1&4\\ -0&1 -\end{pmatrix}. -\] - -Für den Kern $\mathcal{K}(A-E)$ findet man analog -\[ -\left. -\begin{aligned} -Ab_3 -&= --b_4 -\\ -Ab_4 -&=0 -\end{aligned} -\quad\right\} -\qquad\Rightarrow\qquad -A_{\mathcal{K}(A-E)} -= -\begin{pmatrix} -0&-1\\ -0& 0 -\end{pmatrix}. -\] -In der Basis $\mathcal{B}=\{b_1,b_2,b_3,b_4\}$ hat $A$ die Matrix -in Blockform -\[ -A' -= \left( -\begin{array}{cc|cr} -2&4& & \\ -0&2& & \\ +\begin{array}{c|cc} +0& & \\ \hline - & &1&-1\\ - & &0& 1 -\end{array}\right), -\] -die Blöcke gehören zu den invarianten Unterräumen $\mathcal{K}(A-E)$ -und $\mathcal{K}(A-E)$. -Die aus $A-E$ gewonnen invarianten Unterräume sind offenbar auch invariante -Unterräume für $A$. -\end{beispiel} - -\begin{definition} -Ist $A$ eine Matrix mit Eigenwert $\lambda$, dann heisst der invariante -Unterraum -\[ -\mathcal{E}_{\lambda}(A) -= -\mathcal{K}(A-\lambda E) -\] -der verallgemeinerte Eigenraum von $A$. -\end{definition} - -Es ist klar, dass -$E_\lambda(A)=\ker (A-\lambda E)\subset\mathcal{E}_{\lambda}(A)$. - -\subsection{Zerlegung in invariante Unterräume -\label{buch:subsection:zerlegung-in-invariante-unterraeume}} -Wenn $\lambda$ kein Eigenwert von $A$ ist, dann ist $A-\lambda E$ -injektiv und damit $\ker(A-\lambda E)=0$. -Es folgt, dass $\mathcal{K}^i(A-\lambda E)=0$ und daher auch -$\mathcal{J}^i(A-\lambda E)=V$. -Die Zerlegung in invariante Unterräume $\mathcal{J}(A-\lambda E)$ und -$\mathcal{K}(A-\lambda E)$ liefert in diesem Falle also nichts Neues. - -Für einen Eigenwert $\lambda_1$ von $A$ dagegen, erhalten wir die Zerlegung -\[ -V -= -\mathcal{E}_{\lambda_1}(A) -\oplus -\underbrace{\mathcal{J}(A-\lambda_1 E)}_{\displaystyle =V_2}, -\] -wobei $\mathcal{E}_{\lambda_1}(A)\ne 0$ ist. -Die Matrix $A-\lambda_1 E$ ist eingeschränkt auf $\mathcal{E}_{\lambda_1}(A)$ -nilpotent. -Die Zerlegung in invariante Unterräume ist zwar mit Hilfe von $A-\lambda_1E$ -gewonnen worden, ist aber natürlich auch eine Zerlegung in invariante -Unterräume für $A$. -Wir können daher das Problem auf $V_2$ einschränken und nach einem weiteren -Eigenwert $\lambda_2$ von $A$ in $V_2$ suchen, was wieder eine Zerlegung -in invariante Unterräume liefert. -Indem wir so weiterarbeiten, bis wir den ganzen Raum ausgeschöpft haben, -können wir eine Zerlegung des ganzen Raumes $V$ finden, so dass $A$ auf -jedem einzelnen Summanden eine sehr einfach Form hat: - -\begin{satz} -\label{buch:eigenwerte:satz:zerlegung-in-eigenraeume} -Sei $V$ ein $\Bbbk$-Vektorraum und $f$ eine lineare Abbildung mit Matrix -$A$ derart, dass alle Eigenwerte $\lambda_1,\dots,\lambda_l$ von $A$ -in $\Bbbk$ sind. -Dann gibt es eine Zerlegung von $V$ in verallgemeinerte Eigenräume -\[ -V -= -\mathcal{E}_{\lambda_1}(A) -\oplus -\mathcal{E}_{\lambda_2}(A) -\oplus -\dots -\oplus -\mathcal{E}_{\lambda_l}(A). -\] -Die Einschränkung von $A-\lambda_{i}E$ auf den Eigenraum -$\mathcal{E}_{\lambda_i}(A)$ ist nilpotent. -\end{satz} - -\subsection{Das charakteristische Polynom -\label{buch:subsection:das-charakteristische-polynom}} -Ein Eigenvektor von $A$ erfüllt $Av=\lambda v$ oder gleichbedeutend -$(A-\lambda E)v=0$, er ist also eine nichttriviale Lösung des homogenen -Gleichungssystems mit Koeffizientenmatrix $A-\lambda E$. -Ein Eigenwert ist also ein Skalar derart, dass $A-\lambda E$ -singulär ist. -Ob eine Matrix singulär ist, kann mit der Determinante festgestellt -werden. -Die Eigenwerte einer Matrix $A$ sind daher die Nullstellen -von $\det(A-\lambda E)$. - -\begin{definition} -Das {\em charakteristische Polynom} -\[ -\chi_A(x) -= -\det (A-x E) -= -\left| -\begin{matrix} -a_{11}-x & a_{12} & \dots & a_{1n} \\ -a_{21} & a_{22}-x & \dots & a_{2n} \\ -\vdots &\vdots &\ddots & \vdots \\ -a_{n1} & a_{n2} &\dots & a_{nn}-x -\end{matrix} -\right|. -\] -der Matrix $A$ ist ein Polynom vom Grad $n$ mit Koeffizienten in $\Bbbk$. -\end{definition} - -Findet man eine Nullstelle $\lambda\in\Bbbk$ von $\chi_A(x)$, -dann ist die Matrix $A-\lambda E\in M_n(\Bbbk)$ und mit dem Gauss-Algorithmus -kann man auch mindestens einen Vektor $v\in \Bbbk^n$ finden, -der $Av=\lambda v$ erfüllt. -Eine Matrix der Form wie in Satz~\ref{buch:eigenwerte:satz:jordanblock} -hat -\[ -\chi_A(x) -= -\left| -\begin{matrix} -\lambda-x & 1 & & & & \\ - & \lambda-x & 1 & & & \\ - & & \lambda-x & & & \\ - & & &\ddots& & \\ - & & & &\lambda-x& 1 \\ - & & & & &\lambda-x -\end{matrix} -\right| -= -(\lambda-x)^n -= -(-1)^n (x-\lambda)^n -\] -als charakteristisches Polynom, welches $\lambda$ als einzige -Nullstelle hat. -Der Eigenraum der Matrix ist aber nur eindimensional, man kann also -im Allgemeinen für jede Nullstelle des charakteristischen Polynoms -nicht mehr als einen Eigenvektor (d.~h.~einen eindimensionalen Eigenraum) -erwarten. - -Wenn das charakteristische Polynom von $A$ keine Nullstellen in $\Bbbk$ hat, -dann kann es auch keine Eigenvektoren in $\Bbbk^n$ geben. -Gäbe es nämlich einen solchen Vektor, dann müsste eine der Komponenten -des Vektors von $0$ verschieden sein, wir nehmen an, dass es die Komponente -in Zeile $k$ ist. -Die Komponente $v_k$ kann man auf zwei Arten berechnen, einmal als -die $k$-Komponenten von $Av$ und einmal als $k$-Komponente von $\lambda v$: -\[ -a_{k1}v_1+\dots+a_{kn}v_n = \lambda v_k. -\] -Da $v_k\ne 0$ kann man nach $\lambda$ auflösen und erhält -\[ -\lambda = \frac{a_{k1}v_1+\dots + a_{kn}v_n}{v_k}. -\] -Alle Terme auf der rechten Seite sind in $\Bbbk$ und werden nur mit -Körperoperationen in $\Bbbk$ verknüpft, also muss auch $\lambda\in\Bbbk$ -sein, im Widerspruch zur Annahme. - -Durch Hinzufügen von geeigneten Elementen können wir immer zu einem -Körper $\Bbbk'$ übergehen, in dem das charakteristische Polynom -in Linearfaktoren zerfällt. -In diesem Körper kann man jetzt das homogene lineare Gleichungssystem -mit Koeffizientenmatrix $A-\lambda E$ lösen und damit mindestens -einen Eigenvektor $v$ für jeden Eigenwert finden. -Die Komponenten von $v$ liegen in $\Bbbk'$, und mindestens eine davon kann -nicht in $\Bbbk$ liegen. -Das bedeutet aber nicht, dass man diese Vektoren nicht für theoretische -Überlegungen über von $\Bbbk'$ unabhängige Eigenschaften der Matrix $A$ machen. -Das folgende Beispiel soll diese Idee illustrieren. - -\begin{beispiel} -Wir arbeiten in diesem Beispiel über dem Körper $\Bbbk=\mathbb{Q}$. -Die Matrix -\[ -A=\begin{pmatrix} --4&7\\ --2&4 -\end{pmatrix} -\in -M_2(\mathbb{Q}) -\] -hat das charakteristische Polynom -\[ -\chi_A(x) -= -\left| -\begin{matrix} --4-x&7\\-2&4-x -\end{matrix} -\right| -= -(-4-x)(4-x)-7\cdot(-2) -= --16+x^2+14 -= -x^2-2. -\] -Die Nullstellen sind $\pm\sqrt{2}$ und damit nicht in $\mathbb{Q}$. -Wir gehen daher über zum Körper $\mathbb{Q}(\!\sqrt{2})$, in dem -sich zwei Nullstellen $\lambda=\pm\sqrt{2}$ finden lassen. -Zu jedem Eigenwert lässt sich auch ein Eigenvektor -$v_{\pm\sqrt{2}}\in \mathbb{Q}(\!\sqrt{2})^2$, und unter Verwendung dieser -Basis bekommt die Matrix $A'=TAT^{-1}$ Diagonalform. -Die Transformationsmatrix $T$ enthält Matrixelemente aus -$\mathbb{Q}(\!\sqrt{2})$, die nicht in $\mathbb{Q}$ liegen. -Die Matrix $A$ lässt sich also über dem Körper $\mathbb{Q}(\!\sqrt{2})$ -diagonalisieren, nicht aber über dem Körper $\mathbb{Q}$. - -Da $A'$ Diagonalform hat mit $\pm\sqrt{2}$ auf der Diagonalen, folgt -$A^{\prime 2} = 2E$, die Matrix $A'$ erfüllt also die Gleichung -\begin{equation} -A^{\prime 2}-E= \chi_{A}(A) = 0. -\label{buch:grundlagen:eqn:cayley-hamilton-beispiel} -\end{equation} -Dies is ein Spezialfall des Satzes von Cayley-Hamilton~\ref{XXX} -welcher besagt, dass jede Matrix $A$ eine Nullstelle ihres -charakteristischen Polynoms ist: $\chi_A(A)=0$. -Die Gleichung~\ref{buch:grundlagen:eqn:cayley-hamilton-beispiel} -wurde zwar in $\mathbb{Q}(\!\sqrt{2})$ hergeleitet, aber in ihr kommen -keine Koeffizienten aus $\mathbb{Q}(\!\sqrt{2})$ vor, die man nicht auch -in $\mathbb{Q}$ berechnen könnte. -Sie gilt daher ganz allgemein. -\end{beispiel} - -\begin{beispiel} -Die Matrix -\[ -A=\begin{pmatrix} -32&-41\\ -24&-32 -\end{pmatrix} -\in -M_2(\mathbb{R}) -\] -über dem Körper $\Bbbk = \mathbb{R}$ -hat das charakteristische Polynom -\[ -\det(A-xE) -= -\left| -\begin{matrix} -32-x&-41 \\ -25 &-32-x -\end{matrix} -\right| -= -(32-x)(-32-x)-25\cdot(-41) -= -x^2-32^2 + 1025 + &0&1\\ + &0&0 +\end{array} +\right) = -x^2+1. +N_3. +\qedhere \] -Die charakteristische Gleichung $\chi_A(x)=0$ hat in $\mathbb{R}$ -keine Lösungen, daher gehen wir zum Körper $\Bbbk'=\mathbb{C}$ über, -in dem dank dem Fundamentalsatz der Algebra alle Nullstellen zu finden -sind, sie sind $\pm i$. -In $\mathbb C$ lassen sich dann auch Eigenvektoren finden, man muss dazu die -folgenden linearen Gleichungssyteme lösen: -\begin{align*} -\begin{tabular}{|>{$}c<{$}>{$}c<{$}|} -32-i&-41\\ -25 &-32-i -\end{tabular} -& -\rightarrow -\begin{tabular}{|>{$}c<{$}>{$}c<{$}|} -1 & t\\ -0 & 0 -\end{tabular} -& -\begin{tabular}{|>{$}c<{$}>{$}c<{$}|} -32+i&-41\\ -25 &-32+i -\end{tabular} -& -\rightarrow -\begin{tabular}{|>{$}c<{$}>{$}c<{$}|} -1 & \overline{t}\\ -0 & 0 -\end{tabular}, -\intertext{wobei wir $t=-41/(32-i) =-41(32+i)/1025= -1.28 -0.04i = (64-1)/50$ -abgekürzt haben. -Die zugehörigen Eigenvektoren sind} -v_i&=\begin{pmatrix}t\\i\end{pmatrix} -& -v_{-i}&=\begin{pmatrix}\overline{t}\\i\end{pmatrix} -\end{align*} -Mit den Vektoren $v_i$ und $v_{-i}$ als Basis kann die Matrix $A$ als -komplexe Matrix, also mit komplexem $T$ in die komplexe Diagonalmatrix -$A'=\operatorname{diag}(i,-i)$ transformiert werden. -Wieder kann man sofort ablesen, dass $A^{\prime2}+E=0$, und wieder kann -man schliessen, dass für die relle Matrix $A$ ebenfalls $\chi_A(A)=0$ -gelten muss. \end{beispiel} - - - diff --git a/buch/chapters/40-eigenwerte/jnorm.maxima b/buch/chapters/40-eigenwerte/jnorm.maxima new file mode 100644 index 0000000..d4c349b --- /dev/null +++ b/buch/chapters/40-eigenwerte/jnorm.maxima @@ -0,0 +1,6 @@ +J: matrix([a+b*%i, 1], [0, a+b*%i]); +v: matrix([cos(t)],[sin(t)]); +w: J.v; +n: expand(transpose(conjugate(w)).w); +d: expand(diff(n,t)); + diff --git a/buch/chapters/40-eigenwerte/normalformen.tex b/buch/chapters/40-eigenwerte/normalformen.tex index 9169f65..e59f1dc 100644 --- a/buch/chapters/40-eigenwerte/normalformen.tex +++ b/buch/chapters/40-eigenwerte/normalformen.tex @@ -6,23 +6,27 @@ \section{Normalformen \label{buch:section:normalformen}} \rhead{Normalformen} -In den Beispielen im vorangegangenen wurde wiederholt der Trick +In den Beispielen im vorangegangenen Abschnitt wurde wiederholt der Trick verwendet, den Koeffizientenkörper so zu erweitern, dass das charakteristische Polynom in Linearfaktoren zerfällt und für jeden Eigenwert Eigenvektoren gefunden werden können. Diese Idee ermöglicht, eine Matrix in einer geeigneten Körpererweiterung -in eine besonders einfache Form zu bringen, das Problem dort zu lösen. -Anschliessend kann man sich darum kümmern in welchem Mass die gewonnenen +in eine besonders einfache Form zu bringen und das Problem dort zu lösen. +Anschliessend kann man sich darum kümmern, in welchem Mass die gewonnenen Resultate wieder in den ursprünglichen Körper transportiert werden können. +Die dabei verwendete ``einfache Form'' war jeweils etwas ad hoc. +In diesem Abschnitt sollen jetzt etwas systematischer geeignete Normalformen +zusammengestellt werden. \subsection{Diagonalform} +\index{Diagonalform}% Sei $A$ eine beliebige Matrix mit Koeffizienten in $\Bbbk$ und sei $\Bbbk'$ eine Körpererweiterung von $\Bbbk$ derart, dass das charakteristische Polynom in Linearfaktoren \[ \chi_A(x) = -(x-\lambda_1)^{k_1}\cdot (x-\lambda_2)^{k_2}\cdot\dots\cdot (x-\lambda_m)^{k_m} +(x-\lambda_1)^{k_1}\cdot (x-\lambda_2)^{k_2}\dots(x-\lambda_m)^{k_m} \] mit Vielfachheiten $k_1$ bis $k_m$ zerfällt, $\lambda_i\in\Bbbk'$. Zu jedem Eigenwert $\lambda_i$ gibt es sicher einen Eigenvektor, wir @@ -31,35 +35,35 @@ aus Eigenvektoren gibt. In dieser Basis bekommt die Matrix Diagonalform, wobei auf der Diagonalen nur Eigenwerte vorkommen können. Man kann die Vektoren so anordnen, dass die Diagonalmatrix in Blöcke -der Form $\lambda_iE$ zerfällt +der Form $\lambda_iI$ zerfällt \[ \def\temp#1{\multicolumn{1}{|c}{\raisebox{0pt}[12pt][7pt]{\phantom{x}$#1$}\phantom{x}}} A' =\left( \begin{array}{cccc} \cline{1-1} -\temp{\lambda_1E} &\multicolumn{1}{|c}{}& & \\ +\temp{\lambda_1I} &\multicolumn{1}{|c}{}& & \\ \cline{1-2} - &\temp{\lambda_2E}&\multicolumn{1}{|c}{}& \\ + &\temp{\lambda_2I}&\multicolumn{1}{|c}{}& \\ \cline{2-3} & &\temp{\ddots}&\multicolumn{1}{|c}{}\\ \cline{3-4} - & & &\multicolumn{1}{|c|}{\raisebox{0pt}[12pt][7pt]{\phantom{x}$\lambda_mE$}\phantom{x}}\\ + & & &\multicolumn{1}{|c|}{\raisebox{0pt}[12pt][7pt]{\phantom{x}$\lambda_mI$}\phantom{x}}\\ \cline{4-4} \end{array} \right) \] -Über die Grösse eines solchen $\lambda_iE$-Blockes können wir zum jetzigen +Über die Grösse eines solchen $\lambda_iI$-Blockes können wir zum jetzigen Zeitpunkt noch keine Aussagen machen. -Die Matrizen $A-\lambda_kE$ enthalten jeweils einen Block aus lauter +Die Matrizen $A-\lambda_kI$ enthalten jeweils einen Block aus lauter Nullen. Das Produkt all dieser Matrizen ist daher \[ -(A-\lambda_1E) -(A-\lambda_2E) +(A-\lambda_1I) +(A-\lambda_2I) \cdots -(A-\lambda_mE) +(A-\lambda_mI) = 0. \] @@ -69,6 +73,7 @@ $m(A)=0$. Dies ist auch das Polynom von kleinstmöglichem Grad, denn für jeden Eigenwert muss ein entsprechender Linearfaktor in so einem Polynom vorkommen. Das Polynom $m(x)$ ist daher das Minimalpolynom der Matrix $A$. +\index{Minimalpolynome}% Da jeder Faktor in $m(x)$ auch ein Faktor von $\chi_A(x)$ ist, folgt wieder $\chi_A(A)=0$. Ausserdem ist über dem Körper $\Bbbk'$ das Polynom $m(x)$ ein Teiler @@ -76,6 +81,7 @@ des charakteristischen Polynoms $\chi_A(x)$. \subsection{Jordan-Normalform \label{buch:subsection:jordan-normalform}} +\index{Jordan-Normalform}% Die Eigenwerte einer Matrix $A$ können als Nullstellen des charakteristischen Polynoms gefunden werden. Da der Körper $\Bbbk$ nicht unbedingt algebraische abgeschlossen ist, @@ -90,9 +96,7 @@ Wir nehmen im Folgenden an, dass (x-\lambda_1)^{k_1} \cdot (x-\lambda_2)^{k_2} -\cdot -\dots -\cdot +\cdots (x-\lambda_l)^{k_l} \] ist mit $\lambda_i\in\Bbbk'$. @@ -101,9 +105,9 @@ Nach Satz~\ref{buch:eigenwerte:satz:zerlegung-in-eigenraeume} liefern die verallgemeinerten Eigenräume $V_i=\mathcal{E}_{\lambda_i}(A)$ eine Zerlegung von $V$ in invariante Eigenräume \[ -V=V_1\oplus V_2\oplus \dots\oplus V_l, +V=V_1\oplus V_2\oplus \dots\oplus V_l \] -derart, dass $A-\lambda_iE$ auf $V_i$ nilpotent ist. +derart, dass $A-\lambda_iI$ auf $V_i$ nilpotent ist. Wählt man in jedem der Unterräume $V_i$ eine Basis, dann zerfällt die Matrix $A$ in Blockmatrizen \begin{equation} @@ -122,17 +126,17 @@ A' \cline{4-4} \end{array} \right) -\label{buch:eigenwerte:eqn:allgnilpotent} +\label{buch:eigenwerte:eqn:allgjordan} \end{equation} wobei, $A_i$ Matrizen mit dem einzigen Eigenwert $\lambda_i$ sind. Nach Satz~\ref{buch:eigenwerte:satz:allgnilpotent} kann man in den Unterräume die Basis zusätzlich so wählen, dass -die entstehenden Blöcke $A_i-\lambda_i E$ spezielle nilpotente Matrizen -aus lauter Null sind, die höchstens unmittelbar über der Diagonalen -Einträge $1$ haben kann. +die entstehenden Blöcke $A_i-\lambda_i I$ spezielle nilpotente Matrizen sind, +die lauter Nullen als Einträge haben mit Ausnahme +höchstens der Einträge unmittelbar über der Diagonalen, die $1$ sein können. Dies bedeutet, dass sich immer eine Basis so wählen lässt, dass die -Matrix $A_i$ zerfällt in sogenannte Jordan-Blöcke. +Matrix $A_i$ in sogenannte Jordan-Blöcke zerfällt. \begin{definition} Ein $m$-dimensionaler {\em Jordan-Block} ist eine $m\times m$-Matrix @@ -150,7 +154,7 @@ J_m(\lambda) & & & & & \lambda \end{pmatrix}. \] -Eine {\em Jordan-Matrix} ist eine Blockmatrix Matrix +Eine {\em Jordan-Matrix} ist eine Blockmatrix der Form \[ J = @@ -180,7 +184,7 @@ Es gilt \[ \chi_{J_m(\lambda)}(x) = -\det (J_m(\lambda) - xE) +\det (J_m(\lambda) - xI) = (\lambda-x)^m \] @@ -192,14 +196,12 @@ bis $J_{m_p}(\lambda)$ ist = \chi_{J_{m_1}(\lambda)}(x) \chi_{J_{m_2}(\lambda)}(x) -\cdot -\dots -\cdot +\cdots \chi_{J_{m_p}(\lambda)}(x) = (\lambda-x)^{m_1} (\lambda-x)^{m_2} -\cdot\dots\cdot +\cdots (\lambda-x)^{m_p} = (\lambda-x)^m. @@ -240,6 +242,7 @@ charakteristischen Polynom $\chi_A(x)$. \begin{satz}[Cayley-Hamilton] +\label{buch:normalformen:satz:cayley-hamilton} Ist $A$ eine $n\times n$-Matrix über dem Körper $\Bbbk$, dann gilt $\chi_A(A)=0$. \end{satz} @@ -264,17 +267,13 @@ $\chi_A(x)$ ein, erhält man \[ \chi_A(J_i) = -(\lambda_1E - J_1)^{m_1} -\cdot -\ldots -\cdot +(\lambda_1I - J_1)^{m_1} +\cdots \underbrace{ -(\lambda_iE - J_i)^{m_i} +(\lambda_iI - J_i)^{m_i} }_{\displaystyle=0} -\cdot -\ldots -\cdot -(\lambda_iE - J_p)^{m_p} +\cdots +(\lambda_iI - J_p)^{m_p} = 0. \] @@ -289,7 +288,7 @@ $\chi_A(A)$ kann in $\Bbbk$ ausgeführt werden, also ist $\chi_A(A)=0$. Aus dem Beweis kann man auch noch eine strengere Bedingung ableiten. Auf jedem verallgemeinerten Eigenraum $\mathcal{E}_{\lambda_i}(A)$ ist $A_i-\lambda_i$ nilpotent, es gibt also einen minimalen Exponenten -$q_i$ derart, dass $(A_i-\lambda_iE)^{q_i}=0$ ist. +$q_i$ derart, dass $(A_i-\lambda_iI)^{q_i}=0$ ist. Wählt man eine Basis in jedem verallgemeinerten Eigenraum derart, dass $A_i$ eine Jordan-Matrix ist, kann man wieder zeigen, dass für das Polynom @@ -298,9 +297,7 @@ m_A(x) = (x-\lambda_1x)^{q_1} (x-\lambda_2x)^{q_2} -\cdot -\ldots -\cdot +\cdots (x-\lambda_px)^{q_p} \] gilt $m_A(A)=0$. @@ -312,17 +309,17 @@ $m_A(x)$ ist das {\em Minimalpolynom} der Matrix $A$. Polynom $\chi_A(x)$ in Linearfaktoren zerfällt, ist das Minimalpolynom von $A$ das Polynom \[ +m_A(x) += m(x) = (x-\lambda_1)^{q_1} (x-\lambda_2)^{q_2} \cdots -\ldots -\cdots (x-\lambda_p)^{q_p} \] wobei $q_i$ der kleinste Index ist, für den die $q_i$-te Potenz -derEinschränkung von $A-\lambda_i E$ auf den verallgemeinerten Eigenraum +der Einschränkung von $A-\lambda_i I$ auf den verallgemeinerten Eigenraum $\mathcal{E}_{\lambda_i}(A)$ verschwindet. Es ist das Polynom geringsten Grades über $\Bbbk'$, welches $m(A)=0$ erfüllt. \end{satz} @@ -465,6 +462,8 @@ d_{k-1}. Für $k=1$ fallen die Terme $c_{k-1}$ und $d_{k-1}$ weg. In der Basis $\mathcal{D}=\{c_1,d_1,\dots,c_n,d_n\}$ hat die Matrix also die {\em reelle Normalform} +\index{relle Normalform}% +\index{Normalform, reelle}% \begin{equation} \def\temp#1{\multicolumn{1}{|c}{#1\mathstrut}} \def\semp#1{\multicolumn{1}{c|}{#1\mathstrut}} @@ -478,12 +477,12 @@ A_{\text{reell}} \cline{1-6} & &\temp{\alpha}& \beta&\temp{ 1}& 0&\temp{} & & & &&\\ & &\temp{-\beta}&\alpha&\temp{ 0}& 1&\temp{} & & & &&\\ -\cline{3-6} - & & & &\temp{\alpha}& \beta&\temp{} & & & &&\\ - & & & &\temp{-\beta}&\alpha&\temp{} & & & &&\\ -\cline{5-8} - & & & & & &\temp{\phantom{0}}&\phantom{0}&\temp{ }& &&\\ - & & & & & &\temp{\phantom{0}}&\phantom{0}&\temp{ }& &&\\ +\cline{3-8} + & & & &\temp{\alpha}& \beta&\temp{} & &\temp{}& &&\\ + & & & &\temp{-\beta}&\alpha&\temp{} & &\temp{}& &&\\ +\cline{5-10} + & & & & & &\temp{\phantom{0}}&\phantom{0}&\temp{ }& &\temp{}&\\ + & & & & & &\temp{\phantom{0}}&\phantom{0}&\temp{ }& &\temp{}&\\ \cline{7-12} & & & & & & & &\temp{\alpha}& \beta&\temp{ 1}&\semp{ 0}\\ & & & & & & & &\temp{-\beta}&\alpha&\temp{ 0}&\semp{ 1}\\ diff --git a/buch/chapters/40-eigenwerte/spektralradius.tex b/buch/chapters/40-eigenwerte/spektralradius.tex index a36dc33..1cdaf35 100644 --- a/buch/chapters/40-eigenwerte/spektralradius.tex +++ b/buch/chapters/40-eigenwerte/spektralradius.tex @@ -21,23 +21,28 @@ Funktionen $f$ berechnen zu können. % \subsection{Polynom-Funktionen \label{buch:subsection:polynom-funktionen}} +Die einfachsten Funktionen $f(x)$, für die der Wert $f(A)$ +auf offensichtliche Weise berechnet werden kann, sind Polynome. +Die Jordan-Normalform kann dabei helfen, die Potenzen von $A$ +zu berechnen. + In diesem Abschnitt ist $B\in M_n(\Bbbk)$ und $\Bbbk'\supset\Bbbk$ ein -Körper, über dem das charakteristische Polynome $\chi_A(x)$ in +Körper, über dem das charakteristische Polynome $\chi_A(X)$ in Linearfaktoren \[ -\chi_A(x) +\chi_A(X) = -(\lambda_1-x)^{m_1}(\lambda_2-x)^{m_2}\cdot\ldots\cdot(\lambda_p-x)^{m_p} +(\lambda_1-X)^{m_1}(\lambda_2-X)^{m_2}\cdots(\lambda_p-X)^{m_p} \] zerfällt. -Für jedes beliebige Polynome $p(X)\in\Bbbk[X]$ der Form +Für jedes beliebige Polynom $p(X)\in\Bbbk[X]$ der Form \[ -p(X) = a_nX^n + a_{n-1}X^{n-1} + \dots a_1x + a_0 +p(X) = a_nX^n + a_{n-1}X^{n-1} + \dots + a_1x + a_0 \] kann man auch \[ -p(A) = a_nA^n + a_{n-1}A^{n-1} + \dots a_1A + a_0E +p(A) = a_nA^n + a_{n-1}A^{n-1} + \dots + a_1A + a_0I \] berechnen. In der Jordan-Normalform können die Potenzen $A^k$ leicht zusammengstellt @@ -48,6 +53,7 @@ Die $k$-te Potenz von $J_n(\lambda)$ ist die Matrix mit \begin{equation} J_n(\lambda)^k = +\renewcommand{\arraystretch}{1.4} \begin{pmatrix} \lambda^k & \binom{k}{1}\lambda^{k-1} @@ -70,6 +76,13 @@ J_n(\lambda)^k & \dots &\binom{k}{n-3}\lambda^{k-n+3} \\ +0 + & 0 + & 0 + & \lambda^k + & \dots + &\binom{k}{n-4}\lambda^{k-n+4} +\\ \vdots &\vdots &\vdots &\vdots &\ddots & \vdots \\ 0 & 0 & 0 & 0 & \dots & \lambda^k @@ -78,7 +91,7 @@ J_n(\lambda)^k \end{equation} mit den Matrixelementen \[ -(J_n(\lambda)^k)_{ij} +(J_n(\lambda)^k)_{i\!j} = \binom{k}{j-i}\lambda^{k-j+i}. \] @@ -88,12 +101,12 @@ Die Binomialkoeffizienten verschwinden für $j<i$ und $j>i+k$. \begin{proof}[Beweis] Die Herkunft der Binomialkoeffizienten wird klar, wenn man \[ -J_n(\lambda) = \lambda E + N_n +J_n(\lambda) = \lambda I + N_n \] schreibt, wobei $N_n$ die Matrix \eqref{buch:eigenwerte:eqn:nnilpotent} ist. Die Potenzen von $N_n$ haben die Matrix-Elemente \[ -(N_n^k)_{ij} +(N_n^k)_{i\!j} = \delta_{i,j-k} = @@ -104,7 +117,7 @@ Die Potenzen von $N_n$ haben die Matrix-Elemente \] sie haben also Einsen genau dort, wo in der \label{buch:eigenwerte:eqn:Jnkpotenz} die Potenz $\lambda^{k}$ steht. -Die $kt$-te Potenz von $J_n(\lambda)$ kann dann mit dem binomischen +Die $k$-te Potenz von $J_n(\lambda)$ kann dann mit dem binomischen Satz berechnet werden: \[ J_n(\lambda)^k @@ -114,7 +127,8 @@ J_n(\lambda)^k dies ist genau die Form \eqref{buch:eigenwerte:eqn:Jnkpotenz}. \end{proof} -Wir haben bereits gesehen, dass $\chi_A(A)=0$, ersetzt man also das +Wir haben bereits gesehen, dass $\chi_A(A)=0$. +Ersetzt man also das Polynom $p(X)$ durch $p(X)+\chi_A(X)$, dann ändert sich am Wert \[ (p+\chi_A)(A) @@ -126,7 +140,8 @@ p(A) nichts. Man kann also nicht erwarten, dass verschiedene Polynome $p(X)$ zu verschiedenen Matrizen $p(A)$ führen. -Doch welche Unterschiede zwischen Polynomen wirken sich genau aus? +Doch genau welche Unterschiede zwischen Polynomen wirken sich +auf den Wert $p(A)$ aus? \begin{satz} Für zwei Polynome $p(X)$ und $q(X)$ ist genau dann $p(A)=q(A)$, wenn @@ -149,13 +164,13 @@ m(X) = (\lambda_1-X)^{q_1} (\lambda_2-X)^{q_2} -\cdot\ldots -\cdot +\cdots (\lambda_p-X)^{q_p}, \] wobei $q_i$ die Dimension des grössten Jordan-Blocks ist, der in der Jordan-Normalform vorkommt. -Zwei Polynome $p_1(X)$ und $p_2(X)$ haben genau dann den gleichen Wert, +Zwei Polynome $p_1(X)$ und $p_2(X)$ ergeben genau dann den gleichen Wert +auf $A$, wenn die Differenz $p_1(X)-p_2(X)$ genau die Nullstellen $\lambda_1,\dots,\lambda_p$ mit Vielfachheiten $q_1,\dots,q_p$ hat. @@ -172,18 +187,18 @@ A \] mit dem charakteristischen Polynom \[ -\chi_A(x) +\chi_A(X) = --x^3+7x^2-16 x+12 +-X^3+7X^2-16 X+12 = --(x-3)(x-2)^2. +-(X-3)(X-2)^2. \] Daraus kann man bereits ablesen, dass das Minimalpolynom $m(X)$ von $A$ entweder $(X-2)(X-3)$ oder $(X-2)^2(X-3)$ ist. Es genügt also nachzuprüfen, ob $p(A)=0$ für das Polynom $p(X)=(X-2)(X-3) = X^2-5X+6$ ist. Tatsächlich sind die Potenzen von $A$: -\[ +\begin{equation} A^2= \begin{pmatrix} 0& 36& -16 \\ @@ -197,8 +212,9 @@ A^3= -12& -36& 28\\ -24&-126& 83 \end{pmatrix} -\] -und daraus kann man jetzt $P(A)$ berechnen: +\label{buch:eigenwerte:eqn:A2A3} +\end{equation} +und daraus kann man jetzt $p(A)$ berechnen: \begin{equation} p(A) = @@ -229,9 +245,11 @@ p(A) = \begin{pmatrix}1\\1\\2\end{pmatrix} \begin{pmatrix}1&-9&4\end{pmatrix} +\ne 0 \label{buch:eigenwerte:eqn:nichtminimalpolynom} \end{equation} -Also ist tatsächlich $(X-2)^2(X-3)$ das Minimalpolynom. +Daher kann $p(X)$ nicht das Minimalpolynom $A$ +sein, daher muss $(X-2)^2(X-3)$ das Minimalpolynom sein. Das Quadrat des Polynoms $p(X)$ ist $p(X)^2 = (X-2)^2(X-3)^2$, es hat das Minimalpolynom als Teiler, also muss $p(A)^2=0$ sein. @@ -254,11 +272,12 @@ wie zu erwarten war. Wenn sich zwei Polynome nur um das charakteristische Polynom unterscheiden, dann haben sie den gleichen Wert auf $A$. -Das Polynom $p_1(X)=X^3$ unterschiedet sich vom Polynom $p_2(X)=7X^2-16X+12$ +Das Polynom $p_1(X)=X^3$ unterschiedet sich vom Polynom +$p_2(X)=7X^2-16X+12=\chi_A(X)+X^3=p_1(X)+\chi_A(X)$ um das charakteristische Polynom, welches wir bereits als das Minimalpolynom von $A$ erkannt haben. -Die dritte Potenz $A^3$ von $A$ muss sich daher auch mit $p_2(X)$ berechnen -lassen: +Die dritte Potenz $A^3=p_1(A)$ von $A$ muss sich daher auch als $p_2(A)$ +berechnen lassen: \[ 7 \begin{pmatrix} @@ -285,9 +304,9 @@ lassen: -24&-126& 83 \end{pmatrix} = -A^3. -\qedhere +A^3, \] +wie in \eqref{buch:eigenwerte:eqn:A2A3} vorsorglich berechnet worden ist. \end{beispiel} \begin{satz} @@ -299,9 +318,11 @@ für alle Eigenwerte $\lambda$ von $A$. Über dem Körper der komplexen Zahlen ist die Bedingung, dass die Differenz $d(X)=p_1(X)-p_2(X)$ vom Minimalpolynom geteilt werden muss, gleichbedeutend -damit, dass $p_1(X)$ und $p_2(X)$ den gleichen Wert und gleiche Ableitungen -bis zur Ordnung $q_i-1$ haben in allen Eigenwerten $\lambda_i$, wobei -$q_i$ der Exponent von $\lambda_i-X$ im Minimalpolynom von $A$ ist. +damit, dass $p_1(X)$ und $p_2(X)$ die gleichen Nullstellen mit den gleichen +Vielfachheiten haben. +Eine andere Art, dies auszudrücken, ist, dass $p_1(x)$ und $p_2(X)$ +die gleichen Werte und Ableitungen bis zur Ordnung $q_i-1$ haben, wenn +$q_i$ der Exponente von $\lambda_I-X$ im Minimalpolynom von $A$ ist. Das Beispiel illustriert auch noch ein weiteres wichtiges Prinzip. Schreiben wir das Minimalpolynom von $A$ in der Form @@ -317,10 +338,10 @@ A^i = A^{i-k}A^k = -A^{i-k}(-a_{k-1}A^{k-1}+ \dots + a_1 A + a_0E) +A^{i-k}(-a_{k-1}A^{k-1}+ \dots + a_1 A + a_0I) \] in einer Linearkombination kleinerer Potenzen reduzieren. -Jedes Polynom vom Grad $\ge k$ kann also reduizert werden in +Jedes Polynom vom Grad $\ge k$ kann also reduziert werden in ein Polynom vom Grad $<k$ mit dem gleichen Wert auf $A$. \begin{satz} @@ -336,6 +357,7 @@ vom Grad $\deg q<\deg m$ mit $p(A)=q(A)$. \subsection{Approximation von $f(A)$ \label{buch:subsection:approximation}} Die Quadratwurzelfunktion $x\mapsto\sqrt{x}$ lässt sich nicht durch ein +\index{Quadratwurzelfunktion}% Polynom darstellen, es gibt also keine direkte Möglichkeit, $\sqrt{A}$ für eine beliebige Matrix zu definieren. Wir können versuchen, die Funktion durch ein Polynom zu approximieren. @@ -358,9 +380,19 @@ Solche Polynome gibt es dank dem Satz von Stone-Weierstrass immer: \begin{satz}[Stone-Weierstrass] Ist $I\subset\mathbb{R}$ kompakt, dann lässt sich jede stetige Funktion +$f(x)$ durch eine Folge $p_n(x)$ beliebig genau approximieren. \end{satz} +Die Hoffnung ist, $f(A)$ als Grenzwert der Approximationen $p_n(A)$ +zu definieren. +Dazu muss sichergestellt sein, dass verschiedene Approximationen +der Funktion $f$ den gleichen Grenzwert $\lim_{n\to\infty}p_n(A)$ +ergeben. +Im Folgenden soll genauer untersucht werden, ob sich von der +Konvergenz einer Folge $p_n(x)$ auf die Konvergenz von $p_n(A)$ +geschlossen werden kann. + Wir haben schon gezeigt, dass es dabei auf die höheren Potenzen gar nicht ankommt, nach Satz~\ref{buch:eigenwerte:satz:reduktion} kann man ein approximierendes Polynom immer durch ein Polynom von kleinerem Grad @@ -407,8 +439,99 @@ Faktor $\frac23$ kleiner geworden ist. \end{beispiel} \begin{beispiel} -Wir berechnen die Norm eines Jordan-Blocks. - +Wir berechnen die Norm eines $2\times2$-Jordan-Blocks. +Ein $2$-dimensionaler Einheitsvektor kann als +\[ +v\colon +t\mapsto v(t)= +\begin{pmatrix}\cos t\\\sin t\end{pmatrix} +\] +parametrisiert werden. +Für die Zahl $\lambda=a+bi$ bildet der +Jordanblock $J_2(\lambda)$ den Vektor $v(t)$ auf den Vektor +\[ +J_2(\lambda)v(t) += +\begin{pmatrix} +\lambda&1\\ +0&\lambda +\end{pmatrix} +\begin{pmatrix}\cos t\\\sin t\end{pmatrix} += +\begin{pmatrix} +\lambda\cos t + \sin t\\ +\lambda\sin t +\end{pmatrix} +\] +ab +mit der Länge +\begin{align*} +|J_2(\lambda)v(t)|^2 +&= +|\lambda\cos t + \sin t|^2 + |\lambda\sin t|^2 += +(\Re\lambda \cos t + \sin t)^2 ++ +(\Im\lambda \cos t)^2 ++ +|\lambda|^2 \sin^2t +\\ +&= +a^2\cos^2 t ++ +2a\cos t\sin t + \sin^2 t + b^2\cos^2t + (a^2+b^2) \sin^2 t +\\ +&= +(a^2+b^2)(\cos^2t + \sin^2t) + \sin^2t + 2a\cos t\sin t += +|\lambda|^2+2a\cos t\sin t + \sin^2 t +\\ +&= +|\lambda|^2 + a\sin 2t + \frac12(1-\cos 2t). +\end{align*} +Um den maximalen Wert zu finden, leiten wir nach $t$ ab und finden +\begin{align*} +\frac{d}{dt} +|J_2(\lambda)v(t)|^2 +&= +2a\cos 2t ++ +\sin 2t += +0. +\end{align*} +Dividieren wir durch $\cos t$, ergibt sich die Gleichung +\[ +\tan 2t = -2a +\quad\Rightarrow\quad +2t += +\arctan(-2a) +\quad\Rightarrow\quad +\left\{ +\renewcommand{\arraystretch}{2.1} +\setlength\arraycolsep{1pt} +\begin{array}{ccc} +\cos 2t &=& \displaystyle\frac{1}{\sqrt{1+4a^2}}\phantom{.}\\ +\sin 2t &=& \displaystyle\frac{-2a}{\sqrt{1+4a^2}}. +\end{array} +\right. +\] +Setzt man dies in die ursprüngliche Formel für die Länge des +Bildvektors ein, erhält man +\begin{align*} +\|J_2\|^2 += +|J_2(\lambda)v(t)|^2 +&= +|\lambda|^2 + \frac{-2a}{\sqrt{1+4a^2}} + \frac12\biggl(1-\frac{1}{\sqrt{1+4a^2}}\biggr) +\\ +&= +|\lambda|^2 ++ \frac12 +-\frac{1+4a}{2\sqrt{1+4a^2}}. +\end{align*} +Für $a\to\infty$ wächst dies asymptotisch wie $a^2-1$. \end{beispiel} % @@ -416,57 +539,111 @@ Wir berechnen die Norm eines Jordan-Blocks. % \subsection{Potenzreihen \label{buch:subsection:potenzreihen}} +Funktionen, die eine konvergente Potenzreihenentwicklung +\begin{equation} +f(z) += +\sum_{k=0}^\infty a_kz^k +\label{buch:eigenwerte:eqn:potenzreihe} +\end{equation} +\index{Potenzreihe} +haben, wie +zum Beispiel $e^x$, $\sin x$ oder $\cos x$, haben eine in der Folge +der Partialsummen +\[ +p_n(z) = \sum_{k=0}^n a_kz^k +\] +eine Approximation mit Polynomen. +Nach dem {\em Wurzelkriterium} ist die +Reihe~\eqref{buch:eigenwerte:eqn:potenzreihe} +konvergent, wenn +\[ +\limsup_{k\to\infty} \sqrt[n]{|a_kz^k|} < 1 +\] +ist. +\index{Wurzelkriterium}% +Dies führt auf die Formel $1/\varrho = \limsup_{k\to\infty}|a_k|^{\frac1k}$ +für den Konvergenzradius der Potenzreihe. - - +Setzt man die Matrix $M\in M_r(\Bbbk)$ in die Potenzreihe ein, +folgt, dass +\[ +\limsup_{n\to\infty} \sqrt[n]{\|a_kM^n\|} +\le +\limsup_{n\to\infty} \sqrt[n]{|a_n|} +\cdot +\limsup_{n\to\infty} \|M^k\|^{\frac1k} += +\frac{1}{\varrho} +\limsup_{n\to\infty} \|M^k\|^{\frac1k} +\] +sein muss. Dies führt uns auf die Grösse \begin{equation} \pi(M) = -\limsup_{n\to\infty} \|M^n\|^\frac1n. +\limsup_{n\to\infty} \|M^n\|^\frac1n, \label{buch:eqn:gelfand-grenzwert} \end{equation} +die +darüber entscheidet, ob die Potenzreihe $f(A)$ konvergiert. + +Die Zahl $\pi(M)$ erlaubt zunächst einmal zu bestimmen, wie +sich die Potenzen $M^k$ entwickeln. +Für Zahlen ist diese Frage sehr einfach zu entscheiden: wenn $q>1$ ist, +dann geht $q^n\to\infty$, wenn $|q|<1$ ist, dann geht $q^n\to 0$. +Für Matrizen ist die Frage etwas schieriger. +Man kann sich vorstellen, dass eine Streckung in einer Richtung +von einer Stauchung in eine andere Richtung kompensiert wird, wenn +dazwischen eine Drehung stattfindet. +Es ist also durchaus möglich, dass $\|M\|>1$ ist, die +Iterierten $M^k$ aber trotzdem gegen $0$ gehen. + Ist $\pi(M) > 1$, dann gibt es Anfangsvektoren $v$ für die Iteration, für die $M^kv$ über alle Grenzen wächst. Ist $\pi(M) < 1$, dann wird jeder Anfangsvektor $v$ zu einer Iterationsfolge $M^kv$ führen, die gegen $0$ konvergiert. -Die Kennzahl $\pi(M)$ erlaubt also zu entscheiden, ob ein -Iterationsverfahren konvergent ist. +Die Kennzahl $\pi(M)$ erlaubt also zu entscheiden, ob die +Iteration konvergent ist. \index{Konvergenzbedingung}% -Die Berechnung von $\pi(M)$ als Grenzwert ist sehr unhandlich. +\begin{definition} +\label{buch:eigenwerte:def:gelfand-radius} +Der Grenzwert +\[ +\pi(M) += +\limsup_{n\to\infty} \|M^k\|^{\frac1k} +\] +heisst {\em Gelfand-Radius} der Matrix $M$. +\index{Gelfand-Radius}% +\end{definition} + + +% +% Gelfand-Radius und Eigenwerte +% +\subsection{Gelfand-Radius und Eigenwerte +\label{buch:subsection:potenzreihen}} +Die Berechnung des Gelfand-Radius als Grenzwert ist sehr unhandlich. Viel einfacher ist der Begriff des Spektralradius. \index{Spektralradius}% \begin{definition} \label{buch:definition:spektralradius} Der {\em Spektralradius} der Matrix $M$ ist der Betrag des betragsgrössten +\index{Spektralradius}% Eigenwertes. \end{definition} -% -% Gelfand-Radius und Eigenwerte -% -\subsection{Gelfand-Radius und Eigenwerte -\label{buch:subsection:spektralradius}} -In Abschnitt~\ref{buch:subsection:konvergenzbedingung} -ist der Gelfand-Radius mit Hilfe eines Grenzwertes definiert worden. -\index{Gelfand-Radius}% -Nur dieser Grenzwert ist in der Lage, über die Konvergenz eines -Iterationsverfahrens Auskunft zu geben. -Der Grenzwert ist aber sehr mühsam zu berechnen. -\index{Grenzwert}% -Es wurde angedeutet, dass der Gelfand-Radius mit dem Spektralradius -übereinstimmt, dem Betrag des betragsgrössten Eigenwertes. -Dies hat uns ein vergleichsweise einfach auszuwertendes Konvergenzkriterium -geliefert. +Wir wollen in diesem Abschnitt zeigen, dass der Gelfand-Radius mit +dem Spektralradius übereinstimmt. +Dies liefert uns ein vergleichsweise einfach auszuwertendes Konvergenzkriterium. \index{Konvergenzkriterium}% -In diesem Abschnitt soll diese Identität zunächst an Spezialfällen -und später ganz allgemein gezeigt werden. \subsubsection{Spezialfall: Diagonalisierbare Matrizen} Ist eine Matrix $A$ diagonalisierbar, dann kann Sie durch eine Wahl -einer geeigneten Basis in Diagonalform +einer geeigneten Basis in die Diagonalform \index{diagonalisierbar}% \index{Diagonalform}% \[ @@ -576,8 +753,8 @@ Ihre Potenzen haben ebenfalls Blockform: \[ A^k = \begin{pmatrix} B^k & 0 \\ 0 & C^k\end{pmatrix}. \] -Ein Vektor $v$ kann in die zwei Summanden $v_1$ bestehen aus den -ersten $n$ Komponenten und $v_2$ bestehen aus den letzten $m$ +Ein Vektor $v$ kann in die zwei Summanden $v_1$ bestehend aus den +ersten $n$ Komponenten und $v_2$ bestehend aus den letzten $m$ Komponenten zerlegen. Dann ist \[ @@ -613,11 +790,11 @@ Polynom der Blockmatrix $A$ natürlich \index{charakteristisches Polynom}% \index{Polynom!charakteristisch}% \[ -\chi_A(\lambda) = \chi_B(\lambda)\chi_C(\lambda), +\chi_A(\lambda) = \chi_B(\lambda)\chi_C(\lambda). \] -woraus folgt, dass die Eigenwerte von $A$ die Vereinigung der Eigenwerte +Es folgt, dass die Eigenwerte von $A$ die Vereinigung der Eigenwerte von $B$ und $C$ sind. -Daher gilt auch für die Spektralradius die Formel +Daher gilt auch für den Spektralradius die Formel \[ \varrho(A) = \max(\varrho(B) , \varrho(C)). \] @@ -625,7 +802,7 @@ Daher gilt auch für die Spektralradius die Formel \subsubsection{Jordan-Blöcke} \index{Jordan-Block}% Nicht jede Matrix ist diagonalisierbar, die bekanntesten Beispiele sind -die Matrizen +die Jordan-Blöcke \begin{equation} J_n(\lambda) = @@ -640,12 +817,12 @@ J_n(\lambda) \label{buch:spektralradius:eqn:jordan} \end{equation} wobei $\lambda\in\mathbb C$ eine beliebige komplexe Zahl ist. -Wir nennen diese Matrizen {\em Jordan-Matrizen}. Es ist klar, dass $J_n(\lambda)$ nur den $n$-fachen Eigenwert $\lambda$ hat und dass der erste Standardbasisvektor ein Eigenvektor zu diesem Eigenwert ist. -In der linearen Algebra lernt man, dass jede Matrix durch Wahl +In Abschnitt~\ref{buch:subsection:jordan-normalform} +haben wir gesehen, dass jede Matrix durch die Wahl \index{lineare!Algebra}% einer geeigneten Basis als Blockmatrix der Form \[ @@ -658,14 +835,13 @@ J_{n_1}(\lambda_1) & 0 & \dots & 0 \\ 0 & 0 & \dots &J_{n_l}(\lambda_l) \end{pmatrix} \] -geschrieben werden kann\footnote{Sofern die Matrix komplexe Eigenwerte -hat muss man auch komplexe Basisvektoren zulassen.}. +geschrieben werden kann. Die früheren Beobachtungen über den Spektralradius und den -Gelfand-Radius von Blockmatrizen zeigen uns daher, dass +Gelfand-Radius von Blockmatrizen führen uns dazu, dass nur gezeigt werden muss, dass nur die Gleichheit des Gelfand-Radius und des Spektral-Radius von Jordan-Blöcken gezeigt werden muss. -\subsubsection{Iterationsfolgen} +\subsubsection{Potenzen von Jordan-Blöcken} \begin{satz} \label{buch:spektralradius:satz:grenzwert} Sei $A$ eine $n\times n$-Matrix mit Spektralradius $\varrho(A)$. @@ -773,7 +949,7 @@ es im Fall $\varepsilon > 0$ eine Konstante $M$ gibt mit \|A(\varepsilon) ^k\|^\frac1k\le M^\frac1k\varrho(A(\varepsilon)) \\ &\Rightarrow\quad -\pi(A) \le \varrho(A(\varepsilon)) +\pi(A(\varepsilon)) \le \varrho(A(\varepsilon)) \underbrace{\lim_{k\to\infty} M^\frac1k}_{\displaystyle=1} = \varrho(A(\varepsilon)) @@ -790,7 +966,7 @@ Andererseits gibt es für $\varepsilon <0$ eine Konstante $m$ mit \|A(\varepsilon) ^k\|^\frac1k\ge m^\frac1k\varrho(A(\varepsilon)) \\ &\Rightarrow\quad -\pi(A) \ge \varrho(A(\varepsilon)) +\pi(A(\varepsilon)) \ge \varrho(A(\varepsilon)) \underbrace{\lim_{k\to\infty} m^\frac1k}_{\displaystyle=1} = \varrho(A(\varepsilon)) diff --git a/buch/chapters/40-eigenwerte/spektraltheorie.tex b/buch/chapters/40-eigenwerte/spektraltheorie.tex index 466b99e..94a64e1 100644 --- a/buch/chapters/40-eigenwerte/spektraltheorie.tex +++ b/buch/chapters/40-eigenwerte/spektraltheorie.tex @@ -6,11 +6,12 @@ \section{Spektraltheorie \label{buch:section:spektraltheorie}} Aufgabe der Spektraltheorie ist, Bedingungen an eine Matrix $A$ und eine +\index{Spektraltheorie} Funktion $f(z)$ zu finden, unter denen es möglich ist, $f(A)$ auf konsistente Art und Weise zu definieren. Weiter müssen Methoden entwickelt werden, mit denen $f(A)$ berechnet werden kann. -Für ein Polynom $p(z)$ ist $p(A)$ durch einsetzen definiert. +Für ein Polynom $p(z)$ ist $p(A)$ durch Einsetzen definiert. Für Funktionen, die sich nicht durch ein Polynom darstellen lassen, muss eine Approximation der Funktion durch Polynome verwendet werden. Sei also $p_n(z)$ eine Folge von Polynomen, die als Approximation der @@ -41,7 +42,10 @@ konvergente Folge von Polynomen $p_n(z)$ auch die Matrizenfolge $p_n(A)$ konvergiert. Es wird sich zeigen, dass die Menge $K$ das Spektrum von $A$ ist, +$K=\operatorname{Sp}(A)$, +(Definition~\ref{buch:eigenwerte:def:spektrum}), also eine endliche Teilmenge von $\mathbb{C}$. +\index{Spektrum} Jede Funktion kann auf so einer Menge durch Polynome exakt wiedergegeben werden. Es gibt insbesondere Folgen von Polynomen, die eingeschränkt @@ -70,9 +74,11 @@ lassen, woraus sich dann Approximationen von $f(A)$ für diagonalisierbare Matrizen mit reellen Eigenwerten ergeben. Der Satz von Stone-Weierstrass, der in +\index{Stone-Weierstrass, Satz von}% +\index{Satz von Stone-Weierstrass}% Abschnitt~\ref{buch:subsetion:stone-weierstrass} dargestellt wird, ist ein sehr allgemeines Approximationsresultat, welches nicht nur -zeigt, dass die Approximation unter sehr natürlichen Voraussetzungen +zeigt, dass die Approximation unter einigermassen natürlichen Voraussetzungen beliebig genau möglich ist, sondern uns im komplexen Fall auch weitere Einsicht dafür geben kann, welche Voraussetzungen an eine komplexe Matrix gestellt werden müssen, damit man damit rechnen kann, @@ -91,8 +97,10 @@ Approximationsverfahren entwickelt, wovon zwei kurz (ohne Beweise) vorgestellt werden sollen. \subsubsection{Das Legendre-Interpolationspolynom} +\index{Legendre-Interpolationspolynom}% Zu vorgegebenen, verschiedenen Zahlen $z_i\in\mathbb{C}$, $0\le i\le n$, die auch die {\em Stützstellen} genannt werden, +\index{Stützstelle}% gibt es immer ein Polynom vom Grade $n$, welches in den $z_i$ vorgegebene Werte $f(z_i)$ annimmt. Ein solches Polynom lässt sich im Prinzip mit Hilfe eines linearen @@ -100,9 +108,9 @@ Gleichungssystems finden, man kann aber auch direkt eine Lösung konstruieren. Dazu bildet man erst die Polynome \begin{align*} -l(z) &= (z-z_0)(z-z_1)\dots (z-z_n) \qquad\text{und} +l(z) &= (z-z_0)(z-z_1)\cdots (z-z_n) \qquad\text{und} \\ -l_i(z) &= (z-z_0)\dots \widehat{(z-z_i)}\dots (z-z_n). +l_i(z) &= (z-z_0)\cdots \widehat{(z-z_i)}\cdots (z-z_n). \end{align*} Darin bedeutet der Hut, dass dieser Term weggelassen werden soll. Für $z\ne z_i$ ist $l_i(z)=l(z)/(z-z_i)$. @@ -112,10 +120,10 @@ k_i(z) = \frac{l_i(z)}{l_i(z_i)} = -\frac{(z-z_0)\dots \widehat{(z-z_i)}\dots (z-z_n)}{(z_i-z_0)\dots \widehat{(z_i-z_i)}\dots (z_i-z_n)} +\frac{(z-z_0)\cdots \widehat{(z-z_i)}\cdots (z-z_n)}{(z_i-z_0)\cdots \widehat{(z_i-z_i)}\cdots (z_i-z_n)} \] haben die Eigenschaft -$k_i(z_j)=\delta_{ij}$. +$k_i(z_j)=\delta_{i\!j}$. Damit lässt sich jetzt ein Polynom \[ p(z) = \sum_{j=0}^n f(z_j) \frac{l_j(z)}{l_j(z_j)} @@ -126,7 +134,7 @@ p(z_i) = \sum_{j=0}^n f(z_j) \frac{l_j(z_i)}{l_j(z_j)} = -\sum_{j=0}^n f(z_j) \delta_{ij} +\sum_{j=0}^n f(z_j) \delta_{i\!j} = f_(z_i) \] @@ -139,17 +147,19 @@ annimmt, doch ist die Stabilität für grosse $n$ eher beschränkt. \subsubsection{Gleichmassige Approximation mit Bernstein-Polynomen} +\index{Bernstein-Polynom}% Das Legendre-Interpolationspolynom nimmt in den Stützstellen die verlangten Werte an, aber ausserhalb der Stützstellen ist nicht garantiert, dass man eine gute Approximation einer Funktion $f(z)$ erhält. - Für die Approximation auf einem reellen Interval $[a,b]$ hat -Sergei Natanowitsch Bernstein ein +Sergei Natanowitsch Bernstein eine Methode zur expliziten +Konstruktion eines Approximationspolynoms formuliert. + Dazu werden zuerst die reellen Bernsteinpolynome vom Grad $n$ durch \begin{align*} -B_{i,n}(t) = \binom{n}{i} t^i(1-t)^{n-i}. +B_{i,n}(t) = \binom{n}{i} t^i(1-t)^{n-i} \end{align*} definiert. Als Approximationspolynom für die auf dem Interval @@ -179,6 +189,8 @@ verwendet. % \subsection{Der Satz von Stone-Weierstrasss \label{buch:subsetion:stone-weierstrass}} +\index{Stone-Weierstrass, Satz von}% +\index{Satz von Stone-Weierstrass}% Der Satz von Stone-Weierstrass behandelt im Gegensatz zu den in Abschnitt~\ref{buch:subsection:approximation-durch-polynome} besprochenen Approximationsmethoden nicht nur Funktionen von @@ -207,8 +219,8 @@ erst ermöglichen werden. Aus den konstanten Funktionen lassen sich durch algebraische Operationen nur weitere konstante Funktionen erzeugen. Die konstanten Funktionen sind also nur dann eine genügend -reichhaltige Menge, wenn die Menge $K$ nur einen einzigen Punkt -enthält. +reichhaltige Menge für die Approximation von Funktionen auf $K$, +wenn die Menge $K$ nur einen einzigen Punkt enthält. Damit sich Funktionen approximieren lassen, die in zwei Punkten verschiedene Werte haben, muss es auch unter den zur Approximation zur Verfügung stehenden Funktionen solche haben, deren Werte sich @@ -263,6 +275,8 @@ nicht widerspricht aber ein Hindernis für spätere Anwendungen ist. \subsubsection{Der Satz von Stone-Weierstrass für reelle Funktionen} +\index{Satz von Stone-Weierstrass}% +\index{Stone-Weierstrass, Satz von}% Die Beispiele von Abschnitt~\ref{buch:subsection:approximation-durch-polynome} haben bezeigt, dass sich reellwertige Funktionen einer reellen Variable durch Polynome beliebig genau approximieren lassen. @@ -308,6 +322,7 @@ in $A$. Für den Beweis des Satzes wird ein Hilfsresultat benötigt, welches wir zunächst ableiten. Es besagt, dass sich die Wurzelfunktion $t\mapsto\sqrt{t}$ +\index{Wurzelfunktion}% auf dem Interval $[0,1]$ gleichmässig von unten durch Polynome approximieren lässt, die in Abbildung~\ref{buch:eigenwerte:fig:wurzelapproximation} dargestellt @@ -365,6 +380,8 @@ Folge, die gegen $\sqrt{a}$ konvergiert. \end{proof} \begin{proof}[Beweis des Satzes von Stone-Weierstrass] +\index{Stone-Weierstrass, Beweis}% +\index{Satz von Stone-Weierstrasse, Beweis}% Da $A$ eine Algebra ist, ist mit jeder Funktion $f\in A$ für jedes Polynome $p\in\mathbb{R}[X]$ auch $p(f)$ eine Funktion in $A$. \begin{enumerate} @@ -377,12 +394,12 @@ Sei ausserdem $m^2=\sup \{f(x)^2\;|\;x\in K\}$, so dass $f^2/m^2$ eine Funktion mit Werten im Intervall $[0,1]$ ist. Die Funktionen $f_n(x)=mu_n(f(x)^2/m^2)$ sind ebenfalls in $A$ und approximieren gleichmässig $\sqrt{f(x)^2}=|f(x)|$. + \item Schritt: Für zwei Funktionen $f,g\in A$ gibt es eine monoton wachsende Folge, die $\max(f,g)$ gleichmässig beliebig genau approximiert und eine monoton fallende Folge, die $\min(f,g)$ gleichmässig beliebig genau approximiert. - Diese Folgen können aus der Approximationsfolge für den Betrag einer Funktion und den Identitäten \begin{equation} @@ -394,6 +411,7 @@ Funktion und den Identitäten \end{equation} gefunden werden, die in Abbildung~\ref{buch:eigenwerte:fig:minmax} graphisch erklärt werden. + \item Schritt: Zu zwei beliebigen Punkten $x,y\in K$ und Werten $\alpha,\beta\in\mathbb{R}$ gibt es immer eine Funktion in $A$, die in den Punkten $x,y$ die vorgegebenen Werte $\alpha$ bzw.~$\beta$ @@ -405,12 +423,13 @@ f(t) = \beta + \frac{f_0(t)-f_0(y)}{f_0(x)-f_0(y)}(\alpha-\beta) \] -wohldefiniert und nimmt die verlangten Werte an. +wohldefiniert, liegt in $A$ und nimmt die verlangten Werte an. + \item Schritt: Zu jeder stetigen Funktion $f\colon K\to\mathbb{R}$, jedem Punkt $x\in K$ und jedem $\varepsilon>0$ gibt es eine Funktion $g\in A$ derart, dass $g(x)=f(x)$ und $g(y) \le f(y)+\varepsilon$ für alle $y\in K$. -Zu jedem $z\in K$ gibt es eine Funktion in $A$ mit +Zu jedem $z\in K$ gibt es eine Funktion $h_z\in A$ mit $h_z(x)=f(x)$ und $h_z(z) \le f(z)+\frac12\varepsilon$. Wegen der Stetigkeit von $h_z$ gibt es eine Umgebung $V_z$ von $z$, in der immer noch gilt $h_z(y)\le f(y)+\varepsilon$ für $y\in V_z$. @@ -428,8 +447,8 @@ Ausserdem ist $g(z)$ nach dem zweiten Schritt beliebig genau durch Funktionen in $A$ approximierbar. \item Schritt: Jede stetige Funktion $f\colon K\to\mathbb{R}$ kann beliebig genau durch Funktionen in $A$ approximiert werden. -Sei $\varepsilon > 0$. +Sei $\varepsilon > 0$. Nach dem vierten Schritt gibt es für jedes $y\in K$ eine Funktion $g_y$ derart, dass $g_y(y)=f(y)$ und $g_y(x) \le f(x) + \varepsilon$ für $x\in K$. @@ -501,13 +520,21 @@ f(\lambda_1)& & & \\ \end{pmatrix}. \] -\begin{satz} +Insgesamt haben wir damit den folgenden {\em Spektralsatz } für symmetrische +und hermitesche Matrizen erhalten. +\index{Spektralsatz}% + +\begin{satz}[Spektralsatz] \label{buch:eigenwerte:satz:spektralsatz} -Ist $A$ symmetrische oder selbstadjungiert Matrix und $f$ eine Funktion +\index{symmetrische Matrix}% +\index{Matrix, symmetrisch}% +\index{hermitesche Matrix}% +\index{Matrix, hermitesche}% +Ist $A$ symmetrische oder hermitesche Matrix und $f$ eine Funktion auf dem Spektrum $\operatorname{Sp}(A)$ von $A$. Dann gibt es genau eine Matrix $f(A)$, die Grenzwert jeder beliebigen -Folge $p_n(A)$ für Polynomfolgen, die $\operatorname{Sp}(A)$ gleichmässig -gegen $f$ konvergieren. +Folge $p_n(A)$ für Polynomfolgen, die auf $\operatorname{Sp}(A)$ +gleichmässig gegen $f$ konvergieren. \end{satz} \subsubsection{Unmöglichkeit der Approximation von $z\mapsto \overline{z}$ @@ -518,15 +545,10 @@ In diesem Abschnitt zeigen wir, dass sich die Funktion $z\mapsto\overline{z}$ auf der Einheitskreisscheibe $K=\{z\in\mathbb{C}\;|\; |z|\le 1\}$ nicht gleichmässig durch Polynome $p(z)$ mit komplexen Koeffizienten approximieren lässt. +Sei also $p_n(z)$ eine Folge von Polynomen, die auf der Einheitskreisscheibe +gleichmässig gegen $\overline{z}$ konvergieren, also +$\overline{z}=\lim_{n\to\infty}p_n(z)$. -Wäre eine solche Approximation möglich, dann könnte man $\overline{z}$ -auch durch eine Potenzreihe -\[ -\overline{z} -= -\sum_{k=0}^\infty a_kz^k -\] -darstellen. Das Wegintegral beider Seiten über den Pfad $\gamma(t) = e^{it}$ in der komplexen Ebene ist \begin{align*} @@ -541,12 +563,12 @@ i\biggl[ \frac{1}{i(k+1)} e^{it(k+1)}\biggr]_0^{2\pi} 0 \\ \oint_\gamma -\sum_{k=0}^\infty a_kz^k +p(z) \,dz &= -\sum_{k=0}^\infty a_k \oint_\gamma z^k\,dz +\sum_{k=0}^\infty a_{n,k} \oint_\gamma z^k\,dz = -\sum_{k=0}^\infty a_k\cdot 0 +\sum_{k=0}^\infty a_{n,k}\cdot 0 = 0 \\ @@ -558,12 +580,13 @@ i\int_0^{2\pi} \,dt = 2\pi i, \end{align*} dabei wurde $\overline{\gamma}(t)=e^{-it}$ verwendet. Insbesondere widersprechen sich die beiden Integrale. -Die ursprüngliche Annahmen, $\overline{z}$ lasse sich durch Polynome +Die ursprüngliche Annahme, $\overline{z}$ lasse sich durch Polynome gleichmässig approximieren, muss daher verworfen werden. \subsubsection{Der Satz von Stone-Weierstrass für komplexe Funktionen} Der Satz von Stone-Weierstrass kann nach dem vorangegangene Abschnitt -also nicht gelten. +also für komplexe Funktionen nicht gelten, wir haben eine Funktion +gefunden, die sich nicht approximieren lässt. Um den Beweis des Satzes~\ref{buch:satz:stone-weierstrass} auf komplexe Zahlen zu übertragen, muss im ersten Schritt ein Weg gefunden werden, den Betrag einer Funktion zu approximieren. @@ -585,6 +608,8 @@ nur dann bestimmen kann, wenn mit jeder Funktion aus $A$ auch die komplex konjugierte Funktion zur Verfügung steht. \begin{satz}[Stone-Weierstrass] +\index{Satz von Stone-Weierstrass für komplexe Funktionen} +\index{Stone-Weierstrass, Satz für komplexe Funktionen} Enthält eine $\mathbb{C}$-Algebra $A$ von stetigen, komplexwertigen Funktionen auf einer kompakten Menge $K$ die konstanten Funktionen, trennt sie Punkte und ist ausserdem mit jeder Funktion $f\in A$ auch @@ -603,7 +628,8 @@ Beweis des reellen Satzes von Stone-Weierstrass übertragen lässt. \subsection{Normale Matrizen \label{buch:subsection:normale-matrizen}} Aus dem Satz von Stone-Weierstrass für komplexe Matrizen kann man -jetzt einen Spektralsätze für eine etwas grössere Klasse von Matrizen +jetzt einen Spektralsatz für eine etwas grössere Klasse von Matrizen +\index{Spektralsatz}% ableiten, als im Satz~\ref{buch:eigenwerte:satz:spektralsatz} möglich war. Der Satz besagt, dass für eine beliebige Funktion $f$ auf dem Spektrum @@ -621,7 +647,7 @@ $\overline{z}$ eingesetzt werden. Dies erklärt aber noch nicht, wie für $n\times n$-Matrizen vorzugehen ist, wenn $n>1$ ist. -Die Notwendigkeit, die Variable $\overline{z}$ hinzuzunehmen +Die Notwendigkeit, die Variable $\overline{z}$ hinzuzunehmen, ergab sich aus der Anforderung, dass der Betrag aus $|z|^2=z\overline{z}$ konstruiert werden können muss. Insbesondere muss beim Einsetzen eine Matrix entstehen, die nur @@ -660,6 +686,7 @@ $AA^* = A^*A$ ist. \begin{definition} Eine Matrix $A\in M_n(\mathbb{C})$ heisst {\em normal}, wenn $AA^*=A^*A$ gilt. +\index{normal}% \end{definition} \subsubsection{Beispiele normaler Matrizen} @@ -667,12 +694,16 @@ Eine Matrix $A\in M_n(\mathbb{C})$ heisst {\em normal}, wenn $AA^*=A^*A$ gilt. \begin{enumerate} \item Hermitesche und Antihermitesche Matrizen sind normal, denn solche +\index{hermitesch}% +\index{anithermitesch}% Matrizen erfüllen $A^*=\pm A$ und damit \( AA^* = \pm A^2 = A^*A. \) \item Symmetrische und antisymmetrische Matrizen sind normal, +\index{symmetrisch}% +\index{antisymmetrisch}% denn aus $A=A^t$ folgt $A^*=\overline{A}^t$ und damit \begin{align*} AA^* &= A\overline{A}^t = @@ -681,8 +712,10 @@ A^*A &= \end{align*} \item Unitäre Matrizen $U$ sind normal, das $UU^*=I=U^*U$ gilt. +\index{unitär}% \item Orthogonale Matrizen sind normal wegen $O(n) = U(n) \cap M_n(\mathbb{R})$. +\index{orthogonal}% \end{enumerate} Jede Matrix lässt sich durch Wahl einer geeigneten Basis in Jordansche @@ -692,6 +725,7 @@ Satz zeigt. \begin{satz} Eine Dreiecksmatrix ist genau dann normal, wenn sie diagonal ist. +\index{Dreiecksmatrix}% \end{satz} \begin{proof}[Beweis] @@ -699,15 +733,15 @@ Sei $A$ eine obere Dreiecksmatrix, das Argument für eine untere Dreiecksmatrix funktioniert gleich. Wir berechnen ein Diagonalelement für beide Produkte $AA^*$ und $A^*A$. Dazu brauchen wir die Matrixelemente von $A$ und $A^*$. -Bezeichnen wir die Matrixelemente von $A$ mit $a_{ij}$, dann hat $A^*$ -die Matrixelemente $(A^*)_{ij}=\overline{a}_{ji}$. +Bezeichnen wir die Matrixelemente von $A$ mit $a_{i\!j}$, dann hat $A^*$ +die Matrixelemente $(A^*)_{i\!j}=\overline{a}_{ji}$. Damit kann man die Diagonalelemente der Produkte als \begin{align*} (AA^*)_{ii} &= -\sum_{j=1}^n a_{ij}\overline{a}_{ij} +\sum_{j=1}^n a_{i\!j}\overline{a}_{i\!j} = -\sum_{j=i}^n |a_{ij}|^2 +\sum_{j=i}^n |a_{i\!j}|^2 \\ (A^*A)_{ii} &= @@ -716,11 +750,12 @@ Damit kann man die Diagonalelemente der Produkte als \sum_{j=1}^i |a_{ji}|^2 \end{align*} ausrechnen. -Der obere Ausdruck ist die quadrierte Länge der Zeile $i$ der Matrix $A$, -der untere ist die quadrierte Länge der Spalte $i$. +Der obere Ausdruck ist die quadrierte Länge des Zeilenvektors $i$ der Matrix $A$, +der untere ist die quadrierte Länge des Spaltenvektors $i$. Da die Matrix eine obere Dreiecksmatrix ist, hat die erste Spalte höchstens ein einziges von $0$ verschiedenes Element. -Daher kann auch die erste Zeile höchstens dieses eine Elemente haben. +Da die erste Spalte die gleiche Länge hat, +kann auch die erste Zeile höchstens dieses eine Element haben. Die Matrix hat daher Blockstruktur mit einem $1\times 1$-Block in der linken obere Ecke und einem $n-1$-dimensionalen Block für den Rest. Durch Wiederholen des Arguments für den $(n-1)\times (n-1)$-Block @@ -764,6 +799,27 @@ B^*A^*AB was zeigt, dass auch $AB$ normal ist. \end{proof} +\subsubsection{Spektralsatz für normale Matrizen} +Mit dem Begriff der normalen Matrix lässt sich der Spektralsatz nun +abschliessen formulieren. +Die vorangegangene Diskussion hat gezeigt, dass man einen solchen +Satz für nicht normale Matrizen nicht erwarten kann. + +\begin{satz} +\label{buch:eigenwerte:satz:spektralnormal} +Ist $A$ eine normale Matrix und $f$ eine Funktion auf dem Spektrum +$\operatorname{Sp}(A)$ von $A$. +Dann gibt es genau eine Matrix $f(A)$, die der Grenzwert +\[ +f(A) += +\lim_{n\to\infty} p_n(A,A^*) +\] +jeder beliebigen +Folge $p_n(z,\overline{z})$ von Polynomen in $z$ und $\overline{z}$ ist, +die auf $\operatorname{Sp}(A)$ gleichmässig gegen $f$ konvergieren. +\end{satz} + \subsubsection{Äquivalente Bedingungen} Es gibt eine grosse Zahl äquivalenter Eigenschaften für normale Matrizen. Die folgenden Eigenschaften sind äquivalent: @@ -775,24 +831,30 @@ Es gibt eine orthonormale Basis von Eigenvektoren von $A$ für $\mathbb{C}^n$ \item Für jeden Vektor $x\in\mathbb{C}^n$ gilt $\|Ax\|=\|A^*x\|$ \item -Die Forbenius-Norm der Matrix $A$ kann mit den Eigenwerten $\lambda_i$ +Die Frobenius-Norm der Matrix $A$ kann mit den Eigenwerten $\lambda_i$ +\index{Frobenius-Norm}% von $A$ berechnet werden: $\operatorname{Spur}(A^*A) = \sum_{i=1}^n |\lambda_i|^2$ \item Der hermitesche Teil $\frac12(A+A^*)$ und der antihermitesche Teil $\frac12(A-A^*)$ von $A$ vertauschen. +\index{hermitesch}% +\index{antihermitesch}% \item $A^*$ ist ein Polynom vom Grad $n-1$ in $A$. \item Es gibt eine unitäre Matrix $U$ derart, dass $A^*=AU$ +\index{unitär}% \item -Es gibt eine Polarzerlegugn $A=UP$ mit einer unitären Matrix $U$ und +Es gibt eine Polarzerlegung $A=UP$ mit einer unitären Matrix $U$ und +\index{Polarzerlegung} einer postiv semidefiniten Matrix $P$, die untereinander vertauschen. \item Es gibt eine Matrix $N$ mit verschiedenen Eigenwerten, mit denen $A$ vertauscht. \item -Wenn $A$ die (absteigend geordneten) singulärwerte $\sigma_i$ und +Wenn $A$ die (absteigend geordneten) Singulärwerte $\sigma_i$ und +\index{Singulärwert}% die absteigend geordneten Eigenwerte $\lambda_i$ hat, dann it $\sigma_i=|\lambda_i|$. \end{enumerate} diff --git a/buch/chapters/50-permutationen/chapter.tex b/buch/chapters/50-permutationen/chapter.tex index cf3f2ab..e3b6742 100644 --- a/buch/chapters/50-permutationen/chapter.tex +++ b/buch/chapters/50-permutationen/chapter.tex @@ -8,13 +8,17 @@ \lhead{Permutationen} \rhead{} Die Berechnung der Determinante einer Matrix macht ausgedehnten +\index{Determinante}% Gebrauch von der Tatsache, dass die Vertauschung von zwei Zeilen oder Spalten das Vorzeichen des Wertes der Determinanten dreht. In diesem Kapitel sollen die Permutationen der Zeilen abstrakt +\index{Permutation}% untersucht werden. Wir erhalten so eine abstrakte Permutationsgruppe. +\index{Permutationsgruppe}% Ihre Elemente lassen sich auch durch spezielle Matrizen beschreiben, eine Darstellung dieser Gruppe, die auch unmittelbar zu einer +\index{Darstellung}% Formel für die Determinante einer Matrix führt. \input{chapters/50-permutationen/endlich.tex} diff --git a/buch/chapters/50-permutationen/determinante.tex b/buch/chapters/50-permutationen/determinante.tex index 805235d..b30f9a2 100644 --- a/buch/chapters/50-permutationen/determinante.tex +++ b/buch/chapters/50-permutationen/determinante.tex @@ -17,12 +17,16 @@ Entwicklungssatz \begin{equation} \det(A) = -\sum_{i=1}^n (-1)^{i+j} a_{ij} \cdot \det(A_{ij}) +\sum_{i=1}^n (-1)^{i+j} a_{i\!j} \cdot \det(A_{i\!j}) \label{buch:permutationen:entwicklungssatz} \end{equation} von Laplace für die Determinante. -In den Produkten $a_{ij}\cdot\det(A_{ij})$ enthält -die Untermatrix $A_{ij}$ weder Elemente der Zeile $i$ noch der +\index{Entwicklungssatz}% +\index{Laplace, Entwicklungssatz von}% +Die Matrizen $A_{i\!j}$ sind die Minoren der Matrix $A$ +(siehe auch Seite~\pageref{buch:linear:def:minor}). +In den Produkten $a_{i\!j}\cdot\det(A_{i\!j})$ enthält +die Untermatrix $A_{i\!j}$ weder Elemente der Zeile $i$ noch der Zeile $j$. Die Summanden auf der rechten Seite von \eqref{buch:permutationen:entwicklungssatz} @@ -31,7 +35,7 @@ sind daher Produkte der Form a_{1i_1} a_{2i_2} a_{3i_3} -\dots +\cdots a_{ni_n}, \] in denen nur Faktoren aus verschiedenen Spalten der Matrix $A$ @@ -55,9 +59,10 @@ in der Form = \sum_{\sigma\in S_n} c(\sigma) +\, a_{1\sigma(1)} a_{2\sigma(2)} -\dots +\cdots a_{n\sigma(n)} \label{buch:permutationen:cformel} \end{equation} @@ -73,13 +78,15 @@ also = \sum_{\sigma \in S_n} c(\sigma) +\, (P_\tau)_{1\sigma(1)} (P_\tau)_{2\sigma(2)} -\dots +\cdots (P_\tau)_{n\sigma(n)} = c(\tau) -1\cdot 1\cdot\dots\cdot 1 +\, +1\cdot 1\cdots 1 = c(\tau). \] @@ -96,14 +103,14 @@ Die Determinante einer $n\times n$-Matrix $A$ kann berechnet werden als \operatorname{sgn}(\sigma) a_{1\sigma(1)} a_{2\sigma(2)} -\dots +\cdots a_{n\sigma(n)} = \sum_{\tau\in S_n} \operatorname{sgn}(\tau) a_{\tau(1)1} a_{\tau(2)2} -\dots +\cdots a_{\tau(n)n}. \] Insbesondere folgt auch $\det(A)=\det(A^t)$. diff --git a/buch/chapters/50-permutationen/endlich.tex b/buch/chapters/50-permutationen/endlich.tex index 700c0f2..2577b48 100644 --- a/buch/chapters/50-permutationen/endlich.tex +++ b/buch/chapters/50-permutationen/endlich.tex @@ -8,15 +8,24 @@ \rhead{Permutationen} Eine endliche Anzahl $n$ von Objekten können auf $n!$ Arten angeordnet werden. -Als Objektmenge nehmen wir $[n] = \{ 1,\dots,n\}$. +Da es in dieser Diskussion nicht auf die Art der Objekte ankommt, +nehmen wir als Objektmenge die Zahlen $[n] = \{ 1,\dots,n\}$ +(siehe auch Definition~\ref{buch:zahlen:def:[n]}). Die Operation, die die Objekte in eine bestimmte Reihenfolge bringt, ist eine Abbildung $\sigma\colon[n]\to[n]$. -Eine Permutation ist eine umkehrbare Abbildung $[n]\to[n]$. + +\begin{definition} +\label{buch:permutationen:def:permutation} +Eine {\em Permutation} ist eine umkehrbare Abbildung $[n]\to[n]$. +\index{Permutation} Die Menge $S_n$ aller umkehrbaren Abbildungen $[n]\to[n]$ mit der Verknüpfung von Abbildungen als Operation heisst die die {\em symmetrische Gruppe}. +\index{symmetrische Gruppe}% Die identische Abbildung $\sigma(x)=x$ ist das {\em neutrale Element} der Gruppe $S_n$ und wir auch mit $e$ bezeichnet. +\index{neutrales Element}% +\end{definition} \subsection{Permutationen als $2\times n$-Matrizen} Eine Permutation kann als $2\times n$-Matrix geschrieben werden: @@ -67,24 +76,28 @@ dass die Zahlen in der ersten Zeile ansteigend sind: \subsection{Zyklenzerlegung \label{buch:subsection:zyklenzerlegung}} Eine Permutation $\sigma\in S_n$ kann auch mit sogenanten Zyklenzerlegung +\index{Zyklenzerlegung}% analysiert werden. -Zum Beispiel: -\begin{center} -\includegraphics{chapters/50-permutationen/images/zyklenzerlegung.pdf} -\end{center} \begin{definition} Ein Zyklus $Z$ ist eine unter $\sigma$ invariante Teilmenge von $[n]$ minimaler Grösse. +\index{Zyklus}% +\index{invariante Teilmenge}% +\index{minimale Grösse}% Die Zyklenzerlegung ist eine Zerlegung von $[n]$ in Zyklen \[ [n] = -\cup_{i=1}^k Z_i, +\bigcup_{i=1}^k Z_i, \] wobei jede Menge $Z_i$ ein Zyklus ist. \end{definition} +Zum Beispiel: +\begin{center} +\includegraphics{chapters/50-permutationen/images/zyklenzerlegung.pdf} +\end{center} Der folgende Algorithmus findet die Zyklenzerlegung einer Permutation. \begin{satz} @@ -116,18 +129,21 @@ weiter bei 2. Mit Hilfe der Zyklenzerlegung von $\sigma$ lassen sich auch gewisse Eigenschaften von $\sigma$ ableiten. -Sei also $[n] = Z_1\cup\dots\cup Z_k$ die Zyklenzerlegung. -Für jedes Element $x\in S_i$ gilt $\sigma^{|S_i|}(x) = x$. +Sei also $[n] = Z_1\cup\dots\cup Z_k$ die Zyklenzerlegung von $\sigma$. +Für jedes Element $x\in Z_i$ gilt $\sigma^{|Z_i|}(x) = x$. Die kleinste Zahl $m$, für die $\sigma^m=e$ ist, das kleinste gemeinsame Vielfache der Zyklenlängen: \[ m = \operatorname{kgV} (|Z_1|,|Z_2|,\dots,|Z_k|). \] +\index{kgV} +\index{kleinstes gemeinsames Vielfaches} \subsection{Konjugierte Elemente in $S_n$} -Zwei Elemente $g_1,g_2\in G$ einer Gruppe heissen konjugiert, wenn +Zwei Elemente $g_1,g_2\in G$ einer Gruppe heissen {\em konjugiert}, wenn +\index{konjugiert} es ein Element $c\in G$ gibt derart, dass $cg_1c^{-1}=g_2$. -Bei Matrizen hat dies bedeutet, dass die beiden Matrizen durch +Bei Matrizen bedeutet dies bedeutet, dass die beiden Matrizen durch Basiswechsel auseinander hervorgehen. Dasselbe lässt sich auch im Kontext der symmetrischen Gruppe sagen. @@ -136,7 +152,18 @@ Es gibt also eine Permutation $\gamma\in S_n$ derart, dass $\sigma_1=\gamma\sigma_2\gamma^{-1}$ oder $\gamma^{-1}\sigma_1\gamma=\sigma_2$. Dann gilt auch für die Potenzen \begin{equation} -\sigma_1^k = \gamma\sigma_2^k\gamma^{-1}. +\sigma_1^k += +(\gamma\sigma_2\gamma^{-1})^k += +\gamma\sigma_2\underbrace{\gamma^{-1} +\gamma}_{\displaystyle=e}\sigma_2\underbrace{\gamma^{-1} +\gamma}_{\displaystyle=e}\sigma_2\underbrace{\gamma^{-1}\gamma}_{\displaystyle=e} +\cdots +\underbrace{\gamma^{-1} +\gamma}_{\displaystyle=e}\sigma_2\gamma^{-1} += +\gamma\sigma_2^k\gamma^{-1}. \label{buch:permutationen:eqn:konjpot} \end{equation} Ist $Z_i$ ein Zyklus von $\sigma_2$ und $x\in Z_i$, dann ist @@ -156,18 +183,21 @@ von $\sigma_1$ ab. Es folgt daher der folgende Satz: \begin{satz} -Sind $\sigma_1,\sigma_2\in S_n$ konjugiert $\sigma_1=\gamma\sigma_2\gamma^{-1}$ +Seien $\sigma_1,\sigma_2\in S_n$ konjugiert $\sigma_1=\gamma\sigma_2\gamma^{-1}$ mit dem $\gamma\in S_n$. Wenn $Z_1,\dots,Z_k$ die Zyklen von $\sigma_2$ sind, dann sind $\gamma(Z_1),\dots,\gamma(Z_k)$ die Zyklen von $\sigma_1$. \end{satz} -Die Zyklenzerlegung kann mit der Jordan-Normalform \ref{XXX} +Die Zyklenzerlegung kann mit der Jordan-Normalform +\index{Jordan-Normalform}% +(Abschnitt~\ref{buch:subsection:jordan-normalform}) einer Matrix verglichen werden. Durch einen Basiswechsel, welcher durch eine ``Konjugation'' +\index{Basiswechsel}% von Matrizen ausgedrückt wir, kann die Matrix in eine besonders übersichtliche Form gebracht werden. -Wenn $\sigma$ die Zyklenzerlegung $Z_1,\dots,Z_k$ mit Zyklenlängen +Wenn $\sigma$ die Zyklenzerlegung $Z_1,\dots,Z_k$ hat mit Zyklenlängen $l_i=|Z_i|$, dann kann man die Menge $[n]$ wie folgt in Teilmengen \begin{align*} X_1 &= \{1,\dots, l_1\}, diff --git a/buch/chapters/50-permutationen/images/komposition.pdf b/buch/chapters/50-permutationen/images/komposition.pdf Binary files differindex 9e532bf..3922096 100644 --- a/buch/chapters/50-permutationen/images/komposition.pdf +++ b/buch/chapters/50-permutationen/images/komposition.pdf diff --git a/buch/chapters/50-permutationen/images/komposition.tex b/buch/chapters/50-permutationen/images/komposition.tex index ef3ec65..2b73227 100644 --- a/buch/chapters/50-permutationen/images/komposition.tex +++ b/buch/chapters/50-permutationen/images/komposition.tex @@ -10,39 +10,71 @@ \usepackage{pgfplots} \usepackage{csvsimple} \usetikzlibrary{arrows,intersections,math} +\usetikzlibrary{decorations.pathreplacing} \begin{document} \def\skala{1} \begin{tikzpicture}[>=latex,thick,scale=\skala] -\begin{scope}[xshift=-4.5cm] +\begin{scope}[xshift=-4.0cm] + +\def\s{0.527} +\def\o{0.133} + +\def\verbindung#1{ +\fill[color=red!20] ({\o+(#1*\s)},-1.0) rectangle ({\o+(#1*\s)+0.3},0.0); +} + +\verbindung{1} +\verbindung{2} +\verbindung{3} +\verbindung{4} +\verbindung{5} +\verbindung{6} + + \node at (0,0) {$\displaystyle \sigma_1=\begin{pmatrix} 1&2&3&4&5&6\\ 2&1&3&5&6&4 +\end{pmatrix} +%$}; +=\begin{pmatrix} +1&2&3&4&5&6\\ +2&1&3&5&6&4 \end{pmatrix}$}; \node at (0,-1) {$\displaystyle \sigma_2=\begin{pmatrix} 1&2&3&4&5&6\\ 3&4&5&6&1&2 \end{pmatrix} -$}; -\end{scope} -\begin{scope} -\node at (0,0) {$\displaystyle -\begin{pmatrix} -1&2&3&4&5&6\\ -2&1&3&5&6&4 -\end{pmatrix}$}; -\node at (0,-1) {$\displaystyle += \begin{pmatrix} 2&1&3&5&6&4\\ 4&3&5&1&2&6 \end{pmatrix} $}; - \end{scope} -\begin{scope}[xshift=4.5cm] + +%\begin{scope} +%\node at (0,0) {$\displaystyle +%\begin{pmatrix} +%1&2&3&4&5&6\\ +%2&1&3&5&6&4 +%\end{pmatrix}$}; +%\node at (0,-1) {$\displaystyle +%\begin{pmatrix} +%2&1&3&5&6&4\\ +%4&3&5&1&2&6 +%\end{pmatrix} +%$}; +%\end{scope} + +\draw[decorate,decoration={brace,amplitude=4pt}] +(0,0.4) -- (0,-1.4); + +\begin{scope}[xshift=3.1cm] \node at (0,-0.5) {$\displaystyle +\Rightarrow\quad \sigma_2\sigma_1=\begin{pmatrix} 1&2&3&4&5&6\\ 4&3&5&1&2&6 diff --git a/buch/chapters/50-permutationen/matrizen.tex b/buch/chapters/50-permutationen/matrizen.tex index f7e9e31..037c441 100644 --- a/buch/chapters/50-permutationen/matrizen.tex +++ b/buch/chapters/50-permutationen/matrizen.tex @@ -7,11 +7,12 @@ \label{buch:section:permutationsmatrizen}} \rhead{Permutationsmatrizen} Die Eigenschaft, dass eine Vertauschung das Vorzeichen kehrt, ist -eine wohlebekannte Eigenschaft der Determinanten. +eine wohlbekannte Eigenschaft der Determinanten. In diesem Abschnitt soll daher eine Darstellung von Permutationen als Matrizen gezeigt werden und die Verbindung zwischen dem Vorzeichen einer Permutation und der Determinanten hergestellt werden. +\index{Determinante}% \subsection{Matrizen} Gegeben sei jetzt eine Permutation $\sigma\in S_n$. @@ -33,7 +34,7 @@ e_n&\mapsto e_{\sigma(n)} Die Matrix $P_\sigma$ der linearen Abbildung $f_{\sigma}$ hat in Spalte $i$ genau eine $1$ in der Zeile $\sigma(i)$, also \[ -(P_\sigma)_{ij} = \delta_{j\sigma(i)}. +(P_\sigma)_{i\!j} = \delta_{j\sigma(i)}. \] \begin{beispiel} @@ -61,27 +62,35 @@ A_\sigma \end{beispiel} \begin{definition} -Eine Permutationsmatrix ist eine Matrix $P\in M_n(\Bbbk)$ +\label{buch:permutationen:def:permutationsmatrix} +\index{Permutationsmatrix}% +Eine {\em Permutationsmatrix} ist eine Matrix $P\in M_n(\Bbbk)$ derart, die in jeder Zeile und Spalte genau eine $1$ enthalten ist, während alle anderen Matrixelemente $0$ sind. \end{definition} Es ist klar, dass aus einer Permutationsmatrix auch die Permutation der Standardbasisvektoren abgelesen werden kann. +\index{Standardbasisvektor}% Die Verknüpfung von Permutationen wird zur Matrixmultiplikation +\index{Matrixmultiplikation}% von Permutationsmatrizen, die Zuordnung $\sigma\mapsto P_\sigma$ ist also ein Homomorphismus -$ -S_n \to M_n(\Bbbk^n), -$ -es ist $P_{\sigma_1\sigma_2}=P_{\sigma_1}P_{\sigma_2}$. +\index{Homomorphismus}% +$S_n \to M_n(\Bbbk^n)$, +es ist +$P_{\sigma_1\sigma_2}=P_{\sigma_1}P_{\sigma_2}$. +$\sigma$ heisst gemäss Definition~\ref{buch:vektorenmatrizen:def:darstellung} +auch Darstellung der Gruppe $S_n$. +\index{Darstellung}% \subsection{Transpositionen} Transpositionen sind Permutationen, die genau zwei Elemente von $[n]$ vertauschen. -Wir ermitteln jetzt die Permutationsmatrix der Transposition $\tau=\tau_{ij}$ +Wir ermitteln jetzt die Permutationsmatrix der Transposition $\tau=\tau_{i\!j}$. +Sie ist \[ -P_{\tau_{ij}} +P_{\tau_{i\!j}} = \begin{pmatrix} 1& & & & & & & & \\ @@ -93,8 +102,7 @@ P_{\tau_{ij}} & & & & & &1& & \\ & & & & & & &\ddots& \\ & & & & & & & &1 -\end{pmatrix} -\qedhere +\end{pmatrix}. \] Die Permutation $\sigma$ mit dem Zyklus $1\to 2\to\dots\to l-1\to l\to 1$ @@ -148,7 +156,7 @@ P_{\tau_{l-1,l}} 0&0&1&0&\dots\\ \vdots&\vdots&\vdots&\vdots&\ddots \end{pmatrix} -\dots +\cdots \\ &= \begin{pmatrix} @@ -159,7 +167,7 @@ P_{\tau_{l-1,l}} \vdots&\vdots&\vdots&\vdots&\ddots \end{pmatrix} \\ -&\vdots\\ +&\quad\vdots\\ &= \begin{pmatrix} 0&0&0&0&\dots&0&1\\ @@ -168,15 +176,17 @@ P_{\tau_{l-1,l}} 0&0&1&0&\dots&0&0\\ \vdots&\vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\ 0&0&0&0&\dots&1&0 -\end{pmatrix} +\end{pmatrix}. \end{align*} \subsection{Determinante und Vorzeichen} Die Transpositionen haben Permutationsmatrizen, die aus der Einheitsmatrix +\index{Einheitsmatrix}% +\index{Determinante}% entstehen, indem genau zwei Zeilen vertauscht werden. Die Determinante einer solchen Permutationsmatrix ist \[ -\det P_{\tau} = - \det E = -1 = \operatorname{sgn}(\tau). +\det P_{\tau} = - \det I = -1 = \operatorname{sgn}(\tau). \] Nach der Produktregel für die Determinante folgt für eine Darstellung der Permutation $\sigma=\tau_1\dots\tau_l$ als Produkt von Transpositionen, @@ -184,7 +194,7 @@ dass \begin{equation} \det P_{\sigma} = -\det P_{\tau_1} \dots \det P_{\tau_l} +\det P_{\tau_1} \cdots \det P_{\tau_l} = (-1)^l = diff --git a/buch/chapters/50-permutationen/transpositionen.tex b/buch/chapters/50-permutationen/transpositionen.tex index 748b2e9..b8f3d41 100644 --- a/buch/chapters/50-permutationen/transpositionen.tex +++ b/buch/chapters/50-permutationen/transpositionen.tex @@ -12,11 +12,12 @@ Es zeigt sich aber, dass sich eine Permutation in noch elementarere Bausteine zerlegen lässt, die Transpositionen. \begin{definition} -Einen Transposition $\tau\in S_n$ ist ein Permutation, die genau +Eine {\em Transposition} $\tau\in S_n$ ist ein Permutation, die genau zwei Elemente vertauscht. -Die Transposition $\tau_{ij}$ ist definiert durch +\index{Transposition}% +Die Transposition $\tau_{i\!j}$ ist definiert durch \[ -\tau_{ij}(x) +\tau_{i\!j}(x) = \begin{cases} i&\qquad x=j\\ @@ -41,7 +42,7 @@ Es ist also \[ \sigma = -\tau_{12} \tau_{23} \tau_{34} \dots \tau_{k-3,k-2} \tau_{k-2,k-1} \tau_{k-1,k}. +\tau_{12} \tau_{23} \tau_{34} \cdots \tau_{k-3,k-2} \tau_{k-2,k-1} \tau_{k-1,k}. \] \begin{satz} Jede Permutation $\sigma\in S_n$ lässt sich als ein Produkt von @@ -66,6 +67,8 @@ die Anzahl gerade ist oder nicht, ist sehr wohl eine charkterisierende Eigenschaft einer Permutation. \begin{definition} +\index{Vorzeichen}% +\index{Signum}% Das {\em Vorzeichen} oder {\em Signum} einer Permutation $\sigma$ ist die Zahl $\operatorname{sgn}(\sigma)=(-1)^k$, wenn $\sigma$ als Produkt von $k$ Transpositionen geschrieben werden kann. @@ -77,16 +80,18 @@ dann ist $\sigma^{-1}=\tau_k\dots\tau_2\tau_1$, sowohl $\sigma$ wie $\sigma^{-1}$ können also mit der gleichen Zahl von Transpositionen geschrieben werden, sie haben also auch das gleiche Vorzeichen. -Die Abbildung $S_n\to\{\pm\}$, die einer Permutation das Signum zuordnet, -ist ein Homomorphismus von Gruppen, +Die Abbildung $S_n\to\{\pm1\}$, die einer Permutation das Signum zuordnet, +ist ein Homomorphismus von Gruppen +(siehe Definition~\ref{buch:gruppen:def:homomorphismus}), +\index{Homomorphismus}% d.~h. \[ \operatorname{sgn}(\sigma_1\sigma_2) = \operatorname{sgn}(\sigma_1) -\operatorname{sgn}(\sigma_2) +\operatorname{sgn}(\sigma_2). \] -da ganz offensichtlich $\sigma_1\sigma_2$ mit $k_1+k_2$ Transpositionen +Da ganz offensichtlich $\sigma_1\sigma_2$ mit $k_1+k_2$ Transpositionen geschrieben kann, wenn $\sigma_i$ mit $k_i$ Transpositionen geschrieben werden kann. @@ -101,16 +106,24 @@ A_n \{ \sigma\in S_n\;|\; \operatorname{sgn}(\sigma)=1 \} -\subset S_n. += +\ker \operatorname{sgn} +\subset +S_n. \] +\index{Kern}% +\index{alterniernde Gruppe}% heisst die {\em alternierende Gruppe} der Ordnung $n$ Die Elemente von $A_n$ heissen auch die {\em geraden} Permutationen, +\index{gerade Permutation}% +\index{ungerade Permutation}% die Elemente von $S_n\setminus A_n$ heissen auch die {\em ungeraden} Permutationen. \end{definition} Die alternierende Gruppe $A_n$ ist tatsächlich eine Untergruppe. +\index{Untergruppe}% Zunächst ist $\operatorname{sgn}(e)=(-1)^0=1$, also ist $e\in A_n$. Es wurde schon gezeigt, dass mit jedem Element $\sigma\in A_n$ auch das inverse Element $\sigma^{-1}\in A_n$ ist. |