How Google Views the Web
When Larry Page and Sergey Brin founded Google in the late 1990s, their breakthrough was PageRankâ€â€an algorithm that ranks web pages based on their link structure. Instead of just counting keywords, PageRank treats a link from Page A to Page B as a "vote" of confidence.
To model this mathematically, the web is represented as a directed graph where pages are nodes and links are arrows. A hypothetical "random surfer" clicks links at random. The PageRank of a page is the probability that the random surfer ends up on that page after a long time.
The Transition Matrix
Let's represent the web as a transition probability matrix M. If a page has 3 outgoing links, the probability of clicking any one of them is 1/3. The entry Mji represents the probability of transitioning from Page i to Page j.
If we write the probability of being on each page as a probability vector v, the distribution after one step is M ⋅ v. Over time, the probabilities settle into a steady state (stationary distribution) where the probability vector no longer changes. Mathematically:
M ⋅ v = v
This is an eigenvalue equation. It states that v is an eigenvector of M corresponding to the eigenvalue λ = 1.
Solving for PageRank using RREF
To find the eigenvector v, we can rewrite the equation as a homogeneous linear system:
M ⋅ v - v = 0 ⇒ (M - I) ⋅ v = 0
where I is the Identity matrix. This equation says that v lies in the null space (kernel) of the matrix (M - I).
How do we find the null space of a matrix? We use **Gauss-Jordan elimination** to compute the **RREF** of (M - I)! Once the matrix is in RREF, we can read the free variables, construct the parametric solution, and find the stationary vector representing the exact rank probabilities of each web page.
Scaling to the Real Web
In practice, the real web has billions of pages, making manual RREF impossible. Instead of exact row reduction, Google uses iterative numerical methods (like the Power Method) to approximate the PageRank vector. However, the exact mathematical foundation remains rooted in finding the null space via row reduction.