Google Linear Algebra

Google Search Engine & Linear Algebra:
1) Let M(nxn) matrix of size n (say 1 billion) web pages:

$latex
\begin{pmatrix}
m_{11} & m_{12} & \ldots & m_{1n}\\
m_{21} & m_{22} & \ldots & m_{2n}\\
\vdots & \vdots & m_{jk} & \vdots\\
m_{n1} & m_{n2} &\ldots & m_{nn}
\end{pmatrix}
$

$latex m_{jk} = \begin{cases} 1, & \text{if Page }j \text{ linked to Page k} \\
0, & \text{if } \text{ not}
\end{cases}
$

Note: This PageRank of 0 & 1 is over-simplied. The actual PageRank is a fuzzy number between 0 and 1, based on Larry Page's patented PageRank formula, taking into accounts of the importance of the pages linked from and to, plus many other factors.

2) Let v(n) eigenvector of n webpages' PageRank ak:
$latex \begin{pmatrix}
a_1 \\
a_2 \\
\vdots\\
a_k \\
\vdots\\
a_n
\end{pmatrix}
$ $latex \displaystyle \implies a_k= \sum_{j}m_{jk} $
(all Page j pageRanks)
The page k pointed to by all pages j.

3) Let λ eigenvalue: M.v =λ.v

4) Iterate n times: $latex \boxed{(M^{n}).v = \lambda{^n}.v}$

=> page k is ranked more important if many important pages j point to it;
& pages j themselves pointed by other important pages, ...(iterate n times).
=> highest ranked pages appear first in Search list.

Solution 2 (Eigenvalue): Monkeys & Coconuts

Solution 2: Use Linear Algebra

Eigenvalue equation: A.X = λ.X

A =S(x)= $Latex \frac{4}{5}(x-1)$  where x = coconuts

S(x)=λx
Set λ = 1
$Latex \frac{4}{5}(x-1)=x$
x =-4
Also fifth monkey:
$Latex S^5 (x)$ = $Latex (\frac{4}{5})^5 (x-1)+(\frac{4}{5})^5+(\frac{4}{5})^4+\cdots+\frac{4}{5}$

$Latex 5^5$ divides (x-1)

Minimum positive x= -4 mod ($Latex 5^5$ )= $Latex 5^5$-4= 3121 [QED]

Note: λ=1 because "before" and "after" (transformation A)  is the same.