Normal Equation System

Conditions for a Least Squares Minimum

The normal equation converts the first-order optimality condition for a linear least-squares problem into a linear system.

The least squares problem seeks the $x$ that keeps $A \cdot x$ as close to $b$ as possible:

A minimizer satisfies the following linear system:

This is called the normal equation because the residual at a minimizer is normal, or perpendicular, to the column space of $A$.

Least Squares and the Normal Equation

A vector $\hat{x} \in \mathbb{R}^n$ minimizes $\|A \cdot x - b\|_2^2$ if and only if it satisfies $A^T A \cdot \hat{x} = A^T b$. The optimization problem and the normal equation therefore have the same solution set. That equivalence is what turns a minimization problem into a linear system you can solve with elimination or a factorization.

The Residual Is Orthogonal to the Column Space

When $\hat{x}$ minimizes $\|A\hat{x} - b\|_2^2$, the residual vector $A\hat{x} - b$ is orthogonal to every vector in the column space of $A$.

This column space consists of all vectors that can be written as $Ax$ for $x \in \mathbb{R}^n$. The orthogonality condition means

This orthogonality condition holds for every vector $x \in \mathbb{R}^n$. The properties of the inner product give

Because this equality holds for every vector $x$, the vector in parentheses must be zero:

Rearranging this equation gives $A^TA\hat{x}=A^Tb$, the normal equation.

Proof Using Pythagorean Theorem

We can also verify this result in a different way. Let $\hat{x}$ be the solution of the normal equation system and $x$ be any vector in $\mathbb{R}^n$.

Using the Pythagorean theorem, we can write

Because $\hat{x}$ satisfies the normal equation, the cross term is zero. This leaves:

The added squared norm is nonnegative. Therefore, the squared norm of the residual at any $x$ cannot be smaller than at $\hat{x}$:

This inequality proves that $\hat{x}$ indeed gives the minimum value.

Existence and Uniqueness

The normal equation is consistent for every matrix $A \in \mathbb{R}^{m\times n}$ and every vector $b \in \mathbb{R}^m$ because a least-squares minimizer always exists in finite dimensions. The minimizer is unique exactly when $A$ has full column rank:

In that case, $A^{\mathsf T}A$ is invertible and

If $A$ is rank deficient, the normal equation still has solutions, but they are not unique. For any particular solution $\hat{x}$, the complete set is

All these parameter vectors produce the same fitted vector $A\hat{x}$.

Null Space and definiteness proof

For every $z\in\mathbb{R}^n$,

This equation shows that $A^{\mathsf T}A$ is always symmetric positive semidefinite. Moreover,

The calculation gives:

This equality of null spaces shows that $A^{\mathsf T}A$ is positive definite exactly when $A$ has full column rank.

Numerical warning

Positive definiteness gives uniqueness and permits a Cholesky solve, but it does not guarantee good conditioning. For a full-column-rank matrix,

Explicitly forming $A^{\mathsf T}A$ can therefore magnify sensitivity and rounding effects. The inverse formula proves an algebraic identity. In software, use $\mathrm{QR}$ for a well-determined full-rank least-squares solve and $\mathrm{SVD}$ when rank deficiency or severe ill-conditioning matters.

An Example with Two Observations

Let $A=(1,2)^T$ and $b=(2,1)^T$. One scalar parameter cannot match both observations: the first equation asks for $x=2$, while the second asks for $x=1/2$. The least-squares solution balances their squared residuals.

The residual is perpendicular to the line of possible predictions. Moving along that line adds a nonnegative squared distance, as the Pythagorean proof requires.