Source: MATH 416 Abstract Linear Algebra, UIUC Practice Exam
Tags: singular value decomposition, SVD, orthogonal projection, idempotent, quadratic form, positive definite, rank-nullity theorem, dual space, change of basis, similarity, characteristic polynomial, differential equation, linear ODE
Difficulty: Intermediate to Advanced Prerequisites: Inner product spaces, orthogonality, Gram-Schmidt (Part 1). Adjoint operators, self-adjoint operators, Spectral Theorem (Part 2). Eigenvalues and eigenvectors.
This set of notes covers the remaining major topics tested in the MATH 416 exam. The Singular Value Decomposition (SVD) generalises eigenvalue decomposition to any matrix, rectangular or not. Orthogonal projections formalise the idea of "dropping a perpendicular." Quadratic forms link symmetric matrices to geometry. Several supplementary results, including the Rank-Nullity Theorem, dual spaces, and change of basis, round out the toolkit. The exam also tests linear differential equations as an application of linear algebra to function spaces.
SVD writes any m × n matrix as UΣV*, where U and V are unitary and Σ is diagonal with non-negative entries (the singular values). Orthogonal projections require both idempotency (P² = P) and self-adjointness (P* = P). Quadratic forms are classified by the eigenvalues of their associated symmetric matrix. The Rank-Nullity Theorem, dual spaces, and change-of-basis formulas are foundational tools that appear throughout the exam.
Singular Value Decomposition (SVD)
For any m × n matrix A, the factorisation A = UΣV*, where U is m × m unitary, V is n × n unitary, and Σ is m × n diagonal with non-negative real entries σ₁ ≥ σ₂ ≥ ... ≥ 0 on the diagonal. Think of it as revealing the "true geometry" of any linear map: rotate, stretch along coordinate axes, rotate again.
Singular values
The diagonal entries σᵢ of Σ in the SVD. They are the non-negative square roots of the eigenvalues of AA (equivalently, of AA). In simple terms, they measure how much the matrix stretches space in each independent direction.
Orthogonal projection
A linear operator P satisfying P² = P (idempotent) and P* = P (self-adjoint). It projects vectors onto the range R(P) along the direction perpendicular to R(P). The self-adjointness condition ensures the projection is "straight down," not oblique.
Idempotent operator
An operator P with P² = P. Every vector is either fixed by P (if it is in R(P)) or sent to zero (if it is in N(P)). Idempotency alone gives a projection, but not necessarily an orthogonal one.
Quadratic form
A function Q : ℝⁿ → ℝ of the form Q(x) = xᵀAx, where A is a symmetric matrix. The off-diagonal entries of A are half the coefficients of the cross terms. Think of it as a generalised "squared length" that can be made diagonal by choosing the right coordinate axes (the eigenvectors of A).
Rank-Nullity Theorem (Dimension Theorem)
For a linear transformation T : V → W with V finite-dimensional: rank(T) + nullity(T) = dim(V). In simple terms, the dimensions of "what T hits" and "what T kills" always add up to the dimension of the domain.
Dual space (V)*
The vector space of all linear functionals from V to the base field F. In simple terms, V* is the space of all linear "measurement" functions on V. It has the same dimension as V.
Change of basis (similarity)
If [T]β is the matrix of T in basis β, and Q is the change-of-coordinate matrix from β' to β, then [T]{β'} = Q⁻¹[T]_β Q. In simple terms, conjugating by the change-of-basis matrix translates between representations of the same operator.
Characteristic polynomial (for ODEs)
For a linear ODE with constant coefficients, replacing y⁽ⁿ⁾ with rⁿ gives a polynomial whose roots determine the form of the general solution. Think of it as converting a differential equation into an algebra problem.
Every m × n matrix A has a factorisation A = UΣV*, where:
U is m × m unitary (its columns are orthonormal eigenvectors of AA*).
V is n × n unitary (its columns are orthonormal eigenvectors of A*A).
Σ is m × n with σ₁, σ₂, ... on the diagonal and zeros elsewhere.
The singular values σᵢ = √(eigenvalue of A*A), ordered σ₁ ≥ σ₂ ≥ ... ≥ 0.
The workflow for computing SVD:
Compute A*A and find its eigenvalues λ₁ ≥ λ₂ ≥ ... ≥ 0.
Singular values: σᵢ = √λᵢ.
Find orthonormal eigenvectors of A*A to form the columns of V.
Compute uᵢ = (1/σᵢ) A vᵢ for each nonzero singular value to get the corresponding columns of U.
Complete U to a full orthonormal basis if needed (for zero singular values, choose any orthonormal vectors perpendicular to the existing columns).
Worked example: B = [[1, 1], [0, 0]].
B*B = [[1, 1], [1, 1]]. Eigenvalues: λ₁ = 2, λ₂ = 0. Singular values: σ₁ = √2, σ₂ = 0.
Eigenvectors of B*B: v₁ = (1/√2)(1, 1) for λ = 2, v₂ = (1/√2)(1, −1) for λ = 0.
u₁ = (1/√2) B v₁ = (1/√2)[[1,1],[0,0]] · (1/√2)(1,1) = (1, 0).
u₂ = (0, 1) (orthogonal to u₁).
U = I₂, Σ = [[√2, 0], [0, 0]], V* = (1/√2)[[1, 1], [1, −1]].
An orthogonal projection onto a subspace R(P) satisfies two conditions:
Idempotent: P² = P (applying it twice is the same as applying it once).
Self-adjoint: P* = P (the projection direction is perpendicular to R(P)).
Together, these guarantee that N(P) = R(P)⊥, so the projection is truly "along the perpendicular."
Proof sketch that P² = P and P* = P imply orthogonal projection:
Take x ∈ R(P) and y ∈ N(P). Then x = P(z) for some z.
⟨x, y⟩ = ⟨P(z), y⟩ = ⟨z, P*(y)⟩ = ⟨z, P(y)⟩ (using P* = P).
Since y ∈ N(P), P(y) = 0, so ⟨x, y⟩ = 0.
This shows R(P) ⊥ N(P), and since V = R(P) ⊕ N(P) (from P² = P), P is the orthogonal projection onto R(P).
Why P* = P is necessary: The matrix A = [[1, 1], [0, 0]] satisfies A² = A, so it is idempotent. But Aᵀ ≠ A. Its range is span(1, 0) and its null space is span(1, −1), which are not orthogonal. So P is a projection but not an orthogonal one.
A quadratic form Q(x₁, ..., xₙ) = xᵀAx, where A is symmetric.
To construct A from the quadratic expression:
Diagonal entries: the coefficients of the squared terms (xᵢ²).
Off-diagonal entry aᵢⱼ: half the coefficient of the cross term xᵢxⱼ.
Example: Q(x₁, x₂) = 5x₁² + 4x₁x₂ + 2x₂². The matrix is A = [[5, 2], [2, 2]].
To determine positive definiteness, either check:
All eigenvalues are positive, or
All leading principal minors are positive (M₁ = a₁₁ > 0, M₂ = det(A) > 0, etc.).
For the example: M₁ = 5 > 0, M₂ = det(A) = 10 − 4 = 6 > 0, so Q is positive definite.
To eliminate cross terms, diagonalise A: find eigenvalues and orthonormal eigenvectors, form P from the eigenvectors, and substitute x = Py. In the new coordinates, Q = λ₁y₁² + λ₂y₂² + ... with no cross terms.
Example continued: eigenvalues λ = 6 and λ = 1. Eigenvectors (2, 1) and (1, −2), normalised to (1/√5)(2, 1) and (1/√5)(1, −2). Change of variables gives Q = 6y₁² + y₂².
For T : V → W with V finite-dimensional:
rank(T) + nullity(T) = dim(V)
where rank(T) = dim(R(T)) = dim(image of T) and nullity(T) = dim(N(T)) = dim(kernel of T).
This is also called the Dimension Theorem. Note that it is dim(V), the domain, not dim(W), the codomain.
The dual space V* is the set of all linear functionals f : V → F.
V* is itself a vector space, with the same dimension as V.
If β = {v₁, ..., vₙ} is a basis for V, the dual basis β* = {f₁, ..., fₙ} is defined by fᵢ(vⱼ) = δᵢⱼ (1 when i = j, 0 otherwise).
If T : V → V is a linear operator, [T]_β is its matrix in basis β, and Q is the change-of-coordinate matrix from β' to β, then:
[T]_{β'} = Q⁻¹ [T]_β Q
Two matrices related this way are called similar. Similar matrices have the same eigenvalues, trace, determinant, and characteristic polynomial.
For a homogeneous linear ODE aₙy⁽ⁿ⁾ + ... + a₁y' + a₀y = 0:
Form the characteristic polynomial: aₙrⁿ + ... + a₁r + a₀ = 0.
Find its roots r₁, r₂, ....
Distinct real roots rᵢ contribute terms cᵢe^{rᵢ t} to the general solution.
Apply initial conditions to determine the constants.
Example: y'' − 5y' + 6y = 0. Characteristic polynomial: r² − 5r + 6 = (r − 2)(r − 3) = 0. Roots: r = 2, 3. General solution: y = c₁e^{2t} + c₂e^{3t}.
Example: y'' − 4y = 0 with y(0) = 1, y'(0) = 0. Roots: r = ±2. General solution: y = c₁e^{2t} + c₂e^{−2t}. From y(0) = 1: c₁ + c₂ = 1. From y'(0) = 0: 2c₁ − 2c₂ = 0, so c₁ = c₂ = 1/2. Solution: y(t) = (1/2)e^{2t} + (1/2)e^{−2t} = cosh(2t).
SVD: A = UΣV*, with σᵢ = √(eigenvalues of A*A)
SVD column construction: uᵢ = (1/σᵢ) A vᵢ
Orthogonal projection conditions: P² = P and P* = P
Quadratic form matrix (2D): Q = ax₁² + 2bx₁x₂ + cx₂² ⟹ A = [[a, b], [b, c]]
Rank-Nullity: rank(T) + nullity(T) = dim(V)
Change of basis: [T]_{β'} = Q⁻¹ [T]_β Q
ODE characteristic polynomial: y'' + py' + qy = 0 ⟹ r² + pr + q = 0
SVD is the mathematical core of data compression (low-rank approximation), recommendation systems (Netflix prize), and image processing. When you truncate the SVD to keep only the largest singular values, you get the best possible approximation of lower rank. Quadratic forms determine the geometry of conic sections (ellipses, hyperbolas) and appear in optimisation when checking whether a critical point is a minimum (Hessian test). Linear ODEs model springs, circuits, population dynamics, and any system where the rate of change is proportional to the current state.
Students often think any idempotent operator (P² = P) gives an orthogonal projection. It does not. The self-adjointness condition P* = P is also required. Without it, you get an oblique projection.
In the SVD, students sometimes confuse the roles of U and V. Remember: V comes from eigenvectors of AA, U comes from eigenvectors of AA (or from uᵢ = (1/σᵢ)Avᵢ).
For quadratic forms, the off-diagonal entry is half the coefficient of the cross term, not the full coefficient. Q = 5x₁² + 4x₁x₂ + 2x₂² gives A = [[5, 2], [2, 2]], not [[5, 4], [4, 2]].
The Rank-Nullity Theorem says rank + nullity = dim(V), the dimension of the domain. Students frequently write dim(W) (the codomain) by mistake.
⚠️ SVD computation is a 10-mark problem. You must show: computing A*A, finding eigenvalues, taking square roots for singular values, finding eigenvectors for V, computing U columns via uᵢ = (1/σᵢ)Avᵢ, and assembling the final factorisation.
⚠️ The orthogonal projection proof (P² = P and P* = P implies orthogonal projection onto R(P)) is a 10-mark problem. Know the proof and the counter-example (a non-symmetric idempotent matrix).
⚠️ Quadratic forms: be ready to extract the symmetric matrix, check positive definiteness by two methods (eigenvalues or principal minors), and find the diagonalising change of variables. This is a 10-mark comprehensive problem.
⚠️ Rank-Nullity: multiple choice tests whether you know it is dim(V), not dim(W).
⚠️ Dual space definition (V* = set of all linear functionals V → F) is a direct multiple-choice question.
⚠️ Change of basis formula [T]_{β'} = Q⁻¹[T]_β Q is tested. Know which side gets the inverse.
⚠️ Linear ODE questions (characteristic polynomial, initial value problems) appear in both multiple choice and short answer.
Fill in the blank: In the SVD A = UΣV*, U and V are ______ matrices.
True or false: If P² = P, then P is an orthogonal projection.
Fill in the blank: For Q(x₁, x₂) = 5x₁² + 4x₁x₂ + 2x₂², the off-diagonal entry of the associated symmetric matrix is ______.
True or false: The Rank-Nullity Theorem states rank(T) + nullity(T) = dim(W).
Fill in the blank: The dual space V* is the set of all linear ______ from V to F.
Answers: 1. Unitary (or orthogonal, over ℝ). 2. False (also need P* = P). 3. 2 (half of 4). 4. False (it equals dim(V), the domain). 5. Functionals.
Q: For any m × n matrix A, the SVD A = UΣV uses which types of matrices for U and V?*
A: Unitary (or orthogonal) matrices.
Q: What does the Rank-Nullity Theorem state for T : V → W with V finite-dimensional?
A: rank(T) + nullity(T) = dim(V).
Q: A linear operator T is called an isometry if it satisfies which condition?
A: ‖T(x)‖ = ‖x‖ for all x ∈ V (it preserves norms).
Q: If [T]β is the matrix of T in basis β and Q is the change-of-coordinate matrix from β' to β, how is [T]{β'} related to [T]_β?
A: [T]_{β'} = Q⁻¹[T]_β Q.
Q: In the context of dual spaces, what is V defined as?*
A: The set of all linear functionals from V to F.
Q: For the differential equation y'' − 5y' + 6y = 0, what are the roots of the characteristic polynomial?
A: The characteristic polynomial is r² − 5r + 6 = (r − 2)(r − 3) = 0, so r = 2 and r = 3.
Q: Solve y'' − 4y = 0 with y(0) = 1 and y'(0) = 0.
A: Characteristic roots r = ±2. General solution: y = c₁e^{2t} + c₂e^{−2t}. From y(0) = 1: c₁ + c₂ = 1. From y'(0) = 0: 2c₁ − 2c₂ = 0, so c₁ = c₂ = 1/2. Solution: y(t) = (1/2)e^{2t} + (1/2)e^{−2t}.
Q: Compute the SVD of B = [[1, 1], [0, 0]].
A: B*B = [[1, 1], [1, 1]] with eigenvalues 2 and 0. Singular values: σ₁ = √2, σ₂ = 0. V = (1/√2)[[1, 1], [1, −1]]. u₁ = (1/√2)B·(1/√2)(1,1) = (1, 0); u₂ = (0, 1). U = I. Final: B = I · [[√2, 0], [0, 0]] · (1/√2)[[1, 1], [1, −1]].
Q: Let P be a linear operator with P² = P and P = P. Prove P is an orthogonal projection onto R(P).*
A: Take x ∈ R(P) and y ∈ N(P). Write x = P(z). Then ⟨x, y⟩ = ⟨P(z), y⟩ = ⟨z, P*(y)⟩ = ⟨z, P(y)⟩ = ⟨z, 0⟩ = 0. So R(P) ⊥ N(P). Since P² = P gives V = R(P) ⊕ N(P), we have N(P) = R(P)⊥, confirming P is the orthogonal projection onto R(P).
Q: For Q(x₁, x₂) = 5x₁² + 4x₁x₂ + 2x₂², find the symmetric matrix A, determine positive definiteness, and find the diagonalising change of variables.
A: A = [[5, 2], [2, 2]]. Principal minors: M₁ = 5 > 0, M₂ = det(A) = 6 > 0, so Q is positive definite. Eigenvalues: λ² − 7λ + 6 = 0, giving λ = 6 and λ = 1. Normalised eigenvectors: (1/√5)(2, 1) and (1/√5)(1, −2). Set P = (1/√5)[[2, 1], [1, −2]]; then x = Py gives Q = 6y₁² + y₂².
SVD relies on the eigenvalue theory of A*A, connecting back to self-adjoint operators and the Spectral Theorem (Part 2). The orthogonal projection proof uses the adjoint identity from Part 2 and the direct sum decomposition from Part 1. Quadratic forms are classified by the eigenvalues of their symmetric matrix, tying together positive definiteness (Part 2) with diagonalisation. The Rank-Nullity Theorem is a foundational tool used implicitly throughout, particularly when counting dimensions of eigenspaces and null spaces in spectral problems.
singular value decomposition, SVD, singular values, unitary matrix, orthogonal matrix, sigma matrix, orthogonal projection, oblique projection, idempotent, self-adjoint projection, quadratic form, symmetric matrix, positive definite, principal minors, diagonalisation, canonical form, rank-nullity, dimension theorem, kernel, image, null space, range, dual space, linear functional, dual basis, change of basis, similarity, conjugation, characteristic polynomial, linear ODE, homogeneous, constant coefficients, initial value problem, MATH 416, abstract linear algebra, UIUC