Normal Equations - Linear Algebra

SECTION 1

Historical Context & Motivation

Imagine you're trying to draw a straight line through a scatter of data points on a graph. No single line passes through every point, so you want the line that comes as close as possible to all of them. This is the problem of least squares, and it has been one of the most important ideas in mathematics for over two centuries.

In many real situations — predicting the weather, tracking a satellite, or fitting a trend line in science class — you have more data points than unknowns. The system of equations you get has no exact solution. Mathematicians needed a reliable formula to find the best approximate solution, and that formula is what we call the normal equations.

1795 • Gauss Invents Least Squares

Carl Friedrich Gauss, at just 18 years old, develops the method of least squares to predict the orbit of the asteroid Ceres. He keeps it unpublished for years.

1805 • Legendre Publishes First

Adrien-Marie Legendre independently discovers and publishes the least-squares method, writing out the normal equations explicitly for the first time.

1809 • Gauss Publishes His Proof

Gauss finally publishes his version of least squares and connects it to probability theory. He shows why minimizing squared errors is the most natural choice.

1900s • Linear Algebra Formalizes the Idea

Mathematicians rewrite the normal equations using matrix notation — AᵀAx̂ = Aᵀb — making it easy to solve with computers and connecting it to orthogonal projections.

The central question the normal equations answer is: when a system Ax = b has no exact solution, how do we find the vector x̂ that makes Ax̂ as close to b as possible? The answer turns out to hinge on a beautiful idea from geometry — orthogonal projection.

SECTION 2

Core Principles & Definitions

Before we dive into the formula, let's build up the key ideas one at a time. Each concept is like a building block — you'll need all of them to understand why the normal equations work.

Overdetermined System

A system Ax = b is overdetermined when there are more equations than unknowns. Think of it as having too many constraints — you usually can't satisfy all of them at once.

Residual Vector

The residual is the error vector r = b − Ax. It measures how far off our guess x is from the target b. The normal equations minimize the length of this vector.

Column Space

The column space of A is the set of all vectors you can make by combining A's columns. If b isn't in that set, no exact solution exists — but you can project b onto it.

Orthogonal Projection

An orthogonal projection drops a perpendicular from b onto the column space. The foot of that perpendicular, Ax̂, is the closest point in the column space to b.

Transpose (Aᵀ)

The transpose of a matrix flips it over its diagonal — rows become columns. It plays a starring role in the normal equations because Aᵀ acts like a 'bridge' that enforces perpendicularity.

✦

KEY TAKEAWAY

Think of the normal equations like a GPS that can't take you exactly where you want to go. Instead, it finds the closest road to your destination. The 'closest road' is the column space of A, and the GPS uses a perpendicular drop (orthogonal projection) to find the nearest point on that road to your target b.

SECTION 3

Visual Explanation

The diagram below shows the geometric heart of the normal equations. The vector b lives in a higher-dimensional space, but the column space of A is a flat plane (or subspace) inside that space. Since b is not on the plane, no exact solution exists.

The amber arrow is the target vector b. The cyan arrow Ax̂ is its projection onto the column space (the shaded plane). The dashed pink arrow is the residual r, which is perpendicular to the plane. The normal equations guarantee this perpendicularity.

The key geometric insight is this: the closest point on the plane to b is found by dropping a perpendicular from b down to the plane. That perpendicular is the residual r = b − Ax̂. Because r is perpendicular to every vector in the column space, we can write Aᵀr = 0. Expanding r gives us Aᵀ(b − Ax̂) = 0, which rearranges into the normal equations: AᵀAx̂ = Aᵀb.

SECTION 4

Mathematical Framework

Let's build the formula step by step. We start with a system Ax = b that has no exact solution because there are more equations than unknowns.

GOAL: MINIMIZE THE RESIDUAL

Minimize ‖b − Ax‖²

We want to find the vector x̂ that makes the squared length of the residual b − Ax as small as possible. The double bars ‖ ‖ mean 'length' (also called the norm).

PERPENDICULARITY CONDITION

Aᵀ(b − Ax̂) = 0

The residual b − Ax̂ must be perpendicular to every column of A. Multiplying by Aᵀ (the transpose) checks all columns at once. When this equals the zero vector, we know r is perpendicular to the column space.

THE NORMAL EQUATIONS

AᵀA x̂ = Aᵀb

Distribute the Aᵀ in the perpendicularity condition and rearrange. Here AᵀA is a square matrix (n × n) even if A isn't square, and Aᵀb is a vector. You solve this like any square system to find x̂.

EXPLICIT SOLUTION (when AᵀA is invertible)

x̂ = (AᵀA)⁻¹ Aᵀb

If the columns of A are linearly independent (no column is a combination of others), then AᵀA is invertible. You can directly compute x̂ using the inverse. The matrix (AᵀA)⁻¹Aᵀ is sometimes called the pseudo-inverse of A.

ℹ

Why "Normal"?

The word 'normal' here comes from geometry — it means perpendicular. The equations are called 'normal' because they enforce the condition that the residual is perpendicular (normal) to the column space. It has nothing to do with 'ordinary' or 'standard.'

SECTION 5

Detailed Breakdown — Fitting a Line to Data

The most common use of the normal equations is finding the best-fit line (also called the least-squares regression line) through a set of data points. Suppose you have points (x₁, y₁), (x₂, y₂), …, (xₘ, yₘ) and you want to find the line y = c₀ + c₁x that best fits them.

You can write each point as an equation: c₀ + c₁x₁ = y₁, c₀ + c₁x₂ = y₂, and so on. Stack these into a matrix equation Ax = b, where A has a column of 1s and a column of x-values, x = [c₀, c₁]ᵀ is what you're solving for, and b is the column of y-values. With more than two data points, the system is overdetermined.

Five data points (amber dots) are plotted with the best-fit line (cyan) found by the normal equations. The dashed pink segments are the residuals — the vertical distances the normal equations minimize (in a squared sense).

In the diagram above, notice how the cyan line doesn't pass through any point perfectly — but it gets as close as possible to all of them. The normal equations minimize the sum of the squared residuals (the squared lengths of the pink dashed lines). Squaring is important because it prevents positive and negative errors from canceling each other out, and it penalizes big misses more than small ones.

SECTION 6

Worked Example

Let's use the normal equations to find the best-fit line through three points: (1, 1), (2, 1), and (3, 3). We want the line y = c₀ + c₁x.

Finding the Least-Squares Line Through Three Points

1
Step 1 — Set Up the System Ax = b

Each point gives one equation: c₀ + c₁(1) = 1, c₀ + c₁(2) = 1, c₀ + c₁(3) = 3. In matrix form, A = [[1, 1], [1, 2], [1, 3]], x = [c₀, c₁]ᵀ, b = [1, 1, 3]ᵀ. Notice A is 3 × 2 — more rows than columns, so the system is overdetermined.

A is 3 × 2, x is 2 × 1, b is 3 × 1
2
Step 2 — Compute Aᵀ

The transpose of A flips rows and columns: Aᵀ = [[1, 1, 1], [1, 2, 3]]. This is a 2 × 3 matrix.

Aᵀ = [[1, 1, 1], [1, 2, 3]]
3
Step 3 — Compute AᵀA

Multiply Aᵀ (2 × 3) by A (3 × 2) to get a 2 × 2 matrix. Top-left: 1×1 + 1×1 + 1×1 = 3. Top-right: 1×1 + 1×2 + 1×3 = 6. Bottom-left: 1×1 + 2×1 + 3×1 = 6. Bottom-right: 1×1 + 2×2 + 3×3 = 14.

AᵀA = [[3, 6], [6, 14]]
4
Step 4 — Compute Aᵀb

Multiply Aᵀ (2 × 3) by b (3 × 1). First entry: 1×1 + 1×1 + 1×3 = 5. Second entry: 1×1 + 2×1 + 3×3 = 12.

Aᵀb = [5, 12]ᵀ
5
Step 5 — Solve AᵀA x̂ = Aᵀb

We need to solve [[3, 6], [6, 14]] × [c₀, c₁]ᵀ = [5, 12]ᵀ. This is a 2 × 2 system: 3c₀ + 6c₁ = 5 and 6c₀ + 14c₁ = 12. Multiply the first equation by 2: 6c₀ + 12c₁ = 10. Subtract from the second: 2c₁ = 2, so c₁ = 1. Substitute back: 3c₀ + 6 = 5, so c₀ = −1/3.

Best-fit line: y = −1/3 + x, or equivalently y = x − 0.333
6
Step 6 — Verify: Check the Residual

Plug back in: at x = 1, ŷ = 2/3 (residual: 1/3). At x = 2, ŷ = 5/3 (residual: −2/3). At x = 3, ŷ = 8/3 (residual: 1/3). The residual vector r = [1/3, −2/3, 1/3]ᵀ. Check: Aᵀr = [1×(1/3) + 1×(−2/3) + 1×(1/3), 1×(1/3) + 2×(−2/3) + 3×(1/3)] = [0, 0]ᵀ. The residual is perpendicular to the column space, confirming our answer.

Aᵀr = 0 ✓ — The perpendicularity condition is satisfied!

SECTION 7

Strengths & Limitations

The normal equations are powerful, but like any tool, they have trade-offs. Here's an honest look at when they shine and when you might want a different approach.

Aspect	Strength	Limitation
Simplicity	One clean formula: x̂ = (AᵀA)⁻¹Aᵀb. Easy to memorize and implement.	Requires computing a matrix inverse, which can be slow for large matrices.
Exact Answer	Gives the exact least-squares solution directly — no iteration or guessing needed.	Rounding errors can build up when AᵀA has values that are very close together.
Geometric Insight	Connects directly to the beautiful idea of orthogonal projection.	The geometric picture can be hard to visualize beyond 3 dimensions.
Scalability	Great for small-to-medium problems (a few hundred variables).	For very large data sets, methods like QR decomposition or gradient descent are preferred.
Uniqueness	Unique solution when A has linearly independent columns.	If columns are dependent, AᵀA is not invertible and the formula breaks down.

Comparison of strengths and limitations of the normal equations approach

✦

KEY TAKEAWAY

Think of the normal equations as a precise ruler — perfect for measuring a bookshelf, but not ideal for surveying an entire city. For small-to-medium problems, they give you a fast, exact answer. For massive data or numerically tricky situations, more advanced methods (like QR decomposition) are more reliable, just as a surveyor uses GPS instead of a ruler.

SECTION 8

Connection to Advanced Topics

The normal equations are your first step into a much larger world. Many advanced techniques in data science, machine learning, and engineering build on the same least-squares idea. Here's a preview of where the journey leads.

Normal Equations (what you learned)	Advanced Version
Solve AᵀAx̂ = Aᵀb directly	QR Decomposition: Factor A = QR and solve Rx̂ = Qᵀb. More numerically stable.
Find the best-fit line (one output)	Multiple Regression: Same formula, but A has many columns — fitting a plane or hyperplane to data.
Minimize ‖b − Ax‖²	Regularization (Ridge/Lasso): Add a penalty term to prevent overfitting. The formula becomes (AᵀA + λI)x̂ = Aᵀb.
Works when AᵀA is invertible	SVD (Singular Value Decomposition): Always works, even when columns are dependent. Decomposes A into three simpler matrices.

How the normal equations connect to more advanced techniques

Every time a self-driving car processes sensor data, a streaming service recommends a movie, or a scientist models climate data, some version of least squares is running behind the scenes. The normal equations are the foundation on which all these technologies are built. Mastering them now gives you a head start on some of the most important math in modern science and engineering.

SECTION 9

Practice Problems

Question 1: CONCEPTUAL

In your own words, explain why the residual vector r = b − Ax̂ must be perpendicular to the column space of A in order for x̂ to be the least-squares solution. You may use a geometric argument or an everyday analogy.

Show answer

The residual must be perpendicular to the column space because perpendicularity guarantees the shortest distance. Think of standing in a field and looking at a straight road — the closest point on the road is found by walking straight toward it at a right angle, not at a slant. If the residual were not perpendicular, you could slide Ax̂ along the column space and find a point even closer to b, meaning you hadn't found the true minimum yet. The perpendicularity condition Aᵀ(b − Ax̂) = 0 is the mathematical way of ensuring that no further improvement is possible.

Question 2: BASIC CALCULATION

Given A = [[1, 1], [1, 2]] and b = [3, 5]ᵀ, compute AᵀA and Aᵀb. Then solve the normal equations AᵀAx̂ = Aᵀb for x̂.

Show answer

First, Aᵀ = [[1, 1], [1, 2]]. Then AᵀA = [[1×1+1×1, 1×1+1×2], [1×1+2×1, 1×2+2×2]] = [[2, 3], [3, 5]]. Also Aᵀb = [1×3+1×5, 1×3+2×5]ᵀ = [8, 13]ᵀ. Now solve [[2,3],[3,5]] × [c₀,c₁]ᵀ = [8,13]ᵀ. From 2c₀ + 3c₁ = 8, multiply by 3/2: 3c₀ + 4.5c₁ = 12. Subtract from 3c₀ + 5c₁ = 13 to get 0.5c₁ = 1, so c₁ = 2. Then c₀ = (8 − 6)/2 = 1. The solution is x̂ = [1, 2]ᵀ. (Note: this system actually has an exact solution since A is square and invertible.)

Question 3: INTERMEDIATE

Find the least-squares solution to the overdetermined system: x₁ + x₂ = 2, x₁ − x₂ = 0, x₁ + 2x₂ = 4. Write the system in matrix form, form the normal equations, and solve.

Show answer

In matrix form: A = [[1,1],[1,−1],[1,2]], b = [2,0,4]ᵀ. Compute Aᵀ = [[1,1,1],[1,−1,2]]. Then AᵀA = [[1+1+1, 1−1+2],[1−1+2, 1+1+4]] = [[3, 2],[2, 6]]. And Aᵀb = [1×2+1×0+1×4, 1×2+(−1)×0+2×4]ᵀ = [6, 10]ᵀ. Solve 3x₁ + 2x₂ = 6 and 2x₁ + 6x₂ = 10. Multiply the first equation by 3: 9x₁ + 6x₂ = 18. Subtract the second: 7x₁ = 8, so x₁ = 8/7 ≈ 1.14. Then x₂ = (6 − 3×8/7)/2 = (42/7 − 24/7)/2 = (18/7)/2 = 9/7 ≈ 1.29. The least-squares solution is x̂ = [8/7, 9/7]ᵀ.

Question 4: APPLIED

A student measures the temperature (°C) at four times: at t = 0 hours, T = 20; at t = 1, T = 22; at t = 2, T = 23; at t = 3, T = 27. Use the normal equations to find the best-fit line T = c₀ + c₁t. Then predict the temperature at t = 5 hours.

Show answer

Set up A = [[1,0],[1,1],[1,2],[1,3]], b = [20,22,23,27]ᵀ. Compute AᵀA = [[4, 6],[6, 14]] and Aᵀb = [92, 148]ᵀ. Solve 4c₀ + 6c₁ = 92 and 6c₀ + 14c₁ = 148. Multiply the first by 1.5: 6c₀ + 9c₁ = 138. Subtract from the second: 5c₁ = 10, so c₁ = 2. Then c₀ = (92 − 12)/4 = 20. The best-fit line is T = 20 + 2t. At t = 5: T = 20 + 2(5) = 30°C. The model predicts the temperature will be about 30°C after 5 hours, though extrapolation beyond the data range should be done cautiously.

Question 5: CRITICAL THINKING

Suppose A is a matrix whose two columns are identical (for example, A = [[1,1],[2,2],[3,3]]). Explain why the normal equations AᵀAx̂ = Aᵀb cannot be solved using the formula x̂ = (AᵀA)⁻¹Aᵀb. What does this mean geometrically about the column space? Is there still a least-squares solution?

Show answer

When the two columns of A are identical, they are linearly dependent — one is a copy of the other. This means the column space is only a one-dimensional line, not a two-dimensional plane. The matrix AᵀA becomes singular (its determinant is zero), so it cannot be inverted. For example, with A = [[1,1],[2,2],[3,3]], AᵀA = [[14,14],[14,14]], which has determinant 14×14 − 14×14 = 0. Geometrically, the projection of b onto the column space still exists and is unique, but infinitely many combinations of c₀ and c₁ give the same projected vector (since the two columns contribute the same thing). A least-squares solution still exists — in fact, infinitely many exist — but you need the pseudo-inverse (via SVD) rather than the simple inverse formula to find one systematically.

SUMMARY

Lesson Summary

Summary

The normal equations provide a direct formula — AᵀAx̂ = Aᵀb — for finding the least-squares solution to an overdetermined system. They work by requiring the residual vector r = b − Ax̂ to be perpendicular (normal) to the column space of A, which guarantees that Ax̂ is the closest possible approximation to b.

The key steps are: form the transpose Aᵀ, compute AᵀA and Aᵀb, then solve the resulting square system. This technique powers regression line fitting, data analysis, and countless applications in science and engineering. When A's columns are linearly independent, the explicit solution is x̂ = (AᵀA)⁻¹Aᵀb.