Embed Size (px)
Citation preview
Lineare und Multlineare Algebra
(Auszug aus einem Skriptum „Mathematik für Physiker II“
im SS 2002)
Prof. Dr. Hermann Dinges
, Seite 97
Teil IX : Lineare und multilineare Algebra
Themenubersicht
Didaktische Vorrede: Matrizenrechnung, lineare Algebra, geometrische Anschauung.
50. Vorlesung : Affine Geometrie, Geschichtliches Seite 97Punkte, Geraden, Ebenen. Affine Teilraume und ihre Verschiebungen, Affine Teilraume alsNullstellengebilde. Dualraum, duale Abbildung.
”Objekte hoherer Stufe“. Zur Geschichte:
Geometrie in n Dimensionen bei Graßmann, Riemann, Cayley. Hamiltons Quaternionen,
”Vektoranalysis“. Differentialformen bei E. Cartan. Determinanten von Leibniz bis Jacobi.
51. Vorlesung : Determinanten, Dachprodukte Seite 101Die Determinantenfunktion als multiplikative Funktion auf GLn. Die Determinante alsalternierende Multilinearform. Die Determinante als Umrechnungsfaktor fur
”Raumele-
mente“.
52. Vorlesung : Abstrakte Vektorraume, Basis und Dimension Seite 107Axiome, lineare Hulle, lineare Unabhangigkeit, Basis, Austauschlemma. Linearformen,duale Basis. Naturliche Paarung.
53. Vorlesung : k-Vektoren und alternierende k-Formen Seite 112Formale Linearkombinationen von k-fachen Dachprodukten. Umrechnungsregeln. Bezugauf eine Basis. Das
”Vektorprodukt“ als Beispiel. Alternierende Multilinearformen
(ΛkV
)⋆.
Duale Basen {vK : |K| = k} und{ℓ(K) : |K| = k
}. ΛV = Λ◦V ⊕ Λ1V ⊕ . . .⊕ ΛnV . Das
Dachprodukt in der Graßmann-Algebra ΛV .
54. Vorlesung : Minoren, Cofaktoren, Cramer’sche Regel Seite 119Minoren eine Matrix. Cofaktoren und der Laplace’sche Entwicklungssatz fur Determinan-ten, Cramer’sche Regel, Transformation
”polarer“ Vektoren.
55. Vorlesung : Nullraume, Kern und Bild einer linearen Abbildung Nullraumebzgl. der naturlichen Paarung. Der Satz vom Rang. Nullraume bzgl. einer nichtausgear-teten Bilinearform (z.B. Orthogonalraume). Duale Abbildung. Zeilenrang = Spaltenrang.Vektorraum-Homomorphismen und Isomorphismen. Hinweis auf stetige lineare Abbildun-gen.
56. Vorlesung : Tableaus, Basisaustausch, lineare Gleichungssysteme Basis-austausch durch Spaltentableaus. Die Matrizen im vollstandig ausgetauschten Tableau.Gleichungssysteme durch Zeilentableaus. Hinweis auf den Satz von der implizit gegebenenFunktion.
57. Vorlesung : Duale Tableaus, Bilinearformen, Tensoren Seite 135Basiswechsel und Koordinatenwechsel. Matrizen und Tableaus zur Darstellung linearerAbbildungen. Lineare Abbildungen als Bilinearformen. Der Rang einer Bilinearform. DasTensorprodukt U ⊗ V und sein Dualraum U⋆ ⊗ V ⋆.
58. Vorlesung : Lineare Optimierung, perfekter Austausch Seite 141Maximierung als Zeilentableau, Minimierung als Spaltentableau. Zulassige Losungen desSpaltentableaus liefern obere Abschatzungen fur die Zielfunktion im Maximierungspro-blem. Zahlenbeispiel fur perfekten Austausch.
59. Vorlesung : Geometrisches zur linearen Optimierung Seite 146Extremalpunkte. Auf einer abgeschlossenen konvexen MengeK, die keine Geraden enthalt,nimmt jede auf K beschrankte konvexe Funktion ihr Maximum in einem Extremalpunktan. Perfekter Austausch im Fall
”allgemeiner Lage“. Legendre-Dualitat und Dualitat in
der linearen Optimierung. Duale Kegel. Der Satz von Farkas.
sup{cx : x ≥ 0, Ax ≤ b} = inf{ξb : ξ ≥ 0 , ξA ≥ c} .
, Seite 99
Teil IX : Lineare und multilineare Algebra
Didaktische Vorrede:
Die lineare Algebra steht fur die Studierenden der Mathematik neben der elementarenAnalysis ganz am Anfang des Studiums. Den Studierenden der Physik wird in Frankfurtkeine separate Veranstaltung zur
”Linearen Algebra“ oder
”Analytischen Geometrie“ an-
geboten. In der”Mathematik fur Physiker“ soll die Algebra zusammen mit der Geometrie
und der Analysis entwickelt werden. Die Prinzipien des algebraischen Operierens sollenalso sowohl mit geometrischer Anschauung verbunden werden, als auch mit den Ideen vonKonvergenz und Stetigkeit. Die von den Mathematikern so geschatzte Systematik mussda in den Hintergrund treten.Ein besonders empfehlenswertes Lehrbuch ist
A.I. Kostrikin, Yu,I. Manin”Linear Algebra and Geometry“, Taylor & Francis Group
1997.
Die elementaren Teile enthalten gute Ubungsaufgaben. Ungewohnlich sind die intuitivrelativ leicht zuganglichen, sehr ernsthaften Ausblicke auf Anwendungen in der Quanten-mechanik.
Wir haben die Matrizenrechnung als eine Vorstufe der Theorie der Vektorraume imersten Semester zusammen mit den komplexen Zahlen und den Polynomen vorgestellt.Die Matrizen waren da Rechengroßen, die man addieren bzw. multiplizieren kann (wenndie Formate passen). Auf Anschaulichkeit mussten wir verzichten. Dieses Defizit soll nunausgeglichen werden. Wir entwickeln die Theorie der Vektorraume als lineare Geometriemit der Dualitat als zentralem Prinzip. Geometrische Betrachtungen zur Matrizenrech-nung spielten naturlich auch schon an fruheren Stellen der Vorlesung eine Rolle, zuletztbei den Kurven auf einer Mannigfaltigkeit und bei den Extrema mit Nebenbedingungen.Wir sollten also fit sein fur den abstrakten Zugang der linearen Geometrie.
50. Vorlesung : Affine Geometrie, Geschichtliches
Die affine lineare Geometrie handelt zunachst einmal von Punkten, Geraden, Ebenen,. . . , also von affinen Teilraumen (eines gegebenen affinen Raums L). Der VektorraumV der Verschiebungen muss kein R-Vektorraum oder C-Vektorraum sein. Wir wollen alsKoeffizientenkorper einen beliebigen Korper K zulassen.
Zu einem k-dimensionalen affinen Teilraum M ⊆ L gehort der k-dimensionale Teil-vektorraum W seiner Verschiebungen. (Wir nennen ihn manchmal den Tangentialraumvon M .) Wenn P ein beliebiger Punkt von M ist, dann gilt
M = {P : P = P + w mit w ∈W} .
Andererseits kann man M aber auch als Durchschnitt von Hyperebenen beschreiben.
M = {P : a(1)(P ) = 0, . . . , a(m)(P ) = 0} .
Hier sind die a(i)(·) affine Funktionen auf L.Die affinen Funktionen auf L und die dazugehorigen Linearformen auf V spielen eine
ebenso zentrale Rolle in der affinen linearen Geometrie wie die Vektoren. Der Vektor-raum der Linearformen heißt der Dualraum von V . Die Linearformen werden oft auchCovektoren genannt.
Definitionen
a) Eine K-wertige Funktion a(·) auf einem affinen Raum M heißt eine affine Funkti-on, wenn gilt
a((1− λ)P + λQ
)= (1− λ) · a(P ) + λ · a(Q) fur alle P,Q ∈M, λ ∈ K .
b) Eine K-wertige Funktion ℓ(·) auf einem Vektorraum W heißt eine Linearform,wenn gilt
ℓ (αw1 + βw2) = α · ℓ (w1) + β · ℓ (w2) fur alle w1, w2 ∈W, α, β ∈ K .
c) Eine Abbildung ϕ von einem K-Vektorraum V in einem K-Vektorraum U heißt einelineare Abbildung oder eine Vektorraum-Homomorphismus, wenn gilt
ϕ (αv1 + βv2) = α · ϕ (v1) + β · ϕ (v2) fur alle v1, v2 ∈ U, α, β ∈ K .
d) Entsprechend ist der Begriff der affinen Abbildung eines affinen Raums in einenaffinen Raum definiert. Eine affine Abbildung A(·) bestimmt einen Vektorraum-Homomorphismus
ϕ(w) = A(P + w)−A(P ) .
Wir werden uns meistens nur mit dieser linearen Abbildung beschaftigen.
Dimension :
Ein erster zentraler Begriff der affinen linearen Geometrie ist die Dimension (eines Teil-vektorraums bzw. eines affinen Teilraums). Ein Teilvektorraum kann als die lineare Hulleeiner Familie von Vektoren gegeben sein oder als das Nullstellengebilde einer Familie vonLinearformen. In beiden Fallen stellt sich das Problem, die Dimension zu bestimmen.Eine lineare Abbildung bildet Teilvektorraume in Teilvektorraume ab. Die Dimension desBilds kann aber kleiner sein als die Dimension des abgebildeten Raums.
Wenn A(·) eine affine Abbildung ist und a(·) eine affine Funktion auf dem Ziel-raum, dann ist die zuruckgenommene Funktion A⋆(a)(·) eine affine Funktion auf demUrbildraum. Der Pullback A⋆(·) liefert eine lineare Abbildung des Vektorraums aller af-finen Funktionen auf dem Zielraum in den Vektorraum aller affinen Funktionen auf demUrbildraum.
Wir interessieren uns, wie gesagt, vor allem fur lineare Abbildungen (auch lineareOperatoren genannt)
ϕ : V −→ U .
, Seite 101
Der Vektorraum der Linearformen auf V , der Dualraum von V , wird mit V ⋆ bezeichnet.Fur jedes ℓ ∈ U⋆ ist die zuruckgenommene Funktion eine Linearform auf U . Die Ein-schrankung des Pullback ϕ⋆(·) auf U⋆ heißt die zu ϕ duale Abbildung und wird mit ϕ⋆
bezeichnet.ϕ⋆ : V ⋆ ←− U⋆ zu ϕ : V −→ U .
Die duale Abbildung ϕ⋆ bildet Teilvektorraume von U⋆ in Teilvektorraume von V ⋆ ab.Auch hier stellt sich die Frage, wie die Dimension durch die Abbildung verringert wird.Fur alle diese Fragen ist die lineare Algebra zustandig.
Objekte hoherer Stufe
Die lineare Geometrie betrachtet noch andere mathematische Objekte als nur die Vek-toren. Sie beschaftigt sich z.B. auch mit
”Stellungen“ im Raum, die durch Paare von
Vektoren (”Parallelogramme“) gegeben sind. Die Physiker kennen diese Objekte im drei-
dimensionalen Anschauungsraum als”polare Vektoren“. In mehr als dreidimensionalen
Raumen bestimmen auch Tripel, Quadrupel von Vektoren”Stellungen“ im Raum. Diese
Objekte sind die Elemente der Graßmann-Algebra ΛV . Auch mit diesen Objekten undden dazu dualen Objekten, den alternierenden Multilinearformen wird in der affinen Geo-metrie gerechnet. Es ist zu hoffen, dass sich mit dem Rechnen geometrische Vorstellungs-kraft entwickelt, denn die geometrischen Vorstellungen werden wir in der Weiterfuhrungder Theorie der Mannigfaltigkeiten dringend brauchen.Ein Blick in die Geschichte der Geometrie zeigt, dass es einiger geistiger Flexibilitat be-darf, eine tragfahige geometrische Intuition zu entwickeln.
Zur Geschichte
Hermann Graßmann (1809-1877) explizierte 1844 (und dann nochmal 1862) in seiner”Li-
nealen Ausdehnungslehre“ die Idee, dass man mit gewissen geometrischen Großen direktrechnen sollte; es sei unpassend immer nur mit Zahlen zu rechnen. Dabei war das, wasman spater Vektoren nannte, fur Graßmann nur ein spezieller Typ geometrischer Großen.Graßmanns revolutionare Ideen wurden von seinen Zeitgenossen ebensowenig verstan-den wie Riemanns
”Hypothesen, die der Geometrie zugrundeliegen“ (1854). Uberhaupt
wurde die Geometrie von mehr als drei Dimensionen mit Mißtrauen und Unglauben auf-genommen. (Cayley hatte 1843 den Begriff eines Raumes von n Dimensionen in einerweniger abschreckenden Form eingefuhrt als Graßmann.) Die Entwicklung ließ die Ideenvon Graßmann zunachst beiseite. Hamilton bemuhte sich uber Jahre um einen Kalkulder Zahlentripel nach dem Muster der komplexen Zahlen (die man als Zahlenpaare ver-stand). Bei den Tripeln hatte er keinen Erfolg, wohl aber bei den Quadrupeln. Als er 1843die Quaternionen (als Zahlenquadrupel) entdeckte, war die Begeisterung groß. Es zeigtesich aber recht bald, dass man den Wert der Quaternionen fur die Geometrie doch starkuberschatzt hatte. Es blieb immerhin ein Teil der Quaternionenkalkuls im Bewußtsein,namlich die Theorie der Vektoren (der Name stammt von Hamilton).Aus dieser Tradition heraus entwickelte eine spatere Generation von Mathematikern undPhysikern die Vektoranalysis fur affine und fur metrische Raume; zu nennen sind vor al-lem J.W. Gibbs (1839-1903) in Amerika und O. Heaviside (1850-1925) in England.
Der viel tiefer greifende Ansatz von Graßmann wurde erst spater wiederentdeckt. E. Car-tan (1869-1951) baute darauf seine Theorie der Differentialformen und ihrer Integraleuber Mannigfaltigkeiten. Die Differentialformen haben heute einen zentralen Platz in derGeometrie und in der mathematischen Physik.Die von Graßmann eingefuhrten
”Großen hoherer Stufe“ kann man sich als Aquivalenz-
klassen von Parallelogrammen (Dim = 2), Parallelepipeden (Dim = 3) . . . vorstellen. Bevorwir zu einer mathematischen Definition dieser Objekte (und den dazu dualen Objekte)sowie zu den Dachprodukten (
”wedge-products“) kommen, mussen wir einiges uber De-
terminanten sagen.
Geschichtliches uber Determinanten
Die Idee der Determinante ist alter als die lineare Geometrie. Sie geht auf Leibniz (1693)zuruck. (Ein japanischer Wissenschaftshistoriker hat 1914 festgestellt, dass der japanischeMathematiker Seki Kowa die Idee der Determinante bereits 1683 besessen hat.) Der GenferProfessor Gabriel Cramer hat die Determinanten 1750 wiederentdeckt und zur Losunglinearer Gleichungssysteme verwendet. Der Name Determinante stammt von Gauß (1801)und wurde auch von Cauchy (1812) verwendet. Zum Gemeingut der Mathematiker wurdedie Theorie der Determinanten durch eine beruhmte Arbeit von Jacobi
”De formatione et
proprietatibus determiantium“ (1841). Sylvester (1814-1897) pragte den Namen”Jacobi-
Determinante“. Der Begriff der Matrizen (speziell der Jacobi-Matrix einer Abbildung)stammt aus einer spateren Zeit.
Wir wollen die Determinanten in vier Schritten vorstellen.
- Die Determinante als eine multiplikative Funktion auf der Menge der n×n-Matrizen.
- Die Determinante als alternierende Multilinearform auf der Menge der n-Spalten.
- Die Determinante als Umrechnungsfaktor von einer Basis zu einer anderen.
- Die k × k-Determinanten (”Minoren“) als Eintrage in den Matrizen, wleche die
Koordinatentransformation in einer Graßmann-Algebra regelt.
, Seite 103
51. Vorlesung : Determinanten, Dachprodukte
Die Determinante einer n× n-Matrix
Die Determinante einer 2× 2-Matrix
det
(a11 a12
a21 a22
)= a11 · a22 − a12 · a21
ist bereits aus der Schule bekannt. Vielleicht auch die Determinante einer 3 × 3-Matrix;sie ist die alternierende Summe von 6 Produkten. Eine entsprechende Formel gibt es auchfur die Determinante einer n× n-Matrix A =
(aij)i,j
detA =∑
σ
(signσ) · a1σ1· a2
σ2· . . . · anσn
.
Dabei ist uber alle Permutationen σ = (σi1 , . . . , σin) zu summieren. Das Signum von σ ist+1 oder −1, je nachdem, ob σ eine gerade oder eine ungerade Permutation ist.
Exkurs uber Permutationen: Eine bijektive Abbildung einer endlichen Menge heißteine Permutation. Eine Permutation, welche zwei Elemente vertauscht und alle ubrigenfestlaßt, heißt eine Transposition. Jede Permutation kann durch das Hintereinanderschal-ten von Transpositionen gewonnen werden. Die Permutation heißt gerade, wenn man siemit einer geraden Anzahl von Transpositionen gewinnen kann, andernfalls ungerade.Es ist nicht trivial, dass es ungerade Permutationen gibt. Man konnte ja vielleicht ver-muten, dass man jede Permutation (insbesondere jede Transposition) durch eine geradeAnzahl von Permutationen gewinnen kann, wenn man nur geschickt vorgeht.
Satz :
Sei (σ1, . . . , σn) eine Permutation der Zahlen 1, . . . , n. Nennen wir ein Paar i < j eineFehlstelle fur σ, wenn σi > σj . Bei jeder Transposition benachbarter Elemente wird dieAnzahl der Fehlstellen entweder um 1 vergroßert oder um 1 verkleinert. Der Beweis seidem Leser uberlassen.
Corollar : Wenn N(σ) die Anzahl der Fehlstellen fur σ ist, dann gilt
signσ = (−1)N(σ) .
Als Ubung beweise man: Eine zyklische Permutation von k Elementen ist ungerade, wennk gerade ist und gerade, wenn k ungerade ist.
Eigenschaften der Determinantenfunktion
1. Die Determinante der Einheitsmatrix ist = 1.
2. Wenn man eine Spalte (oder eine Zeile) der Matrix A mit λ multipliziert, dannmultipliziert sich die Determinante mit λ.
3. Wenn man zwei Spalten (oder Zeilen) vertauscht, dann multipliziert sich die Deter-minante mit −1.
4. Die Determinantenfunktion ist linear als Funktion der j-ten Spalte (oder i-ten Zeile),wenn man die ubrigen Spalten (bzw. Zeilen) festhalt; i, j beliebig.
Konsequenzen :
1. Eine Matrix mit zwei gleichen Spalten (Zeilen) verschwindet.
2. Wenn man zu einer Spalte (Zeile) Vielfache anderer Spalten (Zeilen) dazuaddiert,dann bleibt die Determinante unverandert.
3. Durch mehrfaches Anwenden dieser Regel kann man die Determinante mit relativgeringem Aufwand ausrechnen. Man muß nur geschickte elementare Zeilenoperatio-nen oder elementare Spaltenoperationen anwenden.
Satz :
Sei A eine n× n-Matrix. Wenn fur ein λ ∈ K
det(A− λ · I) = 0 ,
dann sind die Zeilen (und die Spalten von A−λI linear abhangig und es existieren Spaltenxλ 6= 0 (und Zeilen ξλ 6= 0), sodass
Axλ = λxλ , ξλ ·A = λ · ξλ .
(Diese xλ heißen Eigen-Spaltenvektoren zum Eigenwert λ, die ξλ heißen Eigen-Zeilenvektorenzum Eigenwert λ fur die Matrix A).
Den Beweis verschieben wir auf spater. Wir werden sehen, dass die Menge der Eigen-vektoren zum Eigenwert λ ein Vektorraum ist, der die Dimension k hat, wenn A − λIden Rang n− k hat. Die Begriffe Dimension und Rang werden in den nachsten Wochenausfuhrlich diskutiert.
Bemerkungp(z) := det(A− z · I)
ist ein Polynom n-ten Grades
p(z) = (−z)n + s1 · (−z)n−1 + . . .+ sn
mit sn = detA und s1 = a11 + a22 + . . . + ann. (Der Koeffizient s1 heißt die Spur von A(trace (A)
); Spuren werden uns im nachsten Semester beschaftigen).
p(·) heißt das charakteristische Polynom der Matrix. p(·) ordnet jedem Skalarλ ∈ K einen Skalar p(λ) zu. Wenn K = C, dann hat p(·) Nullstellen (
”Fundamentalsatz
der Algebra“). Fur allgemeine Skalarenkorper K gibt es keinen derartigen Satz. Wir be-handeln im Folgenden K-Vektorraume mit beliebigen Koeffizientenkorper; die Theorie derEigenvektoren und Eigenraume stellen wir zuruck.
, Seite 105
Die Determinante als alternierende Multilinearform
Wir fassen die Determinante von n-reihigen Matrizen als Funktion des n-Tupels der Spal-ten auf. Sei also A =
(aij)i,j=1,...,n
eine I×J-Matrix und aj die I-Spalte mit den Eintragen(aij)i=1,...,n
(fur j = 1, . . . , n) und
detA = Φ (a1, a2, . . . , an) .
Φ(·, ·, . . . , ·) ist dann eine alternierende Multilinearform vom Grad n im Sinne der folgen-den allgemeineren
Definition
Sei V ein n-dimensionaler Vektorraum. Eine K-wertige Funktion Φ(·) auf dem k-fachencartesischen Produkt V ×V × . . .×V heißt eine alternierende k-Form (oder
”alternierende
Multilinearform vom Grad k“), wenn gilt
(i) Φ (w1, . . . , wj, wj+1, . . . , wk) = (−1) · Φ (w1, . . . , wj+1, wj, . . . , wk);
(ii) Φ (λw1, w2, . . . , wk) = λ · Φ (w1, w2, . . . , wk) fur alle λ ∈ K;
(iii) Φ (w′1 + w′′
1 , w2, . . . , wk) = Φ (w′1, w2, . . . , wk) + Φ (w′′
1 , w2, . . . , wk).
Bemerke :
1. Im Falle k = 1 ist die Bedingung (i) leer. Eine 1-Form ist nicht anderes als eineLinearform auf V . Die Gesamtheit aller alternierenden 1-Formen ist der DualraumV ⋆.
2. Der Vektorraum aller alternierenden n-Formen ist eindimensional. Es existiert einealternierende n-Form, welche nicht identisch 0 ist; und jede alternierende n-Formist ein Vielfaches davon.
3. Fur jedes k ist die Gesamtheit aller alternierenden k-Formen ein K-Vektorraum;man kann k-Formen linear kombinieren. Diesen Vektorraum bezeichnet man mitΛkV ⋆. Wir werden spater sehen, dass dieser Vektorraum die Dimension
(nk
)besitzt.
(k = 1, . . . , n).
Studieren wir jetzt den Fall k = n.
Satz :
V sei ein n-dimensionaler Vektorraum, v1, . . . , vn sei eine Basis.
a) Es existiert genau eine alternierende n-Form mit
Φ (v1, . . . , vn) = 1 .
b) Seien w1, . . . , wn Vektoren
wj =∑
viaij fur j = 1, . . . , n .
Dann giltΦ (w1, . . . , wn) = (detA) · Φ (v1, . . . , vn) = detA .
Beweis
1. Wir reprasentieren die Basisvektoren vi durch die Einheitsspalten. Die wj sind danndurch die I-Spalten mit den Eintragen
(aij)i=1,...,n
reprasentiert. Die Determinante
von A liefert die gesuchte alternierende n-Form.
2. Sei Φ(·) eine alternierende n-Form auf dem Raum der n-Spalten. Bei den elemen-taren Spaltenumformungen, die oben zur Berechnung der Determinante empfohlenwurden, bleibt der Wert von Φ(·) unverandert
(aufgrund der Eigenschaften (i), (ii)
und (iii)). Φ(·) ist also durch den Wert Φ (v1, . . . , vn) eindeutig bestimmt.
Corollar 1 Ein n-Tupel von Vektoren w1, . . . , wn ist genau dann linear abhangig, wenn
Φ (w1, . . . , wn) = 0
fur jede alternierende n-Form Φ(·). Das ist genau dann der Fall, wenn die Determinanteder Matrix verschwindet, welche die wj in einer beliebig gewahlten Basis darstellt.
Determinanten als Vergleichsfaktoren
(Sollte auch direkt nach Vorlesung 52 und Vorlesung 53 studiert werden)Wir gehen jetzt erste Schritte auf dem von Graßmann gewiesenen Weg. Wir rechnen mitneuartigen geometrischen Großen im n-dimensionalen Raum. Die Objekte der neuen Artsind die formalen Linearkombinationen von Dachprodukten. Zunachst geht es nur um dien-fachen Dachprodukte. Diese Rechengroßen konnte man als Raumelemente interpretie-ren. Das Entscheidende sind aber die Rechenregeln. Die Algebra ist insofern einfach, alsje zwei
”Raumelemente“ sich nur um einen Faktor unterscheiden; wir brauchen nur einen
Kalkul der Umrechnungsfaktoren. Und das ist der Determinantenkalkul in einem neuenGewand.
Notation
1. v1, . . . , vn und w1, . . . , wn seien linear unabhangige n-Tupel von Vektoren in einemn-dimensionalen K-Vektorraum V . Wir schreiben
1 · w1 ∧ . . . ∧ wn = α · v1 ∧ . . . ∧ vn ,
wenn α die Determinante der Matrix A ist, welche die wj durch die vj ausdruckt :
wj =∑
i
vi · aij fur j = 1, . . . , n .
2. Wenn u1, . . . , un linear abhangig sind, dann schreiben wir
1 · u1 ∧ . . . ∧ un = 0 · v1 ∧ . . . ∧ vn
oder auch kurz 1 · u1 ∧ . . . ∧ un = 0.
, Seite 107
3. Statt 1 · w1 ∧ . . . ∧ wn schreiben wir auch w1 ∧ . . . ∧ wn.Wir wollen mit den Linearkombinationen der formalen Ausdrucke
α · v1 ∧ . . . ∧ vn
rechnen. Die Rechenregeln ergeben sich aus den Rechenregeln fur Determinanten.Diese lauten in der neuen Notation folgendermaßen:
Rechenregeln fur n-fache Dachprodukte
(i) Fur jedes n-Tupel von Vektoren und jedes j gilt
w1 ∧ . . . ∧ wj ∧ wj+1 ∧ . . . ∧ wn = (−1)w1 ∧ . . . ∧ wj+1 ∧ wj ∧ . . . ∧ wn
(”Transpositionen andern das Vorzeichen“)
(ii) µ (λw1) ∧ w2 ∧ . . . ∧ wn = (µλ) · w1 ∧ w2 ∧ . . . ∧ wn(”Skalare Faktoren kann man aus jedem Faktor herausziehen“)
(iii) (w′1 + w′′
1) ∧ w2 ∧ . . . ∧ wn = w′1 ∧ w2 ∧ . . . ∧ wn + w′′
1 ∧ w2 ∧ . . . ∧ wn(Das Dachprodukt ist in jedem Faktor linear)
Bemerke : Wegen (i) mussten wir die Homogenitat (ii) und die Additivitat (iii) nur furden ersten Faktor feststellen.
Satz :
Durch die Rechenregeln (i), (ii) und (iii) ergibt sich fur jede Matrix(aij)
= A
(∑vi1 · ai11
)∧(∑
vi2 · ai22)∧ . . . ∧
(∑vin · ainn
)= (detA) · v1 ∧ . . . ∧ vn .
Beweis (durch einfaches Rechnen)Wir konnen distributiv ausmultiplizieren.Die linke Seite ist die n-fache Summe
∑
i1,...,in
(ai11 · ain2 · . . . · ainn
)vi1 ∧ . . . ∧ vin .
Wenn in einem Dachprodukt zwei Indizes gleich sind, dann ergibt das keinen Beitrag.Wenn σ = (i1, . . . , in) eine Permutation von (1, . . . , n) ist, dann haben wir
vi1 ∧ . . . ∧ vin = (signσ) · v1 ∧ . . . ∧ vn .
Die Summe ist also
∑
σ
(signσ) · ai11 · ai21 · . . . · ainn (v1 ∧ . . . ∧ vn) = (detA) · (v1 ∧ . . . ∧ vn) .
Definition (Volumenmessung)
Eine K-wertige lineare Funktion Ψ(·), welche jeder formalen Linearkombination
∑
α
aαvα1 ∧ . . . ∧ vαn
einen Skalar zuordnet, sodass die Zuordnung mit den Rechenregeln (i), (ii) und (iii) ver-traglich ist, heißt eine Volumenmessung in V .
Bemerke :
1. Eine Volumenmessung ist schon dadurch eindeutig bestimmt, dass man einem be-liebig gewahlten Dachprodukt e1 ∧ . . . ∧ en 6= 0 einen Skalar zuordnet.Man kann sagen, dass die Menge aller Volumenmessungen ein eindimensionaler Vek-torraum ist.
2. Wenn man die Volumenmessung Ψ(·) nur auf die”Monome“ w1∧ . . .∧wn anwendet,
dann hat man eine alternierende n-Form Φ(·), wie im vorigen Abschnitt.
Empfehlung : Man vermute nicht zu viel hinter der Sprechweise”formale Linearkombi-
nation“. Die eventuell vorhandene Scheu wird sich legen; man suche jetzt bitte nicht nacheiner mathematischen Definition. Verstanden hat man, wenn man begreift: Erst durcheinen Gleichheitsbegriff wird aus der Gesamtheit der formalen Linearkombinationen eineMenge im Sinne der Mathematik.
, Seite 109
52. Vorlesung : Abstrakte Theorie der Vektorraume, Basis und
Dimension
Wir haben bereits mehrere R-Vektorraume und C-Vektorraume kennengelernt. Fur dieabstrakte Theorie der (endlichdimensionalen) Vektorraume, die wir jetzt entwickeln wol-len, brauchen wir keine speziellen Eigenschaften des Skalarenkorpers. Sei also K irgendeinKorper.
Definition (K-Vektorraum)
Ein K-Vektorraum ist ein Tupel(V, 0,+, ·) .
Hierbei ist V eine Menge mit einem ausgezeichneten Element 0 und einer Verknupfung +,welche (V, 0,+) zu einer kommutativen Gruppe macht, in welcher 0 das neutrale Elementist.Die skalare Multiplikation · ist eine Abbildung
K× V → V , (α, v) 7→ αv
mit den Eigenschaftenα (v1 + v2) = αv1 + αv2 ,
(α + β)v = αv + βv ,α(βv) = (α · β)v ,
1 · v = v .
Definitionen
a) Eine Teilmenge eines Vektorraums, die gegenuber Addition und skalarer Multipli-kation abgeschlossen ist, heißt ein Teilvektorraum.
b) Der kleinste Teilvektorraum, welcher eine gegebene Familie {vα : α ∈ I} enthalt,heißt die lineare Hulle dieser Familie oder der von der Familie erzeugte Vektorraum.Die Familie heißt ein aufspannendes System fur diesen Vektorraum.
c) Ein Teilvektorraum V heißt endlichdimensional, wenn er ein endliches aufspannen-des System besitzt.
d) Ein endliches aufspannendes System minimaler Lange heißt eine Basis des Teilvek-torraums. Die Lange der Basis heißt die Dimension des Teilvektorraums.
e) Eine Familie {vα : α ∈ I} heißt linear unabhangig, wenn man den Nullvektor nurauf die triviale Weise als Linearkombination der vα darstellen kann.(In unseren K-Vektorraumen gibt es nur endliche Linearkombinationen.)
{vα : α ∈ I} linear unabhangig ⇔(∑
λαvα = 0⇒ ∀ α : λα = 0).
Satz :
Die Dimension eines endlichdimensionalen Vektorraums V ist die maximale Lange eineslinear unabhangigen Tupels.Wenn V n-dimensional ist, dann ist jedes linear unabhangige n-Tupel eine Basis.
Der Beweis wird sich leicht ergeben, wenn wir zuerst einige wichtige Konstruktionenin Vektorraumen diskutieren. Wir konnen den Satz noch etwas anders formulieren.
Satz (Charakterisierung einer Basis)
Sei V ein n-dimensionaler Vektorraum. Dann gilt
a) Jedes linear unabhangige System der Lange n ist ein aufspannendes System.
b) Jedes aufspannende System der Lange n ist ein linear unabhangiges System.
Der Satz weist mehrere Wege, Basen zu konstruieren:a) Wenn ein linear unabhangiges System noch nicht den ganzen Vektorraum V auf-
spannt, dann kann man irgendeinen Vektor, der nicht in der linearen Hulle liegt, hinzu-nehmen, ohne die lineare Unabhangigkeit zu gefahrden.
b) Wenn ein aufspannendes System nicht linear unabhangig ist, dann kann man gewisseVektoren weglassen ohne die lineare Hulle zu verkleinern.
c) Sei {v1, . . . , vn} eine Basis von V und
w = α1 · v1 + . . .+ αnvn .
Wenn ak 6= 0, dann kann man vk durch w ersetzen und erhalt eine neue Basis (”Aus-
tauschlemma“).
Beweis des Austauschlemma
o.B.d.A. nehmen wir an α1 6= 0. Wir konnen dann v1 durch w ersetzen; denn
v1 =1
α1w1 −
n∑
2
αkα1vk
Jedes w = β1v1 +n∑2
βkvk kann auch mit Hilfe des Systems {w, v2, . . . , vn} ausgedruckt
werden
w =β1
α1w +
n∑
2
(βk −
αk · β1
α1
)vk .
Den Austausch notiert man als Pivottransformation eines sog. Spaltentableau.
v1 α1 β1 w 1α1
β1
α1
v2 α2 β2 v2 −α2
α1β2 − α2
α1β1
......
vn αn βn vn −αn
α1βn − αn
α1β1
= w = w = v1 = w
, Seite 111
Diesen Gedanken werden wir spater grundlich verfolgen.
Linearformen, duale Basis
Definition V sei ein K-Vektorraum.
a) Eine K-wertige Funktion ℓ(·) auf V heißt eine Linearform, wenn gilt
ℓ (αv1 + βv2) = α · ℓ (v1) + β · ℓ (v2) fur alle α, β ∈ K , v1, v2 ∈ V .
b) Der Vektorraum aller Linearformen heißt der Dualraum von V und wird mit V ⋆
bezeichnet.
c) Wenn {v1, . . . , v2} eine Basis von V ist und ℓ(1), . . . , ℓ(n) die Linearformen mit
ℓ(i) (vj) =
{1 fur i = j0 fur i 6= j
dann heißt{ℓ(1), . . . , ℓ(n)
}die duale Basis.
Die Bezeichnung”duale Basis“ braucht eine Rechtfertigung. Wir mussen uns uberzeugen.
i) Die ℓ(i)(·) sind linear unabhangig.ii) Die ℓ(i)(·) erzeugen den ganzen Dualraum V ⋆.
Dies ergibt sich aus den folgenden Bemerkungen:
1. Eine Linearform ℓ(·) ist durch ihre Werte in den Basisvektoren vj eindeutig be-stimmt.
ℓ (vj) = βj ⇒ ℓ(∑
αjvj
)=∑
βj · αj .
Es gilt
ℓ(·) =∑
βj · ℓ(j)(·) .
2. Da jedes v ∈ V eine eindeutige Darstellung v =∑αjvj besitzt, sind die Abbildun-
gen v 7−→ αj Linearformen. Sie sind in der Tat die Elemente der dualen Basis. Esgilt
v =∑
ℓ(j)(v) · vj .
Notation : Statt ℓ(v) notiert man 〈ℓ, v〉. Die Abbildung
〈·, ·〉 : V ⋆ × V → K
heißt die naturliche Paarung fur V .
Bemerke
1. Die naturliche Paarung ist bilinear
〈αℓ′ + βℓ′′, · 〉 = α · 〈ℓ′, ·〉+ β · 〈ℓ′′, ·〉〈 ·, αw1 + βw2〉 = α · 〈·, w1〉+ β · 〈·, w2〉 .
2. Jedes v ∈ V liefert eine Linearform auf V ⋆ und jede Linearform auf V ⋆ kommt voneinem v.Man sagt kurz: V ⋆⋆ ist in naturlicher Weise isomorph zu V .
3. Die duale Basis zu{ℓ(1), . . . , ℓ(n)
}ist die ursprungliche Basis {v1, . . . , v2} (wenn man
V ⋆⋆ mit V identifiziert).
Konvention
Wenn man in einem Vektorraum V eine Basis {vj : j ∈ J} ausgezeichnet hat, dann be-schreibt man den Vektor v =
∑αj · vj durch die J-Spalte mit den Eintragen αj . Die
Linearformen ℓ(·), die man auch Covektoren nennt, beschreibt man durch J -Zeilen.ℓ(·) =
∑βj · ℓ(j)(·) ist die Zeile mit den Eintragen βj .
〈ℓ, v〉 ist das”Matrizenprodukt“
∑βj · αj (Zeile × Spalte).
Achtung!
1. Die naturliche Paarung nennt man manchmal das innere Produkt. Man darf diesesinnere Produkt aber nicht mit dem inneren Produkt (
”Skalarprodukt“) in euklidi-
schen Raumen verwechseln.Das Skalarprodukt im euklidischen (bzw. hilbertschen) Raum ist eine Abbildung
〈·|·〉 : V × V → R(bzw. C)
die bilinear (bzw. sesquilinear) ist.
2. Man beachte auch: Aus einem Paar von Spaltenvektoren kann man nicht ohne wei-teres einen Skalar gewinnen; man muss den einen Spaltenvektor zuerst zu einemZeilenvektor machen, z.B. mit Transposition oder durch hermitische Konjugation.
(x, y) 7−→ xT · y oder (x, y) 7−→ x⋆ · y .
Hinweis Bei den d-dimensionalen Mannigfaltigkeiten hat man in jedem Punkt P ∈ Mden Tangentialraum TP . Dies ist der d-dimensionale R-Vektorraum aller Tangentialvek-toren. Sein Dualraum T ⋆P heißt der Cotangentialraum. Das Differential df einer glattenFunktion (
”der Gradient“) liefert in jedem Punkt P einen Covektor.
Die naturliche Paarung macht aus dem Gradienten und dem Tangentialvektor der Kurveγ(·) zu jedem Zeitpunkt t eine reelle Zahl
〈df, γ(t)〉 =d
dtf(γ(t)
).
, Seite 113
Man sagt : Die infinitesimale Anderung der Funktion f entlang der Kurve ist das”innere
Produkt“ des Gradienten mit dem Tangentialvektor.Man sollte bei dieser Aussage nicht denken, dass man eine euklidische Struktur in TPbraucht. Das
”innere Produkt“ ist die naturliche Paarung.
Erganzung (Direkte Summen)
Seien V und W K-Vektorraume. Das kartesische Produkt V × W(d.h. die Gesamtheit
aller Paare (v, w))
besitzt dann in naturlicher Weise eine Vektorraumstruktur
α · (v, w) = (αv, αw)(v1, w1) + (v2, w2) = (v1 + v2, w1 + w2) .
Man nennt diesen Vektorraum die direkte Summe und bezeichnet sie V ⊕W . Zu (v, w) ∈V ×W erhalt man das Element v ⊕ w ∈ V ⊕W .Offenbar gilt :
dim(V ⊕W ) = dimV + dimW .
Wenn (v1, . . . , vn) eine Basis von V ist und (w1, . . . , wm) eine Basis von W , dann ist(v1, . . . , vn, w1, . . . , wm) eine Basis von V ⊕ W . Jedes u ∈ V ⊕ W besitzt genau eineDarstellung u = x1 · v1 + . . .+ xn · vn + y1 ·w1 + . . .+ ym ·wm. Den Dualraum von V ⊕Wkann man mit der direkten Summe V ⋆ ⊕W ⋆ identifizieren.
Hinweis
Wir werden spater zu V,W den Vektorraum V ⊗W , das Tensorprodukt konstruieren. Mandarf das Zeichen ⊗ nicht mit dem Zeichen × fur das mengentheoretische cartesische Pro-dukt verwechseln. Das Tensorprodukt ist ein Vektorraum der Dimension (dim V )·(dimW );die Elemente sind Objekte einer neuen Art. Die Physiker kennen Tragheitstensoren, Span-nungstensoren und dergleichen mehr. Bei der Taylor-Formel sind wir auch schon Tensorenhoherer Stufe begegnet. Die abstrakte Konstruktion der Tensorprodukte verschieben wirauf spater.
53. Vorlesung : k-Vektoren und alternierende k-Formen
(Dieser Abschnitt kann beim ersten Lesen ubersprungen werden. Das Thema kann ge-wiss nicht in einer einzigen Doppelstunde grundlich abgehandelt werden. Man kann denAnfangern wohl nur andeuten, wie sich die Determinanten in die moderne multilineareAlgebra einfugen.)
Definition (k-Vektoren uber V )
V ist ein n-dimensionaler Vektorraum. Fur k = 1, 2, . . . , n definieren wir einen Vektor-raum ΛkV (wobei Λ1V = V ). Dieser Vektorraum heißt der Vektorraum der k-Vektorenuber V . Die Elemente g gewinnt man als formale Linearkombinationen von k-fachen
”Dachprodukten“ w1 ∧ . . . ∧ wk. Dabei sind
∑
α
aα · (wα1 ∧ . . . ∧ wαk) und
∑
β
aβ · (wβ1 ∧ . . . ∧ wβk)
als gleich zu betrachten, wenn sie mit Hilfe der folgenden Regeln ineinander umgerechnetwerden konnen
(i) Fur jedes k-Tupel von Vektoren und jede Permutation (σ1, . . . , σk) gilt
1 · (wσ1 ∧ . . . ∧ wσk) = (signσ) · (w1 ∧ . . . ∧ wk)
(ii) fur alle λ, µ ∈ K gilt
λ · (µw1 ∧ w2 ∧ . . . ∧ wk) = 1 · (λµw1) ∧ w2 ∧ . . . ∧ wk
(Statt 1 · (w1 ∧ . . . ∧ wk) schreiben wir auch einfach w1 ∧ . . . ∧ wk)
(iii) (w′1 + w′′
1) ∧ w2 ∧ . . . ∧ wk = w′1 ∧ w2 ∧ . . . ∧ wk + w′′
1 ∧ w2 ∧ . . . ∧ wk .
Bemerke :
Wenn in einem Dachprodukt der Nullvektor vorkommt, dann ist das Dachprodukt dasNullelement von ΛkV . Ebenso leicht beweist man: Wenn in einem Dachprodukt zwei glei-che Vektoren vorkommen, dann ist das Dachprodukt das Nullelement. Wenn sich irgendein wj als Linearkombination der ubrigen Vektoren darstellen laßt, dann ist das Dachpro-dukt das Nullelement.
Wer den Verdacht hegt, dass man moglicherweise jede formale Linearkombination in dasNullelement umrechnen kann, wird durch die folgenden Rechnungen eines Besseren be-lehrt. Wir werden sehen, dass ΛkV ein
(nk
)-dimensionaler Vektorraum ist. Man kann also(
nk
)linear unabhangige Elemente finden und mit diesen kann man dann jedes Element
von ΛkV in eindeutiger Weise linear kombinieren. Bei der Wahl der Basis hat man großeFreiheiten. Die beliebtesten Basen von ΛkV sind die, die von einer Basis von V herruhren.Diese Basen haben enge Beziehungen zum Kalkul der Determinanten.
, Seite 115
Beispiel
V sei der Vektorraum der Verschiebungen des dreidimensionalen Anschauungsraums.e1, e2, e3 sei eine (positiv orientierte) Orthonormalbasis.Jedes Dachprodukt a ∧ b laßt sich auf eindeutige Weise als Linearkombination der spezi-ellen Dachprodukte
e2 ∧ e3, e3 ∧ e1, e1 ∧ e2 darstellen .
Dies sieht man folgendermaßen
a = a1 · e1 + a2 · e2 + a3 · e3
b = b1 · e1 + b1 · e2 + b3 · e3
a ∧ b = (a1 · e1 + a2 · e2 + a3 · e3) ∧ (b1 · e1 + b2 · e2 + b3 · e3)= α · e2 ∧ e3 + βe3 ∧ e1 + γ · e1 ∧ e2 mit
α =
∣∣∣∣a2 b2
a3 b3
∣∣∣∣ ; β =
∣∣∣∣a3 b3
a1 b1
∣∣∣∣ ; γ =
∣∣∣∣a1 b1
a2 b2
∣∣∣∣
Hinweise
1. Wir bemerken, dass (α, β, γ) die Koeffizienten im traditionellen Vektorprodukt a×b
sind. Die Physiker definieren bekanntlich in der Tradition der”Vektoranalysis“:
a× b = α · e1 + β · e2 + γ · e3 .
Man beachte aber, dass die Ersetzung
e2 ∧ e3 ←→ e1 , e3 ∧ e1 ←→ e2 , e1 ∧ e2 ←→ e3
an die euklidische Struktur (und die Orientierung) gebunden ist. In allgemeinendreidimensionalen Vektorraumen gibt es keinen irgendwie naturlichen Isomorphis-mus von V und Λ2V .
2. Auch die Physiker wissen naturlich, dass die Elemente von Λ2V etwas anderes sindals die ublichen Vektoren; wenn sie genau sein wollen, nennen sie die Elemente vonΛ2V
”polare Vektoren“, im Gegensatz zu den
”axialen“ Vektoren v ∈ V .
Bemerke :
1. Eine Besonderheit der n-dimensionalen Vektorraumen Λn−1V besteht darin, dassman jedes Element als Dachprodukt schreiben kann. Zu jedem p ∈ Λn−1V istnamlich die Menge der Vektoren w mit p ∧ w = 0 ein (n − 1)-dimensionaler Vek-torraum. Wenn w1, . . . , wn−1 eine Basis dieses Vektorraums ist, dann existiert einλ ∈ K, so dass
p = λ · (w1 ∧ . . . ∧ wn−1) .
2. Die k-fachen Dachprodukte (k 6= 1 , n− 1) bilden keinen Vektorraum, man brauchtLinearkombinationen von Dachprodukten.Das Beispiel n = 3, k = 2 sollte nicht zu falschen Vorstellungen verfuhren.
Satz
Sei {v1, . . . , vn} eine Basis von V .Fur K ⊆ {1, 2, . . . , n} mit der Machtigkeit k definieren wir
vK := vn1 ∧ vn2 ∧ . . . ∧ vnk,
wobei 1 ≤ n1 < n2 < . . . < nk ≤ n die Elemente von K sind.Jedes p ∈ ΛkV besitzt dann eine Darstellung
p =∑
aK · vK ,
wobei die Summe uber aller k-Teilmengen K ⊆ {1, 2, . . . , n} zu erstrecken ist.
Beweis
1. Es genugt, die Dachprodukte
p = w1 ∧ . . . ∧ wkzu untersuchen. Die wj stellen wir mit Hilfe der gegebenen Basis dar:
wj =∑
i
viaij fur j = 1, . . . , k .
Die Koeffizienten bilden eine n× k-Matrix A.
2. AK sei die k × k-Matrix, die wir aus A gewinnen, indem wir alle diejenigen Zeilenstreichen, die nicht zu K gehoren. Wir notieren
v1 a(1)1 · · · a
(1)k aK = detAK =
...... =
∑σ
(signσ) · an1σ1· an2
σ2· . . . · ank
σk
////// ////// //////...
... wobei die Summe fur alle Permutationen...
... von K zu erstrecken ist.////// ////// //////////// ////// //////
......
vn a(n)1 · · · a
(n)k
= w1 · · · = wk
3. Nach unseren Umrechnungsregeln (i), (ii), (iii) gilt
w1 ∧ . . . ∧ wk =(∑
vi1 · ai11)∧(∑
vi1 · ai22)∧ . . . ∧
(∑vik · aikk
)
=∑
i1,...,ik
ai11 · ai22 . . . · aikk · (vi1 ∧ vi2 ∧ . . . ∧ vik) .
, Seite 117
Die Summanden, in welchen zwei Summationsindizes gleich sind, liefern keinen Bei-trag. Die anderen sortieren wir nach den k-Teilmengen K; und wir bringen dieIndizes in aufsteigenden Reihenfolge.
4. Somit ergit sich
w1 ∧ . . . ∧ wk =∑
aK · vK . q.e.d.
Die Determinanten aK nennt man die k × k-Minoren der Matrix A. Wer den Ver-dacht hegt, dass man moglicherweise manche Summen
∑bK · vK durch geschickte
Anwendung der Rechenregeln in das Nullelement umrechnen kann, wird durch diefolgende Uberlegung eines Besseren belehrt. Wir werden sehen, dass jede formaleSumme
p =∑
aα · (wα1 ∧ . . . ∧ wαk)
genau eine Darstellung
p =∑
aK · vK besitzt.
M.a.W., die vK sind linear unabhangig in ΛkV .
Definition (Alternierende Multilinearformen)
Eine alternierende k-Form (fur den n-dimensionalen K-Vektorraum V ) ist eine K-wertigeFunktion Φ(·) auf dem kartesischen Produkt V × V × . . .× V mit den Eigenschaften
i⋆) Φ (wσ1 , . . . , wσk) = (signσ) ·Φ (w1, . . . , wk) fur alle k-Tupel w1, . . . , wk und alle Per-
mutationen σ.
ii⋆) Φ (λw1, w2, . . . , wk) = λ · Φ (w1, w2, . . . , wk) fur alle λ ∈ K.
iii⋆) Φ (w′1 + w′′
2 , . . . , wk) = Φ (w′1, w2, . . . , wk) + Φ (w′′
1 , w2, . . . , wk) .
Den K-Vektorraum der alternierenden k-Formen bezeichnet man mit ΛkV ⋆.
Beispiel
ℓ(1)(·), . . . , ℓ(k)(·) seien Linearformen auf V . Wir definieren dazu
Φ (w1, . . . , wk) = det(〈ℓ(i), wj〉
)fur alle w1, . . . , wk .
Φ ist eine alternierende k-Form.
Bemerke
Die alternierenden 1-Formen sind die Linearformen, Λ1V ⋆ = V ⋆.Die alternierenden n-Formen haben wir bereits fruher untersucht; wir haben sie die Vo-lumenmessungen genannt.Es ist ublich auch Λ◦V ⋆ zu definieren; man identifiziert die Elemente mit den Skalaren.
Die Notation ΛkV ⋆ bedarf einer Rechtfertigung. Wir haben ΛkW fur jeden Vektorraumdefiniert. Somit ware also ΛkV ⋆ der Vektorraum aller k-Vektoren uber V ⋆. Das passt gut;denn es gilt der
Satz 1 ΛkV ⋆ = Λk (V ⋆) =(ΛkV
)⋆
1. Jedes Dachprodukt ℓ(1) ∧ . . . ∧ ℓ(k) kann als eine Linearform auf ΛkV verstandenwerden. In der Tat kann jede alternierende k-Form Φ(·) auf V × . . . × V zu einerLinearform auf ΛkV fortgesetzt werden.
2. Jede Linearform λ(·) auf ΛkV ist eine Linearkombination solcher spezieller k-Formen
λ(·) =∑
bβ · ℓ(β1) ∧ . . . ∧ ℓ(βk) .
3. Zwei solche Summen sind (als alternierende k-Formen) genau dann gleich, wennsie sich vermoge der Umrechnungsregeln (i), (ii), (iii) in einem ΛkW (hier Λk (V ⋆)ineinander umrechnen lassen.
Der Beweis dieser Aussagen wird sich aus den folgenden Konstruktionen sehr leicht erge-ben. Wir werden dabei auch beweisen:
Satz 2 (Duale Basen)
Sei {v1, . . . , vn} eine Basis von V und{ℓ(1), . . . , ℓ(n)
}die duale Basis fur V ⋆.
Dann ist {vK : |K| = k} eine Basis von ΛkV und die duale Basis fur ΛkV ⋆ ist{ℓ(K) : |K| = k
}.
(Fur eine k-Teilmenge K von {1, . . . , n} bezeichnet λ(K) das Dachprodukt
λ(K) = ℓn1 ∧ . . . ∧ ℓnk ,
wobei die ni die aufsteigend geordneten Elemente von K sind.)Wir nahern uns dem Beweis der beiden Satze mit einigen elementaren Feststellungen:
Proposition 1
{v1, . . . , vn} sei eine Basis von V , M(·) eine Multilinearform auf dem k-fachen cartesischenProdukt V × . . .× V .M(·) ist dann durch seine Werte auf den k-Tupeln (vi1 , vi2 , . . . , vik) eindeutig bestimmt.Wenn M(·) eine alternierende k-Form ist, dann braucht man nur die Werte in den(vn1 , . . . , vnk
) mit n1 < n2 . . . < nk zu kennen, um M(·) zu identifizieren.
Corollar
Der Vektorraum der alternierenden k-Formen hat hochstens die Dimension(nk
).
Proposition 2
Sei Ψ(·) eine Linearform auf ΛkV und Φ(·) die Einschrankung auf die Dachprodukte
Φ (w1, . . . , wk) := Ψ (v1 ∧ . . . ∧ wk) .
Dann ist Ψ(·) durch Φ(·) eindeutig bestimmt.
, Seite 119
Proposition 3
Zu jeder alternierenden k-Form Φ(·) gibt es genau eine Fortsetzung zu einer Linearformauf ΛkV .
Beweis :
Die Zuweisung∑
aαwα1 ∧ . . . ∧ wαn7−→
∑aα · Φ (wα1 , . . . , wαk
)
ist vertraglich mit den Rechenregeln (i), (ii), (iii) in ΛkV . q.e.d.
Die im Beispiel konstruierten alternierenden k-Formen bezeichnen wir vorubergehendmit
Φ(λ(1), . . . , λ(k)
).
Bemerke :
(i) Wenn wir zwei der λ(i) vertauschen, dann entsteht die k-Form −Φ(·).
(ii) Wenn wir ein λ(i) mit dem Skalar c multiplizieren, dann entsteht die k-Form c ·Φ(·).
(iii) Wenn wir λ(1) als Summe schreiben λ(1) = λ(i)| + λ
(i)‖ , dann ist Φ(·) die Summe
Φ(λ(1), λ(2), . . . , λ(k); ·
)= Φ
(λ
(1)| , λ(2), . . . , λ(k); ·
)+ Φ
(λ
(1)‖ , λ(2), . . . , λ(k); ·
)
Daraus ergibt sich die
Proposition 4
Eine Linearkombination der speziellen k-Formen Φ(λ(1), λ(2), . . . , λ(k)
)hangt nur von dem
entsprechenden Element in ΛkV ⋆ ab∑
bβ · Φ(λβ1, . . . , λβk; ·
)= 〈∑
bβ · λβ1 ∧ . . . ∧ λβk , · 〉 .
Jedes Element von Λk(V ⋆) liefert eine alternierende k-Form und damit eine Linearformauf ΛkV . Dabei gilt fur die Dachprodukte:
〈λ(1) ∧ . . . ∧ λ(k);w1 . . . ∧ wk〉 = det(〈λ(i), wj〉
).
Der Satz von den dualen Basen liegt nun auf der Hand. Wenn {v1, . . . , vn} und{ℓ(1), . . . , ℓ(n)
}zueinander duale Basen sind, dann gilt fur jedes Paar von k-Tupeln
(i1, . . . , ik) (j1, . . . , jk) :
〈λi1 ∧ . . . ∧ λ(ik), wj1 ∧ . . . ∧ wjk〉 =
=
= 0 , wenn die beiden k-Tupel nicht dieselbe Teilmenge K aufzahlen
= sign
(i1 . . . ikj1 . . . jk
), sonst
Konstruktion der Graßmann-Algebra
Wir haben somit Paare zueinander dualer Vektorraume konstruiert :ΛkV und ΛkV ⋆ fur k = 0, 1, . . . , n sind zueinander dual.Man betrachtet dazu die direkten Summen
Λ◦V ⊕ Λ1V ⊕ . . .⊕ ΛnV und Λ◦V ⋆ ⊕ Λ1V ⋆ ⊕ . . .⊕ ΛnV ⋆ .
Dies sind zueinander duale 2n-dimensionale Vektorraume(2n = 1 + n +
(n2
)+ . . .+
(nn+1
)+ 1).
(Was direkte Summen von Vektorraumen sind, haben wir im Anhang zur 52. Vorlesungerlautert.)Die Elemente von ΛkV heißen die homogenen Elemente vom Grad k. Fruher war es ublich,die Elemente von ΛkV Großen k-ter Stufe zu nennen.
Satz (Existenz des Dachprodukts)
Sei p ∈ ΛkV und q ∈ ΛℓV
p =∑aαvα1 ∧ . . . ∧ wαk
q =∑bβwβ1 ∧ . . . ∧ wβℓ
.Es existiert dann ein wohlbestimmtes Element
p ∧ q ∈ Λk+ℓV .
Anders gesagt: ∑
α,β
aαbβ · wα1 ∧ . . . ∧ wαk∧ wβ1 ∧ . . . ∧ wβρ
ist unabhangig von der Darstellung der Faktoren p und q.
Beweis :
Bei jeder der Rechenregeln (i), (ii), (iii), auf den ersten oder auf den zweiten Faktor ange-wandt, bleibt das bilinear ausmultiplizierte Produkt als Element in Λk+ℓV unverandert.q.e.d.
Satz
Fur das Dachprodukt auf der graduierten Algebra
ΛV := Λ◦V ⊕ Λ1V ⊕ . . .⊕ ΛnV
gilt
(i) (p ∧ q) ∧ r = p ∧ (q ∧ r) (Assoziativitat)(ii) (p1 + p2) ∧ q = p1 ∧ q + p2 ∧ q
p ∧ (q1 + q2) = p ∧ q1 + p ∧ q2 (Distributivitat)(iii) p ∈ ΛkV , q ∈ ΛℓV =⇒ q ∧ p = (−1)k·ℓ · p ∧ q
, Seite 121
54. Vorlesung : Minoren, Cofaktoren, Cramer’sche Regel
Wir wollen die Konstruktion der k-Vektoren auf einige klassische Themen der Determi-nantenlehre anwenden.
I. Die Minoren einer Matrix
Wenn man aus einer m×n-Matrix A einige Spalten und einige Zeilen streicht, sodass nurnoch die Zeilen zu den Indizes ∈ K und die Spalten zu den Indizes ∈ H ubrig bleiben(|H| = k = |K|
), so erhalt man eine k × k-Teilmatrix, die wir mit AKH bezeichnen.
(Mit dem oberen Index werden bei uns die Zeilen indiziert, der untere Index verweist aufSpalten.)
detAKH heißt der Minor zu K ×H .
Hier ubernehmen wir die Anordnung der Zeilen und Spalten von der ursprunglichen An-ordnung in der Matrix A.
1 ≤ m1 < m2 < . . .mk ≤ m mit {m1, . . . , mk} = K1 ≤ n1 < n2 . . . < nk ≤ n mit {n1, . . . , nk} = H .
m
...
◦ ◦ ◦
◦ ◦ ◦
◦ ◦ ◦
K
...1
1 . . . H . . . n
Satz (Spezielle Basiswechsel in ΛkV )
Seien {v1, . . . , vn} und {w1, . . . , wn} Basen von V(w1, . . . , wn) = (v1, . . . , vn) · A , wj =
∑vi · aij ;
(v1, . . . , vn) = (w1, . . . , wn) · B , vi =∑wj · bji .
Fur k-Teilmengen K und H ⊆ {1, 2, . . . , n} definieren wirvK = vm1 ∧ . . . ∧ vmk
mit 1 ≤ m1 < . . . < mk ≤ m = n
wH = wn1 ∧ . . . ∧ vnkmit 1 ≤ n1 < . . . < nk ≤ n.
Sowohl die {vK : |K| = k} als auch die {wH : |H| = k} sind eine Basis von ΛkV .Die Eintrage in der Matrix des Basiswechsels sind die Minoren. Es gilt
wH =∑K
vK · det(AKH)
vK =∑H
wH · det(BHK
).
Beweis
Sei n1 < n2 < . . . < nk mit {n1, . . . , nk} = H . Dann gilt
wH =(∑
vi1 · ai1n1
)∧ . . . ∧
(∑vik · aiknk
)
=∑i1...ik
ai1n1. . . aiknk
· vi1 ∧ . . . ∧ vik .
Wir sammeln nach den (i1, . . . , ik) mit {i1, . . . , ik} = K und stellen die Faktoren in auf-steigende Reihenfolge. signσ sei das Vorzeichen dieser Permutation.
wn1 ∧ . . . ∧ wnk=∑
K
vK ·∑
signσ · ai1n1· . . . · aiknk
=∑
vK · det(AKH)
q.e.d.
II. Cofaktoren und der Laplace’sche Entwicklungssatz
Definition
A =(aij)
sei eine n× n-Matrix.Man streiche die h-te Spalte und die k-te Zeile. Man gewinnt den Cofaktor Ch
k zu akh (inder Matrix A) aus der Determinante dieser Matrix
Chk := (−1)h+k · detAKH .
Der Name wird erklarlich, wenn man bedenkt, dass in der expliziten Formel
detA =∑
(signσ)ai11 · . . . · ainn
Terme auftreten, die akh als Faktor enthalten. Der Cofactor hangt nur von der MatrixAKH ab, und es zeigt sich, dass er bis auf das Vorzeichen (−1)h+k die Determinante dieserMatrix ist.
Theorem
Die Matrix der Cofactoren von A ist bis auf den Faktor detA die Inverse A−1.
∑
k
Chk · akj =
{detA falls h = j
0 falls h 6= j
Den Beweis fuhren wir mit Hilfe der Cramer’schen Regel im nachsten Abschnitt. DieFormel im Falle h = j heißt der Lapace’sche Entwicklungssatz fur die j-te Spalte.
, Seite 123
Spezialfalle Wir zeigen das Prinzip des Entwicklungssatzes fur eine 3×3-Matrix, derenDeterminante wir nach der ersten Spalte entwickeln (h = j = 1)
det
a1 b1 c1
a2 b2 c2
a3 b3 c3
= a1 · det
(b2 c2
b3 c3
)− a2 · det
(b1 c1
b3 c3
)+ a3 · det
(b1 c1
b2 c2
).
Fur eine 2 × 2-Matrix sind die Cofaktoren sehr einfach zu berechnen. Man findet daherauch die Inverse sehr leicht
(a bc d
)−1
=1
ad− bc ·(
d −b−c a
).
Eine wichtige Konsequenz des Theorems ist der
Satz
Sei A eine invertierbare n × n-Matrix mit ganzzahligen Eintragen. Wenn detA = +1,dann hat auch die Inverse ganzzahlige Eintrage.
Beweis : Die Eintrage der inversen Matrix sind gerade die Cofaktoren.
III. Die Cramer’sche Regel
Satz : Sei A eine (n× n)-Matrix vom vollen Rang n.Jeden vorgegebenen Spaltenvektor kann man auf genau eine Weise als Linearkombinationder Spalten a1, . . . , an der Matrix A schreiben
a1 · x1 + . . .+ an · xn = b .
Es gilt
xj =1
detA· detBj fur j = 1, . . . , n ,
wo Bj aus A dadurch entsteht, dass man die j-te Spalte durch b ersetzt.
Beweis :
Wir betrachten das Dachprodukt von∑
ajxj = b mit
a1 ∧ . . . ∧ /aj ∧ . . . an = aK , K = {1, 2, . . . /j, . . . , n} .
Auf der linken Seite liefert nur der j-te Summand eine Beitrag, namlich
xj · (−1)j−1 · detA · e1 ∧ . . . ∧ en .
Die rechte Seite ist (−1)j−1 · detBj · e1 ∧ . . . ∧ en. q.e.d.(Hier bezeichnen die ei die Einheitsspalten, also aj =
∑eia
ij.)
Besonders interessant sind die rechten Seiten ei; die Losungen xji sind dann namlich dieEintrage von A−1
ai · x1i + . . .+ an · xni = ei
∑
j
ahj · xji =
{1 falls h = i0 falls h 6= i
Auf der anderen Seite ist detEji der Minor zur Position (i, j).
So liefert die Cramer’sche Regel die Koeffizienten
xji =1
detA· Cj
i .
Damit ist das Theorem bewiesen, aus welchem wir den Laplace’schen Entwicklungssatzhergeleitet haben.
IV. Basiswechsel bei polaren und axialen Vektoren
{v1, v2, v3} und {w1, w2, w3} seien Basen im dreidimensionalen euklidischen Anschauungs-raum mit v1 ∧ v2 ∧ v3 = w1 ∧ w2 ∧ w3
(w1, w2, w3) = (v1, v2, v3) · A(v1, v2, v3) = (w1, w2, w3) · B .
Wir haben also detA = 1.
1. Fur die Koordinaten
x1
x2
x3
bzgl. der vj und
y1
y2
y3
bzgl. der wi
haben wir dannv =
∑xj · vj =
∑yiwi .
Das ergibt fur die Koeffizienten den Zusammenhang
v = (v1, v2, v3)
x1
x2
x3
= (w1, w2, w3)B
x1
x2
x3
= (w1, w2, w3)
y1
y2
y3
Bx = y , und x = Ay .
2. Die polaren Vektoren, das sind die Elemente von Λ2V konnen wir mit den Basen
(V1, V2, V3) = (v2 ∧ v3, v1 ∧ v3, v1 ∧ v2) oder(W1,W2,W3) = (w2 ∧ w3, w1 ∧ w3, w1 ∧ w2) ausdrucken .
, Seite 125
Nach dem Satz vom Basiswechsel in ΛkV haben wir
Wh = wH =∑
K
vK · det(AKH)
=∑
k
Vk · (−1)h+k · Chk .
Hier haben wir, wegen B = A−1 und detA = 1,
Chk = bhk .
Die Formel wird ubersichtlicher, wenn wir die Basen (W1,−W2,W3) und (V1,−V2, V3)wahlen. Im Falle der Gleichorientierung detA = 1 haben wir:
(W1,−W2,W3) = (V1,−V2, V3) · B .
Stellen wir den polaren Vektor p in diesen Koordinatensystemen dar
α1 · (v2 ∧ v3) + α2 · (v3 ∧ v1) + α3 · (v1 ∧ v2) =
p =β1 · (w2 ∧ w3) + β2 · (w3 ∧ w1) + β3 · (w1 ∧ w2) .
p = (V1,−V2, V3)
α1
α2
α3
= (W1,−W2,W3)
β1
β2
β3
=
= (V1,−V2, V3)B
β1
β2
β3
α = Bβ also β = Aα
Beachte : Die Physiker interessieren sich fur diese Umrechnung nur in dem Fall, wo diev und die w gleich orientierte Orthonormalbasen sind. Das ist der Fall A · AT = I. DieseVoraussetzung hat ihren guten Sinn, wenn man Wert legt auf die
”Identifizierung“
v1 ↔ v2 ∧ v3, v2 ↔ v3 ∧ v1, v3 ↔ v1 ∧ v2
w1 ↔ w2 ∧ w3, w2 ↔ w3 ∧ w1, w3 ↔ w1 ∧ w2 .
Unsere Umrechnung brauchte keine euklidische Struktur.
55. Vorlesung : Nullraume, Kern und Bild einer linearen Abbil-
dung
V und V ⋆ seien zueinander duale n-dimensionale K-Vektorraume. 〈·, ·〉 bezeichne dienaturliche Paarung.
Definition
a) Der Nullraum zu einer Menge E von Vektoren ist
NE :={ℓ : ℓ ∈ V ⋆, 〈ℓ, v〉 = 0 fur alle v ∈ E
}⊆ V ⋆ .
b) Der Nullraum zur Menge F ⊆ V ⋆ ist
NF :={v : v ∈ V, 〈ℓ, v〉 = 0 fur alle ℓ ∈ F
}⊆ V .
Dieser Nullraum heißt auch die Losungsmenge des homogenen Gleichungssystems
〈ℓ, v〉 = 0 fur alle ℓ ∈ V .
Wir schreiben auch E† statt NE und F † statt NF (Gelesen :”E Dolch“,
”E Dagger“).
Ohne viel nachzudenken, kann man schon einmal bemerken:
1. Nullraume sind stets Teilvektorraume von V oder von V ⋆.
2. E ⊆ E††; denn v ∈ E ⇒ ∀ ℓ ∈ E† 〈ℓ, v〉 = 0⇒ v ∈ E††.Ebenso sieht man F ⊆ F ††.
3. Je großer F ist, desto kleiner ist der Nullraum F †.
4. Wenn F1 und F2 denselben Teilvektorraum aufspannen, dann gilt F †1 = F †
2 .
5. F ††† = F †; denn einerseits F †† ⊇ F , also F ††† ⊆ F †, und andererseits(F †)†† ⊇ F †.
Satz (Satz vom Rang)
Wenn F einen r-dimensionalen Teilraum aufspannt, dann hat F † die Dimension n − r.Der von F aufgespannte Teilraum ist F ††.
Beweis
1. In F gibt es ein linear unabhangiges r-Tupel ℓ(1), . . . , ℓ(r). Dieses konnen wir zu einerBasis von V ⋆ erganzen: ℓ(1), . . . , ℓ(r), ℓ(r+1), . . . , ℓ(n). Sei nun v1, . . . , vr, vr+1, . . . , vndie duale Basis.{vr+1, . . . , vn} ist dann eine Basis der Nullraums F †; denn genau dann gilt
ℓ(i)(∑
αkvk
)= 0 fur i = 1, . . . , r
wenn αk = 0 fur k = 1, . . . , r .
2. Eine Linearform ℓ(·) verschwindet genau dann auf dem”Losungsraum“ F † des Glei-
chungssystems zu F , wenn ℓ(·) in der linearen Hulle von F liegt.
, Seite 127
Hinweis : Diese Einsicht haben wir bei der Herleitung der Lagrange-Multiplikatorenbenutzt. Wenn eine Linearform auf dem Tangentialraum TP der Untermannigfaltigkeit{P : g(P ) = g(P )
}verschwindet, dann ist sie eine Linearkombination der Gradienten
dg(i) im Punkt P .
Definition
V1 und V2 seien n-dimensionale Vektorraume.Eine Bilinearform
b(·, ·) : V1 × V2 → K
heißt nichtausgeartet, wenn fur kein v1 6= 0 die Linearform b (v1, ·) die Nullform ist,und auch fur kein v2 6= 0 b (·, v2) identisch 0 ist. (Die naturliche Paarung ist eine solchenichtausgeartete Bilinearform auf V ⋆ × V ).
Konstruktion
Sei b(·, ·) nicht ausgeartet. Wir definieren fur E ⊆ V2 den Nullraum bzgl. b(·, ·)
Eb : ={v1 : b (v1, v2) = 0 fur alle v2 ∈ E
}⊆ E1
und ebenso zu F ⊆ V1 den Nullraum
F b : ={v2 : b (v1, v2) = 0 fur alle v1 ∈ F
}⊆ E2 .
Fur diese Konstruktion sieht man wie oben
(i) E1 ⊆ E2 ⇒ Eb1 ⊇ Eb
2
(ii) Ebbb = Eb
(iii) Ebb = span E
(iv) dimE = r ⇒ dimEb = n− r
Beispiel
b(·, ·) sei das Skalarprodukt 〈·|·〉 in einem n-dimensionalen euklidischen Raum (V, ‖ · ‖).In diesem Fall nennt man den Nullraum zu E ⊆ V ublicherweise das orthogonale Kom-plement zu E (oder zur linearen Hulle von E). Man notiert E⊥ (sprich:
”E senkrecht“)
E⊥ ={v : 〈v|w〉 = 0 fur alle w ∈ E
}
Hinweis :
Sei (V, ‖·‖) ein unendlichdimensionaler Hilbertraum. Auch hier definiert man E⊥ fur jedeMenge von Vektoren. Hier ist E⊥ ein abgeschlossener Teilraum von V und E⊥⊥ ist dieabgeschlossene lineare Hulle von E.
Satz (”Duale Abbildung“)
Im endlich-dimensionalen Fall existiert zu jeder linearen Abbildung
ϕ : V → U
genau eine lineare Abbildungϕ⋆ : V ⋆ ← U⋆ .
sodass gilt∀ v ∈ V , k ∈ U⋆ 〈k, ϕ(v)〉 = 〈ϕ⋆(k), v〉 .
Beweis :
Fur jedes k ∈ U⋆ ist 〈k, ϕ(·)〉 eine Linearform auf V . Nennen wir sie ϕ⋆(k).ϕ⋆ ist eine lineare Abildung. Es gilt ϕ⋆⋆ = ϕ.
Hintereinanderschalten linearer Abbildungen fuhrt zum Hintereinanderschalten derdualen Abbildungen. Man muss aber naturlich die Reihenfolge beachten.
V1ϕ−→ V2
ψ−→ V3
.
.................................
...............................
..................
............
.............................
..............................
...............................
.................................�χ
V ⋆1
ϕ⋆
←− V ⋆2
ψ⋆
←− V ⋆3
.
.............................
............................
...........................
.................
........
........................
.........................
..........................
..........................
...........................I
χ⋆
χ(·) = ψ(ϕ(·)
)⇒ χ⋆(·) = ϕ⋆
(ψ⋆(·)
).
Beispiel
V sei der Raum der J-Spalten (dimV = |J | = n)U sei der Raum der I-Spalten (dimU = |I| = m)Jede I × J-Matrix A liefert eine lineare Abbildung
ϕ : V → U v 7→ Av
U⋆ ist der Raum der I-Zeilen ξ = (ξi)iV ⋆ ist der Raum der J-Zeilen η = (ηj)j
ϕ⋆ : V ⋆ ← U⋆ ξ 7→ ξA = η .
Aus der Matrizenrechnung wissen wir namlich
〈ξ, Av〉 = ξ · A · v = 〈ξA, v〉 fur alle v ∈ V, ξ ∈ U⋆ .
Das Hintereinanderschalten solcher Abbildungen wird durch das Matrizenprodukt be-werkstelligt.
, Seite 129
Definition (Kern und Bild)
Sei ϕ : V → U eine lineare Abbildung. Wir definierena) ker ϕ :=
{v : ϕ(v) = 0
}⊆ V (
”Kern von ϕ“)
b) im ϕ :={u : u = ϕ(v) fur ein v ∈ V
}⊆ U (
”Bildraum“)
(Der Vektorraum U heißt der”Zielraum“ fur ϕ.)
Rang (ϕ) = dim(im ϕ).
Ebenso definiert man
kerϕ⋆ ⊆ U⋆ , im ϕ⋆ ⊆ V ⋆ , Rang (ϕ⋆) = dim(im ϕ⋆) .
Satz : (Satz vom Rang einer Abbildung)a) Rang (ϕ) = Rang (ϕ⋆)b) ker ϕ ist der Nullraum von im ϕ⋆ und ker (ϕ⋆) = (im ϕ)†.
Beweis
1. Sei dimV = n, dimU = m und dim(kerϕ) = n− r.vr−1, . . . , vn sei eine Basis von kerϕ. Wir erganzen dieses linear unabhangiges (n−r)-Tupel zu einer Basis von V : v1, . . . , vr, welche durch ϕ in die 0 abgebildet wird.Also
v = α1 · v1 + . . .+ αr · vr , ϕ(v) = 0 ⇒ α1 = . . . = αr = 0d.h. α1 · ϕ (v1) , . . . , α
r · ϕ (vr) = 0 ⇒ α1 = . . . = αr = 0 .
Die Bilder ϕ (v1) , . . . , ϕ (vr) sind also linear unabhangig und liefern somit eine Basisvon im ϕ. dim(im ϕ) = r.
2. Es gilt
ker(ϕ⋆) ={k : k ∈ U⋆ , ϕ⋆(k) = 0
}
={k : 〈ϕ⋆(k), v〉 = 0 fur alle v ∈ V
}
={k : 〈k, ϕ(v)〉 = 0 fur alle v ∈ V
}
={k : 〈k, ·〉 verschwindet auf im ϕ
}= (im ϕ)† .
Nach dem Satz vom Rang haben wir dim(kerϕ⋆) = m− r.
3. Mit dem Schluß von oben erhalten wir dim(im ϕ⋆) = r.
Beispiel (Zeilenrang = Spaltenrang)
Die I×J-Matrix A bildet die J-Spalten in I-Spalten ab. Die Spalten der Matrix spannendas Bild auf. Die Dimension des von den Spalten aufgespannten Vektorraums heißt derSpaltenrang der Matrix A. Die duale Abbildung bildet die I-Spalten in J-Zeilen ab.Die Zeilen von A spannen das Bild auf. Die Dimension des von den Zeilen aufgespanntenVektorraums heißt der Zeilenrang der Matrix A. Da ϕ und ϕ⋆ denselben Rang haben,gilt fur jede Matrix: Zeilenrang = Spaltenrang.
Satz
ϕ : V → U sei eine lineare Abibldung. Die Gleichung ϕ(v) = u hat genau dann eineLosung, wenn u ∈ im ϕ. In diesem Fall gewinnt man alle Losungen dadurch, dass man zueiner speziellen Losung alle Losungen der homogenen Gleichung (d.h. die Elemente derKerne dazu addiert. Wenn ϕ den Rang r hat, dann hat das Bild imϕ die Dimension rund der Kern kerϕ die Dimension n− r.
Sprechweisen
a) Eine lineare Abbildungϕ : V → U
heißt auch ein Vektorraum-Homomorphismus.
b) Wenn U = V , dann spricht man von einem Endomorphismus.
c) Eine injektive (surjektive) lineare Abbildung nannte man fruher auch gerne einenMonomorphismus (bzw Epimorphismus).
d) Wenn eine lineare Abbildung eines endlich-dimensionalen Vektorraums injektiv undsurjektiv (also bijektiv) ist, dann ist die Umkehrabbildung ebenfalls eine lineareAbbildung. Man spricht in diesem Fall von einem Vektorraumisomorphismus.
Beispiel
Wenn man in einem endlichdimensionalen Vektorraum V eine Basis {vj : j ∈ J} aus-zeichnet, dann liefert das einen Isomorphismus
ϕ : V → KJ (Spaltenraum)
Die Eintrage von ϕ(v) sind die Koeffizienten xj in der eindeutigen Darstellung v =∑vj ·
xj . Man kann auch sagen : xj ist der Wert ℓ(j)(v) der j-ten Linearform in der dualen Basis.ϕ nennt man eine Koordinatisierung von V .
Hinweise
1. Die Begriffe Homomorphismus und Isomorphismus sind fur unendlichdimensionaleVektorraume komplizierter. (Wir denken an R- und C-Vektorraume.) In der Theorieder normierten Vektorraume interessiert man sich zunachst einmal fur stetige lineareAbbildungen. (Die Theorie der unbeschrankten linearen Operatoren ist kompliziert.)
2. Fur ein stetiges ϕ ist kerϕ ein abgeschlossener Teilraum, das Bild im ϕ ist abernicht notwendigerweise abgeschlossen.
3. Wenn die stetige lineare Abbildung ϕ : (V, ‖ · ‖)→ (U, ‖ · ‖) injektiv und surjektivist, dann besitzt sie zwar eine Umkehrabbildung; diese lineare Abbildung ϕ−1 istaber nicht notwendigerweise stetig. In solchen Situationen mochte man das WortIsomorphismus nicht gebrauchen. Man definiert wie unten angegeben.
, Seite 131
Beispiel
Sei Vo der C-Vektorraum der trigonometrischen Polynome ohne konstanten Term
f(t) =∑
n 6=0
cneint (endliche Summe)
Die Stammfunktionsbildung ist ein stetiger Endomorphismus
Vo ∋ f 7→ ϕ(f) =∑
n 6=0
cn ·1
ineint ∈ Vo .
ϕ(·) ist injektiv und surjektiv.Die Umkehrabbildung (das ist die
”Ableitung“) ist aber nicht stetig auf V (wenn wir die
ubliche 2-Norm auf V zugrundelegen).
Definition
a) Eine stetige lineare Abildung
ϕ : (V, ‖ · ‖)→ (U, ‖ · ‖)
heißt ein Isomorphismus, wenn es eine stetige lineare Abbildung ψ gibt, sodass
ϕ ◦ ψ(·) = idU und ψ ◦ ϕ(·) = idV .
b) Man sagt von topologischen Vektorraumen, dass sie isomorph sind, wenn es einenIsomorphismus gibt.
Beispiel
V sei der Raum der trigonometrischen Polynome mit der Norm
‖f‖ =
(1
2π
∫ ∣∣f(t)∣∣2dt
)1/2
.
U sei der Raum der finiten Folgen
c = (. . . , c−1, c0, c1, c2, . . .)
mit der Norm
‖c‖ =(∑
|cn|2)1/2 .
Diese topologischen Vektorraume sind isomorph. Hier gibt es sogar isometrische Abbil-dungen
ϕ : (V, ‖ · ‖)→ (U, ‖ · ‖)‖ϕ(f)‖ = ‖f‖ fur alle f ∈ V .
Die ublichste Isometrie ist uns bereits aus dem ersten Semester bekannt. Zu f ∈ V gewinntman die Eintrage ck als die Fourierkoeffizienten;
ck =1
2π
∫e−iktf(t)dt .
Die Umkehrabbildung ψ(·) ist die Uberlagerung der reinen Sinusschwingungen
f = ψ(c) =∑
ckeikt .
(Summenbildung im Sinne der L2-Konvergenz.)
, Seite 133
56. Vorlesung : Tableaus, Basisaustausch, lineare Gleichungssy-
steme
Das praktische Losen von linearen Gleichungssystemen ist eine hochentwickelte Kunst derNumerik. Aus der Sicht der Numerik gibt es kein Verfahren, das sich fur alle Zwecke eig-net. Wenn wir im Folgenden ein Losungsverfahren diskutieren, dann steht der theoretischeGesichtspunkt im Vordergrund. Wir behandeln nicht das sog. Gauß’sche Verfahren; wirbevorzugen vielmehr die Methode der Tableaus. Sie ist ubersichtlicher und wird spaterbei der linearen Optimierung benotigt.Wir beginnen mit dem Basisaustauschsatz. Aus einem n-Tupel von Vektoren soll eineBasis des aufgespannten Vektorraum ausgewahlt werden.{ui ∈ I} sei eine Basis eine m-dimensionalen Vektorraums U . Es wird sich zeigen, dassmanche Aufzahlungen u1, . . . , um ein ubersichtlicheres Bild ergeben als andere. Wir be-halten uns daher vor, im Verlauf der Rechnungen Umnummerierungen vorzunehmen.{wj : j ∈ J} sei ein n-Tupel von Vektoren, gegeben in der Basisdarstellung mit den ui.
wj =∑
i
ui · aij fur j = 1, . . . , n .
Auch hier behalten wir uns eine Umnummerierung gegenuber der anfanglichen Aufzahlungvor. Zunachst nehmen wir nur an: a1
1 = : α 6= 0.Wir konnen die linearen Beziehungen zwischen den Vektoren ui und wj auf verschiedeneWeisen ausdrucken.
(T0) : w1 = u1 · α +m∑2
ui · ai1 fur j = 1
wj = u1 · a1j +
m∑2
ui · aij fur j = 2, . . . , n .
Ubersichtlicher ist das Tableau
u1 α a12 . . . . . . a1
n
u2 a21 a2
2 . . . . . . a2n
......
......
um am1 am2 . . . . . . amn
= w1 = w2 = wn
Wir losen nach u1 auf und erhalten
(T1) : u1 = w1 · α−1 −m∑2
ui · ai1 · α−1 fur j = 1
uj = w1 · α−1 · a1j +
m∑2
ui ·(aij − ai1 · α−1 · a1
j
)fur j = 2, . . . , n .
Ubersichtlicher ist das Tableau
w1 α−1 α−1a12 . . . α−1a1
n
. . . . . . . . . . . . . . . . . . . . . . . .
u2 −a21 · α−1 ...
......
...... aij − ai1α−1a1
j
um −am1 · α−1 ...
= u1 = w2 = wn
Die Transformation (T0)→ (T1) nennt man die Pivottransformation zur Position (1, 1).
Bemerke : Wenn man auf (T1) die Pivottransformation zur Position (1, 1) anwendet,erhalt man (T0).
Vollstandiger Austausch
Wenn (T1) in der Position (2, 2) einen Eintrag 6= 0 hat, dann fuhren wir die Pivottrans-formation zu dieser Position durch; wir
”tauschen“ u2 gegen w2 in der Randbeschriftung.
Wenn die ui und die wj in geeigneter Reihenfolge aufgelistet sind, dann konnen wir solange mit dem Austausch fortfahren, bis die Restmatrix rechts unten die Nullmatrix ist.Wenn die ursprungliche Matrix A den Rang = r hat, dann haben wir nach r Schritten
(Tr) w1
B|| B
|‖
wr. . . . . . . . . . . . . . . . . . . . . . . . . . .ur+1
B‖| 0
um= u1 = ur = wr+1 = wn
B|| ist eine r×r-Matrix; B
|‖ (gelesen: B oben Strich, unten Doppelstrich) ist eine r×(n−r)-
Matrix; B‖| hat das Format (m− r)× r.
Wir notieren w| = (w1, . . . , wr) , w‖ = (wr+1, . . . , wm),u| = (u1, . . . , ur) , u‖ = (ur+1, . . . , um) und haben
a) w‖ = w| · B|‖ + 0
b) u| = w| · B|| + u‖ · B‖
I .
Das Tableau (Tr) sagt uns insbesondere
, Seite 135
a) {w1, . . . , wr, ur+1, . . . , um} ist Basis von U .
b) {w1, . . . , wr} ist Basis von span{wj : j ∈ J}.
Wir wollen jetzt studieren, wie die Matrix B aus der Matrix A im Tableau (To) entsteht.Dazu denken wir uns auch A unterteilt.
(To) u1
A|| A
|‖
ur. . . . . . . . . . . . . . . . . . . . . . . . . . .u‖
A‖| A
‖‖
= w1 = wr = w‖
Satz : (Matrizen fur den Austausch)
a) Die r × r-Matrizen A|| und B
|| sind zueinander invers
b) B‖| = −A‖
| · (A||)−1 ; A
‖| = −B‖
| · (B||)
−1
c) B|‖ = (A
||)−1 · A‖
| ; A|‖ = (B
||)
−1 · B|‖
d) 0 = B‖‖ = A
‖‖ − A
‖| · (A
||)−1 · A|
‖.
Die Formeln sind dieselben wie die beim Ubergang von (To) nach (T1); man muss hier nurauf die Reihenfolge der Faktoren in den Matrizenprodukten aufpassen.
Beweis
Wir schreiben die Beziehungen zwischen den Tupeln u|, u‖ und w|, w‖ in Matrizenschreib-
weise. Wir mussen nicht annehmen, dass B‖‖ die Nullmatrix ist, dass wir also einen
vollstandigen Austausch vorliegen haben. In jedem Fall gilt
(u|, u‖)
A|| A
|‖
A‖| A‖
= (w|, w‖)
(w|, u‖)
B|| B
|‖
B‖| B‖
= (u|, w‖)
Aus der ersten Gleichung erhalten wir
(w|, u‖) = (u|, u‖) = (u|, u‖)
A|| 0
A‖| I
aus der zweiten
(u|, w‖) = (u|, u‖)
A|| 0
A‖I I
B|| B
|‖
B‖| B
‖‖
= (u|, u‖)
A||B
|| A
||B
|‖
A‖|B
|| +B
‖| A
‖|B
|‖ +B
‖‖
Jeder Vektor laßt sich auf genau eine Weise als Linearkombination der ui darstellen; dahergilt
A
||B
|| A|B
|‖
A‖|B
|| +B
‖| A
‖|B
|‖ +B
‖‖
=
I A|‖
0 A‖‖
Das ergibt
a) A||B
|| = I b) A
‖|B
|| +B
‖| = 0
c) A||B
|‖ = A
|‖ c) B
‖‖ = A
‖‖ −A
‖| · B
|‖ q.e.d.
Immer, wenn man ein Tupel von Basisvektoren ui durch ein Tupel der wj austauscht,gelten die Matrizengleichungen a) b) c) d). Die skalare Form haben wir beim Ubergangvon (To) zu (T1) bereits kennengelernt. Im allgemeinen Fall gelten dieselben Formeln; manmuss nur etwas besser aufpassen, weil das Matrizenprodukt nicht kommutativ ist.
Gleichungssysteme durch Zeilentableaus
Ein inhomogenes Gleichungssystem wird traditionellerweise folgendermaßen geschrieben:
a11 · x1 + a1
2 · x2 + . . . +a1n · xn = b1
. . . . . .
am1 · x1 + am2 · x2 + . . . +amn · xn = bm .
Die n× n-Matrix A und die m-Spalte b ist vorgegeben. Gesucht ist eine moglichst uber-sichtliche Beschreibung der Losungsmenge
{x : Ax = b} .
, Seite 137
Erwunscht ist auch (bei festem A) ein Uberblick uber die Menge der b, fur welche eineLosung existiert.
Wir wollen die Problemstellung in die Sprache der Vektorraume ubersetzen:V sei ein n-dimensionaler K-Vektorraum mit einer ausgezeichneten Basis {ej : j ∈ J}.ℓ(1)(·), . . . , ℓ(m)(·) seien Linearformen.
ℓ(i) (∑
ej · xj) =∑aij · xj fur i = 1, . . . , m.
Gesucht ist eine ubersichtliche Beschreibung der Losungsmengen{x : ℓ(i)(x) = −yi
}und
eine Charakterisierung der m-Tupel yi fur welche eine Losung existiert.Wir beschreiben die Gegebenheiten durch ein Zeilentableau
x1 . . . xn
(To)a1
1 . . . a1n = −y1
......
...am1 . . . amn = −ym
(Die Ersetzung bi ↔ −yi wird sich als bequem erweisen.)
Wir wollen das Tableau umformen. Zunachst nehmen wir an : a11 = α 6= 0. Dann konnen
wir namlich die erste Zeile nach x1
”auflosen“.
α · x1 +n∑
2
a1jx
j = −y1 ⇔ 1
αy1 +
∑ 1
αa1j · xj = −x1 .
Die weiteren −yi stellen wir mit {y1, x2, . . . , xn} dar.
−ai1 ·1
αy1 +
m∑
2
(aij − ai1 ·
1
α· a1
j
)xj = −yi fur i = 2, . . . , m .
Dies ist das Zeilentableau
y1 x2 . . . . . . . . . xn
1α
1αa1
21αa1n = −x1
(T1) −a21 · 1
α. . . . . . . . . . . . . . . . . . . . . = −y2
...
... aij − ai1 ·1
α· a1
j
−am1 · 1α
... = −ym
Das Koeffizientenschema ist uns schon von der Pivottransformation des Spaltentableausbekannt. Wie dort wollen wir die Zeilen und Spalten schrittweise so umnummerieren, dasswir xi gegen yi austauschen konnen, i = 1, . . . , r.
Das vollstandig ausgetauschte Zeilentableau lautet :
y1 yr xr+1 xn
(To) = −x1
B||
... B|‖
. . . . . . . . . . . . . . . . . . . . . . . .= −xr= −yr+1
B‖|
... 0 = −ym
In Matrizenform
a) B|| · y| +B
|‖ · x‖ = −x|
b) B‖| · y| = −y‖ .
Interpretation
Die Gleichung b) liefert eine notwendige und hinreichende Bedingung fur die Losbarkeitdes Gleichungssystems.Alle Bedingungen an die Losungsmenge {x : Ax = −y} stecken in den ersten r Gleichun-gen.xr+1, . . . , xn konnen beliebig vorgegeben werden; wenn x1, . . . , xr dazu durch die Glei-chung a) bestimmt werden, dann haben wir eine Losung. Fur jedes zulassige y ist also dieLosungsmenge eine (n− r)-dimensionale lineare Mannigfaltigkeit.
Hinweis (auf den Satz von der implizit gegebenen Funktion)
Zu den Zeilentableaus gibt es ein nichtlineares Analogon:G(1)(·), . . . , G(m)(·) seien glatte Funktionen. Wir interessieren uns fur die Menge der Losun-gen des Gleichungssystems
G(1)(x1, . . . , xn) = −y1
. . . . . .
G(m)(x1, . . . , xn) = −ym
in einer Umgebung von einer speziellen Losung (x, y).Man kann zeigen: Wenn die Jacobi-Matrix vollen Rang m hat, wenn also die Gradientender G(i)(·) linear unabhangig sind, dann ist die Losungsmenge
M ={x : G(x) = −y
}∩ U
fur eine genugend kleine Umgebung U eine (n−m)-dimensionale Mannigfaltigkeit. Diesekann man (nach Umnummerierung der x(j) durch x(r+1), . . . , x(n) parametrisieren.
(x(r+1), . . . , x(n)
)
, Seite 139
sind als lokales Koordinatensystem auf der Losungsmenge zu betrachten. Alle glattenFunktionen f auf M konnen mit diesen x(j) ausgedruckt werden.
f(P ) = F(x(r+1)(P ), . . . , x(n)(P )
)fur P ∈M .
Insbesondere sind die ubrigen x(i) auf der LosungsmengeM als Funktionen von x(r+1), . . . , x(n)
auszudrucken.
x(i)(P ) = H(i)(x(r+1)(P ), . . . , x(n)(P )
)fur i = 1, . . . , r
mit gewissen glatten Funktionen H(i)(·).Die Jacobi-Matrix (
∂H(i)
∂x(j)
)i=1,...,m
j=r+1,...,n
ergibt sich durch die Kettenregel.Die Kettenregel liefert
∂
∂x‖G(H(x‖), x
)= 0⇔ G| ·H ′(x‖) +G‖(x
‖) = 0
−H |(x‖) = (G|)−1 ·G‖(x
‖) .
Die Jacobi-Matrix H ′(·) entspricht der m× (m− r)-Matrix B|‖ in Formel b):
Ax = 0⇔ (A′|, A
′‖)
(x|
x‖
)= 0⇔ A′
|x| + A′
‖x‖ = 0
−x| = (A′|)−1 ·A′
‖x‖ .
57. Vorlesung : Duale Tableaus, Bilinearformen, Tensoren
(Dieser Abschnitt kann zunachst ubersprungen werden)
Es ist naturlich kein Zufall, dass die Koeffizientenmatrizen in den Zeilen- und Spaltenta-bleaus auf dieselbe Weise transformiert werden. Zeilentableau und Spaltentableau konnenals zueinander dual interpretiert werden. Dabei gibt es aber mehrere Moglichkeiten. Wirdiskutieren zuerst den Basiswechsel (fur quadratische Tableaus vom vollen Rang) unddann die Tableaus zu einer linearen Abbildung. Schließlich interpretieren wir lineare Ab-bildungen als Bilinearformen (und umgekehrt).
Basiswechsel und Koordinatenwechsel
V sei ein n-dimensionaler K-Vektorraum, {vj : j ∈ J} sei eine Basis,{ℓ(j) : j ∈ J
}sei
die duale Basis.Jedes v ∈ V besitzt eine eindeutige Darstellung
v =∑
vj · xj , wobei xj = ℓ(j)(v) .
Wir bezeichnen die Funktionen ℓ(j)(·) auf dem affinen Raum V auch mit x(j)(·) und wirnennen sie die Koordinatenfunktionen (zur gegebenen Basis).{ui : i ∈ I} sei eine weitere Basis,
{k(i) : i ∈ I
}sei die duale Basis; statt k(i) schreiben
wir auch y(i)(·).
Satz
Wenn die I × J-Matrix A den Basiswechsel beschreibt
(u1, . . . , un)A = (v1, . . . , vn)∑
i
uiaij = vj fur j ∈ J ,
dann beschreibt die J × I-Matrix B = A−1 den Koordinatenwechsel
A−1
y(1)
...
y(n)
=
x(1)
...
x(n)
∑i
bji · y(i)(·) = x(j)(·) .
, Seite 141
Beweis
Sei B die zu A inverse Matrix. Die Darstellung eines Vektors ist in jedem Koordinaten-system eindeutig bestimmt.
∑vj · xj = v =
∑ui · yi
v =∑
j
(∑
i
uiaij
)xj =
∑
i
ui
(∑
j
aij · xj)
=∑
ui · yi
yi =∑
j
aij · xj fur alle i⇔ xj =∑
bjiyi fur alle j .
Bemerke die Tableaus
x(1) . . . x(n) y(1) . . . (y(n))
u1 a11 a1
n = y(1) v1 b11 b1n = −x(1)
......
......
un an1 ann = y(n) vn bn1 bnn = −x(n)
= v1 . . . = vn = u1 . . . = un
Sie gehen durch vollstandigen Austausch auseinander hervor.
Matrizen und Tableaus zur Darstellung linearer Abbildungen
ϕ : V → U sei eine lineare Abbildung.{vj : j ∈ J} sei eine Basis von V ;
{x(j) : j ∈ J
}sei die duale Basis.
{ui : i ∈ I} sei eine Basis von U ;{y(i) : i ∈ I
}sei die duale Basis.
Die Bilder der Basisvektoren wj = ϕ(vj) besitzen eine eindeutige Darstellung als Linear-kombination der ui.
ϕ(vj) =∑
i
ui · aij fur j ∈ J .
Die duale Abbildungϕ⋆ : V ⋆ ← U⋆
ordnet jedem y(i) eine Linearkombination der x(j) zu
ϕ⋆(y(i))
=∑i
aij · x(j) fur i ∈ I
aij = 〈ϕ⋆(y(i)), vj〉 = 〈y(i), ϕ (vj)〉 .
In Matrizenschreibweise
(ϕ (v1) , . . . , ϕ (vn)
)= (u1, . . . , un)A(
ϕ⋆(y(1)), . . . , ϕ⋆
(y(n)))T
= A ·(x(1), . . . , x(n)
)T.
In Tableau-Schreibweise
x(1) x(n)
u1 a11 a1
n = ϕ⋆(y(1))
...
um am1 amn = ϕ⋆(y(m)
)
= ϕ(v1) = ϕ(vn)
(ϕ(v1), . . . , ϕ(vn))
x(1)
...
x(n)
= (u1, . . . , um)A
x(1)
...
x(n)
= (u1, . . . , um)
ϕ⋆(y(1))
...
ϕ⋆(y(m)
)
.
Lineare Abbildungen als Bilinearformen
Seien U und V K-Vektorraume, U⋆ und V ⋆ die Dualraume.Eine Bilinearform b(·, ·) auf U⋆ × V kann man als lineare Abbildung interpretieren
ϕ : V → U ! b(·, ·) : U⋆ × V → K .
b(·, v) ist namlich eine Linearform auf U⋆, d.h. ein Element von U (U⋆⋆ = U). Fur k ∈ U⋆
ist b(k, ·) eine Linearform auf V , und zwar = ϕ⋆(k)
b(k, v) = 〈k, ϕ(v)〉 = 〈ϕ⋆(k), v〉 .
Sei {ui : i ∈ I} eine Basis von U ;{k(i) : i ∈ I
}sei die duale Basis.
Sei {vj : j ∈ J} eine Basis von V ;{ℓ(j) : j ∈ J
}sei die duale Basis.
Zu u ∈ U, ℓ(·) ∈ V ⋆ gewinnt man eine Bilinearform
(u⊗ ℓ)(·, ·) auf U⋆ × V vermoge der Festsetzung
(u⊗ ℓ)(k, v) = 〈k, u〉 · 〈ℓ, v〉 fur k ∈ U⋆, v ∈ V .
Speziell erhalten wir fur jedes (i, j) ∈ I × J eine Bilinearform ui ⊗ ℓ(j).
Satz : Diese speziellen Bilinearformen bilden eine Basis des K-Vektorraums aller Bili-nearformen auf U⋆ × V .
Beweis : b(·, ·) =∑i,j
aij · ui ⊗ ℓ(j)(·, ·) entspricht der linearen Abbildung
ϕ : V → U mit
ϕ(vj) =∑
i
ui · aij fur j ∈ J .
Das Koeffizientenschema(aij)i,j
ist also die I × J-Matrix, welche ϕ(·) in den gewahlten
Koordinatensystemen ausdruckt.
, Seite 143
Bemerke
1. Die Bilinearform ui ⊗ ℓ(j) entspricht der I × J-Matrix, die in der Position (i, j) denEintrag 1 hat und sonst lauter Nullen.
2. Die Bilinearformen u⊗ ℓ(·, ·) auf U⋆× V entsprechen den linearen Abbildungenvom Rang 1. In der Koeffizientenmatrix sind alle Spalten zueinander proportional(und ebenso naturlich alle Zeilen).
aij = αi · βj, wenn u =∑
ui · αi , ℓ =∑
βj · ℓ(j) .
Satz : Wenn eine Abbildung ϕ : V → U den Rang r hat, dann kann die dazugehorigeBilinearform b(·, ·) als Linearkombination von r Tensorprodukten dargestellt werden.
Beweis :
1. Sei {u1, . . . , um} eine Basis von U , sodass
{u1, . . . , ur} eine Basis von im ϕ ist.
Wahle v1, . . . , vr so, dass ϕ(vj) = uj fur j ≤ r, und setze dieses r-Tupel zu einerBasis {vj : j ∈ J} fort.
2.{k(i) : i ∈ I
}sei die duale Basis von {ui : i ∈ I}.{
ℓ(j) : j ∈ J}
sei die duale Basis von {vj : j ∈ J}.Es gilt 〈k(i), ϕ(vj)〉 = 1 falls i = j ≤ rund andernfalls = 0.
3. Betrachte die Bilinearform
b(·, ·) = u1 ⊗ ℓ(1) + . . .+ ur ⊗ ℓ(r)
in den Paaren{k(i), vj
}. Fur alle n gilt
un ⊗ ℓ(n){k(i), vj
}= 〈k(i), un〉 · 〈ℓ(n), vj〉 .
Dies ist nur dann 6= 0 (und dann = 1), wenn i = j = n. Somit entspricht b(·, ·) dergegebenen Abbildung ϕ : V → U .
Satz :
V1 und V2 seien K-Vektorraume.
b(·, ·) : V1 × V2 → K
sei eine Bilinearform. Dann gilt
dim
{b(·, v2) : v2 ∈ V2
}= dim
{b(v1, ·) : v1 ∈ V1
}.
Beweis :
1. Wir konnen b(·, ·) mit einer linearen Abbildung
ϕ : V1 → V ⋆2
identifizierenv1 7−→ ϕ(v1) ∈ V ⋆
2 〈ϕ(v1), ·〉 = b(v1, ·) .Fur die duale Abbildung
ϕ⋆ : V2 → V ⋆1
haben wir
〈ϕ⋆(v2), ·〉 = b(·, v2) ; denn
〈ϕ(v1), v2〉 = b(v1, v2) = 〈ϕ⋆(v2), v1〉 fur alle v1 ∈ V1, v2 ∈ V2 .
2. {b(·, v2) : v2 ∈ V2} ist ein Teilvektorraum von V ⋆1 , und zwar = im ϕ⋆. Ebenso
{b(v1, ·) : v1 ∈ V
}= im ϕ ⊆ V ⋆
2 .
Da ϕ und ϕ⋆ denselben Rang haben, haben die beiden Vektorraume dieselbe Di-mension.
Definition
Der Rang der Bilinearform b(·, ·) ist die Dimension von{b(v1, ·) : v1 ∈ V1
}.
Tensorprodukt
U und V seien K-Vektorraume, dim U = m, dim V = n. U⋆ bzw. V ⋆ seien die Dualraume.Wir definieren die zueinander dualen Vektorraume U⊗V und U⋆⊗V ⋆ (von der Dimensionm · n) :
1. U⋆ ⊗ V ⋆ ist der Vektorraum aller Bilinearformen auf U × V . Er besteht aus denLinearkombinationen von Bilinearformen der Form k ⊗ ℓ mit k ∈ U⋆, ℓ ∈ V ⋆
(k ⊗ ℓ)(u, v) = 〈k, u〉 · 〈ℓ, v〉 fur alle u, v ∈ U × V .
2. U ⊗ V besteht aus den Bilinearformen auf U⋆ × V ⋆
∑aα · uα ⊗ vα mit uα ∈ U, vα ∈ V .
3. Die naturliche Paarung ist
⟨∑bβ · kβ ⊗ ℓβ ,
∑aα · uα ⊗ vα
⟩=∑
α,β
bβ · aα · 〈kβ, uα〉 · 〈ℓβ · vα〉 .
, Seite 145
Bemerke
Sei {ui : i ∈ I} eine Basis von U , {vj : j ∈ J} eine Basis von V .Sei {k(i) : i ∈ I} bzw. {ℓ(j) : j ∈ J} die duale Basis.Dann bilden die ui⊗vj eine Basis von U⊗V ; die duale Basis (fur den Vektorraum U⋆⊗V ⋆)sind die k(i) ⊗ ℓ(j).
〈k(m) ⊗ ℓ(n) , ui ⊗ vj〉 =
{1 falls m = i, n = j
0 sonst
U ⊗ V (und naturlich auch der Dualraum U⋆ ⊗ V ⋆) ist ein Vektorraum der DimensiondimU · dimV .
58. Vorlesung : Lineare Optimierung, perfekter Austausch
Die Kraft der Tableaus zeigt sich eindrucklich in der linearen Optimierung. Dort will mankeinen vollstandigen Austausch, sondern einen informativen partiellen Austausch, einen
”perfekten“ Austausch.
Maximierungsproblem
Ein Produzent kann die Produkte (j) herstellen (j = 1, . . . , n). Er muss jedoch auf dieBeschranktheit der Ressourcen (i) achten (i = 1, . . . , m). Er sucht nach einem
”Produk-
tionsplan“, welcher den Erlos maximiert.
Minimierungsproblem
Ein Einkaufer kann Grundstoffe (i) einkaufen (i = 1, . . . , m). Er muss aber bei der Zu-sammenstellung seines
”Einkaufsplans“ darauf achten, dass die Wirkstoffe (j) ausreichend
vertreten sind. (j = 1, . . . , n). Er sucht nach einem”Einkaufsplan“, welcher minimalen
Preis hat.
Konvention
Die Daten werden in beiden Fallen in einem Tableau versammelt. Beim Maximierungs-problem wird das Koeffizientenschema als Zeilentableau gelesen, beim Minimierungspro-blem wird es als Spaltentableau gelesen. Wir betrachten die beiden Probleme zur gleichen(m+ 1)× (n+ 1)-Matrix simultan.
x1 x2 xn −1
ξ1... b1 = −y1
...(aij) ...
...
ξm... bm = −ym
. . . . . . . . . . . . . . . . . . . . . . . . . .
−1 c1 c2 . . . . . . . . . cn... d = M
= n1 = n2 = nn = m
Das Zeilentableau wird gelesen:Ein n-Tupel x ≥ 0 ist zulassig (
”feasible“), wenn
Ax ≤ b , d.h. wenn y := −(Ax− b) ≥ 0 .
Der Erlos beim Produktionsplan (x, y) ist cx−d = M . Dieser Erlos M ist zu maximieren.
Sprechweise (”Schlupfvariable“)
Wenn (x, y) ≥ 0 ein zulassiger Produktionsplan ist, dann heißt der Eintrag yi der i-te
, Seite 147
Schlupf (”slack“). yi gibt an, wieviel von der i-ten Ressource unausgenutzt bleibt. Es
wird sich zeigen, dass zu einem optimalen Produktionsplan ein s-Tupel von Ressourcengehort, die voll ausgeschopft werden und ein (n − s)-Tupel von Produkten, die nichtproduziert werden.
Das Spaltentableau wird gelesen:Ein m-Tupel ξ ≥ 0 ist zulassig (
”feasible“), wenn
ξA ≥ c , d.h. wenn η := ξA− c ≥ 0 .
Der Preis des Einkaufsplans (ξ, η) ist ξb− d = m. Dieser Preis ist zu minimieren.
Sprechweise
Wenn (ξ, η) ein zulassiger Einkaufsplan ist, dann heißt der Eintrag ηj der j-te Schlupf.ηj gibt offenbar an, wie weit der Einkaufsplan beim Wirkstoff uber das Soll hinaus geht.Es wird sich zeigen, dass zu jedem optimalen Einkaufsplan ein s-Tupel von Wirkstoffengehort, bei welchen das Soll nicht uberschritten wird und ein (m− s)-Tupel von Grund-stoffen, die nicht eingekauft werden.
Ein trivialer Fall
Nehmen wir an: bi ≥ 0 fur alle i, cj ≤ 0 fur alle j. In diesem Fall ist x = 0 ein optimalerProduktionsplan und ξ = 0 ein optimaler Einkaufsplan.
Beweis :
Die”Nullplane“ sind jedenfalls zulassig. Nehmen wir an, der Produzent weicht ein wenig
vom Nullplan ab; der Erlos sinkt, weil alle cj ≤ 0. Nehmen wir an, der Einkaufer weichtvom Nullplan ab (ohne die Zulassigkeit einzubußen); der Preis steigt, weil alle bi ≥ 0.
Losbarkeit
Wenn die Koeffizeintenmatrix irgendwie vorgegeben wird, dann ist uberhaupt nicht klar,ob zulassige Produktionsplane (bzw. zulassige Einkaufsplane) existieren. Die Mengen
K := {x : x ≥ 0 , Ax ≤ b} = {x : (x, y) ≥ 0} ⊆ Rn+ , bzw.
L := {ξ : ξ ≥ 0 , ξA ≥ c} = {ξ : (ξ, η) ≥ 0} ⊆ Rm+
konnen leer sein.Wenn K 6= ∅, dann kann die Zielfunktion cx− d auf K nach oben unbeschrankt sein.Die Funktionen
M(c, d) := sup{cx− d : x ∈ K} und
m(b, d) := inf{ξb− d : ξ ∈ L}konnen also die Werte ±∞ annehmen.(Das Supremum der leeren Zahlenmenge ist −∞, das Infimum der leeren Zahlenmenge
ist +∞ (Konvention))
Satz
(x, y,M) mit (x, y) ≥ 0 lose das Zeilentableau,(ξ, η,m) mit (ξ, η) ≥ 0 lose das Spaltentableau.Es gilt dann
M ≤M(c, d) ≤ m(b, d) ≤ m .
Beweis
1. Sei (x, y,M) eine Losung des Zeilentableaus, die nicht zulassig sein muss. Und sei(ξ, η,M) eine Losung des Spaltentableaus, die nicht zulassig sein muss. Dann gilt
∑ξi · yi +
∑ηj · xj = m−M .
Es gilt namlich∑
ηjxj =
∑(∑ξia
ij − cj
)xj = ξAx− cx
−∑
ξiyi =
∑ξi
(∑aijx
j − bi)
= ξAx− ξb .
Die Differenz ergibt
ηx+ ξy = −cx+ ξb = −(M + d)− (m+ d) = m−M .
2. Wenn (x, y,M) und (ξ, η,m) zulassige Losungen sind, dann gilt
m−M = ξy + ηx ≥ 0 q.e.d.
Corollar
Seien (x, y,M) und (ξ, η,m) zulassige Lasungen, wie im Satz. Wenn m = M , dann giltx ist ein optimaler Produktionsplan undξ ist ein optimaler Einkaufsplan.
Bemerke
Wenn M(c, d) = +∞, dann L = ∅,wenn m(c, d) = −∞, dann K = ∅.
Zahlenbeispiel
x1 x2 x3 −1
ξ1 4 2 2... 12 = −y1
ξ2 1 0 1... 2 = −y2
ξ3 0 1 3... 4 = −y3
. . . . . . . . . . . . . .... . . .
−1 3 2 2, 5... 0 = M
= η1 = η2 = η3 = m
, Seite 149
Bemerke :
1. Fur den Produzenten ist der Nullplan zulassig. Der Erlos ist 0; er hofft auf hoherenErlos.
2. Fur den Einkaufer ist klar, dass er die Forderungen erfullen kann, wenn er genugendgroße Mengen ξi von den Grundstoffen einkauft. Er muss aber nachdenken, wenn ereinen kleinen Preis erreichen will.Jedenfalls haben wir m(b, d) ≥ 0 nach dem Satz.
Wir wollen das Tableau (T0) durch Pivottransformationen so umformen, dass wir Genau-eres uber M(c, d) und m(c, d) ablesen konnen.Die Pivottransformation zur Position (3, 2) liefert
x1 y3 x3 −1
ξ1 4 −2 −4... 4 = −y1
(T1) ξ2 1 0 1... 2 = −y2
η2 0 1 3... 4 = −x2
. . . . . . . . . . . . . . . .... . . .
−1 3 −2 −3, 5... −8 = M
= η1 = ξ3 = η3 = m
3. Fur den Produzenten ist x1 = 0, y3 = 0, x3 = 0 zulassig.
(x ; y) = (0, 4, 0 ; 4, 2, 0) .
Der Erlos ist M = 8.
4. Der Einkaufer hat die untere Abschatzung 8 fur seinen optimalen Einkaufsplan. Esist aber fraglich, ob er so billig wird einkaufen konnen.
Die Pivottransformation zur Position (1, 1) liefert
y1 y3 x3 −1
η1... 1 = −x1
(T2) ξ2... 1 = −y2
η2... 4 = −x2
. . . . . . . . . . . . . . . . . .... . . .
−1 −34
−12
−12
... −11 = M
= ξ1 = ξ3 = η3 = m
5. Man erhalt einen zulassigen Einkaufsplan, wenn man η1 = 0, ξ2 = 0, η2 = 0 wahlt.Dies bedeutet
(ξ ; η) =
(3
4, 0,
1
2; 0, 0,
1
2
), m = 11 .
6. Das Tableau hat die Form, die wir oben den trivialen Fall genannt haben. DerEinkaufsplan in 5) ist optimal. Der optimale Produktionsplan ist durch
y1 = 0 , y3 = 0 , x3 = 0 gegeben.
(x ; y) = (1, 4, 0 ; 0, 1, 0) , M = 11 .
Die beiden linearen Optimierungsprobleme haben simultan ihre Losung gefunden. Durchgeschickt gewahlte Pivottransformation haben wir das unubersichtliche Problem auf dentrivialen Fall zuruckgefuhrt. Dies nennen wir einen perfekten Austausch.
Frage : Unter welchen Umstanden sollte es gelingen, das Tableau so umzuformen, dassdie Eintrage rechts ≥ 0 und die Eintrage unten ≤ 0 sind?
Hinweis : Bei einem Tableau (”in allgemeiner Lage“) kann man auf
(nk
)·(mk
)Weisen
ein k-Tupel von Randvariablen gegen ein k-Tupel von Randvariablen austauschen. k =1, 2, . . ., min{m,n}. Wer nur einfach probiert, der hat viel zu tun. Der beruhmte Simplex-Algorithmus versucht mit passenden Pivot-Wahlverfahren moglichst schnell zum perfektumgeformten Tableau zu gelangen. Das klappt manchmal sehr gut; es gibt Faustregelnfur viele Spezialfalle. Es hat sich aber gezeigt, dass der Rechenaufwand in vielen Fallenhoch ist. Die Fachleute suchen daher heute lieber nach suboptimalen zulassigen Planen,die man schnell errechnen kann. Sie verzichten auf den optimalen Plan, der nur mit hohemRechenaufwand gefunden werden kann.Ubrigens : Die Komplexitatstheoretiker konnen beweisen, dass das allgemein gestellteProblem der linearen Optimierung in einem technisch prazisen Sinn schwierig ist. Eshat also keinen Sinn, nach allgemeingultigen schlauen Pivot-Wahlverfahren Ausschau zuhalten.
, Seite 151
59. Vorlesung : Geometrisches zur linearen Optimierung
Definition (Extremalpunkte)
Ein Punkt P einer konvexen Menge K heißt ein Extremalpunkt von K, wenn man ihnnur auf triviale Weise als konvexe Kombination weiterer Punkte von K darstellen kann.
∀P,Q ∈ K ∀λ ∈ (0, 1) (1− λ)P + λQ = P ⇒ P = Q = P .
Bemerke : Nicht alle abgeschlossenen konvexen Mengen in einem n-dimensionalen af-finen Raum besitzen Extremalpunkte. Man denke an Halbraume (fur n = 2) oder auchan Zylinder (fur n ≥ 3). Man beweist aber leicht das
Lemma
Sei K eine nichtleere abgeschlossene Teilmenge eines n-dimensionalen affinen Raums.Wenn K keine Geraden enthalt, dann besitzt K mindestens einen Extremalpunkt. Jedenach oben beschrankte konvexe Funktion k(·) nimmt ihr Maximum in einem Extremal-punkt an.
Bemerkung:
Jede kompakte konvexe Teilmenge eines endlichdimensionalen affinen Raums ist die kon-vexe Hulle ihrer Extremalpunkte (ohne Beweis!)
Sei V der Vektorraum aller n-Spalten x. In unserem Maximierungsproblem sind diezulassigen
”Produktionsplane“ die Punkte x im Durchschnitt K von m+ n Halbraumen.
{x : x(j) ≥ 0 fur j=1, . . . , n ; y(i) := −
∑aijx
(j) + b(i) ≥ 0 fur i=1, . . . , m}
Maximierung
Nehmen wir an, dass K nicht leer ist und cx − d auf K nach oben beschrankt. DasMaximum M(c, d) wird mindestens in einem Extremalpunkt x angenommen. Jeder Ex-tremalpunkt von K ist der Schnittpunkt von mindestens n unter den Hyperebenen.
{x : x(j) = 0
}und
{x : y(i) = 0
}
Durch Umnummerieren der Zeilen und Spalten unseres Tableaus konnen wir erreichen,dass die fruhen y(i) und die spaten x(j) in diesem Extremalpunkt verschwinden; kurzgeschrieben
y| = 0 , x‖ = 0 .
Wir betrachten das transformierte Tableau, wo am oberen Rand die yi, i ≤ k und die xj ,j > k stehen. (ξ, η) ist also ein zulassiger Einkaufsplan mit dem Preis M − η0.Dies beweist ξb ≤ M .
Im Falle M⋆ > −∞ funktioniert das Argument auch fur M = M⋆. Es existiert einEinkaufsplan mit minimalem Preis M⋆. Im Falle M⋆ = −∞ finden wir zulassige Ein-kaufsplane mit beliebig kleinem Preis. Auch in diesem Falle gilt also M⋆ = m⋆. Das
Theorem ist bewiesen. Die Eintrage von b sind echt positiv; sie sind die Eintrage von x|
und y‖. Die fur den maximalen Ertrag zu produzierenden Mengen sind
(x| , x‖) = (b| , 0) .
Der maximale Gewinn ist der Wert der Zielfunktion in diesem Punkt, M = −d.
Minimierung
Aus der Annahme, dass die Zielfunktion des Maximierungsproblems im Punkt x maximalist, folgt nun, dass die Eintrage von c nicht positiv sind. Ware namlich ein ck > 0, dannkonnte man durch Vergroßern der entsprechenden Variablen am oberen Rand einen echtgroßeren M-Wert erreichen ohne die Zulassigkeit zu gefahrden.Aus c ≤ 0 folgt dann aber, dass (y|, ξ‖) = (0, 0) einen zulassigen Einkaufsplan liefert. Er
hat den Preis m = −d. Die einzukaufenden Mengen sind (ξ|, ξ‖) = (c|, 0).
Satz
Wenn M(c, d) < ∞ und das Maximum in einem Extremalpunkt x angenommen wird,durch welchen genau nHyperebenen gehen, dann liefert dieses x ein perfekt ausgetauschtesTableau.
Den allgemeinen Fall wollen wir hier nicht diskutieren. Wir wollen die Sachlage lieberaus der Sicht der Legendre-Dualitat erortern.
Duale Kegel
Eine Teilmenge K eines reellen Vektorraums V heißt bekanntlich ein konvexer Kegel,wenn gilt
w1, . . . , wN ∈ K , λk ≥ 0 fur alle k ⇒∑
λkwk ∈ K .
Ein konvexer Kegel ist also eine konvexe Menge mit der zusatzlichen Eigenschaft
w ∈ K ⇒ λw ∈ K fur alle λ ≥ 0 .
Zu jeder Menge E ⊆ V existiert ein kleinster sie umfassender konvexer Kegel; er bestehtaus den Vektoren
w =∑
λkwk mit λk ≥ 0 , wk ∈ E .
Seine abgeschlossenen Hulle ist der kleinste E umfassende abgeschlossene konvexe Kegel.Wir bezeichnen ihn mit Ea.
Definition
Sei E ⊆ V undE⋆ =
{ℓ(·) : 〈ℓ, v〉 ≤ 0 fur alle v ∈ E
}⊆ V ⋆ .
Dann heißt E⋆ der duale Kegel.
, Seite 153
Bemerke :
Zu jedem E ⊆ V ist E⋆ ein abgeschlossener Kegel in V ⋆. Je großer E ist, desto kleiner istE⋆; Ea hat aber denselben dualen Kegel wie E. Man nennt daher E⋆ den zu Ea dualenKegel.
Theorem
Fur jedes E ⊆ V giltE⋆⋆ = Ea .
Dies ist ein Spezialfall der Legendre-Dualitat. Man betrachte auf V die Funktion
k(v) =
{0 falls v ∈ Ea
+∞ sonst
Es handelt sich um eine unterhalbstetige konvexe Funktion. Die Legendre-Transformiertek⋆(·) kann nur die Werte 0 und +∞ annehmen.
{ϑ : k⋆(ϑ) = 0
}={ϑ : sup{ϑv : v ∈ Ea} <∞
}=
= {ϑ : ϑv ≤ 0 fur alle v ∈ Ea} = E⋆ .
E⋆ ist die Endlichkeitsmenge von k⋆; E⋆⋆ ist die Endlichkeitsmenge von k⋆⋆. Nach demSatz von Legendre-Dualitat gilt
k⋆⋆(·) = k(·) also E⋆⋆ = Ea .
Der Satz von Farkas (1902) behandelt einen speziellen Fall: F ist hier eine endliche Mengeim Dualraum V ⋆. F a ist also die Gesamtheit aller positiven Linearkombinationen derElemente von F .
Satz (Farkas)
Ein konvexer Kegel K ⊆ V sei durch endlich viele lineare Ungleichungen gegeben
K :={v : ℓ(k)(v) ≤ 0 fur k = 1, . . . , p
}⊆ V .
Die ubrigen ℓ(·) mit ℓ(v) ≤ 0 fur alle v ∈ K sind dann gerade die positiven Linearkombi-nationen der ℓ(k)(·). In Formeln
ℓ(·) ≤ 0 auf K ⇔ ∃ λ1, . . . , λp ≥ 0 : ℓ(·) =∑
λk · ℓ(k)(·) .
Beweis :
Sei F der von ℓ(1), . . . , ℓ(p) erzeugte Kegel in V ⋆.
F ={ℓ : ℓ(·) =
∑λkℓ
(k)(·) mit λk ≥ 0}.
F ist abgeschlossen.Der duale Kegel ist
F ⋆ = {v : 〈ℓ, v〉 ≤ 0 fur alle ℓ ∈ F} ={v : 〈ℓ(k), v〉 ≤ 0 fur k = 1, . . . , p
}= K .
Da F abgeschlossen ist, haben wir F ⋆⋆ = F , also
ℓ ∈ F ⋆⋆ ⇔ 〈ℓ, ·〉 ≤ 0 auf K ⇔⇔ ℓ ∈ F ⇔ ∃ λ1, . . . , λp ≥ 0 : 0 =
∑λkℓ
(k) .
Hinweis : Der Satz von Farkas ist das konvexe Gegenstuck zu einem Satz der linea-ren Algebra, dem wir schon ofters begegnet sind (z.B. bei der Methode der Lagrange-Multiplikatoren). Dies ist der
Satz
Ein Teilvektorraum L ⊆ V sei durch p lineare Gleichungen gegeben.
L :={v : ℓ(k)(v) = 0 fur k = 1, . . . , p
}⊆ V .
Die ubrigen Linearformen ℓ(·), die auf L verschwinden, sind dann gerade die Linearkom-binationen der ℓ(k)(·).Der Satz von Farkas wird wirksam, wenn man Extrema mit Nebenbedingungen sucht, diedurch endlich viele glatte Ungleichungen gegeben sind.
Dualitat in der linearen Optimierung
Gegeben ist eine m×n-Matrix A, eine m-Spalte b und eine n-Zeile c. Dazu definieren wir
Kb : = {x : x ≥ 0 , Ax ≤ b} und(M)
M⋆ = sup {cy : x ∈ Kb}Lc = {ξ, ξ ≥ 0 , ξA ≥ c}(m)
m⋆ = inf{ξb : ξ ∈ Lc} .
Theorem
Fur beliebige A, b, c gilt :
sup{cx : x ∈ Kb} = M⋆ = m⋆ = inf{ξb : ξ ∈ Lc} .
Vorbemerkungen
1. Wir bestatigen nochmals x ∈ Kb , ξ ∈ Lc ⇒ cx ≤ ξb .Wir haben namlich 0 ≥ ξ(Ax− b) = (ξA− c)x+ cx− ξb.Wir mussen also zeigen, dass es keine Lucke zwischen dem Supremum und demInfimum gibt.
2. M⋆ = ∞ impliziert Lc = ∅ ; denn fur jedes ξ ∈ Lc mussten wir haben ξb ≥ M⋆
(Widerspruch). Auch in diesem Falle gilt also m⋆ = M⋆.
, Seite 155
3. Wenn M⋆ = −∞, dann ist Kb leer. Wir mussen zeigen, dass in diesem Fall ξb aufLc nach unten unbeschrankt ist. Dies werden wir spater erledigen.
4. Sei M > M⋆, und daher cx < M auf Kb. Wir zeigen, dass es ein ξ ∈ Lc gibt mitξb ≤ M . Der Schlussel zum Beweis ist der Satz von Farkas. Allerdings mussen wirerst von den konvexen Mengen Kb ⊆ Rn zu konvexen Kegeln Kb ⊆ Rn+1 ubergehen.
Beweis des Theorems
1. Der Raum der affinen Funktionen
a(x) = α1 · x1 + . . .+ αn · xn − β auf dem Rn
ist ein (n+1)-dimensionaler Vektorraum V ⋆. Wir reprasentieren die Elemente durch(n+ 1)-Zeilen
a(·)↔ (−β, α1, α2, . . . , αn) .
Die Elemente des Dualraums V reprasentieren wir durch (n+1)-Zeilen v = (x0, x1, . . . , xn)T
〈a, v〉 = −βx0 + α1x1 + . . .+ αnx
n .
2. Im Vektorraum V betrachten wir den Kegel
Kb ={x : xj ≥ 0 fur j = 1, . . . , n, bix0 +
∑aijx
j ≤ 0 fur i = 1, . . . , m}.
Der Kegel ist durch (m+ n + 1) lineare Ungleichungen beschrieben.Wir haben also m+ n+ 1 Linearformen ℓ(k)(·) mit ℓ(k)(·) ≤ 0 auf Kb.Nach dem Satz von Farkas sind die ubrigen Linearformen ℓ(·) mit ℓ(·) ≤ 0 auf Kb
die positiven Linearkombinationen.
3. Wir haben nun eine Linearform ℓ(·) mit ℓ(·) ≤ 0 auf Kb, namlich die Linearform
c1 · x1 + . . .+ cn · xn − M · x0 .
Es existieren also η0, η1, . . . , ηn, ξ1, . . . , ξm ≥ 0, sodass
− Mx0 + c1x1 + . . .+ cnx
n =
=η0(−x0) + η1(−x1) + . . .+ ηn(−xn) +∑
i
ξi(−bi · x0 +∑
j
aijxj)
=
(η0 +
∑
i
ξibi
)(−x0) +
n∑
j=1
(−ηj +
∑ξia
ij
)xj .
Wegen der linearen Unabhangigkeit der xj gilt also
∑ξib
i = M − η0∑
ξiaij − cj = ηj fur j = 1, . . . , m .
(ξ, η) ist also ein zulassiger Einkaufsplan mit dem Preis M − η0.Dies beweist ξb ≤ M .
4. Im Falle M⋆ > −∞ funktioniert das Argument auch fur M = M⋆. Es existiert einEinkaufsplan mit minimalem Preis M⋆. Im Falle M⋆ = −∞ finden wir zulassigeEinkaufsplane mit beliebig kleinem Preis. Auch in diesem Falle gilt also M⋆ = m⋆.Das Theorem ist bewiesen.
![Lineare Algebra I Bernd Ammann, WS 2007/08 · ... Lineare Algebra und Analytische Geometrie [8] Falko Lorenz, Lineare Algebra I und II [9] Serge Lang, Linear Algebra, Second Edition,](https://img.pdfslide.org/doc/110x75/5c66806a09d3f252168c7903/lineare-algebra-i-bernd-ammann-ws-200708-lineare-algebra-und-analytische.jpg)
