Dodatna poglavja iz linearne algebre za 1. letnik finančne matematike na FMF Primož Moravec 13. september 2017 1 CIP - Kataložni zapis o publikaciji Narodna in univerzitetna knjižnica, Ljubljana 512.64(075.8) Primož Moravec Dodatna poglavja iz linearne algebre za 1. letnik finančne matematike na FMF [Elektronski vir] / Primož Moravec ; [slike avtor]. - El. knjiga. - Ljubljana : samozal., 2017 Način dostopa (URL): https://www.fmf.uni-lj.si/~moravec/Papers/finmat_alg1.pdf ISBN 978-961-288-021-7 291672320 Kazalo 1 Moore–Penroseov inverz matrike 4 1.1 Psevdoinverz matrike . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.2 Sistemi linearnih enačb . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.3 Metoda najmanjših kvadratov . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2 Jordanova kanonična forma 14 2.1 Izrek o spektralnem razcepu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.2 Jordanova kanonična forma matrike . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.3 Funkcije matrik . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 3 Nenegativne matrike 27 3.1 Ireducibilne matrike . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 3.2 Collatz–Wielandtova funkcija . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 3.3 Največja lastna vrednost nenegativne matrike . . . . . . . . . . . . . . . . . . . . 36 4 Linearen model proizvodnje 39 4.1 Model Leontijeva . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 4.1.1 Zaprti model Leontijeva . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 4.1.5 Odprti model Leontijeva . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 4.2 Obstoj nenegativne rešitve odprtega modela Leontijeva . . . . . . . . . . . . . . . 42 4.3 Obstoj pozitivne rešitve odprtega modela Leontijeva . . . . . . . . . . . . . . . . 44 5 Pozitivni funkcionali 46 5.1 Osnove o linearnih funkcionalih . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 5.2 Konveksne množice in stožci . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 5.3 Pozitivni funkcionali . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 5.4 Separacijski izreki . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 5.5 Farkasova lema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 5.6 Razširitve pozitivnih linearnih funkcionalov . . . . . . . . . . . . . . . . . . . . . 59 2 Uvod Okvirna vsebina: • Moore–Penroseov inverz matrike • Jordanova kanonična forma • Perron–Frobeniusov izrek • Model Leontijeva • Pozitivni funkcionali Predznanje, ki je potrebno za razumevanje snovi, ki je tu obdelana, je pokrito v skripti Tomaža Koširja Linearna algebra za študente Praktične matematike, ki je na voljo na povezavi http://www.fmf.uni-lj.si/˜kosir/poucevanje/0910/alg1-fm.html. Tudi oznake, ki jih uporabljamo, tesno sledijo tistim, ki so uporabljeni v Koširjevi skripti. 3 Poglavje 1 Moore–Penroseov inverz matrike Oglejmo si sistem linearnih enačb Ax = b. Če je matrika A kvadratna in obrnljiva, ima ta sistem enolično rešitev x = A−1 b. Če je sistem rešljiv in je rang matrike A strogo manjši od števila neznank, lahko rešitve, ki jih je neskončno mnogo, dobimo z Gaussovo eliminacijo. V praktičnih problemih pa se pogosto pojavi potreba po tem, da najdemo rešitve sistema eksplicitno s formulo, ki je odvisna od A in b. Po drugi strani, tudi če sistem nima rešitve, bi včasih radi našli „približno” rešitev tega sistema. Kako to dvoje storiti? V tem poglavju si bomo ogledali konstrukcijo Moore–Penroseovega inverza matrike, ki od- govori na zgornje vprašanje. 1.1 Psevdoinverz matrike Definicija. Naj bo A m × n matrika z realnimi elementi. Matriki A+ pravimo psevdoinverz oziroma Moore–Penroseov inverz matrike A, če veljajo naslednje zahteve: 1. AA+ A = A, 2. A+ AA+ = A+, 3. ( AA+)T = AA+, 4. ( A+ A)T = A+ A. Ker morata matriki AA+ in A+ A obstajati, mora biti matrika A+, če obstaja, velikosti n × m. Pripomnimo, da bi lahko pojem psevdoinverza definirali tudi za kompleksne matrike, pri čemer bi v pogojih (3) in (4) transponiranje zamenjali s hermitiranjem; v splošnem bi lahko oba pogoja formulirali kot zahtevo, da sta matriki AA+ in A+ A sebi adjungirani. Od tu dalje se bomo zaradi enostavnosti omejili le na realne matrike. Trditev 1.1.1. Naj bo A matrika. Če za A obstaja psevdoinverz, je enolično določen. Dokaz. Naj bosta B in C psevdoinverza matrike A. Potem je AB = ( ACA) B = ( AC)( AB) = ( AC)T( AB)T = C T A T B T A T = C T( ABA)T = C T A T = ( AC)T = AC. Podobno je BA = CA. Od tod dobimo B = ( BA) B = C( AB) = CAC = C, s čimer je trditev dokazana. 4 5 Kasneje bomo dokazali, da ima vsaka matrika psevdoinverz in izpeljali splošno formulo za računanje le-tega. Tu si oglejmo nekaj posebnih primerov. Primer 1.1.2 . Naj bo A obrnljiva kvadratna matrika. Potem matrika A−1 zadošča lastnostim (1)–(4) iz definicije psevdoinverza, zato je A+ = A−1. Psevdoinverz je torej posplošitev pojma inverza obrnljive kvadratne matrike. Primer 1.1.3 . Naj bo  a  1 a  2  A =  .   .   .  an neničeln stolpec. Potem je 1 A+ = a 1 a 2 . . . an . a 2 + a 2 + · · · + a 2 1 2 n Hitro namreč preverimo, da za to matriko veljajo lastnosti (1)–(4) iz definicije psevdoinverza. Primer 1.1.4 . Naj bo B 0 A = , 0 0 kjer je B obrnljiva kvadratna matrika. Potem je B−1 0 A+ = , 0 0 kar je zopet enostavno preveriti po definiciji. Lema 1.1.5. Za poljubni matriki A in B, za kateri obstaja AB, velja rang( AB) ≤ rang A in rang( AB) ≤ rang B. Dokaz. Stolpci matrike AB so Ab 1 , Ab 2 , . . . , Abn, kjer so b 1 , b 2 , . . . , bn stolpci matrike B. Zato je rang( AB) ≤ rang A. Po drugi strani je rang( AB) = rang( AB)T = rang( B T A T) ≤ rang B T = rang B. S tem je lema dokazana. Trditev 1.1.6. Naj bo A realna matrika, za katero obstaja psevdoinverz. Potem velja: (a) A+ ima tudi psevdoinverz; velja ( A+)+ = A. (b) A T ima tudi psevdoinverz; velja ( A T)+ = ( A+)T . (c) rang A+ = rang A. (d) A T AA+ = A T . Dokaz. Dokaz točk (a) in (b) je rutinsko preverjanje zahtev (1)–(4) iz definicije psevdoinverza, ki ga prepuščamo bralcu. Za dokaz točke (c) uporabimo Lemo 1.1.5 in od tod dobimo rang A = rang( A( A+ A)) ≤ rang( A+ A) ≤ rang A+ in rang A+ = rang( A+( AA+)) ≤ rang( AA+) ≤ rang A, od koder sledi (c). Preostane še dokaz točke (d). Z uporabo (b) dobimo A T = A T( A T)+ A T = A T( A+)T A T = A T( AA+)T = A T AA+ , saj je matrika AA+ po definiciji simetrična. 6 Sedaj bomo pokazali, da ima vsaka realna matrika psevdoinverz. Najprej obdelajmo poseben primer, ko je rang matrike enak številu stolpcev: Izrek 1.1.7. Naj bo A m × n matrika, za katero velja rang A = n. Potem psevdoinverz A+ obstaja in je dan s formulo A+ = ( A T A)−1 A T . Dokaz. Najprej dokažimo, da je matrika A T A, ki je velikosti n × n, obrnljiva. Predpostavimo nasprotno, torej, da je rang( A T A) < n. Potem ima homogen sistem linearnih enačb A T Ax = 0 netrivialno rešitev x ∈ n R . Oglejmo si 0 = x T A T Ax = ( Ax)T Ax = [h Ax, Ax i] , kjer je h , i standardni skalarni produkt v m R . Zaradi pozitivne definitnosti skalarnega produkta sledi Ax = 0, kar pa je nemogoče, ker je rang A = n. Zato A T A ima inverz. Formula za A+ sedaj sledi neposredno iz Trditve 1.1.6 (d). Opomba 1.1.8 . Podoben rezultat lahko pokažemo tudi v primeru, ko je A m × n matrika, za katero je rang A = m. V tem primeru je namreč rang matrike A T tudi enak m, kar je ravno število stolpcev matrike A T. Po izreku 1.1.7 dobimo ( A T)+ = ( AA T)−1 A, iz Trditve 1.1.6 (b) pa sledi A+ = (( AT )+)T = A T( AA T)−1 . Primer 1.1.9 . Naj bo  1 0 A = 1 2 .   −1 3 Ker je rang A = 2, lahko A+ izračunamo s pomočjo formule iz Izreka 1.1.7: A+ = ( A T A)−1 A T   −1 1 0 1 1 −1 1 1 −1 = 1 2  0 2 3   0 2 3 −1 3 3 −1−1 1 1 −1 = −1 13 0 2 3 1 13 1 1 1 −1 = 38 1 3 0 2 3 1 13 15 −10 = . 38 1 7 8 V splošnem primeru lahko problem obstoja psevdoinverza prevedemo na situacijo Izreka 1.1.7 na naslednji način: Trditev 1.1.10. Naj bo A m × n matrika ranga r. Potem obstajata m × r matrika F in r × n matrika G, za kateri velja rang F = rang G = r in A = F G. 7 Dokaz. Vzemimo r linearno neodvisnih stolpcev matrike A in z njimi tvorimo matriko F , ki je velikosti m × r in ima rang enak r. Naj bo Ak k-ti stolpec matrike A. Potem je Ak linearna kombinacija stolpcev matrike F , kar lahko na kratko zapišemo kot Ak = F Gk, kjer so Gk stolpci dolžine r. Če postavimo G = G 1 G 2 . . . Gn , je to matrika velikosti r × n, za katero po konstrukciji velja A = F G. Ker ima matrika G r vrstic, je rang G ≤ r. Po drugi strani pa je r = rang A = rang( F G) ≤ rang G, zato je rang G = r. Primer 1.1.11 . Oglejmo si matriko 1 2 3 A = 4 5 6 .   7 8 9 Rang matrike A je enak 2. Ker sta prva dva stolpca linearno neodvisna, lahko postavimo 1 2 F = 4 5 .   7 8 Sedaj stolpce matrike A izrazimo kot linearne kombinacije stolpcev iz F : 1 1 2 1 2 1 1 4 4 5 , 4 5 4 ,   = 1 ·   + 0 ·   oziroma   = 0   7 7 8 7 8 7 2 1 2 1 2 2 0 5 4 5 , 4 5 5 ,   = 0 ·   + 1 ·   oziroma   = 1   8 7 8 7 8 8 3 1 2 1 2 3 −1 6 4 5 , 4 5 6 .   = −1 ·   + 2 ·   oziroma   = 2   9 7 8 7 8 9 Zato je 1 0 −1 G = . 0 1 2 Izrek 1.1.12. Naj bo A realna matrika, A = F G, kjer sta F in G matriki iz Trditve 1.1.10. Potem psevdoinverz matrike A obstaja in je dan s formulo A+ = G T( GG T)−1( F T F )−1 F T . Dokaz. Iz dokaza Izreka 1.1.7 sledi, da sta matriki GG T in F T F obrnljivi (glej tudi Opombo 1.1.8). Sedaj moramo le še preveriti, da za matriko A+, ki je definirana v Izreku 1.1.12, veljajo zahteve (1)–(4) iz definicije psevdo inverza. Z direktnim računom dobimo AA+ A = F ( GG T( GG T)−1)(( F T F )−1 F T F ) G = F G = A, A+ AA+ = G T( GG T)−1(( F T F )−1 F T F )( GG T( GG T)−1)( F T F )−1 F T = A+ , poleg tega pa sta AA+ = F GG T( GG T)−1( F T F )−1 F T = F ( F T F )−1 F T in A+ A = G T( GG T)−1( F T F )−1 F T F G = G T( GG T)−1 G očitno simetrični matriki. S tem je dokaz končan. 8 Primer 1.1.13 . Poiščimo psevdoinverz matrike 1 2 3 A = 4 5 6   7 8 9 iz Zgleda 1.1.11. Matriko A lahko kot v Trditvi 1.1.10 zapišemo kot A = F G, kjer 1 2 1 0 −1 F = 4 5   in G = . 0 1 2 7 8 Najprej izračunajmo 66 78 2 −2 F T F = in GG T = . 78 93 −2 5 Po Izreku 1.1.12 je A+ = G T( GG T)−1( F T F )−1 F T  1 0 1 5 2 1 93 −78 1 4 7 = 0 1 · ·   6 2 2 54 −78 66 2 5 8 −1 2 −23 −6 11  1 = −2 0 2   . 36 19 6 −7 Omenimo, da obstaja še veliko drugih načinov računanja psevdoinverzov matrik. 1.2 Sistemi linearnih enačb Oglejmo si eno od uporab psevdoinverza matrike. Naj bo dan sistem linearnih enačb Ax = b, kjer je A m × n matrika. Znano je, da rešitev tega sistema obstaja natanko tedaj, ko je rang matrike A enak rangu razširjene matrike A b. Naslednji rezultat karakterizira obstoj rešitev s pomočjo psevdoinverza matrike A: Trditev 1.2.1. Rešitev sistema Ax = b obstaja natanko tedaj, ko je AA+ b = b. Dokaz. Če velja AA+ b = b, je ena od rešitev sistema očitno x = A+ b. Obratno, recimo, da obstaja x, da je Ax = b. Ker je A = AA+ A, dobimo b = AA+ Ax = AA+ b, s tem pa je dokaz končan. Izrek 1.2.2. Naj bo A ∈ m× n R in recimo, da je sistem linearnih enačb Ax = b rešljiv. Potem lahko vse rešitve sistema dobimo s formulo x = A+ b + ( I − A+ A) y, kjer je y ∈ n R poljuben vektor. 9 Dokaz. Iz teorije Gaussove eliminacije že vemo, da če je x 0 neka rešitev sistema Ax = b, potem je množica vseh rešitev sistema enaka x 0 + ker A = { x 0 + z | z ∈ ker A} . Po Trditvi 1.2.1 je A+ b rešitev sistema Ax = b, zato je dovolj preveriti, da je jedro matrike A enako K = {( I − A+ A) y | y ∈ n R }. Vzemimo z ∈ K. Potem je Az = A( I − A+ A) y = Ay − AA+ Ay = 0 , torej je K ⊆ ker A. Obratno, če je z ∈ ker A, potem je Az = 0. Potem je z = ( I − A+ A) z, torej je z ∈ K. S tem je izrek dokazan. Posledica 1.2.3. Naj bo sistem enačb Ax = b rešljiv. Potem je rešitev ena sama natanko tedaj, ko velja A+ A = I. V tem primeru rešitev izračunamo po formuli x = A+ b. Primer 1.2.4 . Dan je sistem enačb x 1 + 2 x 2 + 3 x 3 = 1 4 x 1 + 5 x 2 + 6 x 3 = 2 7 x 1 + 8 x 2 + 9 x 3 = 3 Matrika sistema je 1 2 3 A = 4 5 6 .   7 8 9 V Primeru 1.1.13 smo že izračunali psevdoinverz te matrike: −23 −6 11  1 A+ = −2 0 2 .   36 19 6 −7 Direkten račun pokaže, da velja AA+ b = b, zato sistem ima rešitev po Trditvi 1.2.1. Po Izreku 1.2.2 so vse rešitve sistema oblike x = A+ b + ( I − A+ A) y, kjer je y poljuben vektor v 3 R :  x              1 −23 −6 11 1 1 0 0 −23 −6 11 1 2 3 y 1 1 1 x −2 0 2 2 0 1 0 − −2 0 2 4 5 6 y  2 =     +        2 36 36 x 3 19 6 −7 3 0 0 1 19 6 −7 7 8 9 y 3 −1  1 −2 1   y  1 1 1 = 2 −2 4 −2 y   +    2 . 18 6 5 1 −2 1 y 3 Na prvi pogled izgleda, da bomo dobili triparametrično družino rešitev. V resnici je družina rešitev enoparametrična; če označimo y 1 − 2 y 2 + y 3 t = , 6 dobimo 1 x 1 = − + t, 18 1 x 2 = − 2 t, 9 5 x 3 = + t. 18 Pri tem je t poljubno realno število. 10 1.3 Metoda najmanjših kvadratov Naj bo dan sistem linearnih enačb Ax = b, kjer je A m × n realna matrika in b ∈ m m R . Pri tem predpostavimo, da je prostor R opremljen s standardnim skalarnim produktom. Recimo sedaj, da je sistem protisloven, torej, da nima rešitev. Iz Trditve 1.2.1 vemo, da ta situacija nastopi natanko tedaj, ko AA+ b 6= b. V tem primeru poskušamo najti takšne vektorje x ∈ n R , ki so v nekem smislu „skoraj rešitve” sistema. Načinov za to, kako merimo, ali je nek vektor „skoraj rešitev”, je več. Ogledali si bomo enega od najbolj standardnih. Definicija. Pravimo, da je vektor y ∈ n R rešitev sistema Ax = b po principu najmanjših kvadratov, če za vsak z ∈ n R velja k Ay − b k ≤ k Az − b k . Če torej gledamo funkcijo F : n R → R, definirano s predpisom F ( z) = k Az − b k, iščemo globalni minimum te funkcije na n R . Na problem lahko pogledamo še drugače. Najprej se spomnimo definicije pravokotne projekcije vektorja na podprostor (v našem posebnem primeru): Definicija. Naj bo U podprostor v m m R in v ∈ R \ U . Potem je vektor u ∈ U pravokotna projekcija vektorja v na U , če je vektor u − v pravokoten na vse vektorje iz U . Znano je, da če je { e 1 , e 2 , . . . , ek} ortonormirana baza podprostora U , potem lahko pravokotno projekcijo vektorja v na U izračunamo po formuli u = proj v = h v, e U 1i e 1 + h v, e 2i e 2 + · · · + h v, ek i ek . Za pravokotno projekcijo velja naslednja lastnost: Trditev 1.3.1. Naj bo U podprostor v m m R in v ∈ R \ U . Potem za vsak vektor u ∈ U , različen od proj v, velja U k v − u k > k v − proj v k . U Dokaz. Po definiciji je v −proj v pravokoten na neničeln vektor proj v − u ∈ U . Po Pitagorovem U U izreku je k v − u k2 = k v − proj v + proj v − u k2 = k v − proj v k2 + kproj v − u k2 > k v − proj v k2 , U U U U U to pa dokaže trditev. Trditev 1.3.1 sedaj ponuja način, kako poiščemo rešitev sistema Ax = b po principu najmanjših kvadratov. Ker sistem po predpostavki ni rešljiv, je b / ∈ im A. Označimo w = proj b. im A Po Trditvi 1.3.1 za vsak z ∈ n R velja k b − Az k ≥ k b − w k . Ker je w ∈ im A, ga lahko zapišemo kot w = Ay za nek y ∈ n R . Potem je k b − Az k ≥ k b − Ay k; ker to velja za vsak z ∈ n R , je y rešitev sistema Ax = b po principu najmanjših kvadratov. Lahko se vprašamo, koliko je rešitev danega sistema linearnih enačb po principu najmanjših kvadratov. Oglejmo si najprej primer, ko so stolpci matrike A linearno neodvisni. V tem primeru je rang A = n in dim ker A = n − rang A = 0 , 11 kar pomeni, da je A, gledana kot linearna preslikava n m R → R , injektivna. To pomeni, da je vektor y, konstruiran v zgornjem odstavku, enolično določen. V tem primeru je rešitev sistema po principu najmanjših kvadratov ena sama. V splošnem je lahko takšnih rešitev več, dobimo pa jih tako, da poiščemo vse vektorje y ∈ n R , za katere velja Ay = proj b. im A Ogledali si bomo, kako si lahko s pomočjo psevdoinverza matrike A pomagamo pri iskanju vseh rešitev po principu najmanjših kvadratov. Rezultat je presenetljivo enak kot v Izreku 1.2.2: Izrek 1.3.2. Naj bo dan sistem linearnih enačb Ax = b, kjer je A m × n realna matrika in b ∈ m R . Množica vseh rešitev sistema po principu najmanjših kvadratov je enaka { A+ b + ( I − A+ A) y | y ∈ n R } . Dokaz. Brez škode lahko predpostavimo, da sistem ni rešljiv. Kot zgoraj definirajmo w = proj b. im A Recimo, da sta y n 0 in y 1 takšna vektorja iz R , za katera velja w = Ay 0 = Ay 1 . Potem je y 0 − y 1 ∈ ker A. Povsem enak sklep kot v dokazu Izreka 1.2.2 pokaže, da je ker A = {( I − A+ A) y | y ∈ n R } . Zato je dovolj pokazati, da za vektor v = A+ b velja Av = w. Vzemimo poljuben z ∈ n R . Potem iz Trditve 1.1.6 dobimo h Av − b, Az i = h A T( Av − b) , z i = h( A T AA+ − A T) b, z i = h0 , z i = 0 , torej je vektor Av − b pravokoten na vse vektorje iz im A. Po definiciji pravokotne projekcije je Av = w. V posebnem primeru, ko je rang A = n, smo že videli, da je rešitev sistema po principu najmanjših kvadratov ena sama. Po izreku 1.3.2 je dana z y = A+ b. Če uporabimo še Izrek 1.1.7, dobimo: Posledica 1.3.3. Naj bo dan sistem linearnih enačb Ax = b, kjer je A m × n realna matrika in b ∈ m R . Če je rang A = n, je rešitev sistema po principu najmanjših kvadratov y = ( A T A)−1 A T b. Primer 1.3.4 . Recimo, da imamo podatke meritev količine y v odvisnosti od spremenljivke x: x y 1 0,4 2 0,3 3 0,9 4 1,1 5 3,7 12 Slika 1.1: Odmiki točk od grafa. 3 . 2 . 1 . −1 . 1 . 2 . 3 . 0 −1 . Podatke bi radi aproksimirali s kvadratno funkcijo y = a 0 + a 1 x + a 2 x 2 tako, da bo vsota kvadratov odmikov posameznih točk od ustreznih točk na paraboli pri isti abscisi čim manjša (gl. Sliko 1.1). Problem lahko prevedemo na zgornjega tako, da pogledamo sistem enačb za neznanke a 0, a 1 in a 2, ki ga dobimo, če koordinate točk vstavimo v kvadratno funkcijo. Zapišemo ga lahko v matrični obliki: 1 1 12 0 , 4   1 2 22 a 0 0 , 3     1 3 32 a 0 , 9 .  1 =   1 4 42 a 1 , 1   2   1 5 52 3 , 7 Seveda sistem nima rešitve (to je jasno iz tega, ker se parabola ne bo točno prilegala vsem točkam), iščemo pa rešitev sistema po principu najmanjših kvadratov. Označimo z A matriko sistema in z b vektor na desni strani. Ker je rang A = 3, lahko uporabimo Posledico 1.3.3 in dobimo:  a  0 a  1 = ( A T A)−1 A T b a 2 0 , 4  −1 5 15 55  1 1 1 1 1  0 , 3 = 15 55 225 1 2 3 4 5 0 , 9       55 225 779 1 4 9 16 25 1 , 1   3 , 7  322 −231 35   6 , 4  1 = −231 187 −30 26 , 6     70 35 −30 5 119 , 8  1 , 56  = −1 , 40   0 , 36 Iskana kvadratna funkcija je torej y = 1 , 56 − 1 , 40 x + 0 , 36 x 2 . Graf in točke meritev so prikazani na Sliki 1.2. 13 Slika 1.2: Parabola, ki se najbolje prilega danim točkam. 5 . 4 . 3 . 2 . 1 . −1 . 1 . 2 . 3 . 4 . 5 . 0 −1 . Na podoben način lahko izmerjene podatke aproksimiramo s poljubno linearno kombinacijo danih funkcij. Če imajo točke, dobljene iz meritev, koordinate ( x 1 , y 1) , ( x 2 , y 2) , . . . , ( xm, ym) in podatke aproksimiramo po principu najmanjših kvadratov s funkcijo f ( x) = α 1 f 1( x) + α 2 f 2( x) + · · · + αnfn( x) , kjer so f 1 , f 2 , . . . , fn dane realne funkcije, α 1 , α 2 , . . . , αn pa neznane realne konstante, v resnici rešujemo sistem  f      1( x 1) f 2( x 1) . . . fn( x 1) α 1 y 1 f α y  2( x 1) f 2( x 2) . . . fn( x 2)   2  2   . . .   .  =  .   . . .   .   .   . . . . . .   .   .  f 1( xm) f 2( xm) . . . fn( xm) αn ym po principu najmanjših kvadratov. Če je rang matrike sistema enak n, rešitev dobimo iz Posledice 1.3.3. Več o tem bo bralec spoznal pri numerično naravnanih predmetih. Poglavje 2 Jordanova kanonična forma Kvadratna kompleksna matrika A se da diagonalizirati, če obstajata obrnljiva matrika P in diagonalna matrika D, da je A = P DP −1; pravimo tudi, da je A podobna diagonalni matriki D. Znano je, da diagonalo matrike D sestavljajo lastne vrednosti matrike A, stolpci matrike P pa so ustrezni linearno neodvisni lastni vektorji. Matrika A se da torej diagonalizirati natanko tedaj, ko obstaja baza prostora, sestavljena iz lastnih vektorjev. Jasno je, da obstajajo matrike, ki se ne dajo diagonalizirati; enostaven primer je matrika 0 1 , 0 0 ki ima dvojno lastno vrednost 0, lastni podprostor pa je 1 Lin . 0 Tolažilni rezultat je Schurov izrek, ki pravi, da je vsaka kvadratna kompleksna matrika podobna neki zgornjetrikotni matriki. Kljub temu pa je z neprevidno izbiro baze dobljena zgornjetrikotna matrika še vedno polna neničelnih elementov. Cilj tega poglavja je pokazati, da lahko bazo prostora vedno izberemo tako, da je matrika A podobna bločno diagonalni matriki, katere bloki so zgornjetrikotne matrike, ki imajo „skoraj povsod” same ničle. Prednost tega je, da lahko s pomočjo takšnega zapisa učinkovito računamo potence matrike A, poleg tega pa lahko računamo funkcije matrik f ( A) za primerno izbrane funkcije f . Opomba 2.0.1 . Pred nadaljevanjem vpeljimo še par oznak. Če je A : n n C → C linearna presli- kava, ji lahko glede na bazi B n 1 in B2 prostora C priredimo matriko, ki jo označimo z A B . 2 B1 Če sta C n 1 in C2 neki drugi bazi prostora C , potem lahko A C izrazimo s pomočjo A preko 2 C1 B2B1 prehodnih matrik: A C = P A P . 2 C1 C2B2 B2B1 B1C1 2.1 Izrek o spektralnem razcepu Naj bo A kvadratna kompleksna matrika. Spomnimo se, da je minimalni polinom matrike A polinom mA( λ) z vodilnim koeficientom 1, za katerega velja mA( A) = 0, za vsak drug polinom q( λ), za katerega je q( A) = 0, pa velja, da je deljiv z mA( λ). Iz Cayley–Hamiltonovega izreka sledi, da minimalni polinom mA( λ) deli karakteristični polinom pA( λ) = det( A− λI). Poleg tega je znano, da ima minimalni polinom matrike A iste ničle kot karakteristični polinom, morda z drugimi večkratnostmi. Trditev 2.1.1. Naj bo A ∈ n× n C in p( λ) polinom s kompleksnimi koeficienti, ki je deljiv z minimalnim polinomom mA( λ) matrike A. Naj bo p( λ) = p 1( λ) p 2( λ) , kjer sta p 1 in p 2 tuja 14 15 polinoma. Označimo V n i = ker pi( A) , i = 1 , 2 . Potem je C = V 1 ⊕ V 2 . Glede na ta razcep je A podobna matriki oblike A 1 0 . 0 A 2 Dokaz. Ker sta polinoma p 1 in p 2 tuja, obstajata polinoma q 1 in q 2, da je p 1( λ) q 1( λ) + p 2( λ) q 2( λ) = 1 . Izberimo v ∈ n C . Označimo v 1 = p 2( A) q 2( A) v in v 2 = p 1( A) q 1( A) v. Potem očitno velja v = v 1 + v 2. Ker je po predpostavki p( A) = 0, dobimo p 1( A) v 1 = p 1( A) p 2( A) q 2( A) v = p( A) q 2( A) v = 0 , torej je v n 1 ∈ V 1. Podobno dokažemo, da je v 2 ∈ V 2, torej je C = V 1 + V 2. Pokažimo, da je ta vsota direktna. Če je v ∈ V 1 ∩ V 2, je p 1( A) v = p 2( A) v = 0, zato je v = ( p 1( A) q 1( A) + p 2( A) q 2( A)) v = q 1( A) p 1( A) v + q 2( A) p 2( A) v = 0 . To že pomeni, da je n C = V 1 ⊕ V 2. Če je B1 neka baza prostora V 1, B2 pa baza prostora V 2, potem je B = B1 ∪ B2 baza prostora n C . Za vektor v ∈ V 1 velja p 1( A)( Av) = Ap 1( A) v = 0, torej je A( V 1) ⊆ V 1. Podobno je A( V 2) ⊆ V 2. Zato je matrika A BB iskane oblike. V posebnem lahko Trditev 2.1.1 uporabimo za primer p( λ) = mA( λ) in dobimo: Izrek 2.1.2 (Izrek o spektralnem razcepu). Naj bo A ∈ n× n C in mA( λ) = ( λ − λ 1) k 1 · · · ( λ − λr) kr njen minimalni polinom, pri čemer so λ 1 , . . . , λr paroma različne lastne vrednosti matrike A. Označimo Vi = ker( A − λiI) ki , i = 1 , . . . , r. Potem je n C = V 1 ⊕ V 2 ⊕ · · · ⊕ Vr. Glede na ta razcep je A podobna matriki oblike  A  1 A  2   .  ,  . .    Ar pri čemer je λi edina lastna vrednost matrike Ai za vsak i = 1 , . . . , r. Dokaz. Po Trditvi 2.1.1 je n C = V 1 ⊕ ker q( A) , kjer je q( λ) = ( λ − λ 2) k 2 · · · ( λ − λr) kr . Glede na ta razcep je matrika A podobna matriki A 1 0 . 0 A 0 Recimo, da je λ 1 lastna vrednost matrike A 0. Potem obstaja neničeln vektor v ∈ ker q( A), da je Av = λ 1 v, torej je v ∈ ker q( A) ∩ V 1 = {0}, kar ni mogoče. Torej λ 1 ni lastna vrednost matrike A 0. Minimalni polinom za A 0 je zato enak mA 0 ( λ) = ( λ − λ 2) k 2 · · · ( λ − λr) kr , minimalni polinom matrike A 1 pa je enak mA ( λ) = ( λ − λ 1 1) k 1 . Če prejšnjo trditev sedaj uporabimo za A 0, po r korakih dobimo iskani razcep. Podoben rezultat dobimo tudi, če namesto p( λ) vzamemo karakteristični polinom pA( λ); sklep je skoraj enak, zato ga bomo izpustili. 16 Primer 2.1.3 . Naj bo 1 2 1 A = 1 −1 1 .   2 0 1 Hiter račun pokaže, da je karakteristični polinom matrike A enak pA( λ) = ( λ + 1)2(3 − λ) . Ker velja ( A + I)( A − 3 I) 6= 0, je minimalni polinom matrike A kar mA( λ) = ( λ + 1)2( λ − 3) . Poiščimo najprej bazo za V 1 = ker( A + I)2. Ker je 8 4 6 ( A + I)2 = 4 2 3   8 4 6 matrika ranga 1, je dim V 1 = 2. Baza tega prostora je npr −1  0    B1 = 2 −3   ,   .  0 2  Podobno je baza prostora V 2 = ker( A − 3 I) npr 2   B2 = 1 .    2  V bazi B = B1 ∪ B2 ima A matriko −3 4 0 A BB = P BS AP SB = −1 1 0 .   0 0 3 Primer 2.1.4 . Naj bo P ∈ n× n C projektor, torej matrika, za katero velja P 2 = P . Recimo, da je P 6= 0 , I. Potem je minimalni polinom matrike P enak mP ( λ) = λ( λ − 1). Po Izreku o spektralnem razcepu je n C = ker P ⊕ ker( I − P ). Lahko je videti, da je ker( I − P ) = im P , torej n C = ker P ⊕ im P . Če je x ∈ ker P , je P x = 0, za x ∈ ker( I − P ) pa velja P x = x. Zato ima P glede na zgornji razcep matriko oblike 0 0 . 0 I 2.2 Jordanova kanonična forma matrike Definicija. Naj bo A ∈ n× n C in mA( λ) = ( λ − λ 1) k 1 · · · ( λ − λr) kr njen minimalni polinom, pri čemer so λ 1 , . . . , λr paroma različne lastne vrednosti matrike A. Podprostoru ker( A − λiI) ki pravimo korenski podprostor matrike A za lastno vrednost λi. 17 Iz Izreka o spektralnem razcepu torej sledi, da prostor n C lahko razcepimo na direktno vsoto korenskih podprostorov dane matrike A, glede na ta razcep pa je A podobna bločno diagonalni matriki  A  1 A  2   .  ,  . .    Ar katere bloki so matrike z eno samo lastno vrednostjo. Naš cilj je poiskati primerne baze korenskih podprostorov, v katerih bodo imeli ti bloki čim lepšo obliko. Zato lahko brez škode predposta- vimo, da je kar A matrika z eno samo lastno vrednostjo ρ. V tem primeru je njen karakteristični polinom enak pA( λ) = (−1) n( λ − ρ) n, minimalni polinom pa je oblike mA( λ) = ( λ − ρ) k. Če postavimo B = A − ρI, potem je pB( λ) = (−1) nλn in mB( λ) = λk. To pomeni, da je k najmanjše takšno naravno število, za katerega velja Bk = 0. Definirajmo Wi = ker Bi. Potem dobimo verigo podprostorov {0} = W n 0 ⊆ W 1 ⊆ W 2 ⊆ · · · ⊆ Wk = C . (2.1) Trditev 2.2.1. Inkluzije v verigi (2.1) so stroge. Dokaz. Recimo najprej, da velja W n k−1 = Wk = C . To bi pomenilo Bk−1 = 0, kar pa je v protislovju s tem, da je mB( λ) = λk. Zato velja Wk−1 6= Wk. Recimo, da za nek i velja Wi = Wi+1. Pokažimo, da potem velja Wi+1 = Wi+2. Če namreč izberemo poljuben x ∈ Wi+2, velja Bi+2 x = 0, torej je Bx ∈ Wi+1 = Wi, kar pomeni 0 = BiBx = Bi+1 x, torej je x ∈ Wi+1. S tem smo pokazali Wi+2 ⊆ Wi+1, obratna inkluzija pa vedno velja. Če torej za nek i velja Wi = Wi+1, potem iz zgornjega sledi Wi = Wi+1 = Wi+2 = · · · = Wk−1 = Wk, kar pa je v protislovju s prvim odstavkom. Lema 2.2.2. Za vektor x ∈ n C velja x ∈ Wi natanko tedaj, ko je Bx ∈ Wi−1 . Dokaz. Vektor x leži v Wi natanko tedaj, ko je Bi−1 Bx = Bix = 0, to pa je ekvivalentno z Bx ∈ Wi−1. Definicija. Naj bo V neprazna podmnožica vektorjev v n C . Pravimo, da je V i-linearno neod- visna, če veljajo naslednje zahteve: (a) V je vsebovana v Wi, (b) Vektorji v množici V so linearno neodvisni, (c) Vektorski podprostor Lin V ima trivialen presek s podprostorom Wi−1. Lema 2.2.3. Naj bo i > 1 . Če je množica vektorjev V i-linearno neodvisna, je množica B V = { Bv | v ∈ V} ( i − 1) -linearno neodvisna. 18 Dokaz. Naj bo V = { v 1 , v 2 , . . . , vs} . Ker je V ⊆ Wi, je po Lemi 2.2.2 množica B V vsebovana v Wi−1. Dokažimo sedaj, da je množica vektorjev B V = { Bv 1 , Bv 2 , . . . , Bvs} linearno neodvisna. Recimo, da za neke skalarje α 1 , α 2 , . . . , αs ∈ C velja α 1 Bv 1 + α 2 Bv 2 + · · · + αsBvs = 0 . To pomeni, da je α 1 v 1 + α 2 v 2 + · · · + αsvs ∈ ker B ⊆ ker Bi−1 = Wi−1, torej je zaradi i-linearne neodvisnosti množice V α 1 v 1 + α 2 v 2 + · · · + αsvs ∈ Lin V ∩ Wi−1 = {0} , zato so vektorji Bv 1 , Bv 2 , . . . , Bvs linearno neodvisni. Preostane še dokaz, da je Lin B V ∩ Wi−2 = {0}. Izberimo torej x ∈ Lin B V ∩ Wi−2. To pomeni, da je x = α 1 Bv 1 + α 2 Bv 2 + · · · + αsBvs za neke α 1 , α 2 , . . . , αs ∈ C, poleg tega pa je 0 = Bi−2 x = Bi−2( α 1 Bv 1 + α 2 Bv 2 + · · · + αsBvs) = Bi−1( α 1 v 1 + α 2 v 2 + · · · + αsvs) , kar pomeni α 1 v 1 + α 2 v 2 + · · · + αsvs ∈ Lin V ∩ Wi−1 = {0} . Od tod sledi x = 0, to pa smo želeli dokazati. Sedaj se lotimo konstrukcije posebne baze prostora n C . Ker je Wk−1 pravi podprostor v W n k = C , lahko z dopolnitvijo baze Wk−1 do baze celotnega prostora najdemo tak podprostor U 1 v Wk, da je n C = Wk = U 1 ⊕ Wk−1 . Najprej izberimo poljubno bazo podprostora U 1: U1 = { u(1) , u(1) , . . . , u(1)} . 1 2 s 1 Ker je n C = U 1 ⊕ Wk−1, je množica U1 k-linearno neodvisna. Po Lemi 2.2.3 je množica B U1 ( k − 1)-linearno neodvisna, kar pomeni, da so njeni elementi linearno neodvisni vektorji, ki ležijo v Wk−1, poleg tega pa je Lin B U1 ∩ Wk−2 = {0}. Zato lahko množico B U1 dopolnimo do baze podprostora U 2, za katerega velja Wk−1 = U 2 ⊕ Wk−2: U2 = { Bu(1) , Bu(1) , . . . , Bu(1) , u(2) , u(2) , . . . , u(2)} = { u(2) , u(2) , . . . , u(2)} . 1 2 s 1 s 1+1 s 1+2 s 2 1 2 s 2 Sedaj postopek ponovimo z množico U2; po k korakih dobimo podprostore U 1 , U 2 , . . . , Uk, za katere velja n C = Wk = U 1 ⊕ Wk−1 , Wk−1 = U 2 ⊕ Wk−2 , ... W 2 = Uk−1 ⊕ W 1 , W 1 = Uk ⊕ W 0 = Uk, skupaj z bazami U i = { u( i) , u( i) , . . . , u( i)} 1 2 si podprostorov Ui, ki so konstruirane na podoben način kot zgoraj. Velja: 19 Trditev 2.2.4. Velja n C = U 1 ⊕ U 2 ⊕ · · · ⊕ Uk. Dokaz. Iz konstrukcije sledi n n C = U 1 + U 2 + · · · + Uk. Izberimo x ∈ C in recimo, da je x = x 1 + x 2 + · · · + xk = y 1 + y 2 + · · · + yk, kjer x n i, yi ∈ Ui. Ker je C = U 1 ⊕ Wk−1 in x 1 , y 1 ∈ U 1, zaradi enoličnosti zapisa sledi x 1 = y 1 in x 2 + · · · + xk = y 1 + · · · + yk. S podobnim premislekom dobimo xi = yi za vsak i = 1 , 2 , . . . , k, od tod pa sledi, da je vsota podprostorov res direktna. Iz Trditve 2.2.4 sledi, da je U = U1 ∪ U2 ∪ · · · ∪ U k baza prostora n C . Pravimo ji Jordanova baza za matriko B. Če želimo, da bo matrika B UU za B v tej bazi lepa, moramo bazne elemente razvrstiti na poseben način; najprej zapišemo bazne vektorje v shemo, kot je prikazana v Tabeli 2.1. Tabela 2.1: vektorji Jordanove baze za B u(1) , . . . , u(1) 1 s 1 u(2) , . . . , u(2) , . . . , u(2) 1 s 1 s 2 u(3) , . . . , u(3) , . . . , u(3) , . . . , u(3) 1 s 1 s 2 s 3 .. . . . . .. .. .. u( k) , . . . , u( k) , . . . , u( k) , . . . , u( k) . . . , u( k) 1 s 1 s 2 s 3 sk Nato jih po vrsti izbiramo po stolpcih, začenši s prvim, od spodaj navzgor. Oglejmo si, kako izgleda matrika za B v tako urejeni bazi: Bu( k) = 0 , 1 Bu( k−1) = u( k) , 1 1 Bu( k−2) = u( k−1) , 1 1 ... Bu(1) = u(2) 1 1 Bu( k) = 0 , 2 ... Dobimo torej, da je  J  1 J  2  B UU =  .  ,  . .    Jsk pri čemer je vsaka od matrik Ji oblike 0 1  0 1     J . .   i = . . . . .      0 1 0 20 Matriko B UU ponavadi označimo z J( B) in ji pravimo Jordanova kanonična forma matrike B. Matrikam Ji pravimo Jordanove kletke matrike B. Iz konstrukcije Jordanove kanonične forme za B lahko razberemo, koliko je Jordanovih kletk posameznih velikosti. Opazimo namreč, da vsak stolpec v Tabeli 2.1 porodi natanko eno kletko. Tako imamo natanko s 1 kletk velikosti k × k, število kletk velikosti ( k − 1) × ( k − 1) je enako s 2 − s 1, itd. Splošno, število kletk velikosti j × j je enako sk− j+1 − sk− j. Število vseh kletk je enako sk. Iz zgornje konstrukcije je razvidno še, da je si = dim Wk− i+1 − dim Wk− i = dim ker Bk− i+1 − dim ker Bk− i, i = 1 , 2 , . . . , k, torej je število kletk velikosti j × j enako sk− j+1 − sk− j = 2 dim ker Bj − dim ker Bj+1 − dim ker Bj−1 , j = 1 , 2 , . . . , k. V posebnem je sk = dim ker B, torej je skupno število kletk za B enako velikosti baze lastnega podprostora B za lastno vrednost 0. To je razvidno tudi iz Tabele 2.1, saj bazo lastnega podprostora ker B tvorijo ravno vektorji u( k) , u( k) , . . . , u( k). Poleg tega opazimo, da je največja kletka 1 2 sk dimenzije k × k, kjer je k ravno stopnja minimalnega polinoma matrike B. Vrnimo se sedaj na primer, ko je A matrika z eno samo lastno vrednostjo ρ. Ker je A = B+ ρI, je A po zgornjem premisleku podobna matriki  J  1 J  2  J ( A) =  .  ,  . .    Jsr kjer so matrike Ji oblike  ρ 1  ρ 1     J . .   i = . . . . .      ρ 1 ρ Tudi v tem primeru matrikam Ji pravimo Jordanove kletke za lastno vrednost ρ. V splošnem je po Izreku o spektralnem razcepu matrika A ∈ n× n C podobna bločni matriki  A  1 A  2   .  ,  . .    Ar katere bloki so matrike z eno samo lastno vrednostjo. Zato je A podobna matriki  J( A  1) J ( A  2)  J ( A) =  .  ,  . .    J ( Ar) kjer so J ( Ai) bločno diagonalne matrike, katere bloki so Jordanove kletke (raznih velikosti) za dano lastno vrednost. Matriki J ( A) pravimo Jordanova kanonična forma matrike A. Velja A = P J ( A) P −1 , kjer je P prehodna matrika, katere stolpci so vektorji, ki jih dobimo iz zgornje konstrukcije Jordanove baze za matriko B. Tem stolpcem pravimo Jordanova baza za matriko A. Povzemimo sedaj celoten postopek v splošnem primeru: 21 Postopek za določanje Jordanove kanonične forme: Naj bo A ∈ n× n C matrika. Za vsako lastno vrednost λ matrike A, ki ima večkratnost r, ponovimo naslednji postopek: 1. Izračunamo ( A − λI) i za i = 1 , 2 , . . . . Imamo verigo podprostorov {0} < ker( A − λI) < ker( A − λI)2 < · · · . Potence matrike ( A − λI) računamo toliko časa, dokler so inkluzije v tej verigi stroge. Veriga se sčasoma ustali. Če označimo di = dim ker( A − λI) i, potem obstaja tak k, da velja d 1 < d 2 < · · · < dk−1 < dk = dk+1 = · · · = r. Veriga jeder matrik ( A − λI) i se ustali pri i = k. 2. Iz zgornjih podatkov lahko sklepamo naslednje: (a) Število Jordanovih kletk za lastno vrednost λ je enako d 1. (b) Največja kletka za lastno vrednost λ je velikosti k × k. (c) „Prispevek” lastne vrednosti λ k minimalnemu polinomu mA( x) matrike A je ( x − λ) k. (d) Če definiramo si = dk− i+1 − dk− i, i = 1 , 2 , . . . , k, je število kletk velikosti j × j enako s 1 : j = k , sk− j+1 − sk− j : j 6= k pri čemer j = 1 , 2 , . . . , k. 3. Določimo del Jordanove baze, ki pripada lastni vrednosti λ. Brez škode lahko Jorda- nove kletke za lastno vrednost λ uredimo padajoče po velikosti blokov; recimo, da so te velikosti n 1 ≥ n 2 ≥ · · · ≥ nd . 1 Izberemo v(1) ∈ ker( A − λI) n 1 \ ker( A − λI) n 1−1 , 1 ki je linearno neodvisen od predhodno dobljenih vektorjev, ki bodo tvorili Jordanovo bazo. Izračunamo v(2) = ( A − λI) v(1) , 1 1 v(3) = ( A − λI)2 v(1) , 1 1 ... v( n 1) = ( A − λI) n 1−1 v(1) . 1 1 Nato izberemo v(1) ∈ ker( A − λI) n 2 \ ker( A − λI) n 2−1 , 2 22 ki je linearno neodvisen od predhodno dobljenih vektorjev, ki bodo tvorili Jordanovo bazo. Izračunamo v(2) = ( A − λI) v(1) , 2 2 v(3) = ( A − λI)2 v(1) , 2 2 ... v( n 2) = ( A − λI) n 2−1 v(1) . 2 2 Postopek ponovimo za vsako Jordanovo kletko posebej. Dobljene vektorje zložimo v prehodno matriko P v naslednjem vrstnem redu: ( n ) ( n −1) v( n 1) , v( n 1−1) , . . . , v(1) , v( n 2) , v( n 2−1) , . . . , v(1) , . . . , v d 1 , v d 1 , . . . , v(1) . 1 1 1 2 2 2 d 1 d 1 d 1 Za vsako lastno vrednost Jordanove kletke zložimo bločno diagonalno v matriko J ( A), pri čemer so velikosti kletk za posamezno lastno vrednost urejene padajoče, vektorje Jordanove baze pa v matriko P v vrstnem redu, ki je opisan v koraku 3. Velja A = P J ( A) P −1 . Posledica 2.2.5. Matrika A ∈ n× n C se da diagonalizirati natanko tedaj, ko je njen minimalni polinom oblike mA( λ) = ( λ − λ 1)( λ − λ 2) · · · ( λ − λk) , kjer so λ 1 , λ 2 , . . . , λk paroma različne lastne vrednosti matrike A. Primer 2.2.6 . Naj bo 2 4 −8 A = 0 0 4 .   0 −1 4 Karakteristični polinom matrike A je pA( λ) = (2 − λ)3 , torej je 2 edina lastna vrednost matrike A. Ker je 0 4 −8 A − 2 I = 0 −2 4 ,   0 −1 2 je rang( A − 2 I) = 1, torej je dim ker( A − 2 I) = 2. Matrika A ima torej dve Jordanovi kletki, od koder brez nadaljnjega računanja lahko sklepamo, da je 2 1 0 J ( A) = 0 2 0 .   0 0 2 Poleg tega je ( A − 2 I)2 = 0, torej je dim ker( A − 2 I)2 = 3. Določimo sedaj Jordanovo bazo za A. Ker je naš primer enostavnejši od splošnega, ki je opisan zgoraj, bomo tu oznake nekoliko poenostavili. Za 2 × 2 kletko izberemo vektor v 2 ∈ ker( A − 2 I)2 \ ker( A − 2 I). Lahko vzamemo npr 0 v 2 = 1 .   0 23 Nato izračunamo  4  v 1 = ( A − 2 I) v 2 = −2 .   −1 Za 1 × 1 kletko pa izberemo vektor v 3 ∈ ker( A − 2 I), ki je linearno neodvisen od vektorjev v 1 in v 2. Ustrezna izbira je npr 1 v 3 = 0   . 0 Prehodna matrika P , za katero velja A = P J ( A) P −1, je potem  4 0 1 P = v 1 v 2 v 3 = −2 1 0 .   −1 0 0 Primer 2.2.7 . Recimo, da je A matrika velikosti 5 × 5, ki ima edini lastni vrednosti 2 in -1. Poleg tega vemo, da je rang( A − 2 I) = 3, rang( A − 2 I)2 = 1 in rang( A + I) = 4. V tem primeru je dim ker( A − 2 I) = 2 , dim ker( A − 2 I)2 = 4 , dim ker( A + I) = 1 . Imamo torej dve Jordanovi kletki za lastno vrednost 2 in eno kletko za lastno vrednost 1. Dimenzija ker( A − 2 I)2 je maksimalna možna, zato je velikost največje kletke za lastno vrednost 2 enaka 2 × 2. Tudi dimenzija ker( A + I) je največja možna, zato je kletka za lastno vrednost -1 velikosti 1 × 1. Zato je 2 1 0 0 0  0 2 0 0 0  J ( A) =   0 0 2 1 0  . 0 0 0 2 0    0 0 0 0 −1 2.3 Funkcije matrik Naj bo A kompleksna n × n matrika. Če je p( λ) = a 0 + a 1 λ + a 2 λ 2 + · · · + akλk polinom s kompleksnimi koeficienti, potem definiramo p( A) = a 0 I + a 1 A + a 2 A 2 + · · · + akAk. Pojavi se vprašanje, kako učinkovito izračunati p( A) za dano matriko A. To se prevede na računanje potenc matrike A. Če je stopnja polinoma majhna, potem lahko potence izračunamo neposredno. V splošnem pa je računanje potenc matrike A in s tem tudi p( A) zelo zamudno. Po drugi strani si lahko pri tem pomagamo z Jordanovo kanonično formo. Če je A = P J ( A) P −1, potem je À = P ( J ( A)) `P −1 . Ker je J ( A) oblike  J  1 J  2  J ( A) =  .  ,  . .    Jr 24 kjer so Ji Jordanove kletke za lastne vrednosti matrike A, je  J`  1  J ` 2  ( J ( A)) ` =  .  .  . .    J `r Zato je dovolj videti, kako izračunati potence Jordanove kletke  ρ 1  ρ 1     J = . .  . . . .  .      ρ 1 ρ V ta namen zapišemo J = ρI + N, kjer je 0 1  0 1     N = . .  . . . .  .      0 1 0 Hitro opazimo, da je 0 0 1  0 0 1    . . .   . . .  N 2 = . . .   .    0 0 1    0 0 0 Z indukcijo ni težko preveriti, da je N i zgornje trikotna matrika, ki ima prvih i naddiagonal enakih 0, na ( i + 1)-vi diagonali so same 1, drugje pa ničle. Ker matriki I in N komutirata, dobimo z uporabo binomskega izreka   ρ` ` ρ`−1 ` ρ`−2 . . . . . . ` ρ`− m 1 2 m  ρ` ` ρ`−1 ` ρ`−2 . . . ` ρ`− m+1  1 2 m−1  `  . . . .  X ` . . . . J ` = ( ρI+ N ) ` = ρ`− iN i =  . . . .    . i   i=0 ρ` ` ρ`−1 ` ρ`−2  1 2   ρ` ` ρ`−1   1  ρ` S tem smo našli razmeroma učinkovit način, kako izračunamo vrednost matričnega polinoma v matriki A. Postopek lahko posplošimo na naslednji način. Naj bo f realna (ali komple- ksna) funkcija, ki je neskončnokrat odvedljiva v okolicah lastnih vrednosti matrike A; slednjo predpostavko bomo rabili nekoliko kasneje. Če je A = P J ( A) P −1, potem definiramo f ( A) = P f ( J ( A)) P −1 . Podobno kot zgoraj definiramo  f ( J  1) f ( J  2)  f ( J ( A)) =  .  ,  . .    f ( Jr) 25 kjer so Ji Jordanove kletke matrike A. Preostane nam torej še, da smiselno definiramo f ( Ji). Oglejmo si Jordanovo kletko velikosti ( m + 1) × ( m + 1):  ρ 1  ρ 1     J = . .  . . . .  = ρI + N,      ρ 1 ρ kjer je N matrika kot zgoraj. Sedaj lahko funkcijo f razvijemo v Taylorjevo vrsto okoli točke ρ: ∞ X f ( i)( ρ) f ( λ) = ( λ − ρ) i. i! i=0 Ideja je, da f ( J ) definiramo tako, da v Taylorjevo vrsto vstavimo J namesto λ, podobno kot to naredimo za matrične polinome: ∞ ∞ X f ( i)( ρ) X f ( i)( ρ) f ( J ) = ( J − ρI) i = N i. i! i! i=0 i=0 Težava pa je, da imamo na desni strani neskončno matrično vrsto in bi sedaj morali razviti teorijo o tem, kdaj so takšne vrste konvergentne. Na srečo opazimo, da je vsota pravzaprav končna; po računu zgoraj namreč velja N m+1 = 0. Zato je   f ( ρ) f 0( ρ) f 00( ρ) . . . . . . f ( m)( ρ) 1! 2! ( m)!  f 00( ρ)   f ( ρ) f 0( ρ) . . . f ( m−1)( ρ) 1! 2! ( m−1)!  m   . X f ( i)( ρ)  . . .  f ( J ) = N i = . . . .  . . . .  . i!   i=0  f ( ρ) f 0( ρ) f 00( ρ)   1! 2!     f ( ρ) f 0( ρ)  1! f ( ρ) V resnici se izkaže, da bi za funkcijo f lahko predpostavili nekoliko manj; če je ρ lastna vrednost matrike A in k velikost največje Jordanove kletke za ρ, potem je dovolj, da je funkcija f k-krat odvedljiva v okolici ρ. Primer 2.3.1 . Naj bo 2 4 −8 A = 0 0 4 .   0 −1 4 Izračunajmo sin A. V Primeru 2.2.6 smo že izračunali Jordanovo kanonično formo matrike A in prehodno matriko: 2 1 0  4 0 1 J ( A) = 0 2 0 , P −2 1 0 .   =   0 0 2 −1 0 0 Potem je  2 1  sin sin A = P sin( J ( A)) P −1 = P 0 2 .   sin 2 Po zgornji formuli je 2 1 sin 2 cos 2 sin = . 0 2 0 sin 2 26 Zato je  4 0 1 sin 2 cos 2 0  0 0 −1 sin 2 4 cos 2 −8 cos 2  sin A = −2 1 0 0 sin 2 0 0 1 −2 0 −2 cos 2 + sin 2 4 cos 2 .       =   −1 0 0 0 0 sin 2 1 0 4 0 − cos 2 2 cos 2 + sin 2 Poglavje 3 Nenegativne matrike V tem poglavju bomo obravnavali realne matrike, katerih vsi elementi so nenegativni (oziroma pozitivni). Definicija. Naj bo A = [ aij] matrika nad R. Matrika A je nenegativna, če je aij ≥ 0 za vsaka i, j = 1 , 2 , . . . , n. V tem primeru pišemo A ≥ 0. Podobno pišemo A > 0, če so vsi elementi matrike A pozitivni. Primer 3.0.1 . Matrika 1 2 0 A = 3 0 1   1 1 4 je nenegativna, matrika 1 2 3 1 3 2 1 1 B =   1 1 4 3   2 1 3 5 pa pozitivna. Matrika 0 2 C = 3 −1 ni niti pozitivna niti nenegativna. Definicija. Za realni matriki A in B istih dimenzij pišemo A ≥ B ( A > B), če je A − B ≥ 0 ( A − B > 0). Nekaj očitnih lastnosti relacije ≥ je zbranih v naslednji trditvi; dokaz prepuščamo bralcu: Trditev 3.0.2. Naj bodo A, B, C n × n realne matrike in v ∈ n R . Recimo, da velja A ≥ B. Potem velja: (a) A + C ≥ B + C. (b) Če je C ≥ 0 , potem je AC ≥ BC in CA ≥ CB. (c) Če je v ≥ 0 , je Av ≥ Bv. Nenegativne matrike se zelo pogosto pojavijo v verjetnosti (markovske verige), teoriji grafov (matrike sosednosti grafov) ali v praktičnih primerih v ekonomiji, fiziki in drugje. Odlikuje jih cel kup lepih lastnosti in obstaja cela teorija znotraj linearne algebre, ki se ukvarja z nenegativnimi matrikami. Mi se bomo osredotočili le na kvadratne nenegativne matrike. Glavni rezultat, ki ga bomo dokazali, je Perron–Frobeniusov izrek, ki govori o lastnih vrednostih takšnih matrik. 27 28 3.1 Ireducibilne matrike Definicija. Naj bo σ permutacija množice {1 , 2 , . . . , n}. Permutacijska matrika, ki pripada permutaciji σ, je matrika, ki ima na mestih ( i, σ( i)), kjer i = 1 , 2 , . . . , n, enke, drugje pa ničle. Primer 3.1.1 . Permutacijska matrika, ki pripada identični permutaciji, je ravno identična ma- trika. Če je npr 1 2 3 4 σ = , 2 3 1 4 je ustrezna permutacijska matrika 0 1 0 0 0 0 1 0 P =    . 1 0 0 0   0 0 0 1 Opomba 3.1.2 . Očitno je vsaka permutacijska matrika P ortogonalna, zato je P −1 = P T. Poleg tega opazimo še naslednje: Če kvadratno matriko A z desne množimo s permutacijsko matriko P , ki pripada permutaciji σ, je rezultat matrika, katere i-ti stolpec je σ( i)-ti stolpec matrike A. Če A z leve pomnožimo s P T, dobimo matriko, katere i-ta vrstica je σ( i)-ta vrstica matrike A. Definicija. Naj bo n ≥ 2. Nenegativna n × n matrika A je reducibilna ( razcepna), če obstaja permutacijska matrika P , da je matrika P T AP oblike B C , 0 D kjer sta matriki B in D kvadratni. Nenegativna matrika je ireducibilna ( nerazcepna), če ni reducibilna (razcepna). Matrika A je torej reducibilna, če jo lahko s končno mnogo hkratnih menjav vrstic in stolpcev prevedemo v bločno matriko iz zgornje definicije. Očitno so vse pozitivne matrike ireducibilne. Oglejmo si še kakšen zgled: Primer 3.1.3 . Matrika 1 0 0 A = 3 1 2   2 3 0 je reducibilna; če namreč hkrati zamenjamo 1. in 3. vrstico ter 1. in 3. stolpec, dobimo matriko 0 3 2 2 1 3 ,   0 0 1 ki ima na diagonali en 2 × 2 blok in en 1 × 1 blok, pod prvim blokom pa so same ničle. Matrika 0 1 0 B = 3 0 3   0 2 0 je po drugi strani ireducibilna. To lahko ugotovimo s preverjanjem vseh možnih izrazov P T BP , kjer je P permutacijska matrika velikosti 3×3; takšnih matrik je, vključno z identično matriko, 6. Podrobnosti prepustimo bralcu; kasneje bomo izpeljali dosti bolj nazoren kriterij za preverjanje ireducibilnosti. Trditev 3.1.4. Naj bo A ireducibilna nenegativna matrika velikosti n × n, kjer je n ≥ 2 . Naj bo y nenegativen vektor v n R , ki ima natanko k pozitivnih komponent, kjer je 1 ≤ k < n. Potem ima vektor ( I + A) y več kot k pozitivnih komponent. 29 Dokaz. Naj bo P takšna permutacijska matrika, da ima vektor x = P y prvih k komponent pozitivnih, ostale pa so enake 0. Z drugimi besedami, vektor x dobimo tako, da komponente vektorja y ustrezno premešamo. Oglejmo si vektor ( I + A) y = y + Ay. Ker je A ≥ 0, ima ta vektor kvečjemu n − k ničelnih komponent. Recimo, da jih ima točno n − k (predpostavimo torej nasprotno od tega, kar trdi rezultat). To pomeni, da če je i-ta komponenta vektorja y enaka 0, je tudi i-ta komponenta vektorja Ay enaka 0. Med drugim to pomeni, da če je i-ta komponenta P y enaka nič, je tudi i-ta komponenta P Ay enaka 0. Ker je y = P T x, to pomeni da je i-ta komponenta vektorja P AP T x enaka 0 za i = k + 1 , k + 2 , . . . , n. Označimo B = P AP T in si oglejmo i-to komponento vektorja Bx za i > k: n k X X 0 = bijxj = bijxj. j=1 j=1 Ker pa so xj > 0 za j = 1 , 2 , . . . , k, sledi bij = 0 za i > k, j ≤ k. To pomeni, da je matrika B = P AP T oblike C D , 0 E kjer je C blok velikosti k × k, E pa blok velikosti ( n − k) × ( n − k). To je v protislovju z ireducibilnostjo matrike A. S tem je trditev dokazana. Posledica 3.1.5. Naj bo A nenegativna ireducibilna matrika velikosti n × n, kjer je n ≥ 2 . Naj bo y neničeln nenegativen vektor v n R . Potem je ( I + A) n−1 y > 0 . Naslednji rezultat nam da kriterij za preverjanje ireducibilnosti matrik. Posledica 3.1.6. Nenegativna n× n matrika je ireducibilna natanko tedaj, ko je ( I + A) n−1 > 0 . Dokaz. Če je A ireducibilna, je po Posledici 3.1.5 ( I + A) n−1 ej > 0 , kjer je ej stolpec, ki ima na j-tem mestu 1, drugje pa 0. To pomeni, da je j-ti stolpec matrike ( I + A) n−1 pozitiven. Ker to velja za vse j = 1 , 2 , . . . , n, sledi ( I + A) n−1 > 0. Recimo sedaj, da je ( I + A) n−1 > 0. Recimo, da je matrika A reducibilna. Potem obstaja permutacijska matrika P , da je B C P T AP = , 0 D kjer sta matriki B in D kvadratni. Zato je I + B C n−1 ∗ ∗ P T( I + A) n−1 P = ( P T( I + A) P ) n−1 = ( I + P T AP ) n−1 = = , 0 I + D 0 ∗ kar pa je v protislovju s tem, da je matrika P T( I + A) n−1 P pozitivna. 30 Ta kriterij je koristen za preverjanje ireducibilnosti majhnih matrik. Kot smo videli v po- glavju o Jordanovi kanonični formi, je računanje višjih potenc velikih matrik lahko precej zamu- dno. Primer 3.1.7 . Oglejmo si matriko B iz Zgleda 3.1.3: 0 1 0 B = 3 0 3   . 0 2 0 Ker je  2 1 1 0 4 2 3 ( I + B)2 = 3 1 3 6 10 6 >   =   0 , 0 2 1 6 4 7 je matrika B ireducibilna. Naslednji rezultat pove nekaj o nenegativnih lastnih vektorjih ireducibilnih matrik. Uporabili ga bomo pri dokazu Perron–Frobeniusovega izreka. Trditev 3.1.8. Naj bo x nenegativen lasten vektor nenegativne ireducibilne matrike A. Potem je x > 0 . Dokaz. Naj bo Ax = λx. Če primerjamo komponente na levi in desni strani, lahko sklepamo, da je λ ≥ 0. Če ima x natanko k ničelnih komponent, ima po Trditvi 3.1.4 vektor ( I + A) x več kot k ničelnih komponent. To pa ni mogoče, saj je ( I + A) x = (1 + λ) x, zato mora biti x pozitiven vektor. Izrek 3.1.9. Nenegativna kvadratna matrika A je ireducibilna natanko tedaj, ko za vsak par indeksov ( i, j) obstaja naravno število k, da je ( i, j) -ta komponenta matrike Ak pozitivna. Dokaz. Naj bo A velikosti n× n. Recimo, da je A ireducibilna. Po Posledici 3.1.6 je ( I + A) n−1 > 0. Označimo B = ( I + A) n−1 A. Matrika B je pozitivna; v njej bi lahko obstajal ničeln element le v primeru, ko bi matrika A imela kakšen stolpec iz samih ničel, to pa ne gre zaradi ireducibilnosti. Po binomskem izreku je n−1 X n − 1 B = Ak+1 . k k=0 Ker je bij > 0 za vsaka i, j = 1 , 2 . . . , n, mora obstajati takšen 0 ≤ k ≤ n − 1, da je ( i, j)-ta komponenta matrike Ak+1 pozitivna. Predpostavimo sedaj, da je matrika reducibilna. Pokazali bomo, da obstajata indeksa i in j, da je ( i, j)-ta komponenta matrike Ak enaka 0 za vsak k. Po predpostavki obstaja permutacijska matrika P , da je B C P T AP = , 0 D kjer sta matriki B in D kvadratni, velikost matrike B naj bo s × s. Če velja s + 1 ≤ i ≤ n in 1 ≤ j ≤ s, potem je ( i, j)-ta komponenta matrike B C k P T AkP = ( P T AP ) k = 0 D enaka 0 za vsak k. 31 Izrek 3.1.9 je osnova za zelo uporaben kriterij za preverjanje ireducibilnosti dane matrike. Preden ga navedemo, si oglejmo nekaj pojmov iz teorije grafov. Usmerjen graf je par G = ( V, E), kjer je V množica vozlišč, E pa množica urejenih parov ( i, j), kjer sta i in j vozlišči. Takšnim urejenim parom pravimo povezave; predpostavimo, da naš graf nima povezav oblike ( i, i). Pravimo tudi, da imamo povezavo od i do j in to zapišemo kot i → j. Grafe lahko predstavimo grafično tako, da vozlišča narišemo kot točke, povezave ( i, j) pa kot usmerjene daljice od i do j. Pot v usmerjenem grafu G med vozliščema u in v je končno zaporedje vozlišč u = v 0 , v 1 , v 2 , . . . , vk = v, za katero velja, da so vsi urejeni pari ( vi, vi+1) v množici povezav grafa G. Pravimo, da je k dolžina poti med u in v. Vsakemu (usmerjenemu) grafu lahko priredimo matriko sosednosti. Označimo vozlišča grafa s števili {1 , 2 , . . . , n} in tvorimo n × n matriko A na naslednji način: 1 : obstaja povezava od i do j aij = . 0 : sicer Da se dokazati, da če je A matrika sosednosti usmerjenega grafa, potem je ( i, j)-ti element matrike Ak enak 1, če obstaja pot dolžine k med i in j, in 0 sicer. Posledica 3.1.10. Naj bo A nenegativna matrika velikosti n × n. Priredimo ji usmerjen graf G, katerega vozlišča so števila {1 , 2 , . . . , n} , urejeni par ( i, j) pa je povezava natanko tedaj, ko aij 6= 0 . Potem je matrika A ireducibilna natanko tedaj, ko za vsaka i, j ∈ {1 , 2 , . . . , n} , i 6= j, obstaja pot v grafu G med vozliščema i in j. Dokaz. V grafu G je matrika sosednosti ravno matrika B, za katero je 1 : a b ij 6= 0 ij = . 0 : sicer Rezultat od tod hitro sledi. Primer 3.1.11 . Oglejmo si matriko 0 0 1 0 0 0 0 1 A =    . 0 1 0 0   1 0 0 0 Priredimo ji graf iz Posledice 3.1.10: 1 4 2 3 32 Hitro preverimo, da iz vsakega vozlišča obstaja pot do vsakega drugega vozlišča, torej je matrika A ireducibilna. Oglejmo si še matriko 0 0 1 0 0 0 1 1 B =    . 1 0 0 0   1 1 0 0 Ustrezen graf je 1 4 2 3 Ker iz vozlišča 1 ni poti do vozlišča 2, je matrika B reducibilna. 3.2 Collatz–Wielandtova funkcija V tem razdelku si bomo ogledali funkcijo, ki ji pravimo Collatz–Wielandtova funkcija in igra ključno vlogo pri dokazu Perron–Frobeniusovega izreka. Za začetek vpeljimo oznaki: n n P = {( x 1 , x 2 , . . . xn) ∈ R | xi ≥ 0 za vsak i} , n n E = {( x 1 , x 2 , . . . xn) ∈ P | x 1 + x 2 + . . . + xn = 1} . Poleg tega i-to komponento danega vektorja x označimo z xi. Definicija. Naj bo A nenegativna ireducibilna n × n matrika. Definirajmo funkcijo f n A : P \ {0} → [0 , ∞) s predpisom ( Ax) i fA( x) = min . xi 6=0 xi Funkciji fA pravimo Collatz–Wielandtova funkcija matrike A. Primer 3.2.1 . Naj bo 2 2 1 A = 2 2 1 .   0 2 1 Matrika A je očitno ireducibilna. Izberimo 1 x = 2 .   0 33 Potem je 6 Ax = 6 ,   4 zato je fA( x) = min{6 / 1 , 6 / 2} = 3 . Videli bomo, da je funkcija f n A omejena na P \ {0}. Glavni rezultat, ki ga bomo dokazali, je naslednji: Izrek 3.2.2. Naj bo A nenegativna ireducibilna n × n matrika. Potem funkcija fA, zožena na množico n E , zavzame globalni maksimum. Pri dokazu Izreka 3.2.2 bomo uporabili nekaj pomožnih trditev, ki se dokažejo elementarno, na koncu pa še nekaj malega analize. Potrebne definicije za slednje na hitro povzemimo na tem mestu, pri čemer pripomnimo, da se da vse skupaj narediti v dosti večji splošnosti, tu pa bomo situacijo priredili za naše potrebe. Za a ∈ n R in > 0 definirajmo odprto kroglo s središčem v a in polmerom kot množico K( a, r) = { x ∈ n R | k x − a k < } . Zaporedje vektorjev x n k v R konvergira proti vektorju x, če za vsak > 0 obstaja naravno število k 0, da za vsak k ≥ k 0 velja k xk − x k < , kar lahko pišemo tudi kot xk ∈ K( x, ). To je ekvivalentno s tem, da za vsak i = 1 , 2 , . . . , n zaporedje i-tih komponent vektorjev xk konvergira k i-ti komponenti vektorja x. Pišemo x = lim xk. k→∞ Če je f : n n R → R zvezna funkcija n spremenljivk in xk zaporedje vektorjev v R , ki konvergira proti vektorju x, potem je lim f ( xk) = f ( x) . k→∞ Podmnožica M v n R je odprta, če za vsak a ∈ M obstaja > 0, da je K( a, ) ⊆ M . Za prazno množico dodatno definiramo, da je odprta v n n R . Za podmnožico M ⊆ R pravimo, da je zaprta, če je n R \ M odprta množica. Zaprte množice lahko karakteriziramo kot tiste podmnožice M v n R , za katera velja, da če vzamemo poljubno konvergentno zaporedje v M , potem tudi limita leži v M . Poleg tega pravimo, da je množica M v n R omejena, če obstaja > 0 in a ∈ M , da je M ⊆ K( a, ). Omejenim zaprtim podmnožicam v n R pravimo kompaktne množice. Tudi kompaktnost množic lahko karakteriziramo z zaporedji elementov; množica M ⊂ n R je kompaktna natanko tedaj, ko za vsako zaporedje vektorjev v M obstaja neskončno podzaporedje, ki konvergira k nekemu elementu množice M . Za nas bo pomemben naslednji rezultat: Izrek 3.2.3. Naj bo M kompaktna podmnožica v n R in f : M → R zvezna funkcija. Potem funkcija f zavzame globalna ekstrema na M . Množica n n E je omejena in zaprta podmnožica v R , zato je kompaktna. Na prvi pogled izgleda, da je to že dovolj za dokaz Izreka 3.2.2. Žal pa funkcija f n A ni zvezna na E ; oglejmo si to na primeru: Primer 3.2.4 . Naj bo 2 2 1 A = 2 2 1 .   0 2 1 Naj bo > 0 in definirajmo 1 1 x( ) = 0 .   1 + 34 Očitno je x( ) ∈ 3 E . Poleg tega je 2 +  1 Ax( ) = 2 + .   1 + Zato je fA( x( )) = min{2 + , 1} = 2 + . Velja 1 x = lim x( ) = 0 ,   →0 0 toda lim fA( x( )) = 2 6= 1 = fA( x) . →0 Zato fA ni zvezna v x. Zgornji primer kaže, da sklep z zveznostjo ne bo deloval pri dokazu Izreka 3.2.2, vsaj nepo- sredno ne. Po definiciji funkcije f n A je le-ta gotovo zvezna za tiste x ∈ E , ki so strogo pozitivni, težave pa nastopijo v vektorjih, ki imajo kakšno ničelno komponento; to pokaže tudi zgornji zgled. Ideja dokaza Izreka 3.2.2 je, da se temu izognemo s pomočjo Posledice 3.1.5. Najprej si oglejmo nekaj osnovnih lastnosti Wielandt–Collatzove funkcije: Trditev 3.2.5. Naj bo A nenegativna ireducibilna n× n matrika in fA njena Wielandt–Collatzova funkcija. Naj bo x ∈ n P \ {0} . (a) Za vsak t > 0 velja fA( tx) = fA( x) . (b) Naj bo ρ največje realno število, za katerega je Ax − ρx ≥ 0 . Potem je fA( x) = ρ. (c) Za y = ( I + A) n−1 x velja fA( y) ≥ fA( x) . Dokaz. (a) Direkten račun da ( A( tx)) i t( Ax) i fA( tx) = min = min = fA( x) . ( tx) ( tx) tx i 6=0 i xi 6=0 i (b) Po definiciji funkcije fA je Ax − fA( x) x ≥ 0 , (3.1) kar pomeni, da je fA( x) ≤ ρ. Poleg tega obstaja tak k, da je xk neničelna komponenta vektorja x, k-ta komponenta vektorja Ax − fA( x) x pa je enaka 0. Če je torej ρ > fA( x), potem je k-ta komponenta vektorja Ax − ρx negativna, kar je v protislovju z definicijo števila ρ. Zato je fA( x) = ρ. (c) Pomnožimo neenačbo (3.1) z matriko ( I + A) n−1; to lahko storimo zaradi Trditve 3.0.2: A( I + A) n−1 x − fA( x)( I + A) n−1 x ≥ 0 , oziroma Ay − fA( x) y ≥ 0 . Po točki (b) sledi fA( y) ≥ fA( x). Trditev 3.2.6. Naj bo A nenegativna ireducibilna n× n matrika in fA njena Wielandt–Collatzova funkcija. Potem je f n n A omejena funkcija na P \ {0} . Še več, za vsak x ∈ P \ {0} velja 0 ≤ fA( x) ≤ k A k1 , kjer je k A k1 maksimum vsot stolpcev matrike A. 35 Dokaz. Očitno je fA ≥ 0. Označimo s n X cj = aij i=1 vsoto elementov j-tega stolpca matrike A. Po definiciji imamo za vsak x ∈ n E neenakost ( Ax) i ≥ fA( x) xi, kar lahko zapišemo na dolgo kot n X aijxj ≥ fA( x) xi. j=1 Seštejmo te neenakosti za vse i = 1 , 2 , . . . , n: n n n n X X X X aijxj ≥ fA( x) xi = fA( x) xi = fA( x) . i=1 j=1 i=1 i=1 Na levi strani te neenačbe lahko zamenjamo vrstni red seštevanja: n n X X aijxj ≥ fA( x) , j=1 i=1 n n X X xj aij ≥ fA( x) , j=1 i=1 n X xjcj ≥ fA( x) . j=1 Ker po definiciji velja k A k1 ≥ cj za vsak j = 1 , 2 , . . . , n, dobimo neenakost n n n X X X k A k1 = max ci = max ci xj = max ci · xj ≥ cjxj ≥ fA( x) , i i i j=1 j=1 j=1 kar smo želeli dokazati. Dokaz Izreka 3.2.2. Oglejmo si podmnožico Ω = {( I + A) n−1 x | x ∈ n E } v n R . Podobno kot zgoraj je tudi množica Ω kompaktna. Ker je matrika A ireducibilna, so po Posledici 3.1.5 vsi vektorji iz Ω strogo pozitivni. Zato je funkcija fA zvezna na Ω, torej tam zavzame globalni maksimum. Recimo, da se to zgodi v točki z ∈ Ω, ki je oblike  z  1 z  2  z =  .  .  .   .  zn Vektor z ima vse komponente striktno pozitivne. Definirajmo vektor  z  1 1 z  2  x 0 =  .  . z  .  1 + z 2 + · · · + zn  .  zn 36 Potem je x 0 ∈ n n E . Izberimo sedaj poljuben x ∈ E in postavimo y = ( I + A) n−1 x ∈ Ω. Po Trditvi 3.2.5 (c) je fA( x) ≤ fA( y). Ker je y ∈ Ω, je fA( y) ≤ fA( z) = fA(( z 1 + z 2 + . . . + zn) x 0) = fA( x 0) , pri čemer zadnja enakost sledi iz Trditve 3.2.5 (a). Dokazali smo torej fA( x) ≤ fA( x 0) za vsak x ∈ n E , torej fA zavzame globalni maksimum pri x = x 0. 3.3 Največja lastna vrednost nenegativne matrike Izrek 3.3.1 (Perron–Frobeniusov izrek). Naj bo A ireducibilna nenegativna n × n matrika. Potem obstaja lastna vrednost ρ matrike A, za katero velja ρ ≥ | λ| za vsako lastno vrednost λ matrike A. Poleg tega obstaja pozitiven lasten vektor matrike A za lastno vrednost ρ. Dokaz. Po Izreku 3.2.2 obstaja vektor x 0 ∈ n E , da velja fA( x 0) ≥ fA( x) za vse x ∈ n E . Definirajmo ρ = fA( x 0) . Dokazali bomo, da je ρ iskana maksimalna lastna vrednost matrike A, vektor x 0 pa iskani pozitiven lastni vektor matrike A za lastno vrednost ρ. Dokaz bomo razdelili v več korakov. Korak 1: Dokažimo, da je ρ > 0 . V ta namen si oglejmo vektor 1 1 1   u =  .  n  .   .  1 iz n E . Velja 1 P n n ( Au) a i j=1 ij X ρ ≥ f n A( u) = min = min = min aij. i u 1 i i i n j=1 Slednji izraz je strogo pozitiven, saj zaradi ireducibilnosti matrika A ne more imeti ničelne vrstice. Korak 2: Dokažimo, da je ρ lastna vrednost matrike A, vektor x 0 pa lasten vektor. Recimo, da Ax 0 − ρx 0 6= 0. Po definiciji je Ax 0 − ρx 0 ≥ 0 . Iz Posledice 3.1.5 sledi ( I + A) n−1( Ax 0 − ρx 0) > 0 . Če označimo y 0 = ( I + A) n−1 x 0, lahko zgornjo neenakost zapišemo kot Ay 0 − ρy 0 > 0 . 37 Zato obstaja δ > 0, da je Ay 0 − ( ρ + δ) y 0 ≥ 0 . Po Trditvi 3.2.5 (b) je zato ρ + δ ≤ fA( y 0) , torej je ρ < fA( y 0). To je v protislovju z maksimalnostjo ρ. To pomeni, da je ρ lastna vrednost matrike A z lastnim vektorjem x 0. Korak 3: Dokažimo, da je x 0 > 0. Ker je x 0 ≥ 0, to sledi direktno iz Trditve 3.1.8. Korak 4: Dokažimo, da je ρ ≥ | λ| za vsako lastno vrednost λ matrike A. Naj bo z lasten vektor matrike A za lastno vrednost λ. Napišimo enakost Az = λz po komponentah: n X λzi = aijzj. j=1 Od tod po trikotniški neenakosti sledi n n X X | λ| · | z i| = aijzj ≤ aij| zj| . j=1 j=1 Če to napišemo nazaj v vektorski zapis, dobimo | λ| · | z| ≤ A| z| , pri čemer je | z| vektor, katerega i-ta komponenta je | zi| za vsak i. Po Trditvi 3.2.5 (b) je | λ| ≤ fA(| z|) , ker pa je ρ globalni maksimum funkcije fA, sledi | λ| ≤ ρ. Lastni vrednosti ρ iz Perron–Frobeniusovega izreka pravimo Perron–Frobeniusova lastna vrednost matrike A, pozitivnemu lastnemu vektorju za lastno vrednost ρ pa pravimo Perron– Frobeniusov lasten vektor matrike A. Opomba 3.3.2 . V dokazu Izreka 3.3.1 smo v Koraku 2 pravzaprav dokazali naslednje: Če je x ≥ 0 in Ax − ρx ≥ 0, potem je x lasten vektor matrike A za lastno vrednost ρ. Po Trditvi 3.1.8 je x celo Perron–Frobeniusov lastni vektor za A. Primer 3.3.3 . Oglejmo si matriko 1 2 3 A = 0 1 1 .   2 1 3 Matrika A je nenegativna in ireducibilna, njeni lastni vrednosti sta 5 (enojna) in 0 (dvojna). 5 je torej Perron–Frobeniusova lastna vrednost za A. Lastni podprostor matrike A za lastno vrednost λ = 5 je 7   Lin 2   .  8  7 Perron–Frobeniusovi lastni vektorji matrike A so natanko pozitivni večkratniki vektorja 2  . 8 Perron–Frobeniusov izrek v posebnem velja za vse pozitivne matrike. Če je matrika A nenegativna in reducibilna, sklep Perron–Frobeniusovega izreka ne velja vedno: 38 Primer 3.3.4 . Naj bo 1 1 A = . 0 1 Matrika A je reducibilna. 1 je dvojna lastna vrednost matrike A, Lastni podprostor pa je 1 Lin . 0 Zato matrika A nima striktno pozitivnega lastnega vektorja. Omenimo, da je mogoče pokazati še več lastnosti Perron–Frobeniusovih lastnih vrednosti in vektorjev nenegativnih ireducibilnih matrik. Tu omenimo le dva rezultata v tej smeri: Izrek 3.3.5. Perron–Frobeniusova lastna vrednost nenegativne ireducibilne matrike je enostavna ničla karakterističnega polinoma. Dokaz. Dokaz je predolg, zato ga izpustimo. Posledica 3.3.6. Naj bo A nenegativna ireducibilna matrika. Potem je lastni podprostor za Perron–Frobeniusovo lastno vrednost enorazsežen; vsak Perron-Frobeniusov lasten vektor je ska- larni večkratnik Perron-Frobeniusovega lastnega vektorja z normo 1. Dokaz. Direktna posledica Izreka 3.3.5. Za splošne nenegativne matrike imamo naslednji rezultat, ki sledi iz Perron–Frobeniusovega izreka in dejstva, da so lastne vrednosti in lastni vektorji zvezne funkcije elementov matrik (preveri!): Izrek 3.3.7. Naj bo A nenegativna n × n matrika. Potem ima A nenegativno lastno vrednost ρ, za katero velja ρ ≥ | λ| za vsako lastno vrednost λ matrike A. Poleg tega obstaja nenegativen lasten vektor matrike A za lastno vrednost ρ. Dokaz. Izberimo > 0 in pišimo A = A + B, kjer je B neka pozitivna n × n matrika. Potem je A > 0, zato po Perron–Frobeniusovem izreku obstajata Perron–Frobeniusova lastna vrednost ρ matrike A in Perron-Frobeniusov lasten vektor x > 0. To pomeni, da za vsako lastno vrednost λ matrike A velja ρ ≥ | λ| (3.2) in Ax = ρx. (3.3) Pošljimo sedaj → 0. Potem A → A. Zaradi zgoraj omenjene zveznosti obstajata limiti ρ = lim ρ →0 in x = lim x. →0 Ker je ρ > 0 in x > 0, je ρ ≥ 0 in x ≥ 0. Lastne vrednosti λ matrik A konvergirajo proti λ, ki je zaradi zveznosti lastna vrednost matrike A. Poleg tega zaradi (3.2) in (3.3) velja ρ ≥ | λ| in Ax = ρx. Poglavje 4 Linearen model proizvodnje V ekonomiji je dostikrat pomembno razumeti povezave med proizvodnjo in distribucijo izdelkov. Eden od ključnih modelov, ki pripomorejo k razumevanju tega, je model Leontijeva. V tem poglavju si bomo na kratko ogledali ta model in s pomočjo orodij linearne algebre izpeljali pogoje za to, da model da smiselne rešitve. 4.1 Model Leontijeva Recimo, da imamo n proizvajalcev, od katerih vsak proizvaja natanko eno dobrino. Te proi- zvajalce oziroma dobrine označimo kar s števili 1 , 2 , . . . , n. Naj bo xi količina dobrine i, ki jo proizvedemo. Predpostavimo, da se dobrina i se uporablja pri proizvodnji vseh dobrin 1 , 2 , . . . , n, poleg tega pa lahko del izdelkov proizvajalca i potrebujejo tudi zunanji uporabniki (drugi proi-zvajalci, gospodinjstva,...). Označimo z xij količino dobrine i, ki jo potrebuje prizvajalec j, z di pa označimo količino dobrine i, ki jo potrebujejo zunanji odjemalci. Očitno mora veljati xij ≥ 0 in di ≥ 0. Če predpostavimo, da je proizvodnja enaka povpraševanju, mora veljati xi 1 + xi 2 + . . . + xin + di = xi (4.1) za vsak i = 1 , 2 , . . . , n. Problem, s katerim se bomo ukvarjali, je poiskati takšne xi, da bodo vse enačbe (4.1) izpolnjene. Smiselno je predpostaviti, da vsak od proizvajalcev proizvede pozitivno količino svojega iz- delka (tovarna ne stoji), torej, da velja xi > 0. Takšnim rešitvam bomo rekli smiselne rešitve. V tem primeru lahko definiramo xij aij = . xj Število aij torej pove, koliko enot dobrine i rabimo za proizvodnjo ene enote dobrine j. Enačbe (4.1) lahko v tem primeru zapišemo kot ai 1 x 1 + ai 2 x 2 + . . . + ainxn + di = xi (4.2) za vsak i = 1 , 2 , . . . , n. To lahko zapišemo v matrični obliki; če označimo A = [ aij] in  x    1 d 1 x d  2   2  x =  .  , d =  .  ,  .   .   .   .  xn dn Potem velja Ax + d = x oziroma ( I − A) x = d. (4.3) 39 40 Z drugimi besedami, rešujemo sistem linearnih enačb. Matriki A pravimo matrika Leontijeva oziroma vhodno–izhodna matrika, vektorju x pravimo vektor proizvodnje, vektorju d pa vektor povpraševanja. 4.1.1 Zaprti model Leontijeva Ogledali si bomo dva modela zgornjega proizvodnega problema; razlika bo v tem, ali je vektor povpraševanja ničeln ali ne. Najprej definirajmo: Definicija. Zaprti model Leontijeva je homogen sistem enačb ( I − A) x = 0 , za katerega velja: (a) Matrika A je nenegativna kvadratna matrika. (b) Za vsak j obstaja i, da je aij > 0. (c) aii < 1 za vsak i. (d) Vsota elementov v vsakem stolpcu matrike A je enaka 1. Smiselnost predpostavke (a) je očitna. Predpostavko (b) lahko interpretiramo na naslednji način. Če bi obstajal tak j, da bi veljalo aij = 0 za vse i, bi to pomenilo, da za proizvodnjo dobrine j ne rabimo nobene od dobrin 1 , 2 , . . . , n. V proizvodnem problemu, ki smo ga zgoraj obravnavali, smo predpostavili ravno nasprotno, zato je tudi predpostavka (b) smiselna glede na zgornji problem. Predpostavka (c) v zgornjem modelu proizvodnje enostavno pove, da za proizvodnjo ene enote dobrine i rabimo manj kot eno enoto iste dobrine. Predpostavljamo torej, da lahko vsak proizvajalec proizvede več svojih dobrin, kot jih potrebuje zase. Predpostavko (d) utemeljimo z dejstvom, da pri zaprtem modelu proizvodnje predpostavimo, da se celotna proi- zvodnja dobrine i porabi znotraj vseh panog. To v našem jeziku pomeni, da je vsota elementov v vsakem stolpcu matrike A enaka 1. Na hitro si oglejmo, kdaj obstajajo smiselne rešitve zaprtega modela Leontijeva. Ta model ima vedno nenegativno rešitev x = 0. Če je matrika I − A obrnljiva, t.j., 1 ni lastna vrednost matrike A, potem je x = 0 tudi edina rešitev modela Leontijeva. To seveda ni smiselna rešitev, zato mora matrika A imeti eno lastno vrednost enako 1. V resnici to sledi iz naših predpostavk. Preden to utemeljimo, si oglejmo, kaj so to markovske matrike: Definicija. Markovska matrika je nenegativna matrika, v katerih je vsota vsake vrstice enaka 1. Markovske matrike so pomembne v verjetnosti v teoriji markovskih verig. Primer takšne matrike je 1 / 3 1 / 6 1 / 2 0 1 / 3 2 / 3 .   1 / 2 1 / 2 0 Trditev 4.1.2. Naj bo A markovska matrika. Potem je 1 lastna vrednost matrike A. Za vsako lastno vrednost λ velja | λ| ≤ 1 . Dokaz. Očitno je 1 1   x =  .   .   .  1 41 rešitev sistema ( I − A) x = 0. Vektor x je lasten vektor matrike A za lastno vrednost 1. Naj bo λ poljubna lastna vrednost matrike A z lastnim vektorjem v. Recimo, da velja | λ| > 1. Ker je Anv = λnv, je lim k Anv k = lim | λ| n k v k = ∞ . n→∞ n→∞ To pomeni, da ima za dovolj velik n matrika An vsaj en element, ki je strogo večji kot 1. Po drugi strani pa je lahko preveriti, da je An tudi markovska matrika, ki pa ima po definiciji vse elemente ≤ 1. Protislovje. Izrek 4.1.3. Naj bo ( I − A) x = 0 zaprt model Leontijeva in recimo, da je A ireducibilna matrika. Potem obstaja x > 0 , ki reši dani sistem enačb. Vse smiselne rešitve tega modela so pozitivni večkratniki vektorja x. Dokaz. Po predpostavki je matrika A T markovska matrika. Ker imata A in A T enake lastne vrednosti, iz Trditve 4.1.2 dobimo, da je 1 Perron–Frobeniusova lastna vrednost matrike A, zato iz Perron–Frobeniusovega izreka sledi, da obstaja pozitiven lasten vektor x matrike A za lastno vrednost 1. Drugi del trditve sledi iz Posledice 3.3.6. Oglejmo si še konkreten primer uporabe zaprtega modela Leontijeva: Primer 4.1.4 . Imamo zaprto ekonomijo kmetov, mizarjev in krojačev. Kmetje porabijo 2/5 hrane, 1/3 mizarskih izdelkov in 1/2 oblačil. Mizarji porabijo 2/5 hrane, 1/3 mizarskih izdelkov in 1/2 oblačil. Krojači pri svoji proizvodnji porabijo 1/5 hrane, 1/3 mizarskih izdelkov, ne rabijo pa svojih izdelkov. Zunanje porabe teh treh izdelkov ni. Če označimo panoge po vrsti s števili 1, 2 in 3, je matrika Leontijeva  2 1 1  5 3 2 A = 2 1 1 .  5 3 2  1 1 0 5 3 Vektorji proizvodnje so natanko pozitivni lastni vektorji matrike A za lastno vrednost 1; sistem ( I − A) x = 0 rešimo z Gaussovo eliminacijo:  3 − 1 − 1  1 0 − 15  5 3 2 8 I − A = − 2 2 − 1 ∼ 0 1 − 15 .  5 3 2   8  − 1 − 1 1 0 0 0 5 3 Smiselne rešitve so torej 15 x = t · 15 , t >   0 . 8 Obseg proizvodnje posameznih panog mora biti torej v razmerju 15 : 15 : 8. 4.1.5 Odprti model Leontijeva V nadaljevanju se bomo osredotočili na primer, ko je vektor povpraševanja neničeln: Definicija. Odprti model Leontijeva je sistem enačb ( I − A) x = d, za katerega velja: (a) Matrika A je nenegativna kvadratna matrika. (b) Za vsak j obstaja i, da je aij > 0. (c) d je neničeln nenegativen vektor. 42 (d) A je produktivna matrika, t.j., obstaja vektor y > 0, da je y > Ay. Smiselne rešitve (odprtega, zaprtega) modela Leontijeva so vsi pozitivni vektorji x, ki zado- ščajo sistemu linearnih enačb ( I − A) x = d. Spet si oglejmo smiselnost predpostavk odprtega modela Leontijeva glede na ekonomski problem, ki smo ga opisali zgoraj. Predpostavki (a) in (b) smo utemeljili že zgoraj. Predpostavka (c) je očitno smiselna. Ostane še predpostavka (d), ki v nekem smislu nadomesti predpostavko (c) iz zaprtega modela Leontijeva; intuitivno namreč pomeni, da morajo panoge proizvesti več, kot porabijo, s tem pa ostane nekaj tudi za zunanje odjemalce. Za začetek si oglejmo primer, kaj se zgodi, če produktivnost izpustimo: Primer 4.1.6 . Dana je matrika Leontijeva 1 , 1 1 , 3 A = 0 , 3 0 , 2 in vektor povpraševanja 2 d = . 3 Najprej pokažimo, da A ni produktivna matrika. Če bi bila, bi obstajal pozitiven vektor y, da bi veljalo ( I − A) y > 0. To lahko na dolgo zapišemo kot −0 , 1 −1 , 3 y 1 > 0 , −0 , 3 0 , 8 y 2 kjer sta y 1 , y 2 > 0. To pomeni −0 , 1 y 1 − 1 , 3 y 2 > 0 , −0 , 3 y 1 + 0 , 8 y 2 > 0 , kar je seveda nemogoče. Zato A ni produktivna matrika. Sedaj rešimo sistem ( I − A) x = d, torej −0 , 1 −1 , 3 x 1 2 = . −0 , 3 0 , 8 x 2 3 Ker je 2 × 2 matrika na levi strani obrnljiva, dobimo x −1 1 −0 , 1 −1 , 3 2 1 0 , 8 1 , 3 2 −11 , 70 = = − ≈ , x 2 −0 , 3 0 , 8 3 0 , 47 0 , 3 −0 , 1 3 0 , 64 kar v našem primeru ni smiselna rešitev. Zgornji primer nakazuje, kaj gre narobe, če matrika A ni produktivna. V tem primeru za vsak pozitiven vektor y velja, da je vsaj ena komponenta vektorja ( I − A) y nepozitivna, torej manjša ali enaka 0. Če si ogledamo sistem Leontijeva ( I − A) x = d, pri katerem je d > 0, potem je jasno, da v tem primeru ne bo imel pozitivne rešitve. Ravno to se je zgodilo v Primeru 4.1.6. Naš glavni cilj bo pokazati, da ima odprti model Leontijeva ob zgornjih predpostavkah vedno enolično določeno nenegativno rešitev x. To seveda ni popolnoma zadovoljivo, saj nas zanimajo le strogo pozitivne rešitve sistema ( I − A) x = d. Dokazali bomo, da če je A še ireducibilna matrika, potem ima odprti model Leontijeva vedno enolično določeno strogo pozitivno rešitev. 4.2 Obstoj nenegativne rešitve odprtega modela Leonti- jeva Oglejmo si nekaj lastnosti produktivnih matrik: 43 Lema 4.2.1. Če je A produktivna matrika, elementi matrike Ak konvergirajo proti 0, ko k → ∞ . Dokaz. Naj bo y pozitiven vektor, za katerega velja y > Ay. Očitno je Ay ≥ 0. Zaradi stroge potivnosti obstaja δ ∈ (0 , 1), da velja δy > Ay ≥ 0 . Pomnožimo to neenakost z leve z matriko A; to lahko storimo zaradi Trditve 3.0.2: δAy > A 2 y ≥ 0 . Po drugi strani je tudi δ 2 y > δAy ≥ 0 , zato je δ 2 y > A 2 y ≥ 0 . Podoben sklep z indukcijo pokaže δky > Aky ≥ 0 za vsak k ∈ N. Pošljemo k → ∞. Dobimo lim Aky = 0 , k→∞ kar je krajši zapis za n X lim a( k) y ij j = 0 za vsak i = 1 , 2 , . . . , n, k→∞ j=1 pri čemer je Ak = [ a( k)]. Ker so y ij j > 0, je to možno le, če lim a( k) = 0 za vsaka i, j = 1 , 2 , . . . , n, ij k→∞ s tem pa je dokaz končan. Lema 4.2.2. Če je A produktivna matrika in x ≥ Ax, potem je x ≥ 0 . Dokaz. Iz x ≥ Ax sledi x ≥ Ax ≥ A 2 x. Z indukcijo hitro vidimo, da x ≥ Akx. Pošljemo k → ∞, uporabimo Lemo 4.2.1 in dobimo x ≥ 0. Lema 4.2.3. Če je A produktivna matrika, je matrika I − A obrnljiva. Dokaz. Recimo da to ni res, torej je 1 lastna vrednost matrike A; naj bo x ustrezen lastni vektor. Ker je x = Ax, iz Leme 4.2.2 sledi x ≥ 0. Oglejmo si vektor − x, ki je tudi lasten vektor za A pri lastni vrednosti 1. Isti sklep sedaj pokaže − x ≥ 0. Edina možnost je x = 0, kar pa ne drži. Protislovje. Izrek 4.2.4. Model Leontijeva ima za vsak d ≥ 0 enolično določeno nenegativno rešitev. Dokaz. Po Lemi 4.2.3 je rešitev ena sama in je dana z x = ( I − A)−1 d. Ker je ( I − A) x = d ≥ 0, oziroma x ≥ Ax, Lema 4.2.2 implicira x ≥ 0. Naslednji rezultat nam da uporaben pogoj za preverjanje produktivnosti dane nenegativne matrike: Izrek 4.2.5 (Hawkins–Simonov pogoj). Naj bo A nenegativna matrika. Potem je A produktivna natanko tedaj, ko je I − A obrnljiva matrika in ( I − A)−1 ≥ 0 . 44 Dokaz. Recimo, da je A produktivna. Potem je matrika I − A obrnljiva po Lemi 4.2.3. Definirajmo matrike Bk = I + A + A 2 + · · · + Ak. Potem je ( I − A) Bk = I − Ak+1 . Pošljemo k → ∞ in uporabimo Lemo 4.2.1: lim ( I − A) Bk = I. k→∞ Zato je lim Bk = ( I − A)−1 . k→∞ Ker je A nenegativna matrika, so matrike Bk nenegativne, zato iz zadnje enakosti sledi ( I − A)−1 ≥ 0. Recimo sedaj, da ( I − A)−1 obstaja in je nenegativna matrika. Potem ima sistem 1 1   ( I − A) x =  .   .   .  1 enolično določeno rešitev, ki je po predpostavki nenegativna. Po opombi, ki sledi za Primerom 4.1.6, sledi, da mora biti A produktivna matrika. Primer 4.2.6 . Imejmo odprt model Leontijeva z vhodno–izhodno matriko 1 / 10 1 / 5 3 / 10 A = 0 0 1 / 10   0 0 1 / 5 in vektorjem povpraševanja 1 / 2 d = 2 .   0 Matrika A je po Hawkins–Simonovem pogoju produktivna, saj je 10 / 9 2 / 9 4 / 9 ( I − A)−1 = 0 1 1 / 8 ≥   0 . 0 0 5 / 4 Rešitev je 1 x = ( I − A)−1 d = 2 .   0 Rešitev je res nenegativna, vendar pa ni smiselna, ker pomeni, da proizvajalec 3 ne obratuje. Kot bomo videli v naslednjem razdelku, ta težava ne nastopi, če je vhodno–izhodna matrika ireducibilna. 4.3 Obstoj pozitivne rešitve odprtega modela Leontijeva Izrek 4.3.1. Naj bo A produktivna matrika. Naslednje trditve so ekvivalentne: (a) Odprti model Leontijeva ( I − A) x = d ima enolično določeno pozitivno rešitev za vsak neničeln d ≥ 0 . (b) ( I − A)−1 > 0 . 45 (c) A je ireducibilna matrika. Dokaz. ( a) ⇒ ( b). Ker je A produktivna matrika, ( I − A)−1 obstaja po Lemi 4.2.3. Naj bo d vektor, ki ima i-to komponento enako 1, ostale pa so enake 0. Naj bo x pozitivna rešitev ( I − A) x = d. Potem je x = ( I − A)−1 d ravno i-ti stolpec matrike ( I − A)−1. S tem smo pokazali, da so vsi stolpci matrike ( I − A)−1 pozitivni, zato velja (b). ( b) ⇒ ( a). Enostavno. ( b) ⇐⇒ ( c). Kot v dokazu Izreka 4.2.5 definiramo Bk = I + A + A 2 + · · · + Ak. Potem je lim Bk = ( I − A)−1 . k→∞ Ker je zaporedje matrik Bk po elementih matrik nepadajoče, velja še ( I − A)−1 ≥ Bk za vsak k ∈ N . Naj bo ( I − A)−1 = [ cij] in Ak = [ a( k)]. Najprej opazimo, da c ij ii 6= 0 za vsak i = 1 , 2 , . . . , n. Če je i 6= j, iz zgornje neenakosti sledi cij 6= 0 natanko tedaj, ko obstaja k, da je a( k) 6= 0. Zato je ij ( I − A)−1 > 0 natanko tedaj, ko za vsaka i, j = 1 , 2 , . . . , n obstaja k, da je a( k) 6= 0. Po Izreku ij 3.1.9 to pomeni, da je ( I − A)−1 > 0 natanko tedaj, ko je A ireducibilna matrika. Primer 4.3.2 . Imamo tri dejavnosti, naftno industrijo, električno industrijo in proizvodnjo to- vornjakov. Za eno enoto nafte rabimo 0,5 enote elektrike in 0,6 enote tovornjakov. Za eno enoto elektrike rabimo 0,15 enot nafte in 0,1 enote elektrike. Za eno enoto tovornjakov rabimo 0,35 enot nafte, 0,1 enote elektrike in 0,1 enote tovornjakov. Zunanji trg potrebuje 250.000 enot nafte in 500.000 enot tovornjakov. Koliko enot morajo proizvesti posamezne panoge? Ustrezna matrika Leontijeva je  0 0 , 5 0 , 6 A = 0 , 15 0 , 1 0 ,   0 , 35 0 , 1 0 , 1 vektor povpraševanja pa je 250 . 000 d = 0   . 500 . 000 Po Hawkins-Simonovem pogoju je lahko preveriti, da je matrika A produktivna, saj je 1 , 4876 0 , 9366 0 , 9917 ( I − A)−1 ≈ 0 , 2479 1 , 2672 0 , 1653 .   0 , 6061 0 , 5051 1 , 5152 Rešitev modela Leontijeva je 867 . 769 x = ( I − A)−1 d = 144 . 628 .   909 . 091 Proizvesti moramo torej 867.769 enot nafte, 144.628 enot elektrike in 909.091 enot tovornjakov. Poglavje 5 Pozitivni funkcionali Teorija pozitivnih funkcionalov je del linearne algebre, ki ima pomembne uporabe v ekonomiji, kjer takšni funkcionali nastopajo kot cenovni funkcionali trgov brez arbitraž, poleg tega pa so ključnega pomena pri linearnem programiranju. Tu si bomo ogledali le nekaj osnovnih pojmov in rezultatov. V celotnem poglavju bomo obravnavali vektorski prostor n R , opremljen s standardnim ska- larnim produktom. 5.1 Osnove o linearnih funkcionalih Definicija. Naj bo V vektorski podprostor v n R . Linearen funkcional je linearna preslikava π : V → R. Primer 5.1.1 . Naj bo V ravnina z enačbo x + y + z = 0 v 3 R . Preslikava π : V → R, dana z predpisom π( x, y, − x − y) = 4 x + y, je linearen funkcional. Izberimo bazo prostora V :  1   0  v 1 = 0 1   , v 2 =   . −1 −1 Ker je π( v 1) = 4 in π( v 2) = 1, ima π v tej bazi matriko 4 1 . Izrek 5.1.2 (Rieszov izrek). Naj bo V vektorski podprostor v n R in π : V → R linearen funkci- onal. Potem obstaja enolično določen vektor yπ ∈ V , da je π( x) = h x, yπ i za vsak x ∈ V . Dokaz. Če je { e 1 , e 2 , . . . , em} ortonormirana baza prostora V , vektor yπ = π( e 1) e 1 + π( e 2) e 2 + . . . + π( en) en ustreza pogoju. Če sta y, z ∈ V dva vektorja, ki ustrezata pogoju izreka, je h x, y − z i = 0 za vsak x ∈ V . Od tod hitro sledi y = z, kar nam da enoličnost. Vektorju yπ iz Izreka 5.1.2 pravimo Rieszov vektor linearnega funkcionala π. 46 47 Opomba 5.1.3 . Če je π linearen funkcional na n R , potem ga lahko po Rieszovem izreku zapišemo v obliki π( x 1 , x 2 , . . . , xn) = α 1 x 1 + α 2 x 2 + . . . + αnxn za neke α 1 , α 2 , . . . , αn ∈ R. Če π gledamo kot funkcijo n spremenljivk, je to očitno zvezna funkcija na n R . Primer 5.1.4 . Naj bo π linearen funkcional iz Primera 5.1.1. Ortonormirano bazo prostora V lahko dobimo s pomočjo baze iz omenjenega primera in Gram–Schmidtovega postopka:  1  v 1 1 e 1 = = √ 0 , k   v 1k 2 −1 −1 h v 2 , v 1i h v 2 , v 1i 1 e 2 = v 2 − v / √ v v = 2 . h 1 2 − 1   v 1 , v 1i h v 1 , v 1i 6 −1 Ker je √ π( e 1) = 4 / 2 , √ π( e 2) = −2 / 6 , je Rieszov vektor za π enak  7  1 yπ = π( e 1) e 1 + π( e 2) e 2 = −2 .   3 −5 Naj bo π : V → R linearen funkcional. Iz definicije je jasno, da je dim im π ≤ 1; če je π 6= 0, potem je v resnici dim im π = 1 in zato dim ker π = m − 1, kjer je dim V = m. Če izberemo bazo prostora V , potem lahko linearen funkcional predstavimo z matriko velikosti 1 × m. Naslednji rezultat pove, da se linearna funkcionala na prostoru V , ki imata enaki jedri, skoraj ujemata: Lema 5.1.5. Naj bosta π in ψ linearna funkcionala na podprostoru V . Če je ker π = ker ψ, potem obstaja λ ∈ R , da je π = λψ. Dokaz. Brez škode za splošnost lahko predpostavimo, da sta π in ψ neničelna funkcionala. Označimo dim V = m in K = ker π = ker ψ. Potem je dim K = m − 1. Dopolnimo bazo podprostora K do baze prostora V : V = K ⊕ Lin{ v} . Označimo π( v) = µ 1 in ψ( v) = µ 2. Po konstrukciji sta µ 1 , µ 2 ∈ R \ {0}. Izberimo x ∈ V ; zapišemo ga lahko na enoličen način kot x = k + µv, k ∈ K, µ ∈ R . Potem je π( x) = π( k + µv) = π( k) + µπ( v) = µµ 1. Podobno je ψ( x) = µµ 2, torej je µ 1 π( x) = ψ( x) . µ 2 Ker to velja za vsak x ∈ V , je trditev dokazana. Definicija. Naj bo V vektorski podprostor v n R in π : V → R. Linearen funkcional ˜ π : n R → R je razširitev linearnega funkcionala π, če velja ˜ π( v) = π( v) za vsak v ∈ V . 48 Očiten način, kako lahko linearen funkcional π : V → n R razširimo na celoten R , je naslednji. Izberemo bazo { v n 1 , v 2 , . . . , vm} podprostora V in jo dopolnemo do baze celega R : B = { v 1 , v 2 , . . . , vm, um+1 , . . . , un} . Razširitev ˜ π : n R → R sedaj definiramo tako, da predpišemo, kam se preslikajo bazni vektorji: ˜ π( v 1) = π( v 1) , ˜ π( v 2) = π( v 2) , ... ˜ π( vm) = π( vm) , ˜ π( um+1) = αm+1 ... ˜ π( un) = αn, Kjer so αm+1 , . . . , αn poljubna realna števila. V naslednji lemi pokažemo, da obstaja povezava med razširitvami funkcionala π in elementi (ker π)⊥: Lema 5.1.6. Naj bo ˜ π : n R → R razširitev linearnega funkcionala π. Naj bo z Rieszov vektor funkcionala ˜ π. Potem je z ∈ (ker π)⊥ . Obratno, naj bo z ∈ (ker π)⊥ poljuben vektor. Definirajmo ˜ ψ : n R → R , ˜ ψ( x) = h x, z i . Potem obstaja enolično določen λ ∈ R , da je λ ˜ ψ razširitev linearnega funkcionala π. Dokaz. Izberimo poljuben u ∈ ker π. Potem je h u, z i = π( u) = 0 , torej je z ∈ (ker π)⊥. Dokažimo še drugi del. Brez škode je z 6= 0. naj bo ψ zožitev linearnega funkcionala ˜ ψ na podprostor V . Trdimo, da je ker π = ker ψ; od tod bo rezultat sledil s pomočjo Leme 5.1.5. Če vzamemo x ∈ ker π, je ψ( x) = ˜ ψ( x) = h x, z i = 0, torej je x ∈ ker ψ. Obratno, če je x ∈ ker ψ, je h x, z i = 0. Zapišimo V = ker π ⊕ (ker π)⊥ = ker π ⊕ Lin{ z} . Vektor x torej lahko napišemo kot x = k + αz, kjer je α ∈ R in k ∈ ker π. Potem je 0 = h x, z i = h k, z i + α h z, z i = α k z k2 . Ker je z 6= 0, sledi α = 0, torej x = k ∈ ker π. S tem je dokaz končan. Primer 5.1.7 . Oglejmo si linearen funkcional iz Zgleda 5.1.1. Naj bo torej V ravnina z enačbo x + y + z = 0 v 3 R , funkcional π : V → R pa je definiran z predpisom π( x, y, − x − y) = 4 x + y. Očitno je ker π presek ravnin x + y + z = 0 in 4 x + y = 0, kar je ravno premica skozi izhodišče in s smernim vektorjem  1  s = −4   . 3 49 Zato je ker π = Lin{ s}, torej je (ker π)⊥ ravnina z enačbo x − 4 y + 3 z = 0. Izberimo vektor iz (ker π)⊥: −2 v = 1 .   2 Kot v dokazu Leme 5.1.6 definiramo ˜ ψ : n R → R s predpisom ˜ ψ( u) = h u, v i , kar lahko prepišemo na dolgo kot ˜ ψ( x, y, z) = −2 x + y + 2 z. Poiskati moramo λ ∈ R, da se bo λ ˜ ψ na V ujemal z π: λ ˜ ψ( x, y, − x − y) = λ(−4 x − y) , torej je λ = −1; funkcional − ˜ ψ je ustrezna razširitev funkcionala π na cel 3 R . 5.2 Konveksne množice in stožci V tem razdelku si bomo ogledali še nekaj stvari, ki jih rabimo v nadaljevanju, ko bomo vpeljali pojem pozitivnega linearnega funkcionala. Vektorski prostor n R ima standardno bazo, ki jo sestavljajo nenegativni vektorji. Prav lahko je najti bazo za n R , sestavljeno iz samih pozitivnih vektorjev. Po drugi strani obstajajo podprostori v n R , za katere ne moremo najti baze, katere elementi bi bili pozitivni vektorji; primer takšnega podprostora je V = {( x 1 , x 2 , . . . , xn) | x 1 = 0} . Izkaže pa se, da če podprostor vsebuje vsaj en pozitiven vektor, potem lahko zanj najdemo bazo, sestavljeno iz samih pozitivnih vektorjev. To bomo dokazali, še prej pa rabimo pomožno trditev: Lema 5.2.1. Naj bo V vektorski podprostor v n R . Potem je množica vseh pozitivnih vektorjev v V odprta v n R . Dokaz. Naj bo M množica vseh pozitivnih vektorjev v V . Izberimo  a  1 a  2  a =  .  ∈ M.  .   .  an Ker je a > 0, obstaja > 0, da je a n i > za vsak i. Naj bo K ( a, ) odprta krogla v R s središčem v a in polmerom . Vzemimo sedaj  x  1 x  2  x =  .  ∈ K( a, ) .  .   .  xn Potem je ai − xi ≤ | ai − xi| ≤ p( a 1 − x 1)2 + ( a 2 − x 2)2 + · · · + ( xn − an)2 = k a − x k < , torej xi > ai − > 0. Zato je x ∈ M , torej K( a, ) ⊆ M . Izrek 5.2.2. Naj bo V m-dimenzionalen podprostor v n R . Če obstaja pozitiven vektor v podpro- storu V , potem lahko za V izberemo bazo, sestavljeno iz samih pozitivnih vektorjev. 50 Dokaz. Naj bo v 1 pozitiven vektor v V . Dopolnimo ga do baze prostora V : B = { v 1 , v 2 , . . . , vm} . Za λ ∈ [0 , 1) in j ∈ {1 , 2 , . . . , m} definirajmo vj( λ) = λv 1 + (1 − λ) vj. Direktno lahko preverimo, da je B λ = { v 1 , v 2( λ) , . . . , vm( λ)} tudi baza prostora V , natančen dokaz prepuščamo bralcu. Če sedaj pošljemo λ → 1, vsi vektorji v n j ( λ) konvergirajo proti v 1. Po Lemi 5.2.1 obstaja odprta krogla v R s središčem v 1, katere vsi elementi so pozitivni vektorji. Ko je λ blizu 1, vsi vektorji zj( λ) padejo v to kroglo in so zato pozitivni. Definicija. Podmnožica K v n R je konveksna, če za vsaka x, y ∈ K in vsak λ ∈ [0 , 1] velja tudi λx + (1 − λ) y ∈ K. Primer 5.2.3 . Po definiciji je množica K konveksna natanko tedaj, ko za vsak par točk iz K cela daljica med tema točkama leži v K. Na Sliki 5.1 je na levi primer konveksne, na desni pa nekonveksne podmnožice v ravnini. Slika 5.1: Primera konveksne in nekonveksne množice Lema 5.2.4. Presek poljubne družine konveksnih množic v n R je tudi konveksna množica. Dokaz. Naj bo { Ki | i ∈ I} družina konveksnih množic in K njihov presek. Izberimo x, y ∈ K in λ ∈ [0 , 1]. Ker je za vsak i ∈ I množica Ki konveksna in velja x, y ∈ Ki, je tudi λx+(1− λ) y ∈ Ki za vsak i ∈ I. To pomeni, da je λx + (1 − λ) y ∈ K, kar smo hoteli dokazati. Definicija. Podmnožica K množice n R je stožec, če za vsak x ∈ K velja { λx | λ ≥ 0} ⊆ K. 51 Slika 5.2: Presek dveh konveksnih množic. Primer 5.2.5 . Množica C = {( x, y) ∈ 2 R | x ≥ 0 , x ≤ y ≤ 2 x} je stožec v 2 R (gl. tudi Sliko 5.3). Če namreč vzamemo x v = ∈ C, y in λ ≥ 0, je tudi λx ≥ 0 in λx ≤ λy ≤ 2 λx, zato je λv ∈ C. Slika 5.3: Primer stožca v 2 R . 4 . 3 . 2 . 1 . −1 . 1 . 2 . 3 . 4 . 0 −1 . Postavimo sedaj n n R = { x ∈ | x ≥ 0} . + R Očitno je 1 2 R = [0 , ∞), medtem, ko je ravno prvi kvadrant v koordinatni ravnini. + R+ Lema 5.2.6. Množica n R je zaprta, konveksna in je stožec. + Dokaz. Po definiciji hitro preverimo, da je n R konveksna množica in stožec. Dokažimo še, da + je n n n R zaprta podmnožica v . Vzemimo zaporedje vektorjev y , ki konvergirajo proti + R i ∈ R+ vektorju x. Potem j-te komponente yi,j vektorjev yi konvergirajo k j-ti komponenti xj vektorja x. Ker so y n i,j ≥ 0, je tudi xj ≥ 0, za vsak j, to pa pomeni, da je x ∈ R . + 52 Množico n n R imenujemo pozitiven stožec v . Na koncu tega razdelka le še vpeljimo oznako. + R Za poljubno podmnožico M v n R naj bo M n + = M ∩ R+ množica vseh nenegativnih vektorjev v M . 5.3 Pozitivni funkcionali Definicija. Naj bo π : V → R linearen funkcional. Pravimo, da je π pozitiven, če za vsak nenegativen neničeln vektor x ∈ V velja π( x) > 0. Podobno je π nenegativen linearen funkcional, če je π( x) ≥ 0 za vsak nenegativen vektor x ∈ V . Primer 5.3.1 . Na j bo V ravnina x + y − z = 0 v 3 R . Definiramo π 1 : V → R s predpisom π 1( x, y, x + y) = x + y. Vektor  x  v = y ∈ V   x + y je nengativen natanko tedaj, ko je x ≥ 0 in y ≥ 0. Če je v neničeln in nenegativen, potem je π 1( v) > 0, torej je π 1 pozitiven linearen funkcional. Če pa definiramo π 2 : V → R s predpisom π 2( x, y, x + y) = x, dobimo nenegativen funkcional na V , ki ni pozitiven; velja namreč π 2(0 , 1 , 1) = 0. Lema 5.3.2. Naj bo π : n R → R linearen funkcional in e 1 , e 2 , . . . , en standardna baza prostora n R . Potem je π pozitiven (nenegativen) linearen funkcional natanko tedaj, ko je π( ei) > 0 (π( ei) ≥ 0 ) za vse i = 1 , 2 , . . . , n. Dokaz. Če je π pozitiven (nenegativen) funkcional, očitno velja π( ei) > 0 ( π( ei) ≥ 0) za vse i = 1 , 2 , . . . , n. Obratno, če je π( ei) > 0 in v = α 1 e 1 + α 2 e 2 + · · · + αnen neničeln nenegativen vektor, potem je π( v) = α 1 π( e 1) + α 2 π( e 2) + · · · + αnπ( en) strogo pozitivno število, saj je vsaj eden od αi strogo pozitiven. π je torej pozitiven funkcional. Dokaz za nenegativne funkcionale je podoben. Trditev 5.3.3. Naj bo π : n n R → R linearen funkcional in y ∈ R pripadajoči Rieszov vektor. Potem je π pozitiven (nenegativen) natanko tedaj, ko je y > 0 (y ≥ 0 ). Dokaz. Ker je y = π( e 1) e 1 + π( e 2) e 2 + · · · + π( en) en, trditev neposredno sledi iz Leme 5.3.2. 5.4 Separacijski izreki Definicija. Naj bo π : n n R → R linearen funkcional in y ∈ R pripadajoči Rieszov vektor. Za b ∈ R definiramo H n π ( b) = { x ∈ R | π( x) = h x, y i = b} , H+( b) = { x ∈ n | π( x) = h x, y i ≥ b} , π R H−( b) = { x ∈ n | π( x) = h x, y i ≤ b} . π R Lema 5.4.1. Naj bo π : n n R → R linearen funkcional in b ∈ R . Naj bo xb ∈ R vektor, za katerega velja π( xb) = b. 53 (a) Hπ(0) = ker π, (b) Hπ( b) = xb + Hπ(0) , (c) H+( b) = x (0) , π b + H + π (d) H−( b) = x (0) . π b + H − π Dokaz. Točka (a) sledi neposredno iz definicije. Dokažimo še točko (b), medtem, ko dokaza (c) in (d) izpustimo, saj sta podobna. Izberimo x ∈ Hπ( b). To pomeni, da je π( x) = b. Zato je x− xb ∈ ker π = Hπ(0). S tem smo dokazali, da je x ∈ xb+ Hπ(0). Obratno naj bo x ∈ xb+ Hπ(0). Potem lahko pišemo x = xb + x 0, kjer je x 0 ∈ ker π. Zato je π( x) = π( xb) + π( x 0) = b, torej je x ∈ Hπ( b). Če je π neničeln linearen funkcional, potem je Hπ(0) = ker π podprostor dimenzije n − 1 v n R ; takim podprostorom pravimo hiperravnine. V splošnem je po Lemi 5.4.1 množica Hπ( b) premaknjena hiperravnina. Takšnim množicam pravimo afine hiperravnine. Zaradi enostavnosti bo pojem hiperravnina predstavljal afino hiperravnino. Množici H+( b) pravimo pozitivni π polprostor, množici H−( b) pa negativni polprostor, ki pripada π in b. π Primer 5.4.2 . Oglejmo si funkcional π : 2 R → R, definiran z π( x, y) = x − 2 y. Potem je Hπ(3) premica z enačbo x − 2 y = 3, Hπ(3)+ je polravnina nad to premico, Hπ(3)− pa polravnina pod premico. Definicija. Naj bosta A in B podmnožici v n n R in π linearen funkcional na R . Pravimo, da hiperravnina Hπ( b) separira množici A in B, če velja bodisi π( x) ≥ b ≥ π( y) za vsaka x ∈ A, y ∈ B bodisi π( x) ≤ b ≤ π( y) za vsaka x ∈ A, y ∈ B. Če v zgornjem pogoju neenačaje zamenjamo s strogimi neenačaji, pravimo, da Hπ( b) striktno separira množici A in B. Poleg tega pravimo, da funkcional π (striktno) separira množici A in B, če obstaja b ∈ R, da Hπ( b) (striktno) separira A in B. Slika 5.4: Premica p striktno separira množici A in B. A B p Lema 5.4.3. Naj bosta A in B podmnožici v n R . (i) Če sta A in B konveksni množici, je tudi množica A + B konveksna. 54 (ii) Če je A kompaktna in B zaprta, je množica A + B zaprta. Dokaz. (a) Vzemimo x, y ∈ A + B in izberimo λ ∈ [0 , 1]. Pišemo lahko x = a 1 + b 1 in y = a 2 + b 2, kjer a 1 , a 2 ∈ A in b 1 , b 2 ∈ B. Ker sta A in B konveksni, je λa 1 + (1 − λ) a 2 ∈ A in λb 1 + (1 − λ) b 2 ∈ B. Zato je λx + (1 − λ) y = λa 1 + (1 − λ) a 2 + λb 1 + (1 − λ) b 2 ∈ A + B. (b) Naj zaporedje vektorjev ck = ak + bk ∈ A + B, kjer ak ∈ A in bk ∈ B, konvergira proti nekemu vektorju x. Ker je množica A kompaktna, obstaja podzaporedje ak , ki konvergira k n nekemu a ∈ A. Potem je lim bk = lim ( ck − ak ) = x − a. n→∞ n n→∞ n n Ker je množica B zaprta, je x − a ∈ B, zato je x = a + ( x − a) ∈ A + B. Lema 5.4.4. Množice H n π ( b) , H +( b) in H −( b) so konveksne zaprte podmnožice v . π π R Dokaz. Dokažimo trditev za Hπ( b)+; dokaz za Hπ( b)− je podoben, trditev za Hπ( b) pa sledi iz očitne zveze H+( b) ∩ H−( b) = H π π π ( b) in Leme 5.2.4. Izberimo x, y ∈ Hπ( b)+ in λ ∈ [0 , 1]. Potem je π( λx + (1 − λ) y) = λπ( x) + (1 − λ) π( y) ≥ b, torej je λx + (1 − λ) y ∈ H n π ( b)+. Preostane še dokaz, da je Hπ( b)+ zaprta v R . Izberimo zaporedje vektorjev x n j v Hπ ( b)+, ki konvergirajo k x ∈ R . Potem velja π( xj ) ≥ b, ker pa je funkcija π zvezna na n R , π( xj ) → π( x), zato je tudi π( x) ≥ b. To pomeni, da je x ∈ Hπ( b)+. Naslednji izrek bo osnova za dokaze rezultatov o separaciji: Izrek 5.4.5. Naj bo C zaprta konveksna podmnožica v n R , ki ne vsebuje 0. Potem obstaja x 0 ∈ C, da velja h x 0 , x i ≥ k x 0k2 za vsak x ∈ C. Dokaz. Naj bo > 0 takšen, da je C = { x ∈ C | k x k ≤ } 6= ∅ . Množica C je omejena in zaprta, zato je kompaktna. Poleg tega je tudi konveksna. Če namreč vzamemo x, y ∈ C in λ ∈ [0 , 1], potem je po trikotniški neenakosti k λx + (1 − λ) y k ≤ λ k x k + (1 − λ)k y k ≤ λ + (1 − λ) = . Ker je funkcija x 7→ k x k zvezna, zavzame minimum na C, torej obstaja x 0 ∈ C, da velja k x k ≥ k x 0k za vsak x ∈ C. Po definiciji množice C slednja neenakost velja za vsak x ∈ C. Če je λ ∈ [0 , 1), je zaradi konveksnosti λx + (1 − λ) x 0 ∈ C, zato je k x 0k2 ≤ k x 0 + λ( x − x 0)k2 = k x 0k2 + 2 λ h x 0 , x − x 0i + λ 2k x − x 0k2 . Po preureditvi dobimo 0 ≤ 2h x 0 , x − x 0i + λ k x − x 0k2 . Pošljemo λ → 0: 0 ≤ 2h x 0 , x − x 0i = h x, x 0i − k x 0k2 . Od tod sledi rezultat. Kot posledico navedimo prvi separacijski rezultat: Posledica 5.4.6. Naj bo C zaprta konveksna podmnožica v n R , ki ne vsebuje 0. Potem obstajata linearen funkcional π : n R → R in b ∈ R , da hiperravnina Hπ( b) striktno separira 0 in C. 55 Dokaz. Definiramo π( x) = h x, x 0i, kjer je x 0 vektor, ki ga dobimo iz Izreka 5.4.5. Če postavimo b = k x 0k2 / 2, potem Hπ( b) striktno separira množici {0} in C. p Primer 5.4.7 . Naj bo C = {( x, y) ∈ 2 R | ( x − 2)2 + y 2 ≤ 1} krog v ravnini, ki ima polmer 1 in središče v (2 , 0). Množica C je zaprta in konveksna ter ne vsebuje 0. Premica y = 4 x − 2 separira 0 in C (Slika 5.5). Slika 5.5: Premica separira 0 in konveksno množico. 2 . 1 . 0 −2 . −1 . 1 . 2 . 3 . 0 −1 . −2 . −3 . Naslednji separacijski izrek pove, da za dani podprostor V v n R in konveksno množico C, ki ne seka V , vedno lahko najdemo linearen funkcional, katerega jedro vsebuje V in ki separira n R tako, da eden od polprostorov vsebuje celo množico C. Še prej nekoliko priredimo Izrek 5.4.5 za konkretno situacijo: Izrek 5.4.8. Naj bo C kompaktna konveksna podmnožica v n n R in V vektorski podprostor v R , za katerega velja C ∩ V = ∅ . Potem obstaja x 0 ∈ C, da velja h x 0 , x i ≥ k x 0k2 za vsak x ∈ C in h x 0 , v i = 0 za vsak v ∈ V . Dokaz. Naj bo A = C + V . Po Lemi 5.4.3 je množica A zaprta in konveksna, očitno ne vsebuje 0. Po Izreku 5.4.5 obstaja x 0 ∈ A, da je h x 0 , x i ≥ k x 0k2 za vse x ∈ A. Ker je C ⊆ A, smo s tem dokazali prvi del trditve. Po definiciji množice A velja k x 0k2 ≤ h x + αy, x 0i za vse x ∈ C, y ∈ V in α ∈ R. To je ekvivalentno k x 0k2 − α h y, x 0i ≤ h x, x 0i . Če fiksiramo x in y, je desna stran neenakosti konstantna, leva pa linearna funkcija parametra α. Zato je to možno le, če je h y, x 0i = 0 za vse y ∈ V . 56 Posledica 5.4.9. Naj bo C kompaktna konveksna podmnožica v n R , ki ne seka vektorskega podprostora V . Potem obstajata linearen funkcional π : n R → R in b ∈ R , da je V ⊆ ker π in hiperravnina Hπ( b) striktno separira V in C. Dokaz. Dokaz je povsem enak kot dokaz Posledice 5.4.6, le da tu uporabimo Izrek 5.4.8. Primer 5.4.10 . Naj bo V premica x − y = 0 v 2 R in C krog s središčem v (3 , 0) in polmerom 1. Če definiramo linearen funkcional π( x, y) = x − y, potem je očitno V = ker π, hiperravnina p = Hπ(1), ki je premica z enačbo x− y = 1, pa separira V in C; gl. Sliko 5.6. Slika 5.6: Premica separira konveksno množico in vektorski podprostor v 2 R . 3 . 2 . C 1 . −2 . −1 . 1 . 2 . 3 . 4 . 0 −1 . V p −2 . Posledica 5.4.11. Naj bo V vektorski podprostor v n n R in naj bo y ∈ R \ V . Potem obstajata linearen funkcional π : n R → R , da velja π( y) = 1 in π( x) = 0 za vse x ∈ V . Dokaz. Postavimo C = { y} in uporabimo Izrek 5.4.8. Obstaja torej x n 0 ∈ R , da je h x 0 , y i ≥ k x 0k2 > 0 in h x 0 , x i = 0 za vse x ∈ V . Definirajmo h x 0 , x i π( x) = . h x 0 , y i π je iskani linearen funkcional. 5.5 Farkasova lema Ena od uporab separacijskih izrekov je Farkasova lema, ki govori o obstoju nenegativnih rešitev sistema enačb Ax = b, kjer je A ∈ m× n m R in b ∈ R . Definirajmo K m A = { Ax | x ∈ R } . + Množica KA je torej množica tistih vektorjev b, za katero ima dani sistem kakšno nenegativno rešitev. V naslednji lemi bomo pokazali, da je ta množica zaprta in konveksna: 57 Lema 5.5.1. Naj bodo a m 1 , a 2 , . . . , an neničelni vektorji v R . Potem je množica ( n ) X K = λiai | λi ≥ 0 i=1 zaprt konveksen stožec v m R . Dokaz. Hitro se vidi, da je K konveksen stožec, dokaz prepustimo bralcu. Dokažimo, da je množica K zaprta. Najprej predpostavimo, da so vektorji a 1 , a 2 , . . . , an linearno neodvisni. Označimo Vj = Lin{ a 1 , a 2 , . . . , aj−1 , aj+1 , aj+2 , . . . , an} . Ker aj / ∈ Vj, po Posledici 5.4.9 obstaja linearen funkcional πj, da je πj( aj) 6= 0 in πj( y) = 0 za vse y ∈ Vj. Sedaj vzemimo zaporedje vektorjev yk = αk, 1 a 1 + αk, 2 a 2 + · · · + ak,nan v K m A, ki konvergira proti nekemu vektorju y ∈ R . Hitro opazimo, da je αk,i = πi( yk), zato je yk = π 1( yk) a 1 + π 2( yk) a 2 + · · · + πn( yk) an. Ker so funkcionali πi zvezne funkcije, sledi, da πi( yk) → πi( y), zato je y = lim yk = π 1( y) a 1 + π 2( y) a 2 + · · · + πn( y) an ∈ KA k→∞ . V primeru, da so vektorji a 1 , a 2 . . . , an linearno odvisni, je n X αjaj = 0 j=1 za neke αj ∈ R, ki niso vsi enaki 0. Izberimo x ∈ K in ga zapišimo v obliki n X x = λjaj, j=1 kjer so λj ≥ 0. Naj bo j 0 takšen indeks, da je λj /α minimalen med vsemi števili λ 0 j 0 j /αj , za katere je αj > 0. Potem je n n n X X λj X X λj x = λ 0 0 j aj = λjaj − αjaj = λj − αj aj. αj αj j=1 j=1 0 j=1 j 6= j 0 0 Označimo µj = λj − λj 0 α α j . Če je αj = 0, je µj = λj ≥ 0. Če je αj < 0, je očitno µj ≥ 0, če j 0 pa je αj > 0, je µj ≥ 0 po definiciji indeksa j 0. S tem smo pokazali, da lahko v primeru, ko so vektorji a 1 , a 2 , . . . , an linearno odvisni, izpustimo vsaj enega izmed njih iz definicije K. Če ta postopek zaporedoma ponovimo, lahko situacijo prevedemo na primer, ko so vektorji linearno neodvisni, za tega pa smo trditev že dokazali. Posledica 5.5.2. Množica K m A je zaprt konveksen stožec v R . Dokaz. To sledi direktno iz dejstva, da je ( n ) X KA = λiAei | λi ≥ 0 , i=1 kjer je e n 1 , e 2 , . . . , en standardna baza prostora R , in Leme 5.5.1. 58 Primer 5.5.3 . Naj bo 1 1 A = . 1 2 Potem je x + y KA = | x ≥ 0 , y ≥ 0 . x + 2 y Naj bo C stožec iz Primera 5.2.5. Trdimo, da je KA = C. Če vzamemo x ∈ C, y potem je 2 x − y ≥ 0 in y − x ≥ 0. Zato je 2 x − y x 2 x − y ∈ 2 in = A ∈ K y − x R+ y y − x A. Obratno, za vektor x + y ∈ K x + 2 y A veljajo omejitve 0 ≤ x + y ≤ x + 2 y ≤ 2( x + y), torej pripada stožcu C. Izrek 5.5.4. Naj bo K zaprt konveksen stožec v m m R . Potem b ∈ R pripada K natanko tedaj, ko za vsak y ∈ K, za katerega velja h x, y i ≥ 0 za vsak x ∈ K, velja tudi h b, y i ≥ 0 . Dokaz. „Če” del izreka je očiten. Za dokaz v nasprotno smer predpostavimo, da b / ∈ K. Defini- rajmo Kb = K + {− b} . Po Lemi 5.4.3 je množica Kb zaprta in konveksna. Ker b ne pripada K, sledi 0 / ∈ K. Po Izreku 5.4.5 obstaja vektor x 0 ∈ Kb, da je h x, x 0i ≥ k x 0k2 > 0 za vse x ∈ Kb. To pomeni, da za vse x ∈ K velja h x − b, x 0i > 0, oziroma h x, x 0i > h b, x 0i. Če izberemo x = 0, dobimo h b, x 0i < 0. Po drugi strani, če je x ∈ K in λ > 0, je tudi λx ∈ K, zato po zgornjem premisleku velja λ h x, x 0i > h b, x 0i, oziroma h b, x h 0i x, x 0i > . λ Pošljemo λ → ∞ in dobimo h x, x 0i ≥ 0. Če povzamemo, če x / ∈ K, potem obstaja takšen vektor y = x 0 ∈ K, da je h x, y i ≥ 0 za vsak x ∈ K in h b, y i < 0. S tem je dokaz končan. Izrek 5.5.4 ima naslednjo geometrijsko interpretacijo. Izberimo y ∈ m R in naj bo π( x) = h x, y i pripadajoči linearen funkcional na m R . Spomnimo se, da h x, y i ≥ 0 pomeni, da je x vsebovan v pozitivnem polprostoru H+(0). Zato izrek pravi, da b ∈ K natanko tedaj, ko je b π vsebovan v vsakem polprostoru, ki vsebuje K. Velja torej: Posledica 5.5.5. Zaprt konveksen stožec je enak preseku vseh polprostorov, ki ga vsebujejo. Naslednji izrek je znan kot Farkasova lema: Izrek 5.5.6. Dan je sistem enačb Ax = b, kjer je A ∈ m× n m R in b ∈ R . Ta sistem ima nenegativno rešitev natanko tedaj ko velja: za vsak y ∈ m R , za katerega je h Ax, y i ≥ 0 za vsak x ∈ m R , + velja tudi h b, y i ≥ 0 . Dokaz. Sistem Ax = b ima nenegativno rešitev natanko tedaj, ko je b ∈ KA. Po Posledici 5.5.2 je KA zaprt konveksen stožec. Po Izreku 5.5.4 je b ∈ KA natanko tedaj, ko velja pogoj iz izreka. 59 5.6 Razširitve pozitivnih linearnih funkcionalov Naj bo V m-dimenzionalen vektorski podprostor v n R in π : V → R pozitiven linearen funk- cional. V tem razdelku si bomo ogledali, kdaj lahko najdemo razširitve π, ki so tudi pozitivni linearni funkcionali. Izrek 5.6.1. Obstaja (pozitivna) nenegativna razširitev (pozitivnega) nenegativnega linearnega funkcionala π natanko tedaj, ko podprostor (ker π)⊥ vsebuje (pozitiven) nenegativen neničeln vektor. Dokaz. Naj bo ˜ π pozitivna (nenegativna) razširitev funkcionala π na cel n R . Po Trditvi 5.3.3 je pripadajoči Rieszov vektor y pozitiven (nenegativen) in neničeln. Če vzamemo x ∈ ker π, je h x, y i = ˜ π( x) = π( x) = 0, torej je y ∈ (ker π)⊥. Obratno, naj bo y pozitiven (nenegativen) neničeln vektor v (ker π)⊥. Po Lemi 5.1.6 obstaja λ ∈ n R, da je preslikava ˜ π : R → R, definirana z ˜ π( x) = λ h x, y i , razširitev pozitivnega (nenegativnega) funkcionala π. Očitno mora veljati λ > 0, zato je ˜ π pozitiven (nenegativen) linearen funkcional po Trditvi 5.3.3. Sedaj se bomo omejili na pozitivne funkcionale. Izrek 5.6.1 pravi, da obstaja pozitivna razšritev takšnega funkcionala natanko tedaj, ko (ker π)⊥ vsebuje pozitiven vektor. Da se to vedno zgodi, bo sledilo iz naslednjega rezultata: Trditev 5.6.2. Naj bo U pravi vektorski podprostor v n R , za katerega velja U ∩ n R = {0} . + Potem obstaja baza za U ⊥ , sestavljena iz samih pozitivnih vektorjev. Dokaz. Naj bo C najmanjša konveksna podmnožica v n R , ki vsebuje vse bazne vektorje (v primeru n = 2 je to del premice x + y = 1 v prvem kvadrantu, v primeru n = 3 je C del ravnine x + y + z = 1 v prvem oktantu itd.). Množica C je konveksna in kompaktna ter ne vsebuje 0. Ker je C ⊆ n R , je C ∩ U = ∅. Po Izreku 5.4.8 obstaja x + 0 ∈ C , da velja h x, x 0i ≥ k x 0k2 za vsak x ∈ C in h x 0 , u i = 0 za vsak u ∈ U . Če je x 0 ,i i-ta komponenta vektorja x 0, je x 0 ,i = h x 0 , ei i ≥ k x 0k2 > 0 , torej je x 0 pozitiven vektor. Poleg tega je x 0 ∈ U ⊥. Rezultat sedaj sledi iz Izreka 5.2.2. Končajmo z glavnim rezultatom tega poglavja: Posledica 5.6.3. Naj bo V vektorski podprostor v n R in π : V → R pozitiven linearen funkcional. Potem lahko π vedno razširimo do pozitivnega linearnega funkcionala na n R . Če je V pravi podprostor, je takšnih razširitev neskončno mnogo. Dokaz. Po predpostavki je ker π ∩ n R = {0} . + Zato po Trditvi 5.6.2 obstaja baza za (ker π)⊥, sestavljena iz samih pozitivnih vektorjev. Po Izreku 5.6.1 vsak od teh baznih vektorjev porodi pozitivno razširitev funkcionala π. Naj bo V pravi podprostor dimenzije m. Potem ima (ker π)⊥ dimenzijo n − ( m − 1) ≥ 2. Torej ima π vsaj dve različni pozitivni razširitvi ˜ π 1 in ˜ π 2. Če je λ ∈ [0 , 1], je lahko preveriti, da je tudi λ˜ π 1 + (1 − λ)˜ π 2 pozitivna razširitev funkcionala π (z drugimi besedami, množica vseh pozitivnih razširitev π je konveksna). Takšnih razširitev je torej neskončno mnogo. 60 Primer 5.6.4 . Naj bo V ravnina z enačbo x − y = 0 v 3 R . Definirajmo linearen funkcional π : V → R s predpisom π( x, x, z) = x + z. Očitno je π pozitiven linearen funkcional na V . Jedro π je premica s smernim vektorjem (1 , 1 , −1), ortogonalni komplement jedra pa je ravnina z enačbo x + y − z = 0. Pozitivna baza tega prostora je npr 1 1   (ker π)⊥ = Lin 2 , 1 .      3 2  Oglejmo si npr razširitev, ki jo porodi vektor b = (1 , 2 , 3). Definiramo ψ : 3 R → R s predpisom ψ( v) = h v, b i, kar lahko na dolgo napišemo kot ψ( x, y, z) = x + 2 y + 3 z. Določiti moramo še λ ∈ R, da se bo λψ na V ujemal s π: λψ( x, x, z) = λ(3 x + 3 z) . Od tod sledi λ = 1 / 3; pozitivna razširitev funkcionala π, porojena z vektorjem b, je 1 ˜ π( x, y, z) = ( x + 2 y + 3 z) . 3 Document Outline Moore–Penroseov inverz matrike Psevdoinverz matrike Sistemi linearnih enacb Metoda najmanjših kvadratov Jordanova kanonicna forma Izrek o spektralnem razcepu Jordanova kanonicna forma matrike Funkcije matrik Nenegativne matrike Ireducibilne matrike Collatz–Wielandtova funkcija Najvecja lastna vrednost nenegativne matrike Linearen model proizvodnje Model Leontijeva Zaprti model Leontijeva Odprti model Leontijeva Obstoj nenegativne rešitve odprtega modela Leontijeva Obstoj pozitivne rešitve odprtega modela Leontijeva Pozitivni funkcionali Osnove o linearnih funkcionalih Konveksne množice in stožci Pozitivni funkcionali Separacijski izreki Farkasova lema Razširitve pozitivnih linearnih funkcionalov