Skip to content
LearnMLByDoing
Free

1.1 Linear transformations, eigenvectors and SVD in 3D

35 minFree lessonintermediateMMLStrang3B1B

Every 3×3 matrix turns the unit sphere into an ellipsoid, and its eigenvectors and singular vectors tell you exactly how.

01A matrix is a function on space

A 3×33\times 3 matrix A\tok{matrix_a}{A} is a rule that moves every point x∈R3\mathbf{x}\in\R^3 to AxA\mathbf{x}. Because the rule is linear, three outputs fix it completely: the places where the standard basis vectors e1,e2,e3\mathbf{e}_1,\mathbf{e}_2,\mathbf{e}_3 land.

Ax=x1 Ae1+x2 Ae2+x3 Ae3A\mathbf{x} = x_1\,\tok{basis_image}{A\mathbf{e}_1} + x_2\,\tok{basis_image}{A\mathbf{e}_2} + x_3\,\tok{basis_image}{A\mathbf{e}_3}
Any input is a combination of basis vectors, so its output is the same combination of their images.

Worked example. The viewport's matrix has columns Ae1=(1.6, 0.3, 0)A\mathbf{e}_1=(1.6,\,0.3,\,0), Ae2=(0.4, 0.9, 0.25)A\mathbf{e}_2=(0.4,\,0.9,\,0.25) and Ae3=(0, 0.2, 0.6)A\mathbf{e}_3=(0,\,0.2,\,0.6). Take x=(1,2,0)\mathbf{x}=(1,2,0): one step along e1\mathbf{e}_1 and two along e2\mathbf{e}_2. Then Ax=1⋅(1.6, 0.3, 0)+2⋅(0.4, 0.9, 0.25)=(2.4, 2.1, 0.5)A\mathbf{x} = 1\cdot(1.6,\,0.3,\,0) + 2\cdot(0.4,\,0.9,\,0.25) = (2.4,\,2.1,\,0.5). Row by row gives the same answer: the first output is 1.6⋅1+0.4⋅2+0⋅0=2.41.6\cdot1 + 0.4\cdot2 + 0\cdot0 = 2.4.

Loading figure
The same idea in two dimensions. Drag the cyan dot Ae1A\mathbf{e}_1 and the emerald dot Ae2A\mathbf{e}_2: they are the two columns. The whole grid follows, and the dashed unit circle becomes the cyan ellipse. Try putting both dots on one line and watch the plane collapse.

Those three images are the columns of AA. In the viewport they are the cyan, emerald and amber arrows. Every other point, including the 500 samples on the unit sphere, keeps the coordinates it had relative to e1,e2,e3\mathbf{e}_1,\mathbf{e}_2,\mathbf{e}_3, now measured along the new arrows.

Lines stay lines and the origin stays fixed, so the unit sphere {x:∥x∥=1}\{\mathbf{x} : \|\mathbf{x}\| = 1\} always lands on an ellipsoid, possibly flattened. That one shape summarises the whole matrix. The rest of the lesson reads it three ways: by volume, by invariant directions, and by its principal axes.

A[,]9 values

Row i produces output coordinate i; column j is the image of e_j.

Essence of Linear Algebra, 3Blue1Brown (Grant Sanderson), Ch. 3, Linear transformations and matrices

Mathematics for Machine Learning, Deisenroth, Faisal & Ong, Sec. 2.7

02Volume, orientation and rank

The unit cube spanned by e1,e2,e3\mathbf{e}_1,\mathbf{e}_2,\mathbf{e}_3 maps to the parallelepiped spanned by the columns of AA. Its signed volume is the determinant. Any region can be tiled by small cubes, and each cube is scaled by the same factor, so AA multiplies every volume by ∣det⁡A∣|\det A|.

vol⁡(A Ω)=∣det⁡A∣ vol⁡(Ω)\operatorname{vol}(A\,\Omega) = \left|\tok{determinant}{\det A}\right|\,\operatorname{vol}(\Omega)
Holds for any region, including the unit ball: the ellipsoid's volume is (4/3)π|det A|.

The sign records orientation. A negative determinant means the map contains a reflection: a right-handed frame comes out left-handed. A zero determinant means the columns are linearly dependent. Space is squashed onto a plane or a line, and the ellipsoid becomes a flat disc or a segment. The dimension of that image is the rank.

Why the matrix in the viewport has rank 21/4
  1. 1
    A=[101011112]A = \begin{bmatrix}1&0&1\\0&1&1\\1&1&2\end{bmatrix}

    The third column is the sum of the first two: Ae₃ = Ae₁ + Ae₂.

Lose two dimensions: make column 2 twice column 1 and set column 3 to zero.

Introduction to Linear Algebra, Gilbert Strang, Ch. 5, Determinants

Mathematics for Machine Learning, Deisenroth, Faisal & Ong, Sec. 4.1

03Eigenvectors: directions that only stretch

Most vectors are turned by AA. An eigenvector is a nonzero direction that comes out on its own line, scaled by its eigenvalue:

A v=λ v,v≠0A\,\tok{eigenvector}{\mathbf{v}} = \tok{eigenvalue}{\lambda}\,\tok{eigenvector}{\mathbf{v}},\qquad \mathbf{v}\neq\mathbf{0}

Watch it happen in 2D first. The widget sends a test vector x\mathbf{x} (white) round the unit circle and draws its image AxA\mathbf{x} (amber). Most of the time the two point in different directions. Twice per half-turn they line up, and an emerald tick marks the direction: that is an eigenvector, and ∥Ax∥\|A\mathbf{x}\| at that moment is its eigenvalue.

Loading figure
For A=[2112]A=\begin{bmatrix}2&1\\1&2\end{bmatrix} the sweep finds the diagonal (1,1)(1,1) with λ=3\lambda=3 and the anti-diagonal (1,−1)(1,-1) with λ=1\lambda=1. Switch to Shear: only one direction survives. Switch to Rotation: none does, and the readout turns complex.

Worked example (2×2). For the widget's matrix, A−λI=[2−λ112−λ]A-\lambda I=\begin{bmatrix}2-\lambda&1\\1&2-\lambda\end{bmatrix}. A nonzero v\mathbf{v} with (A−λI)v=0(A-\lambda I)\mathbf{v}=\mathbf{0} exists only if this matrix squashes the plane, that is, if its determinant is zero: (2−λ)2−1=0(2-\lambda)^2-1=0. So 2−λ=±12-\lambda=\pm1, which gives λ=3\lambda=3 and λ=1\lambda=1. Check: A(1,1)=(3,3)=3⋅(1,1)A(1,1)=(3,3)=3\cdot(1,1) and A(1,−1)=(1,−1)=1⋅(1,−1)A(1,-1)=(1,-1)=1\cdot(1,-1). The 3×3 recipe below is the same, with a cubic instead of a quadratic.

Finding them1/4
  1. 1
    Av=λv  ⟺  (A−λI) v=0A\mathbf{v} = \lambda\mathbf{v} \iff (A-\lambda I)\,\mathbf{v} = \mathbf{0}

    Move both terms to one side.

A real cubic always has at least one real root, so every real 3×33\times 3 matrix has at least one invariant line. The other two roots may form a complex-conjugate pair. Then AA rotates a plane, and no other real direction survives. The viewport draws only the real eigenvectors: emerald lines through the origin, with the bright segment reaching ±λv\pm\lambda\mathbf{v}.

Replace the two off-diagonal entries 11 and 00 by their average, 0.50.5 and 0.50.5, so that A=A⊤A=A^{\top}.

Turn the x–y plane instead of stretching it: A=[1.1−0.800.81.10000.6]A=\begin{bmatrix}1.1&-0.8&0\\0.8&1.1&0\\0&0&0.6\end{bmatrix}.

Essence of Linear Algebra, 3Blue1Brown (Grant Sanderson), Ch. 14, Eigenvectors and eigenvalues

Introduction to Linear Algebra, Gilbert Strang, Sec. 6.1

04Symmetric matrices: orthogonal eigenvectors

When A=A⊤A = A^{\top} the picture becomes clean. The spectral theorem guarantees real eigenvalues and an orthonormal basis of eigenvectors, so the matrix factors as

A=QΛQ⊤,Q⊤Q=I,Λ=diag⁡(λ1,λ2,λ3)A = Q\Lambda Q^{\top},\qquad Q^{\top}Q = I,\qquad \Lambda = \operatorname{diag}(\tok{eigenvalue}{\lambda_1},\lambda_2,\lambda_3)
The columns of Q are the eigenvectors. Orthonormal means each has length 1 and every pair is perpendicular, which is exactly what QᵀQ = I says.

Read the product right to left. Q⊤Q^{\top} rotates the eigenvectors onto the coordinate axes, Λ\Lambda stretches each axis by its eigenvalue, and QQ rotates back. In the viewport, the emerald eigenvector lines now run exactly along the ellipsoid's axes, and the semi-axis lengths equal ∣λi∣|\lambda_i|.

A symmetric matrix with every λi≥0\lambda_i \ge 0 is called positive semidefinite (PSD), and positive definite when every λi>0\lambda_i > 0. Then x⊤Ax≥0\mathbf{x}^{\top}A\mathbf{x} \ge 0 for every x\mathbf{x}: the function x↦x⊤Ax\mathbf{x}\mapsto\mathbf{x}^{\top}A\mathbf{x} is a bowl that curves up in every direction. The viewport's matrix has λ=2.33, 1.06, 0.50\lambda = 2.33,\ 1.06,\ 0.50, all positive. A covariance matrix is always PSD (lesson 1.3), and a Hessian that is PSD everywhere means a convex loss (lesson 1.4).

Mathematics for Machine Learning, Deisenroth, Faisal & Ong, Sec. 4.4

Introduction to Linear Algebra, Gilbert Strang, Sec. 6.4

05SVD: rotate, stretch, rotate

A general matrix has no orthogonal eigenbasis. There is always, however, an orthonormal input frame that AA maps onto an orthogonal output frame. That is the singular value decomposition, and every matrix has one:

A=UΣV⊤,Σ=diag⁡(σ1,σ2,σ3),σ1≥σ2≥σ3≥0A = \tok{svd}{U\Sigma V^{\top}},\qquad \Sigma = \operatorname{diag}(\tok{singular_value}{\sigma_1},\sigma_2,\sigma_3),\qquad \sigma_1\ge\sigma_2\ge\sigma_3\ge 0
Building it from AᵀA1/4
  1. 1
    A⊤A=V Σ2 V⊤A^{\top}A = V\,\Sigma^{2}\,V^{\top}

    AᵀA is symmetric, and xᵀAᵀAx = ‖Ax‖² ≥ 0, so it is positive semidefinite: its eigenvalues are real and not negative. The spectral theorem from the previous step applies, and V holds its orthonormal eigenvectors.

Scrub the SVD stage slider. From 0 to 1, V⊤V^{\top} rotates the sphere: the surface looks unchanged, but the coloured sample points move. From 1 to 2, Σ\Sigma stretches along the coordinate axes, so the ellipsoid is axis-aligned at stage 2. From 2 to 3, UU rotates it into place, and the cyan bars σiui\sigma_i\mathbf{u}_i become its semi-axes.

Load a matrix with det⁡A<0\det A<0 and stop at stage 1, then drag the SVD stage slider slowly from 1 to 2.

Mathematics for Machine Learning, Deisenroth, Faisal & Ong, Sec. 4.5

Introduction to Linear Algebra, Gilbert Strang, Ch. 7

06Power iteration and PCA

You rarely need every eigenvector. Power iteration finds the dominant one using only matrix-vector products. The viewport is running it now: the amber arrow xk\mathbf{x}_k starts at (1,1,1)/3(1,1,1)/\sqrt{3}, its image AxkA\mathbf{x}_k grows out of it as a faint arrow (it lands on the ellipsoid), and then xk\mathbf{x}_k turns onto that direction, shrunk back to length 1. The amber dots are the earlier iterates.

xk+1=Axk∥Axk∥,λ1≈xk⊤A xk\mathbf{x}_{k+1} = \frac{A\mathbf{x}_k}{\|A\mathbf{x}_k\|},\qquad \tok{eigenvalue}{\lambda_1} \approx \mathbf{x}_k^{\top}A\,\mathbf{x}_k
The second formula is the Rayleigh quotient: for a unit vector, how much A stretches it along itself. At an eigenvector it equals the eigenvalue exactly.

Write the start vector in the eigenbasis, x0=∑icivi\mathbf{x}_0 = \sum_i c_i\mathbf{v}_i. After kk steps the component along vi\mathbf{v}_i carries a factor λik\lambda_i^k, so everything except v1\mathbf{v}_1 shrinks relative to it like ∣λ2/λ1∣k|\lambda_2/\lambda_1|^k, provided c1≠0c_1 \neq 0. A large eigengap gives fast convergence. Two eigenvalues of equal magnitude give none.

A=PΛP−1  ⟹  Ak=PΛkP−1,Λk=diag⁡(λ1k,λ2k,λ3k)A = P\Lambda P^{-1} \;\Longrightarrow\; A^k = P\Lambda^k P^{-1},\qquad \Lambda^k = \operatorname{diag}(\lambda_1^k,\lambda_2^k,\lambda_3^k)
Diagonalisation: P holds the eigenvectors as columns. Applying A k times only raises each eigenvalue to the k-th power, which is why the largest one wins.

In the viewport the matrix is the symmetrised default, with λ=1.75, 0.90, 0.45\lambda = 1.75,\ 0.90,\ 0.45, so ∣λ2/λ1∣=0.51|\lambda_2/\lambda_1| = 0.51. Each step roughly halves the angle to the emerald v1\mathbf{v}_1: the HUD shows ∠(xk,v1)\angle(\mathbf{x}_k,\mathbf{v}_1) falling from 36.7∘36.7^\circ to under half a degree at k=7k=7, while the Rayleigh quotient climbs to 1.7521.752. Then the loop holds and starts again.

Give the two largest eigenvalues almost the same size: λ=2, 1.9, 0.5\lambda = 2,\ 1.9,\ 0.5.

Now separate them: λ=2, 0.6, 0.5\lambda = 2,\ 0.6,\ 0.5.

Principal component analysis applies the same idea to data. Centre the data matrix to get XcX_c (subtract each column's mean), form the covariance C=1n−1Xc⊤XcC = \tfrac{1}{n-1}X_c^{\top}X_c, and keep the eigenvectors with the largest eigenvalues. Equivalently, take the top right singular vectors of XcX_c. Projecting onto the top kk of them keeps more variance than any other kk-dimensional subspace.

Switch off the power iteration and show the reference data cloud the challenge uses, with its principal components.

X[,]900 values

One sample per row. Subtract the column means before anything else.

components[,]6 values

Orthonormal rows, largest variance first.

Z = X_c @ components.T[,]600 values

Coordinates of each sample in the principal basis.

Mathematics for Machine Learning, Deisenroth, Faisal & Ong, Sec. 10.2

Introduction to Linear Algebra, Gilbert Strang, Sec. 7.3

07Low-rank approximation: keep the big singular values

The SVD writes any matrix as a sum of simple pieces, one per singular value. Each piece σiuivi⊤\sigma_i\mathbf{u}_i\mathbf{v}_i^{\top} is a rank-1 matrix: a column times a row. Keeping only the kk largest pieces gives a cheaper matrix AkA_k, and no other rank-kk matrix is closer to AA.

Ak=∑i=1kσi uivi⊤,∥A−Ak∥2=σk+1,∥A−Ak∥F=σk+12+⋯+σr2A_k = \sum_{i=1}^{k}\tok{singular_value}{\sigma_i}\,\mathbf{u}_i\mathbf{v}_i^{\top},\qquad \|A-A_k\|_2 = \sigma_{k+1},\qquad \|A-A_k\|_F = \sqrt{\sigma_{k+1}^2+\dots+\sigma_r^2}
Eckart–Young: the truncated SVD is the best rank-k approximation in both norms. The error is exactly what you threw away.

The viewport keeps k=2k=2 of the default matrix's three singular values, 1.75, 0.90, 0.451.75,\ 0.90,\ 0.45. The ellipsoid has flattened into a disc along its shortest axis, and the HUD reports the error ∥A−A2∥2=σ3=0.453\|A-A_2\|_2 = \sigma_3 = 0.453. Move the Keep top-k slider to 1 and the disc shrinks to a segment, with error σ2=0.897\sigma_2 = 0.897.

Loading figure
A 24×24 matrix built from three patterns (a bar, a wave and a ramp) plus a little noise. Raise kk: at k=3k=3 the picture is back with 99.2% of the energy ∑σi2\sum\sigma_i^2, stored in 3⋅49=1473\cdot49=147 numbers instead of 576. Beyond that you only add the noise back.

For data, the same bookkeeping is the explained variance ratio. The PCA eigenvalues λi\lambda_i are variances, and λi/∑jλj\lambda_i/\sum_j\lambda_j is the share of the total variance that component ii keeps. Plotting these shares in decreasing order gives a scree plot. For the challenge's cloud the shares are about 85%85\%, 14%14\% and 1.5%1.5\%, so two components keep about 98%98\%.

Keep only the largest singular value: k=1k=1.

Introduction to Linear Algebra, Gilbert Strang, Sec. 7.1

Mathematics for Machine Learning, Deisenroth, Faisal & Ong, Sec. 4.6

Compiling scene
Loading editor

Questions learners ask

What is the difference between eigenvectors and singular vectors?
An eigenvector v satisfies Av = λv, so it keeps its own direction. It exists only for square matrices and need not form an orthogonal set. Singular vectors come in pairs: A maps the right singular vector vᵢ to σᵢuᵢ, where uᵢ is the left singular vector. Both sets are orthonormal and exist for any matrix, including rectangular ones. For a symmetric positive semidefinite matrix the two notions coincide.
Why does PCA use the eigenvectors of the covariance matrix?
The variance of the centred data along a unit direction w is wᵀCw, where C is the covariance matrix. Maximising this quadratic form over unit vectors gives the top eigenvector of C, and repeating under orthogonality constraints gives the next ones. The same directions are the right singular vectors of the centred data matrix, which is how most libraries compute them.
When does power iteration fail or converge slowly?
The error shrinks like |λ₂/λ₁|ᵏ, so convergence is slow when the two largest eigenvalues are close in magnitude. It fails when they have equal magnitude, for example λ and −λ, or a complex pair. It also fails if the start vector has no component along the dominant eigenvector, although rounding errors usually introduce one. Shifts, deflation, or Krylov methods such as Lanczos fix these cases.

Next in Mathematical Foundations

1.2Gradients, Jacobians and the chain ruleLocal linear approximations of functions between vector spaces, and why backprop is just the chain rule applied in order.

Sources

  • Mathematics for Machine Learning, Deisenroth, Faisal & Ong
  • Introduction to Linear Algebra, Gilbert Strang
  • Essence of Linear Algebra, 3Blue1Brown (Grant Sanderson)