Difficulty: Intermediate-Advanced | Prerequisites: Orthogonal projection (Theorem 1 and 2 from Part 1), column space, rank, nullity, conjugate transpose.
When a linear system Ax = b has no exact solution (more equations than unknowns, typically), you can still find the "best" approximate answer by projecting b onto the column space of A. The result, called the least squares solution, minimises ‖Ax − b‖ and is given by x₀ = (AA)⁻¹Ab when A has full column rank.
Least squares approximate solution (x₀)
The vector x₀ such that Ax₀ = Proj_Col(A)(b), i.e. Ax₀ is the closest point in Col(A) to b. It minimises ‖Ax − b‖ over all x.
In simple terms, x₀ is the "best you can do" when Ax = b has no exact answer.
Normal equation
The equation AAx₀ = Ab, which x₀ satisfies. Solving this is how you compute the least squares solution without needing an orthonormal basis for Col(A).
Think of it as the algebraic shortcut that replaces "find an orthonormal basis and project" with "multiply both sides by A* and solve."
Conjugate transpose / adjoint (A)*
For a matrix A ∈ M_{m×n}(F), the adjoint A* is defined as A* = (conjugate of A)ᵀ. Over the reals, A* = Aᵀ. The defining property is ⟨Ax, y⟩_m = ⟨x, A*y⟩_n for all x ∈ Fⁿ, y ∈ Fᵐ.
Column space (Col(A))
The subspace of Fᵐ spanned by the columns of A. Equivalently, Col(A) = {Ax | x ∈ Fⁿ}. When rank(A) < m, the system Ax = b is inconsistent for most b, because b typically lies outside Col(A).
Null space (N(A))
The set of all x such that Ax = 0. Lemma 2 in the lecture shows that N(AA) = N(A), which is the key to proving that AA is invertible when A has full column rank.
Consider Ax = b where A ∈ M_{m×n}(F).
If rank(A) < m, then for most b ∈ Fᵐ the system has no solution, because b does not lie in Col(A).
Col(A) is a subspace of Fᵐ with dimension rank(A) < m, so it is a "thin slice" of the full space.
By the best approximation theorem (Theorem 2), there is a unique vector in Col(A) closest to b, namely Proj_Col(A)(b). Since every vector in Col(A) has the form Ax for some x, we can write this closest point as Ax₀. The vector x₀ is the least squares approximate solution.
Note: x₀ itself may not be unique (different x values can give the same Ax₀), but the projected vector Ax₀ is always unique.
Let ⟨ , ⟩k be the standard inner product on F^k. For any A ∈ M{m×n}(F):
⟨Ax, y⟩_m = ⟨x, A*y⟩_n for all x ∈ Fⁿ, y ∈ Fᵐ
Proof: Write ⟨u, v⟩ = vu (conjugate transpose times u). Then ⟨Ax, y⟩ = y(Ax) = (yA)x = (Ay)x = ⟨x, Ay⟩.
This identity is the reason A* appears in the normal equations: it lets you "move A across" an inner product.
Proof: By rank-nullity, it suffices to show N(A*A) = N(A).
N(A) ⊂ N(AA): If Ax = 0, then AAx = A*0 = 0.
N(AA) ⊂ N(A): If AAx = 0, then ⟨AAx, x⟩ = 0, so ⟨Ax, (A)*x⟩ = ⟨Ax, Ax⟩ = 0 by Lemma 1. Therefore ‖Ax‖ = 0, hence Ax = 0.
Since N(AA) = N(A), they have the same nullity, so rank(AA) = rank(A).
If rank(A) = n (full column rank, where n ≤ m), then the least squares approximate solution is unique and given by:
x₀ = (AA)⁻¹ A b
Proof: We need Proj_Col(A)(b) = Ax₀.
By the uniqueness in Theorem 1, this is equivalent to b − Ax₀ ∈ Col(A)⊥.
b − Ax₀ ∈ Col(A)⊥
⟺ ⟨b − Ax₀, Ax⟩ = 0 for all x ∈ Fⁿ (since Ax ranges over Col(A))
⟺ ⟨A*(b − Ax₀), x⟩ = 0 for all x ∈ Fⁿ (by Lemma 1)
⟺ A*(b − Ax₀) = 0
⟺ Ab = AAx₀
Since rank(A) = n, Lemma 2 gives rank(AA) = n. So AA ∈ M_{n×n} is invertible, and x₀ = (AA)⁻¹ Ab.
Suppose an experiment yields measurements y₁, …, yₘ taken at times t₁, …, tₘ, and the data looks roughly linear.
Hypothesis: y = ct + d for some constants c, d.
Ideally we would have yᵢ = ctᵢ + d for every i. In matrix form:
| t₁ 1 | | y₁ | | t₂ 1 | (c) = | y₂ | | ⋮ ⋮ | (d) | ⋮ | | tₘ 1 | | yₘ |
This is Ax = b, where A is the m × 2 matrix with columns [t₁ … tₘ]ᵀ and [1 … 1]ᵀ, x = (c, d)ᵀ, and b = (y₁, …, yₘ)ᵀ.
With m > 2, this system is almost certainly inconsistent (the data points do not lie exactly on a line). The least squares solution:
(c₀, d₀)ᵀ = (AᵀA)⁻¹Aᵀb
gives the slope c₀ and intercept d₀ of the line that best fits the data in the least-squares sense, i.e. the line that minimises Σ(yᵢ − c₀tᵢ − d₀)².
Adjoint identity (Lemma 1)
⟨Ax, y⟩ = ⟨x, A*y⟩
Rank preservation (Lemma 2)
rank(AA) = rank(A), because N(AA) = N(A)
Least squares formula (full column rank)
x₀ = (AA)⁻¹ A b
Normal equation (equivalent form)
AA x₀ = A b
Conjugate transpose examples
For a column vector (1, 2, 1+i)ᵀ: its adjoint is the row vector (1, 2, 1−i).
For a matrix: swap rows and columns, then conjugate every entry.
Least squares is the mathematical foundation of linear regression in statistics, which is used everywhere from predicting house prices to fitting trendlines in experimental physics. It is also the basis of GPS positioning (over-determined systems from satellite signals) and signal reconstruction in communications engineering. Whenever you have more measurements than unknowns and the data is noisy, least squares gives you the best linear fit.
Students often confuse the least squares solution x₀ with an exact solution. It is not. Ax₀ ≠ b in general; Ax₀ is the projection of b onto Col(A), which is the closest you can get.
A common error is applying x₀ = (AA)⁻¹Ab when A does not have full column rank. If rank(A) < n, then A*A is not invertible and this formula fails. (The least squares solution still exists but is not unique.)
Students sometimes forget to use the conjugate transpose A* and instead use the plain transpose Aᵀ. Over the reals these are the same, but over the complex numbers they differ. Always use A* in the general setting.
Confusing "minimises ‖Ax − b‖" with "minimises ‖x‖." Least squares minimises the residual (the distance from b to Ax), not the size of x itself.
⚠️ Know how to set up the matrix A and vector b for a least squares problem (as in the linear regression example). This is a common exam question.
⚠️ Be able to state and prove both lemmas. Lemma 1 (adjoint identity) is short but essential. Lemma 2 (rank preservation via N(A*A) = N(A)) is a favourite standalone proof question.
⚠️ The derivation of the normal equation AAx₀ = Ab from the condition b − Ax₀ ∈ Col(A)⊥ is a proof you should be able to reproduce from scratch.
⚠️ Check the full column rank condition before applying the formula. If the problem does not state rank(A) = n, you need to verify it or discuss what happens when it fails.
True or False: The least squares solution x₀ satisfies Ax₀ = b exactly. (False, unless b ∈ Col(A))
Fill in the blank: The normal equation is AA x₀ = ___. (Ab)
True or False: rank(A*A) = rank(A) for any matrix A. (True)
Fill in the blank: The adjoint identity says ⟨Ax, y⟩ = ⟨x, ___⟩. (A*y)
True or False: If rank(A) < n, the formula x₀ = (AA)⁻¹Ab still works. (False, A*A is not invertible)
Q: Why does Proj_Col(A)(b) have the form Ax₀ for some x₀?
A: Because Proj_Col(A)(b) lies in Col(A) by definition, and every vector in Col(A) is a linear combination of the columns of A, which can be written as Ax for some x.
Q: Derive the normal equation from the condition that b − Ax₀ is orthogonal to Col(A).
A: b − Ax₀ ∈ Col(A)⊥ means ⟨b − Ax₀, Ax⟩ = 0 for all x. By Lemma 1, ⟨A*(b − Ax₀), x⟩ = 0 for all x, so A*(b − Ax₀) = 0, giving Ab = AAx₀.
Q: Why is A*A invertible when rank(A) = n?
A: By Lemma 2, rank(AA) = rank(A) = n. Since AA is n × n with rank n, it is invertible.
Q: Set up the least squares problem for fitting y = ct + d to data points (1, 3), (2, 5), (3, 8).
A: A = [[1, 1], [2, 1], [3, 1]], b = (3, 5, 8)ᵀ, x = (c, d)ᵀ. The least squares solution is (c₀, d₀)ᵀ = (AᵀA)⁻¹Aᵀb.
Least squares is a direct application of the orthogonal projection and decomposition theory from Part 1 of these notes. It also connects forward to singular value decomposition (SVD), which provides a more numerically stable way to compute least squares solutions, and to the pseudoinverse (Moore-Penrose inverse), which generalises the formula when A does not have full column rank. In statistics, this is the mathematical backbone of ordinary least squares (OLS) regression.
least squares, approximate solution, normal equation, AAx = Ab, conjugate transpose, adjoint, column space, null space, rank, full column rank, linear regression, line of best fit, over-determined system, Proj_Col(A), best approximation, pseudoinverse, SVD, MATH 416, abstract linear algebra