Least Squares Solutions - Linear Algebra

SECTION 1

Historical Context & Motivation

Imagine you're trying to draw a straight line through a scatter of data points, but no single line passes through every point. This is the problem that least squares solutions were invented to solve. In the real world, systems of equations often have no exact solution because the data is noisy, measurements are imperfect, or there are more equations than unknowns. The least squares method finds the answer that comes as close as possible to satisfying all the equations at once.

1795 • Gauss's Early Work

At just 18 years old, Carl Friedrich Gauss developed the method of least squares to predict the orbit of the asteroid Ceres. He used it privately for years before publishing.

1805 • Legendre Publishes First

French mathematician Adrien-Marie Legendre published the first written account of the least squares method, calling it the "method of least squares" (méthode des moindres carrés).

1809 • Gauss Publishes His Version

Gauss published his own derivation, connecting least squares to probability theory and the normal distribution. This sparked a famous priority dispute with Legendre.

1900s • Modern Linear Algebra Connection

Mathematicians realized that the least squares solution is actually a projection onto a subspace. This insight connected the method to orthogonality and inner product spaces.

The central question is this: when a system of equations Ax = b has no exact solution, how do we find the vector x̂ that makes Ax̂ as close to b as possible? The answer lies in the geometry of orthogonal projection.

SECTION 2

Core Principles & Definitions

Before diving into the math, let's build an understanding of the key ideas. A system Ax = b may have no solution because the vector b doesn't live inside the column space of A (the set of all possible outputs Ax). The least squares approach finds the point in the column space that is nearest to b.

Inconsistent Systems

When you have more equations than unknowns (called an overdetermined system), there is usually no vector x that satisfies every equation perfectly. We need a "best fit" instead.

Column Space

The column space of a matrix A, written Col(A), is the set of all vectors that can be written as Ax for some x. If b is not in Col(A), the system Ax = b has no solution.

Orthogonal Projection

The closest point in Col(A) to b is found by dropping a perpendicular from b onto Col(A). This perpendicular drop is called an orthogonal projection, written proj_Col(A) b.

Residual Vector

The difference between b and the projection Ax̂ is called the residual vector, written r = b − Ax̂. The least squares solution minimizes the length of this residual.

Normal Equation

The least squares solution x̂ satisfies the normal equation: AᵀAx̂ = Aᵀb. This equation always has a solution, even when the original system does not.

✦

KEY TAKEAWAY

Think of it like a shadow. Imagine you're standing outside and the sun casts your shadow on the ground. Your body is the vector b (up in 3D space), the ground is the column space (a flat 2D plane), and your shadow is the projection — the closest point on the ground directly below you. The least squares solution finds that "shadow" of b on the column space.

SECTION 3

Visual Explanation

The diagram below shows the geometry behind least squares. The column space of A is represented as a flat plane. The vector b floats above the plane because it is not in Col(A). The projection b̂ = Ax̂ is the closest point on the plane to b, and the residual r = b − Ax̂ is perpendicular to the plane.

The plane represents the column space Col(A). The vector b (red dot) is not in the plane. The projection b̂ = Ax̂ (yellow dot) is the nearest point on the plane, and the residual r (pink dashed line) is perpendicular to the plane. The small square at b̂ marks the right angle.

Notice the key geometric fact: the residual r is perpendicular (orthogonal) to the column space. This perpendicularity is what makes the projection the closest point. If r were tilted at any other angle, the distance from b to the plane would be longer. This is exactly the same reason the shortest distance from a point to a line is the perpendicular distance — a fact you may remember from geometry class.

SECTION 4

Mathematical Framework

Now let's see how the geometry translates into equations. We want to minimize the distance between b and Ax, which means we want to minimize the length ‖b − Ax‖. Since the residual r = b − Ax̂ must be perpendicular to every column of A, we can write this perpendicularity condition using the transpose of A.

ORTHOGONALITY CONDITION

Aᵀ(b − Ax̂) = 0

The residual (b − Ax̂) is orthogonal to every column of A, so Aᵀ times the residual equals the zero vector.

If we distribute the Aᵀ and rearrange, we get the famous normal equation:

NORMAL EQUATION

AᵀA x̂ = Aᵀb

A = the m × n coefficient matrix, Aᵀ = transpose of A, x̂ = the least squares solution vector, b = the target vector. The product AᵀA is always an n × n matrix.

LEAST SQUARES ERROR

‖r‖ = ‖b − Ax̂‖

The least squares error is the length (norm) of the residual vector. This is the smallest possible distance between b and any vector in Col(A).

💡

Why "Least Squares"?

The name comes from what we're minimizing. The length of r is ‖r‖ = √(r₁² + r₂² + ⋯ + rₘ²). Minimizing ‖r‖ is the same as minimizing the sum of the squares of the individual residuals: r₁² + r₂² + ⋯ + rₘ². That's where "least squares" gets its name!

SECTION 5

Least Squares and Line Fitting

One of the most common uses of least squares is fitting a line of best fit to data points. Suppose you have several data points (x₁, y₁), (x₂, y₂), …, (xₘ, yₘ) and you want to find the line y = c₀ + c₁x that passes as close to all of them as possible. You can set this up as the system Ax = b where each row of A comes from one data point.

Four data points (red dots) and the best-fit line (yellow). The pink dashed segments show the residuals — the vertical distances between each point and the line. The least squares method finds the line that makes the sum of the squared residuals as small as possible.

To fit a line y = c₀ + c₁x to data points, we set up the matrix equation with A having a column of 1's and a column of x-values, x̂ = [c₀, c₁]ᵀ is the vector of unknowns (intercept and slope), and b is the vector of y-values. Since the data points usually don't all lie exactly on any line, we solve the normal equation AᵀA x̂ = Aᵀb to find the best-fit coefficients.

Matrix / Vector	Definition	Size
A	Each row is [1, xᵢ] for each data point	m × 2
x̂	The unknowns [c₀, c₁]ᵀ (intercept and slope)	2 × 1
b	The y-values [y₁, y₂, …, yₘ]ᵀ	m × 1
AᵀA	A symmetric 2×2 matrix that we can solve	2 × 2

Setting up the line-fitting problem as Ax = b

SECTION 6

Worked Example

Let's work through a complete example. We want to find the least squares solution to the system Ax = b where:

GIVEN SYSTEM

A = [1, 1; 1, 2; 1, 3], b = [2; 3; 5]

This represents the three data points (1, 2), (2, 3), (3, 5). We want the best-fit line y = c₀ + c₁x.

Finding the Least Squares Line Through Three Points

1
Step 1 — Compute Aᵀ

The transpose of A swaps rows and columns. Since A is 3 × 2, its transpose Aᵀ is 2 × 3: Aᵀ = [1, 1, 1; 1, 2, 3]
2
Step 2 — Compute AᵀA

Multiply Aᵀ (2×3) by A (3×2) to get a 2×2 matrix: AᵀA = [1+1+1, 1+2+3; 1+2+3, 1+4+9] = [3, 6; 6, 14]

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

Multiply Aᵀ (2×3) by b (3×1) to get a 2×1 vector: Aᵀb = [1(2)+1(3)+1(5); 1(2)+2(3)+3(5)] = [10; 23]

Aᵀb = [10; 23]
4
Step 4 — Solve AᵀA x̂ = Aᵀb

We solve the 2×2 system: 3c₀ + 6c₁ = 10 6c₀ + 14c₁ = 23 From the first equation: c₀ = (10 − 6c₁)/3. Substitute into the second: 6(10 − 6c₁)/3 + 14c₁ = 23 20 − 12c₁ + 14c₁ = 23 2c₁ = 3, so c₁ = 3/2 = 1.5 Then c₀ = (10 − 9)/3 = 1/3 ≈ 0.333

x̂ = [1/3; 3/2], so the best-fit line is y = 1/3 + (3/2)x
5
Step 5 — Check the Residual

Compute Ax̂ and the residual r = b − Ax̂: Ax̂ = [1/3 + 3/2; 1/3 + 3; 1/3 + 9/2] = [11/6; 10/3; 29/6] ≈ [1.833; 3.333; 4.833] r = b − Ax̂ = [2 − 1.833; 3 − 3.333; 5 − 4.833] ≈ [0.167; −0.333; 0.167] ‖r‖ = √(0.028 + 0.111 + 0.028) = √0.167 ≈ 0.408

Least squares error ≈ 0.408

SECTION 7

Strengths & Limitations

The least squares method is incredibly powerful and widely used, but like any mathematical tool, it has both strengths and limitations. Understanding these helps you know when to use it and when to be cautious.

Strengths	Limitations
Always gives an answer — even when the system has no exact solution, the normal equation AᵀAx̂ = Aᵀb is always consistent.	Sensitive to outliers — a single extreme data point can drag the best-fit line far from the majority of the data.
Has a clear geometric meaning — the solution is the orthogonal projection, which makes it easy to visualize and understand.	Only finds linear relationships (in standard form). If the true pattern is curved, a straight line won't capture it well.
Computationally efficient — solving the normal equation involves multiplying by Aᵀ and then solving a small system.	If AᵀA is nearly singular (close to having no inverse), the solution may be unstable and sensitive to small data changes.
Foundation for many techniques — used in data science, physics, engineering, statistics, and machine learning.	Assumes errors are equally important — it treats every residual the same, which may not suit all applications.

Comparing the strengths and limitations of the least squares method

✦

KEY TAKEAWAY

Think of least squares like a GPS finding the nearest road when you're off in a field. It doesn't put you exactly where you want to be — it puts you at the closest reachable point. That's tremendously useful, but if the "road" (your model) is in the wrong place entirely, the nearest point on it still won't be helpful. Choosing the right model matters just as much as finding the best fit within it.

SECTION 8

Connections to Advanced Theory

Least squares is not just a stand-alone technique — it connects to several powerful ideas in mathematics. As you advance in linear algebra, you'll see how it links to orthogonal bases, matrix factorizations, and even machine learning. Here's a preview of those connections.

Concept	Connection to Least Squares	Where You'll See It
QR Factorization	Decomposes A into an orthogonal matrix Q and upper triangular matrix R. This gives a more numerically stable way to solve least squares: Rx̂ = Qᵀb.	Numerical linear algebra, computer algorithms
Gram-Schmidt Process	Converts any set of vectors into an orthogonal set. This is the foundation for computing the QR factorization used in least squares.	Inner product spaces, orthogonal projections
Pseudoinverse (A⁺)	A generalized inverse that works even when A doesn't have a regular inverse. The least squares solution can be written x̂ = A⁺b.	Advanced linear algebra, data science
Linear Regression	In statistics, fitting a line to data using least squares is called linear regression. It's the same math with a statistical interpretation.	Statistics, machine learning, data analysis

How least squares connects to advanced topics

If you continue studying linear algebra, you'll discover that the Singular Value Decomposition (SVD) provides the most general and robust framework for least squares problems. The SVD works even when AᵀA is not invertible, making it the go-to tool in modern computational applications. Many algorithms in machine learning and artificial intelligence rely on least squares through SVD every day.

SECTION 9

Practice Problems

Question 1: CONCEPTUAL

If the system Ax = b actually has an exact solution, what happens when you apply the least squares method? What will the residual vector r look like?

Show answer

When Ax = b has an exact solution, the vector b is already in the column space of A. The least squares solution x̂ will be the same as the exact solution x. The residual r = b − Ax̂ will be the zero vector because the projection of b onto Col(A) is b itself. In other words, least squares is a generalization of solving systems — when an exact answer exists, it finds it.

Question 2: BASIC CALCULATION

Given A = [1, 0; 0, 1; 1, 1] and b = [2; 1; 4], compute AᵀA and Aᵀb.

Show answer

First, find Aᵀ = [1, 0, 1; 0, 1, 1]. Then AᵀA = [1+0+1, 0+0+1; 0+0+1, 0+1+1] = [2, 1; 1, 2]. Next, Aᵀb = [1(2)+0(1)+1(4); 0(2)+1(1)+1(4)] = [6; 5]. These are the components of the normal equation AᵀAx̂ = Aᵀb that you would solve in the next step.

Question 3: INTERMEDIATE

Using the results from Problem 2 (AᵀA = [2, 1; 1, 2] and Aᵀb = [6; 5]), solve for the least squares solution x̂ and compute the residual vector.

Show answer

Solve the system 2x₁ + x₂ = 6 and x₁ + 2x₂ = 5. Multiply the first equation by 2: 4x₁ + 2x₂ = 12. Subtract the second: 3x₁ = 7, so x₁ = 7/3. Then x₂ = (5 − 7/3)/2 = (8/3)/2 = 4/3. So x̂ = [7/3; 4/3]. Now Ax̂ = [7/3; 4/3; 7/3+4/3] = [7/3; 4/3; 11/3]. The residual is r = b − Ax̂ = [2−7/3; 1−4/3; 4−11/3] = [−1/3; −1/3; 1/3]. Notice ‖r‖ = √(1/9+1/9+1/9) = √(1/3) ≈ 0.577.

Question 4: APPLIED

A student measures the temperature (°C) at four times during an experiment: at t = 0, T = 20; at t = 1, T = 23; at t = 2, T = 25; at t = 3, T = 30. Set up the matrix A and vector b for finding the best-fit line T = c₀ + c₁t, and then solve for c₀ and c₁.

Show answer

Set A = [1,0; 1,1; 1,2; 1,3] and b = [20; 23; 25; 30]. Compute AᵀA = [4, 6; 6, 14] and Aᵀb = [98; 161]. The normal equation gives 4c₀ + 6c₁ = 98 and 6c₀ + 14c₁ = 161. From the first: c₀ = (98−6c₁)/4. Substitute: 6(98−6c₁)/4 + 14c₁ = 161 → 147 − 9c₁ + 14c₁ = 161 → 5c₁ = 14, so c₁ = 2.8 and c₀ = (98−16.8)/4 = 20.3. The best-fit line is T ≈ 20.3 + 2.8t, meaning the temperature increases by about 2.8°C per unit time.

Question 5: CRITICAL THINKING

Explain why the residual vector r = b − Ax̂ must be orthogonal to every column of A. What would go wrong geometrically if it weren't orthogonal? Use the idea of distance minimization in your reasoning.

Show answer

If the residual r were not perpendicular to Col(A), then r would have a component that lies inside the column space. That component would point along a direction you could "slide" the projection to get even closer to b, which means you haven't found the closest point yet. Geometrically, only when r is perfectly perpendicular is there no way to reduce the distance further — any movement along the column space would start increasing the distance. This is the same reason the shortest distance from a point to a plane (or a line) is always the perpendicular distance. Algebraically, this perpendicularity condition Aᵀr = 0 is exactly what produces the normal equation AᵀAx̂ = Aᵀb.

SUMMARY

Lesson Summary

Summary

When a system Ax = b has no exact solution, the least squares solution x̂ minimizes the distance ‖b − Ax‖ by finding the vector in the column space of A that is closest to b. This closest point is the orthogonal projection of b onto Col(A), and the residual r = b − Ax̂ is perpendicular to every column of A.

The solution is found by solving the normal equation AᵀAx̂ = Aᵀb. This technique powers line fitting (linear regression), data analysis, and many algorithms in science and engineering. Key advanced extensions include QR factorization and the pseudoinverse, which provide more robust computational methods.