Abstract Linear Algebra, University of Illinois at Urbana-Champaign
Difficulty: Intermediate–Advanced | Prerequisites: Inner product spaces, orthogonal complements, column space, rank, nullity, matrix transposes/conjugate transposes.
This lecture tackles what happens when a system of linear equations Ax = b has no exact solution, which is the typical case when there are more equations than unknowns. The answer is to find the "best approximate" solution by projecting b onto the column space of A. Two supporting lemmas do the heavy lifting: one connects inner products with the conjugate transpose, and the other shows that A*A has the same rank as A. Together they yield a clean closed-form formula for the least squares solution. This material underpins linear regression, signal processing, and virtually any applied setting where you fit a model to noisy data.
When Ax = b has no solution, the best approximation is x₀ = (A*A)⁻¹A*b, provided A has full column rank. This works by projecting b onto Col(A) and solving the resulting consistent system. The same formula gives you the line of best fit in linear regression.
Orthogonal complement (W⊥)
The set of all vectors in an inner product space V that are orthogonal to every vector in a subspace W. In symbols: W⊥ = { z ∈ V : ⟨w, z⟩ = 0 for all w ∈ W }. Think of it as "everything perpendicular to W."
Orthogonal decomposition
The fact that any inner product space V splits as V ≅ W ⊕ W⊥. Every vector v ∈ V can be written uniquely as v = w + z where w ∈ W and z ∈ W⊥. In simple terms, you can always break a vector into a piece inside the subspace and a piece perpendicular to it.
Conjugate transpose (A*)
For a matrix A, the conjugate transpose A* is defined as A* = (Aᵀ)̄ = (Ā)ᵀ, i.e. transpose the matrix and then take the complex conjugate of every entry (or vice versa). Over the reals, A* is just the ordinary transpose Aᵀ. Think of it as the matrix version of "flipping and conjugating."
Projection onto Col(A)
The vector Proj_{Col(A)}(b) is the closest vector to b that lives in the column space of A. In simple terms, it is the shadow of b cast onto the subspace spanned by the columns of A.
Least squares solution
The vector x₀ that minimises ‖Ax − b‖, i.e. that makes Ax₀ as close to b as possible. When rank(A) = n, this is x₀ = (A*A)⁻¹A*b.
Normal equations
The system A*Ax = A*b. Solving the normal equations is equivalent to finding the least squares solution. In simple terms, you multiply both sides of the original (inconsistent) system by A* to get a system that is always consistent.
Let W be a subspace of an inner product space (V, ⟨·,·⟩).
Then V ≅ W ⊕ W⊥.
Concretely: every v ∈ V can be written uniquely as v = w + z, with w ∈ W and z ∈ W⊥.
This is the foundation for projection: the "w" component is the projection of v onto W.
Given Ax = b with A ∈ M_{m×n}(𝔽) and rank(A) < m, the system is inconsistent in general (b ∉ Col(A)).
Instead, solve Ax = Proj_{Col(A)}(b). This replaces the unsolvable problem with a solvable one.
Statement: Let ⟨·,·⟩k be the standard inner product on 𝔽^k. For any A ∈ M{m×n}(𝔽), we have ⟨Ax, y⟩_m = ⟨x, A*y⟩_n for all x ∈ 𝔽ⁿ and y ∈ 𝔽ᵐ.
Proof sketch:
Write out ⟨u, v⟩_k = u₁v̄₁ + ⋯ + u_k v̄_k.
Rewrite this as the matrix product v*u.
Then ⟨Ax, y⟩_m = y*(Ax) = (y*A)x = (A*y)*x = ⟨x, A*y⟩_n. ✓
Why it matters: This lemma lets you "move" a matrix from one side of an inner product to the other by replacing it with its conjugate transpose. It is the key tool in the proof of the main theorem.
Statement: rank(A*A) = rank(A) for all A ∈ M_{m×n}(𝔽).
Proof strategy: By the rank-nullity theorem, it suffices to show N(A*A) = N(A).
N(A) ⊆ N(A*A): If Ax = 0, then A*Ax = A*0 = 0. Done.
N(A*A) ⊆ N(A): If A*Ax = 0, then ⟨A*Ax, x⟩ = 0. By Lemma 1, ⟨Ax, (A*)*x⟩ = ⟨Ax, Ax⟩ = 0, so ‖Ax‖ = 0, so Ax = 0. Done.
Upshot: A*A is an n×n matrix with the same rank as A. When rank(A) = n, A*A is invertible.
Statement: If rank(A) = n, then the solution to Ax = Proj_{Col(A)}(b) is x₀ = (A*A)⁻¹A*b.
Proof outline:
Ax₀ = Proj_{Col(A)}(b) is equivalent to b − Ax₀ ∈ Col(A)⊥ (by uniqueness of the orthogonal decomposition, Theorem 1).
b − Ax₀ ∈ Col(A)⊥ means ⟨b − Ax₀, y⟩ = 0 for all y ∈ Col(A).
Every y ∈ Col(A) has the form y = Ax for some x, so ⟨b − Ax₀, Ax⟩ = 0 for all x ∈ 𝔽ⁿ.
By Lemma 1: ⟨A*(b − Ax₀), x⟩ = 0 for all x ∈ 𝔽ⁿ.
This forces A*(b − Ax₀) = 0, i.e. A*b = A*Ax₀.
By Lemma 2, rank(A*A) = rank(A) = n, so A*A is invertible. Therefore x₀ = (A*A)⁻¹A*b. ✓
Name | Formula |
|---|---|
Orthogonal decomposition | v = w + z, w ∈ W, z ∈ W⊥ (unique) |
Inner product / conjugate transpose | ⟨Ax, y⟩ = ⟨x, A*y⟩ |
Rank preservation | rank(A*A) = rank(A) |
Least squares solution | x₀ = (A*A)⁻¹A*b |
Normal equations | A*Ax = A*b |
Suppose an experiment yields measurements y₁, …, y_m taken at times t₁, …, t_m.
Hypothesis: y = ct + d for some universal constants c, d.
Ideally y_i = ct_i + d for all i, which gives the matrix equation:
| t₁ 1 | | y₁ |
| t₂ 1 | (c) = | y₂ |
| ⋮ ⋮ | (d) | ⋮ |
| t_m 1 | | y_m|
A x b
In general this system has no exact solution (more rows than columns, data has noise).
The least squares approximate solution (c₀, d₀)ᵀ = (AᵀA)⁻¹Aᵀb gives the best-fit line.
This is the mathematical foundation behind ordinary linear regression.
"If Ax = b has no solution, you cannot do anything useful." You can. The least squares approach finds the x that gets Ax as close to b as possible.
"A*A is always invertible." Only when A has full column rank (rank(A) = n). If the columns of A are linearly dependent, A*A is singular and the formula does not apply directly.
"The least squares solution makes the error zero." It minimises ‖Ax − b‖, but the error is zero only when b was already in Col(A), i.e. when the system was consistent to begin with.
"A* is just the transpose." Over ℂ, you must also conjugate. A* = (Ā)ᵀ. Over ℝ it reduces to the transpose.
⚠️ The derivation of x₀ = (A*A)⁻¹A*b, and knowing which lemma is used at each step, is a classic exam question.
⚠️ Be ready to prove that N(A*A) = N(A). The direction N(A*A) ⊆ N(A) is the one that uses Lemma 1 and the positivity of the inner product.
⚠️ The rank condition rank(A) = n is essential. Know what breaks if this fails.
⚠️ Setting up the linear regression example as a matrix system Ax = b and identifying A, x, and b is commonly tested.
True or False: V = W ⊕ W⊥ means every vector in V has a unique decomposition into a W-part and a W⊥-part.
Fill in the blank: ⟨Ax, y⟩ = ⟨x, ___⟩.
True or False: rank(A*A) can be strictly greater than rank(A).
Fill in the blank: The least squares solution exists and is unique when rank(A) = ___.
True or False: The normal equations are A*Ax = A*b.
Q: State the formula for the least squares solution to Ax = b when A has full column rank.
A: x₀ = (A*A)⁻¹A*b.
Q: In the proof that N(A*A) ⊆ N(A), which property of the inner product is used after applying Lemma 1?
A: Positive definiteness. ⟨Ax, Ax⟩ = 0 implies Ax = 0 because the inner product of a vector with itself is zero only when the vector is zero.
Q: Why is A*A invertible when rank(A) = n?
A: By Lemma 2, rank(A*A) = rank(A) = n. Since A*A is an n×n matrix with rank n, it is invertible.
Q: Set up the least squares problem for fitting y = ct + d to data points (t₁, y₁), …, (t_m, y_m). What are A, x, and b?
A: A is the m×2 matrix with rows [t_i, 1], x = (c, d)ᵀ, and b = (y₁, …, y_m)ᵀ.
Q: What does it mean geometrically that b − Ax₀ ∈ Col(A)⊥?
A: The residual (the error vector b − Ax₀) is perpendicular to the column space of A. The approximate solution Ax₀ is the point in Col(A) closest to b.
The orthogonal decomposition theorem is the abstract version of Gram-Schmidt orthogonalisation. Gram-Schmidt builds the orthonormal basis that makes the projection computable.
The least squares formula connects directly to statistics: ordinary least squares regression, ANOVA, and the pseudoinverse A⁺ = (A*A)⁻¹A* all live here.
The conjugate transpose and Lemma 1 reappear immediately in the next topic (adjoint operators and the Spectral Theorem), covered in Part 2 of these notes.
least squares, least squares approximation, normal equations, conjugate transpose, adjoint matrix, A star, A dagger, Hermitian transpose, orthogonal complement, orthogonal decomposition, projection onto column space, rank of A*A, linear regression, best fit line, overdetermined system, inconsistent system, MATH 416, abstract linear algebra, UIUC