Kurs:Lineare Algebra I/Affine Räume

Punkte und Vektoren

Im Kapitel 1 haben wir den Standardraum ${ℝ}^n$ eingeführt und seine Elemente einmal als Punkte und andererseits als Vektoren interpretiert. Die naive Vektorvorstellung (als gerichtete Strecke) war hilfreich zur Veranschaulichung der Operationen Vektoraddition und skalare Multiplikation, die für Punkte keinen Sinn machen. Ferner gibt es im Vektorraum stets ein ausgezeichnetes Element - den Nullvektor. Dagegen sind im Punktraum alle Elemente gleichberechtigt. Durch den Begriff des affinen Punktraumes werden wir mathematisch korrekt zwischen Punkten und Vektoren unterscheiden. Nehmen wir den naiven Punktraum als gegeben, dann wollen wir jetzt Vektoren als Parallelverschiebungen (Translationen) des Punktraumes interpretieren, die sich durch einen (ungebundenen) Pfeil charakterisieren lassen. Translationen können verknüpft werden (Hintereinanderausführung der Abbildungen) und durch einen skalaren Faktor gedehnt (resp. gestaucht) werden. Diese beiden Operationen induzieren die Struktur eines Vektorraumes auf der Menge aller Translationen des Punktraumes. Dieses Modell führt zum Begriff des affinen Raumes, die zugehörige mathematische Theorie ist die analytische Geometrie. Lineare Algebra und analytische Geometrie sind zwei verschiedene Betrachtungsweisen zum gleichen mathematischen Gebiet.

Definition 4.1

Ein affiner Raum ist ein Tripel ($𝐀,T_{𝐀},+$) aus einer nichtleeren Punktmenge $𝐀$, einem Vektorraum (von Translationen) $T_{𝐀}$ und einer Abbildung (Operation von $T_{𝐀}$ auf $𝐀$) der Form $Punkt+Vektor=Punkt$:

$+:𝐀\times T_{𝐀}\to 𝐀,(P,x)\mapsto P+x$,

die folgenden Regeln genügt:

($a_1$) $P+0=P$,

($a_2$) $(P+x)+y=P+(x+y)$,

($a_3$) Je zwei Punkte P,Q bestimmen eindeutig einen Vektor $x$ mit $P+x=Q$.

Schreibweisen: $x=\overrightarrow{PQ}=vec(P,Q)$. Jedem Vektor $x\in T_{𝐀}$ entspricht die Translation $t_x:𝐀\to 𝐀,P\mapsto P+x$. Die Dimension eines affinen Raumes ist die Dimension des zugehörigen Vektorraumes, $dim𝐀:=dim{T}_{𝐀}$. Meist spricht man allein von der Punktmenge $𝐀$ als affinen Raum ohne den zugehörigen Vektorraum explizit anzugeben. Die Punktmenge ist bijektiv zum Vektorraum der Translationen nach Fixierung eines Punktes $P_0$, indem jedem Punkt $Q$ der ’Ortvektor’ von $Q$ bzgl. $P_0$ zugeordnet wird: $𝐀\to T_{𝐀},Q\mapsto vec(P_0,Q)$. Die dazu inverse Abbildung lautet: $x\mapsto P_0+x$.

Definition 4.2

Eine Teilmenge eines affines Raumes $H\subset 𝐀$ der Form $H=P+T_H,P\in H$ und $T_H\subset T_{𝐀}$ ein Vektorunterraum, heißt affiner Unterraum.

Ein affiner Unterraum ist selbst affiner Raum. Für jeden Punkt $P\in H$ gilt $P_0+T_H=H=P+T_H$. Beispiele:

1. Der affine n-dimensionale Standardraum: ${𝐀}^n=(K^n,K^n,+)$. Zur Unterscheidung zwischen Punkten und Vektoren wird eine ($n+1$)-te Komponente vorangestellt, die 1 für Punkte und 0 für Vektoren gesetzt wird.

2. Die Lösungsmenge eines inhomogenen linearen Gleichungssystems $\mathscr{H}:=\mathscr{H}(A,b)$ ist ein affiner Raum. Die Translationen sind die Lösungen des zugehörigen homogenen Gleichungssystems $\mathscr{H}(A,0)$. $\mathscr{H}$ ist affiner Unterraum des affinen Standardraumes ${𝐀}^n$. Umgekehrt ist jeder affine Unterraum des Standardraumes Lösungsmenge eines linearen Gleichungssystems.

3. Je zwei verschiedene Punkte $P,Q\in 𝐀$ liegen in einem eindeutig bestimmten affinen Unterraum:

$L(P,Q):=\{X\in 𝐀|X=P+t\cdot vec(P,Q),t\in K\}$, der Geraden durch $P$ und $Q$.

Satz 4.3

Eine Teilmenge $H\subset 𝐀$ von Punkten eines affinen Raumes ist affiner Unterraum gdw. mit je zwei Punkten die Gerade durch diese Punkte in $H$ liegt: $P,Q\in H\Rightarrow L(P,Q)\subset H$.

Folgende Einschränkung ist zu beachten: Im Beweis wird benutzt: $1+1\ne 0$ in $K$. Dies ist nicht in jedem Körper erfüllt. Man denke an $K={𝔽}_2$. Deshalb ist diese Bedingung notwendige Voraussetzung des Satzes!

Lage affiner Unterräume

Der Durchschnitt zweier affiner Unterräume ist offensichtlich wieder ein affiner Unterraum, falls es einen gemeinsamen Punkt gibt: Sei $P_0\in H_1\cap H_2$, dann gilt $H_1\cap H_2=P_0+(T_{H_1}\cap T_{H_2})$. Im Gegensatz zu Vektorunterräumen kann der Durchschnitt affiner Unterräume leer sein:

Definition 4.4

Seien $H_1,H_2\subset 𝐀$ zwei affine Unterräume mit leerem Durchschnitt. $H_1$ und $H_2$ heißen zueinander parallel, falls die zugehörigen Translationsräume ineinander enthalten sind, d.h. $T_{H_1}\subset T_{H_2}$ oder umgekehrt. Andernfalls heißen die Unterräume windschief.

Jeder Punktmenge ordnen wir den kleinsten affinen Unterraum zu, der diese enthält:

Definition 4.5

Sei $M\subset 𝐀$ eine Menge von Punkten, dann heißt der kleinste affine Unterraum, der $M$ enthält, die affine Hülle $\mathscr{H}(M)$.

Lemma 4.6

$\mathscr{H}(P_0,...,P_k)=P_0+Lin\{vec(P_0,P_1),...,vec(P_0,P_k)\}$.

Bezeichne $H_1\vee H_2:=\mathscr{H}(H_1\cup H_2)$ als Verbindung der affinen Unterräume $H_1$ und $H_2$. Man vergleiche die ’affine Hülle’ mit der ’linearen Hülle’. Welche Konstruktion im Vektorraum entspricht der ’Verbindung’? Ist $P_0\in H_1\cap H_2$, dann ist $H_1\vee H_2=P_0+(T_{H_1}+T_{H_2})$. Dies gilt jedoch nur, wenn der Durchschnitt der Unteräume nicht leer ist. Allgemein haben wir die folgende Aussage:

Lemma 4.7

Seien $H_1$ und $H_2$ affine Unterräume, seien $P_1\in H_1$ und $P_2\in H_2$ zwei Punkte. Die affine Hülle von $H_1$ und $H_2$ ist von der Form $H_1\vee H_2:=P_1+U$, wobei $U:=T_{H_1}+T_{H_2}+K\cdot vec(P_1,P_2)$.

Corollar 4.8 (5. Dimensionsformel)

Ist $H_1\cap H_2=\mathrm{\varnothing }$, dann gilt $dim(H_1\vee H_2)=dim(H_1)+dim(H_2)-dim(T_{H_1}\cap T_{H_2})+1$.

Der linearen Unabhängigkeit von Vektoren entspricht die allgemeine Lage von Punkten.

Definition 4.9

Die Punkte $P_0,...,P_k\in 𝐀$ heißen in allgemeiner Lage, wenn $P_{i+1}\notin \mathscr{H}(P_0,...,P_i)$ für $i=0,...,k-1$.

Lemma 4.10

$P_0,...,P_k\in 𝐀$ sind in allgemeiner Lage gdw. $dim(\mathscr{H}(P_0,...,P_k))=k$ gdw. $\{vec(P_0,P_1),...,vec(P_0,P_k)\}$ linear unabhängig in $T_A$.

Insbesondere hängt damit die Eigenschaft ´allgemeine Lage´ nicht von der Reihenfolge der Punkte ab. Maximal ($n+1$) Punkte sind in einem $n$-dimensionalen affinen Raum in allgemeiner Lage. (Hinweis: Hat eine Punktmenge $M$ mehr als $(dim(𝐀)+1)$ Elemente, so gibt es noch eine verallgemeinerte Variante zum Begriff ’allgemeine Lage’, in dem definiert wird: $dim(\mathscr{H}(N))=min\{\mathrm{\#}N-1,dim(𝐀)\}$ für jede Teilmenge $N\subset M$. Frage: Wie könnte man den Begriff ’allgemeine Lage’ für eine beliebige Menge von Vektoren formulieren?)

Satz 4.11

Jeder affine Unterraum $H\subseteq {𝐀}^n$ ist Lösungsmenge eines linearen Gleichungssystems:

$H=\mathscr{H}(A,b)$.

Affine und baryzentrische Koordinaten

Im Vektorraum induziert jede Basis einen Koordinatenisomorphismus auf den Standardvektorraum. Im affinen Raum gilt dies analog, man benötigt dafür stets noch einen Punkt. Damit kann dann insbesondere der letzte Satz auf jeden affinen Raum verallgemeinert werden.

Definition 4.12

Eine Menge $K=(P_0,v_1,...,v_n)$ bestehend aus einem Punkt von $𝐀$ (Ursprung) und einer Basis von $T_{𝐀}$ heißt affines Koordinatensystem. Die zugehörige Koordinatenabbildung ${\mathrm{\Phi }}_K:𝐀\to {𝐀}^n$ ordnet jedem Punkt $P=P_0+{\lambda }_1{v}_1+...+{\lambda }_n{v}_n$ das Koordinaten-Tupel $(P{)}_K:=(1;1,...,n{)}^t$ zu.

Analog zum Basiswechsel gibt es reguläre Transformationsmatrizen hier aus $G{l}_{n+1}$ der Form $\tilde{T}=\left(\begin{array}{cc}1& 0\\ b& T\end{array}\right)$, die den Wechsel des Koordinatensystems beschreiben. Dabei ist $T$ die Transformationsmatrix zwischen den Basen des zugehörigen Vektorraumes und in der ersten Spalte $(1;b_1,...,b_n{)}^t$ stehen die Koordinaten des Ursprungs bzgl. des neuen Koordinatensystems. Für Anwendungen in der linearen Optimierung sind die folgenden Begriffe bedeutsam. Sie gelten im wesentlichen jedoch nur für reelle affine Räume. Deshalb sei bis zum Ende dieses Anschnittes $K=ℝ$ vorausgesetzt, d. h. alle affinen Räume und Vektorräume seien reell. Zur Einführung der so genannten baryzentrischen Koordinaten benötigen wir die folgende Vorbereitung.

Lemma 4.13

Seien $P_0,...,P_k\in 𝐀$ Punkte und ${\lambda }_0,...,{\lambda }_k\in ℝ$ reelle Zahlen mit ${\lambda }_0+...+{\lambda }_k=1$, dann ist der Punkt $P:=Q+{\lambda }_{0}vec(Q,P_0)+...+{\lambda }_{k}vec(Q,P_k)$ unabhängig von der Auswahl eines Punktes $Q$.

Definition 4.14

Seien $P_0,...,P_k\in 𝐀$ Punkte und ${\lambda }_0,...,{\lambda }_k\in ℝ$ reelle Zahlen mit ${\lambda }_0+...+{\lambda }_k=1$, dann heißt $P={\lambda }_0{P}_0+...+{\lambda }_k{P}_k$ eine baryzentrische Darstellung bzgl. der Punkte $P_0,...,P_k$. Dies ist wohldefiniert durch $P:=P_0+\sum _{i=1}^k{\lambda }_i\cdot vec(P_0,P_i)$.

Bemerkungen:

• Ein Punkt $P$ besitzt eine baryzentrische Darstellung bzgl. der Punkte $P_0,...,P_k$ gdw. $P\in \mathscr{H}(P_0,...,P_k)$.
• Die baryzentrische Darstellung eines Punktes $P$ ist eindeutig gdw. die Punkte $P_0,...,P_k$ in allgemeiner Lage sind. In diesem Fall sprechen wir von den Koeffizienten ${\lambda }_0,...,{\lambda }_k$ als die baryzentrischen Koordinaten von P.
• Ein Punkt $Q\in L(A,B)$ liegt zwischen $A$ und $B$ gdw. $Q=sA+tB$ und $s+t=1$ und $0\le s,t$. Mit [$A,B$] bezeichnen wir die Menge dieser Punkte, also die Strecke von $A$ nach $B$. Entsprechende Verallgemeinerungen gelten für konvexe Vielecke. (Hier benötigen wir für die Ordnungsrelation $\le$ die reellen Zahlen!)
• Der Punkt $\frac{1}{2}A+\frac{1}{2}B$ ist der Mittelpunkt der Strecke [A,B].
• Der Punkt $\frac{1}{3}A+\frac{1}{3}B+\frac{1}{3}C$ ist der ’Schwerpunkt’ des Dreiecks mit dem Ecken A,B,C (hier auch der Schnittpunkt der Seitenhalbierenden).

Entsprechende Verallgemeinerungen gelten für Vielecke. Von besonderem Interesse in der linearen Optimierung sind konvexe Polyeder als höher-dimensionale Verallgemeinerung von konvexen Vielecken. Am einfachsten lassen sich konvexe Polyeder als konvexe Hülle einer endlichen Punktmenge beschreiben:

Definition 4.15 (konvex, konvexe Hülle, endliches konvexes Polyeder)

Eine Teilmenge $K\subset 𝐀$ heißt konvex, wenn mit je zwei Punkten $A,B\in K$ die Verbindungsstrecke $[A,B]$ stets in $K$ liegt. Sei $M\subset 𝐀$ eine Punktmenge. Die konvexe Hülle $K(M)$ ist die kleinste konvexe Obermenge von $M$. Ein endliches konvexes Polyeder ist die konvexe Hülle von endlich vielen Punkten.

Die konvexe Hülle ist (wie auch die lineare und die affine Hülle) ein Hüllenoperator, d. h. $K(K(M))=K(M)$. Die konvexe Hülle von $k+1$ Punkten in allgemeiner Lage wird ein k-Simplex genannt.

Satz 4.16

$K(P_0,...,P_k)=\{\sum _{i=0}^k{\lambda }_i{P}_i|{\lambda }_i\ge 0,\sum {\lambda }_i=1\}$.

Offensichtlich ist der Durchschnitt konvexer Mengen wieder konvex. Die Menge der Punkte, die eine lineare Ungleichung erfüllen, nennen wir Halbraum. Halbräume sind konvex. Damit ist die Lösungsmenge eines Systems von linearen Gleichungen und linearen Ungleichungen ebenfalls konvex. In der linearen Optimierung wird daran anknüpfend die Frage gestellt, für eine konvexe Menge gegeben durch lineare Gleichungen und lineare Ungleichungen zu entscheiden, ob sie ein endliches Polyeder ist und wie die Ecken zu finden sind.

Affine Abbildungen

Zwischen affinen Räumen betrachten wir affine Abbildungen. Diese sollen geometrische Eigenschaften im affinen Raum erhalten: (1.) Geraden bleiben erhalten. (2.) Teilverhältnisse bleiben erhalten.

Liegen $A,B,C$ auf einer Geraden $L$, $A\ne B$, dann ist $vec(A,C)=\lambda \cdot vec(A,B)$. Die Zahl $\lambda$ wird Teilverhältnis von $A,B,C$ genannt: $(A:B:C):=\lambda$. Um die folgende Definition einer affinen Abbildung zu motivieren, schließen wir wie folgt: Sei $\phi$ eine Abbildung mit den Eigenschaften (1.) und (2.). Wir betrachten das Bild des Parallelogramms mit den Eckpunkten $A,B:=A+a$, $C:=A+a+b$ und $D:=A+b$ einschließlich seiner Diagonalen. Dies ist dann wieder ein Parallelogramm (warum?). Damit induziert $\phi$ eine Abbildung, und sogar eine lineare:

$T_{\phi }:T_{𝐀}\to T_{𝐀},vec(P,Q)\mapsto vec(\phi (P),\phi (Q))$.

Definition 4.17

Seien $𝐀$ und ${𝐀}^{\prime }$ affine Räume, eine Abbildung $\phi :𝐀\to {𝐀}^{\prime }$ heißt affin, wenn eine lineare Abbildung der zugehörigen Vektorräume $T_{\phi }:T_{𝐀}\to T_{{𝐀}^{\prime }}$ existiert, so dass gilt: $\phi (Q)=\phi (P)+T_{\phi }(vec(P,Q))$ für alle Punkte $P,Q\in 𝐀$.

Anders gesagt, eine affine Abbildung ist die Komposition einer Translation mit einer linearen Abbildung.

Beispiele: Translationen (hier: $T_{\phi }=id$), Parallelprojektionen in einen affinen Unterraum (hier ist $T_{\phi }$ ein Projektionsoperator: $T_{\phi }=T_{\phi }^2$) und Zentralprojektionen zwischen parallelen Unterräumen (hier: $T_{\phi }=\lambda \cdot id$).

Analog zum Prinzip der linearen Fortsetzung in Vektorräumen gilt für affine Abbildungen:

Satz 4.18

Eine affine Abbildung $\phi :𝐀\to {𝐀}^{\prime }$ ist eindeutig bestimmt durch das Bild von $(n+1)$ Punkten in allgemeiner Lage, $n=\dim 𝐀$.

Insbesondere können wir einer affinen Abbildung $\phi :{𝐀}^n\to {𝐀}^m$ eine Matrix $M(\phi )\in Mat(m+1,n+1)$ zuordnen. Dabei ergeben sich die Spalten aus den Bildern $\phi (0),T_{\phi }(e_1),...,T_{\phi }(e_n)$, also $M(\phi )=\left(\begin{array}{cc}1& 0\\ \phi (0)& M(T_{\phi })\end{array}\right)$. Entsprechend der Konvention mit der ’0-ten Komponente’ gilt sowohl für Punkte, als auch für Vektoren: $\phi (P)=M(\phi )P$ und $T_{\phi }(x)=M(\phi )x$. Ferner kann unschwer der Formalismus der Darstellungsmatrix einer affiner Abbildung bzgl. affiner Koordinatensysteme formuliert werden. Es gelten analoge Transformationsformeln.