What is the least-squares solution of a linear system?

When Ax = b has no exact solution, the least-squares solution x̂ is the vector that makes the error b − Ax as short as possible. Geometrically, Ax̂ is the orthogonal projection of b onto the column space of A, the closest point of that space to b, and the error is perpendicular to the column space. Algebraically, x̂ solves the normal equations AᵀA x̂ = Aᵀb.

Where do the normal equations come from?

The error e = b − Ax̂ must be perpendicular to every column of A, because the projection of b onto the column space is the nearest point and the difference from the nearest point is perpendicular to the space. Perpendicular to every column means Aᵀe = 0, that is Aᵀ(b − Ax̂) = 0, which rearranges to AᵀA x̂ = Aᵀb. These equations are always consistent, and have a unique solution when the columns of A are independent.

How does least squares fit a line to data?

To fit b = C + Dt to points (tᵢ, bᵢ), write one equation per point, C + Dtᵢ = bᵢ. In matrix form A has a column of ones and a column of the tᵢ, x = (C, D) and b is the column of the bᵢ. The system is inconsistent unless the points are collinear, so solve the normal equations instead; the resulting line minimizes the sum of the squared vertical distances from the points to the line. Polynomial fits add columns of tᵢ², tᵢ³ and so on.

What happens if the columns of A are dependent?

Then AᵀA is singular and the normal equations have infinitely many solutions: many different x̂ produce the same projection p, differing by vectors in the null space of A. The projection itself is still unique, because the column space and the nearest point in it do not depend on how the space is described. The usual remedies are to remove a redundant column or to use the pseudoinverse, which selects the least-squares solution of smallest length.

Least Squares and Projection

How to use

The Preset pills load seven problems: lines through 3 and 4 points, a parabola through 4 points, projection onto a line and onto a plane, $\mathbf{b}$ in the column space, and dependent columns. Learn more about choosing a problem
The Size steppers (▲ / ▼) set $2$ to $4$ equations and $1$ to $3$ unknowns; Shuffle data builds a polynomial design matrix with random data. Learn more about getting started
Type into any entry of $A$ or of the amber column $\mathbf{b}$ ; the run is rebuilt at once. Learn more about editing the problem
▶ Play runs the procedure, Next → and ← Back step one scene at a time, Reset returns to the start, and the speed menu sets the pace. Learn more about the controls
The scenes run in a fixed order: consistency check, normal equations, solve for $\hat{\mathbf{x}}$ , projection $\mathbf{p}$ , residual $\mathbf{e}$ , projection matrix $P$ , and the fitted curve. Learn more about the scenes in order
$\mathbf{b}$ stays amber, $\hat{\mathbf{x}}$ is the accent, and products that must come out zero, such as $A^T\mathbf{e}$ , are grey; the Step explanations log keeps every stage. Learn more about reading a scene

Project b onto the column space of A: the normal equations AᵀA x̂ = Aᵀb, the projection p = A x̂, and the perpendicular residual.

Preset?When Ax = b has no solution — b is not in the column space of A — the least-squares solution x̂ makes Ax̂ as close to b as possible. The closest point is the projection p of b onto the column space, and the error e = b − p is perpendicular to every column: Aᵀ(b − Ax̂) = 0, the normal equations AᵀA x̂ = Aᵀb. When the columns are independent AᵀA is invertible and P = A(AᵀA)⁻¹Aᵀ is the projection matrix.

Size

A3×2

A and b

A3×2

x =

Step 1 / 8

Step explanations

1Least squares: 3 equations, 2 unknowns

Ax = b has 3 equations and 2 unknowns: fitting a line b = C + Dt to 3 data points, one equation per point. It has an exact solution only if b lies in the column space of A. When it does not, the best we can do is make Ax as close to b as possible: minimize |b − Ax|. That minimum is reached at the projection of b onto the column space, and the normal equations find it.

Ax = b has no solution; make Ax as close to b as possible. Learn more about the setup · what least squares is

Key Terms

Getting Started with the Visualizer

The Residual Is Perpendicular

The Projection Matrix

Projection onto a Line

When the Columns Are Dependent

Reading the Scene Player

Choosing a Problem

What Least Squares Is

Key Terms

Least-squares solution — the

\hat{\mathbf{x}}

that minimizes

\|A\mathbf{x} - \mathbf{b}\|

when

A\mathbf{x} = \mathbf{b}

has no exact solution.

Normal equations —

A^TA\hat{\mathbf{x}} = A^T\mathbf{b}

; always consistent, uniquely solvable when the columns of

A

are independent.

Projection —

\mathbf{p} = A\hat{\mathbf{x}}

, the point of the column space closest to

\mathbf{b}

.

Residual —

\mathbf{e} = \mathbf{b} - \mathbf{p}

, perpendicular to every column of

A

A^T\mathbf{e} = \mathbf{0}

.

Projection matrix —

P = A(A^TA)^{-1}A^T

, with

P\mathbf{b} = \mathbf{p}

; symmetric and idempotent,

P^2 = P

.

Design matrix — for fitting

b = C + Dt

, the matrix with a column of ones and a column of

t

values, one row per data point.

Overdetermined system — more equations than unknowns; generally inconsistent, and the setting for least squares.

Sum of squared errors —

\|\mathbf{e}\|^2

, the quantity least squares minimizes.

Orthogonal decomposition —

\mathbf{b} = \mathbf{p} + \mathbf{e}

with

\mathbf{p} \in C(A)

and

\mathbf{e} \in N(A^T)

, so

\|\mathbf{b}\|^2 = \|\mathbf{p}\|^2 + \|\mathbf{e}\|^2

Getting Started with the Visualizer

DemoData, size, shuffle

Step 0 of 5

Choose a matrix and a right-hand side, then watch

\mathbf{b}

get projected onto the column space.

• Use the Preset pills for seven problems: a line through three points, a line through four, a parabola through four, projection onto a single line, projection onto a coordinate plane, a consistent system with zero residual, and a matrix with dependent columns
• Use the two Size steppers for two to four equations and one to three unknowns; Shuffle data builds a polynomial design matrix with random data
• Edit any entry of

A

or of

\mathbf{b}

directly;

\mathbf{b}

is the amber column
• Hover the ? icon for a reminder of why the residual must be perpendicular to the columns
• Press play or step manually; the step log on the right keeps every stage

When

A

is a design matrix the captions translate everything into the fit: the fitted line or parabola, the fitted values at the data points, and the errors.

The Scenes in Order

DemoLine through 3 points, scene by scene

Step 0 of 5

The visualizer follows the textbook procedure exactly.

• Consistency —

[A \mid \mathbf{b}]

row reduced; a pivot in the last column means no exact solution
• Normal equations —

A^TA

and

A^T\mathbf{b}

formed as products, with their meaning as dot products
• Dependent columns — if

A^TA

is singular the run stops with an explanation
• Solve —

[A^TA \mid A^T\mathbf{b}]

row reduced to

\hat{\mathbf{x}}

; for a single column this is

\mathbf{a}^T\mathbf{b} / \mathbf{a}^T\mathbf{a}

• Project —

\mathbf{p} = A\hat{\mathbf{x}}

as a combination of the columns, compared with

\mathbf{b}

• Residual —

\mathbf{e} = \mathbf{b} - \mathbf{p}

, its length,

A^T\mathbf{e} = \mathbf{0}

, and the Pythagorean split of

\|\mathbf{b}\|^2

• Projection matrix —

P = A(A^TA)^{-1}A^T

with

P\mathbf{b} = \mathbf{p}

P^2 = P

and trace equal to the rank
• Done — the fitted curve when there is one, and the sum of squared errors

No Exact Solution

The frozen picture below shows the default preset's augmented matrix

[A \mid \mathbf{b}]

reduced, with a pivot in the last column: one row reads

0 = 1

, so no line passes through the three points.

That failure is what least squares is for.

Inconsistent system, frozen

[A | b] for the points (0, 6), (1, 0), (2, 0), reduced: a pivot in the last column. No line passes through all three points, so least squares takes over.

A pivot in the augmented column means

\mathbf{b}

is not a combination of the columns of

A

: it lies outside the column space, which here is a plane in

\mathbb{R}^3

. Three points determine a line only if they happen to be collinear; three generic points do not, and three equations in two unknowns generally have no solution.

The consistency check also tells the tool what to expect. When no pivot lands in the last column the least-squares solution will be exact and the residual zero, which the consistent preset shows.

The Normal Equations

The frozen picture below shows

A^TA = \begin{pmatrix} 3 & 3 \\ 3 & 5 \end{pmatrix}

and

A^T\mathbf{b} = (6, 0)

for the default preset, formed as the two products

A^T \cdot A

and

A^T \cdot \mathbf{b}

.

Each entry is a dot product of columns: the

3

in the corner is the column of ones dotted with itself, the count of data points.

Normal equations, frozen

AᵀA = [3, 3; 3, 5] and Aᵀb = (6, 0), formed as products. Each entry is a dot product of columns: the 3 in the corner counts the data points.

Multiplying the inconsistent system through by

A^T

produces a square system that is always solvable, and that is not a trick: it is the statement that the residual must be perpendicular to every column. For a line fit the two equations say the errors sum to zero and the errors are uncorrelated with

t

A^TA

is symmetric and positive semidefinite, and positive definite exactly when the columns are independent. Its entries, the dot products of the columns, are why highly correlated predictors make regression unstable: nearly parallel columns make

A^TA

nearly singular.

Solving for x-hat

The frozen picture below shows

[A^TA \mid A^T\mathbf{b}]

reduced to

\hat{\mathbf{x}} = (5, -3)

: the best line is

b = 5 - 3t

.

Two equations, two unknowns, and a unique answer, unlike the original three equations.

Solving for x̂, frozen

[AᵀA | Aᵀb] reduced to x̂ = (5, −3): the best line is b = 5 − 3t. Two equations, two unknowns, one answer.

The normal equations are a small square system, and any method solves them: row reduction as here, the

2 \times 2

inverse formula, or Cramer's rule. For larger problems the standard practice is to avoid forming

A^TA

at all and use a QR factorization of

A

, which gives the same

\hat{\mathbf{x}}

with less loss of precision.

The solution has a statistical reading. With a column of ones,

D

is the covariance of

t

and

b

divided by the variance of

t

, and

C

makes the line pass through the mean point. Here the mean point is

(1, 2)

and indeed

5 - 3\cdot 1 = 2

The Residual Is Perpendicular

The frozen picture below shows

\mathbf{b} - \mathbf{p} = \mathbf{e} = (1, -2, 1)

for the default preset, and

A^T\mathbf{e} = \mathbf{0}

.

The residual is the part of

\mathbf{b}

the columns cannot reach, and it is perpendicular to everything they can.

The residual, frozen

b − p = (1, −2, 1), of length √6, and Aᵀe = 0: the error is perpendicular to both columns. |b|² = 36 = 30 + 6.

Perpendicularity is the defining property of the projection, and it is what makes

\mathbf{p}

the closest point: for any other point

A\mathbf{x}

of the column space,

\mathbf{b} - A\mathbf{x} = \mathbf{e} + (\mathbf{p} - A\mathbf{x})

with the two parts perpendicular, so by Pythagoras its length exceeds

\|\mathbf{e}\|

.

The residual lives in the left null space of

A

, the orthogonal complement of the column space. Its length is the minimum of

\|A\mathbf{x} - \mathbf{b}\|

, and its square,

6

here, is the sum of squared errors that the fitted line minimizes.

The Projection Matrix

The frozen picture below shows

P = A(A^TA)^{-1}A^T

for the default preset, a

3 \times 3

matrix of sixths, applied to

\mathbf{b}

to give

\mathbf{p} = (5, 2, -1)

directly.

P

projects every vector of

\mathbb{R}^3

onto the plane spanned by the columns of

A

Projection matrix, frozen

P = A(AᵀA)⁻¹Aᵀ, a matrix of sixths, applied to b gives p = (5, 2, −1) at once. Symmetric, P² = P, trace 2.

P

is symmetric, because projection is its own transpose, and idempotent,

P^2 = P

, because projecting a vector already in the plane leaves it alone. Its eigenvalues are

1

on the column space and

0

on the left null space, so its trace, the sum of the eigenvalues, is the dimension of the column space,

2

I - P

is the other projection, onto the left null space, and

(I - P)\mathbf{b} = \mathbf{e}

. The two together are the orthogonal decomposition of

\mathbb{R}^m

that the four-subspace picture promises.

Projection onto a Line

With a single column

\mathbf{a}

the normal equation is the scalar

\mathbf{a}^T\mathbf{a}\,\hat{x} = \mathbf{a}^T\mathbf{b}

. The frozen picture below shows the one-column preset,

\mathbf{a} = (1, 2, 2)

and

\mathbf{b} = (3, 3, 3)

9\hat{x} = 15

, so

\hat{x} = 5/3

.

The projection is

\mathbf{p} = \frac{5}{3}\mathbf{a}

and the residual

(4/3, -1/3, -1/3)

is perpendicular to

\mathbf{a}

Projection onto a line, frozen

One column a = (1, 2, 2), b = (3, 3, 3): the normal equation is 9x̂ = 15, x̂ = 5/3. The vector-projection formula aᵀb / aᵀa in matrix clothing.

This is the vector-projection formula

\mathbf{p} = \frac{\mathbf{a}\cdot\mathbf{b}}{\mathbf{a}\cdot\mathbf{a}}\mathbf{a}

, and the projection matrix is

P = \mathbf{a}\mathbf{a}^T / \mathbf{a}^T\mathbf{a}

, a rank-one matrix. Everything in the general case is this formula with a matrix in place of the vector:

(A^TA)^{-1}

replaces division by

\mathbf{a}^T\mathbf{a}

.

When the columns of

A

are orthogonal, the general projection is just the sum of the projections onto each column separately; that is why orthonormal bases make least squares trivial, and why Gram–Schmidt is worth doing first.

When the Columns Are Dependent

The dependent preset has columns

(1, 2, 3)

and

(2, 4, 6)

, one twice the other. The frozen picture below shows

A^TA = \begin{pmatrix} 14 & 28 \\ 28 & 56 \end{pmatrix}

reducing to a single pivot: singular, and the run stops.

The projection of

\mathbf{b}

onto the column space, a line, still exists; a unique

\hat{\mathbf{x}}

does not.

Dependent columns, frozen

Columns (1, 2, 3) and (2, 4, 6): AᵀA = [14, 28; 28, 56] has one pivot. The projection exists but x̂ is not unique, and the run stops.

A^TA

is invertible exactly when

A

has independent columns, because

A^TA\mathbf{x} = \mathbf{0}

implies

\|A\mathbf{x}\|^2 = \mathbf{x}^TA^TA\mathbf{x} = 0

, so

A\mathbf{x} = \mathbf{0}

, and the two matrices have the same null space. With dependent columns many

\hat{\mathbf{x}}

give the same

\mathbf{p}

, differing by null-space vectors.

The practical fixes are to drop a redundant column, or to use the pseudoinverse, which chooses the

\hat{\mathbf{x}}

of smallest length. In statistics the situation is called collinearity, and the nearly-dependent case is the more common and more dangerous one.

Reading the Scene Player

Each scene shows the matrices for one step with the arithmetic in the caption.

•

\mathbf{b}

is amber throughout, in the matrices and in the input grid
•

\hat{\mathbf{x}}

is accent,

\mathbf{p}

is the target, and

\mathbf{e}

is secondary
• Products that must come out zero, such as

A^T\mathbf{e}

, are drawn in grey with the target highlight
• In the consistency scene the pivot that lands in the last column is muted, since it is the mark of an inconsistent system
• The projection matrix's diagonal is highlighted; its trace is the rank of

A

• Fractions appear as fractions: the normal equations of integer problems have rational solutions

Choosing a Problem

DemoFive presets

Step 0 of 5

The seven presets each make a different point.

• Line through 3 points —

(0, 6)

(1, 0)

(2, 0)

; the best line is

b = 5 - 3t

with errors

(1, -2, 1)

, the classic textbook example
• Line through 4 points — four data points, one more equation, the same procedure
• Parabola through 4 points — three unknowns

C, D, E

and a design matrix with columns

1, t, t^2

• Projection onto a line — a single column

\mathbf{a}

, where the normal equation is the scalar

\mathbf{a}^T\mathbf{a}\,\hat{x} = \mathbf{a}^T\mathbf{b}

• Projection onto a plane — columns

\mathbf{e}_1, \mathbf{e}_2

; the projection keeps the first two coordinates and the residual is the third
• b in the column space — a consistent system; least squares returns the exact solution and

\mathbf{e} = \mathbf{0}

• Dependent columns —

A^TA

is singular and the run stops

Shuffle keeps the design-matrix structure and randomizes the data, so the fitted-curve reading stays available.

What Least Squares Is

A system

A\mathbf{x} = \mathbf{b}

with more equations than unknowns is usually inconsistent:

\mathbf{b}

is not in the column space of

A

, so no

\mathbf{x}

makes

A\mathbf{x}

equal to

\mathbf{b}

. Least squares replaces the impossible demand with a possible one: choose

\hat{\mathbf{x}}

to make the error

\mathbf{e} = \mathbf{b} - A\hat{\mathbf{x}}

as short as possible.

The shortest error is geometric. The set of all

A\mathbf{x}

is the column space, and the point of a subspace closest to

\mathbf{b}

is the orthogonal projection

\mathbf{p}

\mathbf{b}

onto it. So

A\hat{\mathbf{x}} = \mathbf{p}

, and the error

\mathbf{e} = \mathbf{b} - \mathbf{p}

is perpendicular to the whole column space, in particular to each column:

A^T(\mathbf{b} - A\hat{\mathbf{x}}) = \mathbf{0} \qquad\Longleftrightarrow\qquad A^TA\hat{\mathbf{x}} = A^T\mathbf{b}

These are the normal equations. They are always consistent, because

A^T\mathbf{b}

is always in the column space of

A^TA

, and when the columns of

A

are independent

A^TA

is invertible and the solution is unique:

\hat{\mathbf{x}} = (A^TA)^{-1}A^T\mathbf{b}, \qquad \mathbf{p} = A(A^TA)^{-1}A^T\mathbf{b} = P\mathbf{b}

The matrix

P

projects every vector of

\mathbb{R}^m

onto the column space. It is symmetric, satisfies

P^2 = P

, and

I - P

projects onto the orthogonal complement, the left null space, where the residual lives.

Fitting a line

b = C + Dt

to data points

(t_i, b_i)

is exactly this problem with

A

having a column of ones and a column of the

t_i

: each data point is one equation

C + Dt_i = b_i

, the column space is the set of all lines evaluated at the

t_i

, and the least-squares line minimizes the sum of squared vertical errors. Polynomial fits use more columns; the picture is the same. For the theory, see the least squares page and the projections page.

Key Properties

Facts about least squares and projection.

• Existence: the normal equations always have a solution; uniqueness needs independent columns
• Residual orthogonality:

A^T\mathbf{e} = \mathbf{0}

, so

\mathbf{e}

lies in the left null space of

A

• Pythagoras:

\|\mathbf{b}\|^2 = \|\mathbf{p}\|^2 + \|\mathbf{e}\|^2

• Exact case: if

\mathbf{b} \in C(A)

then

\hat{\mathbf{x}}

solves

A\mathbf{x} = \mathbf{b}

exactly and

\mathbf{e} = \mathbf{0}

• Projection matrix:

P = A(A^TA)^{-1}A^T

is symmetric,

P^2 = P

\operatorname{rank} P = \operatorname{tr} P = n

, and

I - P

is the complementary projection
• Single column:

\hat{x} = \mathbf{a}^T\mathbf{b} / \mathbf{a}^T\mathbf{a}

and

P = \mathbf{a}\mathbf{a}^T / \mathbf{a}^T\mathbf{a}

• Orthonormal columns: if

A^TA = I

then

\hat{\mathbf{x}} = A^T\mathbf{b}

and

P = AA^T

, with no inverse to compute
• Line fits: with a column of ones, the errors sum to zero and the fitted line passes through the mean point

(\bar t, \bar b)

• Conditioning:

A^TA

squares the condition number of

A

; QR or the SVD solve the same problem more stably
• Dependent columns:

\mathbf{p}

is still unique, but

\hat{\mathbf{x}}

is not; the pseudoinverse picks the shortest

Why It Matters

Least squares is the most used computation in applied mathematics.

• Regression: every linear regression is a least-squares projection of the response onto the span of the predictors
• Curve fitting and calibration: polynomial, exponential (after a log) and trigonometric fits are all design-matrix problems
• Measurement and surveying: more measurements than unknowns, reconciled by minimizing squared discrepancies; Gauss invented the method for exactly this
• Signal processing: filters and predictors are chosen by least squares; the projection theorem is the orthogonality principle
• Machine learning: the closed-form solution for linear models, and the inner loop of many iterative methods
• Geometry: the projection onto a subspace is the nearest-point map, the foundation of Gram–Schmidt, QR and the four-subspace picture
• Statistics: with independent errors of equal variance, the least-squares estimate is the best linear unbiased one

Worked Example

Fit a line

b = C + Dt

to the points

(0, 6)

(1, 0)

(2, 0)

.

Set up. Each point gives one equation:

C = 6

C + D = 0

C + 2D = 0

. So

A = \begin{pmatrix} 1 & 0 \\ 1 & 1 \\ 1 & 2 \end{pmatrix}, \qquad \mathbf{b} = \begin{pmatrix} 6 \\ 0 \\ 0 \end{pmatrix}

The three equations are inconsistent: no line passes through all three points.

Normal equations.

A^TA = \begin{pmatrix} 3 & 3 \\ 3 & 5 \end{pmatrix}

and

A^T\mathbf{b} = \begin{pmatrix} 6 \\ 0 \end{pmatrix}

, so

3C + 3D = 6

and

3C + 5D = 0

.

Solve. Subtracting,

2D = -6

, so

D = -3

and

C = 5

. The best line is

b = 5 - 3t

.

Project.

\mathbf{p} = A\hat{\mathbf{x}} = (5, 2, -1)

, the heights of the line at

t = 0, 1, 2

.

Residual.

\mathbf{e} = \mathbf{b} - \mathbf{p} = (1, -2, 1)

, with

\|\mathbf{e}\|^2 = 6

. Check:

(1, 1, 1)\cdot\mathbf{e} = 0

and

(0, 1, 2)\cdot\mathbf{e} = 0

, so

A^T\mathbf{e} = \mathbf{0}

. And

\|\mathbf{b}\|^2 = 36 = 30 + 6 = \|\mathbf{p}\|^2 + \|\mathbf{e}\|^2

.

Projection matrix.

(A^TA)^{-1} = \frac{1}{6}\begin{pmatrix} 5 & -3 \\ -3 & 3 \end{pmatrix}

, so

P = A(A^TA)^{-1}A^T = \frac{1}{6}\begin{pmatrix} 5 & 2 & -1 \\ 2 & 2 & 2 \\ -1 & 2 & 5 \end{pmatrix}

, and

P\mathbf{b} = (5, 2, -1) = \mathbf{p}

. Its trace is

2

, the rank of

A

Common Mistakes

A few mistakes recur.

• Solving $A\mathbf{x} = \mathbf{b}$ by row reduction and reading a "solution" — an inconsistent system has none; the least-squares solution comes from the normal equations, not from

[A \mid \mathbf{b}]

• Writing $AA^T$ instead of $A^TA$ — the normal equations use

A^TA

, which is

n \times n

and matches the number of unknowns
• Forgetting to multiply $\mathbf{b}$ by $A^T$ — the right-hand side of the normal equations is

A^T\mathbf{b}

, not

\mathbf{b}

• Expecting $\hat{\mathbf{x}}$ to satisfy the original equations — it satisfies them only when

\mathbf{b}

is in the column space; otherwise

A\hat{\mathbf{x}} = \mathbf{p} \neq \mathbf{b}

• Measuring errors perpendicular to the line — least squares for

b = C + Dt

minimizes vertical errors in

b

, not distances to the line
• Using dependent columns —

A^TA

is then singular and

\hat{\mathbf{x}}

is not unique, though

\mathbf{p}

still is
• Computing $(A^TA)^{-1}$ when the columns are orthonormal — then

A^TA = I

and the inverse is unnecessary