Perronin ja Frobeniuksen lause

Abstract

Tässä tutkielmassa perehdytään matriisiteoriaan. Tarkastelu keskittyy neliömatriiseihin, niiden ominaisarvoihin ja niitä vastaaviin ominaisvektoreihin. Tarkastelu rajataan kahteen osaan, joista toiseen esitetään käytännönsovellus, jossa tarkastellaan Googlen hakukoneen toiminnan matemaattista taustaa.

Vaadittavien lineaarialgebran esitietojen jälkeen tarkastellaan positiivisia neliömatriiseja. Ensin esitellään aputuloksia liittyen positiivisiin matriiseihin, sekä niiden itseisarvoltaan suurimpaan ominaisarvoon eli spektraalisäteeseen ja tätä ominaisarvoa vastaavaan ominaisvektoriin. Näiden aputulosten tarkastelun jälkeen esitellään Perronin lause ja sille esitetään todistus. Perronin lause toteaa, että positiivisella neliömatriisilla on itseisarvoltaan suurin ominaisarvo, joka on aidosti suurempi kuin mikään muu matriisin ominaisarvojen itseisarvoista. Lisäksi lause toteaa, että tämän itseisarvoltaan suurimman ominaisarvon algebrallinen kertaluku on 1 ja sitä vastaava ominaisvektori on positiivinen.

Perronin lauseen todistuksen jälkeen perehdytään verkkoteoriaan, jonka avulla havainnollistetaan graafisesti tutkielman sovellusta. Verkkoteoriaan liittyvien määritelmien ja tulosten esittämisen jälkeen tarkastellaan differenssiyhtälöitä. Differenssiyhtälöissä ajan hetki $t$ liitetään ajanhetkeen $t+1$ lineaarisesti siten, että $Av_t=v_{t+1}$, missä neliömatriisia $A$ kutsutaan siirtymämatriisiksi.

Differenssiyhtälöissä keskitytään Markovin ketjuihin, jotka ovat todennäköisyyksiä kuvaavia differenssiyhtälöitä. Tällaisten differenssiyhtälöiden siirtymämatriisit ovat stokastisia matriiseja, jotka ovat ei-negatiivisia matriiseja ja niiden jokainen sarake summautuu luvuksi yksi. Stokastisten matriisien lisäksi Markovin ketjuissa esiintyvät vektorit $v_i$ ovat todennäköisyysvektoreita eli ei-negatiivisia vektoreita, joiden alkiot summautuvat luvuksi yksi.

Markovin ketjujen teoria toimii teoriapohjana Googlen Pagerank-algorit-mille, jossa sovelletaan Perronin lausetta. Määritellään Google-matriisi, joka on positiivinen stokastinen matriisi. Perronin lause takaa, että tämän matriisin spektraalisäde on luku 1 ja sen virittää positiivinen ominaisvektori, jota kutsutaan tasapainotilavektoriksi. Pagerank-algoritmissa tarkastellaan Markovin ketjua, jonka määrää Google-matriisi $G$ ja tasapainotilavektori $w$. Tällöin Markovin ketjun $Gv_t=v_{t+1}$ avulla saadaan internetin nettisivujen tärkeysjärjestys eli järjestys, jossa hakutulokset tulevat näkyviin hakukoneessa. Tämän tärkeysjärjestyksen kertoo Markovin ketjun vektori $v_{t+1}$.

Tutkielman lopuksi tarkastellaan Perronin lauseen yleistystä eli Perronin ja Frobeniuksen lausetta. Tämä lause antaa vastaavat tulokset kuin Perronin lause, koskien ei-negatiivisia redusoitumattomia matriiseja.

Tarkoituksena on esitellä Perronin ja Frobeniuksen lauseen yleinen versio. Tämän jälkeen esitellään ja todistetaan kyseisen lauseen erikoistapaus, jossa tarkastellaan ei-negatiivisia redusoitumattomia neliömatriiseja, joiden jokin positiivinen kokonaislukupotenssi on positiivinen neliömatriisi. Tämä erikoistapaus toteaa vastaavat tulokset, kuin yleinen Perronin ja Frobeniuksen lause.