Google Illustration:

The following Webpages (1) to (n=6) are linked in a network below:

eg.

Page (1) points to (4),

(2) & (3) points to (1)…

Let

= Probability (**PageRank ***) from Page ( i ) linked to Page (j).

(*) **PageRank**: a measure of how relevant the page’s content to the topic of your query. This value is computed by the proprietary formula designed by the 2 Google Founders Larry Page & Sergey Brin, whose Stanford Math Thesis mentor was Prof Tony Chan (who knows the ‘secret ‘ to put his name always on Google 1st search list.)

The **Markov Transition Matrix** (A) is :

Assume we start surfing from Page (1).

We define** PageRank Vector** x

**x** = (1 0 0 0…0), the Probability of reaching from Page (1) to itself is 1, to other pages is 0.

__First Iteration__:

**x**.A = (1 0 0 0…0).

__2nd Iteration__:

or,

.

.

*n*th Iteration:

When n is large,

converges to a **steady-state vector**, ie

That is,

“Cancel off” both sides by (technically multiply both sides by

So we get,

We say that x is a **Left EigenVector** of A if

By **Perron’s Theorem:**

Every real square matrix with entries that are all positive has

■ a *unique* eigenvector “**x**” with all positive entries;

■ the **x**‘s corresponding eigenvalue ” **λ**” has only *one* associated eigenvector, and

■ this eigenvalue “**λ**” is the *largest* of the eigenvalues.

Applying to A (square matrix with positive real numbers),

=> **one and **__only__ one (left) eigenvector x which satisfies x.A = x

=> x is unique and has all positive entries (PageRank values).

It guarantees that no matter how much the Web changes or what set of Web pages Google indexes, the PageRank vector (**x**) can always be found and will be **unique** !

**Example in the above Illustration**:

If the unique PageRank vector x is computed after n iterations as follow:

Then Google will list the search result in this order:

1st: Page 3 (0.63)

2nd: Page 6 (0.47)

3rd: Page 2 (0.35)

4th: Page 1 (0.25)

5th: Page 5 (0.12)

6th: Page 4 (0.05)

Knowing this trick, some hackers in 2003 initiated a “Google Bomb” attack on President George W. Bush, associated him with Google query “*miserable failure*“.

**Revision**:

Linear Algebra (Left & Right Eigenvectors and eigenvalues).

**Ref**:

《Math Bytes》by Tim Charter

Princeton University Press

[NLB #510 CHA]

**Google Patents**:

https://www.google.com/patents/US6285999

谷歌背后的数学: