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.

Eigenvector & Eigenvalue

1. Matrix (M): stretch & twist space
2. Vector (v): a distance along some direction
3. M.v = v' stretched & twisted by M

Some directions are special:-
a) v stretched but not twisted = Eigenvector;
b) The amount of stretch = constant = Eigenvalue (λ)

Let M the matrix, λ its eigenvalue,
v eigenvector.
By definition: M.v = λ.v
v = I.v (I identity matrix)
M.v = λI.v
(M - λI).v=0
As v is non-zero,
1. Determinant (M- λI) =0 => find λ
2. M.v = λ.v => find v

Note1: Why call Eigenvalue ?
From German: "Die dem Problem eigentuemlichen Werte"
= "The values belonging to this problem"
=> eigenWerte = EigenValue
Eigenvalue also called 'characteristic values' or 'autovalues'.
Eigen in English = Characteristic (but already used for Field).

Note2: Schrödinger Quantum equation's Eigenvalue = Maximum probability of electron presence at the orbit outside nucleus.

Note3: Excellent further explanation of the eigenvector and eigenvalue:

http://lpsa.swarthmore.edu/MtrxVibe/EigMat/MatrixEigen.html