Applications of Eigenvalues

From Theory to Practice

Eigenvalues begin as a purely algebraic construct — solutions to a characteristic polynomial. But once you see them in the wild, they appear everywhere. The PageRank score of every webpage is an eigenvector component. The principal directions along which your data varies most are eigenvectors of a covariance matrix. The long-run probabilities in a stochastic model satisfy an eigenvalue equation. The frequencies at which a bridge will shake apart are square roots of eigenvalues of a structural matrix.

This lesson connects the abstract machinery developed in the previous lessons — finding eigenvalues, computing eigenvectors, diagonalizing matrices — to four landmark applications in computing, data science, probability, and engineering. The mathematics is the same; only the interpretation changes.

Google PageRank

When Google was founded in 1998, its founders Larry Page and Sergey Brin introduced an algorithm — PageRank — that ranked webpages not by their content alone, but by the structure of links pointing to them. The key insight: a page is important if other important pages link to it. This circular definition is resolved elegantly by eigenvalues.

Model the web as a directed graph with n pages. Build the link matrix A where Aᵢⱼ = 1/outDegree(j) if page j links to page i, and 0 otherwise. Each column of A sums to 1 — it is a column-stochastic matrix. The PageRank vector r satisfies:

PageRank Equation

\mathbf{r} = \lambda^{-1} M \mathbf{r}, \quad M = d A + \frac{1-d}{n}\mathbf{1}\mathbf{1}^T

r is the dominant eigenvector of the modified transition matrix M. The damping factor d (typically 0.85) models the probability a random surfer follows a link; (1−d)/n models random jumps to any page. The ones matrix 11ᵀ ensures the system is irreducible — every page can reach every other page.

The eigenvalue λ = 1 is always the largest for a column-stochastic matrix (by the Perron-Frobenius theorem). This guarantees a unique, non-negative dominant eigenvector — the PageRank score vector. Higher score = higher rank in search results.

Why Eigenvalue 1?

The equation Mr = r says that applying M to r leaves r unchanged — r is a fixed point of the matrix transformation. Multiplying by M is like letting a random surfer wander one more step; the PageRank distribution r is stable under one more step. It is the stationary distribution of the random walk on the web graph.

Principal Component Analysis (PCA)

Suppose you have a dataset with many measurements per sample — say, 1000 gene expression levels for each of 500 patients. Most of that information is redundant: correlated features capture overlapping variation. PCA finds the directions in the data space along which variation is greatest, letting you project onto a much smaller subspace without losing much information.

Given a centered data matrix X (rows = samples, columns = features), the covariance matrix is Σ = (1/m) XᵀX. This is a real symmetric matrix, and positive semidefinite as well — vᵀΣv = (1/m)‖Xv‖² ≥ 0 for every v, so no eigenvalue can be negative. By the Spectral Theorem it is therefore always diagonalizable with orthonormal eigenvectors and real (non-negative) eigenvalues:

PCA via Spectral Decomposition

\Sigma = Q D Q^T, \quad \Sigma \mathbf{q}_i = \lambda_i \mathbf{q}_i

Each eigenvector qᵢ is a principal axis — a direction in feature space. The corresponding eigenvalue λᵢ equals the variance of the data projected onto that axis. Larger λᵢ means more variance along that direction, hence more information.

To reduce dimensionality, keep only the k eigenvectors corresponding to the k largest eigenvalues. Project all data points onto these k directions. You now have k-dimensional representations of your data, capturing most of the variation. If the top 10 eigenvalues account for 90% of the total variance (sum of all eigenvalues), a 10-dimensional representation suffices for a 1000-dimensional dataset — a 100× compression.

Geometric Picture

Imagine a cloud of data points shaped like a squashed ellipsoid in high-dimensional space. The eigenvectors of the covariance matrix point along the principal axes of that ellipsoid. The eigenvalues tell you the lengths of those axes. PCA rotates your coordinate system to align with the ellipsoid's natural axes — the most informative directions become coordinate directions.

PCA in Practice

Face recognition (eigenfaces), image compression, genomics, finance (factor models), and noise reduction all rely on PCA. When Netflix builds a recommendation model, it uses a related technique (SVD, closely related to the eigendecomposition) to find a low-dimensional representation of user preferences and movie features.

Markov Chains and Steady State

A Markov chain is a system that transitions between states randomly, where future behavior depends only on the current state — not on history. The transition matrix P has entries Pᵢⱼ = probability of moving from state j to state i. Like A in PageRank, P is column-stochastic: each column sums to 1.

Starting from any initial probability distribution π₀, after many steps the distribution converges to the stationary distribution π∞. This limiting distribution satisfies the eigenvalue equation:

Stationary Distribution

P \boldsymbol{\pi} = \boldsymbol{\pi}, \quad \sum_i \pi_i = 1

Pπ = π means π is an eigenvector of P with eigenvalue 1. The constraint Σᵢ πᵢ = 1 normalizes π to be a probability distribution. For an irreducible, aperiodic chain, the Perron-Frobenius theorem guarantees this π is unique.

Example: Weather Model

Suppose tomorrow's weather depends only on today's: if it is sunny, there is a 90% chance of sun and 10% chance of rain tomorrow; if it rains, there is a 50% chance of rain and 50% chance of sun. The transition matrix is P = [[0.9, 0.5], [0.1, 0.5]]. The stationary distribution satisfies Pπ = π with π₁ + π₂ = 1. Solving: π = [5/6, 1/6]ᵀ ≈ [0.833, 0.167]. In the long run, 83% of days are sunny — regardless of today's weather.

Markov chains model everything from protein folding to credit ratings to the behavior of Google's random surfer. The unifying mathematics is always the same: find the dominant eigenvector of the transition matrix.

Structural Vibration Analysis

When a structure — a bridge, a building, an aircraft wing — vibrates freely (without external forcing), it oscillates at specific frequencies called its natural frequencies. At these frequencies, the entire structure deforms in a characteristic pattern called a mode shape. Both quantities come directly from an eigenvalue problem.

Modeling the structure as a discrete system with n degrees of freedom, the equations of free vibration are governed by the stiffness matrix K and the mass matrix M. Looking for solutions of the form x(t) = v · cos(ωt) leads to the generalized eigenvalue problem:

Free Vibration Eigenvalue Problem

K\mathbf{x} = \omega^2 M \mathbf{x}, \quad \omega_i = \sqrt{\lambda_i}

K is the stiffness matrix (symmetric, positive semi-definite); M is the mass matrix (symmetric, positive definite). The eigenvalues λᵢ equal ωᵢ², where ωᵢ are the natural frequencies (in radians per second). The eigenvectors v are the mode shapes — the deformation patterns at each frequency.

Engineering Significance

If an external force excites a structure at or near one of its natural frequencies, the response can grow dramatically — this is resonance. The Tacoma Narrows Bridge collapsed in 1940 partly because wind excitation matched a natural frequency of the bridge deck. Structural engineers use eigenvalue analysis to find all natural frequencies during design and ensure they do not coincide with expected excitation frequencies (traffic, wind, earthquakes).

Mode shapes are equally important: they reveal which parts of the structure move most during each type of vibration, guiding where to add damping or stiffening. The first mode (lowest frequency, largest wavelength) usually involves the largest displacements and is the most dangerous.

Generalized vs. Standard Eigenvalue Problem

Kv = ω²Mv is a generalized eigenvalue problem. It reduces to the standard form Av = λv by writing A = M⁻¹K (if M is invertible) or by using a Cholesky factorization of M. The eigenvalues of M⁻¹K are ωᵢ² and are always positive for well-posed structural systems.

The Power Iteration Method

All the applications above require computing eigenvalues or eigenvectors of very large matrices — web graphs with billions of nodes, covariance matrices with thousands of features. Direct methods (like computing the characteristic polynomial) are computationally infeasible at such scales. The power iteration algorithm provides a simple, scalable alternative for finding the dominant eigenvector.

The idea is elegant: start with any vector x₀ and repeatedly multiply by A, normalizing after each step:

Power Iteration

\mathbf{x}_{k+1} = \frac{A\mathbf{x}_k}{\|A\mathbf{x}_k\|}

Each step is just a matrix-vector multiply (O(n²) for dense A, much cheaper for sparse A) followed by normalization. The sequence converges to the dominant eigenvector v₁ — the eigenvector corresponding to the largest eigenvalue λ₁ — with the error falling by a factor |λ₂/λ₁| at every step.

Why Does It Work?

Write the initial vector x₀ in the eigenvector basis: x₀ = c₁v₁ + c₂v₂ + … + cₙvₙ. After k applications of A:

Aᵏx₀ = c₁λ₁ᵏv₁ + c₂λ₂ᵏv₂ + … + cₙλₙᵏvₙ = λ₁ᵏ(c₁v₁ + c₂(λ₂/λ₁)ᵏv₂ + …)

If |λ₁| > |λ₂|, the terms (λᵢ/λ₁)ᵏ → 0 for i ≥ 2. After normalization, Aᵏx₀/‖Aᵏx₀‖ → v₁. Read the rate off that expression: the error left in the iterate is carried by (λ₂/λ₁)ᵏ, so each step multiplies the error by the factor |λ₂/λ₁| < 1 — equivalently, the dominant direction gains |λ₁/λ₂| on its nearest rival every pass. The wider the eigenvalue gap, the faster the convergence; a ratio near 1 makes it crawl.

Google's original PageRank computation used exactly power iteration on the web link matrix — converging in roughly 50–100 iterations even for a graph with billions of nodes, because the web graph's structure ensures a good eigenvalue gap.

Beyond Power Iteration

Power iteration finds only the dominant eigenvector. To find all eigenvectors (as in PCA), engineers use QR iteration — a more sophisticated algorithm that simultaneously converges all eigenvalues. For structural problems, the Lanczos algorithm efficiently finds the smallest eigenvalues (lowest natural frequencies) of large sparse matrices. These algorithms are all rooted in the same intuition: repeated multiplication amplifies the dominant directions.

Key Takeaways

Google PageRank ranks webpages by the dominant eigenvector (eigenvalue 1) of the stochastic link matrix — computed via power iteration. PCA finds the principal directions of a dataset as the eigenvectors of the covariance matrix; eigenvalues measure the variance captured. Markov chains converge to a stationary distribution π satisfying Pπ = π — an eigenvector equation. Structural vibration analysis finds natural frequencies ωᵢ = √λᵢ and mode shapes from the generalized eigenvalue problem Kv = ω²Mv. Power iteration is the scalable algorithm underpinning all of these: multiply, normalize, repeat.