Proof of Normal Equations

We will assume that A^TA is invertible. This is a reasonable assumption because there are more equations than unknowns. The length of the vector x is defined to be so the length of the vector squared is The square of the length of the vector Ax-b is the sum of the squares of the errors since each element of Ax - b is the error at a point. We want to minimize this quantity. We claim that the solution to the normal equations, which we will denote as x^* = (A^TA)^-1A^Tb, minimizes the sum of the squares of the errors.

We claim, and will prove, that

||Ax - b||² = ||Ax^* - b||² + ||A (x - x^*)||².

Since we are minimizing over x, ||Ax - b||² will be minimized when x = x^* so that ||A (x - x^*)||² is zero. This is true because ||A (x - x^*)||² can never be negative.

To prove the claim, we will work with the right side of the equation and prove that it is equal to the left side. These equations are numbered. There are short explanations of these steps following the proof.

=	\|\|Ax^* - b\|\|² + \|\|A (x - x^*)\|\|²	(1)
=	(Ax^* - b)^T (Ax^* - b) + (A(x - x^))^T A(x - x^)	(2)
=	(A (A^TA)^{^-1}A^Tb - b)^T (A (A^TA)^{^-1}A^Tb - b)^T +
	(A(x - (A^TA)^-1A^Tb))^{^T} A(x - (A^TA)^-1A^Tb)	(3)
=	(A (A^TA)^-1 A^Tb - b)^{^T} (A (A^TA)^-1 A^Tb - b) +
	(Ax - A (A^TA)^-1 A^Tb)^{^T} (Ax - A (A^TA)^-1 A^Tb)	(4)
=	(b^TA (A^TA)^-1 A^T - b^T) (A (A^TA)^-1 A^Tb - b) +
	(x^TA^T - b^TA (A^TA)^-1 A^T)(Ax - A (A^TA)^-1 A^Tb)	(5)
=	(b^TA (A^TA)^-1 A^TA (A^TA)^-1A^Tb - 2b^TA (A^TA)^-1A^Tb + b^Tb +
	(x^TA^TAx - 2b^TA (A^TA)^-1 A^TAx + b^TA (A^TA)^-1 A^TA (A^TA)^-1A^Tb)	(6)
=	(b^TA (A^TA)^-1 A^Tb - 2b^TA (A^TA)^-1 A^Tb + b^Tb) +
	(x^TA^TAx - 2b^TAx + b^TA (A^TA)^-1 A^Tb)	(7)
=	b^Tb + x^TA^TAx - 2b^TAx	(8)

Now, if we look at the left side of the equation, we can see that it equals the right side because

||Ax - b||² = (Ax - b)^T (Ax - b) = (x^TA^T - b^T) (Ax - b) = x^TA^TAx - 2b^TAx + b^Tb.

This proves that x = x^* = (A^TA)^{^-1}A^Tb uniquely minimizes the sum of the squares of the error for the equation Ax - b.

The following are comments on the steps of the proof:

This is the right hand side of the equation from the claim.
||y||² = y^Ty
Replace x^* with (A^TA)^{^-1}A^Tb.
Distribute A in the second term.
(M + N)^T = M^T + N^T, (RS)^T = S^TR ^T, and (A^-1)^{^T} = (A^T)^{^-1}
Because each term is a vector and x^Ty = y^Tx, which can also be written as , we can multiply in a manner similar to polynomial multiplication. However, we must remember that matrix multiplication is not commutative, so the order of multiplication of the matrices matters.
(A^TA)^{^-1}(A^TA) = I
Combine like terms.

<<<