Twierdzenie Perrona-Frobeniusa i jego zastosowanie w algorytmie Page Rank

Abstrakt

Jednym z ciekawszych i znajdujących wiele zastosowań twierdzeń z algebry liniowej jest twierdzenie Perrona-Frobeniusa. Twierdzenie to jest wspólnym rezultatem prac Oskara Perrona z 1907 i Georga Frobeniusa z 1912. Dzięki niemu wiadomo, iż największa wartość własna rzeczywistej nieujemnej kwadratowej macierzy jest rzeczywista i ma krotność 1. Co więcej, wektor własny korespondujący z tą wartością własną jest ściśle dodatni. Twierdzenie to znajduje zastosowanie w teorii prawdopodobieństwa, ekonomii, demografii, rankingach, a także (dzięki idei Larry'ego Page'a i Sergey'a Brina z 1996 roku) w silnikach wyszukiwarek internetowych. Głównym celem naszego artykułu jestprzedstawienie twierdzenia Perrona-Frobeniusa wraz z zarysem jednego z najpopularniejszych jego dowodów (korzystającego z twierdzenia Brouwera o punkcie stałym) oraz zaprezentowanie jego różnorakich i zaskakujących zastosowań, między innymi w algorytmie Page Rank używanym obecnie przez wyszukiwarkę Google.

The Perron-Frobenius' Theorem and its application in the Page Rank Algorithm

The Perron-Frobenius theorem, which was firstly proved by Oskar Perron in 1907and later extended by Georg Frobenius in 1912, asserts that a real nonnegativesquare matrix has a unique largest real eigenvalue and that the eigenvector corresponding to it has strictly positive components and that this eigenvector is stochastic. This theorem has a wide variety of applications: from probability theory, through economics, demography and rankings to (according to Larry Page and Sergey Brin's idea in 1996) Internet search engines.~The main aim isto present this theorem with one of its most popular proofs (using the Brouwer fixed point theorem) and to explain the idea of several of its applications.