Discrete Wiskunde [version 2 Aug 2010 ed.] [PDF]

Zitiervorschau

DISCRETE WISKUNDE Philippe CARA en Tom DENECKERE 7 februari 2010

Voorwoord Dit zijn nota’s die nuttig kunnen zijn bij het studeren van het vak “Discrete Wiskunde”. Dit vak wordt aan de VUB gedoceerd in het eerste bachelorjaar Wiskunde en Informatica. Voor informatici wordt deze cursus gedoceerd in 39 uur. De wiskundigen volgen slechts 26 uur. Een andere naam voor dit vak is “Discrete Structuren”. Op het examen wordt vooral gepeild naar het begrip van de cursus en de wiskundige technieken die aan de basis liggen. Alle stellingen, lemma’s, gevolgen, . . . moeten gekend zijn, met bewijs. De bewijzen die niet in de cursus staan zou de gemiddelde student zelf moeten kunnen vinden. Er wordt dus verwacht dat deze bewijzen ook gekend zijn. Meer informatie vind je op mijn homepage : http://homepages.vub.ac.be/~pcara Ik verwijs ook naar de cursusfiche voor meer technische informatie. Achteraan deze nota’s vind je ook een bibliografie met referentiewerken die naast deze tekst kunnen geraadpleegd worden. Zij bevatten nog meer voorbeelden en oefeningen. Hierbij wens ik ook de studenten van de 1ste Bachelor Wiskunde van het academiejaar 2005– 2006 te bedanken voor de talrijke verbeteringen die zij aanbrachten in de tekst.

Philippe Cara 7 februari 2010

i

Inhoudsopgave 1 Een beetje brugcursus

1

1.1

Logica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1

1.2

Verzamelingen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2

1.3

Kwantoren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2

1.4

Meerdere kwantoren en negaties . . . . . . . . . . . . . . . . . . . . . . . . . .

3

1.5

Deelverzamelingen en gelijke verzamelingen . . . . . . . . . . . . . . . . . . .

3

1.6

Bewerkingen met verzamelingen . . . . . . . . . . . . . . . . . . . . . . . . . .

4

1.7

Oneindige unies en doorsneden . . . . . . . . . . . . . . . . . . . . . . . . . . .

4

1.8

Cartesisch product . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

1.9

Relaties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

1.10 Functies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6

1.11 Beeld en invers beeld . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

1.12 Ge¨ınduceerde functies, restrictie en corestrictie . . . . . . . . . . . . . . . . . .

7

1.13 Injecties en surjecties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8

1.14 De samenstelling van functies . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9

1.15 Inverse functies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

10

1.16 Oefeningen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

11

2 Stelsels en matrices

15

2.1

Stelsels van lineaire vergelijkingen . . . . . . . . . . . . . . . . . . . . . . . . .

15

2.2

Matrixnotatie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

16

2.3

Matrices in echelonvorm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

18

2.4

Oplossen van stelsels met de spilmethode . . . . . . . . . . . . . . . . . . . . .

21

2.5

Intermezzo: vectoren en vectorruimten . . . . . . . . . . . . . . . . . . . . . .

23

2.6

Matrixrekenen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

31

2.7

Lineaire afbeeldingen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

32

2.8

Enkele voorbeelden van lineaire afbeeldingen . . . . . . . . . . . . . . . . . . .

36

ii

INHOUDSOPGAVE 2.9

iii

Bepalen van de inverse van een matrix . . . . . . . . . . . . . . . . . . . . . . .

38

2.10 Oefeningen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

40

3 Eenvoudige principes van discrete wiskunde

49

3.1

De duiventil . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

49

3.2

Eenvoudige teltechnieken . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

51

3.2.1

Tellen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

51

3.2.2

Somprincipe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

51

Product . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

52

3.3.1

Dubbeltellen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

52

3.3.2

Woorden . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

53

3.3.3

Injecties tellen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

54

3.3.4

Bijecties tellen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

54

3.3.5

Deelverzamelingen tellen . . . . . . . . . . . . . . . . . . . . . . . . . .

55

3.3.6

De driehoek van Pascal . . . . . . . . . . . . . . . . . . . . . . . . . . .

56

3.3.7

Herhalingscombinaties . . . . . . . . . . . . . . . . . . . . . . . . . . . .

57

3.4

Het binomium van Newton . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

57

3.5

Inclusie en exclusie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

59

3.6

Oefeningen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

60

3.3

4 Gehele getallen 4.1

66

Gekende eigenschappen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

66

4.1.1

Andere voorbeelden van ringen . . . . . . . . . . . . . . . . . . . . . .

67

4.2

Welorde . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

68

4.3

Bewijs per inductie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

69

4.4

Quoti¨ent en rest . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

70

4.5

Grootste gemene deler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

71

4.6

Priemgetallen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

74

4.7

De ϕ-functie van Euler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

77

4.8

Congruenties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

80

4.9

Equivalentierelaties en partities . . . . . . . . . . . . . . . . . . . . . . . . . . .

81

4.10 Modulair rekenen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

83

4.11 De Chinese reststelling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

86

4.12 Public key cryptography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

87

4.13 Oefeningen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

89

INHOUDSOPGAVE

iv

5 Inleiding tot de graffentheorie

96

5.1

Definities en terminologie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

96

5.2

Belangrijke voorbeelden . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

97

5.3

Verdere definities en eigenschappen . . . . . . . . . . . . . . . . . . . . . . . .

98

5.4

Eulerpaden . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

99

5.5

Hamiltonpaden . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102

5.6

Gerichte graffen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103

5.7

Isomorfismen tussen graffen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106

5.8

Bomen en bossen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107

5.9

Opspannende bomen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110

5.10 Tellen van opspannende bomen . . . . . . . . . . . . . . . . . . . . . . . . . . . 112 5.10.1 Matrices als voorstelling van graffen . . . . . . . . . . . . . . . . . . . . 112 5.10.2 Het aantal opspannende bomen in een gegeven graf . . . . . . . . . . 112 5.11 Bipartiete graffen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 5.12 Koppelingen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116 5.13 Toewijzingen en het lessenroosterprobleem . . . . . . . . . . . . . . . . . . . . 118 5.14 Planaire graffen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 5.14.1 Platonische lichamen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124 5.15 Het kleuren van planaire graffen . . . . . . . . . . . . . . . . . . . . . . . . . . 125 5.16 Oefeningen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128 6 Genererende functies

136

6.1

Voorbeelden en definitie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136

6.2

Veralgemeende binomiaalco¨effici¨enten . . . . . . . . . . . . . . . . . . . . . . . 138

6.3

Partities van natuurlijke getallen . . . . . . . . . . . . . . . . . . . . . . . . . . 140 6.3.1

Young tableaus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142

6.4

Beroemde genererende functies . . . . . . . . . . . . . . . . . . . . . . . . . . . 142

6.5

Oefeningen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143

7 Recurrentievergelijkingen

146

7.1

Homogene eerste orde lineaire recurrentievergelijkingen . . . . . . . . . . . . 146

7.2

Homogene tweede orde lineaire recurrentievergelijkingen . . . . . . . . . . . 148 7.2.1

Twee re¨ele wortels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148

7.2.2

Twee complex toegevoegde wortels . . . . . . . . . . . . . . . . . . . . 151

7.2.3

E´en re¨ele wortel met multipliciteit twee . . . . . . . . . . . . . . . . . . 152

INHOUDSOPGAVE

v

7.3

Niet-homogene recurrentievergelijkingen . . . . . . . . . . . . . . . . . . . . . 152

7.4

Beroemde particuliere oplossingen . . . . . . . . . . . . . . . . . . . . . . . . . 153

7.5

Een methode met genererende functies . . . . . . . . . . . . . . . . . . . . . . 154

7.6

Oefeningen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155

8 Aanvullingen 8.1

8.2

157

Booleaanse algebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157 8.1.1

Eigenschappen van de Booleaanse bewerkingen . . . . . . . . . . . . . 159

8.1.2

Dualiteitsprincipe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160

8.1.3

Abstracte definite van een Booleaanse algebra . . . . . . . . . . . . . . 160

8.1.4

Voorschriften voor Booleaanse afbeeldingen . . . . . . . . . . . . . . . 161

8.1.5

Schakelingenalgebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162

8.1.6

Reductie van Booleaanse voorschriften . . . . . . . . . . . . . . . . . . 164

Paden in graffen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166 8.2.1

Kortste paden in gewogen graffen . . . . . . . . . . . . . . . . . . . . . 166

8.2.2

Stromen in gewogen gerichte graffen . . . . . . . . . . . . . . . . . . . 168

8.2.3

Enkele toepassingen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178

8.3

Compressie: Huffman en Lempel-Ziv . . . . . . . . . . . . . . . . . . . . . . . 179

8.4

Oefeningen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181

A De stelling van Cauchy–Binet

184

A.1 Herhaling en notatie voor determinanten . . . . . . . . . . . . . . . . . . . . . 184 A.2 De stelling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185 A.3 De helden van dit verhaal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187 B De complexe getallen

188

B.1 Definities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188 B.2 Meetkundige interpretatie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189 B.3 De complexe exponenti¨ele functie . . . . . . . . . . . . . . . . . . . . . . . . . 190 B.4 De logaritmische functie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191 B.5 De complexe trigonometrische functies . . . . . . . . . . . . . . . . . . . . . . 191 B.6 De complexe n-demachtswortel . . . . . . . . . . . . . . . . . . . . . . . . . . . 192 B.7 Complexe veeltermen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193 Bibliografie

196

Index

197

Hoofdstuk 1

Een beetje brugcursus Dit hoofdstuk is gebaseerd op de brugcursus “Wiskunde I” (VUB uitgaven) en hoofdstuk 0 van de cursus “Meetkunde en Lineaire Algebra” van Prof. Kieboom.

1.1 Logica De wiskunde is opgebouwd uit “logische redeneringen”. Deze redeneringen worden in het algemeen bestudeerd in de wiskundige discipline die “logica” heet. Logica komt uitgebreid aan bod in de cursus “Grondslagen van de informatica I” (Prof. De Troyer). Wij zullen de taal en notatie van de zogenaamde predikatenlogica gebruiken om redeneringen neer te schrijven. We herhalen hier enkele notaties en begrippen: • de implicatie: p ñ q (“Als p dan q”). Voorbeeld. “x is deelbaar door 10 ñ x is even”. • de negatie:

p.

Voorbeeld. “Het regent niet”. • de contrapositie van de implicatie: p belangrijk!

ñ q is equivalent met

q

ñ

p. Dit is zeer

Voorbeeld. Om te bewijzen dat “n2 even ñ n even” is het gemakkelijker te bewijzen dat “n

oneven ñ n2 oneven”.

• de equivalentie: p  q (“p is equivalent met q”). p qq ^ pq ñ pq of p p ñ qq ^ p p ñ qq



q is equivalent met p p

Voorbeeld. “n2 even  n even”. • negatie van de implicatie:

p p ñ qq is equivalent met p ^

q.

Opmerking. De negatie van de implicatie is niet hetzelfde als contrapositie! 1

ñ

HOOFDSTUK 1. EEN BEETJE BRUGCURSUS

2

1.2 Verzamelingen Een fundamenteel begrip in de wiskunde is verzameling. Het is echter moeilijk dit begrip precies te defini¨eren. Verzamelingen laten toe alle (wiskundige) objecten met dezelfde kenmerken te groeperen of te verzamelen. Voorbeeld. De verzameling priemgetallen groepeert alle positieve gehele getallen die juist twee verschillende delers bezitten. Een object uit een gegeven verzameling heet een element. We noteren verzamelingen meestal met Latijnse hoofdletters: A, B, C, . . . , X, Y, Z. Sommige verzamelingen verdienen een speciaal symbool:

 t0, 1, 2, . . .u: de natuurlijke getallen Z  t. . . ,
3,
2,
1, 0, 1, 2, . . .u: de gehele getallen Q  t ba a, b P Z ^ b  0u: de rationale getallen

• N • •

~

• R: de re¨ele getallen • C

 ta

bi ~ a, b

P Ru: de complexe getallen

Merk op: Een verzameling kan gedefinieerd worden door haar elementen op te sommen tussen accolades. We kunnen ook een algemene beschrijving geven van haar elementen zoals in het voorbeeld van Q. Hierbij moet je het verticale streepje “ ~ ” lezen als “waarvoor geldt”. Het symbool “P” betekent “is element van” of “behoort tot”. Meer voorbeelden:

 tx P R x   0u R  t x P R x ¥ 0u R0  t x P R x ¡ 0u

• R0 • •

~

~ ~

De lege verzameling ∅ bevat geen elementen. px P Aq korten we af tot x R A, “x behoort niet tot A”.

1.3 Kwantoren Sommige uitspraken of eigenschappen zijn geldig voor alle objecten in een gegeven verzameling. Om dit te noteren gebruiken we de kwantor “voor alle”: . Voorbeeld.  x P R : x2

¥ 0.

Het dubbelpunt “:” betekent in een logische uitspraak “geldt”. Er is ook een kwantor “er bestaat” indien men wil zeggen dat een eigenschap geldt voor minstens e´e´n element in een gegeven verzameling. Voorbeeld. D x P R : x2

 x.

HOOFDSTUK 1. EEN BEETJE BRUGCURSUS

3

Soms wil men benadrukken dat er slechts e´e´n element bestaat met de gegeven eigenschap. Voorbeeld. D! x P R0 : x2  x.

1.4 Meerdere kwantoren en negaties De volgorde van kwantoren heeft belang! Bijvoorbeeld

x P R : Dy P R is waar, terwijl

: x2

y

D y P R :  x P R : x2  y

onwaar is. Opmerking. De letters die we gebruiken als variabelen hebben uiteraard geen belang:

β P R : Db P R

: β2

b

is dezelfde uitspraak als de eerste, maar anders geschreven. Negaties van uitspraken zijn zeer belangrijk. Denk bijvoorbeeld aan het bewijs door contrapositie. De negatie van  x P X : p p x q.

x P

X : pp xq is

Dx P

X :

pp xq en de negatie van

Dx P

X : pp xq is

Voorbeeld. De negatie van

 ε P R0 : D δ P R0 :  x P X : p|x
a|   δq ñ p| f pxq
f paq|   εq is

D ε P R0 :  δ P R0 : D x P X : p|x
a|   δq ^ p| f pxq
f paq| ¥ εq

1.5 Deelverzamelingen en gelijke verzamelingen Indien elk element van een verzameling A ook behoort tot een verzameling B, zeggen we dat A een deelverzameling is van B of dat B de verzameling A omvat. Symbolisch:

A € B  a P A : a P B

Voor A € B schrijven we ook B  A. We hebben steeds B deelverzamelingen heten echte deelverzamelingen van B. Voorbeelden. • t1, 2, 3u € N

€ Z € Q € R € C.

€

B en ∅

€

B. Alle andere

HOOFDSTUK 1. EEN BEETJE BRUGCURSUS • Z

4

‚R

Twee verzamelingen A en B zijn gelijk indien ze dezelfde elementen hebben. Dit is het geval als en slechts als p A € Bq ^ p B € Aq. We noteren (uiteraard) A  B. Gevolg: A  B indien p A ‚ Bq _ pB ‚ Aq, d.w.z. pD a P A : a R Bq _ pD b P B : b R Aq. De verzameling van alle deelverzamelingen van een gegeven verzameling X noteren we P pX q. Er geldt dus P pX q  tS verzameling ~ S € X u

1.6 Bewerkingen met verzamelingen De doorsnede van A en B is de verzameling A X B  t x P A ~ x P Bu. Twee verzamelingen A en B heten disjunct indien A X B  ∅, d.w.z. ze hebben geen elementen gemeenschappelijk.

De unie van A en B is A Y B  t x ~ p x P Aq _ p x verzameling Az B  t x ~ p x P Aq ^ p x R Bqu.

 t1, 2, 3u en B Az B  t1u en Bz A  t4, 5u

Voorbeeld. Stel A

 t2, 3, 4, 5u.

P Bqu.

Het verschil van A en B is de

Dan geldt: A X B

 t2, 3u, A Y B  t1, 2, 3, 4, 5u,

Als A € B, dan heet Bz A het complement van A t.o.v. B. Soms speelt een wiskundige theorie zich volledig af in een gegeven verzameling U. In dat geval worden alle complementen berekend t.o.v. U (tenzij anders vermeld natuurlijk). Voor A € U noteert men dan kort Ac , A¯ of A A voor het complement U z A. De verzameling U noemt men het universum van de theorie.

1.7 Oneindige unies en doorsneden Zij I een verzameling. Onderstel dat voor elke i P I een verzameling Ai gegeven is. Zo bekomen we een verzameling A  t Ai ~ i P I u van verzamelingen ge¨ındexeerd door I.

 t3, 4, 5, 6, 7u en Ai  t1, 2, 3, . . . , iu. Dan is A3  t1, 2, 3u, A4  t1, 2, 3, 4u enz.  N0, Bj  r0, 1j s, een gesloten interval in R. Dan is B1  r0, 1s, B2  r0, 12 s enz.

Voorbeeld. Stel I Stel J

De doorsnede van alle verzamelingen ge¨ındexeerd door I defini¨eren we als

£ A  £ A  tx P

i

~

 i P I : x P Ai u

i I

en analoog defini¨eren we de unie

¤ A  ¤ A  tx P

i I

i

~

D i P I : x P Ai u.

HOOFDSTUK 1. EEN BEETJE BRUGCURSUS

5

Voorbeeld. We keren terug naar de vorige voorbeelden. Er geldt:

¤ P

Ai

 A7

,

i I

¤ P

£ P

Ai

 A3

Bj

 t0u.

i I

Bj

 r0, 1s

j J

,

£ P

j J

1.8 Cartesisch product Zijn A, B twee verzamelingen. Het cartesisch product van A en B is de verzameling A  B : tpa, bq ~ a P A, b P Bu De elementen van A  B heten koppels. Als pa, bq, pc, dq P A  B dan geldt pa, bq  pc, dq ðñ pa  cq ^ pb  dq. Als a  b geldt pa, bq  pb, aq. In het algemeen zijn dus A  B en B  A verschillend. Als A, B € U dan geldt A  B € U  U en niet A  B € U! Als A eindig is (d.w.z. A bevat een eindig aantal elementen) noteren we het aantal elementen in A met | A| of #A. Als A en B eindig zijn geldt | A  B|  | A|  | B|. Voorbeelden. • Stel A  t2, 3u en B  t4, 5, 6u. Vul dan zelf aan: – AB  ...

– BA  ...

• Stel A  r1, 3s en B  r1, 2s. Dan geldt A  B € R  R  R2 .

Notatie. A  A noteren we kort A2 . Ook het Cartesisch product A  A      A van n keer dezelfde verzameling schrijven we An .

1.9 Relaties Een relatie van een verzameling A naar een verzameling B is per definitie een deelverzameling R van het cartesisch product A  B.

Notatie. als pa, bq P R, schrijven we aRb. Voorbeeld. Beschouw de verzameling A A. Dan is: R

 t1, 2, 3, 4u en de relatie “is kleiner dan of gelijk aan” op

 tpa, bq P A  A a ¤ bu  tp1, 1q, p1, 2q, p1, 3q, p1, 4q, p2, 2q, p2, 3q, p2, 4q, p3, 3q, p3, 4q, p4, 4qu ~

HOOFDSTUK 1. EEN BEETJE BRUGCURSUS

6

De inverse relatie R
1 van R is per definitie R
1 : tpb, aq ~ pa, bq

P R u.

Dit is een relatie van B naar A. Voorbeeld. Terugkerend naar het vorige voorbeeld geldt: R
1

 tp1, 1q, p2, 1q, p3, 1q, p4, 1q, p2, 2q, p3, 2q, p4, 2q, p3, 3q, p4, 3q, p4, 4qu.

1.10 Functies Zijn A, B verzamelingen. Een functie van A naar B is een relatie van A naar B waarbij elk element van A precies e´ e´ n keer voorkomt als eerste component van een koppel in de relatie. De verzameling A heet het domein van de functie en B is het codomein. Meestal noteren we functies met kleine letters en vermelden we duidelijk domein en codomein. Als f € A  B een functie is, noteren we f : A ÝÑ B.

 t1, 2, 3u en B  ta, b, c, du, dan is f  tp1, aq, p2, bq, p3, bqu een functie en R  tp1, aq, p2, bq, p2, aq, p3, dqu is een relatie maar geen functie.

Voorbeeld. Als A

Het woord afbeelding is een synoniem voor functie.

Zij f : A ÝÑ B een functie. Indien pa, bq P f noteren we f paq  b. Het element b P B heet beeld van a door f en a heet een origineel van b voor f . We zeggen ook dat f het element a op het element b stuurt, notatie: a ÞÑ b. Merk op: niet alle elementen van het codomein hebben een origineel, maar elk element van het domein heeft wel een beeld. Voor vele functies bestaat er een “formule” om het beeld van een willekeurig element van het domein te berekenen. Dit heet het functievoorschrift. De volledige notatie voor een functie wordt dan: f : A ÝÑ B : a ÞÝÑ f paq

waarbij f paq het functievoorschrift voorstelt. Voorbeelden. • f : R ÝÑ R : x • g: R

ÞÑ x2 "

5

ÝÑ R : x ÞÑ 5x
2x

als als

x x

¥0  0

Opmerking. Een functie wordt dus gedefinieerd door drie gegevens: domein, codomein en functievoorschrift. Deze gegevens zijn alle even belangrijk!

HOOFDSTUK 1. EEN BEETJE BRUGCURSUS

7

1.11 Beeld en invers beeld Voor een functie f : A ÝÑ B en S € A defini¨eren we het beeld van S door f als f pS q :

t f p sq s P S u : tb P B D s P S, f psq  bu ~

~

Dus geldt zeker f pSq € B

f p Aq, het beeld van het hele domein van f , noemen we het beeld van f . We noteren dit soms ook Im f . Im f is dus een deel van het codomein. Dan is f pr
1, 2sq  r0, 4s en Im f  R . Uit dit voorbeeld leren we dat Im f dus in het algemeen niet gelijk is aan het codomein van f . Verwar dus niet beeld en codomein!

Voorbeeld. Zij f : R

ÝÑ R : x ÞÑ x2.

Nog steeds voor f : A als

ÝÑ B maar nu T € B, defini¨eren we het invers beeld van T onder f f
1 pT q : ta

P A f paq P Tu. ~

Merk op dat f
1 pT q een notatie is en niet impliceert dat er voor f een inverse functie bestaat. Als T een singleton tbu is, schrijven we f
1 pbq i.p.v. f
1 ptbuq.

Voorbeeld. Met f zoals in het vorige voorbeeld hebben we: f
1 p4q

 t
2, 2u, f
1 p
1q  ∅ en
1
1 f p f pr0, 1sqq  f pr0, 1sq  r
1, 1s. In het algemeen geldt:  S € A : f
1 p f pSqq  S en, zoals het voorbeeld toont, niet f
1 p f pSqq  S. We bewijzen dit even.

Bewijs. Zij f : A ÝÑ B een functie en S € A. We moeten bewijzen:

 s P S : s P f
1 p f pSqq.

Maar dit is equivalent met

 s P S : f psq P f pSq  t f ptq t P Su, ~

wat duidelijk voldaan is. Je zal andere gelijkaardige eigenschappen in de oefeningen bewijzen.

1.12 Ge¨ınduceerde functies, restrictie en corestrictie Als een functie f : A ÝÑ B gegeven is, kan je gemakkelijk een functie van A  A naar B  B defini¨eren. We beelden pa, a1 q gewoon af op p f paq, f pa1 qq. Algemeen kan je functies An ÝÑ Bn maken voor alle machten n. Je kan ook een functie maken op de delenverzameling P p Aq van A. Door P p Aq ÝÑ P p Bq : S ÞÝÑ f pSq. We noteren al deze functies afgeleid uit f meestal nog altijd met f en noemen ze de functies door f ge¨ınduceerd op A  A (of op An of op P p Aq).

HOOFDSTUK 1. EEN BEETJE BRUGCURSUS

8

We kunnen ook beslissen om de functie f : A ÝÑ B te bekijken op een deelverzameling X van A. Dan spreken we van de restrictie of beperking van f tot X. We noteren deze functie met f |X . Er geldt dus f |X : X ÝÑ B : x ÞÝÑ f p xq We kunnen ook het codomein van de functie f beperken. Zij Y Dan is de corestrictie van f tot Y de functie

€ B zo´ dat  a P A : f paq P Y.

f |Y : A ÝÑ Y : x ÞÝÑ f p xq

We kunnen natuurlijk ook domein en codomein tegelijk beperken zodat we een functie f |YX : X ÝÑ Y bekomen met voor elke x P X : f |YX p xq  f p xq.

1.13 Injecties en surjecties 1 Definitie. Een functie f : A ÝÑ B heet injectief indien elk element van B hoogstens e´e´n keer voorkomt als tweede component van een koppel in f . Anders gezegd: elk element van B heeft hoogstens e´ e´ n origineel. Nog anders gezegd: indien twee elementen van A hetzelfde beeld hebben, moeten ze gelijk zijn. In symbolen: f : A ÝÑ B is injectief ðñ  a, b P A : p f paq  f pbqq ñ pa  bq.

ÝÑ R : x ÞÑ x2 is niet injectief. Immers 12  p
1q2 maar 1 
1. Anderzijds is ÝÑ R : x ÞÑ x2 wel injectief want a2  b2 ðñ a  b, maar aangezien a, b P R , geldt a  b.

Voorbeeld. f : R g:R

We zien dat we een functie injectief kunnen maken door punten uit het domein weg te laten. De functie g uit het voorbeeld is gewoon de restrictie van f tot R , of f |R . 2 Definitie. Een functie f : A ÝÑ B is surjectief indien Im f

 B.

Anders gezegd: elk element van het codomein heeft minstens e´ e´ n origineel. Symbolisch:  b P B : D a P A : f paq  b. Voorbeeld. g : R

ÝÑ R : x ÞÝÑ x2 is niet surjectief. De corestrictie g|R

is dat wel.

Door het codomein te beperken kan je een functie dus surjectief maken. Een functie die tegelijk surjectief en injectief is, heet bijectief. Een functie is bijectief  b P B : D! a P A : f paq  b. Voorbeeld. h : R

ÝÑ R

:x

ðñ

ÞÝÑ x2 is bijectief.

Een bijectie van een verzameling naar zichzelf heet een permutatie. Een zeer belangrijke permutatie is de identieke permutatie of de identiteit. Deze beeldt elk element af op zichzelf. We noteren de identieke permutatie van een verzameling X als 1X . Er geldt dus  x P X : 1X pxq  x of 1X : X ÝÑ X : x ÞÝÑ x Opmerking. Andere notaties voor de identieke permutatie op X zijn i X , IdX of idX .

HOOFDSTUK 1. EEN BEETJE BRUGCURSUS

9

1.14 De samenstelling van functies Beschouw twee functies f : A ÝÑ B en g : B ÝÑ C, waarbij het domein van g het codomein van f is. Dan kunnen we op elk beeld f paq de functie g toepassen. Zo defini¨eren we een nieuwe functie van A naar C die we g  f noteren (lees “g na f ” omdat we eerst f toepassen en dan g). Dus: g  f : A ÝÑ C : a ÞÑ gp f paqq. g f

A

C

B f p aq

a

gp b q

b

Voorbeeld. Stel f : R ÝÑ R : x ÞÑ x
1 en g : R ÝÑ R : x ÞÑ x2 . Dan zijn: g  f : R ÝÑ R : x ÞÑ gpx
1q  px
1q2 f  g : R ÝÑ R : x ÞÑ x 2
1 f  f : R ÝÑ R : x ÞÑ x
2 g  g : R ÝÑ R : x ÞÑ x 4

We merken op dat f

 g  g  f , dus de volgorde heeft belang.

3 Eigenschap. De samenstelling van functies is associatief: voor elke drie functies A ÝÑ B ÝÑ C f

geldt

g

h ÝÑ D

h  p g  f q  p h  gq  f

Bewijs. Domeinen en codomeinen zijn duidelijk gelijk. Zij a P A, dan

ph  pg  f qqpaq    

gp f paqq

hpp g  f qpaqq hp gp f paqqq

ph  gqp f paqq pph  gq  f qpaq.

HOOFDSTUK 1. EEN BEETJE BRUGCURSUS

10

1.15 Inverse functies Definitie: Zij f : A ÝÑ B een functie. Indien een functie g : B ÝÑ A voldoet aan f

 g  1B en g  f  1A

dan heet g een invers voor f . We zeggen dan ook dat f inverteerbaar is.

Niet alle functies hebben een invers. Een inverse g van f : A ÝÑ B moet een functie zijn van B naar A. Dus moet voor elke b P B precies e´ e´ n beeld gpbq P A voorzien worden. Bovendien moet gelden p f  gqpbq  1B pbq  b. Bijgevolg moet gpbq P f
1 pbq. Opdat g : B ÝÑ A een functie zou zijn is dus nodig dat  b P B : f
1 pbq  ∅. Dit komt erop neer dat f surjectief moet zijn.

Als f : A ÝÑ B surjectief is, zouden we als volgt een inverse g : B ÝÑ A kunnen construeren: voor elke b P B kiezen we een beeld gpbq in f
1 pbq. Maar is zulke g dan een invers van f?

De voorwaarde g  f  1 A dwingt de injectiviteit van f . Inderdaad: als f niet injectief is, bestaan er a  a1 P A met f paq  f pa1 q. Stel b : f paq, dan geldt a, a1 P f
1 pbq. Kiezen we dan als beeld van b door g het element a, dan hebben we gpbq  gp f paqq  p g  f qpaq  1 A paq  a, maar ook gpbq  gp f pa1 qq  p g  f qpa1 q  1 A pa1 q  a1 . Dus a  a1 , wat in tegenspraak is met a  a1 .

Als f een bijectie is, is  b P B : f
1 pbq een singleton. Er is dus geen keuze voor het construeren van de inverse g. De functie g : B ÝÑ A is dan wel degelijk een inverse van f . We hebben bewezen: 4 Stelling. Enkel bijectieve functies hebben een invers. 5 Eigenschap. Een functie heeft hoogstens e´e´n invers. Bewijs. Zij f : A ÝÑ B en zijn g : B ÝÑ A en g1 : B ÝÑ A twee inversen. Dan geldt,  b P B: gp b q

     

gp1B pbqq

 g1 qpbqq pg  f  g1 qpbq pg  f qpg1 pbqq 1 A p g1 pbqq g 1 p b q. gpp f

Vermits de domeinen en codomeinen van g en g1 gelijk zijn, hebben we g  g1 . Nu we weten dat elke inverteerbare functie juist e´ e´ n invers heeft, kunnen we spreken over het invers van een functie f in plaats van over een invers. We noteren de inverse functie f
1 . Verwar dit niet met inverse beelden die voor alle functies gedefinieerd zijn, niet enkel voor bijecties. Voorbeeld. h : R? R

ÝÑ R

:x

ÞÑ

ÝÑ R

x.

: x

ÞÑ x2 is een bijectie.

Haar inverse kennen we goed. Het is h
1 :

HOOFDSTUK 1. EEN BEETJE BRUGCURSUS

11

1.16 Oefeningen 1. # Zij pp xq “x is deelbaar door 10” en qp xq “x is even”. • schrijf pp xq en qp xq met symbolen

• Geef de negatie van pp xq

• Geef de conjunctie van pp xq en qp xq

• Schrijf “qp xq impliceert pp xq”, en de contrapositie ervan • Schrijf de equivalentie van pp xq en qp xq op

Zeg van deze uitspraken of ze waar zijn of niet. 2. G # Stel de waarheidstafel op van de exclusieve of (Xor). Ken je een uitdrukking die equivalent is? 3. # Geef de waarheidstafels van • pp

ñ q q ñ p q ñ pq • q  p p _ qq • rp p ñ qq ^ pq ñ rqs ñ p p ñ rq 4. # Toon aan dat p p _ qq en p ^ q logisch equivalent zijn. Wat kan je zeggen over p p ^ qq en p _ q? 5. # Toon aan dat p  q en p p ñ qq ^ pq ñ pq logisch equivalent zijn. 6. G # Het aantal rijen van een waarheidstabel hangt af van het aantal samenstellende uitspraken. Wat is het verband? 7. # Schrijf de waarheidstafels op voor volgende logische uitspraken en leid er een equivalente vorm voor de uitspraak uit af: • • •

p pq p p ^ qq p p _ qq

•

p p ð qq

•

p p  qq

8. G # Een tautologie (of logische wet) is een uitspraak die steeds waar is. Toon aan dat volgende beweringen tautologie¨en zijn en interpreteer: • • • • •

p p ^ p pqq p _ p pq p p ^ pq  p p p ^ q q  p q ^ pq p p _ pq _ rqq  pp p _ qq _ rq

9. # Is p ñ pq ñ pq logisch equivalent met p p

• • • •

p pq  p p ñ p q ñ pq p ñ p p ñ qq p p ñ q q _ p q ñ pq

ñ qq ñ p?

HOOFDSTUK 1. EEN BEETJE BRUGCURSUS

12

10. # Noteer volgende oefeningen met behulp van kwantoren. Bepaal eventueel of de bewering waar of vals is. Schrijf de negatie van de bewering op met kwantoren en met woorden. (a) “Alle mensen zijn slim.” (b) “Er zijn mensen die groot zijn.” (c) “Er zijn mensen die groot zijn en lang haar hebben.” (d) “Niet alle mensen hebben kort haar.” (e) “Alle wegen leiden naar Rome.” (f) “Voor elke mens geldt: als hij groot is, dan is hij niet klein.” (g) “Een geheel getal is positief.” (h) “Elk natuurlijk getal is even.” (i) “Sommige re¨ele getallen zijn positief.” 11. # Schrijf alle deelverzamelingen van t1, 2, 3u. 12. G # Hoeveel deelverzamelingen heeft een verzameling met 2 elementen? Met 3 elementen? Met n elementen? 13. G # Wanneer behoort een element niet tot A X B? Vul aan: x R A X B  . . . 14. G # analoog: x R A Y B  . . . 15. G # analoog: x R Az B  . . . 16. G # Toon aan dat • B  A  AYB  B  AXB  A • A Y p A X Bq  A

• A X p A Y Bq  A 17. G # Wanneer is x

R ” iP I A i ?

18. G # Geef de betekenis in woorden van de volgende uitspraken. Zeg of ze waar of onwaar zijn. Geef de negatie in symbolen en woorden.

 x P Z, D y P Z : x   y • D x P Z, D y P N : x ¡ y • D x P Z,  y P Z : x   y •  ε ¡ 0, D δ ¡ 0,  x P R : | x
a|   δ ñ | f p xq
f paq|   ε 19. # Zij A  t2, 3u, B  t4, 5, 6u en C  ta, b, c, du. Geef A  B, B  A, A  C, C  B, A2 , C  tau. 20. # Zij A  t1, 2, 3, 4u en beschouw de relatie R: “is kleiner dan of gelijk aan” op A. Geef •

de elementen van R. Geef de inverse relatie van R.

21. G # Zij f : A ÝÑ B een functie en S1 , S2

€ A. Bewijs dat

HOOFDSTUK 1. EEN BEETJE BRUGCURSUS

13

(a) f pS1 Y S2 q  f pS1 q Y f pS2 q

(b) f pS1 X S2 q € f pS1 q X f pS2 q Zoek voorbeelden die dit illustreren. 22. G # Zij f : A ÝÑ B een functie die niet noodzakelijk inverseerbaar is, en S T, T1 , T2 € B. Bewijs dat (a) f
1 pT1 Y T2 q  f
1 pT1 q Y f
1 pT2 q

€

A en

(c) f p f
1 pT qq € T

(b) f
1 pT1 X T2 q  f
1 pT1 q X f
1 pT2 q

(d) f
1 p f pSqq  S

Zoek voorbeelden die dit illustreren.

ðñ b P B : f
1 pbq bevat hoogstens e´ e´ n element.

23. G # Toon aan: f : A ÝÑ B is injectief 24. G # (a) Zij f : A ÝÑ B. Toon aan dat f

 1 A  f  1B  f .

(b) Toon aan dat de samenstelling van 2 injecties opnieuw een injectie is. (c) Toon aan dat de samenstelling van 2 surjecties opnieuw een surjectie is. 25. # Zij f p xq 

?x, gpxq  x{4 en hpxq  4x
8. Zoek het functievoorschrift voor:

(a) h  g  f

(b) h  f

g

(c) g  h  f

?

(d) g  f

h

(f)

26. # Zij f p xq  x
3, gp xq  x, hp xq  x3 en jp xq een samenstelling van de bovenstaande:

(b)

? x
3 ? 2 x

(c)

x1 4

(a)

{

(d) 4x

(e)

gh f hg

(e) f

 2x. Schrijf de volgende functies als

apx
3q

(i) x9

3

(f) p2x
6q3

(j) x
6

(g) 2x
3

? ?3

(k) 2 x
3

(h) x3{2

(l)

x


3

27. G # Toon aan voor inverteerbare functies f en g: (a)

p f
1 q
1  f

(b) p g  f q
1

 f
1  g
1

28. G # Onderzoek of volgende functies inverteerbaar zijn. Zo ja, bepaal de inverse functies. Zo nee, definieer een bijectie f˜ met hetzelfde voorschrift als f en bepaal p f˜q
1 .

Ñ R : x ÞÑ |x| f : R Ñ R : x ÞÑ x 1 f : R Ñ R : x ÞÑ 2x 3 ? f : R Ñ R : x ÞÑ x

? Ñ R : x ÞÑ 2x f : R Ñ R : x ÞÑ 1 f : R0 Ñ R : x ÞÑ 2xx
3 f : R Ñ R : x ÞÑ sin x

(a) f : R

(e) f : R

(b)

(f)

(c) (d)

(g) (h)

3

2

HOOFDSTUK 1. EEN BEETJE BRUGCURSUS 29. G # Zij h : Z  Z Surjectief?

Ñ

Z : hp x, yq



2x

14 3y. Bepaal het beeld van h. Is h injectief?

30. G # Bewijs: f pS1 X S2 q  f pS1 q X f pS2 q als f injectief is (zie oef. 21). Geef een voorbeeld van een functie waarbij f pS1 X S2 q  f pS1 q X f pS2 q. 31. G # Bepaal of volgende functies injectief zijn. Geef hun beeld.

Ñ Z : x ÞÑ 2x 1 f : Q Ñ Q : x ÞÑ 2x 1 f : Z Ñ Z : x ÞÑ x3
x

Ñ R : x ÞÑ ex f : r
π {2, π {2s Ñ R : x ÞÑ sin x f : r0, π s Ñ R : x ÞÑ sin x

(a) f : Z

(d) f : R

(b)

(e)

(c)

32. G # Stel f : A Ñ B, met A dan zeggen van f ?

(f)

 X Y Y en X X Y  ∅. Als f|X en f|Y injectief zijn, wat kan je

33. # Bepaal voor elk van de volgende functies f : Z Indien niet surjectief, bepaal f pZq: (a) f p xq  x

(c) f p xq 
x

7

(b) f p xq  2x
3

(d) f p xq  x2

5

Ñ Z of ze injectief of surjectief zijn. (e) f p xq 
x2 (f) f p xq  x3

x

34. # Zelfde vraag als oefening 33, waarbij f als een functie van R naar R beschouwd wordt. 35. G # Toon aan: als A en B verzamelingen zijn, dan geldt: p A  Bq X p B  Aq p A X Bq. [examen augustus 2005]

 p A X Bq 

36. G # Vul aan (gebruik €,  of ) en bewijs: als A en B verzamelingen zijn, dan geldt:

p A  Bq Y p B  Aq [examen augustus 2005]

...

p A Y B q  p A Y B q.

Hoofdstuk 2

Stelsels en matrices Speciaal voor de studenten computerwetenschappen geven we een kort hoofdstuk over matrixrekenen en stelsels. Deze twee onderwerpen zijn zeer nauw verbonden en kennen veel toepassingen in management, het opstellen van dienstregelingen voor treinen of vliegtuigen, het ontwerpen van elektronische componenten zoals computerchips, de simulatie van (parallelle) processoren,. . .

2.1 Stelsels van lineaire vergelijkingen We kennen reeds sinds het secundair onderwijs vergelijkingen van de vorm ax

by  c.

(2.1)

Dit is een vergelijking in twee veranderlijken x en y die men lineair noemt omdat de punten px, yq van het vlak die voldoen aan deze vergelijking een rechte vormen. Dit komt omdat x en y slechts tot de eerste macht verheven worden. De vergelijking y  x2 geeft geen rechte (wel een parabool) en heet dus niet lineair (maar kwadratisch). De vergelijking 4x1
5x2  x1 x2 is ook niet lineair wegens het product x1 x2 in het tweede lid. In het algemeen is een lineaire vergelijking van de vorm a1 x1

a2 x2



an xn

 b,

waarbij de constante b en de co¨effici¨enten a1 , a2 , . . . , an gegeven re¨ele of complexe1 getallen zijn. Het aantal veranderlijken n kan om het even welk niet-nul natuurlijk getal zijn. In deze cursus zal n meestal tussen 2 en 5 liggen. In werkelijke problemen zal n groter zijn. Waarden van 50 tot 500 zijn niet ongewoon. Met zulk een groot aantal veranderlijken moet men een beroep doen op de computer voor het manipuleren van zulke vergelijkingen. Hiervoor is het belangrijk goede algoritmes te ontwikkelen. Dat is dan ook e´ e´ n van de doelen van dit hoofdstuk.

We merkten op dat de verzameling van alle koppels p x, yq P R2 die voldoen aan de vergelijking (2.1) grafisch kan gezien worden als een rechte. Als we nu zoeken naar de koppels 1 Appendix

B bevat een korte herhaling over complexe getallen.

15

HOOFDSTUK 2. STELSELS EN MATRICES

16

die tegelijk voldoen aan twee vergelijkingen, dan zullen we grafisch op zoek gaan naar het snijpunt van twee rechten. "

Voorbeeld.

x1
2x2 3x2


x1


1  3

Elk van deze vergelijkingen geeft aanleiding tot een rechte en er is een uniek punt p3, 2q dat voldoet aan beide vergelijkingen. Dit is het snijpunt van de twee rechten.

Het kan soms gebeuren dat twee rechten geen snijpunt hebben (als ze evenwijdig zijn) of juist alle punten gemeenschappelijk hebben (als ze samenvallen). Om stelsels op te lossen bestaan verscheidene methoden. In het Secundair Onderwijs heb je zeker kennis gemaakt met de zogenaamde substitutiemethode en de combinatiemethode. De combinatiemethode leent zich het best tot veralgemening en toepassing op grote stelsels. We herhalen de methode op een voorbeeld.

$ & x1
2x2 x3  0 p1q 2x2
8x3  8 p2q pS q  %
4x1 5x2 9x3 
9 p3q

We proberen x1 in de eerste vergelijking te houden en elimineren deze veranderlijke in de andere vergelijkingen. Hiervoor tellen we de eerste vergelijking vier keer op bij de derde. We noteren

$ $ & x1
2x2 x3  0 p3q 4p1q & x1
2x2 x3  0 p3q 3{2p2q ðñ % 2x2
8x3  8 ðñ 2
8x3  8 %
4x1 2x 5x2 9x3 
9
3x2 13x3 
9 $ $ $ $ & x1
2x2 x3  0 pp qq
pp qq & x1
2x2 
3 p1q p2q & x1  29 p2q{2 & 2x2  32 ðñ ðñ % % 2x2
8xx33  83 ðñ % % 2xx23  32 3 x3  3 1 2

3 8 3

zodat de oplossing van het stelsel x1 We schrijven OplpSq  tp29, 16, 3qu.

x1 x2 x3

  

 29, x2  16 en x3  3 is.

Notatie. In het algemeen noteren we de verzameling van alle oplossingen van een stelsel pSq met OplpSq. We noemen dit de oplossingenverzameling van pSq.

2.2 Matrixnotatie Voor we lineaire stelsels in het algemeen gaan oplossen, moeten we een afspraak maken om dubbelzinnigheden te vermijden. Immers de oplossingenverzameling van een lineaire vergelijking zoals bijvoorbeeld x
y  1 is 1. een rechte in R2 als we oplossingen in R2 zoeken 2. een vlak in R3 (immers x
y  1  x
y

0z

 1)

29 16 3

HOOFDSTUK 2. STELSELS EN MATRICES

17

3. een rechte in C2 als we oplossingen in C2 zoeken, enzovoort. De afspraak luidt: voor het stelsel

$ c11 x1 ' ' & c21 x1 pSq ' .. ' %.

 

c12 x2 c22 x2

c1n xn c2n xn

 b1  b2

   cmn xn  bm met co¨effici¨enten cij P R voor i P t1, . . . , mu en j P t1, . . . , nu en met tweede leden bi P R voor i P t1, . . . , mu, zoeken we oplossingen x  p x1 , . . . , xn q in R n (tenzij uitdrukkelijk anders cm1 x1

cm2 x2

vermeld). Let er wel op dat sommige co¨effici¨enten cij nul kunnen zijn. De n is hier dus het totaal aantal verschillende onbekenden die voorkomen in de vergelijkingen van pSq.

6 Definitie. Een (re¨ele) matrix is een rechthoekige tabel met (re¨ele) getallen in. We noteren de verzameling van alle matrices met m rijen en n kolommen van re¨ele getallen als Mm,n pRq. Voor een matrix A P Mm,n pRq schrijven we aij voor het element op de i-de rij en in de j-de kolom van A. We schrijven matrices meestal met Latijnse hoofdletters: A, B, C, . . . , X, Y, Z. Om redenen die we later zullen zien, noteren we een matrix met slechts e´e´n kolom liever met een kleine vette letter a, b, c, . . . , x, y, z dan met een hoofdletter. Met het stelsel pSq van hierboven kunnen we twee matrices associ¨eren: de co¨effici¨entenmatrix

 c11  c21 C .  ..

c12 c22 .. .

... ... .. .



c1n c2n   ..  . 

cm1 cm2 . . . cmn en de matrix van de constanten

b  1  b2  b .   ..  bm

Door het feit dat de “naam” van de onbekenden er weinig toe doet, is pSq volledig bepaald door de co¨effici¨entenmatrix C P Mm,n pRq en de kolom b P Mm,1 pRq m.a.w. door de uitgebreide matrix

 pC | bq  

c11 .. . cm1

. . . c1n .. .. . . . . . cmn

b1 .. .

  , soms ook Cu genoteerd.

bm

In het geval van een homogeen lineair stelsel (d.w.z. b

0

0

.. ), kan men volstaan met .

0

de co¨effici¨entenmatrix C om het stelsel volledig te bepalen.

HOOFDSTUK 2. STELSELS EN MATRICES

18

Met elk stelsel pSq kunnen we een homogeen stelsel maken door de tweede leden gelijk te stellen aan nul. We noemen het stelsel pS0 q  pC | 0q het homogeen stelsel geassocieerd met pSq. In matrix notatie krijgen we

 pC | 0q  

c11 .. . cm1

. . . c1n .. .. . . . . . cmn

0 .. .

 

dat we ook kort als

  C

c11 .. . cm1

0

. . . c1n .. .. . . . . . cmn

 

noteren.

Aan de hand van de matrix Cu kunnen we nu gemakkelijk de oplossing van het bovenstaand stelsel schematischer opschrijven.

 

1 0
4


2 2 5

1
8 9

1 0 0

 1
2 1 0   1
2 1 0 
  R 4R  0 2
8 8  R  R  0 2
8 8   0
3 13
9 0 0 1 3
2 0
3  R R  1 0 0 29  R {2  1 0 0 29  2 0 32    0 2 0 32    0 1 0 16  0 8
9

3

1

0

1

3 2

3

1

R1 R2

2

R3 8R3

2

2

3

0 0 1

3

0 0 1

3

We gebruikten hier de zogenaamde elementaire rij-operaties om de matrix te wijzigen. De toegestane operaties zijn 1. de verwisseling van twee rijen: Ri

Ø Rj;

2. de vermenigvuldiging van een rij met c, een niet-nul getal: cRi ; 3. het optellen bij een rij van een veelvoud van een andere rij: Ri

cR j .

Het is belangrijk op te merken dat deze operaties alle omkeerbaar zijn. 1. als we de twee rijen opnieuw verwisselen, is er niets gebeurd; 2. we kunnen een rij terug delen door de niet-nulle constante c; 3. we kunnen van de i-de rij c keer de j-de rij aftrekken. 7 Definitie. Voor een matrix A P Mm,n pRq defini¨eren we de getransponeerde matrix AJ als de matrix met op plaats pi, jq het element a ji van A. We hebben dus dat AJ P Mn,m pRq.

2.3 Matrices in echelonvorm We zagen hoger dat we door toepassen van elementaire rijoperaties matrices of stelsels omvormen tot eenvoudigere matrices of stelsels. We preciseren dit. 8 Definitie. We zeggen dat een m  n-matrix A in gereduceerde rij echelon vorm staat als voldaan is aan de volgende eigenschappen: 1. alle rijen van de matrix die volledig uit nullen bestaan, staan onderaan in de matrix;

HOOFDSTUK 2. STELSELS EN MATRICES

19

2. in elke andere rij is het eerste van nul verschillend element gelijk aan 1; we noemen dit element het hoofdelement van de rij; 3. het hoofdelement op rij i

1 staat rechts van het hoofdelement op rij i, voor elke i;

4. als een kolom het hoofdelement van een bepaalde rij bevat, dan bevat die kolom voor de rest enkel nullen. Een matrix die voldoet aan de voorwaarden 1, 2 en 3 (maar niet noodzakelijk 4) staat in rij echelon vorm. Een matrix A staat in (gereduceerde) kolom echelon vorm als zijn getransponeerde AJ in (gereduceerde) rij echelon vorm staat. Voorbeeld. Volgende matrices staan in rij echelon vorm:   1 5

0 2

0 1 0 3  A 0 0 0 1 0 0 0 0 0 0


2 4 7 0 0

0 0

 4 1  8 0
2 , B  0 0 0 0



2 1 0 0

3 2 1 0

4 3  3 1

0 1 0 0

0 0 1 0

0 0  0 1

en de volgende matrices staan in gereduceerde rij echelon vorm:



1 0  C 0 0 0

0 1 0 0 0

0 0 0 0 0

0 0 1 0 0


2 4 7 0 0



4 8 
2 , D 0 0



1 0  0 0



9 Definitie. Twee matrices A en B heten rijequivalent (resp. kolomequivalent) als B uit A kan verkregen worden door het toepassen van elementaire rij- (kolom-) operaties. 10 Stelling. Elke matrix A is rijequivalent (kolomequivalent) met een matrix in rij (kolom) echelon vorm. Bewijs. Kijk naar de eerste kolom j in A met een van nul verschillend element erin. Verwissel de rij waar dit element in voorkomt met de eerste rij, en deel de nieuwe eerste rij door dit element. We krijgen dus een nieuwe matrix B met de eerste j
1 kolommen nul, en b1j  1. Trek van alle andere rijen bij maal de eerste rij af. We krijgen dan een nieuwe matrix C met de eerste j
1 kolommen nul, c1j  1 en cij  0 voor i ¡ 1. Herhaal nu de bovenstaande procedure voor de matrix

 c  2,j..

. cm,j

1



1





c2,n ..  .  cm,n

We krijgen dan een nieuwe matrix D, rijequivalent met A, waarvoor de eerste j
1 kolommen nul zijn, d1j  d2k  1, voor een k ¡ j, d pq  0 voor p ¥ 1 en j   q   k, dij  0 voor i ¡ 1 en dik  0 voor i ¡ 2. Herhaal deze procedure tot er onderaan in de matrix enkel nog rijen met alleen 0 erin voorkomen. De matrix staat dan in echelonvorm.

HOOFDSTUK 2. STELSELS EN MATRICES

20

We kunnen ons resultaat nog een beetje verscherpen: 11 Stelling. Elke matrix A is rijequivalent (kolomequivalent) met een matrix in gereduceerde rij (kolom) echelon vorm. Bewijs. Pas zelf het algoritme uit het bewijs van stelling 10 aan zodat we een matrix in gereduceerde rij (kolom) echelon vorm krijgen. De in het bewijs van Stelling 10 geschetste methode om een matrix te transformeren naar (gereduceerde) echelonvorm, noemen we de spilmethode. Dit zeer belangrijk algoritme vormt de basis van vele praktische algoritmes i.v.m. matrices. Voorbeeld. We beschouwen de matrix



0 0 A 2 2

2 0 2 0

3 2
5
6


4 3 2 9



1 4  4 7

We zullen de matrix A in rijechelonvorm brengen en hiervoor de spilmethode gebruiken. De eerste kolom is de eerste met een van nul verschillend element erin, en dit staat op de derde rij. We verwisselen de eerste en de derde rij, en we krijgen de matrix



2 0 B1   0 2 Deel nu de eerste rij van B1 door b11

 2:

2 0 2 0



1 0 B2   0 2

1 0 2 0


5

2 2 3 3
4
6 9


52

2 3
6

1 3
4 9



4 4  1 7



2 4  1 7

Tel nu
2 maal de eerste rij op bij de vierde rij:



1 0  B3   0 0

1 0 2
2


52

2 3
1

1 3
4 7



2 4  1 3

Vervolgens verwisselen we de tweede en derde rij van B3 om een van nul verschillend element in de positie p2, 2q te krijgen:   1 1
52 1 2 0 2 3
4 1  B4   0 0 2 3 4 0
2
1 7 3 Deel de tweede rij van B4 door 2:



1 0 B5   0 0

1 1 0
2


52 3 2

2
1

1
2 3 7

2



1 2

4 3

HOOFDSTUK 2. STELSELS EN MATRICES

21

Tel 2 maal de tweede rij op bij de vierde rij:



1 0 B6   0 0 Deel nu de derde rij door 2:



1 0 B7   0 0

1 1 0 0 1 1 0 0


52 3 2

2 2


52 3 2

1 2

1
2 3 3 1
2 3 2

3

2



1 2

4 4 2



1 2

2 4

Trek 2 maal de derde rij af van de vierde rij:



1 0 B8   0 0

1 1 0 0


52 3 2

1 0

1
2 3 2

0

2



1 2

2 0

De matrix B8 staat in rij echelon vorm, en is rijequivalent met A.

2.4 Oplossen van stelsels met de spilmethode 12 Stelling. Beschouw twee lineaire stelsels bepaald door de matrices p A | bq en pC | dq van m vergelijkingen in n onbekenden. Indien de matrices p A | bq en pC | dq rijequivalent zijn (cf. definitie 9), dan is Oplp A | bq  OplpC | dq Bewijs. Het volstaat om na te gaan dat het uitvoeren van elementaire rijoperaties op de matrix p A | bq de oplossingsverzameling ongemoeid laten. Dit is duidelijk: een operatie van type 1 komt er op neer twee vergelijkingen met elkaar te verwisselen; type 2 komt er op neer e´ e´ n van de vergelijkingen met c  0 te vermenigvuldigen; type 3 komt er op neer om bij e´ e´ n van de vergelijkingen c maal e´ e´ n van de andere op te tellen. Als we e´ e´ n van deze drie operaties uitvoeren, krijgen we telkens een stelsel met dezelfde oplossingenverzameling. We geven enkel details voor een operatie van type 3. Zij pu1 , u2 , . . . , un q een oplossing van pSq. Dan geldt voor elke k ck1 u1

ck2 u2



ckn un

P t1, 2, . . . , mu dat

 bk .

Als we nu de i-de vergelijking veranderen door er c keer vergelijking nummer j bij op te tellen, krijgen we als nieuwe i-de vergelijking

pci1

cc j1 q x1

pci2 ccj2 qx2    pcin ccjn qxn  bi cbj . (2.2) Deze vergelijking is voldaan door pu1 , u2 , . . . , un q aangezien we reeds hadden c j1 u1 c j2 u2    cjn un  bj zodat ook ccj1 u1 ccj2 u2    ccjn un  cbj . Samen met ci1 u1 ci2 u2    cin un  bi geeft dit ci1 u1 ci2 u2    cin un cc j1 u1 cc j2 u2    cc jn un  bi cb j zodat vergelijking (2.2) voldaan is.

HOOFDSTUK 2. STELSELS EN MATRICES

22

Onderstel nu omgekeerd dat pu1 , u2 , . . . , un q een oplossing van alle vergelijkingen van pSq maar waarin we de i-de hebben vervangen door (2.2). Wij tonen nu dat pu1 , u2 , . . . , un q ook een oplossing is van de i-de vergelijking van het oorspronkelijk stelsel. Vermits pci1 cc j1 qu1 pci2 cc j2 qu2    pcin cc jn qun  bi cb j en ook cc j1 u1 cc j2 u2    cc jn un  cb j , hebben we ci1 u1 ci2 u2    cin un  pci1 cc j1 qu1 pci2 cc j2 qu2    pcin cc jn qun
pccj1 u1 ccj2 u2    ccjn un q  bi cbj
cbj  bi . Uit stelling 10 volgt nu dat we een stelsel lineaire vergelijkingen als volgt kunnen oplossen: Algoritme (Gauss eliminatie) Neem een lineair stelsel p A oplossen.

| b q.

Dit kunnen we als volgt

1. Gebruik het algoritme uit het bewijs van stelling 10 (i.e. de spilmethode) om de matrix p A | bq in rij echelonvorm te brengen. Noem de nieuwe matrix pC | dq. 2. Er zijn nu twee mogelijkheden: • Er staat een rij die bestaat uit nullen gevolgd door een niet-nul getal in de laatste kolom. Dan heeft het stelsel geen oplossingen. Soms spreken we van een strijdig stelsel.

• In het andere geval lost men het stelsel pC | dq gemakkelijk op door te vertrekken vanaf de onderste vergelijking. Voorbeeld. We lossen het stelsel

$ & x

2y x
2y % 3x y

2z 3t z t z
t

 13  8 
1

op met behulp van Gauss eliminatie. Eerst brengen we de matrix



1 p A | bq   1 3

2 2
2 1 1 1



3 1
1

13 8 
1

in rij echelon vorm. We krijgen achtereenvolgens de volgende matrices: R2 R3


R1  1
3R1 



2 0
4 0
5






R3 R2

1 2 0 1 0 0

2
1
5

3
2
10

2 3 1{4 1{2 3{4 3{2

 R {
4  2 1 2 R3 {
5 

13
5 
40



0 0





13 5{4  27{4

 43 



R3

2 3 1 1{4 1{2 1 1 2

1 0 0

2 2 3 1 1{4 1{2 0 1 2

Ons stelsel is dus equivalent met het stelsel

$ & x %

2y 2z 3t y z{4 t{2 z 2t

 13  5 {4  9



13 5{4  8



13 5 {4  9

HOOFDSTUK 2. STELSELS EN MATRICES

23

We lossen dit stelsel op van onder naar boven:

 9
2t  5{4
z{4
t{2  14 p5
9 2t
2tq 
1  13
2y
2z
3t  13 2
18 4t
3t 
3 t

z y

x

We kunnen dus besluiten dat Oplp A | bq  tp
3

t,
1, 9
2t, tq ~ t P Ru

Merk op dat er hier uiteindelijk meer veranderlijken dan (niet-nulle) vergelijkingen overblijven. In dat geval zijn er oneindig veel oplossingen. Hier zie je dat doordat elke waarde van t een oplossing geeft.

Een variante van het algorimte bestaat erin om de matrix p A | bq in gereduceerde rij echelon vorm te brengen. Dit heeft het voordeel dat de oplossingen onmiddellijk af te lezen zijn uit het nieuwe stelsel pC | dq. Een nadeel is echter dat het meer berekeningen vergt om tot de gereduceerde rij echelon matrix pC | dq te komen. Men noemt deze methode de GaussJordan eliminatie methode. Voorbeeld. We hernemen het bovenstaande voorbeeld, en passen de Gauss-Jordan eliminatie methode toe. We krijgen nu achtereenvolgens de volgende matrices: R2 R3

R1 R3


R1  1
3R1 




2R2  1 0 3{2
R2 



0 1 0 0

2 0
4 0
5

2 1 {4 1 {2 3 {4 3 {2

2
1
5



21{2 5{4  27{4

3
2
10



 34 



R3

1 0 0

 R {
4  2 1 2 R3 {
5 

13
5 
40



0 0

2 3 1 1{4 1{2 1 1 2



13 5{4  8

 R
1{4R  2 3 1 0 0 R1
3{2R3 

0 3{2 2 1 1{4 1{2 0 1 2

21{2 5{4  9



0 0

1 0 0 1


1
3 0
1 2

 

9

Ons stelsel is dus equivalent met het stelsel

$ & x
t % z

y 2t


3 
1  9

,

waaruit de oplossing volgt.

2.5 Intermezzo: vectoren en vectorruimten Bij de matrixnotatie voor stelsels noteerden we b voor de kolom der constanten. Deze “kolommen” kunnen beschouwd worden als matrices met e´ e´ n kolom maar vormen ook voorbeelden van belangrijke objecten van de wiskunde die men vectoren noemt.

HOOFDSTUK 2. STELSELS EN MATRICES

24

Voorbeeld. Een interessante verzameling vectoren is R2 . We noteren de elementen van R2 als kolommen. We hebben dus * "  R2



x y

~

x, y P R

Notatie. We noteren vectoren meestal met vette Latijnse letters: a, b, c, . . . , x, y, z. In R2 kunnen we twee vectoren steeds optellen door elk van de componenten op te tellen.

    1 2 1
2 5 
2

2 5

   33

Ook kunnen we een vector vemenigvuldigen met een re¨eel getal c door elke component te vermenigvuldigen met c.

  3 Als u 
1 en c  5

dan is

    3 15 cu  5
1 
5

We spreken hier over scalaire vermenigvuldiging en noemen het getal c een scalair. Scalairen worden niet vet genoteerd. In feite voldoen de twee bewerkingen van hierboven aan vele eigenschappen. • R2 is een commutatieve groep voor de optelling, d.w.z. 1.

is associatief: voor elke a, b, c

P R2 .

pa

bq

ca

pb

cq

2. Er is een neutraal element 0: 00

a

aa

voor elke a P R2 .

3. Elk element a P R2 heeft een tegengestelde
a: a 4.

p
aq 
a

is commutatief: a voor elke a, b

P R2 .

bb

a0 a

• De scalaire vermenigvuldiging voldoet aan volgende eigenschappen: 1. gemengde associativiteit: voor elke a, b

P R en a P R2;

pabqa  apbaq

HOOFDSTUK 2. STELSELS EN MATRICES

25

2. distributiviteiten: ap a

pa

voor elke a, b

bq

 bqa 

ab

(2.3)

aa

ba

(2.4)

P R en a, b P R2;

3. 1 is neutraal element: voor elke a P

aa

1a

a

R2 .

Voorbeeld. We kunnen vorig voorbeeld uiteraard onmiddellijk veralgemenen tot R n voor elke

n P N0 . De vectoren van R n zijn kolommen met n re¨ele getallen en de optelling en scalaire vermenigvuldiging zijn componentsgewijs gedefinieerd. Ze voldoen aan dezelfde eigenschappen als R2 .

Gesterkt door voorgaande voorbeelden voeren we een algemene definitie in. 13 Definitie. Een verzameling V uitgerust met twee bewerkingen



: V V

ÑV RV Ñ V

:

is een vectorruimte (Eng. vector space, Fr. espace vectoriel) over R (of kortweg R-vectorruimte) indien volgende eigenschappen gelden: pV, q is een commutatieve groep, d.w.z. 1.

is associatief: voor elke a, b, c P V.

pa

bq

ca

pb

cq

2. Er is een neutraal element 0 voor de optelling: 00

a

aa

voor elke a P V.

3. Elk element a P V heeft een tegengestelde
a voor de optelling: a 4.

p
aq 
a

is commutatief: voor elke a, b P V.

De scalaire vermenigvuldiging R  V 1. gemengde associativiteit: voor elke a, b P R en a P V;

a

bb

a0 a

Ñ V voldoet aan de volgende eigenschappen: pabqa  apbaq

HOOFDSTUK 2. STELSELS EN MATRICES

26

2. distributiviteiten: ap a voor elke a, b P R en a, b

pa

P V;

bq

 bqa 

3. 1 is neutraal element: 1a

voor elke a P V.

aa

ab

(2.5)

aa

ba

(2.6)

a

De elementen van V noemen we vectoren. Opmerking. In sommige gevallen is het nuttig om de scalairen niet re¨eel te nemen maar complex. De definitie van een complexe vectorruimte is analoog aan bovenstaande definitie maar met C i.p.v. R. Notatie. Het verschil van vectoren in een vectorruimte wordt als volgt gedefinieerd: u
v : u p
1qv.

Lineaire combinaties Gegeven zijn vectoren v1 , v2 , . . . , vk in R n en scalairen c1 , c2 , . . . , ck . De uitdrukking c1 v 1

c2 v 2



ck vk

is een vector van de vectorruimte R n die we de lineaire combinatie van v1 , v2 , . . . , vk met gewichten c1 , c2 , . . . , ck noemen. Lineaire combinaties zijn van groot belang voor wat volgt. Zij leveren onder andere een bijkomende manier op om een stelsel te noteren. We nemen weer het algemeen stelsel

$ c11 x1 ' ' & c21 x1 pSq ' .. ' %.

cm1 x1

c12 x2 c22 x2 cm2 x2

  

c1n xn c2n xn

 b1  b2

cmn xn

 bm

en defini¨eren nu n kolomvectoren die overeenkomen met de kolommen van de co¨effici¨entenmatrix van pSq. c  1j  c2j  c j :  .   ..  voor j P t1, 2, . . . , nu cmj Verder hebben we ook nog

b  1  b2  b .   ..  bm

HOOFDSTUK 2. STELSELS EN MATRICES

27

Nu kunnen we het stelsel schrijven als x1 c1



x2 c2

xn cn

 b.

Zo zien we dat een oplossing van pSq bestaat uit gewichten x1 , x2 , . . . , xn zodanig dat de vector b een lineaire combinatie is van c1 , c2 , . . . , cn . 14 Definitie. De verzameling van alle lineaire combinaties van de vectoren v1 , v2 , . . . , vk wordt genoteerd als vecttv1 , v2 , . . . , vk u en heet de deelruimte voortgebracht door v1 , v2 , . . . , vk . Opmerking. We spreken van voortgebrachte deelruimte omdat de verzameling vecttv1 , v2 , . . . , vk u op zichzelf een vectorruimte vormt. Bewijs dit als oefening. We zien nu dat het stelsel pSq  pC | bq enkel en alleen een oplossing kan hebben als b P vecttc1 , c2 , . . . , cn u. Met andere woorden enkel als b kan geschreven worden als lineaire combinatie van c1 , c2 , . . . , cn .

Lineaire onafhankelijkheid Beschouw een aantal vectoren a1 , a2 , . . . , an . Als (minstens) e´ e´ n van hen kan geschreven worden als een lineaire combinatie van de overige vectoren, hebben we ai



¸ 

cj aj

j i

en zien we dat 0  c 1 a1

c 2 a2



ci
1 ai
1

p
1qai

ci

1 ai 1



cn an .

We hebben volgende definitie. 15 Definitie. Onderstel dat V een vectorruimte is, en dat a1 , . . . , an P V. We noemen ta1 , . . . , an u lineair afhankelijk als er c1 , c2 , . . . , cn P R bestaan, niet alle nul, zodat de lineaire combinatie

¸n 

ci ai

i 1

de nulvector is. We kunnen nu gemakkelijk bovenstaande vaststelling ook omkeren zodat we volgende stelling krijgen. 16 Stelling. Een stel vectoren ta1 , . . . , an u is lineair afhankelijk als en slechts als e´e´n van de vectoren a1 , . . . , an een lineaire combinatie is van de overige.

HOOFDSTUK 2. STELSELS EN MATRICES Bewijs. Indien ai

 c 1 a1   

Dan is c 1 a1



28

ci
1 ai
1

ci
1 ai
1
ai

ci ci

1 ai 1

1 ai 1

 

cn an cn an

0

met tenminste de i-de co¨effici¨ent verschillend van 0, en dus is ta1 , . . . , an u lineair afhankelijk. Omgekeerd, onderstel dat ta1 , . . . , an u lineair afhankelijk is. Dan is

¸n

ci ai



0

i 1

met tenminste e´ e´ n van de co¨effic¨enten, bijvoorbeeld c j , verschillend van nul. Dan hebben we dat c j
1 cj 1 c1 cn a j
1
a j 1
  
an a j 
a1
  
cj cj cj cj een lineaire combinatie is van de overige vectoren. Voorbeeld. Een verzameling tv1 Immers 1v1

0v2



0vk

 0.

 0, v2 , . . . , vk u die de nulvector bevat is steeds lineair afhankelijk.

17 Definitie. De verzameling ta1 , . . . , an u wordt lineair onafhankelijk genoemd als ze niet lineair afhankelijk is, dus als een lineaire combinatie

¸n 

ci ai

i 1

enkel de nulvector kan zijn als alle co¨effici¨enten ci nul zijn. 18 Gevolg. De volgende eigenschappen zijn equivalent: 1. ta1 , . . . , an u is lineair onafhankelijk; 2. geen enkel van de vectoren a1 , . . . , an is een lineaire combinatie van de overige. Bewijs. Dit volgt onmiddellijk uit de stelling 16, door contrapositie. Een homogeen stelsel pC | 0q heeft uiteraard steeds de nuloplossing want 0 behoort tot de deelruimte voortgebracht door de kolommen van elke matrix C (het volstaat om alle gewichten gelijk aan nul te nemen). Indien er niet-nulle oplossingen zijn, kunnen we nietnulle gewichten x1 , x2 , . . . , xn vinden met

¸n 

xi ci

0

i 1

zodat de kolommen van de matrix C in dat geval lineair afhankelijk zijn. We vatten dit samen in volgende stelling. 19 Stelling. Een homogeen stelsel pC | 0q heeft steeds de nuloplossing. Er zijn niet-nulle oplossingen als en slechts als de kolommen van de matrix C lineair afhankelijk zijn.

HOOFDSTUK 2. STELSELS EN MATRICES

29

Basis en coordinaten ¨ 20 Definitie. Een basis van een vectorruimte V is een verzameling v1 , v2 , . . . , vn van vectoren in V die lineair onafhakelijk zijn en V voortbrengen (d.w.z. vecttv1 , v2 , . . . , vn u  V). 21 Stelling. Als B  tv1 , v2 , . . . , vn u een basis is voor V, bestaan er voor elke vector v getallen c1 , c2 , . . . , cn zodat v

¸n 

P V unieke

ci vi .

i 1

Bewijs. Het is duidelijk dat zulke getallen bestaan. We hebben immers vect B  V zodat elke vector v van V te schrijven is als lineaire combinatie van de vectoren in B. Onderstel nu dat er naast c1 , c2 , . . . , cn ook nog getallen d1 , d2 , . . . , dn bestaan met v

¸n 

di v i .

i 1

Dan geldt

¸n 

i 1

of nog

¸n 

ci vi



¸n 

di v i

i 1

pci
di qvi  0.

i 1

Vermits B lineair onafhankelijk is, besluiten we hieruit dat ci
di Dit betekent dat ci  di voor elke i P t1, 2, . . . , nu.

 0 voor elke i P t1, 2, . . . , nu.

22 Definitie. De unieke gewichten die toelaten om een vector v P V te schrijven als lineaire combinatie van vectoren uit een basis B van V noemen we coordinaten ¨ van v t.o.v. de basis B. We schrijven deze co¨ordinaten rvsB . Er geldt dus v

¸n 

ci vi

i 1

  c1 c2  ðñ rvsB   ..  . . cn

We merken op dat coordinaten ¨ gewoon vectoren zijn in de welbekende vectorruimte R n . Volgende eigenschap toont dat het voldoende is deze vectorruimten goed te kennen om in om het even welke vectorruimte (uitgerust met een basis) te kunnen rekenen. 23 Eigenschap. Zij V een vectorruimte en B een basis. Dan geldt voor alle x, y P V en alle c P R 1. rx 2.

ys B

 rxsB rysB en rcxsB  crxsB .

Bewijs. Dit is een eenvoudige oefening.

HOOFDSTUK 2. STELSELS EN MATRICES

30

Dimensie 24 Lemma. Zij V een vectorruimte en B  tv1 , v2 , . . . , vn u een basis van V. Een lineair onafhankelijk deel van V kan ten hoogste n elementen bevatten. Bewijs. Onderstel dat S  tx1 , x2 , . . . , xm u een lineair onafhankelijk deel is in V. Schrijf cki voor de i-de coordinaat ¨ van xk°t.o.v. de basis B. Als we dan de gewichten x1 , x2 , . . . , xm willen bepalen waarvoor geldt m i1 xi xi  0, krijgen we

 m n ¸ ¸ xi  cij v j  0 



i 1

j 1

m ¸n ¸

of



j 1



 cij xi

vj

 0.

i 1

De lineair onafhankelijkheid van B geeft dan dat voor elke j P t1, 2, . . . , nu geldt dat m ¸



cij xi

 0.

i 1

De gewichten x1 , x2 ,. . . ,xm zijn dus oplossingen van een homogeen stelsel met n vergelijkingen en m onbekenden. Als m ¡ n heeft zulk een stelsel oneindig veel oplossingen (aangezien het niet strijdig kan zijn). Hieruit volgt dat S niet lineair onafhankelijk kan zijn. 25 Stelling. In een gegeven vectorruimte V hebben alle basissen evenveel elementen. Bewijs. Beschouw twee basissen B  tv1 , v2 , . . . , vn u en C vectorruimte V.

 tw1 , w2, . . . , wm u van eenzelfde

We passen vorig lemma toe op de basis B en het lineair onafhankelijk deel C. Hieruit volgt m ¤ n. We kunnen het lemma ook toepassen op de basis C en het lineair onafhankelijk deel B zodat n ¤ m. Hieruit volgt n  m. 26 Definitie. Het aantal elementen in een basis van een vectorruimte V noemen we de dimensie van V. We kunnen nu het lemma anders formuleren. 27 Stelling. In een vectorruimte van dimensie n heeft een lineair onafhankelijk deel hoogstens n vectoren. Indien je de dimensie van een vectorruimte kent, kan je gemakkelijker aantonen dat een stel vectoren een basis vormt. 28 Stelling. Zij V een vectorruimte van dimensie n en zij B  tv1 , v2 , . . . , vn u een verzameling van juist n vectoren in V. Dan zijn volgende eigenschappen equivalent: 1. B is een basis;

HOOFDSTUK 2. STELSELS EN MATRICES

31

2. B is lineair onafhankelijk; 3. B is voortbrengend. Bewijs. Onderstel dat B lineair onafhankelijk is maar niet voortbrengend. Dan is er een vector v van V die niet behoort tot vect B. Dit wil zeggen dat v niet kan geschreven worden als lineaire combinatie van vectoren van B. Maar dan is B Y tvu lineair onafhankelijk met meer dan n elementen, . Onderstel nu dat B voortbrengend is maar niet lineair onafhankelijk. Dan kan minstens e´ e´ n vector vi geschreven worden als lineaire combinatie van de overige vectoren van B. Dan is Bztvu nog steeds voortbrengend. Indien deze verzameling nog niet lineair onafhankelijk is, herhaal je vorige stap om nog vectoren te schrappen. Uiteindelijk krijg je een verzameling met minder dan n vectoren die een basis vormt, . We kunnen nu ook besluiten dat een basis in een vectorruimte een minimaal voortbrengend deel is of ook een maximaal lineair onafhankelijk deel.

2.6 Matrixrekenen Op Mm,n pRq kunnen we de elementsgewijze optelling defini¨eren.

 a11  a21  .. .

a12 a22 .. .

... ... .. .

  b11  b21  .. .

a1n a2n   ..  . 

am1 am2 . . . amn

b12 b22 .. .

bm1 bm2

 



b1n a11 b11 a12 b12 . . . a1n b1n   b2n   a21 b21 a22 b22 . . . a2n b2n   .. .. .. ..    . .  . . . . .   am1 bm1 am2 bm2 . . . amn bmn . . . bmn ... ... .. .

We kunnen een matrix ook vermenigvuldigen met een scalair.

a 11  a21 c .  ..

a12 a22 .. .

... ... .. .

 

a1n ca11  a2n    ca21 ..    .. .   .

am1 am2 . . . amn

ca12 ca22 .. .

... ... .. .



ca1n ca2n   ..  . 

cam1 cam2 . . . camn

Het product van twee matrices is enkel gedefinieerd indien het aantal kolommen van de eerste matrix gelijk is aan het aantal rijen van de tweede. Onderstel dus dat A P Mn,p pRq en B P M p,m pRq. Dan is het product A  B per de definitie gelijk aan een matrix C P Mn,m pRq met volgende elementen. cij



¸p 

aik bkj

k 1

Het element op plaats pi, jq in het product wordt dus bekomen door de i-de rij van matrix A te vermenigvuldigen met de j-de kolom van B. Onderzoek zelf de eigenschappen van deze vermenigvuldiging. Toon onder andere aan dat ze niet commutatief is.

HOOFDSTUK 2. STELSELS EN MATRICES

32

Zij C de co¨effici¨entenmatrix van een stelsel pC | bq. Als we dan een kolommatrix

  x1  x2  x :  .   ..  xn

maken met de veranderlijken, kunnen we het stelsel ook terugvinden uit de vergelijking Cx  b waarbij de ‘’ het matrixproduct voorstelt en we ons ook herinneren dat twee kolomvectoren gelijk zijn als en slechts als al hun componenten gelijk zijn.

2.7 Lineaire afbeeldingen Als we een matrix A P Mm,n pRq nemen, kunnen we daarmee een afbeelding van R n naar R m mee defini¨eren. TA : R n ÝÑ R m : x ÞÝÑ A  x Uit de eigenschappen van de matrixvermenigvuldiging leiden we snel af dat 1. 2.

u, v P Rn : TA pu vq  TA puq TA pvq; u P Rn, c P R : TA pcuq  cTA puq.

29 Definitie. We zeggen dat een afbeelding F : V ruimte W linear is indien 1. 2.

Ñ W van een vectorruimte V naar een vector-

u, v P V : Fpu vq  Fpuq Fpvq; u P V, c P R : Fpcuq  cFpuq.

Toon als oefening volgende stelling aan. 30 Stelling. Voor een lineaire afbeelding F : V

Ñ W geldt steeds

• Fp0q  0; •

u, v P V, c, d P R : Fpcu

dvq  cFpuq

dFpvq.

We tonen nu dat elke lineaire afbeelding F : R n vorm TA voor een zekere matrix A P Mm,n pRq.

Ñ Rm gelijk is aan een afbeelding van de

Uit voorgaande stelling volgt dat het voldoende is om F te kennen op een basis. Inderdaad: neem een basis B  tv1 , v2 , . . . , vn u van R n en een willekeurige vector v. Dan bestaan er getallen v1 , v2 , . . . , vn met v

¸n 

i 1

vi v i .

HOOFDSTUK 2. STELSELS EN MATRICES De lineariteit van F geeft dan F pv q  F p

¸n 

33

¸n

vi v i q 

i 1



vi Fpvi q.

i 1

Dus is het beeld van v gewoon de lineaire combinatie van de beelden van de basisvectoren ° n met dezelfde gewichten vi als in de ontbinding v  i1 vi vi .

Laat ons nu algemeen een lineaire afbeelding F : V ÝÑ W beschouwen. Als we in V een basis B  tv1 , v2 , . . . , vn u kiezen en in W een basis D  tw1 , w2 , . . . , wm u, kunnen we dan ¨ van Fpvq t.o.v. D vinden? uit de coordinaten ¨ van v P V t.o.v. B gemakkelijk de coordinaten

We nemen aan dat rvsB  rv1 v2    vn sJ , m.a.w. v van Fpvi q als rc1i c2i    cmi sJ . Dan geldt F pv q 

 

¸n 

¨  °ni1 vi vi . We noteren de coordinaten

v i F pv i q

i 1 n

m ¸ ¸

vi





¸n m ¸

i 1

j 1



i 1

j 1



c ji w j

 c ji vi

wj,

Waaruit wegens Stelling 21 volgt dat de j-de coordinaat ¨ van Fpvq gelijk moet zijn aan

°n



i 1 c ji vi .

Als we nu de coordinaten ¨ van de beelden van de vectoren van B als kolommen beschouwen van een matrix C, krijgen we in matrixnotatie

rFpvqsD  C  rvsB . Dit toont dat elke lineaire afbeelding, via coordinaten, ¨ correspondeert met een afbeelding TA zoals hoger gedefinieerd. Om te tonen dat C de matrix is van de lineaire afbeelding F t.o.v. de basissen B en D, noteren we hem meestal FDB . Voorbeeld. In het algemeen vormen de veeltermen van graad ten hoogste n in e´ e´ n veranderlijke X een vectorruimte. We noteren deze R n rX s. Beschouw nu de lineaire afbeelding die veeltermen afleidt. F : R2 rX s ÝÑ R1 rX s : aX 2

c ÞÝÑ 2aX

bX

b

Laat ons als basissen eerst de “gewone” basissen kiezen. Dus B : tX 2 , X, 1u en D : tX, 1u. Dan wordt de matrix van F t.o.v. de basissen B en D als volgt bepaald.

We moeten eerst de beelden van de vectoren van B bepalen: FpX 2 q  2X, FpX q  1 en Fp1q  0. De coordinaten ¨ van deze beelden in de basis D zijn gemakkelijk te bepalen. We vullen ze direct in en krijgen   2 0 0 FDB  0 1 0 Voor een andere keuze van basissen krijgen we aan andere matrix. Neem bijvoorbeeld B1 : tX 2 , X 1, X u en D1 : t
1, 5X 2u. Dan zijn FpX 2 q  2X  45 p
1q 25 p5X 2q, FpX 1q  1  p
1qp
1q 0p5X 2q en FpX q  1  p
1qp
1q 0p5X 2q zodat de matrix gegeven wordt door FD1 B1





4{5 2{5




1
1 0

0

HOOFDSTUK 2. STELSELS EN MATRICES

34

Nu we gemakkelijk het beeld van een vector kunnen uitrekenen, kunnen we vraagstukken oplossen zoals “Bepaal alle veeltermen van graad ten hoogste 2 waarvan de afgeleide 5X is.” Dit komt dan neer op het oplossen van een stelsel met co¨effici¨entenmatrix FDB en tweede lid r5 0sJ . We vinden uiteraard 52 X2 c als oplossing. Een belangrijk vraagstuk is “welke vectoren worden afgebeeld op de nulvector?” Dit is zo belangrijk dat we er een nieuw concept mee defini¨eren.

Ñ W een lineaire afbeelding. De kern van F is de verzameling Ker F : tv P V Fpvq  0u 32 Eigenschap. Voor elke lineaire afbeelding F : V Ñ W is Ker F een deelruimte van V.

31 Definitie. Zij F : V

~

Bewijs. We moeten aantonen dat Ker F, samen met de bewerkingen van V, een vectorruimte vormt. Vele van de eigenschappen van vectorruimte worden gewoon overge¨erfd van V (bvb. de associativiteit van de optelling, de gemengde associativiteiten en de commutativiteit van de optelling). Er blijven slechts drie dingen te bewijzen. Beschouw de nulvector 0. We weten reeds (zie hoger) dat Fp0q  0 zodat 0 P Ker F. Neem nu twee vectoren a en b in Ker F. We moeten bewijzen dat a b P Ker F. Om dat na te gaan, laten we F inwerken: Fpa bq  Fpaq Fpbq  0 0  0. Nu blijft nog te bewijzen dat voor elke keuze van c P R en a P Ker F, geldt dat ca P Ker F. Weer eens laten we F inwerken: Fpcaq  cFpaq  c0  0. De kern van een lineaire afbeelding is een zeer nuttig middel om de injectiviteit (zie Definitie 1) van die afbeelding te onderzoeken. 33 Stelling. De lineaire afbeelding F : V de nulvector bevat.

Ñ W is injectief als en slechts als

de kern van F enkel

Bewijs. ñ Zij x een vector van Ker F. Dan geldt Fpxq  0 maar we weten ook dat Fp0q  0 (dit geldt steeds voor een lineaire afbeelding, zie Stelling 30). Dus hebben we Fpxq  Fp0q. De injectiviteit verzekert dan x  0. We hebben dus aangetoond dat elke vector in Ker F gelijk is aan de nulvector.

ð Onderstel Fpaq  Fpbq. Dit is equivalent met Fpaq
Fpbq  0. De lineariteit geeft dan Fpa
bq  0 zodat a
b P Ker F  t0u. Hieruit volgt a
b  0 of nog a  b.

Onderstel dat we de matrix van F t.o.v. basissen B en D kennen. Dan komt het zoeken van de kern neer op het oplossen van het homogeen stelsel p FDB | 0q. De oplossingen geven dan de coordinaten ¨ van de vectoren van Ker F t.o.v. de basis B. Een ander belangrijk begrip is het volgende. 34 Definitie. Het beeld van een lineaire afbeelding is de verzameling van alle beelden door F van vectoren van V. We noteren Im F : tw P W ~ Dv

P V : Fpvq  wu.

HOOFDSTUK 2. STELSELS EN MATRICES

35

Uit deze definitie volgt direct 35 Stelling. De lineaire afbeelding F : V

Ñ W is surjectief 2 als en slechts als

Im F

 W.

We hebben ook 36 Eigenschap. Het beeld van een lineaire afbeelding is steeds een deelruimte van het codomein. Bewijs. Zij F : V ÝÑ W een lineaire afbeelding. We moeten aantonen dat Im F een vectorruimte is. Zoals bij het bewijs van de analoge eigenschap voor de kern, worden vele te bewijzen eigenschappen overge¨erfd van het codomein W. We hoeven enkel aan te tonen dat de nulvector behoort tot Im F en dat sommen en scalaire veelvouden van vectoren van Im F in Im F blijven. Aangezien Fp0q  0, is het duidelijk dat 0 P Im F. Neem twee vectoren x, y P Im F. Dan bestaan er u en v in V met Fpuq  x en Fpvq  y. De lineariteit van F geeft dan Fpu vq  x y, zodat x y P Im F. Hetzelfde voor c P R waar de lineariteit geeft dat cx  cFpuq  Fpcuq P Im F.

Om het beeld van een lineaire afbeelding te bepalen volstaat het de beelden van een basis van het domein te kennen. We weten immers dat de beelden van alle vectoren van het domein lineaire combinaties zijn van beelden van basisvectoren. We hebben dus voor een basis B  tv1 , v2 , . . . , vn u en een lineaire afbeelding F : V ÝÑ W dat Im F

 vecttFpvi q i  1, 2, . . . , nu. ~

37 Definitie. De rang van een lineaire afbeelding is de dimensie van het beeld. Hieruit volgt dat de rang van een lineaire afbeelding F : V ÝÑ W gevonden wordt door te zoeken naar een lineair onafhankelijke deelverzameling in t Fpvi q ~ i  1, 2, . . . , nu die Im F voortbrengt. Weer eens kunnen we gebruik maken van de matrix van F t.o.v. basissen B en D. De kolommen hiervan geven immers de Fpvi q voor i  1, 2, . . . , n. De dimensies van kern en beeld van een lineaire afbeelding staan in verband met elkaar. De som van hun dimensies is gelijk aan de dimensie van het domein. 38 Stelling (Zonder bewijs). Voor een lineaire afbeelding F : V dim Ker F

dim Im F

ÝÑ W geldt

 dim V.

Vermits we de dimensie van de kern van F vinden door de spilmethode toe te passen op het homogeen stelsel met als matrix FDB , vinden we hieruit ook de rang van F: als dim V  n en dim Ker F  k weten we dim Im F  n
k. Vermits k correspondeert met het aantal vrij te kiezen veranderlijken eens de matrix FDB in rijechelonvorm staat, correspondeert de rang van F met het aantal niet-nulle rijen in deze rijechelonvorm. Voor toepassingen is het ook belangrijk om de rang van een matrix te kunnen berekenen. 39 Definitie. De rang van een matrix A is de rang van de afbeelding TA . We noteren de rang van A met rk A. 2 Zie

Definitie 2, blz. 8

HOOFDSTUK 2. STELSELS EN MATRICES Voorbeeld. We beschouwen de matrix



0 0  A 2 2

2 0 2 0

36

3 2
5
6


4 3 2 9



1 4 . 4 7

Dit is de matrix van het voorbeeld op blz. 20. Hij is rijequivalent met volgende matrix.



1 0 B8   0 0


52

1 1 0 0

1
2

3 2

3 2

1 0

0

2



1 2

2 0

De matrix B8 staat in rij echelon vorm. We kunnen besluiten dat rkp Aq  rkp B8 q  3. Als we de matrix verder in gereduceerde rijechelonvorm brengen, vinden we



1 0 B9   0 0 In stelselvorm geeft dit

$ & x %

y z

0 1 0 0

0 0 1 0

9

19  2 5 2


174
3 2

0


9s
192 t  174 s 52 t 
32 s
2t

2  0

,

$ ,  9s
19
t ' / 2 ' / ' / ' 17 s 5 t  / & .  4 2  3  ~ s, t P R . Ker TA   s

2t   2 ' / ' /   ' / s ' / % -

zodat

t

We zien dus dat deze kern dimensie 2 heeft.

2.8 Enkele voorbeelden van lineaire afbeeldingen Lineaire afbeeldingen zijn zeer nuttig bij computer graphics. We geven hier enkele voorbeelden van tweedimensionale transformaties.

Spiegelingen

1





0 x beeldt een punt met coordinaten ¨ af op het punt met coordinaten ¨ De matrix 0
1 y x
y . Dit komt overeen met een spiegeling t.o.v. de X-as. Bestudeer zelf de afbeeldingen bepaald door de matrices


1 0 0

1

en

 0
1
1 0 .

HOOFDSTUK 2. STELSELS EN MATRICES

Puntspiegeling



De matrix


1

37





0 x beeldt een punt met coordinaten ¨ af op het punt met coordinaten ¨ y
1

0 
x 
y . Dit komt overeen met een puntspiegeling t.o.v. de oorsprong.

Rotaties

0
1  x De matrix beeldt een punt met coordinaten ¨ af op het punt met coordinaten ¨ 1 0 y 
y 

. Als we het beeld van een paar punten berekenen, zien we dat het hier eigenlijk gaat x om een rotatie over π {2 radialen.

Laat ons de matrix bepalen van van een rotatie over een gegeven hoek θ. Hiervoor moeten we de coorindaten ¨ van de van de vectoren in een basis.   berekenen 0  1beelden  cos  We nemen de 1 θ gewone basis t , u. De vector 0 belandt na rotatie over θ op sin θ . Voor de vector 0  0
sin1 θ  is het beeld . We krijgen dus de matrix 1 cos θ

cos θ
sin θ  . sin θ

cos θ

Schaalveranderingen







 

k 0 x kx De matrix beeldt een punt met coordinaten ¨ af op het punt met coordinaten ¨ . 0 1 y y Dit komt overeen met een schaalverandering met factor k op de X-as. Analoog geeft de matrix

1 0 0 k

een schaalverandering op de Y-as.

Afschuivingen





1 3 Iets moeilijker zijn de afbeeldingen met een matrix zoals . Deze afbeelding beeldt een 0 1    x x 3y af op het punt met coordinaten ¨ . We zien dus: hoe groter punt met coordinaten ¨ y y de Y-coordinaat ¨ van een punt, hoe meer er bij de X-coordinaat ¨ wordt opgeteld. We krijgen een afschuiving evenwijdig met de X-as. In het algemeen zal een afschuiving met factor k evenwijdig met de X-as een matrix



hebben.



1 k 0 1

HOOFDSTUK 2. STELSELS EN MATRICES

38

Onderzoek zelf afschuivingen evewijdig met de Y-as.

Projecties









1 0 x x beeldt een punt met coordinaten ¨ af op het punt met coordinaten ¨ . De matrix 0 0 y 0  x Dit komt overeen met de projectie van het punt op de X-as. y Er is ook de projectie op de Y-as met als matrix





0 0 . 0 1

Samenstellingen Soms wil je meerdere transformaties na elkaar uitvoeren. Dit kan ook met e´ e´ n enkele matrix. Het volstaat de matrices van de transformaties te vermenigvuldigen met elkaar, in gewenste volgorde van samenstelling. Dus de transformatie die eerst moet worden toegepast komt overeen met de meest rechtse factor van het product. Als we twee lineaire afbeeldingen U ÝÑ V ÝÑ W hebben, samen met drie basissen B, C en D van U, V en W respectievelijk, hebben we dus G

F

pG  FqDB  GDC  FCB . 2.9 Bepalen van de inverse van een matrix Neem een vierkante matrix A P Mn,n pKq, en onderstel dat rkp Aq  n. Dan zet de lineaire afbeelding TA : R n Ñ R n gegeven door linksvermenigvuldiging met de matrix A een basis van R n om in een basis van R n , en dus is TA een bijectie. Als we de Gauss-Jordan eliminatie methode toepassen op het stelsel p A | bq, dan krijgen we dat de matrix p A | bq rijequivalent is met de matrix p In | X0 q, waarbij In de eenheidsmatrix is, en X0 de (unieke) oplossing van het stelsel. Dit is natuurlijk een interessante opmerking op zichzelf, maar ze kan ook gebruikt worden om de inverse van de matrix A te bepalen. Hiervoor maken we eerst volgende opmerkingen: om de inverse van de matrix A te bepalen volstaat het om het stelsel p A | ei q

 0  ..   .  met ei  1 op te lossen voor i  1, . . . , n. Als xi de oplossing is van dit stelsel, dan is  ..  . 0 A
1





x1 x2



xn



HOOFDSTUK 2. STELSELS EN MATRICES

39

Twee stelsels p A | bq en p A | cq kunnen we gelijktijdig oplossen door de matrix p A | b cq in gereduceerde rij echelon vorm te brengen. Indien we de matrix p A | In q in gereduceerde rij echelon vorm brengen, dan krijgen we dus noodzakelijkerwijs de matrix p In | A
1 q. We vatten dit samen als volgt:

40 Stelling. Onderstel dat A P Mnn pRq een reguliere matrix is. Dan is de gereduceerde rij echelon vorm van de matrix p A | In q de matrix p In | A
1 q. 



Voorbeeld. Neem de matrix

1 1 A  0 2 5 5

We brengen de matrix



1 1 p A | I3q   0 2 5 5

1 3 1

1 3 1



1 0 0 1 0 0

0 0  1

in gereduceerde rij echelon vorm. We krijgen achtereenvolgens de volgende matrices:



1 1  0 2 5 5

1 3 1

1 0 0 1 0 0



0 0  1

Trek van de derde rij 5 maal de eerste rij af:



1  0 0

1 2 0

1 3
4

Deel de tweede rij door 2, en de derde door
4:



1  0 0

1 1 0

1 3{2 1



1 0 0 0 1 0 
5 0 1



1 0 0 1{2 5{4 0

0 0 
1{4

Trek de tweede rij af van de eerste rij:



1 0  0 1 0 0


1{2 3{2 1

Tel bij de tweede rij
3{2 maal de derde rij op:



1 0  0 1 0 0


1{2

0 0 
1{4

0

1
15{8 5 {4

0 1




1{2 1 {2

1 0 5{4




1{2 1{2

0 3{8  0
1{4

Tel de helft van de derde rij op bij de eerste rij:



1 0  0 1 0 0 We kunnen besluiten dat A
1 Verifieer zelf dat AA
1

 A
1 A  I3.

0 0 1



13{8
15{8 5 {4

13{8  
15{8 5{4


1{2
1{8 1{2 3{8 0
1{4 


1{2
1{8 1{2 3 {8  0
1{4

 

HOOFDSTUK 2. STELSELS EN MATRICES

40

2.10 Oefeningen 1. Los de volgende lineaire stelsels op via Gauss eliminatie: (a)

(b)

(c)

$ &x 2x % 2x

$ &x % 2x 3x

3y z  4 2y z 
1 3y z  3

$

3z  0 ' & w x
x 2y 4y 4z  7 w 3x 7y 9z  4 ' %
w
2x
4y
6z  6 $ x
y 3z
t  0 ' & y
3z 5t  2 z t0 ' % xx
2y
t 
5

2y 3z  a 5y 5z  b 5y 8z  c

$ y
z
t  0 ' & xx 2y 3z
4t  0 3x 4y
z
t  8 ' % 2x
3y z 3t  3 $ & x y 
7 4y z 
16 % 2x x 2y z  9

2. Bespreek volgende stelsels met parameters a, b, c, d, k, l, s, t (a)

(b)

(c)

(d)

(e)

(f)

$ & x % 2xx

2y
2z 2y
z 4y
7z


2s t 
s 2t 
s
t

$ & lx % xx

y z ly z y lz

  

l 0 1

$ &x x % ax

ay bz y abz y bz

  

3 a b

b

x y
z
u x
y z
u x y kz
u

  

l k 1

$ & %

$ &x x % lx $ & % pa

y lz ly z y z x x 1q x

P R.

  

ay z y az ay z

1

l l2 l k

  

2a 0 a

HOOFDSTUK 2. STELSELS EN MATRICES

41

$ x y z ' &
x y
z ' %
xx

yy
zz $ & x ay a2 z 2 % x xby y b zz

(g)

(h)

   

a b c d

  

1 1 1

3. Definitie 14 zegt dat voor een stel tv1 , v2 , . . . , vk u vectoren de verzameling van alle lineaire combinaties van die vectoren wordt genoteerd als vecttv1 , v2 , . . . , vk u. Toon aan dat deze verzameling een vectorruimte is. 4. Bewijs eigenschap 23 op blz. 29. 5. Bestudeer de eigenschappen van de matrixvermenigvuldiging. Denk aan eigenschappen zoals neutraal element, associativiteit, commutativiteit, . . . 6. Vormt Mm,n pRq een vectorruimte voor de optelling en scalaire vermenigvuldiging van matrices? 7. Beschouw de verzameling S  tp x1 , x2 , x3 , x4 q ruimte van R4 ? Verklaar je antwoord.

P R4

~

x1 x2

 x32

x42 u. Is S een deel-

8. Welke van de volgende deelverzamelingen van R3 zijn lineair onafhankelijk? (a) (b)

tp0, 0, 0qu; tp1, 1, 1q, p2, 2, 2qu;

(c) ∅; (d) (e) (f)

tp1, 1, 0q, p0, 2, 3q, p1, 2, 3q, p3, 6, 6qu; tp1, 1, 0q, p3, 4, 2qu; tp1, 1, 0q, p0, 2, 3q, p1, 2, 3q, p0, 0, 0qu

9. Zijn volgende vectoren lineair onafhankelijk? Geef de dimensie van de deelruimten die ze voortbrengen. • in R5 : (a) (b) (c) (d)

p1, 3,
2, 2, 3q, p1, 4,
3, 4, 2q, p1, 3, 0, 2, 1q, p0, 1,
7, 2, 5q p1, 3, 0, 2, 1q, p1, 5,
6, 6, 3q, p2, 5, 3, 2, 1q p1, 3,
2, 2, 3q, p1, 4,
3, 4, 2q, p2, 3,
1,
2, 2q p0, 1, 3,
2, 1q, p3, 0,
1, 2, 2q, p1, 0, 0,
2,
3q, p
2, 1,
2, 0, 1q, p0, 4, 1,
4, 3q

• in C4 :

(a) p1, i,
1, 1q, p2i,
i,
1 i, 0q, p0, 1 2i,
3
i, 2q, pi, 2i,
3
2i, 2 (b) p2i, 1 i, 1,
1q, p3,
i, 0, 1 2iq, p4i, 2
i, 2 i,
3q

10. Voor welke waarde(n) van h zijn volgende vectoren lineair onafhankelijk?

iq

HOOFDSTUK 2. STELSELS EN MATRICES

(a)

(b)

(c)

(d)

42

 1  
2 
1  3 , 
4,  1 ;
3 h 1  0   2   2  1 , 
5, 0;
2 h 7  1  
3  4  
5,  8 ,  h ; 6
2
8    1 4
2
5 , 7 , h .

11. Gegeven zijn a, a1 , a2 , b, b1 , b2 , c, c1 , c2 P R. Toon aan dat de oplossingen p x, y, zq van het stelsel $ & ax1 by1 cz 1 0 % aa2xx bb2yy ccz2 z00 een deelruimte van R3 vormen. 12. Stel V  C pra, bsq  t f : ra, bs Ñ R ~ f continuu. Welk van de volgende verzamelingen zijn deelruimten van V? (a) (b) (c) (d) (e) (f) (g) (h) (i) (j) (k) (l) (m) (n) (o)

t f P C pra, bsq f pxq ¥ 0, xu; t f P C pra, bsq f is een constante functieu; t f P C pra, bsq f paq  0u; t f P C pra, bsq f paq  5u; t f P C pra, bsq f heeft overal een eindige afgeleideu; tα β sinpxq α, β P Ru; t f P C pra, bsq f 1 p1q  0u (onderstel 1 P ra, bs); t f P C pra, bsq f 1 p0q  1u (onderstel 0 P ra, bs); t f P C pra, bsq f p a 2 b xq  f p a 2 b
xqu; t f P C pra, bsq f paq  f pbqu; t f P C pra, bsq f 1 paq  f pbqu; t f P C pra, bsq f paq f 1 paq f 2paq  0u; t f P C pra, bsq f paq f 1 paq f 2paq  1u; t f P C pra, bsq f paq P Qu; t f P C pra, bsq f paq P RzQu. ~ ~ ~ ~

~

~

~

~

~ ~ ~ ~ ~

~

~

13. Welk van de volgende verzamelingen zijn deelruimten van de vectorruimte RrX s van alle veeltermen met re¨ele co¨effici¨enten? (a) t P (b)

P R rX s t P P R rX s

~ ~

degp Pq evenu; P1 pX q  0u;

HOOFDSTUK 2. STELSELS EN MATRICES (c) ta

(d) ta

(e) t P (f)

(g) (h) (i) (j) (k) (l)

P Ru;

bX 3 ~ a, b cX 2

bX

dX 3 ~ a

b

43

d  0u;

c

P RrXs 1 is een nulpunt van Pu; tP P RrXs degpPq ¡ 2u; tP P RrXs degpPq   2u; tP P RrXs degpPq  2u; tP P RrXs de rest bij deling door X2 tP P RrXs de rest bij deling door X2 tP P RrXs degpPq is onevenu; tP P RrXs PpXq  Pp
Xqu. ~ ~ ~ ~ ~

X

~

X

1 is 0u; 1 is 1u;

~ ~

14. Welke van de volgende deelverzamelingen van RrX s zijn lineair onafhankelijk? (a) t1, X, X 2 u;

(b) t0, X u;

(c) tX 6 , X 6

(d) tX 2

(e) t1, X (f)

t

X2

2u;

1, X 6

1, X 2
1, X u;

1, X
1, X 2
1, X 2

X

1, X 2

1u;


X
1, X

15. Definieer volgende matrices: A :

1u





1 0 1 1

en

B :





0 1 . 0 0

Beschouw vervolgens twee deelverzamelingen van M2,2 pRq: S : t M P M2,2 pRq ~ MA  AMu

T : t M P M2,2 pRq ~ MB  BMu.

Bewijs dat S en T deelruimten zijn van M2,2 pRq. Zoek een basis voor S, T en S X T. Is S Y T een deelruimte? 16. Welke van de volgende verzamelingen veeltermen brengen R2 rX s, de vectorruimten van alle re¨ele veeltermen van graad ten hoogste 2, voort? (a) t1, X, X 2 u;

(b) t1, X
1, pX
1q2 u; (c) tX 2

(d) (e) (f)

t tX 2 tX 2 X2

1, X 2

1, X
2, 2X 2

X, X 1, X 2


X

1u;

X u; 1, X

2X
1, X 2
1u.

2, X 2

X

4u;

HOOFDSTUK 2. STELSELS EN MATRICES

1 :  3
4



 

44

 

0
1 1 5     17. Zij A 1
5 , u : 0 , v :
1 en b : 2 1
3 4 TA pvq. Vind ook x met TA pxq  b. Is deze x uniek?

0 
5.
6

Bepaal TA puq en

18. Welk van de volgende afbeeldingen zijn lineaire afbeeldingen? (a) F : R2

Ñ R3 gedefinieerd door Fpa, bq

(d)

(e)

(f)

(g)

(h)

(i)

19.

(a)

(b)

bq

Ñ R3 gedefinieerd door Fpa, bq  pa b, b, a
bq F : R3 Ñ R3 gedefinieerd door Fpa, b, cq  pb, c, aq F : R3 Ñ R3 gedefinieerd door Fpa, b, cq  pa, b2 c3 , a bq F : R3 Ñ R3 gedefinieerd door Fpa, b, cq  p0, c, aq F : R Ñ R3 gedefinieerd door Fpaq  p1, a, a2 q F : R Ñ R3 gedefinieerd door f paq  p1, a, aq F : R4 Ñ R2 gedefinieerd door Fpa, b, c, dq  pa b c d, a b
1q F : R3 Ñ R gedefinieerd door Fpa, b, cq  a2 b2 c2 F : R2 rX s Ñ R3 rX s is een lineaire afbeelding. Er is gegeven dat Fp1q  1, FpX q  X 2 1, FpX 2 1q  X 3 Bepaal FpaX 2 bX cq. F : R3 rX s Ñ RrX s is een lineaire afbeelding. Er is gegeven dat Fp1q  1, FpX
1q  X 2 1, FpX 2 q  X 10 , FpX 3 q  0 Bepaal FpaX 3 bX 2 cX dq.

(b) F : R2

(c)

 pa, b, a

HOOFDSTUK 2. STELSELS EN MATRICES

45

(c) F : RrX s Ñ R is een lineaire afbeelding. Er is gegeven dat FpX i q  i Bepaal FpX n

X n
1



1q.

20. Welk van de volgende afbeeldingen f i : RrX s Ñ RrX s zijn lineaire afbeeldingen? (a) f 1 p PpX qq  PpX q2 ;

(b) f 2 p PpX qq  XPpX q; (c) f 3 p PpX qq  PpX

(d) f 4 p PpX qq  Pp0q;

1q
PpX q;

(e) f 5 p PpX qq  Pp1q;

(f) f 6 p PpX qq  P2 pX q
P1 pX q;

(g) f 7 p PpX qq  PpX 2 q;

(h) f 8 pan X n an  0); (i) f 9 pan X n

21.

(a) F : R3

an
1 X n
1



a1 X

a0 q

an
1 X n
1



a1 X

a0 q 

 a0 X n an n 1 n 1X

a1 X n
1 an
1 n n X



an
1 X



a1 2 2 X

an (met a0 X.

Ñ R3 is de lineaire afbeelding met matrix 1 3 1 1 2 4 1 0 1

ten opzichte van de standaardbasis van R3 . Bepaal Fpp1, 2, 3qq en Fpp4, 5, 6qq. (b) F : R3

Ñ R2 is de lineaire afbeelding met matrix   1
2 7 1

0

3

ten opzichte van de standaardbasissen van R3 en R2 . Bepaal Fpp2, 3,
1qq en Fpp4, 2,
1qq. (c) F : R3

Ñ R4 is de lineaire afbeelding met matrix 1 2 3  0 5
7 
7 3 2  5

0

4

ten opzichte van de standaardbasissen van R3 en R4 . Bepaal Fpp1, 3,
1qq en Fpp0, 3, 6qq. 22. Vind alle vectoren die op de nulvector worden afgebeeld door TA voor

1 A  0

3 4 1 3 3 7 6


3
2 .
7

HOOFDSTUK 2. STELSELS EN MATRICES

46

 2
3 10 9   7
5 6
7 A 
5 4
2 2  8
9 7 15

23. Bekijk TA voor

 12  
9 Behoort b     tot het beeld van TA ? Bepaal een basis voor de kern van TA . 7 3

24. Bepaal de kern, het beeld, en, indien deze bestaat, de inverse van de volgende lineaire afbeeldingen R2 Ñ R2 : (a) F1 p x, yq  2p x,
yq;

(b) F2 p x, yq  py, 0q;

(c) F3 p x, yq  p x, xq;

(d) F4 p x, yq  p3x (e) F5 p x, yq  p x (f) F6 p x, yq  p x

2y, 6x

y, x
yq;

4yq;

2yq.

y, x

25. Bepaal de kern, het beeld, en, indien deze bestaat, de inverse van de volgende lineaire afbeeldingen R3 Ñ R3 : (a) F1 p x, y, zq  p x

y, y

(c) F3 p x, y, zq  p x

y, x
y, x

(b) F2 p x, y, zq  p2x,
z, x

z, xq; zq;

2yq.

26. Bepaal de kern en het beeld van de volgende lineaire afbeeldingen RrX s Ñ RrX s: (a) F1 p PpX qq  P2 pX q
2P1 pX q;

(b) F2 p PpX qq  XPpX q; (c) F3 pan X n

an
1 X n
1



27. Gegeven zijn de matrices

0 0 A 

0 2 0 1 0 3


1 3 3 2

 3 5  ,

2 4
1 2 4 1

a0 q  a2 X 2

a1 X

1  1 B 
1 2 1

2 1 2 1 2

3 2
1 2 1

a1 X

2 2
2 1 2

a0 .



3 3  1 , 2 1

1
2 0 2
3
1 C  1 1

3 1

2 0



2 5  5 2

Gebruik elementaire rijoperaties om A (resp. B, C) in rijechelonvorm te brengen, en om A (resp. B, C) in gereduceerde rij echelon vorm te brengen. Wat is de rang van A (resp. B, C)? Geef een basis van de deelruimte van R5 (resp. R5 , R4 ) voortgebracht door de kolommen van A (resp. B, C). Gebruik elementaire kolomoperaties om A (resp. B, C) in kolomechelonvorm te brengen. Verifieer dat het aantal lineair onafhankelijke kolommen van A (resp. B, C) gelijk is aan het aantal lineair onafhankelijke rijen.

HOOFDSTUK 2. STELSELS EN MATRICES

47

28. Vind de matrix t.o.v. de gewone basissen van de afbeeldingen met volgende eigenschappen:

ÝÑ R3, Fp1, 0q  p4,
1, 2q en Fp0, 1q  p
5, 3, 6q. (b) F : R2 ÝÑ R2 , Fp1, 0q  p3, 3q en Fp0, 1q  p
2, 5q. (c) F : R3 ÝÑ R2 , Fp1, 0, 0q  p1, 4q, Fp0, 1, 0q  p3,
8q en Fp0, 0, 1q  p
2, 9q. (d) F : R2 ÝÑ R4 , Fp1, 0q  p1, 2, 0, 5q en Fp0, 1q  p3,
6, 1, 0q. (e) F : R2 ÝÑ R2 , F roteert punten kloksgewijs over π radialen. (f) F : R2 ÝÑ R2 , F roteert punten kloksgewijs over π {2 radialen. (g) F : R2 ÝÑ R2 , F is een “verticale afschuiving” met Fp1, 0q  p1, 2q en Fp0, 1q  p0, 1q. (h) F : R2 ÝÑ R2 , Fp1, 0q  p1, 0q en Fp0, 1q  p
3, 1q. Verklaar meetkundig. (i) F : R3 ÝÑ R3 , F projecteert p x1 , x2 , x3 q op het x2 x3 -vlak. (j) F : R2 ÝÑ R2 , F is een spiegeling t.o.v. de rechte x1  x2 . (k) F : R2 ÝÑ R2 , F roteert eerst over π {4 radialen en spigelt dan t.o.v. de x2 -as. (l) F : R2 ÝÑ R2 , F is een puntspiegeling t.o.v. de oorsprong, gevolgd door een rotatie over π {2 radialen. Stel     7 0
1 1 4 1
A :
1 5 2 , B : 5
3 0 ,       1 4 1 0 7 C :
4 0 , D :
2 1 , E :
3 Bepaal indien mogelijk
2A, B
2A, AC, CD, A B, 3C
E, CB en EB. Leg uit indien (a) F : R2

29.

niet mogelijk.

30. Bepaal de inverse van volgende matrices.

1 A :  3

 4 0

2 3 1 2 , 2 3 1



2 11 3 0 1 5 3

31. Zoek de inverse van de volgende matrices: (a)

(b)



1 A  1

 1 2 3  0 1 2 ; D   1 0 1 1 0

2 B  0

 3 2 ;

1 1 1 0 3

a 1  0 E 0 0

1
2 2 3

2 0 1 2



a   1



1   1

1 0 
2 ; G 1

0 0 0 a2 0 0  ; H 0 a3 0  0 0 a4

0 a 0 1 0 0

0 3 1 3 1 3



0 0 a 1

0 0  0 a

0 0 5 5

0 0  0 7



HOOFDSTUK 2. STELSELS EN MATRICES (c) C







a b ; c d

0 0 F 

0 a4

48



0 0 a1 0 a2 0  ; I a3 0 0  0 0 0

1  0



0 3 0 7 3
5 0

32. Bepaal de rang van alle matrices die in dit hoofdstuk voorkomen.