Section 1 of 5 · Mathematical Foundations
Linear Algebra & Proof
Models are compositions of linear maps. Geometry, rank and conditioning explain what a model can represent and when a correct formula still fails numerically.
8 units 18 topics 0/8
Units
8 in this section
- 1.1 Proof habits and shape notation explain · derive6 h
- 1.2 Linear maps, span, independence and change of basis derive4 h
- 1.3 The four subspaces, rank and solution sets derive5 h
- 1.4 Inner products, norms, orthogonality and Gram-Schmidt derive · implement4 h
- 1.5 Projections, residuals and least squares derive · implement5 h
- 1.6 Eigenvalues, symmetric and positive-semidefinite matrices derive6 h
- 1.7 SVD, pseudoinverse and low-rank approximation derive · implement6 h
- 1.8 Batched shapes, operation costs and conditioning derive · measure6 h
Before moving on
Checkpoint
Derive least squares and PCA, implement both from a blank file, and diagnose one rank-deficient or ill-conditioned case.
Deliberately out of scope
Leave for later
- Advanced matrix perturbation bounds
- Specialized sparse-direct solvers
- Functional analysis beyond what later tracks require
Resources for this section
Shared by every unit above
- 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 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.
- 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.
- 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.
Apply the section
Mini-project · Least squares and PCA with rank and conditioning failures (10 to 14 h)
Start the shared
numlab/ repository with a linear-algebra package: a QR least-squares solver, power iteration, a cutoff-aware pseudoinverse and PCA. Each routine is checked against an independent NumPy oracle and shown failing on a case you construct, and the solver with its conditioning evidence carries into the capstone.Steps
- Before coding, write
notes/linalg.md: derive the normal equations, show the least-squares projector is symmetric and idempotent, and present PCA as both maximum variance and best rank approximation. - Implement thin QR by modified Gram-Schmidt or Householder reflections and solve least squares by back substitution on \(Rx=Q^\top b\). Check a full-rank tall case against
numpy.linalg.lstsqwith projector identities, keeping the matrix and tolerances your choice. - Make one column a combination of the others, show the small diagonal entry of
Rand the exploding solution, then detect it with a relative threshold onRentries that you justify, either raising an error or falling back to the minimum-norm solution. - Add power iteration on a symmetric matrix reporting the Rayleigh quotient and the eigen-residual \(\|Av-\rho v\|\) each step. Match
numpy.linalg.eighon a separated case, then construct a tied-magnitude case where the quotient settles at a non-eigenvalue and the residual rule reports failure. - Build a pseudoinverse from
numpy.linalg.svdwith a cutoff relative to the largest singular value, checking it againstnumpy.linalg.pinvand the Penrose conditions, and show the no-cutoff behavior. Implement PCA on centered data and compare components through projectors or reconstructions so sign flips cannot fail. - Assert shapes in every routine, including a batched case, and compare flop counts for the normal equations against QR. Then solve a rising-condition family from a known \(x^*\), tabulating conditioning, residual and error per solver and explaining the digit loss from the residual bound.
Deliverables
numlab/linalg/: QR least squares with rank detection, power iteration, the cutoff pseudoinverse and PCA.- Tests against NumPy oracles covering projector and Penrose checks, both failure cases, sign-invariant comparison and shapes.
notes/linalg.mdwith the derivations andnotes/linalg-defense.mdwith the conditioning table and solver choice.
Checks
- rubric · Self-grade with the rubric below
Rubric
| Criterion | Pass | Strong |
|---|---|---|
| Written derivations | The notes derive the normal equations, projector properties and both PCA views without copying. | Each derivation names the assumption it needs at the step that uses it. |
| Least squares | QR matches numpy.linalg.lstsq on a full-rank case, and the rank-deficient case is detected, not returned. | The rank threshold is justified from the scale of R and rounding, with a minimum-norm fallback checked against the pseudoinverse. |
| Spectral methods | Power iteration matches numpy.linalg.eigh on the separated case and reports failure on the tied case. | The note explains the settled quotient from the tied components, and the stopping rule uses the eigen-residual. |
| SVD and PCA | The pseudoinverse passes the Penrose conditions, and PCA reconstruction error matches the discarded singular values. | Every comparison is sign-invariant, and the no-cutoff behavior is shown. |
| Conditioning evidence | The table reports conditioning, residual and error for both solvers across the family. | The observed digit loss is compared with the residual bound and the squared conditioning of the normal equations. |
Feeds into: Capstone least squares and PCA: the QR solver with its rank failure, sign-invariant PCA checks and the conditioning table behind the solver choice.