Maths for AI
Topic 8 · Linear algebra · ⏱ about 4 h

Eigenvectors, Covariance & SVD

The linear algebra behind PCA, conditioning and convexity.

Show:
In this topic
Beginner

Eigenvectors: directions a matrix only stretches

When you multiply a vector by a matrix, the result usually points in a different direction from the original vector: the matrix both stretches and turns it. But for most matrices there are a few special directions that are only stretched, never turned. A vector in one of those directions is called an eigenvector, and the amount it gets stretched by is its eigenvalue, written λ\lambda (lambda). In symbols,

eigenvector [1, 1]: only stretched (×3)vAv = 3vnot an eigenvector: [1, 0] gets turnedvAv = [2, 1]
For A = [[2,1],[1,2]], the direction [1,1] is only stretched (eigenvalue 3), while most directions, like [1,0], are also turned.
Av=λv. Av = \lambda v.

Let's see this with the matrix A=[2112]A = \begin{bmatrix}2&1\\1&2\end{bmatrix}. Multiply it by the vector [1,1][1, 1]: the result is [2+1, 1+2]=[3,3][2 + 1,\ 1 + 2] = [3, 3], which is exactly 3×[1,1]3\times[1, 1]. The vector kept its direction and was stretched by a factor of 3, so [1,1][1, 1] is an eigenvector with eigenvalue 3. Now try [1,−1][1, -1]: the result is [2−1, 1−2]=[1,−1][2 - 1,\ 1 - 2] = [1, -1], unchanged, so it is an eigenvector with eigenvalue 1. By contrast, [1,0][1, 0] becomes [2,1][2, 1], which points in a different direction, so [1,0][1, 0] is not an eigenvector.

How do we find eigenvalues without guessing? Start from Av=λvAv = \lambda v and move everything to one side: Av−λv=0Av - \lambda v = 0, which can be written (A−λI)v=0(A - \lambda I)v = 0. We want a non-zero vector vv that this matrix sends to zero. That can only happen if the matrix A−λIA - \lambda I squashes space flat, which (as we saw in the matrices topic) means its determinant is zero:

det⁡(A−λI)=det⁡[2−λ112−λ]=(2−λ)2−1=λ2−4λ+3=0. \det(A - \lambda I) = \det\begin{bmatrix}2-\lambda & 1\\ 1 & 2-\lambda\end{bmatrix} = (2-\lambda)^2 - 1 = \lambda^2 - 4\lambda + 3 = 0.

This quadratic factorises as (λ−3)(λ−1)=0(\lambda - 3)(\lambda - 1) = 0, so the eigenvalues are 3 and 1, which matches what we found by hand. For each eigenvalue, you can then find its eigenvector by solving (A−λI)v=0(A - \lambda I)v = 0.

Symmetric matrices, those that equal their own transpose, are especially well behaved, and they are the ones that matter most in machine learning, because covariance matrices and Hessians are always symmetric. A symmetric matrix always has real eigenvalues, and its eigenvectors are perpendicular to each other (in our example, [1,1][1, 1] and [1,−1][1, -1] are at right angles). This means a symmetric matrix can be understood as a simple three-step action: rotate so that the eigenvectors line up with the axes, stretch along each axis by the corresponding eigenvalue, then rotate back. In symbols, A=QΛQ⊤A = Q\Lambda Q^\top, where the columns of QQ are the eigenvectors and Λ\Lambda is a diagonal matrix of the eigenvalues.

Two quick checks are useful when you compute eigenvalues. Their sum always equals the sum of the diagonal entries (the trace): here 3+1=2+23 + 1 = 2 + 2. Their product always equals the determinant: here 3×1=(2)(2)−(1)(1)3\times1 = (2)(2) - (1)(1).

Try it

Try it: find the eigenvectors

Start with the symmetric preset (this matrix). The dashed lines are the eigenvectors: points on them stay on their line. Try rotate: no real eigenvectors, because every direction turns.

Interactive: this part runs in your browser.

Beginner

Covariance and the covariance matrix

Many datasets have features that tend to move together: taller people tend to be heavier, and bigger houses tend to have more bedrooms. Covariance measures this tendency. For two features xx and yy measured on nn examples,

eigenvector 1: large λ (most spread)eigenvector 2: small λ
The eigenvectors of a covariance matrix point along the directions of greatest and least spread; the eigenvalues measure that spread. These are the principal components.
cov⁡(x,y)=1n−1∑i=1n(xi−xˉ)(yi−yˉ). \operatorname{cov}(x, y) = \frac{1}{n-1}\sum_{i=1}^{n}(x_i - \bar x)(y_i - \bar y).

To see what this formula is doing, look at a single term. If, for some example, both xx and yy are above their averages, both brackets are positive and their product is positive. If both are below average, both brackets are negative and their product is again positive. If one is above and the other below, the product is negative. So the covariance is positive when the two features tend to be above or below average together, negative when one tends to be high while the other is low, and close to zero when there is no consistent linear relationship. Because covariance depends on the units of measurement, we often divide by both standard deviations to get the correlation, r=cov⁡(x,y)σxσyr = \frac{\operatorname{cov}(x, y)}{\sigma_x\sigma_y}, which always lies between −1 and 1.

Let's compute everything for a tiny dataset of three points, (1,2)(1, 2), (2,4)(2, 4) and (3,6)(3, 6). The means are xˉ=2\bar x = 2 and yˉ=4\bar y = 4. Subtracting them ("centring" the data) gives (−1,−2)(-1, -2), (0,0)(0, 0) and (1,2)(1, 2). Now each quantity is just an average of products, dividing by n−1=2n - 1 = 2:

var⁡(x)=12[(−1)2+02+12]=1,var⁡(y)=12[(−2)2+02+22]=4, \operatorname{var}(x) = \tfrac12\big[(-1)^2 + 0^2 + 1^2\big] = 1, \qquad \operatorname{var}(y) = \tfrac12\big[(-2)^2 + 0^2 + 2^2\big] = 4,
cov⁡(x,y)=12[(−1)(−2)+(0)(0)+(1)(2)]=2. \operatorname{cov}(x, y) = \tfrac12\big[(-1)(-2) + (0)(0) + (1)(2)\big] = 2.

The correlation is 2/(1×2)=12/(1\times2) = 1, the maximum possible, which makes sense because the three points lie exactly on the line y=2xy = 2x.

With many features, we collect all the variances and covariances into a single covariance matrix SS. The variances go on the diagonal and the covariances go off the diagonal:

S=[var⁡(x)cov⁡(x,y)cov⁡(x,y)var⁡(y)]=[1224]. S = \begin{bmatrix}\operatorname{var}(x) & \operatorname{cov}(x,y)\\ \operatorname{cov}(x,y) & \operatorname{var}(y)\end{bmatrix} = \begin{bmatrix}1 & 2\\ 2 & 4\end{bmatrix}.

There is a neat way to compute it in one step. If XcX_c is the centred data matrix (one row per example), then S=1n−1Xc⊤XcS = \frac{1}{n-1}X_c^\top X_c, because each entry of Xc⊤XcX_c^\top X_c is exactly a sum of products of centred values.

The covariance matrix is symmetric, so it has perpendicular eigenvectors, and these have a very useful meaning: they point along the directions in which the data is most and least spread out, and the eigenvalues measure how much spread there is in each direction. For our example, the eigenvectors are [1,2][1, 2] with eigenvalue 5 and [2,−1][2, -1] with eigenvalue 0. The first points along the line the data lies on; the second is perpendicular to it, and its eigenvalue of zero tells us there is no spread at all in that direction. Those eigenvectors are precisely the principal components that PCA uses to compress data.

Interactive: this part runs in your browser.

Interactive. Change the spreads and the correlation, and watch the covariance matrix, its eigenvalues and its eigenvectors update.
Intermediate · Maths

Positive definiteness, condition number and the SVD

This section introduces three ideas that appear throughout the advanced material: positive definiteness, the condition number, and the singular value decomposition.

A symmetric matrix AA is called positive semi-definite (PSD) if v⊤Av≥0v^\top A v \ge 0 for every vector vv. It can be shown that this is the same as saying that all of its eigenvalues are zero or positive. The geometric meaning is the important part. The expression f(v)=v⊤Avf(v) = v^\top Av is a quadratic function of vv, and when AA is PSD this function is shaped like a bowl: there is no direction in which it slopes downwards forever. If the inequality is strict (v⊤Av>0v^\top Av > 0 for every non-zero vv, equivalently all eigenvalues positive), the matrix is called positive definite, the bowl has a single lowest point, and the matrix is invertible.

A particularly important fact is that X⊤XX^\top X is always positive semi-definite, for any matrix XX. The proof is one line: v⊤X⊤Xv=(Xv)⊤(Xv)=∥Xv∥2v^\top X^\top Xv = (Xv)^\top(Xv) = \lVert Xv\rVert^2, and a squared length can never be negative. This has two big consequences. First, the least-squares loss in linear regression, whose curvature is X⊤XX^\top X, is always a bowl, so it has no misleading local minima. Second, covariance matrices (which are Xc⊤XcX_c^\top X_c divided by a positive number) never have negative eigenvalues, which matches the common-sense fact that variances can't be negative.

The condition number of a symmetric positive definite matrix is the ratio of its largest eigenvalue to its smallest, κ=λmax⁡/λmin⁡\kappa = \lambda_{\max}/\lambda_{\min}. For a loss function, the eigenvalues of the Hessian describe how steeply the bowl curves in each direction. If one direction curves 100 times more steeply than another, κ=100\kappa = 100, and the bowl is a long, narrow valley. As the gradient descent topic shows, the algorithm then zig-zags between the steep walls while making slow progress along the flat floor. Scaling the features so they have similar ranges brings κ\kappa down and makes training much faster.

Eigenvectors only make sense for square matrices, but a data matrix usually has many more rows than columns. The singular value decomposition (SVD) is the tool that works for any matrix. It says that every matrix XX can be written as a product of three simpler matrices:

X=UΣV⊤. X = U\Sigma V^\top.

Here UU and VV are rotation-like matrices (their columns are perpendicular unit vectors), and Σ\Sigma is a diagonal matrix of non-negative numbers σ1≥σ2≥…\sigma_1 \ge \sigma_2 \ge \dots called the singular values. In words, every matrix acts by rotating, then stretching along the axes by the singular values, then rotating again.

The SVD is closely connected to eigenvalues. Substituting it into X⊤XX^\top X and using the fact that U⊤U=IU^\top U = I gives X⊤X=VΣ⊤U⊤UΣV⊤=VΣ2V⊤X^\top X = V\Sigma^\top U^\top U\Sigma V^\top = V\Sigma^2V^\top. Comparing this with the form QΛQ⊤Q\Lambda Q^\top from the first section, we see that the eigenvectors of X⊤XX^\top X are the columns of VV, and its eigenvalues are the squared singular values σj2\sigma_j^2.

Two applications make the SVD indispensable. First, if you keep only the largest kk singular values and set the rest to zero, you get the best possible approximation of XX using a matrix of rank kk, which is the mathematical basis of PCA, image compression and recommender systems. Second, the pseudo-inverse X+=VΣ−1U⊤X^+ = V\Sigma^{-1}U^\top (inverting only the non-zero singular values) solves least-squares problems reliably even when X⊤XX^\top X cannot be inverted, which is what NumPy's lstsq does behind the scenes.

Code

Code: eigenvalues, covariance and SVD

Python · NumPy
import numpy as np

A = np.array([[2.0, 1.0], [1.0, 2.0]])
vals, vecs = np.linalg.eigh(A)              # eigh: for symmetric matrices, sorted ascending
print("eigenvalues:", vals)                 # [1, 3]
print("eigenvectors (columns):\n", vecs.round(3))
v = vecs[:, 1]
print("A v =", A @ v, " lambda v =", vals[1] * v)       # same vector
print("trace", np.trace(A), "= sum", vals.sum(), "| det", round(np.linalg.det(A), 6), "= product", vals.prod())

pts = np.array([[1, 2], [2, 4], [3, 6]], dtype=float)
S = np.cov(pts, rowvar=False)               # rows are observations
print("covariance matrix:\n", S)            # [[1, 2], [2, 4]]
print("its eigenvalues:", np.linalg.eigvalsh(S).round(6))   # [0, 5]

rng = np.random.default_rng(0)
X = rng.normal(size=(50, 3))
print("X^T X eigenvalues all >= 0 (PSD):", np.all(np.linalg.eigvalsh(X.T @ X) >= -1e-10))

U, sing, Vt = np.linalg.svd(X, full_matrices=False)
print("X == U diag(s) V^T ?", np.allclose(X, U @ np.diag(sing) @ Vt))
print("sigma^2:", (sing ** 2).round(3), " eig(X^T X):", np.linalg.eigvalsh(X.T @ X)[::-1].round(3))
X1 = sing[0] * np.outer(U[:, 0], Vt[0])     # best rank-1 approximation
print("rank-1 approximation error:", round(np.linalg.norm(X - X1) ** 2, 3), "= sigma2^2 + sigma3^2 =", round(sing[1] ** 2 + sing[2] ** 2, 3))
Open in playground ↗
Beginner

Practice: check yourself

Work each question out (on paper, in your head, or in Python), type the answer and press ✔ Check. Fractions like 1/4 are fine. Hints and a worked answer are there when you need them.

Question 1.
A=(2005)A = \begin{pmatrix} 2 & 0 \\ 0 & 5 \end{pmatrix}. What is its largest eigenvalue?
Question 2.
If Av=3vAv = 3v and v=(1,2)v = (1, 2), what is the second entry of AvAv?
Question 3.
A covariance matrix has eigenvalues 9 and 1. What fraction of the total variance does the first principal component explain? Give a decimal.
Check yourself

Quiz

1. If Av = 4v, then v is an eigenvector with eigenvalue…

2. Eigenvectors of a symmetric matrix (with distinct eigenvalues) are…

3. Why is XᵀX always positive semi-definite?

4. The eigenvalues of XᵀX equal…

Go deeper

📚 Further reading

Trusted, mostly free sources: official documentation, well-known textbooks and courses. When you want to confirm or go deeper on anything here, start with these.

Ready