171 72 672KB
Norwegian Pages 179 Year 2009
Matriser og vektorrom Dan Laksov & Roy Skjelnes Notater for et gymnaskurs. Skrevet som en del av et prosjekt ˚ ar 2000-2006 støttet av: Marianne och Marcus Wallenbergs Stiftelse. Versjon VII-II. Juli 2009
Matematiska Institutionen, KTH.
Innledning Dette er notater for et kurs om matriser og vektorer for gymnaselever i andre og tredje klasse. Undervisningstiden er en dobbelttime per uke i 24 uker. Undervisningen skal alternere mellom gymnaset der elevene g˚ ar, der en matematikklærer gir undervisningen, og KTH, der en forsker underviser. Vi vil ¨ takke Dick Andersson p˚ a Ostra Reals Gymnasium for hans hjelp med disse notatene, og for hans entusiasme for matematikk, som fikk programlederen til ˚ a starte det opprinnelige prosjektet. Materialet dekker de grunnleggende delene av et vanlig kurs i Lineær algebra p˚ a universiteter og høyskoler. Vektorer, matriser og ligninger er grundig fremstilt, og en abstrakt fremstilling av vektorrom inng˚ ar. Hensikten med kurset er ˚ a lære elevene ˚ a løse lineære ligninger, og ˚ a regne med vektorer og matriser. Samtidig har vi forsøkt ˚ a gi et bredere perspektiv p˚ a matematikken ved ˚ a fremheve betydningen av avbildninger og vektorrom. I oppgavene har vi introdusert materiale fra algebra, kombinatorikk og tallteori, som vi h˚ aper skal virke inspirerende. Forelesningene var en del av et prosjekt 2000-2006 om Matematik f¨or Gymnasiet støttet av Marianne och Marcus Wallenbergs Stiftelse og som har som m˚ al ˚ a øke interessen for-, og kunnskap om-, matematikk i gymnaset. Prosjektlederen vil benytte denne anledningen til ˚ a takke Marianne och Marcus Wallenbergs Stiftelse for støtten, som har gjort prosjektet mulig, og som er en oppmuntring til samarbeide mellom gymnas og høyskole. Vi vil ogs˚ a takke Institut Mittag-Leffler som har hjulpet til med ˚ a forvalte prosjektmidlene.
Matematiska Institutionen, 10. august 2005 Dan Laksov Vi har i den seneste versjonen endret litt p˚ a rekkefølgen av seksjonene. Delen med vektorrom har vi lagt sist i heftet, hvor vi ogs˚ a har lagt ved en seksjon om egenrom. De tre første kapitlene i dette heftet behandler matriser, ligninger og determinanter. Baserte p˚ a tidligere ˚ ars erfarenheter tror vi at disse tre kapitlene er passende i niv˚ a og omfang for kurset. Den siste delen av heften er ment ˚ a fungere som støttematerial for de studenter som velger ˚ a gjøre prosjektarbeid parallelt med kurset. Matematiska Institutionen, 3. august 2007 Dan Laksov og Roy Skjelnes
iii
Lese˚ aret 2007-2008 ble kursdeltagerne bedt om ˚ a lete etter og rapportere feil i heftet. Vi er takknemlige over den insats kursdeltagerne gjorde og over alle de feil de gjorde oss oppmerksomme p˚ a. Spesielt vil vi passe p˚ a˚ a berømme Golshid Baghban, Kalle Knoph, Camilla Trinh, Simon Gunnarsson, Martin Ingemansson, Patrik Rufelt, og Marvin Stahlbacke. De feil disse personer fant i versjon seks finns under linken www.math.kth.se/~skjelnes/KURS/GYMNAS/07/errata.html Foruten disse endringene, inneholder versjon VII et kapittel om anvendelser. Lese˚ aret 2008-2009 var det betydelig vanskeligere ˚ a oppdage feil, men personene Agneta Avasj¨o, Filip Bergqvist, og Oscar Mickelin klarte ˚ a finne noen: www.math.kth.se/~skjelnes/KURS/GYMNAS/08/errata.html Matematiska Institutionen, 29.juni 2009 Dan Laksov og Roy Skjelnes
iv
Innhold 1 Matriser 1.1 Euklidske Vektorer . . . . . . . . . . . . . . . . . . 1.1.4 Visualisering . . . . . . . . . . . . . . . . . . 1.1.5 Spr˚ ak og anvendelser . . . . . . . . . . . . . 1.2 Operasjoner p˚ a vektorer . . . . . . . . . . . . . . . 1.2.1 Multiplikasjon av en skalar med en vektor . 1.2.3 Addisjon av vektorer . . . . . . . . . . . . . 1.3 Matriser . . . . . . . . . . . . . . . . . . . . . . . . 1.3.2 Eksempler p˚ a matriser . . . . . . . . . . . . 1.3.6 Multiplikasjon av en skalar med en matrise . 1.3.8 Addisjon av matriser . . . . . . . . . . . . . 1.4 Matrisemultiplikasjon . . . . . . . . . . . . . . . . . 1.4.1 Multiplikasjon av en matrise med en vektor 1.4.6 Summasjon av indekser . . . . . . . . . . . . 1.4.8 Multiplikasjon av matriser . . . . . . . . . . 1.5 Avbildninger av planet . . . . . . . . . . . . . . . . 1.5.2 Speilinger . . . . . . . . . . . . . . . . . . . 1.5.3 Strekning og krympning . . . . . . . . . . . 1.5.4 Rotasjon . . . . . . . . . . . . . . . . . . . . 1.5.5 Lineære avbildninger . . . . . . . . . . . . . 2 Ligninger 2.1 Eksempler . . . . . . . . . . . . 2.2 Gauss-Jordan eliminasjon . . . 2.2.6 Eliminasjon av variable . 2.2.8 Elementære operasjoner 2.2.10 Eliminasjon for matriser 2.2.12 Elementære matriser . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . . . . . . . . . . . . . . .
. . . . . .
. . . . . . . . . . . . . . . . . . .
. . . . . .
. . . . . . . . . . . . . . . . . . .
. . . . . .
. . . . . . . . . . . . . . . . . . .
. . . . . .
. . . . . . . . . . . . . . . . . . .
. . . . . .
. . . . . . . . . . . . . . . . . . .
1 1 2 5 12 12 12 20 20 22 23 26 26 27 29 38 38 39 39 40
. . . . . .
47 47 60 62 64 64 66
3 Determinanter 73 3.1 Ikke singulære matriser og determinanter . . . . . . . . . . . . 73 v
3.1.6 3.1.7 3.1.11 3.1.12
Systemer med like mange ligninger som Utregning av inverse matriser . . . . . Generell invers til en matrise . . . . . . Determinanter . . . . . . . . . . . . . .
ukjente . . . . . . . . . . . . . . .
4 Vektorrom 4.1 Mengder og vektorrom . . . . . . . . . . . . . . 4.1.2 Mengder . . . . . . . . . . . . . . . . . . 4.1.7 Grupper . . . . . . . . . . . . . . . . . . 4.1.14 Vektorrom . . . . . . . . . . . . . . . . . 4.1.23 Euklidske rom . . . . . . . . . . . . . . . 4.1.24 Paritetsproblemet . . . . . . . . . . . . . 4.2 Avbildninger . . . . . . . . . . . . . . . . . . . 4.2.1 Avbildninger . . . . . . . . . . . . . . . 4.2.4 Surjektivitet, injektivitet og domene . . 4.2.6 Sammensetning av avbildninger . . . . . 4.3 Lineære avbildninger . . . . . . . . . . . . . . . 4.3.1 Lineære avbildninger . . . . . . . . . . . 4.3.8 Matrisemultiplikasjon og sammensetning 4.3.10 Sammensetning av tre avbildninger . . . 4.4 Egenvektorer . . . . . . . . . . . . . . . . . . . 4.4.1 Invariante delmengder . . . . . . . . . . 4.4.5 Egenvektorer . . . . . . . . . . . . . . . 4.4.10 Karakteristisk polynom . . . . . . . . . . 4.4.15 Baser for vektorrom . . . . . . . . . . . 4.4.22 Egenrom . . . . . . . . . . . . . . . . . . 5 Anvendelser 5.1 Et eksempel med Markov kjeder . . . . 5.1.1 Lunsjmodellen . . . . . . . . . . 5.1.2 Matematisk modell . . . . . . . 5.1.3 Matrisepotenser . . . . . . . . . 5.1.4 Markovkjeder . . . . . . . . . . 5.1.9 Lunsjmodellens stabile fordeling 5.1.10 Uavhengighet av initalverdien . 5.2 De komplekse tall . . . . . . . . . . . . 5.2.1 En spesiell klasse matriser . . . 5.2.3 Utvidelse av de reelle tall . . . . 5.2.6 De komplekse tall som det reelle 5.2.7 Geometrisk tolkning av produkt 5.3 Pick’s Sats . . . . . . . . . . . . . . . . vi
. . . .
. . . .
. . . .
. . . .
74 75 77 77
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
87 87 87 89 92 95 96 101 101 103 105 112 112 115 116 121 121 121 122 124 128
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . tallplanet . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
132 132 132 132 133 134 135 136 139 139 140 141 142 145
5.4
5.3.1 Notasjon . . . . . . . . . . Google og informasjonssortering . 5.4.1 Nettet . . . . . . . . . . . 5.4.2 Bl˚ akopi . . . . . . . . . . 5.4.3 Rangering . . . . . . . . . 5.4.4 Popularitetsrangering . . . 5.4.5 PageRank . . . . . . . . . 5.4.7 Matematisk formalisering 5.4.8 Hyperlinkmatrisen . . . . 5.4.11 Rangeringsvektoren . . . . 5.4.14 Iterering . . . . . . . . . .
Fasit
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
145 153 153 153 154 154 155 155 156 157 159 161
vii
Kapittel 1 Matriser 1.1
Euklidske Vektorer
Innledning 1.1.1. En vektor er en horisontal eller vertikal oppstilling av symboler. Vi treffer p˚ a slike1 oppstillinger overallt. En rad med bokstaver i en bok, eller en kolonne i en tabell er en vektor. Slike oppstillinger har ingen interesse i seg selv. Det som gjør vektorer s˚ a viktige er at vi kan regne med dem. Vi kan multiplisere en vektor med et tall og legge sammen to vektorer om de har samme størrelse. Dette gir vektorer en struktur som er avgjørende for anvendelser i og utenfor matematikken. Ennu viktigere er det av vi kan multiplisere en vektor med en matriser. Slike operasjoner er blandt de aller viktigste operasjonene i matematikken og dens anvendelser. En rekke matematiske strukturer blir studert ved2 at vi presenterer dem som operasjoner av matriser p˚ a vektorrom. Det er derfor ikke bare innenfor den disiplinen av matematikken vi skal behandle i denne boken, og som kalles lineær algebra, som teknikkene er nyttige. De gir ogs˚ a informasjon om mange andre, tilsynelatende urelaterte, strukturer. Vi skal gi de viktigste egenskapene ved matrisemultiplikasjon. Først skal vi imidlertid presentere vektorer og forklare hvorfor de er s˚ a viktige. Vi skal ogs˚ a gi deres viktigste egenskaper. Eksempel 1.1.2. De vektorene vi skal se nærmere p˚ a er en oppstilling av tall. Eksempler p˚ a slike oppstillinger er: ( 32 ) , 1 2
√
2 π
slike = s˚ adana ved ¨ ar norska f¨ or vid
1
,
π ( −5 ),
som kalles 2-vektorer. Andre eksempler er: 1 2 3
,
√2 3 −5
,
π π −1
,
som kalles 3-vektorer. For ˚ a spare vertikal plass skriver vi: (1, 2)t = ( 12 ) ,
(π, π, −1)t =
og
π π −1
,
der t øverst til høyre p˚ a vektorene (1, 2)t respektive (π, π, −1)t st˚ ar for transponert. Vilk˚ arlige 2- og 3-vektorer v skriver vi v = ( aa12 ) = (a1 , a2 )t og v =
a1 a2 a3
= (a1 , a2 , a3 )t
der a1 ,a2 og a3 er tall. Vi kan generelt definere n vektorer for hver positivt tall n: Definisjon 1.1.3. La n være et positivt helt tall. En n-vektor v er en oppstilling: a1 a2 v = .. = (a1 , a2 , . . . , an )t . an av tall a1 , a2 , . . . , an . Tallet ai kalles den i’te koordinaten til v. Bokstaven t oppe til høyre p˚ a en liggende vektor st˚ ar for den transponerte av vektoren, t og vi kaller (a1 , a2 , a3 ) for den transponerte av vektoren v.
1.1.4
Visualisering
En vektor er en oppstilling av tall. P˚ a linjen, i planet og i rommet er vi vant til ˚ a visualisere vektorer som punkter. Dette kan hjelpe til med ˚ a forst˚ a endel av egenskapene til vektorer. For eksempel er vi vant til ˚ a visualisere en 2-vektor som et punkt i planet. For eksempel vil (5, 3)t være representert ved 2
y (5, 3)t
3 2 1 0
1
2
3
4
5
x
6
der første koordinaten i (5, 3)t er x-koordinaten og den andre er y-koordinaten. P˚ a en tilsvarende m˚ ate kan vi representere alle punktene i planet, og hvert punkt kan representeres som en vektor. Derfor svarer 2-vektorer helt til punktene i planet. Vi vet ogs˚ a at 3-vektorene svarer til punktene i rommet. Det vil si at vi kan representere 3-vektorer som punkter i rommet der første koordinaten er x-koordinaten, den andre koordinaten er y-koorodinaten og den tredje koordinaten er z-koordinaten, og omvendt, til hvert punkt i planet svarer nøyaktig en 3-vektor. For eksempel vil vektoren (2, 5, 3)t være representert ved z 3 (2, 5, 3)t
2 1 0 1
1
2
3
4
5
6
y
2 x Tilsvarende kan vi representere alle vektorer som punkter i rommet, og omvendt vil hvert punkt i rommet representeres ved en vektor. Vi sier at 2-vektorene er en matematisk modell for planet og 3-vektorene er en matematisk modell for rommet. Det er viktig ˚ a forst˚ a at v˚ are vektorer ikke er virkeligheten, men at de kan brukes som en modell for virkeligheten. Fra et matematisk synspunkt er vektorer av en vilk˚ arlig dimensjon veldefinerte objekter som vi kan regne med. Det spiller ikke noe rolle for den matematiske beskrivelsen at det finnes modeller for 2- og 3-vektorer. Derimot er det typisk at matematikken, som ofte utvikler seg helt etter egne prinsipper og lover, kan brukes til ˚ a beskrive den virkeligheten vi lever i. 3
Fra √ et matematisk synspunkt er 4-vektorer, som (1, 3, −2, 4)t , (6π, 2, −1, π)t og ( 2, −5, 2, 1)t , like naturlige som 2-vektorer og 3-vektorer. Derimot kan vi ikke visualisere 4-vektorer p˚ a en naturlig m˚ ate. Dette har skapt mye filosofisk forvirring om hva det fire dimensjonale rommet er for noe. P˚ a den andre siden har mangelen p˚ a en fysisk modell for det fire dimensjonale rommet gitt3 opphav til mye underholdende litteratur om hvilke mirakler vi kan utføre i rommet om man lever i det fire dimensjonale rommet. Situasjonen tilsvarer hva vi, som lever i det tredimensjonale rommet kan gjøre i det to dimensjonale rommet. For eksempel kan vi ta en todimensjonal person ut av et lukket rom i planet, det vil si et kvadrat, uten ˚ a passere dører eller vinduer, ved ˚ a løfte opp personen i det tredimensjonale rommet, føre personen over veggen, og sette den ned p˚ a utsiden. Like spennende er det ˚ a beskrive hva som skulle hende med oss om vi ble manipulerte av skapelser som befant seg i et eventuelt firedimensjonalt rom som inneholder v˚ art. Matematisk sett har vi ingen problemer med firedimensjonale rom. For oss best˚ ar det fire dimensjonale rommet av 4-vektorer og vi kan operere like fritt i det fire dimensjonale rommet som i det todimensjonale, eller for den sakens skyld i det elvedimensjonale rommet. Det er veldig viktig av vi p˚ a denne naturlige m˚ aten kan arbeide i rom av høy dimensjon. Selvom vi ikke kan se rom av høyere dimensjon enn tre forekommer de ofte i anvendelsene. Vanligvis er koordinatene parametre i et fysisk system. For eksempel n˚ ar vi vil forutsi hvordan været blir i morgen, vil dette avhenge av trykk, temperatur, luftfuktighet, vindhastigheter og retninger, og mye annet. Disse faktorene kalles parametre for værsystemet. For ˚ a f˚ a en bra forutsigelse m˚ a vi ikke bare kjenne disse parametrene der vi st˚ ar, men p˚ a en rekke andre steder p˚ a jorden. Dette blir da nye parametre. I de systemene som finnes i dag for ˚ a forutsi været er antallet parametre enormt, og de matematiske modellene som behandler systemet er ytterst kompliserte. Dette er en av grunnene til at værvarsler over lengre perioder er s˚ a vanskelige. Noe av styrken i matematikken ligger i abstraksjonen. Dette gir oss muligheter til ˚ a betrakte generelle teorier som kan anvendes over store felt. Vi behøver ikke engang ha et bilde av hva som foreg˚ ar, men kan manipulere objektene ganske abstrakt for ˚ a f˚ a ut de resultatene vi behøver. Derfor klarer vi oss oftest uten figurer. I mange situasjoner hjelper det mye ˚ a ha et bilde av situasjonen, selv der det egentlig ikke finnes slike bilder. Vi benytter oss da av analogier i lavere dimensjoner der vi kan tegne. Et eksempel p˚ a dette er de værkartene som brukes i televisjonen til ˚ a illustrere værsituasjonen og der noen ganske f˚ a av parametrene inng˚ ar. Lesere som har stort behov av ˚ a se matematiske p˚ astander, eller kanskje rentav har angst for høyere dimen3
gitt ¨ ar norska f¨ or givet
4
sjoner, oppmuntrer vi til ˚ a tegne figurer i planet og rommet for ˚ a illustrere begrepene vi innfører. Vi gir ogs˚ a noen oppgaver som hjelper den visuelle forst˚ aelsen. N˚ ar vi skal anvende matematikken er det ofte meget viktig ˚ a ha et bra bilde av de matematiske modellene. Spesielt i mekanikk og fysikk er vektorer betraktet som piler meget viktige. Vektorer representerer da fysiske størrelser som b˚ ade har en størrelse og retning. Vi har alle erfaring av hvordan det bidrar til den fysiske forst˚ aelsen at vi b˚ ade kan se i hvilken retning en kraft virker, og hvilken størrelse den har, eller at en pil b˚ ade gir hastigheten til en partikkel, og retningen den beveger seg i.
1.1.5
Spr˚ ak og anvendelser
Ordet vektor kommer fra latin og er avledet av det latinske ordet for ˚ a bære eller føre med seg. Vektorer i en liknende betydelse som vi har innført dem ble først brukt i fysikken og mekanikken, der vektorer er noe som har b˚ ade størrelse og retning, som hastighet og kraft. Vektoren plasseres i det punktet kraften virker og har samme retning som kraften og lengden av vektoren representerer størrelsen til kraften. Det er praktisk at alle pilene i planet, og ikke bare de som begynner i origo, betraktes som vektorer, og at to piler som har samme lengde og retning, men muligens begynner i ulike punkter, betraktes som like. Hver vektor, i denne bemerkelsen, er lik nøyaktig en vektor som begynner i origo, det vil si en vektor i den betydelsen vi har brukt ovenfor. y
t
(c − a, d − b)
(c, d)t
(a, b)t x N˚ ar vi regner med vektorer spiller det imidlertid ingen rolle hvor vektoren virker. Vi velger ˚ a plassere alle vektorene slik at de begynner i origo. 5
y (a, b)t
b
a
x
N˚ ar vi vil illustrere bruken av vektorer med diagrammer er det praktisk ˚ a kunne plassere vektorene der det passer best for den situasjonen vi er i. Vi skal i disse notatene illustrere flere geometriske situasjoner med vektorer, og vise hvordan vektorregning forenkler beregninger og hvordan diagrammer av vektorer gjør det lett ˚ a f˚ a geometrisk oversikt over situasjonen. Det kommer aldrig til ˚ a være noen problemer med ˚ a skille p˚ a en vektor i den algebraiske betydningen vi har sett ovenfor, som en samling av koordinater (a1 , a2 )t og illustrasjonen av en vektor med en pil som begynner i origo (0, 0)t og slutter i punktet (a, b)t , Det kommer heller ikke til ˚ a være noe problem ˚ a forestille oss at vi translaterer denne vektoren til et annet punkt i rommet, som i figuren ovenfor. Vi har illustrert forskjellen, og likheten, mellom en vektor og dens representasjon i planet. Selvsagt er det ikke noen forskjell mellom situasjonen i planet og i rommet. Translasjoner av vektorer i planet og i rommet er lett ˚ a foreta. Ogs˚ a i høyere dimensjonale rom er det ingen problemer ˚ a translatere vektorer og situasjonen er helt analog til den i planet. I dimensjoner større enn tre er imidlertid problemet at vi ikke kan se vektorene s˚ a vi har ingen muligheter for ˚ a illustrere situasjonene med diagrammer, og det har derfor ikke noen mening ˚ a snakke om hvor vi plasserer vektorene. Vi m˚ a da klare oss med den algebraiske representasjonen av vektorer som vi har gitt. Skal vi illustrere hva som hender i høyere dimensjonale rom f˚ ar vi klare oss med analogier i planet og i rommet. I rommet vil vektoren (a, b, c)t være representert av en pil som begynner i origo (0, 0, 0)t og slutter i punktet (a, b, c)t .
6
z c (a, b, c)t
b
y
a x Betraktelsene ovenfor kan brukes som motivasjon for v˚ ar presentasjon av vektorer og ogs˚ a gi en visuell id´e om noen av resultatene om vektorer. Vi skal imidlertid ikke se p˚ a vektorer slik man gjør i anvendelser. For oss skal en vektor være et n-tuppel (a1 , a2 , . . . , an )t . Oppgaver 1.1.6. 1. Det finnes fire 2-vektorer (0, 0), (0, 1), (1, 0), (1, 1) som bare har koordinater 0 eller 1. (1) Skriv opp alle 3-vektorer som bare har koordinater 0 eller 1. (2) Hvor mange n-vektorer er det som bare har koordinater 0 eller 1? 2. Det finnes to 2-vektorer (1, 2), (2, 1) som har koordinater 1 eller 2 og der koordinatene er ulike. Videre finnes et seks vektorer (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1) som har koordinater 1, 2 eller 3 og der alle koordinatene er ulike. (1) Skriv opp alle 4-vektorer som har koordinater 1, 2, 3, eller 4, og der alle alle koordinatene er ulike. (2) Hvor mange n-vektorer finnes som har koordinater 1, 2, . . . , n − 1, eller n og der alle koordinatene er ulike? Vektorene i punkt (2) kalles for permutasjoner av tallene 1. 2, . . . , n. 3. Ved kodning av meddelelser er det vanlig ˚ a representere alfabetet ved strenger av nuller og etter. Dette kan vi gjøre ved ˚ a representere nummeret 7
for hver bokstav binært, det vil si vi representerer a, b, c, d, e, f, g, . . .˚ a ved a →1 b →2 c →3 d →4 e →5 f →6 g →7 .. . ˚ a →29
= (1, 0, 0, 0, 0) = 1 · 2 = (0, 1, 0, 0, 0) = 1 + 1 · 2 = (1, 1, 0, 0, 0) = 1 · 22 = (0, 0, 1, 0, 0) = 1 + 1 · 22 = (1, 0, 1, 0, 0) = 1 · 2 + 1 · 22 = (0, 1, 1, 0, 0) = 1 + 1 · 2 + 1 · 22 = (1, 1, 1, 0, 0) = 1 + 1 · 22 + 1 · 23 + 1 · 24 = (1, 0, 1, 1, 1).
Merk p˚ a norsk er ˚ a den 29’ende bokstaven i alfabetet. Et ord med 6 bokstaver blir da kodet som en vektor med 6·5 = 30 koordinater, som alle er 0 eller 1. For eksempel gir (0, 1, 1, 0, 1, |1, 0, 1, 0, 0, |1, 0, 1, 1, 0, |0, 0, 1, 0, 1, |1, 1, 1, 1, 0, |0, 1, 0, 0, 1) ordet vektor. I kodning benytter man seg ofte av avstanden mellom ord, det vil si antallet koordinater i de tilsvarende vektorene som er ulike. For eksempel, om vi tar ord med en bokstav, f˚ ar vi avstandene d(a, b) = 2, d(a, c) = 1, d(a, d) = 2, d(a, e) = 1, d(a, f ) = 3 og d(a, v) = 4. Mer presist om v = (a1 , a2 , . . . , an )t og w = (b1 , b2 , . . . , bn )t s˚ a definerer vi avstanden d(v, w) mellom vektorene v og w som antallet indekser i slik at ai 6= bi . (1) Fullfør tabellen over representasjonen av alfabetet som 5-vektorer. (2) Vis at avstandsfunksjonen definerer en metrikk p˚ a alle n vektorer med 0’er og 1’ere som koordinater. Det vil si, vi har for alle slike vektorer u, v og w (a) d(v, w) = 0 hvis og bare hvis v = w. (b) d(v, w) = d(w, v). (c) d(u, w) ≤ d(u, v) + d(v, w). Hint. For ˚ a vise del (c) kan det være en fordel ˚ a innføre Kronecker deltaet ( 1 om a = b δab = 0 om a 6= b. 8
Vis først, ved ˚ a diskutere alle muligheter for n˚ ar a, b og c er like eller ulike, at δab + δbc ≤ 1 + δac og at dette er det samme som at 1 − δac ≤ 1 − δab + 1 − δbc . Deretter viser du at om v = (b1 , b2 , . . . , bn ) og w = (c1 , c2 , . . . , cn ) s˚ a er d(v, w) = 1 − δb1 c1 + 1 − δb2 c2 + · · · + 1 − δbn cn . Vis til slutt at (c) følger av at om u = (a1 , a2 , . . . , an ) s˚ a vil 1 − δai ci ≤ 1 − δai bi + 1 − δbi ci for i = 1, 2, . . . , n. Leopold Kronecker (1823-1891) var en av de mest innflytelsesrike matematikerne i forrige ˚ arhundret. Han kjempet for strigens i matematikken og ville inordne matematikken i et liknende aritmetisk mønster som tallteorien. Han er kjent for ˚ a ha sagt at de hele tallene har gud skapt, alt annet er menneskenes verk. (Die ganzen Zahlen hat der liebe Gott gemacht, alles andere ist Menschenwerk). Mindre flatterende er hans kontroverser med Georg Cantor (1845-1918) om mengdelæren, der Cantors teori s˚ a sm˚ att ble alment akseptert som et viktig verktøy i matematikken. Kronecker har gitt viktige bidrag til mange ulike omr˚ ader av matematikken, spesielt til elliptiske funksjoner, idealteorien, representasjonsteorien og tallteorien. 4. Utvid siste delen av Oppgave 3 til vektorer v der koordinatene ai er valgt fra et vilk˚ arlig4 alfabet b1 , b2 , . . . . 5. La m og n være hele tall slik at 0 ≤ m ≤ n. Betrakt følgende tre tall (1) Antallet forskjellige m˚ ater vi kan velge m ulike tall fra tallenen 1, 2, . . . , n uten ˚ a ta hensyn til rekkefølgen av de m tallene. N˚ ar m = 0 setter vi tallet lik 1. For eksempel n˚ ar n = 3 og m = 2 har vi tre valg {1, 2}, {1, 3} og {2, 3}. (2) Antallet n-vektorer som har m koordinater lik 0, og som har n − m koordinater lik 1. For eksempel n˚ ar n = 3 og m = 2 har vi de tre vektorene (0, 0, 1), (0, 1, 0) og (1, 0, 0). 4
vilk˚ arlig (norsk) = godtycklig
9
(3) Antallet stier fra origo (0, 0)t til (m, n − m)t som følger et rutenett av linjer i planet der linjene er parallelle med x-aksen eller y-aksen og der linjene g˚ ar gjennom punktene (a, b)t der a og b er hele tall. For eksempel om n = 3 og m = 2 har vi
(1) Vis at de tre tallene ovenfor er like. (2) Kall dette tallet Bm,n . Vis at Bm,n = Bm,n−1 +Bm−1,n−1 n˚ ar 0 < m < n. (3) Gi mening til formelen ovenfor n˚ ar 0 = m eller m = n. (4) For hver positivt tall setter vi n! = 1 · 2 · · · n og 0! = 1. Vi kaller tallet n! n! for n-fakultet. Vis at Bm,n = m!(n−m)! . 6. En grafe med n hjørner er en samling av n punkter nummerert med 1, 2, . . . , n og kanter som g˚ ar mellom hjørne nummer p og hjørne nummer q for noen p og q med p 6= q. For eksempel er 3
4 1
1
2
2
3
grafer. Den første har 3 hjørner og tre sider {1, 2}, {1, 3} og {2, 3}. En sti av lengde m fra et hjørne p til et hjørne q er en vektor (p0 , p1 , . . . , pn )t der {pi−1 , pi } er en kant for i = 1, . . . , n og der i0 = p og in = q. Alle stier av lengde 1 i den første grafen er (1, 2)t , (1, 3)t og (2, 3)t , og de av lengde 2 som begynner i hjørne 1 er (1, 2, 1)t , (1, 3, 1)t , (1, 3, 2)t , (1, 2, 3)t . Alle stier av lengde 1 i den andre grafen er (1, 2)t , (2, 3)t , (2, 4)t , (3, 4)t , og de av lengde 2 som begynner i hjørnene 1, 2, eller 3 er (1, 2, 1)t , (1, 2, 3)t , (1, 2, 4)t , (2, 1, 2)t , (2, 3, 2)t , (2, 4, 2)t , (2, 3, 4)t , (2, 4, 3)t , (3, 2, 3)t , (3, 4, 3)t , (3, 2, 4)t , (3, 4, 2)t og (3, 2, 1)t . 10
(1) Kontroller listen av stier av lengde 2 i den første grafen og finn alle stier av lengde 3. (2) Kontroller listen av stier av lengde 2 i den andre grafen og finn alle stier av lengde 3.
11
1.2 1.2.1
Operasjoner p˚ a vektorer Multiplikasjon av en skalar med en vektor
Den første operasjonen vi skal studere er multiplikasjon av et tall, eller skalar som vi ofte sier i denne forbindelse, med en vektor. For eksempel kan vi multiplisere tallet 5 med 2-vektoren (1, 2)t ved ˚ a sette 5(1, 2)t = (5, 10)t . √ Tallet 2 kan vi multiplisere med 3-vektoren (−5, 7, π)t ved ˚ a sette √ √ 2(−5, 7, π)t = (−10, 2 7, 2π)t . Produktet at en skalar med en vektor f˚ ar vi alts˚ a ved ˚ a multiplisere hver koordinat i vektoren med skalaren. Mer generelt kan vi multiplisere et tall a med en 2-vektor (a1 , a2 )t ved ˚ a sette a(a1 , a2 )t = (aa1 , aa2 )t og med en 3-vektor (a1 , a2 , a3 )t ved ˚ a sette a(a1 , a2 , a3 )t = (aa1 , aa2 , aa3 )t . Generelt kan vi definere produktet av et tall med en vektor: Definisjon 1.2.2. Produktet av et tall a og en n-vektor v = (a1 , a2 , . . . , an )t er av = a(a1 , a2 , . . . , an )t = (aa1 , aa2 , . . . , aan )t . Vi multipliserer et tall med en vektor ved ˚ a multiplisere tallet med hver koordinat i vektoren. For enkelhets skyld skriver vi −v = (−1)v = (−1)(a1 , a2 , . . . , an )t = (−a1 , −a2 , . . . , −an )t og 0 = 0v = 0(a1 , a2 , . . . , an )t = (0, 0, . . . , 0)t .
1.2.3
Addisjon av vektorer
Vi kan addere to vektorer ar de er like store. For eksempel, om u = (1, 2)t , √ n˚ t v = (3, −5) og w = (π, 2)t setter vi u + v = (1, 2)t + (3, −5)t = (1 + 3, 2 − 5)t = (4, −3)t , √ √ u + w = (1, 2)t + (π, 2)t = (1 + π, 2 + 2)t og √ √ v + w = (3, −5)t + (π, 2)t = (3 + π, −5 + 2)t . 12
Vi adderer to vektorer ved ˚ a addere hver koordinat i den ene vektoren med den tilsvarende koordinaten i den andre vektoren. Mer generelt definerer vi summen av to 2-vektorer (a1 , a2 )t og (b1 , b2 )t ved (a1 , a2 )t + (b1 , b2 )t = (a1 + b1 , a2 + b2 )t og summen av to 3-vektorer (a1 , a2 , a3 )t og (b1 , b2 , b3 )t ved (a1 , a2 , a3 )t + (b1 , b2 , b3 )t = (a1 + b1 , a2 + b2 , a3 + b3 )t . Generelt kan vi definere summen av to n-vektorer: Definisjon 1.2.4. Summen av to n-vektorer (a1 , a2 , . . . , an )t og (b1 , b2 , . . . , bn )t er (a1 , a2 , . . . , an )t + (b1 , b2 , . . . , bn )t = (a1 + b1 , a2 + b2 , . . . , an + bn )t . Det vil si, vi adderer to vektorer ved ˚ a addere hver koordinat i den ene med den tilsvarende koordinaten i den andre. Regneregler 1.2.5. Multiplikasjon av en vektor med en skalar og addisjon av to vektorer gjør det mulig ˚ a regne med vektorer p˚ a en liknende m˚ ate som regninger med tall. Før vi gir de viktigste regnereglene skal vi innføre en praktisk notasjon som gjør bevisene mer gjennomsiktige. Notasjon 1.2.6. Vi skriver (a1 , a2 , . . . , an )t = (ai )tn . Denne notasjonen gjør at vi kan konsentrere oss om den i’te koordinaten ai . Indeksen n viser at vi har en n-vektor. Med denne notasjonen f˚ ar vi at t multiplikasjon av et tall a med en n-vektor v = (ai )n = (a1 , a2 , . . . , an )t kan skrives som av = a(ai )tn = (aai )tn , og addisjon av v med n-vektoren w = (bi )tn = (b1 , b2 , . . . , bn )t kan skrives som v + w = (ai )tn + (bi )tn = (ai + bi )tn . Proposisjon 1.2.7. La u, v og w være tre n-vektorer. Da gjelder følgende regneregler: (1) u + 0 = 0 + u = u, (2) u + (−u) = (−u) + u = 0, 13
(3) (u + v) + w = u + (v + w), (4) u + v = v + u. Bevis. Alle regnereglene følger av enkle regninger. Vi setter u = (ai )tn , v = (bi )tn og w = (ci )tn . (1) Vi har en sekvens av likheter u + 0 = (ai )tn + (0)tn = (ai + 0)tn = (ai )tn = u. Tilsvarende f˚ ar vi at 0 + u = u. (2) Vi har at u + (−u) = (ai )tn + (−(ai )tn ) = (ai )tn + (−ai )tn = (ai − ai )tn = (0)tn = 0. Tilsvarende f˚ ar vi at (−u) + u = 0. (3) Vi har at (u + v) + w = ((ai )tn + (bi )tn ) + (ci )tn = (ai + bi )tn + (ci )tn = (ai + bi + ci )tn . Tilsvarende f˚ ar vi at u + (v + w) = (ai + bi + ci )tn . (4) Vi har at u+v = (ai )tn +(bi )tn = (ai + bi )tn = (bi + ai )tn = (bi )tn +(ai )tn = v + u.
Terminologi 1.2.8. Vi kaller elementet 0 i (1) i Proposisjon 1.2.7 for det nøytrale element for addisjonen, og elementet −u i (2) for inversen til u. Egenskapen (3) kaller vi assosiativitet av addisjonen og egenskapen (4) kaller vi kommutativitet av addisjonen. Merk 1.2.9. Assosiativiteten (u + v) + w = u + (v + w) viser at det ikke spiller noe rolle i hvilken rekkefølge5 vi adderer tre vektorer. Derfor skriver vi u + v + w = (u + v) + w = u + (v + w). Proposisjon 1.2.10. La a og b være tall og la v og w være n-vektorer. Vi har følgende regneregler: (1) a(v + w) = av + aw, (2) (a + b)v = av + bv, (3) a(bv) = (ab)v, (4) 1v = v. Bevis. Vi skriver v = (ai )tn og w = (bi )tn . Alle regnereglene følger av enkle regninger. 5
rekkefølge = f¨ oljd
14
(1) Vi har en sekvens av likheter a(v +w) = a((ai )tn +(bi )tn ) = a(ai + bi )tn = (a(ai + bi ))tn = (aai + abi )tn = (aai )tn + (abi )tn = a(ai )tn + a(bi )tn = av + aw. (2) Vi har at (a + b)v = (a + b)(ai )tn = ((a + b)ai )tn = (aai + bai )tn = (aai )tn + (bai )tn = a(ai )tn + b(ai )tn = av + bv. (3) Vi har at (ab)v = (ab)(ai )tn = (abai )tn = a(bai )tn = a(b(ai )tn ) = a(bv). (4) Vi har at 1v = 1(ai )tn = (1ai )tn = (ai )tn = v.
Terminologi 1.2.11. Egenskapen (1) i Proposisjon 1.2.10 kaller distributivitet av skalarmultiplikasjon med hensyn til addisjon av vektorer, og egenskapen (2) distributivitet av addisjon av skalarer med hensyn til multiplikasjon med vektorer. Vi kaller egenskapen (3) at multiplikasjon av skalarer med vektorer er assosiativ. Merk 1.2.12. Assosiativiteten a(bv) = (ab)v viser at det ikke spiller noe rolle i hvilken rekkefølge vi multiplisere skalarer med vektorer. Derfor skriver vi abv = a(bv) = (ab)v. Oppgaver 1.2.13. 1. La a = 3 og b = 5. Bestem av + bw n˚ ar (1) v = (1, 2)t og w = (−5, 3)t . (2) v = (1, 2, 3)t og w = (−2, −3, 4)t . (3) v = (1, π, 4)t og w = (−2, −3, 4)t . √ (4) v = (1, π)t og w = ( 2, 1)t . 2. La u = (1, 2, 6)t og v = (−1, 2, 3)t . Bestem au + bv n˚ ar (1) a = 3 og b = 2. (2) a = −1 og b = 7. (3) a = π og b = 1. √ (4) a = 2 og b = −2. 3. Bestem 2-vektoren x slik at v − x = w n˚ ar 15
(1) v = (2, 3)t og w = (5, −4)t . (2) v = (−1, −11)t og w = ( 21 , 13 )t . √ (3) v = (π, 3)t og w = (1, 2)t . (4) v = ( 14 , 15 )t og w = ( 31 , −2)t . 4. Bestem 3-vektoren x slik at v − x = w n˚ ar (1) v = (4, 2, 3)t og w = (5, 2, −4)t . (2) v = (−1, 2, −11)t og w = (6, 12 , 31 )t . √ (3) v = (π, 5, 3)t og w = (−7, 1, 2)t . (4) v = (7, 14 , 51 )t og w = ( 31 , −2, 6)t . 5. La v = (1, 1)t og w = (2, −1)t . Bestem konstanter a og b slik at u = av+bw n˚ ar (1) u = (4, 1)t . (2) u = ( 21 , 2)t . (3) u = (− 31 , 1)t . (4) u = (−1, 5)t . 6. La u = (1, 0, 0)t , v = (1, 1, 0)t og w = (2, 0, −1)t . Bestem konstanter a, b og c slik at x = au + bv + cw n˚ ar (1) x = (1, 4, 1)t . (2) x = ( 21 , −7, 2)t . (3) x = (− 31 , 1, 12 )t . (4) x = (−1, 2, 5)t . 7. I denne oppgaven skal du betrakte en vektor i planet som en pil med gitt retning og lengde. Du skal ogs˚ a betrakte to piler som like om de har samme retning og lengde, men ikke nødvendigvis har samme begynnelsespukt. 16
(1) La u = (a, b)t og v = (c, d)t være 2-vektorer. Vis at u + v er diagonalen i rektangelet som har hjørner i punktene (0, 0)t , (a, b)t og (c, d)t . (a, b)t + (c, d)t
y (c, d)t
(a, b)t x (2) La u = (a, b)t og v = (c, d)t være vektorer. Vis at v − u er vektoren som begynner i (a, b)t og slutter i (c, d)t . y
(c, d)t (c, d)t − (a, b)t (a, b)t x
8. Gjør tilsvarende oppgaver som i Oppgave 7 for 3-dimensjonale vektorer. 9. I denne oppgaven skal du betrakte en 2-vektor v = (a1 , a2 )t som p en vektor med begynnelse i origo (0, 0)t og slutt i (a1 , a2 )t . Vi setter kvk = a21 + a22 og om w = (b1 , b2 )t s˚ a setter vi v · w = a1 b1 + a2 b2 . (1) Vis at kvk er lengden av vektoren v = (a1 , a2 )t . (2) Anta at w ikke er origo (0, 0)t . Vis at den korteste avstanden fra punktet (a1 , a2 )t til linjen L gjennom origo og (b1 , b2 )t er p |v|2 |w|2 − (v · w)2 . |w| Hint. Vi har at alle punktene p˚ a linjen L er p˚ a formen t(b1 , b2 )t for noe t. t Vektoren som begynner i t(b1 , b2 ) og slutter i (a1 , a2 )t er ut = (a1 , a2 )t − t(b1 , b2 )t = (a1 − tb1 , a2 − tb2 )t . Vi vil finne den minste lengden vektoren ut 17
kan ha. Vi f˚ ar |ut |2 = (a1 − tb1 )2 + (a2 − tb2 )2 = a21 + a22 − 2t(a1 b1 + a2 b2 ) + t2 (b21 + b22 ) 2 a1 + a22 a1 b1 + a2 b2 2 2 2 = (b1 + b2 ) − 2t 2 +t b21 + b22 b1 + b22 v·v v·w = (w · w) − 2t + t2 w·w w · w (v · w)2 v·w v·v 2 − + (− + t) . = (w · w) w · w (w · w)2 w·w v·w Av det siste uttrykket ser vi at |ut |2 er minst n˚ ar t = w·w , og at vi da har at avstanden kvadrert er (v · w)2 (v · w)2 v·v − = v · v − . (w · w) w · w (w · w)2 w·w
y
L v·w (b , b )t w·w 1 2
t(b1 , b2 )t ut = (a1 , a2 )t − t(b1 , b2 )t
θ
(a1 , a2 )t x
(1) ”(3)”Anta at v = (a1 , a2 )t og w = (b1 , b2 )t begger er forskjellige fra origo. La θ være den av vinklene mellom L og linjen gjennom origo og (a1 , a2 )t som tilfredsstiller 0 ≤ θ ≤ π. Vis at cos θ =
v·w . |v||w|
Hint. For ˚ a vise p˚ astand (3) merker vi at avstanden mellom punktene (a1 , a2 )t v·w og w·w (b1 , b2 ) er den minste avstanden mellom (a1 , a2 )t og linjen L. Derfor v·w vil linjen mellom (a1 , a2 )t og w·w (b1 , b2 ) være høyden i trekanten med hjørner t t t (0, 0) , (a1 , a2 ) og (b1 , b2 ) og derfor st˚ a normalt p˚ a L. Det følger at cos θ = v·w v·w t| |(b ,b ) |w| 1 2 v·w w·w = w·w|v| = |v||w| . |(a1 ,a2 )t | 10. Gjør tilsvarende oppgave som Oppgave 9 i tre dimensjoner. 11. For i = 1, 2, . . . , n setter vi ei = (0, 0, . . . , 0, 1, 0, . . . , 0)t der den i’te koordinaten er 1 og alle andre koordinater er 0. 18
(1) Vis at alle n-vektorer v kan skrives som v = a1 e1 + a2 e2 + · · · + an en for noen tall a1 , a2 , . . . , an . (2) Vis at fremstillingen i (1) er entydig, det vil si at om v = a1 e1 + a2 e2 + · · · + an en = b1 e1 + b2 e2 + · · · + bn en , s˚ a er ai = bi for alle i. (3) Vis at p˚ astanden i (2) er det samme som ˚ a p˚ ast˚ a at om a1 e1 + a2 e2 + · · · + an en = 0, s˚ a er ai = 0 for alle i.
19
1.3
Matriser
Innledning 1.3.1. En matrise er en rektangulær oppstilling av tall. Ordet matrise er avledet av det latinske ordet for livmor. Det var James Joseph Sylvester (1814-1897) som innførte ordet, og brukte det i betydningen av noe som frembringer noe annet, i dette tilfellet determinanter. Determinanter skal vi behandle senere, men historisk kom de før matrisene. Sylvester er mest kjent for sitt arbeide med invariantteorien. Han var en meget allsidig person, blandt annet var han poet. Kanskje det er derfor han er ogs˚ a kjent for ˚ a ha gitt navn til en rekke viktige matematiske begreper. Hver tabell er en matrise. En TV- eller dataskjerm er ogs˚ a en matrise. Slike skjermer best˚ ar av et rektangulært nettverk av punkter der antallet punkter per kvadratsentimeter bestemmer kvaliteten p˚ a bildet. Hvert punkt kan gies en viss gr˚ a- eller faregtone og det er disse gr˚ a eller fargete prikkene som utgjør bildet. Fargen eller gr˚ atonen kan beskrives av et tall. Bildet p˚ a en dataskjerm representeres derfor av en matrise, som for de beste skjermene kan ha imponerende størrelse. Rørlige bilder fremkommer ved at matrisen endrer seg. Hver gang vi ser bilder eller tekst p˚ a en TV-skjerm som speiles, vries, vikles ut, eller forsvinner ut i uendeligheten er det en sekvens av enkle matematiske operasjoner som utføres i rask rekkefølge p˚ a den matrisen som i hvert øyeblikk representerer skjermen. I likhet med vektorer er det ikke matrisen i seg selv som er interessant, men de operasjonene vi kan utføre p˚ a den. Som for vektorer kan vi multiplisere matriser med skalarer og legge sammen to matriser om de har samme størrelse. Den mest fascinerende, komplekse, og mest anvendbare operasjonen er imidlertid multiplikasjon av matriser. Multiplikasjonen kommer inn overalt i matematikken og dens anvendelser. Den kan iblandt virke mystisk og helt umotivert, men vi skal vise at den har en naturlig forklaring.
1.3.2
Eksempler p˚ a matriser
De matrisene vi skal se nærmere p˚ a er rektangulære oppstillinger av tall. Eksempler p˚ a slike oppstillinger er √ 5 −2 π − 5 , ( 32 −1 , 1−π 7 4 ), 1 0 som alle er 2 × 2-matriser. Andre eksempler er √ 3 2 −1 , 4π ( 32 −1 ) , 4 7 2 π−6 5 som er 2 × 3-matriser og 2 −1 3 3 4 7 5 1 6
,
√ 4π 2 −7 , √2 π−6 5 2π 4 0
20
som er 3 × 3-matriser. En vilk˚ arlig 2 × 2-matrise skriver vi ( aa11 21
a12 a22
),
der a11 , a12 , a21 , a22 er tall. Tilsvarende skriver vi ( aa11 21
a12 a13 a22 a23
)
for en vilk˚ arlig 2 × 3-matrise og a11
a12 a13 a21 a22 a23 a31 a32 a33
for en 3 × 3-matrise, der alle aij ’ene er tall. Generelt kan vi definere m × n-matriser for alle hele positive tall m og n: Definisjon 1.3.3. La m og n være hele positive tall. En m × n-matrise er en oppstilling a11 a12 . . . a1n a21 a22 . . . a2n A = .. .. .. . . . am1 am2 . . . amn der alle aij ’ene er tall. Vi kaller vektoren
a1j a2j .. = (a1j , a2j , . . . , amj )t .
amj den j’te søylen til matrisen A og matrisen (ai1 , ai2 , . . . , ain ) for den i’te rekken til A. Tallet aij , det vil si tallet som st˚ ar i i’te rekke og j’te søyle, kaller vi den (i, j)’te koordinaten til A. Merk 1.3.4. En m × 1-matrise er det samme om en m-vektor. Notasjon 1.3.5. Det inng˚ ar mange symboler i en matrise og den tar stor plass. Derfor finnes det flere ulike m˚ ater for ˚ a forenkle notasjonen. Det er vanlig ˚ a forenkle skrivem˚ aten ved ˚ a skrive færre koordinater som i a11 . . . a1n .. A = ... . am1 . . . 21
amn
p˚ a samme m˚ ate som vi kan skrive en n-vektor som (a1 , . . . , an )t . Ennu enklere er det ˚ a skrive A = (aij )m,n , der m og n er antallet rekker, respektive søyler, og aij er den (i, j)’te koordinaten. Denne notasjonen, som vi ofte skal bruke nedenfor, svarer helt til notasjonen (ai )tn for n-vektorer.
1.3.6
Multiplikasjon av en skalar med en matrise
Multiplikasjon av en skalar med en matrise er helt analog med multiplikasjon av en skalar med en vektor. For eksempel kan vi multiplisere tallet 5 med 2 × 2-matrisen ( 12 −4 a sette 3 ) ved ˚ 5 −20 5 ( 12 −4 3 ) = ( 10 15 ) , √ 7 π og tallet 2 med 2 × 3-matrisen −5 ved ˚ a sette 2 −3 0 √ √ 7 π = −10 2 7 2π . 2 −5 2 3 0 4 6 0
Vi multipliserer en skalar med en matrise ved ˚ a multiplisere skalaren med hver koordinat i matrisen. Mer generelt kan vi definere multiplikasjon av et tall a med 2 × 2-matrisen 11 a12 ( aa21 a sette a22 ) ved ˚ a12 aa11 aa12 a ( aa11 21 a22 ) = ( aa21 aa22 ) , og med 2 × 3-matrisen ( aa11 21
a12 a13 a22 a23
11 a ( aa21
) ved ˚ a sette
a12 a13 a22 a23
aa11 ) = ( aa 21
aa12 aa13 aa22 aa23
).
Generelt kan vi definere produktet en av skalar med en m × n-matrise: Definisjon 1.3.7. La a være et tall og la A = (aij )m,n være en m×n-matrise. Produktet av a med A er a11 a12 . . . a1n aa11 aa12 . . . aa1n a21 a22 . . . a2n aa21 aa22 . . . aa2n aA = a .. .. .. = .. .. .. . . . . . . . aam1 aam2 . . . aamn am1 am2 . . . amn Vi multipliserer en skalar med en matrise ved ˚ a multiplisere skalaren med hver koordinat i matrisen. Med v˚ ar forenklete notasjon kan vi skrive dette som aA = a(aij )m,n = (aaij )m,n . Vi skriver −A = (−1)A = (−1)(aij )m,n = (−aij )m,n og 0 = 0A = 0(aij )m,n = (0aij )m,n = (0)m,n . 22
1.3.8
Addisjon av matriser
Tilsvarende addisjon av vektorer kan vi addere matriser om de har samme størrelse. For eksempel, om vi har tre 2 × 2-matriser √ 1 2 −3 4,
5 4 6 −7,
π 5 0 1−π
s˚ a setter vi 1 2 5 4 6 6 ( −3 4 ) + ( 6 −7 ) = ( 3 −3 ) (,
og 4 ( 56 −7 )+
1 2 −3 4 )
√ π 5 0 1−π
=
+
√ 5 π 0 1−π
=
√ 1+π 2+ 5 −3 5−π
√ 5+π 4+ 5 . 6 −6+π
P˚ a samme m˚ ate kan vi addere 2 × 3-matriser ved ˚ a sette √ √ 1 2 3 3 −7 −1 4 −5 2 1 2 3 1+π 2+ 2 14 . π 2 11 ) + = ( −3 ) + ( ) = ( ) og ( −3 4 6 4 6 11 2 4 8 6 10 0 1−π 7 −3 5−π 13 Vi adderer alts˚ a to matriser ved ˚ a addere hver koordinat i den ene matrisen med den tilsvarende koordinaten i den andre matrisen. Mer generelt kan vi a11 a12 b11 b12 addere to 2 × 2-matriser ( a21 a22 ) og b21 b22 ved ˚ a sette 11 ( aa21
a12 a22
)+
b11 b12 b21 b22
=
og vi kan addere to 2 × 3-matriser ( aa11 21 11 ( aa21
a12 a13 a22 a23
)+
b11 b12 b13 b21 b22 b23
a11 +b11 a12 +b12 a21 +b21 a22 +b22
a12 a13 a22 a23
=
) og
,
b11 b12 b13 b21 b22 b23
a11 +b11 a12 +b12 a13 +b13 a21 +b21 a22 +b22 a23 +b23
ved ˚ a sette
.
Generelt kan vi definere summen av to m × n-matriser: Definisjon 1.3.9. La A = (aij )m,n og B = (bij )m,n være to m × n-matriser. Summen av A og B er: a11 a12 . . . a1n b11 b12 . . . b1n a21 a22 . . . a2n b21 b22 . . . b2n A + B = .. .. .. + .. .. .. . . . . . . am1 am2 . . . amn . bm1 bm2 . . . bmn . a11 + b11 a12 + b12 . . . a1n + b1n a21 + b21 a22 + b22 . . . a2n + b2n = . .. .. .. . . . am1 + bm1 am2 + bm2 . . . amn + bmn . 23
Vi adderer to matriser ved ˚ a addere hver koordinat i den ene matrisen med den tilsvarende koordinaten i den andre matrisen. I den forenklete notasjonen kan dette skrives A + B = (aij )m,n + (bij )m,n = (aij + bij )m,n . Oppgaver 1.3.10. 1. La a = 2 og b = 7. Regn ut aA + bB n˚ ar 0 −1 (1) A = ( 37 −1 3 ), B = −1 0 . √ 4 . (2) A = π3 √17 , B = 1−π 2 0 3 −2 0 −1 0 4
(3) A = (4) A =
, B = ( 51 22 13 ). −1 −7 3 10 1 ,B= 2 1 4 .
1 1 4 −7 −2 −3 −1
−3 −1
2 −7 2
2. La A =
1
1
0 2
3 , B = ( 42 −1 ar 0 4 ). Beregn aA + bB n˚
(1) a = 3, b = −1. (2) a = −1, b = 0. (3) a = 7, b = −2. √ (4) a = π, b = 2. 3. Bestem 2 × 2-matrisen X slik at A − X = B n˚ ar 2 3 5 −4 (1) A = ( −1 2 ) og B = ( 3 2 ). 0 −2 1 −5 (2) A = −7 og B = −2 . 3 3 1 1 5 −4 2 3 1 1 og B = (3) A = −1 . 2 3 2 2π √ 3 − 2 2
(4) A =
og B =
5π −4 √ 3 2
.
4. Bestem 3 × 2-matrisen X slik at A − X = B n˚ ar 5 2 −4 (1) A = ( 41 22 34 ) og B = −1 −2 −3 . 6 12 13 −1 2 −11 (2) A = ( 2 6 3 ) og B = −3 −2 −1 . (3) A =
π 5 3 2 3 4 3 4 5
og B =
√ −7 √1 2 . π 4 −5
24
(4) A =
7 3
1 4 3 2
1 5 1 7
og B =
1 3 2 3
−2 6 1 −1 4
.
5. N˚ ar det gjelder skalar multiplikasjon og addisjon oppfører matriser seg som vektorer. Til en m × n-matrise A = (aij )m,n tilordner vi (mn)-vektoren vA = (a11 , a12 , . . . , a1n , a21 , a22 , . . . , a2n , . . . , am1 , am2 , . . . , amn )t . (1) Vis at for alle m × n-matriser A og B og skalarer a og b har vi at v(aA+bB) = avA + bvB . (2) La eij være m × n-matrisen med (i, j)’te koordinat lik 1 og alle andre koordinater lik 0. Vis at hver m × n-matrise A kan skrives p˚ a formen A = a11 e11 + a12 e12 + · · · + a1n e1n + a21 e21 + a22 e22 + · · · + a2n e2n + · · · + am1 em1 + am2 em2 + · · · + amn emn der a11 , a12 , . . . , a1n , a21 , a22 , . . . , a2n , . . . , am1 , am2 , . . . , amn er tall som er entydig bestemte. 6. En grafe med n-hjørner er en samling av n punkter nummerert med 1, 2, . . . , n og kanter som g˚ ar mellom noen av hjørnene p og q med p 6= q. Se Oppgave 6, Seksjon 1.1. Vis at en grafe med n-hjørner svarer til n×n-matriser med koordinater 0 eller 1, og med 0 p˚ a diagonalen. Hint. Sett (p, q)’te koordinaten i n × n-matrisen lik 1 om det finnes en kant mellom p og q, og la alle andre koordinater være 0. For eksempel er 0 1 0 0 0 1 1 1 0 1 respektive 1 0 1 1 0 1 0 1 1 1 0 0 1 1 0 matrisene som svarer til figurene i Oppgave 6, Seksjon 1.1. Hvordan vi skal tilordne en grafe til en n × n-matrise med 0’er og 1’ere som koordinater, og 0 p˚ a diagonalen er nu klart.
25
1.4 1.4.1
Matrisemultiplikasjon Multiplikasjon av en matrise med en vektor
Neste m˚ alsetning er ˚ a definere multiplikasjon av matriser. Vi forbereder oss for dette ved ˚ a betrakte spesialtilfellet der vi multipliserer en matrise med en vektor. t 1 2 Vi multipliserer 2 × 2-matrisen ( −4 a sette 5 ) med 2-vektoren (7, 3) ved ˚ 1·7+2·3 13 1 2 7 ( −4 5 ) ( 3 ) = −4·7+5·3 = ( −13 ) og 2 × 3-matrisen
π √7 3 −1 2 5
π √7 3 −1 2 5
4 −1 6
med 3-vektoren (4, −1, 6)t ved ˚ a sette
=
π4+7(−1)+3·6 √ (−1)4+ 2(−1)+5·6
=
4π+11 √ 26− 2
.
Multiplikasjon av en matrise med en vektor v er bare mulig om matrisen har like mange søyler som v har koordinater. Resultatet er en vektor med like mange koordinater som matrisen har rekker, og i’te koordinaten i denne vektoren er summen av koordinatene i v multiplisert med de tilsvarende koordinatene i i’te rekke i matrisen. Mer generelt multipliserer vi en 2 × 2matrise med 2-vektoren ved ˚ a sette: a1 a11 a1 +a12 a2 11 a12 ( aa21 a22 ) ( a2 ) = a21 a1 +a22 a2 , og en 2 × 3-matrise med 3 vektoren ved ˚ a sette a1 a11 a12 a13 11 a1 +a12 a2 +a13 a3 ( a21 a22 a23 ) aa23 = aa21 a1 +a22 a2 +a23 a3 . Merk 1.4.2. For at det skal være mulig ˚ a multiplisere en matrise med en vektor m˚ a antallet søyler i matrisen være lik antallet koordinater i vektoren. Resultatet er en vektor som har samme antall koordinater som matriser har rekker. Generelt kan vi definere multiplikasjon av en m × n-matrise med en n-vektor: Definisjon 1.4.3. La A = (aij )m,n være en m × n-matrise og v = (ai )tn en n-vektor. Produktet av A med v er a11 a12 . . . a1n a1 a11 a1 + a12 a2 + · · · + a1n an a21 a22 . . . a2n a2 a21 a1 + a22 a2 + · · · + a2n an Av = .. . .. .. .. = .. . . . . . am1 am2 . . . amn . an am1 a1 + am2 a2 + · · · + amn an 26
Produktet av en m×n-matrise A med en n-vektor v gir en m-vektor w og den i’te koordinaten i w f˚ ar vi ved ˚ a multiplisere koordinatene i den i’te rekken i A med de tilsvarende koordinatene i v og ta summen. I den forkortete notasjonen har vi Av = (aij )m,n (ai )tn = (ai1 a1 + ai2 a2 + · · · + ain an )tm . Merk 1.4.4. Resultatet av ˚ a multiplisere en m × n-matrise med en n-vektor er en m-vektor. Regneregler 1.4.5. Vi har mange regneregler for multiplikasjon av en skalar med en matrise og for multiplikasjon av en matrise med en vektor. Før vi gir og beviser de viktigste resultatene innfører vi en enkel notasjon for summer som gjør uttrykkene og regningene mer gjennomskinlige.
1.4.6
Summasjon av indekser
Vi skal ofte h˚ andtere uttrykk p˚ a formen ai1 a1 + ai2 a2 + · · · + ain an . Det er derfor praktisk ˚ a innføre en enkel notasjon for slike summer. Mer generellt skal vi innføre en notasjon for summer av tall. Dette gjøres ved at vi skriver 7 X ai = a3 + a4 + a5 + a6 + a7 , i=3
P P der a3 , a4 , . . . , a7 er tall. Symbolet st˚ ar for sum, og 7i=3 betyr at indeksen i løper fra verdien 3 til verdien 7. Hvilken bokstav vi bruker for indeksen spiller selvsagt ingen rolle s˚ a vi har 7 X
aj = a3 + a4 + a5 + a6 + a7 .
j=3
Med samme notasjon har vi for eksempel 9 X
ai = a1 + a2 + a3 + a4 + a5 + a6 + a7 + a8 + a9
i=1
der alle ai ’ene er tall og 6 X i=1
i 1 2 3 4 5 6 = + + + + + . 2i + 1 3 5 7 9 11 13 27
Vi kan ogs˚ a summere opp til et vilk˚ arlig tall. For eksempel vil n X
i = 1 + 2 + 3 + · · · + n og
i=1
n X
i2i = 1 · 21 + 2 · 22 + 3 · 23 + · · · + n2n .
i=1
Mer generelt har vi at n X
ai = a1 + a2 + · · · + an .
i=1
Med denne hendige notasjonen f˚ ar vi at n X
aij aj = ai1 a1 + ai2 a2 + · · · + ain an .
j=1
Vi kan da uttrykke multiplikasjonen av matrisen A = (aij )m,n med vektoren v = (ai )tn p˚ a den kompakte formen Av = (aij )m,n (ai )tn = (
n X
aij aj )tm .
j=1
P Merk at i uttrykket ( nj=1 aij aj )tm er j en summasjonsindeks mens i er fast og betegner den i’te koordinaten. Vi skal mange ganger ha bruk for likhetene m X i=1
ai
n X
bj =
j=1
m X n X
ai b j =
n X m X j=1 i=1
i=1 j=1
bj ai =
n X j=1
bj
m X
ai .
i=1
De er alle lik summen a1 b1 +a1 b2 +· · ·+a1 bn +a2 b1 +a2 b2 +· · ·+a2 bn +· · ·+am b1 +am b2 +· · ·+am bn . Proposisjon 1.4.7. La a være et tall og v og w to n-vektorer. Videre, la A være en m × n-matrise. Da har vi at (1) A(av) = (aA)v. (2) A(v + w) = Av + Aw. Bevis. Sett v = (ai )tn , w = (bi )tn og A = (aij )m,n . Da har vi at (aA)v = (aaij )m,n (ai )tn = (
n X
aaij aj )tm = (
j=1
n X j=1
28
aij (aaj ))tm = (aij )m,n (aai )tn = A(av).
Videre har vi at A(v + w) =
(aij )m,n ((ai )tn
+
(bi )tn )
= (aij )m,n (ai +
bi )tn
=(
n X
aij (aj + bj ))tm
j=1
=(
n X
aij aj +
j=1
=
1.4.8
(aij )m,n (ai )tn
n X
aij bj )tm = (
n X
j=1
+
aij aj )tm + (
j=1
(aij )m,n (bi )tn
n X
aij bj )tm
j=1
= Av + Aw.
Multiplikasjon av matriser
Vi er nu klare til ˚ a definere multiplikasjon av matriser. Som vanlig begynner vi med noen eksempler som illustrer hva som hender. Vi multipliserer 2 × 25 4 matrisene ( 17 −2 a sette: 3 ) og ( −1 2 ) ved ˚ 1·5+(−2)(−1) 1·4+(−2)2 1 −2 5 4 7 0 ) ( 7 3 ) ( −1 2 ) = = ( 32 34 7·5+3(−1) 7·4+3·2 5 4 √π og produktet av 2 × 2-matrisen ( 71 −2 3 ) med 2 × 3-matrisen −1 2 5 ved 1·5+(−2)(−1) 1·4+(−2)2 1π−2√5 7 0 π−2√5 5 4 √π √ ( 17 −2 ) = 32 34 7π+3√5 . 3 −1 2 5 = 7·5+3(−1) 7·4+3·2 7π+3 5 1 2 −2 Videre kan vi multiplisere 3×2-matrisen −2 5 med 2×3-matrisen ( 03 −1 2 4 ) 0 −1 ved 1 2 1·3+2·0 1(−1)+2·2 1(−2)+2·4 3 3 6 3 −1 −2 −2 5 ( 0 2 4 ) = (−2)·3+5·0 (−2)(−1)+5·2 (−2)(−2)+5·4 = −1 12 24 . 0 −1
0·3+(−1)0 0(−1)+(−1)2 0(−2)+(−1)4
0 −2 −4
Vi kan bare multiplisere to matriser om den første har like mange søyler som den andre har rekker. Resultatet er en matrise med like mange rekker som den første matrisen og like mange søyler som den andre. Den (i, j)’te koordinaten f˚ ar vi ved ˚ a multiplisere koordinatene i den i’te rekken i første matrisen med de tilsvarende koordinatene i den j’te søylen i den andre matrisen og summere. Mer generelt definerer vi produktet av to 2 × 2-matriser ved b11 b12 a11 b11 +a12 b21 a11 b12 +a12 b22 11 a12 ( aa21 a22 ) b21 b22 = a21 b11 +a22 b21 a21 b12 +a22 b22 , og av 2 × 2-matrisen med en 2 × 3-matrise ved b11 b12 b13 a11 b11 +a12 b21 a11 b12 +a12 b22 11 a12 ( aa21 a22 ) b21 b22 b23 = a21 b11 +a22 b21 a21 b12 +a22 b22
a11 b13 +a12 b23 a21 b13 +a22 b23
.
I hvert av tilfellene fremkommer produktet AB ved at vi tar i’te søyle i B og betrakter den som en vektor (b1i , b2i , . . . , bni )t . Denne søylen multipliserer vi med A og f˚ ar den i’te søylen A(b1i , b2i , . . . , bni )t . 29
Merk 1.4.9. Vi ser at at multiplikasjonen ovenfor bare er mulig n˚ ar antallet søyler i den første matrisen er lik antallet rekker i den andre, og at resultatet er en matrise med samme antall rekker som den første matrisen og samme antall søyler som den andre matrisen. Generelt definerer vi produktet av en m × n-matrixe A med en n × p-matrise B ved ˚ a la den i’te søylen i produktet AB være produktet av matrisen A med den i’te søylen i B. Med andre ord, vi f˚ ar i’te søyle i AB ved ˚ a betrakte i’te søyle i B som en vektor (b1i , b2i , . . . , bmi )t og ta produktet A(b1i , b2i , . . . , bmi )t . Matriseprodukt er derfor det samme som p vektorprodukter. Mer presist har vi: Definisjon 1.4.10. La A = (aij )m,n være en m × n-matrise og B = (bij )n,p en n × p-matrise. Produktet av A og B er b11 b12 . . . b1p a11 a12 . . . a1n a21 a22 . . . a2n b21 b22 . . . b2p AB = .. .. .. .. .. .. . . . . . . bn1 bn2 . . . bnp am1 am2 . . . amn a11 b11 + a12 b21 + · · · + a1n bn1 . . . a11 b1p + a12 b2p + · · · + a1n bnp a21 b11 + a22 b21 + · · · + a2n bn1 . . . a21 b1p + a22 b2p + · · · + a2n bnp = . .. .. . . am1 b11 + am2 b21 + · · · + amn bn1 . . . am1 b1p + am2 b2p + · · · + amn bnp I forenklet notasjon f˚ ar vi AB = (aij )m,n (bij )n,p =
X n k=1
aik bkj
. m,p
Sammenliknet med ˚ a skrive ut hele matrisen er uttrykket i forenklet notasjon et under av enkelhet. Merk 1.4.11. Resultatet av ˚ a multiplisere en m × n-matrise med en n × pmatrise er en m × p-matrise. N˚ ar p = 1 f˚ ar vi multiplikasjon av en matrise med en vektor, slik vi har definert den ovenfor. Regneregler 1.4.12. Det finnes mange regneregler for multiplikasjon av en skalar med en matrise, og for addisjon og multiplikasjon av matriser. De fleste regnereglene for skalarmultiplikasjon og addisjon er analoge med de som gjelder for vektorer. Lengre frem skal vi vise at følgende regel er en konsekvens av at vi kan tolke matriser som avbildninger. Vi tar med et bevis her for ˚ a f˚ a trening p˚ a˚ a regne med matriser. 30
Proposisjon 1.4.13. La A være en m × n-matrise, B en n × p-matrise og C en p × q-matrise. Da har vi (AB)C = A(BC). Bevis. Vi Pnsetter A = (aij )m,n , B = (bij )n,p og C = (cij )p,q . Da har vi at AB = ( k=1 aik bkj )m,n . Derfor vil (AB)C =
X p n X l=1
=
aik bkl clj
X p n X
m,q
k=1
A(BC) =
aik
k=1
X p
=
bkl clj
l=1 bkl clj )n,q
l=1 k=1
.
aik bkl clj m,q
k=1 l=1
k=1 l=1
og f˚ ar
Likheten i Proposisjonen følger av at X X p p n X n X aik bkl clj = aik bkl clj m,q
. m,q
Pp
X p n X
m,q
l=1
aik bkl clj
l=1 k=1
P˚ a den andre siden kan vi begynne med BC = ( X n
. m,q
Terminologi 1.4.14. Likheten (AB)C = A(BC) viser at multiplikasjon av matriser er uavhengig av rekkefølgen av multiplikasjonen. Vi sier at multiplikasjon av matriser er assosiativ og skriver ABC = (AB)C = A(BC). Merk 1.4.15. Vi har at ( 10 11 ) ( 11 01 ) = ( 21 11 ) , men ( 11 01 ) ( 10 11 ) = ( 11 12 ) . Matrisemultiplikasjon er derfor avhengig av ordenen av faktorene. Vi sier at matrisemultiplikasjon ikke er kommutativ. Dette skiller matrisemultiplikasjonen fra de andre regnereglene vi har støtt p˚ a og gjør den spesielt interessant. Oppgaver 1.4.16. −3 7 1. La A = ( 53 −2 ar 1 ) og B = ( 2 0 ). Regn ut Av + Bv n˚
(1) v = (2, −3)t (2) v = (5, 4)t 31
(3) v = (π,
√
2)t .
2. La v = (−1, 2)t og w = (5, −3)t . Regn ut Av + Aw n˚ ar (1) A = ( 53 −2 1 ) 3 (2) A = ( 74 −5 ) √ (3) A = π1 −15 .
3. La A = ( 53 −2 1 ). (1) Regn ut AB og BA n˚ ar (a) B = ( 43 −1 2 ) (b) B = ( π6 −1 2 ) √ (c) B = −12 10 . (2) Regn ut AB n˚ ar 0 (a) B = ( 43 −1 2 1) √ √2 . (b) B = π0 −1 2 5
(3) Regn ut BA n˚ ar 4 −1 (a) B = 3 2 0 1 π −1 (b) B = √0 √2 . 2
5
4. Regn ut 1 2 1 2 3 (1) 3 4 ( −2 −3 −4 ) 5 6
1 2 3 (2) ( −2 −3 −4 )
1 2 3 4 5 6
.
5. Kan du finne en 2 × 2-matrise X slik at AX = ( 10 01 ) n˚ ar (1) A = ( 10 21 ). 2 (2) A = ( −3 0 2 ).
(3) A = ( 17 00 ). 32
(4) A = ( 54 02 ). Regn ut XA n˚ ar X finnes. a11 a12 ··· a1n a21 a22 ··· a2n
6. La A = t
a11 a21 a12 a22
.. .
!
.. .
være en m × n-matrise. Vi danner en matrise
am1 am2!··· amn ··· am1 ··· am2
.. .. ved ˚ a la radene i A bli søylene i At . Matrisen At er en . . a1n a2n ··· anm n × m-matrise som kalles den transponerte til matrisen A. Vis at for alle m×n-matriser A og n×p matriser B s˚ a har vi at (AB)t = B t At .
A =
7. La
0 ... 0 1 . . . 0 .. . . .. . . . 0 0 ... 1
1 0 In = .. .
være matrisen med 1 p˚ a diagonalen og alle andre koordinatene lik 0. En elementær operasjon p˚ a en matriser er en av følgende: (1) Multiplikasjon av en rad med et ikke null tall. (2) Multiplikasjon av en rad med et tall og addisjon av denne raden til en annen rad. (3) Ombytte av to rader. 11 a12 For eksempel for matrisen ( aa21 ar vi ved elementære operasjoner de tre a22 ) f˚ matrisene a11 a12 a11 a12 a21 a22 ( aa 21 aa22 ) , ( a21 +aa11 a22 +a12 ) og ( a11 a12 ) .
En elementær n × n-matrise er en matrise som vi f˚ ar fra In ved en av de tre elementære operasjonene. Vis at du kan utføre en elementær operasjon p˚ a en m × n-matrise A ved ˚ a utføre samme operasjon p˚ a Im slik at du f˚ ar en elementær matrise E og deretter ta produktet EA. 8. La I3 = A(123) = A(231) =
1 0 0 0 1 0 0 0 1
0 0 1 1 0 0 0 1 0
,
,
A(132) = A(312) =
1 0 0 0 0 1 0 1 0
0 1 0 0 0 1 1 0 0
,
,
A(213) = A(321) =
0 1 0 1 0 0 0 0 1
0 0 1 0 1 0 1 0 0
,
.
(1) For hver av matrisene Aσ , finn en matrise Aτ slik at Aσ Aτ = Aτ Aσ = I3 . 33
(2) Regn ut (a) A(312) A(231) (b) A(231) A(312) . (3) Vi vil studere omflytninger, eller som vi sier permutasjoner, av tallene 1, 2, 3. Det finnes 6 slike permutasjoner I = B(123) = ( 11 22 33 ) , B(231) = ( 12 23 31 ) ,
B(132) = ( 11 23 32 )
B(312) = ( 13 21 32 ) ,
B(213) = ( 12 21 33 ) B(321) = ( 13 22 31 ) .
Her betyr B(312) = ( 13 21 32 ) at vi flytter 1 til 3, 2 til 1 og 3 til 2. Mer 1 2 3 generelt s˚ a betyr Bσ = σ(1) σ(2) σ(3) at vi flytter i til σ(i) for i = 1, 2, 3. Vi kan multiplisere permutasjoner ved at Bσ Bτ betyr at vi først utfører permutasjonen τ og deretter σ. For eksempel har vi B(132) B(213) = ( 11 23 32 ) ( 12 21 33 ) = ( 13 21 32 ) = B(312) og B(213) B(132) = ( 12 21 33 ) ( 11 23 32 ) = ( 12 23 31 ) = B(231) . Regn ut (a) B(312) B(231) (b) B(231) B(312) . (4) For hver permutasjon Bσ , finn en Bτ slik at Bσ Bτ = Bτ Bσ = I. (5) Sammenlikn resultatene i del (1) med de i del (4), og de i del (2) med de i del (3). Kan du forklare likhetene? 9. Generaliser det du har vist i Oppgave 8 til n×n-matriser og permutasjoner av tallene 1, 2, . . . , n. Hint. Det kan være praktisk ˚ a introdusere Kroneckers delta δij som tar verdien ar i = j og verdien 0 n˚ ar i 6= j. Til en permutasjon 1 n˚ 1 2 ... n Bσ = σ(1) av 1, 2, . . . , n svarer da n×n-matrisen Aσ = (δiσ(j) )n,n . σ(2) ... σ(n) 10. I denne Oppgaven kaller vi matriser p˚ a formen a b −b a
for komplekse tall. Sett 0 1 I2 = ( 10 01 ) og i = ( −1 0).
for hvert tall a setter vi a = aI2 = ( a0 a0 ) . 34
(1) Vis at hver kompleks tall kan skrives entydig p˚ a formen a + bi. (2) Vis at om u = a + bi, v = c + di og w = e + f i er komplekse tall s˚ a har vi (a) 0 + u = u + 0 = u. (b) u + (−u) = (−u) + u = 0. (c) (u + v) + w = u + (v + w). (d) u + v = v + u. (3) Vis at om u = a + bi, v = c + di og w = e + f i er komplekse tall s˚ a har vi (a) 1u = u1 = u. (b) Det finnes et komplekst tall u−1 slik at uu−1 = u−1 u = 1, n˚ ar u 6= 0. (c) (uv)w = u(vw). (d) uv = vu. (4) Vis at om u = a + bi, v = c + di og w = e + f i er komplekse tall s˚ a har vi (a) u(v + w) = uv + uw. Ettersom de komplekse tallene tilfredsstiller (2) (a), (b), (c), (d) og (3) (a), (b), (c), (d) samt (4), sier vi at de danner en kropp. 11. I denne oppgaven kaller vi matriser p˚ a formen a b −c −d −b a d −c c −d a −b . d c b a for kvaternioner. Disse er meget viktig b˚ ade i matematikk og fysikk. De ble oppdaget i 1843 av William Rowan Hamilton (1805-1865), det sies da han gikk over en bro i Dublin. Han ble s˚ a begeistret over kvaternionene at han brukte en stor del av livet p˚ a˚ a studere dem. Hamilton har gjort store innsatser i matematikken og har ogs˚ a bidratt vesentlig til mekanikken. Han var br˚ amoden og ble allerede i 1827 Royal Astronomer of Ireland, en stilling han beholdt hele livet. 35
Sett
1 0 0 0 1 0 I4 = 0 0 1 0 0 0 0 0 −1 0 0 0 j= 1 0 0 0 1 0
0 0 −1 0 , i= 0 0 0 1 0 0 0 −1 , k = 0 0 1 0
0 0 0 0 , 0 −1 1 0 0 0 −1 0 1 0 . −1 0 0 0 0 0
1 0 0 0
For hvert tall setter vi
0 ... 0 a . . . 0 .. . . .. . . . . 0 0 ... a
a 0 a = aI4 = .. .
(1) Vis at hver kvaternion kan skrives entydig p˚ a formen a + bi + cj + dk. (2) Vis at vi har multiplikasjonstabellen · 1 i j k
1 1 i j k
i i −1 −k j
j k j k k −j −1 i −i 1
der (i, j)’te koordinaten i tabellen er produktet av tallet til venstre for i’te rekke og tallet over j’te søyle. (3) Kan du vise at kvaternionene har egenskapene (2) (a), (b), (c), (d) og (3) (a), (b), (c), samt (4) i Oppgave 10 men ikke betingelsen uv = vu? Ettersom kvaternionene tilfredsstiller betingelsene (2) (a), (b), (c), (d) og (3) (a), (b), (c), samt (4) i Oppgave 10 kaller vi dem en skjevkropp. 12. Vi sier at en n × n-matrise A = (aij )n er symmetrisk om aij = aji for alle i og j. Matrisen A er skjevsymmetrisk om aij = −aji og aii = 0 for alle i og j. Videre sier vi at matrisen er øvre triangulær om aij = 0 for alle j > i og at den er nilpotent om aij = 0 for alle j ≥ i. (1) Vis at om A og B er symmetriske s˚ a er A + B symmetrisk. (2) Vis at om A og B er skjevsymmetriske s˚ a er A + B skjevsymmetrisk. (3) Vis at om A og B er triangulære s˚ a er AB triangulær. 36
(4) Vis at om A og B er nilpotent s˚ a er AB nilpotent. (5) Vis at om A er nilpotent s˚ a er An = 0. 13. La A11 , A12 , A21 og A22 være henholdsvis r × p-, r × q-, s × p- og s × qmatriser, og la B11 , B12 , B21 og B22 være henholdsvis p × t-, p × s-, q × t- og q × s-matriser. Vis at B11 B12 A11 A12 A11 B11 +A12 B21 A11 B12 +A12 B22 = A21 A22 B21 B22 A21 B11 +A22 B21 A21 B12 +A22 B22 , der vi har delt opp matrisene i blokker. 14. En grafe med n-hjørner er en samling av n punkter nummerert med 1, 2, . . . , n og kanter som g˚ ar mellom noen hjørner p og q der p 6= q. Se Oppgave 6, Seksjon 1.1. I Oppgave 6, Seksjon 1.3 s˚ a vi hvordan vi at grafer tilsvarer n × n-matriser med bare nuller og enere som koordinater, og med nuller p˚ a diagonalen. (1) Vis at (p, q)’te koordinaten i a og A2 gir antallet stier av lengde 1 respektive 2 mellom p og q. Sammenlikn med resultatene i Oppgave 6, Seksjon 1.1. (2) Vis at (p, q)’te koordinaten i A3 og A4 gir antallet stier av lengde 3 respektive 4 mellom p og q. Sammenlikn med resultatet i Oppgave 6, Seksjon 1.1. (3) Vis at (p, q)’te koordinaten i An gir antallet stier av lengde n mellom p og q.
37
1.5
Avbildninger av planet
Innledning 1.5.1. N˚ ar vi ser tekst og bilder som vries, vendes, speiles, forstørres eller forminskes p˚ a televisjonen eller p˚ a en dataskjerm, s˚ a betrakter vi et fascinerende eksempel p˚ a anvendt matematikk. Bevegelsen fremkommer ved et enormt antall matrisemultiplikasjoner som blir utført i rask rekkefølge p˚ a punktene i planet som svarer til punktene p˚ a billedskjermen. Her skal vi i detalj vise hvordan slike operasjoner fremkommer. En leser med litt kunnskap til datorer kan uten vanskeligheter bruke teorien til ˚ a bevege bilder og tekst p˚ a sin egen dataskjerm. For enkelhets skyld holder vi oss til plane bilder. Vil vi ta hensyn til perspektivet i bildene m˚ a vi gjøre de tilsvarende operasjonene i rommet. En leser som har forst˚ att materialet i dette kapitlet skulle ikke ha noen vanskeligheter med ˚ a generalisere materialet til tre dimensjoner.
1.5.2
Speilinger
0 ). For hvert punkt (a, b)t i planet kan vi multiplisere den tilsvaLa A = ( 10 −1 a 0 rende vektoren med matrisen og f˚ ar et nytt punkt ( 10 −1 ) ( ab ) = ( −b ). Mat trisemultiplikasjonen flytter alts˚ a punktet (a, b) til punktet (a, −b)t . Dette 0 er en speiling av punktet i x-aksen. Tilsvarende vil matrisen ( −1 0 1 ) speile a −a 0 punktet (a, b)t i y-aksen til ( −1 0 1 ) ( b ) = ( b ). Bruker vi istedenfor matrisen −1 0 t flyttes punktet (a, b) til punktet (−a, −b)t ligger symmetrisk om 0 −1 origo. For ˚ a konstruere og analysere operasjoner av planet som er gitt ved 2 × 2matriser er det viktig ˚ a merke at vi kan sette sammen slike flytninger av planet. Om vi, for eksempel, først speiler (a, b)t i x-aksen, det vil si flyta 0 ter den til ( 10 −1 ) ( ab ) = ( −b ), og deretter speiler i y-aksen, det vil si flytter t t −1 0 (a, −b) til ( 0 1 ) (a, −b) = (−a, −b)t , s˚ a er dette det samme som ˚ a bruke −1 0 t −1 0 1 0 a punktet (a, b) . Sammensetning produktmatrisen ( 0 1 ) ( 0 −1 ) = 0 −1 p˚ av flytninger f˚ ar vi alts˚ a ved ˚ a multiplisere matriser. I dette tilfellet er sammensetningen en flytning symmetrisk om origo. y y y
x
x
x
Iblandt kan sammensetningen av matriser gi overraskende resultater. For 38
eksempel sender matrisen ( 01 10 ) punktet (a, b)t til ( 01 10 ) ( ab ) = ( ab ). Dette 0 er speiling om linjen x = y. Speiler vi først punktet i x-aksen med ( 10 −1 ) t og deretter i linjen x = y f˚ ar vi den sammensatte flytningen av (a, b) til a a 1 0 0 −1 0 1 ( 1 0 ) ( 0 −1 ) ( b ) = ( 1 0 ) ( b ) = ( −b a ). Dette innser vi, med litt ettertanke, er det samme som rotasjon av planet 90 grader. t For ˚ a speile arlig a L med c2 +d2 = 1. i2en2vilk˚ linje L velger vi et punkt (c, d) p˚ −d 2cd Matrisen c 2cd gir da en speiling om linjen L (se Oppgave 2). Dette d2 −c2 stemmer for (1, 0)t , som gir speiling om x-aksen, og for (0, 1)t , som gir speiling om y-aksen.
1.5.3
Strekning og krympning
Matrisen ( 30 01 ) transformerer punktet (a, b)t til ( 30 01 ) ( ab ) = ( 3a a b ). Vi har alts˚ strukket planet i x-retningen med en faktor 3. Tilsvarende strekker matrisen ( 10 03 ) planet 3 ganger i y-retningen og matrisen ( 30 03 ) forstørrer planet 3 ganger. 1 1 1 Matrisen 03 01 sender (a, b)t til 03 01 ( ab ) = 3ba som krymper vektoren 1 0 med en faktor 13 i x-retningen. Tilsvarende krymper matrisen 0 31 planet i 1 0 y-retningen og matrisen 03 1 krymper planet med en faktor 13 . 3
y
y 3:1
1:3
x
x
Generelt vil matrisen ( k0 0l ) strekke eller krympe planet med en faktor k i x-retningen og en faktor l i y-retningen.
1.5.4
Rotasjon
Ovenfor s˚ a vi at matrisen ( 01 −1 0 ) gir en rotasjon 90 grader, og at den er den sammensatte av en speiling i x-aksen med en speiling om linjen x = y. Litt omtanke viser at rotasjon med θ grader er det samme som en speiling om xaksen sammensatt med en speiling om linjen L med stigning 21 θ (se Oppgave 2). Rotasjon θ grader f˚ ar vi derfor av matrisen 2 2 2 2 c +d c −d −2cd 2cd 1 0 ( 0 −1 ) = 2cd c2 −d2 , 2cd d2 −c2 39
der (c, d)t er et punkt p˚ a linjen som har vinkelen 12 θ med x-aksen som er 2 2 valgt slik at c + d = 1. Dette er en ganske uvanlig m˚ ate ˚ a se rotasjoner p˚ a. Det vanligste er ˚ a bruke geometriske argumenter, og addisjonsformler for sinus a vise at og cosinus for ˚ θ − sin θ rotasjoner θ grader er gitt av matrisen cos . I virkeligheten gir dette sin θ cos θ samme matriser som ovenfor (se Oppgave 3 og 4). Projeksjoner av punkter ned p˚ a en gitt linje er ogs˚ a gitt av matriser. Slike avbildninger virker litt meningsløse i planet, men i rommet gir de spektakulære effekter n˚ ar de platter ut tredimensjonale figurer til todimensjonale. Matrisen ( 10 00 ) sender punktet (a, b)t til punktet (a, 0)t . Derfor gir matrisen projeksjon p˚ a x-aksen. Tilsvarende gir ( 00 01 ) projeksjonen p˚ a y-aksen. Generelt har vi sett (se Oppgave (9), Seksjon 1.2) at projeksjonen av et punkt (a, b)t p˚ a linjen L gjennom origo og punktet (c, d)t 6= 0 er (ac + bd)(c, d)t = (ac2 + bcd, acd + bd2 )t , n˚ ar vi velger c og d p˚ a linjen slik at c2 + d2 = 1. Derfor vil matrisen gi denne projeksjonen.
1.5.5
c2 cd cd d2
Lineære avbildninger
Vi vil se litt mer generelt p˚ a avbildninger av planet gitt av matriser. La a11 a12 A = ( a21 a22 ). Punktene t(a, b)t + (1 − t)(c, d)t for alle t utgjør linjen gjennom punktene (a, b)t og (c, d)t . Hvert punkt p˚ a linjen vil A sende til punktet ta+(1−t)c taa11 +(1−t)ca11 +tba12 +(1−t)da12 11 a12 ( aa21 = taa a22 ) tb+(1−t)d 21 +(1−t)ca21 +tba22 +(1−t)da22 a12 a11 a12 aa11 +ba12 ca11 +da12 a c = t aa21 +ba22 + (1 − t) ca21 +da22 = t ( aa11 21 a22 ) ( b ) + (1 − t) ( a21 a22 ) ( d ) , a11 a12 a12 a c t som ligger p˚ a linjen gjennom bildene ( aa11 21 a22 ) ( b ) og ( a21 a22 ) ( d ) av (a, b) respektive (c, d)t ved A. Hver matrise har derfor den tiltalende egenskapen at den sender linjer til linjer. Derfor kaller vi disse avbildningene lineære. Dette gjør at den sender trekanter til trekanter og firkanter til firkanter, og s˚ a videre, slik at det er lett ˚ a se hva en slik avbildning av planet gjør. I v˚ are figurer har vi brukt denne egenskapen. Vi har sett at matriser kan speile, rotere, projisere, strekke og trykke sammen, og kan utføre alle kombinasjoner av slike bevegelser. Nu vil vi undersøke hva som hender med arealer under disse transformasjonene. Vi skal se p˚ a hva som hender med et parallellogram, det vil si en firkant slik at motst˚ aende sider er parallelle. Om vi kan bestemme hvordan arealet av et parallellogram forandrer seg ved en lineær avbildning vet vi ogs˚ a hvordan alle rimelige figurer forandrer seg ettersom vi kan tenke oss at vi tilmæmer andre figurer med sm˚ a parallellogrammer.
40
La R være parallellogrammet som er bestemt av punktene (0, 0)t , (a1 , a2 )t og (b1 , b2 )t . y (b1 , b2 )t
(a1 , a2 )t x
(0, 0)
Vi har sett (Oppgave 9, Seksjon 1.2) at avstanden mellom punktet (a1 , a2 )t og linjen gjennom (0, 0)t og (b1 , b2 )t er s (a1 b1 + a2 b2 )2 a21 + a22 − . b21 + b22 Arealet av parallellogrammet er derfor s q (a1 b1 + a2 b2 )2 b21 + b22 a21 + a22 − b21 + b22 q p a21 b22 + a22 b21 − 2a1 b1 a2 b2 = (a1 b2 − a2 b1 )2 = |a1 b2 − a2 b1 |. 11 a12 For en matrise A = ( aa21 a22 ) skriver vi det A = a11 a22 − a12 a21 og kaller det A for determinanten til A. Vi skal se at determinantene spiller en viktig rolle i studiet av matriser. Her noterer vi bare at vi har vist at arealet av parallellogrammet er bestemt av (0, 0)t , (a1 , a2 )t og (b1 , b2 )t er tallverdien av a a det ( b11 b22 ). Matrisen A transformerer parallellogrammet bestemt av vektorene (0, 0)t , (a1 , a2 )t og (b1 , b2 )t til parallellogrammet bestemt av a11 a12 a1 a11 a1 +a12 a2 11 a12 0 0 ( aa21 a22 ) ( 0 ) = ( 0 ) , ( a21 a22 ) ( a2 ) = a21 a1 +a22 a2 a12 b1 a11 b1 +a12 b2 og ( aa11 21 a22 ) b2 = a21 b1 +a22 b2 .
Arealet av parallellogrammet etter forflytningen med A er derfor a1 +a12 a2 a21 a1 +a22 a2 det aa11 11 b1 +a12 b2 a21 b1 +a22 b2 = (a21 b1 + a22 b2 )(a11 a1 + a12 a2 ) − (a11 b1 + a12 b2 )(a21 a1 + a22 a2 ) a1 a2 a12 = (a11 a22 − a12 a21 )(a1 b2 − a2 b1 ) = det ( aa11 21 a22 ) det ( b1 b2 ) . Arealet av et parallellogram multipliseres derfor med faktoren | det A| n˚ ar parallellogrammet forflyttes ved hjelp av A. 41
Vi har ganske grundig behandlet rotasjoner. En rotasjon skal selvsagt bevare lengder og vinkler. Nu vil vi betrakte problemet fra den andre siden og undersøke hvilke 2 × 2-matriser som vil bevare lengder og vinkler. Vi skal vise, kanskje litt overraskende, at om A gir en transformasjon som bevarer lengden p˚ a vektorene e1 = (1, 0)t og e2 = (0, 1)t og dessuten bevarer vinkelen p˚ a 90 grader mellom e1 og e2 s˚ a vil A enten være en rotasjon, eller en speiling fulgt av en rotasjon. p Lengden til en vektor v = (a1 , a2 )t er |v| = a21 + a22 og vinkelen mellom linjene fra origo til punktene v og w = (b1 , b2 )t er (se hint til Oppgave 9) cos θ =
v·v a1 b1 + a2 b2 p =p 2 |v||w| a1 + a22 b21 + b22
a12 om b˚ ade v og w er forskjellige fra origo. Matrisen A = ( aa11 21 a22 ) flytter e1 til (a11 , a21 )t og e2 til (a12 , a22 )t . Skal matrisen A bevare lengden av e1 og e2 m˚ a 2 2 2 2 vi derfor ha at a11 + a21 = 1 og a12 + a22 = 1. Om matrisen skal bevare vinkelen mellom x- og y-aksen m˚ a vi ha at 0 = t t e1 · e2 = Ae1 · Ae2 = (a11 , a21 ) · (a12 , a22 ) = a11 a12 + a21 a22 . Vi har alts˚ a funnet tre likninger som koordinatene til A m˚ a tilfredsstille om lengden av e1 og e2 og vinkelen mellom x- og y-aksen skal bevares
a211 + a221 = 1, a212 + a222 = 1, og a11 a12 + a21 a22 = 0. Disse likningene kan vi løse som i Oppgave 6. Løsningene er √ √ a11 = 1, a12 = 1 − a2 , a21 = 1 − a2 , a22 = −a √ √ a11 = 1, a12 = 1 − a2 , a21 = − 1 − a2 , a22 = a √ √ a11 = 1, a12 = − 1 − a2 , a21 = 1 − a2 , a22 = a √ √ a11 = 1, a12 = − 1 − a2 , a21 = − 1 − a2 , a22 = −a. Dette gir matrisene √ − 1−a2 a √ a , −√1−a 2 1−a2 a
√ − 1−a2 −a
a , −√1−a 2
√
1−a2 a
a , √1−a 2
√
1−a2 −a
.
De vanligste fremstillingene av rotasjon er ved hjelp av sinus og cosinus. P˚ a mange m˚ ater er dette mer naturlig ettersom det er lett ˚ a fremstille vinkler, og derfor rotasjon, med de trigonometriske funksjonen. Det er imidlertid ikke vanskelig ˚ a finne sammenhengen mellom v˚ ar fremstilling og den ved hjelp av sinus og cosinus (se Oppgave 3 og 4). Av likningen a211 + a221 = 1 f˚ ar vi at |a| < 1 s˚ a det finnes nøyaktig to vinkler θ slik at a = cos θ. Da vil 42
√
√ 1 − a2 = 1 − cos θ2 = | sin θ|. Vi ser at det bare finnes en verdi av θ slik at matrisene ovenfor kan skrives p˚ a en av de to formene cos θ − sin θ sin θ cos θ
cos θ sin θ sin θ − cos θ
,
.
Den første av disse er rotasjonen med θ som vi har støtt p˚ a tidligere og den andre er en speiling i x-aksen sammensatt med rotasjonen.
Oppgaver 1.5.6.
1. La L og H være to linjer i planet som danner en vinkel p˚ a θ grader med hverandre, der 0 < θ ≤ 180. Vis at om vi speiler et punkt i H og deretter speiler det nye punktet i L, s˚ a er resultatet det samme som ˚ a rotere det opprinnelige punktet 2θ grader om skjæringspunktet mellom linjene. Hint. La (g, h)t være skjæringspunktet mellom linjene L og H. Videre la K være linjen gjennom et punkt (a, b)t skjæringspunktet (g, h)t . La ϕ være vinkelen mellom K og H, der vi regner tegnet av vinklene ut fra H. Da vil vinkelen mellom K og L være θ − ϕ. Speiler vi (a, b)t i H f˚ ar vi en et punkt t t t (c, d) slik at linjen gjennom (g, h) og (c, d) danner vinkelen θ + ϕ med L. Speiling av (c, d)t i L gir et punkt (e, f )t slik at vinkelen mellom linjen gjennom (e, f )t og (g, h)t danner en vinkel θ + ϕ med L, og derfor vinkelen θ + ϕ + θ − ϕ = 2θ med K. (e, f )t L K θ−ϕ
θ+ϕ (g, h)t
θ ϕ
(a, b)t
θ+ϕ H (c, d)t
2. Vis at
c2 −d2 2cd 2cd d2 −c2
der c2 + d2 = 1 er matrisen som beskriver en speiling
i linjen gjennom (c, d)t 6= 0. 43
y
L
(b1 , b2 )
v·w (b , b )t w·w 1 2
θ
(a1 , a1 )t x
Hint. Det følger av Oppgave 9 i Seksjon 1.2 at linjen fra et punkt (a, b)t som st˚ ar normalt p˚ a linjen L gjennom origo og (c, d)t skjærer L i punktet (ac+bd)(c, d)t . Vektoren fra (a, b)t til (ac+bd)(c, d)t er derfor (ac+bd)(c, d)t − (a, b)t . Speiling i L gies av den doble vektoren. Derfor er punktet symmetrisk med (a, b)t med hensyn til L lik 2(ac + bd)(c, d)t − 2(a, b)t + (a, b)t = (2(ac + bd)c − a(c2 + d2 ), 2(ac + bd)d − b(c2 + d2 ))t 2 2 −d 2cd = (a(c2 − d2 ) + 2bdc, 2acd + (d2 − c2 )b)t = c 2cd ( ab ) . 2 2 d −c 2 2 −d −2cd 3. Vis at matrisene p˚ a formen c 2cd med c2 + d2 = 1 er de samme c2 −d2 θ − sin θ som matrisene cos sin θ cos θ . Hint. Sett a = c2 − d2 . Da vil a = 2c2 − 1 og a = 1 − 2d2 . Derfor ar vi at √ f˚ 2 2 2 4c d = (1 + a)(1 − a) = 1 − a og at 2cd er lik plus eller minus 1 − a2 . Av c2 + d2 = 1 f˚ ar vi at |c| ≤ 1 og |d| ≤ 1 og derfor at √ |a| < 1. Det√finnes derfor eksakt to vinkler θ slik at a = cos θ. Vi har ogs˚ a 1 − a2 = 1 − cos2 θ = | sin θ|. De to valgene av θ gir ulike tegn p˚ a sin θ. Derfor finnes det nøyaktig 2 2 en vinkel θ slik at cos θ = a = c − d . Med denne vinkelen tar matrisen θ − sin θ formen cos sin θ cos θ . Omvendt, om vi har gitt den siste matrisen s˚ a kan vi, ettersom | cos θ| ≤ 1, 2 finne tall c og d slik at 2c = cos θ + 1 og 2d2 = 1 − cos θ. Vi har at c og d er entydig bestemt opp til tegn. Legger vi sammen likningene f˚ ar vi at 2 2 2 2 2c + 2d = 2 s˚ a c + d = 1. Trekker vi likningene fra hverandre f˚ ar vi at 2 2 2 2 2(c − d ) = 2 cos θ s˚ a vi har at cos θ = c − d . Multipliserer vi likningene f˚ ar vi at 4c2 d2 = 1 − cos2 θ = sin2 θ s˚ a 2cd = ± sin θ. Nu bestemmer vi tegnene 2 2 c −d −2cd for c og d slik at 2cd = sin θ. Vi f˚ ar da at matrisen tar formen . 2cd c2 −d2 Merk at c og d ikke er entydig bestemte, men at de to mulige parene (c, d) gir samme matrise. θ sin θ 4. Vis at matrisen cos sin θ − cos θ er en speiling i x-aksen sammensatt med en rotasjon. 44
5. Bruk Oppgave 3 til ˚ a vise ligningene cos(ϕ + θ) = cos ϕ cos θ − sin ϕ sin θ. θ − sin θ Hint. Vi viste i Oppgave 3 at matrisen cos gir en rotasjon θ grader. sin θ cos θ Sammensetter vi denne rotasjonen med en rotasjon ϕ grader f˚ ar vi en rotasjon ϕ + θ grader. Dette kan vi uttrykke som cos θ − sin θ cos(ϕ+θ) − sin(ϕ+θ) cos ϕ − sin ϕ = sin(ϕ+θ) cos(ϕ+θ) . sin ϕ cos ϕ sin θ cos θ sin(ϕ + θ) = cos ϕ sin θ + sin ϕ cos θ,
Multiplikasjon av matrisene i venstre side av likningen gir de søkte ligningene. 6. Vis at likningene a211 + a221 = 1, a212 + a222 = 1 og a11 a12 + a21 a22 = 0 har nøyaktig de 4 løsningene √ √ a11 = 1, a12 = 1 − a2 , a21 = 1 − a2 , a22 = −a √ √ a11 = 1, a12 = 1 − a2 , a21 = − 1 − a2 , a22 = a √ √ a11 = 1, a12 = − 1 − a2 , a21 = 1 − a2 , a22 = a √ √ a11 = 1, a12 = − 1 − a2 , a21 = − 1 − a2 , a22 = −a. Hint. Sett a = a11 . Vi f˚ ar da av den første likningen at a221 = 1−a2 . Da gir den 2 2 andre likningen at a a12 = a211 a212 = (−a21 a22 )2 = a221 a222 = (1 − a2 )(1 − a212 ). Dette gir at (a2 + 1 − a2 )a212 = 1 − a212 = a2 , s˚ a a212 = 1 − a2 . Den andre likningen gir da at a222 = 1 − a212 = a2 . Vi har alts˚ a likningene a11 = a, a212 = 1 − a2 , a221 = 1 − a2 , a222 = a2 . Opptil tegn bestemmer dette koeffisientene til A som uttrykk i a. Det er 8 ulike valg av tegn tilsvarende de 3 kvadratuttykkene. Av de ˚ atte valgene vil alle tilfredsstille de to første likningene men bare fire vil tilfresdstiller den tredje. 7. Løs likningene a211 + a221 = 1, a212 + a222 = 1 og a11 a12 + a21 a22 = 0 p˚ a en slik m˚ ate at du direkte f˚ ar at koordinatene gir matrisene 2 2 2 2 c −d −2cd c −d 2cd , . 2cd c2 −d2 2cd d2 −c2 Hint. Observer at du kan finne tall c og d slik at 2c2 = a11 +1 og 2d2 = 1−a11 . Vis først at da vil a11 = c2 − d2 og c2 + d2 = 1. Derfor vil a221 = 1 − a211 = (1 − a11 )(1 + a11 ) = 4c2 d2 . Fortsett p˚ a denne m˚ aten p˚ a en tilsvarende m˚ ate som vi gjorde ovenfor. 45
8. Tegn en enkel figur p˚ a din dataskjerm, for eksempel et kvadrat. Velg et stort tall n. (1) Se hva som hender n˚ ar du bruker avbildningene 1 0 Sm = 0 1− 2m n p˚ a kvadratet n˚ ar m = 0, 1, . . . , n. (2) Se hva som hender n˚ ar du bruker avbildningene 2π cos n − sin 2π n Rm = sin 2π cos 2π n
n
p˚ a kvadratet n˚ ar m = 0, 1, . . . , n. (3) Prøv ulike kombinasjoner av avbildningene ovenfor, enten ved ˚ a ta produktene Sm Rm eller Rm Sm , eller ved ˚ a la en av dem løpe en stund og deretter bruke den andre, eller en kombinasjon av de to.
46
Kapittel 2 Ligninger 2.1
Eksempler
Innledning 2.1.1. Systemer av lineære ligninger1 oppst˚ ar overalt i matematikken og deres anvendelser er blandt de aller viktigste delene av matematikken. Det er derfor avgjørende ˚ a ha effektive metoder for ˚ a løse lineære ligninger, og det er ofte nødvendig ˚ a forst˚ a den bakomliggende teorien. Her skal vi presentere Gauss-Jordan eliminasjon, som er den mest brukte og mest anvendbare blandt metodene for ˚ a løse lineære ligninger. Denne eliminasjonsmetoden leder ogs˚ a til en god forst˚ aelse for teorien for systemer av lineære lininger. Terminologi 2.1.2. Gauss-Jordan eliminasjon best˚ ar i ˚ a eliminere variable i lineære ligninger. Ettersom vi mange ganger kommer til ˚ a multiplisere alle ledd i en ligning med et gitt tall og legge sammen høyre og venstre siden av ligninger innfører vi en spesiell terminologi for dette. Vi sier at vi multipliserer en ligning med et tall, om vi multipliserer hvert ledd i ligningen med tallet. For eksempel vil multiplikasjon av ligningen x1 − 2x2 − 5x3 = 3 med 3 gi ligningen 3x1 − 6x2 − 15x3 = 9. Mer generelt gir multiplikasjon av ligningen a1 x1 + a2 x2 + · · · + an xn = b med tallet a ligningen aa1 x1 + aa2 x2 + · · · + aan xn = ab. 1
ligning = ekvation
47
Videre sier vi at vi legger sammen to ligninger om vi legger sammen høyre og venstre sidene av ligningene. Om vi legger sammen ligningene x1 − 5x2 + 2x3 = 6 og 2x1 + 3x2 − 6x3 = 1 f˚ ar vi for eksempel ligningen 3x1 − 2x2 − 4x3 = 7. Mer generellt, om vi legger sammen ligningene a1 x1 + a2 x2 + · · · + an xn = b og b1 x1 + b2 x2 + · · · + bn xn = c f˚ ar vi ligningen (a1 + b1 )x1 + (a2 + b2 )x2 + · · · + (an + bn )xn = b + c. Merk 2.1.3. N˚ ar a 6= 0 har ligningen a1 x1 + a2 x2 + · · · + an xn = b
(2.1)
i de n variable x1 , x2 , . . . , xn samme løsninger som ligningen aa1 x1 + aa2 x2 + · · · + aan xn = ab
(2.2)
ettersom (l1 , l2 , . . . , ln )t er en løsning av ligningen (2.1) hvis og bare hvis vektoren (a−1 l1 , a−1 l2 , . . . , a−1 ln )t er en løsning av (2.2). Om b1 x 1 + b2 x 2 + · · · + bn x n = c er en annen ligning vil de tre systemene med to ligninger i n variable a1 x1 + a2 x2 + · · · + an xn = b (2.3) b1 x 1 + b2 x 2 + · · · + bn x n = c a1 x1 + a2 x2 + ··· + an x n = b (2.4) (a1 + b1 )x1 + (a2 + b2 )x2 + · · · + (an + bn )xn = b + c
(a1 + b1 )x1 + (a2 + b2 )x2 + · · · + (an + bn )xn = b + c b1 x 1 + b2 x 2 + ··· + bn x n = c
(2.5)
ha samme løsning. Dette er fordi vi f˚ ar ligningene i (2.3) fra ligningene i (2.4) ved ˚ a trekke begge sider i den første ligningen fra de tilsvarende sidene i den andre, og fra ligningene i (2.5) ved ˚ a trekke begge sider i den andre ligningen fra de tilsvarende sidene i den første. 48
Eksempel 2.1.4. Betrakt matrisen 1 3 1 2 7 0 . A = −1 −4 3 Vi kan multiplisere A med en vilk˚ arlig vektor v = (a1 , a2 , a3 )t i R3 . Produktet TA (v) = A(a1 , a2 , a3 )t = (a1 + 3a2 + a3 , 2a1 + 7a2 , −a1 − 4a2 + 3a3 )t , er ogs˚ a en vektor i R3 . La n˚ a b = (b1 , b2 , b3 )t være en vilk˚ arlig vektor i R3 . Vi vil gi en metode for ˚ a bestemme om vektoren b ligger i bildet av TA , det vil si, om det finnes vektorer x = (x1 , x2 , x3 )t i R3 slik at TA (x) = (x1 + 3x2 + x3 , 2x1 + 7x2 , −x1 − 4x2 + 3x3 )t = (b1 , b2 , b3 )t . Dette betyr at de tre koordinatene i den midterste vektoren skal være like de tilsvarende koordinatene i den høyre vektoren. Ligningen TA (x) = b er derfor det samme som systemet av tre ligninger i tre ukjente x1 + 3x2 + x3 = b1 2x1 + 7x2 = b2 −x1 − 4x2 + 3x3 = b3 .
(2.6)
Vi løser dette systemet ved ˚ a eliminere variable. Først bruker vi den første ligningen til ˚ a eliminere den variable x1 fra de to andre. Multipliser den første ligningen med −2 og legg den til den andre ligningen. Vi f˚ ar ligningssystemet med tre ligninger i tre variable x1 −x1
+ 3x2 + x3 = b1 x2 − 2x3 = −2b1 + b2 − 4x2 + 3x3 = b3 .
(2.7)
Som vi s˚ a i 2.1.3 har systemet (2.7) samme løsninger som systemet (2.6). Nu bruker vi den første ligningen til ˚ a eliminere x1 fra den tredje ligningen ved ˚ a legge den til den tredje ligningen. Vi f˚ ar et system med tre ligninger i tre ukjente x1 + 3x2 + x3 = b1 x2 − 2x3 = −2b1 + b2 − x2 + 4x3 = b1 + b3 . Nu bruker vi den andre ligningen til ˚ a eliminere x2 fra den første og den tredje ligningen. Multipliser først den andre ligningen med −3 og legg den til den første, og legg deretter den andre ligningen til den tredje. Vi f˚ ar x1 x2
+ 7x3 = 7b1 − 3b2 − 2x3 = −2b1 + b2 2x3 = −b1 + b2 + b3 . 49
Nu deler vi den tredje ligningen med 2 og f˚ ar x1 x2
+ 7x3 = 7b1 − 3b2 − 2x3 = −2b1 + b2 x3 = − 21 b1 + 21 b2 + 12 b3 .
Til slutt bruker vi den tredje ligningen til ˚ a eliminere x3 fra de to andre ligningene. Multipliser først den tredje ligningen med −7 og legg den til den første, og deretter med 2 og legg den til den andre. Vi f˚ ar ligningene x1 x2 x3
= 21 b − 13 b − 72 b3 2 1 2 2 = −3b1 + 2b2 + b3 = − 21 b1 + 12 b2 + 21 b3 ,
(2.8)
som ogs˚ a er et system av tre ligninger med tre ukjente. P˚ a hvert trinn i eliminasjonsprosessen vil de ligningene vi f˚ ar ha samme løsninger som ligningssystemet (2.6) som vi startet med. Fordelen med systemet (2.8) er at vi umiddelbart ser at det har nøyaktig en løsning x1 =
21 13 7 b1 − b2 − b3 , 2 2 2
x2 = −3b1 + 2b2 + b3 ,
1 1 1 x3 = − b 1 + b 2 + b 3 . 2 2 2
Løsningen kan ogs˚ a uttrykkes som 21 13 7 1 1 1 t TA ( b1 − b2 − b3 , −3b1 + 2b2 + b3 , − b1 + b2 + b3 ) = (b1 , b2 , b3 )t . 2 2 2 2 2 2 Vi ser at det finnes nøyaktig en løsning uansett hva (b1 , b2 , b3 )t er. Vi merker oss at de variable x1 , x2 , x3 ikke spilte noen vesentlig rolle i regningene ovenfor. Derfor kan vi spare mye plass, og gjøre løsningene mye mer oversiktlige, ved ˚ a sette opp koeffisientene i ligningene (2.6) i en matrise, og bare regne med matrisene. Det vil se, vi bruker bare matrisen 1 3 1 | b1 2 7 0 | b2 (2.9) −1 −4 3 | b3
der vi setter en strek i matrisen for ˚ a skille venstre delen, som er matrisen A vi startet med, fra den høyre, som er vektoren (b1 , b2 , b3 )t i R3 . Operasjonene vi gjorde p˚ a ligningene (2.6) kan vi nu gjøre direkte p˚ a matrisen (2.9). Vi multipliserer første raden i (2.9) med −2 og legger den til den andre raden, og f˚ ar 1 3 1 | b1 0 1 −2 | −2b1 +b2 −1 −4 3 | b3
50
.
Deretter legger vi den første raden til den tredje og f˚ ar 1 3 1 | b1 0 1 −2 | −2b1 +b2 . 0 −1 4 |
b1 +b3
Nu multipliserer vi den andre raden med −3 og legger den til den første, og deretter legger vi den til den tredje. Vi f˚ ar 1 0 7 | 7b1 −3b2 0 1 −2 | −2b1 +b2 . 0 0 2 | −b1 +b2 +b3
Divisjon av den tredje raden med 2 gir 1 0 7 | 7b
1 −3b2
0 1 −2 | −2b1 +b2 0 0 1 | − 12 b1 + 21 b2 + 21 b3
.
Til slutt multipliserer vi den tredje raden med −7 og legger den til den første, og deretter multipliserer vi den med 2 og legger den til den andre. Vi f˚ ar 1 0 0 | 0 1 0 | 0 0 1 |
21 b − 13 b −7b 2 1 2 2 2 3 −3b1 +2b2 +b3 − 12 b1 + 12 b2 + 12 b3
.
Denne matrisen representerer ligningssystemet (2.8) som vi fikk ovenfor. Eksempel 2.1.5. Betrakt matrisen A = ( 01 14 35 ) . Multiplikasjon med en vektor v = (a1 , a2 , a3 )t i R3 gir vektoren TA (v) = A(a1 , a2 , a3 )t = (a2 + 3a3 , a1 + 4a2 + 5a3 )t i R2 . Vi vil undersøke om vektoren (b1 , b2 )t ligger i bildet til TA , det vil si, om det finnes en vektor x = (x1 , x2 , x3 )t slik at TA (x1 , x2 , x3 )t = (b1 , b2 )t , og vi vil bestemme eventuelle slike vektorer. Sammenlikner vi første og andre koordinaten i ligningene TA (x) = TA (x1 , x2 , x3 )t = (x2 + 3x3 , x1 + 4x2 + 5x3 )t = (b1 , b2 )t f˚ ar vi et system av to ligninger i tre ukjente
x1
x2 + 3x3 = b1 + 4x2 + 5x3 = b2 . 51
(2.10)
Disse ligningene løser vi igjen ved ˚ a eliminere variable. Først bytter vi om ligningene og f˚ ar x1 + 4x2 + 5x3 = b2 x2 + 3x3 = b1 . Vi bruker nu den andre ligningen til ˚ a eliminere x2 i den første. Dette gjør vi ved ˚ a multiplisere den andre ligningen med −4 og legge den til den første. Dette gir systemet x1 x2
− 7x3 = −4b1 + b2 + 3x3 = b1
(2.11)
med to ligninger i tre ukjente, som har samme løsninger som systemet (2.10). Vi ser av (2.11) at vi kan velge x3 til ˚ a være et vilk˚ arlig tall x3 = s og at vi for hvert s f˚ ar løsningene x1 = −4b1 + b2 + 7s,
x2 = b1 − 3s,
x3 = s.
Det finnes derfor, for alle valg av (b1 , b2 )t , uendelig mange løsninger, en for hvert valg av s. Vi sier at s er en parameter og at det finnes en 1-dimensjonal familie av løsninger. Vi kan ogs˚ a uttrykke løsningen ved TA (−4b1 + b2 + 7s, b1 − 3s, s)t = (b1 , b2 )t for alle (b1 , b2 )t og alle s. Vi merker igjen at de variable x1 , x2 , x3 ikke spiller noen rolle i eliminasjonen. Derfor sparer vi plass og øker oversikten ved ˚ a erstatte ligningssystemet med den utvidete koeffisientmatrisen 0 1 3 | b1 1 4 5 | b2 . Eliminasjonen av de variable som vi utførte p˚ a systemet (2.10) tilsvarer da ˚ a bytte om radene slik at vi f˚ ar 1 4 5 | b2 0 1 3 | b1 , og deretter ˚ a multiplisere den siste raden med −4 og addere den til den første raden. Dette gir 1 0 −7 | −4b1 +b2 . (2.12) 0 1 3 | b1 Matrisen (2.12) svarer til det samme ligningssystemet (2.11) som vi fant ovenfor. 52
Eksempel 2.1.6. Betrakt matrisen A=
1 2 4 3 −1 2
.
Multiplikasjon med en vektor (a1 , a2 )t i R2 gir vektoren (a1 + 2a2 , 4a1 + 3a2 , −a1 + 2a2 )t i R3 . Vi vil undersøke om vektoren (b1 , b2 , b3 )t ligger i bildet til TA , det vil si, om det finnes vektorer x = (x1 , x2 )t slik at TA (x) = (x1 + 2x2 , 4x1 + 3x2 , −x1 + 2x2 )t = (b1 , b2 , b3 )t .
(2.13)
Sammenlikner vi de tre koordinatene i ligningen (2.13) f˚ ar vi et system av tre ligninger i to ukjente x1 + 2x2 = b1 4x1 + 3x2 = b2 −x1 + 2x2 = b3 .
(2.14)
Vi løser systemet ved ˚ a eliminere variable. Først bruker vi den første ligningen til ˚ a eliminere x1 i de to andre ligningene. Multipliser den første ligningen med −4 og legg den til den andre ligningen, og legg deretter den første ligningen til den tredje. Vi f˚ ar et system av tre ligninger i to ukjente x1 + 2x2 = b1 − 5x2 = −4b1 + b2 4x2 = b1 + b3 . Multipliserer vi den andre ligningen med − 15 f˚ ar vi x1 + 2x2 = b1 x2 = 54 b1 − 51 b2 4x2 = b1 + b3 . Vi bruker nu den andre ligningen til ˚ a eliminere x2 fra den første og tredje ligningen. Multipliser den andre ligningen med −2 og legg den til den første, og multipliser deretter den første ligningen med −4 og legg den til den andre ligningen. Dette gir systemet av tre ligninger i to ukjente x1 x2 0
= − 53 b1 + 25 b2 = 45 b1 − 51 b2 b + 54 b2 + b3 . = − 11 5 1 53
(2.15)
Av ligningssystemet (2.15) ser vi at om ligningen skal ha løsninger s˚ a m˚ a vi 4 b + b + b = 0, eller ha at − 11 3 5 1 5 2 −11b1 + 4b2 + 5b3 = 0.
(2.16)
Bare n˚ ar ligningen (2.16) er oppfyllt har vi at ligningssystemet (2.14) har en løsning, og da er løsningen gitt av 3 2 x 1 = − b1 + b2 , 5 5
4 1 x2 = b 1 − b 2 . 5 5
Vi kan uttrykke dette ved ˚ a si at bildet av TA er planet H = {(b1 , b2 , b3 )t ∈ R3 : −11b1 + 4b2 + 5b3 = 0} og at, for hvert punkt (b1 , b2 , b3 )t i planet H, finnes det nøyaktig et punkt x = (− 35 b1 + 25 b2 , 54 b1 − 15 b2 )t i R2 slik at TA (x) = b. Igjen ser vi at de variable x1 , x2 , x3 ikke har noen vesentlig rolle i eliminasjonen, s˚ a det er enklere og mer instruktivt ˚ a se p˚ a den utvidete koordinatmatrisen 1 2 | b1 4 3 | b2 −1 2 | b3
til systemet (2.14). Eliminasjonene kan da skrives som
1 2 | b1 4 3 | b2 −1 2 | b3
→
1 2 | b1 0 −5 | −4b1 +b2 0 4 | b1 +b3
1 2 |
→
b1 0 1 | 45 b1 − 51 b2 0 4 | b1 +b3
→
1 0 | − 35 b1 + 25 b2 4 b −1b 0 1 | 5 1 5 2 11 0 0 | − 5 b1 + 45 b2 +b3
! .
(2.17) Matrisen lengst til høyre korresponderer med systemet (2.15). Merk 2.1.7. Vi har sett at et lineært system av ligninger kan representeres av en matrise. Ved hjelp av de tre operasjonene (1) multiplikasjon av en rad med et tall og addisjon av denne raden til en annen rad, (2) ombytte av to rader, (3) multiplikasjon av en rad med en ikke null konstant, kan vi f˚ a matrisen over p˚ a en form slik at vi umiddelbart kan finne løsningen til det tilsvarende ligningssystemet. Ettersom ligningssystemet som svarer til den matrisen vi startet med har samme løsninger som ligningssystemet som svarer til den matrisen vi ender opp med har vi f˚ att en effektiv m˚ ate for ˚ a finne løsningene til et system av lineære ligninger. 54
I eksemplene 2.1.4-2.1.6 startet vi med koeffisientmatrisene 1 2 1 3 1 0 1 3 2 7 0 , 4 3 (1 4 5), −1 −4 3 −1 2 og vi endte opp med de tilsvarende matrisene 1 0 1 0 0 1 0 7 0 1 0 , 0 1 . (0 1 3), 0 0 1
0 0
Vi sier at matriser p˚ a formen (2.1) er i redusert trappetrinnsform og prosessen som vi har beskrevet, som reduserte matrisen til denne formen, kalles Gauss-Jordan eliminasjon. En redusert trappetrinnsform er en matrise der radene har første ikke null koeffisient, kalt den ledende koordinaten, lik 1, og i kolonnen som inneholder en ledende koordinat er alle andre koeffisienter lik 0. Videre skal de ledende koordinatene ligge lenger til høyre jo lenger ned i matrisen raden ligger. Vi skal komme tilbake til alle begrepene vi har sett ovenfor i mye større generalitet. Det er viktig fullt ut ˚ a forst˚ a begrepen i de spesielle tilfellene vi har behandlet ovenfor ettersom notasjonen i de generelle tilfellene kan bli ganske involvert. Oppgaver 2.1.8. 1. La A være en 3×3-matrise og b = (b1 , b2 , b3 )t en vektor i R3 . Undersøk om ligningen Ax = b har en løsning x = (x1 , x2 , x3 )t . Bestem alle slike løsninger n˚ ar de finnes. 1 5 1 (1) A = 2 17 4 . 3 18 4
(2) A =
1 2 4 2 1 4 3 3 2
.
(3) A =
1 2 2 2 5 5 1 5 5
.
(4) A =
1 2 3 −1 −2 −3 −5 −10 −15
.
(Gjem utregningene. Du f˚ ar bruk for dem i kommende oppgaver.) 2. La A være en 2 × 3-matrise og b = (b1 , b2 )t en vektor i R2 . Undersøk om ligningen Ax = b har en løsning x = (x1 , x2 , x3 )t . Bestem alle slike løsninger n˚ ar de finnes. (1) A = ( 65 11 00 ). 4 ). (2) A = ( 13 27 14
55
1 1 2 (3) A = ( −2 −2 4 ). 10 1 (4) A = ( 13 −35 3 ).
(Gjem utregningene. Du f˚ ar bruk for dem i kommende oppgaver.) 3. La A være en 3 × 2-matrise og b = (b1 , b2 , b3 )t en vektor i R3 . Undersøk om ligningen Ax = b har en løsning x = (x1 , x2 )t . Bestem alle slike løsninger n˚ ar de finnes. 1 3 2 7 . (1) A = −2 −8 (2) A =
1 4 2 12 3 4
(3) A =
0 5 0 1 0 6
(4) A =
2 15 1 6 −3 −12
.
.
.
(Gjem utregningene. Du f˚ ar bruk for dem i kommende oppgaver.) 1 ). (KTH 4. Bestem alle matriser A slik at a11 = a22 = 1 og A ( 31 ) = ( 10 2000).
5. Løs ligningssystemet x−
z= y+ 2z = x+ 2y− 3z =
6. La A =
1 2 3 2 1 1 3 3 4 3
0 1 4.
, og la TA (v) betegne vektoren vi f˚ ar ved ˚ a multiplisere en
vektor v i R med A. (1) Bestem kjernen til TA , det vil si alle vektorer v i R3 som er slik at TA (v) = 0. (2) Bestem bildet til TA , det vil si alle vektorer TA (v) for v i R3 . 7. For hvert tall b har vi et ligningssystem 5x − y = −2b2 10x − 2y = −b2 − 3b + 2. (1) For hvilke b har systemet løsninger? 56
(2) Bestem løsningene n˚ ar systemet har løsninger. 8. Ofte har vi anvendelse for ˚ a finne heltallsløsninger av lineære ligninger med heltallskoeffisienter. N˚ ar vi søker heltallsløsninger av slike ligninger kalles de diofantiske ligninger. (1) Finn en heltallsløsning, om den finnes, til ligningene (a) 5x + 3y = 1. (b) 11x − 3y = 5. (c) 33x + 27y = 1. (d) 33x + 7y = 1. (2) Bestem alle løsningene til ligningene (a), (b), (c) og (d) i del (1) av denne oppgaven. Hint. Bruk at om du har funnet en løsning (a, b) til ligningen mx + ny = p, der a, b, m, n, p er heltall, og en løsning (c, d) til ligningen mx + ny = 0 s˚ a vil (a + c, b + d) være en løsning av ligningen mx + ny = p. 9. La m, n, p være hele tall. Anta at m og n er innbyrdes primiske, d.v.s. det finnes inget primtall som deler b˚ ade m og n. Hint. Bruk at om du har funnet en løsning (a, b) til ligningen mx + ny = p, der a, b, m, n, p er heltall, og en løsning (c, d) til ligningen mx + ny = 0 s˚ a vil (a + c, b + d) være en løsning av ligningen mx + ny = p. 10. La m, n, p være hele tall. Anta at m og n er innbyrdes primiske, d.v.s. det finnes inget primtall som deler b˚ ade m og n. (1) Vis at den diofantiske ligningen mx + ny = p har en heltallsløsning. (2) Vis at om du har en heltallsløsning s˚ a kan du finne alle heltallsløsninger til den diofantiske ligningen mx + ny = p. Hint. (1) Det rekker ˚ a vise (1) for p = 1 ettersom vi etterp˚ a kan multiplisere ligningen med p. For ˚ a vise ligningen for p = 1 betrakter vi mengden S av alle tall l som har egenskapen at for alle tall n som er innbyrdes primisk med l s˚ a vil det finnes heltallsløsninger av ligningen lx + ny = 1. Vi har at tallet 1 ligger i S. Anta at vi har vist at tallene 1, 2, . . . , m − 1 alle ligger i S. Vi vil vise at da ligger ogs˚ a m i S. La n være primisk med n. Da kan vi finne heltall q og r slik at n = qm + r der 0 < r < m. Men vi har at r er primisk med m fordi en felles faktor ville dele n. Ettersom vi har at r er i S kan vi finne hele tall c og d slik at cm + rd = 1. Men da har vi cm + (n − qm)d = 1, som gir (c − qd)m + nd = 1. Derfor er ogs˚ a m med i S. (2) Bruk samme hint som i forrige oppgave. 57
11. Et utmerket og velkjent eksempel p˚ a et diofantisk problem er Archimedes’ Problema bovinum. Solguden hadde en hjord med kuer og okser. Det var V = vite okser v = vite kuer S = svarte okser s = svarte kuer F = flekkete okser f = flekkete kuer B = brune okser b = brune kuer. Blandt oksene var antallet vite minus antallet brune like en halv pluss en tredjedel av antallet av de svarte. Antallet svarte minus antallet brune var en fjerdedel pluss en femtedel av antallet flekkete. Antallet flekkete minus antallet brune var en sjettedel pluss en syvendedel av antallet vite. Med andre ord var V − B = ( 12 + 13 )S = 65 S 9 S − B = ( 14 + 15 )F = 20 F 1 13 1 F − B = ( 6 + 7 )V = 42 V. Blandt kuene var antallet vite like en tredjedel pluss en fjerdedel av antallet svarte kyr, antallet svarte var en fjerdedel pluss en femtedel av antallet flekkete kyr, antallet flekkete en femtedel pluss en sjettedel av antallet brune kyr, og antallet brune en sjettedel pluss en syvendedel av antallet vite kyr. Med andre ord 7 1 1 v = ( + )(s + S) = (s + S) 3 4 12 1 1 9 s = ( + )(f + F ) = (f + F ) 4 5 20 (2.18) 1 1 11 f = ( + )(b + B) = (b + B) 5 6 30 1 1 13 b = ( + )(v + V ) = (v + V ). 6 7 42 Finn sammensetningen av hjorden. Hint. De tre første ligningene gir 6V − 5S = 6B 20S −9F = 20B −13V +42F = 42B. Løs disse likningen slik at du f˚ ar V =
742 B, 297
S=
178 B, 99
F =
1580 B. 891
Ettersom 1580 og 891 ikke har noen felles faktor m˚ a vi ha, for at F skal være 58
hel, at B = 891G for noe tall G. Derfor har vi at 742 891G = 742 · 3G = 2226G 297 178 S= 891G = 178 · 9G = 1602G 99 B = 891G V =
Setter vi disse verdiene inn i ligningene 2.18 f˚ ar vi −7s 20s −9f 30f −11b −13v +42b 12v
= = = =
11214G 14220G 9801G 28938G
Løs disse fire ligningene i fire ukjente v, s, f, b. Vi f˚ ar om c = 4657 at cv = 7206360G cs = 4893246G cf = 3515820G cb = 5439213G.
(2.19)
Vi har at 4657 er et primtall og det g˚ ar fort ˚ a kontrollere at ingen av tallene p˚ a høyre side i ligningene 2.19 er delbare med 4651. Derfor m˚ a vi ha at G = 4651g for noe heltall g. Vi har derfor vist at V = 10366482g S = 7460514g F = 7358060g B = 4149387g v = 7206360g s = 4893246g f = 3515820g b = 5439213g. Vi ser at vi har uendelig mange løsninger og de minste f˚ ar vi for g = 1.
59
2.2
Gauss-Jordan eliminasjon
Innledning 2.2.1. Vi vil beskrive Gauss-Jordan eliminasjon for generelle lineære ligningssystemer. Dette er en enkel og effektiv metode for ˚ a bestemme om et system av lineære ligninger har løsninger og for ˚ a finne løsningene n˚ ar de eksisterer. Alle grunnprinsippene i eliminasjonen har vi brukt i Eksemplene i Seksjon 2.1. For de som har regnet eksemplene i Seksjon 2.1 kommer derfor metodene i denne seksjonen ikke som noen overraskelse. Det som gjenst˚ ar er ˚ a sette opp notasjonen slik at den blir h˚ andterbar for systemer med mange ligninger og mange ukjente. Notasjonen kan virke komplisert og abstrakt ettersom det forekommer mange rekker og søyler, og det kan virke vanskelig ˚ a se hvor elementene st˚ ar. For de som har gjort eksemplene i Seksjon 2.1 er det enkelt ˚ a se hvordan generaliseringene til m × n-matriser m˚ a være. I virkeligheten er det s˚ a greit at alle med god kjenneskap til eksemplene burde klare generaliseringen p˚ a egen h˚ and. Etter at vi har beskrevet Gauss-Jordan eliminasjonen for generelle linære ligningssystemer, viser vi hvordan disse eliminasjonene kan utføres ved hjelp av matriseoperasjoner. Dette har stor teoretisk betydning og danner grunnlaget for v˚ ar behandling av determinanter i Seksjon 2. Definisjon 2.2.2. Et system av m lineære ligninger i n variable x1 , x2 , . . . , xn er m ligninger p˚ a formen a11 x1 a21 x1
+ a12 x2 + a22 x2
+ · · · + a1n xn + · · · + a2n xn .. .
= =
b1 b2
(2.20)
am1 x1 + am2 x2 + · · · + amn xn = bm . Vi kaller systemet homogent om b1 = b2 = · · · = bm = 0. Det vil si et homogent system av lineære ligninger er et system p˚ a formen a11 x1 a21 x1
+ a12 x2 + a22 x2
+ · · · + a1n xn + · · · + a2n xn .. .
= 0 = 0
am1 x1 + am2 x2 + · · · + amn xn = 0. Matrisen
a11 a12 · · · a1n a21 a22 · · · a2n A= .. . am1 am2 · · · amn 60
(2.21)
kalles koeffisientmatrisen til ligningssystemet a11 a12 · · · a1n a21 a22 · · · a2n .. . am1 am2 · · · amn
og matrisen | b1 | b2 | bm
kalles den utvidete koeffisientmatrisen. Merk 2.2.3. Ligningssystemet (2.20) kan skrives p˚ a formen Ax = b med b = (b1 , b2 , . . . , bm )t og x = (x1 , x2 , . . . , xn )t . Definisjon 2.2.4. Vi sier at matrisen 0 ··· 0 1 a ··· a 0 a 1j2 −1
1j1 +1
0 ··· .. . 0 ... 0 ... . ..
0 0
0 0 0 0
0 ··· 0 0
.. .
···
0
1
.. .
.. .
.. .
··· ···
.. .
···
.. .
0
1j2 +1 a2j2 +1
··· a1js−1 0 a1js+1 ··· a1n ··· a2js−1 0 a2js+1 ··· a2n
.. .
··· ···
0 0
1 asjs+1 0
···
0
0
.. .
0
.. .
.. .
.. .
.. .
.. .
··· asn ··· 0 .. .. . . ···
0
er p˚ a redusert trappetrinnsform. Koordinatene (1, j1 ), (2, j2 ), . . . , (s, js ) kalles de ledende koordinatene og s kalles rangen til matrisen. Den reduserte trappetrinnsformen karakteriseres av at første ikke null koordinat i hver rekke, det vil si ledende koordinatene koordinaten, er 1 og de resterende koordinatene i kolonnen denne 1’eren st˚ ar er 0. Videre ligger de ledende koordinatene lenger til høyre jo lenger ned i matrisen vi kommer. Dette svarer tiil at j1 ≤ j2 ≤ · · · ≤ js . Merk 2.2.5. Det er lettere ˚ a f˚ a en ide om hvordan den reduserte trappetrinnsformen ser ut ved ˚ a omnummerere de variable, eller, hvilket er det samme, ˚ a innføre nye variable y1 , y2 , . . . , yn der y1 = xj1 , y2 = xj2 , . . . , ys = xjs og der ys+1 , ys+2 , . . . , yn er de variable x1 , x2 , . . . ,xj1 −1 , xj1 +1 , . . . , xj2 −1 , xj2 +1 , . . . , xjs −1 , xjs +1 , . . . , xn . Da ser den reduserte matrisen ut som 1 0 ··· 0 a1s+1 a1s+2 ··· a1n 0 1 ··· 0 a2s+1 a2s+2 ··· a2n
. . 0 ···. 0 ··· .. .. . . 0
.. .
.. .
.. .
.. .
.. .
.. .
1 ass+1 ass+2 0
··· 0
61
.. .. . . ··· asn . ··· 0 .. .. . .
···
0
Det er lett ˚ a se at denne matrisen er p˚ a samme form som matrisen i (2.2.4), bare at vi har nummerert om søylene. En annen m˚ ate ˚ a betrakte denne omnummereringen p˚ a er at vi flytter søylene nummer j1 , j2 , . . . , js der de ledende enerne st˚ ar i matrisen i (2.2.4), til søylene nummerert med 1, 2, . . . , s. De resterende n − s søylene i matrisen i (2.2.4) lar vi bli st˚ aende slik at de utgjør de siste n − 2 søylene i den nye matrisen og st˚ ar i samme innbyrdes orden i den nye matrisen som rekkefølgen de hadde i matrisen (2.2.4).
2.2.6
Eliminasjon av variable
Gauss-Jordan eliminasjonen best˚ ar i ˚ a eliminere s˚ a mange variable som mulig fra et system av lineære ligninger. Prosessen vi skal beskrive er ganske grei, men notasjonen kan virke komplisert. Det er derfor viktig ˚ a beherske de eksemplene vi har behandlet i forrige seksjon. Vi begynner med ˚ a bestemme den første variable xj1 som forekommer i ligningssytemet med en ikke null koeffisient ai1 j1 . Vi multipliserer ligning nummer i1 med a−1 i1 j1 og bytter om rad nummer 1 og rad nummer i1 . Den første ligningen i det nye systemet ser da ut som xj1 + b1j1 +1 + · · · + b1n xn . Vi multipliserer nu den første ligningen med passende konstanter og trekker den fra de andre ligningene slik at koeffisientene foran xj1 bli null i alle disse ligningene. Ligningssystemet ser da ut som xj1 + b1j1 +1 xj1 +1 + · · · + b1n xn = c1 b2j1 +1 xj1 +1 + · · · + b2n xn = c2 .. . bmj1 +1 xj1 +1 + · · · + bmn xn = cm . Dette ligningssystemet har samme løsninger som systemet (2.20). Vi bestemmer nu den første variable xj2 i de siste m − 1 ligningene som forekommer med en ikke null koeffisient bi2 j2 . Deretter multipliserer vi rad i2 med b−1 i2 j2 og bytter om den andre rekken og rekke i2 . Koeffisienten foran xj2 i den andre raden er nu 1 og ved ˚ a multiplisere den andre raden med passende konstanter og trekke resultatet fra de resterende radene kan vi oppn˚ a at alle raden bortsett fra rad i2 ikke inneholder den variable xj2 . Ligningssystemet ser nu ut som xj1 + c1j1 +1 xj1 +1 + · · · + c1j2 −1 xj2 −1 +
+ c1j2 +1 xj2 +1 + · · · + c1n xn = d1 xj2 + c2j2 +1 xj2 +1 + · · · + c2n xn = d2 .. . cmj2 +1 xj2 +1 + · · · + cmn xn = dm
62
Denne prosessen kan vi fortsette til det ikke lenger finnes ikke null koeffisienter for noen av variablene, det vil si, alle de gjenst˚ aende ligningene har null til venstre om likhetstegnet. Da vil koeffisientmatrisen være i redusert trappetrinnsform. Alle ligningssystemene vi f˚ ar i prosessen har samme løsninger. Det som skiller det systemet vi startet med fra det vi ender opp med, og som har en redusert trappetrinnsmatrise som koeffisientmatrise, er at vi kan lese løsningene direkte av det siste systemet. For lettest ˚ a innse dette omnummererer vi de variable x1 , x2 , . . . , xn , eller, hvilket er det samme, innfører vi nye variable y1 , y2 , . . . , yn gitt ved y1 = xj1 , y2 = xj2 , . . . , ys = xjs og lar ys+1 , ys+2 , . . . , yn være de resterende variable x1 , x2 , . . . , xj1 −1 , xj1 +1 , . . . xj2 −1 , xj2 +1 , . . . , xjs −1 , xjs +1 , . . . , xn . Systemet har da formen y1 y2 ys
+ d1s+1 ys+1 + d1s+2 ys+2 + · · · +d1n yn + d2s+1 ys+1 + d2s+2 ys+2 + · · · +d2n yn .. .. .. . . . + dss+1 ys+1 + dss+2 ys+2 + · · · +dsn yn 0 0
= f1 = f2 .. . = fs = fs+1 .. . = fm
Vi ser at vi bare har løsninger om betingelsene 0 = fs+1 = fs+2 = · · · = fm er oppfyllt. N˚ ar disse betingelsene holder ser vi at vi kan velge alle variable ys+1 , ys+2 , . . . , yn fritt, ys+1 = ts+1 , ys+2 = ts+2 , . . . , yn = tn og at de resterende variablene y1 , y2 , . . . , ys er gitt av ts+1 , ts+2 , . . . , tn . Med andre ord, n˚ ar fs+1 = fs+2 = · · · = fm = 0, vil løsningene være gitt av y1 = y2 = .. . ys = ys+1 = ys+2 = .. . yn =
f1 f2
−d1s+1 ts+1 − d1s+2 ts+2 − · · · − d1n tn −d2s+1 ts+1 − d2s+2 ts+2 − · · · − d2n tn
fs −dss+1 ts+1 − dss+2 ts+2 − · · · − dsn tn ts+1 ts+2 tn
der vi kan velge alle ti ’ene fritt. Vi sier at at ts+1 , ts+2 , . . . , tn er parametre og at vi har en n − s-dimensjonal familie av løsninger. Merk 2.2.7. Vi ser med det samme at om m = n s˚ a vil ligningssystemet (2.20) ha en eneste løsning om den reduserte trappetrinnsmatrisen er In . Den homogene ligningen har da bare løsningen x1 = x2 = · · · = xn = 0. 63
Om n ≥ m ser vi at løsningen av det homogene systemet avhenger av n − sparametre.
2.2.8
Elementære operasjoner
Som vi har sett spiller ikke de variable noen rolle i Gauss-Jordan eliminasjonen. Derfor er det fordelaktig ˚ a gjøre eliminasjonen direkte p˚ a koeffisientmatrisen, eller p˚ a den utvidete koeffisientmatrisen. Definisjon 2.2.9. La A være en m × n-matrise. Følgende tre operasjoner p˚ a A kalles elementære operasjoner (1) Addisjon av en rad multiplisert med et tall til en annen rad. (2) Ombytte av to rader. (3) Multiplikasjon av en rad med et ikke null tall.
2.2.10
Eliminasjon for matriser
Gauss-Jordan eliminasjonen av variable i et system av lineære ligninger kan overføres direkte til elementære operasjoner p˚ a radene til den tilsvarende koeffisientmatrisen. Prosessen beskrevet i Seksjon 2.2.6 ovenfor kan vi oversette direkte til elementære operasjoner p˚ a matrisen. Vi ser at vi ender opp med en m × n-matrise som er p˚ a redusert trappetrinnsform. Dette kalles GaussJordan reduksjon av matrisen A. Eksempel 2.2.11. Vi vil vise hvordan Gauss-Jordan reduksjonen fungerer p˚ a et system av fire ligninger med seks ukjente x1 3x1 2x1 5x1
+ 2x2 + 6x2 + 4x2 + 10x2
+ x3 + 6x3 + 3x3 + 7x3
− 3x4 − 15x4 − 8x4 − 19x4
+ 5x5 + 21x5 + 12x5 + 29x5
+ x6 + x6 + x6 + 2x6
= = = =
b1 b2 b3 b4 .
(2.22)
Den utvidete koeffisientmatrisen til ligningssystemet (2.22) er ! 1 2 1 −3 5 1 | b 1
3 6 6 −15 21 1 | b2 2 4 3 −8 12 1 | b3 5 10 7 −19 29 2 | b4 .
Multipliserer vi den første raden med −3, −2 og −5 og legger den til radene to, tre og fire respektive f˚ ar vi matrisen ! 1 2 1 −3 5 1 | b 1
0 0 3 −6 6 −2 | −3b1 +b2 0 0 1 −2 2 −1 | −2b1 +b3 0 0 2 −4 4 −3 | −5b1 +b4 .
64
Vi bytter nu om den andre og tredje raden og f˚ ar 1 0 0 0
2 0 0 0
1 1 3 2
−3 −2 −6 −4
5 2 6 4
1 −1 −2 −3
| b1 | −2b1 +b3 | −3b1 +b2 | −5b1 +b4 .
!
Multipliserer vi den andre raden med −1, −3 og −2 og legger den til første, tredje og fjerde raden respektive s˚ a f˚ ar vi 1 0 0 0
2 0 0 0
0 1 0 0
−1 −2 0 0
3 2 0 0
2 −1 1 −1
| 3b1 −b3 | −2b1 +b3 | 3b1 +b2 −3b3 | −b1 −2b3 +b4 .
!
Til slutt multipliserer vi den tredje raden med −2 og legger den til den første raden, og dessuten legger vi den tredje raden til den andre og den fjerde. Vi f˚ ar ! 1 0 0 0
2 0 0 0
0 1 0 0
−1 −2 0 0
3 2 0 0
0 0 1 0
| −3b1 −2b2 +5b3 | b1 +b2 −2b3 | 3b1 +b2 −3b3 | 2b1 +b2 −5b3 +b4 .
(2.23)
Koeffisientmatrisen (2.23) er i redusert trappetrinnsform og svarer til ligningssystemet x1 + 2x2 x3
− x4 + 3x5 + − 2x4 + 2x5 x6 0
= = = =
−3b1 − 2b2 + 5b3 b1 + b2 − 2b3 3b1 + b2 − 3b3 2b1 + b2 − 5b3 + b4 .
Vi ser at ligningssystemet bare har løsninger om 0 = 2b1 + b2 − 5b3 + b4
(2.24)
og n˚ ar ligningen (2.24) er oppfyllt kan vi velge de variable x2 , x4 , x5 fritt lik x2 = s, x4 = t, x5 = u og løsningen til systemet er derfor x1 x2 x3 x4 x5 x6
= = = = = =
−3b1 − 2b2 + 5b3 − 2s + t − 3u s b1 + b2 − 2b3 + 2t − 2u t u 3b1 + b2 − 3b3
for alle tall s, t og u, n˚ ar 0 = 2b1 + b2 − 5b3 + b4 . 65
2.2.12
Elementære matriser
Vi skal se at vi kan erstatte elementære operasjoner p˚ a matriser med matrisemultiplikasjon. For ˚ a oppn˚ a dette innfører vi elementære matriser. Dette har stor teoretisk betydelse. Som vanlig illustrerer vi først teorien med eksempler. Eksempel 2.2.13. La A= Vi har at
1 0 0 0 1 0 a 0 1
1 2 3 −1 4 2 5 −1 0
1 2 3 −1 4 2 5 −1 0
=
.
1 2 3 −1 4 2 5+a −1+2a 3a
.
Istedenfor ˚ a legge a ganger første raden til den tredje raden i matrisen A, kan vi derfor multiplisere A til venstre med den matrisen vi f˚ ar ved ˚ a legge til a ganger første raden til den tredje raden i enhetsmatrisen I3 . Videre har vi at 1 2 3 5 −1 0 0 0 1 −1 4 2 0 1 0 = −1 4 2 . 1 0 0
5 −1 0
1
2 3
Istedenfor ˚ a bytte om første og tredje raden i A kan vi derfor multiplisere A til venstre med matrisen vi f˚ ar n˚ ar vi bytter første og tredje raden i enhetsmatrisen I3 . Til slutt har vi at 1 2 3 1 2 3 1 0 0 −1 4 2 0 1 0 = −1 4 2 . 0 0 a
5 −1 0
5a −a 0
Istedenfor ˚ a multiplisere siste raden i A med a kan vi derfor multiplisere A til venstre med den matrisen vi f˚ ar n˚ ar vi multipliserer siste raden i enhetsmatrisen I3 med a. Definisjon 2.2.14. La m være fiksert, og betrakt (m × m)-matriser. For hvert tallpar 1 ≤ i, j ≤ m, med i 6= j, lar vi 1 0 ··· ··· ··· 0 0 1 ···
···
··· 0
. 0 ··· . . 1 ··· 0 ··· .. .. Eij (a) = . . a ··· 1 ··· 0 ··· .. .. . . . . . 0 ··· ···
···
0 0
··· 1
være matrisen vi f˚ ar av enhetsmatrisen Im ved ˚ a multiplisere den i’te raden med a og legge til den den j’te raden. Videre la 1 0 ··· ··· ··· 0 0 1 ···
···
... 0 ··· 0 ··· 1 .. .. Eij = . . 0 ··· 1 ··· 0 0
···
66
···
··· 0
··· 0 ··· 0
...
··· 1
være matrisen vi f˚ ar av enhetsmatrisen Im ved ˚ a bytte den i’te og j’te raden. Til slutt lar vi 1 0 ··· 0 1 ···
··· 0 ··· 0
... Ei (a) = 0 ··· a ··· .. . . . . ···
0
0
··· 1
være matrisen vi f˚ ar av enhetsmatrisen Im ved ˚ a multiplisere den i’te raden med a 6= 0. Vi kaller matrisene Eij (a), Eij og Ei (a) for elementære matriser. Merk 2.2.15. Det lønner seg ˚ a utføre et par eksempler. Spesielt er det verdt ˚ a merke seg at koordinat (j, i) i matrisen Ei,j (a) er a, og ellers er matrisen lik identitetsmatrisen Im . Setning 2.2.16. La
··· a1n
a11 .. A= .
.. .
am1 ··· amn
være en m × n-matrise. (1) Produktet Eij (a)A er matrisen vi f˚ ar ved ˚ a legge a ganger den i’te raden i A til den j’te raden. Det vil si a11 a12 ··· a1n .. . ai2 ··· ain ai1 . .. Eij (a)A = . aj1 +aai1 aj2 +aai2 ··· ajn +aain .. . am1
am2
···
amn
(2) Produktet Eij A er matrisen vi f˚ ar ved ˚ a bytte om i’te og j’te raden i matrisen A. Det vil si a11 a12 a1n .. . aj1 aj2 ··· ajn .. Eij A = . . ai1 ai2 ··· ain .. . am1 am2 ··· amn
(3) Produktet Ei (a)A er matrisen vi f˚ ar ved ˚ a multiplisere den i’te raden i A med tallet a. Det vil si a11 a12 ··· a1n . aa a ···.. aa in . Ei (a)A = i1 i2 .. . am1 am2 ··· amn
67
Bevis. Alle de tre ligningene følger umiddelbart ved ˚ a utføre matrisemultiplikasjonene Eij (a)A, Eij A respektive Ei (a)A. Korollar 2.2.17. Vi har ligningene ( Eij (a)Eij (−a) = Eij (−a)Eij (a) = Im Eij Eji = Eji Eij = Im , Ei (a)Ei (a−1 ) = Ei (a−1 )Ei (a) = Im . Spesielt finnes det for hver elementær matrise E en annen elementær matrise F slik at EF = F E = Im . Bevis. Dette følger umiddelbart av setningen anvendt p˚ a en elementær matrise E. Merk 2.2.18. Det følger av Setning 2.2.16 at det er det samme ˚ a utføre elementære operasjoner p˚ a en matrise A som det er ˚ a multiplisere A fra venstre med elementære matriser. Gauss-Jordan reduksjon gjør derfor at vi kan multiplisere en n matrise A til venstre med elementære matriser til vi f˚ ar en matrise p˚ a redusert trappetrinnsform. Med andre ord, Gauss-Jordan eliminasjonen gir elementære matriser F1 , F2 , . . . , Fr slik at Fr Fr−1 · · · F1 A = R er en redusert trappetrinnsmatrise. Av Korollar 2.2.17 følger det at vi kan finne elementære matriser E1 , E2 , . . . , Er slik at Ei Fi = Im for alle i. Da har vi at (E1 E2 · · · Er )(Fr · · · F2 F1 ) = E1 E2 · · · Er−1 (Er Fr )Fr−1 · · · F2 F1 = E1 E2 · · · Er−1 Im Fr−1 · · · F2 F1 (2.25) = E1 E2 · · · Er−1 Fr−1 · · · F2 F1 = · · · = Im . Derfor f˚ ar vi at A = Im A = (E1 E2 · · · Er )(Fr · · · F2 F1 )A = E1 E2 · · · Er R. Vi ser at Gauss-Jordan eliminasjonen gir at hver m × n-matrise kan skrives som et produkt av elementære m×m-matriser og en m×n-matrise p˚ a redusert trappetrinnsform. Korollaret uttrykker at de elementære matrisene er invertible i den terminologien vi skal innføre i neste seksjon. Dette, sammen med oppspaltingen av matriser i elementære matriser og trappetrinnsmatriser, gjør at teorien for invertible matriser og determinanter i kommende kapitler blir grei. 68
Oppgaver 2.2.19. 1. For hvilke b har følgende ligningssytemer løsninger? Bestem alle løsningene for de systemene som kan løses (1)
x1 + 2x2 + 2x3 + 19x4 + 0x5 = 7 3x1 + 6x2 + 8x3 + 71x4 + 0x5 = 25 2x1 + 7x2 + 6x3 + 39x4 + 0x5 = 20+b.
(2)
x1 + 2x2 + 3x3 + 26x4 + 21x5 = 9+21b 2x1 + 4x2 + 7x3 + 59x4 + 47x5 = 20+46b 3x1 + 6x2 + 11x3 + 92x4 + 74x5 = 31+74b.
(3)
x1 + 2x2 + 1x3 + 12x4 + 7x5 = 8+b −x1 − 2x2 + 0x3 − 5x4 − 4x5 = −4−b −3x1 − 6x2 − x3 − 22x4 − 14x5 = 15−3b.
(4)
x1 + 2x2 + 3x3 + 5x4 + x5 = 3 −2x1 − 4x2 − 6x3 − 10x4 − 2x5 = −6+b −3x1 − 6x2 − 9x3 − 15x4 − 3x5 = 8−b.
2. Hvilke av matrisene nedenfor er i redusert trappetrinnsform? 1 0 4 0 0 3 (1) 0 0 0 1 0 2 0 0 0 0 1 1
(2)
(3)
1 0
(4)
1 0 0 4 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0
(5)
1 2 3 4 0 5 6 0 0 0 0 1 2 3 0 0 0 0 0 0 0
1 0 4 0 1 3 0 1 0 2 0 1 0 0 0 0 1 2
1 3 0 5 0 1 −1 −2 0 3 0 0 0 0 1 −2
.
3. I Oppgave 1, Seksjon 2.1 skulle du bestemme løsningen til ligningene med koeffisientmatriser 1 5 1 (1) A = 2 17 4 . 3 18 4
(2) A =
1 2 4 2 1 4 3 3 2
.
(3) A =
1 2 2 2 5 5 1 5 5
.
(4) A =
1 2 3 −1 −2 −3 −5 −10 −15
.
Skriv alle disse matrisene som et produkt A = E1 E2 · · · Er R av elementære matriser Ei og en matrise R p˚ a redusert trappetrinnsform. 69
4. I Oppgave 2, Seksjon 2.1 skulle du finne løsningen til ligningene med koeffisientmatriser (1) A = ( 65 11 00 ). 4 ). (2) A = ( 13 27 14 1 1 2 (3) A = ( −2 −2 4 ). 10 1 (4) A = ( 13 −35 3 ).
Skriv alle disse matrisene som et produkt A = E1 E2 · · · Er R av elementære matriser Ei og en matrise R p˚ a redusert trappetrinnsform. 5. I Oppgave 3, Seksjon 2.1 skulle du finne løsningen til ligningene med koeffisientmatriser 1 3 2 7 (1) A = −2 . −8 (2) A =
1 4 2 12 3 4
(3) A =
0 5 0 1 0 6
(4) A =
2 15 1 6 −3 −12
.
.
.
Skriv alle disse matrisene som et produkt A = E1 E2 · · · Er R av elementære matriser Ei og en matrise R p˚ a redusert trappetrinnsform. 6. Bestem alle matrisene X som tilfredsstiller 1 3 −2 4 −3 2 −4 6 X = −2 4 . 3 2
5 −2
1
7. Bestem alle matrisene X som tilfredsstiller 1 0 1 0 2 4 1 1 0 X = 2 3 4 . 1 1 1
1 4 7
8. N˚ ar vi har et lineært ligningssystem med heltallskoeffisienter behøver vi ofte ˚ a bestemme heltallsløsninger til dette systemet. Vil vi bestemme heltallsløsninger til et system med heltallskoeffisienter sier vi at ligningssystemet er diofantisk. La a, b, c, d være tall slik at ad − bc 6= 0. 70
(1) Vis at ligningssystemet ax + by = e cx + dy = f har en eneste løsning. (2) Vis at om a, b, c, d, e, g, f er heltall s˚ a har ligningen heltallsløsninger om ad − bc deler e og f . 9. La a11 x1 a21 x1
+ a12 x2 + a22 x2
+ · · · + a1n xn + · · · + a2n xn .. .
= 0 = 0
(2.26)
am1 x1 + am2 x2 + · · · + amn xn = 0. være et homogent ligningssystem. Anta at Gauss-Jordan eliminasjonen reduserer systemet til x1 x2 xs
+d1s+1 xs+1 + d1s+2 xs+2 + · · · +d1n xn +d2s+1 xs+1 + d2s+2 xs+2 + · · · +d2n xn .. .. . . +dss+1 xs+1 + dss+2 xs+2 + · · · +d2n xn
(1) Vis at alle løsningene til 2.26 er gitt av = = .. .
−d1s+1 ts+1 − d1s+2 ts+2 − · · · − d1n tn −d2s+1 ts+1 − d2s+2 ts+2 − · · · − d2n tn
xs = xs+1 = xs+2 = .. .
−dss+1 ts+1 − dss+2 ts+2 − · · · − dsn tn ts+1 ts+2
x1 x2
xn
=
tn .
for gitte tall ts+1 , ts+2 , . . . , tn . (2) Vis at mengden av løsninger til (1) H = {(a1 , a2 , . . . , an ) : di1 a1 +ai2 a2 +· · ·+ain an = 0} for i = 1, 2, . . . , m er et vektorrom: Det vil si, om P og Q er med i løsningsmengden H da er ogs˚ a P + Q med i H. Og, for en vilk˚ arlig skalær c s˚ a vil cP være med i H om P er med i H. 71
(3) Betrakt de n − s løsningene til ligningene fs+1 = (−b1s+1 , −b2s+1 , . . . , −bss+1 , 1, 0, . . . , 0) fs+2 = (−b1s+2 , −b2s+2 , . . . , −bss+2 , 0, 1, . . . , 0) .. . fn = (−b1n , −b2n , . . . , −bsn , 0, . . . , 0, 1) som svarer til følgende n − s ulike verdier av ts+1 , ts+2 , . . . , tn ts+1 = 1, ts+1 = 0,
ts+2 = 0, ts+2 = 1,
..., ...,
tn = 0 tn = 0
...,
tn = 1.
.. . ts+1 = 0,
ts+2 = 0,
Vis at alle løsningene v i H kan uttrykkes p˚ a formen v = as+1 fs+1 + as+2 fs+2 + · · · + an fn for alle valg av tall as+1 , as+2 , . . . , an . (4) Vis at om as+1 fs+1 + as+2 fs+2 + · · · + an fn = 0 s˚ a vil as+1 = as+2 = · · · = an = 0.
72
Kapittel 3 Determinanter 3.1
Ikke singulære matriser og determinanter
Innledning 3.1.1. De systemene av lineære ligninger vi støter p˚ a har ofte like mange ligninger som ukjente. Vi skal i denne Seksjonen behandle slike systemer. Ofte vil koeffisientmatrisen A være invertibel, det vil si at det finnes en matrise B slik at BA er identitetsmatrisen In . Kjenner vi B kan vi ved ˚ a regne som med tall finne løsningen til ligningssystemet. Vi skal vise hvordan vi kan avgjøre om det finnes en invers, og hvordan man effektivt kan finne denne inversen. Setning 3.1.2. La A være en n × n-matrise. Følgende tre utsagn er ekvivalente. (1) Det finnes en n × n-matrise B slik at BA = In . (2) Den eneste n-vektoren v slik at Av = 0 er nullvektoren. (3) Matrisen A er et produkt A = E1 E2 · · · Er av elementære matriser Ei . N˚ ar betingelsene (1), (2) og (3) holder vil AB = In . Bevis. Anta at betingelsen (1) holder. Om Av = 0 f˚ ar vi at v = In v = (BA)v = B(Av) = B0 = 0. Derfor er v = 0 og betingelsen (2) holder. Anta at betingelsen (2) holder. Vi vet at vi kan skrive A som A = E1 E2 · · · Er R der Ei ’ene er elementære matriser og R er en n × n-matrise i redusert trappetrinnsform. Vi skal vise at R = In s˚ a betingelsen (3) holder. Anta tvert imot at R 6= In . om R = (bij )n,n m˚ a det finnes en indeks j slik at bjj = 0. La i 73
være den minste slike indeksen. Da er 1 0 ··· 0 b1i 0 1 ··· 0 b2i
. . .. .. 0 0 R = 0 0 0 0 . . .. ..
b1i+1 ··· b2i+1 ···
. . . .. .. . .
.. .
.. .. .. . . .
.. .
··· 1 bi−1i bi−1i+1 ··· 0 0 bii+1 ··· 0 0 0
0 0 ··· 0 0 0 ··· 0
0 0
0 0
b1n b2n
.. .
.. . ··· bi−1n ··· bin , ··· bi+1n .. .. . . ··· bn−1n ··· 0
og om v = (−b1i , −b2i , . . . , −bi−1i , 1, 0, . . . , 0)t f˚ ar vi at Rv = 0. Da følger det at Av = E1 E2 · · · Er Rv = 0. Men antagelsen var at om Av = 0 s˚ a er v = 0. Ettersom v 6= 0 har vi en motsigelse mot antagelsen at R 6= In . Derfor m˚ a R = In . Anta at betingelsen (3) holder. Da vil A = E1 E2 · · · Er der E1 , E2 , . . . , Er er elementære matriser. Det følger av Korollar 2.2.17 at vi kan velge elementære matriser F1 , F2 , . . . , Fr slik at Fi Ei = In for alle i. Sett B = Fr · · · F2 F1 . Vi ser av ligningene i Korollar 2.2.17 at BA = Fr · · · F2 F1 E1 E2 · · · Er = In og at AB = E1 E2 · · · Er Fr · · · F2 F1 = In . Derfor følger det at betingelsen (1) holder. Videre følger det at om betingelsen (3) holder s˚ a har vi at AB = In . Definisjon 3.1.3. La A være en n × n-matrise. Vi sier at A er invertibel, eller ikke singulær, om det finnes en matrise B slik at AB = BA = In . Merk 3.1.4. For en n × n-matrise A finnes det bare en matrise B slik at AB = BA = In . Dette er fordi om C er en annen matrise som tilfredsstiller AC = CA = In s˚ a har vi at B = BIn = B(AC) = (BA)C = In C = C. Definisjon 3.1.5. Om A er en ikke singulær n × n-matrise og B er matrisen slik at AB = BA = In s˚ a skriver vi B = A−1 og kaller vi A−1 for den inverse matrisen til A.
3.1.6
Systemer med like mange ligninger som ukjente
La a11 x1 + a12 x2 + · · · + a1n xn = b1 a21 x1 + a22 x2 + · · · + a2n xn = b2 .. . an1 x1 + an2 x2 + · · · + ann xn = bn 74
være et system av n-ligninger med n ukjente. Koeffisientmatrisen til systemet er a11 a12 ··· a1n ! a21 a22 ··· a2n
A=
.. .
.. .
.
an1 an2 ··· ann
Ligningssystemet kan vi skrive som Ax = b der x = (x1 , x2 , . . . , xn )t og b = (b1 , b2 , . . . , bn )t . Dette systemet er spesielt enkelt ˚ a løse n˚ ar A er ikke singulær. Vi har da at x = In x = (A−1 A)x = A−1 (Ax) = A−1 b. Systemet har derfor nøyaktig en løsning og denne løsningen er gitt av x = A−1 b.
3.1.7
Utregning av inverse matriser
Vi s˚ a nettopp at det for systemer av lineære ligninger med like mange ligninger som variable er viktig ˚ a kunne avgjøre om koeffisientmatrisen er ikke singulær. N˚ ar den er ikke singulær f˚ ar vi en løsning om vi kan bestemme den inverse til koeffisientmatrisen. Setning 3.1.2 gir oss en effektiv metode for ˚ a bestemme om en matrise er singulær og til ˚ a regne ut den inverse matrisen n˚ ar den finnes. Vi bruker Gauss-Jordan eliminasjon for ˚ a redusere matrisen til redusert trappetrinnsform, og holder hele tiden orden p˚ a hvilke elementære operasjoner vi har brukt ved b˚ ade ˚ a multiplisere A og identitetsmatrisen In med de elementære matrisene. Eksempel 3.1.8. Vi vil vise at vi samtidig kan avgjøre om matrisen A = ( 13 27 ) er ikke singulær og finne den inverse matrisen n˚ ar denne finnes. Vi skriver 1 2 | 1 0 3 7 | 0 1 . Vi utfører nu elementære operasjoner samtidig p˚ a den venstre matrisen som er koeffisientmatrisen til systemet, og p˚ a den høyre matrisen, som er identitetsmatrisen. Multipliser den første raden med −3 og legg den til den andre raden. Vi f˚ ar 1 2 | 1 0 0 1 | −3 1 . Deretter multipliserer vi den andre raden med −2 og legger den til den første raden. Dette gir 1 0 | 7 −2 . 0 1 | −3 1 75
Til venstre st˚ ar nu identitetsmatrisen, hvilket viser at matrisen A er ikke 7 −2 singulær. Matrisen vil høyre er den inverse matrisen, det vil si A−1 = −3 1 . For ˚ a være sikre p˚ a dette er det bare ˚ a regne ut A−1 A og se at vi f˚ ar I2 . Eksempel 3.1.9. Vi vil vise at vi samtidig kan avgjøre om matrisen A = 1 1 0 2 3 3 er inverterbar, og bestemme inversen n˚ ar den finnes. Vi bruker ele3 5 9 mentære operasjoner p˚ a matrisen 1 1 0 | 1 0 0 2 3 3 | 0 1 0 . 3 5 9 | 0 0 1
Først multipliserer vi den første raden med −2 og −3 og legger den til den andre respektive den tredje raden. Dette gir 1 1 0 | 1 0 0 0 1 3 | −2 1 0 . 0 2 9 | −3 0 1
Deretter multipliserer vi den andre raden med −1 og −2 og legger den til den første respektive den tredje raden. Dette gir 1 0 −3 | 3 −1 0 0 1 3 | −2 1 0 . 0 0 3 | 1 −2 1
Legger vi den siste raden til den første og drar den fra den andre f˚ ar vi 1 0 0 | 4 −3 1 0 1 0 | −3 3 −1 . 0 0 3 | 1 −2 1 1 3
Til slutt multipliserer vi den siste raden med 1 0 0 |
4 −3 1 0 1 0 | −3 3 −1 0 0 1 | 13 − 23 13
og f˚ ar
.
Ettersom vi har enhetsmatrisen til venstre er matrisen ikke singulær. Den 4 −3 1 3 −1 . Igjen kan vi kontrollere høyre matrisen er da inversen A−1 = −3 1 2 1 3
−3
3
v˚ are utregninger ved ˚ a utføre multiplikasjonen A−1 A og se at vi f˚ ar I3 . Eksempel 3.1.10. Metoden vi har brukt avslører, som vi harbemerket, om 1 3 0 en matrise har en invers. Prøver vi metoden p˚ a matrisen A = 5 16 0 m˚ a vi 3 2 0 regne p˚ a matrisen 1 3 0 | 1 0 0 5 16 0 | 0 1 0 3 2 0 | 0 0 1
76
.
Multipliser den første raden med −5 og −3 og legg den til den andre respektive tredje raden. Vi f˚ ar 1 3 0 | 1 0 0 0 1 0 | −5 1 0 0 −7 0 | −3 0 1
.
Deretter multipliserer vi den andre raden med −3 og med 7 og legger den til den første respektive den siste raden. Vi f˚ ar 1 0 0 | 16 −3 0 0 1 0 | −5 1 0 . 0 0 0 | −38 7 1
Ettersom den reduserte trappetrinnsmatrisen vi har til venstre ikke er I3 følger det av Setning 3.1.2 at matrisen A ikke har noen invers. Da kan heller ikke den inverse st˚ a til høyre.
3.1.11
Generell invers til en matrise
For ˚ a bestemme om en n × n-matrise A har en invers og finne den inverse om matrisen er invertibel utfører vi elementære operasjoner p˚ a n × 2n-matrisen C = (A | In ) som har matrisen A til venstre om skillelinjen og matrisen In til høyre. Vi multipliserer A med elementære matriser F1 , F2 , . . . , Fr til vi har at matrisen Fr · · · F2 F1 A = R er p˚ a redusert trappetrinnsform. Vi har da redusert matrisen til D = (Fr · · · F2 F1 A | Fr · · · F2 F1 ) = (R | Fr · · · F2 F1 ). Det følger av Setning 3.1.2 at A er invertibel nøyaktig n˚ ar R = In , det vil si n˚ ar Fr · · · F2 F1 A = In . Sett B = Fr · · · F2 F1 . Da er B inversen til A fordi BA = Fr · · · F2 F1 A = In . Vi har derfor at n˚ ar A er invertibel s˚ a leder Gauss-Jordan eliminasjon anvendt p˚ a den utvidete matrisen med A til venstre og In til høyre til matrisen (In | A−1 ) som vi har sett i eksemplene ovenfor.
3.1.12
Determinanter
Determinanter oppst˚ ar overalt i matematikken. De kommer inn p˚ a de mest uventete steder. Vi har allerede sett at de uttrykker volymer av parallellepiped. De spiller en fundamental rolle, som Jakobianer, for ligninger i flere 77
variable, og for differensiallikninger forekommer de som Wronskianer og Pfaffianer. I lineæralgebraen bruker vi blandt annet determinanter til˚ a gi kriterier for ikke singulære matriser, og i eksplisitte løsninger, som Cramers regel, for løsninger av systemer av lineære ligninger. Determinanter har mest teoretisk interesse. N˚ ar vi skal regne ut determinanter bruker vi oftest varianter av Gauss-Jordan eliminasjon. Her skal vi gi de viktigste egenskapene til determinanter og gi noen metoder for hvordan man beregner dem. Først er det hendig ˚ a kjenne til permutasjoner og deres viktigste egenskaper. Definisjon 3.1.13. En permutasjon σ av tallene (1, 2, . . . , n) er en omordning (σ(1), σ(2), . . . , σ(n)) av disse tallene. Det vil si at σ(1), σ(2), . . . , σ(n) er tallene 1, 2, . . . , n i noen rekkefølge. Vi kan yttrykke det samme ved at en permutasjon σ er en bijeksjon σ : N → N av mengden N = {1, 2, . . . , n} til seg selv. Mengden av alle permutasjoner betegner vi med Sn . Vi kaller Sn den symmetriske gruppen p˚ a n-bokstaver. Det er klart at Sn har n! = 1 · 2 · · · n elementer. Sammensetningen τ σ av to permutasjoner σ : N → N og τ : N → N , er sammensetningen som avbildninger, det vil si vi bruker først avbildningen σ og deretter τ og f˚ ar bijeksjonen τ σ : N → N , det vil si (τ σ)(i) = τ (σ(i)) for alle i. Den spesielle permutasjonen som tar i til j og j til i, men som holder alle andre tall fast betegner vi med τij . Det vil si vi har at τij (i) = j, τij (j) = i, og τij (k) = k for alle k forskjellig fra i og j. Vi kaller permutasjoner p˚ a formen τij for transposisjoner. Avbildningen som holder alle elementene 1, 2, . . . , n fast skriver vi som id. Eksempel 3.1.14. Vi har at S2 = {id, τ12 }. Videre har vi S3 = {id, τ23 = (1, 3, 2), τ12 = (2, 1, 3), σ = (2, 3, 1), τ = (3, 1, 2), τ13 = (3, 2, 1)}. Vi har for eksempel στ13 = (1, 3, 2) = τ23 og τ13 σ = (2, 1, 3) = τ12 . Definisjon 3.1.15. Vi sier at et par (ij) med i < j er en inversjon for en permutasjon σ om σ(i) > σ(j). Tegnet sign(σ) til σ er 1 om antallet inversjoner til σ er like og −1 om antallet inversjoner er odde. 78
Eksempel 3.1.16. Identiteten id har ingen inversjoner s˚ a sign(id) = 1. I S3 har vi sign(τ23 )=−1 sign(τ12 )=−1 sign(σ) = 1 sign(τ ) = 1 sign(τ13 )=−1
fordi fordi fordi fordi fordi
τ23 (2) > τ23 (3) τ12 (1) > τ12 (2) σ(1) > σ(3), σ(2) > σ(3) τ (1) > τ (2), τ (1) > τ (3) τ13 (1) > τ13 (2), τ13 (1) > τ13 (3), τ13 (2) > τ13 (3).
Merk 3.1.17. Om vi skal bytte om tallene i og j blandt tallene (1, 2, . . . , n) uten ˚ a flytte de andre tallene kan vi gjøre det ved ˚ a flytte i en plass til høyre j−i-ganger, til vi bytter den med j. Vi f˚ ar da permutasjonen (1, 2, . . . , i−1, i+ 1, . . . , j − 1, i, j + 1, . . . , n). Deretter flytter vi j en plass til venstre j − i − 1 ganger til vi bytter den med i + 1. Vi f˚ ar da permutasjonen (1, 2, . . . , i − 1, j, i + 1, . . . , j − 1, i, j + 1, . . . ). Med andre ord har vi at τij = (τii+1 τi+1i+2 · · · τ(j−3)(j−2) τ(j−2)(j−1) )(τ(j−1)j τ(j−2)(j−1) · · · τ(i+1)(i+2) τi(i+1) ) (3.1) for hver permutasjon σ i Sn vil permutasjonene σ og στii+1 bare skille seg p˚ a hvordan de flytter tallene i og i + 1 og vi har στii+1 (i) = σ(i + 1) og στii+1 (i + 1) = σ(i). Derfor er (i, i + 1) en inversjon i den ene men ikke i den andre, og alle andre inversjoner er de samme. Derfor har vi at sign(στii+1 ) = −sign(σ).
(3.2)
Ved ˚ a bruke dette j − i − 1 + j − i = 2(j − i) − 1 ganger i formelen (3.1) ser vi at sign(στij ) = −sign(σ). Spesielt har alle transposisjoner negativt tegn. Definisjon 3.1.18. La A være en n × n-matrise. Summen X det A = sign(σ)a1σ(1) a2σ(2) · · · anσ(n)
(3.3)
σ∈Sn
kalles determinanten til A. Determinanten er følgelig en sum der termene er pluss eller minus produktet av en koordinat fra hver rekke og en fra hver søyle. Tegnet er bestemt av antallet ganger vi g˚ ar til venstre n˚ ar vi velger koordinatene vi multipliserer med. Dette er fordi inversjonene i den tilsvarende permutasjonen svarer til at vi g˚ ar til venstre. a12 Eksempel 3.1.19. For A = ( aa11 21 a22 ) har vi X det A = a1σ(1) a2σ(2) = a11 a22 + sign(τ12 )a1τ12 (1) a2τ12 (2) = a11 a22 − a12 a21 . σ∈S2
79
For matrisen A = det A =
X
a11
a12 a13 a21 a22 a23 a31 a32 a33
har vi
a1σ(1) a2σ(2) a3σ(3) = a11 a22 a33 + sign(τ23 )a1τ23 (1) a2τ23 (2) a3τ23
σ∈S3
+ sign(τ12 )a1τ12 (1) a2τ12 (2) a3τ12 (3) + sign(σ)a1σ(1) a2σ(2) a3σ(3) + sign(τ )a1τ (1) a2τ (2) a3τ (3) + sign(τ12 )a1τ13 (1) a2τ13 (2) a3τ13 (3) = a11 a22 a33 − a11 a23 a32 − a12 a21 a33 + a12 a23 a31 + a13 a21 a32 − a13 a22 a31 = a11 a22 a33 + a12 a13 a31 + a13 a21 a32 − a11 a23 a32 − a12 a21 a13 − a13 a22 a31 . For ˚ a huske formelen for det A til en 3 × 3-matrise skriver vi opp matrisen to ganger ! a11
a21
a12
&
a31
a22 a32
a13
&
. &
a13 a13
a11
. &
. &
a21 a31
a12
.
. &
a22
a13
.
a32
a23 a33
og tar summen av termene vi f˚ ar n˚ ar vi multipliserer til høyre med pluss og til venstre med minus. Setning 3.1.20. Determinanten har tre fundamentale egenskaper (1) Multipliserer vi en rekke i A med tallet a vil determinanten multipliseres med a. Det vil si a11 ... a1n a11 ... a1n . aai1 ..... aain .. det . = a det ... . .. an1 ... ann . an1 ... ann
(2) Om hver koordinat i en rekke til A er en sum av to termer vil determinanten til A være en sum av determinantene til matrisene vi f˚ ar n˚ a bare en av hver term er med i matrisen. Det vil si a11 ... a1n a11 ... a1n a11 ... a1n .. .. .. .. .. .. . . . . . . b +c det i1 i1 ... bin +cin = det bi1 ... bin + det ci1 ... cin .. .. .. .. .. .. . . . . . . an1
...
ann
an1 ... ann
an1 ... ann
(3) Om to rekker i en matrise A er like s˚ a er determinanten lik 0. Det vil si a11 ... a1n . .. .. . a1 ... an . .. det .. = 0. a1 ... a.n . .. .. . an1 ... ann
80
Bevis. Det er klart at egenskapene (1) og (2) holder ettersom vi har at hvert produkt a1σ(1) a2σ(2) · · · anσ(n) inneholder nøyaktig et element fra hver rekke og vi har de to ligningene a1σ(1) · · · aaiσ(i) · · · anσ(n) = aa1σ(1) · · · anσ(n) og a1σ(1) · · · (biσ(i) + ciσ(i) ) · · ·anσ(n) = a1σ(1) · · · biσ(i) · · · anσ(n) + a1σ(1) · · · ciσ(i) · · · anσ(n) . For ˚ a vise p˚ astanden (3) merker vi at ettersom aik = ajk for alle k s˚ a vil termene a1σ(1) · · · aiσ(i) · · · ajσ(j) · · · anσ(n) og a1τ (1) · · · aiτ (i) · · · ajτ (j) · · · anτ (n)
(3.4)
være like n˚ ar σ(k) = τ (k) n˚ ar k er forskjellig fra i og j og σ(i) = τ (j) og σ(j) = τ (i). Med andre ord er termene (3.4) like n˚ ar τ = στij . Men i determinanten forekommer det første leddet i (3.4) med koeffisienten sign(σ) og den andre med sign(τ ). Ettersom vi har sett i Bemerkning 3.1.17 at sign(τ ) = sign(στkj ) = −sign(σ) vil de to leddene summere til null. Korollar 3.1.21. Om vi bytter om to rekker i en matrise, vil determinanten bytte tegn. Det vil si a11 ... a1n a11 ... a1n .. .. . .. . . . .. a ... a a ... a i1 j1 in jn .. .. = − det .. .. det . . . . aj1 ... ajn ai1 ... a.in . . .. .. .. .. . . an1 ... ann
an1 ... ann
Bevis. Det følger av (3) at determinanten til matrisen a11 ... a1n .. .. . . a +a ... a +a in jn i1 j1 . .. .. . ai1 +aj1 ... ain +a jn .. .. . . an1
...
(3.5)
ann
er null. Bruker vi egenskapen (2) tre ganger p˚ a determinanten av matrisen (3.5) f˚ ar vi at den er summen av determinantene til de fire matrisene a11 ... a1n a11 ... a1n a11 ... a1n a11 ... a1n .. .. .. .. . .. .. .. . . . . a. ... a . .. . jn ai1 ... ain ai1 ... ain j1 aj1 ... ajn .. .. .. .. .. , ... , ... , ... . (3.6) . . . . . aj1 ... ajn ai1 ... ain aj1 ... ajn ai1 ... ain . . . .. .. .. .. .. . .. . . . . . . . . an1 ... ann
an1 ... ann
an1 ... ann
81
an1 ... ann
Det følger av egenskapen (1) at de to midterste matrisene i (3.6) har determinant lik null. Derfor har determinanten til de to ytterste matrisene i (3.6) motsatt tegn. Merk 3.1.22. Bytter vi om to rader i en matrise bytter determinanten tegn. Derfor er det(Eij A) = − det A. Spesielt har vi at det Eij = −1. Multipliserer vi en rad med et tall a følger det av egenskapen (1) at determinanten multipliseres med a. Derfor er det(Ei (a)A) = a det A, og spesielt vil det Ei (a) = a. Videre, multipliserer vi en rekke i en matrise med a og legger den til en annen matrise f˚ ar vi av egenskapen (2) at determinanten er den samme som summen av determinanten til A og determinanten til den matrisen der en rekker er a ganger en annen rekke. Det følger av egenskapene (1) og (2) at determinanten der en rekke er et tall ganger en annen rekker er null. Derfor har vi at det(Eij (a)A) = det A. Spesielt f˚ ar vi at det Eij (a) = 1. Vi har vist at det Eij (a) = 1, det Ei (a) = a, det Eij = −1 og for hver matrise A og hver elementær matrise E har vi at det(EA) = det E det A. Merk 3.1.23. Determinanten til en øvre diagonal matrise a11 a12 ... a1n ! A=
0 a22 ... a2n
.. .
0
.. 0
. . ..
... ann
er produktet av diagonalelementene a11 a22 · · · ann . Med andre ord har vi at det(A) = a11 a22 · · · ann . Dette er fordi vi tar produkter fra alle rekker og søyler s˚ a det eneste elementet i summen for determinanten 3.1.18 er det som ikke inneholder 0 er produktet av diagonalelementene. Merk 3.1.24. Formelen (3.3) kan brukes til ˚ a regne ut determinanter for 2 × 2-matriser, og den er ganske bra for 3 × 3-matriser. For større matriser er det ofte raskere ˚ a bruke Gauss-Jordan eliminasjon, eller snarere en forenklet variant av denne. Vi ser for eksempel av 3.1.23 at vi ikke behøver ˚ a redusere til den reduserte trappetrinnsformen. Det rekker ˚ a redusere til en trappetrinnsform der elementene ovenfor de ledende koordinatene kan være forskjellig fra null. Dette kalles Gauss eliminasjon. Av 3.1.22 ser vi at vi i Gauss eliminasjonen bare behøver ˚ a holde orden p˚ a ombytte av rekker, som svarer til at determinanten bytter tegn, og multiplikasjon av en rekke med et tall, som betyr at determinanten multipliseres med dette tallet. Nedenfor skal vi gi et par eksempler p˚ a hvordan vi kan regne ut determinanter til matriser p˚ a ulike m˚ ater. Hver person som skal regne ut determinanter kan spare mye arbeide ved ˚ a bruke sin fantasi. 82
1 2 3 Eksempel 3.1.25. Bruker vi Gauss eliminasjon p˚ a matrisen A = 4 −1 2 7 3 1 multipliserer viførste rekke med −4 og −7 og drar fra andre respektive tredje 1 2 3 rekke s˚ a vi f˚ ar 0 −9 −10 . Multipliserer vi nu den andre raden med − 91 s˚ a f˚ ar 0 −11 −20 1 2 3 vi 0 1 109 . Deretter legger vi 11 ganger andre rekke til den tredje og f˚ ar 1 2 0 −113 −20 10 0 1 9 . Determinanten til den siste matrisen er (−20·9+10·11)/9 = 10 0 0 −20+
9
11
−70/9. Under eliminasjonen har vi multiplisert med −1/9. Derfor har vi at det A = (−9)(−70/9) = 70. Det bemerkelsesverdige er at vi av formelen 3.1.18 med det samme ser at determinanten skal være et heltall, men at brøker oppst˚ ar p˚ a veien, og forsvinner i det endelig svaret. Vi kan ved ˚ a være litt smarte redusere brøkregningene og holde orden p˚ a konstanter. Eliminasjonen kan for eksempel gjøres litt anderledes som 1 2 3 1 2 3 1 2 9 3 1 2 3 1 2 3 10 4 −1 2 . → 0 −9 −10 → 0 9 10 −−−→ 0 9 10 → 00 90 180−11·10 0 −11 −20
7 3 1
0 11 20
0 11·9 20·9
Determinanten av den siste matrisen er 9 · (180 − 110) = 9 · 70, men ettersom vi under eliminasjonen har multiplisert en rad med med 9 blir det A = 70. 3 18 36 Eksempel 3.1.26. Gauss eliminasjon brukt p˚ a matrisen A = 9 43 115 gir 11 40 222
3 18 36 9 43 115 11 40 222
1 3
−−−→
1 6 12 9 43 115 11 40 222
→
1
6 12 0 −2 7 0 −26 90
− 21
−−−→
1 6 12 0 1 − 72 0 −26 90
1 6
→
12 0 1 − 72 0 0 90− 72 26
Determinanten til den siste matrisen er 90 − 7 · 13 = −1. Ettersom vi p˚ a 1 1 veien har multiplisert med 3 og − 2 blir det A = 3(−2)(−1) = 6. Vi kan forenkle den siste delen av regningen ved ˚ a observere at vi ved a ˚ 1 6 12 legge til −13 ganger den andre rekken til den tredje i matrisen 0 −2 7 f˚ ar 0 −26 90 1 6 12 matrisen 0 −2 7 , som har determinant lik 2. Vi f˚ ar derfor det A = 3·2 = 6. 0 0 −1
Setning 3.1.27. La A og B være to n × n-matriser. (1) Matrisen A er ikke-singulær hvis og bare hvis det A 6= 0. (2) Vi har at det(AB) = det A det B. Bevis. Vi kan skrive matrisene A og B p˚ a formen A = E1 E2 · · · Er R respektive B = F1 F2 · · · Fs S der R og S er reduserte trappetrinnsmatriser og Ei og Fi er elementære matriser. Vi har sett at A og B er ikke-singulære hvis og bare hvis R respektive S er enhetsmatrisen In . Det følger av Bemerkning 83
.
3.1.23 at R = In hvis og bare hvis det R 6= 0. Av Bemerkningen 3.1.22 har vi at det A = det E1 det E2 · · · det Er det R og vi vet at determinanten til en elementær matrise er forskjellig fra null. Derfor er det A 6= 0 hvis og bare hvis det R 6= 0, hvilket holder hvis og bare hvis R = In . Vi har derfor at det A 6= 0 hvis og bare hvis A er et produkt av elementære matriser, og det følger av Setning 3.1.2 at dette er det samme som at A er ikke-singulær. Det følger ogs˚ a at egenskapen (2) holder n˚ ar A og B er ikke-singulære ettersom vi da har at det(AB) = det E1 det E2 · · · det Er det F1 det F2 · · · det Fs = det A det B. Videre gjelder formelen om B er singulær. Dette er fordi da m˚ a AB være singulær fordi vi f˚ ar av Setning 3.1.2 at det finnes en ikke null vektor v slik at Bv = 0 og derfor ABv = 0. Det følger da av del (1) av Setningen at begge sider av ligningen (2) er null. Til slutt anta at B er ikke singulær og A er singulær. Da finnes en vektor w 6= 0 slik at Aw = 0. Vi har at B er invertibel s˚ a den inverse B −1 finnes og vi setter v = B −1 w. Da er v 6= 0 fordi w = Bv. Men vi har at ABv = ABB −1 w = Aw = 0 s˚ a da er AB singulær. Men n˚ ar A og AB er singulære følger igjen formel (2) av formel (1) ettersom begge sidene i (2) er null. Oppgaver 3.1.28. 1. I Oppgave 1 i Seksjon 2.1 skulle du finne løsningen til ligningene med koeffisientmatriser 1 5 1 (1) A = 2 17 4 . 3 18 4
(2) A =
1 2 4 2 1 4 3 3 2
.
(3) A =
1 2 2 2 5 5 1 5 5
.
(4) A =
1 2 3 −1 −2 −3 −5 −10 −15
.
Bestem hvilke av matrisene som er invertibel og finn den inverse for disse. 2. Beregn determinantene til matrisene 2 3 5 (1) 7 −1 0 . 3 −2 1
(2)
2 10 8 −7 −17 −37 −8 −28 −36
. 84
(3) (4) (5)
16 −14
12 40 −29 9 56 −67 105
−6
12 24 −4 2 −5 2 −14 −49
15 20 35 18 17 105 9 11 28
.
.
.
3. For hvilke x er determinanten til matrisen 1 2 x 1 0 −2 2 1 3 1 −1 2 −1 0 0 2
større eller lik null. (KTH 2000). 4. En 3 × 3-matrise A defineres av x x+3y A yz = 2y−z . x+z
Er A inverterbar? (KTH 1999). Hint. Sett in passende verdier for x, y, z. 1 2 1 5. La A = 0 −1 0 . 1 1 λ
(1) For hvilke verdier av λ har matrisen A en invers? (2) Finn inversen for disse verdiene av λ. 6. Vis at om a, b, c, d er hele tall slik at ad − bc = 1 s˚ a er matrisen A = ( ac db ) invertibel og den inverse matrisen har heltallskoeffisienter. 7. La A og B være ikke singulære n × n-matriser. Vis at den inverse til AB er (AB)−1 = B −1 A−1 . 8. Vis at om A = (aij ) er en invertibel matrise s˚ a er den transponerte At = t −1 −1 t (aji ) ogs˚ a invertibel og (A ) = (A ) . Hint. Vi først at formelen holder for elementære matriser. 9. La A være en m × n-matrise med m < n. (1) Vis at n × n-matrisen At A alltid er singulær. (2) Vis at m × m-matrisen AAt kan være b˚ ade singulær og ikke singulær. 85
10. La Pn være mengden av n×n-permutasjonsmatriser definert i 9, Seksjon 1.4 og la ϕ : Sn → Pn være avbildningen definert ved ϕ(σ) = (aiσ(j) )nn . Vis at for alle σ i Sn s˚ a har vi sign(σ) = det(ϕ(σ)). 11. La A = (aij ) være en n × n-matrise. For alle i og j lar vi Aij være den (n − 1) × (n − 1)-matrisen vi f˚ ar ved ˚ a stryke rad i og kolonne j i A. Vis at (1) det A = ai1 det Ai1 − ai2 det Ai2 + · · · + ain det Ain . (2) det A = a1j det A1j − a2j det A2j + · · · + anj det Anj . 12. La A og B være n × p-matriser. Vi skriver A(i1 , i2 , . . . , ip ) og B(i1 , i2 , . . . , ip ) for de p × p-matrisene matrisene vi f˚ ar ved av kolonne nummer i1 , i2 , . . . , ip i A respektive B. Vis at X det(At B) = det A(i1 , i2 , . . . , ip ) det B(i1 , i2 , . . . , ip ). 0≤i1 0 og n1 + · · · + np ≤ n. Vi har ogs˚ a at den eneste vektoren som er med i to forskjellige egenrom, er null-vektoren. 128
Bevis. Dimensjonen dim(Ei ) = ni til et vektorrom er antallet vektorer i en bas. At ni > 0 er ekte større enn null er det samme som at det finnes nullskilte vektorer x ∈ Ei . Siden λi var antatt ˚ a være en egenverdi har vi at determinanten det(λi In − A) = 0. Av Sats (3.1.2) finnes det dermed ikke trivielle løsninger x. Dette viser at ni > 0. La oss n˚ a vise den siste p˚ astanden. La x være en vektor som er med i b˚ ade Ei og Ej . Vi f˚ ar da at λi x = TA (x) = λj x. Det vil si at (λi − λj )x = 0. Siden egenverdiene λi 6= λj følger det n˚ a at x = 0. Dette viser at kun null-vektoren er med i to forskjellig egenrom. Vi skal n˚ a vise at n1 + . . . + np ≤ n. Siden hvert egenrom E1 , . . . , Ep er delrom av Rn har de alle en basis (Setning 4.4.21). La βi = {xi,1 , . . . , xi,ni } være en basis for egenerommet Ei . La β være vektorene som forekommer i β1 , β2 , . . . , βp . Vi trenger kun ˚ a vise at alle vektorene i β tilsammen satisfierer (2) i Definisjon 4.4.16. Fordi, om vektorene satisfierer (2) da kan de utvides til en basis for Rn ved Proposisjon 4.4.19. Dette igjen betyr at det totale antallet vektorer i β1 , . . . , βp som er n1 + · · · + np m˚ a være mindre eller lik n. Anta derfor at vi at har en sum nj np n2 X X X 0= a1,j x1,j + a2,j x2,j + · · · + ap,j xp,j . (4.7) j=1
j=1
j=1
Vi vil vise at alle koeffisientene ai,j er null. La oss kalle de forskjellig summene for v1 , . . . , vp , der ni X vi = ai,j xi,j ∈ Ei . (4.8) j=1
Om vi = 0 s˚ a vil ligningen (4.8) i Ei medføre at ai,j = 0 for alle j = 1, . . . , ni siden vektorene βi = {xi,1 , . . . , xi,ni } er en basis for Ei , og spesielt satisfierer vektorene (2) i Definisjon 4.4.16. Det er dermed nok ˚ a vise at v1 = . . . = vp = 0 er alle null-vektoren. Om en vektor, si v1 var forskjellig fra null ser vi av ligningen (4.7) at −v1 er en lineær kombinasjon av vektorene i β2 , . . . , βp . Dette betyr at det finnes null-skilte vektorer i b˚ ade E1 og i Ei for minst en i 6= 1. Dette har vi vist over er umulig. Korollar 4.4.27. Om en (n × n)-matrise A har n forskjellige egenvektorer, da finnes det nøyaktig n invariante linjer. Med andre ord, la de forskjellige egenrommene være E1 , . . . , En , og sett dimEi = ni . Vi har at ni = 1 og at n1 + · · · + nn = n. Bevis. Hver egenverdi λ1 , . . . , λn gir egenrom E1 , . . . , En . Disse egenrommene har dimensjon minst 1, men siden deres sum er mindre eller lik n, er egenrommene en-dimensjonale. Dette betyr at egenrommene er linjer. 129
Eksempel 4.4.28. Matrisen A i Eksempel (4.4.12) var en (2 × 2)-matrise, med to forskjellige egenverdier λ1 = −1 og λ2 = 2. Vi har dermed at egenrommene E1 og E2 begge er linjer. Disse invariante linjene har vi eksplisitt beskrevet i eksemplet. Merk 4.4.29. Anta n˚ a at matrisen A har n forskjellige egenverdier, og la L1 , . . . , Ln være de n-forskjellige invariante linjene. La vidre xi ∈ Li være en vektor forskjellig fra null. Vi har sett i Eksempel (4.4.18) at xi er en basis for Li , og vi har sett at β = {x1 , . . . , xn } satisfierer (2) i Definisjon 4.4.16. Siden antallet vektorer i β er lik n, s˚ a er β en basis. Dette betyr at hver vektor x ∈ Rn kan skrives som x = a1 x1 + a2 x2 + . . . + an xn .
(4.9)
Vi vet hvordan avbildningen TA virker p˚ a de invariante linjene; avbildningen strekker linjen Li med faktoren λi . Men, vi vet ogs˚ a hvordan avbildningen TA virker p˚ a en villk˚ arlig vektor x. Fordi vi kan uttrykke vektoren x som en sum (4.9), og da vil TA (x) = λ1 a1 x1 + λ2 a2 x2 + . . . + λn an xn . Denne observasjonen er viktig b˚ ade for den teoretiske forst˚ aelsen av avbildninger, og for praktiske anvendelser. Oppgaver 4.4.30. 1. Finn karakteristisk polynom, egenvektorer og egenverdier til matrisen A, n˚ ar 1 2 1 0 0 0 a) A = b) A = c) A = 0 2 0 2 0 0 0 1 2 1 1 1 d) A = e) A = f) A = 1 0 1 2 1 1 2. Finn egenverdier og egenvektorer til den lineære avbildning TA : R2 → R2 som gis ved a) Speiling om x-aksen. b) Speiling om linjen x = y. c) Projeksjon ned p˚ a x-aksen. d) Projeksjon ned p˚ a linjen x = y. e) Projeksjon ned p˚ a linjen 2x = y. 130
f) Speiling om linjen 2x = y. g) Speiling om en gitt linje L som g˚ ar gjennom vektoren (0,0). h) Projeksjon ned p˚ a en gitt linje L som g˚ ar gjennom vektoren (0,0). i) Rotasjon, rundt (0,0), med en vinkel med 60 grader. 3. La Tθ : R2 → R2 være en rotasjon med vinkel θ. Avgjør hvilke rotasjonsvinkler θ som har egenvektorer. 4. La A være en (n × n)-matrise, og λ1 en egenverdi. Vis at løsningsmengden E1 = {x ∈ Rn | TA (x) = λ1 x} er et vektorrom. 5. La β = {v1 , . . . , vn } være en sekvens av vektorer i et vektorrom V , og anta at β tilfredstiller krav (2) i Definisjon (4.4.16). Vis at dette kravet er ekvivalent med nullvektoren 0 kan kun skrives som 0 = 0 · v1 + 0 · v2 + · · · + 0 · vn .
131
Kapittel 5 Anvendelser 5.1
Et eksempel med Markov kjeder
Vi vil i denne seksjonen gi et eksempel p˚ a en Markovkjede. Eksemplet er kanskje ikke helt realistisk, men realistiske anvendelser finns - noe vi skal se senere.
5.1.1
Lunsjmodellen
Ved en ikke navngitt skole har de to typer p˚ alegg A og B. Elevene velger selv p˚ alegg, men det viser seg at deres valg er helt bestemt av hva de valgte dagen før. En elev som dagen før valgte p˚ alegget A vil idag forkaste dette alternativet, og dermed velge p˚ alegg B. Derimot vil 25 prosent av elevene som valgte p˚ alegg B ig˚ ar g˚ a tilbake til p˚ alegg A idag (˚ aja, minnet er kort).
5.1.2
Matematisk modell
La oss beskrive lunsjmodellen over med matriser, og spesielt f˚ a frem et matematisk uttrykk for hvordan fordelingen skjer med tid. Vi registrerer hvor mange som velger de forskjellige p˚ alegg den første dagen. Om T er det totale antallet elever, og t er antallet elever som velger p˚ alegget A, da sier vi at t/T er andelen som valgte A. La a1 være andelen elevene som velger p˚ alegg A, og b1 andelen av elevene som velger p˚ alegg B. Vi vil hele tiden anta att en elev alltid velger p˚ alegg A eller B, og spesielt har vi at a1 + b1 = 1. Sett a X1 = 1 , b1 og vi kaller X1 initialvektoren. Gitt initalvektoren X1 og vi kan lese av hvordan valgfordelingen blir ved dag to. Vi lar a2 være andelen av studenter som 132
velger p˚ alegg A den andre dagen, og b2 andelen som velger p˚ alegg B den andre dagen. Av modellen har vi dermed at a2 = 0 · a1 + 14 b1 , og vi har at b2 = a1 + 43 b1 . Skriver vi dette p˚ a matrise form, har vi a2 0 · a1 + 0.25 · b1 X2 = = . (5.1) b2 1 · a1 + 0.75 · b1 Vi kan fortsette p˚ a samme m˚ ate og finne X3 = [a3 , b3 ]tr som 0 · a2 + 0.25 · b2 . X3 = 1 · a2 + 0.75 · b2
(5.2)
Vi kan deretter sette inn verdiene for X2 = [a2 , b2 ]tr og uttrykke X3 i termer av initialverdiene. Dvs, i utrykkene for X3 substituerer vi verdiene for a2 og b2 med de uttrykkene vi fant i (5.1). Dette gir 1 3 3 1 a + b a + b 1 1 1 1 16 = 43 X3 = 1 4 3 16 3 . 13 b + (a + b ) a + b 1 1 1 1 4 4 4 4 16 1
5.1.3
Matrisepotenser
Kikker vi en stund p˚ a uttrykkene (5.1) og (5.2) for fordelingene X2 og X3 , ser vi følgende. Vi har at 1 1 2 0 4 a2 a1 0 4 = . X3 = 1 34 b2 1 34 b1 La derfor
0 H= 1
1 4 3 4
,
og la Xn = [an , bn ]tr være fordelingen ved dag n. Vi har att fordelingen ved dag (n + 1) gis ved 0 · an + 14 bn . Xn+1 = H · Xn = an + 34 bn Det følger n˚ a at Xn+1 = HXn = H · H · Xn−1 = · · · = H n · X1 , og vi har en lukket formel som beskriver fordelingen ved en hvilken som helst dag, gitt at vi kjenner fordelingen ved dag 1. Vi har 3 13 1 3 2 3 4 16 64 H = 3 13 , H = 16 13 51 . 4
16
16
133
64
5.1.4
Markovkjeder
En m-vektor X = (p1 , . . . , pm ) hvis koordinater pi ≥ 0 er ikke-negative og som summerer opp som p1 +· · ·+pm = 1, kalles en utfallsvektor. Vi tenker oss at vi har m stykk utfall av en gitt hendelse, og sannsynligheten for at utfall i skal forekomme gis ved sannsynlighet pi . For eksempel, i lunsjmodellen har vi at hendelsen er ˚ a velge p˚ alegg, og de to mulige utfall vi har er at p˚ alegg A eller p˚ alegg B velges. En (m × m)-matrise H hvor hver kolonne er en utfallsvektor kalles en stokastisk matrise. En sekvens av utfallsvektorer X1 , X2 , . . . , kalles en Markovkjede hvis det finnes en stokastisk matrise H slik at Xn+1 = HXn for alle n > 1. Eksempel 5.1.5. Lunsjmodellen beskrevet over er et enkelt eksempel p˚ a en Markovkjede. Proposisjon 5.1.6. La H være en stokastisk matrise, og la X være en vektor. Da vil summen av koordinatene til HX være lik summen av koordinatene til X. Spesielt, om X er en utfallsvektor da er ogs˚ a HX en utfallsvektor. Bevis. La X = [p1 , . . . , pm ]tr og la hi,j være koeffisientene til den stokastiske matrisen H. Koeffisientene [q1 , . . . , qm ]tr til produktet HX gis ved formelen qi =
m X
hi,j xj ,
for i = 1, . . . , m.
(5.3)
j=1
Vi har at m X i=1
qi =
m X m X i=1 j=1
hi,j xj =
m m X X j=1
hi,j xj =
i=1
m X
xj .
j=1
Dette viser at koeffisientene til X summerer opp til samme verdi som koeffisientene til HX. Det er videre klart at koeffisientene (5.3) er positive, slik at hvis X er en utfallsvektor følger det at ogs˚ a HX er en utfallsvektor. I lunsjmodellen over har vi et lukket uttrykk for situasjonsfordelingen ved dag n. Vi ønsker mere eksplisitt ˚ a lese av hva fordelingen blir. Eksempel 5.1.7. Betrakt matrisen 1 1 Q= . 4 −1 Dette er en inverterbar matrise med invers 1 1 1 −1 Q = . 5 4 −1 134
La H være matrisen fra eksemplet med lunsjmodellen. Vi har dermed at v˚ ar 1 0 −1 Q HQ = 0 − 41 er en diagonalmatrise. Proposisjon 5.1.8. La P være en (m × m)-matrise. Og anta at det finnes en inverterbar matrise Q slik at Q−1 P Q = D er en diagonalmatrise d1 0 · · · 0 . . . .. . 0 d2 D=. . . . .. .. 0 .. 0 ··· dm Da har vi, for hvert heltall n ≥ 0 at n d1 0 · · · 0 . . . .. . −1 0 dn2 n P = Q . . Q . . .. .. 0 .. 0 ··· dnm Spesielt ser vi at produktet P n reduseres til et produkt av tre matriser. Bevis. Vi har at Q−1 P Q = D, og dermed ogs˚ a at P = QDQ−1 . Dermed blir P n = (QP Q−1 )(QP Q−1 ) · · · (QP Q−1 ) = QDn Q−1 . Siden D er en diagonalmatrise har vi at n n d1 0 · · · 0 d1 0 · · · 0 . . . .. . . . .. . . 0 d2 0 dn2 n D =. . =. . . . . .. .. 0 .. .. 0 .. .. 0 ··· dm 0 ··· dnm Vi har dermed vist sats.
5.1.9
Lunsjmodellens stabile fordeling
Vi returnerer til v˚ ar lunsjmodell og fordelingen av p˚ alegg. Skolens ledning er interessert i ˚ a vite hvorvidt fordelingen av p˚ alegg stabiliserer seg med tiden. Etter første dag kan vi lese av hvor mange som valgte p˚ alegg A og hvor 135
mange som valgte p˚ alegg B. Om vi vet hva fordelingen blir i det lange løp s˚ a kan vi rasjonalisere kafeterians innkjøp ved ˚ a kjøpe inn rett mengde av de respektive p˚ alegg. Vi har at Xn = H n X1 , og vi har matrisen Q fra Eksemplet (5.1.7) som diagonaliserer H. Dette gir at H n = QDn Q−1 . Inversen til Q har vi beskrevet over i Eksempel (5.1.7), og innsatt dette gir n 1 0 1 1 1 1 1 n H = (−1) 4 −1 5 4 −1 0 4 1 0 1 1 1 1 1 = (−1)n 4 −1 5 4 −1 0 4n 1 1 1 1 1 = )n+1 −( −1 )n 5 4 −1 −( −1 4 4 1 1 − ( −1 )n+1 1 − ( −1 )n 4 4 . = )n+1 4 + ( −1 )n 5 4 + ( −1 4 4 N˚ ar n vokser blir termene (1/4)n sm˚ a og forsumbare. Dette betyr at 1 a1 + b1 n , for store n. Xn+1 = H X1 ' 5 4a1 + 4b1
(5.4)
For ˚ a ytterligere fortydligjøre, anta at etter første dagen s˚ a hadde halvparten av eleven valgt p˚ alegg A, og den andre halvparten av elevene hadde valgt p˚ alegg B. Da ville fordelingen bli, med a1 = b1 = 21 , at 20 prosent velger p˚ alegg A mens restværende 80 prosent velger p˚ alegg B. Dette betyr at innkjøpspersonene burde kjøpe inn, allerede etter den første uken, 4 ganger mer av p˚ alegg B enn A.
5.1.10
Uavhengighet av initalverdien
I lunsjmodellen v˚ ar kom vi frem til et uttrykk (5.4) som fordelingen nærmet seg mot. Med initalverdien a1 = b1 = 21 kunne vi konkludere at etter en stund ville omtrent 80 prosent av elevene velge p˚ alegg B mens de restværende elevene ville velge p˚ alegg A. Dette var v˚ ar tolkning av at Xn ' ( 15 , 54 )tr . Det er kanskje overraskende at konklusjonen er uavhengig av hva første dags resultatet er. Vi trenger med andre ord ikke engang vite hva elevene velger den første dagen. Vi har at a1 + b1 = 1 da elevene alltid vil velge et av p˚ aleggene. Innsetter vi b1 = 1 − a1 i uttrykket (5.4) s˚ a f˚ ar vi fordelningen Xn ' ( 15 , 54 )tr , som er uavhengig av a1 . 136
Lunsjmodellen har dermed en unik utfallsvektor X slik at HX = X. Dette er dog ikke et generelt faktum. For eksempel kan vi betrakte identitetsmatrisen H = I som en stokastisk matrise. Da er enhver utfallsvektor X slik at HX = X. Definisjon 5.1.11. En matrise H er primitiv om det finnes et heltall n > 0 slik at koeffisientene i H n er strikt positive. Proposisjon 5.1.12 (Perron-Frobenius). La H være en stokastisk matrise for en Markovkjede. Anta at matrisen H er primitiv. Da finnes det en unik utfallsvektor X slik at HX = X. Vi viser ikke denne sats. I lunsjmodellen har vi at den stokastiske matrisen H er primitiv siden H 2 har positive koeffisienter. Om en stokastisk matris H har en unik utfallsvektor X da kaller vi X det stabile utfall. Merk 5.1.13. La H være en stokastisk matrise for en Markovkjede slik at hendelse ved steg n gis som Xn = H n X1 , der X1 er initialhendelsen. Det er ikke alltid at sekvensen {Xn } konvergerer mot en vektor X. Et enkelt eksempel p˚ a dette er ˚ a velge 0 1 H= . 1 0 Vi har at H 2 er identitetsmatrisen. Om X = [x, y]tr er en vektor har vi at HX = [y, x]tr , og dermed at H 2n X = X
og
H 2n+1 X = HX.
Spesielt har vi at sekvensen {Xn } = {X, HX, X, HX, X, HX, ...} ikke konvergerer mot en vektor, s˚ afremt ikke x = y slik at HX = X. La oss returnere til den generelle situasjonen med H en stokastisk matrise H for en Markovkjede. Om det skulle finnes en slik stabil tilstand X da ville vi ha ligningen HX = X, som kan skrives som X − HX = (1 − H) · X = 0. Dette kan vi anvende for ˚ a forsøke ˚ a bestemme den stabile tilstanden direkte. Gitt en stokastisk matrise H. Bestem deretter alle løsninger til ligningen ovenfor, dvs alle vektorer X slik at (1 − H)X = 0, og der koordinatene til X summerer opp til 1. Har man flaks, dvs. er Markovkjeden generisk nok, vil det finnes en unik slik tilstand X. 137
Merk 5.1.14. I eksemplet med lunsjmodellen ovenfor, s˚ a tryllet vi frem diagonaliseringsmatrisen Q. Det finnes et standardresept for ˚ a konstruere slike matriser, og denne er n˚ art beslektet med teorien for egenvektorer (Kapittel 4.4). Men, selv om man i teorien forst˚ ar hvordan man skal finne diagonaliseringsmatrisene Q, er det i praksis ganske vanskelig. N˚ ar matrisestørrelsen blir mer enn (3 × 3)-matriser blir det nærmest umulig ˚ a gjøre dette for h˚ and. Vanskeligheten best˚ ar i ˚ a finne røtter til det karakteristiske polynomet til H, som er et polynom av grad m om H er en (m × m)-matrise. Deretter, etter ˚ a muligens ha konstruert matrisen Q s˚ a m˚ a man konstruere Q−1 , og dette er generelt veldig tidskrevende. I virkelige modeller kan man ikke skride frem som vi har gjort i v˚ art lille eksempel. Istedenfor beregner man iterasjoner av matrisen H, og approksimerer det stabile utfallet med produket H n X der X er en gitt utfallsvektor.
138
5.2 5.2.1
De komplekse tall En spesiell klasse matriser
La C være delmengden av (2 × 2)-matriser p˚ a formen a −b C= | reelle tall a, b . b a Vi ser at identitetsmatrisen 1 och nullmatrisen 0 er med i C. La Z og W være to villk˚ arlige element i C. Da har vi a −b c −d Z= og W = , b a d c for reelle tall a, b, c og d. Vi utfører følgende beregninger a + c −(b + d) Z +W = b+d a+c ac − bd ad + bc Z ·W = −ad − bc ac − bd ac − bd ad + bc W ·Z = . −ad − bc ac − bd
(5.5) (5.6) (5.7)
Av (5.5) har vi at mengden C er lukket under summasjon; matrisen man f˚ ar ved ˚ a summere to villk˚ arlige element i C vil igjen være et element i C. Ved ˚ a skrive ad + bc = −(−ad − bc) ser vi av (5.6) at mengden C ogs˚ a er lukket under matriseprodukt. Og ved ˚ a sammenligne (5.6) med (5.7) s˚ a observerer vi at matrisproduktet er kommutativt n˚ ar vi restrikterer oss til mengden C. En viktig egenskap ved tall er at ethvert tall forskjellig fra null, har en multiplikativ invers. Og dette leder oss til neste observasjon med mengden C. Proposisjon 5.2.2. La Z 6= 0 være et element i C. Da er Z inverterbar, og inversen Z −1 er ogs˚ a med i C. Mer presist, om a −b Z= , b a har vi at det(Z) = a2 + b2 6= 0, og at Z
−1
=
a a2 +b2 −b a2 +b2
139
b a2 +b2 a a2 +b2
.
Bevis. Direkte beregning gir att det(Z) = a2 + b2 som er forskjellig fra null s˚ afremt (a, b) 6= (0, 0). Dermed er Z inverterbar om Z 6= 0, og ved ˚ a bruke −1 formelen for invers til (2×2)-matriser ser vi at Z er p˚ a overnevnte form. Mengden C er med andre ord lukket under sum, og enhver matrise Z har en additiv invers −Z, mengden er lukket under multiplikasjon og enhver matrise Z 6= 0 har en multiplikativ invers Z −1 , og multiplikasjonen er kommutativ. Alle disse egenskapene rettferdiggjør begrepet tall, og mengden C kalles de komplekse tall.
5.2.3
Utvidelse av de reelle tall
De reelle tallene R kan p˚ a en naturlig m˚ ate identifiseres med en delmengde av C. Vi identifiserer det reelle tallet a med matrisen a 0 a·1= . 0 a a 0 Om vi for ethvert reelt tall a lar Ta = . Ved identifiseringen av de 0 a reelle tallene R som en delmengde av C har vi at a = Ta . Vi har at Ta + Tb = Ta+b
og Ta · Tb = Tab .
Dette betyr at addisjonen og multiplikasjonen av de relle tall sammenfaller med matriseaddisjon og matrisemultiplikasjon av elementer i C. Det er med dette vi mener naturlig identifikasjon. Det finnes matriser i C som ikke er p˚ a formen Ta for noe reelt tall a, slik at de reelle tallene R identifiseres med en ekte delmengde av C. Et eksempel p˚ a et element i C som ikke er p˚ a formen Ta , for noe reelt tall a er tallet 0 −1 Ω= . 1 0 En overraskende egenskap ved tallet Ω er at Ω2 = − [ 10 01 ]. Tallet Ω i kvadrat blir minus identitetsmatrisen. Identitetsmatrisen er det samme som T1 under identifikasjonen beskrevet ovenfor, slik at vi har ligningen Ω2 = −1. Eksempel 5.2.4. Betrakt ligningen X 2 = 5, i C. Dette betyr at vi søker matriser p˚ a formen x −y X= (5.8) y x slik at X 2 = 5, der 5 skal tolkes som tallet 5 multiplisert med identitetsmatrisen. Eller om man vil, som tallet 5 betraktet som en delmengde av C 140
under identifikasjonen beskrevet over, dvs T5 . Ved ˚ a anvende formelen (5.6) f˚ ar vi at matriseligningen X 2 = 5 blir 2 x − y 2 −2xy 5 0 = , 2xy x2 − y 2 0 5 som igjen er ekvivalent med de to ligningene x2 − y 2 = 5 og 2xy = 0.
(5.9)
Den siste av disse to gir at enten er x = 0 eller s˚ a er y = 0. Innsetter vi x = 0 2 i den første ligningen i (5.9) f˚ ar vi −y = 5, som ikke har løsning. Innsetter vi derimot y = 0 i den første ligningen (5.9) f˚ ar vi x2 = 5, som har løsningen √ x = ± 5. Med andre ord; betrakter vi ligningen x2 = 5 som en ligning i R eller som en a f˚ ar vi uansett kun tilbake de vanlige løsningene matriseligning X 2 = 5 i C, s˚ √ x = ± 5. Eksempel 5.2.5. Motivert av forrige eksempel, la oss n˚ a betrakte en ligning som ikke har reelle løsninger. For eksempel X 2 = −1. La X være en matrise som i (5.8). Ligningen X 2 = −1 blir da 2 x − y 2 −2xy −1 0 = , 2xy x2 − y 2 0 1 som er ekvivalent med lignignene x2 − y 2 = −1 og 2xy = 0.
(5.10)
Det følger at enten er x = 0, eller y = 0. Innsetter vi y = 0 i den første ligningen i (5.10) f˚ ar vi x2 = −1 som ikke har løsning. Derimot, innsetter vi isteden x = 0 f˚ ar vi −y 2 = −1 som har løsningen y = ±1. Ligningen X 2 = −1 har løsningene 0 −1 0 1 Ω= og − Ω = . 1 0 −1 0 Disse to løsningene ligger ikke i den delmengde av C som de reelle tall utgjør. Vi har, til en gitt ligning, funnet løsninger som ikke er relle tall.
5.2.6
De komplekse tall som det reelle tallplanet
Det reelle tallplanet R2 best˚ ar som kjent av alle ordnede tallpar. Vi kan til ethvert slikt tallpar z = (a, b) tillordne matrisen a −b Z= . (5.11) b a 141
Det er klart at vi med dette identifiserer R2 med C. De reelle tall R betraktet som en delmengde av C blir da identifisert med den horisontale x-aksen. N˚ a som vi har en multiplikasjon p˚ a de komplekse tallene C, f˚ ar vi ved identifi2 2 kasjonen C = R overført en multiplikasjon p˚ a planet R . La oss betegne produktet p˚ a R2 med ∗. Gitt to punkt i planet z = (a, b) og w = (c, d) hva er z ∗ w =? Eneste m˚ aten ˚ a besvare dette p˚ a er ˚ a betrakte z og w som element C, utføre matrisemultiplikasjonen, og deretter g˚ a tilbake til R. La Z og W være matrisene som tilsvarer punktene z og w under identifikasjonen (5.11). Om z = (a, b) og w = (c, d) da er a −b c −d Z= og W = . b a d c Produktet ZW har vi beskrevet over (5.6), og vi f˚ ar at z ∗ w = (ac − bd, −ad − bc).
5.2.7
Geometrisk tolkning av produkt
Vi klarte i forrige seksjon ˚ a utlede et uttryk for produktet z ∗ w av to punkt i planet. Vi vil i denne seksjonen gi en geometrisk tolkning av dette produktet. Hva skjer? Vi begynner med ˚ a beskrive et punkt z = (a, b) i planet i polære koordinater. Vinkler m˚ aler vi moturs i radianer, og vi m˚ aler fra den positive horisontelle akselen. y (a, b)t
b
ϕ a
x
Vi tenker oss et punkt (a, b) som i figuren over. √ Av Pytagoras Sats har vi t at radien r fra origo till punktet (a, b) er r = a2 + b2 . Om vi videre lar ϕ være vinkelen mellom x-aksen og linjesegmentet fra origo til punktet (a, b)t , har vi identiteten z = (a, b) = (r cos ϕ, r sin ϕ). Av denne omskrivningen f˚ ar vi at matrisen a −b cos ϕ − sin ϕ Z= =r· . b a sin ϕ cos ϕ 142
Om vi p˚ a lignende m˚ ate skriver om punktet w = (c, d) = (s cos θ, s sin θ) f˚ ar vi at cos ϕ − sin ϕ cos θ − sin θ Z ·W =r ·s . sin ϕ cos ϕ sin θ cos θ De to konstantene r og s er lette ˚ a behandle og kan settes utenfor selve matriseproduket. Bruker vi n˚ a resultatet i Oppgave (5), side 43, f˚ ar vi att cos ϕ − sin ϕ cos θ − sin θ cos(ϕ + θ) − sin(ϕ + θ) Z·W = rs · = rs . sin ϕ cos ϕ sin θ cos θ sin(ϕ + θ) cos(ϕ + θ) Med andre ord har vi at z ∗ w = (rs cos(ϕ + θ), rs sin(ϕ + θ)). Vi har dermed multiplisert radien r til z med radien s til w, og vi har addert deres respektive vinkler. Det er dermed lett ˚ a forestille seg hva produktet betyr geometrisk. z∗w w = (c, d)t θ+ϕ z = (a, b)t
θ ϕ
Merk 5.2.8. Vi opplever de reelle tallene som naturlige da vi har møtt disse siden barneskolen. Som vi nettopp har sett finnes det en utvidelse av de relle tall til de komplekse tall. Et fundamentalt resultat innenfor algebraen gir at algebraiske uttrykk p˚ a formen p(z) = a0 z n + a1 z n−1 + . . . + an−1 z + an , der a0 , . . . , an er komplekse tall og z er ubestemt, kan skrives som en produkt av lineære faktorer. Dvs, p(z) = a0 (z − α1 )(z − α2 ) · · · (z − αn ), der α1 , . . . , αn er komplekse tall. Fra et slikt algebraisk perspektiv er de komplekse tallene mer naturlig enn de reelle. Herifra er kanskje ikke steget langt til funderinger om hva vi mener med begrepet tall, og hvilke som eventuelt er naturlige. I litteraturen vil begrepet kropp være en aksiomatisering av det 143
som vi i dagligtalen kaller tall. B˚ ade de reelle tallene og de komplekse tallene C er eksempel p˚ a kropper. Som vi har beskrevet ovenfor har de komplekse tallene en egenskap som de reelle tallene ikke har. Nemlig, den at ethvert polynom p(z) kan skrive som en produkt av lineære faktorer. Dette betegnes med at de komplekse tallene er algebraisk lukket.
144
5.3 5.3.1
Pick’s Sats Notasjon
Et polygon er en plan figur hvis rand gis av et endelig antall rette linjesegment. Der linjesegmentene, som utgjør polygonets rand, skjærer hverandre har vi polygonets hjørner. Polygonet minus dets rand danner polygonets indre. Definisjon 5.3.2. Et enkelt polygon P er et polygon kun med heltallshjørner og hvor randkurven er sammenhengende og uten selvskjæringer.
Til et gitt polygon lar vi R(P ) være antallet heltallspunkter p˚ a randen, antallet heltallspunkter i dets indre skriver vi som I(P ), og vi lar A(P ) betegne arealet til polygonet. Vi skal vise at klassen av enkle polygon tilfredstiller Picks identitet; 1 R(P ) + I(P ) − A(P ) = 1. 2 Eksempel 5.3.3. Eksempel p˚ a et enkelt polygon hvor vi lett innser at Picks identitet gjelder er triangelen nedenfor. (4, 2)
(0, 0)
(4, 0)
Koordinatene til triangelen er (4, 0), (4, 2) og (0, 0). Arealet til triangelen er A = 4. Antallet indrepunkter er I = 1, og antallet randpunkter er R = 8. Dette gir at 21 R + I − A = 4 + 1 − 4 = 1. 145
Proposisjon 5.3.4. La P være en rettvinklet triangel med heltallshjørner. Anta att triangelen er slik at kateterne st˚ ar parallelt med koordinataksene. Da gjelder Picks identitet for triangelen P . Bevis. Anta at det finns m heltalls punkter langs det ene katetet, n heltalls punkter langs det andre katetet, og k heltallspunkter langs hypotenusen. Vi har en skjematisk figur.
n
k
m Merk at sidelengdene til katetene er (m − 1) og (n − 1) slik at arealet till triangelen er A = (m−1)(n−1) . Antallet randpunkter er 2 R = m + n + k − 3. Da katetene st˚ ar parallelt med koordinataksene kan vi lett lese av antallet indre punkter. Figuren ovenfor kan vi forestille oss som den ene halven av et rektangel F .
n
k
m Diagonalen i rektangelet F blir da hypotenusen i triangelen P . Antallet indre punkter til rektangelet F er (m − 2)(n − 2). Merk at det finnes k punkter p˚ a diagonalen, og av disse er k − 2 i det indre av rektangelet. Siden diagonalen deler F i to identiske kopier av P følger det att antallet indre punkter i P er 1 1 I = (m − 2)(n − 2) − (k − 2) = (mn − 2m − 2n + 6 − k). 2 2 Anvender vi disse uttrykkene s˚ a f˚ ar vi at R + 2I − 2A blir m + n + k − 3 + (mn − 2m − 2n − k + 6) − (mn − m − n + 1) = 2. 146
Dette viser proposisjonen. Proposisjon 5.3.5. La P være et polygon. La C være et linjesegment mellom to hjørner til P . Anta at hele segmentet C er inneholdt i polygonet, og anta at segmentet C deler opp polygonet i to biter P1 og P2 . Om Picks identitet holder for P1 og P2 da holder ogs˚ a Picks identitet for P .
P2 C P1
Bevis. Anta at linjesegmentet som vi deler opp polygonet P med har c antall heltallspunkter. La oss kalle dette nye linjesegmentet for C. Merk at de to endepunktene til linjesegementet C ligger p˚ a randen til polygonen P . Vi har I(P ) = I(P1 ) + I(P2 ) + c − 2, der antallet c−2 kommer fra segmentet C. Summererer vi opp randpunktene til P1 og P2 vil linjesegmentet C bli regnet to ganger. Det eneste bidraget fra linjesegmentet C til randpunktene av P er de to endepunktene. Dette gir R(P ) = R(P1 ) + R(P2 ) − 2 · c + 2. Trivielt har vi at A(P ) = A(P1 )+A(P2 ). Summerer vi n˚ a opp R(P )+2I(P )− 2A(P ) og innsetter uttrykkene over, f˚ ar vi R(P1 ) + R(P2 ) + 2I(P1 ) + 2I(P2 ) − 2 − 2A(P1 ) − 2A(P2 ). Ved antagelsen gjelder Picks identitet for polygonene P1 og P2 slik at R(P1 )+ 2I(P1 )−2A1 (P ) = 2 = R(P2 )+2I(P2 )−2A(P2 ). Innsetter vi dette i uttrykket over f˚ ar vi R(P ) + 2I(P ) − 2A(P ) = 2 hvilket viser proposisjonen. Korollar 5.3.6. Picks identitet holder for rektangler hvis sider er parallelle med koordinataksene. Bevis. P˚ astanden følger av Proposisjon (5.3.4) og Proposisjon (5.3.5). 147
Vi har vist Picks sats for rettvinklede triangler hvis katet st˚ ar parallelt med koordinataksene. Vi vil straks vise at Picks identitet holder for alle triangler. Vi merker oss at en villk˚ arlig triangel P kan utvides til et rektangel F hvis sider er parallelle med koordinataksene. Til hver side i triangelen P som ikke st˚ ar parallet med koordinataksene legger vi en rettvinklet triangel slik at hypotenusen til den rettvinklede triangelen møter den gitte siden i P . Hjørnene til triangelen P vil da havne p˚ a sidene til rektangelet F , se figuren under.
P
Beroende p˚ a triangelen P s˚ a trenger vi enten en, to eller tre rettvinklede triangler for ˚ a forme rektangelet F . I figuren over har vi betraktet tilfellet hvor ingen av sidene er parallelle med koordinataksene. De to gjenst˚ aende tilfellene kan vi illustrere med følgende figurer
P
Merk ogs˚ a at siden sidene til rektanglet er parallelle med koordinataksene vil hjørnene til rektanglet ha heltallskoordinater. Rektanglet F er med andre ord et enkelt polygon. Proposisjon 5.3.7. Picks identitet holder for triangler. Bevis. La oss begynne med det mest generelle tilfellet hvor ingen av triangelen P sine sider st˚ ar parallelt med koordinataksene. La c1 , c2 , c3 være antallet heltallspunkter p˚ a sidene til P . Merk at vi dermd teller hjørnepunktene to ganger. Vi har 3 X R(P ) = (ci − 2) + 3. (5.12) i=1
148
La T1 , T2 , T3 være de rettvinklede trianglene vi trenger for ˚ a forme rektangelet F . Ved ˚ a betrakte figuren vi har tegnet ovenfor ser vi at I(P ) +
3 X
I(Ti ) +
i=1
3 X
(ci − 2) = I(F ).
(5.13)
i=1
Vi vil om et øyeblikk ogs˚ a trenge følgende uttrykk for randpunktene til rektanglet. Merk at vi ved ˚ a summere randpunktene til trianglene T1 , T2 og T3 teller hjørnene i trianglene dobbelt. Dermed, ved ˚ a deretter subtrahere randpunktene til triangelen P f˚ ar antall randpunkter til rektangelet F . Med andre ord har vi 3 3 X X R(Ti ) − ( (ci − 2) + 3) = R(F ). (5.14) i=1
i=1
Vi vil n˚ a vise at R(P ) + 2I(P ) = 2 + 2A(P ). Vi løser ut I(P ) ved hjelp av (5.13), og bruker dette samt (5.12) for ˚ a uttrykke R(P ) + 2I(P ) som 3 X
(ci − 2) + 3 + 2I(F ) − 2
i=1
=−
3 X
I(Ti ) − 2
i=1
3 X
(ci − 2) + 3 + 2I(F ) − 2
i=1 3 X
=−(
3 X
3 X
(ci − 2)
i=1
I(Ti )
i=1
(ci − 2) + 3) + 6 + 2I(F ) − 2
i=1
3 X
I(Ti ).
(5.15)
i=1
Deretter bruker vi identiteten (5.14) for ˚ a omskrive venstre summand i (5.15). Dette gir at (5.15) blir R(F ) −
3 X
R(Ti ) + 6 + 2I(F ) − 2
i=1
3 X
I(Ti ).
(5.16)
i=1
Deretter bruker vi at Picks identitet gjelder for trianglene T1 , T2 , T3 ved Proposisjon (5.3.4) og for rektangelet F ved Korollar (5.3.6). Dermed kan vi omskrive (5.16) som 2 + 2A(P ) + 6 −
3 X
(2 + 2A(Ti )).
i=1
Da vi har at A(R) = A(P ) + A(T1 ) + A(T2 ) + A(T3 ), følger det at Picks identitet holder for en triangel i generell posisjon. Om triangelen P har to sider parallelle med koordinataksene følger p˚ astanden av Proposisjon (5.3.4). 149
Om triangelen P kun har en side parallell med en av koordinataksene har vi at uttrykkene (5.12) og (5.13) kun endres med at summasjonsindeksen n˚ a skal løpe fra i = 1 til i = 2. Derimot s˚ a ser vi at uttrykket (5.14) ikke lenger holder, og m˚ a byttes ut med 2 X i=1
R(Ti ) −
2 X
ci + c3 = R(F ).
i=1
Bevisgangen for ˚ a vise at R(P ) + 2I(P ) = 2 + 2A(P ) blir ellers identisk med argumentet gitt over, og vi overlater dette til leseren. Setning 5.3.8 (Pick’s Sats). La P være et enkelt polygon, og la R være antall heltallspunkter p˚ a randen, I antallet heltallspunkter i polygonets indre og A polygonets area. Da har vi følgende identitet 1 R + I − A = 1. 2 Bevis. Først viser vi at det finnes hjørner i polygonet P som danner en vinkel som er minder enn 180◦ . La x1 være et hjørnepunkt. Om vinkelen i dette hjørnet er mindre enn 180 grader, er vi klare. Hvis ikke g˚ ar vi langs randen, i en gitt retning, til neste hjørnepunkt x2 . Er vinkelen her mindre enn 180 grader er vi klare, hvis ikke fortsetter vi langs randen til neste hjørnepunkt. Siden randen er sammenhengende og uten selvskjæringer vil vi nødvendgivs finne et hjørne hvor vinkelen er mindre enn 180 grader. Fordi, det motsatte ville bety at vi etter et endelig antall steg langs randen kommer tilbake til punktet x1 , og vi ville ha et hull i polygonet. Dette er umulig siden randen er sammenhengende. Vi vil deretter vise at vi kan finne et linjesegment C mellom to hjørner, der segmentet C er helt inneholdt i polygonet P . La x være et hjørnepunkt hvor polygonet P danner en vinkel som er mindre enn 180◦ . La z1 og z2 være de to andre endepunktene til de linjesegmentene som bestemmer x. Om linjesegmentet l mellom z1 og z2 er inneholdt i polygonet P da er vi ferdige. Hvis ikke lar vi q1 , . . . , qm være hjørnepunktene til P som ligger innenfor triangelen med hjørner z1 , z2 og x. Denne mengden er ikke-tom siden l er antatt ˚ a skjærer randen. Hvert punkt q1 ligger p˚ a en linje li som er parallell med linjen l. La y være et av hjørnepunktene p˚ a linjen l0 som ligger nærmest punktet x. 150
x y
l0 l
z1
z2
Linjesegmentet C mellom x og y vil være helt inneholdt i polygonet P . Dette betyr at hver gang vi har et polygon P med fler enn tre hjørner, da kan vi finne et linjesegment C mellom to hjørner som er helt inneholdt i polygonet P . Av Proposisjon (5.3.5) holder det med ˚ a vise sats for hver av disse to polygon P1 og P2 . Polygonet P1 (og P2 ) har mindre antall hjørner enn P . S˚ afremt dette polygonet ikke er en triangel, kan vi finne linjesegment C1 som er inneholdt i P1 og som gir oss to polygon P11 og P12 . Av Proposisjon (5.3.5) holder det ˚ a vise sats for P11 og P12 . Vi kan dermed fortsette ˚ a dele opp polygonene til vi kun har triangler, og det er nok ˚ a vise Picks identitet for disse triangler. Av Proposisjonen (5.3.7) har vi dermed vist Picks Sats. Merk 5.3.9. Det er lett ˚ a huske at Picks identitet er en lineær relasjon mellom randpunkter, indrepunkter og areal. Derimot, som leseren vil oppdage, er det vanskelig ˚ a huske de konstantene som inng˚ ar i Picks identitet. Det er derimot ganske enkelt ˚ a bestemme disse konstantene. Gitt at vi vet at relasjonen er lineær, dvs vi har Rx + Iy + Az = w, for noen heltallskonstanter x, y, z og w. Ved ˚ a tegne opp tre passende figurer f˚ ar vi et lineært ligningssystem som vi ikke har noe problem med ˚ a løse. For eksempel, la P1 være enhetskvadratet, P2 være triangelen vi f˚ ar ved ˚ a halvere enhetskvadratet, og la P3 være et kvadrat med sider av lengde to.
151
Plasserer vi disse figurene med heltallshjørner finner vi at P1 har areal 1, ingen indre punkter og 4 randpunkter. Dette gir ligningen 4x + z = w. Triangelen P2 har halve arealet til P1 , tre randpunkter, mens P3 har areal 4, og 8 randpunkter og 1 indrepunkt. Disse tre polygonene gir oss ligningssystemet 4x + z = w 1 3x + z = w 2 8x + y + 4z = w. Vi har visstnok bare listet tre ligninger, og har fire ukjente i systemet, men dette er nok. Gauss-Jordan eliminasjon p˚ a systemet over gir z = −w,
5 8 y = − w − z = w, 3 3
1 1 1 x = w − z = w. 3 6 2
En løsning f˚ ar vi med w = 1, som gir 12 R + 1 · I − 1 · A = 1. Andre valg gir relasjoner ekvivalente med Picks identitet. Merk 5.3.10. Det er viktig at polygonet er enkelt, dvs at det ikke har “hull”. Skal man generalisere Picks identitet til mer generelle polygon m˚ a formelen ta hensyn til s˚ akalt Euler karakteristikk. Generalisering til høyere dimensjonelle figurer, dvs polytoper ble oppdaget ganske nylig. Se artikkelen til Howard Iseri “An Exploration of Pick’s Theorem in Space” Math. Mag. 81 (2008), no. 2, pp. 106–115, og dennes referanser for videre lesning.
152
5.4
Google og informasjonssortering
Nettet som vi alle kjenner til er en enorm hop av hjemmesider inneholdende all mulig tenkelig og utenkelig informasjon. Det er en fantastisk følelse ˚ a ha tilgang til all den informasjon som finnes p˚ a nettet. Et umiddelbart problem som dykker opp er hvordan man skal finne relevant informasjon. Vi skal her beskrive hvordan søkmotoren Google finner n˚ alen i høystakken.
5.4.1
Nettet
Internett best˚ ar av hjemmesider. Hver hjemmeside har en unik adresse, og sidene inneholder tekst samt pekere (linker) til andre hjemmesider. En nettleser gjør det mulig ˚ a˚ apne og lese en hjemmeside, og problemet som søkmotorene skal hjelpe oss med er ˚ a sortere ut hjemmesidene som er relevante for en gitt søkning. For ˚ a forst˚ a kompleksiteten i problemet gjeldende informasjonssorteringen er det verdt ˚ a merke seg følgende. Nettet er veldig stort, og faktisk er det vanskelig ˚ a bestemme antallet hjemmesider. Et estimat gjort januar 2004 (se [2]) indikererer at det dengang fantes 10 milliarder hjemmesider som i snitt inneholdt 500 KB informasjon. Vidre har vi at nettet er dynamisk. Ikke bare dukker det opp kontinuerlig nye hjemmesider, men gamle sider endres ved at ny tekst og nye pekere legges til.
5.4.2
Bl˚ akopi
Før man begynner ˚ a sortere informasjonen, s˚ a tar man først en slags bl˚ akopi av nettet. Sm˚ a avanserte program (s˚ akalte webcrawlers) søker opp nettets hjemmesider, leser av informasjonen og følger opp pekerne for ˚ a finne fler hjemmesider. Siden nettet hele tiden endrer seg blir disse programmene aldri avsluttede, men g˚ ar til stadighet gjennom eksisterende hjemmesider. Det tar omtrent (se [1]) tre hele uker for ˚ a søke gjennom nettet! Informasjonen som disse programmene henter blir lagret i en stor indekseringsfil. I indekseringsfilen lagres alle typer av ord som blir funnet p˚ a hjemmesiden, samt informasjon om hvilke hjemmesider som inneholder de respektive ordene. Om vi tenker oss hjemmesidene nummererte som 1, 2, . . ., da kan en del av indekseringsfilen se ut som • matrimonium 8, 24 • matrise 3, 11, 15, 879, 1000032 • matrose 6, 11, 3059. 153
Dette betyr at ordet “matrise” forekommer p˚ a hjemmesidene nummerert som 3, 11, 15, 879 og 1000032, mens hjemmeside 11 inneholdt b˚ ade termen matrise og matrose. Denne indekseringsfilen er selvsagt enorm da alle typer av ord, innefor alle tenkelige spr˚ ak forekommer. ˚ Aret 2003 var denne indekseringsfilen omkring 4 milliarder stor og Google hadde en maskinpark best˚ aende av 15000 datamaskiner for ˚ a lagre indekseringsfilen. Men, poenget er at selv om denne filen er stor s˚ a tar det ikke langt tid for en datamaskin ˚ a søke igjennom en slik liste.
5.4.3
Rangering
N˚ ar vi bruker en søkmotor s˚ a skriver vi inn en tekst eller bare et ord som beskriver v˚ art interesse. Deretter vil søkmotoren liste opp alle hjemmesider som inneholder v˚ ar søkte tekst. Disse hjemmesider blir listet etter en gitt rangering, der hjemmeside med høyest rang kommer først. Grunnen til at de fleste av oss bruker søkmotoren Google er fordi den har en rangering som vi opplever som fornuftig; de mest relevante sidene kommer først. For eksempel, om du gjør et søk p˚ a ordet “matrise” s˚ a for du ikke bare 5 treff som eksemplet v˚ art over indikerer, men hele 175 000 treff. Det tar Google cirka 0.2 sekunder for ˚ a bestemme en ordnet liste av de 175 000 hjemmesider som inneholder ordet matrise, og høyest opp kommer Wikipedia. Hvordan er dette mulig?
5.4.4
Popularitetsrangering
Et menneske kan fort avgjøre hvorvidt en hjemmeside virker relevant eller ikke, men en søkmotor har ingen kvalitativ forst˚ aelse av tekst. I prinisippet kan et program bare telle hvor mange ganger et gitt ord forekommer. I tiden før soekmotoren Google var det vanlig ˚ a rangere hjemmesidene etter hvor mange pekere en side hadde, en s˚ akalt popularitetsrangering. En hjemmeside som hadde mange pekere til seg m˚ atte være viktig siden mange eiere av hjemmesider hadde lagt til en peker dit. En annen rangering som var brukt telte kun hvor mange ganger et gitt ord forekom p˚ a siden. Her tenkte man seg at en viktig side ville anvende det gitte ordet flere ganger. Popularitetsrangeringen gir en bedre rangering enn ˚ a kun telle antallet forekomster av et ord per side, men popularitetsrangeringen er lett ˚ a manipulere. For ˚ a fremheve sin side under denne rangeringen lager man en million nye hjemmesider som inneholder en peker til sin side. Man skal ikke glemme at det finnes mange kommersielle aktører ute p˚ a nettet som er veldig interesserte i ˚ a f˚ a sine sider synlige. En god og fornuftig rangering m˚ a være vanskelig ˚ a manipulere. Blant annet ryktes det om at en av pre-Google tidens store søkemotorer, Alta 154
Vista, ikke ville returnerer sin egen hjemmesiden som den viktigste n˚ ar man søkte p˚ a “Alta Vista”. Et beskrivende eksempel p˚ a at rangeringsordningen ikke fungerte.
5.4.5
PageRank
For ˚ a rangere hjemmesider skapte Sergey Brin og Larry Page en rangering som siden 1998 har dominert markedet for søkmotorer. ˚ A gjøre et nettsøk med en søkmotor heter idag simpelthen ˚ a google. Selv grunnideen som vi skal beskrive er enkel. Hver peker til en hjemmeside P skal vi tenke p˚ a som et rekommendasjonsbrev for P . En hjemmeside med mange rekommendasjonsbrev bør i utgangspunktet være mere viktig en en hjemmeside med f˚ a rekommendasjonsbrev. Men, som vi indikerte over er dette alene ikke nok for ˚ a gi en god rangering. Vi skal ogs˚ a ta hensyn til hvem som sender rekommendasjonsbrevene, dvs. hvilke sider som peker til hjemmesiden P . Eksempel 5.4.6. Vi tenker oss personer som søker jobb. Deres rekommendasjonsbrev vil være avgjørende for rangeringen av de søkende, og i dette eksemplet tenker vi oss at de ikke har noen andre merittlister. Her kan vi tenke oss at en søker X har 1000 rekommendasjonsbrev, mens en annen søker Y har et brev. Om jobben for eksempel handlet om IT og programmering og Y har rekommendasjonsbrev fra Bill Gates, da er det rimelig ˚ a rangere Y før X, til tross for det store antallet rekommendasjonsbrev X har. Et rekommendasjonsbrev fra Bill Gates vil regnes som viktig. Men om det viste seg at en person som regnes som viktig, skriver veldig mange rekommendasjonsbrev da blir dennes brev med en gang mindre viktige.
5.4.7
Matematisk formalisering
La oss gjøre om ideen i Eksempel (5.4.6) til en matematisk modell for rangering av hjemmesider. Vi tenker oss at nettets hjemmesider er nummererte som P1 , P2 , . . . Pn . Vi leser av antallet pekere |Pj | fra hjemmeside Pj , denne informasjonen har vi ogs˚ a lagret p˚ a indekseringsfilen. Viktigheten eller rangen, til hjemmeside Pj skriver vi som r(Pj ) og er enn˚ a et ubestemt tall. Basert p˚ a eksemplet med rekommendasjonsbrev vil vi at rangen til en hjemmeside P skal baseres p˚ a pekere fra andre hjemmesider til hjemmeside P . Pekerne tenker vi p˚ a som rekommendasjonsbrev. Hver hjemmeside Q som peker til hjemmesiden P har selv en viktighet, dvs rang. Rangen til hjemmesiden Q skal vekte pekeren, men vi vil ogs˚ a ta hensyn til hvorvidt hjemmesiden Q har mange pekerer til andre hjemmesider. Dette gir at rangen til en hjemmeside 155
Pi skal tilfredstille ligningen r(Pi ) =
X r(Pj ) j7→i
|Pj |
,
(5.17)
der vi summerer over alle hjemmesider j 7→ i som peker til hjemmesiden Pi . Rangen til Pi bestemmes som summen av rangen av innpekende hjemmesider delt p˚ a deres totale antall pekere.1 Det er verdt ˚ a bemerket at rangen r(P ) til en hjemmeside er enn s˚ a lenge en ubestemte verdi. Vi har kun satt opp ligningssystemet (5.17) som vi ønsker skal bestemme rangeringsvektoren. Det er ingenting som garanterer at ligningssystemet har, ikke trivielle, løsninger.
5.4.8
Hyperlinkmatrisen
Vi vil n˚ a vise hvordan vi løser PageRank ligningen (5.17). Vi P1 , P2 , . . . , Pn være hjemmesidene, og vi lar |Pj | være antallet pekere fra hjemmeside Pj . Vi teller antallet pekere fra Pj til Pi som maksimalt en. Vi konstruerer deretter hyperlinkmatrisen H som er en (n × n)-matrise, og der koeffisient (i, j) er 1 om hjemmeside j peker til hjemmeside i, |Pj | Hi,j = 0 ellers. Merk at definisjonen av hyperlinkmatrisen H bare gir mening hvis alle hjemmesidene P1 , P2 , . . . , Pn har pekere. Vi vil av tekniske grunner ikke her ta med hjemmesider som ikke har pekere. Vi merker oss at hyperlinkmatrisen konstrueres baseres kun p˚ a informasjon som søkmotorene kan lese av. Eksempel 5.4.9. Betrakt følgende mikro-nett best˚ aende av fire hjemmesider 1, 2, 3 och 4. Disse hjemmesidene har pekere som pilene i diagrammet nedenfor indikerer. 2
4
1
3
1
Om du er interessert i ˚ a se en gitt hjemmesides pagerank, ihvertfall tilnærmelsesvis, kan du besøke www.seochat.com/seo-tools/pagerank-lookup/.
156
Hjemmeside 1 har en peker til hjemmeside 3, og hjemmeside 3 har en peker til hjemmeside 4. Hjemmeside 4 har en peker til hjemmeside 1 og hjemmeside 2, mens hjemmeside 2 har en peker til de andre tre. Vi har at |P1 | = 1, |P2 | = 3, |P3 | = 1 og |P4 | = 2. Ligningssystemet som gir rangeringen av de forskjellige hjemmesidene blir dermed r(P2 ) r(P4 ) + 3 2 r(P4 ) r(P2 ) = 2 r(P2 ) r(P3 ) = r(P1 ) + 3 r(P2 ) r(P4 ) = + r(P3 ) 3 r(P1 ) =
Hyperlinkmatrisen til dette eksemplet blir 1 0 3 0 12 0 0 0 1 2 H= 1 1 0 0 . 3 0 13 1 0 Det er ingen tilfeldighet at kolonnene summerer opp til verdien 1. Proposisjon 5.4.10. Hyperlinkmatrisen H er en stokastisk matrise. Bevis. Vi har at alle koeffisientene i H er ikke-negative, og m˚ a kun verifiere at kolonne elementene summerer til 1. Vi har, for fiksert j, at koeffisient Hi,j i hyperlinkmatrisen er null hvis hjemmeside j ikke peker til hjemmeside i. Og, per definisjon vil det finnes nøyaktig |Pj | nullskilte koeffisienter Hi,j = |P1j | , slik at |Pj | n X X 1 = 1. Hi,j = |P | j α=1 i=1
5.4.11
Rangeringsvektoren
La n være antallet hjemmesider, og la X = [x1 , . . . , xn ]t være en vektor i Rn . Vi merker oss PageRank ligningen (5.17) er ingeting annet enn i’te rad i matriseproduket HX. Med andre ord har vi HX = X. 157
Rangeringsvektoren som vi søker skal være en vektor R = (r1 , r2 , . . . , rn ) med positive koeffisienter ri > 0, som satisfierer HR = R. Vi kan anta at koeffisientene summerer opp til 1, slik at R er en utfallsvektor. Koeffesient ri i rangeringsvektoren vil gi rangen til hjemmeside Pi . Den koeffisient som er størst peker ut den hjemmesiden som rangerest høyest, og som anses mest viktig. Vi har enn˚ a ikke funnet en slik rangeringsvektor. Vi vet engang ikke hvorvidt det finnes løsninger, eller om det finnes om de er unike. For ˚ a garantere løsninger til systemet introduserer vi en ubestemt skalær λ, og betrakter HX = λX. En vektor X som tilfredstiller ligningen HX = λX kalles en egenvektor til H, med egenverdi λ. Proposisjon 5.4.12. La X være en vektor slik at HX = λX for et gitt tall λ. Anta at koeffisientene til X = (x1 , . . . , xn ) er slik at summen ikke P summerer opp til null, ni=1 xi 6= 0. Da er egenverdien λ = 1. Bevis. Av Proposisjon (5.1.6) har vi at koordinatenePtil X summerer opp n til samme verdi som koordinatene til HX. La r = i=1 xi , og vi har av ligningen HX = λX at r = λr. Ved antagelsen er r 6= 0, og det følger derav at λ = 1. Proposisjonen ovenfor gir i prinsippet eksistens av rangeringsvektorer. Egenvektorer vil det alltid finnes, og det eneste vi mener med i prinsippet er kravet om at koordinatene summerer opp til et tall forskjellig fra null. Eksempel 5.4.13. La oss g˚ a tilbake til mikronettet diskutert i Eksempel (5.4.9). Vi satte der opp hyperlinkmatrisen, og vi vil her finne rangeringsvektoren. Ligningssystemet HX = X skriver vi som (I4 − H)X = 0, og dette blir 1 − 13 0 − 21 x 0 1 0 − 12 y = 0. −1 − 1 1 0 3 z −1 − 1 1 0 3 w 0 − 31 −1 1 Gauss-Jordan eliminasjon gir trappeformen 1 − 31 0 − 21 0 1 0 − 1 . 2 0 0 1 − 56 158
arlig Løsninger til dette systemet er w = t, z = 65 t, y = 12 tx = 23 t, med t et villk˚ tall. Kravet om at vektoren ogs˚ a skal være en utfallsvektor gir 2 1 5 4+3+5+6 t + t + t + tt = t( ) = 3t = 1, 3 2 6 6 5 1 , 3 ). Dette gir at hjemmeside P4 er den viktigste, gir det unike utfallet ( 29 , 16 , 18 P3 den nest viktigste. Mens hjemmeside P2 er den minst viktige. Om vi kunne avgjøre om matrisen H var primitiv ville vi av Perron-Frobenius Satsen (Sats 5.1.12) ha eksistens av en stabilt utfall. Hyperlinkmatrisen H er enorm, og har i snitt kun 11 nullskilte element per kolonne og det er umulig ˚ a avgjøre hvorvidt hyperlinkmatrisen H er primitiv. Vi har alts˚ a ikke den teoretiske forst˚ aelsen for ˚ a forst˚ a hyperlinkmatrisen fullt ut. Det er ikke klart at hyperlinkmatrisen har et stabilt utfall og man kan spekulere i hvilke konsekvenser dette kan tenkes gi, men faktum er at søkmotoren Google fungerer utmerket.
5.4.14
Iterering
Diagonaliseringstrikset vi gjorde for ˚ a finne det stabile utfallet i eksempel med lunsjmodellen (Seksjon 5.1) er helt umulig ˚ a applisere til hyperlinkmatrisen. ˚ A konstruere en diagonaliseringsmatrise, og dets invers, krever mange beregninger. Størrelsen til hyperlinkmatrisen gjør at kompleksiteten i disse beregningene blir uoverkommelige. Det man gjør, og som gjøres veldig raskt, er ˚ a tilnærme utfallsvektoren X med iterasjoner. La X1 være en vilk˚ arlig n utfallsvektor. Da vil Xn+1 = H X1 være en approksimasjon til X, og det viser seg at omtrent 50 iterasjoner er nok. Dvs, med n = 50 s˚ a f˚ ar vi en rangeringsvektor X51 som er en god nok tilnærmelse for at vi brukere skal oppleve søkmotoren som god, om ikke utmerket. Merk 5.4.15. Det er klart at vi i beskrivelsen av søkmotoren Google gir en grov skisse av hvordan den fungerer. Søkmotoren inneholder blant annet en hel del finere delrutiner hvor blant annet nettsurferens klikkinger registreres og siden brukes for ˚ a bestemme rangeringen. Vidre s˚ a er hyperlinkmatrisen H s˚ a stor at flere praktiske problemer m˚ a overvinnes for i det hele tatt skrive opp denne, for ˚ a ikke nevne hvordan man skal kunne foreta 50 iterasjoner. En annen ting man kan merke seg er at rangeringsvektoren som søkmotoren Google produserer gir en absolutt rangering. Rangeringen bestemmes kun av pekere, og ikke av innehold. Dette har visse uheldige konsekvenser. For eksempel, en høyt rangert side kanskje inneholder mye av interesse om et spesifikt tema, men har null interesse for en som vil lese om matriser. Om denne høyt rangerte siden skulle inneholde ordet “matrise” da ville denne sannsynlig komme først ved søk p˚ a dette ord. 159
Referanser [1] Dan Laksov “Matematikk og informasjonssøkning p˚ a nettet” Normat 51, nr. 3 (2003) pp 119-131. [2] Amy Langville & Carl Meyer “Google’s PageRank and Beyond. The science of search engine rankings.” Princeton University Press 2006. [3] L. Page, S. Brin, R. Motvani, T. Winograd “The PageRank Citation Ranking: Bringing Order to the Web” http://dbpubs.stanford.edu:8090/pub/1999-66
160
Fasit Oppgaver til Seksjon 1.2 [side 15] (1) Svar (1) (−22, 21)t . (2) (−7, −9, 29)t . (3) (−7, 3π − 15, 32)t . √ (4) (3 + 5 2, 3π + 5)t . (2) Svar (1) (1, 10, 24)t . (2) (−8, 12, 15)t . (3) (π − 1, 2π + 2, 6π + 3)t . √ √ √ (4) ( 2 + 2, 2 2 − 4, 6 2 − 6)t . (3) Svar (1) (−3, 7)t . (2) (− 23 , − 34 )t . 3 (3) (π − 1, 3 −
√
2)t .
1 11 t (4) (− 12 , 5).
161
(4) Svar (1) (−1, 0, 7)t . (2) (−7, 23 , − 34 )t . 3 (3) (π + 7, 4, 3 −
√
2)t .
, 9 , − 29 )t . (4) ( 20 3 4 5 (5) Svar (1) a = 2, b = 1. (2) a = 32 , b = − 21 . (3) a = 59 , b = − 94 . (4) a = 3, b = −2. (6) Svar (1) a = −1, b = 4, c = −1. (2) a =
23 ,b 2
= −7, c = −2.
(3) a = − 31 , b = 1, c = − 21 . (4) a = 7, b = 2, c = −5.
Oppgaver til Seksjon 1.3 [side 24] (1) Svar (1) ( 67 −9 6 ). 7−5π √ 30 √ (2) 6+7 2 2 7 . 10 7 (3) ( 41 5 14 29 ). −5 −47 41 (4) 22 −7 30 . 3
−6 12
162
(2) Svar (1)
2 −8 −6 −23 6 −1
(2)
−2 3 1 7 −2 −1
.
(3)
6 −19 −13 −53 14 −1
(4)
.
.
√ √ √ 2π+4 √2 −3π− 2 −π+3√ 2 . 2π π+4 2 −7π+2 2
(3) Svar (1)
−3 7 −4 0
.
(2)
−1 3 −5 0
.
13 3 3 2
(3)
− 92 − 43
(4)
√−3π√ 7 − 2− 3 0
.
.
(4) Svar 0 7 (1) ( −1 2 4 7 ). 3 34 −3 2 (2) −7 . 5 8 4
(3) (4)
√ π+7 4 3− 2 . 5 29 2 −π − 4 3 5
20 3 7 3
9 4 5 4
− 29 5
8 7
.
Oppgaver til Seksjon 1.4 [side 31] (1) Svar (1) ( −11 7 ). (2) ( 30 29 ). √ √2 . (3) 2π+5 5π+ 2 163
(2) Svar (1) ( 22 11 ). (2) ( 25 21 ). (3)
√ − 5+4π . 5
(3) Svar −9 , BA = 17 21 −4 . 5π−3 −2π−1 −9 . (b) AB = 5π−12 36 −10 3π+6 −1 , BA = √ √ √ 5 5 2+3 −2 2+1 . , BA = (c) AB = 53√2+2 −5 2 2−1 3 14 −9 15 −1
(1) (a) AB =
(2) (a) AB = (b) AB = (3) (a) BA = (b) BA =
14 −9 −2 15 −1 1 . √ √ 5π −9 5 √2−2√ 5 . 3π −1 3 2+ 5
17 −9 21 −4 3 1
.
5π−3 −2π−1 √2 √ √ 6 √ 5 2+3 5 −2 2+ 5
.
(4) Svar −3 −4 −5 (1) −5 −6 −7 . −7 −8 −9
22 28 (2) ( −31 −40 ).
(5) Svar (1) ( 10 −2 1 ). 1 1 −3 3 . (2) 0 1 2
(3) Nei, matrisen er ikke inverterbar. 1 0 (4) −52 1 . 5 2
164
Oppgaver til Seksjon 2.1 [side 55] (1) Svar (1) x1 = −4b1 − 2b2 + 3b3 x2 = 4b1 + b2 − 2b3 x3 = −15b1 − 3b2 + 7b3 . (2) 5 4 2 x 1 = − b1 + b2 + b3 9 9 9 5 2 4 x 2 = b1 − b2 + b3 9 9 9 1 1 1 x 3 = b1 + b2 − b3 . 6 6 6 (3) x1 = 5b1 − 2b2 x2 + x3 = −2b1 + b2 0 = 5b1 − 3b2 + b3 . (4) x1 + 2x2 + 3x3 = b1 0 = b1 + b2 0 = 5b1 + b3 . (2) Svar (1) x 1 = b1 − b2 x2 = −5b1 + 6b2 x3 = s. (2) x1 = 7b1 − 2b2 x2 = −b2 − 3b1 − 2t x3 = t. 165
(3) 1 1 x 1 = b1 − b2 − t 2 4 x2 = t 1 1 x3 = + b2 . b1 8 (4) 7 2 b1 + b2 − t 13 13 1 x2 = (3b1 − b2 ) 65 x3 = t. x1 =
(3) Svar (1) x1 = 7b1 − 3b2 x2 = −2b1 + b2 0 = −2b1 + 2b2 + b3 . (2) x1 = 3b1 − b2 1 x2 = (b2 − 2b1 ) 4 0 = b3 + 2b2 − 7b1 . (3) x1 = t x 2 = b2 0 = b1 − 5b2 0 = b3 − 6b2 . (4) x1 = 5b2 − 2b1 1 x2 = (b1 − 2b2 ) 3 0 = b3 + 7b2 − 2b1 . 166
(4) Svar
1 −2 . 3 1
(5) Svar 1 x=− , 3
y=
5 3
1 og z = − . 3
Oppgaver til Seksjon 2.2 [side 69] (1) Svar (1) 5 2 − b − 7u 3 3 2 1 = + b+u 3 3 = 2 − 7u =u = t.
x1 = x2 x3 x4 x5 (2) x1 x2 x3 x4 x5
= 3 − 9b − 5t − 2u =u = 2 − 11b − 7t =t = 3b.
x1 x2 x3 x4 x5
= b − 120 − 5t − 2u =u = −89 − 7t =t = 31.
(3)
(4) Ingen løsning.
167
Oppgaver til Seksjon 3.1 [side 84] (1) Svar −4 4 (1)
−2 3 1 −2 −15 −3 7 − 97
(2)
4 9 1 6
4 9 − 79 1 6
4 18 4 18 − 61
.
! .
(3) Nei, ikke inverterbar (4) Nei, ikke inverterbar. (2) Svar (1) -76 (2) 72 (3) 0 (4) −8 · 27 (5) −16 · 3 · 5
Oppgaver til Seksjon 4.3 [side 117] (1) Svar (1) (8, −2)t . (2) (π + 1, 1 − π)t . √ √ (3) ( 2 − 7, − 2 − 7)t . (2) Svar (1) (5, 9)t . √ √ (2) ( 2 + 2 − π, 7 2 − π)t . (3) (15, −35)t . 168
(4) Svar (1) (a) Bilde R2 . Kjerne (0, 0)t . (b) Bilde s(1, −2)t . Kjerne s(−2, 1)t . (c) Bilde R2 . Kjerne (0, 0)t . (d) Bilde s(1, 1)t . Kjerne s(−1, 1)t . (2) Avbildningene A1 og A3 er injektive og surjektive. De andre to er hverken eller. (3) En avbildning er injektiv hvis og bare hvis kjernen er 0. (5) Svar (1) (a) Bilde R2 . Kjerne s(3, 9, −7)t . (b) Bilde R2 . Kjerne s(0, 7, 2)t + t(2, −1, 0)t . (c) Bilde R2 . Kjerne s(13, −13, 2)t . (d) Bilde R2 . Kjerne s(1, −1, 0)t . (2) Ingen av avbildningene er injektive, og alle er surjektive. (3) En avbildning er injektiv hvis og bare hvis kjernen er 0. (6) Svar (1) (a) Bilde s(1, 2, 3)t + t(3, −1, 0)t . Kjerne (0, 0)t . (b) Bilde s(1, 2, 3)t + t(−2, −4, 0)t . Kjerne (0, 0)t . (c) Bilde s(1, 1, 0)t + t(1, 1, 13)t . Kjerne (0, 0)t . (d) Bilde s(1, 1, 6)t . Kjerne s(1, −1)t . (2) A1 , A2 og A3 er injektive. Ingen av avbildningene er surjektive. (3) En avbildning er injektiv hvis og bare hvis kjernen er 0.
169
Register 1-dimensjonal, 52 n-dimensjonal familie, 63 n-fakultet, 10 addisjonstabell, 99 alfabet, 9 assosiativitet, 14, 15, 31, 90, 95 avbildning, 102 bijektiv, 104 bilde, 103, 104 definisjonsmengde, 104 definisjonsomr˚ ade, 103 domen, 103, 104 dual, 120 funksjon, 102 identitetsavbildningen, 104 injektiv, 104 invers, 108 kjerne, 113, 117 ko-domen, 103 lineær, 40, 112 matrise, 101 m˚ almengde, 103 polynomfunksjon, 111 regel, 102, 108 sammensatt, 105, 106 surjektiv, 103, 104 transitiv, 116 trappetrinnsfunksjon, 110 avstand, 8 begrenset støtte, 109 Cantor, Georg, 9
Cramers regel, 78 determinant, 20, 41, 68 diagonalelement, 82 diagonalisering, 133 diofantisk, 57, 70 distributivitet, 15, 95 elementær operasjon, 64 eliminere variable, 49 familie av løsninger, 52 Gauss eliminasjon, 82 Gauss-Jordan eliminasjon, 47, 55 Gauss-Jordan reduksjon, 64 graf, 10, 25, 108 rettet, 109 gruppe, 90 abelsk, 89 kommutativ, 89 symmetriske gruppen, 78 halv˚ apent intervall, 109 hjørne, 109 homogent, 60 hyperplan, 98 indeks, 27 innbyrdes primiske, 57 integral, 110 invariantteori, 20 invers, 14, 90 inversjon, 78 invertibel, 68 170
kant, 25, 109 kommutativitet, 14, 31, 90, 139 konvergens, 100 koordinat ledende, 55, 61, 82 polære, 141 Kronecker delta, 8 Kronecker, Leopold, 9 kropp, 35, 143 algebraisk lukket, 143 skjevkropp, 36 krympe, 39 kvadrering, 102 kvaternioner, 35
stokastisk, 133 søyle, 21 transponert, 33 trappetrinnsform, 82 utvidete koeffisientmatrisen, 61 mengde, 87 element, 87 objekt, 87 undermengde, 88 mengdelære, 87 metrikk, 8 multiplikasjonstabell, 36 multiplisere en ligning med et tall, 47 Nils Henrik Abel, 90 nøytral, 14 nøytralt element, 90
ledende koordinat, 61 løkke, 109 løsninger, 90
orientering, 96
Markovkjede, 133 matematisk modell, 3 matrise, 20 m × n-matrise, 21 øvre diagonal, 82 øvre triangulær, 36 blokk, 37 elementær n-matrise, 33 elementær matrise, 66, 67 elementær operasjon, 33 hyperlink, 155 identitetsmatrise, 73 ikke singulær, 74 invers, 74 invertibel, 73, 74 koeffisientmatrise, 61 koordinat, 21 nilpotent, 36 primitiv, 136 rang, 61 redusert trappetrinnsform, 55, 61 rekke, 21
PageRank, 154 parallellogram, 40 parameter, 4, 52, 63 paritetsproblemet, 96 permutasjon, 7, 34, 78 Picks identitet, 144 polygon, 144 enkelt, 144 produkt, 12 punktvis, 109 skalar, 12 skjevsymmetrisk, 36 stabilt utfall, 136 sti, 10 strekke, 39 sum, 27 Sylvester, James Joseph, 20 symmetrisk, 36 system av m lineære ligninger, 60 tall, 87
171
hele tall, 87 komplekse tall, 34, 139 naturlige tall, 87 rasjonale tall, 87 reelle tall, 87 tegn, 78 transposisjon, 78 vektor, 1, 2, 95 n-tuppel, 7 initalvektor, 131 koordinat, 2 orthonormal, 96 transponert, 2 utfallsvektor, 133 vektorrom, 92, 94 Euklidisk, 88 underrom, 95
172