Unit 1.4 · about 4 h
54 / 324Inner products, norms, orthogonality and Gram-Schmidt
Orthonormal coordinates separate directions without mixing their lengths. They are the geometric foundation of projections, QR and spectral decompositions.
- derive
- implement
You can now
- Derive Cauchy-Schwarz and the induced norm, distance and angle from a real inner product.
- Prove that orthonormal coordinates preserve inner products and lengths.
- Implement Gram-Schmidt and check orthogonality, reconstruction and a dependent-column failure.
Covers
- Inner products, norms, angles and distance
- Orthogonality, orthonormal bases and Gram-Schmidt
Study, in this order
2 steps
- Orthogonal vectors and Gram-SchmidtMIT 18.06 - Linear Algebra
Video Lecture 14, Orthogonal vectors and subspaces; Lecture 17, Orthogonal matrices and Gram-Schmidt
- Inner-product geometry and its inequalitiesMathematics for Machine Learning
Chapter 3, sections 3.1 to 3.5 (pp. 71 to 79), especially Cauchy-Schwarz, equation (3.17); section 3.8.3, Gram-Schmidt Orthogonalization (pp. 89 to 90)
Depth · Use these definitions and the Gram-Schmidt construction to check the lectures. Leave function inner products and rotations.
Focus on
- A real inner product is bilinear, symmetric and positive definite. Its induced norm is \(\sqrt{<x,x>}\); angles require both vectors to be nonzero.
- For \(y\) nonzero, expand the nonnegative squared norm of \(x-(<x,y>/<y,y>)y\) to derive Cauchy-Schwarz. Handle \(y=0\) separately.
- Gram-Schmidt subtracts components in previously accepted directions and then normalizes. Independence is what prevents a zero residual in exact arithmetic.
- For tall \(Q\) with \(Q^\top Q=I\), lengths are preserved in the coordinate-to-vector map. \(QQ^\top\) need not be the identity.
Reproduce closed-book
A=np.array([[1,-1],[1,2],[1,0]],dtype=np.float64), with no random draws: for each column v, sequentially set R[i,j]=Q[:,i]@v and v-=R[i,j]*Q[:,i], then R[j,j]=norm(v,2) and Q[:,j]=v/R[j,j]. Reject a residual norm \(\le 10^{-12}\) on this small scale. Check the Frobenius norms of Q.T@Q-I and A-Q@R; the reference run gives 3.6e-16 and 2.2e-16. Against Qref=np.linalg.qr(A,mode='reduced')[0], the projector difference norm(Q@Q.T-Qref@Qref.T,'fro') is 5.1e-16. Require all three below 1e-12. Replacing \(b_2\) by \(2b_1\) must trigger the dependence guard.Traps
- Orthogonal vectors are not necessarily unit vectors. Projection coefficients need division by their squared lengths unless they are normalized.
- Normalizing a zero or numerically tiny Gram-Schmidt residual produces invalid or unreliable columns. A fixed threshold is only appropriate to the stated scale.
- Comparing \(Q\) columns directly with a library QR ignores valid sign changes. Compare spans through projectors and check your own reconstruction.
Practice
18.06 Problem set 6: Gram-Schmidt in \(\mathbb{R}^4\)
Problem set 6, Strang 4th ed., section 4.4, Problem 18
Orthogonalize the three difference vectors and prove they span the complement of \((1,1,1,1)\). Attempt before opening the official solutions. Run your implementation on these columns as a second case.
Self-test
-
Where does positive definiteness enter Cauchy-Schwarz?
For \(y\) nonzero it gives \(<y,y>>0\), permitting division. The squared residual is nonnegative, yielding \(<x,y>^2\le <x,x><y,y>\). Equality requires the residual to be zero, again by positive definiteness. For \(y=0\) both sides are zero. -
How does Cauchy-Schwarz imply the triangle inequality?
Expand \(\|x+y\|^2=\|x\|^2+2<x,y>+\|y\|^2\) and bound \(<x,y>\le\|x\|\|y\|\). This is at most \((\|x\|+\|y\|)^2\). Both sides are nonnegative, so taking square roots preserves the inequality. -
Why does Gram-Schmidt keep the same span at every step?
The new residual is the current input minus a combination of earlier outputs, so it lies in the enlarged input span. Conversely the input is that residual plus earlier outputs. Independence makes the residual nonzero, so normalization changes neither span. The first nonzero input establishes the base case. -
For \(Q\) of shape 3 by 2 with orthonormal columns, why is \(QQ^\top\) not \(I_3\)?
Its image has dimension two and it annihilates the one-dimensional orthogonal complement. \(I_3\) has rank three. \(Q^\top Q=I_2\) still implies \(\|Qz\|_2=\|z\|_2\) for \(z\) in \(\mathbb{R}^2\).
Completion criterion
Stop when
You derive the inequality, reproduce the two-vector orthonormal basis, pass the three norm checks and reject dependent columns before division.
Mark passed, then open 1.5 Only mark this when you can do it without notes.Leads to
- 1.5 Projections, residuals and least squares Use orthonormal columns to construct a projection.
- 3.6 Schedules, gradient accumulation and clipping Apply vector norms to clipping; leave optimizer exercises there.
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.
- 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.
- MIT 18.065 - Applied matrix bridge Use lectures 3-10 after 18.06 for SVD, PCA, low-rank approximation, matrix norms and solver difficulty.
- 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.