1 Lichamen en vectorruimten Lichamen Vectorruimten Toepassing: Codes... 13

Voorwoord Dit zijn de aantekeningen bij de colleges Lineaire Algebra 3 en 4 voor de voorjaarskwartalen van 2006, aan eerstejaars wiskunde- en natuurkundestudenten van de Radboud Universiteit Nijmegen. Nadat in Lineaire Algebra 1 en 2 de basisbegrippen voor vectorruimten en lineaire afbeeldingen daartussen over R zijn gegeven, wordt in Lineaire Algebra 3 begonnen met generalisatie naar willekeurige grondlichamen. Om dat mogelijk te maken worden eerst enkele basisbegrippen uit de abstracte algebra ingevoerd, zoals lichamen en (polynoom)ringen, en toegelicht. Na een hoofdstuk over lineaire afbeeldingen, en de afhankelijkheid van bijbehorende matrices van de basiskeuze, volgt in Hoofdstuk 4, een aantal belangrijke constructies van vectorruimten. In Hoofdstuk 5 staat de vraag naar diagonaliseerbaarheid van matrices centraal, en komen eigenruimten, de stelling van Cayley-Hamilton, en de Jordan normaalvorm aan de orde. In de Hoofdstukken 6 en 7 komen inproductruimten aan de orde. Na een algemene inleiding over bilineaire vormen, spitst de behandeling zich toe op reële en complexe vectorruimten. In Hoofdstuk 7 wordt gekeken naar lineaire afbeeldingen die, op een of andere manier, inproducten behouden: unitaire (orthogonale) en Hermitese (symmetrische) afbeeldingen (en hun matrices), alsmede de diagonaliseerbaarheid daarvan. Tevens is een sectie over geadjungeerden, normaliteit en het verband met unitaire en Hermitese afbeeldingen toegevoegd. Aan de hand van deze aantekeningen wordt 2 uur hoorcollege per week gegeven, gedurende ongeveer 15 weken. Daarbij hoort een werkcollege van 2 uur voor het maken van wat uitgebreidere opgaven (opgenomen aan het einde van dit dictaat). Er zijn afzonderlijke tentamens over de eerste helft en de tweede helft van de stof. Mijn aantekeningen zijn hier en daar gebaseerd op het eerder gebruikte dictaat Algebra B, geschreven door Arno van den Essen, en op delen van het boek Linear Algebra van Friedberg, Insel en Spence. Wieb Bosma, december 2005

1

2

Inhoudsopgave 1 Lichamen en vectorruimten 1.1 Lichamen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Vectorruimten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Toepassing: Codes . . . . . . . . . . . . . . . . . . . . . . . . . . .

5 5 9 13

2 Ringen en polynomen 2.1 Ringen . . . . . . . . . . . . 2.2 Eenheden en Nuldelers . . . 2.3 Gehele getallen, polynomen, 2.4 Factoren en Nulpunten . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

19 19 21 22 27

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

33 33 34 37 37

4 Enkele constructies 4.1 Enkele Constructies van Vectorruimten . . . . . . . . . . . . . . . .

41 41

5 Eigenwaarden en Diagonaliseerbaarheid 5.1 Diagonaliseerbaarheid . . . . . . . . . . 5.2 Eigenruimten . . . . . . . . . . . . . . . 5.3 Cayley-Hamilton . . . . . . . . . . . . . 5.4 Toepassingen . . . . . . . . . . . . . . . 5.5 Jordan normaalvorm . . . . . . . . . . .

. . . . .

47 47 49 54 56 57

6 Inproductruimten 6.1 Bilineaire Vormen . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2 Reëel-symmetrische bilineaire vormen . . . . . . . . . . . . . . . . 6.3 Inproductruimten . . . . . . . . . . . . . . . . . . . . . . . . . . . .

63 63 68 70

7 Transformaties van Inproductruimten 7.1 Orthogonale en Unitaire Transformaties . . . . . . . . . . . . . . . 7.2 Symmetrische en Hermitese Transformaties . . . . . . . . . . . . . 7.3 Geadjungeerde en Normaliteit . . . . . . . . . . . . . . . . . . . . .

75 75 78 80

. . . . . . . . . . . . . . . . . . . . en deelbaarheid . . . . . . . . . . .

3 Lineaire afbeeldingen en matrices 3.1 Lineaire Afbeeldingen . . . . . . 3.2 Matrices . . . . . . . . . . . . . . 3.3 Determinant . . . . . . . . . . . . 3.4 Toepassing: Regel van Cramer .

3

. . . .

. . . .

. . . .

. . . .

. . . .

. . . . .

. . . .

. . . . .

. . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

4

INHOUDSOPGAVE

Hoofdstuk 1

Lichamen en vectorruimten Inleiding In Lineaire Algebra 1 heb je al kennis gemaakt met het begrip vectorruimte. In dit hoofdstuk gaan we dat begrip generaliseren, en wel door toe te staan dat de scalairen uit andere objecten bestaan dan slechts de reële getallen, waartoe ze tot dusverre beperkt waren. De scalairen moeten aan zekere eisen voldoen om de gegeneraliseerde definitie zinnig te maken; zo moet je scalairen kunnen optellen en met elkaar vermenigvuldigen, en moeten er scalaire elementen 1 en 0 zijn. Je krijgt de eigenschappen van vectorruimten terug wanneer je eist dat de scalairen een lichaam vormen. Onze eerste taak zal zijn om lichamen te definiëren en er voorbeelden van te geven.

1.1

Lichamen

Voor een algemenere definitie van vectorruimte zullen we eigenschappen van de reële getallen bestuderen en proberen in een abstracte definitie te vangen. Vervolgens zullen we kijken naar andere objecten die aan diezelfde eigenschappen voldoen. De eigenschappen waar we op doelen zijn niet uitsluitend die van de getallen zelf, maar ook van de bewerkingen die je er op uit kunt voeren: je kunt reële getallen bij elkaar optellen, en je kunt ze met elkaar vermenigvuldigen. Een lichaam zal een verzameling zijn waar we op soortgelijke manier 2 operaties hebben die aan overeenkomstige eigenschappen voldoen. Die eigenschappen zijn dat het niet uitmaakt in welke volgorde je getallen optelt (of vermenigvuldigt), dat er speciale reële getallen zijn (namelijk 0 en 1) die bij optelling of vermenigvuldiging geen effect hebben, en de manier waarop de vermenigvuldiging zich ‘verdeelt’ over de optelling (we maken dat precies in 1.1.3). Maar eerst definiëren we wat een bewerking is, omdat we meer algemene operaties willen toestaan dan alleen optelling en vermenigvuldiging. Als V een verzameling is, geven we met V × V de verzameling geordende paren (v 1 , v2 ) met v1 , v2 ∈ V , aan. Definities 1.1.1 Een bewerking · op een verzameling V is een afbeelding van V × V naar V . Een bewerking is commutatief als v 1 · v2 = v2 · v1 voor elk tweetal v1 , v2 ∈ V , en een bewerking · heet associatief als (v 1 · v2 ) · v3 = v1 · (v2 · v3 ), voor elk drietal v1 , v2 , v3 . 5

6

HOOFDSTUK 1. LICHAMEN EN VECTORRUIMTEN

Met andere woorden: een bewerking voegt aan elk paar elementen van V een derde element toe. Bij een commutatieve bewerking maakt het niet uit in welke volgorde je de bewerking uitvoert en voor een associatieve bewerking maakt het niet uit hoe je de haakjes zet in v1 · v2 · v3 . Voorbeelden 1.1.2 Je kent al heel veel voorbeelden van bewerkingen: we keken al naar de optelling en vermenigvuldiging van reële getallen. Let wel op: bij een bewerking hoort een verzameling. Je kunt niet zeggen dat + een bewerking is, maar wel dat + een bewerking is op de reële getallen (of gehele getallen, enz.). (i) Optellen vormt een bewerking op de natuurlijke getallen N. Evenzo vermenigvuldigen. (ii) Aftrekken is een bewerking op de gehele getallen Z, maar niet op N. (iii) Delen is een bewerking op de verzameling Q ∗ van rationale getallen die ongelijk aan nul zijn (maar niet op de gehele getallen ongelijk 0). (iv) De gebruikelijke optelling en vermenigvuldiging van polynomen vormen bewerkingen op de verzameling R[x] van polynomen met reële coëfficiënten. (v) Zowel optellen als vermenigvuldigen is een bewerking op M n (R), de n × n matrices met reële coëfficiënten. (vi) Als X een verzameling is, dan kun je aan twee afbeeldingen f en g van X naar zichzelf een nieuwe afbeelding g ◦ f toevoegen, door (g ◦ f )(x) = g(f (x)). Deze samenstelling g ◦ f van de afbeeldingen f en g is zelf ook weer een afbeelding X → X. Dus is ◦ een bewerking op de verzameling afbeeldingen X X van X naar zichzelf. Als speciaal geval kun je bijvoorbeeld kijken naar alle functies van R naar R. ♣ Opgave 1. Laat zien dat de samenstelling ◦ van functies R → R niet commutatief is maar wel associatief.

Definitie 1.1.3 Een lichaam is een verzameling V met daarop twee bewerkingen + en ×, die voldoen aan:

[L1] + op V is associatief: (x + y) + z = x + (y + z), voor alle x, y, z ∈ V ; [L2] er is een (nul)element 0 ∈ V zodanig dat 0 + x = x + 0 = x voor alle x ∈ V ; [L3] bij elke x ∈ V is er een tegengestelde −x ∈ V zodanig dat x + (−x) = (−x) + x = 0; [L4] + op V is commutatief: x + y = y + x voor alle x, y ∈ V ; [L5] × op V is associatief: (x × y) × z = x × (y × z), voor alle x, y, z ∈ V ; [L6] er is een (eenheids)element 1 ∈ V zodanig dat 1 × x = x × 1 = x voor alle x∈V; [L7] bij elke x ∈ V met x 6= 0 is er een inverse x −1 ∈ V zodanig dat x × x−1 = x−1 × x = 1; [L8] × op V is commutatief: x × y = y × x voor alle x, y ∈ V ; [L9] de operatie × is distributief over +, dat wil zeggen: x × (y + z) = (x × y) + (x × z) en (x + y) × z = (x × z) + (y × z), voor alle x, y, z ∈ V .

Opmerkingen 1.1.4 Een lichaam bestaat dus uit een drietal (V, +, ×), namelijk een verzameling V met twee bewerkingen daarop. In deze definitie hebben we de bewerkingen met + en × aangegeven, omdat in voorbeelden die we kennen (zoals de reële getallen) dat natuurlijk is. Maar de bewerkingen hoeven helemaal geen optelling of vermenigvuldiging te zijn — daarvan zien we zo voorbeelden.

1.1. LICHAMEN

7

Er zijn heel veel belangrijke algebra¨ısche strukturen die bestaan uit een verzameling V , en één of twee operaties die voldoen aan een deelverzameling van de axioma’s L1–9. Zo is een groep een verzameling met een bewerking die voldoet aan L1–3, en een commutatieve groep (die meestal abelse group wordt genoemd) voldoet bovendien aan L4. Een ring met 1 is een verzameling V met operaties + en × die voldoen aan L1–6 en aan L9; als deze bovendien aan L8 voldoet, is het een commutatieve ring met 1. Meer hierover in Hoofdstuk 2. In een lichaam kun je dus elk tweetal elementen optellen en aftrekken, vermenigvuldigen en delen (mits je niet door nul deelt). Een lichaam vormt een abelse groep ten opzichte van de optelling +, en de elementen die niet nul zijn vormen een abelse groep ten opzichte van de vermenigvuldiging ×. Als (V, +, ×) een lichaam is en een deelverzameling U ⊂ V vormt met dezelfde bewerkingen ook een lichaam, dan zeggen we dat (U, +, ×) een deellichaam van V is. We zeggen wel dat U een deellichaam is van V (en bedoelen dan: met dezelfde bewerkingen). In een lichaam (en algemener, in een ring) (V, +, ×) definiëren we de aftrekking van twee elementen nu door a − b = a + (−b), en de deling van a door een element b 6= 0 door a/b = a × b−1 . ♣ Opgave 2. Bewijs dat wanneer (V, +, ×) een lichaam is, en U een deelverzameling van V is die 0 en 1 bevat, geldt: (U, +, ×) is een lichaam dan en slechts dan als voor elk tweetal elementen a, b ∈ U met b 6= 0 geldt a − b ∈ U en a/b ∈ U .

Voorbeelden 1.1.5 We geven de belangrijkste voorbeelden van lichamen. (i) (R, +, ×): de reële getallen vormen onder optelling en vermenigvuldiging een lichaam. Om dat te bewijzen moet je nagaan dat de eigenschappen L1–9 gelden. De meeste daarvan zijn flauw. (ii) (Q, +, ×): de rationale getallen (breuken) vormen onder optelling en vermenigvuldiging een lichaam. Natuurlijk kun je weer alle eigenschappen waaraan een lichaam moet voldoen gaan verifiëren, maar het is eenvoudiger om de eigenschap uit de opgave te gebruiken die zegt dat (Q, +, ×) een deellichaam is van (R, +, ×): het is duidelijk dat de breuken een deelverzameling van de reële getallen vormen die gesloten is onder het nemen van verschillen en quotiënten. (iii) (C, +, ×): de complexe getallen vormen onder optelling en vermenigvuldiging een lichaam met (R, +, ×) als deellichaam! We definiëren hier de complexe getallen als paren (a, b) ∈ R 2 van reële getallen die we optellen als vectoren in R 2 en vermenigvuldigen volgens (a, b) × (c, d) = ((a × c) − (b × d), (a × d) + (b × c)), gebruik makend van de vermenigvuldiging (en optelling) in R. Vaak schrijven we a + bi voor (a, b) in C, waarbij dan i 2 = −1. De reële getallen kunnen we dan vereenzelvigen met de deelverzameling van paren (a, 0). (iv) De verzameling V = {0} met de gewone optelling en vermenigvuldiging vormt een lichaam dat uit maar 1 element bestaat; in het bijzonder is 0 = 1 in deze ring! Omdat dit speciale geval soms tot complicaties leidt, zullen we het vanaf nu expliciet uitsluiten, en eisen: de ringen en lichamen die wij beschouwen hebben ten minste twee verschillende elementen 0 6= 1.

8

HOOFDSTUK 1. LICHAMEN EN VECTORRUIMTEN (v) De gehele getallen vormen geen lichaam onder optelling en vermenigvuldiging omdat je van z ∈ Z geen inverse in Z kunt vinden, tenzij z ∈ {−1, 1}.

Voorbeeld 1.1.6 (Z/mZ) We construeren de commutatieve ring (met 1) Z/mZ, de restklassenring modulo m, als volgt. Laat m > 1 een vast natuurlijk getal zijn (de modulus). We delen Z op in restklassen modulo m, namelijk de deelverzamelingen Ri = {z : z ∈ Z | ∃k ∈ Z : z = i + k · m} voor i ∈ Z. Dan is duidelijk dat Ri = Rj wanneer i − j een veelvoud van m is, en dat Ri ∩ Rj = ∅ wanneer Ri 6= Rj . We hebben zo precies m disjuncte restklassen gemaakt, R0 , R1 , . . . , Rm−1 . Vaak geven we de restklasse Ri , waar i zelf in zit, aan met ¯i. Als i en j in dezelfde restklasse zitten, schrijven we i ≡ j mod m, en zeggen dat i congruent j modulo m is. Dus i ≡ j mod m

⇐⇒

⇐⇒

R i = Rj

¯i = ¯j

⇐⇒

m | i − j.

We definiëren optelling en vermenigvuldiging van ¯i en ¯j door ¯i + ¯j = i + j en ¯i × ¯j = i × j. Nu is Z/mZ de verzameling van de m restklassen modulo m met deze optelling en vermenigvuldiging. Niet alle elementen (ongelijk 0) hebben een inverse in Z/mZ tenzij m een priemgetal is. Voor een priemgetal p is de ring Z/pZ wel een lichaam dat uit precies p verschillende elementen bestaat. Zo’n eindig lichaam Z/pZ wordt ook wel met Fp aangegeven. Later zullen we zien dat voor elke macht q = p k van een priemgetal p er een eindig lichaam Fq van q elementen bestaat (en voor geen enkel ander natuurlijk getal). Bovendien is er in essentie maar één zo’n lichaam. ♣ Opgave 3. Maak een opteltabel en een vermenigvuldigingstabel voor Z/7Z. Hoe lees je aan deze tabel de eigenschappen L2–4, L6–8 af? Laat zien dat Z/7Z een lichaam vormt. ♣ Opgave 4. De quaternionen van Hamilton H worden gedefinieerd als uitdrukkingen van de vorm a + bi + cj + dk met a, b, c, d ∈ R. Twee zulke uitdrukkingen a1 + b1 i + c1 j + d1 k en a2 + b2 i + c2 j + d2 k zijn hetzelfde dan en slechts dan als a1 = a2 en b1 = b2 en c1 = c2 en d1 = d2 . Optellen geschiedt componentsgewijs, hetgeen som a1 + a2 + (b1 + b2 )i + (c1 + c2 )j + (d1 + d2 )k geeft, en vermenigvuldiging vindt plaats met de regels: i2 i·j j·k k·i

= j2 = k = i = j

=

k2 = −1 j · i = −k k · j = −i i · k = −j.

Laat zien dat H met deze bewerkingen een niet-commutatieve ring vormt. (Voor het bewijs van associativiteit van vermenigvuldiging helpt het om a + bi + cj + dk = (a + bi) + (c + di)j te schrijven.) Geef een isomorfisme aan van H met de deelring van M2 (C) bestaande uit matrices A · I + B · J + C · K + D · L, waar A, B, C, D ∈ R en 0 i 0 1 i 0 1 0 . , L= , K= , J= I= i 0 −1 0 0 −i 0 1 Laat ook zien dat a + bi + cj + dk een inverse heeft tenzij a = b = c = d = 0, door te kijken naar (a + bi + cj + dk) · (a − bi − cj − dk). De quaternionen vormen een scheeflichaam: een ring die aan alle axioma’s voor een lichaam voldoet behalve de commutativiteit [L8].

1.2. VECTORRUIMTEN

1.2

9

Vectorruimten

Nu zijn we in staat definities en stellingen uit Lineaire Algebra 1 en 2 te generaliseren. Definitie 1.2.1 Zij L een lichaam. Een L-vectorruimte is een verzameling V met een bewerking + en een afbeelding die aan elk paar (λ, v) ∈ L × V een element λv ∈ V toevoegt, die voldoen aan:

[V1] de operatie + op V is associatief: (u + v) + w = u + (v + w), voor alle u, v, w ∈ V ; [V2] er is een (nul)element 0 ∈ V zodanig dat 0 + v = v + 0 = v voor alle v ∈ V ; [V3] bij elke v ∈ V is er een tegengestelde −v ∈ V zodanig dat v + (−v) = (−v) + v = 0; [V4] de operatie + op V is commutatief: v + w = w + v voor alle v, w ∈ V ; [V5] 1v = v voor alle v ∈ V ; [V6] λ(v + w) = λv + λw voor alle λ ∈ L en v, w ∈ V ; [V7] (λ + µ)v = λv + µv voor alle λ, µ ∈ L en v ∈ V ; [V8] (λµ)v = λ(µv) voor alle λ, µ ∈ L en v ∈ V .

Opmerkingen 1.2.2 Vergeet niet dat de eis dat + een bewerking is oplegt dat [V0] v1 + v2 ∈ V voor alle v1 , v2 ∈ V .

Een afbeelding L × V → V , voor een lichaam L en een verzameling V , die aan V[5 − 8] voldoet wordt een scalaire vermenigvuldiging genoemd. Kort samengevat kunnen we dan zeggen dat een L-vectorruimte niets anders is dan een additieve groep (V, +) met daarop een scalaire vermenigvuldiging gedefinieerd. De elementen van L heten scalairen, die van V vectoren. Merk op dat bij een vectorruimte dus een lichaam hoort waaruit de scalairen komen. In Lineaire Algebra 1 werd onder vectorruimte het speciale geval van R-vectorruimte of reële vectorruimte verstaan. Het is ook mogelijk een struktuur analoog aan een vectorruimte maar dan algemener over een ring te definiëren, een zogenaamd R-moduul. Voorbeelden 1.2.3 (i) Uit Lineaire Algebra 1 ken je de ruimte R n bestaande uit n-tallen reële getallen (geschreven als rijvector of kolomvector) met de coördinaatsgewijze optelling en scalaire vermenigvuldiging. Net zo is de verzameling van alle rijtjes van n elementen uit een lichaam L een L-vectorruimte, die we met L n aangeven (voor n ≥ 1). Per definitie is L 0 = {0}.

(ii) De verzameling van oneindige rijtjes elementen x 1 , x2 , . . . van L is een Lvectorruimte onder coördinaatsgewijze optelling en vermenigvuldiging, die we met L∞ aangeven. (iii) De verzameling van elementen van L[x] vormt met optelling en scalaire vermenigvuldiging λ(am xm + · · · + a1 x + a0 ) = (λam )xm + · · · + (λa1 )x + λa0 een L-vectorruimte, voor elk lichaam L.

(iv) Laat Mm×n (L) voor een lichaam L en positieve gehele getallen m, n de verzameling van m × n matrices met coëfficiënten in L zijn. Dan is Mm×n (L) een L-vectorruimte (onder optelling), als de scalaire vermenigvuldiging λM eruit bestaat elke coëfficiënt van de matrix M met λ te vermenigvuldigen.

10


(v) Voor een willekeurige verzameling S vormt de verzameling van afbeeldingen φ : S → L naar een lichaam L een vectorruimte als we optelling definiëren door (φ1 + φ2 )(s) = φ1 (s) + φ2 (s) voor s ∈ S, en scalaire vermenigvuldiging door (λφ)(s) = λ · φ(s) voor s ∈ S, λ ∈ L. We geven die ruimte wel aan met LS . Merk op dat met S = {1, 2, . . . , n} we Ln vinden, dat LN = L∞ en dat Mm×n (L) hetzelfde is als LS voor S = {1, 2, . . . , m} × {1, 2, . . . , n}. (vi) Met L = R en I een open interval van R is L S = RI de vectorruimte van reëelwaardige functies op I. Leggen we op dat de functies k-maal continu differentieerbaar zijn, dan geven we die ruimte wel met C (k) (I) aan. Zo bestaat C (0) (R) uit de continue reële functies. ♣ Opgave 5. Laat zien dat Rn een Q-vectorruimte is. Is Cn een R-vectorruimte? En is Qn een R-vectorruimte?

Definitie 1.2.4 Een L-lineaire deelruimte van een L-vectorruimte V is een deelverzameling U ⊂ V met de eigenschap dat: (i) 0 ∈ U ; (ii) u1 + u2 ∈ U voor alle u1 , u2 ∈ U ; (iii) λu ∈ U voor elke λ ∈ L en u ∈ U . Opmerkingen 1.2.5 Net als in het reële geval geldt hier weer dat de naam Llineaire deelruimte terecht suggereert dat het een deelverzameling U ⊂ V is die met de van V geërfde optelling en scalaire vermenigvuldiging zelf een L-vectorruimte vormt. In veel van de definities laten we de toevoeging L- wel weg als het onbelangrijk is, of duidelijk uit de context om welk lichaam het gaat. ♣ Opgave 6. Laat zien dat de eerste voorwaarde uit 1.2.4 gemist kan worden mits we eisen dat U niet-leeg is; laat door twee voorbeelden zien dat geen van beide andere voorwaarden gemist kan worden. ♣ Opgave 7. Laat zien dat de convergente rijtjes y1 , y2 , . . . een lineaire deelruimte vormen van R∞ .

Definities 1.2.6 Een L-lineaire combinatie van elementen v 1 , . . . , vk uit een Lvectorruimte V is een element λ1 v1 +· · ·+λk vk ∈ V , waar λi ∈ L. Het L-opspansel van v1 , . . . , vk is de verzameling van alle L-lineaire combinaties van v 1 , . . . , vk : hv1 , . . . , vk i = {λ1 v1 + · · · + λk vk | λ1 , . . . , λk ∈ L}. Een volledig stelsel (of ook wel opspannend stelsel) vectoren voor een vectorruimte V is een verzameling {v1 , v2 , . . . , vk } ⊂ V zodat V = hv1 , v2 , . . . , vk i; we zeggen dat de vi de ruimte V opspannen (over L). Een L-basis voor een vectorruimte V is een volledig stelsel dat bovendien onafhankelijk is over L; hier heet v 1 , v2 , . . . , vk een onafhankelijk stelsel over L als voor λ 1 , . . . , λk ∈ L geldt: λ1 v1 + · · · + λ k vk = 0

⇒

λ1 = λ2 = · · · = λk = 0.

Een stelsel dat niet onafhankelijk is heet natuurlijk afhankelijk. Op grond van de onderstaande stelling kunnen we voor de dimensie dim V van een vectorruimte V 6= {0} het maximale aantal n van onafhankelijke vectoren in V nemen als zo’n

1.2. VECTORRUIMTEN

11

eindig getal n bestaat; als dat niet bestaat is de dimensie oneindig. De nulruimte {0} heeft per definitie dimensie 0. Zodra een basis B = {b1 , . . . , bn } voor een L-vectorruimte is gekozen, kan elk element v ∈ V op unieke manier gerepresenteerd worden door een coördinatenvector v = (v1 , . . . , vn )B ∈ Ln , namelijk zo dat v = v 1 b1 + · · · + v n bn . Opmerking 1.2.7 Eigenlijk is het beter om een basis niet als verzameling te definiëren, want de volgorde doet er wel degelijk toe (voor de coördinatenvector bijvoorbeeld)! (Zie ook de opgave na 4.1.14.) Stelling 1.2.8 (Hoofdstelling van de Lineaire Algebra) Als er een L-basis van de L-vectorruimte V is die uit n > 0 elementen bestaat, dan heeft elke L-basis van V precies n elementen. Stelling 1.2.9 Zij V een vectorruimte en n ≥ 1. Als {v 1 , . . . , vn } ⊂ V een volledig stelsel vormen, is elk stelsel {w1 , . . . , wm } ⊂ V met m > n afhankelijk. De bewijzen van deze twee stellingen in Lineaire Algebra 1 voor het geval L = R blijken op een enkel detail na (lees L in plaats van R) ook in het algemene geval te gelden: de laatste stelling bewijs je door te laten zien dat een homogeen stelsel van n vergelijkingen in m onbekenden altijd een oplossing heeft (in L) die niet de nul-oplossing is. Dan bewijs je de Hoofdstelling door te laten zien dat #B 1 ≤ #B2 en #B2 ≤ #B1 als B1 en B2 allebei bases voor V zijn, en dus moet #B 1 = #B2 . Voorbeelden 1.2.10 (i) De dimensie van Ln is n, en L∞ heeft oneindige dimensie. De standaardbasis E = {e1 , . . . , en } van Ln bestaat uit de vectoren       1 0 0  0   1   0        e1 =  .  , e 2 =  .  , · · · , e n =  .  .  ..   ..   ..  0

0

1

(ii) Mm×n (L) is een vectorruimte van dimensie mn. (iii) L[x] is oneindig dimensionaal, voor elk lichaam L.

♣ Opgave 8. Is het over een willekeurig lichaam waar dat een homogeen stelsel van n vergelijkingen in m onbekenden (met m > n) oneindig veel oplossingen heeft? ♣ Opgave 9. Bewijs dat een homogeen stelsel van n vergelijkingen in m onbekenden over Z altijd oplossingen in Z heeft. Is het waar dat er altijd oneindig veel oplossingen in Z zijn als m > n? ♣ Opgave 10. Laat zien dat Q[x] een oneindig-dimensionale Q-vectorruimte vormt, door voor elke n > 0 een onafhankelijk stelsel van n elementen uit Q[x] aan te geven.

Stelling 1.2.11 Elke lineaire deelruimte U van een eindig-dimensionale vectorruimte V is eindig-dimensionaal, en er geldt dim U ≤ dim V . Ook het bewijs van deze stelling verloopt precies zo als voor het speciale geval L = R: bewijs eerst een lemma.

12


Lemma 1.2.12 Als {v1 , . . . , vn } een onafhankelijk stelsel vormen in de vectorruimte V , en w ∈ V \ hv1 , . . . , vn i, dan is {v1 , . . . , vn , w} onafhankelijk. Vervolgens laat je zien dat een maximaal onafhankelijk stelsel in U ⊂ V ten hoogste n = dim V elementen kan bevatten. Ook dat gaat over een willekeurig lichaam. ♣ Opgave 11. Het bewijs van het lemma over R gebruikte dat met ai , a ∈ R: a1 u1 + · · · + an un + av = 0

⇒

v = b 1 u1 + · · · + b n un ,

met bi ∈ R. Laat met een voorbeeld zien dat dit niet waar is als je eist dat ai , a, bi ∈ Z.

Gevolgen 1.2.13 In een eindig-dimensionale vectorruimte is elk onafhankelijk stelsel aan te vullen tot een basis, en is elk volledig stelsel uit te dunnen tot een basis. ♣ Opgave 12. Bewijs dat (voor elke n ≥ 1 en elk lichaam L) de diagonaalmatrices (met alleen niet-nul elementen toegestaan op de diagonaal) een lineaire deelruimte van M n×n (L) vormen. Bepaal de dimensie van deze ruimte en geef een basis. ♣ Opgave 13. Laat zien dat W1 en W2 lineaire deelruimten van Q5 zijn en W3 niet; bepaal ook de dimensie en een basis voor W1 en W2 . Hier is W1 = { (a, b, c, d, e) ∈ Q5 | a + b = c + d }, en W2 = { (a, b, c, d, e) ∈ Q5 | a = b = c en a + d + e = 0 }, en W3 = { (a, b, c, d, e) ∈ Q5 | a2 = b + 1 }. ♣ Opgave 14. Bewijs dat de doorsnede van twee lineaire deelruimten van een L-vectorruimte V weer een lineaire deelruimte van V is. Laat zien dat zelfs geldt dat ∩i∈I Wi een lineaire deelruimte van V is als alle Wi dat zijn, voor i ∈ I. ♣ Opgave 15. Geef een voorbeeld waaruit blijkt dat de vereniging van twee lineaire deelruimten van een L-vectorruimte V niet weer een lineaire deelruimte van V hoeft te zijn. Bewijs dat zelfs geldt voor lineaire deelruimten W1 , W2 van V dat: W1 ∪ W2 is een lineaire deelruimte van V dan en slechts dan als W1 ⊂ W2 of W2 ⊂ W1 . ♣ Opgave 16. Laat zien dat voor elk lichaam L en elk geheel getal n ≥ 0 de deelverzameling { f ∈ L[x] | deg f ≤ n } een lineaire deelruimte is van L[x]; deze ruimte zullen we wel met L[x](n) aangeven. Bepaal de dimensie van L[x](n) en geef een basis.

1.3. TOEPASSING: CODES

1.3

13

Toepassing: Codes

Als toepassing van vectorruimten over eindige lichamen kijken we naar foutenverbeterende codes. We benutten slechts elementaire kennis van vectorruimten, en van het standaardinproduct. Definitie 1.3.1 Als R een commutatieve ring met 1 is en R n de verzameling van rijtjes elementen van R ter lengte n (voor een n ≥ 1), dan is het standaardinproduct n n op PnR de functie hv, wi → R die aan twee elementen v, w ∈ R het element i=1 vi wi ∈ R toevoegt.

Opmerking 1.3.2 Het is gebruikelijk om het standaardinproduct te definiëren voor het speciale geval dat R een lichaam is, en R n de standaard vectorruimte van dimensie n. Het is voor enkele van de voorbeelden verderop prettig deze algemenere definitie te hebben. Een algemenere definitie van inproducten voor een vectorruimte volgt nog in Hoofdstuk 6. ♣ Opgave 17. Is het met bovenstaande definitie altijd waar dat het inproduct hv, vi van een vector ongelijk aan 0 is (wanneer v niet uit louter nullen bestaat)?

Definities 1.3.3 Een lineaire (foutenverbeterende) code over F q is een lineaire deelruimte van Fnq , voor een n ≥ 1. We zullen meestal simpelweg over een code C over Fq spreken. De codewoorden zijn de elementen van F nq die bevat zijn in C. De dimensie dim C van de code is de dimensie van de deelruimte. De lengte van de code is de dimensie n van de ruimte waaruit de vectoren afkomstig zijn, dus de lengte van de codewoorden. Opmerkingen 1.3.4 Merk op dat per definitie het nulwoord altijd in een code zit. Het aantal elementen van de code is gelijk aan q k , als k = dim C en q het aantal elementen van het lichaam. De verhouding tussen k en n wordt wel de ‘rate’ van de code genoemd: van de n coördinaten van elk codewoord dragen er k bij aan de informatie, de overige n − k zijn ‘opvulsel’, redundantie. Het doel van codetheorie is om die n − k extra coördinaten efficiënt te gebruiken om ervoor te zorgen dat de informatie uit het codewoord nog te achterhalen is wanneer een deel van het codewoord onderweg verminkt of verloren is geraakt, bijvoorbeeld door ‘ruis’ op de transmissielijn. Het uitgangspunt van het model dat ten grondslag ligt aan codetheorie is steeds dat de kans klein is dat informatie verminkt overkomt. Voorbeelden 1.3.5 Het eenvoudigste voorbeeld van een foutenverbeterende code is de repetitiecode ter lengte n over F 2 : om een bit informatie (0 of 1) over te sturen wordt die bit n maal verzonden. De codewoorden zijn hier dus slechts de vectoren (1, 1, . . . , 1) en (0, 0, . . . 0) in F n2 , en de dimensie k is 1. Wanneer de ontvanger nu het woord (1, 1, 0, 1, 1) ontvangt terwijl de binaire repetitiecode van lengte 5 gebruikt wordt, zal onder de aanname dat fouten vrij zelden op treden, de conclusie moeten luiden dat hoogstwaarschijnlijk het codewoord (1, 1, 1, 1, 1) werd uitgezonden, maar dat op de derde positie een fout optrad. Ook wanneer er onderweg de uitzonderlijke pech optreedt dat twee bits worden omgezet kan de ontvanger hier nog tot de juiste conclusie komen met betrekking tot de bedoelde waarde van de bit. De repetitiecode ter lengte n is dus (n−1)/2 foutenverbeterend als n oneven is: we komen tot de juiste conclusie over het bit dat overgezonden

14


moest worden mits de kans op i fouten maar (veel) kleiner is dan de kans op n − i fouten. Deze aanname, dat elk cijfer van de code met kleine waarschijnlijkheid onderweg wordt veranderd, en dat het uitgezonden codewoord de vector zal zijn geweest die in de code zit en op het kleinst mogelijke aantal plaatsen van de ontvangen vector afwijkt, leidt tot de methode om de informatie te achterhalen die maximale waarschijnlijkheidsdecodering wordt genoemd. Definities 1.3.6 Het gewicht van een vector v uit F nq is het aantal posities i waarvoor de coördinaat vi ∈ Fq niet nul is. De Hammingafstand h(v, w) tussen twee vectoren v, w uit Fnq is het aantal posities j waarop de coördinaten v en w verschillen: h(v, w) = #{j : 1 ≤ j ≤ n | v j 6= wj }, dus 0 ≤ h(v, w) ≤ n. De minimumafstand van een code C is het kleinste positieve getal d waarvoor codewoorden v, w ∈ C bestaan met h(v, w) = d. ♣ Opgave 18. Bewijs dat h(v, w) gelijk is aan het gewicht van de vector v − w. Laat ook zien dat de minimumafstand van een code gelijk is aan het minimumgewicht van de code, dat wil zeggen, de kleinste positieve g waarvoor een codewoord van gewicht g bestaat. ♣ Opgave 19. Bewijs dat de Hammingafstand een metriek definieert, dat wil zeggen, voor alle u, v, w ∈ Fnq geldt: (i) h(v, w) ≥ 0; en [h(v, w) = 0 ⇐⇒ v = w]; (ii) h(v, w) = h(w, v); (iii) h(u, v) + h(v, w) ≥ h(u, w).

Definitie 1.3.7 Een code C van lengte n over F q heet e-foutenverbeterend als geldt dat voor elke vector v ∈ Fnq er hoogstens één codewoord c ∈ C is met h(c, v) ≤ e. Dat betekent dat wanneer een codewoord op precies e plaatsen wordt verminkt, er nog steeds een uniek codewoord op afstand ≤ e is. De code heet dan bovendien e+1-foutendetecterend als geldt dat elke op e+1 plaatsen verminkte vector afstand minstens e + 1 tot alle codewoorden heeft. Het is mogelijk dat er dan meerdere codewoorden op afstand e + 1 liggen, zodat unieke decodering onmogelijk is, maar er liggen geen codewoorden op afstand ≤ e. Voorbeeld 1.3.8 (parity check) Een simpel voorbeeld van een code die 1-foutdetecterend is, maar niet foutenverbeterend, is een code van lengte (zeg) 3 over F2 die bestaat uit alle woorden van even gewicht. Wanneer er dan een woord van oneven gewicht wordt ontvangen is het duidelijk dat er minstens 1 fout is opgetreden, maar wáa´r is niet duidelijk. ♣ Opgave 20. Ga na dat voor elke lengte n de vectoren van even gewicht in F n2 een code vormen, en dat de codewoorden precies die vectoren zijn waarvoor het inproduct met de vector die uit allemaal enen bestaat, nul is.

Voorbeeld 1.3.9 (UPC) Een eenvoudig voorbeeld van foutendetectie wordt gebruikt in de streepjescode die hoort bij de Universal Product Code, UPC. Deze codering, sinds 1973 in gebruik, is terug te vinden op heel veel consumptiegoederen, en bestaat uit 12 decimale cijfers, hier te representeren als een element v ∈ Z/10Z)12 . Het eerste cijfer geeft een indicatie van het type product, de volgende 5 cijfers geven de fabrikant aan, en daarna volgen 5 cijfers voor het product.


15

Het laatste cijfer v12 is het zogenaamde check-cijfer en wordt geheel bepaald door de regel h(3, 1, 3, 1, 3, 1, 3, 1, 3, 1, 3, 1), vi = 0 ∈ Z/10Z, dat wil zeggen, 3

6 X i=1

v2i−1 +

6 X i=1

v2i = 0 ∈ Z/10Z.

Voorbeeld 1.3.10 Het international standard book number (ISBN) is een ander voorbeeld van een ‘codering’ die van een check-cijfer gebruik maakt. Het ISBN is (op te vatten als) een vector w uit (Z/11Z) 10 met de restriktie dat de eerste 9 coördinaten ongelijk aan 10 zijn; ze worden elk weergegeven als decimale cijfers, en representeren land (1 tot 3 cijfers), uitgever (1 tot 5 cijfers), en boek. Het allerlaatste cijfer is weer een element dat als check-digit dient, en dat wél elk element uit Z/11Z kan zijn, weergegeven door een decimaal (de kleinste niet-negatieve representant van de restklasse) of de letter X (die de restklasse 10 representeert. De waarde ervan wordt volledig bepaald door de regel h(10, 9, 8, 7, 6, 5, 4, 3, 2, 1), wi =

10 X i=1

(11 − i)wi = 0 ∈ Z/11Z.

Voorbeeld 1.3.11 Op de meeste producten wordt sinds 1 januari 2005 het European Article Number vermeld in plaats van de UPC. Dit EAN bestaat uit een vector x ter lengte 13 over Z/10Z, waar het laatste cijfer x 13 een check-digit is, bepaald door h(1, 3, 1, 3, 1, 3, 1, 3, 1, 3, 1, 3, 1), xi = 3

6 X i=1

v2i +

7 X i=1

v2i−1 = 0 ∈ Z/10Z.

Oude UPC aanduidingen kunnen simpel vervangen worden door een EAN door de oude vector vooraf te laten gaan door een 0. De nieuwe EAN aanduidingen geven land, fabrikant, en product met een wisselend aantal cijfers weer. Per 1 januari 2007 worden ook de oude ISB nummers vervangen door een 13-cijferige ISBN-13, die net zo is opgebouwd als de EAN; de eerste 3 cijfers van de nieuwe aanduiding (die voorlopig altijd 978 zullen zijn) staan voor het universele ‘Bookland’. ♣ Opgave 21. Ga na dat elke e foutenverbeterende code ook e − 1 foutenverbeterend is.

Stelling 1.3.12 Een code met minimumafstand d is e-foutenverbeterend dan en slechts dan wanneer d ≥ 2e + 1. Bewijs. Veronderstel dat er een vector v bestaat op afstand kleiner of gelijk e van twee codewoorden w1 en w2 . Dan is h(w1 , w2 ) ≤ h(w1 , v) + h(v, w2 ) ≤ 2e, hetgeen in tegenspraak is met d ≥ 2e + 1, tenzij w 1 = w2 . Dus is er hoogstens één vector op afstand ten hoogste e als de minimumafstand ten minste 2e + 1 is. Is daarentegen de minimumafstand d hoogstens 2e, dan zijn er twee codewoorden u, w op afstand d ≤ 2e van elkaar. Vorm nu een rij u = x1 , x2 , . . . , xd , xd+1 = w

16


ter lengte d + 1 van vectoren, waarbij x i+1 steeds op precies 1 coördinaat van xi verschilt. Dan is er een vector v = xbd/2c die op hoogstens e coördinaten van u en op niet meer dan e coördinaten van w verschilt. Dus kunnen e fouten niet uniek verbeterd worden. ♣ Opgave 22. Laat zien dat een andere formulering van dezelfde stelling is: een code is e foutenverbeterend dan en slechts dan als alle verschillende bollen met straal e om codewoorden disjunct zijn.

De centrale vraag voor de coderingstheorie is gelegen in de spanning tussen de twee eisen die we graag aan codes zouden opleggen. In de eerste plaats willen we zoveel mogelijk informatie oversturen, dat wil zeggen de rate k/n zo groot mogelijk maken (en de redundantie klein). Anderzijds willen we graag zoveel mogelijk fouten kunnen herstellen, dus e (en daarmee d volgens de Stelling) zo groot mogelijk kiezen; maar een grote minimumafstand betekent veel vectoren buiten de codewoorden, dus juist een lage rate. Er bestaan heel veel grenzen op de omvang van goede codes. We geven hier een bekende bovengrens op het aantal codewoorden als de dimensie en het aantal fouten e dat verbeterd moet kunnen worden gegeven is. Stelling 1.3.13 (Hamming grens) Een code over F q van lengte n en minimumafstand groter of gelijk 2e + 1 heeft hoogstens Pe

i=0

codewoorden.

qn n i

(q − 1)i

Bewijs. Alle bollen met straal e rond codewoorden moeten disjunct zijn. Deze bevatten in totaal e X n (q − 1)i #C · i i=0 vectoren, omdat een woord op afstand i van codewoord w op ni plaatsen op (q − 1)i manieren van v kan verschillen. Dit aantal vectoren is begrens door q n , waaruit de grens volgt. Opmerkingen 1.3.14 Veronderstel nu dat we een k-dimensionale code willen construeren in een n-dimensionale vectorruimte over F q (met k < n). Het volstaat dan om k onafhankelijke vectoren te kiezen, en C te laten bestaan uit de F q -lineaire combinaties van deze k basisvectoren, die we soms schrijven als een k × n matrix G. We hoeven codewoorden dan niet meer te geven door de n coördinaten uit Fnq , maar het volstaat om de k coördinaten uit Fq van de vector ten opzichte van de gekozen basis (de rijen van de generatormatrix) te geven! Een andere manier om een k-dimensionale deelruimte van F nq te bepalen, is door n − k onafhankelijke lineaire vergelijkingen op te schrijven en daarvan de oplossingsruimte te bepalen: de k-dimensionale ruimte is dan de kern van een n × (n − k) matrix H. Het verband tussen de generatormatrix G en de parity-checkmatrix H wordt dan precies gegeven door de relatie G · H = 0. De codewoorden zijn die vectoren die lineaire combinatie van de rijen van G zijn, en dat zijn ook precies die vectoren die standaardinproduct 0 hebben met de kolommen van H.


17

Voorbeeld 1.3.15 ( binaire Hamming code ) We construeren een code ter lengte n = 7 over F2 van dimensie k = 4. Laat de rijen van de matrix H bestaan uit alle mogelijke drietallen bits, met uitzondering van 3 nullen; een systematische manier om dat te doen is door de binaire schrijfwijze van alle getallen van 1 tot en met 7 te gebruiken. Laat deze 7 × 3 matrix de parity-checkmatrix van de code C3 over F2 zijn; de codewoorden zijn dus die rijvectoren ter lengte 7 over F 2 die inproduct nul hebben met elk van de drie kolommen van H. Daarvan zijn er 2 4 . Algemener, voor r ≥ 2 schrijven we zo een 2 r − 1 × r parity-checkmatrix Hr op door de binaire schrijfwijze van de getallen 1, 2, . . . , 2 r − 1 in r bits als rijen te nemen. We vinden dan een code van dimensie (2 r − 1) − r. Deze Hammingcode is altijd 1-foutenverbeterend. ♣ Opgave 23. Wat is de rate van Cr ?

18


Hoofdstuk 2

Ringen en polynomen Inleiding In dit Hoofdstuk hebben we systematisch enkele resultaten verzameld over ringen, vooral polynoomringen, die we elders willen gebruiken.

2.1

Ringen

We herhalen eerst de definitie van ring. Definities 2.1.1 Een commutatieve ring met 1, is een verzameling V met daarop twee bewerkingen + en ×, die voldoen aan:

[L1] + op V is associatief: (x + y) + z = x + (y + z), voor alle x, y, z ∈ V ; [L2] er is een (nul)element 0 ∈ V zodanig dat 0 + x = x + 0 = x voor alle x ∈ V ; [L3] bij elke x ∈ V is er een tegengestelde −x ∈ V zodanig dat x + (−x) = (−x) + x = 0; [L4] + op V is commutatief: x + y = y + x voor alle x, y ∈ V ; [L5] × op V is associatief: (x × y) × z = x × (y × z), voor alle x, y, z ∈ V ; [L6] er is een (eenheids)element 1 ∈ V zodanig dat 1 × x = x × 1 = x voor alle x∈V; [L8] × op V is commutatief: x × y = y × x voor alle x, y ∈ V ; [L9] de operatie × is distributief over +, dat wil zeggen: x × (y + z) = (x × y) + (x × z) en (x + y) × z = (x × z) + (y × z), voor alle x, y, z ∈ V .

Als [L8] niet geldt hebben we een ring met 1, voor ons kortweg ring.

Opmerkingen 2.1.2 Een commutatieve ring met 1 voldoet dus aan alle eisen van een lichaam behalve de inverteerbaarheid van niet-nul elementen. Wanneer wij in het vervolg over een (commutatieve) ring spreken, bedoelen we altijd een (commutatieve) ring met 1. Voor een deelring U van V eisen we ook dat het eenheidselement 1 ∈ V in U zit (en daar het eenheidselement is). ♣ Opgave 24. Laat (R, +, ×) een ring zijn; bewijs dat een deelverzameling S van R een deelring is als: (i) 1R ∈ S; (ii) als a, b ∈ S dan ook a − b ∈ S; (iii) als a, b ∈ S dan ook a × b ∈ S.

19

20

HOOFDSTUK 2. RINGEN EN POLYNOMEN

♣ Opgave 25. Laat zien dat de deelverzameling van Z bestaande uit de even getallen voldoet aan L1–5 en L8–9. Dit is een commutatieve ring zonder eenheidselement, die we niet als deelring van Z beschouwen omdat 1 er niet in zit.

Voorbeelden 2.1.3 De belangrijkste voorbeelden van ringen zijn, naast de lichamen, voor ons de volgende. (i) De gehele getallen Z, met de gewone optelling en vermenigvuldiging; dit is een commutatieve ring. (ii) De ring Z/mZ, de restklassenring modulo m, voor een geheel getal m > 1, met de gebruikelijke optelling en vermenigvuldiging van restklassen, zoals gedefinieerd in 1.1.6. Dit is steeds een commutatieve ring. (iii) Als R een commutatieve ring met 1 is (bijvoorbeeld één van de ringen of lichamen die we hierboven zagen) kun je daaruit een nieuwe ring R[x] van polynomen met coëfficiënten bestaat uit de Pn in R nmaken: de verzameling 2 polynomen of veeltermen i=0 ai x = a0 + a1 x + a2 x + · · · + an xn , waar n ≥ 0 een geheel getal is. De operaties zijn de optelling van polynomen: n X

m X

i

ai x +

i=0

max(m,n)

j

bj x =

j=0

(

i=0

i

ai x ) × (

m X

(ai + bi )xi ,

i=0

en de vermenigvuldiging van polynomen n X

X

j

bj x ) =

j=0

m+n X

(

k X

k=0 i=0

ai × bk−i )xk .

Hier nemen we ai = 0 voor alle i > n en bj = 0 voor j > m. Deze polynoomring R[x] is zelf weer een commutatieve ring met 1, maar geen lichaam omdat bijvoorbeeld het polynoom x geen inverse heeft. In Lineaire Algebra 1 en 2 heb je al kennis gemaakt met het speciale geval R = R. (iv) In Lineaire Algebra 1 en 2 heb je ook gezien dat je vierkante matrices van reële getallen kunt optellen en vermenigvuldigen. Veel algemener kunnen we bij elke commutatieve ring met 1 een nieuwe ring van n × n matrices M n (R) met coëfficiënten in R maken: de verzameling bestaat uit vierkante n × n matrices, en de operaties zijn de optelling van matrices, waar de som van     b11 b12 · · · b1n a11 a12 · · · a1n  b21 b22 · · · b2n   a21 a22 · · · a2n   . en  ..  .. ..  .. .. ..  ...   .. . . .  . . . an1

an2

···

gedefinieerd is door  a11 + b11  a21 + b21  ..  .

an1 + bn1

bn1

ann

a12 + b12 a22 + b22 .. .

··· ··· .. .

an2 + bn2

···

en vermenigvuldiging van matrices, middels Pn  Pn a × b a1i × bi2 1i i1 Pi=1 Pi=1 n  ni=1 a2i × bi1 i=1 a2i × bi2  . ..  . Pn . Pn . i=1 ani × bi2 i=1 ani × bi1

bn2

···

 a1n + b1n a2n + b2n   ..  .

bnn

ann + bnn

het product P · · · Pni=1 a1i × bin  n ··· i=1 a2i × bin   .. ..  . . Pn ··· i=1 ani × bin

2.2. EENHEDEN EN NULDELERS

21

Met andere woorden: optellen en vermenigvuldigen van zulke matrices doe je op precies dezelfde manier als waarop je dat eerder hebt gezien in het speciale geval dat alle coëfficiënten reëel waren. Voor elke n ≥ 1 krijgen we zo (voor gegeven commutatieve ring R) een ring Mn (R). Als n > 1 is die ring Mn (R) niet commutatief! ♣ Opgave 26. Wat is het eenheidselement, en wat is het nulelement in R[x]? En in Mn (R)?

We hebben gezien dat elke ring R (dus in het bijzonder elk lichaam) in ieder geval de elementen 0, 1 bevat. Maar dan moet ook 1 + 1 in R zitten, een element dat we gewoonlijk met 2 aangeven. Maar let op: het kan best zijn dat 2 gelijk is aan één van de elementen die we al opschreven: 0 of 1. Maar als 1 + 1 = 1 dan moet 1 = 0 (want tel bij beide kanten de tegengestelde −1 op), en dat hebben we juist verboden (in Voorbeeld 1.1.5(iv)). Dus 2 is een nieuw element o`f gelijk aan 0. Datzelfde argument kun je herhalen: 1 + 1 + 1 ∈ R komt al voor onder {0, 1, 2} o`f het is een nieuw element; in het eerste geval moet 1 + 1 + 1 = 0 (tenzij al gold 1 + 1 = 0). Definitie 2.1.4 Laat R een ring zijn; als er een natuurlijk getal m bestaat zodanig dat 1 + 1 + · · · + 1 = m × 1 = 0 ∈ R, dan is de karakteristiek van R het kleinste positieve natuurlijke getal met die eigenschap; als zo’n m niet bestaat is de karakteristiek per definitie 0. Als de karakteristiek van R gelijk aan 0 is, dan zijn alle elementen 1, 2, 3, . . . verschillend: er bestaat dan een injectie van Z → R. Omgekeerd, als er zo’n injectieve afbeelding bestaat moet de karakteristiek wel 0 zijn. ♣ Opgave 27. Geef voor elk natuurlijk getal m ≥ 2 twee verschillende voorbeelden van een ring van karakteristiek m.

2.2

Eenheden en Nuldelers

Vervolgens kijken we naar twee speciale soorten elementen in een ring. Definities 2.2.1 Een element r van een ring R (niet noodzakelijk commutatief) heet een eenheid in R als er een inverse voor r in R bestaat, datwil zeggen, een element t ∈ R met r × t = t × r = 1). De inverse van r geven we meestal met r −1 aan. Een element r ∈ R heet een nuldeler in R als r 6= 0 en er een element s ∈ R bestaat met s 6= 0 zodat r × s = 0 of s × r = 0. ♣ Opgave 28. Laat zien dat in een lichaam elk element dat niet 0 is een eenheid is. ♣ Opgave 29. Geef twee elementen r, s van M2 (Z) met de eigenschap dat r × s = 0 maar s × r 6= 0.

Stelling 2.2.2 Een eenheid in een ring R (niet noodzakelijk commutatief) kan geen nuldeler zijn.

22


Bewijs. Laat r ∈ R een eenheid zijn, en veronderstel dat r ook een nuldeler is. Dan is r 6= 0 en we veronderstellen dat er een s ∈ R is met s 6= 0 en r × s = 0 ∈ R. Omdat r een eenheid is, is er een t ∈ R met t × r = 1. Dan is s = 1 × s = (t × r) × s = t × (r × s) = t × 0 = 0, dus s = 0, in tegenspraak met bovenstaande. Het geval s × r = 0 gaat net zo, door rechts met t te vermenigvuldigen. De aanname dat r een nuldeler is leidt dus tot een tegenspraak. ♣ Opgave 30. Zij · een bewerking op een verzameling V . Definieer voor n ≥ 3 het product v1 · v2 · · · vn inductief (voor vi ∈ V ) door (v1 · v2 · · · vn−1 ) · vn . Laat (met behulp van inductie naar n) zien dat als · associatief is, voor alle n ≥ 3 en alle k met 1 ≤ k ≤ n−1 geldt: (v1 · v2 · · · vk ) · (vk+1 · · · vn ) = v1 · v2 · · · vn . ♣ Opgave 31. Bewijs dat het eenheidselement 1 ∈ R uniek bepaald is. ♣ Opgave 32. Geef een voorbeeld van een ring zonder nuldelers waarin niet elk element (ongelijk aan 0) een eenheid is. ♣ Opgave 33. Laat zien dat de eenheden van een ring R een groep vormen onder ×. Deze groep geven we aan met R∗ . ♣ Opgave 34. Bewijs dat Mn (R)∗ bestaat uit de n × n reële matrices met determinant ongelijk aan 0. Deze groep geven we ook wel met GLn (R) aan. Waarom is dit geen ring (voor elke n > 0)? ♣ Opgave 35. Beschrijf GLn (Z), en algemener, de groep GLn (R) voor een commutatieve ring R. ♣ Opgave 36. Bewijs dat de ring Z/nZ een lichaam is dan en slechts dan als n een priemgetal is. ♣ Opgave 37. Als V een verzameling is, geven we met P (V ) de machtsverzameling van V aan: P (V ) bestaat uit de deelverzamelingen van V . Laat zien dat (P (V ), +, ×) een commutatieve ring (met 1) wordt als we de optelling + en vermenigvuldiging × definiëren door voor deelverzamelingen A, B ⊂ V te nemen: A + B = (A ∪ B) \ (A ∩ B),

A × B = A ∩ B.

Laat ook zien dat P (V ) zo alleen een lichaam wordt als #V = 1.

2.3

Gehele getallen, polynomen, en deelbaarheid

In deze paragraaf zetten we een aantal belangrijke eigenschappen van gehele getallen en polynomen op een rijtje, vooral eigenschappen die betrekking hebben op deelbaarheid. We willen vooral laten zien hoezeer de ringen Z en L[x], voor een lichaam L, op elkaar lijken. Definities 2.3.1 Laat R een commutatieve ring (zoals altijd met 1) zijn. Als d, f ∈ R dan is d een deler van f (notatie d | f ) als er een q ∈ R bestaat met f = qd; we zeggen ook dat d het element f deelt, dat f deelbaar is door d in R, en dat f een veelvoud is van d. Een gemene deler van f, g ∈ R is een d ∈ R die zowel f als g deelt; een grootste gemene deler van f en g is een gemene deler d ∈ R van f en g met de eigenschap dat elke andere gemene deler d 0 een deler van d is. Zo’n grootste gemene deler geven we aan met ggd(f, g).

2.3. GEHELE GETALLEN, POLYNOMEN, EN DEELBAARHEID

23

♣ Opgave 38. Laat zien dat elk element van een commutatieve ring een deler is van 0. ♣ Opgave 39. Laat zien dat elk element van een commutatieve ring deelbaar is door 1.

Definities 2.3.2 Een polynoom over R is element van R[x], en dat is van de vorm f = an xn + an−1 xn−1 + · · · + a1 x + a0 , waar ai ∈ R. Zo’n polynoom bestaat dus uit een som van termen ai xi ; een polynoom dat uit één zo’n term bestaat heet ook wel een monoom. De ai uit R zijn de coëfficiënten van het polynoom; gewoonlijk schrijven we alleen termen met ai 6= 0 op (tenzij alle coëfficiënten nul zijn: we schrijven dan gewoon 0). De graad van f (notatie: deg f ) is, als f 6= 0 is, de hoogste macht van xn die met niet-nul coëfficiënt voorkomt, en de coëfficiënt van deze xn heet de kopcoëfficiënt. Als de kopcoëfficiënt 1 is noemen we het polynoom monisch. De coëfficiënt a0 heet de constante coëfficiënt. Als ai = 0 voor alle i > 0 dan heet polynoom een constant polynoom. Het nulpolynoom is het constante polynoom 0; de graad hiervan is per definitie −∞. De x in deze uitdrukkingen is de onbepaalde, onbekende, of variabele. De regels voor optellen en vermenigvuldigen (die R[x] tot een commutatieve ring maken) zagen we al in 2.1.3. Net als bij vermenigvuldiging van reële getallen schrijven we vaak f ·g of f g voor het product f ×g van polynomen. Merk op dat het nulelement, respectievelijk het eenheidselement van R[x] de constante polynomen 0, respectievelijk 1 zijn. Waarschijnlijk ben je polynomen al eerder tegengekomen als functies; het is belangrijk op te merken dat we polynomen hier niet in de eerste plaats als functies beschouwen, maar als elementen van een ring. Een polynoom f ∈ R[x] definieert wel een afbeelding f : R → R omdat we f kunnen evalueren: zo is f (r) = a n r n + · · · a1 r + a0 1 ∈ R voor f als boven. We noemen f (r) ook wel de waarde van f in r. Een nulpunt van f in R is een r ∈ R zodanig dat f (r) = 0. Als R een deelring van S is, kunnen we elementen van R via de inbedding ook als elementen van S opvatten; dat betekent dat we in dit geval f ∈ R[x] ook kunnen evalueren in een s ∈ S: f (s) ∈ S. Zo zul je geen moeite hebben om f (π) uit te rekenen als het f het polynoom x 2 − 1 met gehele coëfficiënten is. ♣ Opgave 40. Laat zien dat als R geen nuldelers heeft voor de graden van polynomen geldt: deg f g = deg f + deg g. [Let op het nulpolynoom!]

Sommige eigenschappen van R[x] hangen af van die van R; een heel belangrijk speciaal geval is dat waar R een lichaam is, dat we in deze paragraaf steeds met L aangeven. ♣ Opgave 41. Bewijs dat R[x] nuldelers heeft dan en slechts dan als R nuldelers heeft.

We bekijken nu deling met rest, eerst voor gehele getallen. Stelling 2.3.3 Bij elke n, m ∈ Z met m 6= 0 bestaan er q, r ∈ Z zodat: n = q · m + r,

0 ≤ r < |m|;

bovendien zijn deze q en r uniek bepaald. Voor polynomen geldt vrijwel eenzelfde resultaat.

24


Stelling 2.3.4 Laat R een commutatieve ring zijn; bij elke f, g ∈ R[x], bestaan er polynomen q, r ∈ R[x] zodat: f = q · g + r,

deg r < deg g;

mits de kopcoëfficiënt bn van g een eenheid in R is; bovendien zijn deze q en r dan uniek bepaald. Bewijs. Eerst bewijzen we het bestaan van q en r, met inductie naar de graad m = deg f . Omdat de kopcoëfficiënt van g inverteerbaar is, is deg g ≥ 0; we mogen ook aannemen dat m = deg f ≥ deg g = n, want anders voldoen q = 0 en r = f . Als m = 0 dan is f = a0 en g = b0 , en omdat bij aanname bn = b0 inverteerbaar is, geldt de gevraagde gelijkheid met r = 0 en q = a 0 b−1 0 . Laat nu m−n g. Als dit polynoom 0 is voldoen r = 0 en x m ≥ 1; beschouw h = f − am b−1 n m−n aan de gestelde eisen. Is dit niet het geval, dan is deg h < deg f q = am b−1 n x m−n g precies tegen elkaar wegvallen. omdat de kopcoëfficiënten van f en am b−1 n x We kunnen dan op h en g de inductiehypothese toepassen: er bestaan q 0 en r 0 met h = q 0 g + r 0 en deg r 0 < deg g; maar dan is m−n m−n + q 0 )g + r 0 , g = (am b−1 f = h + am b−1 n x n x m−n + q 0 en r = r 0 aan alle condities. en voldoen q = am b−1 n x Om de uniciteit te bewijzen veronderstellen we dat

f = q 0 · g + r 0 = q 00 · g + r 00 , beide aan de eisen voldoen. Dan is (q 0 − q 00 )g = r 00 − r 0 . Stel dat r 0 6= r 00 . Dan is q 0 6= q 00 . Omdat bn ∈ R een eenheid is, is g geen nuldeler, en dus is (zie opgave): deg(r 00 − r 0 ) = deg(q 0 − q 00 )g = deg g + deg(q 0 − q 00 ) ≥ deg g, hetgeen in tegenspraak is met deg r 00 < deg g en deg r 0 < deg g. Dus r 0 = r 00 , maar dan is (q 0 − q 00 )g = 0 en moet q 0 = q 00 . ♣ Opgave 42. Welke aanpassingen aan bovenstaand bewijs zijn nodig om het ook te laten werken voor het geval 2.3.3 van gehele getallen? ♣ Opgave 43. Geef twee polynomen f, g ∈ Z[x] waarbij je geen q, r ∈ Z[x] kunt vinden met f = q · g + r, deg r < deg g.

Om te laten zien dat gehele getallen altijd een grootste gemene deler hebben, geven we algoritme om deze te vinden. Algoritme 2.3.5 [ Euclides ] Gegeven: m, n ∈ Z; niet beide nul Levert: de positieve grootste gemene deler d ∈ Z van m en n. [1] Initialiseer: M = 0, N = m and r = n. [2] Herhaal de volgende stappen zolang r 6= 0:

(i) vervang M door N en N door r; (ii) bepaal q, r zodanig dat M = qN + r met 0 ≤ r < |N |;

[3] Lever d = |N | af.

2.3. GEHELE GETALLEN, POLYNOMEN, EN DEELBAARHEID

25

Dit algoritme termineert omdat elke keer dat stap [2] wordt uitgevoerd (mogelijk met uitzondering van de eerste!), de absolute waarde van r strikt afneemt, en dus wordt dit uiteindelijk 0. Het algoritme is correct omdat de grootste gemene deler van m en n altijd gelijk is aan de grootste gemene deler van n en r, als r de rest bij deling van m door n is. ♣ Opgave 44. Bewijs de laatste bewering. ♣ Opgave 45. Waarom levert het algoritme niet altijd een niet-negatief getal af wanneer we de absoluut-strepen in stap [3] weglaten? ♣ Opgave 46. Als m > n > 0 dan is M = m en N = n na het toepassen van stap [2]; als n > m > 0 dan geldt na het tweemaal toepasssen van stap [2] dat M = n en N = m. Laat dat zien.

In het vervolg nemen we steeds polynomen f = a m xm + am−1 xm−1 + · · · a1 x + a0 en g = bn xn + bn−1 xn−1 + · · · b1 x + b0 uit R[x], met am 6= 0 en bn 6= 0. We willen bovenstaand algoritme imiteren voor het berekenen van de grootste gemene deler van twee polynomen f en g uit R[x], met R een commutatieve ring, door herhaalde deling met rest toe te passen. Dat gaat alleen maar goed als de deler g een inverteerbare kopcoëfficiënt heeft (dus bijvoorbeeld als g monisch is). Voor het gemak nemen we aan dat alle niet-nul coëfficiënten inverteerbaar zijn door simpelweg te eisen dat R een lichaam L vormt. Algoritme 2.3.6 [ Euclides ] Gegeven: polynomen f, g ∈ L[x] over een lichaam L Levert: de monische grootste gemene deler d ∈ L[x] van f en g.

[1] Initialiseer: F = 0, G = f and r = g. [2] Herhaal de volgende stappen zolang r 6= 0: (i) vervang F door G en G door r; (ii) bepaal q, r zodanig dat F = qG + r met deg r < deg G; [3] Lever d = G/Gk af waar Gk de kopcoëfficiënt van G is.

♣ Opgave 47. Ga na dat we in stap [2] kunnen eisen dat r monisch is. Waarom moeten we dan nog steeds in stap [3] door de kopcoëfficiënt delen? ♣ Opgave 48. Als deg f > deg g > 0 dan is F = f en G = g na het toepassen van stap [2]; als deg g > deg f > 0 dan geldt na het tweemaal toepasssen van stap [2] dat F = g en G = f . Laat dat zien.

Voorbeeld 2.3.7 Bij wijze van voorbeeld bepalen we de monische grootste gemene deler van f = x6 + x4 − x3 − x en g = x5 + 2x3 + x2 + x + 1 in Q[x]. In stap [2](i) wordt F0 = 0, G0 = f en r = g; elke keer dat in het algoritme F en G vervangen worden verhogen we in dit voorbeeld de index van F i en Gi , en we geven de bijbehorende q en r dezelfde index. In stap [2](i) wordt dan F 1 = G0 = f en G1 = r = g. Deling met rest (bijvoorbeeld door een staartdeling) levert op dat F1 = x · G1 + (−x4 − 2x3 − x2 − 2x), dat wil zeggen: q1 = x en r1 = −x4 − 2x3 − x2 − 2x. Dus krijgen we F2 = G1 = x5 + 2x3 + x2 + x + 1 en G2 = −x4 − 2x3 − x2 − 2x; waarna quotiënt q2 = −x + 2 rest r2 = 5x3 + x2 + 5x + 1 geeft: F2 = (−x + 2)G2 + (5x3 + x2 + 5x + 1).

26


Vervolgens, met F3 = G2 = −x4 − 2x3 − x2 − 2x en G3 = 5x3 + x2 + 5x + 1 krijgen we q3 = 1/5x − 9/25 en r3 = 9/25x2 + 9/25: 1 9 9 9 F3 = (− x − )G3 + ( x2 + ). 5 25 25 25 Dus F4 = G3 = 5x3 + x2 + 5x + 1 en G4 = F4 = (

9 2 25 x

+

9 25 ,

waarmee

9 125 x + )G4 + 0. 9 25

Met q4 = 125/9x + 9/25 krijgen we rest 0 en daarom termineert het algoritme na 9 het afleveren van G4 / 25 = x2 + 1. Stelling 2.3.8 In een polynoomring L[x] over een lichaam L heeft elk tweetal polynomen f, g, niet beide 0, een grootste gemene deler d; deze is bepaald op vermenigvuldiging met niet-nul elementen uit L na, en daarom uniek als we opleggen dat d monisch is. Het bovenstaande algoritme bepaalt deze unieke monische grootste gemene deler. Bewijs. Als f = 0 dan is g een grootste gemene deler van f en g en omgekeerd; dus we nemen nu aan (zonder beperking der algemeenheid) dat deg f ≥ deg g ≥ 0. De crux van het bewijs is de opmerking dat als d een gemene deler is van f en g, dan ook van elke lineaire combinatie af + bg: immers, als f = ud en g = vd voor zekere u, v ∈ R[x] dan is af + bg = aud + bvd = (au + bv)d. Passen we dit toe op r = f − qg, met q, r bepaald uit deling met rest, dan zien we dat d een gemene deler is van f, g dan en slechts dan als het gemene deler van g, r is: dus is de grootste gemene deler van f, g, gelijk aan de grootste gemene deler van g, r, mits één van beide bestaat. Dit argument gaan we herhalen, als in het algoritme van Euclides. Laat daartoe F1 = f en G1 = g en laat d een gemene deler van f en g zijn. Bepaal q1 en r1 zodat F1 = q1 G1 +r1 ; dan zijn de gemene delers van F1 , G1 dezelfde als die van G1 , r1 . We vervangen daarom het paar F1 , G1 door F2 = G1 , G2 = r1 , met dezelfde gemene delers, maar met deg G 2 = deg r1 < deg G1 . Zo vinden we uit een paar Fi , Gi een nieuw paar Fi+1 , Gi+1 met dezelfde gemene delers, maar met deg Gi+1 < deg Gi . Na eindig veel stappen vinden we Gh met deg Gh ≥ 0 en deg Gh+1 = −∞, dat wil zeggen, dat Gh+1 = 0. We zijn terug in de situatie die we allereerst bekeken en nu hebben F h+1 = Gh en Gh+1 = 0 een grootste gemene deler Gh . Dat toont in alle gevallen het bestaan van een grootste gemene deler aan. Uniciteit volgt omdat voor twee verschillende grootste gemene delers d en d 0 enerzijds geldt dat d = qd0 en anderzijds d0 = q 0 d. Tesamen is d = qq 0 d, dus (1 − qq 0 )d = 0. Als d 6= 0 dan moet 1 − qq 0 = 0 (want L[x] heeft geen nuldelers), dus qq 0 = 1. Dan zijn q en q 0 polynomen van graad 0, dus constanten. Dat bewijst dat d en d0 een constante factor schelen; eisen we dat de grootste gemene deler monisch is, dan is deze dus uniek bepaald. Een kleine toevoeging aan het algoritme van Euclides maakt het mogelijk niet alleen de monische grootste gemene deler d = ggd(f, g) van 2 polynomen te vinden, maar daarbij zogenaamde multiplicatoren s, t ∈ R[x] met de eigenschap dat d = s · f + t · g.

2.4. FACTOREN EN NULPUNTEN

27

Stelling 2.3.9 (uitgebreide ggd) In L[x] bestaat bij elk tweetal polynomen f, g, niet beide nul, een uniek tweetal s, t ∈ L[x] zodanig dat s · f + t · g = d waar d de monische grootste gemene deler van f en g is, en zowel deg s < deg g als deg t < deg f . Opmerking 2.3.10 Het vinden van de multiplicatoren vereist slechts een beetje boekhouden bij het uitvoeren van het algoritme van Euclides. Het opschrijven hiervan kost onevenredig veel ruimte en laten we hier achterwege. Voorbeeld 2.3.11 In het voorgaande voorbeeld vinden we: 5 1 7 5 1 2 ( x2 − x− )·(x6 +x4 −x3 −x)+(− x3 + x2 − x+1)·(x5 +2x3 +x2 +x+1) = x2 +1. 9 9 9 9 9 9

2.4

Factoren en Nulpunten

Vervolgens houden we ons bezig met de vraag hoe polynomen met coëfficiënten uit een lichaam in factoren uiteen vallen. Wederom is de analogie met Z treffend. De volgende eenvoudige stelling drukt uit dat in een commutatieve ring delers van graad 1 van een gegeven polynoom corresponderen met nulpunten van dat polynoom. Stelling 2.4.1 Als a ∈ R en f ∈ R[x] dan geldt: x−a

deelt

f

⇐⇒

f (a) = 0.

Bewijs. Als f deelbaar is door x − a dan is f = q(x − a), voor zekere q ∈ R[x]. Evalueren in a geeft f (a) = q(a) · 0 = 0 ∈ R. Voor de omkering pas je deling met rest toe op f en g = x − a: er is een q ∈ R en een r ∈ R[x] van graad kleiner dan 1 (dus een constante r0 ∈ R) zodat f = q(x − a) + r0 . Maar dan is 0 = f (a) = q(a) · 0 + r0 , dus r0 = 0 en f = q(x − a) is deelbaar door (x − a). De stelling geeft dus een eenvoudige methode om te controleren of een polynoom deelbaar is door x − a: reken f (a) uit. Als de deling opgaat (dus f (a) = 0) zul je nog wel een berekening (bijvoorbeeld een staartdeling) uit moeten voeren om het quotient te vinden. ♣ Opgave 49. Ga van het polynoom f = x6 + x5 − 2x4 + x2 + x − 2 ∈ Z[x] na door welke twee polynomen x − i met i ∈ {−2, −1, 0, 1, 2} het deelbaar is. Voer de deling q = f /((x − i1 )(x − i2 )) voor die waarden ook uit. ♣ Opgave 50. Bewijs dat f ∈ R[x] door x deelbaar is dan en slechts dan als a0 = 0. P ♣ Opgave 51. Bewijs dat f ∈ R[x] door x−1 deelbaar is dan en slechts dan als ai = 0.

♣ Opgave 52. Laat f ∈ R[x] en z ∈ C; bewijs dat f (z) = 0 impliceert dat f (¯ z) = 0 (waar z¯ de complex geconjugeerde van z is).

De stelling die we beneden willen formuleren zal laten zien dat in L[x] we elementen (net als gehele getallen) in factoren kunnen ontbinden. Stelling 2.4.2 (Hoofdstelling der Rekenkunde) Elk natuurlijk getal n ≥ 2 is te schrijven als product van positieve machten van verschillende priemgetallen; deze schrijfwijze is uniek op volgorde van de factoren na.

28


Eerst moeten we de elementen definiëren die voor polynomen de rol van priemgetallen zullen overnemen. Definities 2.4.3 Een element r ∈ R in een commutatieve ring R zonder nuldelers heet irreducibel in R als geldt: r 6= 0 en r is geen eenheid maar als r = s · t met s, t ∈ R dan is s een eenheid of t is een eenheid in R. Als r wel als zo’n product van niet-eenheden is te schrijven heet hij reducibel. Voorbeelden 2.4.4 In een lichaam is elk element nul of een eenheid en zijn er dus geen irreducibele elementen. In Z zijn de irreducibele elementen precies de priemgetallen en de reducibele elementen de samengestelde getallen. In een polynoomring R[x] over een commutatieve ring R zonder nuldelers heten de irreducibele elementen irreducibele polynomen. Als R = L een lichaam is, dan zijn de irreducibele elementen de polynomen f ∈ R[x] met deg f ≥ 1 waarvoor geen polynomen g, h ∈ R[x] bestaan zodat f = g ·h en zowel deg g < deg f als deg h < deg f . Als R geen lichaam is zijn er in het algemeen ook nog irreducibele elementen uit R in R[x] (irreducibele polynomen van graad 0). Lemma 2.4.5 Laat p, f, g ∈ L[x] met L een lichaam. Als p irreducibel is en p is een deler van f · g, dan is p een deler van f of g. Bewijs. Veronderstel dat het irreducibele polynoom p geen deler is van f . Dan is de monische grootste gemene deler van p en f dus 1, en bestaan er volgens 2.3.9 polynomen s, t ∈ L[x] zodat 1 = s · p + t · f . Omdat p een deler is van f · g is er ook een h ∈ L[x] met p · h = f · g. Maar bij elkaar geeft dat g = g · 1 = g · (s · p + t · f ) = s · p · g + t · f · g = s · p · g + t · p · h = p · (s · g + t · h), dus p deelt g. Stelling 2.4.6 Elk monisch polynoom f ∈ L[x] over een lichaam is te schrijven als product van positieve machten van monische, irreducibele polynomen uit L[x] zijn; deze schrijfwijze is uniek op volgorde van de factoren na. Bewijs. Dat elke monische f een ontbinding als product van monisch irreducibele factoren heeft kan met inductie (naar de graad m van) f bewezen worden. Elke f ∈ L[x] van graad 1 is irreducibel. Is f met deg f = m > 1 zelf irreducibel, dan zijn we klaar, en anders zijn er g, h ∈ L[x] zodat f = g · h, die beide graad kleiner dan m hebben en dus op grond van de inductiehypothese als product van irreducibele polynomen te schrijven zijn. Hun product geeft dan zo’n ontbinding voor f , die na het bij elkaar nemen van gelijke irreducibele factoren een product als in de Stelling geeft. De eenduidigheid hiervan is als volgt in te zien: veronderstel dat er twee ontbindingen p1 p2 · · · pk = q1 q2 · · · ql voor f zijn, met alle pi , qj monisch en irreducibel. Dan deelt p1 het product van de qj , en dus op grond van het voorafgaande lemma (herhaald toegepast) tenminste één der q j , zeg q1 . Maar q1 is irreducibel en monisch evenals p1 , dus p1 = q1 . Nu is p1 (p2 · · · pk − q2 · · · ql ) = 0, dus p2 · · · pk = q2 · · · ql , en we kunnen hetzelfde argument herhalen. Uiteindelijk vinden we dan dat k = l en (eventueel na hernummering van de q j ) dat pi = qi voor 1 ≤ i ≤ k. Hetgeen te bewijzen was. ♣ Opgave 53. Wat gaat er fout in de stelling als we ‘monisch’ weglaten?


29

Opmerkingen 2.4.7 De stelling geeft het beoogde analogon van priemfactorontbinding in Z. Een commutatieve ring zonder nuldelers waarin elk element (op volgorde van factoren en vermenigvuldiging met eenheden na) uniek als product van irreducibele elementen geschreven kan worden heet een factorontbindingsring. We weten nu dat Z en L[x] (voor elk lichaam L) een factorontbindingsring is. Algemener geldt zelfs dat R[x] een factorontbindingsring is als R het zelf is; dus geldt bijvoorbeeld ook in Z[x] eenduidige priemfactorontbinding. Maar het algemene bewijs is iets lastiger. Om de stelling te gebruiken zouden we nog graag willen kunnen herkennen wat de irreducibele polynomen zijn in L[x]; maar dat hangt sterk af van het lichaam L. De reden dat het lichaam der complexe getallen C zo’n belangrijke rol speelt is gelegen in het feit (zoals uitgedrukt in de volgende stelling) dat het algebra¨ısch afgesloten is: elke algebra¨ısche vergelijking over C heeft een oplossing! We bewijzen deze stelling hier niet. Stelling 2.4.8 (Hoofdstelling van de Algebra) Als f ∈ C[x] en deg f 6= 0 dan is er een z ∈ C zodat f (z) = 0. Gevolg 2.4.9 Als f een monisch polynoom is dan geldt: (i) f ∈ C[x] is irreducibel ⇐⇒ deg f = 1; (ii) f ∈ R[x] is irreducibel ⇐⇒ deg f = 1 of f = x 2 + bx + c met b2 − 4c < 0. Bewijs. Als f ∈ C[x] graad groter dan 1 heeft, is er een ontbinding van f van de vorm f = (x − z) · g op grond van 2.4.1 en 2.4.8, en dus is f reducibel. Bovendien is over een willekeurig lichaam elk polynoom van graad 1 irreducibel. Als f ∈ R[x] en er is een r ∈ R met f (r) = 0, dan is, net als boven, f reducibel tenzij f van graad 1 is. Maar zo’n r bestaat niet altijd; wél is er altijd een z ∈ C met f (z) = 0. Neem nu dus aan dat zo’n z ∈ C bestaat met z ∈ / R; vanwege opgave 32 is dan ook f (¯ z ) = 0. Dan moet f deelbaar zijn door g = (x − z)(x − z¯) = x2 − (z + z¯)x + z¯ z . Omdat zowel b = −(z + z¯) ∈ R als c = z¯ z ∈ R, is g ∈ R[x]. Maar g | f en f is irreducibel in R[x], dus f = g en g is irreducibel. Bovendien is b2 − 4c = (z + z¯)2 − 4z¯ z = (z − z¯)2 < 0.

♣ Opgave 54. Bewijs dat (z − z¯)2 ≤ 0 geldt voor alle z ∈ C, en dat geldt (z − z¯)2 = 0 ⇐⇒ z ∈ R.

Opmerkingen 2.4.10 Voor een monisch kwadratisch polynoom√ f = x 2 + bx + c geeft de wortelformule natuurlijk altijd de twee nulpunten −b ± b2 − 4c en ook daaraan zie je dat f reducibel is over R als b 2 − 4c ≥ 0. Een ander direkt gevolg van 2.4.8 is dat elk polynoom f ∈ C[x] precies m = deg f nulpunten heeft, mits we een nulpunt z precies k maal tellen als (x − z) k een deler is van f maar (x − z)k+1 niet. We noemen deze k de multipliciteit van het nulpunt z. Over Q bestaan monisch irreducibele polynomen van willekeurige graad m ≥ 1; de polynomen xm − 2 zijn bijvoorbeeld irreducibel in Q[x], voor elke m ≥ 1, maar we hebben nog niet de hulpmiddelen om dat hier te bewijzen. Er volgt uit dat de √ m k k/m rationale machten 2 = 2 van 2 voor 1 ≤ k < m irrationaal zijn, dat wil zeggen, niet in Q liggen. ♣ Opgave 55. Bewijs dat in L[x], met L een lichaam, voor elk polynoom f geldt dat het aantal nulpunten (geteld met multipliciteiten) ten hoogste deg f is.

30


♣ Opgave 56. Laat aan de hand van een voorbeeld zien dat een polynoom f ∈ R[x], met R een commutatieve ring, het aantal nulpunten groter kan zijn dan de graad van f .

Een laatste overeenkomst tussen Z en L[x] ligt in de mogelijkheid tot het vormen van restklassenringen. De ring Z kon voor gegeven modulus m > 1 opgedeeld worden in equivalentieklassen a ¯ = {b ∈ Z: b ≡ a mod m}, waar b ≡ a mod m niets anders betekende dan: m deelt b − a; nog anders gezegd: de deling van b door m heeft dezelfde rest als die van a. Omdat we in L[x] ook deling met rest kunnen toepassen, krijgen we op een zelfde manier de volgende definitie. Definitie 2.4.11 De restklassenring L[x]/f , voor een f ∈ L[x] met deg f > 0, bestaat uit de verzameling equivalentieklassen g¯ = {h ∈ L[x] : h ≡ g mod f } = {g + tf : t ∈ L[x]} (waar h ≡ g mod f dan en slechts dan als f een deler is van h − g), voorzien van ¯ = g · h. ¯ = g + h en g¯ · h optelling en vermenigvuldiging, gegeven door: g¯ + h ♣ Opgave 57. Bewijs dat in L[x]/f geldt: h ∈ g¯ dan en slechts dan als bij deling met rest geldt g = qg f + r en h = qh f + r, met dezelfde rest r. ♣ Opgave 58. Ga na dat L[x]/f zo een commutatieve ring met 1 vormt.

Stelling 2.4.12 L[x]/f is een lichaam dan en slechts dan als f irreducibel is in L[x]. Bewijs. Veronderstel dat f reducibel is, dus f = g · h met deg g < deg f en deg h < deg f . Dan is f geen deler van g of h, maar wel van g · h; dus is g 6= 0 ∈ L[x]/f en h 6= 0 ∈ L[x]/f maar g · h = 0 ∈ L[x]/f , zodat g, h nuldelers zijn, en L[x]/f geen lichaam kan zijn. Dat bewijst de implicatie ⇒. Veronderstel nu dat f irreducibel is, en laat g ∈ L[x] niet deelbaar zijn door f . Dan is de monische grootste gemene deler van f en g gelijk aan 1, dus bestaan er volgens 2.3.9 polynomen s, t ∈ L[x] zodat s · f + t · g = 1, oftewel t · g = 1 + s · f : dat betekent dat t¯g¯ = ¯1 ∈ L[x]/f . Bij het willekeurige element g ∈ L[x] met g¯ 6= ¯0 vonden we dus een t ∈ L[x] zodat t¯ = g¯−1 . Elk niet-nul element in L[x]/f is kennelijk inverteerbaar: de ring L[x]/f is een lichaam. Opmerkingen 2.4.13 De voorgaande stelling geeft aan hoe lichaamsuitbreidingen gemaakt kunnen worden: begin met een lichaam L en vind een irreducibel polynoom f ∈ L[x], dan is K = L[x]/f een lichaam. Bijvoorbeeld met L = Q en 2 f = x√2 − 2 vinden we K = L[x]/(x √ − 2), een√lichaam dat bestaat uit elementen a + b 2, met a, b ∈ Q, waar a + b 2 en c + d 2 opgeteld worden volgens √ √ √ (a + b 2) + (c + d 2) = (a + c) + (b + d) 2, en vermenigvuldigd via √ √ √ (a + b 2) × (c + d 2) = (ac + 2bd) + (ad + bc) 2, √ 2 (werk de haakjes uit en gebruik dat ( 2) = 2). Dit lichaam L geven we aan met √ Q[ 2]. Als L het lichaam van p elementen is, kunnen we zo een lichaam met p n elementen construeren door een monisch irreducibel polynoom van graad n over L te vinden. Later zal blijken dat we voor elke p en elke n ≥ 2 zo’n polynoom kunnen vinden.


31

♣ Opgave 59. Vind een irreducibel polynoom van graad 2 over F3 , schrijf alle elementen op van een lichaam van 9 elementen, inclusief een tabel die bij elk tweetal hun product geeft. ♣ Opgave 60. Bewijs dat als R een ring zonder nuldelers is, de enige eenheden van R[x] de eenheden van R zijn. ♣ Opgave 61. Bepaal de monische grootste gemene deler d en multiplicatoren s, t zodanig dat sf + tg = d voor: (i) f = x3 + 1, g = x5 + 1; (ii) f = x5 + 2x4 + 3x3 + 5x2 − 3, g = x4 + x2 − 6. ♣ Opgave 62. Ontbind de volgende polynomen in irreducibele factoren in Q[x], in R[x] en in C[x]: (i) x4 − 2; (ii) x8 − 1.

♣ Opgave 63. Ontbind de polynomen x3 − 1 en x5 − x in F5 [x] in irreducibele factoren.

♣ Opgave 64. Laat L een lichaam zijn en f ∈ L[x] met deg f = 3. Bewijs: f is reducibel dan en slechts dan als f een nulpunt in L heeft. √

♣ Opgave 65. Bewijs dat met α = −1+2 −3 ∈ C de verzameling Z[α] = {a+bα : a, b ∈ Z} een ring vormt (met de gewone optelling en vermenigvuldiging). Teken de deelverzameling Z[α] ⊂ C. ♣ Opgave 66. Geef twee elementen f, g in Z[x] met grootste gemene deler 1, waarvoor géén elementen s, t ∈ Z[x] bestaan met sf + tg = 1.

32


Hoofdstuk 3

Lineaire afbeeldingen en matrices Ook voor lineaire afbeeldingen herhalen we de belangrijkste definities en stellingen uit het reële geval in de algemenere context van vectorruimten over een willekeurig lichaam L.

3.1

Lineaire Afbeeldingen

Definities 3.1.1 Een L-lineaire afbeelding tussen L-vectorruimten V en W is een afbeelding f : V → W die voldoet aan (i) f (v1 + v2 ) = f (v1 ) + f (v2 ) voor alle v1 , v2 ∈ V ; (ii) f (λv) = λf (v) voor alle v ∈ V en λ ∈ L.

Als V = W dan heet een L-lineaire afbeelding ook wel een (lineaire) transformatie of een endomorfisme. Als W = L (de L-vectorruimte van dimensie 1) dan heet een L-lineaire afbeelding ook wel een lineaire functionaal. Een isomorfisme (van vectorruimten) is een L-lineaire afbeelding die tevens bijectie is; als er een isomorfisme tussen V en W bestaat heten ze isomorf: V ∼ = W (precieser: L-isomorf, notatie V ∼ =L W ). In het speciale geval dat W = V heet zo’n isomorfisme een automorfisme. ♣ Opgave 67. Is draaiing over π/4 een Q-lineaire afbeelding op de deelruimte Q2 van R2 ? ♣ Opgave 68. Bewijs dat een L-lineaire afbeelding f van V naar W een isomorfisme is dan en slechts dan als er een L-lineaire afbeelding g van W naar V bestaat met g ◦ f = id V en f ◦ g = idW . Deze g heet de inverse van f , en noteren we met g = f −1 , en f heet dan ook wel inverteerbaar. ♣ Opgave 69. Geef een isomorfisme tussen Mm×n (L) en Lmn .

Opmerkingen 3.1.2 Net als in het reële geval volgt onmiddellijk uit de definitie dat voor L-lineaire afbeelding geldt dat voor elk natuurlijk getal n f (λ1 v1 + · · · + λn vn ) = λ1 f (v1 ) + · · · + λn f (vn ), als vi ∈ V en λi ∈ L voor 1 ≤ i ≤ n, dus f is echt lineair. Onder isomorfismen worden belangrijke lineaire eigenschappen behouden, zoals (on)afhankelijkheid. Als twee L-vectorruimten dezelfde eindige dimensie n hebben, 33

34

HOOFDSTUK 3. LINEAIRE AFBEELDINGEN EN MATRICES

dan zijn ze daarom isomorf: een isomorfisme wordt gegeven door de elementen van de basis van de één naar die van de ander af te beelden. Beide zijn dus isomorf met Ln . Bij een lineaire afbeelding f : V → W horen twee lineaire deelruimten, namelijk de kern Ker(f ) ⊂ V en het beeld Im(f ) ⊂ W . Dan is f surjectief dan en slechts dan als Imf = W , en injectief dan en slechts dan als Kerf = {0}. Ook de volgende stelling geldt weer. Stelling 3.1.3 Als f : V → W een L-lineaire afbeelding is, en V is eindig-dimensionaal, dan zijn ook Ker(f ) en Im(f ) dat, en bovendien is dim Kerf + dim Imf = dim V. ♣ Opgave 70. Laat zien dat R en C niet isomorf zijn (als R-vectorruimte). Geldt Q ∼ =Q R? ♣ Opgave 71. Geef een isomorfisme van Q-vectorruimten tussen Q[x] en Q[π]. Zijn R[x] en R[π] ook isomorf? Wat is de dimensie van R als Q-vectorruimte? ♣ Opgave 72. Geldt L∞ ∼ =L L[x]?

3.2

Matrices

Net als in het reële geval kunnen we L-lineaire afbeeldingen tussen eindig-dimensionale L-vectorruimten altijd representeren met behulp van matrices; daarvoor is het nodig dat we een basis B = {b1 , . . . , bn } voor V kiezen en een basis C = {c1 , . . . , cm } voor W . Dan kunnen we f : V → W geven door middel van de matrix   m11 m12 · · · m1n  m21 m22 · · · m2n    Mf = CMfB =  . .. ..  ∈ Mm×n (L), ..  .. . . .  mm1 mm2 · · · mmn

die aangeeft wat het beeld w (als coördinatenvector ten opzichte van de basis C) is van een vector v (gegeven als coördinatenvector ten opzichte van de basis B), namelijk      w1 v1 m11 m12 · · · m1n  m21 m22 · · · m2n   v2   w2       Mf (v) =  . .. ..   ..  =  ..  = w. . . .  . . . .  .   .  mm1 mm2 · · · mmn

vn

wm

De matrix Mf is dus sterk afhankelijk van de keuze van de bases B en C. De kolommen van de matrix CMfB bestaan uit beelden van de basisvectoren f (b 1 ), . . . , f (bn ), uitgedrukt op de basis C. Het samenstellen van lineaire afbeeldingen h = g ◦ f waar f : V → W en g: W → X, correspondeert met het vermenigvuldigen van de bijbehorende matrices: Mh = Mg Mf , waarbij we dan wel moeten zorgen dat f en g gegeven worden ten opzichte van dezelfde basis C voor W : D

MhB = DMgC · CMfB .

3.2. MATRICES

35

Een transformatie f van V is inverteerbaar als er een inverse transformatie f −1 van V bestaat met de eigenschap dat f −1 ◦ f = f ◦ f −1 = idV , de identieke afbeelding op V . Voor eindig-dimensionale vectorruimten is dat equivalent met de eis dat M f een inverteerbare matrix is, en dan is M f −1 = Mf−1 . Laat V nu eindig-dimensionaal met basis B = {b 1 , b2 , . . . , bn } zijn, en f een lineaire transformatie van V die inverteerbaar is. Dan geeft f een automorfisme van V , en vormen de beelden {f (b1 ), . . . , f (bn )} ook weer een basis van V . De matrix BM B heeft in de i-de kolom de co¨ ordinatenvector van het beeld f (bi ) ten opzichte f van de basis B. Nemen we als nieuwe basis C voor V de vectoren c i = f (bi ), dan kunnen we de matrix met in de i-de kolom de coördinaten van f (bi ) = ci op basis B natuurlijk ook interpreteren als de matrix van de afbeelding die c i geschreven op basis C stuurt naar ci geschreven op basis B. Met andere woorden, B

C Mid = BMfB .

Maar dan is de matrix die de bi op basis C schrijft ook gemakkelijk te vinden: C

B Mid =

B

C Mid

−1

=

MfB

B

−1

.

C en CM B zijn van groot belang; ze geven co¨ ordinatentransforDe matrices BMid id B (v) dezelfde vector maties. Als een vector v gegeven is op basis B, dan is CMid C gemakkelijk te maar dan uitgeschreven op de basis C. Meestal is de matrix BMid vinden (omdat de kolommen de coördinaten van de nieuwe basisvectoren op de B wilt gebruiken om oorspronkelijke basis B zijn) terwijl je de inverse matrix CMid een vector op de nieuwe basis te schrijven.

Voorbeeld 3.2.1 We bekijken een eenvoudig voorbeeld in R 3 . Laat B de standaardbasis zijn, ten opzichte waarvan de vector v gegeven is. Gevraagd is om de vector v uit te drukken op een nieuwe basis C, als bijvoorbeeld         2 1  5  −1 v =  2 , C =  0 , 1 , 1  .   0 0 1 3 Omdat de vectoren c1 , c2 , c3 hier een mooie ‘diagonaalvorm’ hebben, kun je het juiste antwoord direct aflezen: v = 3c 3 − c2 − 4c1 . In het algemeen is dat niet zo eenvoudig, maar volgt het antwoord uit C

B Mid (v) =

B

C Mid

−1

(v),

C als kolommen c , c , c op basis B heeft. Hier dus: waar BMid 1 2 3

    −1    −4 5 −1 2 −1 5 −1 2 1  0 1 1   2  =  0 1 −1   2  =  −1  , 3 3 0 0 1 3 0 0 1 

hetgeen overeenkomt met wat we al zagen.

C zijn. Dan zijn we in staat om van een lineaire transLaat Φ nu de matrix BMid formatie g van V gegeven ten opzichte van de basis B, ook de matrix van g ten opzichte van de nieuwe basis C te bepalen. Immers, om g ten opzichte van C te

36


bepalen kunnen we eerst vectoren herschrijven van C naar B, dan de g ten opzichte van B nemen en tenslotte weer teruggaan naar de basis C. Dus: C

MgC = Φ−1 · BMgB · Φ.

Matrices A, B ∈ Mn×n (L) waarvoor een inverteerbare C ∈ M n×n (L) bestaat zodat A = C −1 · B · C heten geconjugeerd (met elkaar, in M n×n (L)). Het belangrijkste thema van de volgende hoofdstukken zal zijn om een met A geconjugeerde matrix te vinden die prettigere eigenschappen heeft dan A zelf, met andere woorden, om door overgang op een andere basis een mooiere matrix voor een gegeven afbeelding te vinden. ♣ Opgave 73. Laat zien dat ‘geconjugeerd zijn’ een equivalentierelatie op Mn×n (L) definieert.

Voorbeeld 3.2.2 We geven een toepassing in V = R 2 , namelijk om de matrix M` te bepalen, ten opzichte van de standaardbasis, van de lineaire afbeelding ` die een gegeven vector spiegelt in de lijn y = 3x. Laten we een speciale basis B = {b 1 , b2 } kiezen voor R2 , en wel zo dat de eerste basisvector b 1 op ` ligt, en de tweede er loodrecht op staat. Dus, bijvoorbeeld, 1 −3 b1 = , b2 = . 3 1 De matrix BM`B voor spiegeling in de lijn y = 3x ten opzichte van de basis B voor R2 is eenvoudig, immers het beeld van b 1 (die op ` ligt) is b1 zelf, en van b2 (die loodrecht op ` staat) wordt het spiegelbeeld −b 2 ; met andere woorden: 1 0 B B M` = . 0 −1 Volgens het bovenstaande is MÈ = Φ−1 · BM`B · Φ,

E

E aangeeft hoe e in B uit te drukken. Nu is waar Φ = BMid i −3 −3 1 −3 1 1 1 + = b1 + b2 , e1 = = 1 0 10 3 10 10 10 1 3 1 3 0 1 −3 e2 = = + = b1 + b2 , 1 3 1 10 10 10 10

dus B

E Mid

E

zodat E

MÈ

=

1 −3 3 1

=Φ=

B Mid

−1

=Φ

1 0 0 −1

=

1 10 −3 10

3 10 1 10

1 −3 3 1 1 10 −3 10

3 10 1 10

,

,

=

−8 10 6 10

6 10 8 10

.

In dit geval was het gemakkelijk om Φ −1 op te schrijven, en moesten we moeite doen om Φ te vinden.

3.3. DETERMINANT

3.3

37

Determinant

Tot slot van deze sectie vatten we eigenschappen van de determinant samen. Deze eigenschappen kunnen voor een willekeurig lichaam L geheel analoog aan het geval L = R afgeleid worden; de determinant wordt dan gedefinieerd als de unieke alternerende multilineaire afbeelding op M n×n (L) die waarde 1 heeft op de eenheidsmatrix In . De cofactor van Aij is (−1)i+j det A(i,j) , waar A(i,j) de (n − 1) × (n − 1)-matrix is verkregen uit A door daaruit de i-de rij en de j-de kolom weg te laten. Dan geldt in de eerste plaats (en dit kan zelfs als definitie voor de determinant genomen worden) dat: (1) det(A) = A11 als A ∈ M1×1 (L); (2) det(A) = A11 A22 − A21 A12 als A ∈ M2×2 (L); P (n) det(A) = ni=1 (−1)i+j Aij det A(i,j) als A ∈ Mn×n (L) en 1 ≤ j ≤ n.

Hier kan deze ontwikkeling naar de j-de kolom ook vervangen worden door de ontwikkeling naar de i-de rij: P (n0 ) det(A) = nk=1 (−1)i+k Aik det A(i,k) met 1 ≤ i ≤ n.

In het bijzonder geldt voor een bovendriehoeksmatrix (waarin onder de hoofddiagonaal allemaal nullen staan) en voor Qn een benedendriehoeksmatrix (alemaal nullen boven de diagonaal) dat det A = i=1 Aii . Ook geldt voor elke A dat de determinant gelijk is aan de determinant van zijn getransponeerde (verkregen door te spiegelen in de hoofddiagonaal), dus det A = det At . Uit multilineariteit volgt ook dat: • verwisseling van twee verschillende rijen (of kolommen) van A tot vermenigvuldiging van det A met −1 leidt; • vermenigvuldiging van een rij (of kolom) van A met een scalar λ tot vermenigvuldiging van det A met λ leidt; • het optellen van een veelvoud van een rij (of kolom) van A bij een andere rij (of kolom) det A ongemoeid laat. Omdat ook geldt: det AB = det A · det B voor elk tweetal A, B ∈ M n×n (L), hebben we dat A inverteerbaar is dan en slechts dan als det A 6= 0, en dan is det A−1 = (det A)−1 ; bovendien is, als A inverteerbaar is A−1 =

T 1 1 adjA = (−1)i+j det A(i,j) , det A det A

waar de geadjungeerde adjA van A ∈ Mn×n (L) gedefinieerd is als de matrix in Mn×n (L) met op plaats i, j de cofactor (−1) j+i det A(j,i) . Let op dat dit de i, j-de cofactor van de getransponeerde van A is!

3.4

Toepassing: Regel van Cramer

De regel van Cramer geeft over elk lichaam de unieke oplossing van een stelsel van n lineaire vergelijkingen in n onbekenden wanneer deze bestaat. Laat namelijk de vergelijkingen gegeven zijn door A · x = b, waar b ∈ L n een kolomvector is en A een n × n matrix met coëfficiënten uit L. Dan heeft dit stelsel een unieke oplossing x ∈ Rn dan en slechts dan wanneer det A 6= 0, en die oplossing wordt gegeven door Ak xk = det det A , waar Ak de matrix is waarin de k-de kolom van A is vervangen door de vector b.

38


Alhoewel dit een elegante formulering geeft, is deze methode aanzienlijk omslachtiger in de praktijk dan het bepalen van de oplossing van het stelsel door middel van vegen. ♣ Opgave 74. Laat zien dat als R een commutatieve ring met 1 is, een element A ∈ Mn×n (R) inverteerbaar is als det R inverteerbaar is in R. ♣ Opgave 75. Laten f en g lineaire afbeeldingen zijn tussen L-vectorruimten V en W . Bewijs dat geldt: f = g dan en slechts dan als f (v) = g(v) voor alle v ∈ V dan en slechts dan als f (b) = g(b) voor elke b in een basis voor V . ♣ Opgave 76. Geef een isomorfisme tussen L[x](n) en Ln+1 . ♣ Opgave 77. Laat zien dat de afbeelding d die aan f ∈ L[x] diens afgeleide f 0 toevoegt een lineaire transformatie van L[x] is. Kies een basis B voor L[x] en bepaal de matrix MdB2 . Bepaal ook een basis voor de kern en voor het beeld van d2 .

Voorbeeld 3.4.1 In dit uitgewerkte voorbeeld willen we de volgende vraag beantwoorden: hoe ziet de matrix van de lineaire transformatie F van Q 2 er uit wanneer is gegeven dat 4 1 7→ F : −1 2 en −1 −1 F : 7→ . 1 −5 Omdat deze vraag alleen zinvol is wanneer we zeggen ten opzichte van welke basis voor Q2 de matrix dient te worden gespecificeerd, voegen we hieraan toe dat we het antwoord zowel willen ten opzichte van de basis waarvoor we boven de coördinaten van de vectoren hebben uitgedrukt — laten we zeggen E — als ten opzichte van de basis 1 −1 B = {b1 , b2 }, met b1 = , b2 = , 2 1 (waar de coördinaten van b1 , b2 weer ten opzichte van E zijn gegeven). Kortom, we zoeken EMFE en BMFB . Er zijn meestal veel manieren om vragen als deze op te lossen. We zullen er een paar schetsen. We beginnen met EMFE . Omdat in deze matrix de kolommen gaan bestaan uit de beelden (ten opzichte van E) van de basisvectoren 1 0 e1 = , e2 = 0 1 gebruiken we de lineariteit van F om deze beelden te vinden: 3 −1 4 −1 1 0 0 , = + )= + = F( =F 3·F −6 −5 −1 1 2 3 1 en daarmee 1 0 −1 1 −1 2 F = F( − )= − = . 0 1 1 −2 −5 3 Daarom is E

MFE =

2 1 3 −2

.

3.4. TOEPASSING: REGEL VAN CRAMER

39

In het algemeen is het niet altijd zo eenvoudig als hier om de beelden van de ei te vinden wanneer beelden van onafhankelijke vectoren b j gegeven zijn, maar uiteindelijk is dit niets anders dan het oplossen van de n stelsels vergelijkingen ei =

n X

xj bj ,

j=1

waar de xj van i zullen afhangen. In dit geval hebben we gevonden 1 2 e1 = b1 − b2 , 3 3

e2 =

1 1 b1 + b2 . 3 3

We bepalen nu BMFB door te gebruiken dat B

E E E E B MFB = BMid · MF · Mid ,

E een vector geschreven op basis E herschrijft op basis B, en EM B = waar BMid id −1 BM E de inverse operatie is. Omdat de basisvectoren b en b al zijn gegeven 1 2 id in coördinaten ten opzichte van E, weten we al dat 1 −1 E B , Mid = 2 1

immers, een lineaire combinatie van b 1 en b2 is dezelfde lineaire combinatie van de kolommetjes beschouwd als coördinaten ten opzichte van E. Maar dan is −1 1 1 1 −1 B E 3 3 . = Mid = − 32 13 2 1 Natuurlijk hadden we dit werk eigenlijk al gedaan door de vectoren e 1 en e2 boven uit te drukken in b1 en b2 , en het resultaat (opgevat als kolom-coördinaatvectoren) was ook hetzelfde. Maar dan is het vinden van BMFB nog slechts een kwestie van het vermenigvuldigen van drie matrices: 1 1 1 −2 1 −1 2 1 B B 3 3 . = MF = · · −3 −1 2 1 3 −2 − 23 13 Ter controle: we zien hier dus bijvoorbeeld dat 1 −1 4 F (b1 ) = 1 · b1 − 3 · b2 = −3· = 2 1 −1 in coördinaten ten opzichte van E, zoals aanvankelijk gegeven. Een meer rechtstreekse manier om BMFB te bepalen is analoog aan de methode die we gebruikten om EMFE te vinden: probeer de beelden F (b1 ) en F (b2 ) te schrijven als lineaire combinatie van de vectoren b 1 en b2 ; dat geeft direct de kolommen voor BMFB . In dit geval is wel weer eenvoudig te zien dat 4 1 −1 F (b1 ) = = −3· , −1 2 1 en in het algemeen kun je dat weer doen door de stelsels lineaire vergelijkingen F (bi ) =

n X

yj bj

j=1

op te lossen (de yj zullen weer afhangen van i).

40


Hoofdstuk 4

Enkele constructies 4.1

Enkele Constructies van Vectorruimten

In deze sectie zullen we een aantal constructies van vectorruimten geven die we in het vervolg zullen gebruiken. Definitie 4.1.1 [ Hom ] Als V en W twee K-vectorruimten zijn, dan vormt de verzameling van K-lineaire afbeeldingen van V naar W een K-vectorruimte, Hom K (V, W ), onder optelling gedefinieerd door (f + g)(v) = f (v) + g(v),

voor v ∈ V,

wanneer f, g beide K-lineaire afbeeldingen van V naar W zijn, en scalaire vermenigvuldiging (λf )(v) = λ · f (v), voor v ∈ V, voor elke λ ∈ K. Definitie 4.1.2 [ Duale ] Als W = K 1 noemen we Hom(V, W ) = Hom(V, K) de duale ruimte van V , en gebruiken we de notatie V ∗ = Hom(V, K), terwijl we de elementen van die duale al lineaire functionalen noemden. Stelling 4.1.3 Als V en W eindig-dimensionale vectorruimten zijn met dim V = m en dim W = n, dan is Hom(V, W ) ∼ = Mn×m (K). In het bijzonder geldt: dim Hom(V, W ) = mn, en dim V ∗ = dim V = m. Bewijs. Kies K-bases B voor V en C voor W . De afbeelding ψ: Hom K (V, W ) → Mn×m (K) die aan f ∈ HomK (V, W ) de matrix CMfB toevoegt is surjectief (want we zagen al eerder dat elke n × m matrix een K-lineaire afbeelding bepaalt), Klineair (omdat de optelling en scalaire vermenigvuldiging van lineaire afbeeldingen hetzelfde resultaat oplevert als de overeenkomstige operatie op de bijbehorende matrices), en heeft als kern slechts de nul-afbeelding (want als de beelden van alle basisvectoren nulvectoren zijn moeten alle beelden wel nul zijn). 41

42

HOOFDSTUK 4. ENKELE CONSTRUCTIES

Definities 4.1.4 Zij V een K-vectorruimte van dimensie m, en laat B = {b 1 , b2 , . . . bm } een basis voor V zijn. We definiëren de lineaire functionalen b∗1 , b∗2 , . . . , b∗m door b∗i aan v = v1 b1 + · · · + vi bi + · · · + vm bm ∈ V het element vi ∈ K toe te laten voegen; deze b∗i heten de coördinatenfuncties van V (met betrekking tot B). Op grond van de volgende stelling wordt B ∗ = {b∗1 , b∗2 , . . . , b∗m } de duale basis van V met betrekking tot B genoemd. ♣ Opgave 78. Ga na dat b∗i (bj ) = δij , waar als gebruikelijk de Kronecker-delta gegeven is door δij = 1 als i = j en δij = 0 als i 6= j.

Stelling 4.1.5 Wanneer B = {b1 , b2 , . . . bm } een basis voor V is, dan vormt B ∗ = {b∗1 , b∗2 , . . . , b∗m } een basis voor V ∗ . Bewijs. Het is duidelijk dat de b∗i elementen van V ∗ zijn, zodat het op grond van voorgaande stelling voldoende is te laten zien dat de b ∗i onafhankelijk zijn. Veronderstel daartoe dat λ1 b∗1 + λ2 b∗2 + · · · λm b∗m = 0 ∈ V ∗ , voor zekere λi ∈ K; dan is 0(bi ) = λ1 b∗1 (bi ) + λ2 b∗2 (bi ) + · · · λm b∗m (bi ) = λi , en dus zijn alle λi = 0. Hetgeen te bewijzen was. ♣ Opgave 79. Laat B = {(2, 1), (−1, 3)} Q-basis voor Q2 zijn. Bepaal B ∗ .

Stelling 4.1.6 Voor een eindig-dimensionale vectorruimte V geldt: V ∼ = V ∗∗ . Bewijs. Definieer β: V → V ∗∗ door aan v ∈ V de afbeelding vˆ: V ∗ → K toe te voegen waarvoor vˆ(u∗ ) = u∗ (v) voor elke u∗ ∈ V ∗ . Dan is het gemakkelijk in te zien dat vˆ inderdaad een lineaire functionaal op V ∗ is, dus een element van V ∗∗ . Ook is eenvoudig in te zien dat β een isomorfisme is, als volgt. Lineariteit geldt omdat β(v1 + λv2 )(u∗ ) = u∗ (v1 + λv2 ) = u∗ (v1 ) + λu∗ (v2 ) = (β(v1 ) + λβ(v2 ))(u∗ ). Veronderstel dat β(v) = 0 ∈ V ∗∗ , dat wil zeggen dat vˆ(u∗ ) = 0 voor elke u∗ ∈ V ∗ ; als v 6= 0 dan is {v} aan te vullen tot een basis {v, b 2 , . . . , bm } voor V . Maar dan is vˆ(v ∗ ) = v ∗ (v) = 1 6= 0 in tegenspraak met het bewezene, dus volgt uit β(v) = 0 dat v = 0, met andere woorden, β is injectief. Tenslotte is dim V ∗∗ = dim V ∗ = dim V , en dus is β een isomorfisme. Definitie 4.1.7 Laten V en W eindig-dimensionale K-vectorruimten zijn van dimensie m en n. Als f een K-lineaire afbeelding f : V → W is dan definiëren we de getransponeerde van f als de afbeelding f T : W ∗ → V ∗ waarvoor f T (w∗ ) = w∗ ◦ f . ♣ Opgave 80. Laat zien dat transponeren zo aan een element f ∈ Hom(V, W ) een element f T ∈ Hom(Hom(W, K), Hom(V, K)) toevoegt.

4.1. ENKELE CONSTRUCTIES VAN VECTORRUIMTEN

43

Stelling 4.1.8 Laten V en W eindig-dimensionale K-vectorruimten zijn met bases V = {v1 , . . . , vm } en W = {w1 , . . . , wn }. Dan geldt: V∗

∗

MfWT = (WMfV )T .

Bewijs. De essentiële stap in het bewijs is de volgende regel, die laat zien dat ten opzichte van de basis V ∗ de i-de coëfficiënt van f T (wj∗ ), die op plaats i, j in de matrix voor f T staat, gelijk is aan (wj∗ ◦ f )(vi ) = wj∗ (α1i w1 + · · · + αni wn ) = αji , waar αrs op plaats r, s in de matrix voor f staat. Definitie 4.1.9 [ Quoti¨ ent ] Als V een K-vectorruimte is, en U een lineaire deelruimte, dan heet voor iedere v ∈ V de verzameling v + U = {v + u: u ∈ U }, een nevenklasse van U in V . Omdat v1 + U = v2 + U dan en slechts dan als v1 − v2 ∈ U , geldt dat v1 + U en v2 + U ofwel disjunct zijn, ofwel samenvallen: (v1 + U ) ∩ (v2 + U ) =

of

v1 + U = v2 + U.

Daarom splitsen de nevenklassen de hele ruimte op in een disjuncte vereniging. Bovendien vormen de nevenklassen een vectorruimte, die we met V /U aangeven, als we optelling definiëren door (v1 + U ) + (v2 + U ) = (v1 + v2 ) + U en scalaire vermenigvuldiging door λ(v1 +U ) = (λv1 )+U . De ruimte V /U is de quotiëntruimte van U in V . Stelling 4.1.10 Als V een eindig-dimensionale vectorruimte is, dan geldt voor elke lineaire deelruimte U : dim V /U = dim V − dim U. Bewijs. Vul een basis u1 , u2 , . . . , uk van U aan tot een basis u1 , . . . , uk , uk+1 , . . ., um van V . PDan vormen uk+1 + U, . . . , um + UPeen basis voor V /U . Een m afhankelijkheid m i=k+1 λi (ui + U ) = 0 impliceert dat i=k+1 λi ui ∈ U , en dus het Pm Pk bestaan van λ1 , . . . , λk zodat i=k+1 λi ui − j=1 λj uj = 0, in tegenspraak met het gegeven dat u1 , . . . , um een basis van V P is. Anderzijds impliceert Pk datzelfde m gegeven datP elke v ∈ V te schrijven is als v = i=1 λi ui , en omdat i=1 λi ui ∈ U , is v + U = m i=k+1 λi ui + U . Als V eindig-dimensionaal is heet de dimensie van V /U wel de co-dimensie van U in V .

♣ Opgave 81. Geef een mooier (basiskeuze-vrij) bewijs van bovenstaande stelling door op de afbeelding φ : V → V /U , die aan v ∈ V de nevenklasse v + U toevoegt, de dimensiestelling 3.1.3 toe te passen.

Definitie 4.1.11 [ Directe som ] Als W een K-vectorruimte is en V1 , V2 , . . . , Vk zijn lineaire deelruimten van W , dan is de som van die deelruimten de lineaire deelruimte gedefinieerd door V =

k X i=1

Vi = V1 + V2 + · · · + Vk = {v1 + v2 + · · · + vk : vi ∈ Vi }.

44


Een som heet een directe som (en we schrijven V = V 1 ⊕ V2 ⊕ · · · ⊕ Vk ) als geldt dat elke v ∈ V op precies één manier te schrijven is als v = v 1 + v2 + · · · + vk met vi ∈ Vi voor 1 ≤ i ≤ k. ♣ Opgave 82. Ga na dat de som V1 + · · · + Vk een lineaire deelruimte van W is.

Stelling 4.1.12 Zij V een vectorruimte met lineaire deelruimten V 1 , V2 , . . . , Vk . Dan zijn de volgende beweringen equivalent: (i) V = V1 ⊕ V2 ⊕ · · · ⊕ Vk ; P (ii) V = V1 + V2 + · · · + Vk en Vi ∩ j6=i Vj = {0} voor i = 1, 2, . . . , k; (iii) B1 , B2 , . . . , Bk vormen een basis voor V als Bi een basis voor Vi is (voor 1 ≤ i ≤ k). Bewijs. ((i) ⇒ (ii)) Als V = PV1 ⊕ V2 ⊕ · · · Vk dan zeker V = V1 + V2 + · · · Vk , en veronderstel dat v ∈ Vi ∩ j6=i Vj . Dan is 0 = 0 + 0 = v + (−v) en dat P geeft twee verschillende manieren om 0 ∈ V als som van elementen van V i en j6=i Vj te schrijven, in tegenspraak met de aanname dat de som direct is, tenzij v = 0. Dus is 0 de enige vector in de doorsnede. (i) (i) ((ii) ⇒ (iii)) Laat Bi = {b1 , . . . , bni } een basis voor Vi zijn. Het is eenvoudig in te zien dat B = B1 , B2 , . . . , Bk dan een opspannend P stelsel voor V1 +V2 +· · · +Vk is. We moeten laten zien dat de voorwaarde V i ∩ j6=i Vj = {0} voor i = 1, 2, . . . , k impliceert dat B een basis is. Veronderstel eens dat B geen basis is, dan is er kennelijk een afhankelijkheid van de vorm k X j=1

(j) (j)

(λ1 b1 + · · · + λn(j)j bn(j)j ) = 0.

(i)

Veronderstel dat λr 6= 0 voor zekere 1 ≤ r ≤ ni ; als voor elke j 6= i en elke index (i) (i) (j) (i) (i) m met 1 ≤ m ≤ nj geldt dat λm = 0 dan is w = λ1 b1 + · · · + λni bni = 0 met tenminste 1 coëfficiënt ongelijk aan 0, in tegenspraak metP het feit dat B i een basis voor Vi is. Maar dan moet w 6= 0, en is w ∈ Vi en −w ∈ j6=i Vj , en dus zit w in de doorsnede van beide, in tegenspraak met onze aanname. Kennelijk kan er geen (i) λr 6= 0 bestaan: het stelsel B is onafhankelijk. ((iii) ⇒ (i)) Laat Bi een basis voor Vi zijn, en veronderstel dat B = B1 , B2 , . . ., Bk een basis voor V is; het is direct duidelijk dat V = V 1 + V2 + · · · + Vk , we moeten aantonen dat deze som direct is. Veronderstel eens dat dit niet zo is, dat wil zeggen, er is een v ∈ V die twee schrijfwijzen v = v 10 + · · · + vk0 = v100 + · · · + vk00 heeft met vi0 , vi00 ∈ Vi voor P 1 ≤ i ≤ k. Voor tenminste één i is v i0 6= vi00 ; schrijf w 0 = vi0 P 00 00 0 0 00 00 en w = vi , en ook x = j6=i vj en x = j6=i vj . Dan is w0 + x0 = w00 + x00 = v, en dus w0 − w00 = x00 − x0 . Schrijf elk van de vr0 en vr00 nu op de basis Br voor 1 ≤ r ≤ k; dan hebben we een niet-triviale lineaire combinatie van elementen van B met als som 0, in tegenspraak met de veronderstelling dat B een basis voor V is. Gevolg 4.1.13 Als V = V1 ⊕ V2 ⊕ · · · ⊕ Vk dan is dim V = dim V1 + dim V2 + · · · + dim Vk . Voorbeelden 4.1.14 Elke vectorruimte is de directe som van de 1-dimensionale deelruimten opgespannen door een basisvector. Zo is K 3 natuurlijk te schrijven als K 3 = K ⊕ K ⊕ K = K · e1 ⊕ K · e2 ⊕ K · e3 , maar ook is K 3 = K 2 ⊕ K.

4.1. ENKELE CONSTRUCTIES VAN VECTORRUIMTEN

45

Als U ⊂ V een lineaire deelruimte is, bestaat er altijd een deelruimte T ⊂ V zodat T ⊕ U = V . Dat is eenvoudig in te zien door een basis van U aan te vullen met vectoren t1 , . . . , tk tot een basis voor V . De ruimte opgespannen door de t i kan dan voor T genomen worden. De ruimte T heet in zo’n geval een complement van U . ♣ Opgave 83. Laat B = {b1 , b2 , b3 } een basis voor K 3 zijn. Laat zien dat K 3 = S1,2 +S2,3 waar Si,j voor i 6= j de ruimte opgespannen is door Bi,j = {bi , bj }. Laat ook zien dat K 3 6= S1,2 ⊕ S2,3 ; toch is B1,2 ∪ B2,3 = B. Dit is de reden dat in 4.1.12(iii) niet gewoon kunnen schrijven: ∪i Bi is een basis voor V als Bi een basis voor Vi is.

Definitie 4.1.15 De directe som van vierkante matrices A (t) ∈ Mnt ×nt (K), for t = 1, 2, . . . k, is de vierkante matrix A ∈ M n×n (K), met n = n1 + n2 + · · · + nk , gedefinieerd door:  (1) Ai,j 0 < i, j ≤ n1     (2)   n1 < i, j ≤ n2  Ai,j . .. Ai,j = .. .    (k)  A n − nk = n1 + n2 + · · · + nk−1 < i, j ≤ nk    i,j 0 elders. Dit schrijven we wel als



  A = A(1) ⊕ A(2) ⊕ · · · ⊕ A(k) =  

A(1) 0 ··· 0 (2) 0 A ··· 0 .. .. .. .. . . . . 0 0 · · · A(k)



  . 

Opmerkingen 4.1.16 Een matrix als in bovenstaande directe som A (1) ⊕ A(2) ⊕ · · · ⊕ A(k) heet wel een blok-diagonaal matrix bestaande uit k blokken. Elke matrix is een blok-diagonaal matrix bestaand uit 1 blok. Een n × n diagonaalmatrix is een blok-diagonaal matrix bestaande uit n blokken. Het verband tussen directe sommen van deelruimten en van matrices wordt gegeven in de stelling beneden; in volgende hoofdstukken zullen we ons bezighouden met het vinden van geschikte blokken. Definitie 4.1.17 Een lineaire deelruimte U van een vectorruimte V heet invariant met betrekking tot de lineaire transformatie φ als geldt dat φ(u) ∈ U voor alle u ∈ U . We schrijven ook wel φ[U ] ⊂ U . Merk op dat U niet puntsgewijs invariant hoeft te zijn, dat wil zeggen, het hoeft niet zo te zijn dat φ(u) = u voor elke u. Stelling 4.1.18 Laat een eindig-dimensionale vectorruimte V met een lineaire transformatie φ gegeven zijn, en veronderstel dat er deelruimten U 1 , U2 , . . . , Uk van V bestaan zodanig dat V = U1 ⊕ U2 ⊕ · · · ⊕ Uk en Ui is invariant ten opzichte van φ. Dan geldt: M φ = M φ1 ⊕ M φ2 ⊕ · · · ⊕ M φk ,

wanneer φi = φ|Ui de beperking tot Ui is, Mφ = MφB de matrix van φ ten opzichte van B = B1 , B2 , . . . , Bk is, en Mφi = MφBi de matrix van φi ten opzichte van Bi , voor bases Bi van Ui .

46


Bewijs Bekijk het beeld van een basis vector uit B j : dat is een lineaire combinatie van de vectoren uit Bj zelf, gegeven door de juiste kolom uit M φj . ♣ Opgave 84. Laat zien dat {0}, V , Kerφ en Imφ invariante deelruimten zijn voor elke lineaire transformatie φ van een vectorruimte V . ♣ Opgave 85. Als T en U beide K-vectorruimten zijn kunnen we hun directe product T × U definiëren als de verzameling {(t, u): t ∈ T, u ∈ U } met scalaire vermenigvuldiging λ(t, u) = (λt, λu), voor λ ∈ K. Laat zien dat T × U een K-vectorruimte is van dimensie dim T + dim U . ♣ Opgave 86. Veronderstel dat T en U beide deelruimten zijn van de K-vectorruimte V . Definieer de lineaire afbeelding φ: T × U → V door φ(t, u) = t − u voor t ∈ T , u ∈ U . Gebruik φ om te bewijzen dat dim(T + U ) − dim(T ∩ U ) = dim T + dim U .

Hoofdstuk 5

Eigenwaarden en Diagonaliseerbaarheid 5.1

Diagonaliseerbaarheid

Zoals we zagen hangt de matrix die behoort bij een lineaire transformatie af van de keuze van een basis voor de ruimte. In dit hoofdstuk buigen we ons eerst over de vraag of er altijd een basiskeuze bestaat waarvoor de matrix diagonaalvorm heeft. Definities 5.1.1 Een matrix D ∈ Mn,n (K) heet diagonaalmatrix als Di,j = 0 voor alle i 6= j, (met 1 ≤ i, j ≤ n). Een matrix M ∈ M n,n (K) heet diagonaliseerbaar als er een met M geconjugeerde matrix bestaat die diagonaalmatrix is. Een lineaire transformatie T van een eindig-dimensionale vectorruimte V heet diagonaliseerbaar als er een basis B bestaat zodat M TB een diagonaalmatrix is. ♣ Opgave 87. Laat zien dat de diagonaalmatrix D = dIn met constante diagonaal commuteert met elke andere n × n matrix.

Stelling 5.1.2 Een lineaire transformatie T van een eindig-dimensionale vectorruimte V is diagonaliseerbaar dan en slechts dan als M TB diagonaliseerbaar is voor elke basis B van V . Bewijs. Duidelijk. Laat nu T een diagonaliseerbare lineaire transformatie zijn, en B = {b 1 , b2 , . . . , bn } een basis ten opzichte waarvan MTB = D een diagonaalmatrix is. Dan is Db i = Di,i bi , met Di,i ∈ K, met andere woorden: de vectoren b i worden door D met een factor Di,i vermenigvuldigd. Omgekeerd, als je in V een basis B = {b 1 , b2 , . . . , bn } kunt vinden zodanig dat T bi = di bi , dan is MTB de diagonaalmatrix D met op de diagonaal D i,i = di . Definitie 5.1.3 Een eigenvector voor een lineaire transformatie T van de Kvectorruimte V is een v ∈ V zodanig dat v 6= 0 en T v = λv, voor zekere λ ∈ K; deze λ heet de (bij v behorende) eigenwaarde voor T . Een eigenvector voor de matrix M ∈ Mn,n (K) is een 0 6= v ∈ V met M v = λv voor zekere λ ∈ K; die λ heet de (bij v behorende) eigenwaarde voor M . De bij een eigenwaarde λ van een 47

48

HOOFDSTUK 5. EIGENWAARDEN EN DIAGONALISEERBAARHEID

transformatie T (of matrix M ) behorende eigenruimte E λ is de lineaire deelruimte van V bestaande uit de vectoren u ∈ V met T u = λu (danwel M u = λu), Eλ = {v ∈ V : T v = λv}. ♣ Opgave 88. Ga na dat Eλ een lineaire deelruimte van V is.

We hebben boven, samenvattend, zojuist de volgende stelling bewezen. Stelling 5.1.4 Een lineaire transformatie T : V → V is diagonaliseerbaar dan en slechts dan als er een basis van V is die bestaat uit eigenvectoren voor T . Opmerkingen 5.1.5 Per definitie is de eigenschap dat v een eigenvector is voor een lineaire transformatie T niet afhankelijk van de keuze van een basis B voor de vectorruimte V ; in het bijzonder zal een eigenvector van T dus een eigenvector zijn voor MTB , voor elke basis B. Omgekeerd zal een eigenvector voor een M TB eigenvector voor T en dus voor elke M TB zijn. Het is duidelijk dat de eigenruimte bij de eigenwaarde 0 de kern van de transformatie (of matrix) is. Meetkundig, over R, is een vector v eigenvector voor T als zijn beeld een (reëel) veelvoud λv van v zelf is. Is λ > 1 dan wordt de vector opgeblazen, is 0 < λ < 1 dan wordt v ingekrompen. Met λ = 1 blijft v invariant. Is λ < 0 dan wordt v eerst gespiegeld in de oorsprong, waarna hetzelfde geldt met |λ| in plaats van λ. ♣ Opgave 89. Ga na dat bovenstaande meetkundige opmerkingen omtrent een reële vectorruimte gelden voor de hele lijn µv opgespannen door een eigenvector v. ♣ Opgave 90. Geef een voorbeeld van een lineaire transformatie die geen eigenvectoren heeft.

Voorbeeld 5.1.6 Veronderstel dat A de matrix is van een lineaire transformatie van Q2 (ten opzichte van de standaardbasis) met A=

1 3 4 2

.

Een berekening leert onmiddellijk dat A

1 −1

= −2

1 −1

,

A

3 4

=5

3 4

,

n 1 3 o de transformatie gegeven zodat ten opzichte van de basis B = , 4 −1 wordt door −2 0 B . A = 0 5 Natuurlijk is het de kunst om die twee eigenvectoren te vinden.

5.2. EIGENRUIMTEN

5.2

49

Eigenruimten

In deze paragraaf is V een n-dimensionale K-vectorruimte, met n > 0. Het is niet moeilijk in te zien wat de eigenwaarden van een lineaire transformatie kunnen zijn. Immers, λ is een eigenwaarde voor T dan en slechts dan als T v = λv voor een v ∈ V met v 6= 0, dat wil zeggen (λ − T )v = 0, oftewel v ∈ Ker(λ − T ). Hier is λ de vermenigvuldiging met de scalar λ, en dat schrijven we ook wel als λI, waar I = idV , de identieke afbeelding op V . We vinden onmiddellijk de volgende stelling. Stelling 5.2.1 Zij V een eindig-dimensionale K-vectorruimte. Dan is λ ∈ K een eigenwaarde voor T dan en slechts dan als U = Ker(λI − T ) niet {0} is, en in dat geval is U de bij λ behorende eigenruimte E λ voor T . Omdat λ eigenwaarde voor T is dan en slechts dan als λ een eigenwaarde is voor M = MTB , waar B een basis voor V is, geldt dit dan en slechts dan als M v = λv = λIn v voor een v ∈ V met v 6= 0, dat wil zeggen (λI n − M )v = 0, oftewel v ∈ Ker(λIn − M ), waar In natuurlijk de n × n eenheidsmatrix is. Gevolg 5.2.2 Met notaties als boven, en B een basis voor V , geldt: λ ∈ K is eigenwaarde voor T dan en slechts als det(λI n − M ) = 0, waar M = MTB . Definitie 5.2.3 Zij M ∈ Mn×n (K); het polynoom pM (x) = det(xIn − M ) ∈ K[x] heet het karakteristieke polynoom van M . Voor een lineaire transformatie T van V met matrix M = MTB ten opzichte van een basis B voor V heet het polynoom pM ∈ K[x] een karakteristiek polynoom voor T . Lemma 5.2.4 Het karakteristieke polynoom van T hangt niet af van de keuze voor de basis B. Bewijs. Als B en B 0 twee bases voor V zijn, geldt met M = M TB en M 0 = MTB dat M = CM 0 C −1 voor zekere C ∈ Mn×n (K). Dan is pM

0

det(xIn − M ) = det(xIn − CM 0 C −1 ) = det(C(xIn − M 0 )C −1 ) = det(xIn − M 0 ) en dat is pM 0 , dat wil zeggen: de karakteristieke polynomen van M en M 0 zijn gelijk. Opmerkingen 5.2.5 We kunnen dus spreken van het karakteristieke polynoom van T , dat we met pT aan zullen geven. Bovendien hebben we bewezen dat λ ∈ K een eigenwaarde voor T is dan en slechts dan als het een nulpunt van het karakteristieke polynoom van T is. Met volledige inductie (naar n) is het duidelijk dat pT een polynoom in K[x] is van graad n. Op grond van de opgave na 2.4 weten we dan dat T niet meer dan n = dim V eigenwaarden kan hebben. Bij een gegeven eigenwaarde is de eigenruimte precies de kern van de afbeelding λI − T . ♣ Opgave 91. Bewijs dat voor het karakteristieke polynoom pT = pn xn + pn−1 xn−1 + P · · · + p1 x + p0 ∈ K[x] van T : V → V geldt dat pn = 1, dat pn−1 = − i Mi,i en dat P p0 = (−1)n det M , waar M = MTB voor een willekeurige basis B voor V . De som i Mi,i van diagonaalelementen wordt het spoor van de matrix M genoemd.

50


Voorbeeld 5.2.6 Laat A=

1 1 4 1

de matrix van een lineaire transformatie van Q 2 ten opzichte van de standaardbasis zijn. Teneinde de eigenwaarden van A te vinden bepalen we λ − 1 −1 = (λ − 1)2 − 4 = (λ − 3)(λ + 1). det(λI2 − A) = −4 λ − 1 De eigenwaarden van de bij A horende transformatie zijn dus 3 en −1. Om E3 te vinden, moeten we Ker(3I2 − A) bepalen, dat wil zeggen de kern van de matrix waarvan we hierboven de determinant uitrekenden, met λ = 3 ingevuld: 2 −1 . E3 = Ker(3I2 − A) = Ker −4 2

v1 in de eigenruimte E3 geeft dat maar één lineaire condiv2 tie, namelijk 2v1 = v2 . De eigenruimte bestaat dan uit alle (rationale) veelvouden 1 van . 2 Net zo is E−1 de kern van

Voor vectoren v =

−2 −1 −4 −2

,

n −1 o zodat E−1 = µ :µ ∈ Q . 2

n 1 Om de matrix van de transformatie ten opzichte van de basis B = , 2 −1 o in plaats van de standaardbasis te bepalen, kunnen we volgens 3.2 dus 2 A conjugeren met de matrix ΦE,B die een vector gegeven in basis B coordinaten uitdrukt in coordinaten ten opzichte van de standaardbasis; maar dan is 1 −1 MΦ = , 2 2 en dus de gevraagde matrix B

A =

MΦ−1 AMΦ

=

1 −1 2 2

−1

1 1 4 1

1 −1 2 2

.

Anderzijds weten we natuurlijk al precies wat het resultaat zal zijn: immers B is een basis bestaande uit eigenvectoren, en omdat de bijbehorende eigenwaarden 3 en −1 zijn zal het resultaat 3 0 B A = 0 −1 moeten zijn!

5.2. EIGENRUIMTEN

51

♣ Opgave 92. Ga na dat de identiteit AB = MΦ−1 AMΦ inderdaad geldt.

De grootste nog resterende complicatie is gelegen in de mogelijkheid dat eigenwaarden met zekere multipliciteiten voorkomen. Definitie 5.2.7 De (algebra¨ısche) multipliciteit van een nulpunt α ∈ K van een polynoom f ∈ K[x] is de grootste k ≥ 1 waarvoor (x − α) k het polynoom f deelt in K[x]. Eerst laten we zien dat de situatie overzichtelijk is wanneer alle multipliciteiten 1 zijn. Stelling 5.2.8 Als xi eigenvector van T is met eigenwaarde λ i , en λi 6= λj voor 1 ≤ i < j ≤ k, dan zijn x1 , x2 , . . . , xk lineair onafhankelijk. Bewijs. Inductie naar k. Voor k = 1 is de stelling zeker waar. Veronderstel eens dat µ1 x1 + µ2 x2 + · · · + µk xk = 0, met k > 1, en xi als in de stelling. Er geldt dan (T −λk )(µ1 x1 +µ2 x2 +· · ·+µk xk ) = (λ1 −λk )µ1 x1 +· · ·+(λk−1 −λk )µk−1 xk−1 = 0. Op grond van de inductiehypothese is x 1 , x2 , . . . , xk−1 lineair onafhankelijk, dus (λj − λk )µj = 0, voor j = 1, 2, . . . , k − 1, en omdat λj 6= λk moet µj = 0, voor j = 1, 2, . . . , k − 1. Maar dan ook µk = 0, en we zijn klaar! Gevolg 5.2.9 Als T over K precies n verschillende eigenwaarden heeft is T diagonaliseerbaar over K. Bewijs. De n = dim V verschillende eigenvectoren x i zijn op grond van voorgaande stelling onafhankelijk en vormen dus een basis voor V , ten opzichte waarvan T diagonaalvorm heeft. Let wel dat er in feite twee voorwaarden staan in dit gevolg: alle nulpunten van het karakteristieke polynoom moeten in K liggen en ze moeten ook allemaal verschillend zijn! ♣ Opgave 93. Geef een voorbeeld van een lineaire transformatie van Q2 die pas aan de voorwaarden van het gevolg voldoet als we hem opvatten als transformatie van R 2 .

Stelling 5.2.10 Als T een diagonaliseerbare transformatie van de eindig-dimensionale K-vectorruimte V is, dan splitst het karakteristieke polynoom p T (x) ∈ K[x] in K[x] volledig in lineaire factoren. Bewijs. Ten opzichte van zekere basis is T een diagonaalmatrix; op de diagonaal staan dan de eigenwaarden λi van T . Die moeten in het lichaam K zitten, en dus valt pT over K uiteen in de lineaire factoren x − λ i . Let wel: het belangrijkste van de laatste stelling is dat p T al over het lichaam K in lineaire factoren uiteen valt. Dat garandeert natuurlijk nog niet dat alle eigenwaarden verschillend zijn. De omkering van Stelling 5.2.10 blijkt ook niet te gelden!

52


Voorbeeld 5.2.11 Beschouw de lineaire transformatie van Q 3 gegeven door   3 1 −2 A =  −1 0 5 . −1 −1 4 Het karakteristieke polynoom van A is

det |λI3 − A| = (λ − 2)2 (λ − 3). Om E2 te bepalen kijk je naar de kern van   −1 −1 2  1 2 −5  ; 1 1 −2

omdat de rang van deze matrix 2 is, zal de kern dimensie 1 hebben. Daarom is E 2 ook 1-dimensionaal, net als E3 . Andere eigenwaarden zijn er niet, en dus kan er geen basis voor Q3 zijn bestaande uit eigenvectoren: A is niet diagonaliseerbaar! ♣ Opgave 94. Bepaal E2 en E3 in dit voorbeeld.

Het niet-diagonaliseerbaar zijn van A in het voorbeeld werd veroorzaakt doordat voor een zekere eigenwaarde (λ = 2) de multipliciteit van die eigenwaarde (2) groter was dan de dimensie van de eigenruimte E λ (1). ♣ Opgave 95. Bewijs dat dit fenomeen niet op kan treden als de multipliciteit 1 is, door te laten zien dat als λ eigenwaarde is, er geldt dim Eλ ≥ 1.

De dimensie van Eλ wordt ook wel de meetkundige multipliciteit van λ genoemd; de volgende stelling drukt dan uit dat de meetkundige multipliciteit ten hoogste gelijk is aan de algebra¨ısche multipliciteit. Stelling 5.2.12 Als T eigenwaarde λ met multipliciteit m heeft dan geldt 1 ≤ dim Eλ ≤ m. Bewijs. Omdat λ eigenwaarde is, geldt dim E λ ≥ 1 (zie voorgaande opgave). Voor de andere ongelijkheid vullen we een basis van de deelruimte E λ van dimensie ` aan tot een basis B voor V . Ten opzichte van die basis is de matrix D A B MT = , 0 C waar



een ` × ` matrix is, en dus

  D= 

 λ 0 ··· 0 0 λ ··· 0   .. . . . . ..  , . . . .  0 ··· 0 λ

pT (x) = (x − λ)` det(xIn−` − C). De multipliciteit m van λ is dus minstens ` = dim E λ . In feite gebruiken we in het bewijs alleen maar een speciaal geval van het volgende lemma, dat we later nogmaals zullen gebruiken.

5.2. EIGENRUIMTEN

53

Lemma 5.2.13 Als U een onder T invariante deelruimte van V is, dan is p T |U , het karakteristieke polynoom van de beperking van T tot U , een deler van p T . Bewijs. Vul een basis voor U aan tot een basis voor V ; dan wordt T ten opzichte van die basis gegeven door de matrix B A M= , 0 C waar B de matrix voor de beperking T | U is. det(λIn − M ) = det(λIk − B) det(λIn−k − C).

De bewering volgt dan omdat

♣ Opgave 96. Bewijs dat laatste netjes!

Stelling 5.2.14 Laat T een lineaire transformatie zijn van de K-vectorruimte V , van eindige dimensie n. Dan zijn de volgende beweringen equivalent: (i) T is diagonaliseerbaar; (ii) pT (x) splitst in K[x] in lineaire factoren: Y pT = (x − λ)mλ λ

èn dim Eλ = mλ , waar λ de verschillende eigenwaarden van T doorloopt. (iii) V = ⊕λ Eλ . Bewijs. Als (i) geldt, splitst pT volledig in lineaire factoren over K volgens Stelling 5.2.10. Kies nu een basis B ten opzichte waarvan T door een diagonaalmatrix wordt gegeven; dan is elke bi ∈ B eigenvector bij één van de eigenwaarden λ van T , en bovendien is het duidelijk dat Bλ = {b ∈ B : T b = λb} een basis is voor Eλ , voor elke eigenwaarde λ. Maar dan is #Bλ = dim Eλ en X X X n = #B = #Bλ = dim Eλ ≤ mλ = deg pT = n, λ

λ

λ

op grond van Stelling 5.2.12, dus moet dim E λ = mλ , voor elke eigenwaarde λ. Als λ0 6= λ dan is het duidelijk dat Eλ0 ∩ Eλ = {0}, want λ0 v = T v = λv voor een v in de doorsnijding. Omdat u0 en u zelfs lineair onafhankelijk zijn als u 0 ∈ Eλ0 en u ∈ Eλ , op grond van Stelling 5.2.8, vormt ∪ λ Bλ dan een onafhankelijk stelsel in V als Bλ een basis voor Eλ is. Geldt nu (ii), dan is n = # ∪λ Bλ , en dus is ∪λ Bλ een basis voor V , terwijl Eλ0 ∩ Eλ = {0}. Daaruit volgt (iii). Tenslotte volgt (i) direct uit (iii) omdat een basis voor E λ bestaat uit eigenvectoren van T . Ten opzichte van een basis voor V die bestaat uit de vereniging van bases voor de Eλ heeft T dus een diagonaalmatrixvoorstelling. De stelling zegt dus, onder andere, dat T diagonaliseerbaar is dan en slechts dan als V de directe som is van eigenruimten. ♣ Opgave 97. Bewijs dat dim Eλ = mλ dan en slechts dan als rang(λIn − M ) = n − mλ , waar M de matrix van de lineaire transformatie ten opzichte van een basis voor V is. ♣ Opgave 98. Laat zien dat als T een lineaire transformatie van een eindig-dimensionale V is en V is de directe som van invariante deelruimten Vi (met 1 ≤ i ≤ k), dan is pT het (i) (i) product van pT , waar pT het karakteristieke polynoom is van de beperking van T tot Vi , voor 1 ≤ i ≤ k.

54

5.3


Cayley-Hamilton

Doel van deze paragraaf is te laten zien dat lineaire transformaties aan zekere algebra¨ısche vergelijkingen voldoen. Daartoe blijkt het nuttig te zijn om, voor een niet-nul vector w in een eindig-dimensionale K-vectorruimte V waarop een lineaire transformatie T werkt, te kijken naar w, T w, T 2 w, . . . en in het bijzonder naar lineaire relaties daartussen. Als T w lineair afhankelijk is van w = T 0 w moet w wel een eigenvector van T zijn. Is T w onafhankelijk van w, dan kan het zijn dat T 2 w lineair afhankelijk is van w en T w, enzovoorts. We kijken naar de kleinste k waarvoor T k w lineair afhankelijk is van w, T w, T 2 w, . . . , T k−1 w. Omdat de ruimte Tw opgespannen door alle T i w een lineaire deelruimte is van V bestaat er zo’n k. Bovendien is T w invariant onder T . Er zijn coëfficiënten c0 , c1 , . . . , ck−1 ∈ K met T k w = c0 w + c1 T w + · · · + ck−1 T k−1 w,

en hierin zijn een matrix voor Tw en diens karakteristieke polynoom nu eenvoudig uit te drukken. Lemma 5.3.1 Met notatie als boven geldt dat van T tot Tw gegeven wordt door  0 0 0 ···  1 0 0 ···   0 1 0 ···   .. .. . . . . . . M T |Tw =   . .  . ..  0 0   0 0 0 ··· 0 0 0 ···

de matrix voor de beperking T | Tw 0 0 0 0 0 0 .. .. . .

c0 c1 c2

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



     ,     

ten opzichte van de basis w, T w, , . . . , T k−1 w. Bovendien is het karakteristieke polynoom van T |Tw gelijk aan xk − ck−1 xk−1 − · · · − c1 x − c0 . Bewijs Voor de vorm van de matrix gebruikt men simpelweg dat T de basisvectoren T i w opschuift, voor 0 ≤ i ≤ k − 2, en de relatie voor T k w. De rest volgt direct. ♣ Opgave 99. Bewijs met inductie naar k dat het karakteristieke polynoom van de matrix uit het lemma inderdaad xk − ck−1 xk−1 − · · · − c1 x − c0 is.

Opmerkingen 5.3.2 De matrix uit het voorafgaande lemma wordt wel de companion matrix van het polynoom xk − ck−1 xk−1 − · · · − c1 x − c0 genoemd. In het volgende willen we uitdrukkingen van de vorm a 0 +a1 T +· · ·+ak−1 T k−1 , voor een lineaire transformatie T van V , weer als lineaire transformatie van V opvatten. Het zal duidelijk zijn hoe dit moet: (a0 + a1 T + · · · + ak−1 T k−1 )v = a0 v + a1 T v + · · · + ak−1 T k−1 v, een combinatie van vermenigvuldiging met een scalar en het loslaten van T op een vector. Deze lineaire afbeeldingen vormen een ring, die we wel met K[T ] aangeven. Maken we een basiskeuze, dan kunnen we T door een matrix M T voorstellen, en de lineaire afbeelding a0 + a1 T + · · · + ak−1 T k−1 door a0 + a1 MT + · · · + ak−1 MTk−1 . We krijgen dan een ring K[MT ], die een deelring is van Mn×n (K).

5.3. CAYLEY-HAMILTON

55

Stelling 5.3.3 [ Cayley-Hamilton ] Voor een lineaire transformatie T van een eindig-dimensionale vectorruimte V met karakteristiek polynoom p T geldt: pT (T ) = 0. Bovendien is, als MT een matrix voor T is ten opzichte van een basis voor V pT (MT ) = 0. Dat wil zeggen: T en MT voldoen aan hun eigen karakteristieke vergelijking. Bewijs. Om te laten zien dat pT (T ) = 0 (de nulafbeelding), moeten we laten zien dat pT (T ) : v 7→ 0 voor elke v ∈ V . Als v = 0, dan is pT (T )(v) = 0, omdat 0 het beeld van 0 is voor elke lineaire afbeelding. Als v 6= 0, bekijk dan Tv , de ruimte opgespannen door v, T v, T 2 v, . . .. Dit is een lineaire deelruimte van V , en daarom eindig-dimensionaal, zeg dim T v = k. Maar dan is de k + 1-ste vector T k v al bevat in v, T v, . . . , T k−1 v, dat wil zeggen, er bestaan coëfficiënten c0 , c1 , . . . , ck−1 in K zodat T k v = −c0 v − c1 T v · · · − ck−1 T k−1 v. Volgens Lemma 5.3.1 geldt nu pT |Tv (x) = xk + ck−1 xk−1 + · · · + c1 x + c0 , terwijl volgens Lemma 3.2.13 dit polynoom een deler is van p T . Dus is er een polynoom q(x) ∈ K[x] zodat pT (x) = q(x)(xk + ck−1 xk−1 + · · · + c1 x + c0 ). Substitueren we hierin T voor x, dan geeft dit pT (T ) = q(T )(T k + ck−1 T k−1 + · · · + c1 T + c0 ), een gelijkheid tussen twee lineaire afbeeldingen waarvoor het rechterlid toegepast op v beeld 0 heeft, vanwege bovenstaande relatie. Maar dan is dus ook p T (T )(v) = 0, zoals te bewijzen was. De bewering voor matrices volgt hieruit (of volgens een analoog argument). Voorbeeld 5.3.4 Laat T : Q3 → Q3 gegeven zijn door     −b + c a T :  b  7→  a + c  , 3c c

zodat, ten opzichte van de standaardbasis {e 1 , e2 , e3 } de afbeelding gegeven wordt door:   0 −1 1 MT =  1 0 1  . 0 0 3

Daaruit volgt direct dat T e1 = e2 , en T 2 e1 = T e2 = −e1 . Daarom is de ruimte Te1 opgespannen door e1 , T e1 , T 2 e1 , . . . dezelfde als die opgespannen door e 1 en T e1 ,

56


dat wil zeggen door {e1 , e2 }. We zien op twee manieren dat het karakteristieke polynoom va de beperking tot Te1 het kwadratische polynoom x2 + 1 is: immers T 2 e1 = −e1 . Ook kunnen we kijken naar de matrix van beperking T | Te1 , namelijk M T |T1 =

0 −1 1 0

,

zodat volgens de definitie van het karakteristiek polynoom we p T |T1 = x2 + 1 krijgen. Dit polynoom deelt pT . Kijken we naar de ruimte Te3 opgespannen door e3 , T e3 , T 2 e3 , . . ., dan vinden we:         0 1 1 2 2        e3 = 0 , T e3 = 1 , T e3 = T 1 = 4 , 1 3 3 9 en vervolgens

         2 1 0 5 2 T 3 e3 = T  4  =  11  = 3  0  −  1  + 3  4  , 9 3 1 27 9 

oftewel

T 3 e3 = 3T 2 e3 − T e3 + 3e3 . Het karakteristieke polynoom is dus pT |Te (x) = x3 − 3x2 + x − 3 = (x2 + 1)(x − 3). 3

Op grond van de graad moet dit de hele p T zijn! ♣ Opgave 100. Bereken pT |Te (x) met behulp van de definitie. 3

5.4

Toepassingen

De stelling van Cayley-Hamilton kan toegepast worden om bijvoorbeeld de onderstaande drie (met elkaar samenhangende) problemen op te lossen. Om de inverse van een (inverteerbare) matrix M ∈ M n×n (K) te bepalen, gebruikt men de algebra¨ısche relatie pM (M ) = 0: laat pM (x) = xk + ck−1 xk−1 + · · · + c1 x + c0 , dan geldt dus M (M k−1 + ck−1 M k−2 + · · · + c1 ) = −c0 , zodat M −1 =

M k−1 + ck−1 M k−2 + · · · + c1 . −c0

♣ Opgave 101. Laat zien dat c0 = ± det M , en daarom c0 6= 0 voor een inverteerbare M.

Om een (grote) macht van M (nu niet noodzakelijk inverteerbaar) te bepalen, zeg M m , kan men Cayley-Hamilton tezamen met het algoritme van Euclides gebruiken. Bepaal namelijk polynomen q en r zodanig dat xm = q(x)pM (x) + r(x),

5.5. JORDAN NORMAALVORM

57

met deg r < deg pM . Dan is M m = q(M )pM (M ) + r(M ), zodat M m = r(M ). Het polynoom r heeft dan kleine graad (maar mogelijk grote coëfficiënten!). Net zo kan men het uitgebreide algoritme van Euclides toepassen om polynomen s en t te bepalen waarvoor s(x)pM (x) + t(x)xm = 1, wanneer M een inverteerbare matrix is. Deze gelijkheid van lineaire afbeeldingen (met rechts de identieke afbeelding 1 = id impliceert met Cayley-Hamilton dat M −m = t(M ). Omdat voor grote m de graad van t(x), die begrensd wordt door de graad van pM , veel kleiner is dan m, kan dit een goed manier zijn om een grote negatieve macht van een inverteerbare matrix uit te rekenen. Wederom kunnen de coëfficiënten van t(x) groot worden. Voorbeeld 5.4.1 Laat M=

2 1 1 −1

,

dan vinden we eenvoudig pM (x) = x2 − x − 3. Volgens Cayley-Hamilton is dus M 2 − M − 3I = 0, zodat M −I . M −1 = 3 ♣ Opgave 102. Bereken pM op twee manieren. ♣ Opgave 103. Bereken (M − I)/3 en laat zien dat het de inverse van M is.

Wanneer we met dezelfde M de beschreven methode toepassen om M 10 uit te rekenen, vinden we eerst de rest r(x) = 1159x + 1524 bij deling van x 10 door pM = x2 − x − 3; dan laat M 10 = r(M ) zich eenvoudig bepalen. ♣ Opgave 104. Bereken q(x) en r(x) zodat x10 = q(x)pM (x) + r(x). ♣ Opgave 105. Bereken r(M ), en vergelijk het resultaat (en de moeite!) met een directe berekening van M 10 . ♣ Opgave 106. Bepaal M −10 met de methode uit 5.4, en met behulp van de vorige opgaven.

5.5

Jordan normaalvorm

We hebben reeds gezien dat lineaire transformaties niet altijd diagonaliseerbaar zijn. Een belangrijke reden is dat het karakteristieke polynoom niet noodzakelijk geheel in lineaire factoren splitst over het lichaam waarover we werken. Maar zelfs als dat wel het geval is — bijvoorbeeld wanneer we over de complexe getallen werken — zien we uit Stelling 5.2.14 dat het voor diagonaliseerbaarheid noodzakelijk is dat de dimensies van alle eigenruimten gelijk zijn aan de multipliciteiten van de bijbehorende eigenwaarden. Voorbeeld 5.5.1 Het is eenvoudig om voorbeelden van lineaire transformaties te maken (in vectorruimten van eindige dimensie over een willekeurig lichaam!) die niet diagonaliseerbaar zijn terwijl het karakteristieke polynoom wel volledig in lineaire factoren uiteenvalt. Zorg er bijvoorbeeld voor dat 0 de enige eigenwaarde is, door een bovendriehoeksmatrix voor de transformatie te kiezen met bovendien

58


op de diagonaal allemaal nullen. Dan is het karakteristieke polynoom gelijk aan xn , en 0 de enige eigenwaarde, met multipliciteit n. De eigenruimte bij λ = 0 is de kern van de matrix, waarvan de dimensie gelijk is aan n − r, met r de rang van de matrix. Zodra er niet-nul elementen in de bovendriehoek staan is de rang groter dan nul en dus de dimensie van de kern kleiner dan n. Wat we in deze paragraaf willen laten zien is dat een lineaire transformatie T van een eindig-dimensionale vectorruimte V , mits het karakteristieke polynoom ervan geheel in lineaire factoren uiteenvalt, ‘bijna diagonaliseerbaar’ is, in een heel precieze zin. Namelijk, dat er dan een basis voor V bestaat ten opzichte waarvan de transformatie een matrix heeft die bestaat uit ‘bijna-diagonaal’ blokken. Preciezer, ten opzichte van die basis is de matrix van T de directe som van Jordan blokken, waar een k × k Jordan blok Jk (λ) een k × k matrix van de vorm   λ 1 0 ··· 0  0 λ 1 0     .. . . . . . . ..   . . . . .      ..  0 . λ 1  0 ··· 0 0 λ is. Een directe som van Jordan blokken heet een Jordan matrix.

♣ Opgave 107. Laat zien dat een Jordan matrix een diagonaalmatrix is dan en slechts dan als alle blokken afmeting 1 × 1 hebben. ♣ Opgave 108. Bewijs dat het karakteristieke polynoom van een Jordanmatrix gelijk is Q aan (x − λi ), waar de λi de diagonaalelementen van de matrix zijn.

♣ Opgave 109. Bewijs dat de dimensie van de eigenruimte bij de eigenwaarde λ van het Jordan blok J(λ) precies 1 is. Laat zien dat hieruit volgt dat de dimensie van Eλ voor een Jordanmatrix J gelijk is aan het aantal Jordanblokken J(λ) in de directe som die J vormt. ♣ Opgave 110. Geef vier 4×4 Jordanmatrices (over de rationale getallen) met uitsluitend eigenwaarde 2, en eigenruimten E2 van dimensie respectievelijk 1, 2, 3 en 4.

Definities 5.5.2 Zij T een transformatie van de eindig-dimensionale vectorruimte V . Met I geven we de identieke afbeelding id V aan. Een vector v ∈ V met v 6= 0 is gegeneraliseerde eigenvector bij λ als er een k ∈ Z ≥1 bestaat zodat (λI−T )k (v) = 0. De gegeneraliseerde eigenruimte bij λ van T is de deelruimte Gλ = {v ∈ V | ∃k ∈ Z≥1 : (λI − T )k (v) = 0}. ♣ Opgave 111. Laat zien dat een lineaire combinatie van twee gegeneraliseerde eigenvectoren bij λ inderdaad weer een gegeneraliseerde eigenvector bij λ is. ♣ Opgave 112. Als k minimaal is met de eigenschap dat (λI − T )k (v) = 0, dan is (λI − T )k−1 (v) een eigenvector van T . Toon dit aan en concludeer dat gegeneraliseerde eigenvectoren alleen kunnen optreden bij eigenwaarden λ van T . ♣ Opgave 113. Laat zien dat Gλ invariant is onder T . ♣ Opgave 114. Bewijs dat Eλ ⊂ Gλ . ♣ Opgave 115. Bewijs dat alle basisvectoren gegeneraliseerde eigenvector zijn voor T als T ten opzichte van de basis een Jordanmatrix is.

5.5. JORDAN NORMAALVORM Voorbeeld 5.5.3 Laat de 6 × 6 Jordanmatrix J1 (2) ⊕ J2 (5) ⊕ J3 (2):  2 0 0 0 0  0 5 1 0 0   0 0 5 0 0   0 0 0 2 1   0 0 0 0 2 0 0 0 0 0

59 J gegeven zijn als directe som van 0 0 0 0 1 2

       

ten opzichte van de basis b1 , . . . , b6 . De vectoren b1 , b2 , b4 zijn dan eigenvectoren (bij eigenwaarden 2, 5, 2), terwijl b 3 , b5 , b6 gegeneraliseerde eigenvector zijn, bij 5, 2, 2. Immers, (5I6 −J)(b3 ) = b2 , dus (5I6 −J)2 (b3 ) = 0, en net zo (2I6 −J)(b6 ) = b5 , en (2I6 − J)(b5 ) = b4 , zodat (2I6 − J)3 (b6 ) = (2I6 − J)2 (b5 ) = (2I6 − J)(b4 ) = 0. De ruimte G2 is de directe som van een 1-dimensionale en een 3-dimensionale deelruimte, terwijl E2 dimensie 2 heeft. Definitie 5.5.4 Als v een gegeneraliseerde eigenvector van T is bij λ, en m minimaal zodat (λI − T )m (v) = 0, dan noemen we (λI − T )m−1 (v), (λI − T )m−2 (v), . . ., (λI − T )(v),v, een cykel van gegeneraliseerde eigenvectoren voor T (van lengte m). Merk op dat de eerste vector in zo’n cykel eigenvector bij λ is en dat dit ook de enige eigenvector in de cykel is. Lemma 5.5.5 De vectoren in een cykel van gegeneraliseerde eigenvectoren voor T zijn lineair onafhankelijk. Bewijs. Met inductie naar de lengte m. Voor m = 1 is het duidelijk. Laat nu vm−1 , . . . v0 zo’n cykel zijn bij λ, en veronderstel dat µ m−1 vm−1 + · · · µ0 v0 = 0. Pas (λI − T ) toe: omdat (λI − T )vi = vi+1 voor i = m − 2, . . . , 0 en (λI − T )vm−1 = 0, geeft dat µm−2 vm−1 + · · · µ0 v1 = 0. Volgens de inductiehypothese zijn dan µ i = 0 voor i = m − 2, . . . , 0 . Dan ook µm−1 vm−1 = 0 en dus µm−1 = 0 (want vm−1 6= 0 is eigenvector). In het voorbeeld zagen we dat bij Jordanblokken cykels van gegeneraliseerde eigenvectoren horen. Dat is algemeen waar. Stelling 5.5.6 De matrix van de transformatie T is ten opzichte van een basis B een Jordanmatrix dan en slechts dan als B een vereniging van cykels van gegeneraliseerde eigenvectoren is. Bewijs. Bij elk k × k Jordanblok hoort een cykel van lengte k, dat is duidelijk. Omgekeerd geeft zo’n cykel vk−1 , . . . v0 ook een Jordanblok, precies omdat steeds (λI − T )vi = vi+1 voor i = k − 2, . . . , 0 en (λI − T )vk−1 = 0.

Het idee is nu om bij elke eigenvector van T een cykel van gegeneraliseerde eigenvectoren van maximale lengte te maken, en als basis voor de ruimte de vereniging van die cykels te nemen. We moeten nog laten zien dat zo’n vereniging van cykels een linear onafhankelijk stelsel geeft, en dat we zo een aantal vectoren krijgen dat de dimensie van de hele ruimte is. We zagen al dat de cykels zelf louter onafhankelijke vectoren bevatten. De volgende stelling zegt dat cykels bij verschillende eigenwaarden ook onafhankelijk zijn. (Merk op dat uit het voorbeeld blijkt dat dat niet genoeg is: er kunnen ook verschillende cykels bij dezelfde λ zijn; merk ook op dat dit stelling 5.2.8 generaliseert.)

60


Stelling 5.5.7 Als xi gegeneraliseerde eigenvector van T is bij eigenwaarde λ i , en λi 6= λj voor 1 ≤ i < j ≤ k, dan zijn x1 , x2 , . . . , xk lineair onafhankelijk. Bewijs. Inductie naar k. Voor k = 1 is de stelling zeker waar. Zij k > 1, en x i als in de stelling. Laat mi minimaal zijn met de eigenschap dat (λ i I − T )mi (xi ) = 0. Dan is, zoals we al zagen, wi = (λi I − T )mi −1 (xi ) eigenvector voor T bij de eigenwaarde λi . Veronderstel nu eens dat µ1 x1 + µ2 x2 + · · · + µk xk = 0, dan is enerzijds k−1 Y i=i

(λi I − T )mi

!

· (λk I − T )mk −1 (µ1 x1 + µ2 x2 + · · · + µk xk )

gelijk aan 0, maar anderzijds gelijk aan ! k−1 k−1 Y Y mi (λi − λk )mi · wi . · wk = µk (λi I − T ) µk i=i

i=i

Maar wk is eigenvector bij λk , dus niet nul, en ook is λi 6= λk . Maar dan moet µk = 0. Op grond van de inductiehypothese is x 1 , . . . , xk−1 lineair onafhankelijk, dus zijn alle µi gelijk aan 0: alle xi zijn lineair onafhankelijk. Gevolg 5.5.8 Als Bi een basis is voor de gegeneraliseerde eigenruimte G λi , en λi 6= λj voor i 6= j dan is B1 , B2 , . . . Bk een onafhankelijk stelsel. Lemma 5.5.9 Als C1 , . . . , Ck cykels van gegeneraliseerde eigenvectoren van T zijn bij dezelfde eigenwaarde λ, en de eigenvectoren w i ∈ Ci vormen een lineair onafhankelijk stelsel, dan vormt C = C 1 ∪ C2 ∪ · · · ∪ Ck een lineair onafhankelijk stelsel vectoren. Bewijs. Het bewijs gaat weer met inductie naar het aantal elementen n van C. Voor de inductiestap kijken we naar de deelruimte W opgespannen door n de elementen van Ci ; die ruimte is invariant onder λI − T , en het beeld wordt opgespannen door de n − k vectoren uit C \ {w 1 , . . . , wk } (de laatste vector uit elke cykel weggelaten). Onder de inductiehypothese heeft dat beeld dan dimensie precies n − k. De kern van λI − T bevat de k onafhankelijke eigenvectoren w i , en de dimensiestelling zegt dan dat W dimensie n heeft. Gevolg 5.5.10 Als het karakteristieke polynoom van de transformatie T op V volledig in lineaire factoren splitst, dan bestaat er een basis voor V ten opzichte waarvan de matrix van T Jordanmatrix is. Bewijs. Kies voor elke λ een basis voor E λ , en bij elke basisvector een cykel van gegeneraliseerde eigenvectoren. Stelling 5.5.11 Laat T een transformatie van de K-vectorruimte V zijn waarvoor het karakteristieke polynoom pT (x) over K splitst als pT (x) = (x − λ1 )m1 · · · (x − λk )mk (met λi 6= λj als i 6= j). Dan is voor i = 1, . . . , k: Gλi = Ker((λi I − T )mi ),

dim Gλi = mi .

5.5. JORDAN NORMAALVORM

61

Bewijs. Kies een basis B voor V ten opzichte waarvan T een Jordanmatrix heeft. Op de diagonaal komen precies mi eigenwaarden λi voor, dus dim Gλi ≥ mi . Anderzijds vormt een vereniging van bases voor G λi een basis voor V , dus n=

k X i=1

dim Gλi ≥

k X

mi = n.

i=1

Omdat per definitie Gλi ⊃ Ker((λi I − T )mi ), resteert slechts de bewering Gλi ⊂ Ker((λi I − T )mi ), te bewijzen. Omdat dim Gλi = mi kan geen cykel van gegeneraliseerde eigenvectoren in Gλi langer zijn dan mi . Dus elke vector in dim Gλi is bevat in Ker((λi I − T )mi ). Gevolg 5.5.12 Onder dezelfde aannamen als in de voorgaande stelling geldt: T

is diagonaliseerbaar

⇐⇒

∀λ : Gλ = Eλ .

Op de uniciteit van de Jordan normaalvorm (op volgorde van de blokken na) gaan we hier niet verder in.

62


Hoofdstuk 6

Inproductruimten 6.1

Bilineaire Vormen

In dit hoofdstuk en het volgende gaan we gebruik maken van afstandsbegrip op reële en complexe vectorruimten. In het algemeen is er geen begrip afstand (of lengte) gedefinieerd in een lichaam. Maar in C, en dus in deellichamen daarvan, is dat wel het geval. Het afstandsbegrip in een vectorruimte wordt bepaald door het inproduct; dat is een speciaal geval van een bilineaire vorm, die we wel voor willekeurige lichamen kunnen definiëren. Definitie 6.1.1 Zij V een K-vectorruimte. Dan heet een afbeelding B : V × V → k, die aan (v, w) een getal B(v, w) toevoegt een bilineaire vorm als (1) Voor elke w ∈ V is de afbeelding Bw : V → k, gedefinieerd door Bw (v) = B(v, w), een k-lineaire afbeelding; en (2) Voor elke v ∈ V is de afbeelding Bv : V → k, gedefinieerd door Bv (w) = B(v, w), een k-lineaire afbeelding. We noemen B symmetrisch als B(v, w) = B(w, v) voor elke v, w ∈ V . We noemen B anti-symmetrisch als B(v, w) = −B(w, v) voor elke v, w ∈ V . Het zal duidelijk zijn waar de naam vandaan komt: een bilineaire afbeelding is lineair in beide argumenten v, w. Het belangrijkste voorbeeld van een bilineaire vorm wordt gegeven door het inproduct. Voorbeelden 6.1.2 P (i) Het gewone inproduct op Rn gegeven door B(v, w) =< v, w >= ni=1 vi wi is een bilineaire vorm. (ii) Als A ∈ Mn×n (K) een n × n matrix is dan geeft de afbeelding B A (v, w) = v T Aw ∈ K een bilineaire vorm op K n . De volgende stelling drukt uit dat wanneer we in V een basis kiezen, zeg E = {e1 , . . . , en }, B vastligt door de waarden B(ei , ej ) op deze basis. Bijgevolg kunnen we B representeren door een matrix, namelijk de matrix waarin op positie i, j de waarde van B(ei , ej ) staat. Stelling 6.1.3 Als B een bilineaire vorm is op een vectorruimte V met basis E = {e1 , . . . , en }, dan geldt: B(a, b) = B(

n X i=1

αi ei ,

n X j=1

βj ej ) =

n n X X i=1 j=1

63

αi βj B(ei , ej ) = aT B(ei , ej )b.

64

HOOFDSTUK 6. INPRODUCTRUIMTEN

Bewijs. Gebruik achtereenvolgens lineariteit in het eerste en het tweede argument: B(a, b) = B(

n X

αi ei ,

n X

βj ej ) =

αi B(ei ,

=

n X

βj ej )

j=1

i=1

j=1

i=1

n X

n X n X

αi βj B(ei , ej ) = aT B(ei , ej )b.

i=1 j=1

Definitie 6.1.4 We noteren de matrix met op plek i, j het getal B(e i , ej ) met MEB of MB als de basis duidelijk is. Deze matrix heet de Gram matrix van B. Stelling 6.1.5 Zij B een bilineaire vorm. Zij C de bilineaire vorm gedefinieerd door C(v, w) = v T MBE w. Dan geldt B = C. Bewijs. Voor de lezer. Opmerking 6.1.6 Blijkbaar heeft elke bilineaire vorm de vorm van voorbeeld 6.1.2(2). Na basiskeuze is elke bilineaire vorm te schrijven als: 

  α1    B( ...  ,  αn

  β1 .. ) = α a β +α a β +. . .+α a β = (α , . . . , α )A   1 11 1 1 12 2 n nn n 1 n .  βn

 β1 ..  .  βn

waar A de matrix (aij ) = MB is. Veel eigenschappen van een bilineaire vorm B zijn van de matrix M B af te lezen. Stelling 6.1.7 B

is symmetrisch

⇐⇒

MB

is symmetrisch.

Bewijs. MB is symmetrisch dan en slechts dan als (M B )ij = (MB )ji voor alle i, j. Per definitie is (MB )ij = B(ei , ej ), dus symmetrie van MB is equivalent met: B(ei , ej ) = B(ej , ei ) voor Stelling 6.1.3 P alle i, jPhetgeen volgensP P het geval is dan en slechts dan als B( ni=1 αi ei , nj=1 βj ej ) = B( nj=1 βj ej , ni=1 αi ei ) voor alle α1 , . . . , αn , β1 , . . . , βn , dat wil zeggen B(v, w) = B(w, v) voor alle v, w. In het bovenstaande hebben we niets geëist over de gekozen basis. Dus symmetrie is onafhankelijk van de keuze van basis. Gevolg 6.1.8 Voor bases E, F van V geldt: MBE

symmetrisch

⇐⇒

MBF

symmetrisch.

Zoals we ons in het vorige hoofdstuk afvroegen of we een matrix die een lineaire afbeelding ten opzichte van een gekozen basis representeerde altijd op diagonaalvorm konden brengen door basisverandering, zo kunnen we hier dezelfde vraag stellen voor de matrix die een bilineaire vorm representeert.

6.1. BILINEAIRE VORMEN

65

Voorbeeld 6.1.9 Zij V = R3 en laat B((α1 , α2 , α3 ), (β1 , β2 , β3 )) = α1 β1 − α1 β2 − α2 β1 + 2α2 β2 + 4α3 β3 . We bekijken het effect van het gebruik van een andere dan de standaardbasis E; zij bijvoorbeeld F := {f1 , f2 , f3 } = {e1 , e1 + e2 , 12 e3 }. Laten we eens kijken hoe B er ten opzichte van F uitziet. B(a1 f1 + a2 f2 + a3 f3 , b1 f1 + b2 f2 + b3 f3 ) 1 1 = B(a1 e1 + a2 (e1 + e2 ) + a3 e3 , b1 e1 + b2 (e1 + e2 ) + b3 e3 ) 2 2 1 1 = B((a1 + a2 )e1 + a2 e2 + a3 e3 , (b1 + b2 )e1 + b2 e2 + b3 e3 ) 2 2 1 1 = (a1 + a2 )(b1 + b2 ) − (a1 + a2 )b2 − a2 (b1 + b2 ) + 2a2 b2 + 4( a3 b3 ) 2 2 = a 1 b1 + a 2 b2 + a 3 b3 . Ten opzichte van deze basis is de bilineaire afbeelding gewoon het inproduct! Het is dus van belang om bilineaire vormen op verschillende bases te beschouwen. Met BF zullen we de bilineaire vorm ten opzichte van de basis F aangeven. In het voorgaande voorbeeld: B E ((α1 , α2 , α3 ), (β1 , β2 , β3 )) = α1 β1 − α1 β2 − α2 β1 + 2α2 β2 + 4α3 β3 en B F ((α1 , α2 , α3 ), (β1 , β2 , β3 )) = α1 β1 + α2 β2 + α3 β3 . De volgende Stelling geeft het verband tussen de matrix M BE = MBE en de matrix MBF = MBF aan. −→E , de transforStelling 6.1.10 Laten E en F bases voor V zijn, en zij T = Φ F I matiematrix die F in E overvoert. Dan geldt:

MBF = T T MBE T.

♣ Opgave 116. Bewijs deze bewering.

Ging een matrix die een lineaire afbeelding representeerde onder basistransformatie over in een geconjugeerde matrix T −1 M T , de matrix van een bilineare vorm gaat over in T T MB T. Definitie 6.1.11 We noemen twee vierkante matrices M, N ∈ M n×n (K) equivalent als er een inverteerbare T bestaat zodat M = T T N T . We schrijven M ∼ N . Twee bilineaire vormen B en C noemen we equivalent (en we schrijven wel B ∼ C) als voor zekere basiskeuze geldt: M C ∼ MB . Met andere woorden: B en C zijn equivalent als er bases E, F bestaan zodat E B = CF . ♣ Opgave 117. Laat zien dat dit ook echt een equivalentierelatie definieert. ♣ Opgave 118. Als er een inverteerbare T is zodat T T MB T een diagonaalmatrix is dan is B symmetrisch. Bewijs dat.

We kunnen ons (wederom) afvragen of een symmetrsiche matrix altijd equivalent is met een diagonaalmatrix. In dit geval is het antwoord ‘bijna altijd’ bevestigend. Eerst maar eens een uitzondering.

66


Voorbeeld 6.1.12 Zij M=

0 1 1 0

∈ M2×2 (F2 ).

Dan is M niet equivalent met een diagonaalmatrix. Kijk maar: laat T een willekeurige inverteerbare matrix zijn dan a c 0 1 a b 2ca ad + bc T T MT = = b d 1 0 c d ad + bc 2bd en ad + bc = ad − bc = det(T ) 6= 0 in F2 . Dat dit niet werkt in dit geval heeft te maken met het feit dat in F 2 de gelijkheid 2 = 0 geldt. In een lichaam met 2 6= 0 gaat het wel goed. Stelling 6.1.13 Zij M een symmetrische matrix over een lichaam K van karakteristiek 6= 2. Dan is M equivalent met een diagonaalmatrix D. Bewijs. We geven een bewijs in de vorm van een algoritme, dat je precies vertelt hoe je D kunt construeren. We veronderstellen dat M ∈ M n×n (K). Stap 1: Als M een diagonaalmatrix is (bijvoorbeeld de nulmatrix, of een 1 × 1 matrix), dan ben je klaar. Stap 2: Veronderstel dat n ≥ 2. Allereerst moet je een v 1 vinden met v1T M v1 6= 0: Als er een diagonaalelement Mii 6= 0 is, kies dan v1 = ei (want eT i M ei = Mii ). Zijn alle elementen op de diagonaal 0 zoek dan i, j zodat M ij 6= 0. Neem T T T v1 = ei + ej , want (ei + ej )T M (ei + ej ) = eT i M ei + ei M ej + ej M ei + ej M ej = Mii + Mij + Mji + Mjj = Mij + Mji = 2Mij 6= 0. Stap 3: Laat w = M v1 , en bepaal de kern van de afbeelding f : V → K gedefinieerd door f (u) = uT w. Merk op dat dit een lineaire afbeelding is. Bovendien is f surjectief: laat a = f (v 1 ) ∈ K, dan is a 6= 0 door de keuze van v1 . Voor b ∈ K is f ((b/a)v1 ) = (b/a)f (v1 ) = b. Omdat n = dim(Kerf )+dim(Imf ) heeft Ker(f ) ⊆ V dimensie n − 1. Laat {v2 , . . . , vn } een basis voor Kerf zijn. Stap 4: Maak nu Tn = (v1 , v2 , . . . , vn ), met de vectoren vi als kolommen. Stel Tn is niet inverteerbaar. Dat is equivalent met: {v 1 , v2 , . . . , vn } is een afhankelijk stelsel. Omdat {v2 , . . . , vn } een onafhankelijk stelsel is, kan dat laatste alleen als v1 ∈ {v2 , . . . , vn } = Ker(f ), oftewel f (v1 ) = 0; dat is in tegenspraak met de keuze in Stap 2. Dus Tn is inverteerbaar. Bovendien is TnT M Tn van de vorm a 0 0 0 M 0

waar M een symmetrische (n−1)×(n−1) matrix is, omdat (T nT M Tn )ij = viT M vj en vi M v1 = f (vi ) = 0 voor i > 1 want vi ∈ Ker(f ). 0 Ga nu naar Stap 1 en herhaal de procedure voor M . Het is duidelijk dat dit proces na eindig veel stappen een diagonaalmatrix D oplevert. ♣ Opgave 119. Ga na waar in het bewijs gebruikt is dat de karakteristiek van het lichaam geen 2 is.

Tot slot van deze paragraaf introduceren we kwadratische vormen.

6.1. BILINEAIRE VORMEN

67

Definitie 6.1.14 Een kwadratische vorm Q over een lichaam K in n variabelen is een homogeen polynoom van graad 2 met coëfficiënten in K. Opmerking 6.1.15 Dat een polynoom P = P (x 1 , x2 , . . . , xn ) in n variabelen homogeen van graad k is betekent dat wanneer we P schrijven als som van termen X pk1 ,k2 ,...,kn xk11 xk22 · · · xknn , P =

met natuurlijke exponenten kj , een coëfficiënt pk1 ,k2 ,...,kn alleen maar ongelijk 0 mag zijn als k1 + k2 + · · · + kn = k. Een kwadratische vorm bestaat dus uit termen van de vorm qi,j xi xj (waar i en j gelijk kunnen zijn). Door substitutie kunnen we een polynoom over een lichaam K in n variabelen opvatten als een afbeelding van K n (of een willekeurige n-dimensionale Kvectorruimte V ) naar K; met andere woorden, via Q(v) = Q((v1 , v2 , . . . , vn )) = Q(v1 , v2 , . . . , vn ), kan een kwadratische vorm als afbeelding Q : K n → K worden opgevat. Stelling 6.1.16 Als K een lichaam is van karakteristiek ongelijk aan 2 dan is er een één-éénduidig verband tussen kwadratische vormen in n variabelen op K en symmetrische n × n matrices over K. Bewijs. Laat Q(x1 , x2 , . . . , xn ) =

X

qi,j xi xj .

1≤i≤j≤n

Definieer dan de matrix P ∈ Mn×n (K) door Pii = qi,i en Pij = qi,j /2 voor i 6= j; hier is 1 ≤ i, j ≤ n. Gevolg 6.1.17 Over een lichaam van karakteristiek ongelijk 2 kunnen we met een kwadratische vorm Q in n variabelen een unieke symmetrische bilineaire vorm B op K n , voorzien van de standaardbasis, associëren. Dan geldt: Q(x) = B(x, x). Bewijs. Deze associatie volgt uit de stelling, omdat een symmetrische matrix P uit Mn×n (K) correspondeert met een symmetrische bilineaire vorm op K n met een gegeven basis, via B(v, w) = v T P w. Dan is Q(x) = B(x, x). ♣ Opgave 120. Onder bovenstaande correspondentie geldt: B(v, w) = (Q(v+w)−Q(v)− Q(w))/2.

Voorbeeld 6.1.18 Laat Q de kwadratische vorm in 3 variabelen over Q zijn gegeven door Q(x1 , x2 , x3 ) = x21 + 5x1 x2 + 2x2 x3 + x23 . Dit is een homogeen polynoom, waarmee we de symmetrische matrix  

1 5 2

0

5 2

 0 0 1  1 1

associëren. Met Q correspondeert dan de symmetrische bilineaire vorm B(v, w) = v1 w1 + 5/2v2 w1 + 5/2v1 w2 + v2 w3 + v3 w2 + v3 w3 .

68

6.2


Re¨ eel-symmetrische bilineaire vormen

In deze sectie laten we zien dat we symmetrische bilineaire vormen (en daarmee kwadratische vormen) op een reële vectorruimte onder equivalentie kunnen karakteriseren door drie invarianten. Definitie 6.2.1 Voor een reële diagonaalmatrix D definiëren we de 3 natuurlijke getallen n0 , n+ , n− als volgt: n0 (D) is het aantal nullen op de diagonaal van D, n+ (D) is het aantal positieve elementen op de diagonaal van D, en n − (D) is het aantal negatieve getallen op de diagonaal van D. Voor een symmetrische bilineaire vorm B op een eindig-dimensionale reële vectorruimte V definiëren we dan n0 (B) = n0 (D), n+ (B) = n+ (D), n− (B) = n− (D), voor een diagonaalmatrix D met D ∼ MB . Merk op dat bij elke symmetrische B volgens Stelling 6.1.13 zo’n D bestaat. In het algemeen zijn er natuurlijk meerdere diagonaalmatrices die voldoen (je kunt immers bijvoorbeeld de basisvectoren verwisselen, of met een factor opblazen), maar de volgende stelling drukt uit dat dit toch een goede definitie is, namelijk, dat deze onafhankelijk is van de mogelijke keuze van D. ♣ Opgave 121. Als B = T T AT en T is inverteerbaar, dan is rang(B) = rang(A).

Stelling 6.2.2 Laat B een bilineaire vorm op een reële n-dimensionale vectorruimte V zijn. Als D ∼ MB ∼ D 0 , met diagonaalmatrices D en D 0 , dan geldt: n0 (D) = n0 (D 0 ),

n+ (D) = n+ (D 0 ),

n− (D) = n− (D 0 ).

Bewijs. Merk eerst op dat ∼ een equivalentierelatie is, zodat de twee diagonaalmatrices D en D 0 voldoen aan D ∼ D 0 , oftewel er is een inverteerbare T zodat T T D 0 T = D. Nu is n0 (D) = n − rang(D) de dimensie van de kern van D, en net zo n0 (D 0 ) = n − rang(D 0 ) de dimensie van de kern van D 0 . Maar omdat T inverteerbaar is, geldt rang(D) = rang(D 0 ) = r en dus n0 (D) = n0 (D 0 ). Laat B nu de basis van V zijn ten opzichte waarvan B matrix D = M BB heeft, dan is D 0 = T T D 0 T = D de matrix MBC waar C = T B. We ordenen deze bases zo dat de eerste p = n+ (D), resp. p0 = n+ (D 0 ) elementen b1 , . . . , bp en c1 , . . . , cp0 positieve waarden B(bi , bi ) en B(cj , cj ) opleveren, en de volgende m = n− (D), resp. m0 = n− (D 0 ) negatieve waarden. Veronderstel nu eens dat p = n+ (D) < n+ (D 0 ) = p0 ; omdat n = n0 + n+ + n− voor een diagonaalmatrix, geldt dan m = n − (D) > n− (D 0 ) = m0 . Bekijk nu de verzameling vectoren S = {b1 , b2 , . . . , bp , cp0 +1 , . . . cp0 +m0 }. Dat zijn er p + m0 < 0 p + m = r. De lineaire afbeelding f : V → R p+m gegeven door f (v) = (B(v, b1 ), . . . , B(v, bp ), B(v, cp0 +1 ), . . . B(v, cp0 +m0 )) heeft een beeld van dimensie ≤ p + m0 < n − n0 (D) = r, dus kern van dimensie ≥ n − (p + m0 ) > n − (n − n0 (D)) = n0 (D) = n − r, en daarom is er een w in de kern van f die niet bevat is in de ruimte opgespannen door {b r+1 , . . . , bn }. Schrijf w op basis B en gebruik dat w ∈ Kerf , dan is voor 1 ≤ i ≤ p: 0 = f (w)i = B(

n X k=1

wk bk , bi ) = wi B(bi , bi ),

¨ 6.2. REEEL-SYMMETRISCHE BILINEAIRE VORMEN

69

zodat B(w, w) = B(

n X

wk bk ,

n X

wk bk ) =

wk2 B(bk , bk )

=

p+m X

wk2 B(bk , bk ) < 0,

k=p+1

k=1

k=1

k=1

n X

omdat minstens één wk 6= 0. Schrijf vervolgens w op basis C, dan is voor p 0 + 1 ≤ j ≤ p 0 + m0 : n X wk0 ck , cj ) = wj0 B(cj , cj ), 0 = f (w)j = B( k=1

zodat

B(w, w) = B(

n X k=1

wk0 ck ,

n X k=1

wk0 ck )

=

n X

0

2 wk0 B(ck , ck )

=

k=1

p X

2

wk0 B(ck , ck ) > 0,

k=1

omdat weer minstens één wk 6= 0. Maar dat is een tegenspraak! Omdat het geval n+ (D) > n+ (D 0 ) op precies dezelfde manier tot een tegenspraak leidt, moet n+ (D) = n+ (D 0 ), en dus ook n− (D) = n− (D 0 ). Gevolg 6.2.3 Twee symmetrische bilineaire vormen op een reële vectorruimte V zijn equivalent dan en slechts dan als hun invarianten n 0 , n+ , n− hetzelfde zijn. Gevolg 6.2.4 Zij B een symmetrische bilineaire vorm op een reële vectorruimte V . Dan bestaat er een basis voor V zodanig dat voor elk tweetal vectoren v, w ∈ V met coördinaten vi , wi ten opzichte van deze basis geldt: B(v, w) = v1 w1 + · · · + vp wp − vp+1 wp+1 − · · · − vr wr , waar p = n+ (B) ≥ 0, en r = p + m met m = n− (B) ≥ 0. Bewijs. De bewering is equivalent met de bewering dat de Gram matrix van B een diagonaalmatrix is (ten opzichte van zekere basis) met op de diagonaal p getallen 1, dan m getallen −1 en tenslotte n − r getallen 0. Stelling 6.2.2 zegt dat een basis B bestaat zodat MB diagonaalmatrix D is met positieve D ii voor 1 ≤ i ≤ p p en negatieve Dii voor p + 1 ≤ i ≤ r. Vervangen we de basisvectoren b i door bi / |Dii | dan volgt de bewering. Voorbeeld 6.2.5 We bekijken het voorbeeld uit 6.1.18, en laten B op R 3 gegeven zijn door   1 25 0 M =  52 0 1  , 0 1 1

ten opzichte van de standaardbasis e 1 , e2 , e3 . Het algoritme uit het bewijs van 6.1.13 heeft het volgende effect. Omdat M11 6= 0 nemen we v1 = e1 ; dan heeft w = M v1 coördinaten 1, 5/2, 0 en de kern van de afbeelding f (u) = u1 + 5/2u2 wordt voortgebracht door van (−5/2, 1, 0)T en (0, 0, 1)T . Dat ebetekent dat we moeten kijken naar       1 0 0 1 25 0 1 − 25 0 1 0 0 1 , T3T M T3 =  − 25 1 0   52 0 1   0 1 0  =  0 − 25 4 0 0 1 0 0 1 0 1 1 0 1 1

70


en het algoritme met de 2 × 2 deelmatrix herhalen. We vinden 25 25 1 0 −4 1 −4 1 1 T2T M 0 T2 = = 25 1 1 0 1 25 0 4 4

0 725 16

.

Als diagonaalvorm van B vinden we dus (na normalisatie van de lengten): B(v, w) = v1 w1 − v 2 w2 + v 3 w3 . Gevolg 6.2.6 Bij elke kwadratische vorm Q in n variabelen x i over R bestaat een lineaire transformatie TP: Rn → Rn zodanig dat voor de variabelen yi , gegeven door y = T x geldt: Q(y) = ni=1 qi yi2 . Bovendien is het aantal qi dat positief, negatief, of nul is onafhankelijk van de keuze van T , en kan q i ∈ {−1, 0, 1} door geschikte keuze van T bereikt worden. Bewijs. Dit volgt onmiddellijk uit de resultaten van deze en de vorige paragraaf. Voorbeeld 6.2.7 Natuurlijk werkt het algoritme uit het bewijs van Stelling 6.1.13 altijd, zoals in het voorgaande voorbeeld. We geven een alternatieve methode om met de hand de ‘diagonaalvorm’ voor een kwadratische vorm te bepalen. Daarvoor bezien we hetzelfde geval als in het vorige voorbeeld, waar Q correspondeert met   1 52 0  5 0 1 , 2 0 1 1

dus Q(x1 , x2 , x3 ) = x21 + 5x1 x2 + 2x2 x3 + x23 . We proberen eerst alle termen met x1 erin als sommen (of verschillen) van kwadraten te schrijven; 5 5 x21 + 5x1 x2 = (x1 + x2 )2 − ( x2 )2 , 2 2

en daarna hetzelfde voor x2 (bedenk dat net we een term met x22 hebben toegevoegd!): 5 2 5 −( x2 )2 + 2x2 x3 = −( x2 − x3 )2 , 2 2 5 zodat we vinden: 5 5 2 29 Q(x1 , x2 , x3 ) = (x1 + x2 )2 − ( x2 − x3 )2 + x23 . 2 2 5 25 Na overgang op nieuwe variabelen wordt dit: Q(y 1 , y2 , y3 ) = y12 − y22 + y32 . ♣ Opgave 122. Schets voor alle mogelijk waarden van (n+ , n− , n0 ) voor een symmetrische bilineaire B op R3 de oplossingsverzameling in R3 van Q(x1 , x2 , x3 ) = 0.

6.3

Inproductruimten

We herhalen eerst de definitie van een reële inproductruimte. Definities 6.3.1 Een inproduct op een reële vectorruimte V is een symmetrische bilineaire vorm B op V waarvan de bijbehorende kwadratische vorm Q positief definiet is op V , dat wil zeggen, voor alle 0 6= v ∈ V geldt Q(v) = B(v, v) > 0. We

6.3. INPRODUCTRUIMTEN

71

geven zo’n inproduct meestal aan met < v, w > in plaats van B(v, w). De ruimte V voorzien van een inproduct heet een inproductruimte. √ De lengte of norm ||v|| van een v ∈ V is gedefinieerd door ||v|| = < v, v >. De afstand d(v, w) tussen twee vectoren v, w ∈ V is per definitie de lengte van de verschilvector: d(v, w) = ||v − w||. De hoek tussen niet-nul vectoren v, w ∈ V is de hoek φ waarvoor de cosinusregel geldt: < v, w > . cos φ = ||v|| · ||w||

Twee vectoren v, w staan loodrecht op elkaar (genoteerd als v ⊥ w) als hun inproduct 0 is: < v, w >= 0. We zeggen ook wel dat v en w orthogonaal zijn; algemener is een stelsel van vectoren v 1 , v2 , . . . , vn orthogonaal als elk tweetal het is, dus < vi , vj >= 0 voor i 6= j. Het stelsel heet orthonormaal als het orthogonaal is en elk vector lengte 1 heeft: ||vi || = 1. Als W een lineaire deelruimte is van een inproductruimte V geven we met W ⊥ de lineaire deelruimte aan van vectoren die orthogonaal zijn met alle vectoren van W . Als verzameling is dus W ⊥ = {v ∈ V |∀w ∈ W :< v, w >= 0}. Opmerkingen 6.3.2 In een algemene K-vectorruimte kun je niet over positief definiet spreken; het is dan ook niet zo duidelijk hoe het lengtebegrip te generaliseren naar K-vectorruimten (maar we zullen dat straks wel doen voor complexe vectorruimten). Omdat deellichamen van R (zoals bijvoorbeeld Q) de ordening van R erven, kunnen we op vectorruimten over zulke lichamen wel eenvoudig dezelfde begrippen definiëren. Merk op dat de hoek tussen vectoren slechts bepaald is op veelvouden van 2π na; vaak legt men de hoek eenduidig vast door een representantensysteem modulo 2π te kiezen. Zowel 0 ≤ φ < 2π als −π ≤ φ < π wordt daarvoor wel genomen. De nulvector staat loodrecht op elke andere vector, maar maakt nooit deel uit van een orthogonaal stelsel. Een bondige manier om een orthonormaal stelsel te karakteriseren is door het Kroneckersymbool, < vi , vj >= δij . Voorbeelden 6.3.3 (i) Het standaardinproduct op R n wordt gedefinieerd door < v, w >= v1 w1 + · · · + vn wn ; de lengte van v = (v1 , v2 , . . . , vn ) is dan q ||v|| = v12 + v22 + · · · + vn2 . Voor n = 1 is die lengte dus de absolute waarde: ||v|| = |v|. De ruimte R n voorzien van het standaardinproduct wordt wel de n-dimensionale Euclidische vectorruimte genoemd. (ii) Dit voorbeeld kwamen we ook al in Algebra 2 tegen: De verzameling van reëelwaardige, continue functies C([0, 1]) op het interval [0, 1] vormt een vectorruimte onder de gebruikelijke optelling van functies en vermenigvuldiging met scalairen. We kunnen deze tot een inproductruimte maken door Z 1 f (x)g(x)dx < f, g >= 0

als inproduct te nemen. (iii) Op de vectorruimte Mn×n (R) van reële n × n matrices (onder optelling) kunnen we een inproduct definiëren door < M, N >= Tr(N T M ).

72


♣ Opgave 123. Laat zien dat alle inproducten op Rn equivalent zijn met het standaardinproduct (als bilineaire vorm). ♣ Opgave 124. Ga na dat Tr(N T M ) een inproduct definieert.

De volgende stelling karakteriseert de inproducten onder de bilineaire vormen, aan de hand van hun bijbehorende matrices.

♣ Opgave 125. Laat zien dat als M ∼ N voor M, N ∈ Mn×n (R) dan det M > 0 ⇐⇒ det N > 0.

Stelling 6.3.4 Als M = MB de matrix van de symmetrische bilineaire vorm B op de n-dimensionale reële vectorruimte V is ten opzichte van een willekeurige basis, dan geldt: B

is een inproduct

⇐⇒

det M (k) > 0

voor 1 ≤ k ≤ n,

waar M (k) de k × k ‘linksbovendeelmatrix’ (Mij )1≤i,j≤k is. Bewijs Kies een basis E = {e1 , e2 , . . . , en } voor V ten opzichte waarvan M diagonaalvorm heeft. Als B een inproduct is, geldt M ii = B(ei , ei ) > 0. Voor elke 1 ≤ k ≤ n geldt bovendien dat B een inproduct is op de ruimte opgespannen door e1 , . . . , ek , en daarop is MB = M (k) en det M (k) = M11 · · · Mkk > 0. Laat, omgekeerd, M = MB gegeven zijn ten opzichte van een basis E, en de eigenschap hebben dat de linksbovendeelmatrices M (k) allemaal positieve determinant hebben. Bepaal dan voor k = 1, 2, . . . , n met behulp van de Gram-Schmidt orthogonalisatiemethode vectoren f 1 , f2 , . . . , fk uit e1 , e2 , . . . , ek met de eigenschappen dat f1 , f2 , . . . , fk en e1 , e2 , . . . , ek dezelfde deelruimte van V opspannen, dat f1 , f2 , . . . , fk een orthogonaal stelsel vormt en dat ||f 1 || · ||f2 || · · · ||fk || = det M (k) . Dan is ten opzichte van de basis f1 , . . . , fn de symmetrische vorm B gegeven door B(fi , fj ) = 0 als i 6= j en B(fi , fi ) = det M (i) / det M (i−1) > 0, voor i = 2, 3, . . . n, terwijl B(f1 , f1 ) = M11 > 0. Dus is B(

n X i=1

λi fi ,

n X i=1

λi fi ) =

n X

λ2i B(fi , fi ) > 0.

i=1

Vervolgens definiëren we complexe inproductruimten. Het is niet goed genoeg om naar bilineaire vormen te kijken, omdat de waarden van B(v, v) niet altijd reëel zijn (en dan geen zinnige ‘lengte’ geven). Definities 6.3.5 Een Hermitese vorm op een complexe vectorruimte V is een afbeelding H : V × V → C die voldoet aan:

(1) Voor elke w ∈ V is de afbeelding Hw : V → k, gedefinieerd door Hw (v) = H(v, w), een C-lineaire afbeelding; en (2) Voor elke v, w ∈ V geldt H(v, w) = H(w, v), de complex geconjugeerde van H(w, v).

♣ Opgave 126. Laat zien dat een Hermitese H wel voldoet aan H(v, w1 +w2 ) = H(v, w1 )+ H(v, w2 ), maar dat H(v, λw) = λH(v, w).

Opmerkingen 6.3.6 Vanwege de eigenschap uit de opgave noemt men H wel sesquilineair (‘anderhalf lineair’). Merk ook op dat een Hermitese H wél bilineair is op een reële (deel)vectorruimte, en dat H(v, v) ∈ R voor elke v ∈ V .

6.3. INPRODUCTRUIMTEN

73

Definities 6.3.7 Een complex inproduct is een positief definiete Hermitese vorm H op een complexe vectorruimte V , dus H(v, v) > 0 voor v ∈ V . Een paar bestaande uit V met een complex inproduct heet een complexe inproductruimte. Voorbeelden 6.3.8 (i) Het standaardinproduct op Cn is < v, w >= v1 w1 + · · · + vn wn ; de lengte van v = (v1 , v2 , . . . , vn ) is dan p √ ||v|| = v1 v1 + v2 v2 + · · · + vn vn = |v1 |2 + · · · + |vn |2 , √ als we met |a + bi = a2 + b2 de modulus van een complex getal aangeven. Voor n = 1 is de lengte dus gewoon de modulus: ||v|| = |v|. (ii) De verzameling van complexwaardige, continue functies op het interval [0, 1] vormt een vectorruimte onder de gebruikelijke optelling van functies en vermenigvuldiging met scalairen. We kunnen deze tot een inproductruimte maken door Z 2π 1 f (x)g(x)dx < f, g >= 2π 0 als inproduct te nemen. (iii) Op de vectorruimte Mn×n (C) van complexe n × n matrices (onder optelling) kunnen we een inproduct definiëren door < M, N >= Tr(N ∗ M ), waar N ∗ = N t de complex-geconjugeerde getransponeerde van N is (die soms ook wel ge-adjungeerde wordt genoemd). ♣ Opgave 127. Ga na dat 1 < f, g >= 2π

Z

2π

f (x)g(x)dx 0

inderdaad een inproduct op C C ([0, 2π]) definieert; waar wordt de continu¨ıteit gebruikt? ♣ Opgave 128. Ga na dat Tr(N ∗ M ) een inproduct definieert.

Stelling 6.3.9 Zij V een inproductruimte over het lichaam L der reële of complexe getallen. Dan: (i) (ii) (iii) (iv)

voor elke v ∈ V en λ ∈ L geldt: ||λv|| = |λ| · ||v||; ||v|| ≥ 0; en bovendien geldt: ||v|| = 0 ⇐⇒ v = 0; voor elke v, w ∈ V geldt: | < v, w > | ≤ ||v|| · ||w||; voor elke v, w ∈ V geldt: ||v + w|| ≤ ||v|| + ||w||.

Bewijs. Bewering (i) volgt onmiddellijk uit q p √ < λv, λv > = λλ < v, v > = |λ| < v, v >.

In het bijzonder is < 0, 0 >= 0, en omdat vanwege het positief definiet zijn van √ < v, v > geldt ||v|| = < v, v > > 0 tenzij < v, v >= 0, volgt (ii). Als w = 0 geldt ongelijkheid (iii) trivialerwijze; neem nu aan w 6= 0. Dan is voor λ ∈ L de volgende uitdrukking niet-negatief:: ||v−λw||2 =< v−λw, v−λw >=< v, v > −λ < v, w > −λ < w, v > +λλ < w, w > .

74


Met de speciale keuze: λ=

< v, w > < w, w >

levert dat het niet-negatief zijn van < v, v > −

| < v, w > |2 | < v, w > |2 = ||v||2 − < w, w > ||w||2

en dan volgt (iii). Gebruik nu (iii) om te zien dat: ||v + w||2 =< v + w, v + w >= ||v||2 + < v, w > +< v, w > + ||w||2 en dat is ten hoogste ||v||2 + 2||v|| · ||w|| + ||w||2 hetgeen gelijk is aan (||v|| + ||w||) 2 . Opmerkingen 6.3.10 De ongelijkheden in 6.3.9(iii) en (iv) staan bekend als de Cauchy-Schwarz ongelijkheid en de driehoeksongelijkheid; voor het reéle geval zagen we deze al in Lineaire Algebra 2.

Hoofdstuk 7

Transformaties van Inproductruimten Inleiding In de komende secties beschouwen we lineaire transformaties van reële en complexe inproductruimten die aan extra eigenschappen voldoen die betrekking hebben op het verband tussen transformatie en inproduct. Het zal blijken dat we daarmee ook eigenschappen kunnen afleiden voor zulke transformaties die met diagonaliseerbaarheid samenhangen. Steeds zullen we een begrip voor reële inproductruimten en een corresponderend begrip voor complexe inproductruimten invoeren, en bovendien begrippen die op de bijbehorende matrices slaan. We moeten ook sterker dan voorheen onderscheid maken tussen eindig- en oneindig-dimensionale vectorruimten.

7.1

Orthogonale en Unitaire Transformaties

Het eerste paar begrippen zal blijken die transformaties te karakteriseren die zowel lengten als hoeken behouden. Definitie 7.1.1 Een lineaire afbeelding T : V → W tussen reële inproductruimten heet een isometrie als geldt dat < T v1 , T v2 >=< v1 , v2 >

voor alle v1 , v2 ∈ V .

Als T bovendien inverteerbaar is, dan heet T orthogonaal. Stelling 7.1.2 Zij T : V → W een lineaire afbeelding tussen reële inproductruimten met dim V = dim W eindig; dan geldt: T is een isometrie

⇐⇒

T is orthogonaal.

Bewijs. De ene implicatie is duidelijk; voor de andere moeten we bewijzen dat een isometrie T inverteerbaar is. Omdat dim V = dim W = n < ∞ volstaat het injectiviteit van T te bewijzen, dat wil zeggen, te laten zien dat KerT = {0}. Veronderstel maar dat T v = 0; omdat < v, v >=< T v, T v >= 0 moet v = 0. Definities 7.1.3 We zeggen dat een lineaire afbeelding T : V → W tussen reële inproductruimten lengten behoudt als geldt ||T v|| = ||v|| voor alle v ∈ V ; we zeggen 75

76

HOOFDSTUK 7. TRANSFORMATIES VAN INPRODUCTRUIMTEN

dat T hoeken behoudt als voor elk tweetal v 1 , v2 geldt dat de hoek tussen T v1 en T v2 gelijk is aan de hoek tussen v1 en v2 . Stelling 7.1.4 Een lineaire afbeelding T : V → W tussen reële inproductruimten behoudt lengten en hoeken dan en slechts dan als T een isometrie is. Bewijs. Dit volgt direkt uit de definities van lengte, hoek, en isometrie. Definitie 7.1.5 Een matrix M ∈ Mn×n (R) heet orthogonaal wanneer M T M = In . Deze definitie zegt dus dat van een orthogonale M de kolommen een orthonormaal stelsel vormen. De volgende stelling laat zien dat het dubbele gebruik van dezelfde term ‘orthogonaal’ geen misverstand is. ♣ Opgave 129. Geldt voor een orthogonale matrix M dat M M T = In ?

Stelling 7.1.6 Zij T een lineaire transformatie van de n-dimensionale reële inproductruimte V . Dan zijn equivalent: (i) de transformatie T is orthogonaal; (ii) er is een orthonormale basis E voor V zodat M TE een orthogonale matrix is; (iii) de matrix MTB is orthogonaal voor elke orthonormale basis B van V; (iv) T voert orthonormale bases voor V over in orthonormale bases. Bewijs. Voor een orthonormale basis B = {b 1 , . . . , bn } van V is < T bi , T bj > het inproduct van twee kolommen van MTB . Als T orthogonaal is, dan is het stelsel {T b1 , . . . , T bn } ook weer orthonormaal, dat wil zeggen, M TB is een orthogonale matrix. Dus (i) impliceert (iii). De kolommen van MTB vormen de beelden van {b1 , . . . , bn } onder T ; als deze kolommen een orthonormaal stelsel vormen wanneer B dat is, voert T kennelijk elke orthonormale basis B over in een orthonormale basis T B. Dat is (iv). Als B een orthonormale basis voor V is, dan is < v, w >=<

n X

vi bi ,

i=1

n X

wj bj >=

j=1

n X

vi wj < bi , bj >=

i,j=1

n X

vi wi .

i=1

Als (iv) geldt, dan is ook T B = {T b1 , . . . , T bn } een orthonormaal stelsel, en < T v, T w >=<

n X

vi T b i ,

i=1

n X

wj T bj >=

n X

vi wj < T bi , T bj >=

vi wi ,

i=1

i,j=1

j=1

n X

dat wil zeggen: (i) geldt. Omdat het duidelijk is dat (iii) ook (ii) impliceert, hoeven we tenslotte nog slechts te laten zien dat uit (ii) ook weer (i) volgt. Als M TE orthogonaal is, dan is T E een orthonormaal stelsel, en volgt voor elk tweetal v, w ∈ V door ze op basis E te schrijven dat: < T v, T w >=< T

n X

vi ei , T

i=1

net als < v, w >=<

n X

wj ej >=

i=1

vi wj < T ei , T ej >=

vi ei ,

n X j=1

wj ej >=

n X i=1

i,j=1

j=1

n X

n X

n X i=1

vi wi .

vi wi ,

7.1. ORTHOGONALE EN UNITAIRE TRANSFORMATIES

77

♣ Opgave 130. Laat zien dat de orthogonale n × n matrices over R een ondergroep vormen van de groep GLn (R).

Het complexe analogon van de orthogonale afbeelding is de unitaire afbeelding; de naam wordt duidelijk uit de eerstvolgende stelling. Definitie 7.1.7 Een lineaire afbeelding T : V → W tussen complexe inproductruimten heet een unitaire afbeelding als geldt dat < T v1 , T v2 >=< v1 , v2 >

voor alle v1 , v2 ∈ V ,

en bovendien dat T inverteerbaar is. Stelling 7.1.8 Voor een eigenwaarde λ van een unitaire transformatie geldt: |λ| = 1. Bewijs. Laat λ eigenwaarde zijn van de unitaire T , bij eigenvector v. Dan is < v, v >=< T v, T v >=< λv, λv >= λλ < v, v >, dus (1 − λλ) < v, v >= 0. Omdat v 6= 0 is < v, v >6= 0 en dus |λ| = 1.

♣ Opgave 131. Bewijs dat de eigenwaarden van een orthogonale afbeelding slechts ±1 kunnen zijn. T

Definitie 7.1.9 Een matrix M ∈ Mn×n (C) heet unitair wanneer M M = In . Stelling 7.1.10 Zij T een lineaire transformatie van de n-dimensionale complexe inproductruimte V . Dan zijn equivalent: (i) de transformatie T is unitair; (ii) er is een orthonormale basis E voor V zodat M TE een unitaire matrix is; (iii) de matrix MTB is unitair voor elke orthonormale basis B van V; (iv) T voert orthonormale bases voor V over in orthonormale bases. Bewijs. Geheel analoog aan 7.1.6. De volgende stelling laat zien dat unitaire afbeeldingen altijd diagonaliseerbaar zijn. Stelling 7.1.11 Zij T een unitaire lineaire transformatie van een eindig-dimensionale complexe inproductruimte V . Dan heeft V een orthonormale basis bestaande uit eigenvectoren voor T . Bewijs. Met inductie naar de dimensie n van V . Als n = 1 is er niets te bewijzen. Veronderstel dat n ≥ 2; kies een eigenvector w voor T (dat kan altijd omdat we over de complexe getallen werken!). Die kunnen we eventueel normaliseren (tot lengte 1) door door de lengte te delen. Laat W nu de 1-dimensionale deelruimte van V opgespannen door w zijn. Omdat w eigenvector is en T inverteerbaar, is T [W ] = W . Beschouw ook W ⊥ ; dan is T [W ⊥ ] ⊂ T [W ]⊥ , want als u ∈ W ⊥ dan T u ∈ T [W ]⊥ daar < T u, T w >=< u, w >. Maar V = W ⊕W ⊥ (dit volgt bijvoorbeeld uit Gram-Schmidt orthogonalisatie), zodat V = T [V ] = T [W ]⊕T [W ] ⊥ = W ⊕T [W ]⊥ zodat T beperkt tot W ⊥ een transformatie van een n − 1-dimensionale deelruimte is, waarvoor de unitaire eigenschap natuurlijk nog steeds geldt. De orthonormale basis van W ⊥ bestaande uit eigenvectoren voor (de beperking van) T , die op grond van de inductiehypothese dan bestaat, kan met de genormaliseerde van w aangevuld worden tot zo’n basis voor heel V .

78

7.2


Symmetrische en Hermitese Transformaties

De volgende begrippen hebben bepaalde symmetrie-eigenschappen ten aanzien van beide argumenten in een inproduct. Definitie 7.2.1 Een lineaire transformatie T : V → V van een reële inproductruimte heet een symmetrische transformatie als geldt dat < T v1 , v2 >=< v1 , T v2 >


Stelling 7.2.2 Zij T een lineaire transformatie van de n-dimensionale reële inproductruimte V . Dan zijn equivalent: (i) de afbeelding T is symmetrisch; (ii) er is een orthonormale basis E voor V zodat M TE symmetrisch is; (iii) de matrix MTB is symmetrisch voor elke orthonormale basis B van V. Bewijs. Ten opzichte van een orthonormale basis B = {b 1 , . . . , bn } van V is < T bi , bj >= Mji en < bi , T bj >= Mij , als Mkl de k-de coëfficiënt van de l-de kolom van M = MTB is, en die kolom is T bl . Als T symmetrisch is, geldt Mij =< bi , T bj >=< T bi , bj >= Mji , dus M is een symmetrische matrix. Daarom volgt (iii) uit (i). Het is duidelijk dat (ii) uit (iii) volgt. Als (ii) geldt voor de orthonormale basis E = {e 1 , . . . , en } van V , dan is < T v, w >=<

n X

vi T e i ,

n X

vi ei ,

i=1

n X

wj ej >=

j=1

n X n X

vi wj Mji ,

n n X X

vi wj Mij .

i=1 j=1

voor elke v, w, en < v, T w >=<

i=1

n X

wj T ej >=

i=1 j=1

j=1

Beide inproducten zijn gelijk als M = M TE een symmetrische matrix is, en dan is T een symmetrische transformatie. Dus (i) volgt uit (ii). Het complexe analogon van de symmetrische afbeelding is de Hermitese afbeelding. Definitie 7.2.3 Een lineaire transformatie T : V → V tussen van een complexe inproductruimte heet een Hermitese transformatie als geldt dat < T v1 , v2 >=< v1 , T v2 >


Stelling 7.2.4 Voor een complexe eigenwaarde λ van een Hermitese afbeelding geldt: λ ∈ R. Bewijs. Laat λ eigenwaarde zijn van de Hermitese T , bij eigenvector v. Dan is λ < v, v >=< λv, v >=< T v, v >=< v, T v >=< v, λv >= λ < v, v >, dus (λ − λ) < v, v >= 0. Omdat v 6= 0 is is λ = λ.

7.2. SYMMETRISCHE EN HERMITESE TRANSFORMATIES

79 T

Definitie 7.2.5 Een matrix M ∈ Mn×n (C) heet Hermites wanneer (M ∗ =)M = M. Stelling 7.2.6 Zij T een lineaire transformatie van de n-dimensionale complexe inproductruimte V . Dan zijn equivalent: (i) de afbeelding T is Hermites; (ii) er is een orthonormale basis E zodat M TE Hermites is; (iii) de matrix MTB is Hermites voor elke orthonormale basis B van V; Bewijs. Geheel analoog aan 7.2.2. Ook Hermitese afbeeldingen blijken weer diagonaliseerbaar te zijn. Stelling 7.2.7 Zij T een Hermitese lineaire transformatie van een eindig-dimensionale complexe inproductruimte V . Dan heeft V een orthonormale basis bestaande uit eigenvectoren voor T . Bewijs. Het bewijs is vrijwel gelijk aan dat van 7.1.11, en gaat met inductie naar n = dim V . Als n = 1 is er niets te bewijzen. Voor n ≥ 2 kiest men weer een eigenvector w voor T , en laat W de 1dimensionale deelruimte van V opgespannen door w zijn. Wederom is T [W ] ⊂ W en T [W ⊥ ] ⊂ W ⊥ ; dat laatste omdat voor u ∈ W ⊥ en voor alle y ∈ W nu geldt dat 0 =< u, T y >=< T u, y >, dus T u ∈ W ⊥ . Vanwege V = W ⊕ W ⊥ en de inductiehypothese volgt de bewering. In dit geval geldt een zelfde conclusie voor het reële geval. Gevolg 7.2.8 Zij T een symmetrische lineaire transformatie van een eindig-dimensionale reële inproductruimte V . Dan heeft V een orthonormale basis bestaande uit eigenvectoren voor T . Bewijs. Kies een orthonormale basis B voor V , dan is M TB een reëel symmetrische matrix, die ook een transformatie Tˆ op Cn (met n = dim V ) definieert. Bovendien is Tˆ Hermites, zodat Tˆ een eigenvector w heeft met eigenwaarde λ ∈ R volgens 7.2.4. Het reële (of het imaginaire) deel van w is dan een reële eigenvector van Tˆ , en dus van T . Maar dat betekent dat bij elke symmetrische T een reële eigenvector gevonden kan worden, en dus kan het bewijs met inductie net zo uitgevoerd worden als van stelling 7.2.7. ♣ Opgave 132. Laat zien dat als A, B Hermitese matrices zijn, ook AB + BA en i(AB − BA) Hermites zijn. Geldt hetzelfde met symmetrisch in plaats van Hermites? ♣ Opgave 133. Laat zien dat AB niet noodzakelijk Hermites is als de matrices A en B het zijn. ♣ Opgave 134. Laat A ∈ M3×3 (R) de matrix   1 −2 −2 1 −2 −2 1  3 −2 1 −2

zijn. Bepaal een orthonormale basis van eigenvectoren van A en bepaal ook een B ∈ M3×3 (C) met B 2 = A.

80


♣ Opgave 135. Bewijs dat voor een symmetrische reële n × n matrix A geldt: det A =

n Y

λi ,

i=1

waar λ1 , . . . , λn de eigenwaarden van A zijn. Geldt dit ook als A complex is?

7.3

Geadjungeerde en Normaliteit

In 7.1 en 7.2 werd bewezen dat voor het bestaan van een orthonormale basis bestaande uit eigenvectoren van een lineaire transformatie T in een eindig-dimensionale complexe inproductruimte V het voldoende is dat T Hermites is (volgens 7.2.7) of dat T unitair is (volgens 7.1.11). In deze paragraaf onderzoeken we noodzakelijke voorwaarden voor T voor het bestaan van zo’n basis. Eerst een Lemma dat we al eens gebruikten. Lemma 7.3.1 Zij V een eindig-dimensionale inproductruimte met orthonormale basis E = {e1 , e2 , . . . , en }. Dan geldt: P (i) x = ni=1 < x, ei > ·ei voor elke x ∈ V ; (ii) als T : V → V lineaire transformatie is, dan geldt M TE = (< T ej , ei >)ni,j=1 . Bewijs. (i) Volgt direct uit: < x, ei >=<

n X j=1

xj · ej , ei >=

n X

xj < ej , ei >= xi ,

j=1

omdat E een orthonormale basis is. Gebruik voor (ii) dat de j-de kolom van M TE bestaat uit het beeld van de vector ej ; volgens (i) is: n X T ej = < T ej , ei > ·ei , i=1

en er volgt dat op de i-de plaats van de j-de kolom (M TE )i,j =< T ej , ei > staat.

Stelling 7.3.2 Zij V een eindig-dimensionale complexe inproductruimte, en laat U : V → C een lineaire afbeelding zijn. Dan bestaat er een uniek bepaalde vector y ∈ V zodat voor alle x ∈ V geldt: U (x) =< x, y >. P Bewijs. Kies een orthonormale basis {e 1 , e2 , . . . , en }, dan is y = ni=1 U (ei ) · ei de gevraagde vector. Definieer namelijk S(x) =< x, y >, voor alle x ∈ V , dan is S lineair (omdat het inproduct lineair in het eerste argument is), en er geldt: S(ej ) =< ej , y >=< ej ,

n X i=1

U (ei ) · ei >=

n X

U (ei )· < ej , ei >= U (ej ).

i=1

Dus S = U . Dat bewijst het bestaan van y. Om te laten zien dat y uniek is, veronderstel je dat er een y 0 zodat ook U (x) =< 0 x, y > voor alle x; met U (x) =< x, y > volgt dan dat < x, y − y 0 >= 0 voor elke x. Kiezen we x = ei dan volgt dat de i-de coefficient van y − y 0 ten opzichte van de basis E gelijk 0 moet zijn. Omdat dit voor elke i geldt is y − y 0 = 0, dus y = y 0 .

7.3. GEADJUNGEERDE EN NORMALITEIT

81

Stelling 7.3.3 Zij V een eindig-dimensionale complexe inproductruimte, en laat T : V → V een lineaire transformatie zijn. Dan bestaat er een unieke lineaire transformatie T ∗ : V → V zodat voor elke x, y ∈ V : < T x, y >=< x, T ∗ y > . Bewijs. Kies y ∈ V . Definieer de afbeelding U : V → C door U (x) =< T x, y >, voor alle x ∈ V . Dan is U lineair omdat T en het inproduct het zijn: U (x1 + x2 ) =< T (x1 + x2 ), y >=< T x1 + T x2 , y >=< T x1 , y > + < T x2 , y > hetgeen gelijk is aan U (x1 ) + U (x2 ), en U (λx) =< T (λx), y >=< λT x, y >= λ < T x, y >= λU (x). Volgens de voorgaande Stelling is er dus een unieke vector z ∈ V zodat U (x) =< x, z > voor alle x ∈ V . Definieer nu T ∗ : V → V door T ∗ y = z, dan geldt zeker < T x, y >= U (x) =< x, z >=< x, T ∗ y > voor alle x, y ∈ V . Bovendien is T ∗ lineair, want < x, T ∗ (y1 +y2 ) >=< T x, y1 +y2 >=< T x, y1 > + < T x, y2 >=< x, T ∗ y1 +T ∗ y2 >, en ¯ < T x, y >= λ ¯ < x, T ∗ y >=< x, λT ∗ y > . < x, T ∗ (λy) >=< T x, λy >= λ Tenslotte is T ∗ uniek bepaald, want veronderstel dat er een lineaire transformatie R is zodat < T x, y >=< x, Ry > voor alle x, y ∈ V . Dan is < x, T ∗ y >=< x, Ry > voor alle x, y, dus < x, (T ∗ − R)y >= 0. Dan moet (T ∗ − R)y = 0, voor alle y ∈ V , dus T ∗ = R. Definitie 7.3.4 De unieke T ∗ bij een lineaire transformatie T wordt de geadjungeerde van T genoemd. Deze geadjungeerde heeft dus de eigenschap dat altijd < T x, y >=< x, T ∗ y >. Maar we weten dat voor het inproduct ook geldt dat < x, T y >= < T y, x > = < y, T ∗ x > =< T ∗ x, y >, met andere woorden: mits men adjungeert mag de transformatie T binnen het inproduct van argument wisselen! Stelling 7.3.5 Zij V een eindig-dimensionale complexe inproductruimte, en laten T en U lineaire transformaties van V zijn. Dan: (i) (ii) (iii) (iv)

(T + U )∗ = T ∗ + U ∗ ; ¯ ∗; (λT )∗ = λT ∗ (T U ) = U ∗ T ∗ ; T ∗∗ = T .

82


Het bewijs van 7.3.5 bestaat uit eenvoudige verificatie. Maar het volgt ook direkt uit de eigenschappen van matrices (zie beneden). Voor matrices A hadden we al eerder de notatie A ∗ ingevoerd, zie 6.3.8, en wel om de complex-geconjugeerde getransponeerde van A aan te geven: A ∗ = A¯T . We laten nu zien dat dit niet een ongelukkige keuze van notatie is: ten opzichte van een orthonormale basis is de matrix van de geadjungeerde van T inderdaad de geconjugeerd-getransponeerde van de matrix van T . Stelling 7.3.6 Zij V een eindig-dimensionale complexe inproductruimte met orthonormale basis E, en laat T : V → V een lineaire transformatie zijn. Dan geldt: MTE ∗ = (MTE )∗ .

Bewijs. Laat A = MTE de matrix van T ten opzichte van E zijn, en B = M TE ∗ die van T ∗ . Dan (volgens 7.3.1(ii)): Bi,j =< T ∗ ej , ei >=< ej , T ei >= < T ei , ej > = A¯j,i , zodat B = A¯T . Propositie 7.3.7 Laten A en B element van M n×n (C) zijn. Dan geldt: (i) (A + B)∗ = A∗ + B ∗ ; ¯ ∗; (ii) (λA)∗ = λA ∗ (iii) (AB) = B ∗ A∗ ; (iv) A∗∗ = A. Bewijs. Volgt onmiddellijk uit de eigenschappen van complexe conjugatie en transpositie. Het bewijs van 7.3.5 volgt nu direkt uit 7.3.6 en 7.3.7. De eerder geintroduceerde begrippen Hermites en unitair voor lineaire transformaties van complexe vectorruimten zijn nauw verwant aan adjungeren. De eis voor Hermites zijn was dat < T x, y >=< x, T y > voor elke x, y ∈ V , terwijl een unitaire afbeelding voldoet aan < T x, T y >=< x, y > voor elke x, y ∈ V . Met I V geven we de identieke afbeelding op V aan. Propositie 7.3.8 Laat T een lineaire transformatie van de eindig-dimensionale complexe vectorruimte V zijn. Dan geldt: (i) T is Hermites ⇐⇒ T∗ = T, (ii) T is unitair ⇐⇒ T T ∗ = IV = T ∗ T ⇐⇒ T ∗ = T −1 . Bewijs. De transformatie T is Hermites dan en slechts dan als < T x, y >=< x, T y > altijd geldt; anderzijds geldt altijd < T x, y >=< x, T ∗ y > dus Hermites zijn is equivalent met T = T ∗ . Unitair zijn betekent dat altijd < T x, T y >=< x, y >. Maar er geldt ook steeds dat < T x, T y >=< T ∗ T x, y > en dus is unitair zijn equivalent met T ∗ T = IV . Dus T ∗ = T −1 , maar dan is ook T ∗ T = T T ∗ . We zagen ook reeds dat Hermites zijn het bestaan van een orthonormale basis van eigenvectoren impliceerde (en dus diagonaliseerbaarheid). De omgekeerde implicatie blijkt in het complexe geval n´ıet op te gaan: een noodzakelijke en voldoende voorwaarde voor diagonaliseerbaarheid in het complexe geval blijkt normaliteit te zijn.


83

Definitie 7.3.9 De lineaire transformatie T van een complexe vectorruimte heet normaal als T T ∗ = T ∗ T . We noemen een matrix A ∈ Mn×n (C) normaal wanneer A∗ A = AA∗ . Gevolg 7.3.10 T is normaal dan en slechts dan als M TE normaal is, voor een orthonormale basis E. Gevolg 7.3.11 (i) Als T Hermites is dan is T normaal. (ii) Als T unitair is dan is T normaal. Alvorens we afleiden dat normaliteit equivalent is met het bestaan van een orthonormale basis van eigenvectoren, bekijken we enkele eigenschappen van normale transformaties. Stelling 7.3.12 Laat V een eindig-dimensionale complexe inproductruimte met orthonormale basis E zijn en laat T : V → V een lineaire transformatie zijn. Als T normaal is, dan geldt: (i) kT xk = kT ∗ xk voor alle x ∈ V ; (ii) T − λIV is normaal, voor elke λ ∈ C; (iii) als v een eigenvector voor T is met eigenwaarde λ, dan is v ook een eigen¯ vector voor T ∗ , en wel met eigenwaarde λ; (iv) als v1 en v2 eigenvectoren van T zijn bij verschillende eigenwaarden, dan < v1 , v2 >= 0. Bewijs. (i) Voor elke x ∈ V geldt kT xk2 =< T x, T x >=< T ∗ T x, x >=< T T ∗ x, x >=< T ∗ x, T ∗ x >= kT ∗ xk2 , en lengten zijn altijd niet-negatief. (ii) Omdat IV∗ = IV is ¯ V )(T − λIV ) = T ∗ T − λT ¯ − λT ∗ + |λ|2 IV = (T − λIV )∗ (T − λIV ) = (T ∗ − λI ∗ ∗ 2 ¯ = T T − λT − λT + |λ| IV = (T − λIV )(T − λIV )∗ . (iii) Beschouw U = T − λIV voor de eigenwaarde λ van T . Voor de bijbehorende eigenvector v is dan U v = 0. Volgens (ii) is U normaal, zodat op grond van (i): ¯ 0 = kU vk = kU ∗ vk = k(T − λIV )∗ vk = kT ∗ v − λvk, ¯ en daarom is T ∗ v = λv. (iv) Omdat λ1 < v1 , v2 > gelijk is aan ¯ 2 v2 >= λ2 < v1 , v2 >, < λ1 v1 , v2 >=< T v1 , v2 >=< v1 , T ∗ v2 >=< v1 , λ en omdat λ1 6= λ2 volgt dat < v1 , v2 >= 0. ♣ Opgave 136. Waar in het bewijs van 7.3.12(iv) wordt normaliteit gebruikt?

Stelling 7.3.13 Zij V een eindig-dimensionale complexe inproductruimte, en laat T een lineaire transformatie van V zijn. Dan is T normaal dan en slechts dan als er een orthonormale basis voor V is bestaande uit eigenvectoren van T .

84


Bewijs. Veronderstel dat T normaal is. We plegen inductie naar de dimensie n. Als n = 1 is het duidelijk. Laat λ een nulpunt zijn van het karakteristieke polynoom van T , en zij w een eigenvector van T bij λ. Dan is w ook een eigenvector ¯ Zij W de ruimte opgespannen door w en laat x ∈ W ⊥ . Dan is van T ∗ (bij λ). ¯ >= λ < x, w >= 0, < T x, w >=< x, T ∗ w >=< x, λw dus T x ∈ W ⊥ , dus W ⊥ is T -invariant. Omdat V = W ⊕ W ⊥ , is W ⊥ een n − 1-dimensionale T -invariante ruimte, waarop we de inductiehypothese kunnen toepassen: we vinden een orthonormale basis w 2 , w3 , . . . , wn van eigenvectoren van T . Dan is w/kwk, w2 , w3 , . . . , wn een basis van de gevraagde vorm voor V . Veronderstel, voor de omkering, dat B = {b 1 , . . . , bn } een orthonormale basis van V is, bestaande uit eigenvectoren voor T . Ten opzichte van die basis wordt T gegeven door een diagonaalmatrix:   λ1 0 · · · 0  0 λ2 · · · 0  A = MTB =  .. . . . ,  ... . ..  . 0

maar dan is

A∗ = MTB∗

···

0

¯ λ1  0 =  ... 0

0 ¯2 λ .. .

··· ··· .. .

0

···

λn

 0 0  ..  .  ¯n λ

ook een diagonaalmatrix, en diagonaalmatrices commuteren, dus T T ∗ = T ∗ T . Stelling 7.3.14 Zij V een eindig-dimensionale complexe inproductruimte, en laat T een lineaire transformatie van V zijn. Dan is T unitair dan en slechts dan als er een orthonormale basis voor V is bestaande uit eigenvectoren van T bij eigenwaarden van absolute waarde 1. Bewijs. Als T unitair is dan is T normaal (volgens Gevolg 7.3.11) en dus bestaat er een orthonormale basis van eigenvectoren; elke eigenwaarde λ van een unitaire afbeelding heeft |λ| = 1, omdat unitaire afbeeldingen lengten behouden (zie 7.1.8). Dat bewijst de ene implicatie. Voor de omkering nemen we het bestaan aan van zo’n speciale basis B bestaande uit vectoren bi bij de eigenwaarden λi met |λi | = 1. Dan is T normaal (volgens ¯ i volgens 7.3.12. Stelling 7.3.13), dus bi is ook eigenvector van T ∗ met eigenwaarde λ Dus: ¯ i bi = |λi |2 bi = bi , T ∗ T bi = T ∗ (λi bi ) = λi λ dus T ∗ T = IV en T is orthogonaal.

Tenslotte nog een stelling die verband legt tussen de begrippen normaal en unitair voor matrices. Definitie 7.3.15 Twee matrices A en B heten unitair equivalent als A = U ∗ BU voor een unitaire matrix U . Merk op dat voor zulke matrices U ∗ = U −1 . Stelling 7.3.16 Laat A ∈ Mn×n (C). Dan is A normaal dan en slechts dan als A unitair equivalent is aan een diagonaalmatrix.


85

Bewijs. Als A normaal is, dan bestaat er een orthonormale basis voor de vectorruimte opgebouwd uit eigenvectoren van A die orthonormaal zijn; maar na transformatie naar die basis is A dan op diagonaalvorm gebracht, en de transformatiematrix bestaat uit de kolommen die de eigenvectoren zijn, en deze vormen een orthonormaal stelsel. Dus is de transformatiematrix unitair. Omgekeerd, veronderstel dat A = U ∗ DU , met U unitair en D een diagonaalmatrix; dan: AA∗ = (U ∗ DU )(U ∗ DU )∗ = (U ∗ DU )(U ∗ D ∗ U ) = U ∗ DD ∗ U = U ∗ D ∗ DU = A∗ A, dus A is normaal. Voor reële inproductruimten is de situatie een kleine beetje anders. In dit geval blijkt symmetrie (het reële equivalent van Hermites) de belangrijke eigenschap te zijn. Stelling 7.3.17 Zij V een eindig-dimensionale reële inproductruimte, en laat T een lineaire transformatie van V zijn. Dan is T symmetrisch dan en slechts dan als er een orthonormale basis voor V is bestaande uit eigenvectoren van T . Bewijs. Dit volgt direkt uit 7.2.8 en 7.2.2. Stelling 7.3.18 Laat A ∈ Mn×n (R). Dan is A symmetrisch dan en slechts dan als A orthogonaal equivalent is aan een diagonaalmatrix. Bewijs. Net als in het complexe geval 7.3.16. ♣ Opgave 137. Geef een voorbeeld van lineaire transformatie T van de R2 die wel voldoet aan T ∗ T = T T ∗ maar die niet diagonaliseerbaar is. ♣ Opgave 138. Laat B de basis van V = R3 zijn bestaande        2 √ 1 1 1 √ 2 B  0  ,  √2  ,  2 √3  en MT =  0 3 √1 0 0 0 3

uit  2 4 −1 −4  0 1

de matrix voor een lineaire transformatie T van V . Laat zien dat T orthogonaal is, en dat T symmetrisch is, en bepaal een orthonormale basis van V bestaande uit eigenvectoren voor T . ♣ Opgave 139. Laat het reële lineaire stelsel vergelijkingen Ax = b gegeven zijn door:     4 1 2 1 A =  1 −1 2  , en b =  −11  . 19 1 5 0

Bepaal een oplossing v voor AA∗ v = b en laat zien dat w = A∗ v voldoet aan Ax = b en dat voor elke andere oplossing w 0 geldt dat ||w0 || ≥ ||w||.

86


Huiswerkopgaven

87

Huiswerkopgaven I

♠ Huiswerk I-1. Veronderstel dat de verzameling R met bewerkingen + en × gegeven is. (i) Laat zien dat als R, + aan [L2] voldoet, het element 0 uniek is. (ii) Laat zien dat als R, +, × een ring met 1 vormt (die niet noodzakelijk commutatief is), er geldt dat 0 × r = r × 0 = 0, dat −1 × r = r × −1 = −r, en dat r × (−s) = (−r) × s = −(r × s) voor alle r, s ∈ R. Houd in elke stap bij welke eigenschap je gebruikt! ♠ Huiswerk I-2. Laat V een verzameling zijn met daarop een bewerking die we met · aangeven. Veronderstel dat deze bewerking associatief is, dus ∀x, y, z ∈ V :

(x · y) · z = x · (y · z).

(i) Laat zien dat dan ook geldt: ∀x, y, z, a ∈ V :

((x · y) · z) · a = (x · y) · (z · a).

Het is eenvoudig (maar vervelend) om te laten zien dat matrixvermenigvuldiging van 2 × 2 matrices van rationale getallen een associatieve bewerking is; dus × is een associatieve bewerking op M2 (Q). (ii) Laat door een tegenvoorbeeld zien dat × geen commutatieve bewerking is op M 2 (Q). (iii) Laat zien dat voor een verzameling met een associatieve bewerking niet altijd geldt: ∀x, y, z ∈ V :

(x · y) · z = y · (z · x).

♠ Huiswerk I-3. Laat E een eindige, niet-lege verzameling zijn. Laat P (E) de machtsverzameling van E zijn, dat is de verzameling waarvan de elementen de deelverzamelingen van E zijn. (i) Voor elk tweetal deelverzamelingen A, B van E definiëren we A + B = (A ∪ B) \ (A ∩ B);

(ii) (iii) (iv) (v)

dus A + B bestaat uit elementen van E die wel in de vereniging maar niet in de doorsnede van A en B zitten. Laat zien dat dit een bewerking op P (E) geeft. Laat zien dat deze bewerking + op P (E) commutatief is. Laat zien dat er een element 0 van P (E) bestaat zodat A + 0 = A. Laat zien dat bij elke A in P (E) een A−1 bestaat zodat A + A−1 = 0, met de 0 uit (iii). Maak twee plaatjes van drie elkaar snijdende cirkels die drie deelverzamelingen A, B, C van E voorstellen. Elementen van A liggen dan binnen de eerste cirkel, van A ∩ B in het stuk waar A en B overlappen, enz. Geef door arcering in het eerste plaatje aan waar (A+B)+C zit, en in het tweede waar A+(B +C). Is + associatief op P (E)?

Huiswerkopgaven II

Een relatie ∼ op een verzameling V wordt gedefinieerd door een deelverzameling R van V × V , bestaande uit de elementen (v, w) ∈ V × V waarvoor v ∼ w; we zeggen dan dat v in relatie ∼ tot w staat. Voor alle paren die niet in R zitten geldt v 6∼ w. Een voorbeeld is de relatie ≤ op Z. Een equivalentierelatie op een verzameling V is een relatie ∼ op V zodanig dat voor alle u, v, w ∈ V geldt: u ∼ u (reflexiviteit), en v ∼ u als u ∼ v (symmetrie), en u ∼ w als u ∼ v èn v ∼ w (transitiviteit). Een equivalentierelatie splitst V op in (disjuncte) equivalentieklassen. ♠ Huiswerk II-1. De elementen van Z/mZ zijn de restklassen ¯ 0, ¯ 1, . . . , m − 1. (i) Maak een opteltabel en een vermenigvuldigtabel voor Z/2Z, Z/3Z, Z/6Z en Z/8Z. (De rijen en kolommen van de tabel corresponderen met de verschillende elementen van Z/mZ, en op plaats i, j staat de som, resp. het product van ¯i en ¯j in Z/mZ.) (ii) Geef aan hoe je uit deze tabellen ziet of een element eenheid is en of een element nuldeler is. (iii) Gebruik (ii) om deze vraag te beantwoorden: welke van de vier ringen uit (i) vormen een lichaam? (iv) Laat zien dat de relatie x ∼ y ⇐⇒ x ≡ y mod m (dus x ¯ = y¯) een equivalentierelatie op Z is. ♠ Huiswerk II-2. In de volgende onderdelen is R = Z/2Z de ring van restklassen modulo 2, die dus alleen uit ¯ 0, ¯ 1 bestaat. (i) Hoeveel verschillende elementen heeft M2 (R), de ring van 2×2 matrices met coëfficiënten uit R? (ii) Wat is het element 0 in M2 (R) en wat is het element 1 (uit de definitie van lichaam, ring enz.)? (iii) Vind een element ongelijk aan 0 in M2 (R) dat geen eenheid is. (iv) Vind een element ongelijk aan 1 in M2 (R) dat een eenheid is. (v) Vind twee elementen r, s in M2 (R) met r × s = 0 maar s × r 6= 0. ♠ Huiswerk II-3. Laat S[x] de polynoomring zijn met S = Z/6Z: de elementen zijn dus polynomen met coëfficiënten in Z/6Z. Vind een polynoom f van graad 2 en een polynoom g van graad 3 in S[x] met f × g = 0, en vind ook twee polynomen p, q ∈ S[x] van graad minstens 1 met p × q = x + 2 ∈ S[x].

♠ Huiswerk II-4. [ Breukenlichaam ]. Laat R met + en × een ring (commutatief met 1) zonder nuldelers zijn. We definiëren een equivalentierelatie ∼ op de verzameling V = {(r, s) : r, s ∈ R, s 6= 0} als volgt: (r1 , s1 ) ∼ (r2 , s2 )

⇐⇒

r 1 × s2 = r2 × s1 .

We geven de equivalentieklasse van elementen uit V waar (t, n) in zit meestal aan met Op deze klassen kunnen we optelling en vermenigvuldiging definiëren door t1 t2 t1 × n 2 + t 2 × n 1 + = , n1 n2 n1 × n 2

en

t n.

t1 t2 t1 × t 2 × = . n1 n2 n1 × n 2

(i) Wanneer R = Z, waaruit bestaat dan de verzameling elementen van V die equivalent zijn met (0, 1), en waaruit de equivalentieklassen van (1, 1) en van (3, −1)? (ii) Laat zien dat voor R = Z bij elke equivalentieklasse een tegengestelde bestaat, en, als het niet de klasse 01 is, ook een inverse. (iii) Als nu R = Q[x], beantwoord dan dezelfde vragen uit (i) en (ii). De constructie in deze opgave maakt het breukenlichaam bij een domein.

Huiswerkopgaven III

♠ Huiswerk III-1. Laten R en S beide commutatieve ring met 1 zijn. (i) Laat zien dat uit de definitie volgt dat voor een ringhomomorfisme f geldt dat f (0) = 0, waar links het nulelement van R staat en rechts dat van S. (ii) Is de afbeelding die aan elke r ∈ R het element 0 toevoegt een ringhomomorfisme? (iii) Wat is er mis met de volgende redenering: de eis dat f (1) = 1 in de definitie van ringhomomorfisme is overbodig want f (1) × f (r) = f (1 × r) = f (r) voor elke r ∈ R, dus is f (1) = 1. (iv) Laat zien dat er geen ringhomomorfisme van Z/5Z naar Z/3Z bestaat, en wel van Z/6Z naar Z/3Z. (v) We kunnen de verzameling paren {(x, y) : x ∈ R, y ∈ S} tot een commutatieve ring met 1 maken door de bewerkingen (r1 , s1 ) + (r2 , s2 ) = (r1 + r2 , s1 + s2 ) en (r1 , s1 ) × (r2 , s2 ) = (r1 × r2 , s1 × s2 ) te definiëren. Geef het nulelement en het eenheidselement van deze ring R × S aan, en geef ook twee verschillende nuldelers in deze ring aan. (vi) Geef een ringisomorfisme tussen Z/6Z en Z/2Z × Z/3Z. (vii) Vind alle eenheden en alle nuldelers in Z/9Z en in Z/3Z × Z/3Z. Bestaat er een ringisomorfisme tussen Z/9Z en Z/3Z × Z/3Z? ♠ Huiswerk III-2. Laat K een lichaam zijn. We schrijven elementen uit K n als rijvectoren. (i) Laat zien dat de verzameling W bestaande uit elementen (w1 , w2 , w3 , w4 , w5 ) ∈ K 5 met w2 − w3 − w4 = 0 een lineaire deelruimte van K 5 vormt. (ii) Wat is de dimensie van W ? Geef ook een basis voor W . (iii) Laat zien dat de rationale oplossingen van het stelsel vergelijkingen x1 − 2x2 + x3 2x1 − 4x2 − x3

= 0 = 0

een lineaire deelruimte U van Q3 vormen. (iv) Geef de dimensie en een basis voor U . ♠ Huiswerk III-3. Weer is K een lichaam, en Mn (K) bestaat uit de vierkante n × n matrices over K. (i) Laat zien dat de verzameling Dn van n × n diagonaalmatrices over K (alleen op de diagonaal mogen elementen 6= 0 zijn) een lineaire deelruimte is van Mn (K). (ii) Bepaal de dimensie van Dn , en geef een basis voor Dn . (iii) Hoeveel elementen heeft Dn als K = F3 een lichaam met 3 elementen is? ♠ Huiswerk III-4. Laat V een K-vectorruimte zijn. (i) Bewijs dat de doorsnede W1 ∩ W2 van twee lineaire deelruimten W1 , W2 van V weer een lineaire deelruimte van V is. (ii) Geef een voorbeeld waaruit blijkt dat de vereniging W1 ∪ W2 van twee lineaire deelruimten van V niet weer een lineaire deelruimte van V hoeft te zijn. (iii) Bewijs dat zelfs geldt voor lineaire deelruimten W1 , W2 van V dat W1 ∪ W2 een lineaire deelruimte van V is dan en slechts dan als W1 ⊂ W2 of W2 ⊂ W1 .

Huiswerkopgaven IV

♠ Huiswerk IV-1. [ Universal Product Code en International Standard Book Number ] (i) Beschouw de UPC (0, 7, 7, 7, 7, 8, 6, 6, 3, 5, 2, c) van een muziek-CD. Bepaal c. (ii) Ga na dat de UPC (0, 1, 2, 9, 8, 1, 7, 0, 0, 1, 2, 6) verminkt is; geef twee verschillende correcties van 1 cijfer die tot een correcte UPC leiden. (iii) Bewijs dat de UPC 1 fout kan detecteren, maar niet kan corrigeren. (iv) Bepaal het check-digit d van het boek met ISBN (9, 0, 6, 1, 6, 8, 3, 7, 9, d). (v) Bewijs dat ISBN 1 fout kan detecteren, maar niet kan corrigeren. (vi) Bewijs dat ISBN een andere veeloptredende typefout kan detecteren, namelijk de verwisseling van 2 cijfers die naast elkaar staan. (vii) Is de ISBN codering lineair in de zin dat zowel de nulvector als de som van elk tweetal codewoorden een codewoord is? (Let hierbij niet op de betekenis van cijfers als landenaanduiding etc) ♠ Huiswerk IV-2. Bewijs dat de Hammingafstand op Fn2 voor elke n een metriek definieert. ♠ Huiswerk IV-3. [ Even gewicht code ] (i) Laat zien dat de vectoren van even gewicht in Fn2 een code vormen. (ii) Wat is de minimumafstand van de code uit (i)? (iii) Vormen de even gewicht vectoren in Fn3 een code? ♠ Huiswerk IV-4. [ Hamming codes ] (i) Schrijf alle codewoorden van de Hammingcode C2 met r = 2 op. (ii) Schrijf alle codewoorden van de Hammingcode C3 met r = 3 op. (iii) Wat is de dimensie van de Hammingcode C4 met r = 4? (iv) Schrijf de parity-checkmatrix H3 (volgens de constructie van het dictaat) voor C3 op. (v) Een vector c uit F72 zit in C3 wanneer geldt dat het product van de vector c en de matrix H3 precies de nulvector oplevert (in F32 ). Veronderstel nu dat alleen de i-de bit van c gewijzigd is, wat is dan het product c0 H3 van de gewijzgde c0 en H3 ? (vi) Gebruik het vorige onderdeel om te bepalen in welke co¨ ordinaat van de vector (1, 1, 0, 0, 1, 1, 0) een fout geslopen is. (vii) Laat voor r = 2, 3, 4 zien dat de Hammingcode precies de Hamming grens bereikt voor e = 1.

Huiswerkopgaven V

♠ Huiswerk V-1. Laat ψ op R3 de lineaire afbeelding zijn die een vector v roteert over een vaste hoek φ om de lijn door de oorsprong opgespannen door e1 + e2 + e3 , waar E = {e1 , e2 , e3 } een basis voor R3 is. (i) Kies een handige nieuwe basis C voor R3 en geef de matrix CMψC voor de afbeelding ψ ten opzichte van deze basis. C E (ii) Geef de matrices EMid en CMid . E E (iii) Geef de matrix Mψ voor ψ ten opzichte van de oorspronkelijke basis E. ♠ Huiswerk V-2. Laat φ de lineaire afbeelding van Q2 naar Q[x](2) zijn gedefinieerd door 1 2 2 φ = 2 − 3x + x , φ = 1 − x2 . 1 3 Hier is Q[x](2) de vectorruimte van polynomen van graad ten hoogste 2 over Q. −1 a (i) Bepaal het beeld van en van voor willekeurige a, b ∈ Q. 2 b (ii) Kies bases voor Q2 en Q[x](2) en geef de matrix van φ ten opzichte hiervan. (iii) Geef een basis voor het beeld van φ en een basis voor de kern van φ. (iv) Is er een vector in Q2 met beeld 1 − x? Zo ja, geef zo’n vector. Idem voor beeld −6 + 10x − 6x2 . ♠ Huiswerk V-3. Laat K een lichaam zijn, en laten V, W twee K-vectorruimten zijn. (i) Bewijs: als f een injectieve lineaire afbeelding is, dan is het beeld van een eindig stelsel lineair onafhankelijke vectoren weer lineair onafhankelijk. (ii) Bewijs: als V en W eindig-dimensionaal zijn en f is een isomorfisme, dan is dim V = dim W . (iii) Laat V = Q[x] en W de lineaire deelruimte van Q[x] bestaande uit {a0 + a1 x + a2 x2 + · · · + an xn ∈ Q[x]: a1 = a3 = a5 = · · · = 0} (dus polynomen waarin geen oneven machten van x voorkomen). Is de afbeelding φ : V → W die gegeven wordt door φ(c0 + c1 x + · · · + ck xk ) = c0 + c1 x2 + c2 x4 + · · · ck x2k een lineaire afbeelding? En is de afbeelding injectief? Surjectief? ♠ Huiswerk V-4. [ Differentiatie ] De afbeelding D van de vectorruimte R[x] van polynomen met reële coëfficiënten naar zichzelf is gegeven door de gebruikelijke differentatieregels, dus D(f (x)) = f 0 (x) (i) Laat zien dat D een lineaire afbeelding is. (ii) Wanneer we D beperken tot de deelruimte R[x](n) van polynomen van graad ten hoogste n, wat is dan het beeld en wat is de kern van D? Geef ook de matrix MD ten opzichte van een basis voor R[x](n) . (iii) Bestaat er een polynoom f ∈ R[x] zodanig dat D(f ) = f ? (iv) Je kunt D voortzetten tot lineaire afbeelding op de reële vectorruimte van formele P∞ machtreeksen i=0 ai xi (er mogen dus nu oneindig veel niet-nul termen zijn). Bepaal een formele machtreeks F met D(F ) = F .

Huiswerkopgaven VI

♠ Huiswerk VI-1. In de volgende onderdelen zijn steeds twee bases B and C voor Q 2 B gegeven, Bepaal in alle gevallen de matrix CMid , die een vector gegeven door coordinaten ten opzichte van basis B schrijft in coordinaten ten opzichte van C, en ook de matrix B C Mid . (i) −1 2 1 0 . , , C= , B= −3 5 0 1 (ii) B=

−4 3

2 , , −1

−4 2 . , C= 1 1

(iii) B=

0 1 , , 1 0

C=

0 −1

−1 . , 0

(iv) a b B= , , c d

1 0 C= , . 0 1

♠ Huiswerk VI-2. Laat V de vectorruimte M2×2 (Q) van 2 bij 2 matrices over Q zijn, en laat de standaardbasis E bestaan uit de elementaire matrices (met een 1 op één plaats en elders 0-en). E als B de basis voor V is bestaande uit (i) Bepaal BMid 1 1 1 1 1 1 1 0 . , , , 1 1 1 0 0 0 0 0 C , als C de basis voor V is bestaande uit (ii) Bepaal BMid 1 0 0 1 1 0 0 1 , , , , 0 1 1 0 1 0 1 1

en controleer je antwoord door te kijken naar de som van de vectoren uit C. ♠ Huiswerk VI-3. [ Uitwendig product en normaalvergelijking ] Laat een vlak V in R3 gegeven zijn door de vectorvergelijking ~x = p~ + λ~ q + µ~r, voor onafhankelijke vectoren q~ en ~r in R3 , met λ, µ ∈ R. Met h~a, ~bi geven we het standaardinproduct van ~a, ~b ∈ R3 aan. (i) Laat zien dat als ~n loodrecht op q~ en op ~r staat (dus h~n, q~i = h~n, ~ri = 0) dat dan ~n loodrecht op ~x − p~ staat voor elke vector ~x met eindpunt in het vlak V . (ii) Laat omgekeerd zien dat, wanneer ~n loodrecht op ~x − p ~ staat voor elke vector ~x met eindpunt in het vlak V , wel moet gelden dat ~ n loodrecht op ~q en op ~r staat.   q2 r3 − q 3 r2 (iii) Laat zien dat de vector ~q × ~r =  −q1 r3 + q3 r1 , die het uitwendig product of q1 r2 − q 2 r1 uitproduct of vector product van q~ en ~r heet, loodrecht staat op ~q en ~r. (iv) Leid uit het voorgaande af dat de co¨ ordinaten van alle ~x met eindpunt in V voldoen aan:     p 1 q1 r1 x1 q 1 r 1 det  x2 q2 r2  = det  p2 q2 r2  . p 3 q3 r3 x3 q 3 r 3 Deze lineaire vergelijking heet wel een normaalvergelijking voor het vlak.

(v) Geef een normaalvergelijking voor het vlak door de punten A = (1, 2, 3), B = (2, −1, 1) en C = (1, 1, 1). ♠ Huiswerk VI-4. [ Uitwendig product (vervolg) ] Laat ~a × ~b het uitwendig product van ~a en ~b zijn als gegeven in Huiswerkopgave VI-3. (i) Bewijs dat over elk lichaam van karakteristiek ongelijk aan 2 uit de eigenschap van determinanten dat verwisseling van twee verschillende kolommen van een vierkante matrix resulteert in vermenigvuldiging van de determinant met −1 volgt dat de determinant nul is wanneer twee kolommen hetzelfde zijn. (ii) Laat zien dat voor elk drietal vectoren ~a, ~b, ~c uit R3 geldt dat   a 1 b1 c1 h~a, ~b × ~ci = det  a2 b2 c2  . a 3 b3 c3

(iii) Gebruik (ii) en de eigenschappen van determinanten om te laten zien dat ~a × ~b = −~b × ~a, voor elk tweetal vectoren ~a, ~b uit R3 . (iv) Idem voor de eigenschappen h~a, ~b × ~ci = h~a × ~b, ~ci en h~a, ~a × ~bi = 0. (v) Bewijs dat k~a × ~bk2 = k~ak2 · k~bk2 − h~a, ~bi2 . (vi) Gebruik (v) en de eigenschap h~a, ~bi = k~ak · k~bk · cos φ, waar φ de hoek tussen ~a en ~b is, om te laten zien dat k~a × ~bk = k~ak · k~bk · sin φ.

Huiswerkopgaven VII

♠ Huiswerk VII-1. Laat V de vectorruimte Q3 zijn en W = Q2 . (i) Laat B de basis van V zijn bestaande uit de vectoren       1 1 0 b1 =  0  , b2 =  2  , b3 =  0  . 1 1 1

Bepaal de duale basis B ∗ door voor i = 1, 2, 3 aan te geven wat het beeld   x b∗i  y  z

is van de vector met co¨ ordinaten x, y, z ten opzichte van de standaardbasis. Hint: b∗i (bj ) = δij . (ii) Zij C de basis van W bestaande uit −1 2 . , c2 = c1 = 3 1 Bepaal net als in (i) de duale basis C ∗ . (iii) Laat f de lineaire afbeelding van V naar W zijn die ten opzichte van de standaardbases voor V en W door de matrix −3 0 1 M= −5 72 4 gegeven wordt. Bepaal CMfB , de matrix van f ten opzichte van de basis B voor V en C voor W (door de beelden van bi op de basis C te schrijven). (iv) Gebruik de definitie van de getransponeerde f T om f T (c∗1 ) en f T (c∗2 ) te bepalen: daarvoor is het nodig dat je de waarde van de functionaal f T (c∗1 ) op b1 , op b2 , en op b3 uitrekent, en net zo de waarden van f T (c∗2 ) op b1 , op b2 , en op b3 . Gebruik dat c∗i (cj ) = δij . ∗ ∗ (v) Met (iv) kun je nu direct de matrix B MfC van f T ten opzichte van de de bases C ∗ en B ∗ opschrijven. Doe dat en laat zien wat het verband met CMfB is. ♠ Huiswerk VII-2. Laat V de reële 3-dimensionale vectorruimte R3 zijn en laat U een vlak door de oorsprong zijn. Steeds is v + U = {v + u : u ∈ U }. (i) Laten v1 en v2 vectoren uit V zijn. Bewijs dat voor de nevenklassen v1 +U en v2 +U geldt: v1 + U = v2 + U dan en slechts dan als v1 − v2 ∈ U . (ii) Laat zien dat hieruit volgt: v1 + U = v2 + U of (v1 + U ) ∩ (v2 + U ) = ∅. (iii) Laat zien dat uit de definities volgt: als v1 +U = v2 +U dan geldt ook (w+U )+(v1 + U ) = (w + U ) + (v2 + U ), voor w ∈ V . (Optelling hangt niet van keuze representant af) (iv) Zijn beweringen (i), (ii) of (iii) ook waar als U niet door de oorsprong gaat? (v) Zijn beweringen (i), (ii) of (iii) ook waar als U een vlak door de oorsprong in de vierdimensionale ruimte F45 over het lichaam van 5 elementen is?

Huiswerkopgaven VIII

♠ Huiswerk VIII-1. In de onderstaande onderdelen geef je het bewijs voor de volgende Stelling, die het analogon in Z is van Stelling 2.1.2. • Stelling Laat a, b ∈ Z met a ≥ 0 en b > 0; dan bestaan er q, r ∈ Z met a = q · b + r en 0 ≤ r < b; bovendien zijn deze q en r uniek bepaald. (i) (ii) (iii) (iv)

Geef q en r die voldoen als a = 0. Geef q en r die voldoen als a < b. Geef q en r die voldoen als a = b. Neem nu aan dat a > b. Veronderstel dat je de Stelling al hebt bewezen voor alle c, b ∈ Z met c < a (de Inductiehypothese). Laat zien dat dan de bewering ook volgt voor a en b. (v) Laat zien dat q en r uniek zijn door aan te nemen dat er nog een tweede stel q 0 , r0 met dezelfde eigenschap en een tegenspraak af te leiden.

♠ Huiswerk VIII-2. (i) Laat zien dat als f, g twee polynomen in Z[x] ongelijk aan nul zijn, dat deg f · g = deg f + deg g. Is dit ook waar als f = 0 of g = 0 (met deg 0 = −∞)? (ii) Laat zien dat als f, g twee polynomen in (Z/6Z)[x] zijn, niet hoeft te gelden dat deg f · g = deg f + deg g. En in (Z/2Z)[x]? (iii) Is het voor elke commutatieve ring R met 1 waar dat voor elk tweetal polynomen f, g ∈ R[x] geldt dat deg(f + g) = max(deg f, deg g)? (iv) Vind alle nulpunten uit Z/12Z van het polynoom x2 + 11 ∈ (Z/12Z)[x]. (v) Laat zien dat er monische polynomen in (Z/12Z)[x] zijn die op twee essentieel verschillende manieren als product van irreducibele polynomen te schrijven zijn. ♠ Huiswerk VIII-3. Gebruik het (uitgebreide) algoritme van Euclides om de onderdelen (i) en (iii) te beantwoorden. (i) Vind de grootste gemene deler d van 35 en 26, en ook getallen s en t zodanig dat s × 35 + t × 26 = d. (ii) Is 26 een eenheid in Z/35Z, en zo ja, wat is de inverse van 26? (iii) Vind de grootste gemene deler van f = x3 + ¯ 1 en g = x2 + ¯ 1, waar de polynomen f, g element zijn van (Z/2Z)[x]. (iv) Laat door substitutie zien dat zowel f als g deelbaar is door x + ¯ 1. ♠ Huiswerk VIII-4. Ontbind de volgende polynomen over de aangegeven lichamen in irreducibele factoren. (i) x4 − 2 over Q, over R en over C; (ii) x8 − 1 over Q, over R en over C; (iii) x3 − 1 over Z/5Z (het lichaam met 5 elementen); (iv) x5 − x over Z/5Z.

Huiswerkopgaven IX

♠ Huiswerk IX-1. Het karakteristieke polynoom van een vierkante matrix M ∈ M n×n (K) over een lichaam K is het polynoom det(xIn − M ) ∈ K[x]. (i) Bepaal het karakteristieke polynoom voor de matrix   0 1 0 A = 0 0 1. 2 −5 4

(ii) Bepaal de eigenwaarden van A over het lichaam Q. (iii) Bepaal bij elk van de eigenwaarden λ van A een basis voor de deelruimte van alle eigenvectoren bij de eigenwaarde λ, dus met A · v = λ · v. (iv) Is de matrix A diagonaliseerbaar over Q? (v) Vat de matrix A nu op als een element van M3×3 (F2 ) door de coëfficiënten te reduceren modulo 2. Herhaal de vragen voor de matrix A¯ die je zo krijgt, met Q vervangen door F2 .

♠ Huiswerk IX-2. Laat V de vectorruimte Q[x](2) van rationale polynomen van graad ten hoogste 2 zijn. Definieer de transformatie φ van V door φ(f (x)) = f (x)+xf 0 (x)+f 0 (x), waar f (x) in V is en f 0 (x) de afgeleide van f is. (i) Kies een basis B voor V en bepaal MφB . (ii) Bepaal het karakteristieke polynoom van φ. (iii) Bepaal alle eigenwaarden van φ. (iv) Bepaal bij elke eigenwaarde λ van φ de eigenruimte Eλ . (v) Laat zien dat φ diagonaliseerbaar is, en bepaal C zodanig dat C −1 · MφB · C een diagonaalmatrix is. ♠ Huiswerk IX-3. Laat K een lichaam zijn, en n ≥ 1. Een scalaire n × n matrix is een matrix van de vorm d · In , voor een d ∈ K (dus een diagonaalmatrix waarvan alle diagonaalelementen hetzelfde zijn). (i) Laat zien dat de enige matrix die geconjugeerd is met de scalaire matrix d · I n de matrix d · In zelf is. (ii) Bewijs dat een diagonaliseerbare matrix die precies 1 eigenwaarde heeft een scalaire matrix is. (iii) Bewijs dat de matrix 1 1 0 1 niet diagonaliseerbaar is.

Huiswerkopgaven X

♠ Huiswerk X-1. Gegeven zijn twee lineaire transformaties van Q4 , ten opzichte van de standaardbasis bepaald door de matrices 2 − 32 1 0 2 A= 0 − 12 0 1 

3 2

− 23 − 21

−1

 3 −1  , −1 −1

2 − 23 0 0 B= 0 −1 0 1 

3 2

 3 −1 0  . 0 0 −1 −1

(i) Bepaal van de transformaties behorende bij A en bij B alle eigenwaarden en de bijbehorende eigenruimten. (ii) Gebruik Stelling 3.2.14 uit het dictaat om te bepalen of A en B diagonaliseerbaar zijn of niet. ♠ Huiswerk X-2. Laat V de vectorruimte C4 zijn, en T de lineaire transformatie van V gegeven door     a 2a − b b  a+b  T = . c c−d d c+d (i) Vindt twee T -invariante deelruimtes U1 , U2 van V van dimensie 2. (ii) Geef de matrix M van T ten opzichte van de basis die bestaat uit de vereniging van bases voor U1 en U2 . (iii) Bepaal het karakteristieke polynoom pT . (iv) Is T diagonaliseerbaar? (v) Laat zien dat pT (M ) = 0. (vi) Gebruik de methode van Toepassing 2.3.5 om M 25 te bepalen. ♠ Huiswerk X-3. [ Toepassing: Markov keten ] In een peiling heeft 25 van de 30 ondervraagde stadsbewoners aangegeven komend jaar in de stad te blijven, terwijl de overige 5 naar het platteland willen verhuizen. Van de 30 ondervraagde plattelandsbewoners heeft maar 1 aangegeven naar de stad te willen verhuizen in het komende jaar. Dit resultaat kan in deze matrix worden samengevat: 25 1 30 . P = 30 29 5 30

30

(i) Aangenomen dat de steekproeven helemaal representatief zijn en mensen doen wat ze zeggen te willen, hoeveel mensen wonen er dan na een jaar op het platteland en hoeveel in de stad als dat er aanvankelijk allebei 30 duizend zijn? (ii) Aangenomen dat de voorkeuren niet veranderen in de loop der tijd, hoe is de verdeling dan na 2 jaar, en na 10? (Een formule volstaat!) (iii) We willen, onder dezelfde aannamen, uitrekenen of, en zo ja, hoe, de bevolkingsverdeling stabiliseert: daartoe bepalen we de limiet P ∞ als volgt: laat zien dat P diagonaliseerbaar is, en bepaal een matrix Q zodanig dat Q · P · Q−1 = D een diagonaalmatrix is. Laat zien dat D ∞ bestaat en bepaal daaruit P ∞ . (iv) Hoe zal (onder de gegeven aannamen) de verdeling van bewoners over stad en platteland zijn? Hoe hangt dit af van de oorspronkelijke verdeling?

Huiswerkopgaven XI

♠ Huiswerk XI-1. In de volgende onderdelen is steeds T een lineaire transformatie van de K-vectorruimte V , en zijn U1 en U2 lineaire deelruimten van V die invariant zijn onder T . Geef voor elk van de beweringen een bewijs of een tegenvoorbeeld. (i) U1 ∩ U2 is een T -invariante lineaire deelruimte van V ; (ii) U1 ∪ U2 is een T -invariante lineaire deelruimte van V ; (iii) U1 + U2 is een T -invariante lineaire deelruimte van V . ♠ Huiswerk XI-2. Laat T de lineaire transformatie van Q4 zijn bepaald door:     a+b a b b−c T = . a+c c a+d d Voor een vector v ∈ V is Tv de deelruimte van Q4 opgespannen door v, T v, T 2 v, . . . (i) Bepaal de matrix M van T ten opzichte van de standaardbasis van Q4 . (ii) Bepaal de ruimte Tu als u de eerste standaardbasisvector e1 is, door u, T u, T 2u enzovoorts te bepalen totdat je een afhankelijkheid vindt van T k u met de voorgaande T i u; bepaal ook het karakteristieke polynoom pT |Tu van de beperking van T tot Tu (vgl. Voorbeeld 3.3.4.). (iii) Doe hetzelfde als u de tweede basisvector e2 is, en idem voor de vierde basisvector e4 . (iv) Volgens Lemma 3.2.13 delen de gevonden polynomen pT |Tu het karakteristieke polynom pT van T ; bepaal hieruit pT . (v) Bepaal pT ook op de gebruikelijke wijze direkt. (vi) Is T diagonaliseerbaar? ♠ Huiswerk XI-3. Laat K een lichaam zijn, en n ≥ 1. Laat V de vectorruimte Mn×n (K) van n × n matrices over K zijn. Zij T de afbeelding die aan een matrix M ∈ Mn×n (K) diens getransponeerde M t toevoegt. (i) Laat zien dat T een lineaire afbeelding van V naar zichzelf is. (ii) Laat zien dat 1 en −1 de enige eigenwaarden van T zijn. (iii) Beschrijf de eigenruimten E1 en E−1 van T . (iv) Bepaal de dimensie van E1 en E−1 als n = 3 en K = Q; is T diagonaliseerbaar in dit geval? (v) Dezelfde vragen als in (iv) voor n = 3 en K = F2 .

Huiswerkopgaven XII

♠ Huiswerk XII-1. In deze opgave schrijven we elementen van Q2 als rijvectoren. Zijn de onderstaande afbeeldingen van Q2 × Q2 naar Q bilineair? Zo ja, laat dat zien door de Grammatrix ten opzichte van de standaardbasis te geven; zo nee, geef een voorbeeld waaruit dat blijkt. (i) A((a1 , a2 ), (b1 , b2 )) = a21 b21 + a2 b2 (ii) B((a1 , a2 ), (b1 , b2 )) = a1 b1 + a2 b1 + a1 b2 + a2 b2 + 1 (iii) C((a1 , a2 ), (b1 , b2 )) = a1 + b1 + a2 b2 (iv) D((a1 , a2 ), (b1 , b2 )) = a1 b1 − a2 b2 + a1 a2 − b1 b2 (v) E((a1 , a2 ), (b1 , b2 )) = a1 b1 . (vi) F ((a1 , a2 ), (b1 , b2 )) = (a1 + a2 )(b1 + b2 ). 0 1 de matrix van een bilineaire vorm voor Q2 . ♠ Huiswerk XII-2. Zij M = 1 0 (i) Geef de bilineaire vorm B die bij M hoort. (ii) Laat zien dat M equivalent is met een diagonaalmatrix D met behulp van de methode gesuggereerd in Voorbeeld 4.1.12. (Het is niet nodig om het Algoritme uit 4.1.13 te gebruiken!) ♠ Huiswerk XII-3. Laat B de bilineaire vorm op Q2 zijn die aan vectoren v, w ∈ Q2 met coordinaten v1 , v2 , w1 , w2 ten opzichte van de standaardbasis toevoegt B(v, w) = 2v1 w1 − v1 w2 + v2 w1 − 3v2 w2 . (i) Bepaal de matrix MB voor B ten opzichte van de standaardbasis. −1 1 C } door MBC te , (ii) Bepaal MB voor B ten opzichte van de basis C = { 1 1 schrijven als ΦT MB Φ voor een basistransformatie Φ. (iii) Bepaal MBC ook rechtstreeks door B(ci , cj ) uit te rekenen, waar ci , cj ∈ C. ♠ Huiswerk XII-4. In deze opgave is AT de getransponeerde van de matrix A. (i) Bewijs dat voor alle 2 × 2 matrices A en B geldt: (A · B)T = B T · AT . (ii) Gebruik dat (A · B)T = B T · AT voor alle vierkante matrices A, B geldt om te laten zien dat (A−1 )T = (AT )−1 . (iii) Laat zien dat A + AT een symmetrische matrix is, voor elke vierkante matrix A. (iv) Bewijs dat als de vierkante matrix A equivalent is met een diagonaalmatrix, A een symmetrische matrix is.

Huiswerkopgaven XIII

♠ Huiswerk XIII-1. Ten opzichte van de standaardbasis e1 , e2 , e3 van R3 zijn de bilineaire vormen B en C gedefinieerd door B(a1 e1 + a2 e2 + a3 e3 , b1 e1 + b2 e2 + b3 e3 ) = a1 b2 + a1 b3 + a2 b1 + a2 b3 + a3 b1 + a3 b2 , en C(a1 e1 + a2 e2 + a3 e3 , b1 e1 + b2 e2 + b3 e3 ) = a1 b1 + a1 b2 − a1 b3 + a2 b1 + a2 b3 − a3 b1 + a3 b2 − 3a3 b3 . (i) Laat zien dat B en C allebei symmetrisch zijn. (ii) Bepaal de Grammatrix van B en die van C. (iii) Gebruik het algoritme op blz. 57 van het diktaat om bilineaire vormen B0 en C0 te vinden waarvan de Grammatrix een diagonaalmatrix en waarvoor geldt dat B 0 ∼ B en C0 ∼ C. (iv) Is B ∼ C? (v) Bepaal de bij C behorende kwadratische vorm Q en bepaal hiervoor een ‘diagonaalvorm’ zoals in Voorbeeld 4.2.7. (vi) Doe hetzelfde voor de kwadratische vorm die bij B hoort; je kunt hiervoor kijken naar de manier je B0 uit B verkreeg in (iii). ♠ Huiswerk XIII-2. [ Het meetkundige en het rekenkundige gemiddelde ] √ ele getallen x en y op twee (i) Bewijs de ongelijkheid xy ≤ x+y 2 voor niet-negatieve re¨ manieren: rechtstreeks, door beide zijden te kwadrateren, behulp van de √ enmet √ x y en √ . ongelijkheid van Cauchy-Schwarz voor de vectoren √ y x (ii) Veronderstel dat je weet dat voor alle niet-negatieve reële getallen x1 , x2 , . . . , xk geldt: √ x1 + x 2 + · · · + x k k . x 1 x2 · · · x k ≤ k Bewijs dan dat ook voor alle niet-negatieve reële getallen y1 , y2 , . . . , y2k geldt √

2k

y1 y2 · · · y2k ≤

y1 + y2 + · · · + y2k , 2k

y2k−1 +y2k 2 en (i) te gebruiken). (door te schrijven x1 = y1 +y 2 , . . . , xk = 2 (iii) Veronderstel weer dat je weet dat voor alle niet-negatieve reële x1 , x2 , . . . , xk geldt:

√ k

x 1 x2 · · · x k ≤

x1 + x 2 + · · · + x k . k

Laat zien dat dan volgt dat voor alle niet-negatieve reële getallen x1 , x2 , . . . , xk−1 geldt dat x1 + x2 + · · · + xk−1 √ k−1 x1 x2 · · · xk−1 ≤ , k−1 x +x +···+x

(door xk = 1 2k−1 k−1 te nemen). De onderdelen (i), (ii) en (iii) laten zien dat voor alle n niet-negatieve reële getallen √ x1 , . . . , xn geldt dat het meetkundig gemiddelde n x1 x2 · · · xn ten hoogste gelijk is aan het x1 +x2 +···+xn rekenkundig gemiddelde . n (iv) Laat zien dat onder alle rechthoeken met een omtrek van 20 cm het vierkant de grootste oppervlakte heeft. (v) Laat zien dat onder alle rechthoekige blokken met een inhoud van 8 cm3 de kubus de kleinste oppervlakte heeft.

Huiswerkopgaven XIV

♠ Huiswerk XIV-1. Met M t geven we de getransponeerde van een matrix M aan, met z¯ de complex geconjugeerde van een complex getal z. (i) Laat zien dat voor een Hermitese vorm H op een complexe vectorruimte V voor elk drietal vectoren v, w1 en w2 uit V en elke λ ∈ C geldt dat H(v, w1 + w2 ) = ¯ H(v, w1 ) + H(v, w2 ) en H(v, λw1 ) = λH(v, w1 ). (ii) Bewijs dat een complexe n×n matrix M unitair is dan en slechts dan als de kolommen een orthonormaal stelsel vormen (met betrekking tot het standaard-inproduct). (iii) Laat zien dat voor n×n matrices M, N geldt dat (M +N )t = M t +N t en (M ·N )t = N t M t (dat laatste door de coëfficiënten op positie i, j links en rechts te vergelijken). (iv) Veronderstel dat M en N twee Hermitese n × n matrices zijn. Laat zien dat niet noodzakelijk M · N Hermites is maar wel M · N + N · M . ♠ Huiswerk XIV-2. (i) Laat zien dat een n × n reële matrix orthogonaal is dan en slechts dan als Q−1 = Qt (de inverse is de getransponeerde) en dat daaruit volgt dat ook de rijen van een orthogonale matrix een orthonormaal stelsel vormen. (ii) Bewijs dat de determinant van een orthogonale matrix ±1 is. (iii) Bewijs dat alle eigenwaarden van een orthogonale matrix ±1 zijn. (iv) Bewijs dat als Q, R orthogonale matrices zijn, ook Q−1 en Q·R orthogonale matrices zijn. ♠ Huiswerk XIV-3. In deze opgave beschouwen we orthogonale transformaties van R2 . (i) Geef de matrix (ten opzichte van de standaardbasis) behorende bij de lineaire transformatie van V die de draaiing over een hoek φ geeft (door de beelden van de standaardbasisvectoren te beschouwen). (ii) Doe hetzelfde voor de lineaire afbeelding die de spiegeling geeft in de lijn door de oorsprong die een hoek φ met de oorsprong maakt. (iii) Bewijs dat een orthogonale 2 × 2 matrix van de vorm x −y x y of y x y −x is, voor reële getalen x, y met x2 + y 2 = 1. (iv) Laat zien dat een orthogonale transformatie van de R2 een draaiing of een spiegeling in een lijn is. Hoe kun je aan de determinant de twee gevallen van elkaar onderscheiden (vgl. XIV-2(ii))? (v) Laat ook zien dat je de spiegeling in een lijn kunt schrijven als samenstelling van een spiegeling in de x-as en een draaiing. Over welke hoek?

1 Lichamen en vectorruimten Lichamen Vectorruimten Toepassing: Codes... 13

Recommend Documents