Survey of Mathematics
Unit 3

Linear algebra, deeper

The spectral theorem, the SVD, Jordan form, and the bridge to algebra.

9 chapters written · 40 definitions · 38 theorems · builds on Unit 2

The story

Unit 2 asked whether a matrix can be diagonalized. This unit answers it. Symmetric matrices always can, with perpendicular eigenvectors (3.1, the spectral theorem), and that one theorem explains quadratic forms and the shape of conics (3.2) and the geometry of rotations and reflections (3.3).

Every matrix, symmetric or not, has a singular value decomposition (3.4): a rotation, a stretch along axes, another rotation. It is behind PCA, image compression and low-rank approximation, and it measures how badly a computation can go wrong (3.5: conditioning). Matrices that cannot be diagonalized have the next best form, Jordan form (3.6).

The unit ends with three bridges: dual and quotient spaces (3.7, toward MATH 540), matrix calculus and backpropagation (3.8, toward machine learning), and groups, rings and fields (3.9, toward MATH 541).

Chapters

  1. 3.1Symmetric matrices and the spectral theoremA symmetric matrix has real eigenvalues and perpendicular eigenvectors, so it is nothing but a stretch along perpendicular axes. That is the spectral theorem, the most useful theorem in linear algebra, and Apostol's chapter 5 that MATH 375 only touched.
  2. 3.2Quadratic forms and principal axesAn expression like 5x² + 4xy + 2y² is a symmetric matrix in disguise. Rotating to the eigenvector axes removes the cross term, which classifies every conic and quadric, and decides whether a matrix is positive definite.
  3. 3.3Orthogonal matrices, rotations and reflectionsThe matrices that never stretch anything are exactly those whose columns are orthonormal. In the plane they are rotations and reflections; in space every rotation turns about a fixed axis. Their inverse is free, which is why computers love them.
  4. 3.4The singular value decomposition and PCAEvery matrix, of any shape, is a rotation, then a stretch along the axes, then another rotation. The stretch factors (singular values) measure how much each direction matters, which gives the best low-rank approximation of a matrix and the principal components of a data set.
  5. 3.5Matrix norms, conditioning, and why numerics failSome linear systems turn a tiny error in the data into a huge error in the answer. The condition number, the ratio of the largest to the smallest singular value, measures exactly how much, and tells you how many digits a computer can be trusted with.
  6. 3.6Cayley–Hamilton, Schur, and the Jordan formNot every matrix can be diagonalized, but every matrix can be made triangular by a unitary change of basis (Schur), satisfies its own characteristic polynomial (Cayley–Hamilton), and is similar to an almost-diagonal matrix of Jordan blocks. The Jordan form says exactly how diagonalization fails.
  7. 3.7Dual spaces and quotient spacesA linear functional reads one number off a vector, and all the functionals on V form a space V* of the same dimension, whose maps are given by the transpose. Dividing V by a subspace U, by treating vectors that differ by something in U as the same, gives the quotient space V/U, and the first isomorphism theorem says every linear map is "quotient, then relabel", which is rank–nullity in its deepest form.
  8. 3.8Matrix calculus and backpropagationTraining a neural network means computing how a single number (the loss) changes with millions of weights. The derivative of a composition is a product of matrices, and evaluating that product from the output backwards is backpropagation.
  9. 3.9Groups, rings and fields: a preview built from what you knowTake the axiom idea of 2.1 and apply it to a single operation, and you get a group. Cosets give Lagrange's theorem, that the size of a subgroup divides the size of the group. A second operation gives a ring, and a ring in which every non-zero element can be divided by is a field, such as the integers mod a prime. Fields are the scalars that vector spaces always needed.

The theorem chain

Every theorem in the unit, in the order it is proved. Each one is used by the ones after it. The label says whether it is on the 375/376 exams (T), an Apostol extra (A), or beyond both (B).

3.1 Symmetric matrices and the spectral theorem

  1. Theorem · T Symmetric matrices have real eigenvalues Every eigenvalue of a Hermitian (in particular real symmetric) matrix is a real number.
  2. Theorem · T Eigenvectors of a symmetric matrix are orthogonal Eigenvectors of a symmetric matrix for different eigenvalues are perpendicular.
  3. Theorem · A Spectral theorem Every real symmetric matrix is orthogonally diagonalizable: A=QΛQTA = Q\Lambda Q^{\mathsf T}, with real eigenvalues and an orthonormal basis of eigenvectors.

3.2 Quadratic forms and principal axes

  1. Theorem · A Principal axes theorem Rotating to an orthonormal eigenbasis of A turns xTAxx^{\mathsf T}Ax into λ1y12+⋯+λnyn2\lambda_1 y_1^2 + \dots + \lambda_n y_n^2, with no cross terms.
  2. Theorem · A Positive definite iff positive eigenvalues A symmetric matrix is positive definite exactly when every eigenvalue is positive.

3.3 Orthogonal matrices, rotations and reflections

  1. Theorem · A Orthogonal means length-preserving For a square real matrix Q, these are equivalent: QᵀQ = I; Q preserves dot products; Q preserves lengths.
  2. Theorem · A Determinant of an orthogonal matrix An orthogonal matrix has determinant +1 (a rotation) or −1 (it includes a reflection).
  3. Theorem · A Orthogonal 2 by 2 matrices Every 2×2 orthogonal matrix is a rotation R_θ (det 1) or a reflection across a line (det −1).
  4. Theorem · B Euler's rotation theorem Every 3×3 rotation (orthogonal, det 1) fixes a line through the origin: it is a turn about an axis.
  5. Theorem · A Eigenvalues of an orthogonal matrix Every eigenvalue of an orthogonal (or unitary) matrix has absolute value 1.

3.4 The singular value decomposition and PCA

  1. Theorem · B Every matrix has an SVD Every real m×n matrix has a singular value decomposition A = UΣVᵀ.
  2. Theorem · B Eckart–Young theorem The truncated SVD A_k is the best rank-k approximation of A; its error is the first discarded singular value σ_{k+1} (in the operator norm).

3.5 Matrix norms, conditioning, and why numerics fail

  1. Theorem · B Error amplification bound If Ax = b and A(x + δx) = b + δb, then ‖δx‖/‖x‖ ≤ κ(A) · ‖δb‖/‖b‖.

3.6 Cayley–Hamilton, Schur, and the Jordan form

  1. Theorem · T Schur's theorem Every complex square matrix has a Schur decomposition A = UTU*.
  2. Theorem · T Cayley–Hamilton theorem Every square matrix satisfies its own characteristic polynomial: if p(λ) = det(λI − A), then p(A) = 0.
  3. Theorem · B Jordan normal form theorem Every complex square matrix is similar to a Jordan form, unique up to reordering the blocks.

3.7 Dual spaces and quotient spaces

  1. Proposition · B Functionals on R^n are rows Every linear functional on Rn\mathbb R^n is φ(x)=a1x1+⋯+anxn\varphi(x) = a_1x_1 + \dots + a_nx_n with ai=φ(ei)a_i = \varphi(e_i), which is the row [a1 ⋯ an][a_1\ \cdots\ a_n] times the column xx; and every such row gives a functional.
  2. Proposition · B Dual basis from the inverse matrix If the columns of an invertible matrix B are a basis b₁,…,bₙ of Rⁿ, the dual basis functionals are the rows of B⁻¹.
  3. Theorem · B The dual basis is a basis If φ₁,…,φₙ is the dual basis of a basis v₁,…,vₙ of V, it is a basis of V*. In particular dim V* = dim V, and every functional is φ = φ(v₁)φ₁ + … + φ(vₙ)φₙ.
  4. Theorem · B The dual map has the transposed matrix If A is the matrix of T: V → W in bases v₁…vₙ and w₁…wₘ, then the matrix of Tᵀ: W* → V* in the dual bases is Aᵀ.
  5. Corollary · B Dual of a composition (S∘T)ᵀ = Tᵀ∘Sᵀ: the dual map of a composition is the composition of the dual maps in the opposite order.
  6. Theorem · B Dimension of an annihilator For a subspace U of a finite-dimensional V, dim U⁰ = dim V − dim U.
  7. Corollary · B Row rank equals column rank, by duality rank Tᵀ = rank T, so a matrix and its transpose have the same rank.
  8. Theorem · B Cosets are the classes modulo a subspace Define v ∼ w when v − w ∈ U. This is an equivalence relation whose class of v is exactly the coset v + U. So v + U = w + U iff v − w ∈ U, and any two cosets are equal or disjoint.
  9. Theorem · B The quotient space is a vector space The sum and scalar multiple on V/U are well defined, V/U is a vector space with zero vector O + U = U, and v ↦ v + U is a linear map from V onto V/U whose null space is U.
  10. Theorem · B Dimension of a quotient space If V is finite-dimensional and U a subspace, then dim V/U = dim V − dim U.
  11. Theorem · B First isomorphism theorem for vector spaces For a linear map T: V → W, the rule T̄(v + N(T)) = T(v) is a well-defined isomorphism from V/N(T) onto the range of T.
  12. Corollary · B Rank–nullity from the first isomorphism theorem dim V − dim N(T) = dim V/N(T) = dim range T, which is rank–nullity.

3.9 Groups, rings and fields: a preview built from what you know

  1. Theorem · B Consequences of the group axioms In any group: the identity is unique; each element has exactly one inverse; (ab)⁻¹ = b⁻¹a⁻¹; ab = ac implies b = c (and ba = ca implies b = c); and ax = b has the unique solution x = a⁻¹b.
  2. Proposition · B Subgroup test A non-empty subset H of a group G is a subgroup as soon as ab⁻¹ is in H whenever a and b are in H.
  3. Theorem · B A repeated move has as many positions as its order If g has finite order k then ⟨g⟩ = {e, g, g², …, g^(k−1)} has exactly k elements, and gᵐ = e exactly when k divides m.
  4. Theorem · B Lagrange's theorem If H is a subgroup of a finite group G, then the order of H divides the order of G: |G| = [G : H] · |H|.
  5. Corollary · B Consequences of Lagrange's theorem In a finite group G: the order of every element divides |G|, so g^|G| = e; a group of prime order p is cyclic; and, for the group of invertible classes mod n, a^φ(n) ≡ 1 (Euler), in particular a^(p−1) ≡ 1 for prime p (Fermat).
  6. Proposition · B Homomorphisms preserve identity and inverses A homomorphism sends the identity to the identity and inverses to inverses: φ(e) = e and φ(a⁻¹) = φ(a)⁻¹. Its kernel is a subgroup, and φ is one-to-one iff the kernel contains only the identity.
  7. Theorem · B The sign is a homomorphism For permutations σ and τ of {1,…,n}, sgn(τ∘σ) = sgn(τ)·sgn(σ). So sgn: Sₙ → ({1, −1}, ×) is a homomorphism, whose kernel is the group Aₙ of even permutations.
  8. Proposition · B Zero times anything in a ring In any ring, 0·a = 0 and (−1)·a = −a.
  9. Lemma · B A field has no zero divisors In a field, ab = 0 implies a = 0 or b = 0.
  10. Theorem · B Z_n is a field exactly when n is prime For n ≥ 2, the ring Zₙ of integers mod n is a field if and only if n is prime.

Terms this unit defines

AdjointSymmetric operatorHermitianOrthogonally diagonalizableQuadratic formPrincipal axesPositive definiteOrthogonal matrixIsometryRotation matrixUnitary matrixSingular valueSingular value decompositionLow-rank approximationPrincipal component analysisOperator normCondition numberMachine epsilonInvariant subspaceSchur decompositionMinimal polynomialGeneralized eigenvectorJordan blockJordan formLinear functionalDual spaceDual basisDual mapAnnihilatorCosetQuotient spaceComputational graphBackpropagationGroupAbelian groupSubgroupOrder of an elementHomomorphismRingField

Unit review

A mixed set of 12 quick checks drawn at random from the 68 in this unit's chapters. Each one says which chapter it comes from, so a miss tells you what to reread. Press "New set" for another mix.

Where it leads

Units that build on this one: Unit 7, Differential equations, Unit 12, Number theory and algebra.