Linear Algebra — 05 · Inner Products, the Spectral Theorem and the SVD

Linear Algebra 02 defined a vector space with only addition and scaling: an abstract vector space has no lengths and no angles until you add them. This post adds them with an inner product — the dot product of $\mathbb{R}^n$ is the model — and three big results follow. Orthogonal projection gives the best approximation from a subspace, which is the whole theory of least squares. The spectral theorem says every real symmetric matrix is diagonal in an orthonormal basis — the eigen-story of Linear Algebra 04 with no defective cases and perpendicular eigenvectors. And the singular value decomposition extends that to every matrix, square or not: any linear map is a rotation, a stretch along perpendicular axes, and another rotation. The SVD gives the best low-rank approximation, the pseudoinverse and principal component analysis. This is the last post of the base series; a table at the end lists planned extensions.

Series map: 00 Vectors & Linear Systems → 01 Matrix Algebra, Inverses & LU → 02 Vector Spaces, Basis & Dimension → 03 Linear Maps, Change of Basis & Determinants → 04 Eigenvalues & Diagonalization → 05 Inner Products, Spectral Theorem & SVD (this post).

---

Learning Outcome

• State the inner product axioms, and prove the Cauchy–Schwarz and triangle inequalities.
• Use orthonormal bases: coordinates by inner products, Pythagoras, Parseval.
• Project onto a subspace, prove the best-approximation property, and run Gram–Schmidt to get $A = QR$.
• Solve least-squares problems with the normal equations and with QR, and fit a line to data.
• Recognise orthogonal matrices, state the spectral theorem, and sketch its proof.
• Test a symmetric matrix for positive definiteness in four equivalent ways, and find the principal axes of a quadratic form.
• State the SVD, compute it for a $2 \times 2$ example, and read it geometrically as rotate–stretch–rotate.
• Use the SVD for norms, condition numbers, best low-rank approximation (Eckart–Young), the pseudoinverse and PCA.

---

Chapter 1 — Inner products and norms

Terminology

• Inner product on a real vector space $V$ — a function $\langle u, v\rangle \in \mathbb{R}$ that is symmetric, linear in each argument, and positive definite (axioms below).
• Inner product space — a vector space together with an inner product.
• Norm $\lVert v\rVert = \sqrt{\langle v, v\rangle}$ — the length of $v$. A unit vector has norm 1.
• Orthogonal — $\langle u, v\rangle = 0$, written $u \perp v$.
• Orthonormal list — pairwise orthogonal unit vectors.
• Orthogonal complement $W^\perp = \{v : \langle v, w\rangle = 0 \text{ for all } w \in W\}$.
• Orthogonal matrix — a square real matrix $Q$ with $Q^TQ = I$.

Axioms and examples

An inner product on a real vector space satisfies, for all $u, v, w$ and scalars $c$:

1. Symmetry: $\langle u, v\rangle = \langle v, u\rangle$.
2. Linearity: $\langle u + cv, w\rangle = \langle u, w\rangle + c\langle v, w\rangle$ (and so, by symmetry, linear in the second slot too).
3. Positive definiteness: $\langle v, v\rangle \ge 0$, with equality only for $v = 0$.

Examples:

• Dot product on $\mathbb{R}^n$: $\langle x, y\rangle = x^Ty = \sum x_i y_i$. This is the default in this post.
• Weighted dot product: $\langle x, y\rangle = \sum w_i x_i y_i$ with all $w_i > 0$. More generally $\langle x, y\rangle = x^TMy$ for any symmetric positive definite $M$ (Chapter 6).
• Functions: on $C[0,1]$, $\langle f, g\rangle = \int_0^1 f(t)g(t)\,dt$. For example $\langle 1, t - \tfrac12\rangle = \int_0^1 (t - \tfrac12)\,dt = 0$: the constant 1 and $t - \frac12$ are orthogonal, and $\lVert t - \tfrac12\rVert^2 = \frac{1}{12}$.
• Matrices: $\langle A, B\rangle = \operatorname{tr}(A^TB) = \sum_{i,j} a_{ij}b_{ij}$ (the Frobenius inner product).

Over $\mathbb{C}$ the symmetry axiom becomes $\langle u, v\rangle = \overline{\langle v, u\rangle}$ and the standard product is $\sum x_i \overline{y_i}$; everything below has a complex version with $A^T$ replaced by the conjugate transpose $A^*$.

Cauchy–Schwarz and the triangle inequality

Theorem 1 (Cauchy–Schwarz). $\lvert\langle u, v\rangle\rvert \le \lVert u\rVert\,\lVert v\rVert$, with equality if and only if $u$ and $v$ are linearly dependent.

Proof. If $v = 0$ both sides are 0. Otherwise, for every real $t$,

$$0 \le \lVert u - tv\rVert^2 = \lVert u\rVert^2 - 2t\langle u, v\rangle + t^2\lVert v\rVert^2.$$

A quadratic in $t$ with positive leading coefficient that is never negative has at most one real root, so its discriminant is $\le 0$: $4\langle u, v\rangle^2 - 4\lVert u\rVert^2\lVert v\rVert^2 \le 0$. Equality means the discriminant is 0, so for some $t$ the quadratic is 0, that is $u = tv$; conversely $u = tv$ gives equality directly. ∎

Cauchy–Schwarz makes angles possible: define $\theta \in [0, \pi]$ by $\cos\theta = \frac{\langle u, v\rangle}{\lVert u\rVert\lVert v\rVert}$, a number in $[-1, 1]$. Example: $u = (1, 2, 2)$, $v = (3, 0, 4)$ have $u \cdot v = 11$, $\lVert u\rVert = 3$, $\lVert v\rVert = 5$, so $\cos\theta = 11/15$ and $\theta \approx 42.8°$.

Theorem 2 (triangle inequality). $\lVert u + v\rVert \le \lVert u\rVert + \lVert v\rVert$.

Proof. $\lVert u + v\rVert^2 = \lVert u\rVert^2 + 2\langle u, v\rangle + \lVert v\rVert^2 \le \lVert u\rVert^2 + 2\lVert u\rVert\lVert v\rVert + \lVert v\rVert^2 = (\lVert u\rVert + \lVert v\rVert)^2$, using Cauchy–Schwarz in the middle. Take square roots. ∎

The same expansion gives Pythagoras: if $u \perp v$ then $\lVert u + v\rVert^2 = \lVert u\rVert^2 + \lVert v\rVert^2$.

---

Chapter 2 — Orthogonality and projection

Orthonormal bases

Proposition 3. An orthogonal list of nonzero vectors is linearly independent.

Proof. If $\sum c_i v_i = 0$, take the inner product with $v_j$: every term except $c_j\langle v_j, v_j\rangle$ vanishes, so $c_j\lVert v_j\rVert^2 = 0$ and $c_j = 0$. ∎

The same computation shows why orthonormal bases are so convenient. If $q_1, \dots, q_n$ is an orthonormal basis, then for every $v$:

$$v = \sum_{i=1}^n \langle v, q_i\rangle\, q_i, \qquad \lVert v\rVert^2 = \sum_{i=1}^n \langle v, q_i\rangle^2.$$

Coordinates are just inner products — no linear system to solve. The second formula is Parseval's identity.

Orthogonal projection onto a subspace

Let $W$ be a subspace with orthonormal basis $q_1, \dots, q_k$. The orthogonal projection of $v$ onto $W$ is

$$P_W v = \sum_{i=1}^{k} \langle v, q_i\rangle\, q_i.$$

The residual $v - P_W v$ is orthogonal to every $q_j$ (take the inner product and use orthonormality), hence to all of $W$. So every $v$ splits uniquely as $v = P_W v + (v - P_W v)$ with the first part in $W$ and the second in $W^\perp$, and $\dim W + \dim W^\perp = \dim V$.

Theorem 4 (best approximation). $P_W v$ is the unique closest point of $W$ to $v$: for every $w \in W$ with $w \neq P_W v$,

$$\lVert v - w\rVert > \lVert v - P_W v\rVert.$$

Proof. Write $v - w = (v - P_W v) + (P_W v - w)$. The first part is in $W^\perp$, the second in $W$, so by Pythagoras $\lVert v - w\rVert^2 = \lVert v - P_W v\rVert^2 + \lVert P_W v - w\rVert^2$, and the last term is positive when $w \neq P_W v$. ∎

In matrix form. If $Q$ is the $n \times k$ matrix with orthonormal columns $q_i$, then $Q^TQ = I_k$ and the projection matrix is $P = QQ^T$. If the columns of $A$ are any basis of $W$ (not orthonormal), then

$$P = A(A^TA)^{-1}A^T.$$

Every projection matrix satisfies $P^2 = P$ and $P^T = P$. Projection onto a single line through $a$ is $\frac{aa^T}{a^Ta}$; for example the projection of $b = (3, 0, 3)$ onto the line through $a = (1, 2, 2)$ is $\frac{a \cdot b}{a \cdot a}a = \frac{9}{9}a = (1, 2, 2)$, with residual $(2, -2, 1) \perp a$.

Common pitfall: $\sum \langle v, q_i\rangle q_i$ is the projection only when the $q_i$ are orthonormal. With a non-orthogonal basis, adding up the one-dimensional projections double-counts, and the result is not the closest point. Use $A(A^TA)^{-1}A^T$, or orthonormalise first.

---

Chapter 3 — Gram–Schmidt and QR

The algorithm

Given independent vectors $v_1, \dots, v_n$, Gram–Schmidt produces an orthonormal list $q_1, \dots, q_n$ with the same span at every stage: $\operatorname{span}(q_1, \dots, q_j) = \operatorname{span}(v_1, \dots, v_j)$ for each $j$. At step $j$, subtract from $v_j$ its projection onto the span of the earlier $q$'s, then normalise:

$$w_j = v_j - \sum_{i < j} \langle v_j, q_i\rangle\, q_i, \qquad q_j = \frac{w_j}{\lVert w_j\rVert}.$$

$w_j \neq 0$ because $v_j$ is not in the span of $v_1, \dots, v_{j-1}$. So every finite-dimensional inner product space has an orthonormal basis.

Worked example. $v_1 = (1, 1, 0)$, $v_2 = (1, 0, 1)$, $v_3 = (0, 1, 1)$.

• $q_1 = \frac{1}{\sqrt2}(1, 1, 0)$.
• $\langle v_2, q_1\rangle = \frac{1}{\sqrt2}$, so $w_2 = (1, 0, 1) - \frac12(1, 1, 0) = (\frac12, -\frac12, 1)$, with $\lVert w_2\rVert = \sqrt{3/2}$. Then $q_2 = \frac{1}{\sqrt6}(1, -1, 2)$.
• $\langle v_3, q_1\rangle = \frac{1}{\sqrt2}$ and $\langle v_3, q_2\rangle = \frac{1}{\sqrt6}$, so $w_3 = (0, 1, 1) - \frac12(1, 1, 0) - \frac16(1, -1, 2) = (-\frac23, \frac23, \frac23)$, and $q_3 = \frac{1}{\sqrt3}(-1, 1, 1)$.

Check: $q_1 \cdot q_2 = \frac{1 - 1 + 0}{\sqrt{12}} = 0$, $q_1 \cdot q_3 = \frac{-1 + 1 + 0}{\sqrt6} = 0$, $q_2 \cdot q_3 = \frac{-1 - 1 + 2}{\sqrt{18}} = 0$.

QR factorisation

Gram–Schmidt, written as matrices, is a factorisation. Each $v_j$ is a combination of $q_1, \dots, q_j$ only, with coefficients $r_{ij} = \langle v_j, q_i\rangle$ ($i < j$) and $r_{jj} = \lVert w_j\rVert$. So

$$A = QR,$$

with $Q$ having orthonormal columns and $R$ upper triangular with positive diagonal. For the example, $R = Q^TA$:

$$R = \begin{pmatrix} \sqrt2 & 1/\sqrt2 & 1/\sqrt2 \\ 0 & \sqrt{3/2} & 1/\sqrt6 \\ 0 & 0 & 2/\sqrt3 \end{pmatrix} \approx \begin{pmatrix} 1.4142 & 0.7071 & 0.7071 \\ 0 & 1.2247 & 0.4082 \\ 0 & 0 & 1.1547 \end{pmatrix}.$$

Watch out: Classical Gram–Schmidt loses orthogonality in floating point when the columns are nearly dependent. Libraries compute QR with Householder reflections (or use modified Gram–Schmidt, which subtracts each projection from the updated vector). The factorisation is the same; the arithmetic is more stable.

---

Chapter 4 — Least squares

The problem

An overdetermined system $Ax = b$ ($A$ is $m \times n$ with $m > n$) usually has no solution: $b$ is not in the column space $C(A)$. The least-squares solution $\hat x$ minimises $\lVert b - Ax\rVert$. By Theorem 4, $A\hat x$ must be the projection of $b$ onto $C(A)$, so the residual $e = b - A\hat x$ is orthogonal to every column of $A$: $A^Te = 0$. That gives the normal equations

$$A^TA\,\hat x = A^Tb.$$

If the columns of $A$ are independent, $A^TA$ is invertible (if $A^TAx = 0$ then $x^TA^TAx = \lVert Ax\rVert^2 = 0$, so $Ax = 0$, so $x = 0$), and $\hat x = (A^TA)^{-1}A^Tb$ is unique.

Worked example — fitting a line

Fit $y = c_0 + c_1 x$ to the points $(1, 1), (2, 2), (3, 2), (4, 5)$. Each point gives one equation $c_0 + c_1 x_i = y_i$:

$$A = \begin{pmatrix} 1 & 1 \\ 1 & 2 \\ 1 & 3 \\ 1 & 4 \end{pmatrix}, \quad b = \begin{pmatrix} 1 \\ 2 \\ 2 \\ 5 \end{pmatrix}, \quad A^TA = \begin{pmatrix} 4 & 10 \\ 10 & 30 \end{pmatrix}, \quad A^Tb = \begin{pmatrix} 10 \\ 31 \end{pmatrix}.$$

$\det(A^TA) = 120 - 100 = 20$, so

$$\hat c = \frac{1}{20}\begin{pmatrix} 30 & -10 \\ -10 & 4 \end{pmatrix}\begin{pmatrix} 10 \\ 31 \end{pmatrix} = \frac{1}{20}\begin{pmatrix} -10 \\ 24 \end{pmatrix} = \begin{pmatrix} -0.5 \\ 1.2 \end{pmatrix}.$$

The best line is $y = -0.5 + 1.2x$. The fitted values are $(0.7, 1.9, 3.1, 4.3)$ and the residuals $e = (0.3, 0.1, -1.1, 0.7)$. Checks: $A^Te = 0$, that is, the residuals sum to 0 and $\sum x_i e_i = 0.3 + 0.2 - 3.3 + 2.8 = 0$. The minimum sum of squared errors is $0.09 + 0.01 + 1.21 + 0.49 = 1.8$; no other line does better.

Least squares with QR

If $A = QR$ (reduced: $Q$ is $m \times n$), the normal equations $R^TQ^TQR\hat x = R^TQ^Tb$ simplify to

$$R\hat x = Q^Tb,$$

solved by back substitution. This is the method used in practice. Forming $A^TA$ squares the condition number (Chapter 7), which can destroy half the significant digits; QR avoids it.

---

Chapter 5 — Orthogonal matrices and the spectral theorem

Orthogonal matrices

A square $Q$ with $Q^TQ = I$ has orthonormal columns and $Q^{-1} = Q^T$. It preserves inner products, lengths and angles: $(Qx)\cdot(Qy) = x^TQ^TQy = x \cdot y$. Taking determinants, $\det(Q)^2 = 1$, so $\det Q = \pm 1$. In $\mathbb{R}^2$ the orthogonal matrices are exactly the rotations ($\det = 1$) and the reflections ($\det = -1$) of Linear Algebra 03. Products and inverses of orthogonal matrices are orthogonal.

A change of basis to an orthonormal basis uses an orthogonal $P$, so $P^{-1}AP = P^TAP$: no inverse to compute.

The spectral theorem

Theorem 5 (spectral theorem, real symmetric case). If $A$ is a real symmetric $n \times n$ matrix ($A^T = A$), then:

1. all eigenvalues of $A$ are real;
2. eigenvectors for distinct eigenvalues are orthogonal;
3. $A$ has an orthonormal basis of eigenvectors, so $A = Q\Lambda Q^T$ with $Q$ orthogonal and $\Lambda$ real diagonal.

Conversely, any $Q\Lambda Q^T$ is symmetric, so a real matrix is orthogonally diagonalizable if and only if it is symmetric.

Proof sketch. The key identity is $\langle Ax, y\rangle = x^TA^Ty = x^TAy = \langle x, Ay\rangle$.

(1) Let $Av = \lambda v$ with $v \in \mathbb{C}^n$ nonzero. The number $\bar v^TAv$ equals its own complex conjugate (conjugate it, use that $A$ is real, then transpose the $1 \times 1$ result and use $A^T = A$), so it is real. It also equals $\lambda\,\bar v^Tv = \lambda\sum\lvert v_i\rvert^2$, and $\sum\lvert v_i\rvert^2 > 0$ is real. So $\lambda$ is real.

(2) If $Av_1 = \lambda_1 v_1$ and $Av_2 = \lambda_2 v_2$, then $\lambda_1\langle v_1, v_2\rangle = \langle Av_1, v_2\rangle = \langle v_1, Av_2\rangle = \lambda_2\langle v_1, v_2\rangle$, so $(\lambda_1 - \lambda_2)\langle v_1, v_2\rangle = 0$.

(3) Induction on $n$. By (1) there is a real eigenvalue $\lambda_1$ with a unit eigenvector $q_1$. The complement $W = q_1^\perp$ is mapped into itself: if $w \perp q_1$ then $\langle Aw, q_1\rangle = \langle w, Aq_1\rangle = \lambda_1\langle w, q_1\rangle = 0$. On the $(n-1)$-dimensional space $W$, $A$ still satisfies $\langle Ax, y\rangle = \langle x, Ay\rangle$, so by induction $W$ has an orthonormal basis of eigenvectors $q_2, \dots, q_n$. Together with $q_1$ this is an orthonormal eigenbasis of $\mathbb{R}^n$. ∎

Worked example. $B = \begin{pmatrix} 2 & 1 & 1 \\ 1 & 2 & 1 \\ 1 & 1 & 2 \end{pmatrix}$ from Linear Algebra 04 has eigenvalues $4, 1, 1$. The eigenvector $(1,1,1)$ for 4 is automatically orthogonal to the eigenplane $x + y + z = 0$ for 1. Inside that plane, Linear Algebra 04 used $(-1, 1, 0)$ and $(-1, 0, 1)$, which are not orthogonal to each other — Gram–Schmidt fixes that. An orthonormal choice is

$$q_1 = \tfrac{1}{\sqrt3}(1, 1, 1), \quad q_2 = \tfrac{1}{\sqrt2}(1, -1, 0), \quad q_3 = \tfrac{1}{\sqrt6}(1, 1, -2), \qquad Q^TBQ = \operatorname{diag}(4, 1, 1).$$

The spectral decomposition writes $A$ as a sum of rank-one projections:

$$A = \lambda_1 q_1q_1^T + \lambda_2 q_2q_2^T + \dots + \lambda_n q_nq_n^T.$$

For $B$: $B = 4q_1q_1^T + q_2q_2^T + q_3q_3^T$. Since $q_2q_2^T + q_3q_3^T = I - q_1q_1^T$, this is $B = I + 3q_1q_1^T$.

Trick: For symmetric matrices, eigenvectors from different eigenvalues are orthogonal for free. You only need Gram–Schmidt inside an eigenspace of dimension 2 or more.

---

Chapter 6 — Positive definite matrices and quadratic forms

Four equivalent tests

A symmetric matrix $A$ is positive definite if $x^TAx > 0$ for every $x \neq 0$, and positive semidefinite if $x^TAx \ge 0$ for every $x$.

Theorem 6. For a real symmetric $n \times n$ matrix $A$, the following are equivalent:

1. $A$ is positive definite;
2. every eigenvalue of $A$ is positive;
3. every leading principal minor (the determinant of the top-left $k \times k$ block, $k = 1, \dots, n$) is positive (Sylvester's criterion);
4. elimination without row swaps succeeds with every pivot positive;
5. $A = R^TR$ for some invertible $R$ — for example the Cholesky factor, upper triangular with positive diagonal.

Proof of 1 ⇔ 2. Write $A = Q\Lambda Q^T$ and put $y = Q^Tx$ (a change to the eigenvector basis; $y \neq 0$ exactly when $x \neq 0$). Then

$$x^TAx = y^T\Lambda y = \lambda_1 y_1^2 + \dots + \lambda_n y_n^2,$$

which is positive for all $y \neq 0$ exactly when every $\lambda_i > 0$. For 5 ⇒ 1: $x^TR^TRx = \lVert Rx\rVert^2 > 0$ when $x \neq 0$ because $R$ is invertible. The links to 3 and 4 go through the LU factorisation of Linear Algebra 01: the $k$-th pivot equals the ratio of the $k$-th and $(k-1)$-th leading minors. ∎

Worked example.

$$K = \begin{pmatrix} 2 & -1 & 0 \\ -1 & 2 & -1 \\ 0 & -1 & 2 \end{pmatrix}.$$

• Leading minors: $2$, $4 - 1 = 3$, $\det K = 4$. All positive.
• Pivots: $2$, $\frac32$, $\frac43$ — the ratios $\frac21, \frac32, \frac43$ of consecutive minors.
• Eigenvalues: $2 - \sqrt2 \approx 0.586$, $2$, $2 + \sqrt2 \approx 3.414$.
• The quadratic form is a sum of squares: $x^TKx = 2x^2 - 2xy + 2y^2 - 2yz + 2z^2 = x^2 + (x - y)^2 + (y - z)^2 + z^2$, which is $0$ only when $x = y = z = 0$.

All four tests agree: $K$ is positive definite. (This matrix is the second-difference matrix that appears when a differential equation $-u'' = f$ is discretised.)

Common pitfall: Positive entries do not make a matrix positive definite, and negative entries do not prevent it. $\begin{pmatrix} 1 & 2 \\ 2 & 3\end{pmatrix}$ has all entries positive but determinant $-1$, so its eigenvalues are $2 \pm \sqrt5$, one of them negative; $K$ above has negative entries and is positive definite.

Quadratic forms and principal axes

A quadratic form is $q(x) = x^TAx$ with $A$ symmetric (any cross term $bxy$ is split evenly between the two off-diagonal entries). The spectral theorem rotates the axes so the cross terms disappear.

Worked example. $q(x, y) = 5x^2 + 4xy + 2y^2$ has $A = \begin{pmatrix} 5 & 2 \\ 2 & 2 \end{pmatrix}$, with trace 7 and determinant 6, so eigenvalues $6$ and $1$. Unit eigenvectors: $\frac{1}{\sqrt5}(2, 1)$ for 6 and $\frac{1}{\sqrt5}(-1, 2)$ for 1. In the rotated coordinates $u = \frac{2x + y}{\sqrt5}$, $v = \frac{-x + 2y}{\sqrt5}$,

$$q = 6u^2 + v^2.$$

(Check at $(x, y) = (1, 0)$: $u = 2/\sqrt5$, $v = -1/\sqrt5$, and $6 \cdot \frac45 + \frac15 = 5 = q(1, 0)$.) The level curve $q = 6$ is the ellipse $u^2 + v^2/6 = 1$: semi-axis $1$ along $(2, 1)$ and $\sqrt6$ along $(-1, 2)$. The principal axes are the eigenvectors, and the semi-axes are $\sqrt{c/\lambda_i}$ for the level $q = c$. In calculus the same idea classifies critical points: a positive definite Hessian means a local minimum.

---

Chapter 7 — The singular value decomposition

The theorem

Diagonalization needs a square matrix, and even then it can fail or need complex numbers. The SVD always works.

Theorem 7 (SVD). Every real $m \times n$ matrix $A$ of rank $r$ can be written as

$$A = U\Sigma V^T,$$

where $U$ ($m \times m$) and $V$ ($n \times n$) are orthogonal and $\Sigma$ is $m \times n$ with diagonal entries $\sigma_1 \ge \sigma_2 \ge \dots \ge \sigma_r > 0$ and zeros elsewhere. The $\sigma_i$ are the singular values (uniquely determined by $A$); the columns $v_i$ of $V$ and $u_i$ of $U$ are the right and left singular vectors, and $Av_i = \sigma_i u_i$.

Proof. $A^TA$ is symmetric and positive semidefinite ($x^TA^TAx = \lVert Ax\rVert^2 \ge 0$), so by the spectral theorem it has an orthonormal eigenbasis $v_1, \dots, v_n$ with eigenvalues $\lambda_1 \ge \dots \ge \lambda_n \ge 0$. Exactly $r$ of them are positive, because $A^TA$ has the same null space as $A$ (shown in Chapter 4), hence rank $r$. Put $\sigma_i = \sqrt{\lambda_i}$ and, for $i \le r$, $u_i = Av_i/\sigma_i$. These are orthonormal:

$$u_i \cdot u_j = \frac{v_i^TA^TAv_j}{\sigma_i\sigma_j} = \frac{\lambda_j\, v_i \cdot v_j}{\sigma_i\sigma_j} = \begin{cases} 1 & i = j \\ 0 & i \neq j. \end{cases}$$

Extend $u_1, \dots, u_r$ to an orthonormal basis of $\mathbb{R}^m$. Then $Av_i = \sigma_i u_i$ for $i \le r$ and $Av_i = 0$ for $i > r$, which is $AV = U\Sigma$, that is $A = U\Sigma V^T$. ∎

Dropping the zero parts gives the compact form $A = \sum_{i=1}^{r}\sigma_i u_i v_i^T$, a sum of $r$ rank-one matrices. The SVD also hands you orthonormal bases for all four fundamental subspaces of Linear Algebra 02: $v_1, \dots, v_r$ for the row space, $v_{r+1}, \dots, v_n$ for the null space, $u_1, \dots, u_r$ for the column space, and $u_{r+1}, \dots, u_m$ for the left null space.

Worked example

$$A = \begin{pmatrix} 3 & 0 \\ 4 & 5 \end{pmatrix}, \qquad A^TA = \begin{pmatrix} 25 & 20 \\ 20 & 25 \end{pmatrix}.$$

$A^TA$ has trace 50 and determinant $625 - 400 = 225$, so eigenvalues $45$ and $5$, with unit eigenvectors $v_1 = \frac{1}{\sqrt2}(1, 1)$ and $v_2 = \frac{1}{\sqrt2}(-1, 1)$. The singular values are $\sigma_1 = \sqrt{45} = 3\sqrt5 \approx 6.708$ and $\sigma_2 = \sqrt5 \approx 2.236$. Then

$$u_1 = \frac{Av_1}{\sigma_1} = \frac{(3, 9)/\sqrt2}{3\sqrt5} = \frac{1}{\sqrt{10}}(1, 3), \qquad u_2 = \frac{Av_2}{\sigma_2} = \frac{(-3, 1)/\sqrt2}{\sqrt5} = \frac{1}{\sqrt{10}}(-3, 1),$$

$$A = \underbrace{\frac{1}{\sqrt{10}}\begin{pmatrix} 1 & -3 \\ 3 & 1 \end{pmatrix}}_{U} \underbrace{\begin{pmatrix} 3\sqrt5 & 0 \\ 0 & \sqrt5 \end{pmatrix}}_{\Sigma} \underbrace{\frac{1}{\sqrt2}\begin{pmatrix} 1 & 1 \\ -1 & 1 \end{pmatrix}}_{V^T}.$$

Checks: $\sigma_1\sigma_2 = 15 = \det A$ (here $\det U = \det V = 1$), and $\sigma_1^2 + \sigma_2^2 = 50 = 9 + 0 + 16 + 25$, the sum of the squared entries.

Watch out: The singular values of $A$ are not its eigenvalues. This $A$ is triangular with eigenvalues 3 and 5, but singular values $6.708$ and $2.236$. For a symmetric matrix the singular values are the absolute values of the eigenvalues (more generally this holds for normal matrices, those with $A^TA = AA^T$), and for a positive semidefinite matrix they are exactly the eigenvalues.

Geometry: rotate, stretch, rotate

Read $A = U\Sigma V^T$ from right to left as three steps applied to the unit circle:

1. $V^T$ is orthogonal: it rotates (or reflects) the plane, carrying $v_1, v_2$ to $e_1, e_2$. Here $V^T$ is rotation by $-45°$. The circle stays a circle.
2. $\Sigma$ stretches along the axes by $\sigma_1$ and $\sigma_2$. The circle becomes an axis-aligned ellipse with semi-axes $6.708$ and $2.236$.
3. $U$ rotates again, carrying $e_1, e_2$ to $u_1, u_2$. Here $U$ is rotation by about $71.6°$ (the angle of $(1, 3)$).

So every linear map of $\mathbb{R}^n$ sends the unit sphere to an ellipsoid (flattened when $A$ is singular); the singular values are its semi-axes, the $u_i$ their directions, and the $v_i$ the unit vectors that land on them. In general $U$ and $V$ may include a reflection; both can be chosen as rotations exactly when $\det A \ge 0$ (for square $A$).

Norms and conditioning

• Spectral norm: $\lVert A\rVert_2 = \max_{\lVert x\rVert = 1}\lVert Ax\rVert = \sigma_1$ — the longest semi-axis.
• Frobenius norm: $\lVert A\rVert_F = \sqrt{\sum a_{ij}^2} = \sqrt{\sigma_1^2 + \dots + \sigma_r^2}$ (orthogonal matrices do not change it).
• Condition number of an invertible $A$: $\kappa(A) = \sigma_1/\sigma_n$, the ratio of the longest to the shortest semi-axis. For the example $\kappa = 3\sqrt5/\sqrt5 = 3$. Solving $Ax = b$ can amplify relative errors in $b$ by up to $\kappa$; since $\sigma_i(A^TA) = \sigma_i^2$, forming the normal equations squares it. This, and not the size of $\det A$, measures closeness to singularity (Linear Algebra 03, Chapter 7).

---

Chapter 8 — Using the SVD

Low-rank approximation

Theorem 8 (Eckart–Young, statement). Let $A = \sum_{i=1}^r \sigma_i u_i v_i^T$ and, for $k < r$, $A_k = \sum_{i=1}^k \sigma_i u_i v_i^T$. Among all matrices $B$ of rank at most $k$,

$$\min_{\operatorname{rank} B \le k}\lVert A - B\rVert_2 = \lVert A - A_k\rVert_2 = \sigma_{k+1}, \qquad \min_{\operatorname{rank} B \le k}\lVert A - B\rVert_F = \lVert A - A_k\rVert_F = \sqrt{\sigma_{k+1}^2 + \dots + \sigma_r^2}.$$

Keep the $k$ largest singular triples and drop the rest; nothing of rank $k$ does better. For the example,

$$A_1 = 3\sqrt5\, u_1v_1^T = \frac{3}{2}\begin{pmatrix} 1 & 1 \\ 3 & 3 \end{pmatrix} = \begin{pmatrix} 1.5 & 1.5 \\ 4.5 & 4.5 \end{pmatrix}, \qquad A - A_1 = \begin{pmatrix} 1.5 & -1.5 \\ -0.5 & 0.5 \end{pmatrix},$$

and $\lVert A - A_1\rVert_F^2 = 2.25 + 2.25 + 0.25 + 0.25 = 5 = \sigma_2^2$, as the theorem says.

Storage: a rank-$k$ approximation of an $m \times n$ matrix needs $k(m + n + 1)$ numbers instead of $mn$. For a $1000 \times 1000$ greyscale image and $k = 50$, that is $100\,050$ numbers instead of $1\,000\,000$, about 10%. Whether the result looks acceptable depends on how fast the singular values decay.

The pseudoinverse

The Moore–Penrose pseudoinverse of $A = U\Sigma V^T$ is

$$A^+ = V\Sigma^+U^T,$$

where $\Sigma^+$ is $n \times m$ with $1/\sigma_i$ in place of each nonzero $\sigma_i$. It inverts $A$ on the row space and sends the left null space to 0. $x^+ = A^+b$ is the least-squares solution of $Ax = b$ with the smallest norm — well defined even when $A$ is rank-deficient and the normal equations have infinitely many solutions. If $A$ has independent columns, $A^+ = (A^TA)^{-1}A^T$ and $A^+b$ is the $\hat x$ of Chapter 4; for the line fit, $A^+b = (-0.5, 1.2)$. If $A$ is invertible, $A^+ = A^{-1}$.

Example. $A = \begin{pmatrix} 1 & 1 \\ 1 & 1 \end{pmatrix} = 2\,uu^T$ with $u = \frac{1}{\sqrt2}(1, 1)$, so $A^+ = \frac12 uu^T = \frac14\begin{pmatrix} 1 & 1 \\ 1 & 1\end{pmatrix}$. For $b = (1, 3)$ (not in the column space), $x^+ = A^+b = (1, 1)$. Every $x$ with $x_1 + x_2 = 2$ gives the same smallest residual (because $Ax = (2, 2)$, the projection of $b$), and $(1, 1)$ is the shortest of them.

Principal component analysis

Put $N$ data points in $\mathbb{R}^p$ as the rows of a matrix and subtract the mean of each column, giving a centred $N \times p$ matrix $X$. The sample covariance matrix is $C = \frac{1}{N - 1}X^TX$. If $X = U\Sigma V^T$ then $C = V\frac{\Sigma^T\Sigma}{N - 1}V^T$, so:

• the principal directions are the right singular vectors $v_i$ (eigenvectors of $C$);
• the variance along $v_i$ is $\sigma_i^2/(N - 1)$;
• projecting the data onto $v_1, \dots, v_k$ is the best $k$-dimensional summary in the least-squares sense (Eckart–Young applied to $X$).

Worked example. The four points $(3, 3), (-3, -3), (1, -1), (-1, 1)$ already have mean zero. $X^TX = \begin{pmatrix} 20 & 16 \\ 16 & 20\end{pmatrix}$ has eigenvalues 36 and 4 with eigenvectors $(1, 1)$ and $(1, -1)$, so the singular values of $X$ are 6 and 2. The first principal direction is $\frac{1}{\sqrt2}(1, 1)$ with variance $36/3 = 12$; the second has variance $4/3$. The first component explains $36/(36 + 4) = 90\%$ of the total variance.

Common pitfall: Forgetting to centre the data. Without subtracting the mean, the first "principal component" mostly points at the mean itself. Also scale the columns first when they are in different units, or the largest-unit variable dominates.

---

Practice Exercises

1. Show that $\langle f, g\rangle = \int_0^1 f(t)g(t)\,dt$ satisfies the positive-definiteness axiom on $C[0,1]$. Then find the projection of $f(t) = t$ onto the constants.

Solution

$\langle f, f\rangle = \int_0^1 f^2 \ge 0$. If $f$ is continuous and $f(t_0) \neq 0$, then $f^2 > \frac12 f(t_0)^2$ on some interval around $t_0$, so the integral is positive; hence $\langle f, f\rangle = 0$ forces $f = 0$. (Continuity matters here.) Projection onto $\operatorname{span}(1)$: $\frac{\langle t, 1\rangle}{\langle 1, 1\rangle}\cdot 1 = \frac{1/2}{1} = \frac12$. The residual $t - \frac12$ is orthogonal to 1, as computed in Chapter 1.

2. Apply Gram–Schmidt to $a_1 = (1, 1, 1, 1)$, $a_2 = (0, 1, 2, 3)$.

Solution

$q_1 = \frac12(1, 1, 1, 1)$. $\langle a_2, a_1\rangle / \langle a_1, a_1\rangle = 6/4 = \frac32$, so $w_2 = (0, 1, 2, 3) - \frac32(1, 1, 1, 1) = (-\frac32, -\frac12, \frac12, \frac32)$ with $\lVert w_2\rVert = \sqrt{\frac94 + \frac14 + \frac14 + \frac94} = \sqrt5$. So $q_2 = \frac{1}{2\sqrt5}(-3, -1, 1, 3)$. (This is the "centred $x$" that makes line fitting at $x = 0, 1, 2, 3$ decouple.)

3. For the line fit in Chapter 4, compute the projection matrix $P = A(A^TA)^{-1}A^T$ and check $Pb$.

Solution

$(A^TA)^{-1} = \frac{1}{20}\begin{pmatrix} 30 & -10 \\ -10 & 4\end{pmatrix}$, and

$$P = \frac{1}{10}\begin{pmatrix} 7 & 4 & 1 & -2 \\ 4 & 3 & 2 & 1 \\ 1 & 2 & 3 & 4 \\ -2 & 1 & 4 & 7 \end{pmatrix}.$$

$Pb = \frac{1}{10}(7 + 8 + 2 - 10,\ 4 + 6 + 4 + 5,\ 1 + 4 + 6 + 20,\ -2 + 2 + 8 + 35) = (0.7, 1.9, 3.1, 4.3)$, the fitted values. Also $P^2 = P$ and $P^T = P$.

4. Is $\begin{pmatrix} 4 & 2 \\ 2 & 3\end{pmatrix}$ positive definite? Use two different tests.

Solution

Leading minors: $4 > 0$ and $12 - 4 = 8 > 0$: yes. Eigenvalues: trace 7, determinant 8, so $\lambda = \frac{7 \pm \sqrt{49 - 32}}{2} = \frac{7 \pm \sqrt{17}}{2}$, both positive because $\sqrt{17} < 7$. Or complete the square: $4x^2 + 4xy + 3y^2 = (2x + y)^2 + 2y^2$.

5. Find the singular values of $E = \begin{pmatrix} 2 & 2 \\ 1 & -1\end{pmatrix}$ and its condition number.

Solution

$E^TE = \begin{pmatrix} 5 & 3 \\ 3 & 5\end{pmatrix}$ has eigenvalues 8 and 2, so $\sigma_1 = 2\sqrt2$, $\sigma_2 = \sqrt2$, and $\kappa = 2$. Check: $\sigma_1\sigma_2 = 4 = \lvert\det E\rvert = \lvert -2 - 2\rvert$.

6. Prove that if $Q$ is orthogonal then every real eigenvalue of $Q$ is $\pm1$, and every singular value of $Q$ is 1.

Solution

If $Qv = \lambda v$ with $v \neq 0$, then $\lVert v\rVert = \lVert Qv\rVert = \lvert\lambda\rvert\,\lVert v\rVert$, so $\lvert\lambda\rvert = 1$. Singular values are square roots of the eigenvalues of $Q^TQ = I$, all equal to 1: an orthogonal map sends the unit sphere to itself.

7. Show that for a symmetric positive semidefinite matrix the SVD and the spectral decomposition coincide, and give a $2 \times 2$ symmetric matrix where they differ.

Solution

If $A = Q\Lambda Q^T$ with all $\lambda_i \ge 0$ (sorted in decreasing order), then $U = V = Q$ and $\Sigma = \Lambda$ is a valid SVD. For a symmetric matrix with a negative eigenvalue, such as $\begin{pmatrix} 1 & 2 \\ 2 & 1\end{pmatrix}$ (eigenvalues $3, -1$), the singular values are $3$ and $1$: the sign moves into $U$ (take $u_2 = -v_2$).

---

Cheat-sheet

Idea	Formula or fact
Inner product	symmetric, linear, $\langle v, v\rangle > 0$ for $v \neq 0$
Cauchy–Schwarz	$\lvert\langle u, v\rangle\rvert \le \lVert u\rVert\lVert v\rVert$
Orthonormal coordinates	$v = \sum\langle v, q_i\rangle q_i$
Projection	$P = QQ^T$ or $A(A^TA)^{-1}A^T$; $P^2 = P = P^T$
Best approximation	$P_Wv$ is the closest point of $W$
Gram–Schmidt	$w_j = v_j - \sum_{i<j}\langle v_j, q_i\rangle q_i$
QR	$A = QR$, $R$ upper triangular
Least squares	$A^TA\hat x = A^Tb$, or $R\hat x = Q^Tb$
Orthogonal matrix	$Q^TQ = I$, $\det Q = \pm1$, keeps lengths
Spectral theorem	$A = A^T \iff A = Q\Lambda Q^T$, real $\Lambda$
Positive definite	eigenvalues, leading minors, pivots all $> 0$; $A = R^TR$
Quadratic form	principal axes = eigenvectors of $A$
SVD	$A = U\Sigma V^T$, $Av_i = \sigma_iu_i$, $\sigma_i = \sqrt{\lambda_i(A^TA)}$
Norms	$\lVert A\rVert_2 = \sigma_1$, $\lVert A\rVert_F^2 = \sum\sigma_i^2$, $\kappa = \sigma_1/\sigma_n$
Eckart–Young	best rank $k$: keep the top $k$ terms; error $\sigma_{k+1}$
Pseudoinverse	$A^+ = V\Sigma^+U^T$, minimum-norm least squares
PCA	centre, SVD; variance along $v_i$ is $\sigma_i^2/(N-1)$

---

What's next

This completes the base series: from solving $Ax = b$ by elimination (post 00) to the SVD, which describes any matrix completely by two orthonormal bases and a list of stretch factors. The table below lists the posts planned to extend the series. The most natural next step is canonical forms — the full proof of the Jordan form stated in Linear Algebra 04 — followed by the numerical side, where the algorithms behind numpy.linalg (LU with pivoting, Householder QR, the QR eigenvalue algorithm, Golub–Kahan SVD) are studied for speed and accuracy.

Planned future extensions

Post	Topic	What it covers
06	Jordan form and canonical forms	generalised eigenvectors, the Jordan form proof, minimal polynomial, rational canonical form, $e^{At}$ for defective matrices
07	Numerical linear algebra	floating point and conditioning, LU with pivoting, Householder QR, QR eigenvalue algorithm, computing the SVD, iterative solvers (conjugate gradient, GMRES)
08	Linear algebra for machine learning	linear regression and ridge regression, PCA in practice, matrix calculus and gradients, low-rank methods, embeddings
09	Tensors and multilinear algebra	dual spaces, bilinear forms, tensor products, exterior algebra and the determinant revisited, tensor decompositions
10	Functional analysis preview	normed and Hilbert spaces, infinite orthonormal bases and Fourier series, bounded operators, the spectral theorem for compact self-adjoint operators

---

References

• Sheldon Axler, Linear Algebra Done Right, 4th ed., Springer (2024) — Chapter 6 (inner product spaces, Gram–Schmidt, orthogonal projection, least squares) and Chapter 7 (self-adjoint operators, the spectral theorem, positive operators, SVD). Open access at linear.axler.net.
• Gilbert Strang, Introduction to Linear Algebra, 6th ed., Wellesley-Cambridge Press (2023) — orthogonality, projections, least squares, Gram–Schmidt; symmetric and positive definite matrices; the SVD and PCA.
• Gilbert Strang, Linear Algebra and Learning from Data, Wellesley-Cambridge Press (2019) — the SVD, Eckart–Young, PCA and low-rank approximation from the data-science side.
• Lloyd N. Trefethen, David Bau III, Numerical Linear Algebra, SIAM (1997) — Lectures 4–5 (SVD), 6–11 (projectors, QR, Gram–Schmidt, Householder, least squares), 12–15 (conditioning and stability).
• Gene H. Golub, Charles F. Van Loan, Matrix Computations, 4th ed., Johns Hopkins University Press (2013) — the reference for QR, SVD and least-squares algorithms.
• Roger A. Horn, Charles R. Johnson, Matrix Analysis, 2nd ed., Cambridge University Press (2012) — positive definite matrices, the spectral theorem and the SVD with complete proofs.
• Carl Eckart, Gale Young, "The approximation of one matrix by another of lower rank", Psychometrika 1 (1936), 211–218 — the original low-rank approximation theorem.
• MIT OpenCourseWare, 18.06 Linear Algebra (Spring 2010), Gilbert Strang — lectures 14–17 (orthogonality, projections, least squares, Gram–Schmidt), 25 and 27 (symmetric and positive definite matrices) and 29 (SVD); and 18.065 Matrix Methods in Data Analysis, Signal Processing, and Machine Learning (Spring 2018).

Note: this post is in progress. Planned additions: complex inner product spaces and unitary matrices, the spectral theorem for normal matrices, a proof of Eckart–Young, a larger PCA example on real data with a scree plot, and a total-least-squares section.

---