Lineaire Algebra 2 [version 11 Apr 2017 ed.] [PDF]

Zitiervorschau

Lineaire Algebra 2 Jan Brandts

11 april 2017

2

Inhoudsopgave 0.1

Inleiding en opzet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1 Canonieke vormen 1.1 Lineaire transformaties en gelijkvormige matrices . . . . . . . . . . . . . . . 1.1.1 Gelijkvormigheid en gelijkvormigheidsklassen . . . . . . . . . . . . . 1.1.2 Elementaire gelijkvormigheidstransformaties . . . . . . . . . . . . . . 1.1.3 Gelijkvormige matrices horen bij dezelfde lineaire transformatie . . . . . 1.1.4 Voorbeeld: de gelijkvormigheidsklassen van de vectorruimte F2×2 2 1.2 Triangulatiestellingen voor lineaire transformaties . . . . . . . . . . . . . . . 1.2.1 Geschiedenis en motivatie . . . . . . . . . . . . . . . . . . . . . . . . 1.2.2 Triangulatie van 2 × 2 matrices . . . . . . . . . . . . . . . . . . . . . 1.2.3 Blokvermenigvuldiging en triangulatie van 3 × 3 matrices . . . . . . 1.2.4 Inductiebewijs van de triangulatiestelling van Jacobi . . . . . . . . . 1.2.5 Invariante deelruimtes en complete vlaggen . . . . . . . . . . . . . . 1.2.6 De triangulatiestelling van Schur . . . . . . . . . . . . . . . . . . . . 1.2.7 Toepassing: Schur decompositie en Google’s PageRank . . . . . . . . 1.2.8 Spectraalstellingen voor normale, Hermietse, en unitaire matrices . . 1.3 De Jordannormaalvorm van een lineaire transformatie . . . . . . . . . . . . n (h) . . . . . . . . . 1.3.1 Gerichte gelijkvormigheidstransformaties met Eij 1.3.2 Gerichte gelijkvormigheidstransformaties met Πk` . . . . . . . . . . . 1.3.3 De klasse van nilpotente Jordanvormen . . . . . . . . . . . . . . . . 1.3.4 Gelijkvormigheidstransformaties van stricte bovendriehoeksmatrices 1.3.5 Jordanvormen en de Jordannormaalvorm van een matrix . . . . . . 1.4 Opgaven . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 Dualiteit 2.1 De duale vectorruimte . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.1 Voorbeelden en eerste ori¨entatie . . . . . . . . . . . . . . . . . . 2.1.2 De duale basis β ∗ van V ∗ behorende bij een basis β van V . . . . 2.1.3 De dubbelduale vectorruimte V ∗∗ en het natuurlijke isomorfisme 2.1.4 Het isomorfisme van Riesz . . . . . . . . . . . . . . . . . . . . . . 2.1.5 De duale L∗ van een lineaire afbeelding L . . . . . . . . . . . . . 2.1.6 De annihilator . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.7 Quoti¨entruimtes . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Opgaven . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

. . . . . . . . .

. . . . . . . . .

5

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

7 7 8 9 11 13 14 16 16 18 20 21 23 25 26 30 32 35 37 41 46 46

. . . . . . . . .

53 53 54 56 59 60 65 67 68 70

4

INHOUDSOPGAVE

3 Niet-negatieve lineaire algebra 3.1 Perron-Frobeniustheorie . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1.1 De Neumannrij en de Neumannreeks . . . . . . . . . . . . . . . . 3.1.2 Perron-Frobeniustheorie voor positieve matrices . . . . . . . . . . 3.1.3 Von Mises-iteratie . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1.4 Een analytische aanpak van Perron-Frobeniustheorie . . . . . . . 3.1.5 Niet-negatieve matrices als limiet van positieve matrices . . . . . 3.1.6 Reducibele en irreducibele niet-negatieve matrices . . . . . . . . 3.1.7 Perron-Frobeniustheorie voor irreducibele niet-negatieve matrices 3.2 Dubbelstochastische matrices en de permanent . . . . . . . . . . . . . . 3.2.1 De stelling van Birkhoff-Van Neumann . . . . . . . . . . . . . . . 3.2.2 De permanent van een matrix . . . . . . . . . . . . . . . . . . . . 3.2.3 De permanent versus de determinant . . . . . . . . . . . . . . . . 3.2.4 De determinantale complexiteit van de permanent . . . . . . . . 3.2.5 Het algoritme van Ryser voor het berekenen van de permanent . 3.2.6 Een formule van Glynn . . . . . . . . . . . . . . . . . . . . . . .

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

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

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

77 77 78 80 83 84 85 87 90 91 93 97 98 100 101 103

0.1. INLEIDING EN OPZET

0.1

5

Inleiding en opzet

Deze tekst is bedoeld voor wiskundestudenten die reeds een gedegen eerste kennismaking hebben gehad met het vakgebied van de lineaire algebra en bekend zijn met vectorruimtes over een lichaam K, zoals ruimtes van matrices Kn×k , polynomen K[X]≤n , oneindige rijtjes KN , en nog algemener functies KK . We veronderstellen daarom kennis van begrippen als basis, co¨ordinaten, dimensie, lineaire transformaties en hun matrices, determinanten, eigenwaarden en eigenvectoren, evenals van de axiomatische opbouw van inproductruimtes over R en C. Wiskundestudenten aan de Universiteit van Amsterdam bezitten deze kennis nadat ze in hun eerste semester het 6 EC vak Lineaire Algebra hebben gevolgd (en gehaald), gegeven uit het gelijknamige boek van Paul Igodt en Wim Veys (Universtaire Pers Leuven, tweede editie). Het doel van deze tekst is primair om te voorkomen dat de in het eerste semester opgedane kennis te snel verwatert doordat er niet direct mee wordt doorgewerkt, en studenten bij logische vervolgvakken zoals Representatietheorie en Numerieke Lineaire Algebra, die vaak meer dan een jaar later pas gevolgd worden, niet thuis geven. Natuurlijk bestaat de inhoud uit nieuwe onderwerpen, die doorgaans te geavanceerd zijn (misschien ook te exotisch) om in een eerste kennismaking op te nemen. Over deze onderwerpen nu meer. In het eerste hoofdstuk over canonieke vormen herhalen we dat matrices in Kn×n gelijkvormig zijn als en alleen als ze dezelfde lineaire afbeelding voorstellen. Als voorbeeld bepalen we alle gelijkvormigheidsklassen van de eindige matrixruimte F22×2 . Vervolgens bewijzen we de stelling van C. Jacobi, die zegt dat als K algebra¨ısch afgesloten is, iedere gelijkvormigheidsklasse van Kn×n een bovendriehoeksmatrix bevat. We scherpen dit resultaat aan tot de observatie van I. Schur dat er zelfs een orthonormale basis bestaat ten opzichte waarvan een gegeven lineaire transformatie bovendriehoeksvorm aanneemt. Weer als speciaal geval van het laatste bewijzen we de spectraalstellingen voor zelfgeadjungeerde, voor normale, en voor unitaire transformaties van een eindigdimensionale vectorruimte V over K. Tot slot van het eerste hoofdstuk geven we een ongebruikelijk bewijs van de existentie en uniciteit van de Jordannormaalvorm van een bovendriehoeksmatrix R, gebaseerd op R. Brualdi’s The Jordan Canonical Form: An Old Proof. The American Mathematical Monthly 49(3) uit 1987. Voordeel van dit bewijs is, dat het ´en volledig is, ´en zeer elementair: er wordt een algoritme gegeven dat slechts bestaat uit het opeenvolgend toepassen van elementaire gelijkvormigheidstransformaties. Dit zijn transformaties van de vorm R 7→ E −1 RE waarbij E −1 een elementaire rij-operatie is, die studenten al kennen uit de context van het oplossen van stelsels vergelijkingen. Zo wordt duidelijk hoe een gegeven basis stapsgewijs aangepast kan worden tot het een Jordanbasis is, waarbij iedere stap ten hoogste twee basisvectoren verandert. Dit kan vervolgens zelfs als programmeer-opgave aan de studenten worden voorgelegd. Keerzijde van de gevolgde aanpak is dat concepten als gegeneraliseerde eigenvectoren, minimiumpolynomen, en Jordanketens onderbelicht blijven. Bestaande bewijzen van de existentie en uniciteit van de Jordannormaalvorm op grond van deze geavanceerdere concepten zijn echter veel minder triviaal, beginnen vaak met een willekeurige matrix A in plaats van een bovendriehoeksmatrix, en leiden vaak ook af van de uiteindelijke eenvoud van de berekening zodra een bovendriehoeksvorm bereikt is. Het achteraf introduceren van de geavanceerdere concepten nadat existentie en uniciteit al bewezen is, lijkt daarom een goede oplossing. In het tweede hoofdstuk behandelen we de duale vectorruimte van een doorgaans eindigdimen-

6

INHOUDSOPGAVE

sionale vectorruimte V over K. We geven de definitie van V ∗ , beschrijven de duale basis van V ∗ gegeven een basis van V , en leggen het verband met individuele co¨ordinaten. Vervolgens doen we een poging om het natuurlijke isomorfisme V ∼ = V ∗∗ inzichtelijk te maken door te benadrukken dat v ∈ V niet alleen een passieve rol heeft als argument van v ∗ (v), met v ∗ ∈ V ∗ een functionaal op V , maar ook een actieve rol ten aanzien van diezelfde v ∗ waarin v ∗ gezien wordt als het argument van v. Ervaring leert dat studenten hier in eerste instantie veel moeite mee hebben. Weinig verwonderlijk, gezien hun (school)achtergrond waarin de notatie f (x) frequenteert en een abusievelijk x(f ) hoogstwaarschijnlijk slechts een reprimande opleverde. Verdere onderwerpen in Hoofdstuk 2 zijn het isomorfisme van Riesz, de duale van een lineaire afbeelding, de annihilator, en kort de quoti¨entruimte. Alles blijft eindigdimensionaal, alhoewel we wel hinten naar de problematiek die optreedt bij vectorruimtes van dimensie oneindig. Hoofdstuk 3 behandelt enkele onderwerpen uit de context van de niet-negatieve lineaire algebra. Uiteraard de Perron-Frobeniustheorie, eerst voor positieve, later voor niet-negatieve matrices. Deze ligt onder andere aan de basis van discrete Markovprocessen. Hierin komen op elegante wijze een aantal eerdere concepten bijeen, die daardoor extra oefening krijgen. Zo wordt convergentie van de Neumannrij (Ak )k∈N bewezen door toepassing van canonieke vormen, en maakt het convergentiebewijs van de Von Mises-iteratie gebruik van zowel de Neumannrij als de Neumannreeks, alsmede van de Schurvorm van een matrix. Zodra nietnegativiteit aan bod komt, wordt de tekst combinatorisch van aard. We defini¨eren reducibele en irreducibele matrices aan de hand van hun onderliggende gerichte grafen en destilleren de Perron-Frobeniusstellingen in deze context. Vervolgens bekijken we het Birkhoff-polytoop Ωn van dubbelstochastische n×n matrices als belangrijke deelverzameling van niet-negatieve matrices. We bewijzen de stelling van Birkhoff-Von Neumann nadat we de stelling van FrobeniusK¨onig hebben bewezen die het mogelijk maakt te concluderen dat iedere M ∈ Ωn een positieve diagonaal heeft. Positieve diagonalen vormen een duidelijke motivatie voor de permanent van een matrix. We besteden aandacht aan de verhouding determinant-permanent, en de complexiteit van hun berekening. Tot slot leiden we het Algoritme van Ryser af en de Formule van Glynn, twee methodes die de permanent in orde 2n arithmetische operaties berekenen. Ook hier kunnen programmeer-opgaven worden uitgeschreven die het een en ander illustreren. Ieder hoofdstuk eindigt met een klein aantal opgaven, die ook niet de hele stof dekken. Docenten worden van harte aangemoedigd om naar eigen inzicht passende opgaven toe te voegen. Verantwoording Met aan zekerheid grenzende waarschijnlijkheid bevat deze tekst onnauwkeurigheden en zelfs fouten, echter geen pertinente opzettelijke leugens (althans, niet veel). Hij is meegegroeid met de cursus waar hij onderdeel van uitmaakt, en moet dan ook worden gezien als een project in aanbouw. Ik stel het zeer op prijs als fouten en/of opmerkingen worden gemeld. Jan Brandts Amsterdam, 21 maart 2017

Hoofdstuk 1

Canonieke vormen In dit hoofdstuk onderzoeken we hoe de keuze van een basis β voor een eindig dimensionale vectorruimte V over een getallenlichaam K doorwerkt in de matrix Lββ van een lineaire transformatie van V . Dit zal leiden tot de triangulatiestellingen van Jacobi en Schur. De laatste zal als speciale gevallen de spectraalstellingen voor zelfgedjungeerde, normale, en unitaire transformaties impliceren. Tot slot leiden we middels elementaire gelijkvormigheidstransformaties, toegepast op bovendriehoeksmatrices, de Jordannormaalvorm van een matrix af.

1.1

Lineaire transformaties en gelijkvormige matrices

Laat (V, K) een vectorruimte zijn over K met basis β = hv1 , . . . , vn i voor zekere n ∈ N. Schrijf coβ : V → Kn voor de co¨ ordinaatafbeelding   α1 coβ   V 3 α1 v1 + · · · + αn vn = v 7→  ...  ∈ Kn (1.1) αn die aan ieder element v ∈ V zijn geordende vector van co¨ordinaten ten opzichte van β toevoegt, en schrijf homK (V, V ) voor de verzameling van alle lineaire transformaties L : V → V . Gegeven een lineaire transformatie L ∈ homK (V, V ) is Lββ ∈ Kn×n de unieke matrix zo, dat ∀v ∈ V :

coβ (L(v)) = Lββ coβ (v).

(1.2)

Schrijf ε = he1 , . . . , en i voor de standaardbasis van Kn . De matrix Lββ is als volgt te bepalen. Propositie 1.1.1 Voor iedere j ∈ {1, . . . , n} is de j-de kolom van Lββ gelijk aan coβ (L(vj )). Bewijs. Laat j ∈ {1, . . . , n}. Uit (1.1) volgt dat coβ (vj ) = ej . Dus, substitutie van v = vj in (1.2) laat zien dat coβ (L(vj ) = Lββ ej . Merk tot slot op dat Lββ ej de j-de kolom van Lββ is.  Als γ een basis van V is ongelijk aan β, dan zal Lγγ in het algemeen ongelijk zijn aan Lββ . Dit roept de vraag op welke matrices op kunnen treden als de matrix van L ten opzichte van een gegeven basis van V . De verzameling van al deze matrices noteren we met M(L) = {A ∈ Kn×n | A = Lββ voor zekere basis β van V }. 7

(1.3)

8

HOOFDSTUK 1. CANONIEKE VORMEN

Voor elke L ∈ homK (V, V ) zal M(L) een gelijkvormigheidklasse van matrices in Kn×n blijken. We brengen daarom nu eerst het begrip gelijkvormigheid in de herinnering.

1.1.1

Gelijkvormigheid en gelijkvormigheidsklassen

We schrijven GLn (K) voor de deelverzameling van alle inverteerbare matrices in Kn×n . Definitie 1.1.2 (Gelijkvormigheid) Een matrix B ∈ Kn×n heet gelijkvormig met A ∈ Kn×n als er een X ∈ GLn (K) bestaat zodanig dat B = X −1 AX. Opmerking 1.1.3 Het is niet moeilijk na te gaan dat de relatie ∼ op Kn×n × Kn×n gedefinieerd door A ∼ B ⇔ A is gelijkvormig met B (1.4) een equivalentierelatie is. Deze relatie deelt Kn×n op in disjuncte equivalentieklassen, die we ook wel gelijkvormigheidsklassen noemen. Veel gemeenschappelijke eigenschappen van gelijkvormige matrices worden ge¨ımpliceerd door de resultaten geformuleerd in het komende lemma en het erna geformuleerde gevolg. Lemma 1.1.4 Veronderstel dat A, B ∈ Kn×n gelijkvormige matrices zijn. Dan geldt: • voor ieder polynoom p ∈ K[Y ] is p(A) gelijkvormig is met p(B); • det(A) = det(B); • dim(ker(A)) = dim(ker(B)). Bewijs. Veronderstel dat B = X −1 AX voor zekere X ∈ GLn (K). Laat p(Y ) = Y ` met ` ∈ N willekeurig. Dan geldt p(B) = B ` = (X −1 AX)` = X −1 A` X = X −1 p(A)X. Dit bewijst de eerste bewering voor monomen. De generalisatie naar polynomen is nu eenvoudig. De tweede bewering volgt uit de productformule voor determinanten, en de derde uit de equivalentie X −1 w = 0 ⇔ w = 0. Immers, Bv = 0

⇔

X −1 AXv = 0

⇔

AXv = 0.

Hieruit volgt dat b1 , . . . , bp een basis is van ker(B) als en alleen als Xb1 , . . . , Xbp een basis is van ker(A) en dus zijn de dimensies van beide nulruimtes gelijk.  Gevolg 1.1.5 Als A, B ∈ Kn×n gelijkvormig zijn dan geldt voor iedere ` ∈ N ∪ {0}: • voor alle λ ∈ K zijn (A − λI)` en (B − λI)` gelijkvormig; • de karakteristieke polynomen van A` en B ` zijn gelijk; • de algebra¨ısche multipliciteiten van de eigenwaarde λ van A` en van B ` zijn gelijk; • de meetkundige multipliciteiten van de eigenwaarde λ van A` en van B ` zijn gelijk. Het nut van de observaties over machten van gelijkvormige matrices blijkt uit het volgende.

1.1. LINEAIRE TRANSFORMATIES EN GELIJKVORMIGE MATRICES

9

Voorbeeld 1.1.6 Onderstaande 4×4 matrices A en B hebben beide 0 als enige eigenwaarde,     0  0 A= 0 0

1 0 0 0

0 0 0 0

0 0  1  0

en

0  0  0 0

1 0 0 0

0 1 0 0

0 0  = B, 0  0

met algebra¨ısche multipliciteit 4 en meetkundige multipliciteit 2. Toch zijn A en B niet gelijkvormig: voor A2 = 0 is de meetkundige multipliciteit van 0 vier, maar voor B 2 6= 0 drie.

1.1.2

Elementaire gelijkvormigheidstransformaties

Om te laten zien dat gelijkvormigheid in relatief kleine, overzichtelijke stappen kan worden bestudeerd, brengen we elementaire rij-operaties en elementaire matrices in de herinnering. Definitie 1.1.7 (Elementaire rij-operaties) De elementaire rij-operaties toegepast op de rijen R1 , . . . , Rn van een matrix zijn: • Rj → λRj , (λ 6= 0): het vermenigvuldigen van een rij met λ 6= 0; • Rj ↔ Ri : het verwisselen van twee rijen; • Rj → Rj + λRi , (i 6= j): het optellen van een veelvoud van een rij bij een andere rij. De restrictie i 6= j in de derde operatie sluit de onomkeerbare operatie Rj → Rj − 1 · Rj uit. Ieder van deze elementaire rij-operaties correspondeert met vermenigvuldiging van links met een zogeheten elementaire matrix. Definitie 1.1.8 (Elementaire matrices) Voor alle gehele k, ` ∈ {1, . . . , n} met k 6= ` en h ∈ K defini¨eren we de elementaire matrices n > Dkn (h) = In + (h − 1)ek e> k en Ek` (h) = In + hek e` ,

(1.5)

die mogelijk alleen op positie (k, k), respectievelijk (k, `), afwijken van de identiteit In ∈ Kn×n , en de elementaire matrices Πk` = In − (ek − e` )(ek − e` )> ,

(1.6)

dus Πk` is de identiteit In met kolommen k en ` verwisseld. Opmerking 1.1.9 De matrix Dkn (h) is een diagonaalmatrix met inverse Dkn (h−1 ) als h 6= 0, n (h) is een driehoeksmatrix met inverse E n (−h) voor alle h ∈ K, en Π−1 = Π . en Ek` k` k` k` Voorbeeld 1.1.10 Voorbeelden van ieder van deze elementaire matrixtypes zijn      1 1  0 D24 ( ) =  0 2 0

0

0 0 1 0 0  2 , 0 1 0  0 0 1

1  0 4 E24 (−3) =  0 0

0 1 0 0

0 0 0 −3  en 1 0  0 1

1  0 4 Π23 =  0 0

0 0 1 0

0 1 0 0



0 0  . 0  1

Linksvermenigvuldiging met D22 ( 21 ) geeft de rij-operatie R2 → 21 R2 . Linksvermenigvuldiging 4 (−3) geeft R → R − 3R , en Π4 correspondeert met R ↔ R . met E24 2 2 4 2 3 23

10

HOOFDSTUK 1. CANONIEKE VORMEN

Rechtsvermenigvuldiging van een matrix met een elementaire matrix resulteert op voorspelbare wijze in drie overeenkomstige types elementaire kolomoperaties. Definitie 1.1.11 (Elementaire kolom-operaties) De elementaire kolom-operaties toegepast op de kolommen K1 , . . . , Kn van een matrix zijn: • Kj → λKj , (λ 6= 0): het vermenigvuldigen van een kolom met λ 6= 0; • Kj ↔ Ki : het verwisselen van twee kolommen; • Kj → Kj + λKi , (i 6= j): het optellen van een veelvoud van een kolom bij een andere kolom. De restrictie i 6= j in de derde operatie sluit de onomkeerbare operatie Kj → Kj − 1 · Kj uit. Voorbeeld 1.1.12 Het product XD24 (2) correspondeert met de elementaire kolomoperatie 4 (3) met K → K + 3K , en XΠ K2 → 2K2 op X, het product XE24 4 4 2 23 met K2 ↔ K3 . Definitie 1.1.13 (Elementaire gelijkvormigheidstransformaties) Laat A ∈ Kn×n en X ∈ GLn (K). De omzetting A → B = X −1 AX (1.7) heet een gelijkvormigheidstransformatie van A met X. Deze zullen we vaak kortweg noteren als X A→B (1.8) Als de matrix X elementair is, spreken we van een elementaire gelijkvormigheidstransformatie. Opmerking 1.1.14 Omdat iedere X ∈ GLn (K) een product X1 · . . . · X` is van elementaire X

matrices, is A → B een op´e´envolging van elementaire gelijkvormigheidstransformaties: A

X1

→

X1−1 AX1

X2

→

...

X

→`

X`−1 · . . . · X1−1 AX1 · . . . · X` = X −1 AX = B.

Zo wordt een gelijkvormigheidstransformatie dus in inzichtelijke kleine stappen onderverdeeld. De effecten van elementaire gelijkvormigheidstransformaties leggen we uit met voorbeelden. 4 (2), Voorbeeld 1.1.15 Beschouw de gelijkvormigheidstransformatie van een matrix met D22    

 D24 (2)−1 

∗ 2 ∗ ∗ ∗ 4 ∗ ∗ 2 3 2 2  4  1 3 1 1  D (2) =  . ∗ 2 ∗ ∗  2 ∗ 4 ∗ ∗  ∗ 1 ∗ ∗ ∗ 2 ∗ ∗

Deze correspondeert met de twee operaties K2 → 2K2 en R2 → 21 R2 . Bekijk vervolgens     ∗  1 4 E24 (3)−1  ∗ 1

1 ∗ 1 ∗ 1 ∗ 4 −2 −2 −2 −8  1 1 1  4  E (3) =  , 1 ∗ 1  24 ∗ 1 ∗ 4  1 1 1 1 1 1 4

wat overeenkomt met R2 → R2 − 3R4 en K4 → K4 + 3K2 . Dus, alleen rij twee en kolom vier veranderen, en rij vier en kolom twee bepalen die verandering. Tot slot, laat      (Π423 )−1 

∗ 2 3 ∗

2 1 ∗ ∗ 2 1 1  4  3 Π = 2 3 4 4  23 3 4 ∗ ∗

1 2 ∗ 4 3 4  1 2 1  4 3 ∗

dan zien we dat R2 ↔ R3 en K2 ↔ K3 . In alle gevallen zijn de bewerkingen associatief.

1.1. LINEAIRE TRANSFORMATIES EN GELIJKVORMIGE MATRICES

11

Opmerking 1.1.16 Het is duidelijk dat gelijkvormigheidstranformaties met matrices van type Dkn en Πnk` het aantal nullen in een matrix niet veranderen. n zijn in staat is om het Voorbeeld 1.1.17 Gelijkvormigheidstransformaties van het type Ek` aantal nullen in een matrix te laten toenemen, zoals blijkt uit     1 1 1 0 2 2 −1 E12 (1) = . (1.9) E12 (1) 0 2 0 2 2 (1) kennelijk onafhankelijke eigenvectoren zijn horende bij Merk op dat de kolommen van E12 de eigenwaarden 1 en 2 van de gegeven matrix.

We keren nu terug naar de vraag welke matrices optreden als matrix van ´e´en L ∈ homK (V, V ).

1.1.3

Gelijkvormige matrices horen bij dezelfde lineaire transformatie

Laat V een vectorruimte zijn over K van dimensie n. In deze sectie bewijzen we eerst dat iedere matrix uit Kn×n optreedt als matrix van een lineaire transformatie L ∈ homK (V, V ), en vervolgens dat matrices A, B ∈ Kn×n gelijkvormig zijn als en alleen als er een L ∈ homK (V, V ) en basissen β en γ van V bestaat zo, dat A = Lββ en B = Lγγ . Lemma 1.1.18 Laat β = hv1 , . . . , vn i een basis zijn van een vectorruimte V over K. Voor iedere A ∈ Kn×n bestaat er een L ∈ homK (V, V ) zo, dat A = Lββ . Bewijs. Schrijf (aij ) = A voor de entries van A. Iedere lineaire afbeelding L wordt uniek bepaald door de beelden L(v1 ), . . . , L(vn ). Laat in dit geval L bepaald worden door L(vj ) = a1j v1 + · · · + anj vn , voor iedere j ∈ {1, . . . , n}. Dan geldt per definitie dat   a1j   coβ (L(vj )) =  ...  = Aej = Acoβ (vj ) anj en vergelijken we dit met (1.2) dan zien we dat blijkbaar A = Lββ .



Lemma 1.1.19 Laat L ∈ homK (V, V ). Alle matrices in M(L) zijn gelijkvormig. Bewijs. Laat β en γ basissen zijn van V en coβ en coγ de co¨ordinaatafbeeldingen. De matrices Lββ en Lγγ uit M(L) zijn de unieke matrices waarvoor coβ (L(v)) = Lββ coβ (v) en

coγ (L(v)) = Lγγ coγ (v)

(1.10)

voor alle v ∈ V . Beschouw de identieke afbeelding id : V → V : v 7→ v. Omdat id een bijectie is, is de matrix idγβ van id inverteerbaar, en heeft de eigenschap dat coγ (v) = coγ (id(v)) = idγβ coβ (v) en coβ (v) = (idγβ )−1 coγ (v)

(1.11)

12

HOOFDSTUK 1. CANONIEKE VORMEN

voor alle v. Combineren we (1.10) met (1.11) dan zien we dat coβ (L(v)) = (idγβ )−1 coγ (L(v)) = (idγβ )−1 Lγγ coγ (v) = (idγβ )−1 Lγγ idγβ coβ (v)

(1.12)

voor alle v ∈ V . Kennelijk geldt Lββ = (idγβ )−1 Lγγ idγβ en dus zijn Lββ en Lγγ gelijkvormig.



We tonen nu aan dat M(L) zelfs een complete equivalentieklasse onder gelijkvormigheid is. Lemma 1.1.20 Laat β = hv1 , . . . , vn i een basis zijn van een vectorruimte V over K. Dan bestaat er voor iedere X ∈ GLn (K) een basis γ van V zo dat X = idγβ . Bewijs. Laat X ∈ GLn (K) gegeven zijn, met inverse Y = (yij ). Definieer voor iedere j ∈ {1, . . . , n} een element wj ∈ V door wj = y1j v1 + · · · + ynj vn .

(1.13)

Schrijf γ = hw1 , . . . , wn i. Het is eenvoudig na te gaan dat γ een basis is voor V . Merk op dat (1.13) laat zien dat   y1j   coβ (wj ) =  ...  = Y ej = Y coγ (wj ). ynj Kennelijk geldt dat Y = idβγ en dus is X = Y −1 = (idβγ )−1 = idγβ .



Voor we onze laatste conclusie trekken, onderzoeken we welke basisveranderingen overeenkomen met de elementaire gelijkvormigheidstransformaties uit de vorige sectie. Gevolg 1.1.21 Laat β = hv1 , . . . , vn i. Dan geldt: • als γ gelijk is aan β met vk vervangen door h−1 vk , dan is idγβ = Dkn (h); n (h); • als γ gelijk is aan β met v` vervangen door v` − hvk , dan is idγβ = Ek`

• als γ gelijk is aan β met vk en v` verwisseld, dan is idγβ = Πnk` . Deze kunnen met goed recht de drie types elementaire basisveranderingen genoemd worden. Gevolg 1.1.22 Laat L ∈ homK (V, V ). Als B gelijkvormig is met A ∈ M(L), is B ∈ M(L). Bewijs. Laat A ∈ M(L). Dan is A = Lββ voor zekere basis β = hv1 , . . . , vn i van V . Laat nu B = X −1 AX voor zekere X ∈ GLn (K). Volgens Lemma 1.1.20 bestaat er een basis γ van V waarvoor idγβ = X. Dus geldt B = X −1 AX = (idγβ )−1 Lββ idγβ en dus is B = Lγγ . Dit bewijst de bewering.



Samengevat hebben we nu aangetoond dat de verzameling Kn×n bestaat uit equivalentieklassen van gelijkvormige matrices, en dat iedere klasse bestaat uit alle mogelijke matrices van een lineaire transformatie L ∈ homK (V, V ) ten opzichte van alle basiskeuzes voor V .

1.1. LINEAIRE TRANSFORMATIES EN GELIJKVORMIGE MATRICES

1.1.4

13

Voorbeeld: de gelijkvormigheidsklassen van de vectorruimte F22×2

We illustreren het voorgaande in de meest eenvoudige setting mogelijk. Beschouw het eindige lichaam F2 = {0, 1} met optelling en vermenigvuldiging als in de volgende tabellen, + 0 1

0 1 0 1 1 0

en

× 0 1

0 1 0 0 0 1

De tweedimensionale vectorruimte F22 over F2 bestaat uit de volgende vier elementen,         0 1 0 1 2 F2 = , , , . 0 0 1 1 Opmerking 1.1.23 Er zijn 44 = 256 verschillende manieren om aan iedere v ∈ F22 een element K(v) ∈ F22 toe te kennen. Er bestaan dus 256 verschillende afbeeldingen K van F22 naar F22 , waarvan zal blijken dat slechts een klein deel lineair is. De drie elementen uit F22 ongelijk aan nul zijn paarsgewijs lineair onafhankelijk. Hieruit volgt dat er zes verschillende basissen bestaan van F22 , namelijk de drie basissen             1 0 1 1 0 1 , , , , , , 1 1 1 0 1 0 en de drie basissen waarin de volgorde van ieder bovenstaand paar van vectoren is omgedraaid. De vectorruimte    0 0 1 , 0 0 0    0 1 1 , 1 1 1

van 2 × 2 matrices F2×2 2     0 0 0 0 , , 0 0 1 0     1 1 1 1 , , 1 0 1 1

met entries   0 1 , 0 0   1 0 , 1 1

uit F2 bevat de volgende 16 elementen,        1 0 1 1 1 0 0 , , , , 0 1 0 0 1 0 1        0 1 0 0 0 1 1 . , , , 1 0 1 1 0 1 0

Hiervan zijn er slechts zes inverteerbaar,             1 0 0 1 0 1 1 1 1 0 1 1 GL2 (F2 ) = , , , , , . 0 1 1 0 1 1 0 1 1 1 1 0 De derde matrix is de inverse van de zesde, de overige vier zijn inverse van zichzelf. Merk de correspondentie op tussen de matrices uit GL2 (F2 ) en de bovengegeven zes basissen van F22 . Opmerking 1.1.24 De elementaire matrices in GL2 (F2 ) zijn I = D12 (1) = D22 (1) en       0 1 1 1 1 0 2 2 Π212 = , E12 (1) = , E21 (1) = . 1 0 0 1 1 1 De overige twee elementen van F2×2 zijn hiervan een product: 2     0 1 1 1 2 2 2 = Π12 E21 (1) en = Π212 E12 (1). 1 1 1 0 Dit laat zien dat iedere X ∈ GL2 (F2 ) een product is van elementaire matrices.

14

HOOFDSTUK 1. CANONIEKE VORMEN

Volgens Lemma 1.1.18 is iedere A ∈ F22×2 de matrix van een lineaire transformatie L van F22 ten opzichte van een gegeven basis van F22 , dus bevat homF2 (F22 , F22 ) zestien elementen. Sommige van de matrices in F2×2 zijn gelijkvormig, zoals bijvoorbeeld 2     0 1 1 1 2 −1 = (Π12 ) Π212 , 1 1 1 0 en zijn dus matrices van dezelfde lineaire transformatie ten opzichte van verschillende basissen. Opmerking 1.1.25 Gelijkvormigheid kan vaak al ontkracht worden door het berekenen van eigenwaarden en eigenvectoren. Dat laatste is hier zeer eenvoudig: voor A ∈ F22×2 , bereken Av voor de drie niet-nul elementen uit F22 en controleer of Av een veelvoud van v is. Omdat                0 1 1 0 0 1 0 1 0 1 1 1 = , = , = 1 1 0 1 1 1 1 1 1 1 1 0 helemaal geen eigenwaarden in F2 , en is dus bijheeft de hier figurerende matrix uit F2×2 2 voorbeeld niet gelijkvormig met de volgende matrix die een eigenwaarde nul heeft:      0 1 1 1 . = 0 1 1 1 De overige twee vectoren in F22 zijn geen eigenvectoren voor deze laatste matrix. Enig rekenwerk verdeelt de 16 elementen van F22×2 onder in de volgende zes equivalentieklassen C1 , . . . , C6 onder gelijkvormigheid:         0 0 1 0 0 1 1 1 C1 = , C2 = , C3 = , , 0 0 0 1 1 1 1 0            1 0 1 1 0 1 0 0 0 1 1 1 , , , , C5 = , , C4 = 1 0 0 1 1 1 1 0 1 1 0 0             1 0 0 0 1 1 0 0 1 0 0 1 C6 = , , , , , . 0 0 0 1 0 0 1 1 1 0 0 1 

Kennelijk bestaat er niet voor iedere lineaire transformatie L van een vectorruimte V een basis β zo, dat Lββ bovendriehoeksmatrix is. We onderzoeken nu wanneer dit wel zo is.

1.2

Triangulatiestellingen voor lineaire transformaties

We memoreren de definitie van diagonaliseerbaarheid van lineaire transformaties en matrices. Definitie 1.2.1 (Diagonaliseerbaar) Een lineaire transformatie L ∈ homK (V, V ) heet diagonaliseerbaar als er een basis β van V bestaat waarvoor Lββ een diagonaalmatrix is. Een matrix A ∈ Kn×n heet diagonaliseerbaar als A gelijkvormig is met een diagonaalmatrix. Opmerking 1.2.2 Sectie 1.1 laat zien dat L diagonaliseerbaar is als en alleen als iedere matrix Lγγ van L gelijkvormig is met een diagonaalmatrix.

1.2. TRIANGULATIESTELLINGEN VOOR LINEAIRE TRANSFORMATIES

15

Niet iedere lineaire transformatie L van een vectorruimte V over K is diagonaliseerbaar. Als het lichaam K echter algebra¨ısch afgesloten is, dan zal het wel altijd mogelijk blijken om L op bovendriehoeksvorm te brengen. Definitie 1.2.3 Een lichaam K heet algebra¨ısch afgesloten als ieder niet-constant polynoom p ∈ K[X] met co¨effici¨enten in K een nulpunt heeft in K. Stelling 1.2.4 (Hoofdstelling van de Algebra) Het lichaam C is algebra¨ısch afgesloten. Naast dit bekende voorbeeld van een algebra¨ısch afgesloten lichaam geven we nog een tweede voorbeeld, met als doel te laten zien dat de komende stellingen niet uitsluitend over C gaan. Definitie 1.2.5 (Algebra¨ısche en transcendente getallen) Een getal a ∈ C heet algebra¨ısch als a een nulpunt is van een polynoom p ∈ Z[X]. We schrijven Q voor de verzameling van algebra¨ısche getallen. De getallen in C \ Q heten transcendent. Bekende voorbeelden van transcedente getallen zijn π en e. Stelling 1.2.6 De deelverzameling Q ⊂ C is een algebra¨ısch afgesloten en aftelbaar lichaam. Het is de doorsnede van alle algebra¨ısch afgesloten lichamen die Q bevatten. In navolging van het voorgaande geven we nu ook een bekend en een minder bekend voorbeeld van lichamen die niet algebra¨ısch afgesloten zijn. Voorbeeld 1.2.7 Het lichaam R is niet algebra¨ısch afgesloten. Immers, het niet-constante polynoom p(X) = 1 + X 2 uit R[X] heeft geen nulpunt in R. Voorbeeld 1.2.8 Beschouw het lichaam F2 uit Sectie 1.1.4. Het polynoom p(X) = 1 + X 2 uit F2 [X] heeft wel een nulpunt in F2 . Desondanks is F2 niet algebra¨ısch afgesloten: het niet-constante polynoom p(X) = X 2 + X + 1 heeft namelijk geen nulpunt in F2 . In Stelling 1.2.9 en Stelling 1.2.10 geven we nu twee formuleringen van hetzelfde resultaat, dat we vervolgens in een aantal stappen, ge¨ıllustreerd met voorbeelden, gaan bewijzen. Stelling 1.2.9 (Triangulatiestelling van Jacobi) Zij (V, K) een vectorruimte over een algebra¨ısch afgesloten lichaam K. Voor iedere lineaire transformatie L : V → V bestaat er een basis γ van V waarvoor de matrix Lγγ van L een bovendriehoeksmatrix in Kn×n is. Een equivalente (zie Sectie 1.1) matrix-formulering van Stelling 1.2.9 is de volgende. Stelling 1.2.10 (Matrixtriangulatie) Als K algebra¨ısch afgesloten is, dan is iedere A ∈ Kn×n gelijkvormig met een bovendriehoeksmatrix in Kn×n . Opmerking 1.2.11 In Sectie 1.1.4 zagen we dat de volgende twee matrices een gelijkvormigheidklasse vormen in F2×2 2 ,     0 1 1 1 , . 1 1 1 0 Geen van beide is dus gelijkvormig met een bovendriehoeksmatrix in F2×2 2 . Dit laat zien dat de veronderstelling in Stelling 1.2.10 dat K algebra¨ısch afgesloten is kan niet gemist worden.

16

1.2.1

HOOFDSTUK 1. CANONIEKE VORMEN

Geschiedenis en motivatie

Stelling 1.2.10 is vernoemd naar Carl Jacobi (1804-1851), die hem in 1837 publiceerde.

Carl Jacobi (1804-1851) en Issai Schur (1875-1941) Issai Schur (1875-1941) liet zien dat er onder dezelfde voorwaarden zelfs altijd een orthonormale basis β van V bestaat zodanig dat de matrix Lββ van de lineaire transformatie L bovendriehoeks is. Dit sterkere resultaat staat te boek als de Schurdecompositie. We bewijzen het in Sectie 1.2.6. Vervolgens illustreren we het belang van de Schurdecompositie. In Sectie 1.2.7 zien we hoe de Schurdecompositie kan worden ingezet om een kort bewijs te geven in de context van Google’s PageRank. In Sectie 1.2.8 leiden we er de diverse spectraalstellingen mee af voor normale, voor zelfgeadjungeerde, en voor unitaire transformaties. We beginnen echter in Secties 1.2.2 en 1.2.3 met het bestuderen van twee eenvoudige gevallen van Stelling 1.2.10, te weten A ∈ K2×2 en A ∈ K3×3 , en geven enkele voorbeelden. Daarna zal een inductieargument in Sectie 1.2.4 de stelling bewijzen voor A ∈ Kn×n voor alle n ∈ N.

1.2.2

Triangulatie van 2 × 2 matrices

De volgende relatief eenvoudige observatie staat aan de basis van alle triangulatiestellingen. Lemma 1.2.12 Gegeven een matrix A ∈ Kn×n met K algebra¨ısch afgesloten. Laat λ ∈ K en 0 6= x ∈ Kn met Ax = λx. Laat X ∈ GLn (K) zijn, met eerste kolom gelijk aan x. Dan is    X −1 AX =  

λ ∗ ... 0 ∗ ... .. .. . . 0 ∗ ...

∗ ∗ .. .

   . 

(1.14)

∗

Oftewel, de eerste kolom van X −1 AX is gelijk aan λe1 . Bewijs. Omdat Xe1 gelijk is aan de eerste kolom x van X, geldt Ax = λx ⇔ AXe1 = λXe1 ⇔ X −1 AXe1 = λe1 . Omdat X −1 AXe1 de eerste kolom is van de matrix X −1 AX, bewijst dit de bewering.



1.2. TRIANGULATIESTELLINGEN VOOR LINEAIRE TRANSFORMATIES

17

Opmerking 1.2.13 Als A ∈ Kn×n en K is algebra¨ısch afgesloten, dan heeft het karakteristieke polynoom p(A) ∈ K[X]≤n van A tenminste ´e´en nulpunt in K en dus bestaan λ ∈ K en x ∈ Kn , x 6= 0 zodanig dat Ax = λx. Daarnaast kan {x} ook altijd uitgebreid worden tot een basis γ = hx, x2 , . . . , xn i van Kn , en dus bestaat er een X ∈ GLn (K) met eerste kolom Xe1 = x. Dus voor alle A ∈ Kn×n is voldaan aan de voorwaarden van Lemma 1.2.12. Opmerking 1.2.14 Beschouw de re¨ele vectorruimte (R2 , R). Het lichaam R is niet algebra¨ısch afgesloten: het niet-constante polynoom p(X) = 1 + X 2 heeft immers geen nulpunt in R. De rotatie om de oorsprong van R2 over 90 graden is een lineaire transformatie L : R2 → R2 zonder re¨ele eigenwaarden. Er bestaat daarom geen basis β van R2 zodanig dat Lββ een bovendriehoeksmatrix is. Lemma 1.2.12 geeft onmiddellijk het bewijs van Stelling 1.2.10 voor n = 2, en ook een rekenrecept om X ∈ GL2 (K) te bepalen zodanig dat X −1 AX = R bovendriehoeks is. Gevolg 1.2.15 Laat A ∈ K2×2 en Ax = λx met λ ∈ K en 0 6= x ∈ K2 . Laat X ∈ GL2 (K) een matrix zijn met eerste kolom gelijk aan x. Dan is   λ ∗ −1 (1.15) X AX = 0 ∗ en dit is dus een bovendriehoeksmatrix die gelijkvormig is met de matrix A. Bewijs. De matrix X −1 AX in (1.14) is nu 2 × 2 en dus triviaal bovendriehoeks.



Voorbeeld 1.2.16 We beschouwen de matrix A ∈ C2×2 met als enige eigenwaarde λ = 1,     7 4 −2 A= , ker(A − I) = span{x} met x = . (1.16) −9 −5 3 Omdat A geen twee lineair onafhankelijke eigenvectoren heeft, is A niet diagonaliseerbaar. We gaan daarom A op bovendriehoeksvorm brengen. Kies hiertoe, als ´e´en van de vele mogelijke keuzes (zie ook Opmerking 1.2.17) voor X ∈ GL2 (C) de matrix     −2 1 −2 3 −1 X= , dan is X = (1.17) 3 −2 1 −2 en vinden we X

−1

 AX =

−2 3 1 −2



7 4 −9 −5



−2 1 3 −2

En dus is R een bovendriehoeksmatrix gelijkvormig met A.



 =

1 1 0 1

 = R.

(1.18) 

Opmerking 1.2.17 De keuze van X in (1.17) is verre van uniek; de eerste kolom kan iedere eigenvector van A zijn, de tweede kolom iedere vector die geen veelvoud is van de eerste. Hier kozen we de tweede kolom zo, dat det(X) = 1. Hierdoor bevat de inverse X −1 geen breuken. Verschillende keuzes resulteren doorgaans in verschillende bovendriehoeksvormen van A, die natuurlijk wel dezelfde diagonaal-elementen hebben (mogelijk in een andere volgorde).

18

HOOFDSTUK 1. CANONIEKE VORMEN

Opmerking 1.2.18 De matrix X kan zelfs zo worden gekozen, dat de kolommen orthonormaal zijn, door de gevonden eigenvector op lengte ´e´en te schalen, en er een tweede kolom met lengte ´e´en loodrecht op de eerste naast te zetten. In Sectie 1.2.6 komen we hier op terug. Het volgende voorbeeld illustreert Stelling 1.2.9 ingeval n = 2. Voorbeeld 1.2.19 Beschouw de complexe vectorruimte (C[X]≤1 , C) van polynomen van graad ten hoogste ´e´en in X met complexe co¨effici¨enten, met daarop de lineaire transformatie L:

C[X]≤1 → C[X]≤1 :

p 7→ p + p(0)X.

(1.19)

Het polynoom p1 met voorschrift p1 (X) = X is een eigenvector van L bij eigenwaarde 1, immmers, L(p1 ) = p1 + 0 · p1 = p1 . Samen met het constante polynoom p2 (X) = 1 geeft dit een basis β = hp1 , p2 i van C[X]≤1 . Het is vervolgens eenvoudig om na te gaan dat   1 1 β , (1.20) Lβ = 0 1 dus de matrix van L ten opzichte van β is een bovendriehoeksmatrix.



Opmerking 1.2.20 De algemene werkwijze bij een lineaire transformatie L van een tweedimensionale vectorruimte V is, om eerst de matrix Lγγ ∈ K2×2 horend bij een willekeurige basis γ = hγ1 , γ2 i van V te bepalen. Immers, als vervolgens x = (x1 , x2 )> een eigenvector is van Lγγ in K2 , dan is u = x1 γ1 + x2 γ2 een eigenvector van L in V . Vul vervolgens hui op willekeurige wijze aan tot een basis β = hu, vi van V , dan is Lββ bovendriehoeks.

1.2.3

Blokvermenigvuldiging en triangulatie van 3 × 3 matrices

We laten nu middels een voorbeeld zien hoe we een matrix A ∈ K3×3 op bovendriehoeksvorm kunnen brengen, gebruik makend van het feit dat we dit voor 2 × 2 matrices al kunnen. Eerst een nuttig lemma over het rekenen met matrices die in blokvorm zijn gepartitioneerd. Lemma 1.2.21 (Blokvermenigvuldiging) Laat X, Y ∈ Kn×n en laat k, ` ∈ N met k + ` = n. Partitioneer     A B E F X= en Y = , (1.21) C D G H waarbij A, E ∈ Kk×k en D, H ∈ K`×` . Dan geldt   AE + BG AF + BH XY = . CE + DG CF + DH Bewijs. Volgt door geduldig uitschrijven.

(1.22) 

De blokvermenigvuldiging in (1.22) is dus volstrekt analoog aan die van twee 2 × 2 matrices. Gevolg 1.2.22 Veronderstel dat X ∈ Kn×n gepartitioneerd wordt als   A B , X= 0 D

(1.23)

1.2. TRIANGULATIESTELLINGEN VOOR LINEAIRE TRANSFORMATIES

19

waarbij A ∈ Kk×k en D ∈ K`×` met k, ` ∈ N, k + ` = n. Laat H ∈ GL` (K), dan geldt  −1     I 0 A BH I 0 = , (1.24) X 0 H 0 H 0 H −1 DH waarbij I ∈ Kk×k de identiteitsmatrix is. De blokvermenigvuldiging in Gevolg 1.2.22 zullen we gebruiken in het volgende voorbeeld. Voorbeeld 1.2.23  −1 A =  −2 −2

De volgende matrix A heeft als enige eigenwaarde λ = 1,    −1 3 1 −2 5  en ker(A − I) = span{x} met x =  1  . −3 6 1

(1.25)

Er zijn dus geen drie lineair onafhankelijke eigenvectoren, en dus is A niet diagonaliseerbaar. We laten zien hoe we A op bovendriehoeksvorm kunnen brengen. Hiertoe construeren we eerst een eenvoudig inverteerbare matrix X ∈ GL3 (K) waarvoor Xe1 = x, bijvoorbeeld,     1 0 0 1 0 0 X =  1 1 0  , waarvoor X −1 =  −1 1 0  , (1.26) 1 0 1 −1 0 1 en vinden we in overeenstemming met Lemma  1 −1  X AX = 0 0

1.2.12 dat  −1 3 −1 2  = B −2 3

een matrix is met als eerste kolom λe1 = e1 . Beschouw vervolgens de 2 × 2 matrix     1 −1 2 . met eigenvector C= 1 −2 3

(1.27)

(1.28)

Deze 2 × 2 matrix kan, net als in Voorbeeld 1.2.16, op bovendriehoeksvorm worden gebracht, bijvoorbeeld middels de matrix Y ∈ GL2 (C)       1 0 −1 2 1 0 1 2 −1 Y CY = = . (1.29) −1 1 −2 3 1 1 0 1 En dus, met behulp van Gevolg 1.2.22 vinden we dat    −1   1 2 3 1 0 1 0 B =  0 1 2  = R. 0 Y 0 Y 0 0 1 Combineren we (1.27) en (1.30) dan zien we dat we     1 0 0 1 1 0    0 Z=X = 1 1 0 0 Y 1 0 1 0

(1.30)

met    0 0 1 0 0 1 0 = 1 1 0  1 1 1 1 1

een matrix Z ∈ GL3 (C) hebben gecontrueerd waarvoor Z −1 AZ = R bovendriehoeks is.

(1.31) 

20

HOOFDSTUK 1. CANONIEKE VORMEN

Opmerking 1.2.24 Ondanks dat in (1.26) iedere inverteerbare matrix X met een niettriviaal veelvoud van x als eerste kolom volstaat, is het plezierig als X zonder al te veel rekenwerk ge¨ınverteerd kan worden. Merk hiertoe op dat X altijd van de vorm       1 0 0 0 0 1 0 0 1  a 1 0  of  1 0 0  of  0 1 0  , (a, b ∈ K) (1.32) b 0 1 a 1 0 1 0 0 kan worden gekozen, en dat de inverses hiervan vrijwel onmiddellijk op te schijven zijn. Opmerking 1.2.25 Ook de 2 × 2 matrix Y in (1.29) is op soortgelijke wijze gekozen om zijn eenvoudige inverse: het is altijd mogelijk om voor Y een marix van de vorm     1 0 0 1 Y = of Y = (1.33) a 1 1 0 te kiezen, en ook hiervan zijn de inverse direct op te schrijven. Opmerking 1.2.26 Ook in dit voorbeeld kan zowel de matrix X als de matrix Y zo worden gekozen, dat de kolommen orthonormaal zijn. De matrix X zal echter doorgaans niet meer van de vorm (1.32) zijn, noch zal Y van de vorm (1.33) zijn. Dit resulteert dan in een matrix Z met orthonormale kolommen zodanig dat Z −1 AZ bovendriehoeks is. Zie weer Sectie 1.2.6. Het zal nu duidelijk zijn hoe een matrix A ∈ Kn×n op bovendriehoeksvorm kan worden gebracht, ervanuitgaande dat we weten hoe dat moet voor een matrix B ∈ K(n−1)×(n−1) .

1.2.4

Inductiebewijs van de triangulatiestelling van Jacobi

We bewijzen nu Stelling 1.2.10 met behulp van volledige inductie. We veronderstellen dat K een algebra¨ısch afgesloten lichaam is. Inductiebasis: In Gevolg 1.2.15 in Sectie 1.2.2 zagen we reeds dat Stelling 1.2.10 geldt voor n = 2. De stelling geldt overigens natuurlijk ook voor n = 1. Inductiehypothese: Voor iedere matrix B ∈ K(n−1)×(n−1) bestaat er een Y ∈ GLn−1 (K) zodanig dat Y −1 BY = T een bovendriehoeksmatrix is. Inductiestap: Laat A ∈ Kn×n . Dan bestaat er volgens Lemma 1.2.12 een matrix X ∈ GLn (K) zodanig dat   λ b −1 X AX = . (1.34) 0 B Hierbij is b ∈ K1×(n−1) en B ∈ K(n−1)×(n−1) en is λ ∈ K een eigenwaarde van A. Volgens de inductiehypothese bestaat er een Y ∈ GLn−1 (K) zodanig, dat Y −1 BY = T bovendriehoeks is. Met behulp van Gevolg 1.2.22 geldt nu dat  −1    −1      1 0 1 0 λ b 1 0 λ bY 1 0 X −1 AX = = = R, 0 Y 0 Y 0 Y 0 B 0 Y 0 T en omdat T bovendriehoeks is, is R dat ook. Merk tot slot op dat de matrix   1 0 Z=X ∈ GLn (K), 0 Y

(1.35)

1.2. TRIANGULATIESTELLINGEN VOOR LINEAIRE TRANSFORMATIES

21

als product van twee inverteerbare matrices. We concluderen dat Z −1 AZ = R bovendriehoeks is. Dit bewijst Stelling 1.2.10.  Opmerking 1.2.27 De triangulatieconstructie van Jacobi kan al worden ingezet zodra ´e´en eigenwaarde van A bekend is. Daarna moet steeds een eigenwaarde van een kleinere matrix gevonden worden om het proces te kunnen continueren. Mocht A diagonaliseerbaar zijn, dan leidt dit proces in het algemeen echter niet automatisch tot een diagonalisatie van A. Voorbeeld 1.2.28 Gegeven de matrix     1 −1 −1 1 1 −2  met Ax = x voor x =  1  . A =  −2 2 1 4 −1 Een eenvoudig inverteerbare matrix  1 0 X= 1 1 −1 0 We vinden nu dat

X ∈ GL3 (C) met x als eerste   1 0 0 0  met X −1 =  −1 1 1 0 1

kolom is  0 0 . 1

 1 −1 −1 2 −1  = R, X −1 AX =  0 0 0 3

(1.36)

(1.37)



(1.38)

en R is bij toeval al bovendriehoeks. De eigenwaarden van A staan op de diagonaal van R. Indien gewenst kan A nu gediagonaliseerd worden door een basis van eigenvectoren te bepalen.

1.2.5

Invariante deelruimtes en complete vlaggen

Om de meetkundige betekenis van de triangulatiestelling van Jacobi te duiden, introduceren we twee nieuwe meetkundige begrippen. Definitie 1.2.29 (Invariante deelruimte) Zij L ∈ homK (V, V ). Een deelruimte U van V heet invariant onder L, of, indien de context duidelijk is kortweg invariant, als geldt dat L(u) ∈ U voor alle u ∈ U . Om aan te geven dat L(u) ∈ U voor alle u ∈ U zullen we ook de notatie L(U ) ⊂ U gebruiken. Voorbeeld 1.2.30 Zij u een eigenvector van een lineaire transformatie L : V → V van een vectorruimte (V, K). Dan is U = span{u} een invariante deelruimte onder L. Voorbeeld 1.2.31 Iedere deelruimte U ⊂ V van een vectorruimte (V, K) is invariant onder zowel de identieke afbeelding id : V → V : v → 7 v, als de nulafbeelding 0 : V → V : v 7→ 0. Definitie 1.2.32 (Vlag) Zij V een vectorruimte van dimensie n. Een rij geneste deelruimtes U1 ⊂ U2 ⊂ · · · ⊂ Uk ⊂ V

met dim(U1 ) < dim(U2 ) < · · · < dim(Uk )

met strict stijgende dimensies heet een vlag, en een complete vlag indien k = n.

(1.39)

22

HOOFDSTUK 1. CANONIEKE VORMEN

Definitie 1.2.33 (Ge¨ınduceerde complete vlag) Zij γ = hc1 , . . . , cn i een basis van een vectorruimte (V, K). Laat voor iedere k ∈ {1, . . . , n}, Uk = span{c1 , . . . , ck }.

(1.40)

Dan heet U1 ⊂ U2 ⊂ · · · ⊂ Un = V de door γ ge¨ınduceerde complete vlag. Voorbeeld 1.2.34 De standaardbasis he1 , . . . , en i induceert E1 ⊂ E2 ⊂ · · · ⊂ En = Kn met Ek = span{e1 , . . . , ek }. Deze complete vlag heet de standaardvlag in Kn . Het volgende lemma combineert de concepten van complete vlag en invariante deelruimte. Lemma 1.2.35 Laat R ∈ Kn×n . De standaardvlag bestaat uit invariante deelruimtes onder de lineaire transformatie L : Kn → Kn : x 7→ Rx als en alleen als R bovendriehoeks is. Bewijs. Laat k ∈ {1, . . . , n}. Duidelijk is dat Rx ∈ Ek voor alle x ∈ Ek als R bovendriehoeks is, en dus is Ek invariant onder L. Als R niet bovendriehoeks is, is e> i Rej 6= 0 voor zekere n ≥ i > j ≥ 1. Maar dat betekent dat Rej 6∈ Ej , en dus is Ej niet invariant.  We herformuleren nu de triangulatiestelling van Jacobi in deze nieuwe terminologie. Stelling 1.2.36 Zij (V, K) een vectorruimte met K algebraisch afgesloten. Voor iedere L ∈ homK (V, V ) bestaat er een complete vlag van invariante deelruimtes onder L. Bewijs. Laat op grond van Stelling 1.2.10 γ = hc1 , . . . , cn i een basis van V zijn waarvoor Lγγ een bovendriehoeksmatrix is. We gaan aantonen dat de door γ ge¨ınduceerde complete vlag U1 ⊂ U2 ⊂ . . . Un−1 ⊂ Un = V bestaat uit invariante deelruimtes Uk = span{c1 , . . . , ck }. Merk hiertoe op dat Lγγ de matrix is waarvoor geldt dat coγ (L(v)) = Lγγ coγ (v)

(1.41)

voor alle v ∈ V , waarbij coγ : V → Kn de co¨ordinaatafbeelding is. Laat nu k ∈ {1, . . . , n} gegeven zijn en kies u ∈ Uk . Dan is coγ (u) ∈ Ek = span{e1 , . . . , ek }. Omdat Lγγ bovendriehoeks is, is wegens Lemma 1.2.35 ook Lγγ coγ (u) ∈ Ek . En dus geeft (1.41) dat coγ (L(u)) ∈ Ek , wat equivalent is met L(u) ∈ Uk . Dit bewijst de bewering.  We besteden nu even kort aandacht aan de omkering van de uitspraak in Stelling 1.2.36. Stelling 1.2.37 Zij L : V → V een lineaire transformatie van een vectorruimte (V, K). Veronderstel dat U1 ⊂ U2 ⊂ . . . Un−1 ⊂ Un = V een complete vlag van invariante deelruimtes onder L is. Dan bestaat er een basis γ van V waarvoor Lγγ bovendriehoeks is. Bewijs. Laat γ1 = {c1 } een basis zijn van U1 . Kies nu voor iedere k ∈ {2, . . . , n} achtereenvolgens γk = γk−1 ∪ {ck } waarbij ck ∈ Uk en ck 6∈ Uk−1 . Dan is γ = γn = hc1 , . . . , cn i een basis van V met de eigenschap dat L(ck ) ∈ Uk , en dus is Lγγ een bovendriehoeksmatrix. 

1.2. TRIANGULATIESTELLINGEN VOOR LINEAIRE TRANSFORMATIES

1.2.6

23

De triangulatiestelling van Schur

In deze sectie gaan we na wat het concept inproduct kan toevoegen aan de triangulatiestelling van Jacobi. Dit zal leiden tot de triangulatiestelling van Schur. Lemma 1.2.38 Laat (V, K, h·, ·i) een inproductruimte zijn met basis γ = hc1 , . . . , cn i. Laat U1 ⊂ U2 ⊂ · · · ⊂ Un de complete vlag zijn ge¨ınduceerd door de basis γ van V . Dan bestaat er ook een orthonormale basis β die diezelfde vlag induceert. Bewijs. Definieer U0 = {0}. Voor iedere opeenvolgende k ∈ {1, . . . , n}, kies bk ∈ Uk met bk ⊥ Uk−1 en kbk k = 1. Dan is span{b1 , . . . , bk } = Uk voor alle k ∈ {1, . . . , n}. Dus induceert hb1 , . . . , bn i dezelfde comlete vlag als γ. Omdat bk loodrecht staat op b1 , . . . , bk−1 en kbk k = 1 voor alle k ∈ {1, . . . , n} is β = hb1 , . . . , bn i daarnaast ook een orthonormale basis van V .  Gevolg 1.2.39 Het Gram-Schmidt proces toegepast op γ resulteert in een orthonormale basis β die dezelfde vlag induceert als γ. Immers, ´e´en van de karakteriserende eigenschappen van het Gram-Schmidt proces is dat voor alle k ∈ {1, . . . , n} span{b1 , . . . , bk } = span{c1 , . . . , ck }.

(1.42)

Gram-Schmidt is dus een speciaal geval van de constructie in het bewijs van Lemma 1.2.38. Na deze inleiding zijn we in staat om de triangulatiestelling van Schur te bewijzen. Stelling 1.2.40 (Triangulatiestelling Schur) Zij (V, K, h·, ·i) een inproductruimte over een algebra¨ısch afgesloten lichaam K. Voor elke lineaire transformatie L : V → V bestaat er een orthonormale basis β van V waarvoor de matrix Lββ van L een bovendriehoeksmatrix is. Bewijs. Op grond van Stelling 1.2.9 bestaat er een basis γ = hc1 , . . . , cn i van V zodanig, dat de matrix Lγγ een bovendriehoeksmatrix is. Laat U1 ⊂ U2 ⊂ · · · ⊂ Un = V de door γ ge¨ınduceerde complete vlag zijn. Volgens Stelling 1.2.36 bestaat deze uit invariante deelruimtes onder L. Volgens Lemma 1.2.38 bestaat er een orthonormale basis β = hb1 , . . . , bn i zodanig dat voor alle k ∈ {1, . . . , n} dat span{b1 , . . . , bk } = span{c1 , . . . , ck } = Uk .

(1.43)

Omdat Uk invariant is, geldt L(bk ) ∈ span{b1 , . . . , bk }, en dus is Lββ bovendriehoeks.



De overeenkomstige formulering van Stelling 1.2.40 in termen van matrices is de volgende. Stelling 1.2.41 Gegeven een matrix A ∈ Kn×n met K algebra¨ısch afgesloten en een inproduct h·, ·i op Kn . Dan bestaat er een matrix U ∈ Kn×n met h·, ·i-orthonormale kolommen zodanig dat U −1 AU = R een bovendriehoeksmatrix is. Opmerking 1.2.42 Met A ∈ Cn×n en h·, ·i het standaardinproduct op Cn , zegt Stelling 1.2.41 dat er een unitaire matrix U bestaat zodanig dat U ∗ AU = R bovendriehoeks is. Definitie 1.2.43 (Schurvorm en Schurdecompositie) Een bovendriehoeksmatrix R als in Stelling 1.2.40 en Stelling 1.2.41 heet een Schurvorm van L of A, en de factorisatie A = U RU ∗ equivalent aan Stelling 1.2.41 een Schurdecompositie of Schurfactorisatie van A.

24

HOOFDSTUK 1. CANONIEKE VORMEN

Opmerking 1.2.44 Stelling 1.2.41 kan ook als volgt worden bewezen. Laat Au = λu met kuk = 1. Laat U ∈ Kn×n een matrix zijn met orthonormale kolommen met U e1 = u. Dan is volgens Lemma 1.2.12 de eerste kolom van U −1 AU gelijk is aan λe1 . Vervolgens kan een inductiebewijs worden gegeven, met als enige verschil met Sectie 1.2.6 dat de transformatiematrices niet alleen inverteerbaar zijn, maar zelfs orthonormale kolommen hebben. Dit alternatieve korte bewijs heeft twee nadelen. Ten eerste zouden we dan de triangulatiestelling van Jacobi niet zijn tegengekomen, en die zal later zijn nut nog bewijzen. Ten tweede is het veel minder rekenwerk eerst een basis γ te bepalen ten opzichte waarvan Lγγ bovendriehoeks is, en deze vervolgens met Gram-Schmidt te orthonormaliseren. Het boven gesuggereerde inductiebewijs volgend hebben we voor iedere k ∈ {2, . . . , n} een k × k matrix nodig met orthonormale kolommen, wat tot veel overbodige orthonormalisaties leidt. Voorbeeld 1.2.45 In Voorbeeld 1.2.16 zagen we de matrix A ∈ C2×2 ,     7 4 −2 A= , ker(A − I) = span{x} met x = . −9 −5 3

(1.44)

We brachten A op bovendriehoeksvorm door een X ∈ GL2 (C) te construeren met x als eerste kolom. We willen nu een sterker resultaat, namelijk, A op bovendriehoeksvorm brengen middels een matrix U met orthonormale kolommen. Kies derhalve   1 −2 3 U=√ (1.45) 3 2 13 dan heeft U orthonormale kolommen, geldt dus dat U −1 = U ∗ , en vinden we vervolgens        1 1 7 4 1 −13 −2 3 −2 3 ∗ √ . (1.46) U AU = √ = −9 −5 0 1 3 2 3 2 13 13 De rechtermatrix is inderdaad bovendriehoeks, maar niet gelijk aan R uit Voorbeeld 1.2.16. De Frobeniusnorm kAkF van een matrix A ∈ Cn×n is de wortel van de som van de kwadraten van de entries van A. Het is niet moelijk in te zijn dat als U unitair is, kU ∗ AU kF = kAkF .

(1.47)

In het bovenstaande voorbeeld uit zich dit in de gelijkheid 42 + 52 + 72 + 92 = 12 + 12 + 132 .

(1.48)

We beschouwen nu nogmaals de matrix uit Voorbeeld 1.2.23. Voorbeeld 1.2.46 λ = 1 en  −1  A = −2 −2

In Voorbeeld 1.2.23 zagen we de matrix A ∈ C3×3 met enige eigenwaarde  −1 3 −2 5  en −3 6

 1 ker(A − I) = span{x} met x =  1  . 1

Na enig rekenwerk vonden we in (1.30) dat   1 2 3 Z −1 AZ =  0 1 2  , waarbij 0 0 1



 1 0 0 Z =  1 1 0 . 1 1 1

(1.49)



(1.50)

1.2. TRIANGULATIESTELLINGEN VOOR LINEAIRE TRANSFORMATIES

25

Om een matrix U met orthonormale kolommen te vinden waarvoor U −1 AU bovendriehoeks is, volstaat het volgens Gevolg 1.2.39 om het Gram-Schmidt proces (van links naar rechts) toe te passen op de kolommen van Z. Dit geeft √ √  1/√3 −2/√6 √0 U =  1/√3 1/√6 1/√2  en 1/ 3 1/ 6 −1/ 2 



1 U ∗ AU =  0 0

p √  18 p200/3 1 16/3  . 0 1

(1.51)

Deze bovendriehoeksmatrix is daarmee dus een Schurvorm van A. Opmerking 1.2.47 Laat k ≤ n. Het toepassen van het Gram-Schmidt proces op de kolommen b1 , . . . , bk van een matrix B ∈ Kn×k resulteert in orthonormale vectoren q1 , . . . , qk die de kolommen zijn van een matrix Q ∈ Kn×k zodanig dat B = QR, Q> Q = I ∈ Kk×k , R ∈ Kk×k is bovendriehoeks.

(1.52)

Immers, de `-de kolom b` van B is per constructie in het Gram-Schmidt proces een lineaire combinatie van q1 , . . . , q` . De factorisatie (1.52) heet een QR-factorisatie van B. Indien nu X ∈ GLn (K) zodanig is, dat X −1 AX = R bovendriehoeks is, en X = QU met Q> Q = I en U bovendriehoeks een QR-decompositie van X is, dan volgt dat Q∗ AQ = Q−1 AQ = U X −1 AXU −1 = U RU −1 bovendriehoeks is als product van drie bovendriehoeksmatrices U, R en U −1 . Dit bewijst de Stelling van Schur in termen van QR-factorisatie van de matrix X in de Stelling van Jacobi.

1.2.7

Toepassing: Schur decompositie en Google’s PageRank

In het PageRank model van Page en Brin, de oprichters van Google, wordt een eigenvector berekend van de Google matrix G ∈ Rn×n . Deze matrix G is van de vorm G = αS + (1 − α)T, met

T =

ee> en α ∈ [0, 1). n

(1.53)

Hierbij is e de all-ones vector, oftewel, de som van alle standaard basisvectoren, α is een geheime parameter, en S ∈ Rn×n is een matrix die de link-structuur van het internet codeert.

Larry Page (b. 1973) en Sergey Brin (b. 1973)

26

HOOFDSTUK 1. CANONIEKE VORMEN

Bekend is dat de entries in iedere kolom van S niet-negatief zijn en optellen op tot ´e´en, oftewel, e> S = e> en dus

S > e = e.

Zo’n matrix heet kolomstochastisch. Merk op dat hier niets anders staat dan dat e een eigenvector is van S > horend bij eigenwaarde λ = 1. Dus heeft ook S een eigenwaarde 1. Omdat ook de kolommen van T optellen tot ´e´en, geldt hetzelfde voor G. Dus ook G is kolomstochastisch, en G> e = e. Dus is 1 ook een eigenwaarde van G. De volgende stelling is van groot belang voor het effici¨ent kunnen uitrekenen van een eigenvector horend bij λ = 1. Stelling 1.2.48 dim ker(G − I) = 1. Als λ 6= 1 een eigenwaarde is van G, dan |λ| ≤ α. Bewijs. Deze stelling werd in 2003 bewezen door S. Kamvar and T. Haveliwala.

Sepandar Kamvar en Taher Haveliwala Ze publiceerden het in een onderzoeksartikel van acht bladzijden getitled The Second Eigenvalue of the Google Matrix (Technical Report, Stanford University) dat inmiddels al ruim driehonderd keer is geciteerd. Het kan veel korter met de Schurdecompositie. Bewijs. Laat U ∗ S > U = R een Schurvorm van S > zijn met de eigenschap dat de eerste ko√ √ lom u = U e1 gelijk is aan de (genormaliseerde) eigenvector e/ n van S > . Dan is U ∗ e = ne1 , is de linksboven entry van R aan ´e´en, en zijn alle andere diagonaalentries van R in absolute waarde ten hoogste ´e´en. Het is niet moeilijk te zien dat ook de matrix U ∗ G> U = αU ∗ S > U + (1 − α)

U ∗ ee∗ U = αR + (1 − α)e1 e> 1, n

(1.54)

bovendriehoeks is. Immers, αR is bovendriehoeks, en (1 − α)e1 e> 1 is een matrix waarvan de linksboven-entry gelijk is aan 1 − α en de overige entries zijn nul. De linksboven-entry van U ∗ G> U is gelijk aan α · 1 + (1 − α) = 1. De overige diagonaalentries zijn in absolute waarde ten hoogste gelijk aan α. Maar deze diagnonaalentries zijn de eigenwaarden van U ∗ G> U , en dus ook de eigenwaarden van G> , en dus de complex geconjugeerden van de eigenwaarden van G. Omdat we al weten dat G ook een eigenwaarde λ = 1 heeft, weten we nu dat de eigenruimte behorende bij deze eigenwaarde dimensie ´e´en heeft als 0 ≤ α < 1. 

1.2.8

Spectraalstellingen voor normale, Hermietse, en unitaire matrices

In deze sectie beperken we ons tot lineaire transformaties van complexe inproductruimtes en hun matrices A ∈ Cn×n . We brengen eerst de geadjungeerde transformatie in de herinnering.

1.2. TRIANGULATIESTELLINGEN VOOR LINEAIRE TRANSFORMATIES

27

Definitie 1.2.49 ((Zelf-)geadjungeerde transformatie) Zij L : V → V een lineaire transformatie van een inproductruimte (V, C, h·, ·i). Dan is de lineaire transformatie L∗ : V → V met de eigenschap dat hL∗ (v), wi = hv, L(w)i voor alle v, w ∈ V

(1.55)

de geadjungeerde van de transformatie L. Als L = L∗ heet L zelfgeadjungeerd. Opmerking 1.2.50 De afbeelding L∗ is door (1.55) goedgedefinieerd: laat β = hb1 , . . . , bn i een orthonormale basis zijn van V , dan is L∗ (v) = β1 b1 + . . . βn bn waarbij βk uniek bepaald wordt door w = bk te substitueren in (1.55). De lineariteit van L∗ is niet moeilijk. Definitie 1.2.51 ((Zelf-)geadjungeerde matrix) De geadjungeerde A∗ van een matrix > A ∈ Cn×n is de matrix A∗ = A . Als A∗ = A dan heet A zelfgeadjungeerd. Lemma 1.2.52 Zij L : V → V een lineaire transformatie van een inproductruimte (V, C, h·, ·i) en K : V → V zijn geadjungeerde. Laat β = hb1 , . . . , bn i een orthonormale basis zijn van V . Dan geldt Kββ = (Lββ )∗ , (1.56) oftewel, de matrix van de geadjungeerde is gelijk aan de geadjungeerde van de matrix. Bewijs. We passen stap voor stap bekende definities en resultaten toe, 1

2

3

4

5

6

β > > > β e> i (Lβ ej ) = ei coβ (L(bj )) = hbi , L(bj )i = hK(bi ), bj i = hbj , K(bi )i = ej coβ (K(bi )) = ej Kβ ei

en concluderen van de ij-de entry van Lββ de geconjugeerde is van de ji-de entry van Kββ . Toelichtingen: (1) coβ (L(v)) = Lββ coβ (v) voor alle v ∈ V en dus ook voor v = bj , waarmee coβ (v) = ej ; (2) als L(bj ) = α1 b1 + · · · + αn bn dan is e> i coβ (L(bj )) = αi maar ook hbi , L(bj )i = αi ; (3) dit geldt precies wegens de definitie (1.55) van geadjungeerde afbeelding; (4) geconjugeerde symmetrie van een complex inproduct; (5) als K(bi ) = γ1 b1 + · · · + γn bn dan is hbj , K(bj )i = γj maar ook e> j coβ (K(bi )) = γj ; (6) coβ (K(v)) = Kββ coβ (v) voor alle v ∈ V en dus ook voor v = bi , waarmee coβ (v) = ei .



Gevolg 1.2.53 De matrix ten opzichte van een orthonormale basis van een zelfgeadjungeerde lineaire transformatie is zelfgeadjungeerd. Na de geadjungeerde in de herinnering te hebben geroepen, zijn we in staat om normale lineaire transformaties te defini¨eren. Definitie 1.2.54 (Normale lineaire transformatie) Een lineaire transformatie L : V → V van een inproductruimte (V, C, h·, ·i) heet normaal als L∗ ◦ L = L ◦ L∗ , waarbij ◦ staat voor de samenstelling van afbeelingen.

(1.57)

28

HOOFDSTUK 1. CANONIEKE VORMEN

Definitie 1.2.55 (Normale matrix) Een matrix A ∈ Cn×n heet normaal als A∗ A = AA∗ . De normale matrices zijn via orthonormale bases gerelateerd aan normale transformaties. Lemma 1.2.56 Zij L : V → V een lineaire transformatie van een inproductruimte (V, C, h·, ·i) en β een orthonormale basis van V . Dan is L normaal als en alleen als Lββ normaal is. Bewijs. Als Lββ de matrix is van L, dan geeft Lemma 1.2.52 dat (Lββ )∗ de matrix is van L∗ . Omdat daarnaast de matrix van een samengestelde afbeelding gelijk is aan het product van de matrices van de samenstellende afbeeldingen, volgt de bewering onmiddellijk.  We bewijzen nu nog twee belangrijke hulpresultaten, Lemma’s 1.2.57 en 1.2.58, voor normale matrices, die resulteren in de spectraalstelling voor normale matrices en transformaties. Lemma 1.2.57 A ∈ Cn×n is normaal als en alleen als iedere Schurvorm van A normaal is. Bewijs. Zij A = U RU ∗ een Schurdecompositie van A. Dan is A∗ = U R∗ U ∗ en dus AA∗ = (U RU ∗ )(U R∗ U ∗ ) = U RR∗ U ∗ en A∗ A = (U R∗ U ∗ )(U RU ∗ ) = U R∗ RU ∗

(1.58)

Dus A∗ A = AA∗ als en alleen als U R∗ RU ∗ = U RR∗ U ∗ . En omdat U inverteerbaar is, is dit zo als en alleen als R∗ R = RR∗ .  Lemma 1.2.58 Iedere normale bovendriehoeksmatrix R ∈ Cn×n is een diagonaalmatrix. Bewijs. Met volledige inductie. Voor n = 1 is de uitspraak triviaal waar. Neem als inductiehypothese aan dat de uitspraak geldt voor iedere bovendriehoeksmatrix T ∈ C(n−1)×(n−1) . Laat R ∈ Cn×n een bovendriehoeksmatrix zijn, en schrijf R∗ R = RR∗ gepartitioneerd uit als       ρ r∗ ρ r∗ ρ 0 ρ 0 = (1.59) r T∗ 0 T 0 T r T∗ waarbij ρ ∈ C, r ∈ Cn−1 en T ∈ C(n−1)×(n−1) bovendriehoeks. Uitvermenigvuldigen met behulp van Lemma 1.2.21 geeft dat     ρρ ρr∗ ρρ + r∗ r r∗ T ∗ = (1.60) rρ rr∗ + T ∗ T Tr T ∗T Dus is ρρ = ρρ + r∗ r, dus r∗ r = 0 en volgt uit de inproduct-axioma’s dat r = 0. Maar dan is ook rr∗ = 0, dus is T ∗ T = T ∗ T , en dus is T volgens de inductiehypothese diagonaal.  Stelling 1.2.59 (Spectraalstelling: normale matrices) Er is een unitaire matrix U zodanig dat U ∗ AU = Λ een diagonaalmatrix is als en alleen als A ∈ Cn×n normaal is. Bewijs. Zij A ∈ Cn×n normaal. Omdat C algebra¨ısch afgesloten is, bestaat er een volgens Stelling 1.2.41 een Schurdecompositie A = U RU ∗ van A met U unitair en R bovendriehoeks. Lemma 1.2.57 geeft dat R net als A normaal is, en Lemma 1.2.58 bewijst vervolgens dat R een diagonaalmatrix is. Veronderstel omgekeerd dat A = U ΛU ∗ met U unitair en Λ diagonaal, dan geldt dat A∗ = U Λ∗ U ∗ en dus dat A∗ A = (U Λ∗ U ∗ )(U ΛU ∗ ) = U (Λ∗ Λ)U ∗ = U (ΛΛ∗ )U ∗ = (U ΛU ∗ )(U Λ∗ U ∗ ) = AA∗

(1.61)

1.2. TRIANGULATIESTELLINGEN VOOR LINEAIRE TRANSFORMATIES

29

waarbij we gebruikten dat diagonaalmatrices triviaal normaal zijn. Dus is A normaal.



Spectraalstelling 1.2.59 is van centraal belang binnen de lineaire algebra. Het vertelt exact welke lineaire transformaties L : V → V van een inproductruimte (V, C, h·, ·i) ten opzichte van een geschikt gekozen orthonormale basis β van V een diagonaalgedaante Lββ aannemen. Stelling 1.2.60 (Spectraalstelling: normale transformaties) Laat L : V → V een lineaire transformatie van een inproductruimte (V, C, h·, ·i) zijn. Dan bestaat er een orthonormale basis β waarvoor Lββ een diagonaalmatrix is als en alleen als L normaal is. Bewijs. Veronderstel dat L normaal is, en laat γ = hc1 , . . . , cn i een orthonormale basis van V zijn. Volgens Lemma 1.2.56 is Lγγ dan een normale matrix. Op grond van Stelling 1.2.59 bestaat er een unitaire matrix U zodanig dat U ∗ Lγγ U diagonaal is. De kolommen van U vormen dus een orthonormale basis van eigenvectoren van Lγγ . Zoals bekend is iedere eigenvector van Lγγ de co¨ ordinaatvector coγ (v) van een eigenvector v van L. Dus is voor iedere j ∈ {1, . . . , n} is de vector bj ∈ V gedefinieerd door   u11 . . . u1n n X  ..  bj = u1j c1 + · · · + unj cn = uij ci , voor U =  ... (1.62) .  i=1 un1 . . . unn een eigenvector van L. Daarnaast is ook β = hb1 , . . . , bn i een orthonormale basis van V , omdat voor alle i, j ∈ {1, . . . , n} geldt hbi , bj i = hu1i c1 + · · · + uni cn , u1j c1 + · · · + unj cn i = u1i u1j + · · · + uni unj = ei U ∗ U ej . (1.63) Dus is Lββ diagonaal, en zelfs gelijk aan U ∗ Lγγ U . Dit bewijst ´e´en van beide implicaties. De andere implicatie is een eenvoudige oefening.  De volgende spectraalstelling gaat over de deelverzameling van zelfgeadjungeerde matrices; hiervoor kan een sterker resultaat worden bewezen dan voor normale matrices, in de zin dat de diagonaalmatrix re¨ele entries heeft, welke corresponderen met re¨ele eigenwaarden. Stelling 1.2.61 (Spectraalstelling: zelfgeadjungeerde matrices) Er bestaat een unitaire matrix U zodanig dat U ∗ AU = Λ een re¨ele diagonaalmatrixis als en alleen als A ∈ Cn×n zelfgeadjungeerd is. Bewijs. Laat A ∈ Cn×n met A∗ = A. Dan is A normaal en bestaat er volgens Stelling 1.2.59 een unitaire matrix U en een diagonaalmatrix Λ zo, dat U ∗ AU = Λ. Dus is A = U ΛU ∗ , en is A∗ = U Λ∗ U ∗ . Maar omdat A = A∗ volgt hieruit dat Λ = Λ∗ , en dus is de diagonaal re¨eel. Omgekeerd is triviaal A∗ = A zodra A = U ΛU ∗ met U unitair en Λ re¨eel diagonaal.  Stelling 1.2.62 (Spectraalstelling: zelfgeadjungeerde transformaties) Laat L : V → V een lineaire transformatie van een inproductruimte (V, C, h·, ·i) zijn. Dan is er een orthonormale basis β waarvoor Lββ re¨el diagonaal is als en alleen als L zelfgeadjungeerd is. Bewijs. Volledig analoog aan het bewijs van Stelling 1.2.60, met als toevoeging dat uit Stelling 1.2.61 volgt dat de eigenwaarden van L re¨eel zijn.  Tot slot bewijzen we de spectraalstellingen voor unitaire afbeeldingen en matrices.

30

HOOFDSTUK 1. CANONIEKE VORMEN

Definitie 1.2.63 (Unitaire lineaire transformatie) Een lineaire transformatie L : V → V van een inproductruimte (V, C, h·, ·i) heet unitair als L∗ ◦L = id = L◦L∗ , waarbij id : V → V staat voor de identieke afbeelding. Opmerking 1.2.64 De karakterisering L∗ ◦ L = id is equivalent met h(L∗ ◦ L)(v), wi = hv, wi

(1.64)

voor alle v, w ∈ V , en met behulp van de definitie van geadjungeerde transformatie met hL(v), L(w)i = hv, wi

(1.65)

voor alle v, w ∈ V , wat laat zien dat L hoeken en afstanden behoudt. Definitie 1.2.65 Een getal z ∈ C heet unimodulair als |z| = 1. Stelling 1.2.66 (Spectraalstelling: unitaire matrices) Er bestaat een unitaire matrix U en een diagonaalmatrix Λ met unimodulaire diagonaalentries zodanig dat A = U ΛU ∗ als en alleen als A ∈ Cn×n unitair is. Bewijs. Laat A ∈ Cn×n met A∗ A = I. Dan is A normaal en bestaat er volgens Stelling 1.2.59 een unitaire matrix U en een diagonaalmatrix Λ zo, dat U ∗ AU = Λ. Dus is A = U ΛU ∗ , en is A∗ = U Λ∗ U ∗ . Maar omdat AA∗ = I volgt hieruit dat ΛΛ∗ = I, en dus geldt voor een diagonaalentry λ van Λ dat λλ = 1. Dus is |λ| = 1. Omgekeerd is triviaal A∗ A = I zodra A = U ΛU ∗ met U unitair en Λ diagonaal met unimodulaire diagonaalentries.  Stelling 1.2.67 (Spectraalstelling: unitaire transformaties) Laat L : V → V een lineaire transformatie van een inproductruimte (V, C, h·, ·i) zijn. Dan is er een orthonormale basis β waarvoor Lββ diagonaal is met unimodulaire diagonaalentries als en alleen als L unitair is. Bewijs. Volledig analoog aan het bewijs van Stelling 1.2.60, met als toevoeging dat uit Stelling 1.2.66 volgt dat de eigenwaarden van L unimodulair zijn. 

1.3

De Jordannormaalvorm van een lineaire transformatie

We zagen in Sectie 1.2 dat iedere lineaire transformatie L : V → V van een vectorruimte (V, K) over een algebra¨ısch afgesloten lichaam K op bovendriehoeksvorm kan worden gebracht. Dit betekent dat voor iedere A ∈ Kn×n er een X ∈ GLn (K) bestaat met X −1 AX = R bovendriehoeks. We gaan dit resultaat aanscherpen middels verdere gelijkvormigheidstransformaties toegepast op bovendriehoeksmatrices. Eerst herinneren we aan de elementaire gelijkvormigheidstranformaties uit Sectie 1.1.2. Lemma 1.3.1 Gegeven een bovendriehoeksmatrix R ∈ Kn×n en h ∈ K en 1 ≤ k ≤ n. Laat T = Dkn (h)−1 R Dkn (h).

(1.66)

Dan kan T = (tij ) alleen afwijken van R in entries t1k , . . . , tk−1,k en entries tk,k+1 , . . . , tkn . Links in Figuur 2.1 illustreren we het effect van een gelijkvormigheidstransformatie met Dkn (h). Alleen in de donkere delen van de k-de rij en de k-de kolom kunnen entries veranderen.

1.3. DE JORDANNORMAALVORM VAN EEN LINEAIRE TRANSFORMATIE

31

Voorbeeld 1.3.2 Beschouw de gelijkvormigheidstransformatie van een bovendriehoeksmatrix 4 (2) met D22     2

1

1

 0 1 1 1  4  0 1 4 D22 (2)−1  D (2) =  0 0 1 1  22 0 0

1 2

1 2

1

0

1

0

1

1

1

0

1

0

0

1 0

. 1  1 

De tweede kolom en de tweede rij worden hierdoor respectievelijk vermenigvuldigd met 2 en 12 . Dit verandert de entries boven en rechts naast de positie (2, 2). Lemma 1.3.3 Gegeven een bovendriehoeksmatrix R ∈ Kn×n en h ∈ K en 1 ≤ k < ` ≤ n. Laat n n T = Ek` (h)−1 R Ek` (h). (1.67) Dan kan T = (tij ) alleen afwijken van R in entries t1` , . . . , tk,` en entries tk,`+1 , . . . , tkn . n (h) is de kolom-operatie K → K + hK . Omdat R Bewijs. De vermenigvuldiging S = REk` ` ` k bovendriehoeks is, verandert dit hooguit de bovenste k entries van K` . De vermenigvuldiging n (−h)S verandert evenzo hooguit de laatste n − ` entries in rij k.  Ek`

Voorbeeld 1.3.4 Beschouw de gelijkvormigheidstransformatie van een bovendriehoeksmatrix 4 (1), met de elementaire matrix E24 

2 0  4 E24 (1)−1  0 0

1 2 0 0



1 1 3 0



1 2 1  4  0 E (1) =  1  24 0 3 0

1 2 0 0

1 1 3 0



2 0  . 1  3

De rechtsvermenigvuldiging correspondeert met K4 → K4 +K2 , de linksvermenigvuldiging met R2 → R2 − R4 . Hierdoor veranderen de entries op en boven positie (2, 4). n (h). Figuur 2.1 rechts illustreert het effect van een gelijkvormigheidstransformatie met Ek` Alleen de entries in het donkere deel van de k-de rij en `-de kolom kunnen veranderen. In het bijzonder is het effect van de transformatie op de entry rk` op positie (k, `) aangegeven.

k

Dkn (h)

}

×h

n (h) Ek`

`

+h

}

k Dkn (h)−1

k

rk` 7→ rk` + h(rkk − r`` )

k

× h1

−h

n (h)−1 Ek`

`

Dkn (h)−1 · R · Dkn (h)

n (h)−1 · R · E n (h) Ek` k`

Figuur 2.1 Elementaire gelijkvormigheidstransformaties van een bovendriehoeksmatrix R.

32

HOOFDSTUK 1. CANONIEKE VORMEN

Lemma 1.3.5 Gegeven een bovendriehoeksmatrix R ∈ Kn×n en 1 ≤ k < ` ≤ n. Laat T = Π−1 k` R Πk` .

(1.68)

Dan kan T = (tij ) alleen afwijken van R in t1m , . . . , t`m en tmk , . . . , tmn met m ∈ {k, `}. Opmerking 1.3.6 Dus R en T verschillen hooguit in de entries tij in de k-de en `-de rij en kolom, maar niet als i < k of j > `. In het algemeen is T niet bovendriehoeks. Voorbeeld 1.3.7 Beschouw de gelijkvormigheidstransformatie van een bovendriehoeksmatrix met Π423    
−1  Π423 

1 0 0 0

1 2 0 0

1 2 3 0

1 1 2  4  0 Π = 3  23 0 4 0

1 3 2 0

1 0 2 0

1 3  . 2  1

De tweede en derde kolom worden verwisseld, en de tweede en derde rij. Na de gelijkvormigheidstransformatie in Voorbeeld 1.3.4 is de (2, 4)-entry gelijk is aan nul. We onderzoeken nu wanneer we welke entries in de bovendriehoek naar nul kunnen transformeren n (h). met behulp van de gelijkvormigheidstransformaties met matrices van type Ek` Opmerking 1.3.8 Het is niet mogelijk om het aantal nullen in een matrix te veranderen met elementaire gelijkvormigheidstransformaties met matrices van de types Dkn (h) en Πnk` .

1.3.1

Gerichte gelijkvormigheidstransformaties met Eijn (h)

Het volgende lemma verwoordt het resultaat van Voorbeeld 1.3.4 in zijn volle algemeenheid. Lemma 1.3.9 Gegeven een bovendriehoeksmatrix (rij ) = R ∈ Kn×n , h ∈ K en 1 ≤ k < ` ≤ n. Laat n n (h), (1.69) (h)−1 R Ek` T = Ek` en schrijf T = (tij ). Dan geldt dat tk` = rk` + hrkk − hr`` . Als bovendien rkk 6= r`` en h=

rk` , r`` − rkk

(1.70)

(1.71)

dan geldt dat tk` = 0. n (h) telt h maal de k-de kolom van R op bij Bewijs. Rechtsvermenigvuldiging van R met Ek` n (−h) de `-de kolom, en dus in het bijzonder hrkk op bij rk` . Linksvermenigvuldiging met Ek` trekt h maal de `-de rij af van de k-de rij, en dus in het bijzonder hr`` af van rk` + hrkk . Dit bewijst (1.70). De bewering over de keuze van h in (1.71) is vervolgens eenvoudig. 

Opmerking 1.3.10 Als (rij ) = R ∈ Kn×n bovendriehoeks is en rkk = r`` voor zekere k < ` n (h)−1 RE n (h) dat t = r dan volgt uit (1.70) dat met (tij ) = T = Ek` k` k` voor alle h ∈ K. k` Voorbeeld 1.3.4 was al een goede illustratie van Lemma 1.3.9, want het transformeerde de (2, 4)-entry naar nul. We proberen nu ook de (2, 3)-entry naar nul te transformeren.

1.3. DE JORDANNORMAALVORM VAN EEN LINEAIRE TRANSFORMATIE

33

Voorbeeld 1.3.11 Beschouw de matrix die resulteerde in het rechterlid in Voorbeeld 1.3.4. De entry op positie (2, 3) is gelijk aan 1. Met h = 1/(3 − 2) = 1 als in (1.71) volgt 

2  0 4 E23 (1)−1   0 0

1 2 0 0

1 1 3 0

  2  0  4  E23 (1) =    1 3

2 0 0 0

1 2 0 0

 2 2 0 −1   3 1  0 3

(1.72)

en in overeenstemming met Lemma 1.3.9 is de entry op positie (2, 3) gelijk aan nul. De entry erboven en er rechts naast zijn ook veranderd. Lemma 1.3.3 gaf al aan dat dit kan gebeuren. Opmerking 1.3.12 Merk op dat de (4, 2)-entry, die we in Voorbeeld 1.3.4 naar nul hadden getransformeerd, na de transformatie in Voorbeeld 1.3.11 weer ongelijk is aan nul! Lemma 1.3.3 laat zien in welke volgordes de transformaties kunnen worden toegepast om nullen te cre¨eren op alle posities (i, j) in een bovendriehoeksmatrix R waarvoor rii 6= rjj . Stelling 1.3.13 Zij R = (rij ) ∈ Kn×n een bovendriehoeksmatrix, en laat U(R) = {(i, j) ∈ {1, . . . , n} × {1, . . . n}, i < j | rii 6= rjj } .

(1.73)

Er bestaat een volgorde (i1 , j1 ), . . . , (ip , jp ) van de p elementen van U(R) en een keuze van getallen h1 , . . . , hp ∈ K zo, dat met het product X = Ein1 j1 (h1 ) · . . . · Einp jp (hp )

(1.74)

X −1 RX = T, met T = (tij ),

(1.75)

geldt dat een bovendriehoeksmatrix is waarvoor tij = 0 voor alle (i, j) ∈ U(R). Bewijs. Het volstaat een volgorde (i1 , j1 ), . . . , (ip , jp ) te kiezen waarin voor ieder tweetal opeenvolgende posities (iq , jq ) en (iq+1 , jq+1 ) geldt dat jq < jq+1 of iq > iq+1 . Hieruit volgt immers dat als q < r dan jq < jr of iq > ir . In beide gevallen zal volgens Lemma 1.3.3 een gelijkvormigheidstransformatie Einr jr (h) de entry op positie (iq , jq ) niet veranderen. In het bijzonder zal dus iedere tranformatie een nul cre¨eren, die daarna niet meer zal verdwijnen.  Het volgende algoritme illustreert een volgorde als genoemd in het bewijs van Stelling 1.3.13. Algoritme 1.3.14 Laat R ∈ Kn×n en schrijf U = U(R). Selecteer (i, j) ∈ U met i maximaal, en als er daar meerdere van zijn, met j minimaal. Pas een transformatie toe om de (i, j)-entry naar nul te transformeren. Verwijder (i, j) uit U en herhaal het proces tot U leeg is. Vanaf nu zullen we vaak een gelijkvormigheidstransformatie B = X −1 AX noteren met X

A −→ B om op die manier wat meer transformaties naast elkaar op dezelfde bladzijde te krijgen.

34

HOOFDSTUK 1. CANONIEKE VORMEN

Voorbeeld 1.3.15 We illustreren Stelling 1.3.13 met de matrix R uit Voorbeeld 1.3.4, 

2  0 R= 0 0

1 2 0 0



1 1 3 0

1 1  , 1  3

waarvoor U(R) = {(1, 3), (1, 4), (2, 3), (2, 4)} .

De door Algoritme 1.3.14 gegeven volgorde is (2, 3), (2, 4), (1, 3), (1, 4). De respectievelijke elementaire gelijkvormigheidstransformaties geven we schematisch weer als 

2  0 R= 0 0

1 2 0 0

1 1 3 0





1 2 4 (1) 1  E23  0 −→  1  0 3 0

1 2 0 0

2 0 3 0





2 1 4 (2) 0  E13  0 −→  0 1  0 3

1 2 0 0

2 0 −1 4 (−1) 0 0  E14  0 −→  0 3 1  0 0 3





1 2 0 0

0 0 3 0



0 0  = T. 1  3

4 (1), is de transformatie Omdat de entry op positie (2, 4) toevallig al nul is na toepassing van E23 4 E24 (h2 ) = I hier weggelaten. Het product X van de transformatiematrices is

1 0 2 −1  0 1 1 0  4 4 4 4 X = E23 (1) · E24 (0) · E13 (2) · E14 (−1) =  0 0 1 0  0 0 0 1



 (1.76)

en met deze X is X −1 RX dus gelijk aan T . Een gevolg van Stelling 1.3.13 is een bekend resultaat. Gevolg 1.3.16 Als alle eigenwaarden van R verschillen dan geeft Algoritme 1.3.14 een X zo, dat X −1 RX = Λ een diagonaalmatrix is. Dus Algoritme 1.3.14 diagonaliseert R. Voorbeeld 1.3.17 Laat R gegeven zijn door 

 1 2 3 R =  0 2 3  en dus U(R) = {(1, 2), (1, 3), (2, 3)} . 0 0 3

(1.77)

De door Algoritme 1.3.14 gegeven volgorde voor de elementaire gelijkvormigheidstransformaties is (2, 3), (1, 2), (1, 3). We vinden:        1 2 3 1 2 9 1 0 9 E3 ( 9 ) 1 0 0 3 (3) 3 (2) E23 E12 13 R =  0 2 3  −→  0 2 0  −→  0 2 0  −→2  0 2 0  = Λ, 0 0 3 0 0 3 0 0 3 0 0 3 

(1.78)

met als bijbehorende transformatiematrix 

1 2 3 3 3 9 X = E23 (3) · E12 (2) · E13 ( )= 0 1 2 0 0

9 2



3 , 1

waarvoor het eenvoudig te verifi¨eren is dat RX = XΛ de matrix R diagonaliseert.

(1.79)

1.3. DE JORDANNORMAALVORM VAN EEN LINEAIRE TRANSFORMATIE

35

Opmerking 1.3.18 Zowel de matrix X = (xij ) in (1.76) als de matrix X = (xij ) in (1.79) heeft de eigenschap dat xiq jq = hq voor alle (iq , jq ) ∈ U(R). Dit is geen toeval. Immers, Algoritme 1.3.14 geeft een lijst entries (i1 , j1 ), . . . , (ip , jp ) met bijbehorend product X van transformatiematrices > X = Ein1 j1 (h1 ) · . . . · Einp jp (hp ) = (In + ei1 e> j1 ) · . . . · (In + eip ejp )

(1.80)

Als q < r geldt voor de paren indices (iq , jq ) en (ir , jr ) dat iq < jq en ir < jr omdat ze corresponderen met posities boven de diagonaal. Daarnaast geldt of iq > ir , of iq = ir en jq < jr , per definitie van Algoritme 1.3.14. Hieruit volgt dat het uitvermenigvuldigen van het product in (1.80) geldt dat > (1.81) X = In + ei1 e> j1 + . . . eip ejp Immers, als iq > ir volgt uit iq < jq dat jq > ir . Anderzijds, als iq = ir dan volgt uit iq < jq > > ook dat ir = iq < jq . In beide gevallen is dus e> jq eir = 0 en dus ook eiq ejq eir ejr = 0. Voorbeeld 1.3.19 Voor n = 4 bewijst Opmerking 1.3.18 niets anders dan dat 

1 0 0  0 1 0  0 0 1 0 0 0



0 0  a  1

1 0 0 0

0 1 0 0

0 b 1 0



0 0  0  1



1  0 = 0 0



1 0 0 0 0 1 0 c  0 0 1 0  0 0 0 1

1 0 0 0



d 0 0 1 0 0  0 1 0  0 0 1

1 0 0 0

0 1 0 0

e 0 1 0



0 0  0  1

1 0 0 0

0 1 0 0

0 0 1 0



f 0  0  1



d e f 1 b c  voor alle 0 1 a  0 0 1

a, b, c, d, e, f ∈ K.

Overeenkomstige identiteiten gelden ook voor iedere andere waarde van n, als de matrices in deze door Algoritme 1.3.14 gegenereerde volgorde staan.

1.3.2

Gerichte gelijkvormigheidstransformaties met Πk`

Gelijkvormigheidstransformaties met elementaire matrices van het type Πk` kunnen worden ingezet om gelijke eigenwaarden naast elkaar op de diagonaal van R te positioneren. Het gevolg daarvan is dat de nullen boven de diagonaal in rechthoekige blokken terechtkomen. Voorbeeld 1.3.20 Gegeven de matrix 

2  0 R= 0 0

1 3 0 0

2 1 2 0



1 3  , 1  3

met U(R) = {(1, 2), (1, 4), (2, 3), (3, 4)} .

(1.82)

Algoritme 1.3.14 geeft als transformatievolgorde (3, 4), (2, 3), (1, 2), (1, 4). De respectievelijke elementaire gelijkvormigheidstransformaties geven we schematisch weer als 

2  0 R −→  0 0 4 (1) E34

1 3 0 0

2 1 2 0





3 2 4 (−1) 4  E23  0 −→  0  0 3 0

1 3 0 0

1 0 2 0





3 2 4 (1) 4  E12  0 −→  0  0 3 0

0 3 0 0

1 −1 2 4 (−1) 0 4  E14  0 −→  2 0  0 0 3 0





0 3 0 0

1 0 2 0



0 4  . 0  3

36

HOOFDSTUK 1. CANONIEKE VORMEN

Deze matrix kunnen we met een permutatie Πk` nu zo transformeren, dat gelijke eigenwaarden naast elkaar op de diagonaal komen te staan,     2

0

1

2

0

0

1

0

 0 3 0 4  Π423  0 2 0 0   0 0 2 0  −→  0 0 3 4 . 0

0

0

3

0

0

0

(1.83)

3

De getransformeerde matrix is blok-diagonaal is en beide blokken op de diagonaal zijn bovendriehoeks. Het bijbehorende product X van de elementaire matrices is     1

X=

4 E34 (1)

·

4 E23 (−1)

·

4 E12 (1)

·

4 E14 (−1)

·

Π423

1

0 −1 1 0 1 −1 0  4  0 −1 1 0  Π = . 1  23 0 1 0 1  0 1 0 0 0 1

 0 1 −1 = 0 0 1 0

0

Merk op dat X zelf geen bovendriehoeksmatrix meer is. Opmerking 1.3.21 De gelijkvormigheidstransformatie met Π23 kan al toegepast worden zodra de entry op positie (2, 3) gelijk is aan nul. Immers, dan is het resultaat al bovendriehoeks. Opmerking 1.3.22 Het is ook mogelijk om de volgorde van de diagonaalentries om te draaien in vergelijking tot (1.83), middels     2

0

1

3

0

4

0

0

 0 3 0 4  4 4 4  0 3 0 0  . Π423 Π434 Π412  Π Π Π = 0 0 2 0  12 34 23 0 0 2 1  0

0

0

3

0

0

0

2

Sterker nog, iedere volgorde van de getallen op de diagonaal kan worden bewerkstelligd. Bovenstaand voorbeeld met opmerkingen geeft aanleiding tot de volgende stelling. Lemma 1.3.23 Laat (rij ) = R ∈ Kn×n bovendriehoeks zijn, en k zo dat rkk 6= rk+1,k+1 . Dan is rk,k+1 n −1 n (1.84) T = Π−1 · R · Ek,k+1 (h) · Πk,k+1 met h = k,k+1 · Ek,k+1 (h) rk+1,k+1 − rkk bovendriehoeks met tkk = rk+1,k+1 en tk+1,k+1 = rkk . n Bewijs. De gelijkvormigheidstransformatie met Ek,k+1 (h) cre¨eert een nul op positie (k, k+1), waarna verwisseling van rijen k en k + 1 en kolommen k en k + 1 de beide diagonaalentries rkk en rk+1,k+1 verwisselt. De entries op posities (k, k + 1) en (k + 1, k) zijn en blijven nul. 

Lemma 1.3.23 wordt ge¨ıllustreerd in het volgende eenvoudige voorbeeld. Voorbeeld 1.3.24 Zie hoe  1 2  R= 0 2 0 0

R naar T wordt   3 1 3 E23 (−2)   2 0 −→ 1 0

getransformeerd in    2 −1 1 −1 2 3 Π23  0 1 0 =T 2 0  −→ 0 1 0 0 2

en dat de volgorde 1, 2, 1 van de diagonaalentries van R is veranderd in 1, 1, 2 voor T .

(1.85)

1.3. DE JORDANNORMAALVORM VAN EEN LINEAIRE TRANSFORMATIE

37

We kunnen nu een van de hoofdresultaten uit deze sectie formuleren. Stelling 1.3.25 Laat R ∈ Kn×n bovendriehoeks zijn met verschillende eigenwaarden λ1 , . . . , λp met respectievelijke algebra¨ısche multipliciteiten m1 , . . . , mp . Dan bestaat er een X ∈ GLn (K) zodanig dat     X −1 RX =  

T1

0

0 .. . 0

T2 .. .

... .. . .. . 0

...

0 ..  . 

 = T,

(1.86)

0  Tp

waarbij Tj een mj × mj bovendriehoeksmatrix is met alle diagonaalentries gelijk aan λj . Bewijs. Laat k het kleinste gehele getal zijn waarvoor rkk = λ1 . Dan zijn in het bijzonder r11 , . . . , rk−1,k−1 allemaal ongelijk aan rkk . Pas nu Lemma 1.3.23 toe om de entries op posities (k, k) en (k−1, k−1) te verwisselen, vervolgens nogmaals om de entries op posities (k−1, k−1) en (k − 2, k − 2) te verwisselen, enzovoorts, totdat λ1 op positie (1, 1) staat. Doe nu hetzelfde met de overige diagonaalentries die gelijk zijn aan λ1 , dan met alle diagonaalentries die gelijk zijn aan λ2 , enzovoorts. Pas tot slot Stelling 1.3.13 toe om nullen te cre¨eren op alle posities (k, `) waarvoor de entries op posities (k, k) en (`, `) verschillen. Dit geeft precies een matrix van de vorm T in (1.86).  In Sectie 1.3.4 bestuderen we verdere transformaties van de matrices T1 , . . . , Tp uit Stelling 1.3.25. Eerst besteden we Sectie 1.3.3 aan de beschrijving van het beoogde doel.

1.3.3

De klasse van nilpotente Jordanvormen

In deze sectie introduceren we de matrices die uiteindelijk als bouwstenen zullen fungeren voor de eenvoudigste matrix J die gelijkvormig is met een gegeven A ∈ Kn×n . Definitie 1.3.26 (Nilpotente Jordanvorm) Een matrix (sij ) = S ∈ Kn×n waarvoor iedere entry die ongelijk aan 0 is, gelijk is aan 1 en direct boven de diagonaal op een positie (i, i + 1) staat, oftewel, sij 6= 0

⇒

j =i+1

en

sij = 1,

(1.87)

noemen we een nilpotente Jordanvorm. Definitie 1.3.27 (Nilpotent Jordanblok) De nilpotente Jordanvorm in Kn×n met n − 1 entries gelijk aan 1 heet het nilpotente Jordanblok, en wordt genoteerd als Nn . Opmerking 1.3.28 Voor n = 1 is de matrix N1 = [0] het 1 × 1 nilpotente Jordanblok. Opmerking 1.3.29 Er bestaan precies 2n−1 nilpotente Jordanvormen in Kn×n , want iedere entry op positie (i, i+1) wordt gekozen uit {0, 1}. Er is precies ´e´en n×n nilpotent Jordanblok. Voorbeeld 1.3.30 Voor n = 4 bestaan er dus precies acht nilpotente Jordanvormen, te weten         0

 

0 0

0

0 0

  , 0   0

1 0

0

0 0

  , 0   0

0 0

0

1 0

  , 0   0

0 0

0 0

, 1  0 

38

HOOFDSTUK 1. CANONIEKE VORMEN 

0

 

0 0

  1 0

0

 

1 0

, 1   0  

0 0

0

, 1   0  

1 0

  1 0

0

, 0   0  

1 0

 1 0

. 1  0 

De matrix rechtsonder is het 4 × 4 nilpotente Jordanblok N4 . Opmerking 1.3.31 Een nilpotente Jordanvorm S ∈ Kn×n beeldt iedere standaardbasisvector ek af op 0 of op ek−1 . In het bijzonder is Se1 = 0. Hieruit volgt direct dat S n = 0, en dus dat S inderdaad nilpotent is. Het grootste gehele getal p waarvoor S p 6= 0, de nilpotentieindex van S, is gelijk aan het grootste aantal naast elkaar staande enen op posities (i, i + 1). Het nilpotente Jordanblok is dus de enige nilpotente Jordanvorm met nilpotentie-index n − 1. Lemma 1.3.32 Voor het nilpotente Jordanblok Nt ∈ Kt×t geldt dat ker(Ntj ) = span{e1 , . . . , ej }

(1.88)

voor alle j ∈ {1, . . . , t}, en ker(Ntj ) = Kt voor alle j ≥ t. Bewijs. De matrix Nt beeldt de standaardbasisvectoren van Kt als volgt op elkaar af, N

N

N

N

t t t t et −→ et−1 −→ . . . −→ e1 −→ 0.

(1.89)

Dus Ntj beeldt ek af op 0 als k ≤ j, en op ek−j als k > j.



Voorbeeld 1.3.33 Bovenstaand lemma wordt ge¨ıllustreerd door      0

 N4 = 

1 0

0

1 0

, N42 =  1  0 



0 1 0 0 0 1   , N43 =  0 0  0





0 0 1 0 0 0 0   , N44 =  0 0  0



0 0 0 0 0 0  0 0  0

en hogere machten van N4 zijn uiteraard ook gelijk aan nul. Iedere nilpotente Jordanvorm is als volgt opgebouwd uit nilpotente Jordanblokken. Lemma 1.3.34 Elke nilpotente Jordanvorm S ∈ Kn×n heeft een blokpartitionering als 

Nt1

  0 S= .  .. 0

0 Nt2 .. . ...

... .. . .. . 0

0 .. .



   0 

(1.90)

Nt p

met nilpotente Jordanblokken Nt1 , . . . , Ntp op de diagonaal, en nullen buiten deze blokken. Bewijs. Laat i1 < · · · < ip = n de indices zijn van de rijen in S die gelijk aan nul zijn. Laat i0 = 0 en definieer tj = ij − ij−1 voor alle j ∈ {1, . . . , p}. Dan is S van de vorm (1.90).  Opmerking 1.3.35 De blokpartitionering van S ontstaat derhalve door onder iedere rij nullen een horizontale streep te zetten, en links van iedere kolom nullen een verticale streep.

1.3. DE JORDANNORMAALVORM VAN EEN LINEAIRE TRANSFORMATIE

39

Voorbeeld 1.3.36 We illustreren Lemma 1.3.34 middels het blokpartitioneren van vier van de matrices uit Voorbeeld 1.3.30         0

1

0

0

0

0

0

0

0

0

0

0

0

1

0

0

 0 0 0 0   0 0 1 0   0 0 1 0   0 0 0 0   0 0 0 0  en  0 0 0 0  en  0 0 0 1  en  0 0 0 1  . 0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

met respectievelijke diagonaalblokken N2 , N1 , N1 en N1 , N2 , N1 en N1 , N3 en N2 , N2 . We introduceren nu eerst wat nieuwe terminologie, die resultaten compacter helpt verwoorden. Partities en de partitiefunctie spelen een grote rol binnen de wiskunde. Definitie 1.3.37 (Partitie(-functie)) Laat n ∈ N. Een partitie τ van n ∈ N, notatie τ ` n, is een tupel τ = [t1 , . . . , tk ] van getallen t1 , . . . , tk ∈ N zo, dat n = t1 + · · · + tk met t1 ≥ · · · ≥ tk .

(1.91)

De getallen t1 , . . . , tk heten de delen van n, en k ≤ n is de lengte van de partitie. De functie p : N → N die aan n het aantal partities p(n) van n toevoegt heet de partitiefunctie. Voorbeeld 1.3.38 De volgende tupels zijn alle verschillende partities van 5, [5], [4, 1], [3, 2], [3, 1, 1], [2, 2, 1], [2, 1, 1, 1], [1, 1, 1, 1, 1], en dus is p(5) = 7. Partities kunnen inzichtelijk worden gevisualiseerd met behulp van Young tableaus. Definitie 1.3.39 (Young tableau) Het Young tableau van een partitie τ = [τ1 , . . . , τp ] ` n is een afbeelding bestaande uit n vierkanten van gelijke grootte. Deze zijn verdeeld over p aansluitende rijen, met τj aansluitende vierkanten links uitgelijnd naast elkaar in rij j.

Figuur 2.2 Young tableaus van de zeven partities van n = 5. Sommige paren van Young tableaus zijn elkaars gespiegelde in de hoofddiagonaal. Definitie 1.3.40 (Geconjugeerde partitie) Laat τ = [τ1 , . . . , τp ] ` n ∈ N. Voor iedere j ∈ {1, . . . , n}, schrijf τj∗ voor het aantal delen van τ dat groter dan of gelijk is aan j. De positieve getallen τ1∗ , . . . , τq∗ vormen de geconjugeerde partitie τ ∗ = [τ1∗ , . . . , τq∗ ] ` n van τ . Voorbeeld 1.3.41 Beschouw de partitie τ = [2, 2, 1] ` 5. Alledrie de delen zijn groter dan of gelijk aan 1, dus τ1∗ = 3. Alleen het eerste en tweede deel zijn groter dan of gelijk aan 2 dus τ2∗ = 2. Er zijn geen delen groter dan twee. Dus τ ∗ = [3, 2] is de geconjugeerde partitie van τ .

40

HOOFDSTUK 1. CANONIEKE VORMEN

Eenvoudig gesteld telt τ ∗ het aantal vierkanten per kolom in het Young diagram van τ . Als gevolg hiervan is het Young diagram van τ ∗ de gespiegelde van het Young diagram van τ . τ = [2, 2, 1]

conjugatie

τ ∗ = [3, 2]

Figuur 2.3 Young tableaus van geconjugeerde partities zijn elkaars gespiegelde. We gaan nu in op de vraag wat partities te maken hebben met nilpotente Jordanvormen. Definitie 1.3.42 (Type nilpotente Jordanvorm) De aflopend gesorteerde groottes van de Jordanblokken op de diagonaal van de volgens (1.90) gepartitioneerde nilpotente Jordanvorm S ∈ Kn×n vormen een partitie τ ` n. Deze partitie heet het type van S. Voorbeeld 1.3.43 De acht matrices in Voorbeeld 1.3.30 hebben de volgende types, [1, 1, 1, 1] [2, 1, 1] [2, 1, 1] [2, 1, 1] [3, 1] [2, 2] [3, 1] [4] waarbij de types op de overeenkomstige positie staan genoteerd als de matrices. Opmerking 1.3.44 Het type τ ` n van het n × n Jordanblok Nn is de partitie τ = [n]. Lemma 1.3.45 Zij S ∈ Kn×n een nilpotente Jordanvorm van type τ met geconjugeerde τ ∗ . Dan is τ`∗ het aantal nilpotente Jordanblokken van S van afmetingen ` × ` of groter. Stelling 1.3.46 Laat S ∈ Kn×n een nilpotente Jordanvorm zijn van type τ ` n. Dan geldt dat dim(ker(S ` )) = τ1∗ + · · · + τ`∗ (1.92) voor alle ` ≤ q, waarbij τ ∗ = [τ1∗ , . . . , τq∗ ] de geconjugeerde van τ is. Bewijs. Laat ` ∈ {1, . . . , q} gegeven zijn. Wegens de blokvorm van S in (1.90) geldt dat S ` v = 0 als en alleen als Nt`j vj = 0 voor alle j ∈ {1, . . . , p}, waarbij vj bestaat uit de entries van v die in dezelfde rijen staan als Ntj . In het bijzonder geldt dus dat dim(ker(S ` )) = dim(ker(Nt`1 )) + · · · + dim(ker(Nt`p )).

(1.93)

Lemma 1.3.32 geeft dat dim(ker(Nt`j )) gelijk is aan het minimum van tj en `. Dus, dim(ker(Nt`j )) is precies dan 1 groter dan dim(ker(Nt`−1 )) als het blok Ntj afmetingen ` × ` of groter heeft, j ` oftewel, als tj ≥ `. Dus dim(ker(S )) − dim(ker(S `−1 )) is gelijk aan het aantal nilpotente Jordanblokken Ntj van S met tj ≥ `, en dus volgens Lemma 1.3.45 gelijk aan τ` . Een eenvoudig inductieargument bewijst nu de bewering.  Voorbeeld 1.3.47 Bekijk de machten van de nilpotente Jordanvorm S van type τ = [3, 2],     0

  S= 

1 0

0

1 0

    2 , S =    0 1 0

0 1 0 0 0

   , S 3 = 0, 0 0  0

dan is τ ∗ = [2, 2, 1] en zien we dat dim(ker(S)) = τ1∗ = 2, dim(ker(S 2 )) = τ1∗ + τ2∗ = 4, en dim(ker(S 3 )) = τ1∗ + τ2∗ + τ3∗ = 5. Dit illustreert de uitspraak van Stelling 1.3.46.

1.3. DE JORDANNORMAALVORM VAN EEN LINEAIRE TRANSFORMATIE e3

S

e2

S

e1

41

S 0

ker(S 1 ) = span{e1 , e4 } ker(S 2 ) = span{e1 , e4 , e2 , e5 }

e5

S

e4

0

ker(S 3 ) = span{e1 , e4 , e2 , e5 , e3 }

S

Figuur 2.4 Illustratie horend bij Voorbeeld 1.3.47. Reden dat we het concept type van een Jordanblok introduceren, is de volgende stelling. Stelling 1.3.48 Gegeven nilpotente Jordanvormen S, T ∈ Kn×n met types σ ` n en τ ` n. Dan zijn S en T gelijkvormig als en alleen als σ = τ . Bewijs. Veronderstel dat σ 6= τ . Dan is ook σ ∗ 6= τ ∗ en bestaat er dus een ` ∈ N zo, dat dim(ker(S ` )) = σ1∗ + · · · + σ`∗ 6= τ ∗ + · · · + τ`∗ = dim(ker(T ` )).

(1.94)

Hieruit volgt dat S ` en T ` niet gelijkvormig zijn, en dus S en T ook niet. Immers, als B = X −1 AX dan is B ` = (X −1 AX)` = X −1 A` X, en als b1 , . . . , bq een basis is voor ker(B ` ) dan is Xb1 , . . . , Xbq een basis voor ker(A` ). Omgekeerd, veronderstel dat σ = τ . Dan bestaat er een permutatie Π ∈ GLn (K) zodanig dat B = Π−1 AΠ. Voor details, zie Lemma 1.3.49.  Lemma 1.3.49 (Blokpermutatie) Zij X ∈ Kn×n en k + ` = n. Blokpartitioneer X als   A B X= C D waarbij A ∈ Kk×k en D ∈ K`×` . Dan geldt dat     D C 0 I` −1 Π XΠ = waarbij Π = . B A Ik 0 Bewijs. De rechtsvermenigvuldiging met Π zet kolommen ` + 1, . . . , n voor de kolommen 1, . . . , k, en de linksvermenigvuldiging met Π−1 doet hetzelfde met de rijen.  Opmerking 1.3.50 Iedere permutatiematrix Π is unitair, en dus is Π−1 = Π> . We laten nu zien dat iedere nilpotente matrix gelijkvormig is met een nilpotente Jordanvorm.

1.3.4

Gelijkvormigheidstransformaties van stricte bovendriehoeksmatrices

Ieder van de bovendriehoeksmatrices T1 , . . . , Tp in (1.86) heeft de eigenschap dat de entries op de diagonaal allemaal hetzelfde zijn. Deze matrices zijn dus van de vorm T` = λ` I` + M`

(1.95)

voor zekere λ` ∈ K, en waarbij M` een stricte bovendriehoeksmatrix is. Definitie 1.3.51 (Stricte bovendriehoeksmatrix) Een bovendriehoeksmatrix (rij ) = R ∈ Kn×n heet strict als rjj = 0 voor alle j ∈ {1, . . . , n}.

42

HOOFDSTUK 1. CANONIEKE VORMEN

Merk op dat alle eigenwaarden van een stricte bovendriehoeksmatrix gelijk zijn aan nul. Opmerking 1.3.52 Als M ∈ Kn×n strict bovendriehoeks is en T = λI + M voor zekere λ ∈ K, dan is voor iedere X ∈ GLn (K), X −1 T X = λI + X −1 M X.

(1.96)

Als ook X −1 T X bovendriehoeks is, zijn al zijn diagonaalentries gelijk aan λ. Immers, de eigenwaarden van T en X −1 T X zijn gelijk. In dat geval is X −1 M X strict bovendriehoeks. Om gelijkvormigheidstransformaties van matrices T = λI + M met M strict bovendriehoeks te begrijpen volstaat het dus om die van M te begrijpen. Stelling 1.3.53 (Jordan) Laat M ∈ Kn×n strict bovendriehoeks zijn. Dan bestaat er een X ∈ GLn (K) zo, dat S = X −1 M X een nilpotente Jordanvorm is. Bewijs. Het volgende eenvoudige voorbeeld bewijst deze stelling voor n = 2, en doet als zodanig dienst als inductiebasis. Voorbeeld 1.3.54 Laat M ∈ K2×2 strict bovendriehoeks zijn. Dan is M van de vorm   0 k met k ∈ K. M= 0 0 Als k = 0 dan is M een nilpotente Jordanvorm van type τ = [1, 1]. Als k 6= 0 dan is       1 1 −1 1 0 0 k 1 0 0 1 =S = D2 ( ) M D 2 ( ) = 0 k1 0 0 0 k 0 0 k k

(1.97)

en is S een nilpotente Jordanvorm van type τ = [2], oftewel, het 2 × 2 nilpotente Jordanblok. ˆ ∈ K(n−1)×(n−1) strict bovendriehoeks is, er een Inductiehypothese. Veronderstel dat als M −1 ˆ Y = Sˆ een nilpotente Jordanvorm is. Y ∈ GLn−1 (K) bestaat zo, dat Y M Eerste deel Inductiestap. Laat M ∈ Kn×n strict bovendriehoeks zijn. Dan kunnen we M blok-partitioneren als   ˆ b M ˆ ∈ K(n−1)×(n−1) strict bovendriehoeks en b ∈ Kn−1 . M= , met M 0 0 Volgens de inductiehypothese bestaat er een Y ∈ GLn−1 (K) zo, dat 

Y 0

0 1

−1

 M

Y 0

0 1



 =

S c 0 0



waarbij c = Y −1 b,

(1.98)

ˆ Y een nilpotente Jordanvorm is van M ˆ . De taak die resteert is om de matrix en S = Y −1 M in (1.98), die op de laatste kolom na in de gewenste vorm staat, nog verder te transformeren. Tweede deel Inductiestap. We laten nu zien hoe we de entry ck van c naar nul kunnen transformeren als er op positie (k, k + 1) in Sˆ een 1 staat.

1.3. DE JORDANNORMAALVORM VAN EEN LINEAIRE TRANSFORMATIE

43

Lemma 1.3.55 Veronderstel dat S = (sij ) een nilpotente Jordanvorm is met sk,k+1 = 1. Dan geldt na de transformatie  n    (−ck ) S cˆ S c Ek+1,n −→ (1.99) 0 0 0 0 dat cˆj = cj voor alle j 6= k en cˆk = 0. n Bewijs. De linksvermenigvuldiging met Ek+1,n (−ck ) telt een veelvoud van de n-de rij op bij de (k + 1)-ste rij. Echter, de n-de rij is nul en dit verandert dus niets aan de matrix. De n rechtsvermenigvuldiging met Ek+1,n (−ck )−1 trekt ck maal de (k + 1)-ste kolom af van de n-de kolom. Maar die (k + 1)-ste kolom is gelijk aan ek . Dit bewijst de bewering. 

Lemma 1.3.55 wordt duidelijk ge¨ıllustreerd door het volgende voorbeeld. Voorbeeld 1.3.56 Wegens de enen op posities (1, 2) en (3, 4) kunnen de eerste en derde entry van de laatste kolom met behulp van Lemma 1.3.55 naar nul worden getransformeerd,       0

   

1 0

0 0 0

0 0 1 0

1 2 3 4 0

0

 E 5 (−1)   25   −→   

1 0

0 0 0

0 0 1 0

0 2 3 4 0

0

 E 5 (−3)   45   −→   

0 0 0

1 0

0 0 1 0

0 2 0 4 0

  . 

Omdat ieder van beide transformaties slechts ´e´en entry verandert, kunnen ze ook in omgekeerde volgorde worden toegepast met hetzelfde resultaat, er geldt namelijk 5 5 5 5 X = E25 (−1)E45 (−3) = E45 (−3)E25 (−1)

en hiermee is    X= 

1

0 1

0 0 1



0 0 0 −1   0 0  1 −3  1

   

en X −1 = 

1

0 1

0 0 1

0 0 0 1

0 1 0 3 1

    

oftewel, de inverse kan weer eenvoudig worden bepaald. Derde deel Inductiestap. De uitgangssituatie is de matrix na herhaald toepassen van Lemma 1.3.55, zodat als de i-de entry van cˆ ongelijk is aan nul, de i-de rij van S gelijk is aan nul. Het volgende lemma ligt aan de basis van de resterende transformaties. Opmerking 1.3.57 Wegens Lemma 1.3.49 nemen we zonder verlies van algemeenheid aan, dat S in de vorm (1.90) staat met oplopende blokgroottes t1 ≤ · · · ≤ tp . Lemma 1.3.58 Zij S ∈ Kn×n een nilpotente Jordanvorm met nilpotente Jordanblokken in oplopende groottes van linksboven naar rechtsonder. Laat   S d , 0 0

44

HOOFDSTUK 1. CANONIEKE VORMEN

en neem aan dat elke entry van d = (dj ) die niet nul is, staat naast een rij van S die wel nul is. Laat ` het grootste gehele getal zijn met d` 6= 0. Veronderstel dat d` = 1 en dat dk 6= 0 met k 6= `. Dan is    n  n (dk ) Ek−q+1,n−q (dk ) S d Ek,n−1 S dˆ , −→ · · · −→ 0 0 0 0 waarbij q de grootte is van het nilpotente Jordanblok waartoe de entry (k, k) van S behoort, en geldt dat dˆj = dj voor alle j 6= k en dˆk = 0. n Bewijs. Toepassing van Ek,n−1 (dk ) maakt de (k, n)-entry gelijk aan nul, en de entry op n positie (k − 1, n − 1) gelijk aan dk als kolom k − 1 niet nul is. In dat geval zal Ek−1,n−2 (dk ) de entry op positie (k − 1, n − 1) nul maken, maar de entry op positie (k − 2, n − 2) gelijk aan dk als kolom k − 2 niet nul is. Omdat het aantal rijen van het nilpotente Jordanblok waar entry (`, `) toe behoort groter dan of gelijk is aan het aantal kolommen van het blok waar n (dk ) de entry dk entry (k, k) toe behoort, zal in stap q met transformatiematrix Ek−q+1,n−q op positie (k − q + 1, n − q) nul worden zonder verdere veranderingen. 

Opmerking 1.3.59 De aanname dat d` = 1 is zonder verlies van algemeenheid. Als d` 6= 0 kan dit immers bewerkstelligd worden middels de transformatie Dn (d−1 ` ). Lemma 1.3.58 laat zich goed uitleggen middels een voorbeeld. Hierin zijn de entries in de laatste kolom in beide nul-rijen ongelijk aan nul, oftewel, op posities (2, 6) en (5, 6). Voorbeeld 1.3.60 In termen van Lemma 1.3.58 is hier ` = 5 en k = 2 en q = 2, en dus       0

     

1 0

0 0 0

0 0 0 0 1 0 0 1 0

0 2 0 0 1 0

0

   E 6 (2)   25   −→     

1 0

0 0 0

0 2 0 0 1 0 0 1 0

0 0 0 0 1 0

0

   E 6 (2)   14   −→     

1 0

0 0 0

0 0 0 0 0 0   1 0 0  . 0 1 0  0 1  0

6 (2) maakt weliswaar de (2, 5) entry gelijk aan nul, maar introduceert een Toepassing van E25 6 (2) maakt deze entry 2 op positie (1, 4) omdat de tweede kolom niet nul is. Toepassing van E14 weer nul. Echter, omdat de eerste kolom nul is, gebeurt er verder niets en is het doel bereikt.

Opmerking 1.3.61 Het product X van de transformatiematrices n n n X = Ek` (h1 ) · Ek−1,`−1 (h2 ) · . . . · Ek−t,`−t (ht )

kan, net als in Opmerking 1.3.18, direct worden opgeschreven. Lemma 1.3.58 kan worden toegepast om op c` na iedere entry ongelijk aan nul in de laatste kolom, liggende in een nulrij, naar nul te transformeren. De entry c` = 1 blijft als enige ongelijk aan nul over in de laatste kolom. Tot slot kan een blok-permutatie worden toegepast zo, dat deze 1 aansluit bij het blok waar hij rechts naast ligt.

1.3. DE JORDANNORMAALVORM VAN EEN LINEAIRE TRANSFORMATIE

45

Voorbeeld 1.3.62 Stel dat de laatste kolom op ´e´en entry na naar nul is getransformeerd, dan sluit een blokpermutatie deze entry aan op het Jordanblok waar hij bij hoort, zoals bijvoorbeeld            

0 1 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0

0 0 1 0 0 0

0 0 0 1 0 0

0 1 0 0 0 0

     Π   −→     

0 0 0 0 0 0

1 0 0 0 0 0

0 1 0 0 0 0

0 0 0 0 0 0

0 0 0 1 0 0

0 0 0 0 1 0

       met Π =     

0 0 0 1 0 0

0 0 0 0 1 0

1 0 0 0 0 0

0 1 0 0 0 0

0 0 1 0 0 0

0 0 0 0 0 1

   .  

Er resulteert dus een nilpotente Jordanvorm van type τ = [3, 3]. Hiermee is het inductiebewijs van Stelling 1.3.53 voltooid.



We geven nu ook een volledig voorbeeld waarin alle stappen van het bewijs van Stelling 1.3.53 achter elkaar worden uitgevoerd op een expliciet gegeven 4 × 4 matrix. Voorbeeld 1.3.63 We bepalen inductief een nilpotente Jordanvorm van de gegeven matrix M . De eerste drie stappen liggen voor de hand,         0

 M =

0 2 1 3 1 0 0 2  D24 ( 2 )  −→  0 1  0

1 0

1 0 0

3 0 4 (−1) 4  E23  −→  1  0

1 0 0 0 0

3 0 4 (−3) 5  E24  −→  1  0

1 0 0 0 0

0 5  . 1  0

De eerste stap brengt het 2 × 2 linksbovenblok in Jordanvorm, de tweede stap het 3 × 3 linksbovenblok met Lemma 1.3.55, dat in de derde stap gebruikt wordt om entry (1, 3) nul te maken. Omdat het grootste Jordanblok van de 3 × 3 matrix niet rechtsonder staat, permuteren we beide blokken,       0

1 0

 

0 0 0

0 0 5  Π  −→  1  0

0 0

0 1 0

1 0  5  0

0

1

0

 0 0 1 met Π =  1 0 0

  1

Vervolgens passen we Lemma 1.3.58 toe, waarbij ` = 3, k = 1 en q = 1, maar niet voordat we de entry op positie (3, 4) middels een diagonaalschaling naar 1 hebben getransformeerd,      1  0

 

0 0

0 1 0 0 1 1 0  D44 ( 5 )  0 −→  0 5  0

0 1 0

5

0

1

4 ( ) 0  E13 5  −→   1 0

0 0

0 0 1 0  , 0 1  0

en dit is derhalve een nilpotente Jordanvorm van M , met type τ = [3, 1]. Om de bijbehorende transformatiematrix X uit te rekenen, berekenen we 1 1 4 4 4 1 (−1) · E24 (−3) · Π · D44 ( ) · E13 ( ). X = D24 ( ) · E23 2 5 5 De eerste drie termen zijn eenvoudig samen te nemen, net als de laatste drie, wat resulteert in      0 1 0 0 − 21 − 32   0 0 0 1 0  1 0 0 0 1 0 0

1

0

 0 X= 0

1 2

0

Deze matrix X is dus zo, dat

X −1 M X

0 1

1 5

0

0 0 10 0 0 1  −5 0 4 −3  0  =  . 0  10 10 0 2 0 1 0 0 0 2 5

een nilpotente Jordanvorm is.

46

HOOFDSTUK 1. CANONIEKE VORMEN

Opmerking 1.3.64 Als X −1 M X een nilpotente Jordanvorm is, is ook (λX)−1 M (λX) dat voor alle 0 6= λ ∈ K. Dus als K = Q dan kan een X met gehele entries worden gekozen.

1.3.5

Jordanvormen en de Jordannormaalvorm van een matrix

We koppelen nu de nilpotente Jordanvormen via Stelling 1.3.25 aan willekeurige matrices. Definitie 1.3.65 (Jordanvorm) Een matrix J ∈ Kn×n heet een Jordanvorm als 

J1

0

  J = 

0 .. . 0

J2 .. . ...

... .. . .. . 0

0 ..  . 



 waarbij Jt ∈ Knt ×nt = λt It + St 0 

(1.100)

Jp

voor iedere t ∈ {1, . . . , p} en iedere matrix St is een nilpotente Jordanvorm. Stelling 1.3.66 (Jordan) Zij K algebra¨ısch afgesloten. Iedere matrix A ∈ Kn×n is gelijkvormig met een Jordanvorm. Bewijs. Volgens Stelling 1.3.25 is A gelijkvormig met een blok-diagonaalmatrix met diagonaalblokken gelijk aan Tt = λt I + Mt met Mt strict bovendriehoeks. Volgens Stelling 1.3.48 bestaat er een inverteerbare Xt zo, dat Xt−1 Mt Xt = St een nilpotente Jordanvorm is, en dus 

X1

0

   

0 .. . 0

X2 .. . ...

... .. . .. . 0

−1 

T1

0

   

0 .. . 0

T2 .. . ...

0 ..  . 

 0  Xp

... .. . .. . 0

X1 0 ..  .  0  . 0  .. Tp 0



0 X2 .. . ...

... .. . .. . 0

 

J1

0

  =   0

0 .. . 0

J2 .. .

0 ..  .  Xp

...

... .. . .. . 0

waarbij Jt = λt It + St .

0 ..  . 

 ,

0  Jp



Definitie 1.3.67 (Jordannormaalvorm) Zij A ∈ Kn×n . Een Jordanvorm J die gelijkvormig is met A heet een Jordannormaalvorm van A.

1.4

Opgaven

Opgave 1.1: Aanvulling tot een inverteerbare of zelfs unitaire 2 × 2 matrix (a) Bepaal voor ieder van de volgende vectoren uit C2 een matrix X ∈ GL2 (C) met een niet-triviaal veelvoud van die vector als eerste kolom. Geef daarnaast ook X −1 .           1 0 3 2 1 u= , v= , w= , x= , y= . −4 −4 i 1 2 (b) Bepaal voor ieder van die vectoren een matrix U ∈ C3×3 met orthonormale kolommen waarvan de eerste een niet-triviaal veelvoud is van de gegeven vector. Geef ook U −1 .

1.4. OPGAVEN

47

Opgave 1.2: Aanvulling tot een inverteerbare 3 × 3 matrix (a) Bepaal voor ieder van de volgende vectoren uit C3 een matrix X ∈ GL3 (C) met een niet-triviaal veelvoud van die vector als eerste kolom. Geef daarnaast ook X −1 .           1 0 0 2 3 u =  1  , v =  2  , w =  0  , x =  −4  y =  2  . 1 4 i 6 1 Opgave 1.3: 2 × 2 Jacobi-triangulatie en Schur-triangulatie (a) Bepaal voor ieder van de volgende matrices Aj ∈ C2×2 een matrix Xj ∈ GL2 (C) zo, dat Xj−1 Aj Xj = Rj een bovendriehoeksmatrix is.  A1 =

1 0 1 1



 , A2 =

1 0 2 1



 , A3 =

3 2 −2 −1



 , A4 =

1 1 −1 −1

 .

(b) Bepaal voor iedere Aj ook een unitaire Uj zo, dat Uj−1 Aj Uj = Tj bovendriehoeks is. (c) Verifieer dat kTj k2F = kAj k2F , met kXk2F de som van de kwadraten van de entries van X. Opgave 1.4: 3 × 3 Jacobi-triangulatie en Schur-triangulatie (a) Bepaal voor ieder van de volgende matrices Aj ∈ C3×3 een matrix Xj ∈ GL3 (C) zo, dat Xj−1 Aj Xj = Rj een bovendriehoeksmatrix is.      0 4 2 1 −1 −3 0 0 0 3 3  , A3 =  −1 0 1  . 3 1  , A2 =  1 A1 =  1 1 2 0 0 0 2 5 −1 1 

(b) Bepaal voor iedere Aj ook een unitaire Uj zo, dat Uj−1 Aj Uj = Tj bovendriehoeks is. (c) Verifieer dat kTj k2F = kAj k2F , met kXk2F de som van de kwadraten van de entries van X. Opgave 1.5: Een 4 × 4 Jacobi-triangulatie Bepaal voor de matrix 

2 1 0  −1 0 0 A=  2 2 3 −1 −1 −1

 0 0   1  1

een matrix X ∈ GL4 (C) zo, dat X −1 AX = R bovendriehoeks is. Opgave 1.6: Unitaire matrices Laat U, V unitair zijn. Bewijs dat de matrices    1 U 0 U U V, , en √ −U 0 V 2 ook unitair zijn.

U U



48

HOOFDSTUK 1. CANONIEKE VORMEN

Opgave 1.7: Een spectraalstelling voor scheefsymmetrische matrices Formuleer en bewijs middels de Schurdecompositie een spectraalstelling voor scheefsymmetrische matrices. Herinner je dat A ∈ Cn×n scheefsymmetrisch is als A∗ = −A. Opgave 1.8: Schur-decompositie van een rang-1 matrix Laat e1 de eerste standaardbasisvector van Cn zijn. (a) Laat zien dat er voor iedere 0 6= u ∈ Cn een unitaire U bestaat met U ∗ u = kuke1 . Laat nu u, v ∈ Cn ongelijk aan nul zijn en bekijk de rang-1 matrix A = uv ∗ . (b) Bepaal met behulp van U een Schurdecompositie van A. Opgave 1.9: Gelijkvormigheid versus unitaire equivalentie Matrices A, B ∈ Cn×n zijn gelijkvormig als er een inverteerbare X is waarvoor B = X −1 AX, en unitair equivalent als er een unitaire X is waarvoor B = X ∗ AX. (a) Ga na dat beide begrippen een equivalentierelatie defini¨eren op Cn×n . (b) Laat zien dat unitair equivalente matrices gelijkvormig zijn. (c) Geef een voobeeld van twee gelijkvormige matrices die niet unitair equivalent zijn. (d) Laat zien dat gelijkvormige matrices dezelfde eigenwaarden hebben. Schrijf nu SA , SB voor de respectievelijke verzamelingen van Schurvormen van A, B ∈ Cn×n . (e) Als A en B unitair equivalent zijn, geldt dan dat SA = SB ? (f ) Als A en B gelijkvormig zijn, geldt dan dat SA = SB ? (g) Als SA ∩ SB 6= ∅, zijn A en B dan unitair equivalent? n (h) en Π . Voor het schrijfHerinner je de definitie van de elementaire matrices Dkn (h), Ek` k` gemak zullen we hier de superscripts n steeds weglaten.

Opgave 1.10: Elementaire gelijkvormigheidstransformaties met Dk (h) en Πk` Bereken de volgende producten zonder de elementaire matrices uit te schrijven, en dus door het effect van deze matrices te interpreteren als elementaire rij- en kolomoperaties. 1 D2 ( )−1 2



1 0

2 1





 1 1 1 −1 1 −1  0 D2 ( ) en D3 ( ) D2 ( ) 2 2 2 0

2 1 0

 0 1 1 2  D2 ( )D3 ( ). 2 2 1

(1.101)

  3 1 −1  6  Π13 en Π−1 4 Π 23 12 7 7

2 5 8

 3 6  Π12 Π23 . 7

(1.102)

1  4 Π−1 13 7

2 5 8

Probeer in ´e´en keer de correcte productmatrix op te schrijven, dus zonder tussenresultaten.

1.4. OPGAVEN

49

Opgave 1.11: Elementaire gelijkvormigheidstransformaties met Ek` (h) Bereken de volgende producten zonder de elementaire matrices uit te schrijven, en dus door het effect van deze matrices te interpreteren als elementaire rij- en kolomoperaties. 

2 E12 (1)−1  0 0 

1  0 E34 (π)−1   0 0

1 2 0 0

  1 2 1  E12 (1) en E23 (−1)−1  0 8 0

1 4 0

  1  1   E34 (π) en E24 (−1)−1   1  1

1 1 1 0

1 0 0 0

1 2 0 0

1 4 0

 1 1  E23 (−1). 8

(1.103)

1 1 1 0

 1 1   E (−1). 1  24 1

(1.104)

Probeer in ´e´en keer de correcte productmatrix op te schrijven, dus zonder tussenresultaten. Opgave 1.12: Diagonalisatie middels gelijkvormigheidstransformaties met Ek` (h) Diagonaliseer ieder van de volgende matrices middels ten hoogste drie gelijkvormigheidstransformaties met een elementaire matrix van het type Ek` (h). " R1 =

1 0 0

1 0 0

0 6 3

#

" , R2 =

2 0 0

1 1 0

0 6 4

#

" R3 =

1 2 −3 0 −1 1 0 0 −2

# .

Geef aan welke matrices Ek` (h) achteraanvolgens worden toegepast, en geef hun product. Opgave 1.13: Transformeren naar een deels gegeven vorm Geef aan welke elementaire gelijkvormigheidstransformaties op Ri moeten worden toegepast om Ri naar de gegeven vorm Ti te transformeren. Bereken ook hun product. " # " # " # " # R1 =

1 0 0

1 2 0

1 1 3

−→

1 0 0



1  0 R3 =  0 0

∗ ∗ 3 ∗ 0 2 3 2 0 0

= T1

4 1 1 0



1 0 0

R2 = 

5 1 6   0 −→  7  0 2 0

1 2 0

1 1 3

−→

2 0 0

∗ ∗ 1 ∗ 0 3

= T2 .

∗ ∗ ∗ 1 ∗ ∗  = T3 . 0 2 ∗  0 0 2



De getalswaarden van de sterretjes zijn willekeurig (en hoeven niet aan elkaar gelijk te zijn). Opgave 1.14: Transformeren naar een gegeven vorm Geef aan welke elementaire gelijkvormigheidstransformaties op R moeten worden toegepast om R naar de gegeven vorm T te transformeren. 

0  0 R= 0 0

3 1 0 0

4 5 0 0





6 1 7   0 −→  0 8  1 0

1 1 0 0

0 0 0 0



0 0  = T. 1  0

50

HOOFDSTUK 1. CANONIEKE VORMEN

Opgave 1.15: Transformeren naar een gegeven Jordanvorm Geef aan welke elementaire gelijkvormigheidstransformaties op Ri moeten worden toegepast om Ri naar de gegeven vorm Tj te transformeren.         1 1 1 1 1 0 0 1 1 0 1 0 R1 =  0 1 0  −→  0 1 0  = T1 , R2 =  0 0 1  −→  0 0 1  = T2 . 0 0 1 0 0 1 0 0 0 0 0 0 



0 0  = T3 . 1  1





0 0  = T4 . 1  2



1 1  0 1 R3 =  0 0 0 0

0 1 1 0

1 1 0 3 2   0 1 1 −→  0 0 1 1  1 0 0 0



0 1 2 0

2 0 0 1 0   0 2 1 −→  0 0 2 1  2 0 0 0

2 0  0 2 R4 =  0 0 0 0





Opgave 1.16: Transformeren naar een Jordanvorm Geef aan welke elementaire gelijkvormigheidstransformaties op Ri moeten worden toegepast om Ri naar een Jordanvorm Ji te transformeren. Geef ook Ji .       1

1

0

0

0

2

1

0

0

0

0

1

0

0

0

 0 0 0 0 1   0 0 0 0 1   0 1 0 0 0        R1 =  0 0 1 1 3 , R2 =  0 0 0 1 0 , R3 =  0 0 0 1 0   0 0 0 1 2   0 0 0 0 1   0 0 0 0 0  0

0

0

0

1

   R4 =  

0

1 1 0 1 0 0 0 0 0 0

0 0 2 0 0

0 0 1 2 0

2 0 3 2 3

0

0

0



0



    , R5 =   

0

1 1 0 1 0 0 0 0 0 0

0 0 2 0 0

0 0 2 2 0

2 0 4 2 2

0

0

   . 

Opgave 1.17: Partities en hun geconjugeerden (a) Geef alle partities τ ` 6, waarbij geconjugeerden onder elkaar staan. (b) Teken ook hun Young tableaus. (c) Geef voor iedere τ ` 6 een nilpotente Jordanvorm S van type τ . Opgave 1.18: Gelijkvormigheid van nilpotente Jordanvormen (a) Gegeven de twee nilpotente Jordanvormen   0

   S1 =   

0

1 0



       en S2 =  0 1    0 1  0

0

1 0

 1 0

   . 0  0 1  0

0

0

1.4. OPGAVEN

51

Bewijs dat S1 en S2 gelijkvormig zijn door een X ∈ GL6 (C) te geven waarvoor X −1 S1 X = S2 . (b) Gegeven de twee nilpotente Jordanvormen  



0

   S1 =   

0

1 0

       en S2 =  0 1    0 1 

0



1 0 0

1 0

   .  0 1 

0

0

Bewijs vanuit de definitie van gelijkvormigheid dat S1 en S2 niet gelijkvormig zijn. Opgave 1.19 Gegeven zijn de matrices       0 2 1 0 2 1 0 0 1 0 0  , M2 =  0 2  , M3 =  0 2 . M1 =  0 0 0 (a) Bepaal een Xj ∈ GL3 (C) zo, dat Xj−1 Mj Xj = Sj een nilpotente Jordanvorm is. Opgave 1.20 Een matrix N ∈ Kn×n heet nilpotent als N p voor zekere gehele p ≥ 1. Bewijs dat A ∈ Kn×n met K algebra¨ısch afgesloten, nilpotent is als en alleen als alle eigenwaarden van A nul zijn. Opgave 1.21 Gegeven zijn de nilpotente matrices  −2   0 4 2  −1 −2 4 , A2 = −1 0 1  , A3 =  A1 = −1 −1 2 1 2 0 −1 



3 1 1 1

 2 −1 2 −1  . 1 0  1 0

(a) Bepaal een Xj ∈ GL3 (C) zo, dat Xj−1 Aj Xj = Mj een stricte bovendriehoeksmatrix is. (b) Bepaal een Yj ∈ GL3 (C) zo, dat Yj−1 Mj Yj = Sj een nilpotente Jordanvorm is. Opgave 1.22: Hoeveelheid nilpotente Jordanvormen van een gegeven type Bewijs dat het aantal nilpotente Jordanvormen van type τ = [τ1 , . . . , τp ] ` n gelijk is aan p! ∗ )! , (τ1∗ − τ2∗ )! · . . . · (τq∗ − τq+1 waarbij τ ∗ = [τ1∗ , . . . , τq∗ ] de geconjugeerde partitie van τ is, en τq+1 = 0. Hint: Zij S ∈ Kn×n een nilpotente Jordanvorm is van type τ = [τ1 , . . . , τp ] ` n. ∗ Bewijs dat τ`∗ − τ`−1 het aantal nilpotente Jordanblokken van S van afmetingen ` × ` is.

52

HOOFDSTUK 1. CANONIEKE VORMEN

Hoofdstuk 2

Dualiteit Dit hoofdstuk behandelt enkele concepten gerelateerd aan dualiteit. Dualteit is een begrip dat op zeer uiteenlopende deelgebieden van de wiskunde een rol speelt maar desondanks, of misschien wel juist daardoor, een niet goed gedefinieerde betekenis heeft. Gelukkig is de duale vectorruimte die we hier introduceren en bestuderen ondubbelzinnig en duidelijk gedefinieerd. We geven voorbeelden van (elementen uit) de duale vectorruimte, en beschrijven de duale basis van de duale vectorruimte en de relatie met het begrip co¨ordinaten. We behandelen het natuurlijk isomorfisme tussen een vectorruimte en de duale van zijn duale, en het Riesisomorfisme tussen de duale vectorruimte en de vectorruimte zelf. We defini¨eren de duale van een lineaire afbeelding, en de annihilator van een verzameling. Daar waar dwarsverbanden zijn zullen deze expliciet worden opgemerkt.

2.1

De duale vectorruimte

We brengen de volgende definitie in de herinnering. Definitie 2.1.1 (homK (V, W )) Gegeven twee vectorruimtes (V, K) en (W, K) over K noteren we de verzameling van alle lineaire afbeeldingen V → W met homK (V, W ). Lemma 2.1.2 De verzameling homK (V, W ) is een vectorruimte over K indien voorzien van de gebruikelijke optelling van L, K ∈ homK (V, W ) middels L+K :V →W :

v 7→ L(v) + K(v)

en de gebruikelijke vermenigvuldiging met scalairen k ∈ K middels k·L:V →W :

v 7→ k · L(v)

waarbij de + en de · in de rechterleden de vectorruimtebewerkingen op W zijn. Als speciaal geval van deze definitie en dit lemma bekijken we de keuze W = K. Definitie 2.1.3 (Duale vectorruimte (V ∗ , K) van (V, K)) De vectorruimte homK (V, K) noteren we met (V ∗ , K) of kortweg met V ∗ en noemen we de duale vectorruimte van V . Elementen uit de duale vectorruimte staan bekend onder een veelvoud van namen. Definitie 2.1.4 (Lineaire functionaal, covector, 1-vorm) Een element v ∗ ∈ V ∗ wordt ook wel een lineaire functionaal genoemd, of een covector, of een 1-vorm. 53

54

2.1.1

HOOFDSTUK 2. DUALITEIT

Voorbeelden en eerste ori¨ entatie

We geven hier voorbeelden van elementen uit de duale vectorruimte, en daarnaast ook wat resultaten die we verderop in meer algemeenheid zullen bewijzen. Eerst bekijken we (Kn )∗ . Voorbeeld 2.1.5 Beschouw de vectorruimte (Kn , K). Dan is voor iedere vast gekozen y ∈ Kn de afbeelding `y : Kn → K : x 7→ y > x (2.1) een lineaire functionaal op Kn en daarmee dus een element van (Kn )∗ . Opmerking 2.1.6 In Voorbeeld 2.1.5 is `y ∈ (Kn )∗ . De matrix y > is geen element van (Kn )∗ . Het is slechts de matrix van de lineaire afbeelding `y ten opzichte van de standaardbasis. Stelling 2.1.7 De afbeelding L : Kn → (Kn )∗ : y 7→ `y

(2.2)

met `y als in Voorbeeld 2.1.5 is een lineaire bijectie. Bewijs. De lineariteit is eenvoudig na te gaan. Omdat er voor iedere y 6= 0 een x ∈ Kn bestaat met y > x 6= 0, geldt dat `y = 0 ⇔ y = 0. Dus is ker(L) = {0}, en is L injectief. Ook is L surjectief, immers, laat ` : Kn → K gegeven zijn en laat z ∈ K1×n de matrix zijn van ` ten opzichte van de standaardbases van Kn en van K. Dan is dus `(x) = zx voor alle x ∈ K en dus geldt met y = z > dat ` = `y . Dus iedere ` ∈ (Kn )∗ is van de vorm `y voor zekere y. Gevolg 2.1.8 Er geldt dat (Kn )∗ ∼ = Kn . In het bijzonder is dim(Kn )∗ = n. Bewijs. De afbeelding L uit Stelling 2.1.7 is een lineaire bijectie en dus een isomorfisme.  Opmerking 2.1.9 Het voorgaande kan geherformuleerd worden als dat (Kn )∗ = {`y | y ∈ Kn },

(2.3)

waarbij er voor iedere ` ∈ (Kn )∗ precies ´e´en y ∈ Kn bestaat zo, dat ` = `y . Opmerking 2.1.10 Als K = R dan is `y (x) = y > x = hy, xi het standaardinproduct op Rn met een vast gekozen vector y ∈ Rn . Ook als K = C is `y (x) = y > x = y ∗ x = hy, xi het standaardinproduct op Cn met een vast gekozen vector, alleen nu is dat met y. Lineaire functionalen op een eindigdimensionale vectorruimte laten zich beschrijven middels de combinatie van Stelling 2.1.7 en de co¨ordinaatafbeelding horende bij een basis β van V . Opmerking 2.1.11 In het vervolg zullen we een willekeurig element uit V ∗ vaak aanduiden met v ∗ . Dit is slechts een notatie, in het bijzonder is de asterisk hier geen bewerking op v. Stelling 2.1.12 Gegeven een vectorruimte (V, K) met basis β = hv1 , . . . , vn i. Dan bestaat er voor iedere v ∗ ∈ V ∗ precies ´e´en y ∈ Kn zodat v ∗ = `y ◦ coβ

(2.4)

waarbij `y de afbeelding Kn → K : x 7→ y > x is. De toevoeging Kn → V ∗ : y 7→ v ∗ is lineair.

2.1. DE DUALE VECTORRUIMTE

55

Bewijs. Laat v ∗ : V → K gegeven zijn en beschouw daarnaast de co¨ordinaatafbeelding coβ : V → Kn . Zie nu het diagram in Figuur 3.1. v∗

V

n v ∗ ◦ co−1 β :K →K

=

∼ =

coβ

K `y

`y : Kn → K

Kn Figuur 3.1 Factorisatie van een element v ∗ ∈ V ∗ . n De samenstelling v ∗ ◦ co−1 β is een lineaire afbeelding K → K. Volgens Stelling 2.1.7 bestaat ∗ er een unieke y ∈ Kn zo, dat v ∗ ◦ co−1 β = `y , en dus zo, dat v = `y ◦ coβ . Volgens Stelling 2.1.7 is de toevoeging y 7→ `y lineair. Dus is de samenstelling y 7→ `y ◦ coβ = v ∗ dat ook. 

Gevolg 2.1.13 Er geldt dat V ∗ ∼ = Kn , en in het bijzonder dat V ∗ ∼ =V. We eindigen deze sectie met enkele explicietere voorbeelden van lineaire functionalen. Een bekend element uit de duale van de ruimte van vierkante matrices is het spoor. Voorbeeld 2.1.14 De lineaire afbeelding Sp : Kn×n → K :

A 7→ Sp(A)

(2.5)

waarbij Sp(A) staat voor het spoor van A, is een covector uit (Kn×n )∗ . Daarnaast is voor gegeven vast gekozen v, w ∈ Kn ook Kn×n → K :

A 7→ v > Aw

(2.6)

een lineaire functionaal op Kn×n en daarmee een element uit (Kn×n )∗ . Oneindigdimensionale vectorruimtes leveren doorgaans interessantere duale vectorruimtes. Voorbeeld 2.1.15 Beschouw de vectorruimte (C(I), R) van continue functies op het interval I = [a, b] met a, b ∈ R. Dan is de afbeelding Iab : C(I) → R :

Z

b

f 7→

f (x)dx,

(2.7)

a

Rb waar a de Riemann-integraal is, een lineaire functionaal op C(I), en dus is Iab ∈ C(I)∗ . Daarnaast is de functie-evaluatie ex : C(I) → R :

f 7→ f (x)

(2.8)

ook een element van C(I)∗ voor iedere vast gekozen x ∈ I. In het bijzonder is ook Tab : C(I) → R :

f 7→ (b − a)

f (a) + f (b) 2

een element van C(I)∗ , het is immers een lineaire combinatie van ea en eb uit (2.8).

(2.9)

56

HOOFDSTUK 2. DUALITEIT

De lineaire functionalen Iab en Tab uit vorig voorbeeld zijn als volgt aan elkaar gerelateerd. Opmerking 2.1.16 Definieer de zogeheten interpolatie-afbeelding π : C(I) → R[X]≤1 :

f 7→ π(f )

(2.10)

die aan f ∈ C(I) toevoegt het unieke lineaire polynoom π(f ) ∈ R[X]≤1 dat waarde f (a) aanneemt in a en f (b) in b. Zie ook Figuur 3.2. Het polynoom π(f ) heet de lineaire interpolant van f . Het is eenvoudig na te gaan dat dan voor alle f ∈ C(I), Tab (f ) = Iab (π(f )),

(2.11)

dus Tab (f ) is een approximatie van Iab (f ) berekend door π(f ) te integreren in plaats van f zelf. Definitie 2.1.17 (Trapeziumregel) Tab (f ) heet de trapeziumregel-approximatie van Iab (f ). De trapeziumregel is een voorbeeld van een zogeheten kwadratuurformule.

f f (b)

f (b) 1 2 (f (a)

π(f ) f (a)

+ f (b))

f (a) Tab (f )

Tab (f )

a

a

b

b

Figuur 3.2 De trapeziumregel Tab (f ) = 12 (f (a) + f (b))(b − a) benadert Iab (f ).

2.1.2

De duale basis β ∗ van V ∗ behorende bij een basis β van V

Veronderstel dat (V, K) een vectorruimte is van eindige dimensie. In Sectie 2.1.1 zagen we dat V ∗ isomorf is met V . We defini¨eren nu een basis voor V ∗ , gegeven een basis β van V . Definitie 2.1.18 (Duale basis) Zij (V, K) een vectorruimte met basis β = hv1 , . . . , vn i. Laat voor iedere j ∈ {1, . . . , n} v 7→ e> j coβ (v).

vj : V → K :

Hiermee is β ∗ = hv 1 , . . . , v n i een basis voor V ∗ , de duale basis genaamd. Opmerking 2.1.19 In Figuur 3.3 wordt v j gedefinieerd in termen van Figuur 3.1. V ∼ =

coβ

Kn

vj K `ej

v j = `ej ◦ coβ

(2.12)

2.1. DE DUALE VECTORRUIMTE

57

Figuur 3.3 De v j ∈ V ∗ uit Definitie 2.1.18 in termen van `ej uit Voorbeeld 2.1.5. Opmerking 2.1.20 Met Definitie 2.1.18 laat de co¨ordinaatafbeelding zich als volgt herschrijven,  1  v (v)   coβ : V → Kn : v 7→  ...  . (2.13) v n (v)

In het bijzonder zien we dus dat voor alle v ∈ V, v = v 1 (v)v1 + · · · + v n (v)vn ,

(2.14)

en tevens dat j



v (vi ) = δij =

1 als i = j . 0 als i 6= j

(2.15)

Merk op dat de karakterisering van v 1 , . . . , v n in (2.15) equivalent is met Definitie 2.1.18. We bewijzen nu dat β ∗ inderdaad een basis is. Omdat we in Gevolg 2.1.13 al zagen dat dim(V ∗ ) = dim(V ) = n volstaat het om de lineaire onafhankelijkheid van β ∗ aan te tonen. Lemma 2.1.21 De covectoren v 1 , . . . , v n zijn lineair onafhankelijk. Bewijs. Laat α1 , . . . , αn ∈ K zodanig zijn dat α1 v 1 + · · · + αn v n = 0 ∈ V ∗ ,

(2.16)

waarbij het rechterlid het neutrale element van V ∗ is, oftewel de nulfunctionaal 0 : V → K : v 7→ 0 ∈ K. Laat nu j ∈ {1, . . . , n} en evalueer (2.16) in vj ∈ V . Wegens (2.15) is v j (vi ) = δij en dus impliceert (2.16) dat K 3 0 = 0(vj ) = α1 v 1 (vj ) + · · · + αn v n (vj ) = αj v j (vj ) = αj . Omdat j willekeurig was, is α1 = · · · = αn = 0 en zijn v 1 , . . . , v n dus lineair onafhankelijk.  We kunnen vervolgens de bij β ∗ horende co¨ordinaatafbeelding coβ ∗ : V ∗ → Kn onderzoeken. Lemma 2.1.22 Zij V een vectorruimte met basis β = hv1 , . . . , vn i en laat β ∗ = h1 , . . . , v n i de bij β horende duale basis zijn voor V ∗ . Dan geldt dat  ∗  v (v1 )   .. coβ ∗ : V ∗ → Kn : v ∗ 7→  (2.17) , . v ∗ (vn )

oftewel, met andere woorden, dat v ∗ = v ∗ (v1 )v 1 + · · · + v ∗ (vn )v n voor alle v ∗ ∈ V ∗ .

(2.18)

58

HOOFDSTUK 2. DUALITEIT

Bewijs. Evalueer de beide lineaire functionalen in het linker- en rechterlid van (2.18) in v1 , . . . , vn met behulp van relatie (2.15) en concludeer gelijkheid.  We illustreren de duale basis en Lemma 2.1.22 met twee voorbeelden. Voorbeeld 2.1.23 Beschouw R2 voorzien van de standaardbasis ε = he1 , e2 i. De duale vectorruimte (R2 )∗ bestaat volgens Stelling 2.1.7 uit alle afbeeldingen `y : R 2 → R :



x1 x2



 7→ [y1 , y2 ]



x1 x2

, met y1 , y2 ∈ R.

We zien in het bijzonder dat `y = y1 e1 + y2 e2 , waarbij e1 : R2 → R :

x 7→ e> 1 x en

e2 : R2 → R :

x 7→ e> 2x

de individuele-co¨ ordinaatfunctionalen zijn. Het tupel he1 , e2 i is de duale basis ε∗ voor (R2 )∗ . Merk op dat `y = `y (e1 )e1 + `y (e2 )e2 , wat Lemma 2.1.22 illustreert. Het volgende voorbeeld speelt zich af in een polynoomruimte. Voorbeeld 2.1.24 Beschouw de vectorruimte (R[X]≤2 , R). Laat β = hφ0 , φ1 , φ2 i, waarbij φ0 : R → R :

X 7→ 1,

φ1 : R → R :

X 7→ X,

φ2 : R → R :

X 7→ X 2 .

De duale basis β ∗ = hφ0 , φ1 , φ2 i voor (R[X]≤2 )∗ bestaat per Definitie 2.1.18 en Opmerking 2.1.20 uit de individuele-co¨ ordinaatfunctionalen, die samen de co¨ ordinaatafbeelding coβ bepalen,  0  φ (·) coβ (·) =  φ1 (·)  . φ2 (·) Beschouw nu de integratie-afbeelding I01

Z : R[X]≤2 → R :

p→

1

p(X)dX. 0

Dan is I01 ∈ (R[X]≤2 )∗ en vertelt Lemma 2.1.22 dat 1 1 I01 = I01 (φ0 )φ0 + I01 (φ1 )φ1 + I01 (φ2 )φ2 = φ0 + φ1 + φ2 . 2 3 Hiermee hebben we de integratie-functionaal I01 dus expliciet geschreven als lineaire combinatie van de individuele-co¨ ordinaatfunctionalen φ1 , φ2 , φ3 . Opmerking 2.1.25 In het voorgaande voorbeeld hebben we in feite niets anders laten zien dan dat Z 1 1 1 a + bX + cX 2 dX = a + b + c (2.19) 2 3 0 oftewel, we hebben de integraal uitgedrukt als lineaire combinatie van de co¨ordinaten a, b, c.

2.1. DE DUALE VECTORRUIMTE

2.1.3

59

De dubbelduale vectorruimte V ∗∗ en het natuurlijke isomorfisme

In deze sectie bestuderen we de duale van de duale vectorruimte V ∗ , oftwel de dubbelduale vectorruimte V ∗∗ = (V ∗ )∗ van V . Volgens Definitie 2.1.3 is V ∗∗ = homK (V ∗ , K)

(2.20)

en deze vectorruimte bestaat dus uit alle lineaire functionalen V ∗ → K. Opmerking 2.1.26 Als V = R bestaat V ∗ = R∗ uit de lineaire afbeeldingen van R naar R, en V ∗∗ uit de lineaire afbeeldingen, die aan dergelijke lineaire afbeeldingen scalairen toevoegen. Dus V ∗∗ lijkt doorgaans niet hetzelfde als V , tenzij we onze interpretatie van V subtiel herzien. Definitie 2.1.27 (Duale koppeling) Zij V een vectorruimte met duale V ∗ . Schrijf voor alle v ∗ ∈ V en v ∈ V hv ∗ , vi = v ∗ (v). (2.21) De afbeelding h·, ·i : V ∗ × V → K heet de duale koppeling van het duale paar V, V ∗ . Opmerking 2.1.28 De uitdrukking hv ∗ , vi is geen inproduct. Als V een inproductruimte is, zullen we verschillende notaties nodig hebben voor inproduct en duale koppeling. De charme van de notatie hv ∗ , vi en van het hele concept van duale koppeling is, dat het een perfecte symmetrie suggereert tussen wat v ∗ doet met v, en omgekeerd, wat v doet met v ∗ . Opmerking 2.1.29 Het is gebruikelijk om v ∗ (v) en dus hv ∗ , vi te lezen als v ∗ ge¨evalueerd in v. De symmetrie in de notatie hv ∗ , vi moedigt echter aan om dit ook te lezen als v ge¨evalueerd in v ∗ . Dit interpreteert v als lineaire functionaal V ∗ → K : v ∗ 7→ hv ∗ , vi, als element van V ∗∗ . In Figuur 3.4 illustreren we de symmetrie tussen de gebruikelijke werking van V ∗ op V en de hier nieuw te beschouwen werking van V op V ∗ . v1

v2

vn

v1

1

0

0

v2

0

1

v ∗ (v) = hv ∗ , vi = v(v ∗ ) v ∗ : V → K : v 7→ hv ∗ , vi

vn

0

1

0

0

1

v : V ∗ → K : v ∗ 7→ hv ∗ , vi

Figuur 3.4. Dualiteit: het symbool v is zowel een element van V , als een element van V ∗∗ . We gebruiken in Figuur 3.4 voor de lineaire functionaal V ∗ → K : v ∗ 7→ hv ∗ , vi uit de vectorruimte V ∗∗ hetzelfde symbool v als voor het element v uit V . De motivatie hiervoor is dat we voor de lineaire functionaal V → K : v 7→ hv ∗ , vi standaard het symbool v ∗ gebruiken. Opmerking 2.1.30 Om de vraag te beantwoorden of het gebruik van het symbool v voor de afbeelding V ∗ → K : v ∗ 7→ hv ∗ , vi geen mathematische inconsistentie oplevert, zullen we aantonen dat iedere v ∈ V op deze manier precies ´e´en element uit V ∗∗ voorstelt, en omgekeerd, dat ieder element uit V ∗∗ voor is te stellen middels precies ´e´en element uit V .

60

HOOFDSTUK 2. DUALITEIT

In de volgende stelling gebruiken we daarom vooralsnog niet het symbool v maar H(v). Stelling 2.1.31 (Natuurlijk isomorfisme) Zij V, V ∗ een duaal paar met duale koppeling h·, ·i : V ∗ ×V → K. Laat H : V → V ∗∗ de afbeelding zijn die aan v ∈ V de lineaire functionaal H(v) : V ∗ → K :

v ∗ 7→ hv ∗ , vi

(2.22)

uit V ∗∗ toevoegt. Dan is H een lineaire bijectie tussen V en V ∗∗ , het natuurlijke isomorfisme. Opmerking 2.1.32 We schrijven H(v)(v ∗ ) voor de functionaal H(v) ∈ V ∗∗ ge¨evalueerd in v ∗ . Het alternatief is om de duale koppeling tussen V ∗ en V ∗∗ te gebruiken, maar dat is wellicht verwarrend. In het bijzonder is dus H(v)(v ∗ ) = hv ∗ , vi. Bewijs. We bewijzen eerst de lineariteit van H. Laat α, β ∈ K en v, w ∈ V . Dan geldt voor alle v ∗ ∈ V ∗ dat H(αv + βw)(v ∗ ) = hv ∗ , αv + βwi = αhv ∗ , vi + βhv ∗ , wi = αH(v)(v ∗ ) + βH(w)(v ∗ ), en dus zijn H(αv + βw) en αH(v) + βH(w) gelijk als afbeeldingen op V ∗ . Vervolgens laten we zien dat H injectief is. Veronderstel hiertoe dat H(v) = 0. Dit betekent dat H(v)(v ∗ ) = hv ∗ , vi = 0 ∈ K voor alle v ∗ ∈ V ∗ , en dus in het bijzonder voor de elementen v 1 , . . . , v n van de duale basis β ∗ van V ∗ horende bij een gekozen basis β = hv1 , . . . , vn i van V . Dus is hv j , vi = v j (v) = 0 voor alle j ∈ {1, . . . , n}, en volgt met behulp van Opmerking 2.1.20 dat coβ (v) = 0 en dus is v = 0. Dus is H injectief, en omdat dim(V ) = dim(V ∗∗ ) = n is H bijectief.  Opmerking 2.1.33 Als we het symbool v gebruiken voor zowel het element uit V als voor het element V ∗ → K : v ∗ 7→ hv ∗ , vi uit V ∗∗ dan valt te verdedigen dat V ∗∗ = V .

2.1.4

Het isomorfisme van Riesz

In Opmerking 2.1.9 zagen we dat iedere lineaire functionaal ` op Rn op precies ´e´en manier kan worden geschreven als het nemen van het inproduct met een vast gekozen y ∈ Rn . We bewijzen nu iets soortgelijks voor iedere eindigdimensionale re¨ele inproductruimte. Opmerking 2.1.34 Om verwarring met de duale koppeling h·, ·i te voorkomen schrijven we (·, ·) voor een inproduct. Stelling 2.1.35 (Riesz) Laat (V, R, (·, ·)) een inproductruimte zijn van dimensie n ∈ N. Dan is voor iedere u ∈ V de afbeelding `u : V → R :

v 7→ (u, v)

(2.23)

u 7→ `u

(2.24)

een element uit V ∗ . Definieer nu J :V →V∗ :

dan is J een lineaire bijectie en dus een isomorfisme, het Riesz-isomorfisme genaamd.

2.1. DE DUALE VECTORRUIMTE

61

Bewijs. De lineariteit van `u en van J volgen eenvoudig. Om injectiviteit van J te bewijzen, merk op dat `u (u) = (u, u) = kuk2 en dus volgt uit een inproductaxioma dat `u = 0 ⇒ u = 0. Dus ker(J ) = {0} en is J injectief. Gevolg 2.1.13 laat zien dat dim(V ∗ ) = dim(V ) = n en dus is J zelfs bijectief. We concluderen dat J een isomorfisme is.  Opmerking 2.1.36 In de overeenkomstige Stelling 2.1.7 was nog niet bewezen dat dim(V ∗ ) = dim(V ) en dus moest daar de surjectiviteit van L nog expliciet worden bewezen.

Frigyes Riesz (1880-1956) Definitie 2.1.37 (Riesz-representant) Het unieke element v ∈ V zo, dat (v, w) = v ∗ (w) voor alle w ∈ V heet de Riesz-representant van v ∗ in V . Opmerking 2.1.38 Laat (V, C, (·, ·)) een complexe inproductruimte zijn van dimensie n ∈ N. Dan is voor iedere u ∈ V de afbeelding `u : V → R :

v 7→ (u, v)

(2.25)

een element uit V ∗ , want complexe inproducten zijn lineair in de tweede component. Definieer nu J : V → V ∗ : u 7→ `u (2.26) dan is J weliswaar een bijectie maar niet een lineaire bijectie. Immers, J (αu) = `αu en `αu (v) = (αu, v) = α(u, v) = α`u (v) dus J (αu) = αJ (u). Dus is J geen lineaire afbeelding. Hij wordt anti-lineair of geconjugeerdlineair genoemd. We zullen in het vervolg alleen de re¨ele inproductruimten bekijken. Voorbeeld 2.1.39 In Opmerking 2.1.9 is y de Riesz-representant van `y . Voorbeeld 2.1.40 Beschouw voor zekere a < b het standaardinproduct Z (q, r) =

b

q(X)r(X)dX a

62

HOOFDSTUK 2. DUALITEIT

op de vectorruimte (R[X]≤n , R) van polynomen van graad ten hoogste n. De Riesz-representant van de integratie-afbeelding Iab ∈ (R[X]≤n )∗ gedefinieerd door Z b b Ia : R[X]≤n → R : r 7→ r(X)dX a

is het polynoom R → R : X 7→ 1. Immers, Iab (r) = (1, r) voor alle r ∈ R[X]≤n . Voorbeeld 2.1.41 Op de ruimte (Rn×n , R) defini¨eren we het inproduct (X, Y ) = Sp(X > Y ). De Riesz-representant van de lineaire functionaal Sp : Rn×n → R :

Y 7→ Sp(Y )

is de identiteitsmatrix I ∈ Rn×n . Immers, Sp(Y ) = Sp(I > Y ) = (I, Y ) voor alle Y ∈ Rn×n . Het volgende voorbeeld is wellicht wat verrassender. Voorbeeld 2.1.42 Laat A ∈ GLn (R) gegeven zijn met A> = A. Definieer voor alle y, z ∈ Rn , (y, z)A = y > Az. (2.27) Dan is (·, ·)A een inproduct op Rn . Beschouw nu het stelsel Ax = b van lineaire vergelijkingen voor gegeven b ∈ Rn . Omdat geldt dat (x, z)A = x> Az = x> A> z = (Ax)> z = b> z

(2.28)

is de oplossing x van Ax = b de Riesz-representant van de lineaire functionaal z 7→ b> z. Het Riesz-isomorfisme J is een lineaire afbeelding tussen vectorruimtes, en dus kunnen we β∗ de matrix Jβ van J beschouwen ten opzichte van bases β en β ∗ . Lemma 2.1.43 Zij (V, R, (·, ·)) een inproductruimte met basis β = hv1 , . . . , vn i. Schrijf β ∗ = hv 1 , . . . , v n i voor de bijbehorende duale basis van V ∗ . Dan is   (v1 , v1 ) . . . (vn , v1 ) ∗   .. .. Jββ =  (2.29)  . . (v1 , vn ) . . . (vn , vn ) de matrix van het Riesz-isomorfisme J : V → V ∗ ten opzichte van β en β ∗ . ∗

Bewijs. Per definitie is Jββ de matrix waarvoor geldt dat ∗

coβ ∗ (J (v)) = Jββ · coβ (v)

(2.30) ∗

voor alle v ∈ V , zoals afgebeeld in Figuur 3.5. Dus is de j-de kolom van Jββ gelijk aan     J (vj )(v1 ) (vj , v1 )     .. .. coβ ∗ (J (vj )) =  (2.31) = , . . J (vj )(vn ) (vj , vn )

2.1. DE DUALE VECTORRUIMTE

63

waar we gebruik maakten van Lemma 2.1.22 en de definitie van J uit Stelling 2.1.35.



In Figuur 3.5 vatten we ´e´en en ander schematisch samen. Definitie 2.1.18 van duale basis β ∗ = hv 1 , . . . , v n i, Opmerking 2.1.20 over de vorm van coβ in termen van v 1 , . . . , v n , Lemma 2.1.22 voor de co¨ ordinaten ten opzichte van β, en bovenstaand Lemma 2.1.43 voor de matrix van het Riesz-isomorfisme ten opzichte van β en β ∗ . β ∗ = {v 1 , . . . , v n }

β = {v1 , . . . , vn } j

 coβ (v) = 

V∗

v∗

hv , vivj coβ

j=1



J

V

hv 1 , vi

Rn



 ..  . n hv , vi

=

coβ ∗ ∗ Jββ

Rn



(v1 , v1 ) . . .  ..  . (v1 , vn ) . . .

n X

hv ∗ , vj iv j

j=1

 hv ∗ , v1 i   .. coβ ∗ (v ∗ ) =   . ∗ hv , vn i 

=

v=

n X

 (vn , v1 )  ..  . (vn , vn )

Figuur 3.5 Matrix van het Riesz-isomorfisme ten opzichte van basis en duale basis. Opmerking 2.1.44 De co¨ ordinaatvector coβ (J −1 (v ∗ )) van de Riesz-representant J −1 (v ∗ ) ∗ van v kan dus worden uitgerekend als oplossing x van het stelsel lineaire vergelijkingen ∗

Jββ x = coβ ∗ (v ∗ ),

(2.32)

∗

waarbij de matrix Jββ is als in Lemma 2.1.43. Voorbeeld 2.1.45 Beschouw nogmaals Voorbeeld 2.1.40, met voor het gemak de expliciete keuzes n = 2 en verder a = 0 en b = 1. We gaan de Riesz-representant p = J −1 (I01 ) van I01 uitrekenen. Kies hiertoe β = h1, X, X 2 i. De co¨ ordinaten van I01 ten opzichte van β ∗ hebben we reeds uitgerekend in Voorbeeld 2.1.24. Dan geeft Lemma 2.1.43 dat     1 21 31 1 ∗ Jββ coβ (p) =  12 13 41  coβ (p) =  21  = coβ ∗ (I01 ). (2.33) 1 3

1 4

1 5

1 3

Hieruit volgt dat coβ (p) = e1 ∈ R3 en dus dat p = 1, zoals we al zagen in Voorbeeld 2.1.40. ∗

Opmerking 2.1.46 Als β in Lemma 2.1.43 orthonormaal is, is Jββ = I, de identiteitsmatrix. In dat geval geldt kennelijk coβ ∗ (J (v)) = coβ (v), oftewel, v=

n X j=1

αj vj

⇔

J (v) =

n X

αj v j .

(2.34)

j=1

In dat geval kan de Riesz-representant v = J −1 (v ∗ ) van v ∗ het eenvoudigst worden bepaald.

64

HOOFDSTUK 2. DUALITEIT

We geven nu een voorbeeld waaruit blijkt dat als de vectorruimte V geen eindige dimensie heeft, de representatiestelling van Riesz niet zonder meer geldig blijft. Voorbeeld 2.1.47 Beschouw de inproductruimte (C(I), R, (·, ·)) van continue functies op het interval I = [0, 1], voorzien van het standaardinproduct Z 1 f (x)g(x)dx. (2.35) (f, g) = 0

We bekijken weer de lineaire functionaal I01 ∈ C(I)∗ . Net als in Voorbeeld 2.1.40 geldt ook hier dat (1, g) = I01 (g) (2.36) voor alle g ∈ C(I). Dus I01 heeft een Riesz-representant in C(I). Bekijk nu echter de functieevaluatie in x = 0, ε0 : C(I) → R : g 7→ g(0). (2.37) Deze functionaal is lineair en dus ε0 ∈ C(I)∗ . Veronderstel nu dat er een f ∈ C(I) bestaat met de eigenschap dat (f, g) = ε0 (g) voor alle g ∈ C(I). (2.38) Dan is f niet de nulfunctie. Omdat f continu is, bestaat er een niet-leeg open interval K = (a, b) ⊂ [0, 1] zo, dat f (x) 6= 0 voor alle x ∈ K. Laat nu g(x) = (x − a)(b − x) voor alle x ∈ K en g(x) = 0 voor alle x 6∈ [a, b]. Zie Figuur 3.6. f

f (x)g(x) > 0 op K f (x)g(x) = 0 op I \ K

g 0

a

K

b

⇒

(f, g) > 0 ε0 (g) = 0

1

Figuur 3.6 Voor iedere f ∈ C(I) is er een g ∈ C(I) met g(0) = 0 en (f, g) 6= 0. Dan is g ∈ C(I) met ε0 (g) = 0. Ook is f (x)g(x) = 0 voor alle x 6∈ K. Omdat voor alle x∈K ´ of f (x)g(x) > 0, ´ of f (x)g(x) < 0 is (f, g) 6= 0. Uit deze tegenspraak volgt dat er geen f ∈ C(I) bestaat zo, dat (f, g) = ε0 (g) voor alle g ∈ C(I). Opmerking 2.1.48 Dualiteit heeft in oneindig veel dimensies veel meer onverwachte wendingen dan in eindig veel dimensies. De representatiestelling van Riesz, maar bijvoorbeeld ook het natuurlijk isomorfisme hoeven daar niet meer geldig te zijn. Functie-evaluatie heeft wel een Riesz-representant op iedere polynoomruimte (R[X]≤n , R). Voorbeeld 2.1.49 Beschouw de vectorruimte (R[X]≤1 , R) van lineaire polynomen voorzien van het standaardinproduct Z 1 (q, r) = q(X)r(X)dX. −1

We bepalen de Riesz-representant van de evaluatie-functionaal ε0 : R[X]≤1 → R : p 7→ p(0). Hietoe kiezen we de basis β = h1, Xi voor R[X]≤1 . We vinden middels Lemma 2.1.22 dat     ε0 (1) 1 coβ ∗ (ε0 ) = = . (2.39) ε0 (X) 0

2.1. DE DUALE VECTORRUIMTE

65

Vervolgens berekenen we expliciet de matrix ∗ Jββ

 =

2 0

0

 (2.40)

2 3

met als gevolg dat coβ (J en dus dat r = J −1 (ε0 ) = Z

1

(r, p) = −1

1 2

−1

(ε0 )) =

h

∗ Jββ

i−1

 coβ ∗ (ε0 ) =

1 2

0

 ,

(2.41)

· 1 + 0 · X. En inderdaad, met p(X) = a + bX vinden we dat

1 1 1 2 1 (a + bX)dX = (aX + bX ) = a = p(0) = ε0 (p). 2 2 2 −1

(2.42)

Dit bevestigt dat r de Riesz-representant is van ε0 ∈ (R[X]≤1 )∗ .

2.1.5

De duale L∗ van een lineaire afbeelding L

Laat (V, K) en (W, K) vectorruimtes zijn over een lichaam K. Dan induceert iedere lineaire afbeelding L : V → W op natuurlijke wijze een zogeheten duale afbeelding L∗ : W ∗ → V ∗ . Definitie 2.1.50 (Duale afbeelding en pull-back) Voor iedere L ∈ homK (V, W ) defini¨eren we de duale afbeelding L∗ ∈ homK (W ∗ , V ∗ ) middels L∗ : W ∗ → V ∗ :

w∗ 7→ w∗ ◦ L.

(2.43)

De functionaal L∗ (w∗ ) heet de pull-back van w∗ in V ∗ onder L. Het is eenvoudig na te gaan dat L∗ goedgedefinieerd en linear is. V

L

V ∗ 3 w∗ ◦ L

W w∗ ∈ W ∗

L∗ : W ∗ → V ∗ : w∗ 7→ w∗ ◦ L

K L∗ Figuur 3.6 Definitie van de duale afbeelding L∗ en de pull-back w∗ ◦ L van w∗ . Opmerking 2.1.51 In de context van complexe inproductruimtes gebruikten we de notatie L∗ voor de geadjungeerde van een lineaire afbeelding L : V → W . Dit is de afbeelding zo, dat (v, L∗ (w))V = (L(v), w)W

(2.44)

voor alle v ∈ V en w ∈ W . Hier is (·, ·)V het inproduct op V en (·, ·)W het inproduct op W . Ondanks dat we de duale van een afbeelding L ook met L∗ aanduiden, is dit niet hetzelfde. Opmerking 2.1.52 De asterisk in L∗ is een bewerking ∗ : homK (V, W ) → homK (W ∗ , V ∗ ).

66

HOOFDSTUK 2. DUALITEIT

Voorbeeld 2.1.53 Laat L : R → R : x 7→ 2x. Dan beeldt L∗ een functionaal w∗ op R af op de functionaal v ∗ = L∗ (w∗ ) gedefinieerd door v∗ : R → R :

x 7→ w∗ (2x).

(2.45)

Deze v ∗ is dan de pull-back van w∗ onder L. Voorbeeld 2.1.54 Laat (C(I), R) de vectorruimte van continue functies op I = [a, b] zijn. Beschouw de lineaire afbeelding π : C(I) → R[X]≤1 :

f 7→ π(f ),

(2.46)

waarbij π(p) de lineaire interpolant is van f , oftewel, het unieke polynoom in R[X]≤1 dat waarde f (a) aanneemt in a en waarde f (b) in b. Laat vervolgens Z b b Ia : R[X]≤1 → R : g 7→ g(x)dx. (2.47) a

Dan is Iab ∈ (R[X]≤1 )∗ en is L∗ (Iab ) gelijk aan de lineaire functionaal Iab ◦ L, die we herkennen als Z b 1 b Ta : C(I) → R : f 7→ π(f )(x)dx = (f (a) + f (b)) (b − a), (2.48) 2 a oftewel, de trapeziumregel Tab ∈ (C(I))∗ is de pull-back van Iab onder π. Zie Figuur 3.7. C(I)

π R[X]≤1 Iab ∈ (R[X]≤1 )∗

C(I)∗ 3 Tab R

π ∗ (Iab ) = Tab

π∗ Figuur 3.7 Relatie tussen Iab en Tab via de duale π ∗ van de lineaire-interpolatieafbeelding. De duale L∗ van een lineaire afbeelding is zoals gezegd niet gelijk aan de geadjungeerde. Wel kunnen we het volgende onmiddellijk inzien. Vergelijk dit met Opmerking 2.1.51. Stelling 2.1.55 Laat L∗ ∈ homK (W ∗ , V ∗ ) de duale zijn van L ∈ homK (V, W ). Dan geldt voor alle v ∈ V en w∗ ∈ W ∗ , hL∗ (w∗ ), viV = hw∗ , L(v)iW

(2.49)

waarbij h·, ·iV de duale koppeling tussen V ∗ en V en h·, ·iW die tussen W ∗ en W is. Bewijs. Er geldt per definitie van duale koppeling en van L∗ dat hw∗ , L(v)iW = w∗ (L(v)) = (w∗ ◦ L)(v) = L∗ (w∗ )(v) = hL∗ (w∗ ), viV . Dit bewijst de bewering.

(2.50) 

De matrix van L∗ blijkt eenvoudigweg de getransponeerde te zijn van die van L, indien we V ∗ en W ∗ voorzien van de duale bases van die van V en W .

2.1. DE DUALE VECTORRUIMTE

67

Stelling 2.1.56 Laat βV = hv1 , . . . , vn i een basis zijn van V en βW = hw1 , . . . , wk i een basis voor W . Laat L∗ ∈ homK (W ∗ , V ∗ ) de duale zijn van L ∈ homK (V, W ). Dan is β∗

(L∗ )βV∗ = (LββW )> , V

(2.51)

W

∗ de duale bases van β en β waarbij βV∗ en βW V W zijn.

Bewijs. Per definitie van de beide matrices geldt β∗

∗ ∗ (w ) coβV∗ (L∗ (w∗ )) = (L∗ )βV∗ coβW

(2.52)

W

voor alle w∗ ∈ W ∗ , en tevens dat voor alle v ∈ V , coβW (L(v)) = LββW coβV (v). V

(2.53)

Laat nu i ∈ {1, . . . , k} en j ∈ {1, . . . , n} gegeven zijn. Dan geldt dat β∗

β∗

∗ V > ∗ V j > ∗ j ∗ j ∗ (w ) = e coβ ∗ (L (w )) = hL (w ), vi iV , e> i (L )β ∗ ej = ei (L )β ∗ coβW i V W

W

waar de tweede gelijkheid (2.52) gebruikt en de derde gelijkheid Lemma 2.1.22. Idem vinden we βW j > > βW e> j LβV ei = ej LβV coβV (vi ) = ej coβW (L(vi )) = hw , L(vi )iW , waarbij de tweede gelijkheid (2.53) gebruikt en de derde Opmerking 2.1.20. Omdat wegens Stelling 2.1.56 geldt dat hwj , L(vi )iW = hL∗ (wj ), vi iV vinden we dat β∗

∗ V > βW e> i (L )β ∗ ej = ej LβV ei .

(2.54)

W

Dit bewijst de bewering.

2.1.6



De annihilator

Het begrip annihilator in de duale vectorruimte is gerelateerd aan het begrip orthogonaal complement in een inproductruimte. Definitie 2.1.57 (Annihilator) Zij (V, K) een vectorruimte en S ⊂ V . Dan heet de verzameling S ◦ = {v ∗ ∈ V ∗ | v ∗ (s) = 0 voor alle s ∈ S} (2.55) de annihilator van S in V ∗ . In het bijzonder geldt dus dat v ∗ ∈ S ◦ als en alleen als S ⊂ ker(v ∗ ). Opmerking 2.1.58 Als v ∗ nul is op S, is v ∗ ook nul op de deelruimte van V opgespannen door de elementen van S. In het bijzonder is S ◦ dus een lineaire deelruimte van V ∗ , ook als S geen deelruimte is. Tot slot is eenvoudig in te zien dat V ◦ = {0} en {0}◦ = V ∗ . Annihilatoren worden uiteraard kleiner naarmate de te annihileren verzameling groter wordt. Lemma 2.1.59 Laat (V, K) een vectorruimte zijn met duale V ∗ . Dan geldt S⊂T ⊂V

⇒

T ◦ ⊂ S◦ ⊂ V ∗.

(2.56)

68

HOOFDSTUK 2. DUALITEIT

Bewijs. Als v ∗ (t) = 0 voor alle t ∈ T dan is v ∗ (s) = 0 voor alle s ∈ S.



De omgekeerde implicatie in (2.56) is niet geldig.

De Canadese band Annihilator (1984) Voorbeeld 2.1.60 Beschouw de deelverzameling {e1 } ⊂ R3 . Ieder element van (R3 )∗ is te schrijven als `y : R3 → R : x 7→ y > x, en `y (e1 ) = 0 als en alleen als e> 1 y = 0. Dus, {e1 }◦ = {`y : R3 → R : x 7→ y > x | e> 1 y = 0}.

(2.57)

Merk op dat {e1 }◦ ook gelijk is aan het opspansel van e2 en e3 , waarbij ε∗ = he1 , e2 , e3 i de duale basis is van de standaardbasis ε = he1 , e2 , e3 i. Het voorgaande voorbeeld illustreert het aangekondigde verband tussen orthogonale complementen en annihilatoren. Dit verband wordt expliciet gemaakt middels het Riesz-isomorfisme. Stelling 2.1.61 Zij (V, R, (·, ·)) een inproductruimte en S ⊂ V . Dan geldt span(S)⊥ = J −1 (S ◦ ),

(2.58)

waarbij J : V → V ∗ het Riesz-isomorfisme is. Bewijs. Laat v ∗ ∈ S ◦ . Dan is v ∗ (s) = 0 voor alle s ∈ S. Per definitie van Riesz-representant is J −1 (v ∗ ) de vector uit V waarvoor geldt dat (J −1 (v ∗ ), v) = v ∗ (v) voor alle v ∈ V ,

(2.59)

en dus staat J −1 (v ∗ ) loodrecht op alle s ∈ S en daarmee ook loodrecht op alle lineaire combinaties van vectoren uit S. Dus J −1 (v ∗ ) ∈ span(S)⊥ . Omgekeerd, laat w ∈ span(S)⊥ , dan geldt in het bijzonder dat (w, s) = 0 voor alle s ∈ S, en dus is J (w) : V → R :

v 7→ (w, v)

een element is van S ◦ . Dit bewijst de bewering.

2.1.7

(2.60) 

Quoti¨ entruimtes

Laat V een vectorruimte zijn met lineaire deelruimte W . Dan kunnen we de volgende equivalentierelatie defini¨eren op V , x∼y

⇔

x − y ∈ W.

(2.61)

2.1. DE DUALE VECTORRUIMTE

69

Deze relatie verdeelt V in equivalentieklassen die we aanduiden met [x], waarbij [x] = {x + w | w ∈ W }.

(2.62)

De quoti¨entverzameling V /W is de verzameling van equivalentieklassen, V /W = {[x] | x ∈ V }.

(2.63)

Als we deze verzameling voorzien van de volgende optelling en scalaire vermenigvuldiging, in de zin dat voor alle [x], [y] ∈ V /W en alle α ∈ K, [x] + [y] = [x + y]

en

α[x] = [αx],

(2.64)

dan is V /W zelfs een vectorruimte, de quoti¨entruimte van V en W genaamd. Voorbeeld 2.1.62 Beschouw R2 met als deelruimte het opspansel van w ∈ R2 met w 6= 0. Dan bestaat R2 /W uit de verzameling van lijnen parallel aan W , oftewel, R2 /W = { {x + αw | α ∈ R} | x ∈ R2 }.

(2.65)

Het nul-element uit R2 /W is [0]. Immers, [x] + [0] = [x + 0] = [x]. Merk op dat [w] en [0] hetzelfde element zijn in R2 /W . Ter illustratie gaan we nu aantonen dat als [v] 6= [0], de verzameling h[v]i een basis is voor R2 /W . Omdat [v] 6= [0] geldt sowieso dat h[v]i lineair onafhankelijk is in R2 /W . We hoeven dus alleen nog maar aan te tonen dat het opspansel van h[v]i gelijk is aan R2 /W . Laat hiertoe [x] ∈ R2 /W willekeurig zijn. Dan vinden we α[v] = [x]

⇔

[αv] = [x]

⇔

αv − x ∈ W

⇔

αv + βw = x

(2.66)

voor zekere β ∈ R. Omdat [v] 6= [w] = [0] zijn v en w lineair onafhankelijk in R2 , en dus is het bestaat van α en β waarvoor αv + βw = x voor iedere x ∈ R2 gegarandeerd. Dus is er een α ∈ R zodanig dat α[v] = [x] en dus wordt R2 /W opgespannen door h[v]i. We laten tot slot een verband zien tussen de duale van de quoti¨entruimte V /W van een vectorruimte V en een deelruimte W , en de eerder ten tonele gevoerde annihilator. Stelling 2.1.63 Laat W een deelruimte zijn van een eindig dimensionale vectorruimte V . Dan geldt dat (V /W )∗ ∼ = W ◦ ⊂ V ∗. Bewijs. Een lineaire functionaal v ∗ op V induceert een goed gedefinieerde lineaire functionaal v˜∗ op V /W v˜∗ : V /W → K : [v] 7→ v ∗ (v) (2.67) als en alleen als v ∗ constant is op de equivalentieklassen van V . Dit is zo als en alleen als v ∗ (x) = v ∗ (x) + v ∗ (w) voor alle x ∈ V en alle w ∈ W , en dus als en alleen als W ⊂ ker(v ∗ ), oftewel v ∗ ∈ W ◦ . Hiermee is bewezen dat de afbeelding W ◦ → (V /W )∗ :

v ∗ 7→ v˜∗

met v˜∗ als in (2.67), een bijectie is. De lineariteit van deze bijectie volgt eenvoudig.



70

2.2

HOOFDSTUK 2. DUALITEIT

Opgaven

Opgave 2.1 Geef voor ieder van de volgende vectorruimtes twee voorbeelden van elementen uit de duale, (a) (R, R) (b) (C, C) (c) (C, R) (d) (R3×2 , R) (e) (RN , R) (f ) (R[X]≤3 , R) (g) (R∗ , R) (h) ((RR )∗ , R). Opgave 2.2 (a) Geef de duale basis β ∗ horende bij de basis β = {2} van (C, C). (b) Geef de duale basis β ∗ horende bij de basis β = {1, i} van (C, R). Opgave 2.3 Gegeven is de basis β = {v1 , v2 , v3 } van R3 waarbij 

     1 1 1 v1 =  0  , v 2 =  1  , v 3 =  1  . 0 0 1 Geef de volledige functievoorschriften van de elementen v 1 , v 2 , v 3 van de duale basis β ∗ . Opgave 2.4 Ga na dat de afbeelding L lineair is, waarbij L : Kn → (Kn )∗ : y 7→ `y

(2.68)

en waarbij `y : Kn → K : x 7→ y > x. Opgave 2.5 Definieer de afbeelding π : C(I) → R[X]≤1 :

f 7→ π(f )

(2.69)

die aan f ∈ C(I) toevoegt het lineaire polynoom π(f ) ∈ R[X]≤1 dat waarde f (a) aanneemt in a en f (b) in b. Het polynoom π(f ) heet de lineaire interpolant van f . (a) Bewijs dat π een goed gedefinieerde lineaire afbeelding is.

2.2. OPGAVEN

71

(b) Ga na dat voor alle f ∈ C(I), Tab (f ) = Iab (π(f )),

(2.70)

waarbij Iab en Tab zijn zoals gedefinieerd in ´e´en van de voorbeelden. Opgave 2.6 Beschouw de vectorruimte (R[X]≤2 , R) met basis β = {φ0 , φ1 , φ2 } waarbij φ0 : R → R :

X 7→ 1,

φ1 : R → R :

X 7→ X,

φ2 : R → R :

X 7→ X 2 .

Laat voor gegeven x ∈ R de afbeelding εx gedefinieerd zijn door εx : R[X]≤2 → R :

f 7→ f (x).

(a) Laat zien dat εx ∈ (R[X]≤2 )∗ . Laat β ∗ = {φ0 , φ1 , φ2 } de bij β horende duale basis zijn van (R[X]≤2 )∗ , en coβ ∗ : (R[X]≤2 )∗ → R3 de bij β ∗ horende co¨ ordinaatafbeelding. (b) Bereken coβ ∗ (εx ). Opgave 2.7 Beschouw de vectorruimte (R[X]≤2 , R) met basis β = {φ0 , φ1 , φ2 } waarbij φ0 : R → R :

X 7→ 1,

φ1 : R → R :

X 7→ X,

φ2 : R → R :

Laat zoals voorheen de afbeelding T01 gedefinieerd zijn als T01 : R[X]≤2 → R :

1 f 7→ (f (0) + f (1)). 2

(a) Laat zien dat T01 ∈ (R[X]≤2 )∗ . Laat β ∗ = {φ0 , φ1 , φ2 } de bij β horende duale basis zijn van (R[X]≤2 )∗ , en coβ ∗ : (R[X]≤2 )∗ → R3 de bij β ∗ horende co¨ ordinaatafbeelding. (b) Bereken coβ ∗ (T01 ). Opgave 2.8 Beschouw op de vectorruimte (R2×2 , R) de afbeelding Sp : R2×2 → R : (a) Laat zien dat Sp ∈ (R2×2 )∗ .

A 7→ Sp(A).

X 7→ X 2 .

72

HOOFDSTUK 2. DUALITEIT

Schrijf h·, ·i voor de duale koppeling tussen R2×2 en (R2×2 )∗ . (b) Bereken hSp, Ii. Laat nu ε = {E1 , E2 , E3 , E4 } de standaardbasis van R2×2 zijn, dus         1 0 0 0 0 1 0 0 E1 = , E2 = , E3 = , E4 = . 0 0 1 0 0 0 0 1 Laat ε∗ = {E 1 , E 2 , E 3 , E 4 } de duale basis zijn van ε voor de duale ruimte (R2×2 )∗ , en coε∗ : R2×2 → R4 de bijbehorende co¨ ordinaatafbeelding. (c) Bereken coε∗ (Sp). Opgave 2.9. De duale basis β ∗∗ van de duale basis β ∗ Gegeven is een vectorruimte (V, K) met basis β = {v1 , . . . , vn }. Laat β ∗ = {v 1 , . . . , v n } de bij β horende duale basis van V ∗ zijn. Schrijf H : V → V ∗∗ :

v 7→ H(v), waarbij

H(v) : V ∗ → K :

v ∗ 7→ hv ∗ , vi

voor het natuurlijke isomorfisme tussen V en V ∗∗ . Bewijs dat β ∗∗ = {H(v1 ), . . . , H(vn )} de duale basis van β ∗ voor V ∗∗ is. Opgave 2.10 Beschouw de inproductruimte (R3 , R, (·, ·)) voorzien van het standaardinproduct. Gegeven is de basis β = {v1 , v2 , v3 } van R3 , waarbij       1 1 1 v1 =  0  , v2 =  1  en v3 =  1  . 0 0 1 Schrijf β ∗ = {v 1 , v 2 , v 3 } voor de bijbehorende duale basis van (R3 )∗ , en laat J : R3 → (R3 )∗ het Riesz-isomorfisme zijn. (a) Bereken de Riesz-representanten van v 1 , v 2 en v 3 in R3 . Laat vervolgens H : R3 → (R3 )∗∗ het natuurlijke isomorfisme zijn. (b) Bereken H(v1 + v2 + v3 )(v 1 + v 2 + v 3 ). Opgave 2.11 Beschouw de inproductruimte (R[X]≤n , R, (·, ·)) waarbij Z

1

(q, r) =

q(X)r(X)dX. −1

2.2. OPGAVEN

73

Definieer voor iedere gehele niet-negatieve n de afbeelding εn0 : R[X]≤n → R :

q 7→ q(0).

(a) Bepaal de Riesz-representant van ε00 in R[X]≤0 . (b) Bepaal de Riesz-representant van ε10 in R[X]≤1 . (c) Bepaal de Riesz-representant van ε20 in R[X]≤2 . Opgave 2.12 Beschouw de inproductruimte (R[X]≤n , R, (·, ·)) waarbij Z 1 q(X)r(X)dX. (q, r) = −1

Definieer voor iedere gehele niet-negatieve n de afbeelding q 7→ q 0 (0).

δ0n : R[X]≤n → R :

(a) Bepaal de Riesz-representant van δ00 in R[X]≤0 . (b) Bepaal de Riesz-representant van δ01 in R[X]≤1 . (c) Bepaal de Riesz-representant van δ02 in R[X]≤2 . Opgave 2.13 Bn = {0, 1}n bestaat uit de vectoren in Rn met entries uit {0, 1}. We schrijven e ∈ Bn voor de som van de standaardbasisvectoren e1 , . . . , en van Rn . Voor gegeven r ∈ Bn is r = e − r, en dus is e = 0, 0 = e en r = r. De entries van r, r ∈ Bn noteren we met r1 , . . . , rn en r1 , . . . , rn . ∗

Voor iedere vast gekozen r ∈ Bn , definieer een lineaire functionaal `r ∈ (Rn×n ) door `r : Rn×n → R :

X 7→ r> Xr.

Laat βn de standaardbasis van Rn×n zijn, oftewel, βn = {Xij ∈ Rn×n | Xij = ei e> j }. Dus Xij = ei e> j heeft als gebruikelijk een 1 op positie (i, j) en nullen op de overige posities. ∗

Schrijf βn∗ = {X 11 , . . . , X nn } voor de bijbehorende duale basis voor (Rn×n ) . Voor iedere r ∈ Bn bestaan er dan a11 , . . . , ann ∈ R zodanig dat `r = a11 X 11 + · · · + ann X nn . (a) Laat zien dat aij = ri rj voor alle i, j ∈ {1, . . . , n}. Schrijf vervolgens J : Rn×n → Rn×n


∗

voor het Riesz-isomorfisme behorende bij het inproduct (X, Y ) = Sp(X > Y ). (b) Bewijs dat J (rr> ) = `r , oftewel, dat de matrix R = rr> de Riesz-representant van `r in Rn×n is.

74

HOOFDSTUK 2. DUALITEIT

Opgave 2.14 Laat L ∈ homK (V, W ), en laat L∗ : W ∗ → V ∗ : w∗ 7→ w∗ ◦ L de duale afbeelding zijn. (a) Bewijs dat L∗ (w∗ ) een lineaire afbeelding is. (b) Bewijs dat L∗ een lineaire afbeelding is. (c) Bewijs dat L injectief is als en alleen als L∗ surjectief is. (d) Bewijs dat L∗ bijectief is als en alleen als L bijectief is. Opgave 2.15 Gegeven drie vectorruimtes U, V, W over K, laat A ∈ homK (U, V ) en B ∈ homK (V, W ). Bewijs dat (BA)∗ = A∗ B ∗ . Opgave 2.16 Laat V en W eindigdimensionale vectorruimten over een lichaam K zijn. Bewijs dat de toevoeging ∗ : homK (V, W ) → homK (W ∗ , V ∗ ) : L 7→ L∗ een lineaire bijectie is. Opgave 2.17 Gegeven de lineaire afbeelding L : R3×3 → R3×3 :

X 7→

X + X> . 2

(a) Bepaal de pull-back van Sp ∈ (R3×3 )∗ onder L. Schrijf S voor de deelverzameling van elementen uit (R3×3 )∗ die door de pull-back onder L op zichzelf worden afgebeeld. (b) Bewijs dat S een deelruimte is en geef een basis voor S. Opgave 2.18 Schrijf H : R2×2 → R2×2


∗∗

: Y 7→ H(Y ) voor het natuurlijke isomorfisme.

(a) Geef het domein, codomein, en (functie-)voorschrift van H(Y ), voor gegeven Y ∈ R2×2 . Beschouw nu de afbeelding T :R

2×2

 →R:

X 7→ [1 1]X

1 1

 .

Schrijf h·, ·i1 voor de duale koppeling tussen R2×2 en (R2×2 )∗ en h·, ·i2 voor de duale koppeling tussen (R2×2 )∗ en (R2×2 )∗∗ . Kies vanaf nu expliciet   1 1 Y = . 1 1

2.2. OPGAVEN

75

Geef in de komende onderdelen voldoende motivatie voor je antwoorden. (b) Bereken hH(Y ), T i2 . Definieer L : R2×2 → R2×2 : X 7→ Y X en schrijf L∗ voor zijn duale afbeelding. (c) Bepaal de pull-back van T onder L en bereken vervolgens hL∗ (T ), Y i1 . Opgave 2.19 Zij (V, K) een vectorruimte met dim(V ) = n ∈ N en L ∈ homK (V, V ). Laat L∗ : V ∗ → V ∗ de duale afbeelding zijn van L, en L∗∗ = (L∗ )∗ : V ∗∗ → V ∗∗ de duale afbeelding van L∗ . Bewijs dat L∗∗ H = HL, oftewel, dat voor alle v ∈ V geldt dat L∗∗ (H(v)) = H(L(v)) waarbij H : V → V ∗∗ het natuurlijke isomorfisme is.

76

HOOFDSTUK 2. DUALITEIT

Hoofdstuk 3

Niet-negatieve lineaire algebra Het deelgebied van de niet-negatieve lineaire algebra houdt zich bezig met matrices en vectoren waarvan alle entries niet-negatieve (of zelfs positieve) re¨ele getallen zijn. Zulke matrices komen bijvoorbeeld af van een lineaire transformatie L : Rn → Rn die de eigenschap heeft dat het niet-negatieve orthant Rn≥0 = [0, ∞)n ⊂ Rn op zichzelf wordt afgebeeld. Ten opzichte van de standaardbasis ε van Rn is de matrix Lεε van L dan niet-negatief. Echter, ook binnen de stochastiek komen niet-negatieve matrices en vectoren nogal eens voor. Hiervan liggen alle entries vaak zelfs in het interval [0, 1] en stellen in die context waarschijnlijkheden voor. We bestuderen daarom de dubbelstochastische matrices en defini¨eren tevens de permanent van een matrix, een functie die op het eerste gezicht erg lijkt op de determinant, en die ook in de niet-negatieve combinatorische context een belangrijke rol speelt. Binnen diezelfde combinatoriek en in het bijzonder de grafentheorie komen zelfs geregeld 0/1-matrices voor, oftewel matrices waarvan alle entries uit de verzameling {0, 1} komen.

3.1

Perron-Frobeniustheorie

Positieve en niet-negatieve matrices komen veel voor binnen de stochastiek, combinatoriek, en binnen het wiskundig modelleren van allerlei natuurwetenschappelijke fenomenen: temperatuur, dichtheid, en concentratie zijn immers allemaal niet-negatief. Definitie 3.1.1 (Positieve/niet-negatieve matrix) Laat (aij ) = A ∈ Rn×k . Als aij > 0 voor alle i, j ∈ {1, . . . , n} schrijven we A > 0 en heet A een positieve matrix. Als aij ≥ 0 voor alle i, j ∈ {1, . . . , n} schrijven we A ≥ 0 en heet A een niet-negatieve matrix. Opmerking 3.1.2 Overeenkomstig schrijven we A > B als A − B > 0 en A ≥ B als A − B ≥ 0, en bedoelen we met A < B dat B > A, met A ≤ B dat B ≥ A, enzovoorts. Tot slot schrijven we |A| voor de matrix waarvan de entries de absolute waarden zijn van die van A. Een waarschuwing is hier op zijn plaats. Als x ∈ R en x ≥ 0 en x 6= 0 dan is x > 0. Echter, als A ∈ Rn×k met nk > 1 en A ≥ 0 en A 6= 0, impliceert dit niet dat A positief is: zie bijvoorbeeld de 1 × 2 matrix A = [1 0]. Deze is niet positief, maar ook niet de nul-matrix. Zonder bewijs vermelden we de volgende elementaire eigenschappen. Lemma 3.1.3 (E1) Als A > 0 en x ≥ 0, x 6= 0, dan is Ax > 0; 77

78

HOOFDSTUK 3. NIET-NEGATIEVE LINEAIRE ALGEBRA

(E2) Als A > 0 en x > y dan is Ax > Ay; (E3) Als A ≥ 0 en x ≥ y dan is Ax ≥ Ay; (E4) Voor alle A ∈ Rn×k en x ∈ Rk geldt dat |Ax| ≤ |A||x|; (E5) Voor alle matrices A en B waarvoor AB bestaat geldt dat |AB| ≤ |A||B|. Deze en dergelijke eigenschappen zullen we in het vervolg vrijelijk toepassen indien nodig.

3.1.1

De Neumannrij en de Neumannreeks

Als r ∈ R en |r| < 1 dan is limk→∞ rk+1 = 0, en convergeert tevens de meetkundige reeks ∞ X

rk =

j=0

1 − rk+1 1 . , want 1 + r + r2 + · · · + rk = 1−r 1−r

(3.1)

Een vooral theoretisch zeer nuttig overeenkomstig resultaat voor matrices werd bewezen door de Duitse wiskundige Carl Neumann.

Carl Neumann (1832-1925) Eerst een definitie, die de voorwaarde |r| < 1 voor convergentie helpt te generaliseren. Definitie 3.1.4 (Spectraalstraal) Laat A ∈ Cn×n . De spectraalstraal van A is het re¨ele, niet-negatieve getal ρ(A) = max{|λ| | λ ∈ σ(A)} waarbij σ(A) de verzameling van eigenwaarden van A is, het spectrum van A. De verzameling {z ∈ C | |z| ≤ ρ(A)} heet de spectrale schijf, met als rand de spectrale cirkel. Dus ρ(A) is de straal van de kleinste gesloten schijf rond 0 ∈ C waarop alle eigenwaarden van A liggen, de spectrale schijf. ∗ ∗ C

∗

∗

∗

}

0

ρ(A)

∗ is een eigenwaarde

ρ(A)

∗

Figuur 3.1 Het spectrum, de spectrale cirkel, de spectrale schijf, en de spectraalstraal.

3.1. PERRON-FROBENIUSTHEORIE

79

Opmerking 3.1.5 De spectraalstraal ρ(A) is niet altijd een eigenwaarde. Zie A = [−1]. De met (3.1) corresponderende uitspraken verdelen we over een lemma en twee stellingen. Lemma 3.1.6 Laat λ ∈ C met |λ| < 1 en laat ` ∈ N. Dan geldt dat   k k−` λ = 0. lim k→∞ `

(3.2)

Bewijs. Dit volgt uit de begrenzing van de binomiaalco¨effici¨ent middels   k k! k(k − 1) . . . (k − ` + 1) k` = = ≤ , ` `!(k − `)! `! `! en de eventueel herhaalde toepassing van de regel van de l’Hopital op f (x) = x` λx .



Stelling 3.1.7 (Neumannrij) Laat A ∈ Cn×n en veronderstel ρ(A) < 1, dan geldt dat de limiet voor k → ∞ van de Neumannrij (Ak )k≥0 gelijk is aan de nulmatrix, lim Ak = 0.

k→∞

Bewijs. In Stelling 1.3.25 bewezen we dat er voor alle A ∈ Cn×n een X ∈ GLn (C) bestaat zo, dat     X −1 AX =  

T1

0

0 .. . 0

T2 .. . ...

... .. . .. . 0

0 ..  . 



(3.3)

0  Tp

waarbij Tj = λj I + Mj met Mj ∈ Cmj ×mj strict bovendriehoeks en dus nilpotent. Hierbij is mj de meetkundige multipliciteit van de eigenwaarde λj van A. Nu volgt eenvoudig dat 

T1k

0

  Ak = X  

0 .. . 0

T2k .. . ...

... .. . .. . 0

0 ..  .  −1 X . 0  Tpk



Gebruik makend van het feit dat de beide matrices λj I en Mj commuteren, vinden we met behulp van het binomium van Newton dat voor alle k ∈ N, Tjk

mj   k   X k k−` ` X k k−` ` = (λj I + Mj ) = λ Mj = λ Mj . ` j ` j k

`=0

`=1

waarbij de laatste gelijkheid geldt omdat Mj nilpotent is met index ten hoogste mj . Omdat |λj | < 1 wegens de aanname dat ρ(A) < 1 volgt met Lemma 3.1.6 dat de limiet voor k naar oneindig van Tjk gelijk is aan de nulmatrix, en dus ook die van Ak .  Opmerking 3.1.8 De voorwaarde ρ(A) < 1 is noodzakelijk voor de convergentie van de Neumannrij naar nul, maar niet noodzakelijk voor convergentie. Zie bijvoorbeeld A = I. In Sectie 3.1.3 laten we zien dat limk→∞ Ak ook bestaat als A > 0 en ρ(A) = 1.

80

HOOFDSTUK 3. NIET-NEGATIEVE LINEAIRE ALGEBRA

Stelling 3.1.9 (Neumannreeks) Laat A ∈ Cn×n en veronderstel dat ρ(A) < 1, dan geldt dat ∞ X Ak = (I − A)−1 . (3.4) j=0

Bewijs. Voor iedere gehele k ≥ 0 geldt dat (I + A + A2 + · · · + Ak )(I − A) = I − Ak+1 . De limiet voor k → ∞ van het rechterlid bestaat volgens Lemma 3.1.7 en dus vinden we dat ∞ X

Ak (I − A) = I.

j=0

Omdat I − A vierkant is, is de som links van de matrix I − A kennelijk zijn inverse.

.

Dus als N nilpotent is, is I − N inverteerbaar met als inverse een polynoom in N . Opmerking 3.1.10 De voorwaarde ρ(A) < 1 is noodzakelijk voor de convergentie van de Neumannreeks in Stelling 3.1.9, omdat in een convergente som de individuele termen naar nul convergeren. De voorwaarde is echter niet nodig voor de inverteerbaarheid van I − A. Zie     2 1 3 1 met σ(A) = {2, 4}, I − A = − A= 1 2 1 3 en merk op dat I − A inverteerbaar is wegens det(I − A) = 3 ondanks dat ρ(A) = 4.

3.1.2

Perron-Frobeniustheorie voor positieve matrices

Oskar Perron en Georg Frobenius bewezen resultaten voor eigenwaarden en eigenvectoren van niet-negatieve matrices.

Oskar Perron (1880-1975) en Georg Ferdinand Frobenius (1849-1917)

De bewijzen zijn het eenvoudigst voor positieve matrices. Lemma 3.1.11 Laat A ∈ Rn×n . Als A > 0 dan is zijn spectraalstraal ρ(A) > 0. Bewijs. Stel dat ρ(A) = 0. Dit betekent dat alle eigenwaarden van A gelijk zijn aan nul. Maar dan is A nilpotent en bestaat er dus een p met Ap = 0. Echter, als A > 0 dan is duidelijk ook Ak > 0 voor alle k. Deze tegenspraak bewijst de bewering.  Het volgende lemma is sterker dan het lijkt: uit de aanname dat A > 0 een niet-negatieve eigenvector x heeft, volgt dat x zelfs positief is, met positieve bijbehorende eigenwaarde.

3.1. PERRON-FROBENIUSTHEORIE

81

Lemma 3.1.12 Laat A ∈ Rn×n , A > 0. Als Ax = λx voor zekere x ≥ 0, x 6= 0, dan volgt dat x > 0 en tevens dat λ > 0. Bewijs. Omdat 0 6= x ≥ 0 geeft (E1) uit Lemma 3.1.3 dat Ax > 0. Omdat Ax = λx geldt dus dat λx > 0. Omdat Rn 3 x ≥ 0 volgt dat R 3 λ > 0 en dus, tot slot, dat x > 0.  Ondanks dat de spectraalstraal van een matrix doorgaans geen eigenwaarde is, is dit wel het geval indien A > 0, en bestaat er een positieve eigenvector horende bij ρ(A). Stelling 3.1.13 Laat A ∈ Rn×n . Als A > 0 dan bestaat er een x > 0 zodanig dat Ax = ρ(A)x.

(3.5)

waarbij ρ(A) de spectraalstraal is van A. Bewijs. Veronderstel op grond van Lemma 3.1.11 zonder verlies van algemeenheid dat ρ(A) = 1. Dit impliceert dat er een λ ∈ σ(A) bestaat met |λ| = 1 en een y 6= 0 waarvoor Ay = λy. Voor deze λ en y geldt dat |y| = |λ||y| = |λy| = |Ay| ≤ |A||y| = A|y|, waarbij we gebruik maken van eigenschap (E4) uit Lemma 3.1.3. We concluderen dat w = A|y| − |y| ≥ 0.

(3.6)

We gaan bewijzen dat zelfs w = 0 door een tegenspraak af te leiden uit de veronderstelling dat w 6= 0. Omdat A > 0 volgt met (E1) uit Lemma 3.1.3 dat zowel Aw > 0 als dat A|y| > 0. Dit verklaart beide ongelijkheden in AA|y| > A|y| > 0.

(3.7)

Kennelijk is iedere entry van AA|y| groter dan de overeenkomstige entry van A|y|. Dus bestaat er een ε > 0 met 1 AA|y| > A|y| > 0. (3.8) 1+ε Schrijf nu A en z = A|y|. B= 1+ε Met deze notatie verandert (3.8) in Bz > z > 0. Maar dan is met (E2) uit Lemma 3.1.3 ook B 2 z = B(Bz) > Bz want B > 0, en met inductie zien we dat B k z > z > 0 voor alle k ∈ N. Echter ρ(A) 1 ρ(B) = = < 1, 1+ε 1+ε dus geeft Stelling 3.1.7 dat B k → 0 voor k → ∞. Dit is in tegenspraak met B k z > z > 0 voor alle k. Dus w = 0, oftewel, A|y| = |y|. Maar dan is x = |y| = 6 0 een eigenvector van A behorende bij een eigenwaarde λ = 1 van A, en uit Lemma 3.1.12 volgt tot slot dat x > 0.  Opmerking 3.1.14 Het feit dat B k → 0 is niet in tegenspraak met B k z > 0 voor alle k. Het is dus noodzakelijk om de ongelijkheid B k z > z > 0 te bewijzen in plaats van slechts B k z > 0. Dit verklaart de ogenschijnlijke grote hoeveelheid werk in bovenstaand bewijs.

82

HOOFDSTUK 3. NIET-NEGATIEVE LINEAIRE ALGEBRA

De eigenruimte van de eigenwaarde ρ(A) van A bevat dus een positieve vector x > 0. We laten zien dat alle andere eigenvectoren behorende bij ρ(A) hier veelvouden van zijn. Stelling 3.1.15 Laat A ∈ Rn×n en veronderstel dat A > 0. Dan is dim ker(A − ρ(A)I) = 1. Bewijs. Veronderstel wegens Lemma 3.1.11 zonder verlies van algemeenheid dat ρ(A) = 1. Uit Stelling 3.1.13 volgt dat er een x > 0 bestaat met Ax = x. Laat nu y 6= 0 met Ay = y. We tonen aan dat y een veelvoud is van x. Merk hiertoe op dat er een α ∈ R bestaat zodanig dat z = y + αx ≥ 0, terwijl z ook ten minste ´e´en entry gelijk aan nul heeft. Als nu z 6= 0 volgt uit Az = z en Lemma 3.1.12 dat z > 0, wat in tegenspraak is met het feit dat z ten minste ´e´en entry gelijk aan nul heeft. Dus z = 0 en dus is y = −αx een veelvoud van x.  Definitie 3.1.16 (Perronvector) Laat A ∈ Rn×n met A > 0. De unieke x > 0 waarvoor Ax = ρ(A)x en

e> x = 1, waarbij

e = e1 + · · · + en

de all-ones vector is, heet de Perronvector van A. Opmerking 3.1.17 Een van de bekendste en recent in de belangstelling staande Perronvectoren is de Google PageRank vector van Larry Page en Sergey Brin. Ter afronding van de Perron-Frobeniustheorie voor positieve matrices tot slot het volgende. Stelling 3.1.18 De enige eigenwaarde van 0 < A ∈ Rn×n met absolute waarde ρ(A) is ρ(A). Bewijs. Volgens Stelling 3.1.13 is ρ(A) ∈ σ(A). Resteert de uniciteit aan te tonen. Veronderstel op grond van Lemma 3.1.11 zonder verlies van algemeenheid dat ρ(A) = 1. Laat λ ∈ σ(A) met |λ| = 1. Dan bestaat er dus een y 6= 0 met Ay = λy. Hiervoor geldt net als in het bewijs van Steling 3.1.13 dat A|y| = |y| > 0. Per definitie van matrix-vectorvermenigvuldiging impliceren de respectievelijke gelijkheden A|y| = |y| en Ay = λy, dat voor alle k ∈ {1, . . . , n}, |yk | =

n X j=1

akj |yj | en λyk =

n X

akj yj

(3.9)

j=1

en dus, X n akj |yj | = |yk | = |λyk | = akj yj . j=1 j=1

n X

(3.10)

Nu geldt dat de absolute waarde |z1 + · · · + zn | van de som van n complexe getallen alleen gelijk is aan de som |z1 |+· · ·+|zn | van de absolute waarden als ze allemaal hetzelfde argument hebben, zoals ge¨ıllustreerd in Figuur 3.2.

0

∗

|z1 | + · · · + |zn | = |z1 + · · · + zn | ⇔

C

∗ ∗∗ φ ∗

φ = arg(z1 ) = · · · = arg(zn )

Figuur 3.2 Driehoeksgelijkheid in C alleen bij gelijke argumenten. Dus concluderen we uit (3.10) en het feit dat |y| > 0 dat yk = αk y1 voor zekere αk > 0 voor alle k ∈ {1, . . . , n}. Dus is y een (eventueel complex) veelvoud y1 α van een positieve vector α. Maar dan is ook α een eigenvector van A behorende bij eigenwaarde λ. En omdat Aα re¨eel is, gelijk is aan λα, en in het bijzonder positief, is λ ook positief en re¨eel. Hieruit volgt dat λ = 1, en dus is λ = 1 de enige eigenwaarde van A op de spectrale cirkel. 

3.1. PERRON-FROBENIUSTHEORIE

3.1.3

83

Von Mises-iteratie

De Von Mises-iteratie, ook wel machtsmethode genoemd, is een methode, al veel eerder gebruikt door Jacobi, om een eigenvector te berekenen horend bij de unieke eigenwaarde van A die het grootst is in absolute waarde, en waarvan de eigenruimte dimensie ´e´en heeft.

Richard von Mises (1883-1953) en Carl Jacobi (1804-1851) We bewijzen nu dat de Neumannrij (Ak )k∈N convergeert als ρ(A) = 1 en A > 0. Het bewijs maakt gebruik van de Neumann rij- en reeks uit Sectie 3.1.1 en van de Schurdecompositie uit Sectie 1.2.6 en illustreert als zodanig de onderlinge samenhang van diverse gereedschappen. Stelling 3.1.19 Laat A ∈ Rn×n met A > 0. Veronderstel dat ρ(A) = 1. Dan geldt dat lim Ak = uw>

(3.11)

k→∞

waarbij Au = u > 0 met kuk = 1 en A> w = w met w > 0. Bewijs. Omdat A > 0 is volgens Stelling 3.1.13 ρ(A) = 1 een eigenwaarde van A, en bestaat er een unieke positieve eigenvector u > 0 met kuk = 1 zo, dat Au = u. Dus bestaat er (zie Sectie 1.2.6) een Schurdecompositie van A van de vorm   1 b ∗ A = U T U waarbij T = , met U ∗ U = I en U e1 = u. 0 R De eigenwaarden van de bovendriehoeksmatrix R zijn de eigenwaarden van A ongelijk aan 1. Op grond van Stelling 3.1.18 zijn deze allemaal kleiner dan 1 in absolute waarde. Dus ρ(R) < 1. We berekenen nu machten van A,    k  k 1 b 1 b ∗ A = U U =U U ∗. 0 R 0 R k

Met volledige inductie kan eenvoudig worden aangetoond dat 

1 b 0 R

k

 =

1 b(I + R + · · · + Rk−1 ) 0 Rk

 .

Omdat ρ(R) < 1 volgt met behulp van Lemma 3.1.7 en Stelling 3.1.9 dat   1 b(I − R)−1 k U ∗ = U e1 v > U ∗ waarbij v > = [1, b(I − R)−1 ] lim A = U 0 0 k→∞

(3.12)

84

HOOFDSTUK 3. NIET-NEGATIEVE LINEAIRE ALGEBRA

en dus vinden we dat lim Ak = uw> waarbij

k→∞

u = U e1 en w> = v > U ∗ .

Daarnaast geldt kennelijk dat limk→∞ (A> )k = wu> en dus is w > 0 een eigenvector bij λ = 1 = ρ(A> ) van A> . . Gevolg 3.1.20 Als x ∈ Rn zodanig is dat w> x = α 6= 0, dat lim Ak x = u(w> x) = αu.

k→∞

Dus, de rij (Ak x)k≥0 convergeert naar een niet-triviaal veelvoud van de eigenvector bij λ = 1. Opmerking 3.1.21 Matrixvermenigvuldiging is associatief: (Ak )x = Ak−1 (Ax). Het is echter veel rekenwerk om A tot de k-de macht te verheffen en Ak te vermenigvuldigen met x. Effici¨enter is x1 = Ax uit te rekenen, dan x2 = Ax1 , tot en met xk = Axk−1 = Ak x. Het laatste vergt k matrix-vectorvermenigvuldigingen, het eerste k matrix-matrixvermenigvuldigingen. Het uiteindelijke resultaat is natuurlijk hetzelfde: xk = Ak x. Opmerking 3.1.22 De Google Pagerankvector wordt in de praktijk niet precies uitgerekend, maar in drie decimalen nauwkeurig benaderd met xk = Axk−1 = Ak x voor zekere k 0 dan heeft A een positieve eigenvector behorende bij een positieve eigenwaarde. Bewijs. Associeer met de matrix A > 0 de lineaire afbeelding LA :

Rn≥0 → Rn≥0 , x 7→ Ax

van het onbegrensde niet-negatieve orthant Rn≥0 naar zichzelf. Definieer S = {x ∈ Rn≥0 | e> x = 1}. Oftewel, S is het deel van het affiene hypervlak met vergelijking x1 + · · · + xn = 1 dat in Rn≥0 ligt. In Figuur 3.3 is S de driehoek in R3 met als hoekpunten de drie standaardbasisvectoren. Merk op dat S gesloten, begrensd, en convex is. Bekijk nu de continue afbeelding KA :

S→S:

x 7→

Ax e> Ax

=

LA (x) . > e LA (x)

Dan is KA continu als quoti¨ent van continue afbeeldingen. 

 0  0  1

 0  1  0 

R3≥0

KA : S → S x 7→



 1  0  0

Ax e> Ax

S

S = {x ∈ R3≥0 | e> x = 1}

Figuur 3.3: Dekpuntstelling van Brouwer toegepast op het domein S. Volgens Stelling 3.1.24 is er een x ∈ S is met KA (x) = x. Voor deze x geldt dus dat Ax = (e> Ax)x. Omdat x ∈ S geldt dat x ≥ 0 en x 6= 0. Omdat x ≥ 0 en x 6= 0 is Ax > 0. Omdat Ax = (e> Ax)x vinden we dus tot slot dat e> Ax > 0 en x > 0.  In plaats van alle Perron-Frobeniusstellingen opnieuw te bewijzen, richten we ons nu op de vraag welke overeenkomstige resultaten gelden voor de klasse van niet-negatieve matrices.

3.1.5

Niet-negatieve matrices als limiet van positieve matrices

We bekijken nu de niet-negatieve matrices A ≥ 0 die niet positief zijn. Met andere woorden, we gaan uit van tenminste ´e´en entry gelijk aan nul. De volgende observatie is triviaal.

86

HOOFDSTUK 3. NIET-NEGATIEVE LINEAIRE ALGEBRA

Opmerking 3.1.27 Ieder niet-negatieve n × n matrix A ≥ 0 is de limiet van een rij positieve matrices (Ak )k≥1 . Een voorbeeld van zo’n rij is 1 Ak = A + ee> > 0, k waarbij e = e1 + · · · + en de all-ones vector is. Sommige eigenschappen van positieve matrices blijken soms zelfs in de limiet niet meer op te gaan voor niet-negatieve matrices, zoals blijkt uit de volgende voorbeelden. Voorbeeld 3.1.28 Laat



0 A= 0 0

 0 0 . 0

1 0 0

(3.13)

Dan is ρ(A) = 0, wat inderdaad een limietgeval is van Lemma 3.1.11. Tevens is ρ(A) ∈ σ(A), net zoals in Stelling 3.1.13. Echter A heeft in contrast met Stelling 3.1.18 heeft A twee lineair onafhankelijke niet-negatieve eigenvectoren horend bij ρ(A). Voorbeeld 3.1.29 De matrix

 A=

0 1 1 0

 .

(3.14)

heeft twee verschillende eigenwaarden −1 en 1 op de spectrale cirkel, wat wezenlijk anders is dan voor positieve matrices, zie Stelling 3.1.18. Omdat     0 1 1 0 2k+1 2k , en A = A = 1 0 0 1 bestaat de limiet voor k → ∞ van Ak niet, in tegenstelling tot Stelling 3.1.19 voor positieve matrices. De limiet van Ak x bestaat alleen in het triviale geval x1 = x2 . Stelling 3.1.30 Laat A ∈ Rn×n , A ≥ 0. Dan bestaat er een 0 6= x ≥ 0 zo, dat Ax = ρ(A)x. Bewijs. Laat Ak = A + k1 ee> > 0 voor iedere k ∈ N. Schrijf ρk = ρ(Ak ) en laat pk > 0 de unieke Perronvector van Ak zijn, oftewel, Ak pk = ρk pk , e> pk = 1.

(3.15)

Omdat eigenwaarden continu zijn als functies van de entries van de matrix, zijn ook continue functies van die eigenwaarden, zoals de spectraalstraal, continu. Dus geldt dat lim ρk = lim ρ(Ak ) = ρ( lim Ak ) = ρ(A).

k→∞

k→∞

k→∞

(3.16)

n De verzameling van bijbehorende Perronvectoren {pk }∞ k=1 is bevat in [0, 1] en dus begrensd. ∞ Volgens de stelling van Bolzano-Weierstrass heeft {pk }k=1 een convergente deelrij {pk` }∞ `=1 , waarvoor dus geldt

lim pk` = p ≥ 0 en e> p = e> lim pk` = lim e> pk` = 1

`→∞

`→∞

`→∞

(3.17)

waaruit volgt dat p 6= 0. Tot slot vinden we omdat beide afzonderlijke limieten bestaan dat Ap = lim Ak` lim pk` = lim Ak` pk` = lim ρk` pk` = lim ρk` lim pk` = ρ(A)p. `→∞

`→∞

En dit bewijst de bewering.

`→∞

`→∞

`→∞

`→∞

(3.18) 

Opmerking 3.1.31 Stelling 3.1.30 bewijst niet dat de eigenvector p ≥ 0 van A ≥ 0 de limiet is van de rij (pk )k∈N van Perronvectoren van de matrices Ak , noch dat deze uniek is.

3.1. PERRON-FROBENIUSTHEORIE

3.1.6

87

Reducibele en irreducibele niet-negatieve matrices

Om verdere resultaten te kunnen bewijzen over niet-negatieve matrices introduceren wat enkele begrippen uit de grafentheorie binnen de lineaire algebra. Definitie 3.1.32 (Verbindingsgraaf ) Laat (aij ) = A ∈ Rn×n . De gerichte graaf G(A) = (V, E) bestaande uit de punten (vertices) V = {1, . . . , n} en de pijlen (edges) E ⊂ V × V met (i, j) ∈ E als en alleen als aij 6= 0 heet de verbindingsgraaf van A. Merk op dat deze definitie loops toestaat: pijlen van een punt naar zichzelf. Grafen vormen een wiskundige structuur die voor het eerst werd bestudeerd door Euler.

Leonhard Euler (1707-1783) Omgekeerd kunnen we met iedere gerichte graaf een matrix associ¨eren. Definitie 3.1.33 (Verbindingsmatrix) Zij G = (V, E) met V = {1, . . . , n} een gerichte graaf. De matrix (mij ) = M(G) ∈ {0, 1}n×n waarvoor mij = 1 als en alleen als er in G een pijl van vertex i naar vertex j gaat heet de verbindingsmatrix van G. Dus mij = 1 ⇔ (i, j) ∈ E. Voorbeeld 3.1.34 Hier tekenen we de verbindingsgraaf G(A) van de gegeven matrix A en de verbindingsmatrix M(G(A)) van die graaf.  0 −1 0 0  0 0 1 −2   A=  0 0 0 1  3 1 0 0

1



2



0  0 M(G(A)) =   0 1

G(A) =

4

1 0 0 1

0 1 0 0

 0 1   1  0

3

Merk op dat A = M(G(A)) als en alleen als A een 0/1-matrix is, oftewel, als A ∈ {0, 1}n×n . Definitie 3.1.35 (Wandeling) Zij G = (V, E) een gerichte graaf en p ∈ N. Dan heet een rij (v0 , . . . , vp ) ∈ V p+1 van punten in G een wandeling van lengte p van v0 naar vp als (vk , vk+1 ) ∈ E voor alle k ∈ {0, . . . , p − 1}. Opmerking 3.1.36 De wandelingen in G = (V, E) van lengte 1 zijn precies de edges e ∈ E. Voorbeeld 3.1.37 Er zijn precies tien wandelingen van lengte twee in de verbindingsgraaf G(A) van A uit Voorbeeld 3.1.34, te weten (1, 2, 3), (1, 2, 4), (2, 3, 4), (2, 4, 1), (2, 4, 2), (3, 4, 1), (3, 4, 2), (4, 1, 2), (4, 2, 3), (4, 2, 4). Dit zijn uiteraard alle mogelijkheden om een wandeling van lengte 1 met 1 stap uit te breiden.

88

HOOFDSTUK 3. NIET-NEGATIEVE LINEAIRE ALGEBRA

De volgende stelling veralgemeniseert de observatie uit het voorgaande voorbeeld. Stelling 3.1.38 Zij G een graaf met verbindingsmatrix B = M(G). Schrijf w(i, j, k) voor het aantal verschillende wandelingen in G van i naar j van lengte k. Dan geldt dat k w(i, j, k) = e> i B ej .

(3.19)

Het rechterlid is de entry van B k op positie (i, j). Bewijs. Laat `1 , . . . , `p de vertices zijn die een wandeling van lengte ´e´en verwijderd zijn van i, oftewel, de directe buren van i. Deze buren zijn als volgt verkrijgbaar uit de i-de rij van B, > e> i B = (e`1 + · · · + e`p ) .

(3.20)

w(i, j, k) = w(`1 , j, k − 1) + · · · + w(`p , j, k − 1).

(3.21)

Daarnaast geldt natuurlijk dat

Veronderstel nu als inductie-hypothese dat (3.19) correct is voor alle wandelingen van lengte k − 1, oftewel, dat k−1 w(i, j, k − 1) = e> ej (3.22) i B voor alle i, j. Dan vinden we in combinatie met (3.21) en (3.20) dat k−1 k−1 k−1 ej = (e`1 + · · · + e`p )> B k−1 ej = e> ej w(i, j, k) = e> ej + · · · + e> i BB `1 B `p B

(3.23)

en dus is (3.19) ook geldig voor het bepalen van de hoeveelheid verschillende wandelingen van lengte k. Omdat de inductie-basis is verwoord in Opmerking 3.1.36 bewijst dit de stelling.  Het bewijs van Stelling 3.1.38 is gevisualiseerd in Figuur 4.3.

`2

i

> > e> i B = e`1 + · · · + e`p

k−1 e e> j `1 B

`1

k−1 e e> j `2 B

j k−1 > k−1 e = e> j `1 B
ej +· · ·+e`p B > k−1 > k ei B B ej = ei B ej

.. . `p

k−1 e e> j `p B

Figuur 4.3 Illustratie van het bewijs van Stelling 3.1.38. Voorbeeld 3.1.39 Keren we terug naar Voorbeeld 3.1.34, dan berekenen we dat 

0  0 2 M(G(A)) =   0 1

1 0 0 1

0 1 0 0

 0 0  0 1   1  0 0 1

1 0 0 1

0 1 0 0

  0 0  1 1  = 1   1 0 0

0 1 1 1

1 0 0 1

 1 1  . 0  1

(3.24)

De entries ongelijk aan nul in M(G(A))2 komen overeen met de tien wandelingen van lengte twee in G(A) die zijn opgesomd in Voorbeeld 3.1.37.

3.1. PERRON-FROBENIUSTHEORIE

89

Definitie 3.1.40 (Drager) De drager supp(A) van een matrix (aij ) = A ∈ Kn×k is de verzameling van alle paren (i, j) waarvoor aij 6= 0. Opmerking 3.1.41 Als A ≥ 0 dan is supp(A) = supp(M(G(A))). Ook geldt dat de dragers van M(G(A))k en Ak dan aan elkaar gelijk zijn. Zo geldt bijvoorbeeld schematisch dat      0 +  0 0  0 0 + +

0 0 0 + + +  0 0 0 +  0 0 0 0 + +

0 0 0 0 + + + +   + + 0 +  = , 0 +   + + 0 0  0 0 0 + + +

ongeacht de exacte waarden van de positieve entries. Dit komt doordat voor alle x ≥ 0, y ≥ 0 het inproduct x> y ≥ 0, en dat x> y = 0 als en alleen als supp(x) ∩ supp(y) = ∅. We formuleren dit resultaat zonder verder bewijs in de volgende stelling. Stelling 3.1.42 Laat k ∈ N, A, B ≥ 0. Als supp(A) = supp(B), dan supp(Ak ) = supp(B k ). We introduceren nu tot slot een combinatorische eigenschap van matrices die de PerronFrobeniustheorie voor positieve matrices deels laat generaliseren voor niet-negatieve matrices. Definitie 3.1.43 (Reducibiliteit) Gegeven A ∈ Rn×n met verbindingsgraaf G(A). Als er in G(A) voor ieder paar i, j ∈ {1, . . . , n} een wandeling van i naar j bestaat dan heet A irreducibel. Als A niet irreducibel is, heet A reducibel. Gevolg 3.1.44 Een niet-negatieve matrix A ∈ Rn×n is irredicibel als en alleen als voor ieder k paar i, j ∈ {1, . . . , n} er een k ≤ n bestaat zo, dat e> i A ej > 0. Bewijs. Dit volgt uit Stelling 3.1.38 in combinatie met Stelling 3.1.42 (want A is niet noodzakelijkerwijs gelijk aan M(G(A))) en de observatie dat als er een wandeling bestaat van i naar j in G(A), dan bestaat er ook een van lengte ten hoogste n.  Opmerking 3.1.45 Irreducibiliteit van A ≥ 0 impliceert niet dat er een N ∈ N bestaat zo, dat Ak > 0 voor alle k ≥ N . Zie bijvoorbeeld de duidelijk irreducibele matrix A horend bij de graaf of drie vertices 1, 2, 3 met pijlen 1 → 2, 2 → 3 en 3 → 1,       0 1 0 0 0 1 1 0 0 A =  0 0 1  , A2 =  1 0 0  , A3 =  0 1 0  , A4 = A. 1 0 0 0 1 0 0 0 1 k Dus is (e> i A ej )k∈N is een 3-periodieke rij voor ieder paar i, j ∈ {1, . . . , n}, en dus is voor ieder paar i, j ∈ {1, . . . , n} tenminste ´e´en van de matrices A, A2 , A3 positief op positie (i, j).

Gevolg 3.1.46 0 ≤ A ∈ Rn×n is irreducibel als en alleen als A + A2 + . . . + An > 0. De volgende stelling bewijst hetzelfde voor een eenvoudiger ogend polynoom in A. Stelling 3.1.47 0 ≤ A ∈ Rn×n met n ≥ 2 irreducibel als en alleen als (I + A)n−1 > 0.

90

HOOFDSTUK 3. NIET-NEGATIEVE LINEAIRE ALGEBRA

Bewijs. Veronderstel dat A ≥ 0 irreducibel is. Laat i 6= j. Per definitie bestaat er een wandeling van i naar j. De kortste wandeling van i naar j heeft uiteraard lengte ten hoogste n − 1. Definieer nu de graaf G als G(A) met daaraan toegevoegd voor iedere vertex een extra pijl naar zichzelf indien deze niet al bestaat. Dan heeft G de volgende eigenschappen: • G = G(I + A); • er bestaat een wandeling in G van lengte n − 1 van iedere vertex i naar zichzelf; • ieder wandeling van lengte ` < n − 1 van i naar j kan worden aangevuld tot lengte n − 1. Omdat er in G(A + I) voor ieder tweetal punten i, j ∈ {1, . . . , n} een wandeling van lengte precies n−1 bestaat van i naar j, volgt uit Stelling 3.1.38 dat alle entries van [M(G(A+I))]n−1 positief zijn. Stelling 3.1.42 geeft nu dat ook (A + I)n−1 > 0. Dit bewijst de bewering in de ene richting. Om de te bewijzen dat A irreducibel is als (A + I)n−1 > 0, merk op dat dit laatste impliceert dat de verbindingsgraaf G(A + I) van A + I voor ieder paar i, j ∈ {1, . . . , n} een wandeling bevat van i naar j, en in het bijzonder voor elk paar i, j met i 6= j. De verbindingsgraaf G(A) van A ontstaat uit G(A + I) door het eventueel verwijderen van een aantal pijlen van een punt i naar zichzelf. Dit verwijdert wellicht wandelingen van i naar zichzelf van lengte ´e´en. Echter, als n ≥ 2 dan is er een wandeling van i naar een punt j 6= i, en een wandeling van j naar i, en dus ook een wandeling van i naar zichzelf.  Opmerking 3.1.48 De 1 × 1 matrix A = [0] is reducibel. Echter, (I + A)0 = (1 + 0)0 = 10 = 1 > 0. Dit laat zien dat de aanname dat n ≥ 2 in de vorige stelling niet kan worden gemist.

3.1.7

Perron-Frobeniustheorie voor irreducibele niet-negatieve matrices

Laat A ≥ 0. Veronderstel dat A irreducibel is. Dan weten we dat B = (A+I)n−1 > 0. Dus op B is de Perron-Frobeniustheorie voor positieve matrices van toepassing, en we concluderen: • Lemma 3.1.11: 0 < ρ(B) ∈ σ(B), • Stelling 3.1.13: er bestaat een x > 0 waarvoor Bx = ρ(B)x, • Stelling 3.1.15: de dimensie van de kern van B − ρ(B)I is gelijk aan ´e´en, • Stelling 3.1.18: ρ(B) is de enige eigenwaarde van B die op de spectrale cirkel ligt. We destilleren hieruit de volgende informatie over de matrix A zelf. Lemma 3.1.49 Laat 0 ≤ A ∈ Rn×n en B = (I + A)n−1 . Dan geldt λ ∈ σ(A)

⇒

(1 + λ)n−1 ∈ σ(B).

(3.25)

Bewijs. Laat Av = λv. Dan is (I + A)v = v + λv = (1 + λ)v, en dus (I + A)(I + A)v = (I + A)(1 + λ)v = (1 + λ)2 v. Een eenvoudig inductie-argument bewijst nu de bewering.  Lemma 3.1.50 Laat 0 ≤ A ∈ Rn×n . Veronderstel dat A irreducibel is. Laat B = (I +A)n−1 . Dan geldt dat ρ(B) = (1 + ρ(A))n−1 . (3.26)

3.2. DUBBELSTOCHASTISCHE MATRICES EN DE PERMANENT

91

Bewijs. De eigenwaarden van B zijn gelijk aan (1 + λ)n+1 , met λ ∈ σ(A), en dus is ρ(B) = max |(1 + λ)n−1 | = ( max |1 + λ|)n−1 = (1 + ρ(A))n−1 . λ∈σ(A)

λ∈σ(A)

De tweede gelijkheid geldt omdat er een λ ∈ σ(A) bestaat zo, dat |1 + λ| ≥ 1, namelijk λ = ρ(A) ∈ σ(A). De derde geldt omdat als de schijf |z| ≤ ρ ´e´en naar rechts verschuift in C, het punt met grootste modulus in de verschoven schijf het punt z = 1 + ρ is.  Lemma 3.1.51 Laat 0 ≤ A ∈ Rn×n . Veronderstel dat A irreducibel is. Dan is ρ(A) > 0. Bewijs. Omdat A irreducibel is, bestaat er wegens Definitie 3.1.43 een wandeling van zekere positieve lengte k van vertex 1 naar 1 in de verbindingsgraaf G(A) van A. Maar dan bestaat er ook een wandeling van 1 naar 1 van lengte `k voor alle ` ∈ N. Wegens Stelling 3.1.38 geldt k` nu dat e>  1 A e1 > 0 voor alle ` ∈ N. Dus is A niet nilpotent, en dus is ρ(A) > 0. Stelling 3.1.52 Laat 0 ≤ A ∈ Rn×n . Als A irreducibel is dan bestaat er een v > 0 zo, dat Av = ρ(A)v. Tevens is dim(ker(A − ρ(A)I)) = 1. Bewijs. Volgens Stelling 3.1.30 is ρ(A) een eigenwaarde van A en bestaat er een v ≥ 0 zo, dat Av = ρ(A)v. Laat nu B = (I + A)n−1 . Dan is Bv = (1 + ρ(A))n−1 v = ρ(B)v wegens Lemma 3.1.49 en Lemma 3.1.50 en dus is v een veelvoud van de positieve Perronvector van B. Deze v is dus een positieve eigenvector van A horende bij eigenwaarde ρ(A). Tot slot, stel dat ook Aw = ρ(A)w voor zekere w ∈ Rn . Dan volgt met Lemma 3.1.49 en Lemma 3.1.50 dat Bw = ρ(B)w. Omdat volgens Stelling 3.1.15 dim(ker(B − ρ(B)I)) = 1 zijn v en w lineair afhankelijk. Dus is ook de kern van A − ρ(A)I ´e´endimensionaal.  Opmerking 3.1.53 De eigenschap dat een positieve matrix precies ´e´en eigenwaarde op de spectrale cirkel heeft, geldt niet voor irreducibele niet-negatieve matrices. De matrix B uit (3.13) die twee verschillende eigenwaarden heeft op de spectrale cirkel is immers irreducibel.

3.2

Dubbelstochastische matrices en de permanent

Een belangrijke klasse van niet-negatieve matrices komt voort uit het vakgebied van de stochastiek. De entries representeren bepaalde kansen en liggen daarmee in het interval [0, 1]. De naam Markov is onlosmakelijk met dergelijke matrices verbonden. Verderop komen we ook een belangrijk resultaat tegen van K¨onig.

´nes K¨ Andrej Markov (1856-1922) en De onig (1884-1944)

92

HOOFDSTUK 3. NIET-NEGATIEVE LINEAIRE ALGEBRA

Schrijf zoals gebruikelijk e = e1 + · · · + en voor de som van de standaardbasisvectoren in Rn . Dan is Ae de vector met rijsommen van A, en e> A de vector met kolomsommen van A. Definitie 3.2.1 (Stochastische matrices) Een niet-negatieve matrix S heet rijstochastisch als Se = e en kolomstochastisch als e> S = e> , en dubbelstochastisch indien beide het geval is. We schrijven Ωn ⊂ Rn×n voor de deelverzameling van dubbelstochastische matrices. Voorbeeld 3.2.2 De eenvoudigste voorbeelden van dubbelstochastische mutatiematrices. Voor n = 3 zijn dit de zes matrices          1 0 0 1 0 0 0 1 0 0 1 0 0 0  0 1 0 ,  0 0 1 ,  1 0 0 ,  0 0 1 ,  1 0 0 0 1 0 1 0 0 0 1 1 0 0 0 1

matrices zijn de per   1 0 0 1 0 ,  0 1 0 . 0 1 0 0

Andere voorbeelden van dubbelstochastische matrices zijn magische vierkanten gedeeld door hun magische som, en de constante matrices Cn waarvan alle entries gelijk zijn aan 1/n,       16 2 3 13 8 1 6 1 1 1   1 1  1  5 11 10 8  3 5 7  en M4 = , C3 =  1 1 1  . M3 =   9 7 6 12 15 34 3 4 9 2 1 1 1 4 14 15 1 Opmerking 3.2.3 Dubbelstochastische matrices spelen verrassend vaak een belangrijke rol in deelgebieden van de wiskunde die schijnbaar niets met stochastiek van doen hebben. De permutatiematrices uit bovenstaand voorbeeld blijken de elementaire bouwstenen te zijn van alle dubbelstochastische matrices, en verdienen daarom een formele definitie. Definitie 3.2.4 (Permutatiematrices) Schrijf Sn voor de groep van alle bijecties σ : {1, . . . , n} → {1, . . . , n} :

i 7→ σ(i),

(3.27)

oftewel, Sn is de symmetrische groep op {1, . . . , n}. Voor gegeven σ ∈ Sn is Πσ = [eσ(1) | . . . |eσ(n) ]

(3.28)

de permutatiematrix bestaande uit de door σ gepermuteerde standaard basisvectoren. Opmerking 3.2.5 In Definitie 3.2.4 wordt impliciet een groepshomomorfisme gedefinieerd, h : Sn → GLn (R) :

σ 7→ Πσ .

Het is namelijk niet moeilijk om na te gaan dat voor alle τ, σ ∈ Sn , h(τ ◦ σ) = Πτ ◦σ = Πτ Πσ = h(τ )h(σ). De studie van groepshomomorfismes G → GL(V ) met onder andere als doel de structuur van een groep G te bestuderen binnen een vertrouwdere context heet representatietheorie. De volgende observaties zijn nuttig voor het begrip van dubbelstochastische matrices.

3.2. DUBBELSTOCHASTISCHE MATRICES EN DE PERMANENT

93

Lemma 3.2.6 Laat σ, τ ∈ Sn en M, N ∈ Ωn . Dan geldt Πσ M Πτ ∈ Ωn en M N ∈ Ωn . Oftewel, de verzameling Ωn van dubbelstochastische matrices is gesloten onder rij- en kolompermutaties en vormt een halfgroep ten opzichte van de gebruikelijke matrixvermenigvuldiging. Bewijs. De tweede bewering volgt doordat N e = e en e> M = e> en dus, M N e = M e = e en e> M N = e> N = e> . De eerste bewering is een speciaal geval van de tweede.



Opmerking 3.2.7 Veronderstel dat M ∈ Ωn inverteerbaar is. Dan geldt natuurlijk dat M −1 e = e en e> M −1 = e> . Echter, M −1 ∈ Ωn als en alleen als M een permutatiematrix is. Definitie 3.2.8 (Convexe combinatie) Zij V een re¨ele vectorruimte. Gegeven v1 , . . . , vm ∈ V heet v een convexe combinatie van v1 , . . . , vm als geldt dat v=

m X

µj vj waarbij

j=1

m X

µj = 1 en ∀j ∈ {1, . . . , n} : µj ≥ 0.

(3.29)

j=1

Iedere convexe combinatie is dus een specifieke lineaire combinatie van gegeven vectoren. Lemma 3.2.9 Laat n ∈ N. Iedere convexe combinatie X µ σ Πσ , µσ ≥ 0 (σ ∈ Sn ) en M=

X

µσ = 1

(3.30)

σ∈Sn

σ∈Sn

van permutatiematrices is dubbelstochastisch. Bewijs. Het is duidelijk dat M ≥ 0, en bovendien geldt dat X X Me = µ σ Πσ e = µσ e = e σ∈Sn

σ∈Sn

en e> M = e>

X σ∈Sn

µ σ Πσ =

X

µσ e> Πσ =

σ∈Sn

X

µσ e> = e> ,

σ∈Sn

waarbij we gebruikten dat Πσ dubbelstochastisch is. Dit bewijst de bewering.

3.2.1



De stelling van Birkhoff-Van Neumann

De omgekeerde implicatie van Lemma 3.2.9 lijk intu¨ıtief duidelijk, maar is desondanks toch een behoorlijk pittige stelling

Garrett Birkhoff (1911-1996) en John von Neumann (1903-1957)

94

HOOFDSTUK 3. NIET-NEGATIEVE LINEAIRE ALGEBRA

Hij is vernoemd naar Garrett Birkhoff en John Von Neumann. Stelling 3.2.10 (Birkhof-Von Neumann) Zij M een dubbelstochastische n × n matrix. Dan is X X M= µ σ Πσ met µσ ≥ 0 en µσ = 1. (3.31) σ∈Sn

σ∈Sn

Oftewel, iedere dubbelstochastische matrix is een convexe combinatie van permutatiematrices. Het bewijs van deze steling vereist flink wat wat voorbereiding. Deze voorbereiding motiveren we eerst door het bewijs met een voorbeeld aannemelijk te maken. Definitie 3.2.11 (Diagonaal (combinatorisch)) Laat A ∈ Kn×n met entries aij . Binnen het wiskundige deelgebied van de combinatoriek heet voor iedere σ ∈ Sn de deelverzameling dσ = {a1σ(1) , . . . , anσ(n) } een diagonaal van A. Dit generaliseert het concept van de gebruikelijke (hoofd-)diagonaal. Als dσ uit positieve getallen bestaat, noemen we dσ een positieve diagonaal. Opmerking 3.2.12 Helaas sluit deze definitie niet heel mooi aan op Definitie 3.2.4, in de −1 zin dat dσ niet precies de positieve diagonaal van Πσ is, maar die van Π> σ = Πσ = Πσ −1 . Dit zou natuurlijk eenvoudig rechtgezet kunnen worden door de definitie van diagonaal aan te passen tot dσ = {aσ(1)1 , . . . , aσ(n)n } maar om historische redenen kiezen we ervoor dat hier niet te doen. Voorbeeld 3.2.13 Beschouw het 3 × 3 magische aan 15,  8 1  M= 3 5 4 9

vierkant met rij- en kolomsommen gelijk  6 7 . 2

De matrix M heeft zes diagonalen in de zin van Definitie 3.2.11. We zien dat bijvoorbeeld de hoofddiagonaal 8, 5, 2 positief is, met minimum element 2. Dus is M schrijven als 2I + N , 

     8 1 6 2 0 0 6 1 6 M =  3 5 7  =  0 2 0  +  3 3 7  = 2I + N, 4 9 2 0 0 2 4 9 0 waarbij N niet-negatief is, en de rijen en kolommen van N allemaal optellen tot 13 en de drager van N strict kleiner is dan die van M . De hoofddiagonaal van N is niet positief, maar de diagonaal {6, 7, 9} wel, en dus is N = 6J + P , 

     6 1 6 6 0 0 0 1 6 N =  3 3 7  =  0 0 6  +  3 3 1  = 6J + P, 4 9 0 0 6 0 4 3 0

3.2. DUBBELSTOCHASTISCHE MATRICES EN DE PERMANENT waarbij P niet-negatief is met rij- en kolomsommen N . Zo doorgaande vinden we      1 0 0 1 0 0 0 0      M =2 0 1 0 +6 0 0 1 +3 0 1 0 0 1 0 1 0 1 0

95

gelijk aan 7, en kleinere drager heeft dan      1 0 0 1 0 1 0 0  + 3 1 0 0  +  0 0 1  0 0 1 0 1 0 0

en dus hebben we M geschreven als som van positieve veelvouden van permutatiematrices. De hier gevolgde strategie ligt niet uniek vast, maar berust op keuzes voor positieve diagonalen. De strategie in het voorgaande voorbeeld is succesvol als iedere niet-negatieve matrix waarvan alle rijen en kolommen optellen tot hetzelfde positieve getal, een positieve diagonaal heeft. Om dit te bewijzen bekijken we nu eerst een stelling over niet-negatieve matrices zonder positieve diagonalen. Dergelijke matrices bevatten noodzakelijkerwijs behoorlijk wat nullen. Voorbeeld 3.2.14 Het gonaal hebben:  1  1 0

is eenvoudig na te gaan dat de volgende matrices geen positieve dia     1 1 1 1 1 0 1 1 1 1  en  0 0 1  en  0 1 1  . 0 0 0 0 1 0 1 1

Dit komt doordat deze matrices een k × ` blok met nullen hebben, dat zo groot is (namelijk k + ` = 4 = n + 1), dat de k rijen naast dit blok in minder dan k kolommen liggen, en er dus geen positieve diagonaal langs dit blok met nullen gelegd kan worden. Opmerking 3.2.15 Laat σ, τ ∈ Sn . Als A ∈ Rn×n geen positieve diagonaal heeft, dan heeft ook Πσ AΠτ geen positieve diagonaal. Stelling 3.2.16 (Frobenius-K¨ onig) Een niet-negatieve n × n matrix A heeft geen positieve diagonaal als en alleen als er indexverzamelingen {i1 , . . . , ik } en {j1 , . . . , j` } bestaan met k + ` = n + 1 waarvoor aij = 0 indien i ∈ {i1 , . . . , ik } en j ∈ {j1 , . . . , j` }. Bewijs. Veronderstel op grond van Opmerking 3.2.15 zonder verlies van algemeenheid dat   B C A= met 0 ∈ Rk×` , waarbij k + ` = n + 1. (3.32) 0 D De matrix D met k rijen heeft wegens k + ` = n + 1 minder dan k kolommen. Laat nu dσ een diagonaal van A zijn. De laatste k entries van dσ staan (per definitie) in k verschillende kolommen van A. Dus tenminste ´e´en van die entries staat niet in D en dus heeft A in (3.32) geen positieve diagonaal. We bewijzen nu de omgekeerde bewering met inductie. Als A een niet-negatieve 1 × 1 matrix is zonder positieve diagonaal, volgt dat A = [0] en heeft A inderdaad een k × ` deelmatrix gelijk aan nul met k + ` = n + 1. Als inductiehypothese nemen we aan dat iedere niet-negatieve (n − 1) × (n − 1) matrix zonder positieve diagonaal een p × q deelmatrix gelijk aan nul heeft met p + q = n. Laat nu A ∈ Rn×n niet-negatief zijn en veronderstel dat A geen positieve diagonaal heeft. Als A de nulmatrix is, is er niets te bewijzen. Neem daarom zonder verlies van algemeenheid aan dat de entry a11 van A positief is en schrijf   a11 c> A= . (3.33) b B

96

HOOFDSTUK 3. NIET-NEGATIEVE LINEAIRE ALGEBRA

Omdat a11 > 0 en A geen positieve diagonaal heeft, volgt dat B geen positieve diagonaal heeft. Dus heeft B een p × q deelmatrix gelijk aan nul met p + q = n. Zonder verlies van algemeenheid veronderstellen we dit blok rechts-onder in B. Dus:   E F A= G 0 waarbij G ∈ Rp×p en F ∈ Rq×q kennelijk vierkante matrices zijn. Als dG en dF diagonalen zijn van G en F , dan is dG ∪ dF een diagonaal van A. Omdat A geen positieve diagonaal heeft impliceert dit dat tenminste ´e´en van de matrices F en G geen positieve diagonaal heeft. Neem weer zonder verlies van algemeenheid aan dat G geen positieve diagonaal heeft. De inductiehypothese laat zien dat G dan een s × t nulblok heeft met s + t = p + 1. Samen met het nulblok rechts van G geeft dit het gevraagde k × ` blok nullen in A met k + ` = n + 1.  Gevolg 3.2.17 Laat M ∈ Ωn . Dan heeft M een positieve diagonaal. Bewijs. Laat M ≥ 0 en veronderstel dat M geen positieve diagonaal heeft. De Stelling van Frobenius-K¨ onig 3.2.16 laat zien dat de rijen en kolommen van M dan gepermuteerd kunnen worden tot   A B Π1 M Π2 = , (3.34) 0 D waarbij D p rijen heeft en q < p kolommen. Als de rijen van D optellen tot ´e´en, tellen alle entries van D op tot p. Maar dan telt minstens ´e´en kolom van D op tot ten minste p/q > 1. Hieruit volgt dat de matrix in (3.34) niet dubbelstochastisch is, en dus M 6∈ Ωn .  Na al deze voorbereiding kunnen we nu de Stelling van Birkhoff-Von Neumann bewijzen. We doen dit middels een eindig inductie-argument naar de grootte van de drager. Bewijs. Omdat iedere M ∈ Ωn wegens Gevolg 3.2.17) een positieve diagonaal heeft, bestaat de drager van M uit minimaal n elementen. Als inductiebasis beschouwen we het geval dat de drager van M ∈ Ωn uit n elementen bestaat. Duidelijk is dat M dan een permutatiematrix is. Veronderstel nu als inductiehypothese dat iedere M ∈ Ωn waarvan de drager uit q elementen bestaat, met n ≤ q ≤ p te schrijven is als convexe combinatie van maximaal p − (n − 1) permutatiematrices. Beschouw nu een M ∈ Ωn met een drager van p + 1 elementen. Dan heeft M wegens Gevolg 3.2.17 een positieve diagonaal dσ . Het minimale element d∗σ van deze diagonaal is uiteraard positief, maar ook kleiner dan 1 omdat M behalve de diagonaal dσ nog minstens ´e´en entry groter dan nul heeft. Laat nu  1  ∗ > N= M − d Π σ σ . 1 − d∗σ Het is eenvoudig na te gaan dat N ∈ Ωn , en dat N een drager heeft met maximaal p elementen. Volgens de inductiehypothese geldt dat p−(n−1)

N=

X j=1

p−(n−1)

µj Πj met

X

µj = 1 en mj ≥ 0, j ∈ {1, . . . , p − (n − 1)},

j=1

waarbij sommige uj mogelijk gelijk aan nul zijn. En dus is ∗ M = d∗σ Π> σ + (1 − dσ )N

3.2. DUBBELSTOCHASTISCHE MATRICES EN DE PERMANENT

97

en dit is een convexe combinatie van ten hoogste p + 1 − (n − 1) permutatiematrices.



Omdat bovenstaand bewijs een sterker resultaat is dan de bewering in Stelling 3.2.10, scherpen we deze stelling nog wat aan tot de volgende. Stelling 3.2.18 (Birkhof-Von Neumann) Laat M ∈ Ωn . Veronderstel dat M een drager van p elementen heeft. Dan is p−(n−1)

M=

X

p−(n−1)

µσj Πσj

met µσj ≥ 0 en

j=1

X

µσj = 1.

(3.35)

j=1

Iedere M ∈ Ωn is dus een convexe combinatie van hooguit n2 − n + 1 permutatiematrices. Bovenstaande kan deels geherformuleerd worden in termen van de permanent van een matrix.

3.2.2

De permanent van een matrix

De definitie van de permanent van een matrix heeft veel weg van die van de determinant. Definitie 3.2.19 (Permanent) De permanent per(A) van een n × n matrix A = (aij ) is het getal X a1σ(1) · a2σ(2) · . . . · anσ(n) . (3.36) per(A) = σ∈Sn

De permanent is dus de som van alle diagonaalproducten van een matrix, waarbij we met het diagonaalproduct van een diagonaal dσ het product van alle getallen in dσ bedoelen. Opmerking 3.2.20 Als A ∈ {0, 1}n×n is per(A) het aantal positieve diagonalen van A. Als A niet-negatief is dan is per(A) > 0 als en alleen als A een positieve diagonaal heeft. Voorbeeld 3.2.21 Voor 2 × 2 matrices A is per(A) = a11 a22 + a12 a21 terwijl voor 3 × 3 matrices A per(A) = a11 a22 a33 + a11 a23 a32 + a12 a21 a33 + a12 a23 a31 + a13 a21 a32 + a13 a22 a31 .

(3.37)

Opmerking 3.2.22 De permanent is net als de determinant een voorbeeld van een Schurfunctie. Dat is een matrixfunctie van de vorm X f (σ)a1σ(1) · a2σ(2) · . . . · anσ(n) , σ∈Sn

waarbij f : Sn → C een groepshomomorfisme is. Dit homomorfisme is voor de permanent het triviale homomorfisme σ 7→ 1 en voor de determinant is het σ 7→ sign(σ). We kunnen enkele resultaten uit Sectie 3.2 herformuleren middels de permanent. Zo laat de Stelling 3.2.16 van Frobenius-K¨ onig zien wanneer de permanent van een matrix nul is. Net als voor de determinant heeft dat een duidelijke, in dit geval combinatorische, interpretatie.

98

HOOFDSTUK 3. NIET-NEGATIEVE LINEAIRE ALGEBRA

Stelling 3.2.23 (Frobenius-K¨ onig) Laat A ≥ 0. Dan is per(A) = 0 als en alleen als er permutaties σ, τ ∈ Sn bestaan zo, dat   B C Πσ AΠτ = 0 D en waarin de nulmatrix afmetingen k × ` heeft met k + ` = n + 1. Gevolg 3.2.17 wordt in de nieuwe terminologie het volgende. Stelling 3.2.24 Voor alle M ∈ Ωn geldt dat per(M ) > 0. De volgende aanscherping van dit laatste resultaat vermelden we om historische redenen: hij werd in eerste instantie in 1926 als vermoeden geformuleerd door Van der Waerden. Schrijf zoals eerder Cn voor de matrix in Ωn waarvan alle entries gelijk zijn aan 1/n. Stelling 3.2.25 Voor alle M ∈ Ωn geldt per(M ) ≥ per(Cn ) = n−n n!. De hier geformuleerde ongelijkheid lijkt niet onaannemelijk maar werd pas in 1980 bewezen en heeft ervoor gezorgd dat de permanent enkele decennia uitvoerig onder de loep is genomen, ondanks dat hij lang daarvoor al ge¨ıntroduceerd werd door Augustin-Louis Cauchy.

Augustin-Louis Cauchy (1789-1857), Bartel Leendert van der Waerden (1903-1996), Herbert John Ryser (1923-1985), en Henryk Minc (1919-2013)

E´en van de ontwikkelingen was het algoritme van Ryser in Sectie 3.2.5, tot op heden ´e´en van de snelste manieren om de permanent van een matrix te berekenen. Het naslagwerk Permanents van Henryk Minc is een beroemd boek dat vrijwel alleen over de permanent gaat.

3.2.3

De permanent versus de determinant

De permanent lijkt sterk op de determinant. Zo geldt bijvoorbeeld dat • per(I) = det(I) = 1 waarbij I de identiteitsmatrix is; • de permanent en de determinant zijn lineair in ieder van de rijen. Laat nu σ ∈ Sn een transpositie zijn, oftewel, het omwisselen van twee elementen. Dan geldt det(Πσ A) = − det(A) maar per(Πσ A) = per(A).

(3.38)

Dit ogenschijnlijk onschuldige onderscheid tussen beide heeft verstrekkende consequenties. Zo is de permanent van een matrix met twee gelijke rijen niet altijd nul. Wel is de permanent net als de determinant te berekenen door rij- en/of kolom-ontwikkeling.

3.2. DUBBELSTOCHASTISCHE MATRICES EN DE PERMANENT

99

Voorbeeld 3.2.26 Laat 

 1 0 4 A= 2 1 1  3 2 1 dan geldt dat  per(A) = 1 · per

1 1 2 1





2 1 3 1



0 4 2 1



+ 0 · per

 + 4 · per

2 1 3 2



0 4 1 1



= 3 + 0 + 28 = 31,

maar bijvoorbeeld ook dat  per(A) = 1 · per

1 1 2 1



 + 2 · per

 + 3 · per

= 3 + 16 + 12 = 31,

dus ontwikkeling gaat net als bij de determinant, maar dan zonder de mintekens. Voor de berekening van de determinent is er een alternatief dat ook prima werkt als er geen nullen in de matrix staat. Immers, A kan middels elementaire rij-operaties geschreven worden als A = E1 · . . . · Ep · R waarbij Ej elementaire matrices zijn en R bovendriehoeks is. De Stelling van Cauchy-Binet stelt dat det(AB) = det(A) det(B) en dus is det(A) = det(E1 ) · . . . · det(Ep ) · det(R) waarbij det(R) het diagonaalproduct van R is. Een dergelijke productregel geldt echter niet voor de permanent, zoals blijkt uit het volgende voorbeeld. Voorbeeld 3.2.27 Beschouw de matrices A en B met per(A) = 6 en per(B) = 0, " A=

1 1 1

1 1 1

1 1 1

#

" , B=

1 0 0

1 0 0

1 1 1

#

" , AB =

1 1 1

1 1 1

3 3 3

# .

We berekenen eenvoudig dat per(AB) = 18. Ondank dit negatieve resultaat gelden wel de volgende eenvoudige deelresultaten. Lemma 3.2.28 Als R bovendriehoeks is, is per(R) het product van de diagonaalentries. Lemma 3.2.29 Laat A, B ∈ Rn×n . Dan geldt per(AB) = per(A)per(B) als B een diagonaalmatrix of een permutatiematrix is.

100

3.2.4

HOOFDSTUK 3. NIET-NEGATIEVE LINEAIRE ALGEBRA

De determinantale complexiteit van de permanent

Het is onbekend wat de snelste manier is om de permanent van een matrix uit te rekenen. Opmerking 3.2.30 Evaluatie van per(A) middels X per(A) = a1σ(1) · a2σ(2) · . . . · anσ(n) σ∈Sn

berekent n! − 1 keer een som en n!(n − 1) keer een product van twee getallen. Voorbeeld 3.2.31 Voor n = 3 is dit 3! − 1 = 5 optellingen en 3!(3 − 1) = 12 vermenigvuldigingen: per(A) = a11 a22 a33 + a11 a23 a32 + a12 a21 a33 + a12 a23 a31 + a13 a21 a32 + a13 a22 a31 . Passen we echter rij-ontwikkeling naar de eerste rij toe, oftewel, halen we a11 en a12 en a13 buiten haakjes, dan is per(A) = a11 (a22 a33 + a23 a32 ) + a12 (a21 a33 + a23 a31 ) + a13 (a21 a32 + a22 a31 ) . Dit kost 5 optellingen en 9 vermenigvuldigingen, en is dus iets goedkoper. Het volgende eenvoudige lemma geeft het algemene resultaat. Lemma 3.2.32 Het berekenen van per(A) middels rij-ontwikkeling kost n! − 1 optellingen en n! vermenigvuldigingen. Bewijs. Met volledige inductie. Het berekenen van de 2 × 2 permanent kost 1 optelling en 2 producten. Veronderstel als inductiehypothese dat voor B ∈ R(n−1)×(n−1) de berekening (n − 1)! − 1 optellingen en (n − 1)! producten kost. Rij-ontwikkeling voor A ∈ Rn×n berekent per(A) = a11 per(M11 ) + · · · + a1n per(M1n )

(3.39)

waarbij Mij de matrix is die overblijft door uit A de i-de rij en j-de kolom te verwijderen. Evaluatie van deze uitdrukking zoals in (3.39) kost n[(n−1)!−1]+ (n−1) = n!−1 optellingen en n(n − 1)! = n! vermenigvuldigingen.  Opmerking 3.2.33 Als er een algoritme bestaat dat per(A) uitrekent door minder dan q(n) optellingen en vermenigvuldigingen te doen waarbij q een vast polynoom is, dan is impliciet bewezen dat P=NP. De vraag of P=NP is een Milleniumprobleem waarvan de oplossing een miljoen dolar oplevert. Overigens denken de meeste experts dat P ongelijk is aan NP. Opmerking 3.2.34 Voor de determinant bestaat zo’n polynoom q, en is derdegraads in n. Om het berekenen van de permanent te vereenvoudigen zijn vele pogingen ondernomen. Een onderdeel van dergelijke pogingen is om per(A) te schrijven als det(F (A)) voor een geschikte afbeelding F . Zo is bijvoorbeeld     a b a −b per = det . c d c d

3.2. DUBBELSTOCHASTISCHE MATRICES EN DE PERMANENT

101

Het is bewezen dat voor 3 × 3 matrices er geen F bestaat met de eigenschap dat iedere entry van F (A) affien lineair is in de entries van A, waarvoor per(A) = det(F (A)). Daarom zoekt men het nu hogerop; in dit geval, in hogere dimensies. Open probleem: Gegeven A ∈ Rn×n . Wat is de kleinste waarde van m als functie van n zo, dat er een afbeelding F :

Rn×n → Rm×m :

A 7→ F (A)

bestaat die affien-lineair is in de entries van A, met de eigenschap dat per(A) = det(F (A)). Definitie 3.2.35 (Determinantale complexiteit van de permanent) De waarde van m als functie van n in dit open probleem heet de determinantal complexity of the permanent. Een stelling van Grenet uit 2012 bewijst dat m ≤ 2n − 1 en geeft daarnaast expliciet de afbeelding F . Voor A ∈ R3×3 geeft dit de volgende 7 × 7 matrix F (A),   0 a d g 0 0 0  0 1 0 0 i f 0       0 0 1 0 0 c i  a b c    , en per(A) = det(F (A). 0 0 0 1 c 0 f A =  d e f  , F (A) =      g h i  e 0 0 0 1 0 0   h 0 0 0 0 1 0  b 0 0 0 0

0

1

Het is voor n = 3 verder alleen bekend dat m > 4, dus de minimale waarde is 5, 6 of 7.

3.2.5

Het algoritme van Ryser voor het berekenen van de permanent

In 1963 vond Herbert William Ryser een methode om de complexiteit van de berekening van de permanent terug te brengen van O(n!) voor rij-ontwikkeling tot O(2n n). Eerst illustreren we deze methode voor n = 3. Bekijk als voorbeeld de matrix   1 2 3  4 5 6 . (3.40) 7 8 9 Met (3.37) vinden we dat per(A) de som is van de zes diagonaalproducten per(A) = 1 · 5 · 9 + 1 · 6 · 8 + 2 · 4 · 9 + 2 · 6 · 7 + 3 · 4 · 8 + 3 · 5 · 7 = 450.

(3.41)

Deze zes diagonaalproducten vormen een deelverzameling van de in totaal 33 = 27 producten van de entries die je krijgt als je de haakjes wegwerkt in het product P (A) van de rijsommen van A, gedefinieerd als P (A) = (1 + 2 + 3)(4 + 5 + 6)(7 + 8 + 9). Deze 27 producten zijn 1·4·7 1·5·7 1·6·7 1·4·8 1·5·8 1·6·8 1·4·9 1·5·9 1·6·9

2·4·7 2·5·7 2·6·7 2·4·8 2·5·8 2·6·8 2·4·9 2·5·9 2·6·8

3·4·7 3·5·7 3·6·7 3·4·8 3·5·8 3·6·8 3·4·9 3·5·9 3·6·9

Ryser bedacht een manier om de som van de ongewenste 21 producten op effici¨ente wijze af te trekken van P (A). Deze manier is er eerst de som van 24 van af te trekken, en de som van

102

HOOFDSTUK 3. NIET-NEGATIEVE LINEAIRE ALGEBRA

de drie die er teveel van zijn afgetrokken, daarna toch weer bij op te tellen. Hoe deed hij dit? Schrijf Aj voor de 3 × 2 matrix die uit A ontstaat door de j-de kolom te verwijderen,       2 3 1 3 1 2 A1 =  5 6  , A 2 =  4 6  , A 3 =  4 5  . 8 9 7 9 7 8 Voor iedere j ∈ {1, 2, 3} bestaat het product P (Aj ) van de rijsommen van Aj uit acht termen, P (A1 ) = (2 + 3)(5+ 6)(8 +9) = 2·5·8 +2·5·9 +2·6·8 +2·6·9 +3·5·8 +3·5·9 +3·6·8 +3·6·9, P (A2 ) = (1 + 3)(4+ 6)(7 +9) = 1·4·7 +1·4·9 +1·6·7 +1·6·9 +3·4·7 +3·4·9 +3·6·7 +3·6·9, P (A2 ) = (1 + 2)(4+ 5)(7 +8) = 1·4·7 +1·4·8 +1·5·7 +1·5·8 +2·4·7 +2·4·8 +2·5·7 +2·5·8. Merk op dat ieder van deze 24 producten bestaat uit drie getallen die uit twee van de drie kolommen van A komen, en dus geen diagonaalproducten van A zijn. Merk vervolgens op dat drie van de bovenstaande 24 producten twee keer voorkomen, namelijk, precies de producten van drie getallen uit dezelfde kolom. Dit leidt tot de conclusie dat per(A) = P (A) − [P (A1 ) + P (A2 ) + P (A3 ) ] + P (A1,2 ) + P (A2,3 ) + P (A1,3 ),

(3.42)

waarbij Ai,j de matrix is die je krijgt door kolommen i en j uit A te verwijderen. Voor de gegeven matrix A vinden we daarom dat per(A) = 2160 − (935 + 640 + 405) + 270 = 450. Dit komt dus precies overeen met de middels de definitie gevonden waarde in (3.41). Opmerking 3.2.36 Ryser berekent in totaal 11 producten, tegen 12 producten in (3.41). Echter, in (3.41) worden slechts 5 optellingen gedaan, en in Ryser’s methode 21 (alhoewel slim administreren dit aantal wat laat slinken). Dus voor n = 3 kost Ryser’s methode niet bepaald minder werk dan het uitschrijven van de definitie van permanent of rij-ontwikkeling. Aan de basis van de methode van Ryser voor een matrix A ∈ R3×3 staat het product van de rijsommen P (A) = (a11 + a12 + a13 )(a21 + a22 + a23 )(a31 + a32 + a33 ). (3.43) Als we de dit product uitvermenigvuldigen, ontstaat er een som van 27 producten van drie getallen, die de eigenschap hebben dat ze uit drie verschillende rijen van A komen. Dus, X P (A) = a1f (1) · a2f (2) · a3f (3) (3.44) f :{1,2,3}→{1,2,3}

waarbij gesommeerd wordt over de verzameling S van alle 27 verschillende functies van {1, 2, 3} naar zichzelf. De permanent van A is precies gelijk aan de som over de deelverzameling S ∗ van bijectieve functies van {1, 2, 3} naar zichzelf. De methode van Ryser is nu gebaseerd op de volgende observatie. Laat Sj de verzameling zijn van functies van {1, 2, 3} naar {1, 2, 3} \ {j}. Dan behoort iedere niet-bijectieve f ∈ S tot ´e´en of meerdere van de verzamelingen S1 , S2 , S3 . En dus kan de som over S ∗ geschreven worden als X X X X X X X X X = − − − + + + − , (3.45) S∗

S

S1

S2

S3

S1 ∩S2

S2 ∩S3

S1 ∩S3

S1 ∩S2 ∩S3

waarbij aangetekend dient te worden dat de doorsnede S1 ∩ S2 ∩ S3 in dit geval leeg is.

3.2. DUBBELSTOCHASTISCHE MATRICES EN DE PERMANENT

103

Opmerking 3.2.37 Formule (3.45) heet het principe van inclusie en exclusie, en kan worden gegeneraliseerd naar n × n matrices, met hierbij horende matrices die ontstaan door uit A ´e´en, twee, tot en met n − 1 kolommen weg te laten. Schrijf [n] = {1, . . . , n}. Het product P (A) van de rijsommen van A bestaat uit de nn producten van n entries van A, waarbij ieder van deze n entries afkomstig zijn uit de n verschillende rijen van A. Met andere woorden, X a1f (1) · a2f (2) · . . . · anf (n) (3.46) (a11 + . . . + a1n ) · . . . · (an1 + . . . + ann ) = P (A) = f :[n]→[n]

waarbij gesommeerd wordt over alle nn functies f : [n] → [n]. Hiervan willen we de n! producten overhouden waarvan de n getallen die het product vormen, uit verschillende kolommen van A afkomstig zijn: oftewel, sommeren over alle bijectieve functies f : [n] → [n]. De algemene formule van Ryser laat zich als volgt opschrijven. Schrijf Σj (A) voor de verzameling van alle n×(n−k) matrices die ontstaan door op alle mogelijke verschillende manieren k kolommen uit A te verwijderen. Dan is dus Σ0 (A) = {A}, Σ1 (A) = {A1 , . . . , An }, . . . , Σn−1 (A) = {Ae1 , . . . , Aen }.

(3.47)

Laat vervolgens Sk =

X

P (X),

(3.48)

X∈Σk (A)

waarbij P (X) staat voor het product van de rijsommen van X. Dan geldt dat per(A) = S0 − S1 + S2 − S3 + . . . + (−1)n−1 Sn−1 .

(3.49)

Merk op dat S0 = P (A) en S1 = P (A1 ) + · · · + P (An ) en Sn−1 = P (Ae1 ) + · · · + P (Aen ) en dat we voor n = 3 hiermee inderdaad de eerder gegeven formule (3.42) terugvinden. Opmerking 3.2.38 Laat s ⊂ [n]. De formule van Ryser voor A ∈ Rn×n berekent P (As ) voor de matrix As die uit A ontstaat door de kolommen waarvan de index in s zit te verwijderen. Omdat [n] precies 2n deelverzamelingen heeft, worden er dus in totaal (n − 1)2n vermenigvuldigingen berekend. Dit is veel, maar ook veel minder dan n! zoals bij rij-ontwikkeling.

3.2.6

Een formule van Glynn

In 2010 ontwikkelde David G. Glynn van de Flinders University of South Australia in Adelaide een familie van alternatieve formules om de permanent van een n × n matrix A = (aij ) te berekenen in zijn artikel The permanent of a square matrix, European Journal of Combinatorics 31(7):1887-1891. De eenvoudigste van deze formules is de volgende:   n n n X Y X Y  per(A) = 21−n vj  aij vj . (3.50) v∈Bn

j=1

i=1 j=1

Hierbij loopt de eerste som over de verzameling Bn = {v = (v1 , . . . , vn ) ∈ {−1, 1}n | v1 = 1} , die dus uit 2n−1 vectoren bestaat. We zullen deze formule hier niet bewijzen.

(3.51)