Unit 1.6 · about 6 h
56 / 324Eigenvalues, symmetric and positive-semidefinite matrices
Symmetry turns a matrix into independent orthogonal directions. The signs of its eigenvalues then decide whether its quadratic form is a valid squared length or has a downhill direction.
- derive
You can now
- Derive a symmetric eigendecomposition and explain why a general square matrix may not diagonalize.
- Give the spectral-theorem induction argument, including the invariant orthogonal complement.
- Prove the eigenvalue test for PSD and the Gram-matrix singularity criterion.
Covers
- Eigenvalues, eigenvectors, diagonalization and spectral reasoning
- Symmetric and positive-semidefinite matrices; Gram matrices
Study, in this order
3 steps
- Eigenvectors, diagonalization and symmetric matricesMIT 18.06 - Linear Algebra
Video Lectures 21 and 22, Eigenvalues and eigenvectors and Diagonalization and powers of A; Lecture 25, Symmetric matrices and positive definiteness; Lecture 27, Positive definite matrices and minima
Depth · Focus Lecture 25 on real eigenvalues and orthogonal eigenvectors; learn the conjugate-transpose argument even though the worked matrices are real. In Lecture 27, focus on quadratic-form tests, not optimization applications.
- Gram matrices and the spectral theoremMathematics for Machine Learning
Chapter 4, section 4.2, Theorems 4.14 and 4.15 on p. 111 and Example 4.8 on pp. 111 to 112; section 4.4 (pp. 115 to 119)
Depth · Check the Gram proof line by line. For repeated eigenvalues, distinguish an orthonormal eigenbasis that exists from an arbitrary basis returned for the eigenspace. Leave Jordan form.
- Positive definite and semidefinite matricesMIT 18.065 - Applied matrix bridge
Lecture 5, Positive Definite and Semidefinite Matrices
Focus on
- A real symmetric matrix has an orthonormal eigenbasis. Distinct eigenvalues imply orthogonality; repeated eigenvalues require choosing an orthonormal basis within the eigenspace.
- Complete the spectral-theorem proof by showing that the complement of one unit eigenvector is invariant under \(A\), then induct on dimension. State the eigenvalue-existence fact you use.
- For symmetric \(A=Q\Lambda Q^\top\), \(x^\top Ax=\sum_i \lambda_i (q_i^\top x)^2\). PSD means every eigenvalue is nonnegative; positive definite means every eigenvalue is positive.
- \(A^\top A\) is PSD since \(x^\top A^\top Ax=\|Ax\|_2^2\). It is singular exactly when \(A\) has a nontrivial kernel.
Reproduce closed-book
S once in NumPy: S=np.array([[2,1],[1,2]],dtype=np.float64); lam,Q=np.linalg.eigh(S), with no random draws. Compute norm(S-(Q*lam)@Q.T,'fro') and norm(Q.T@Q-I,'fro'). The reference values are 6.5e-16 and 3.2e-16; require both below 1e-12, and lam within vector 2-norm 1e-12 of (1,3).Traps
- A positive diagonal does not imply PSD: \(\left[\begin{smallmatrix}1&2\\2&1\end{smallmatrix}\right]\) has eigenvalue -1 and its quadratic form at \((1,-1)\) is -2.
- Invertibility does not imply diagonalizability. The worked \(J\) is invertible but defective.
- The PSD eigenvalue test assumes symmetry. Do not classify a nonsymmetric matrix using only signs of its eigenvalues, or silently pass it to
eigh.
Practice
18.06 Problem set 8: diagonal entries and the largest eigenvalue
Problem set 8, Problem 10 (Strang 4th ed., section 6.4, #30)
Prove \(a_{11}\le \lambda_{\max}\) using orthonormal coordinates. Attempt before the official solution. The section mini-project should add power iteration with a separated dominant magnitude, a tied-magnitude failure and an eigen-residual check.
MML Exercise 4.5: invertibility versus diagonalizability
Chapter 4, Exercise 4.5, printed p. 137
Classify all four 2 by 2 matrices. Exhibit enough independent eigenvectors, or the missing eigenspace dimension, rather than relying on a software label.
Self-test
-
How do you complete the spectral-theorem proof, including its assumptions and base case?
For \(n=1\) the real entry and unit basis suffice. For \(n>1\), the characteristic polynomial has a complex root by the fundamental theorem of algebra, hence an eigenpair \(Az=\lambda z\). Real symmetry gives \(A^*=A\), so \(z^*Az\) is real and \(z^*z>0\); therefore \(\lambda\) is real. A nonzero real or imaginary part of \(z\) gives a real eigenvector \(v\), which can be normalized. For \(w\) perpendicular to \(v\), \(v^\top Aw=(Av)^\top w=\lambda v^\top w=0\), using symmetry. Thus \(v\)'s complement is invariant. In an orthonormal basis its restriction is real symmetric of dimension \(n-1\); the induction hypothesis supplies an orthonormal eigenbasis there. Adjoin \(v\). -
Why are eigenvectors for distinct eigenvalues orthogonal?
For real symmetric \(A\), \((Av)^\top w=v^\top Aw\), so \(\lambda v^\top w=\mu v^\top w\). Distinct \(\lambda\) and \(\mu\) allow division by \(\lambda-\mu\), forcing \(v^\top w=0\). This argument alone does not handle repeated eigenvalues. -
Why is PSD equivalent to nonnegative eigenvalues for a symmetric matrix?
Symmetry supplies the orthonormal spectral decomposition. Nonnegative eigenvalues make every term in the quadratic-form sum nonnegative. Conversely, testing the form on each unit eigenvector gives its eigenvalue, so PSD forces each to be nonnegative. -
When is \(A^\top A\) singular?
If \(Az=0\) for nonzero \(z\), then \(A^\top Az=0\). Conversely, \(A^\top Az=0\) implies \(0=z^\top A^\top Az=\|Az\|^2\), so \(Az=0\). Real Euclidean positive definiteness is used at the last step. Thus the Gram matrix is singular iff the columns of \(A\) are dependent.
Completion criterion
Stop when
You give the spectral-theorem proof with its base case and invariant complement, diagonalize \(S\), and prove or refute PSD claims using a quadratic-form witness or the symmetric spectrum.
Mark passed, then open 1.7 Only mark this when you can do it without notes.Leads to
- 1.7 SVD, pseudoinverse and low-rank approximation Apply the spectral theorem to \(A^\top A\) to construct an SVD.
- 2.2 Conditioning, basis expansions, ridge, lasso and elastic net Use PSD geometry to understand ridge's shifted Gram spectrum.
- 3.1 Initialization and signal scale across depth Apply spectral and variance reasoning to signal propagation.
Resources for this unit
- MIT 18.06 - Linear Algebra Follow lectures 1-10, 14-17, 21-22, 25, 27, 29-31 and 33 with matching problems. This is the ordered first pass.
- MIT 18.065 - Applied matrix bridge Use lectures 3-10 after 18.06 for SVD, PCA, low-rank approximation, matrix norms and solver difficulty.
- Mathematics for Machine Learning Use Chapters 2-4 and §10.2 to check notation or re-derive a result. Do not treat it as a second course.
Also in this section
- MIT 6.042J - Proof strand Study textbook Chapters 1 and 3, §§4.1-4.4 and §§5.1-5.4 with matching Unit 1 problems. Leave the rest of the course.
- Introduction to Applied Linear Algebra Sample Chapters 1-13 and the extra exercises for computational practice in fitting, least squares and pseudoinverses.
- Essence of Linear Algebra Open only when a geometric picture is missing; it does not replace derivation or problem solving.
- NumPy broadcasting and matmul shape rules Read General broadcasting rules and Broadcastable arrays, then
matmulNotes for stacked matrices and one-dimensional promotion. These close the pool's array-semantics gap. - Fundamentals of Numerical Computation: conditioning and operation counts Python edition, section 2.8 through Residual and backward error for the fixed-matrix perturbation bound; section 2.5.3 for triangular-solve and LU flop counts. Use Exercise 2.8.7 for a condition-number proof, not the unseeded Hilbert experiment.