LINEARE ALGEBRA II - uni-due.dehn213me/sk/knoop/Linal2.pdf · LINEARE ALGEBRA II 127. Kapi tel VI I...

Teil 2

LINEARE ALGEBRA II

127

Kapitel VII

Euklidische und unitareVektorraume

Wir beschaftigen uns jetzt mit Vektorraumen, die noch eine zusatzliche Struktur tragen.

Der Winkel zwischen Vektoren im IR2 bzw. im IR3 laßt sich mit Hilfe des sogenannten Ska-larprodukts berechnen. Durch Vergleich mit dem Kosinussatz erhalt man z. B. im IR2 fur zweiVektoren a = (a1, a2) und b = (b1, b2) die Beziehung:

!a! · !b! · cos ! = (a1, a2) ·!

b1

b2

"

= a1 b1 + a2 b2 ;

dabei sei ! der (kleinere der beiden) Winkel, welcher von den Vektoren a und b eingeschlossenwird, und es sei !a! bzw. !b! die Lange der Vektoren a bzw. b, d. h.: !a! =

#a1

2 + a22 und

!b! =#

b12 + b2

2 .

Wir wollen in allgemeinen Vektorraumen mit einem Skalarprodukt Drehungen beschreiben undspeziell im IR2 oder im IR3 Ellipsen bzw. Ellipsoide drehen und die beschreibende Gleichung inAbhangigkeit vom Drehwinkel aufstellen. Ist zum Beispiel

M! =$(x, y) " IR2

%%%x2

a2+

y2

b2= 1

&

eine Ellipse um den ”Koordinatenursprung“, so soll M! um 45! gegen den Uhrzeigersinn (umden Nullpunkt (0, 0) herum) gedreht werden. Wie lautet dann die beschreibende Gleichung furdie gedrehte Ellipse? — Solche und ahnliche Fragen behandeln wir in diesem und im nachstenKapitel.

§ 26 Skalarprodukte

26.1 Definition

Gegeben seien ein Vektorraum V " VRK (uber einem kommutativen Korper K ) und eineAbbildung s : V # V $ K .

129

130 KAPITEL VII. EUKLIDISCHE UND UNITARE VEKTORRAUME

a) s heißt eine Bilinearform auf V , wenn s in jeder Komponente linear ist, d. h. wenn gilt:

(BF1) s(v1 + v2 , w) = s(v1, w) + s(v2, w) ,

s(" v , w) = " s(v, w)

(BF2) s(v , w1 + w2) = s(v, w1) + s(v, w2) ,

s(v , " w) = " s(v, w)

fur alle v, v1, v2, w, w1, w2 " V und " " K .

b) Eine Bilinearform s auf V " VRK heißt symmetrisch, wenn fur alle v, w " V gilt:

s(v, w) = s(w, v) .

c) Eine symmetrische Bilinearform s auf einem reellen Vektorraum V " VRIR heißtein Skalarprodukt, wenn fur alle v " V \ {0} gilt:

s(v, v) > 0 .

d) Ist K = C und erfullt s die Eigenschaft (BF1) sowie

s(v , w1 + w2) = s(v, w1) + s(v, w2)und s(v , " w) = " s(v, w)

fur alle v, w, w1, w2 " V und " " C , dann heißt s eine Sesquilinearform31 auf V .

e) Eine Sesquilinearform s auf V " VRC heißt Hermite’sch32 oder eine Hermite’scheForm, wenn fur alle v, w " V gilt:

s(v, w) = s(w, v) .

(Speziell gilt fur alle v " V stets: s(v, v) " IR .)

f) Eine Hermite’sche Form s (auf einem komplexen Vektorraum V ) heißt ein Skalarprodukt,wenn fur alle v " V \ {0} gilt:

s(v, v) > 0 .

g) Ist s ein Skalarprodukt auf V " VRK , so heißt V ein euklidischer33 Vektorraum im FallK = IR oder ein unitarer Vektorraum im Fall K = C .

26.2 Beispiele

a) Ist V = IRn, dann wird fur x = (x1, x2, . . . , xn) und y = (y1, y2, . . . , yn) ein Skalarprodukt sdurch

s(x, y) := x · yt =n'

i=1

xi yi

definiert. (Dies ist also konsistent mit dem Begriff Skalarprodukt aus Definition 6.6.)31Lat.–ital.:

”1 1

2 fach linear“32Charles Hermite, franzosischer Mathematiker (!24.12.1822, †14.01.1901)33Eukleides von Alexandria, genannt: Euklid, altgriechischer Mathematiker (!ca. 365 v. Chr., †ca. 300 v. Chr.)

§ 26. SKALARPRODUKTE 131

b) Ist V = Cn , so wird entsprechend ein Skalarprodukt s definiert durch

s(x, y) := x · y t = x · yt =n'

i=1

xi yi .

In den Fallen a) und b) nennt man s dann das kanonische Skalarprodukt im IRn bzw. im Cn.

c) Es sei I := [%1 ;+1 ] und V := {f : I $ IR | f ist stetig auf I } . Dann wird mit

s(f, g) :=( +1

"1f(t) · g(t) dt

fur f, g " V ein Skalarprodukt s auf dem reellen Vektorraum V erklart.

d) Ist I = [%1 ; 1 ] und V := {f " Abb(I, C) | f ist stetig auf I } , so wird durch

s(f, g) :=( 1

"1f(t) · g(t) dt

entsprechend ein Skalarprodukt s auf dem komplexen Vektorraum V erklart.

26.3 Bemerkung

Es ist ublich, bei Skalarprodukten &f, g' anstatt s(f, g) zu schreiben.Um simultan die Falle K = IR bzw. K = C bei Skalarprodukten behandeln zu konnen,schreiben wir kunftig IK an Stelle von IR bzw. C .

Ist nun V " VRIK mit dimIK V = n und B = (v1, v2, . . . , vn) eine Basis von V , v :=n)

i=1xi vi

und w :=n)

i=1yi vi mit xi, yi " IK fur alle 1 ( i ( n sowie s eine symmetrische Bilinearform

bzw. eine Hermite’sche Form auf V , dann gilt:

s(v, w) =n'

i=1

xi · s(vi, w) =n'

i=1

xi ·n'

j=1

yj s(vi, vj)

= (x1, x2, . . . , xn)* +, -

= !B(v)t

·

.

////0

s(v1, v1) s(v1, v2) · · · s(v1, vn)s(v2, v1) s(v2, v2) · · · s(v2, vn)

......

...s(vn, v1) s(vn, v2) · · · s(vn, vn)

1

22223·

.

////0

y1

y2...

yn

1

22223

* +, -= !B(w)

.

26.4 Definition

Ist V " VRIK mit der Basis B = (v1, v2, . . . , vn) und s eine symmetrische Bilinearform (bzw.Hermite’sche Form) auf V wie oben, so heißt

ΦB(s) := (s(vi, vj))1#i,j#n " Mat(n, n; IK)

die darstellende Matrix von s bezuglich B.Aus Bemerkung 26.3 folgt direkt die Symmetrie von ΦB(s) im Fall IK = IR (vgl. Definition 6.8)und ΦB(s)H := ΦB(s)

t= ΦB(s)t = ΦB(s) im Fall IK = C (vgl. Satz 20.7(iv)).

Matrizen A " Mat(n, n; C) mit der Eigenschaft AH = A heißen Hermite’sch.


26.5 Lemma

Ist V " VRIK mit der Basis B = (v1, v2, . . . , vn) (also dimIK V = n), so wird durch die Zuordnungf : s )$ ΦB(s) eine bijektive Abbildung von der Menge der symmetrischen Bilinearformen (bzw.Hermite’schen Formen) auf V in die Menge der symmetrischen (bzw. Hermite’schen) Matrizenaus Mat(n, n; IK) definiert.

Beweis:

Ist A " Mat(n, n; IK) , v =n)

i=1xi vi und w =

n)i=1

yi vi , dann definieren wir sA durch

sA(v, w) := (x1, x2, . . . , xn) · A · (y1, y2, . . . , yn)t .

Ist IK = IR und A symmetrisch, so ist sA eine symmetrische Bilinearform auf V wegen

sA(v, w) = sA(v, w)t = (y1, y2, . . . , yn) · At · (x1, x2, . . . , xn)t

= (y1, y2, . . . , yn) · A · (x1, x2, . . . , xn)t

= sA(w, v) .

Im Fall IK = C und A Hermite’sch folgt entsprechend, daß sA eine Hermite’sche Form auf Vist. Bezeichnen wir die Abbildung A )$ sA mit g , so gilt fur A = (#ij) :

(f * g)(A) = f(sA) = ΦB(sA) = ($ij)1#i,j#n

mit$ij = sA(vi, vj) = ei · A · ej

t = ei · Aj = #ij .

Entsprechend gilt: (g * f)(s) = g(ΦB(s)) = s!B(s) =: r mit

r(v, w) = (x1, x2, . . . , xn) · ΦB(s) · (y1, y2, . . . , yn)t

= (x1, x2, . . . , xn) · (s(vi, vj))1#i,j#n · (y1, y2, . . . , yn)t

= s(v, w) .

Aus f * g = id und g * f = id folgt dann die Behauptung. !

26.6 Satz

Es sei V " VRIK endlich–dimensional und s eine symmetrische Bilinearform bzw. eine Her-mite’sche Form auf V ; ferner seien B = (v1, v2, . . . , vn) und B$ = (v$1, v$2, . . . , v$n) zwei Basenvon V sowie T := ΦB

B!(idV ) " GL(n; IK) die Transformationsmatrix des Basiswechsels von Bnach B$ .Ist dann A := ΦB(s) und B := ΦB!(s) , so gilt: A = T t · B · T .

Beweis:

Seien v =n)

i=1xi vi und w =

n)i=1

yi vi aus V gegeben; ist dann v =n)

i=1x$i v

$i und w =

n)i=1

y$i v$i ,

so gilt nach Lemma 17.1 (aus Lineare Algebra I):

(x$1, x$2, . . . , x

$n)t = T · (x1, x2, . . . , xn)t und (y$1, y

$2, . . . , y

$n)t = T · (y1, y2, . . . , yn)t .

§ 26. SKALARPRODUKTE 133

Daraus folgt (mit dem Beweis zu Lemma 26.5):

s(v, w) = s!B! (s)(v, w) = sB(v, w)

= (x$1, x$2, . . . , x$n) · B · (y$1, y$2, . . . , y$n)t

= (x$1, x$2, . . . , x$n) · B · (y$1, y$2, . . . , y$n)t

= (x1, x2, . . . , xn) · T t · B · T · (y1, y2, . . . , yn)t

= (x1, x2, . . . , xn) · T t · B · T · (y1, y2, . . . , yn)t

= s!B(s)(v, w) = sA(v, w)= (x1, x2, . . . , xn) · A · (y1, y2, . . . , yn)t .

!

26.7 Definition

Es sei s eine symmetrische Bilinearform (oder Hermite’sche Form) auf V " VRIK ; dann heißtdie Abbildung

qs : V $ IR mit qs(v) := s(v, v)

die zugeordnete quadratische Form.Und qs (bzw. s) heißt positiv definit, wenn fur alle Vektoren v " V \ {0} gilt: qs(v) > 0 .Gilt fur v " V nur die Ungleichung: qs(v) + 0 , so heißt qs (bzw. s) positiv semidefinit.Und qs (bzw. s) heißt indefinit, wenn es Vektoren v, w " V gibt mit qs(v) < 0 und qs(w) > 0 .

26.8 Bemerkungen

(i) Eine symmetrische Bilinearform (bzw. Hermite’sche Form) s ist genau dann ein Skalar-produkt, wenn s positiv definit ist.

(ii) Im Fall IK = IR gilt folgende Beziehung zwischen der symmetrischen Bilinearform s undder zugeordneten quadratischen Form qs :

s(v, w) =14

[qs(v + w)% qs(v % w)] =12

[qs(v + w)% qs(v)% qs(w)] .

(iii) Im Fall IK = C gilt fur eine Hermite’sche Form s und die zugeordnete quadratischeForm qs der Zusammenhang:

s(v, w) =14

[qs(v + w)% qs(v % w) + i qs(v + i w)% i qs(v % i w)]

mit i2 = %1 .

(iv) Gemaß Lemma 26.5 erhalten wir durch eine symmetrische (bzw. Hermite’sche) MatrixA " Mat(n, n; IK) eine quadratische Form qA auf dem IKn mit

qA(x) := sA(x, x) = (x1, x2, . . . , xn) · A · (x1, x2, . . . , xn)t = x · A · x t = x · A · xH

fur alle x =n)

i=1xi ei " IKn .

Das fuhrt zu:


26.9 Definition

Eine symmetrische (bzw. Hermite’sche) Matrix A " Mat(n, n; IK) heißt positiv definit, wennfur alle Vektoren x " IKn \ {0} gilt:

x · A · xH > 0 .

26.10 Bemerkung

Ist A " Mat(n, n; IK) positiv definit, so ist A stets regular.

Eine Diagonalmatrix ist genau dann positiv definit, wenn alle Diagonaleintrage positiv sind.

§ 27 Orthogonalisierung

In einem Vektorraum V " VRIK mit Skalarprodukt &·, ·' kann man die Lange (den Betrag oderdie Norm) eines Vektors v " V kanonisch einfuhren durch:

! · ! : V $ IR , v )$ !v! := &v, v'12 =

4&v, v' .

Wie man leicht nachpruft, gelten dann die folgenden charakteristischen Eigenschafteneiner Norm ! · ! auf V :

(N1) !v! = 0 ,- v = 0 .(N2) !" v! = |"| !v! fur alle v " V und " " IK .(N3) !v + w! ( !v!+ !w! fur alle v, w " V .

Es laßt sich ferner sofort zeigen, daß aus diesen Axiomen (N1) – (N3) die Eigenschaft !v! + 0fur alle v " V folgt.

Ein Vektor v " V mit !v! = 1 heißt ein Einheitsvektor.

Das dritte Axiom (N3), die sogenannte Dreiecksungleichung, kann auf folgenden Satz zuruck-gefuhrt werden:

27.1 Satz (Ungleichung von Cauchy34–Schwarz35–Bunjakowski36)

Sei V " VRIK ein Vektorraum mit Skalarprodukt &·, ·' ; dann gilt fur alle Vektoren v, w " V :

|&v, w'| " !v! · !w! .

In dieser Ungleichung steht genau dann das Gleichheitszeichen, wenn v und w linear abhangigsind.

(Oftmals findet man diesen Satz auch als Cauchy–Schwarz’sche Ungleichung .)34Augustin–Louis de Cauchy, franzosischer Mathematiker (!21.08.1789, †22.05.1857)35Karl Hermann Amandus Schwarz, deutscher Mathematiker (!25.01.1843, †30.11.1921)36Viktor Jakowlewitsch Bunjakowski, russischer Mathematiker (!16.12.1804, †12.12.1889)

§ 27. ORTHOGONALISIERUNG 135

Beweis zu Satz 27.1:

Fur w = 0 ist die Behauptung klar. #Gilt: w .= 0 , also insbesondere: !w! .= 0 , dann erhalten wir mit " :=

&v, w'!w!2 =

&w, v'!w!2 :

0 ( &v % " w , v % " w'= &v, v' % " &w, v' % " &v, w'+ " " &w, w'

= &v, v' % |&w, v'|2

!w!2 % |&v, w'|2

!w!2 +|&v, w'|2

!w!4 !w!2

= !v!2 % |&v, w'|2

!w!2 .

Multiplikation auf beiden Seiten mit !w!2 > 0 liefert:

!v!2 · !w!2 % |&v, w'|2 + 0 .

Gilt (im Fall w .= 0 ) das Gleichheitszeichen, so ist 0 = v % " w = v % &v, w'!w!2 w ; also sind v

und w linear abhangig. Sind umgekehrt v und w linear abhangig, etwa v = µw mit µ " IK , sofolgt:

|&v, w'| = |µ| |&w, w'| = |µ| · !w!2 = |µ| !w! · !w! = !µw! · !w! = !v! · !w! .

!

Hieraus ergibt sich dann die Dreiecksungleichung fur Normen:

27.2 Korollar (Minkowski’sche37 Ungleichung)

Ist V " VRIK mit einem Skalarprodukt &·, ·' versehen, so gilt fur alle Vektoren v, w " V :

!v + w! ( !v!+ !w! .

Beweis:

Wegen Re " (#

(Re ")2 + (Im ")2 = |"| gilt:

!v + w!2 = &v + w , v + w' = !v!2 + &v, w'+ &w, v'+ !w!2

= !v!2 + &v, w'+ &v, w'+ !w!2

= !v!2 + 2 Re&v, w'+ !w!2

( !v!2 + 2 |&v, w'| + !w!2

( !v!2 + 2 !v! · !w!+ !w!2 nach Satz 27.1

= (!v!+ !w!)2 .

!37Hermann Minkowski, deutscher Mathematiker und Physiker (!22.06.1864, †12.01.1909)


Eine Norm ! ·! auf einem Vektorraum V " VRIK induziert in kanonischer Weise eine Abstands-funktion oder Metrik d auf V durch38:

d : V # V $ IR , (v, w) )$ d(v, w) := !v % w! ,

die durch folgende Eigenschaften charakterisiert ist:

(M1) d(v, w) = 0 ,- v = w .(M2) d(v, w) = d(w, v) (Symmetrie).(M3) d(u, w) ( d(u, v) + d(v, w) (Dreiecksungleichung).

Dabei seien u , v und w beliebige Elemente aus V .Aus diesen Axiomen (M1) – (M3) erhalt man entsprechend die Eigenschaft: d(v, w) + 0 furalle v, w " V . Mit d(v, w) mißt man also den Abstand zweier Vektoren.

27.3 Bemerkungen

(i) Es sei V " VRIK euklidisch bzw. unitar; dann gilt fur alle Vektoren v, w " V :

a) !v + w!2 = !v!2 + !w!2 + &v, w'+ &w, v' (Satz des Pythagoras39

in allgemeiner Form).b) !v + w!2 + !v % w!2 = 2 (!v!2 + !w!2) (Parallelogrammgleichung).

(ii) Es sei V " VRIK ein Vektorraum mit einer Norm ! · ! . Es existiert genau dann ein Ska-larprodukt s auf V mit !v! = (s(v, v))

12 fur alle v " V , wenn ! · ! die obige Parallelo-

grammgleichung erfullt.Dieser Satz geht auf J. v. Neumann40 und P. Jordan41 und das Jahr 1935 zuruck. DerBeweis wird ublicherweise in der Funktionalanalysis gefuhrt (oder vgl. [24, S. 155]).

27.4 Definition

Es sei V " VRIK ein euklidischer oder unitarer Vektorraum.

a) Sind v, w " V mit &v, w' = 0 , so heißt v orthogonal zu w. Wir schreiben dann: v / w .

b) Sind U und W Untervektorraume von V , so heißt U orthogonal zu W , wenn fur alle u " Uund alle w " W gilt: u / w . Kurzschreibweise: U / W .

c) Eine beliebige Familie (vi)i%I von Vektoren aus V heißt orthogonal, wenn fur alle i, j " Imit i .= j gilt: vi / vj . Man nennt (vi)i%I dann auch ein Orthogonalsystem in V .

d) Eine Familie (vi)i%I von Vektoren aus V heißt orthonormal, wenn die Familie (vi)i%I or-thogonal ist und wenn fur alle i " I gilt: !vi! = 1 .Entsprechend bezeichnet man (vi)i%I dann auch als Orthonormalsystem in V .

e) Eine Familie (vi)i%I von Vektoren aus V heißt eine Orthonormalbasis von V , falls (vi)i%I

eine Basis von V und orthonormal ist.38Engl. distance = Distanz, Abstand, Entfernung39Pythagoras von Samos, altgriechischer Philosoph, Mathematiker, Astronom und Ordensfuhrer (!ca. 580

v. Chr., †ca. 500 v. Chr.)40John (Johann, Janos) von Neumann, ungarisch–deutsch–amerikanischer Mathematiker, Informatiker und Phy-

siker (!28.12.1903, †08.02.1957)41Ernst Pasqual Wilhelm Jordan, deutscher theoretischer Physiker (!18.10.1902, †31.07.1980)


27.5 Beispiele

(i) Ist &·, ·' das kanonische Skalarprodukt im IKn , so bildet (e1, e2, . . . , en) eine Orthonormal-basis des IKn .

(ii) Es sei I := [ 0 ; 2% ] und V := {f " Abb(I, C) | f ist stetig auf I } wie in Beispiel 26.2d),

&f, g' :=( 2"

0f(t) · g(t) dt und ek(x) := eikx = cos kx + i sin kx fur x " I .

Dann gilt fur alle j, k " ZZ mit j .= k :

&ej , ek' =( 2"

0ej(t) · ek(t) dt =

( 2"

0eijt · eikt dt

=( 2"

0eijt · (cos kt + i sin kt) dt =

( 2"

0eijt · (cos kt% i sin kt) dt

=( 2"

0eijt · ( cos(%kt) + i sin(%kt)) dt =

( 2"

0eijt · e"ikt dt

=( 2"

0ei(j"k)t dt =

( 2"

0

5cos((j % k) t) + i sin((j % k) t)

6dt

=1

j % k

7sin((j % k) t)% i cos((j % k) t)

82"

0

=1

i (j % k)ei(j"k)t

%%%2"

0= 0 .

Also bildet (ek)k%ZZ ein Orthogonalsystem. Wegen &ek, ek' = 2% ist dann ( 1&2"

ek)k%ZZ eineorthonormale Familie in V .

27.6 Definition

Es seien V " VRIK euklidisch bzw. unitar und U ein endlich–dimensionaler Untervektorraumvon V mit einer Orthonormalbasis (u1, u2, . . . , un) . Dann heißt die Abbildung

PU : V $ U mit PU (v) :=n'

i=1

&v, ui'ui

die Orthogonalprojektion von V auf U .

27.7 Beispiel

Es sei V = IR2 , Ui := <ui> mit u1 = 1&2(1, 1) und

u2 = 1&2(%1, 1) . Dann gilt fur v = (0, 1) :

PU1(v) = &v, u1'u1 =102

u1 =12

(1, 1)

undPU2(v) = &v, u2'u2 =

102

u2 =12

(%1, 1) ,

also: PU1(v) + PU2(v) = v = idIR2(v) .

!...........................................................................................................................................................

...................................................................................................................................

!

u2

"

u1#

v

!PU2(v)

"PU1(v)

.........................................

...............................................................................................................

U1 U2

Wir haben damit v zerlegt in zwei Komponenten, wobei &PU1(v), PU2(v)' = 0 ist.


27.8 Definition

Sei V " VRIK euklidisch bzw. unitar mit Unterraumen V1, V2, . . . , Vk . Der Vektorraum V heißtdie orthogonale Summe von V1, V2, . . . , Vk, wenn folgendes gilt:

(i) V = V1 + V2 + . . . + Vk .

(ii) Es ist Vi / Vj fur alle 1 ( i, j ( k mit i .= j .

Wir schreiben dann: V = V11/ V21/ . . .1/ Vk .

27.9 Bemerkung

Ist V orthogonale Summe von V1, V2, . . . , Vk , so ist die Summe direkt: V = V1 2 V2 2 . . .2 Vk .

Beweis:

Nach Bemerkung 4.8(ii) ist zu zeigen: Vi 3k)

j=1j '=i

Vj = {0} fur alle 1 ( i ( k .

Sei dazu x " Vi und x =k)

j=1j '=i

vj "k)

j=1j '=i

Vj . Dann gilt fur alle v " Vi :

&x, v' =k'

j=1j '=i

&vj , v' = 0 , also speziell: &x, x' = 0 ,- x = 0 .

!

Wir wollen uns jetzt mit der Existenz von Orthonormalbasen beschaftigen.

27.10 Satz (Orthonormalisierungsverfahren von Schmidt42–Gram43)

Zu jedem endlichen oder hochstens abzahlbar–unendlichen System (x1, x2, x3, . . . ) linear un-abhangiger Vektoren aus einem euklidischen bzw. unitaren Vektorraum V " VRIK gibt esgenau ein entsprechendes Orthonormalsystem (v1, v2, v3, . . . ) mit folgenden Eigenschaften:

(a) Fur alle k = 1, 2, 3, . . . gilt:

<x1, x2, . . . , xk> = <v1, v2, . . . , vk> =: Vk .

(b) Die zu dem Basiswechsel von (x1, x2, . . . , xk) nach (v1, v2, . . . , vk) in Vk gehorende Trans-formationsmatrix besitzt eine positive Determinante Dk fur jedes k = 1, 2, 3, . . . .

42Erhard Schmidt, deutscher Mathematiker (!13.01.1876, †06.12.1959)43Jørgen Pedersen Gram, danischer Mathematiker (!27.06.1850, †29.04.1916)



Die orthonormalen Vektoren v1, v2, v3, . . . werden induktiv definiert.Ist das System endlich, so bricht das Verfahren nach endlich vielen Schritten ab. Wegen derlinearen Unabhangigkeit von (x1, x2, x3, . . . ) ist stets x1 .= 0 , also v1 := x1

(x1( ein Vektor mitder Lange !v1! = 1 . Außerdem gilt: <x1> = <v1> = V1 mit D1 = 1

(x1( > 0 . Ist umgekehrte1 " V mit <e1> = <x1> , so gilt: e1 = c x1 mit c " IK . Also ist c die Determinante derTransformationsmatrix; wegen (b) muß namlich c > 0 gelten. Wir erhalten aus !e1! = 1 :

1 = &e1, e1' = c c &x1, x1' = |c|2 !x1!2 ,

was mit c > 0 sofort c = 1(x1( liefert. Damit ist e1 = v1 eindeutig (Induktionsanfang).

Es seien nun die Vektoren v1, v2, . . . , vn so konstruiert, daß (a) und (b) fur k = 1, 2, . . . , n erfulltsind (Induktionsvoraussetzung).Dann gilt: Vn+1 = <x1, x2, . . . , xn, xn+1> = <v1, v2, . . . , vn, xn+1> ; wir betrachten:

wn+1 := xn+1 %n'

#=1

&xn+1, v#' v# = xn+1 % PVn(xn+1) .

Nach dem Austauschlemma 3.8 gilt: Vn+1 = <v1, v2, . . . , vn, wn+1> . Fur jedes µ = 1, 2, . . . , nist ferner

&vµ, wn+1' = &vµ, xn+1' %n'

#=1

&xn+1, v#' &vµ, v#' = &vµ, xn+1' % &xn+1, vµ' = 0 ,

also (v1 , v2 , . . . , vn , vn+1 := 1(wn+1( wn+1) ein Orthonormalsystem mit der Eigenschaft (a).

Die Transformation lautet:v1 = #11 x1

v2 = #21 x1 + #22 x2

v3 = #31 x2 + #32 x2 + #33 x3...

vn = #n1 x1 + #n2 x2 + . . . + #nn xn

vn+1 = #n+1,1 x1 + #n+1,2 x2 + . . . + #n+1,n xn +1

!wn+1!xn+1 .

Mithin gilt fur die Determinante:

Dn+1 =n9

i=1

#ii ·1

!wn+1!= Dn ·

1!wn+1!

;

und nach Induktionsvoraussetzung ist Dn > 0 , also auch Dn+1 > 0 .Ist umgekehrt en+1 " V derart, daß (v1, v2, . . . , vn, en+1) ein Orthonormalsystem mit den Ei-

genschaften (a) und (b), so gilt wegen (a) analog zu oben: en+1 =n)

#=1## v# + c xn+1 mit c .= 0 .

Daher gilt auch: en+1 = c [xn+1 %n)

#=1$# v# ] . Fur µ = 1, 2, . . . , n erhalten wir:

0 = &en+1, vµ' = c [&xn+1, vµ' % $µ] , d. h. wegen c .= 0 : $µ = &xn+1, vµ' .

Es folgt schließlich:en+1 = c [xn+1 % PVn(xn+1)] = c wn+1

und damit wegen Bedingung (b) wie beim Induktionsanfang: c = 1(wn+1( .

Also ist en+1 = vn+1 eindeutig bestimmt (Induktionsschritt). !


27.11 Folgerung

Es sei V " VRIK euklidisch oder unitar und U ein endlich–dimensionaler Unterraum von V .Besitzt V endliche oder abzahlbar–unendliche Dimension, so kann jede Orthonormalbasis vonU zu einer Orthonormalbasis von V erganzt werden. Speziell besitzt dann V selbst eine Ortho-normalbasis.

Beweis:

Es sei dimIK U = n und (v1, v2, . . . , vn) eine Orthonormalbasis von U . Diese Basis kann zu einerBasis (v1, v2, . . . , vn, xn+1, xn+2, . . . ) von V erganzt werden (vgl. Beweis zu Satz 3.12). Wendenwir auf diese Basis das Verfahren von Schmidt–Gram an, so bleiben die ersten v1, v2, . . . , vn

erhalten, und es ergibt sich eine Orthonormalbasis (v1, v2, . . . , vn, vn+1, vn+2, . . . ) von V . !

27.12 Beispiel

Wir versehen den IR4 mit dem kanonischen Skalarprodukt &·, ·' und wenden Satz 27.10 auf dielinear unabhangigen Vektoren

x1 = (4, 2,%2,%1) , x2 = (2, 2,%4,%5) , x3 = (0, 8,%2,%5)

an. Wir erhalten das Orthonormalsystem (v1, v2, v3) mit

v1 =1

!x1!x1 =

15

(4, 2,%2,%1) ;

w2 = x2 % &x2, v1' v1 = (2, 2,%4,%5)% 255· 15

(4, 2,%2,%1) = (%2, 0,%2,%4) ,

v2 =1

!w2!w2 =

1024

(%2, 0,%2,%4) ;

w3 = x3 % &x3, v1' v1 % &x3, v2' v2

= (0, 8,%2,%5)% 255· 15

(4, 2,%2,%1)% 24024

· 1024

(%2, 0,%2,%4)

= (%2, 6, 2, 0) ,

v3 =1

!w3!w3 =

1044

(%2, 6, 2, 0) .

27.13 Satz

Es sei V " VRIK euklidisch oder unitar und U ein endlich–dimensionaler Untervektorraum mitder Orthonormalbasis (u1, u2, . . . , un) . Dann gilt fur jeden Vektor v " V :

!v % PU (v)! ( !v % u! fur alle u " U .

Beweis:

Es ist fur jedes 1 ( j ( n (nach dem Beweis zu Satz 27.10):

&v % PU (v) , uj' =:v %

n'

i=1

&v, ui'ui , uj

;= 0 - &v % PU (v) , u$' = 0 4u!%U .

§ 28. ADJUNGIERTE ABBILDUNGEN 141

Fur alle v " V gilt damit:

!v % u!2 = !(v % PU (v)) + (PU (v)% u)!2

= !v % PU (v)!2 + 2 Re&v % PU (v) ,

=u!%U, -* +PU (v)% u '+ !PU (v)% u!2

= !v % PU (v)!2 + !PU (v)% u!2 + !v % PU (v)!2 .

Und Gleichheit liegt genau dann vor, wenn PU (v)% u = 0 , d. h. u = PU (v) ist. !

§ 28 Adjungierte Abbildungen

Ohne dies explizit zu erwahnen, seien in diesem Abschnitt stets V,W " VRIK als zwei euklidi-sche oder unitare Vektorraume und F : V $ W als eine IK–lineare Abbildung vorgegeben.Ist M 5 V eine Teilmenge, so heißt

M) := {v " V | v / M} = {v " V | &v, m' = 0 fur alle m " M}

das orthogonale Komplement von M in V .

28.1 Definition

Eine IK–lineare Abbildung F * : W $ V heißt die zu F adjungierte Abbildung, wenn fur allev " V und w " W gilt44:

&Fv , w'W = &v , F *w'V .

28.2 Bemerkungen

(i) Im allgemeinen muß zu einer linearen Abbildung F keine adjungierte Abbildung existieren.

(ii) Existiert F * jedoch, so ist F * eindeutig bestimmt.

Beweis zu (ii):

Ist F $ neben F * ebenfalls eine adjungierte Abbildung zu F , so gilt fur jedes v " V und jedesw " W gemaß Definition 28.1:

&v , F *w % F $w' = &v, F *w' % &v, F $w' = &Fv,w' % &Fv,w' = 0 .

Daraus folgt: F *w % F $w = 0 oder F *w = F $w . !

28.3 Satz

Ist dimIK V = n , so existiert zu jeder linearen Abbildung F : V $ W die adjungierte AbbildungF * : W $ V . Ist (v1, v2, . . . , vn) eine Orthonormalbasis von V , so gilt fur alle w " W :

F *w =n'

#=1

&w , Fv#' v# .

44Hierbei bezeichnet !·, ·"W und !·, ·"V das jeweilige Skalarprodukt in W bzw. in V , worauf wir kunftig nichtmehr extra hinweisen. Ferner werden die Klammern bei der Abbildung weggelassen; statt F (v) oder F "(w)schreibt man kurz: Fv bzw. F "w .



Nach Folgerung 27.11 besitzt V eine Orthonormalbasis (v1, v2, . . . , vn) . Dann gilt fur jedes v " Vdie Darstellung:

v =n'

#=1

&v, v#' v# .

Ist namlich v =n)

#=1## v# mit ## " IK , so folgt: &v, vµ' =

n)#=1

## &v# , vµ' = #µ . Definieren wir

nun F * wie oben, so ist F * wegen der Linearitat des Skalarproduktes in der ersten Komponentegemaß (BF1) ebenfalls linear. Ferner gilt dann:

&Fv,w' =n'

#=1

&v, v#' &Fv# , w' =n'

#=1

&v, v#' &w, Fv#'

=:v ,

n)#=1&w, Fv#' v#

;= &v, F *w' .

!

28.4 Satz

Zu F : V $ W existiere die adjungierte Abbildung F * : W $ V . Dann existiert auch die zuF * adjungierte Abbildung F ** : V $ W mit F ** = F . Ferner gilt:

Ker F * = (Im F )) und KerF = (Im F *)) .

Ist F surjektiv, so ist F * injektiv; ist F * surjektiv, dann ist F injektiv.

Beweis:

Es gilt: &F *w, v' = &w, F **v' = &v, F *w' = &Fv,w' = &w, Fv' ; also ist F ** = F . Ferner gilt:

w " Ker F * ,- F *w = 0 ,- &v, F *w' = &Fv,w' = 0 4v%V

,- w / Im F ,- w " (Im F )) .

Weiter gilt wegen (F *)* = F ** = F auch: KerF = KerF ** = Ker (F *)* = (Im F *)) .Ist F surjektiv, so gilt: KerF * = (Im F )) = W) = {0} , d. h. daß F * injektiv ist. Ist F *

surjektiv, dann folgt entsprechend: KerF = (Im F *)) = V ) = {0} . !

28.5 Satz

Es seien V und W endlich–dimensional, (v1, v2, . . . , vn) eine Orthonormalbasis von V und(w1, w2, . . . , wr) eine Orthonormalbasis von W . Ist dann A die darstellende Matrix der linearenAbbildung F : V $ W bezuglich dieser Basen, so besitzt die adjungierte Abbildung F * : W $ Vbezuglich dieser Basen die darstellende Matrix AH .



Gemaß §16 gilt fur die Matrix A = (#ij) : F (v#) =r)

$=1#$# w$ . Hieraus folgt: &F (v#), w$' = #$#

fur alle 1 ( & ( r und 1 ( ' ( n . Ist B = ($ij) die darstellende Matrix von F * , so gilt

entsprechend: F *(w$) =n)

#=1$#$ v# , also: &F *(w$), v#' = $#$ fur jedes 1 ( ' ( n und 1 ( & ( r .

Daraus folgt:

$#$ = &F *w$, v#' = &v# , F *w$' = &Fv# , w$' = #$# = ##$t 4 1#"#n

1###r,

d. h.: B = At = At = AH . !

28.6 Definition

Es sei V " VRIK euklidisch bzw. unitar. Ein Endomorphismus F : V $ V heißt normal , wenndie zu F adjungierte Abbildung F * : V $ V existiert und mit F vertauschbar ist, d. h. fallsgilt:

F * F * = F * * F .

28.7 Satz

Ein Endomorphismus F : V $ V ist genau dann normal, wenn der zu F adjungierte Endomor-phismus F * existiert und fur alle v, w " V gilt:

&Fv , Fw' = &F *v , F *w' .

Beweis:

”-“: Aus F * F * = F * * F folgt sofort:

&Fv, Fw' = &v, F *(Fw)' = &v, F (F *w)' = &F (F *w), v' = &F *w, F *v' = &F *v, F *w' .

”,“: Umgekehrt ergibt sich aus &Fv, Fw' = &F *v, F *w' fur alle v, w " V :

&F (F *v), w' = &F *v, F *w' = &Fv, Fw' = &F *(Fv), w' ,

also: &F * F * v % F * * F v , w' = &(F * F * % F * * F )v , w' = 0 .Da dies auch bei festem v fur samtliche w " V gilt, erhalten wir: F * F * v = F * * F v .Weil dieses v " V aber beliebig wahlbar ist, folgt also: F * F * = F * * F .

!

28.8 Folgerung

Es sei F " EndIK(V ) normal. Dann gilt:

a) KerF = KerF * .

b) F und F * besitzen dieselben Eigenvektoren: Ist v " V Eigenvektor von F zum Eigen-wert " " IK , so ist v auch Eigenvektor von F * zum Eigenwert " .


Beweis zu Folgerung 28.8:

zu a): Aus Satz 28.7 folgt direkt fur alle v " V : !Fv!2 = !F *v!2 ; also ist Fv = 0aquivalent zu F *v = 0 .

zu b): Und aus Satz 28.7 folgt weiterhin:

&Fv % " v , Fv % " v' = !Fv!2 % " &v, Fv' % " &Fv, v'+ " " !v!2

= !F *v!2 % " &F *v, v' % " &v, F *v'+ |"|2 !v!2

= &F *v % " v , F *v % " v' .

Damit ist Fv = " v aquivalent zu F *v = " v .

!

28.9 Satz (Spektralsatz fur komplexe normale Endomorphismen)

Es sei V " VRC unitar mit dimC V = n . Dann sind folgende Aussagen fur einen Endomor-phismus F : V $ V aquivalent:

a) F ist normal.

b) Es existiert eine Orthonormalbasis von V , die aus lauter Eigenvektoren von F besteht.

Beweis:

”a)-b)“: Es existiert ein Eigenwert "1 " C von F und ein zugehoriger Eigenvektor v1 " V .Ohne Beschrankung der Allgemeinheit konnen wir !v1! = 1 voraussetzen (Indukti-onsanfang).Sei nun W := <v1>) = {w " V | &v1, w' = 0} das orthogonale Komplementdes Aufspanns von v1 in V . Wir konnen (v1) erganzen zu einer Orthonormalbasis(v1, v2, v3, . . . , vn) von V ; dann gilt: W = <v2, v3, . . . , vn> , also: dimC W = n% 1 .Weiter gilt fur alle w " W nach Folgerung 28.8b):

&v1, Fw' = &F *v1, w' = &"1 v1 , w' = "1 &v1, w' = 0 ,

d. h.: Fw " W . Damit ist F (W ) 5 W , also G := F |W : W $ W ein normalerEndomorphismus in W (mit der adjungierten Abbildung G* = F *|W ). Nach Indukti-onsvoraussetzung existiert eine Orthonormalbasis von W , die nur aus Eigenvektorenvon G , also auch von F besteht. Zusammen mit v1 erhalten wir die gewunschteOrthonormalbasis von V .

”b)- a)“: Sei (v1, v2, . . . , vn) eine Orthonormalbasis von V aus lauter Eigenvektoren von F .Wir definieren einen Endomorphismus G : V $ V durch G(vi) := "i vi und lineareFortsetzung, wenn Fvi = "i vi fur 1 ( i ( n ist. Dann gilt fur alle 1 ( i, j ( n :

&Fvi, vj' = &"i vi , vj' = "i &vi, vj' = "i · (ij

= &vi , "j vj' = &vi, Gvj' ;


also folgt fur samtliche v, w " V : &Fv,w' = &v, Gw' . Damit ist G = F * .Weiter gilt fur jedes i = 1, 2, . . . , n :

F *Fvi = G("i vi) = "i "i vi = "i "i vi

= F ("i vi) = F (Gvi) = FF *vi ,

also: F * * F = F * F * . Daher ist F normal.

!

28.10 Bemerkung und Definition

Ist V " VRC unitar und (v1, v2, . . . , vn) eine Orthonormalbasis von V aus Eigenvektoren desEndomorphismus F " EndC(V ) , so gilt fur die darstellenden Matrizen von F und F * bezuglichdieser Basis wegen der Normalitat von F :

A · AH = AH · A .

Folglich sagt man, eine Matrix A " Mat(n, n; C) heiße normal , wenn A · AH = AH · A gilt.

28.11 Bemerkung

Ist V " VRC unitar, F : V $ V normal und (v1, v2, . . . , vn) eine Orthonormalbasis von V ;

dann gilt fur beliebiges v :=n)

i=1&v, vi' vi aus V mit vi als jeweilige Eigenvektoren von F zum

Eigenwert "i " C :

F (v) =n'

i=1

&v, vi'F (vi) =n'

i=1

"i &v, vi' vi =n'

i=1

"i P<vi>(v) .

Dabei ist P<vi> die Orthogonalprojektion von V auf den von vi erzeugten Unterraum. Setzen

wir zur Abkurzung Pi := P<vi> , so gilt daher: F =n)

i=1"i Pi mit

(Pi * Pj)(v) = Pi(&v, vj' vj) = &v, vj' &vj , vi' vi = (ij Pi(v) = (ij Pj(v) = (Pj * Pi)(v) .

Sei nunmehr V " VRIR euklidisch und F : V $ V normal, so ist Satz 28.9 nicht direkt uber-tragbar, wenn nicht die Existenz lauter reeller Eigenwerte gewahrleistet ist. Dann kann man sichjedoch folgendermaßen behelfen:Ist dimIR V = n , so definieren wir W := V # V = V 2 und erklaren darauf eine Addition undeine Skalarmultiplikation mit komplexen Zahlen durch die Festlegungen

(x1, y1) + (x2, y2) := (x1 + x2 , y1 + y2) und # · (x, y) := (#1 x% #2 y , #1 y + #2 x)

fur alle x, x1, x2, y, y1, y2 " V und # = #1+i#2 " C . Man uberlegt sich, daß dadurch ein Vektor-raum (W, +, ·) uber C entsteht mit dimC W = dimIR V = n . Und W heißt die komplexe Erwei-terung von V . Identifizieren wir namlich (x,0) mit x " V , so wird V isomorph in W eingebet-tet. Wegen i ·(x,0) = (0, x) konnen wir dann fur jedes z := (x, y) " W schreiben: z = x+i y .Ist nun &·, ·' das Skalarprodukt auf V , so erklaren wir ein Skalarprodukt s : W #W $ C durch

s(z, z$) := (&x, x$'+ &y, y$') + i (&y, x$' % &x, y$')


fur alle z = (x, y) und z$ = (x$, y$) aus W . Dann ist s das einzige Skalarprodukt auf W mits|V+V = &·, ·' . (Ist namlich t : W #W $ C ein Skalarprodukt mit t|V+V = &·, ·' , so folgt furz = x + i y und z$ = x$ + i y mit x, x$, y, y$ " V :

t(z, z$) = t(x, x$) + i t(y, x$)% i t(x, y$) + t(y, y$) ;

und wegen t(x, x$) = &x, x$' , t(y, x$) = &y, x$' , t(x, y$) = &x, y$' , t(y, y$) = &y, y$' erhalt man:

t(z, z$) = (&x, x$'+ &y, y$') + i (&y, x$' % &x, y$') = s(z, z$) . )

Damit laßt sich jeder euklidische Vektorraum in einen unitaren Vektorraum einbetten.Ist weiter F : V $ V eine IR–lineare Abbildung, so gibt es genau eine C–lineare Abbildung<F : W $ W mit <F |V = F , d. h. mit <F (v) = F (v) fur alle v " V . Dazu definieren wir:

<F (z) = <F (x + i y) := F (x) + i F (y)

fur alle z = x + i y " W . Ist F normal, dann ist auch <F normal. Hierzu uberlegen wir unszunachst, daß fur den zu <F adjungierten Endomorphismus <F * gilt:

<F *(x + i y) = F *(x) + i F *(y) , d. h.: <F * = =F * .

(Denn: Seien z = x + i y und z$ = x$ + i y$ beliebig aus W ; dann gilt:

s( <F (x + i y) , x$ + i y$) = s(F (x) + i F (y) , x$ + i y$)

= (&F (x), x$'+ &F (y), y$') + i (&F (y), x$' % &F (x), y$')= (&x, F *(x$)'+ &y, F *(y$)') + i (&y, F *(x$)' % &x, F *(y$)')= s(x + i y , F *(x$) + i F *(y$)) . )

Hieraus folgt schließlich wegen F * F * = F * * F und !F *G = <F * <G fur F,G " EndIR(V ) :

<F * <F * = <F * =F * = !F * F * = !F * * F = =F * * <F = <F * * <F .

Also ist mit F auch <F normal.

28.12 Lemma

Es sei V " VRIR euklidisch mit dimIR V = n und F " EndIR(V ) normal. Mit W " VRC

bezeichnen wir die unitare Erweiterung von V und mit <F " EndC(W ) die lineare Fortsetzungvon F auf W gemaß Bemerkung 28.11. Ist dann z = x + i y aus W mit !z! :=

#s(z, z) = 1

ein Eigenvektor von <F zum Eigenwert " " C \ IR , so ist z$ = x% i y ebenfalls ein Eigenvektorvon <F mit !z$! = 1 zum Eigenwert " . Ferner sind z und z$ dann orthogonal.

Beweis zu Lemma 28.12:

Wegen x, y " V ist &x, y' = &y, x' . Hieraus folgt fur das z$ = x% i y " W :

s(z$, z$) = (&x, x'+ &y, y') + i (&%y, x' % &x,%y') = &x, x'+ &y, y' = s(z, z) = 1 .


Weiter gilt mit " = "1 + i"2 fur "1, "2 " IR :

<F (z) = F (x) + i F (y) = " · z = ("1 x% "2 y) + i ("1 y + "2 x) ,

also: F (x) = "1 x% "2 y sowie F (y) = "1 y + "2 x und daher:

<F (z$) = F (x)% i F (y) = ("1 % i"2) · (x% i y) = " · z$ .

Nach Folgerung 28.8b) ist z$ ein Eigenvektor von <F * zum Eigenwert " = " . Daraus folgt:

" s(z, z$) = s(" · z , z$) = s( <Fz , z$) = s(z , <F *z$) = s(z , " · z$) = " s(z, z$) .

Und wegen " .= " ergibt sich letztlich, daß s(z, z$) = 0 ist. !

28.13 Satz (Spektralsatz fur reelle normale Endomorphismen)

Es sei V " VRIR euklidisch mit dimIR V = n und F : V $ V ein Endomorphismus. Dann sindfolgende Aussagen aquivalent:

a) F ist normal.

b) Es existiert eine Orthonormalbasis von V derart, daß die darstellende Matrix A von Fbezuglich dieser Basis die Gestalt

A =

.

//////0

"1 "2 0. . ."k Ak+1

Ak+2

0 . . .Am

1

2222223

hat, wobei "1, "2, . . . ,"k die reellen Eigenwerte von F sind und wobei die Diagonaleintra-ge A# reelle (2# 2)-Matrizen der Form

A# =!

## +$#

%$# ##

"

sind fur ' = k+1, k+2, . . . ,m . Jedem A# entspricht ein Paar "# ,"# konjugiert komplexerEigenwerte von <F mit ## = Re "# und $# = Im "# .


”a)-b)“: Man fuhrt den Beweis durch vollstandige Induktion nach n .Der Fall n = 1 ist trivial.Es sei also n + 1 und die Behauptung fur kleinere Dimension bewiesen. Besitzt Feinen reellen Eigenwert, dann ergibt sich die Behauptung wie im Beweis zum Spek-tralsatz 28.9. #Besitzt F nun keinen reellen Eigenwert, so betten wir V in seine komplexe ErweiterungW ein und setzen F zu einem Endomorphismus <F von W fort. Sei dazu " " C \ IREigenwert von <F zu einem Eigenvektor z " W mit !z! = 1 . Ist z = x + i y mit


x, y " V , so ist z$ = x% i y " W nach Lemma 28.12 Eigenvektor von <F mit !z$! = 1zum Eigenwert " . Ferner gilt: z / z$ . Wir setzen jetzt

v1 :=102

(z + z$) =0

2 x und v2 :=1

i0

2(z % z$) =

02 y ;

also sind v1, v2 " V mit

&v1, v1' = &v2, v2' =12

(s(z, z) + s(z, z$) + s(z$, z) + s(z$, z$)) = 1

und &v1, v2' = &v2, v1' = % 12i

(s(z, z)% s(z, z$) + s(z$, z)% s(z$, z$)) = 0 .

Weiter gilt:

Fv1 =102

( <Fz + <Fz$) =102

(" z + " z$)

=12

(" + ") · 102

(z + z$) +i

2("% ") · 1

i0

2(z % z$)

= (Re ") v1 % (Im ") v2

und Fv2 =1

i0

2( <Fz % <Fz$) =

1i0

2(" z % " z$)

=12i

("% ") · 102

(z + z$) +12

(" + ") · 1i0

2(z % z$)

= (Im ") v1 + (Re ") v2 .

Damit lauten die ersten beiden Spalten der darstellenden Matrix A von F bezuglicheiner Basis (v1, v2, . . . , vn) von V :

A =

.

//////0

Re " Im " 6 6 · · · 6% Im " Re " 6 6 · · · 6

0 0 6 6 · · · 6...

......

......

0 0 6 6 · · · 6

1

2222223.

Der weitere Beweis verlauft wie bei Satz 28.9. Wir betrachten hierzu U := <v1, v2>).Es gilt dann fur beliebiges u " U :

&v1, Fu' = s(v1, <Fu) = s( <F *v1, u)

=102

s( <F *z + <F *z$ , u) =102

[s(" z , u) + s(" z$ , u)]

=102

>"02

s(v1 + i v2 , u) +"02

s(v1 % i v2 , u)?

=12

" [s(v1, u) + i s(v2, u)] +12

" [s(v1, u)% i s(v2, u)] = 0 .

und entsprechend: &v2, Fu' = 0 . Also gilt: F (U) 5 U . Damit ist G := F |U einnormaler Endomorphismus in U , auf den die Induktionsvoraussetzung angewandtwerden kann.


”b)- a)“: Nach Satz 28.5 hat F * bezuglich der Orthonormalbasis von V die darstellende MatrixAH = At . (Dadurch ist dann F * eindeutig festgelegt wie im Beweis zum Spektral-satz 28.9.) Wegen A ·At = At ·A ergibt sich die Normalitat von F ; es gilt namlich:

A · At =

.

/////0

"12. . .

"k2

Ak+1 ·Ak+1t

. . .Am ·Am

t

1

222223mit A# · A#

t =!

##2+$#

2 00 ##

2+$#2

"

.

!

28.14 Definition

Es sei V " VRIK euklidisch oder unitar. Ein Endomorphismus F : V $ V heißt selbstad-jungiert, wenn fur alle v, w " V gilt:

&Fv , w' = &v , Fw' ,

d. h. wenn F mit seiner adjungierten Abbildung F * ubereinstimmt.

28.15 Bemerkung

Ein selbstadjungierter Endomorphismus ist stets normal. Jeder selbstadjungierte Endomorphis-mus F " EndIK(V ) besitzt nur reelle Eigenwerte. Also existiert im endlich–dimensionalen Falleine Orthonormalbasis von V , die aus lauter Eigenvektoren von F besteht. Bezuglich dieserBasis ist die darstellende Matrix von F dann eine reelle Diagonalmatrix.

Beweis:

Sei V " VRC unitar, F " EndC(V ) selbstadjungiert und " " C Eigenwert von F mit Ei-genvektor x " V \ {0} ; dann gilt:

" &x, x' = &" x , x' = &Fx, x' = &x, Fx' = &x , " x' = " &x, x' ,

wegen !x!2 .= 0 also: " = " - " " IR .Ist V " VRIR euklidisch, so sei W die komplexe unitare Erweiterung von V und <F : W $ Wdie Fortsetzung von F " EndIR(V ) auf W " VRC . Mit F ist auch <F selbstadjungiert, weil gilt:

s( <F (x + i y) , x$ + i y$) = s(Fx + i Fy , x$ + i y$)

= (&Fx, x$'+ &Fy, y$') + i (&Fy, x$' % &Fx, y$')= (&x, Fx$'+ &y, Fy$') + i (&y, Fx$' % &x, Fy$')

= s(x + i y , Fx$ + i Fy$) = s(x + i y , <F (x$ + i y$)) .

Aufgrund der ersten Uberlegung besitzt <F nur reelle Eigenwerte. Sei also " " IR Eigenwert undz " W zugehoriger Eigenvektor von <F , d. h. <Fz = " z mit z = x+ i y . Wegen <Fz = Fx+ i Fyund " · z = " x + i" y folgt dann: Fx = " x und Fy = " y . Also ist " auch einEigenwert von F . (Umgekehrt ist jeder Eigenwert von F sofort Eigenwert von <F .) !

Diese Erkenntnisse wenden wir nun auf spezielle Endomorphismen, d. h. auch auf bestimmteMatrizen an.


§ 29 Orthogonale und unitare Endomorphismen

29.1 Definition

Es sei V " VRIK euklidisch bzw. unitar; ein Endomorphismus F : V $ V heißt orthogonalbzw. unitar, wenn fur alle v, w " V gilt:

&Fv , Fw' = &v, w' .

29.2 Satz

Es sei V " VRIK euklidisch bzw. unitar und F : V $ V ein Endomorphismus. Dann sindfolgende Aussagen paarweise aquivalent:

a) F ist orthogonal bzw. unitar.

b) Aus !v! = 1 folgt stets: !Fv! = 1 .

c) Fur alle v " V gilt: !v! = !Fv! .

d) Ist (v1, v2, . . . , vn) ein Orthonormalsystem, so bildet (Fv1 , Fv2 , . . . , Fvn) ebenfalls einOrthonormalsystem in V .

Beweis:

”a) - b)“: Ist &v, v' = 1 , so folgt direkt: &Fv , Fv' = 1 .

”b) - c)“: Ohne Beschrankung der Allgemeinheit sei v .= 0 ; mit w := 1(v( v ist dann

!w! = 1 und v = !v! · w , also gilt: !Fv! = !v! · !Fw! = !v! .

§ 29. ORTHOGONALE UND UNITARE ENDOMORPHISMEN 151

”c) - d)“: Nach Bemerkung 26.8 folgt wegen &vj , vk' = 0 fur alle j .= k :

Re (4 &Fvj , Fvk') = !Fvj + Fvk!2 % !Fvj % Fvk!2

= !vj + vk!2 % !vj % vk!2 = 0

und Im (4 &Fvj , Fvk') = !Fvj + i Fvk!2 % !Fvj % i Fvk!2

= !vj + i vk!2 % !vj % i vk!2 = 0 .

”d) - a)“: Ohne Einschrankung seien v .= 0 und w .= 0 ; wir mussen zeigen:&Fv, Fw' != &v, w' .

1. Fall: Ist w = c · v und e := 1(v( v , dann gilt:

&v, w' = &!v! e , c !v! e' = !v!2 c &e, e' = !v!2 c

und &Fv, Fw' = !v!2 c &Fe, Fe' .

Nach Voraussetzung ist mit (e) auch (Fe) ein Orthonormalsystem in V , d. h. esgilt: !Fe! = 1 .2. Fall: Sind v, w linear unabhangig, so existiert nach dem Satz von Schmidt–Gram eine Orthonormalbasis (v1, v2) von dem von v und w aufgespannten Un-terraum U . Ist dann v = x1 v1 + x2 v2 und w = x1

$ v1 + x2$ v2 , so folgt:

&Fv, Fw' = &x1 Fv1 + x2 Fv2 , x1$ Fv1 + x2

$ Fv2'= x1 x1

$ &Fv1, Fv1'+ x1 x2$ &Fv1, Fv2'+

+ x2 x1$ &Fv2, Fv1'+ x2 x2

$ &Fv2, Fv2'= x1 x1

$ + x2 x2$ = &v, w' ,

da mit (v1, v2) auch (Fv1, Fv2) ein Orthonormalsystem bildet.

!

29.3 Satz

Es sei V " VRIK euklidisch bzw. unitar und F : V $ V linear; dann gilt:

a) Ist F orthogonal, so ist <F unitar.

b) Ist F orthogonal bzw. unitar, so ist F injektiv.

c) Ist F ein Automorphismus, so ist F genau dann orthogonal bzw. unitar, wenn F"1 = F *

gilt.

Beweis:

zu a): folgt direkt aus Satz 29.2d). #zu b): ist klar nach Definition 29.1. #


zu c): Es seien v$, w$ " V ; dann existieren v, w " V mit v$ = Fv und w$ = Fw . Darausfolgt:

&F"1v$ , F"1w$' = &F"1Fv , F"1Fw' = &v, w' .

Ist F orthogonal bzw. unitar, so ergibt sich weiter:

&F"1v$ , F"1w$' = &v, w' = &Fv, Fw' = &v$, w$' .

Also ist mit F auch F"1 orthogonal bzw. unitar. Ferner gilt fur beliebige v " V undw$ " V mit w$ = Fw :

&Fv,w$' = &Fv, Fw' = &v, w' = &v , F"1w$' .

Damit ist F * = F"1 .Ist umgekehrt F ein Automorphismus mit F"1 = F * , dann folgt fur alle v, w " V :

&Fv, Fw' = &v, F *Fw' = &v, w' ,

d. h. F ist orthogonal bzw. unitar.

!

Ist nun dimIK V = n mit einer Basis B = (v1, v2, . . . , vn) von V und F ein Automorphismus aufV sowie A = ΦB

B(F ) die darstellende Matrix von F bezuglich B , dann gilt: A"1 = ΦBB(F"1) .

Ist daruber hinaus B = (v1, v2, . . . , vn) eine Orthonormalbasis von V , so gilt: AH = ΦBB(F *) .

Also ist F genau dann orthogonal bzw. unitar, wenn A"1 = At bzw. A"1 = AH gilt.

Das fuhrt zu:

29.4 Definition

Eine quadratische Matrix A " Mat(n, n; C) heißt unitar, wenn A regular ist mit A"1 = AH .Eine quadratische Matrix A " Mat(n, n; IR) heißt orthogonal, wenn A regular ist mit A"1 = At .

29.5 Bemerkung

Es sei V " VRIK euklidisch bzw. unitar mit dimIK V = n. Nach Satz 29.3c) ist ein Endomorphis-mus F : V $ V genau dann orthogonal bzw. unitar, wenn eine Orthonormalbasis von V derartexistiert, daß die darstellende Matrix von F bezuglich dieser Basis orthogonal bzw. unitar ist.(Denn: Nach Korollar 14.7 ist ein injektiver Endomorphismus auf einem endlich–dimensionalenVektorraum bereits ein Automorphismus.)

29.6 Lemma

Fur eine Matrix A = (#ij) " Mat(n, n; IK) sind folgende Aussagen paarweise aquivalent:

a) A ist orthogonal bzw. unitar.

§ 29. ORTHOGONALE UND UNITARE ENDOMORPHISMEN 153

b) Die Zeilen von A bilden ein Orthonormalsystem im IKn , d. h. es gilt:

&Ai, Aj' =n'

k=1

#ik #jk = (ij fur alle 1 ( i, j ( n .

c) Die Spalten von A bilden ein Orthonormalsystem im IKn , d. h. es gilt:

&Ai, Aj' =n'

k=1

#ki #kj = (ij fur alle 1 ( i, j ( n .


Es gilt fur jedes i, j = 1, 2, . . . , n :

(#j1,#j2, . . . ,#jn)t = (AH)j , also: &Ai, Aj' = Ai · (AH)j

und (#1j ,#2j , . . . ,#nj) = (AH)j , also: &Ai, Aj' = (AH)j · Ai .

Gemaß Bemerkung 6.7(i) ist damit die Aussage b) aquivalent zu A · AH = En und Aussage c)aquivalent zu AH · A = En . Also ist nach Definition 29.4 A orthogonal bzw. unitar. !

Wir wenden dieses Ergebnis auf den Spektralsatz 28.9 an:

29.7 Satz (Spektralzerlegung fur normale Matrizen)

Fur eine komplexe Matrix A " Mat(n, n; C) sind aquivalent:

a) A ist normal, d. h. es gilt: A · AH = AH · A .

b) Es existieren eine Orthonormalbasis (v1, v2, . . . , vn) des Cn und Eigenwerte "1, "2, . . .. . . , "n " C von A , so daß gilt:

A =n'

i=1

"i vi · viH .

Beweis:

Es sei K = (e1t, e2

t, . . . , ent) die kanonische Orthonormalbasis des Cn , und F der durch A

induzierte Endomorphismus bezuglich K . Dann existiert zur normalen Matrix A gemaß Satz 28.9eine Orthonormalbasis B = (v1, v2, . . . , vn) des Cn derart, daß die darstellende Matrix D von Fbezuglich B Diagonalgestalt hat. Laut §17 (siehe Lineare Algebra I) gilt hierbei:

D = S"1 · A · S mit S = Rt und vi =n'

j=1

rij ejt fur R = (rij) .

(In der i-ten Spalte von S stehen die Koordinaten von vi bezuglich K .) Daraus folgt nun:

A = S · D · S"1 ,


wobei die Diagonaleintrage von D genau die Eigenwerte "i von F sind. Da die Spalten von Seine Orthonormalbasis des Cn bilden, ist S nach Lemma 29.6 unitar, d. h.: S"1 = SH . Schreibenwir dann D in der Form D =

n)i=1

"i Eii mit den kanonischen Matrizen Eii " Mat(n, n; C) aus

dem Beweis zu Satz 6.5, so folgt die behauptete Darstellung mit dyadischen Produkten:

A =n'

i=1

"i (S · Eii · SH) =@ n'

i=1

"i [(v1, v2, . . . , vn) · Eii]A·

.

///0

v1H

v2H

...vn

H

1

2223

= [("1 v1,0,0, . . . ,0) + (0, "2 v2,0, . . . ,0) + (0,0, . . . ,0, "n vn)] ·

.

///0

v1H

v2H

...vn

H

1

2223

= "1 v1 · v1H + "2 v2 · v2

H + . . . + "n vn · vnH =

n'

i=1

"i vi · viH .

Ist umgekehrt A =n)

i=1"i vi · vi

H , dann folgt: AH =n)

j=1"j vj · vj

H , nach Lemma 29.6 also:

A · AH =n'

i,j=1

"i "j vi · viH · vj · vj

H =n'

i=1

|"i|2 vi · viH = AH · A .

!

Fur den Fall IK = IR erhalten wir analog:

29.8 Satz (Spektralzerlegung fur symmetrische Matrizen)

Fur eine reelle Matrix A " Mat(n, n; IR) sind aquivalent:

a) A ist symmetrisch, d. h. es gilt: A = At .

b) Es existieren eine Orthonormalbasis (v1, v2, . . . , vn) des IRn und Eigenwerte "1, "2, . . .. . . , "n " IR von A mit

A =n'

i=1

"i vi · vit .

Beweis:

”a) - b)“: Nach Satz 20.7(iv) besitzt A als symmetrische Matrix nur reelle Eigenwerte "i .Dann liefert der Spektralsatz 28.13 mit Lemma 29.6: A = S · D · St , wobeidie Spalten von S die kanonischen Koordinaten der Eigenvektoren vi zu denEigenwerten "i von A sind (entsprechend zum Beweis von Satz 29.7).

”b) - a)“: Aus der Spektraldarstellung folgt (wie oben) sofort: At = A . #!

§ 30. DREHUNGEN UND SPIEGELUNGEN 155

29.9 Bemerkung

Man sagt auch, daß normale Matrizen unitar–diagonalahnlich und symmetrische Matrizenorthogonal–diagonalahnlich seien.Speziell sind unitare oder orthogonale Vektorraum–Automorphismen normal; jeder Eigenwerteines solchen Endomorphismus hat den Absolutbetrag 1 . (Ist namlich Fv = " v , so folgt nachSatz 29.2: !v! = !Fv! = |"| !v! , also: |"| = 1 .)

29.10 Definition und Satz

Die MengenO(n) := {A " GL(n; IR) | A"1 = At } ,

U(n) := {A " GL(n; C) | A"1 = AH }

und SO(n) := {A " O(n) | detA = +1 }

bilden jeweils mit der Matrixmultiplikation als Verknupfung eine Gruppe, namlich die orthogo-nale Gruppe, die unitare Gruppe bzw. die eigentlich (oder spezielle) orthogonale Gruppe.

Wahrend die unitaren Matrizen vollstandig beschrieben werden konnen, ist dies bisher bei denorthogonalen Matrizen nicht der Fall.

§ 30 Drehungen und Spiegelungen

Ist A " Mat(n, n; IR) eine orthogonale Matrix, d. h. gilt: A " O(n) , so existiert nach Spek-tralsatz 28.13 eine Orthonormalbasis B des IRn derart, daß die darstellende Matrix von ΨB

B(A)bezuglich dieser Basis die Form

D =

.

//////0

"1 "2 0. . ."k Ak+1

Ak+2

0 . . .Am

1

2222223

mit den reellen Eigenwerten "1, "2, . . . ,"k und den ”Zweier–Kastchen“ A# =@

## $#

%$# ##

Ahat.

Wegen A " O(n) ist "# " {%1, 1} fur alle 1 ( ' ( k und ##2 + $#

2 = |"# |2 = 1 furalle k+1 ( ' ( m . Also existiert zu jedem ' " {k+1, k+2, . . . ,m} genau ein )# " IR mit0 < )# < 2% , )# .= % sowie ## = cos )# und $# = sin )# .Ist also F : IRn $ IRn ein orthogonaler Automorphismus, so existiert eine Orthonormalbasisderart, daß fur die darstellende Matrix von F bezuglich dieser Basis gilt:

D =

.

//////0

1 . . . 01%1 . . .%1

Ak+10 . . . Am

1

2222223


mit den unteren Diagonalblocken A# =!

cos )# sin )#

% sin )# cos )#

"

. Wir erhalten daraus sofort:

30.1 Bemerkung

Ein Matrix A " O(n) ist genau dann eigentlich orthogonal, wenn %1 als Eigenwert von A einegeradzahlige Vielfachheit besitzt. Die durch A " SO(n) induzierten Endomorphismen heißenauch Drehungen.

Es sei V " VRIR euklidisch mit dimIR V = n und W ein (n%1)-dimensionaler Untervektorraum.Wir wahlen eine Orthonormalbasis (v1, v2, . . . , vn"1) von W aus; dann existiert ein vn " V mitvn " <v1, v2, . . . , vn"1>) und !vn! = 1 . Wir definieren eine Abbildung S = SW : V $ Vdurch

S(v) := v % 2 &v, vn' vn = v % 2 P<vn>(v) .

Damit ist S eine IR–lineare Abbildung mit

&Sv, Sw' = &v, w' % 2 &v, vn' &vn, w' % 2 &v, vn' &w, vn'+ 4 &v, vn' &w, vn' &vn, vn' = &v, w' .

Also ist S ein orthogonaler Endomorphismus mit

S(vn) = %vn und S(w) = w fur alle w " W .

Schreiben wir v " V in der Form v = w + # vn = w + &v, vn' vn mit w " W , so gilt:

S(v) = S(w + # vn) = S(w) + &v, vn'S(vn) = w + &v, vn' (%vn) = w % # vn .

Ein solches S heißt Spiegelung an dem (n% 1)-dimensionalen Unterraum W . Fur die darstellen-de Matrix A = ΦB

B(S) von S bezuglich B = (v1, v2, . . . , vn) gilt dann: detA = %1 . Wir sagendeshalb auch: detS := detΦB

B(S) = %1 .

30.2 Satz

Ist V " VRIR euklidisch mit dimIR V = n und F : V $ V ein orthogonaler Endomorphismusmit det F = detΦK

K(F ) = %1, so existiert eine Drehung D und eine Spiegelung S mit F = S*D .

Beweis:

Sei W ein (n%1)-dimensionaler Unterraum von V mit einer Orthonormalbasis (v1, v2, . . . , vn"1)von W und B = (v1, v2, . . . , vn"1, vn) als Orthonormalbasis von V sowie S definiert wie in Be-merkung 30.1. Dann ist D := S"1 * F ein orthogonaler Endomorphismus mit

det D = detΦKK(D) = detS"1 · detF = detS · detF = (%1) · (%1) = 1 .

!


30.3 Beispiele

Es sei V " VRIR euklidisch und F : V $ V ein orthogonaler Endomorphismus.

a) Ist dimIR V = 2 , so gilt bezuglich einer geeigneten Orthonormalbasis von V fur diedarstellende Matrix von F :

D0 =!

1 00 1

"

, D" =!%1 0

0 %1

"

, D% =!

cos ) sin )% sin ) cos )

"

oder S =!

1 00 %1

"

mit ) " ] 0 ; 2% [ und ) .= % . Dabei beschreibt D% die Drehung um 0 mit Winkel ) imUhrzeigersinn. (Setzen wir # := 2% % ) , d. h. ) = 2% % # , so folgt:

D% =!

cos(2%%#) sin(2%%#)% sin(2%%#) cos(2%%#)

"

=!

cos # % sin #sin# cos #

"

=: D& .

Also beschreibt D& die Drehung um 0 mit Winkel # gegen den Uhrzeigersinn. Damit istdie Bezeichnung ”Drehung mit Winkel #“ konsistent zu Beispiel 20.12.)

b) Ist dimIR V = 3 , dann gilt fur die darstellende Matrix von F bezuglich einer geeignetenOrthonormalbasis von V :

D% =

.

/01 0 00 cos ) sin )0 % sin ) cos )

1

23 oder D% =

.

/0%1 0 0

0 cos ) sin )0 % sin ) cos )

1

23 mit 0 ( ) < 2% .

Ist dann B = (v1, v2, v3) eine solche Orthonormalbasis von V mit ΦBB(F ) = D% , so be-

trachten wir als Untervektorraume von V jeweils

die Drehachse Da := <v1> und die Drehebene Da) := <v2, v3> von F .

Da v1 zum Eigenwert 1 gehort, bleibt Da unter F fest; und Da) wird durch F auf

sich selbst abgebildet. Die Einschrankung F |Da$ stellt eine Drehung des 2-dimensionalen

Unterraumes Da) dar. Der Drehwinkel ) ist nicht eindeutig festgelegt; aus der Bezie-

hung sp(D%) = 1 + 2 cos ) folgt:

cos ) =12( sp(D%)% 1) .

Ist nun A = (#ij) " SO(3) die darstellende Matrix der Drehung F bezuglich irgendeinerBasis von V , so gilt wegen der Invarianz der Spur bei ahnlichen Matrizen:

sp(A) = #11 + #22 + #33 = 1 + 2 cos ) ,- cos ) =12

(#11 + #22 + #33 % 1) .

30.4 Satz

Sei A " SO(3) ; dann gibt es Werte #,$, ) " [ 0 ; 2% [ mit

A =

.

/0cos ) sin ) 0

% sin ) cos ) 00 0 1

1

23 ·

.

/01 0 00 cos $ sin$0 % sin$ cos $

1

23 ·

.

/0cos # sin# 0

% sin# cos # 00 0 1

1

23 =: M1,% ·M2,' ·M1,& .



Es sei A = (#ij) . Wir wollen zeigen, daß !, *, $ " IR existieren mit !, * " ]%2% ; 0 ] und0 ( $ < 2% sowie M1,( · A · M1,) = M2,' . Wegen (M1,()"1 = M1,"( und (M1,))"1 = M1,")

erhalten wir dann mit ) := %! und # := %* die Behauptung. Dazu sei

B = ($ij) := M1,( · A · M1,)

=

.

/0cos ! sin! 0

% sin ! cos ! 00 0 1

1

23 ·

.

/0#11 #12 #13

#21 #22 #23

#31 #32 #33

1

23 ·

.

/0cos * sin* 0

% sin* cos * 00 0 1

1

23

=:

.

/00

A( 00 0 1

1

23 ·

.

/0#13

C #23

#31 #32 #33

1

23 ·

.

/00

A) 00 0 1

1

23

=

.

/0A( · C A( ·

!#13

#23

"

#31 #32 #33

1

23 ·

.

/00

A) 00 0 1

1

23

=

.

/0A( · C · A) A( ·

!#13

#23

"

(#31, #32) · A) #33

1

23 .

1. Schritt: Es gilt: $33 = #33 ; da A orthogonal ist, ergibt sich: |#33| ( 1 . Wir wahlenein 0 ( $ < 2% mit cos $ = #33 .

2. Schritt: Es gilt: $13 = (cos ! , sin!) ·!

#13

#23

"

= #13 cos !+#23 sin! ; wir wahlen daher

ein %2% < ! ( 0 mit #13 cos ! + #23 sin! = 0 .

3. Schritt: Wir mussen ein %2% < * ( 0 mit $11 = 1 finden, d. h. mit

(cos ! , sin!) ·!

#11 #12

#21 #22

"

·!

cos *

% sin*

"

= 1 .

Hierfur wahlen wir * " ]%2% ; 0 ] mit

(x1, x2) := (cos ! , sin!) ·!

#11 #12

#21 #22

"

= (cos * , % sin*) .

Diese Wahl von * ist moglich wegen

x12 + x2

2 = (#11 cos ! + #21 sin! + #31 · 0)2 ++ (#12 cos ! + #22 sin! + #32 · 0)2 ++ ( #13 cos ! + #23 sin! + #33 · 0* +, -

= 0

)2 = 1 ,

da mit A und M1,( auch M1,( · A orthogonal ist. Dann gilt wegen $11 = 1und B " O(3) sofort: $12 = $21 = $31 = 0 . Mit det A = 1 muß schließlichauch gelten:

det!

$22 $23

$32 $33

"

= 1 , also:!

$22 $23

$32 $33

"

=!

cos $ ± sin$7 sin$ cos $

"

.

!


30.5 Definition

Ist A " SO(3) , so heißen die Großen #,$, ) " [ 0 ; 2% [ aus Satz 30.4 die Euler’schen45 Winkelder zu A gehorigen Drehung.

30.6 Beispiel

Haben wir als darstellende Matrix

A =

.

//0

%14

02 %1

2

03 1

4

02

14

06 %1

2 %14

06

12

02 0 1

2

02

1

223 ,

so rechnet man direkt nach, daß A " SO(3) ist. Gemaß dem Beweis zu Satz 30.4 erhalten wirzunachst:

cos $ = 12

02 , d. h.: $ = "

4 8 $ = 74% und

14

02 cos !% 1

4

06 sin ! = 0 ,- tan! = 1&

3, d. h.: ! = %5

6% 8 ! = %116 % .

Daraus ergibt sich weiter im 3. Schritt:

(cos ! , sin!) ·!%1

4

02 %1

2

03

14

06 %1

2

"

= (cos * , % sin*) ,

d. h.:

(% 12

03 , %1

2) ·!%1

4

02 %1

2

03

14

06 %1

2

"

= (0 , 1) = (cos * , % sin*) fur ! = %56%

oder (12

03 , 1

2) ·!%1

4

02 %1

2

03

14

06 %1

2

"

= (0 , %1) = (cos * , % sin*) fur ! = %116 % ,

also:* = %"

2 8 * = %32% .

Somit gilt fur die Euler’schen Winkel zu A :

# = %* = "2 8 # = 3

2% , $ = "4 8 $ = 7

4% , ) = %! = 56% 8 ) = 11

6 % .

30.7 Bemerkung

Die Matrizen D% aus Beispiel 30.3 bzw. M1,( oder M2,' aus Satz 30.4 stellen Drehungen um denWinkel ),! bzw. $ im Uhrzeigersinn dar, was (vgl. Beispiel 30.3a) Drehungen um 2%%) , 2%%!bzw. 2% % $ gegen den Uhrzeigersinn entspricht. Drehungen gegen den Uhrzeigersinn um denWinkel ),! bzw. $ entsprechen also die Matrizen

D% =!

cos ) % sin )sin ) cos )

"

, M1,( =

.

/0cos ! % sin! 0sin! cos ! 0

0 0 1

1

23

bzw. M2,' =

.

/01 0 00 cos $ % sin$0 sin$ cos $

1

23 .

45Leonhard Euler, schweizerischer Mathematiker und Physiker (!15.04.1707, †18.09.1783)


Damit gilt Satz 30.4 auch in der Form:

A = M1,% · M2,' · M1,& .

Geometrisch lassen sich die Euler’schen Winkel im IR3 wie folgt interpretieren:

.......

................

....................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................

............................................

....................................................................................................................................................

.........................

.................

...............................................................................................................................................................................................................................................................................................................

....................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................

........................

.......................................................................................................................................................................................................

...................................................................

.....................................................................................

..............................

.................................

...................................................................

.....................................................................................................................................

.................................................

............................................................................................................................................

..........................................

.......

.......

.....

.....................

.............................................................................................!..................................................................................................................................................!

!!!"

#

$

%%%%%%&'''''''''(

))

))

)))

*

...................................................................................................................................................................................................................................................

................................................................................

.............................

..........................

.....................

.................

# )

$

#$

)

$

e1t

e2t

e3t

A·e1t

A·e2t

A·e3t

Man spricht dabei auch vom Prazessionswinkel #, vom Nutationswinkel $ und vom Drehungs-winkel ) (oder %) ).

§ 31 Hauptachsentransformation

Unter einem quadratischen Polynom uber IK in den Unbestimmten t1, t2, . . . , tn verstehen wireinen Ausdruck der Form

P (t1, t2, . . . , tn) :='

1#i#j#n

aij ti tj +'

1#i#n

a0i ti + a00

mit Koeffizienten aij " IK fur alle 0 ( i ( j ( n .

31.1 Definition

Eine Teilmenge Q 5 IKn heißt eine Quadrik (oder Hyperflache zweiter Ordnung), wenn es einquadratisches Polynom P in den Unbestimmten t1, t2, . . . , tn " IK gibt mit

Q = {(x1, x2, . . . , xn) " IKn | P (x1, x2, . . . , xn) = 0} .

§ 31. HAUPTACHSENTRANSFORMATION 161

31.2 Beispiele

a) Ist n = 2, so stellt Q = {(x1, x2) " IR2 | x12+x2

2%25 = 0} eine Quadrik im IR2 , namlichdie Kreislinie um (0, 0) mit Radius 5 dar. Die Koeffizienten des zugehorigen quadratischenPolynoms sind hier: a00 = %25 , a01 = a02 = 0 , a11 = a22 = 1 und a12 = 0 .

b) Ebenso ist fur n = 2 die Menge

Q := {(x1, x2) " IR2 | 41 x12 % 24 x1 x2 + 34 x2

2 % 25 = 0}

eine Quadrik im IR2 . Welche geometrische Gestalt hat Q nun?Wir schreiben dazu Q in der Form:

(x1, x2) · A ·!

x1

x2

"

= 25 mit A :=!

41 %12%12 34

"

.

Laßt sich etwa durch eine Drehung die geometrische Gestalt von Q besser bestimmen?Setzen wir weiter:

!x1

x2

"

=!

cos # % sin#sin# cos #

"

·!

y1

y2

"

=: T& ·!

y1

y2

"

mit # " IR , so ergibt sich wegen T&"1 = T&

t die Darstellung:

(x1, x2) · A ·!

x1

x2

"

= (y1, y2) · T&"1 · A · T& ·

!y1

y2

"

.

Kann man also A durch T& auf Diagonalgestalt transformieren?Wegen det (" E2 % A) = (" % 50) (" % 25) besitzt A die einfachen Eigenwerte "1 = 25und "2 = 50 . Es existiert daher ein # " IR mit

T&"1 · A · T& = 25

!1 00 2

"

.

Somit ist!

34

"

ein Eigenvektor von A zu "1 und!%4

3

"

Eigenvektor zu "2 . Also bil-

det5!

3545

"

,

!%4

535

"6eine Orthonormalbasis des IR2 aus Eigenvektoren, und wir erhalten

tatsachlich als Drehmatrix:

T& =15

!3 %44 3

"

.

Folglich stellt Q die um den Winkel # mit cos # = 35 und sin # = 4

5 gedrehte Quadrik Q$

dar fur

Q$ =$(y1, y2) " IR2

%%% (y1, y2) ·!

1 00 2

"

·!

y1

y2

"

= 1&

= {(y1, y2) " IR2 | y12 + 2 y2

2 = 1} .

Man erkennt: Q ist eine um # gedrehte Ellipse.


31.3 Bemerkung

Wir uberlegen uns, wie man die Gleichung einer Quadrik Q allgemein durch Matrizen ausdruckenkann. Dazu setzen wir fur P (t1, t2, . . . , tn) =

)1#i#j#n

aij ti tj +)

1#i#na0i ti + a00 fest:

#ii := aii fur alle 0 ( i ( n sowie #ij = #ji :=12

aij fur alle 0 ( i < j ( n

und bilden aus diesen Koeffizienten die quadratische Matrix

A$ :=

.

////0

#00 #01 · · · #0n

#10 #11 · · · #1n...

......

#n0 #n1 · · · #nn

1

22223=:

.

////0

#00 #01 · · · #0n

#10... A

#n0

1

22223" Mat(n+1 , n+1 ; IK)

sowie den Vektorx$ := (1, x1, x2, . . . , xn)t " IKn+1 .

Dann ist A$ symmetrisch, und es gilt fur x := (x1, x2, . . . , xn) :

P (x1, x2, . . . , xn) = (x$)t · A$ · x$ , also: Q = {(x1, x2, . . . , xn) " IKn | (x$)t · A$ · x$ = 0} .

Dabei heißt A$ die erweiterte Matrix zu A und x$ der erweiterte Spaltenvektor zu x.Unser Ziel ist es nun, durch eine orthogonale Transformation die Matrix A auf Diagonalgestaltzu bringen und anschließend durch eine (noch genau zu definierende) ”Verschiebung“ moglichstviele Eintrage der ersten Zeile bzw. Spalte zu Null zu machen. Da A symmetrisch ist, existiertim Fall IK = IR ein S " O(n) mit

St · A · S =

.

/0"1 0"2 . . .0 "n

1

23 =: D ,

wobei "1, "2, . . . ,"n " IR die Eigenwerte von A sind. Durch eventuelle Vertauschung der Spaltenvon S (und entsprechend der Zeilen von St ) konnen wir erreichen, daß gilt:

"i > 0 fur alle i = 1, 2, . . . , k ,

"i < 0 fur alle i = k+1, k+2, . . . ,m

und "i = 0 fur alle i = m+1, m+2, . . . , n .

Wir setzen dann:

S$ :=

.

////0

1 0 · · · 00... S0

1

22223und erhalten: B$ := (S$)t · A$ · S$ =

.

////0

#00 $01 · · · $0n

$10... D

$n0

1

22223.

Wie kann man etwa feststellen, ob A nur positive Eigenwerte besitzt? Als Folgerung aus Ubungs-aufgabe 28–6 ist dies aquivalent zur positiven Definitheit von A . Gibt es dazu also ein ”handli-cheres“ Kriterium als x · A · xH > 0 4x '=0 aus Definition 26.9?

Vorher machen wir uns klar, in welcher Weise sich fur ein S " GL(n; IK) die Eigenwerte voneiner symmetrischen bzw. Hermite’schen Matrix A " Mat(n, n; IK) zu denen von St · A · Sverhalten (vgl. Satz 26.6). Wir beweisen hierzu:


31.4 Satz (Sylvester’scher46 Tragheitssatz)

Vorgegeben seien V " VRIK mit dimIK V = n , eine symmetrische Bilinearform s bzw. eineHermite’sche Form s auf V , zwei Basen Bi von V , die darstellenden Matrizen Ai := ΦBi(s)von s sowie ki " IN als Anzahl der positiven Eigenwerte von Ai und li " IN als Anzahl dernegativen Eigenwerte von Ai , jeweils fur i = 1, 2 . Dann gilt:

k1 = k2 , l1 = l2 und rg(A1) = rg(A2) .

Beweis:

In §28 und §29 haben wir gezeigt, daß es eine orthogonale bzw. unitare Matrix Si derart gibt,daß Si

"1 ·Ai · Si =: Di eine Diagonalmatrix ist, welche die gleichen Eigenwerte wie Ai besitzt.Sei nun B$i die Basis von V mit ΦB!i(s) = Di . Wir definieren fur i = 1, 2 jeweils:

V +i := {<v1, v2, . . . , vr> | v$ " B$i 9 s(v$, v$) > 0 41#$#r }

und V "i := {<w1, w2, . . . , wt> | w* " B$i 9 s(w* , w* ) < 0 41#*#t } .

Dann ist in beiden Fallen

V0 := {v " V | s(v, w) = 0 fur alle w " V }

derjenige Unterraum, welcher von den restlichen Basisvektoren aufgespannt wird. (Beachte hier-zu: ΦB!i(s) = (s(vj , vk)) = Di .) Daraus folgt also: rg(A1) = rg(A2) = n % dimV0 . Weitergilt:

V = V +1 1/ V "

1 1/ V0 und V = V +2 1/ V "

2 1/ V0 .

Wegen ki = dimV +i und li = dimV "

i fur beide i = 1, 2 folgt demnach: k1 + l1 = k2 + l2 .Es bleibt also noch zu zeigen: k1 = k2 . Nun ist s(v, v) > 0 fur alle v " V +

2 \{0} und s(v, v) ( 0fur alle v " V "

1 1/ V0 ; somit gilt: V +2 3 (V "

1 1/ V0) = {0} . Hieraus folgt: V +2 5 V +

1 und damit:k2 ( k1 . Analog ergibt sich: k1 ( k2 . Also ist insgesamt k1 = k2 . Und dies bedeutet schließlichauch: l1 = l2 . !

31.5 Folgerung

Ist A " Mat(n, n; IK) symmetrisch bzw. Hermite’sch und S " GL(n; IK) , so haben A undSt · A · S den gleichen Rang sowie die gleichen Anzahlen positiver und negativer Eigenwerte.

Beweis:

Direkte Anwendung von Satz 26.6 und Satz 31.4. # !

Nun stellen wir eine praktische Bedingung fur positive Definitheit bereit:

46James Joseph Sylvester, englischer Mathematiker und Jurist (!03.09.1814, †15.03.1897)


31.6 Satz (Kriterium von Hurwitz47)

Es sei A " Mat(n, n; IR) symmetrisch mit A = (#ij)1#i,j#n und Ak := (#ij)1#i,j#k furk = 1, 2, . . . , n die linke obere (k # k)-Teilmatrix von A . Dann sind aquivalent:

a) A ist positiv definit.

b) Es gilt: detAk > 0 fur jedes 1 ( k ( n .

Beweis:

”a)-b)“: Wir zeigen zuerst: Ist B " Mat(k, k; IR) fur alle k " {1, 2, . . . , n} positiv definit, sogilt: det B > 0 .Sei dazu S " O(k) (gemaß Satz 29.8) mit

St · B · S =

.

/0µ1 0µ2 . . .0 µk

1

23 ,

wobei µ1, µ2, . . . , µk > 0 die Eigenwerte von B sind. Dann gilt nach dem Determi-nanten–Multiplikationssatz: detB = µ1 · µ2 · . . . · µk > 0 .Sei jetzt Vk := {(x1, x2, . . . , xn) " IRn | xk+1 = xk+2 = . . . = xn = 0} fur jedes1 ( k ( n ; dann gilt wegen der positiven Definitheit von A fur alle vk " Vk \ {0} :

vk · A · vkt = (x1, x2, . . . , xk) · Ak · (x1, x2, . . . , xk)t > 0 .

Also ist Ak positiv definit, und damit folgt aus der Voruberlegung: det Ak > 0 furjedes 1 ( k ( n .

”b)- a)“: Wir zeigen die Behauptung durch vollstandige Induktion uber n .Der Induktionsanfang n = 1 ist trivial. #Sei die symmetrische Matrix A =: An " Mat(n, n; IR) mit det Ak > 0 fur alle1 ( k ( n gegeben. Nach Induktionsvoraussetzung ist An"1 " Mat(n%1, n%1; IR)positiv definit; also existiert ein Sn"1 " O(n%1) mit

Sn"1t · An"1 · Sn"1 =

.

/0"1 0"2 . . .0 "n"1

1

23 ,

wobei "1, ", . . . , "n"1 > 0 die Eigenwerte von An"1 sind. Daraus folgt:.

///0

0Sn"1

t ...0

0 · · · 0 1

1

2223 · A ·

.

///0

0Sn"1

...0

0 · · · 0 1

1

2223 =

.

///0

"1 0 $1. . . ...0 "n"1 $n"1

$1 · · · $n"1 $n

1

2223 =: C .

Wegen det A = detAn > 0 gilt: det C > 0 . Setzen wir weiter

T :=

.

///0

c1

En"1...

cn"1

0 · · · 0 1

1

2223

47Adolf Hurwitz, deutscher Mathematiker (!26.03.1859, †18.11.1919)


mit ci := %$i

"ifur jedes 1 ( i ( n% 1 , so ergibt sich:

T t · C · T =

.

///0

0En"1

...0

c1 · · · cn"1 1

1

2223 · C ·

.

///0

c1

En"1...

cn"1

0 · · · 0 1

1

2223

=

.

///0

"1 0 $1. . . ...0 "n"1 $n"1

)1 · · · )n"1 )n

1

2223 ·

.

///0

c1

En"1...

cn"1

0 · · · 0 1

1

2223

mit )i := ci "i + $i = 0 fur alle 1 ( i ( n% 1 und dem Eintrag

)n :=n"1'

i=1

ci $i + $n = %n"1'

i=1

$i2

"i+ $n .

Damit erhalten wir:

T t · C · T =

.

///0

"1 0 "1 c1+$1. . . ...0 "n"1 "n"1 cn"1+$n"1

0 · · · 0 )n

1

2223 =: D ,

woraus schließlich wegen detT = detT t = 1 und det C > 0 sowie "1, "2, . . . ,"n"1 > 0folgt: )n > 0 . Also ist D positiv definit und daher nach Folgerung 31.5 auch C .Nochmalige Anwendung von Folgerung 31.5 liefert die positive Definitheit von A .

!

31.7 Folgerung

Eine symmetrische Matrix A " Mat(n, n; IR) ist genau dann negativ definit, d. h.:

x · A · xt < 0 fur alle x " IRn \ {0} ,

wenn gilt: (%1)k · det Ak > 0 fur jedes 1 ( k ( n .

Beweis:

Betrachte B := %A und wende das Kriterium von Hurwitz (Satz 31.6) auf B an. # !

31.8 Definition

Nach dem Sylvester’schen Tragheitssatz 31.4 gibt es zu jeder symmetrischen bzw. Hermite’schenMatrix A " Mat(n, n; IK) eindeutig bestimmte naturliche Zahlen k und l sowie eine MatrixS " GL(n; IK) mit

A = St ·

.

/0Ek 0 00 %El 00 0 0

1

23 · S .


Man nennt (k, l) den Typ von A, k den (Tragheits–)Index von A, k%l die Signatur von A undl den Morse–Index 48 von A.Wir schreiben dafur: k = IndexA und k % l = SignA .

Wenden wir diese Ergebnisse mit obiger Begriffsbildung auf das Transformationsproblem reellerQuadriken an, so existiert folglich eine Matrix S1 " GL(n; IR) mit

S1t · A · S1 =

.

/0Ek 0 00 %Em"k 00 0 0

1

23 ,

wobei m := rg(A) und k = IndexA , also SignA = 2 k %m ist. Setzen wir

S$1 :=

.

///0

1 0 · · · 00... S1

0

1

2223 ,

dann ergibt sich fur die erweiterte Matrix A$ von A :

B$1 := (S$1)

t · A$ · S$1 =

.

////0

c00 c01 · · · c0n

c10 Ek 0 0... 0 %Em"k 0

cn0 0 0 0

1

22223

mit c0i = ci0 fur jedes 1 ( i ( n . Bezuglich der durch S$1 bestimmten neuen Koordinateny1, y2, . . . , yn hat eine Quadrik Q 5 IRn die Gleichung

y12 + y2

2 + . . . + yk2 % yk+1

2 % yk+22 % . . .% ym

2 + 2 (c01 y1 + c02 y2 + . . . + c0n yn) + c00 = 0 .

Setzen wir weiter

S$2 :=

.

/////////////////0

1 0 0 0%c10

...%ck0

Ek 0 0

ck+1,0...

cm0

0 Em"k 0

0...0

0 0 En"m

1

222222222222222223

,

48Harold Calvin Marston Morse, amerikanischer Mathematiker (!24.03.1892, †22.06.1977)


so istB$

2 := (S$2)t · B$1 · S$2 = (S$2)t · (S$1)t · A$ · S$1 · S$2

=

.

/////////0

d00 0 0 c0,m+1 · · · c0n

0 Ek 0 0

0 0 %Em"k 0

cm+1,0...

cn0

0 0 0

1

2222222223

.

Wir wollen spater untersuchen, welche geometrische Veranderung fur Q durch die obige MatrixS$2 " Mat(n+1, n+1; IR) beschrieben wird.Nehmen wir nun an, durch S$2 ergaben sich ”vernunftige“ neue Koordinaten z1, z2, . . . , zn , soließe sich die reelle Quadrik Q auf die Form

z12+z2

2+. . .+zk2%zk+1

2%zk+22%. . .%zm

2+2 (cm+1,0 zm+1+cm+2,0 zm+2+. . .+cn0 zn)+d00 = 0

bringen. Wir werden in §34 anhand dieser Gleichung eine Klassifikation der Quadriken vorneh-men.

31.9 Beispiel

Wir betrachten die Menge

Q := {(x, y) " IR2 | 8 x2 + 12 x y + 17 y2 % 44 x% 58 y % 7 = 0} ,

von der wir zeigen wollen, daß sie eine Quadrik darstellt, die wir bereits kennen. Dazu bildenwir gemaß Bemerkung 31.3:

A =!

8 66 17

"

und A$ =

.

/0%7 %22 %29%22%29 A

1

23

und berechnen die Eigenwerte von A ; es ergeben sich: "1 = 20 und "2 = 5 . Zugehorige

normierte Eigenvektoren sind105

!12

"

und105

!2

%1

"

. Also transformiert S :=105

!2 1

%1 2

"

die Matrix A auf Diagonalgestalt, d. h.:

St · A · S =!

5 00 20

"

.

Mit S$ :=

.

/01 0 000 S

1

23 erhalten wir:

(S$)t · A$ · S$ =

.

//0

%7 % 15&5% 80&

5% 15&

55 0

% 80&5

0 20

1

223 =: B$ .


Setzen wir weiter.

/01xy

1

23 = S$ ·

.

/01uv

1

23 , d. h.: x =105

(2 u + v) 9 y =105

(%u + 2 v)

,- u =105

(2 x% y) 9 v =105

(x + 2 y) ,

so gilt:

Q =$(x, y) " IR2

%%% (1, x, y) · A$ ·

.

/01xy

1

23 = 0&

=$(u, v) " IR2

%%% (1, u, v) · B$ ·

.

/01uv

1

23 = 0&

.

Nun ist (durch quadratische Erganzung)

(1, u, v) · B$ ·

.

/01uv

1

23 = 20 v2 + 5 u2 % 16005

v % 3005

u% 7

= 205v2 % 80

5v +

165

6+ 5

5u2 % 60

5u +

95

6% 64% 9% 7

= 205v % 40

5

62+ 5

5u% 30

5

62% 80 ;

also ergibt sich mit w := u% 305

und z := v % 405

:

Q = {(w, z) " IR2 | 20 z2 + 5 w2 = 80}

=$(w, z) " IR2

%%%w2

16+

z2

4= 1

&.

Damit stellt Q eine gedrehte und verschobene Ellipse mit den Halbachsen a = 4 und b = 2 dar:

$

#z

w

Q

.........

..............................

.............................

....................................................

..........................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................

..................................

.............................................. ..

......

.....

......

.......

.........

.....................................................................................

............

"

Der Ubergang von (u, v) zu (w, z) bedeutet gerade eine ”Verschiebung des Koordinatensystems“.Wir sprechen von der Normalform einer Quadrik, wenn wir eine Drehung und eine Verschiebungdurchgefuhrt haben; dieser Prozeß heißt Hauptachsentransformation.Insgesamt gilt hier:

x =105

(2 w + z) + 2 und y =105

(%w + 2 z) + 1 ;

und die Ellipse im (w, z)–Koordinatensystem wird in den Punkt (2, 1) verschoben und anschlie-ßend um circa %26,6! gedreht (oder umgekehrt). Ferner ist:

w =105

(2 x% y % 3) , also: w = 0 ,- y = 2x% 3

und z =105

(x + 2 y % 4) , also: z = 0 ,- y = %12

x + 2 .

Kapitel VIII

Affine Geometrie

§ 32 Affine Raume

32.1 Definition

Ein a!ner Raum uber dem Korper K ist ein Tripel A................................................... := (M,V, $) , bestehend aus einer

nichtleeren Menge M , einem K–Vektorraum V = (V,+, ·) und einer Abbildung

$ : M #M $ V , (P,Q) )$%$PQ

mit den folgenden Eigenschaften:

(A1) Es gilt:%$PQ +

%$QR =

%$PR fur alle P,Q,R " M .

(A2) Fur alle P " M und alle v " V gibt es genau ein Q " M mit%$PQ = v .

Die Elemente von M heißen Punkte des affinen Raumes, und V heißt der Di"erenzraum von A................................................... .

Den Vektor%$PQ " V nennt man den Di"erenzvektor von P und Q. Manchmal sprechen wir auch

kurz vom affinen Raum M (uber K ) statt von (M,V, $) .Die leere Menge " soll ebenfalls ein affiner Raum (uber K ) sein.

32.2 Bemerkung

In §5 (siehe Lineare Algebra I) haben wir affine Unterraume von Vektorraumen eingefuhrt.Wir uberlegen uns, daß dies die wichtigsten Beispiele fur affine Raume sind.Ist namlich V " VRK und W 5 V ein Untervektorraum, so definierten wir eine Menge

M := {v + w | w " W} = v + W

als affinen Unterraum von V . Nun ist M auch ein affiner Raum uber dem Korper K mit dem

Differenzraum W und der Abbildung%$PQ := Q% P . Denn:

(i) Ist P = v + w1 , Q = v + w2 mit w1, w2 " W , so gilt: Q% P = w2 %w1 " W , also ist$ eine Abbildung von M #M nach W gemaß Definition 32.1.

169

170 KAPITEL VIII. AFFINE GEOMETRIE

(ii) Fur alle P,Q,R " M gilt das Axiom (A1):

%$PQ +

%$QR = (Q% P ) + (R%Q) = R% P =

%$PR .

(iii) Zu jedem P " M und jedem w " W setzen wir: Q := P+w ; dann ist mit P = v+w1 " Mauch Q = P + w = v + (w1 + w) aus M , und es folgt Axiom (A2):

%$PQ = Q% P = P + w % P = w .

Speziell kann also jeder Vektorraum als affiner Raum aufgefaßt werden.

32.3 Bemerkungen

(i) Das Axiom (A2) besagt, daß die Abbildung #P : M $ V mit #P (Q) :=%$PQ fur alle

P " M bijektiv ist.

(ii) Es gilt:%$PQ = 0 genau dann, wenn P = Q ist.

(iii) Es ist stets%$PQ = %

%$QP .

(iv) Es gilt:%%%$P1Q1 =

%%%$P2Q2 ,-

%%%$P1P2 =

%%%$Q1Q2 .

!

!"

%!

!"%

P1

P2

Q2

Q1

%%%$P1P2

%%%$P2Q2

%%%$Q1Q2

%%%$P1Q1

...........................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................

..................................................................

..................................................................

..................................................................

...............................................................

....

....

....

....

....

....

....

....

....

....

..

Beweis:

zu (i): ist klar. #

zu (ii): Nach (A1) gilt:%$PP +

%$PP =

%$PP , also:

%$PP = 0 . Und (A2) liefert die Behauptung.

zu (iii): Gemaß (A1) und (ii) gilt:%$PQ +

%$QP =

%$PP = 0 , also folgt:

%$PQ = %

%$QP .

zu (iv): Es gilt:

%%%$P1P2 %

%%%$Q1Q2 =

%%%$P1P2 +

%%%$P2Q1 % (

%%%$P2Q1 +

%%%$Q1Q2) =

%%%$P1Q1 %

%%%$P2Q2 .

!

§ 32. AFFINE RAUME 171

32.4 Definition

Eine Teilmenge L 5 M eines affinen Raumes A................................................... = (M, V, $) heißt ein a!ner Unterraum

von A................................................... , wenn fur einen beliebigen Punkt P " L die Differenzmenge W := {

%$PQ | Q " L} ein

Untervektorraum von V ist, oder wenn L = " gilt.Im Fall L .= " liegt genau dann ein affiner Unterraum vor, wenn (L,W, $|L+L) mit derAbbildung $ : M #M $ V ein affiner Raum (uber K ) ist.

(Diese Definition ist unabhangig von der Wahl des Punktes P " L . Ist namlich P $ " L , dann

gilt:%$P $Q =

%$P $P +

%$PQ = %

%$PP $ +

%$PQ " W ,- Q " L .)

Ist A................................................... = (M, V, $) ein affiner Raum (uber K ), so heißt dimK A.............................................

...... := dimK V die Dimensionvon A.............................................

...... . Wir setzen fur den leeren affinen Raum: dimK " := %1 .

Es sei nun (Li)i%I eine Familie von beliebig vielen affinen Unterraumen des affinen RaumesA................................................... = (M,V, $) mit zugehorigen Differenzraumen Wi " VRK . Gilt dann: L =

Bi%I

Li .= " , so

ist L ein affiner Unterraum von A................................................... mit Differenzraum W =

Bi%I

Wi .

(Denn L ist ein affiner Unterraum von A................................................... genau dann, wenn fur ein festes P " L die Menge

{%$PQ | Q " L} ein Untervektorraum von V ist. Nun gilt:

{%$PQ | Q " L} =

$%$PQ

%%% Q "C

i%I

Li

&=

$%$PQ

%%% Q " Li 4i%I

&

=C

i%I

{%$PQi | Qi " Li} =

C

i%I

Wi = W . )

Ist X 5 M , so existiert ein kleinster affiner Unterraum von A................................................... = (M, V, $) , der X umfaßt,

namlichB

L%X a!nerUnterraumvon A.....................................

.

L .

Ist (Li)i%I eine beliebige Familie von affinen Unterraumen, so heißt der kleinste affine Unter-raum, welcher die Vereinigung

Di%I

Li enthalt, der Verbindungsraum der Familie (Li)i%I .

Wir schreiben dafur:Ei%I

Li . Ist I .= " endlich, so bezeichnen wir den Verbindungsraum

von (Li)i=1,2,...,n mit:nE

i=1Li oder L1 8 L2 8 . . . 8 Ln .

Sind P und Q nur Punkte aus M , so schreiben wir einfach: P 8Q anstelle von {P} 8 {Q} .

32.5 Bemerkung

Es seien L1 und L2 zwei affine Unterraume von A................................................... = (M,V, $) . Fur den Differenzraum W des

Verbindungsraumes L = L1 8 L2 gilt:

W =F

W1 + W2 , falls L1 3 L2 .= "(W1 + W2)2 U , falls L1 3 L2 = " ,

wobei U der Differenzraum von P1 8 P2 fur zwei beliebige Punkte P1 " L1 und P2 " L2 ist.


V = IR3

............... ............... ............... ............... ............... ............... ............... ............... ............... ............... ............... ............... ............... ............... ............... ............... ...............

...............................................................................................................................................................................................................................................................

...............................................................................................................................................................................................

..............................

..............................

..............................

..............................

..............................

..............................

...........

.................................................................................................................................................................................................................................

L1

#

......................................................................................................

..............

....................................

....................................

....................................

.................... ..................

......................

...............................................................................................................................................................................................................................................................................................................................

L2

#

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .$ $&&&&&'

((

((()

Beweis zu Bemerkung 32.5:

1. Fall: Sei L13L2 .= " , etwa P " L13L2 ; wir betrachten N := {Q " M |%$PQ " W1 +W2} .

Dann ist N ein affiner Unterraum von A................................................... mit (P " N und) Differenzraum W1 + W2 . Ferner

gilt: Li 5 N fur i = 1, 2 , also ist auch L1 8 L2 5 N und damit W 5 W1 + W2 . Andererseitsgilt wegen Li 5 L1 8 L2 auch: Wi 5 W fur i = 1, 2 , d. h.: W1 + W2 5 W . Daraus folgt:N = L1 8 L2 .

2. Fall: Es sei jeweils Li .= " fur i = 1, 2 und L13L2 = " . (Alle anderen Moglichkeiten sind

trivial.) Wir wahlen zwei Pi " Li fest und betrachten N := {Q " M |%$P1Q " W1+W2 + U} .

Dann ist L1 5 N und wegen%$P1Q =

%%%$P1P2 +

%$P2Q sowie

%%%$P1P2 " U auch L2 5 N . Damit gilt:

L1 8 L2 5 N und W 5 W1+W2 + U . Umgekehrt gilt wegen Li 5 L1 8 L2 fur i = 1, 2 undP18P2 5 L18L2 , auch: W1+W2 +U 5 W . Daraus folgt: W = W1+W2 +U und L18L2 = N .Wir zeigen noch, daß (W1 + W2) + U eine direkte Summe ist. Dazu betrachten wir die Menge

U $ := {" ·%%%$P1P2 | " " K} = U . (Wegen

%%%$P1P2 " U und da U ein K–Vektorraum ist, folgt sofort:

"%%%$P1P2 " U fur alle " " K , also: U $ 5 U . Andererseits ist N $ := {Q " M |

%$P1Q " U $}

ein affiner Raum mit Pi " N $ , also P1 8 P2 5 N $ . Dies bedeutet: U 5 U $ , d. h.: U = U $ .)

Angenommen, es existierte ein w " (W1 + W2)3U mit w .= 0 . Dann ware "%%%$P1P2 " W1 + W2

fur ein geeignetes " " K \ {0} , also galte:%%%$P1P2 " W1 + W2 . Es wurden demnach Qi " Li mit

%%%$P1P2 =

%%%$P1Q1 +

%%%$Q2P2 oder

%%%$Q1Q2 =

%%%$Q1P1 +

%%%$P1P2 +

%%%$P2Q2 = 0 existieren. Das ergabe: Q1 = Q2

im Widerspruch zur Voraussetzung L1 3 L2 = " .!

32.6 Satz (Dimensionsformel)

Es seien L1 , L2 zwei endlich–dimensionale affine Unterraume von A................................................... = (M, V, $) . Dann gilt:

a) dimK L1 + dimK L2 = dimK(L1 8 L2) + dimK(L1 3 L2)im Falle L1 = " oder L2 = " oder L1 3 L2 .= " .

b) dimK L1 + dimK L2 = dimK(L1 8 L2) + dimK(W1 3W2)% 1im Falle L1 .= " und L2 .= " und L1 3 L2 = " .



zu a): Ist L1 = " oder L2 = " , dann bleibt nichts zu zeigen. #Hat man L13L2 .= " , so gilt nach Bemerkung 32.5 und Dimensionsformel 4.3 (sieheLineare Algebra I):

dim (L1 8 L2) = dim W = dim (W1 + W2)= dim W1 + dim W2 % dim (W1 3W2)= dim L1 + dim L2 % dim (L1 3 L2) .

zu b): Ebenfalls mit Bemerkung 32.5 und Satz 4.3 folgt fur disjunkte L1, L2 .= " analog:

dim (L1 8 L2) = dim W = dim (W1 + W2) + dim U

= dim W1 + dim W2 % dim (W1 3W2) + dim U

= dim L1 + dim L2 % dim (W1 3W2) + 1 .

!

32.7 Bemerkung

Affine Unterraume der Dimension 1 nennen wir Geraden, bei affinen Unterraumen der Dimen-sion 2 sprechen wir von Ebenen.Ist L ein affiner Unterraum von M mit L .= M , und existiert ein P " M mit L 8 P = M ,so heißt L eine Hyperebene von M . Ist dabei dimK M = n , dann sind die Hyperebenen von Mgenau die affinen Unterraume der Dimension n% 1 .Zwei affine Unterraume Li .= " eines affinen Raumes heißen parallel , wenn W1 5 W2 oderwenn W2 5 W1 gilt. Wir schreiben dann auch: L1 ! L2 .

32.8 Definition

Es sei A................................................... = (M, V, $) ein affiner Raum uber K . Eine Familie (Pi)i%{0},I von Punkten

aus M heißt a!n unabhangig bzw. eine a!ne Basis von M , wenn die Familie (%%%$P0Pi )i%I linear

unabhangig bzw. eine Basis von V ist. (Ist eine Familie von Punkten aus M nicht affin unab-hangig, so nennt man sie a!n abhangig.)Ist dabei dimK V = n , und bilden P0, P1, P2, . . . , Pn eine affine Basis von M , so heißt P0

der Ursprung oder Koordinatenanfang. Und wir nennen dann dieses geordnete (n + 1)-Tupel(P0, P1, P2, . . . , Pn) ein Koordinatensystem von A.............................................

...... .

32.9 Lemma

Es seien A................................................... = (M,V, $) ein affiner Raum und (Pi)i=0,1,2,...,n eine Familie affin unabhangiger

Punkte aus M . Dann sind folgende Aussagen aquivalent:

(a) (Pi)0#i#n ist eine affine Basis von M .

(b) dimK M = n .

(c) M = P0 8 P1 8 P2 8 . . . 8 Pn .



”(a) ,- (b)“: ist klar. #

”(a) - (c)“: Sei N := P0 8 P1 8 P2 8 . . . 8 Pn und W der zugehorige Differenzraum. Wegen

Pi " N fur alle 0 ( i ( n und%%%$P0Pi " W fur jedes 1 ( i ( n . Da die

%%%$P0Pi

eine Basis von V bilden, ist W = V , also auch N = M .

”(c) - (b)“: Weil alle (Pi)0#i#n affin unabhangig sind, sind die einzelnen Punkte paarweiseverschieden. Mehrmalige Anwendung der Dimensionsformel 32.6 liefert dann:

dimM = dim (P0 8 P1 8 P2 8 . . . 8 Pn)= dim (P0 8 P1 8 P2 8 . . . 8 Pn"1) + dim Pn* +, -

= 0

% 0 + 1

= dim (P0 8 P1 8 P2 8 . . . 8 Pn"2) + dim Pn"1* +, -= 0

% 0 + 1 + 1

= . . .

= dim (P0 8 P1) + (n% 1)= dim P0* +, -

= 0

+ dimP1* +, -= 0

% 0 + 1 + (n% 1)

,- dimM = n .

!

Ist (P0, P1, P2, . . . , Pn) ein Koordinatensystem des affinen Raumes A................................................... = (M,V, $) uber

dem Korper K , dann konnen wir jedem Punkt P " M umkehrbar eindeutig einen Vektor(x1, x2, . . . , xn) " Kn zuordnen:

Ist P " M , so existiert genau ein (x1, x2, . . . , xn) " Kn mit%$P0P =

n'

i=1

xi%%%$P0Pi .

Dieses n-Tupel (x1, x2, . . . , xn) bezeichnen wir als die Koordinaten von P bezuglich des Koordi-natensystems (P0, P1, P2, . . . , Pn). Ist Q " M ein Punkt mit den Koordinaten (y1, y2, . . . , yn) ,

dann hat der Vektor%$PQ " V bezuglich der Basis (

%%%$P0P1,

%%%$P0P2, . . . ,

%%%$P0Pn) in V die Koordinaten

(y1 % x1 , y2 % x2 , . . . , yn % xn) wegen%$PQ =

%$P0Q%

%$P0P .

Ist nun (P *0 , P *

1 , P *2 , . . . , P *

n) ein weiteres Koordinatensystem von A................................................... , so entspricht der Basis-

transformation in V von der Basis (%%%$P0P1,

%%%$P0P2, . . . ,

%%%$P0Pn) zur Basis (

%%%$P *

0 P *1 ,%%%$P *

0 P *2 , . . . ,

%%%$P *

0 P *n)

eine Transformationsmatrix C mit%%%$P *

0 P *i =

n)j=1

)ij%%%$P0Pj (vgl. Lemma 17.1 in Lineare Alge-

bra I). P *0 habe bezuglich (P0, P1, P2, . . . , Pn) die Koordinaten (t1, t2, . . . , tn) " Kn , d. h.:

%%%$P0P *

0 =n'

j=1

tj%%%$P0Pj .

Hat jetzt P " M die Koordinaten (x1, x2, . . . , xn) bezuglich (P0, P1, P2, . . . , Pn) und die Ko-

ordinaten (x*1, x*2, . . . , x*n) bezuglich (P *0 , P *

1 , P *2 , . . . , P *

n) , so gilt wegen%$P0P =

%%%$P0P *

0 +%$P *

0 Peinerseits:

%$P0P =

n'

j=1

xj%%%$P0Pj ,

%$P *

0 P =n'

i=1

x*i%%%$P *

0 P *i


und andererseits:

%$P0P =

n'

j=1

tj%%%$P0Pj +

n'

i=1

x*i

n'

j=1

)ij%%%$P0Pj =

n'

j=1

7tj +

n'

i=1

x*i )ij

8%%%$P0Pj ,

also: (x1, x2, . . . , xn) = (t1, t2, . . . , tn) + (x*1, x*2, . . . , x*n) · C .Dies ist genau die Transformationsformel aus Lemma 17.1 wegen

.

////0

x1 % t1x2 % t2

...xn % tn

1

22223= Ct ·

.

////0

x*1x*2...

x*n

1

22223= S ·

.

////0

x*1x*2...

x*n

1

22223,-

.

////0

x*1x*2...

x*n

1

22223= S"1 ·

.

////0

x1 % t1x2 % t2

...xn % tn

1

22223.

Dabei sind die xj % tj fur 1 ( j ( n gerade die Koordinaten von%$P0P %

%%%$P0P *

0 =%$P *

0 P " V

bezuglich der Basis (%%%$P0P1,

%%%$P0P2, . . . ,

%%%$P0Pn) .

32.10 Definition

Es sei A................................................... = (M, V, $) ein affiner Raum uber K ; eine Familie (Pi)i%I von Punkten Pi " M

heißt kollinear, wenn die Punkte alle auf einer Geraden liegen.Ist (P0, P1, P ) ein Tripel kollinearer Punkte aus M mit P0 .= P1 , so existiert genau ein Skalar

+ = +(P0, P1, P ) " K mit%$P0P = + ·

%%%$P0P1 . Wir nennen dieses + das Teilverhaltnis der kolline-

aren Punkte P0, P1, P und schreiben: + = TV(P0, P1, P ) .

!P0 !P !P1# #

Sind nun x# , y# , z# fur 1 ( ' ( n die Koordinaten von P0, P1, P bezuglich irgendeinesKoordinatensystems von A.............................................

...... , so gilt: z# % x# = + · (y# % x#) fur alle ' = 1, 2, . . . , n ,wobei dimK M =: n vorausgesetzt sei. Fur jene ' " {1, 2, . . . , n} mit y# % x# .= 0 erhalten wirdann:

TV(P0, P1, P ) =z# % x#

y# % x#.

Und P heißt der Mittelpunkt von P0 und P1, wenn TV(P0, P1, P ) = 12 gilt (was naturlich nur

fur Korper K mit charK .= 2 sinnvoll ist49).

32.11 Definition

Wir sprechen von einem reellen bzw. komplexen affinen Raum, wenn fur den zugrundegelegtenKorper K = IR bzw. K = C gilt.Ist A.............................................

...... = (M,V, $) ein affiner Raum uber IK mit einem euklidischen bzw. unitaren VektorraumV " VRIK , so nennt sich A.............................................

...... selbst ein euklidisch–a!ner bzw. unitar–a!ner Raum.

Fur zwei Punkte P,Q " M heißt dann d(P,Q) := !%$PQ! =

G

&%$PQ,

%$PQ'

der Abstand von P nach Q.

49Vgl. etwa Seite 86; in K soll hier also 1 + 1 #= 0 gelten.


Sind P,Q,Q$ " M paarweise verschiedene Punkte eines euklidisch–affinen RaumesA................................................... = (M,V, $) mit dem Skalarprodukt &·, ·' , so heißt

$(g, g$) := arccos|&%$PQ,

%$PQ$'|

!%$PQ! · !

%$PQ$!

" [ 0 ; "2 ]

der Winkel zwischen den Geraden g = P 8Q und g$ = P 8Q$ .

...........................................................................................................................................................................................................................................................................................................................................................................................................................................

....................................

....................................

....................................

....................................

....................................

....................................

....................................

....................................

....................................

....................................

....................................

..

........

.........

.................................................

$g

g$

!Q$

!P

!Q

§ 33 Affine Abbildungen

Gegeben seien hier stets zwei nichtleere affine Raume A................................................... = (M, V, $) und IB = (N, W, ,$)

uber demselben Korper K .

33.1 Definition

Eine Abbildung f : M $ N heißt a!n, falls es eine K–lineare Abbildung Ff : V $ W gibt

mit50 Ff (%$PQ) =

%%%%%%%$f(P )f(Q) fur alle P,Q " M .

33.2 Bemerkungen

(i) Jede affine Abbildung f : M $ N bestimmt eindeutig eine lineare Abbildung Ff : V $ W .

(ii) Ist F : V $ W eine lineare Abbildung, so gibt es zu vorgegebenen P0 " M und P *0 " N

genau eine affine Abbildung f : M $ N mit f(P0) = P *0 und Ff = F .

(iii) Ist f : M $ N affin, und ist die Familie (Pi)i%I affin abhangig in M , dann sind dieBildpunkte (f(Pi))i%I affin abhangig in N .

(iv) Ist f : M $ N affin, und sind (f(Pi))i%I affin unabhangig in N , so sind auch die Urbilder(Pi)i%I affin unabhangig in M .

(v) Ist f : M $ N affin und (Pi)i%I eine affine Basis von M , so ist f durch Qi := f(Pi) furalle i " I eindeutig festgelegt.

(vi) Ist ID = (S, U, !) ein weiterer affiner Raum uber K , und sind g : N $ S sowief : M $ N affin, dann ist auch die Komposition g * f : M $ S eine affine Abbildungmit Fg!f = Fg * Ff .

50Man beachte, daß sich die erste Pfeiloperation $ auf A...............................

, die zweite dagegen auf !$ von IB bezieht. Kunftigwird dies bei mehreren a!nen Raumen nicht mehr extra unterschieden.

§ 33. AFFINE ABBILDUNGEN 177


zu (i): ist klar. #zu (ii): Eindeutigkeit von f : Angenommen, es gabe noch eine affine Abbildung g : M $ N

mit g(P0) = P *0 und Fg = F . Dann gilt fur alle P " M :

Ff (%$P0P ) = Fg(

%$P0P ) = F (

%$P0P ) , d. h. gemaß Definition:

%%%%%%%$f(P0)f(P ) =

%%%%%%%$g(P0)g(P ) = F (

%$P0P ) ,-

%%%%%%$P *

0 f(P ) =%%%%%%$P *

0 g(P ) = F (%$P0P ) .

Daraus folgt nach Axiom (A2): f(P ) = g(P ) , also: f = g .Andererseits definieren wir die affine Abbildung f gerade durch die letzte Gleichung;somit ist auch die Existenz von f gesichert.

zu (iii) – (v): folgt aus den entsprechenden Ergebnissen von Bemerkung 14.2 (ii) und (iii) sowieSatz 14.6 (siehe Lineare Algebra I). #

zu (vi): Die Linearitat von Fg * Ff ergibt sich direkt aus Bemerkung 14.2(iv); ferner ist furbeliebige P,Q " M :

Fg

5Ff (

%$PQ)

6= Fg

5%%%%%%%$f(P ) f(Q)

6=%%%%%%%%%%%%$g(f(P ))g(f(Q)) =

%%%%%%%%%%%%%%%$(g *f)(P ) (g *f)(Q) .

!

Als weitere Folgerung zu §14 ergibt sich:

33.3 Satz

Ist f : M $ N affin mit zugehoriger linearer Abbildung Ff : V $ W , dann gilt:

(a) Es ist f injektiv genau dann, wenn Ff injektiv ist.

(b) Es ist f surjektiv genau dann, wenn Ff surjektiv ist.

(c) Ist f bijektiv, so ist die Umkehrabbildung f"1 : N $ M affin mit Ff&1 = (Ff )"1 .

Beweis:

zu (a) & (b): sind klar. #zu (c): Fur R,S " N seien P,Q " M mit f(P ) = R und f(Q) = S ; dann gilt nach

Definition von Ff :

Ff

5%%%%%%%%%%%%$f"1(R) f"1(S)

6=%$RS , also: (Ff )"1(

%$RS) =

%%%%%%%%%%%%$f"1(R) f"1(S) .

!


33.4 Satz

Es sei f : M $ N eine affine Abbildung; dann gilt:

a) Ist L ein affiner Unterraum von M , so ist das Bild f(L) ein affiner Unterraum von N .

b) Ist L$ ein affiner Unterraum von N , so ist das Urbild"1f (L$) ein affiner Unterraum von M .

Beweis: siehe Ubungsaufgabe 33–1. (!)

Es seien nun (P0, P1, P2, . . . , Pn) ein Koordinatensystem von A................................................... und (Q0, Q1, Q2, . . . , Qm) ein

Koordinatensystem von IB .Ist f : M $ N affin, so gehort zu der linearen Abbildung Ff " HomK(V,W ) bezuglich der

Basen A = (%%%$P0P1,

%%%$P0P2, . . . ,

%%%$P0Pn) von V und B = (

%%%$Q0Q1,

%%%$Q0Q2, . . . ,

%%%%$Q0Qm) von W eine

Matrix ΦAB (Ff ) = A = (#ij) " Mat(m, n;K) mit

Ff (%%%$P0Pj ) =

m'

i=1

#ij%%%$Q0Qi .

Ist weiter%%%%%%$Q0f(P0) =

m)i=1

ti%%%$Q0Qi , d. h. sind (t1, t2, . . . , tm) " Km die Koordinaten von f(P0)

bezuglich (Q0, Q1, Q2, . . . , Qm) , dann folgt fur die Koordinaten x = (x1, x2, . . . , xn) eines be-liebigen Punktes P " M und seine ”Bild–Koordinaten“ x* = (x*1, x*2, . . . , x*m) von f(P ) " N :.

////0

x*1x*2...

x*m

1

22223=

.

////0

t1t2...

tm

1

22223+ A ·

.

////0

x1

x2...

xn

1

22223. (6)

Es gilt namlich:

%%%%%%$Q0f(P ) =

%%%%%%$Q0f(P0) +

%%%%%%%$f(P0)f(P ) =

m'

i=1

ti%%%$Q0Qi + Ff (

%$P0P )

=m'

i=1

ti%%%$Q0Qi +

n'

j=1

xj Ff (%%%$P0Pj )

=m'

i=1

ti%%%$Q0Qi +

n'

j=1

xj

m'

i=1

#ij%%%$Q0Qi .

Umgekehrt definiert jedes (t1, t2, . . . , tm) " Km und jede Matrix A " Mat(m, n;K) durch (6)eine affine Abbildung.

33.5 Definition

Es sei A................................................... = (M, V, $) ein affiner Raum uber K . Jede bijektive affine Abbildung f : M $ M

heißt eine A!nitat oder ein a!ner Automorphismus.Gilt dabei: Ff = " · idV mit " " K , so heißt f eine Dilatation mit Faktor " ; im Falle " = 1nennt man f eine Translation, im Fall " = 0 heißt die Dilatation f entartet.


33.6 Lemma

Es seien A................................................... = (M,V, $) ein affiner Raum uber K und f : M $ M eine affine Abbildung.

Dann sind aquivalent:

a) f ist eine Translation.

b) Fur alle P,Q " M gilt:%%%%$Pf(P ) =

%%%%$Qf(Q) .

Beweis:

Wegen%%%%$Pf(P ) = %

%%%%$f(P )P = %

5%%%%%%%$f(P )f(Q) +

%%%%$f(Q)Q +

%$QP

6=%%%%$Qf(Q) %

%%%%%%%$f(P )f(Q) +

%$PQ gilt

fur alle P,Q " M :%%%%$Pf(P ) =

%%%%$Qf(Q) ,-

%%%%%%%$f(P )f(Q) =

%$PQ ,

d. h.: Ff (%$PQ) =

%%%%%%%$f(P )f(Q) = idV (

%$PQ) . !

33.7 Bemerkung

Bezuglich der Komposition * als Verknupfung bilden die Affinitaten auf M eine Gruppe, nam-lich die sogenannte a!ne Gruppe Aff(M) von M ; die Translationen auf M bilden die (abelsche)Gruppe T(M) . Insgesamt gilt:

{idM} : T(M) : Aff(M) : S(M) .

Beweis:

Da S(M) eine Gruppe ist (gemaß Beispiel 1.6d) aus Lineare Algebra I), genugt es zu zeigen,daß f *g " Aff(M) gilt fur alle f, g " Aff(M) bzw. daß f *g " T(M) gilt fur alle f, g " T(M) .Diese Aussagen sind aber offensichtlich erfullt. # !

33.8 Definition

Es sei A................................................... = (M,V, $) euklidisch–affin oder unitar–affin. Eine Affinitat f : M $ M heißt

eine Kongruenz, wenn fur alle P,Q " M gilt: !%%%%%%%$f(P )f(Q)! = !

%$PQ! .

Diese Eigenschaft einer Kongruenz nennt man Langentreue.

33.9 Lemma

Es sei A................................................... = (M, V, $) euklidisch–affin bzw. unitar–affin. Fur eine Affinitat f : M $ M sind

folgende Aussagen aquivalent:

a) f ist eine Kongruenz.

b) Die Abbildung Ff ist ein orthogonaler bzw. unitarer Endomorphismus.



Wegen Ff (%$PQ) =

%%%%%%%$f(P )f(Q) gilt fur alle P,Q " M :

!%%%%%%%$f(P )f(Q)! = !

%$PQ! ,- !Ff (

%$PQ)! = !

%$PQ! .

Wegen (A2) folgt also:f ist eine Kongruenz genau dann, wenn !Ff (v)! = !v! gilt fur alle v " V .

Dies bedeutet mit Satz 29.2: Ff " EndIK(V ) ist orthogonal bzw. unitar. !

33.10 Definition

Es seien A................................................... = (M,V, $) euklidisch–affin bzw. unitar–affin und f : M $ M eine Affinitat.

Dann heißt f eine Ahnlichkeit, wenn ein reelles c > 0 existiert mit !%%%%%%%$f(P )f(Q)! = c · !

%$PQ!

fur alle P,Q " M . Und c selbst wird der Ahnlichkeitsfaktor von f genannt.

33.11 Bemerkung

Es sei A................................................... = (M, V, $) ein euklidisch–affiner oder unitar–affiner Raum; dann bilden die Ahn-

lichkeiten eine weitere Untergruppe51 von Aff(M) , die Gruppe Ahn(M) . Die KongruenzenKon(M) auf M wiederum bilden eine Untergruppe von Ahn(M) . Unter Verwendung von Be-merkung 33.7 hat man damit den Zusammenhang:

{idM} : T(M) : Kon(M) : Ahn(M) : Aff(M) : S(M) .

Es sei nun U eine Untergruppe von Aff(M) . Eine Aussage uber Teilmengen von A................................................... = (M,V, $)

heißt U–invariant , wenn folgendes gilt:

Trifft die Aussage auf Teilmengen M1, M2, M3, . . . 5 M zu, so soll sie fur beliebigef " U auch auf die Teilmengen f(M1), f(M2), f(M3), . . . 5 f(M) zutreffen.

Die Menge aller solchen U–invarianten Aussagen wird dann die zu U gehorende Geometrie ge-nannt. Die zu Aff(M) gehorende Geometrie heißt a!ne Geometrie, die zu Ahn(M) bzw.Kon(M) gehorende Geometrie nennt man Ahnlichkeitsgeometrie bzw. Kongruenzgeometrie(oder euklidische Geometrie).Eine solche gruppentheoretische Charakterisierung der Geometrien ist der Inhalt des sogenann-ten Erlanger Programms von F. Klein52.

Wichtige Invarianten sind hier:

51Die genaue Definition einer Untergruppe entnehme man bitte §42 aus Algebra I.52Christian Felix Klein, deutscher Mathematiker (!25.04.1849, †22.06.1925)


33.12 Satz

(a) Es sei f : M $ N affin; mit P,Q,R sind auch f(P ), f(Q), f(R) kollinear. Aus P .= Q undf(P ) .= f(Q) folgt: TV(P,Q,R) = TV(f(P ), f(Q), f(R)) . Speziell laßt jede Affinitatf : M $ M Kollinearitat und Teilverhaltnis invariant.

(b) Jede Abbildung f " Ahn(M) ist winkeltreu (im Fall K = IR ), d. h. fur paarweise ver-schiedene P,Q,Q$ " M gilt:

$(P 8Q , P 8Q$) = $(f(P ) 8 f(Q) , f(P ) 8 f(Q$)) .

(c) Jede Abbildung f " Kon(M) ist langentreu und winkeltreu.

Beweis:

zu (a): Sind P,Q,R " M kollinear, so ist dimL ( 1 , wobei L := P 8 Q 8 R sei. Damitgilt: dim f(L) = dimFf (U) mit U als Differenzraum zu L . Und Satz 15.2 (Dimen-sionsformel) liefert: dimFf (U) ( dimU = dim L ( 1 . Also sind die Bildpunkte

f(P ), f(Q), f(R) " N ebenfalls kollinear. Ist dann P .= Q und%$PR = + ·

%$PQ , so

folgt:%%%%%%%$f(P )f(R) = Ff (

%$PR) = + · Ff (

%$PQ) = + ·

%%%%%%%$f(P )f(Q) ,

d. h.: + = TV(f(P ), f(Q), f(R)) .

zu (b): Wir drucken das Skalarprodukt im Zahler von Definition 32.11 durch die Norm aus(vgl. Bemerkung 26.8(ii)) und benutzen Definition 33.10. #

zu (c): siehe Definition 33.8 und Teil (b) mit Bemerkung 33.11. #

!

Die Eigenschaft aus Satz 33.12(a) ist charakteristisch fur Affinitaten. Dazu:

33.13 Definition

Es sei A................................................... = (M,V, $) ein affiner Raum und f : M $ M eine bijektive Abbildung; f heißt

eine Kollineation, wenn fur jede Gerade L in M auch f(L) eine Gerade ist.

Dann gilt namlich:

33.14 Satz (Hauptsatz der affinen Geometrie)

Ist A................................................... = (M,V, $) ein affiner Raum uber IR mit Dimension dimIR M + 2 , so ist jede

Kollineation f : M $ M eine Affinitat.


§ 34 Klassifikation von Quadriken

Wir betrachten nunmehr den euklidisch–affinen Raum A................................................... = (IRn, IRn, $) mit

%$PR = R % P

fur alle P,R " IRn . Ist dann

Q := {(x1, x2, . . . , xn) " IRn | (x$)t · A$ · x$ = 0}

eine reelle Quadrik (nach Bemerkung 31.3), so haben wir in §31 bereits gezeigt:

Es existiert eine orthogonale Matrix S$ " O(n+1) derart, daß fur x$ = S$ · y$ gilt:

Q = {(y1, y2, . . . , yn) " IRn | (y$)t · B$ · y$ = 0} ,

wobei

B$ :=

.

/////////////////0

c00 c01 · · · c0k c0,k+1 · · · c0m c0,m+1 · · · c0n

c01 "1... . . . 0 0

c0k "k

c0,k+1 "k+1... 0

. . . 0c0,m "m

c0,m+1 0... 0 0

. . .c0n 0

1

222222222222222223

sei mit den Eigenwerten "1, "2, . . . ,"k > 0 und "k+1, "k+2, . . . ,"m < 0 von A .

Es gilt dann also fur die Koordinaten von Q :.

//0

x1x2...

xn

1

223 = S ·

.

//0

y1y2...

yn

1

223

mit einer zugehorigen orthogonalen Matrix S " O(n) . Setzen wir nun:

T $ :=

.

///////////0

1 0 0% 1

+1c01

... Em 0% 1

+mc0m

0... 0 En"m0

1

222222222223

und y$ = T $ · z$ , dann erhalten wir weiter:

B$ · T $ =

.

//////////0

d00 c01 · · · c0m c0,m+1 · · · c0n

0 "1... . . . 00 "m

c0,m+1... 0 0

c0n

1

22222222223

§ 34. KLASSIFIKATION VON QUADRIKEN 183

sowie

C $ := (T $)t · B$ · T $ =

.

//////////0

d00 0 · · · 0 c0,m+1 · · · c0n

0 "1... . . . 00 "m

c0,m+1... 0 0

c0n

1

22222222223

.

Daraus ergibt sich die ”transformierte“ Quadrik

Q = {(z1, z2, . . . , zn) " IRn | (z$)t · C $ · z$ = 0}

mit

(6)

.

//0

y1y2...

yn

1

223 =

.

////////0

% 1+1

c01...

% 1+m

c0m

0...0

1

222222223

+

.

//0

z1z2...

zn

1

223 , d. h.:

.

//0

z1z2...

zn

1

223 =

.

////////0

1+1

c01...

1+m

c0m

0...0

1

222222223

+ S"1 ·

.

//0

x1x2...

xn

1

223

Und durch (6) wird eine Kongruenz f : IRn $ IRn in A................................................... beschrieben. Wir erhalten also:

34.1 Satz (Metrische Hauptachsentransformation)

Es sei Q eine reelle Quadrik, m := rg(A) und m$ := rg(A$) . Dann gibt es eine Kongruenzf : IRn $ IRn und Skalare #1, #2, . . . ,#m " IR* derart, daß f(Q) 5 IRn beschrieben wirddurch eine Gleichung der Form

(a)z1

2

#12

+z2

2

#22

+ . . . +zk

2

#k2% zk+1

2

#k+12% zk+2

2

#k+22% . . .% zm

2

#m2

= 0 , falls m = m$ ist.

(b)z1

2

#12

+z2

2

#22

+ . . . +zk

2

#k2% zk+1

2

#k+12% zk+2

2

#k+22% . . .% zm

2

#m2

= 1 , falls m + 1 = m$ ist.

(c)z1

2

#12

+z2

2

#22

+ . . . +zk

2

#k2% zk+1

2

#k+12% zk+2

2

#k+22% . . .% zm

2

#m2

+ 2 zm+1 = 0 , falls m + 2 = m$ ist.

Beweis:

Wir erhalten durch eine Kongruenz f :

Q = {(z1, z2, . . . , zn) " IRn | (z$)t · C $ · z$ = 0}

mit rg(C $) = rg(A$) (vgl. Folgerung 31.5).

Typ (a): Ist m = m$ , so folgt: d00 = c0,m+1 = c0,m+2 = . . . = c0n = 0 . Wir setzen #i := 10|+i|

fur jedes i = 1, 2, . . . ,m .


Typ (b): Ist m + 1 = m$ , dann folgt: d00 .= 0 und c0,m+1 = c0,m+2 = . . . = c0n = 0 . OhneBeschrankung der Allgemeinheit konnen wir d00 < 0 voraussetzen (anderenfalls mul-tiplizieren wir die Gleichung mit %1 und ordnen die z1, z2, . . . , zm um). Wir dividierendie Gleichung durch |d00| und setzen #i := ( |+i|

|d00|)" 1

2 fur alle i = 1, 2, . . . ,m .

Typ (c): Gilt: m + 2 = m$ , so existiert mindestens ein Index r " {m + 1, m + 2, . . . , n} mitc0,r .= 0 . Ohne Einschrankung konnen wir r = m + 1 annehmen (sonst ordnen wirdie zm+1, zm+2, . . . , zn geeignet um). Unser Ziel ist es, durch eine Kongruenz f dieEintrage d00, c0,m+2, c0,m+3, . . . , c0n zum Verschwinden zu bringen. Wir setzen dazuv := (c0,m+1, c0,m+2, . . . , c0n) " IRn"m sowie v1 := v

(v( und bestimmen nach demVerfahren von Schmidt–Gram eine Orthonormalbasis (v1, v2, . . . , vn"m) des IRn"m .Dann beschreibt die erweiterte Matrix

R$ :=

.

//////////0

1 0 · · · 0 0 · · · 00... Em 00

µ v1t 0 v1

t · · · vn"mt

1

22222222223

mit µ := % d00

2 !v!

eine Kongruenz, da die zugehorige Matrix R orthogonal ist. Mit etwas Rechnungergibt sich hieraus die folgende Matrix:

(R$)t · C $ · R$ =

.

/////////////0

0 0 0 · · · 0 !v! 0 · · · 00 "1 00 "2... . . . 00 0 "m

!v!0... 0 00

1

22222222222223

.

Und wir setzen schließlich #i := ( |+i|(v()

" 12 jeweils fur i = 1, 2, . . . ,m .

!

34.2 Bemerkung

Die Darstellung einer reellen Quadrik in der Form (a), (b) oder (c) aus Satz 34.1 nennen wirdie (metrische) Normalform einer Quadrik.Allein durch Berechnung von m = rg(A) , m$ = rg(A$) sowie s := SignA und s$ := SignA$

kann man den ”Typ“ der Quadrik bestimmen. Dabei wollen wir uns bezuglich s und s$ an C $

mit d00 < 0 im Fall (b) bzw. mit c0,m+1 .= 0 im Fall (c) orientieren.

34.3 Beispiel

Nach Rang und Signatur von A und A$ klassifizieren wir nun die Quadriken im IR2 mit A .= 0 ;dies sind die sogenannten Kurven zweiter Ordnung (oder Kegelschnitte).Mit obigen Bezeichnungen erhalten wir folgende Tabelle:


m m! s s! Gleichung Beschreibung

2 3 2 1x2

a2+

y2

b2= 1 Ellipse (bzw. Kreis, falls a = b )

2 3 0 %1x2

a2% y2

b2= 1 Hyperbel

2 3 %2 %3 %x2

a2% y2

b2= 1 leere Menge "

2 2 2 2x2

a2+

y2

b2= 0 Nullpunkt (0, 0)

2 2 0 0x2

a2% y2

b2= 0 zwei sich schneidende Geraden

1 3 1 1x2

a2+ 2 y = 0 Parabel

1 2 1 0x2

a2= 1 paralleles Geradenpaar

1 2 %1 %2 %x2

a2= 1 leere Menge "

1 1 1 1x2

a2= 0 (Doppel-)Gerade (y–Achse)

34.4 Beispiel

Entsprechend werden jetzt alle Quadriken im IR3 mit A .= 0 klassifiziert; dies sind die soge-nannten Flachen zweiter Ordnung. In der nachsten Tabelle beziehen sich die Nummern in denKastchen auf die nachfolgenden Abbildungen.


3 4 3 2x2

a2+

y2

b2+

z2

c2= 1 Ellipsoid 1

3 4 1 0x2

a2+

y2

b2% z2

c2= 1 einschaliges Hyperboloid 2

3 4 %1 %2x2

a2% y2

b2% z2

c2= 1 zweischaliges Hyperboloid 3

3 4 %3 %4 %x2

a2% y2

b2% z2

c2= 1 leere Menge "

3 3 3 3x2

a2+

y2

b2+

z2

c2= 0 Nullpunkt (0, 0, 0)

3 3 1 1x2

a2+

y2

b2% z2

c2= 0 Kegel 6

2 4 2 2x2

a2+

y2

b2+ 2 z = 0 elliptisches Paraboloid 7



2 4 0 0x2

a2% y2

b2+ 2 z = 0 hyperbolisches Paraboloid 8

2 3 2 1x2

a2+

y2

b2= 1 elliptischer Zylinder 9

2 3 0 %1x2

a2% y2

b2= 1 hyperbolischer Zylinder 10

2 3 %2 %3 %x2

a2% y2

b2= 1 leere Menge " (”nullteiliger Zylinder“)

2 2 2 2x2

a2+

y2

b2= 0 Gerade (z–Achse)

2 2 0 0x2

a2% y2

b2= 0 zwei sich schneidende Ebenen

1 3 1 1x2

a2+ 2 y = 0 parabolischer Zylinder 14

1 2 1 0x2

a2= 1 zwei parallele Ebenen

1 2 %1 %2 %x2

a2= 1 leere Menge " (”konjugiert komplexe Ebenen“)

1 1 1 1x2

a2= 0 (Doppel-)Ebene ((y, z)–Ebene)

1 Ellipsoid : 2 EinschaligesHyperboloid :

3 ZweischaligesHyperboloid :


6 Kegel : 7 ElliptischesParaboloid :

8 HyperbolischesParaboloid :

9 ElliptischerZylinder :

10 HyperbolischerZylinder :

14 ParabolischerZylinder :

(Quelle: [14])

Andererseits existiert nach §31 eine erweiterte Matrix S$1 " GL(n+1 ; IR) , so daß fur x$ = S$1 ·y$gilt:

Q = {(y1, y2, . . . , yn) " IRn | (y$)t · B$1 · y$ = 0} mit B$

1 :=

.

////0

c00 c01 · · · c0n

c01 Ek 0 0... 0 %Em"k 0

c0n 0 0 0

1

22223.

Setzt man (vgl. Seite 166f.)

S$2 :=

.

/////////////////0

1 0 0 0%c01

...%c0k

Ek 0 0

c0,k+1...

c0m

0 Em"k 0

0...0

0 0 En"m

1

222222222222222223


und y$ = S$2 · z$ , dann ergibt sich weiter:

Q = {(z1, z2, . . . , zn) " IRn | (z$)t · B$2 · z$ = 0}

mit

B$2 :=

.

/////////0

d00 0 0 c0,m+1 · · · c0n

0 Ek 0 0

0 0 %Em"k 0

c0,m+1...

c0n

0 0 0

1

2222222223

.

Die Koordinatentransformation

(z1, z2, . . . , zn)t = (c01, . . . , c0k,%c0,k+1, . . . ,%c0m, 0, . . . , 0)t + S1"1 · (x1, x2, . . . , xn)t

beschreibt also wegen S1 " GL(n; IR) eine Affinitat f : IRn $ IRn in A................................................... .

Damit erhalten wir:

34.5 Satz (Affine Hauptachsentransformation)

Es sei Q eine reelle Quadrik, m = rg(A) und m$ = rg(A$) . Dann gibt es eine Affinitatf : IRn $ IRn derart, daß f(Q) 5 IRn beschrieben wird durch eine Gleichung der Form

(a) z12 + z2

2 + . . . + zk2 % zk+1

2 % zk+22 % . . .% zm

2 = 0 , falls m = m$ ist.

(b) z12 + z2

2 + . . . + zk2 % zk+1

2 % zk+22 % . . .% zm

2 = 1 , falls m + 1 = m$ ist.

(c) z12 + z2

2 + . . . + zk2 % zk+1

2 % zk+22 % . . .% zm

2 + 2 zm+1 = 0 , falls m + 2 = m$ ist.

Beweis:

Wir erhalten durch eine Affinitat: Q = {(z1, z2, . . . , zn) " IRn | (z$)t · B$2 · z$ = 0} mit

B$2 =

.

/////////0

d00 0 0 c0,m+1 · · · c0n

0 Ek 0 0

0 0 %Em"k 0

c0,m+1...

c0n

0 0 0

1

2222222223

und rg(B$2) = rg(A$) .

Typ (a): d00 = c0,m+1 = c0,m+2 = . . . = c0n = 0 ergibt sofort die Behauptung. #Typ (b): d00 .= 0 9 c0,m+1 = c0,m+2 = . . . = c0n = 0 . Ohne Beschrankung der Allgemeinheit

sei d00 < 0 . Wir setzen (z1, z2, . . . , zn) = & · (y1, y2, . . . , yn) mit & :=0%d00 und

dividieren die entstehende Gleichung durch &2 .


Typ (c): Ohne Einschrankung sei c0,m+1 .= 0; wir setzen wi = zi fur i " {1, 2, . . . , n}\{m+1}und 2 wm+1 = 2 (c0,m+1 zm+1 + c0,m+2 zm+2 + . . . + c0n zn) + d00 , d. h.:

.

///////0

w1...

wm+1...

wn

1

22222223

=

.

/////////0

1. . . 0

1c0,m+1 · · · c0n

10 . . .

1

1

2222222223

·

.

///////0

z1...

zm+1...

zn

1

22222223

+

.

///////////0

0...0

d00/20...0

1

222222222223

.

Daraus ergibt sich die in (c) angegebene (a!ne) Normalform von Q . Die obige Ko-ordinatentransformation beschreibt dann eine Affinitat.

!

34.6 Beispiel

Wir betrachten die Quadrik Q des IR3 mit der Gleichung

x2 + 5 y2 + 9 z2 + 4 x y + 2 x z + 10 y z % 2 z = 2 ;

dann lautet die beschreibende Matrix

A$ =

.

///0

%2 0 0 %10 1 2 10 2 5 5

%1 1 5 9

1

2223 =

.

///0

%2 0 0 %100 A

%1

1

2223

mit detA = %1 und daher: det A$ = %2 · det A % 1 = 1 . Also gilt direkt: rg(A) = 3 undrg(A$) = 4 . Da A weder positiv definit noch negativ definit ist, besitzt A entweder zwei positiveund einen negativen Eigenwert oder umgekehrt einen positiven und zwei negative Eigenwerte.Damit handelt es sich bei Q um ein einschaliges oder zweischaliges Hyperboloid (vgl. 2 bzw. 3 ).

Wegen pA(0) = (%1)3 ·detA = 1 und pA(5) = det

.

/04 %2 %1

%2 0 %5%1 %5 %4

1

23 < 0 sowie limt-.

pA(t) = ;

hat A genau zwei positive und genau einen negativen Eigenwert. Also stellt Q ein einschaligesHyperboloid dar.

Kapitel IX

Konvexe Mengen undlineare Optimierung

§ 35 Problemstellung

Das Hauptproblem der linearen Optimierung ist die Maximierung oder Minimierung einer Funk-tion von mehreren Veranderlichen, welche einigen Beschrankungen (Restriktionen) unterliegt;dabei werden diese sogenannte Zielfunktion und die Restriktionen als linear angenommen (oderdurch lineare Ausdrucke approximiert). Im Prinzip geht es also bei Problemen der linearen Opti-mierung immer um die optimale Aufteilung knapper Ressourcen (Kapazitaten) auf verschiedeneVerwendungszwecke oder um die optimale Kombination von Einsatzfaktoren fur vorgegebeneZwecke.53

35.1 Beispiel (Transportproblem)

Ein Baugeschaft liefere 1 000 Sacke Zement an drei Baustellen B1, B2 und B3 . Der Zement werdein zwei Lagerhallen L1 und L2 an verschiedenen Orten aufbewahrt. Die Kosten pro Sack beimTransport von der Lagerhalle Li zur Baustelle Bj , der Bedarf an Zement an den drei Baustellenund der vorhandene Lagerbestand gehen aus folgender Tabelle hervor:

Transportkosten in DM je Sack BedarfBaustelle ab Lager L1 ab Lager L2 in Sacken

B1 0,90 0,60 300B2 1,00 0,40 500B3 1,20 1,00 200

Lagerbestand 600 400 1 000

Hieraus laßt sich die Kostenfunktion Φ herleiten, wenn wir mit x die Anzahl der Sacke bezeich-nen, die von L1 nach B1 geliefert wird, und mit y die Anzahl der Sacke, die von L1 nach B2

53Naheres zur okonomischen Praxis, siehe etwa [9].

190

§ 35. PROBLEMSTELLUNG 191

geliefert wird:

Φ(x, y) = 0,9 · x + 1,0 · y + 1,2 · (600% x% y) ++ 0,6 · (300% x) + 0,4 · (500% y) + 1,0 · (200% (600% x% y))

= 0,1 · x + 0,4 · y + 700 (in DM) .

Wir suchen nun ein Minimum von Φ unter einigen Einschrankungen54 an die auftretenden Gro-ßen:

x + 0 , y + 0 ,

600% x% y + 0 ,- x + y ( 600 ,

300% x + 0 ,- x ( 300 ,

500% y + 0 ,- y ( 500 ,

%400 + x + y + 0 ,- x + y + 400 .

Die Menge K aller Punkte (x, y) " IR2 , die jeder dieser sechs Bedingungen genugen, hat etwafolgende Gestalt:

$ xy + 0

#

y

x + 0

........

........

........

........

........

........

........

........

........

........

........

........

........

........

........

........

........

........

........

........

........

........

........

........

........

........

........

........

........

........

........

........

........

........

........

........

........

........

........

........

........

........

........

........

........

........

........

........

........

........

........

........

........

........

........

........

........

........

........

........

........

........

........

.....

x ( 300

.................................................................................................................................................................................................................................................................................................................................... y ( 500

........................

........................

........................

........................

........................

........................

........................

........................

........................

........................

........................

........................

........................

........................

........................

........................

........................

........................

........................

........................

........................

........................

........................

........................

.............

x + y + 400

........................

........................

........................

........................

........................

........................

........................

........................

........................

........................

........................

........................

........................

........................

........................

........................

........................

........................

........................

..

x + y ( 600

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

K

......................................................................................................................................................................................................................................................................................................................................................................................................................

......................................................................................................................................................................................................................................................................................................................................................................................................................

......................................................................................................................................................................................................................................................................................................................................................................................................................

......................................................................................................................................................................................................................................................................................................................................................................................................................

L910

L880

L850

L770

Es sei also ein Minimum von Φ auf K 5 IR2 gesucht, d. h. ein optimaler Punkt P " K mit

Φ(P ) = minQ%K

Φ(Q) .

Dazu betrachten wir die GeradenLz := {(x, y) " IR2 | Φ(x, y) = z} ,

also: 0,1 · x + 0,4 · y + 700 = z ,- y = %14 x + 5

2 (z % 700) .

Man erkennt: Je großer der Wert von z ist, desto großer wird der y–Achsenabschnitt der Gera-den Lz . Fur einige z–Werte sind in der obigen Skizze die Geraden Lz eingezeichnet. Wir erhaltenminimale Kosten fur z = 770,– DM ; dann ist (x, y) = (300, 100) " K der einzige Punkt in K ,fur den dieses Minimum von Φ angenommen wird.

54Meistens ergeben sich diese Beschrankungen direkt aus dem praktischen Rahmen des Problems; so sprichtman z. B. von Absatz- oder Transportrestriktionen etc.

192 KAPITEL IX. KONVEXE MENGEN UND LINEARE OPTIMIERUNG

Als Losung ergibt sich damit der ”optimale Transportplan“:

Transportmenge in Sacken BedarfBaustelle ab Lager L1 ab Lager L2 in Sacken

B1 300 0 300B2 100 400 500B3 200 0 200

Lagerbestand 600 400 1 000

Um Aufgaben dieser Art genau zu beschreiben, benotigt man im allgemeinen jedoch eine großeZahl von Veranderlichen und hat eine große Zahl von Restriktionen. Dann kann man die Losungnicht mehr wie oben durch geometrische Betrachtungen erhalten. Denn bereits bei drei reel-len Variablen x, y, z werden durch die Vorzeichenbedingungen die Seiten einer Ebene im IR3

beschrieben.

Wir wollen nun die Standardform der linearen Optimierungsaufgabe beschreiben:

35.2 Definition

Vorgegeben seien zwei feste Spaltenvektoren p " IRn und b " IRm sowie eine feste MatrixA = (#ij) 1#i#m

1#j#n" Mat(m, n; IR) .

Der Grundtyp der linearen Optimierung besteht darin, einen Vektor x " IRn zu finden mit derEigenschaft55:

pt · x = Min!

unter den Nebenbedingungen (oder Restriktionen):

A · x + b + 0

und den Vorzeichenbedingungen56:x + 0 .

Dabei sei fur einen reellen Vektor v = (v1, v2, . . . , vk)t ”Nicht–Negativitat“ festgelegt durch:

v + 0 :,- vi + 0 4i=1,2,...,k .

Setzt man y := A · x + b , so erhalten wir aus den Ungleichungen bei den Nebenbedingungendie Gleichungen

A · x% y + b = 0

und zusatzlich die Vorzeichenbedingungen y + 0 .Setzen wir weiter

Hx := (x1, x2, . . . , xn, y1, y2, . . . , ym)t " IRn+m

und Hp := (p1, p2, . . . , pn, 0, 0, . . . , 0)t " IRn+m

sowie Hb := b und HA := (A |%Em) " Mat(m , m+n ; IR) ,

55Die Komponenten von p bestimmen also die Zielfunktion " des Optimierungsproblems.56Man spricht auch von Nicht–Negativitats–Bedingungen.

§ 36. KONVEXE MENGEN 193

dann ist die obige Aufgabe aquivalent zur Formulierung:

Hp t · Hx = Min!mit HA · Hx + Hb = 0 , Hx + 0 .

Wir erhalten also eine lineare Optimierungsaufgabe in m + n Variablen, wobei als Nebenbedin-gung genau m lineare Gleichungen gegeben sind.Fur theoretische Uberlegungen ist diese Darstellung der Aufgabe gunstiger, wohingegen beikonkreten Anwendungsbeispielen die Nebenbedingungen in Form von Ungleichungen vorliegen.Die beim Ubergang von Ungleichungen zu Gleichungen eingefuhrten Großen y1, y2, . . . , ym " IRnennen wir Schlupfvariablen57.

§ 36 Konvexe Mengen

36.1 Definition

Es sei V " VRIR ein reeller Vektorraum; eine Menge K 5 V heißt konvex, wenn fur allePunkte p, q " K und alle t " [ 0 ; 1 ] gilt58:

(1% t) p + t q " K .

Ist V = IRn und ! " (IRn)* eine Linearform auf V , etwa (vgl. §18 aus Lineare Algebra I):

!(x) =n'

i=1

#i xi mit x = (x1, x2, . . . , xn)t und #1, #2, . . . ,#n " IR ,

so heißt H 5 IRn ein Halbraum, wenn fur ein $ " IR gilt:

H = H(,' := {x " IRn | !(x) + $ + 0} .

(Eigentlich mußten wir von einem abgeschlossenen Halbraum H sprechen.)

36.2 Bemerkungen

(i) Jeder Halbraum H 5 IRn ist konvex.

(ii) Ist (Ki)i%I eine beliebige Familie konvexer Mengen Ki 5 V , so ist auchBi%I

Ki konvex

in V (wobei die leere Menge " definitionsgemaß auch als konvex angesehen werde).

Beweis:

zu (i): Sind p, q " H und ist t " [ 0 ; 1 ] , dann gilt stets:

!((1% t) p + t q) + $ = (1% t)!(p) + t !(q) + $

= (1% t)* +, -% [0 ; 1]

(!(p) + $* +, -

/0

) + t (!(q) + $* +, -

/0

) + 0 .

zu (ii): ist klar. #

!57Und die x1, x2, . . . , xn nennt man Struktur- oder Entscheidungsvariablen.58Dies bedeutet, daß die geradlinige Verbindungsstrecke von p nach q ganz in K liegen muß.


36.3 Folgerung

Ist eine lineare Optimierungsaufgabe nach Definition 35.2 vorgegeben, so ist die durch die Ne-benbedingungen beschriebene Menge L := {x " IRn | A · x + b + 0} konvex.

Beweis:

Mit !i(x) =n)

j=1#ij xj fur alle 1 ( i ( m gilt:

L =mC

i=1

$x " IRn

%%%n)

j=1#ij xj + $i + 0

&=

mC

i=1

H(i,'i .

!

36.4 Definition

Ist K 5 IRn eine konvexe Menge, und sind P0, P1, P2, . . . , Pm " K , dann heißt

m'

j=0

"j Pj mit "j + 0 sowiem)

j=0"j = 1

eine Konvexkombination der P0, P1, P2, . . . , Pm. Ist M 5 IRn eine beliebige Teilmenge, so nenntman59

kon(M) :=$ m'

j=0

"j Pj

%%% m " IN ,m)

j=0"j = 1 , "j + 0 , Pj " M 40#j#m

&

die konvexe Hulle von M . Also ist kon(M) die Menge aller endlichen Konvexkombinationen vonPunkten aus M . Ist M endlich, etwa M = {P0, P1, P2, . . . , Pm} , d.h. speziell, dass die PunkteP0, . . . , Pm paarweise verschieden sind, dann schreiben wir kurz:

kon(P0, P1, P2, . . . , Pm) := kon({P0, P1, P2, . . . , Pm}) .

36.5 Bemerkungen

(i) Ist K 5 IRn konvex, so gilt: kon(P0, P1, . . . , Pm) 5 K fur beliebige P0, P1, . . . , Pm " K .

(ii) Ist M 5 IRn eine beliebige Menge, so gilt: kon(M) =C

M0K0IRnK konvex

K .

Beweis:

zu (i): ergibt sich durch vollstandige Induktion nach m. #zu (ii): Wir uberlegen uns zuerst, daß kon(M) stets eine konvexe Menge ist.

Dazu seien P,Q " kon(M) beliebig ausgewahlt, jeweils als Konvexkombination

59Eine andere Schreibweise fur die konvexe Hulle von M ist: M .

§ 36. KONVEXE MENGEN 195

P =m1)j=0

"j Pj mit "j + 0 ,m1)j=0

"j = 1 und P0, P1, . . . , Pm1 " M bzw. Q =m2)

k=0µk Qk

mit µk + 0 ,m2)

k=0µk = 1 und Q0, Q1, . . . , Qm2 " M dargestellt, sowie ", µ + 0 mit

" + µ = 1 . Dann gilt:

" P + µQ =m1'

j=0

" "j Pj +m2'

k=0

µµk Qk

mit " "j + 0 und µ µk + 0 sowiem1)j=0

" "j +m2)

k=0µµk = "

m1)j=0

"j +µm2)

k=0µk = "+µ = 1,

d. h.: " P + µ Q " kon(M) .Wegen M 5 kon(M) folgt damit:

C

M0K0IRnK konvex

K 5 kon(M) .

Ist andererseits K $ 5 IRn konvex mit K $ < M , so gilt mit Teil (i) auch die umgekehrteInklusion: kon(M) 5 K $ 5

C

M0K0IRnK konvex

K .

!

36.6 Definition

(i) Eine Menge K 5 IRn heißt ein konvexes Polyeder, wenn es endlich viele (paarweise ver-schiedene) Punkte P0, P1, . . . , Pm " IRn gibt mit K = kon(P0, P1, . . . , Pm) .

(ii) Eine Menge S 5 IRn heißt ein k-Simplex, wenn genau k+1 Punkte P0, P1, P2, . . . , Pk " IRn

existieren, die affin unabhangig sind und fur die gilt: S = kon(P0, P1, P2, . . . , Pk) .

!0-Simplex

!!...........................................................................................................

1-Simplex! !

!.........................................................................................................................................................

........................................................................................................................................................................................................................................................

2-Simplex! !

!!

.................................................................................................................................................................................................................................................................................................................................................................................................................

......

......

......

......

......

................................................

................................................

3-Simplex

(iii) Gilt speziell: S = kon(P0, P1, P2, . . . , Pk) mit P0 = 0 und Pi = eit fur alle 1 ( i ( k ,

so heißt S das Standard–k-Simplex im IRn.

(iv) Bildet S = kon(P0, P1, P2, . . . , Pk) ein k-Simplex im IRn, so heißen die Punkte P0, P1, P2, . . .. . . , Pk auch die Ecken von S.Nach §32 gibt es zu jedem P " S genau einen Vektor ("0, "1, "2, . . . ,"k) " IRk+1 mit

"i + 0 undk)

i=0"i = 1 sowie P =

k)i=0

"i Pi . Dieses (k + 1)-Tupel ("0, "1, "2, . . . ,"k)

bezeichnet man als die baryzentrischen60 Koordinaten von P .

36.7 Lemma

Ist K = kon(P0, P1, . . . , Pm) 5 IRn ein konvexes Polyeder, so ist K abgeschlossen und be-schrankt, also kompakt.

60Die baryzentrischen Koordinaten beziehen sich auf den Schwerpunkt des k-Simplex.



Wir setzen61 r := max0#j#m

!Pj! ; dann ist die Menge Kr(0) := {x " IRn | !x! ( r} konvex (denn

aus x, y " Kr(0) und t " [ 0 ; 1 ] folgt: !(1% t)x+ t y! ( (1% t) !x!+ t !y! ( (1% t) r+ t r = r )und enthalt die Punkte P0, P1, . . . , Pm . Somit gilt: K 5 Kr(0) , und K ist daher beschrankt.Ferner ist K auch abgeschlossen. Sei dazu (Qk)k%IN eine Folge in K mit lim

k-.Qk = Q " IRn ;

dann gilt fur jedes k " IN : Qk =m)

j=0"k,j Pj mit 0 ( "k,j ( 1 und

m)j=0

"k,j(")= 1. Die beschrankte

Zahlenfolge ("k,0)k%IN besitzt eine konvergente Teilfolge ("kl,0)l%IN (da IR vollstandig ist), dieFolge ("kl,1)l%IN hat eine konvergente Teilfolge ("ml,1)l%IN , . . . usw. So fortfahrend erhalten wireine Teilfolge (nl)l%IN derart, daß alle Folgen ("nl,j)l%IN fur jedes 0 ( j ( m in IR konvergieren.Damit gilt:

Q = limk-.

Qk = liml-.

Qnl = liml-.

m'

j=0

"nl,j Pj =m'

j=0

( liml-.

"nl,j)Pj " K

wegen liml-.

"nl,j " [ 0 ; 1 ] fur alle 0 ( j ( m undm)

j=0liml-.

"nl,j = liml-.

m)j=0

"nl,j(")= 1 . !

36.8 Satz

Ist K 5 IRn konvex und kompakt sowie Q " IRn \K , dann existiert ein Funktional ! " (IRn)*

mit der Eigenschaft:!(P ) > !(Q) fur alle P " K .

Beweis:

Fur d(x) := !x % Q! ist wegen |d(x) % d(y)| = |!x % Q! % !y % Q!| ( !x % y! die Funktiond : IRn $ IR stetig. Also nimmt d auf K ein Minimum an, d. h. es existiert ein Punkt M " Kmit !M % Q! ( !x % Q! fur alle x " K . Wir betrachten nun eine Abbildung ! : IRn $ IRmit !(x) := &x , M %Q' ; dann ist ! " (IRn)* (also linear), und fur beliebiges P " K und allet " [ 0 ; 1 ] gilt wegen M + t (P %M) " K :

!M %Q!2 ( !M + t (P %M)%Q!2

= !M %Q!2 + t2 !P %M!2 + 2 t &M %Q , P %M',- 0 ( t2 !P %M!2 + 2 t &M %Q , P %M' 4t% [0 ; 1] .

Daraus folgt: 0 ( t !P %M!2 + 2 &M %Q , P %M' fur alle t " ] 0 ; 1 ] und damit:

0 ( &M %Q , P %M' = !(P )% !(M) ,- !(P ) + !(M) .

Wegen Q " IRn \ K ist aber !(M)% !(Q) = &M %Q , M %Q' = !M %Q!2 > 0 . !61Mit % · % bezeichnen wir hier die vom kanonischen Skalarprodukt auf dem IRn induzierte euklidische Norm;

d. h. wir setzen %x% :=#!x, x" =

&x1

2 + x22 + . . . + xn

2 . Und K$(P ) sei im folgenden die abgeschlossene

Kugel um den Mittelpunkt P ' IRn mit Radius " > 0 .

§ 37. EXTREMALPUNKTE 197

§ 37 Extremalpunkte

Ist S := kon(P0, P1, P2, . . . , Pk) ein k-Simplex im IRn und P eine Ecke von S , so bleibt dieMenge S \ {P} konvex. Ist namlich ohne Beschrankung der Allgemeinheit P = P0 , und sindQ,R " S \ {P0} , so gilt fur die baryzentrischen Koordinaten von Q bzw. R :

Q =k'

i=0

"i Pi mit 0 ( "0 < 1 und R =k'

i=0

µi Pi mit 0 ( µ0 < 1 .

Daraus folgt fur alle t " [ 0 ; 1 ] :

(1% t)Q + t R =k'

i=0

((1% t)"i + t µi)Pi mit 0 ( (1% t) "0 + t µ0 < 1 ,

d. h.: (1% t)Q + t R " S \ {P0} .Ist P " S jedoch keine Ecke von S , dann ist S \ {P} nicht mehr konvex; denn sonst wareS \ {P} eine kleinere konvexe Menge, die alle Punkte P0, P1, P2, . . . , Pk enthalten wurde (imWiderspruch zur Definition der konvexen Hulle; vgl. Bemerkung 36.5(ii)).

Dies fuhrt zu:

37.1 Definition

Es sei K 5 IRn eine konvexe Menge. Ein Punkt P " K heißt extremal oder ein Extremalpunkt,wenn K \ {P} konvex ist.

37.2 Bemerkung

Ist K = kon(P0, P1, . . . , Pm) ein konvexes Polyeder im IRn und P " K ein extremaler Punkt,so gilt stets: P " {P0, P1, . . . , Pm} .

Extremalpunkte von konvexen Polyedern heißen daher auch Ecken des Polyeders.

Beweis:

Ist P " K \ {P0, P1, . . . , Pm} , etwa P =m)

j=0"j Pj mit 0 ( "j ( 1 und

m)j=0

"j = 1 , so existieren

mindestens zwei Koordinaten, die großer als Null sind. Ohne Einschrankung seien dies "0 > 0und "1 > 0 ; dann gilt:

Q0 := ("0 + "1) P0 +m'

j=2

"j Pj " K \ {P} und Q1 := ("0 + "1) P1 +m'

j=2

"j Pj " K \ {P} ,

zugleich aber auch:

"0

"0 + "1Q0+

"1

"0 + "1Q1 = "0 P0+

"0

"0 + "1

m'

j=2

"j Pj +"1 P1+"1

"0 + "1

m'

j=2

"j Pj =m'

j=0

"j Pj = P .

Also kann K \ {P} nicht konvex sein. !


37.3 Lemma

Es sei K 5 IRn konvex und ! " (IRn)* eine Linearform; ferner sei ein x0 " K gegeben mit) := !(x0) = min {!(x) | x " K} . Ist dann K $ := K 3 {x " IRn | !(x) = )} und P einExtremalpunkt von K $ , so ist P auch Extremalpunkt von K .

Beweis:

Angenommen, P ware kein Extremalpunkt von K, d. h. K \ {P} nicht konvex; dann existiertenP1, P2 " K und 0 < " < 1 mit P = " P1+(1%") P2. Da P Extremalpunkt von K $ ist, liegen nichtzugleich beide Punkte P1, P2 in K $ . Ohne Beschrankung der Allgemeinheit sei P1 /" K $ , also!(P1) > ) . Wegen !(P2) + ) folgt der Widerspruch: ) = !(P ) = " !(P1)+(1%") !(P2) > ) .

!

37.4 Satz

Es sei der Grundtyp einer linearen Optimierungsaufgabe vorgegeben, und es sei K 5 IRn

die durch die Nebenbedingungen und die Vorzeichenbedingungen beschriebene konvexe Menge,d. h.:

K := L 3 L$ =m+nC

i=1

H(i,'i

mit L =mB

i=1H(i,'i und !i(x) =

n)j=1

#ij xj fur alle 1 ( i ( m sowie L$ =m+nB

i=m+1H(i,0 mit

!i(x) = xi"m fur jedes m + 1 ( i ( m + n . Ist dann K .= " kompakt, so gilt:

(1) K besitzt mindestens einen Extremalpunkt.

(2) Ist Φ " (IRn)* ein lineares Funktional, dann existiert ein extremaler Punkt P " K mitΦ(P ) = min

Q%KΦ(Q) .

Ein solcher Punkt P heißt optimal (bezuglich der Zielfunktion Φ).

Beweis:

zu (1): Es sei K0 := K . Wegen der Stetigkeit von !1 : IRn $ IR existiert auf K0 einMinimum )1 := min

P%K0

!1(P ) , und es gilt: )1 + %$1 . Definieren wir

K1 := K03 {P " IRn | !1(P ) = )1} , dann ist K1 abgeschlossen und beschrankt, alsokompakt, mit K1 .= " . Daher existiert wieder ein )2 := min

P%K1

!2(P ) , und dabei ist

)2 + %$2 . Verfahrt man so induktiv weiter, dann erhalten wir:

Km+n = Km+n"1 3 {P " IRn | !m+n(P ) = )m+n}= {x " IRn | !1(x) = )1 , !2(x) = )2 , . . . , !m+n(x) = )m+n} .= " .

Somit ist Km+n der Losungsraum eines inhomogenen linearen Gleichungssystems.Ist W der Losungsraum des zugehorigen homogenen Systems und P " Km+n einbeliebiger Punkt, dann gilt: Km+n = P +W . Wegen der Kompaktheit von Km+n muß

§ 38. BESTIMMUNG OPTIMALER PUNKTE 199

W = {0} sein (besteht also nur aus der trivialen Losung), so daß gilt: Km+n = {P} .Damit ist P Extremalpunkt von Km+n, und Lemma 37.3 liefert sukzessive, daß Pauch Extremalpunkt von K ist.

zu (2): Wir setzen ) := minP%K

Φ(P ) ; dann ist K $ = K 3 {x " IRn | Φ(x) = )} kompakt und

K $ .= " . Ferner gilt:

K $ =m+nC

i=1

H(i,'i 3 {x " IRn | Φ(x) + )} 3 {x " IRn | Φ(x) ( )}

=m+nC

i=1

H(i,'i 3 H!,"% 3H"!,% .

Nach Teil (1) besitzt K $ einen extremalen Punkt P , der nach Lemma 37.3 auchExtremalpunkt von K ist.

!

§ 38 Bestimmung optimaler Punkte

Ist K =m+nBi=1

H(i,'i nichtleer und kompakt, so konnen wir uns bei der Suche nach optimalen

Punkten auf die Extremalpunkte von K beschranken. Wir zeigen zunachst:

38.1 Lemma

Es sei M 5 IRn ein affiner Unterraum des IRn mit dimIR M + 1 ; ferner sei

KM :=m+nC

i=1

{x " M | !i(x) + $i + 0} .

Ist dann P " KM ein Extremalpunkt von KM , so gibt es ein i " {1, 2, . . . ,m + n} mit !i .= 0und !i(P ) + $i = 0 .

Beweis:

Wir lassen alle !i mit !i(x) + $i = 0 fur alle x " M weg; dadurch wird KM nicht verandert.Deshalb konnen wir ohne Beschrankung der Allgemeinheit voraussetzen, daß zu jedem Indexi " {1, 2, . . . ,m + n} ein Punkt x " M mit !i(x) + $i > 0 existiert.Angenommen, es ware nun !i(P ) + $i > 0 fur alle 1 ( i ( m + n . Dann existierte einMinimum - := min

1#i#m+n!i(P ) + $i > 0 , und wegen der Stetigkeit aller !i gabe es ein ( > 0

mit62 !i(K,(P )) 5 K!(!i(P )) fur jedes 1 ( i ( m + n , d. h.: |!i(Q) % !i(P )| ( - fur alleQ " M mit !P %Q! ( ( . Also galte fur ein solches Q stets:

%- ( !i(Q)% !i(P ) ( - ,- !i(Q) + !i(P )% - + %$i , d. h.: K,(P ) 5 KM .

Somit ware P innerer Punkt einer in K,(P ) und damit auch ganz in KM gelegenen Strecke.Daher ist P nicht extremal im Widerspruch zur Voraussetzung. !

62Hier ist die Kugel K%

I#i(P )

Jalso das symmetrische Intervall um #i(P ) ' IR der Lange 2 $ > 0 .


38.2 Satz

Es sei K :=m+nBi=1

H(i,'i ; dann sind fur P " K folgende Aussagen aquivalent:

a) P ist ein Extremalpunkt von K .

b) Es existieren Indizes i1, i2, . . . , in " {1, 2, . . . ,m + n} derart, daß !i1 , !i2 , . . . ,!in alsVektoren aus (IRn)* linear unabhangig sind, und es gilt:

!i1(P ) + $i1 = 0 9 !i2(P ) + $i2 = 0 9 . . . 9 !in(P ) + $in = 0 .

Beweis:

”a)-b)“: 1. Schritt: Wir wenden Lemma 38.1 auf M0 = IRn und K0 := KM0 = K an. Danngibt es ein i1 " {1, 2, . . . ,m + n} mit !i1 .= 0 und !i1(P ) + $i1 = 0 .

2. Schritt: Wir setzen einfach M1 := {x " IRn | !i1(x) + $i1 = 0} und dannK1 := KM1 = K0 3M1 . Wegen !i1 .= 0 gilt: dimIR M1 = n % 1 . Au-ßerdem ist P auch Extremalpunkt von K1 , denn aus der Konvexitat vonK0 \ {P} folgt die von K1 \ {P} . Lemma 38.1 liefert die Existenz einesIndex i2 " {1, 2, . . . ,m+n}\{i1} mit !i2 |M1 .= 0 und !i2(P )+$i2 = 0.

3. Schritt: Wir setzen M2 := {x " M1 | !i2(x)+$i2 = 0} und K2 = K13M2 . Wegen!i2 |M1 .= 0 gilt: dimIR M2 = n% 2 , und analog ist P ein Extremalpunktvon K2 .

Fahren wir so immer weiter fort, dann folgt als(n + 1)-ter Schritt: Es gilt:

Mn := {x " Mn"1 | !in(x) + $in = 0} =nC

k=1

{x " IRn | !ik(x) + $ik = 0}

mit dimIR Mn = n % n = 0 und P " Mn , also: Mn = {P} . Da P dieeinzige Losung des linearen Gleichungssystems

n'

j=1

#ik,j xj + $ik = 0 fur k = 1, 2, . . . , n

ist, sind die Linearformen !i1 , !i2 , . . . ,!in mit !ik(x) =n)

j=1#ik,j xj

linear unabhangig.

”b)- a)“: Wir setzen K0 := K ,

K1 := K0 3 {x " IRn | !i1(x) + $i1 = 0} ,

K2 := K1 3 {x " IRn | !i2(x) + $i2 = 0} ,...

Kn := Kn"1 3 {x " IRn | !in(x) + $in = 0} = {P} .

Dann ist P Extremalpunkt von Kn , also gemaß Lemma 37.3 auch Extremalpunktvon Kn"1 . Und n-malige Anwendung dieses Lemmas liefert schließlich, daß P Extre-malpunkt von K ist.

!


38.3 Folgerung

Ist K =m+nBj=1

H(j ,'j kompakt, so besitzt K hochstens!

m + n

n

"

Extremalpunkte.

Beweis:

Nach Satz 38.2 besitzt K hochstens so viele Extremalpunkte wie n-elementige Teilmengen einer(m + n)-elementigen Menge existieren. (Vgl. Bemerkung 52.2 aus Algebra I.) # !

38.4 Bemerkung

Die bisherigen Uberlegungen ergeben fur den Fall, daß K =m+nBj=1

H(j ,'j nichtleer und beschrankt

ist, folgendes ”naive“ Losungsverfahren:

(A) Bestimme alle linear unabhangigen Teilmengen

{!i1 , !i2 , . . . ,!in} 5 {!1, !2, . . . ,!m+n}

und berechne jeweils die Losungen P1, P2, . . . , Pk der zugehorigen linearen Gleichungssy-steme

!il(x) + $il = 0 fur l = 1, 2, . . . , n .

Dabei gibt es hochstens k (!

m + n

n

"

solche Gleichungssysteme.

(B) Bestimme alle diejenigen Punkte Pk1 , Pk2 , . . . , Pkr mit r ( k , die zur ”Losungsmen-ge“ K gehoren (durch Einsetzen in die restlichen Ungleichungen !j(Pk#) + $j + 0 furdie Indizes j " {1, 2, . . . ,m+n} \ {i1, i2, . . . , in} , wenn jedes Pk# durch die Linearformen!i1 , !i2 , . . . ,!in bestimmt wurde).

(C) Berechne nun Φ(Pk1),Φ(Pk2), . . . ,Φ(Pkr) und suche einen minimalen dieser endlich vielenWerte. Der zugehorige Punkt Pk# ist dann optimal bezuglich der Zielfunktion Φ .

Praktisch ist diese Methode63 allerdings kaum anwendbar; so hat man z. B. fur n = m = 10

bereits!

m + n

n

"

=!

2010

"

=20!

10! · 10!= 184 756 mogliche Extremalpunkte.

Gesucht ist also ein Verfahren, das solche Ecken ”ansteuert“, die mit großerer Wahrscheinlichkeitoptimal sind.

38.5 Lemma

Ist K 5 IRn konvex, Φ " (IRn)* ein Funktional, P " K und - > 0 mit Φ(P ) ( Φ(x) fur allex " K!(P ) 3K , so gilt:

Φ(P ) ( Φ(y) fur alle y " K .

63Man spricht hierbei auch von vollstandiger Enumeration.



Es sei y " K mit y .= P ; dann wahle 0 < s ( -

!y % P! und betrachte ys := (1% s) P + s y .

Wegen !ys % P! = s !y % P! ( - und der Konvexitat von K ist ys " K!(P ) 3K . Es folgt:(1% s) Φ(P ) + sΦ(y) = Φ(ys) + Φ(P ) , also: Φ(y) + Φ(P ) . !

38.6 Bemerkung

Ist K ein konvexes Polyeder im IRn , so ist eine Ecke P " K genau dann optimal bezuglich Φ ,wenn fur alle Ecken Q " K gilt: Φ(P ) ( Φ(Q) .

Dabei genugt es, Ecken Q zu untersuchen, fur welche die Verbindungsstrecke von P nach Q,

[P ,Q ] := {(1% t)P + t Q | 0 ( t ( 1} 5 K ,

keine Punkte aus anderen Verbindungsstrecken von Eckpunkten aus K enthalt.

Beweis:

Angenommen, es gebe Ecken Q1, Q2 " K und einen Punktx " [P ,Q ] 3 [Q1 , Q2 ] mit Φ(P ) ( Φ(Qi) fur i = 1, 2 ; dannist x = (1 % t)Q1 + t Q2 mit einem t " [ 0 ; 1 ] , und es folgt(wieder mit der Linearitat von Φ ):

Φ(x) = (1% t) Φ(Q1) + t Φ(Q2) + Φ(P ) .

Außerdem ist x = (1% s) P + s Q fur ein s " ] 0 ; 1 [ , also gilt:

Φ(x) = (1% s) Φ(P ) + sΦ(Q) + Φ(P )

oder sΦ(Q) + sΦ(P ) ,- Φ(Q) + Φ(P ) .

!

Beispiel fur K 5 IR2 :

!

! !!

!

....................................

....................................

........................................................................................................................................................

....................................

....................................

....................................

....................................

......................................................................................................

......................................................................................................................................................................................................................................................................................................................................................................................

............................

............................

............................

............................

P

Q$

Q1

Q2

Q

38.7 Definition

Es sei K 5 IRn ein konvexes Polyeder und P,Q zwei Ecken von K . Die Verbindungsstrecke[P ,Q ] heißt eine Kante von K, wenn K \ [P ,Q ] konvex ist. Ferner heißen P und Q dannbenachbarte Ecken.

Implizit haben wir bisher daran gedacht, daß die Menge K :=m+nBj=1

H(j ,'j ein konvexes Polyeder

ist, wenn K nichtleer und zugleich beschrankt ist. Wir wollen dies nun auch explizit zeigen:

38.8 Lemma

Ist K .= " beschrankt, so ist K stets die konvexe Hulle ihrer Extremalpunkte, also speziell einkonvexes Polyeder.



Es seien P1, P2, . . . , Pk mit k (Im+n

n

Jdie Extremalpunkte von K sowie L := kon(P1, P2, . . . , Pk).

Da K konvex ist, gilt bereits: L 5 K (siehe Bemerkung 36.5(i)). Angenommen, es existiertenun ein Q " K \ L . Gemaß Satz 36.8 wahlen wir ein ! " (IRn)* aus mit !(Q) < !(x) furalle x " L . Wir setzen $ := min

x%K!(x) ( !(Q) und betrachten die kompakte konvexe Menge

K $ := K 3 {x " IRn | !(x) = $} . Nach Satz 37.4 (angewandt auf K $ = K 3H(,"' 3H"(,' )besitzt K $ dann mindestens einen extremalen Punkt P . Laut Lemma 37.3 ist dieses P auchExtremalpunkt von K. Damit ist jedoch P " L im Widerspruch zu $ = !(P ) ( !(Q) < !(x)fur alle x " L . !

38.9 Bemerkung

Damit erhalten wir folgenden Losungsweg zur Bestimmung eines optimalen Punktes fur den

Fall, daß K =m+nBj=1

H(j ,'j nichtleer und beschrankt ist:

(i) Starte mit einer Ecke P der ”Losungsmenge“ K und berechne den Wert Φ(P ) .

(ii) Berechne Φ(Q) fur alle zu P benachbarten Ecken Q " K .

(iii) Gilt: Φ(P ) ( Φ(Q) fur alle benachbarten Ecken Q , so ist P schon optimal.

(iv) Existiert anderenfalls eine benachbarte Ecke Q mit Φ(Q) < Φ(P ) , dann setze P := Qund beginne bei (i) von vorne.

Dies ist die Idee fur das Simplex–Verfahren, das erstmals G. B. Dantzig64 im Jahre 1947 ent-worfen hat. Bevor wir den Algorithmus notieren, wollen wir uns uberlegen, wie man von einemextremalen Punkt P ausgehend eine benachbarte Ecke Q erreichen kann.

Analog zu Lemma 37.3 und Satz 37.4 zeigen wir:

38.10 Lemma

Es sei K 5 IRn ein konvexes Polyeder und ! " (IRn)* eine Linearform; ferner existiere einx0 " K mit ) := !(x0) = min {!(x) | x " K} , und es sei K $ = K 3 {x " IRn | !(x) = )} . Istdann [ P ,Q ] eine Kante von K $ , so ist [ P ,Q ] auch eine Kante von K .

Beweis:

Angenommen, [ P ,Q ] ware keine Kante von K , d. h. K \ [P ,Q ] nicht konvex; dann existiertenP1, P2 " K \ [P ,Q ] und ein " " ] 0 ; 1 [ mit x = " P1 + (1% ")P2 " [P ,Q ] . Da [ P ,Q ] Kantevon K $ ist, liegen nicht beide Punkte P1, P2 in K $. Ohne Einschrankung sei P1 /" K $ , also!(P1) > ) . Wegen !(P2) + ) folgt der Widerspruch: ) = !(x) = " !(P1) + (1% ") !(P2) > ) .

!64George Bernard Dantzig, amerikanischer Mathematiker (!08.11.1914)


38.11 Satz

Es sei K =m+nBj=1

H(j ,'j nichtleer und beschrankt, also ein konvexes Polyeder im IRn . Ferner seien

{!i1 , !i2 , !i3 , . . . ,!in} und {!i2 , !i3 , . . . ,!in+1} linear unabhangige Mengen, P,Q " K mit

!i1(P ) + $i1 = !i2(P ) + $i2 = !i3(P ) + $i3 = . . . = !in(P ) + $in = 0sowie !i2(Q) + $i2 = !i3(P ) + $i3 = !i4(P ) + $i4 = . . . = !in+1(P ) + $in+1 = 0 .

Dann sind P und Q benachbarte Ecken.

Beweis:

Nach Satz 38.2 sind P und Q Ecken von K . Wir definieren jetzt:

K1 := K ,

K2 := K1 3 {x " IRn | !i2(x) + $i2 = 0} ,

K3 := K2 3 {x " IRn | !i3(x) + $i3 = 0} ,...

Kn := Kn"1 3 {x " IRn | !in(x) + $in = 0}und M := {x " IRn | !i2(x) + $i2 = !i3(x) + $i3 = . . . = !in(x) + $in = 0} .

Wegen der linearen Unabhangigkeit von !i2 , !i3 , . . . ,!in stellt M eine Gerade im IRn dar; undes gilt: Kn = K 3M . Ferner ist P " M und Q " M ; da P und Q Ecken von K sind, folgt:Kn = [P ,Q ] . Daher ist [P ,Q ] eine Kante von Kn , also mit Lemma 38.10 auch von Kn"1 unddamit schließlich eine Kante von K1 = K . !

§ 39 Das Simplex–Verfahren

In Bemerkung 38.9 und Satz 38.11 wird beschrieben, wie wir zu einer Losung der linearenOptimierungsaufgabe gemaß Definition 35.2 kommen konnen. Wir starten hierzu mit einerbeliebigen Ecke P der nichtleeren, kompakten Menge K . Nach Satz 38.2 existieren Indizesi1, i2, . . . , in " {1, 2, . . . ,m + n} derart, daß !i1 , !i2 , . . . ,!in linear unabhangige Funktionalesind mit !i" (P )+$i" = 0 fur jedes 1 ( ' ( n . Wegen dimIR(IRn)* = dimIR HomIR(IRn, IR) = n(nach §18) bilden die !i1 , !i2 , . . . ,!in eine Basis des Dualraumes (IRn)* . Um nun von P zueiner benachbarten Ecke zu gelangen, muß eines dieser linearen Funktionale !ik ausgetauschtwerden (vgl. Satz 38.11), so daß wieder eine linear unabhangige Familie entsteht. Seien da-zu !j1 , !j2 , . . . ,!jm diejenigen Linearformen, die nicht fur P benotigt werden. Dann existierenSkalare aµ# " IR mit

!jµ =n'

#=1

aµ# !i" fur alle 1 ( µ ( m .

Ferner gibt es Koeffizienten c1, c2, . . . , cn " IR mit

Φ =n'

#=1

c# !i" .

§ 39. DAS SIMPLEX–VERFAHREN 205

Diese Daten einschließlich der Funktionswerte an der Stelle P fassen wir im sogenannten Ecken–Tableau von P zusammen:

P !i1 !i2 · · · !in Werte!j1 a11 a12 · · · a1n !j1(P ) + $j1

!j2 a21 a22 · · · a2n !j2(P ) + $j2...

......

......

!jm am1 am2 · · · amn !jm(P ) + $jm

Φ c1 c2 · · · cn Φ(P )

Wie kann man diesem Tableau aber ansehen, ob P ein optimaler Punkt ist? — Mit obigenBezeichnungen ergibt sich:

39.1 Satz

(1) Gilt: c1 + 0 , c2 + 0 , . . . , cn + 0 , dann ist P optimal bezuglich Φ .

(2) Ist c#0 < 0 fur ein '0 " {1, 2, . . . , n} , so gilt: Φ(P ) > Φ(x) fur alle Punkte

x " M+ := {y " IRn | !i" (y) + $i" = 0 4#%{1,2,...,n}\{#0} 9 !i"0(y) + $i"0

+ 0} ,

die von P verschieden sind.

Beweis:

Fur alle x " IRn gilt zunachst:

Φ(x)% Φ(P ) =n'

#=1

c# (!i" (x)% !i" (P )) =n'

#=1

c# (!i" (x) + $i" ) .

zu (1): Ist x " K , d. h. !i" (x)+$i" + 0 fur alle 1 ( ' ( n , so folgt direkt: Φ(x)%Φ(P ) + 0.zu (2): Ist x " M+ \ {P} , dann gilt: Φ(x)% Φ(P ) = c#0 (!i"0

(x) + $i"0) < 0 .

!

Jetzt ist es moglich, daß dieser ”Suchstrahl“ M+ mit K nur genau den Punkt P gemeinsam hat.

39.2 Definition

Es sei P eine Ecke von K =m+nBj=1

H(j ,'j ; dann heißt P einfach (oder nicht–entartet), wenn

!j(P ) + $j = 0 fur genau n Indizes j " {1, 2, . . . ,m + n} erfullt ist. Ansonsten heißt Peine mehrfache (oder entartete) Ecke.

Dem Ecken–Tableau kann man nun entnehmen, ob P eine einfache Ecke von K ist. Dies ist nam-lich genau dann der Fall, wenn in der Werte–Spalte des Ecken–Tableaus (abgesehen von Φ(P ) )


keine Null auftaucht. Ist eine solche einfache Ecke P nicht optimal, so existiert eine benachbarteEcke Q " K mit Φ(Q) < Φ(P ) (vgl. §38). Wie erhalt also man dieses Q ?

Man muß hierfur ein Funktional der Basis austauschen. Sei dazu '0 " {1, 2, . . . , n} wie obenmit c#0 < 0 . Wir betrachten den Suchstrahl M+ . Da P einfach ist, gibt es einen Punktz " K 3M+ \ {P} . Wir betrachten fur t + 0 ein

zt := P + t (z % P ) " M+

und beobachten die Werte !jµ(zt) + $jµ fur jedes 1 ( µ ( m . Weil P nicht–entartet ist, giltweiter:

!jµ(z0) + $jµ > 0 fur alle 1 ( µ ( m .

Also existiert ein Parameter t0 > 0 und ein Index µ0 " {1, 2, . . . ,m} mit

!jµ0(zt0) + $jµ0

= 0 .

Wir berechnen dann, fur welches µ der Wert !jµ(zt) + $jµ zuerst verschwindet. Dazu schreibenwir:

!jµ =n'

#=1

aµ# !i" fur jedes 1 ( µ ( m .

Ware aµ#0 = 0 fur alle 1 ( µ ( m , so galte:

!jµ(zt) =n'

#=1# '=#0

aµ# !i" (zt) = %n'

#=1# '=#0

aµ# $i" = %n'

#=1

aµ# $i" = !jµ(P ) + %$jµ

fur alle t + 0 . Also ist M+ 5 K im Widerspruch zur Kompaktheit von K .

Sei daher aµ0#0 .= 0 fur (mindestens) ein µ0 " {1, 2, . . . ,m} . Nach dem Austauschlemma 3.8 (ausLineare Algebra I) bilden die Linearformen !i1 , !i2 , . . . ,!i"0&1 , !jµ0

, !i"0+1 , !i"0+2 , . . . ,!in

eine Basis von (IRn)* . Also existiert genau ein

Q " {y " IRn | !i" (y) + $i" = 0 4#%{1,2,...,n}\{#0} } mit !jµ0(Q) + $jµ0

= 0 .

Damit erhalten wir:

!jµ0(P ) =

n'

#=1

aµ0# !i" (P ) = %n'

#=1

aµ0# $i" und

!jµ0(Q) =

n'

#=1

aµ0# !i" (Q) = aµ0#0 !i"0(Q)%

n'

#=1# '=#0

aµ0# $i" ,

also: aµ0#0 (!i"0(Q) + $i"0

) = !jµ0(Q) + aµ0#0 $i"0

+n'

#=1# '=#0

aµ0# $i"

= !jµ0(Q)% !jµ0

(P ) = %(>0, -* +

!jµ0(P ) + $jµ0

) < 0

,- !i"0(Q) + $i"0

= %!jµ0

(P ) + $jµ0

aµ0#0

. (6)


Es folgt:Q " M+ \ {P} ,- !i"0

(Q) + $i"0> 0

,- aµ0#0 < 0 .

Es existiert also mindestens ein Index µ " {1, 2, . . . ,m} mit aµ#0 < 0 , und der zugehorige,eindeutig bestimmte Punkt Qµ " M+ mit !jµ(Qµ) + $jµ = 0 ist genau dann eine zu Pbenachbarte Ecke von K , wenn der sogenannte charakteristische Quotient

.µ :=!jµ(P ) + $jµ

aµ#0

< 0

maximal wird bezuglich der Teilmenge {µ " {1, 2, . . . ,m} | aµ#0 < 0} . Ist nun µ0 ein solcherIndex mit maximalem .µ0 , so tauschen wir !i"0

gegen !jµ0aus.

Dazu mussen wir die Koeffizienten aµ#$ und c#

$ bezuglich der neuen Basis berechnen, d. h. be-zuglich der Basis (!i1 , !i2 , . . . ,!i"0&1 , !jµ0

, !i"0+1 , !i"0+2 , . . . ,!in) des (IRn)* . Wegen aµ0#0 .= 0

und !jµ0=

n)#=1

aµ0# !i" ergibt sich:

!i"0= % aµ01

aµ0#0

!i1 % . . . % aµ0,#0"1

aµ0#0

!i"0&1 +1

aµ0#0

!jµ0% aµ0,#0+1

aµ0#0

!i"0+1 % . . . % aµ0n

aµ0#0

!in

und fur jedes µ " {1, 2, . . . ,m} \ {µ0} :

!jµ =5aµ1 %

aµ01

aµ0#0

aµ#0

6!i1 + . . . +

5aµ,µ0"1 %

aµ0,#0"1

aµ0#0

aµ#0

6!i"0&1 +

+aµ#0

aµ0#0

!jµ0+

5aµ,#0+1 %

aµ0,#0+1

aµ0#0

aµ#0

6!i"0+1 + . . . +

5aµn %

aµ0n

aµ0#0

aµ#0

6!in .

Entsprechend folgt fur die Zielfunktion:

Φ =5c1 %

aµ01

aµ0#0

c#0

6!i1 + . . . +

5c#0"1 %

aµ0,#0"1

aµ0#0

c#0

6!i"0&1 +

+c#0

aµ0#0

!jµ0+

5c#0+1 %

aµ0,#0+1

aµ0#0

c#0

6!i"0+1 + . . . +

5cn %

aµ0n

aµ0#0

c#0

6!in .

In dieser Situation heißt das Element aµ0#0 ein Pivot65, die '0-te Spalte heißt Pivotspalte unddie µ0-te Zeile Pivotzeile.

39.3 Bemerkung (Simplex–Verfahren)

Fassen wir alle Ergebnisse zusammen, so erhalt man fur den Fall, daß P eine einfache, nicht–optimale Ecke des beschrankten, nichtleeren Bereichs K ist:

(A) Man stelle das Ecken–Tableau von P auf und kontrolliere, ob in der Werte–Spalte alleWerte !jµ(P ) + $jµ ungleich Null sind; nur dann ist P eine einfache Ecke.

(B) Wahle einen negativen Koeffizienten c#0 in der Zeile von Φ ; dann wird '0 der Index derPivotspalte.

65Franz. pivot = Angel; Dreh-, Angelpunkt; Achse


(C) Berechne fur alle in der Pivotspalte stehenden Elemente aµ#0 , die negativ sind, den cha-rakteristischen Quotienten

.µ =!jµ(P ) + $jµ

aµ#0

.

(D) Eine Zeile des Index µ0 mit maximalem .µ0 kann als Pivotzeile gewahlt werden. Wirnehmen also aµ0#0 als Pivot. Die dadurch festgelegte, zu P benachbarte Ecke Q ist wiedereinfach, wenn der maximale Wert von .µ genau einmal angenommen wird.

(E) Ersetze die Koeffizienten aµ# und c# im Tableau von P gemaß folgender Regeln:

(1) beim Pivot durch: aµ0#0$ =

1aµ0#0

.

(2) in der Pivotzeile durch:

(2.1) aµ0#$ = % aµ0#

aµ0#0

4#%{1,2,...,n}\{#0} ,

(2.2) !i"0(Q) + $i"0

= %!jµ0

(P ) + $jµ0

aµ0#0

.

(3) in der Pivotspalte durch:

(3.1) aµ#0$ =

aµ#0

aµ0#0

4µ%{1,2,...,m}\{µ0} ,

(3.2) c#0$ =

c#0

aµ0#0

.

(4) Fur alle anderen µ " {1, 2, . . . ,m} \ {µ0} und ' " {1, 2, . . . , n} \ {'0} setze man:

(4.1) aµ#$ = aµ# %

aµ0#

aµ0#0

· aµ#0 ,

(4.2) c#$ = c# %

aµ0#

aµ0#0

· c#0 ,

(4.3) !jµ(Q) + $jµ = !jµ(P ) + $jµ % aµ#0 ·!jµ0

(P ) + $jµ0

aµ0#0

;

(4.4) Φ(Q) = Φ(P )% c#0 ·!jµ0

(P ) + $jµ0

aµ0#0

.


Es sind nur noch die Regeln (E) (2.2), (4.3) und (4.4) zu zeigen.Dabei ist (2.2) gerade die Aussage (6) auf Seite 206. #Nach Definition von P und Q gilt ferner:

!jµ(P ) =n'

#=1

aµ# !i" (P ) = %n'

#=1

aµ# $i"

und !jµ(Q) =n'

#=1

aµ# !i" (Q) =n'

#=1# '=#0

aµ# !i" (Q) + aµ#0 !i"0(Q)

= %n'

#=1# '=#0

aµ# $i" + aµ#0 !i"0(Q) ,

also: !jµ(Q)% !jµ(P ) = aµ#0 (!i"0(Q) + $i"0

) .

Und Einsetzen von (2.2) liefert (4.3). Analog ergibt sich (4.4). # !


39.4 Beispiel

Wir betrachten nochmals das Transportproblem 35.1. Dort war gefordert:

%x % y + 600 + 0 , d. h.: !1(x, y) := %x % y und $1 := 600 .

%x + 300 + 0 , d. h.: !2(x, y) := %x und $2 := 300 .

%y + 500 + 0 , d. h.: !3(x, y) := %y und $3 := 500 .

x + y % 400 + 0 , d. h.: !4(x, y) := x + y und $4 := %400 .

x + 0 , d. h.: !5(x, y) := x und $5 := 0 .

y + 0 , d. h.: !6(x, y) := y und $6 := 0 .

Ferner wird HΦ(x, y) := 0,1 ·x+0,4 ·y genau dann minimal, wenn Φ(x, y) = HΦ(x, y)+700 minimalist. Oftmals gehort der Nullpunkt 0 zu K und man startet mit diesem. Hier ist das jedoch nichtder Fall. Wir gehen deshalb bei der Suche nach einer Start–Ecke gemaß Bemerkung 38.4(A) vor:!1 und !3 sind linear unabhangig; man berechnet P := (100, 500)t als Losung von

!1(P ) + $1 = !3(P ) + $3 = 0 ,- %x% y + 600 = %y + 500 = 0 .

Wegen !i(P ) +$i > 0 fur i = 2, 4, 5, 6 ist P eine einfache Ecke von K 5 IR2 . Wir konnen alsodas Ecken–Tableau von P aufstellen und mit dem Simplex–Verfahren 39.3 beginnen:

P !1 !3 Werte .

!2 1 %1 200 %200 =!4 %1 0 200!5 %1 1 100!6 0 %1 500 %500HΦ %0,1 %0,3 210

>

Wir wahlen '0 = 2 und bestimmen die charakteristischen Quotienten fur µ = 1 und µ = 4 .Dann wird . maximal fur µ0 = 1 , also ist !3 durch !2 zu ersetzen. Und Q := (300, 300)t istLosung von

!1(Q) + $1 = !2(Q) + $2 = 0 ,- %x% y + 600 = %x + 300 = 0

mit Q " K . Wir erhalten fur diese Ecke Q das nachste Tableau:

Q !1 !2 Werte .

!3 1 %1 200!4 %1 0 200 %200 =!5 0 %1 300!6 %1 1 300 %300HΦ %0,4 0,3 150

>


Nun ist '0 = 1 , und man erhalt: µ0 = 2 . Somit muß !1 durch !4 ersetzt werden. UndR := (300, 100)t bekommt man als Losung von

!2(R) + $2 = !4(R) + $4 = 0 ,- %x + 300 = x + y % 400 = 0 ,

wobei R " K ist. Es ergibt sich schließlich das Ecken–Tableau:

R !4 !2 Werte .

!3 %1 %1 400!1 %1 0 200!5 0 %1 300!6 1 1 100HΦ 0,4 0,3 70

Jetzt gilt: c1 + 0 und c2 + 0 , also ist R = (300, 100)t tatsachlich eine optimale Ecke mitHΦ(R) = 70 , d. h. fur das ursprungliche Kostenfunktional: Φ(R) = HΦ(R) + 700 = 770 (in DM).

39.5 Bemerkung

Notwendige Voraussetzungen fur die Durchfuhrung des Simplex–Verfahrens 39.3 waren:

a) K ist kompakt.

b) K besitzt nur einfache Ecken.

Diese Bedingungen sind ”normalerweise“ erfullt. Was passiert aber, wenn a) oder b) nicht erfulltist?

zu a): Ist zum Beispiel als konvexer Bereich

K = {(x, y)t " IR2 | x + 0 9 y + 0} 5 IR2

gegeben, so besitzt die Zielfunktion Φ mit Φ(x, y) = x+y zwar ein Minimum im Null-punkt 0 " K , aber %Φ ist auf dem nicht–kompakten K nach unten unbeschrankt.Es existiert daher gar keine optimale Losung bezuglich %Φ .

zu b): Es sei n = 2 und

K := {(x, y)t " IR2 | x + 0 9 y + 0 9 %y + 3 + 0 9 %x + 2 + 0 9 %x + y + 0}

durch zwei Vorzeichenbedingungen und drei Restriktionen sowie Φ(x, y) := %x alsZielfunktion vorgegeben. Soll hierauf das Simplex–Verfahren angewandt werden, soergeben sich zunachst die linearen Funktionale:

!1(x, y) := %y und $1 := 3 ,

!2(x, y) := %x und $2 := 2 ,

!3(x, y) := %x + y und $3 := 0 ,

!4(x, y) := x und $4 := 0 ,

!5(x, y) := y und $5 := 0 .


Fur K 5 IR2 haben wir die Situation:

$y + 0

#

x + 0

....................................................................................................................................................................................................................................................................................................................................y ( 3

........

........

........

........

........

........

........

........

........

........

........

........

........

........

........

........

........

........

........

........

........

........

........

........

........

........

........

........

........

........

........

........

........

........

........

........

........

........

........

........

....

x ( 2............................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................

y + x

...................................................................................................................................................................................................................................................................................... M3+

M1+ = M2

+

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

K

Im allgemeinen wird man — allein anhand der Nebenbedingungen und Vorzeichen-bedingungen — nicht sofort sehen, daß sich die Bedingung y + 0 , also !5 , alsuberflussig erweist. Dies macht den Nullpunkt 0 " K zu einer mehrfachen Ecke mit

!3(0) = !4(0) = !5(0) = 0 .

Man erhalt deswegen drei verschiedene Tableaus fur 0 , namlich:

0 !3 !4 Werte!1 %1 %1 3!2 0 %1 2!5 1 1 0Φ 0 %1 0

>

0 !3 !5 Werte!1 0 %1 3!2 1 %1 2!4 %1 1 0Φ 1 %1 0

>

0 !4 !5 Werte!1 0 %1 3!2 %1 0 2!3 %1 1 0Φ %1 0 0

>

Die Pivotspalte ist jeweils eindeutig festgelegt. Wir erhalten dabei die Suchstrahlen

M1+ := {(x, y)t " IR2 | !3(x, y) = 0 9 !4(x, y) + 0}

= {(x, y)t " IR2 | x = y 9 x + 0} ,

M2+ := {(x, y)t " IR2 | x = y 9 y + 0}

und M3+ := {(x, y)t " IR2 | y = 0 9 x + 0} .

Man erkennt, daß M1+ und M2

+ zusammenfallen. Nun ist M3+ als Suchstrahl nicht

geeignet, da keine Kante von K eingeschlossen wird; jedoch eignet sich M1+ = M2

+

fur ein Austauschverfahren.Diese Beobachtung fuhrt unter einer Zusatzbedingung an das Tableau allgemein beientarteten Ecken weiter (vgl. hierzu [11], Abschnitt 2.3.4, oder auch [7]).

Kapitel X

Grundzuge derprojektiven Geometrie

Mochte man in der Realitat auftretende Zentralprojektionen mathematisch beschreiben, so wirdman zur sogenannten projektiven Geometrie gefuhrt. ”Objekte“ der Abbildung sind dann nichtmehr einzelne Punkte des IR2 oder IR3 , sondern gesamte Geraden in diesen Raumen.

§ 40 Projektive Raume

40.1 Definition

Es sei V " VRK ein beliebiger K–Vektorraum; dann heißt

IP (V ) := {U | U ist Untervektorraum von V mit dimK U = 1 }

der zu V gehorige projektive Raum. Die Elemente von IP (V ) nennt man Punkte (obwohl sieformal Geraden in V sind). Und

dimK IP (V ) := dimK V % 1

heißt die (projektive) Dimension von IP (V ). Es ist IP ({0}) = " mit dimK " = %1 .Wir setzen IPn(K) := IP (Kn+1) und nennen IPn(K) den (kanonischen) n-dimensionalen pro-jektiven Raum uber K.Eine Teilmenge Z 5 IP (V ) des projektiven Raumes zu V heißt ein (projektiver) Unterraumvon IP (V ), wenn Z genau aus den eindimensionalen Unterraumen eines Untervektorraumes Wvon V besteht, d. h. wenn Z = IP (W ) gilt.Gilt speziell: dimK Z = 1 , dann spricht man von (projektiven) Geraden, und im FalledimK Z = 2 von (projektiven) Ebenen.

40.2 Bemerkung

Der Begriff des projektiven Raumes unterscheidet sich also von dem des Vektorraumes nurdurch die Art der Auffassung. Alle Satze uber Untervektorraume eines Vektorraumes konnenalso sofort in Satze uber projektive Unterraume eines projektiven Raumes ubersetzt werden. Soist zum Beispiel der Durchschnitt beliebig vieler projektiver Unterraume wieder ein projektiverUnterraum.

212

§ 40. PROJEKTIVE RAUME 213

40.3 Definition

Ist (Zi)i%I eine beliebige Familie projektiver Unterraume eines projektiven Raumes IP (V ) , d. h.Zi = IP (Wi) mit Untervektorraumen Wi 5 V , so heißt der kleinste projektive Unterraumvon IP (V ) , der die Vereinigung

Di%I

Zi enthalt, der Verbindungsraum der Familie (Zi)i%I . Wir

bezeichnen ihn mitEi%I

Zi . Ist dabei I = {1, 2, . . . , n} , so schreiben wir auch:nE

i=1Zi

oder Z1 8 Z2 8 . . . 8 Zn .Ein projektiver Unterraum H von IP (V ) heißt eine Hyperebene, wenn H .= IP (V ) gilt undwenn ein Punkt P " IP (V ) existiert mit H 8 P = IP (V ) .

40.4 Bemerkung

Unter Berucksichtigung von Bemerkung 4.8(ii) und 3.3(iv) (aus Lineare Algebra I) erhaltman fur einen Verbindungsraum:

K

i%I

Zi =C

Z1S

i'I

Zi projektiver

Unterraum von IP (V )

Z = IP5 '

i%I

Wi

6= IP

@ C

W 1S

i'I

Wi Unter-

vektorraum von V

WA

,

wobei Zi = IP (Wi) ist.

Beweis:

Es ist)i%I

Wi ein Untervektorraum von V mit Wj 5)i%I

Wi fur alle j " I , also gilt weiter:

Zj = IP (Wj) 5 IP ()i%I

Wi) fur alle j " I . Daraus folgt:

K

j%I

Zj 5 IP5 '

i%I

Wi

6.

Umgekehrt ist IP (Wj) = Zj 5Ei%I

Zi = IP (W $) mit einem Untervektorraum W $ von V fur alle

j " I . Daraus ergibt sich: Wj 5 W $ fur alle j " I , also:)j%I

Wj 5 W $ und damit:

IP5 '

j%I

Wj

65 IP (W $) =

K

i%I

Zi .

!

40.5 Satz (Dimensionsformel)

Es sei IP (V ) ein endlich–dimensionaler projektiver Raum zu V " VRK sowie Z1 = IP (W1) undZ2 = IP (W2) zwei projektive Unterraume von IP (V ) . Dann gilt:

dimK Z1 + dimK Z2 = dimK(Z1 8 Z2) + dimK(Z1 3 Z2) .

Ist H eine projektive Hyperebene und Z ein nicht in H enthaltener Unterraum von IP (V ) , sofolgt:

dimK(Z 3H) = dimK Z % 1 .

Insbesondere besitzen in einer projektiven Ebene E , d. h. in E = IP (V ) mit dimK V = 3 , zweiverschiedene Geraden stets genau einen Schnittpunkt.

214 KAPITEL X. GRUNDZUGE DER PROJEKTIVEN GEOMETRIE


Die Dimensionsformel 4.3 fur Untervektorraume liefert mit Bemerkung 40.4:

dimZ1 + dim Z2 = dim W1 % 1 + dim W2 % 1= dim (W1 + W2)% 1 + dim (W1 3W2)% 1= dim IP (W1 + W2) + dim IP (W1 3W2)= dim (Z1 8 Z2) + dim (Z1 3 Z2) .

Ist Z nicht in H enthalten, so gilt: Z8H = IP (V ) , also: dim (Z8H) = dim IP (V ) = dim H +1und damit:

dim (Z 3H) = dim Z + dim H % dim (Z 8H) = dim Z % 1 .

Ist dim E = 2 , dann sind die Hyperebenen in E genau die projektiven Geraden. Daher gilt furzwei verschiedene Geraden G1 und G2 in E :

dim (G1 3G2) = dim G1 % 1 = 0 ,

d. h. G1 3G2 ist ein projektiver Punkt aus E . !

Es seien nun IP (V ) ein projektiver Raum mit dimK V + 1 , H eine Hyperebene von IP (V ) undP0 " IP (V ) \ H , d. h. P0 8 H = IP (V ) . Ferner sei W derjenige Untervektorraum von V mitH = IP (W ) und M := IP (V ) \H . Wir wollen eine Abbildung $ : M #M $ W so definieren,daß A.............................................

...... = (M,W, $) ein affiner Raum uber K wird. Zu P0 " M wahlen wir einen festen Vektorv0 " V mit P0 = IP (<v0>) . Ist jetzt P " M , so existiert wegen V = <v0>2W genau ein

vP " W mit P = IP (<v0 + vP>) . Fur zwei Punkte P,Q " M setzen wir%$PQ := vQ % vP .

Dann gelten die Axiome (A1) und (A2) aus Definition 32.1.

Dabei ist (A1) bereits klar wegen%$PQ +

%$QR =

%$PR .

Zu (A2): Sind P " M und P = IP (<v0 + vP>) sowie w " W gegeben, so betrachte einfach

Q := IP (<v0 + vP + w>) ; dann ist%$PQ = vQ % vP = vP + w % vP = w .

Nach Konstruktion ist also A................................................... = (IP (V ) \H , W , $) ein affiner Raum uber K mit Dimension

dimK A................................................... = dimK W = dimK H + 1 = dimK IP (V ) .

Dies fuhrt zu:

40.6 Definition

Entfernt man aus einem projektiven Raum IP (V ) zu V " VRK eine Hyperebene H , so kanndie Menge aller ubrigen Punkte als ein affiner Raum A.............................................

...... uber K mit dimK A................................................... = dimK IP (V )

aufgefaßt werden.Die Punkte von M = IP (V ) \ H heißen eigentliche Punkte, die von H uneigentliche Punkte.Und H selbst heißt die zu A.............................................

...... gehorige uneigentliche Hyperebene.

§ 40. PROJEKTIVE RAUME 215

Skizze fur das Beispiel V = IR3 :

..................................................................................................................................

..................................................................................................................................

..................................................................................................................................

..................................................................................................................................

..........................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................

H = IP (W )

!

...............................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................P

.................................................................................................................

P0

.................................................................................................................................................................

#

$

........................................................................*

''''(v

++

+,v0

.............................................................................................................................................................................................................................................................

......

......

...................

Ist P = IP (<v>) , so existiert genau ein Skalar " " K und genau ein Vektor w " W mitv = " v0 + w . Wegen P /" H ist " .= 0 , also gilt: 1

+ v = v0 + 1+ w = v0 + vP .

40.7 Satz

Wir ubernehmen die obigen Bezeichnungen; es gilt:

a) Ist Z := IP (U) 5 IP (V ) ein projektiver Unterraum, so ist Z0 := Z 3 M ein affinerUnterraum von A.............................................

...... = (M, W, $) .

b) Ist Z0 .= " ein affiner Unterraum von M , so existiert genau ein projektiver UnterraumZ = IP (U) 5 IP (V ) mit Z0 = Z 3M .

Es gilt dann: dimK Z0 = dimK Z , und der Differenzraum zu Z0 ist U 3W .

Beweis:

zu a): Ist Z 5 H , so folgt wegen M = IP (V ) \H sofort: Z0 = Z 3M = " ; also ist Z0 einaffiner Unterraum. Sonst existiert ein P " Z0 , und es ist

{%$PQ | Q " Z0} = {

%$PQ | Q " Z} 3 {

%$PQ | Q " M} = U 3W

der Differenzraum zu Z0 .zu b): Ist Z0 .= " ein affiner Unterraum von M mit dem Differenzraum X , so wahlen wir

fur festes P " Z0 ein v " V mit P = IP (<v>) ; dann ist v /" W . Wir setzenU := X + <v> und Z := IP (U) . Dann ist Z0 = Z 3M . Und aus Z0 = Z 3Mmit Z = IP (U) folgt: U = (U 3W ) + <v> = X + <v> wie in Teil a); also ist Ueindeutig bestimmt.Im Falle endlicher Dimension gilt: dim Z0 = dimX = dimU % 1 = dim Z .

!

Wir wollen im endlich–dimensionalen Fall mit Koordinaten rechnen. Dazu legen wir fest:


40.8 Definition

Ein (r+1)-Tupel (P0, P1, P2, . . . , Pr) von Punkten eines projektiven Raumes IP (V ) zu V " VRK

heißt projektiv unabhangig, wenn eine der folgenden aquivalenten Bedingungen erfullt ist:

(a) Es gibt r + 1 linear unabhangige Vektoren v0, v1, v2, . . . , vr " V mit Pi = IP (<vi>) furjedes i = 0, 1, 2, . . . , r .

(b) Jedes (r + 1)-Tupel (v0, v1, v2, . . . , vr) von Vektoren aus V mit Pi = IP (<vi>) fur allei = 0, 1, 2, . . . , r ist linear unabhangig.

(c) Es gilt: dimK(P0 8 P1 8 P2 8 . . . 8 Pr) = r .

Ist dimK IP (V ) = n , so heißt ein (n + 2)-Tupel (P0, P1, P2, . . . , Pn, Pn+1) eine projektive Basisvon IP (V ), wenn je n + 1 Punkte davon projektiv unabhangig sind.

40.9 Bemerkung

Es sei dimK IP (V ) = n , d. h. dimK V = n+1 . Weiter sei (P0, P1, P2, . . . , Pn, Pn+1) eine projek-tive Basis von IP (V ) . Wir wahlen dazu Vektoren v0, v1, v2, . . . , vn+1 " V mit Pi = IP (<vi>)fur alle i = 0, 1, 2, . . . , n + 1 . Da jeweils n + 1 von ihnen eine Basis von V " VRK bilden,existieren Skalare "0, "1, "2, . . . ,"n " K mit vn+1 =

n)i=0

"i vi . Dabei sind alle "i .= 0 , denn

sonst waren die n + 1 Vektoren vn+1 und vj fur jedes j " {0, 1, 2, . . . , n} \ {i} linear abhangig.Mit wi := "i vi fur 0 ( i ( n gilt dann:

Pi = IP (<wi>) fur alle 0 ( i ( n und Pn+1 = IP (<w0 + w1 + w2 + . . . + wn>) .

Bei fester Wahl von vn+1 ist die Basis (w0, w1, w2, . . . , wn) von V eindeutig bestimmt. Ist namlichPn+1 = IP (<v$n+1>) , so gilt die Darstellung: v$n+1 = c vn+1 mit c .= 0 . Und zu v$n+1 gibt esgenau eine Basis (w$0, w$1, w$2, . . . , w$n) von V mit Pi = IP (<w$i>) fur alle 0 ( i ( n und

Pn+1 = IP (<w$0 + w$1 + w$2 + . . . + w$n>) , d. h. v$n+1 =n)

i=0w$i . Daraus folgt: w$i = c wi

fur i = 0, 1, 2, . . . , n . Also ist durch (P0, P1, P2, . . . , Pn+1) auf obige Art und Weise eine Basis(w0, w1, w2, . . . , wn) von V bis auf einen gemeinsamen Faktor c .= 0 aller Vektoren eindeutigbestimmt.Ist nun P " IP (V ) ein beliebiger Punkt mit P = IP (<v>) , so entspricht v bezuglich der Basis(w0, w1, . . . , wn) eindeutig ein (n + 1)-Tupel (x0, x1, . . . , xn) " Kn+1 , das bis auf einen gemein-samen Faktor c .= 0 eindeutig bestimmt ist. Wegen v .= 0 gibt es mindestens eine Komponentexi .= 0 . Ist dann P = IP (<v$>) , etwa v$ = a v mit a .= 0 , so unterscheiden sich die Koordi-naten von v$ bezuglich der Basis (w0, w1, . . . , wn) von denen von v nur durch den gemeinsamenFaktor a .= 0 . Man bezeichnet dabei (x0, x1, . . . , xn) als homogene Koordinaten von P " IP (V )bezuglich der sogenannten Grundpunkte P0, P1, . . . , Pn und des Einheitspunktes Pn+1.Die Grundpunkte Pi selbst haben die Koordinaten ei+1 , die Koordinaten des EinheitspunktesPn+1 lauten (1, 1, . . . , 1) . Umgekehrt bestimmt jedes von 0 " Kn+1 verschiedene (n + 1)-Tupel(x0, x1, . . . , xn) bezuglich der Basis (w0, w1, . . . , wn) genau einen Punkt P " IP (V ) .Ist speziell IP (V ) = IPn(K) = IP (Kn+1) , so erhalt man die kanonische projektive Basis vonIPn(K) aus der kanonischen Basis (e1, e2, . . . , en+1) des Kn+1 und dem zusatzlichen Vektor

(1, 1, . . . , 1) =n+1)i=1

ei .

§ 41. PROJEKTIVITATEN 217

§ 41 Projektivitaten

Gegeben seien nunmehr zwei projektive Raume IP (V ) und IP (W ) zu V,W " VRK sowie einVektorraum–Isomorphismus F : V $ W . Dann bildet F jeden 1-dimensionalen Untervektor-raum von V auf einen 1-dimensionalen Untervektorraum von W ab. Deshalb induziert F einebijektive Abbildung f : IP (V ) $ IP (W ) durch

f(P ) := IP (<F (v)>) fur alle P = IP (<v>) .

Ist namlich P = IP (<v$>) fur v$ = c v mit c .= 0 , so gilt: F (v$) = c F (v) , also folgt:<F (v$)> = <F (v)> . Damit ist f wohldefiniert. Außerdem ist f wegen der Bijektivitat vonF ebenfalls injektiv und zugleich surjektiv. Wir schreiben dafur kurz: f = IP (F ) .

41.1 Definition

Eine bijektive Abbildung f : IP (V ) $ IP (W ) heißt eine Projektivitat, wenn ein IsomorphismusF : V $ W existiert mit f = IP (F ) .

41.2 Bemerkung

Fur zwei Isomorphismen F1, F2 : V $ W gilt genau dann: IP (F1) = IP (F2) , wenn ein Skalar" " K* existiert mit F2 = " F1 .

Beweis:

”,“: Sei F2 = " F1 mit " .= 0 und fi := IP (Fi) fur i = 1, 2 . Dann gilt fur jeden Vektorv " V : <F1(v)> = <F2(v)> , also: f1(P ) = f2(P ) fur alle P " IP (V ) .

”-“: Ist f1 = IP (F1) = IP (F2) = f2 , so gibt es zu jedem v " V ein " " K* mitF2(v) = " F1(v) . Wir mussen zeigen, daß fur alle v " V dasselbe " .= 0 gewahltwerden kann. Gilt: dim V ( 1 , so ist die Behauptung bereits klar. Sonst betrachtenwir linear unabhangige v, w " V . Dann gibt es ", µ, ' " K* mit F2(v) = " F1(v) ,F2(w) = µF1(w) und F2(v + w) = ' F1(v + w) . Daraus folgt wegen der Linearitatvon F1 und F2 :

" F1(v) + µ F1(w)% ' F1(v + w) = ("% ') F1(v) + (µ% ') F1(w) = 0 .

Da F1 ein Isomorphismus ist, sind F1(v) und F1(w) linear unabhangig. Und hierausergibt sich: " = ' = µ .

!

41.3 Lemma

Es seien (P0, P1, . . . , Pn+1) und (Q0, Q1, . . . , Qn+1) zwei Basen des n-dimensionalen projektivenRaumes IP (V ) . Dann gibt es genau eine Projektivitat f : IP (V ) $ IP (V ) mit f(Pi) = Qi furalle 0 ( i ( n + 1 .



Wir wahlen gemaß Bemerkung 40.9 zwei Basen (w0, w1, . . . , wn) und (w$0, w$1, . . . , w$n) von V mit

Pi = IP (<wi>) , Qi = IP (<w$i>) fur alle 0 ( i ( n

und Pn+1 = IP (<w0 + w1 + . . . + wn>) , Qn+1 = IP (<w$0 + w$1 + . . . + w$n>) .

Nach Satz 14.6 (siehe Lineare Algebra I) existiert genau ein Automorphismus F : V $ Vmit F (wi) = w$i fur jedes 0 ( i ( n . Dann erfullt f = IP (F ) die geforderten Eigenschaften,und die Existenz von f ist gezeigt.Ist g : IP (V ) $ IP (V ) eine weitere Projektivitat mit g(Pi) = Qi fur alle 0 ( i ( n+1 , so mußmit g = IP (G) gelten:

F (wi) = ci G(wi) 40#i#n und F (w0 + w1 + . . . + wn) = c G(w0 + w1 + . . . + wn) .

Wegen der linearen Unabhangigkeit von G(w0), G(w1), . . . , G(wn) folgt: c = c0 = c1 = . . . = cn ,also: F = c G . Und Bemerkung 41.2 liefert die Eindeutigkeit: f = g . !

Ist (P0, P1, . . . , Pn+1) eine projektive Basis von IP (V ) — man spricht auch von einem (projekti-ven) Koordinatensystem (P0, P1, . . . , Pn+1) —, so betrachten wir die Basis (w0, w1, . . . , wn) vonV mit Pi = IP (<wi>) fur jedes i = 0, 1, . . . , n und Pn+1 = IP (<w0 + w1 + . . . + wn>) .Ist f = IP (F ) eine Projektivitat auf IP (V ) , so entspricht der K–linearen Abbildung F bezuglichder Basis (w0, w1, . . . , wn) umkehrbar eindeutig eine Matrix A = (#ij) " GL(n+1 ; K) mit

F (wj) =n)

i=0#ij wi fur alle 0 ( j ( n . Ist (w$0, w$1, . . . , w$n) eine andere Basis von V mit

Pi = IP (<w$i>) fur alle 0 ( i ( n und Pn+1 = IP (<w$0 + w$1 + . . . + w$n>) ,

dann folgt: w$i = c wi und damit fur die darstellende Matrix B bezuglich (w$0, w$1, . . . , w$n) dieGleichheit: A = B .

Nun ist F durch f noch nicht eindeutig bestimmt. Ist namlich f = IP (F ) = IP (G) , so folgtnach Bemerkung 41.2: F = " G mit einem " " K* . Dann gilt fur die darstellenden Matrizen Avon F bzw. B von G bezuglich derselben Basis (w0, w1, . . . , wn) der Zusammenhang: A = " B .Umgekehrt definieren zwei Matrizen A, B " GL(n+1 ; K) genau dann die gleiche Projektivitat,wenn A = " B mit " .= 0 gilt.

Sind (x*0, x*1, . . . , x*n) die homogenen Koordinaten von P " IP (V ) und (x*0$, x*1$, . . . , x*n$) diehomogenen Koordinaten von f(P ) " IP (V ) , so gilt:

.

////0

x*0$

x*1$

...x*n$

1

22223= A ·

.

////0

x*0x*1...

x*n

1

22223.

Wir wollen jetzt eine Projektivitat auf dem gemaß Definition 40.6 konstruierten affinen Raumbetrachten.Dazu sei IP (V ) ein projektiver Raum zu V " VRK mit dimK IP (V ) = n und A.............................................

...... = (M,W, $)derjenige n-dimensionale affine Raum uber K , der aus IP (V ) durch Herausnahme einer un-eigentlichen Hyperebene H entsteht. Weiter sei (P0, P1, . . . , Pn) ein affines Koordinatensystem


von A................................................... , d. h. (

%%%$P0P1,

%%%$P0P2, . . . ,

%%%$P0Pn) ist eine Basis von W . Wir konstruieren ein projektives

Koordinatensystem (P *0 , P *

1 , . . . , P *n , P *

n+1) von IP (V ) auf folgende Art und Weise:Nach Satz 40.5 schneiden die projektiven Verbindungsgeraden P0 8 P# die Hyperebene H ingenau einem Punkt P *

# := (P0 8 P#) 3 H , jeweils fur ' = 1, 2, . . . , n . Sei zudem P *n+1 " M

der Punkt mit%%%%$P0P *

n+1 =n)

#=1

%%%$P0P# ; dann hat P *

n+1 die affinen Koordinaten (1, 1, . . . , 1) " Kn .

Setzen wir noch P *0 := P0 , so bildet (P *

0 , P *1 , . . . , P *

n , P *n+1) eine projektive Basis von IP (V ) .

Ist P0 = IP (<v0>) und setzen wir v# :=%%%$P0P# fur jedes 1 ( ' ( n, so bildet (v0, v1, . . . , vn) eine

Basis von V und (v1, v2, . . . , vn) eine Basis von W ; es gilt: P *n+1 = IP (<v0 + v1 + . . . + vn>) .

Ist P " A................................................... , also P " M mit den affinen Koordinaten (x1, x2, . . . , xn) , d. h.

%$P0P =

n)i=1

xi%%%$P0Pi ,

so betrachten wir:

v := v0 +%$P0P = v0 +

n'

i=1

xi vi ;

dann ist P = IP (<v>) . Also sind (1, x1, x2, . . . , xn) die homogenen Koordinaten von P be-zuglich des projektiven Koordinatensystems (P *

0 , P *1 , . . . , P *

n+1) .Sind umgekehrt (x*0, x*1, . . . , x*n) die homogenen Koordinaten eines Punktes P " IP (V ) , und ist(v1, v2, . . . , vn) die obige Basis von W , so gilt: P " H ,- x*0 = 0 . Ist also P ein eigentlicher

Punkt, d. h. ein Punkt aus A................................................... , dann gilt: x*0 .= 0 ; und damit ist auch

51,

x*1x*0

,x*2x*0

, . . . ,x*nx*0

6ein

(n + 1)-Tupel homogener Koordinaten von P . Es folgt:

%$P0P = 1 · v0 +

n'

i=1

x*ix*0

vi % v0 =n'

i=1

x*ix*0

vi ,

und5x*1x*0

,x*2x*0

, . . . ,x*nx*0

6sind die affinen Koordinaten von P .

Sei nun f0 eine Affinitat auf A................................................... = (M,W, $). Dann existiert bezuglich der Basis (P0, P1, . . . , Pn)

eine Matrix A0 " GL(n;K) und ein n-Tupel (t1, t2, . . . , tn) " Kn derart, daß fur die affi-nen Koordinaten (x1, x2, . . . , xn) von P " M und die affinen Koordinaten (x$1, x$2, . . . , x$n) vonf0(P ) " M gilt:

(6)

.

////0

x$1x$2...

x$n

1

22223=

.

////0

t1t2...tn

1

22223+ A0 ·

.

////0

x1

x2...

xn

1

22223.

Die homogenen Koordinaten von P bzw. f0(P ) bezuglich des projektiven Koordinatensystems(P *

0 , P *1 , . . . , P *

n+1) sind dann (1, x1, x2, . . . , xn) bzw. (1, x$1, x$2, . . . , x

$n) . Und (6) laßt sich daher

in der folgenden Form schreiben:.

//////0

1x$1x$2...

x$n

1

2222223=

.

//////0

1 0 0 · · · 0t1t2... A0

tn

1

2222223·

.

//////0

1x1

x2...

xn

1

2222223=: A ·

.

//////0

1x1

x2...

xn

1

2222223.

Wegen A " GL(n+1 ; K) definiert A in eindeutiger Weise eine Projektivitat f : IP (V ) $ IP (V ).Fur P " A.............................................

...... gilt: f0(P ) = f(P ) . Also ist f eine Fortsetzung der Affinitat f0 : M $ M auf


A................................................... zu einer Projektivitat f auf IP (V ) . Dabei gilt: f(H) = H fur die uneigentliche Hyperebene,

und f ist die einzige Fortsetzung von f0 " Aff(M) zu einer Projektivitat auf IP (V ) .

Ist schließlich umgekehrt f ein Projektivitat auf IP (V ), welcher hinsichtlich der projektivenBasis (P *

0 , P *1 , . . . , P *

n+1) die Matrix A " GL(n+1 ;K) entspricht, so ist notwendig dafur, daßf die Fortsetzung einer Affinitat f0 auf A.............................................

...... darstellt, daß f in IP (V ) uneigentliche Punkte aufuneigentliche Punkte abbildet, d. h. daß f(H) = H gilt. Nun ist P " H genau dann, wenn furseine homogenen Koordinaten (x*0, x*1, . . . , x*n) bezuglich der projektiven Basis (P *

0 , P *1 , . . . , P *

n+1)gilt: x*0 = 0 . Und f(H) = H impliziert also fur die Matrix A = (#ij)0#i,j#n die Bedingung:#01 = #02 = . . . = #0n = 0 . Wegen det A .= 0 muß dann aber #00 .= 0 sein. Da A nur bis auf einenkonstanten Faktor c .= 0 durch f eindeutig bestimmt ist, konnen wir etwa #00 = 1 annehmen.Ist nun P " IP (V ) ein eigentlicher Punkt mit den affinen Koordinaten (x1, x2, . . . , xn) , so folgtweiter:

.

//////0

1x$1x$2...

x$n

1

2222223= A ·

.

//////0

1x1

x2...

xn

1

2222223und x$i = #i0 +

n'

#=1

#i# x# fur alle 1 ( i ( n .

Also sind (x$1, x$2, . . . , x$n) die affinen Koordinaten von f(P ) ; und f ist damit Fortsetzung einerAffinitat f0 auf A.............................................

...... , welcher hinsichtlich des affinen Koordinatensystems (P0, P1, . . . , Pn) dieMatrix A0 = (#ij)1#i,j#n und der Vektor (#10, #20, . . . ,#n0)t aus Kn zugeordnet sind.

Insgesamt haben wir damit gezeigt:

41.4 Satz

Jede Affinitat f0 auf A................................................... kann eindeutig zu einer Projektivitat f auf IP (V ) fortgesetzt werden.

Umgekehrt induziert eine Projektivitat f auf IP (V ) genau dann eine Affinitat f0 auf A................................................... , wenn

f(H) = H gilt.

41.5 Definition

Es seien Zi = IP (Ui) fur i = 1, 2 zwei projektive Unterraume von IP (V ) mit dimK Z1 = dimK Z2.Die Abbildung f : Z1 $ Z2 heißt Zentralprojektion, wenn es einen projektiven UnterraumZ = IP (U) derart gibt, daß folgende drei Eigenschaften erfullt sind:

(a) Es gilt: Z 8 Z1 = Z 8 Z2 = IP (V ) .

(b) Es gilt: Z 3 Z1 = Z 3 Z2 = " .

(c) Fur alle P " Z1 ist f(P ) = (Z 8 P ) 3 Z2 .

Sind Z1 und Z2 Hyperebenen, so bedeuten die Bedingungen (a) und (b), daß Z ein Punktaußerhalb von Z1 ? Z2 ist. Im allgemeinen sind (a) und (b) aquivalent zu:

V = U 2 U1 = U 2 U2 .

Der projektive Unterraum Z heißt dann das Zentrum von f .


....................................

....................................

....................................

....................................

....................................

....................................

....................................

....................................

....................................

....................................

....................................

....................................

......

Z2

......................................................................................................................................................................................................................................................................................................................................................................................................................................................

Z1

..................................................................................................................................................................................................................................................................................................................................................................................

!Z

!f(P )

!P

41.6 Satz

Jede Zentralprojektion ist eine Projektivitat.

Beweis:

Mit obigen Bezeichnungen sei f : Z1 $ Z2 die Zentralprojektion; gesucht ist ein Vektorraum–Isomorphismus F : U1 $ U2 mit f = IP (F ) .Wir betrachten hierfur die Abbildung pr : V = U 2 U2 $ U2 mit pr(u + u2) := u2 undsetzen F := pr |U1 . Dann ist F linear; außerdem ist F bijektiv. (Denn: Zu jedem u2 " U2 gibtes eindeutig bestimmte u " U und u1 " U1 mit u2 = u + u1 , d. h.: u1 = %u + u2 ; also istF (u1) = pr(%u + u2) = u2 .)Wir zeigen, daß f = IP (F ) gilt. Dazu sei P = IP (<u1>) " Z1 mit u1 " U1 . Wir bildenW := U 2<u1> ; dann ist (nach Bemerkung 40.4) IP (W ) = IP (U) 8 IP (<u1>) = Z 8 P mitF (<u1>) = W 3 U2 , d. h. es gilt:

IP (F )(P ) = IP (<F (u1)>) = IP (W 3 U2) = IP (W ) 3 IP (U2) = (Z 8 P ) 3 Z2 = f(P ) .

!

41.7 Definition

Gegeben seien vier kollineare Punkte P0, P1, P2, P eines projektiven Raumes IP (V ) , d. h. alleP0, P1, P2, P liegen auf einer projektiven Geraden Z = IP (U) .Sind dabei P0, P1, P2 paarweise verschieden, etwa Pi = IP (<vi>) , dann sind je zwei von ihnenprojektiv unabhangig. Also bildet (P0, P1, P2) ein projektives Koordinatensystem von Z mit denGrundpunkten P0, P1 und dem Einheitspunkt P2 . Ein Punkt P " Z besitzt bezuglich diesesKoordinatensystems die homogenen Koordinaten (x0, x1) " K2 . Im Fall P .= P1 gilt: x0 .= 0 ;dann ist

x1

x0durch die vier Punkte eindeutig bestimmt. Man nennt diesen Skalar

x1

x0" K

das Doppelverhaltnis des geordneten 4-Tupels (P0, P1, P2, P ) kollinearer Punkte und bezeichnetes mit kurz mit DV(P0, P1, P2, P ) .Ist P = P1 , d. h. x0 = 0 , so setzen wir fur das Doppelverhaltnis: DV(P0, P1, P2, P ) = ; .

41.8 Lemma

Ist f : IP (V ) $ IP (V ) eine Projektivitat, so laßt f das Doppelverhaltnis kollinearer Punktestets unverandert.



Sind P0, P1, P2, P kollineare projektive Punkte, so sind ebenfalls f(P0), f(P1), f(P2), f(P ) kol-linear, da Isomorphismen Unterraume eines Vektorraumes auf Unterraume gleicher Dimensionabbilden. Gilt: Pi = IP (<vi>) fur i = 0, 1, 2 sowie P = IP (<v>) mit v0 + v1 = v2 , und istv = x0 v0 + x1 v1 , dann folgt fur f = IP (F ) :

f(Pi) = IP (<F (vi)>) fur i = 0, 1, 2 und f(P ) = IP (<F (v)>) .

Andererseits gilt aber auch: F (v0) + F (v1) = F (v2) und F (v) = x0 F (v0) + x1 F (v1) , also:

DV(P0, P1, P2, P ) =x1

x0= DV(f(P0), f(P1), f(P2), f(P )) .

!

Wir wollen zum Abschluß zwei ”geometrische“ Anwendungen betrachten:

41.9 Satz (Satz von Desargues66)

In einer projektiven Ebene IP (V ) seien zwei Dreiecke in perspektivischer Lage gegeben, d. h.es seien paarweise verschiedene Punkte P1, P2, P3 und P1

$, P2$, P3

$ derart gegeben, daß sich dieVerbindungsgeraden P1 8 P1

$ , P2 8 P2$ und P3 8 P3

$ in einem Punkt Z " IP (V ) schneiden.Dann sind die Schnittpunkte

Q1 := (P1 8P2)3 (P1$ 8P2

$) , Q2 := (P2 8P3)3 (P2$ 8P3

$) und Q3 := (P1 8P3)3 (P1$ 8P3

$)

entsprechender ”Dreiecksseiten“ kollinear.

...........................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................

........................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................

....................................

....................................

....................................

....................................

....................................

....................................

....................................

....................................

....................................

....................................

....................................

....................................

....................................

....................................

....................................

....................................

....................................

....................................

....................................

....................................

....................................

....................................

....................................

....................................

....................................

....................................

...................

IP (V )

!P1

!P2

!P3

!P1$

! P2$

!P3$

!Z..................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................

...........................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................

...........................................................................................................................................................................................................................................................................................................................................................................................................................................

..........................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................

..................................................................................................................................................................................................................................................................................................................................................................................................................................................................................

..................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................

!Q1!

Q2

!Q3

!R!R$!S

.................................................................................................................................

................................................

f

..............................

.........................

.......................

..........

......................... .......................

g

.....................................................................................................................................

.........................

.......................

h

......................................................

..............................................................................................................................................................................................................................................................................................

............................................................................................................................................

..................................................

..................................................

..................................................

..............................................................................................................................................................................................................................................................................................................

............. ............. ............. ............. ............. ............. ............. ............. ............. ............. ............. ............. ............. ............. ............. ............. ............. ............. ............. ............. ............. ............. ............. ............. ............. .............

66Gerard Desargues, franzosischer Mathematiker, Architekt und Ingenieur (!21.02.1591, †Okt. 1661)



Es seien

R := (P1 8 P2) 3 (P3 8 P3$) , R$ := (P1

$ 8 P2$) 3 (P3 8 P3

$) , S := (Q1 8Q3) 3 (P3 8 P3$)

und T := (Q1 8Q3) 3 (P2 8 P3) , T $ := (Q1 8Q3) 3 (P2$ 8 P3

$) .

Dann ist zu zeigen, daß gilt: Q2 = T = T $ . Dazu genugt es, T = T $ nachzuweisen, d. h.:DV(Q1, Q3, S, T ) = DV(Q1, Q3, S, T $) . Sei dazu f : Q1 8Q3 $ Q1 8 P1 die Zentralprojektionmit dem Zentrum P3 . Dann ist f nach Satz 41.6 eine Projektivitat, laßt also das Doppelver-haltnis unverandert gemaß Lemma 41.8, und es gilt:

DV(Q1, Q3, S, T ) = DV(Q1, P1, R, P2) .

Entsprechend ergibt sich durch die Zentralprojektion g : Q1 8 P1 $ Q1 8 P1$ mit Zentrum Z :

DV(Q1, P1, R, P2) = DV(Q1, P1$, R$, P2

$) .

Schließlich liefert h : Q1 8 P1$ $ Q1 8Q3 mit dem Zentrum P3

$ analog:

DV(Q1, P1$, R$, P2

$) = DV(Q1, Q3, S, T $) .

Zusammengefaßt hat man also: T = T $ . !

In ahnlicher Weise folgt (zum Beweis siehe [11], Abschnitt 3.3.7):

41.10 Satz (Satz von Pappos67)

In einer projektiven Ebene seien zwei verschiedene Geraden Z und Z $ sowie darauf jeweilspaarweise verschiedene Punkte P1, P2, P3 " Z und P1

$, P2$, P3

$ " Z $ vorgegeben. Dann erweisensich die Schnittpunkte

Q1 := (P1 8P2$)3 (P1

$ 8P2) , Q2 := (P2 8P3$)3 (P2

$ 8P3) und Q3 := (P3 8P1$)3 (P3

$ 8P1)

als kollinear.

!P1

!P2

!P3

!P1$ !

P2$ !

P3$

.........................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................

........

........

........

........

........

........

........

........

........

........

........

........

........

........

........

........

........

........

........

........

........

........

........

........

........

........

........

........

........

........

........

........

........

........

........

........

........

........

........

........

.

..............................................................................................................................................................................................................................................................................................................................................................................................................................................................................................

.....................................................................................................................................................................................................................................................................................................................................................................

..............................

..............................

..............................

..............................

..............................

..............................

..............................

..............................

..............................

..............................

..............................

..............................

..............................

..............................

..............................

..............................

..............................

..............................

............

! !!.........................................

..................................................................................

..................................................................................

..................................................................................

..................................................................................

..................................................................................

..................................................................................

..................................................................................

..................................................................................

.............................................................................. Z

............................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................... Z $

!Z 3 Z $........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........ Q1 8Q3 8Q2

67Pappos von Alexandria, altgriechischer Mathematiker und Astronom (um 320 n. Chr.)

Date post:	19-Oct-2020
Category:	Documents
Upload:	others
View:	1 times
Download:	0 times

LINEARE ALGEBRA II - uni-due.dehn213me/sk/knoop/Linal2.pdf · LINEARE ALGEBRA II 127. Kapi tel VI I...

Documents