In the previous parts of this series (Part I and Part II), we established a solid foundation by introducing the fundamental concepts, terminology, and core theory of linear algebra. In this final part (Part III), we bridge the gap between theory and application by demonstrating how linear algebra operates in real-world systems. To illustrate this connection, we will introduce one of the most elegant and historically influential applications of linear algebra: PageRank, Google's original ranking algorithm, which revolutionized how information is organized and retrieved on the web.

While this article focuses on PageRank, it represents only one of the many ways linear algebra drives modern technology. Another particularly exciting and rapidly developing area is data security and cryptography. In particular, linear algebra provides the mathematical foundation for emerging post-quantum cryptographic techniques, such as lattice-based cryptography, which are designed to remain secure against the capabilities of future quantum computers. Because this field is evolving rapidly, a thorough treatment is beyond the scope of the present series. However, we hope to return to this topic in a future series dedicated to exploring the central role of linear algebra in modern cryptography.

That said, we will try to explain the concepts and ideas in the simplest language possible while preserving mathematical accuracy. This goal is the very reason this site exists: to bridge the gap between mathematical theory and practical intuition, so that even readers without deep technical backgrounds can follow along. This means that if you are just curious about how PageRank works, you can read through like any other article; while those seeking deeper understanding will find the mathematical structure clearly laid out.

Search Engines in the Information Age

As a society living in the “Information Age,” we face the daily challenge of navigating vast oceans of content. The internet—arguably one of the greatest innovations in human history—reflects what people want to learn, watch, play, buy, or explore. Yet most content online is not particularly helpful, making it essential to choose our search results wisely.

From a sharper perspective, information selection is precisely what search engines like Google and Microsoft Bing does for us every day. When we type a query into search engine, we receive a list of pages sorted (more or less) by relevance. This article aims to show how linear algebra helped revolutionize this ranking process through one of the most famous algorithms ever created: PageRank.

Many linear algebra textbooks often mention PageRank as one of the most famous application of linear algebra, but they rarely illustrate how linear algebra enters the picture. That is precisely what we aim to do here. Of course Google's founders, Larry Page and Sergey Brin, invested enormous effort in developing these ideas, fortunately the underlying mathematics is much more accessible today. And with modern computational tools and a wealth of freely available resources, it is far easier to understand the connection between PageRank and linear algebra than it was when the algorithm was first introduced.

What Does a Search Engine Actually Do?

Before diving into PageRank, let us briefly outline the four main components of a search engine; a crawler, an indexer, a ranking algorithm, and a query engine:

• A Web Crawler: Methodically copies pages from the web into a database, tracking hyperlinks between pages.
• An Indexer: Processes these pages and determines relevant keywords for their efficient retrieval.
• A Ranking Algorithm: Determines the order of each page so that the most relevant, useful, important, or preferred options appear first.
• A Query Engine: (The search bar) Retrieves and displays results based on the ranking algorithm.

While each part above is a fascinating problem in itself, we will focus primarily on the third: the ranking algorithm. And in particular PageRank, which was Google's early novel ranking method, named after co-founder Larry Page.

How PageRank Works (High-Level Overview)

In the early days of the Internet, ranking websites seemed straightforward: simply count how many other websites link to a page. The intuition was reasonable—the more backlinks a website has, the more popular it must be. Unfortunately, this approach was easy to manipulate. Anyone could create dozens of low-quality websites that all linked to a single page, artificially inflating its importance. These collections of websites that all hyperlink to each other for the purpose of increasing search engine rankings became known as link farms.

PageRank's breakthrough was realizing that not every link should count equally. A backlink from an important website should matter far more than dozens of low-quality backlinks from obscure websites. According to Google: "PageRank works by counting the number and quality of links to a page to estimate how important the website is. The underlying assumption is that more important websites are likely to receive more links from other important websites".

Instead of asking "How many pages link here?" Google asked a much better question: "How important are the pages that link here?" . This seemingly simple idea transformed the ranking problem into one of the most famous applications of linear algebra. The big question, then, is: How does PageRank determine whether a backlink is high quality or low quality?

Emergent Importance: Everyone Starts Equal

Many people assume Google manually identified important websites—such as Wikipedia or CNN—and labeled them as authoritative. In reality, PageRank is built on a much simpler assumption: "important websites tend to receive links from other important websites".

Crucially, every website starts with the same initial importance. At the beginning, CNN.com and Spamsite.com carry equal weight. Through iterative computation, authority and importance emerges naturally. The result is a stable ranking in which CNN has a much higher PageRank score—and is therefore considered a far more authoritative source—without Google ever needing to manually designate it as such. How this happens will be illustrated with an example later.

A Mini PageRank Universe

To understand PageRank and why it transformed search engines, we will:

• Model the web as a directed graph: Each page is a node (also called a vertex), and each hyperlink is a directed edge (an arrow).
• Build a link matrix: From the PageRank equations, we will encode how pages point to one another using a matrix whose entries represent link structure.
• Implement a simplified PageRank; Showing how iterative methods converge to a stable ranking by computing an importance score for every page simultaneously.

We start by building a small “mini universe” of web pages and links. Our toy web consists of 14 pages: A, B, C, D, E, F, G, H, I, J, K, L, M, N. The links between them are defined as shown below in Figure 1:

At first glance, pages B and E appear to be the most important because they receive the largest number of incoming links. However, once we apply PageRank, the ranking changes dramatically. Another page unexpectedly emerges as the most important, while B's apparent dominance is significantly reduced. In fact, a page like H, despite having only a single incoming link, ultimately ranks far above B.

From Web Graph to System of Linear Equations

To understand PageRank properly, we begin with the web graph itself. If we had a very naive ranking algorithm, the simplest idea would be:

\[ x_i = \text{in-degree}(v_i) \] Where;

• \(v_i\); represents page \(i\) in our web graph, \(\text{in-degree}(v_i)\) is the number of links pointing to page \(v_i\), and \(x_i\) is the importance (ranking) score assigned to page \(v_i\).
• What this equation means: A page's score is simply the number of incoming links it has. Every link counts as one vote, no matter which page it comes from.
• Example from our mini-universe: Page B receives links from pages A, C, D, L, M, and N. Its in-degree is therefore 6, so this simple ranking method would assign page B a score of 6.

Unfortunately, our naive formula cannot distinguish quality from noise because it treats all links as equally valuable. Surely, a backlink from CNN.com should matter more than a backlink from Spamsite.com.

Improving the Ranking: Weighted Votes

To fix this, we let each page “vote” for the pages it links to. Whereby, the importance of a page should depend on the importance of the pages that endorse it. Then:

\[ x_i = \sum_{j \in S_i} x_j \]

• \(S_i\) is the set of all pages that link to page \(v_i\). \(j \in S_i\) means "for every page \(j\) in that set"; We add all of these values together.
• \(x_j\) is the importance score of one page linking to \(v_i\), and \(x_i\) is the final importance score of page \(v_i\).
• What this equation means: Instead of counting links, we add the importance scores of the pages providing those links. Links from more important pages contribute more to the final score.
• Example from our mini-universe: For page B, the set of linking pages is \(S_B=\{A,C,D,L,M,N\}\). The score of page B is therefore calculated by adding together the scores of pages A, C, D, L, M, and N.

This is better, but still flawed. A page with a high score could unfairly influence the system simply by linking to many other pages. To prevent this, each vote is weighted by the number of outbound links of the voting page:

\[ x_i = \sum_{j \in S_i} \frac{x_j}{\text{out}(v_j)} \] Whereby;

• We divide \(x_j\) with \(\operatorname{out}(v_j)\), which is the number of outgoing links on page \(v_j\) (also called out-degrees).
• What this equation means: A page shares its importance equally among all of its outgoing links. Pages with many outgoing links spread their influence more thinly than pages with only a few links.
• Example from our mini-universe: Page D links to pages B, E, and N, so \(\operatorname{out}(D)=3\). If page D has a PageRank score of \({x_D}\), then each linked page receives \(\dfrac{x_D}{3}\) units of D's voting power.

This is the core idea behind PageRank: links are votes, but votes from important pages count more, and each page's voting power is divided among its outgoing links.

Applying the System to Our Mini Universe

Let us now apply this formula to our 14-page web. For each page \(v_i\), we write an equation expressing its importance in terms of the sum of the pages linking to it. Below are several representative equations from our mini-universe.

Example Equations

Page B receives links from A, C, D, L, M, and N. Using the out-degrees of each:

\[ x_B= \frac{x_A}{2}+ \frac{x_C}{2}+ \frac{x_D}{3}+ \frac{x_L}{3}+ \frac{x_M}{2}+ \frac{x_N}{2} \]

Notice that we are not trying to compute B directly. Instead, we are expressing the relationship that must hold between all page scores simultaneously.

Page E receives links from D, F, G, I, J, and K:

\[ x_E= \frac{x_D}{3}+ \frac{x_F}{4}+ \frac{x_G}{4}+ \frac{x_I}{3}+ \frac{x_J}{3}+ \frac{x_K}{3} \]

Page I receives links from F, H, J, and K:

\[ x_I= \frac{x_F}{4}+ x_H+ \frac{x_J}{3}+ \frac{x_K}{3} \]

We can write similar equations for all 14 pages in the network. Collectively, they form a system of 14 linear equations with 14 unknown page scores.

Writing the System as a Matrix Equation

As we outlined in Part I, the essential information of a linear system can be expressed compactly in matrix form. So, rather than writing 14 separate equations, we can represent the entire system as a single matrix equation. The unknown page scores are collected into one column vector, which has dimensions; \(14\times1;\)

\[ x= \begin{bmatrix} x_A\\ x_B\\ x_C\\ \vdots\\ x_N \end{bmatrix}, \]

The link structure of the web is encoded in a 14 × 14 link matrix \(M\). Each column represents a web page that distributes its importance, while each row represents a page receiving that importance. If page \(v_j\) links to page \(v_i\), then the corresponding matrix entry is: \(M_{ij}=\dfrac{1}{\operatorname{out}(v_j)}\). If page \(v_j\) does not link to page \(v_i\), then; \(M_{ij}=0\)

Because every outgoing link receives an equal share of a page's importance, the entries in each column add up to one. Such a matrix is called a column-stochastic matrix. Multiplying this matrix by the page score vector automatically computes all 14 equations at once. The complete system therefore becomes:

\[ x=Mx. \]

Connection to Eigenvectors

In Part II, we introduced one of the fundamental concepts of linear algebra: eigenvalues and eigenvectors, together with the equation;

\[ Ax=\lambda x. \]

Notice that the complete system equation \(x=Mx\) can be rewritten as;

\[ Mx=1\cdot x. \]

Comparing this with the general eigenvalue equation; \(Ax=\lambda x,\) we see that the PageRank vector is simply an eigenvector of the link matrix \(M\) whose eigenvalue is

\[ \boxed{\lambda=1.} \]

Finding the eigenvector (also called dominant right eigenvector), which corresponds to this eigenvalue (\({\lambda=1}\)), is the central mathematical problem behind Google's original PageRank algorithm. Everything that follows—including the damping factor, the random-surfer model, and the power iteration algorithm—is designed to compute this eigenvector efficiently for the enormous graph formed by the World Wide Web.

Iterative Computation: Power Method

This eigenvector (PageRank score) can be computed either algebraically or iteratively. For a web graph containing billions of pages, an algebraic solution is computationally impractical. So, instead of solving \(\mathbf{x} = M\mathbf{x}\) directly, PageRank score is approximated using an iterative procedure known as the power iteration method (or simply the power method). The process begins by assuming that every page is equally important:

\[ \mathbf{x}^{(0)} = \frac{1}{N}\mathbf{1}, \]

where \(N\) is the number of pages in the web graph (from our mini universe \(N = 14\)) and \(\mathbf{1}\) is a column vector of length \(N\) containing only ones. At each step, we update the scores by multiplying with the link matrix:

\[ \mathbf{x}^{(k+1)} = M\mathbf{x}^{(k)}. \]

Intuitively, this means: “take the current importance scores and redistribute them according to the link structure.” After few iterations, the scores stabilize and no longer change significantly—this stable vector is the PageRank eigenvector.

To illustrate this process, we implemented the undamped PageRank algorithm in Python for our mini web graph. Starting from equal importance for every page (\(1/14 \approx 7.14\%\)), the program repeatedly applies the update rule above until the PageRank scores converge. Figure 2: shows how the PageRank scores evolve over the first twenty iterations. (Throughout the discussion, PageRank scores are expressed as percentages by multiplying the scores by 100)

Several important observations emerge from these results:

• Initially, every page has equal importance; After the first iteration, page B receives the highest score (19.05%) because it has the largest number of incoming links
• Link quantity alone is not enough: As the iterations continue, PageRank distinguishes between the quantity and quality of incoming links. Although B has many incoming links, they come primarily from low-ranked pages, causing its score to fall from 19.05% to just 1.02% after twenty iterations. By that point, even pages such as G (9.78%) and K (10.13%) have higher PageRank scores. This illustrates how link farms are ineffective.
• High-quality links dominate: Page I, despite having only three incoming links, steadily gains importance because those links originate from increasingly authoritative pages. Its PageRank rises to approximately 23.23%, making it the highest-ranked page in the network.
• A single authoritative link can outweigh many weak ones: Page H has only one incoming link, yet its final PageRank (18.61%) is almost identical to that of E (18.67%), which has six incoming links. This demonstrates that the authority of a linking page is far more important than the number of links.

Why Does the Power Method Converge?

The key question is: why does repeatedly multiplying by \(M\) cause the scores to converge to the PageRank vector? The answer lies in the properties of stochastic matrices, eigenvectors, and eigenvalues. As outlined earlier, the link matrix \(M\) is column-stochastic, meaning that each column represents a probability distribution and sums to one. A fundamental property of stochastic matrices is that they always have an eigenvalue equal to \(\boxed{\lambda_1=1.}\)

Under the conditions satisfied by the PageRank algorithm, this is the dominant eigenvalue, while the magnitudes of all remaining eigenvalues are strictly less than one. Because the dominant eigenvalue satisfies \(\lambda_1=1\), while every other eigenvalue satisfies \(|\lambda_i|<1\), the non-dominant terms become progressively smaller with each iteration. Eventually, they vanish, leaving only the dominant eigenvector, which is the PageRank vector.

This explains the behaviour observed in Figure 2:. Initially, every page starts with equal importance, meaning that the starting vector contains a mixture of different eigendirections. During each iteration, the influence of non-dominant components disappears, while the dominant structure of the web graph becomes increasingly visible. Pages supported by authoritative pages, such as I and H, gain importance, while pages whose importance comes mainly from weak sources, such as B, gradually lose influence.

A natural question is how many iterations are required for a web graph containing billions of pages to stabilize. Fortunately, the power method converges remarkably quickly. In practice, Google has reported that only a few dozen to a few hundred iterations are typically sufficient to obtain a stable PageRank vector, making the algorithm practical even at web scale.

Introducing the Damping Factor

The real web is much larger and more complex than our toy example. It contains pages with no outgoing links (dead ends/dangling pages), disconnected groups of pages that cannot be reached from the rest of the web, and spider traps (where a user can become trapped inside a small group of pages that only link to one another). These situations can prevent the PageRank algorithm from converging to a unique ranking.

To address these issues, PageRank introduces a damping factor, usually denoted by \(d\) (Google originally chose \(d = 0.85\)). The idea is to model a more realistic random surfer:

• With probability \(d\), the surfer follows one of the outgoing links from the current page.
• With probability \(1 - d\), the surfer jumps (teleports) to a random page anywhere on the web.

This leads to the modified PageRank equation:

\[ \mathbf{x} = \frac{1-d}{N}\mathbf{1} + dM\mathbf{x}, \]

where:

• \(N\) is the total number of pages.
• \(\frac{1-d}{N}\mathbf{1}\) represents the random teleportation to any page.
• \(dM\mathbf{x}\) represents following links according to the link matrix.

Rewriting this in matrix form, we obtain the so-called Google matrix:

\[ G = dM + \frac{1-d}{N}\mathbf{1}\mathbf{1}^T, \]

and the PageRank vector is now defined by:

\[ \mathbf{x} = G\mathbf{x}. \]

The matrix \(G\) is still stochastic and has strictly positive entries. By the Perron-Frobenius theorem, such a matrix has a unique positive eigenvector associated with eigenvalue 1. This guarantees that the PageRank vector exists, is unique, and can be found by iteration.

In our mini universe, applying a damping factor (\(d = 0.85\)) reduces the extreme dominance of page I while still recognizing that it is an important hub. At the same time, it rescues low-degree pages from having effectively zero importance, making the ranking more realistic and robust.

Conclusion: Putting It All Together

We have now seen the full journey from raw links to PageRank scores:

• We modelled the web as a directed graph of pages and hyperlinks.
• We translated this graph into a link matrix \(M\), where each column describes how a page distributes its importance.
• We expressed PageRank as a system of linear equations \(x = Mx\), revealing that the ranking vector is an eigenvector with eigenvalue 1.
• We computed PageRank iteratively using the power method, watching importance emerge over time.
• We introduced the damping factor and the Google matrix \(G\), ensuring a unique, stable ranking that reflects both link structure and random jumps.

In our toy web, we have illustrated these ideas in a concrete setting. Explaining why page I emerges as highly important, why simply counting incoming links can be misleading, and how damping produces a ranking that is both stable and fairer. Although our example is deliberately small, the same mathematical principles scale to networks containing billions of webpages, where PageRank and related ranking algorithms are applied at an immense scale.

More importantly, this journey reveals the power of linear algebra. Throughout this three-part series, we have seen how linear algebra provides a unifying framework for understanding and transforming data. Vectors, matrices, tensors, eigenvalues, and eigenvectors are not merely abstract mathematical objects—they form a language for describing structure, analysing patterns, and solving complex real-world problems. PageRank is perhaps one of the clearest examples of this connection, demonstrating how a concept as seemingly abstract as the principal eigenvector can shape the way billions of people discover information every day.