Proof of Least Squares Characterization for Linear Regression (Normal Equations)

Throughout, $m$, $p$, $X$, $y$, $\mathrm{RSS}$, $0_p$, and $0_m$ are as in the theorem statement. For $v=(v_1,\dots,v_p)$ in Euclidean space $\mathbb{R}^p$ and $w=(w_1,\dots,w_m)\in\mathbb{R}^m$, the vectors $Xv\in\mathbb{R}^m$ and $X^{\top}w\in\mathbb{R}^p$ are matrix-vector products, where $X^{\top}$ is the transpose of $X$; $u\cdot z$ denotes the dot product and $u-z$ the difference of points $u,z$ of the same Euclidean space; and $d_E$ is the Euclidean distance. All coordinatewise manipulations below use only the arithmetic of real numbers (commutativity, associativity, and distributivity of addition and multiplication, and the ordering of squares), applied to finite sums.

Step 0: Preliminary identities.

(a) Squared distance as a sum of squares. Let $k$ be a natural number and $u,z\in\mathbb{R}^k$. By the definition of the Euclidean distance, $d_E(u,z)$ is the nonnegative square root of the nonnegative real number $\sum_{i=1}^k (u_i-z_i)^2$, so by the defining property of the nonnegative square root,

$$d_E(u,z)^2=\sum_{i=1}^k (u_i-z_i)^2=(u-z)\cdot(u-z).$$

In particular three facts follow. First, $d_E(u,z)^2\ge 0$, as a finite sum of squares. Second, $d_E(u,z)^2=d_E(z,u)^2$, since $(u_i-z_i)^2=(z_i-u_i)^2$ for each $i$. Third, if $d_E(u,z)^2=0$ then $u=z$: each term $(u_i-z_i)^2$ is nonnegative, so if the sum is $0$ every term is $0$, hence $u_i=z_i$ for every $i$.

(b) Adjoint identity. For every $v\in\mathbb{R}^p$ and $w\in\mathbb{R}^m$,

$$(Xv)\cdot w=v\cdot(X^{\top}w).$$

Indeed, by the definitions of the matrix-vector product and of the transpose, $(X^{\top}w)_i=\sum_{\alpha=1}^m (X^{\top})_{i\alpha}w_\alpha=\sum_{\alpha=1}^m X_{\alpha i}w_\alpha$ for each $i\in\{1,\dots,p\}$, and exchanging the order of the two finite sums (allowed by commutativity and associativity of real addition, together with distributivity) gives

$$(Xv)\cdot w=\sum_{\alpha=1}^m\Bigl(\sum_{i=1}^p X_{\alpha i}v_i\Bigr)w_\alpha=\sum_{i=1}^p v_i\Bigl(\sum_{\alpha=1}^m X_{\alpha i}w_\alpha\Bigr)=\sum_{i=1}^p v_i\,(X^{\top}w)_i=v\cdot(X^{\top}w).$$

(c) Linearity in the vector argument. For all $\beta,\gamma\in\mathbb{R}^p$ and each $\alpha\in\{1,\dots,m\}$,

$$\bigl(X\beta-X\gamma\bigr)_\alpha=\sum_{i=1}^p X_{\alpha i}\beta_i-\sum_{i=1}^p X_{\alpha i}\gamma_i=\sum_{i=1}^p X_{\alpha i}(\beta_i-\gamma_i)=\bigl(X(\beta-\gamma)\bigr)_\alpha,$$

so $X\beta-X\gamma=X(\beta-\gamma)$.

(d) Symmetry of the dot product. For $u,z\in\mathbb{R}^k$ we have $u\cdot z=\sum_{i=1}^k u_iz_i=\sum_{i=1}^k z_iu_i=z\cdot u$, by commutativity of real multiplication.

Step 1: The normal equations imply minimality (sufficiency in part 1).

Assume $X^{\top}(y-X\hat\beta)=0_p$ and write $r=y-X\hat\beta\in\mathbb{R}^m$. Let $\beta\in\mathbb{R}^p$ be arbitrary. Consider the three points $A=X\hat\beta$, $B=y$, $C=X\beta$ of $\mathbb{R}^m$. Then $B-A=r$ and, using Step 0(c), (b), and (d),

$$(B-A)\cdot(C-A)=r\cdot\bigl(X\beta-X\hat\beta\bigr)=\bigl(X(\beta-\hat\beta)\bigr)\cdot r=(\beta-\hat\beta)\cdot\bigl(X^{\top}r\bigr)=(\beta-\hat\beta)\cdot 0_p=0,$$

since a dot product with $0_p$ is a sum of zero terms. Thus $B-A$ and $C-A$ are orthogonal, and the Pythagorean theorem in Euclidean space yields

$$d_E(B,C)^2=d_E(A,B)^2+d_E(A,C)^2,\qquad\text{that is,}\qquad d_E(y,X\beta)^2=d_E(X\hat\beta,y)^2+d_E(X\hat\beta,X\beta)^2 .$$

By the symmetry in Step 0(a), $d_E(y,X\beta)^2=\mathrm{RSS}(\beta)$ and $d_E(X\hat\beta,y)^2=d_E(y,X\hat\beta)^2=\mathrm{RSS}(\hat\beta)$, so

$$\mathrm{RSS}(\beta)=\mathrm{RSS}(\hat\beta)+d_E(X\hat\beta,X\beta)^2\ \ge\ \mathrm{RSS}(\hat\beta), \tag{1}$$

because $d_E(X\hat\beta,X\beta)^2\ge0$ by Step 0(a). Since $\beta$ was arbitrary, $\hat\beta$ is a least squares estimator.

Step 2: Minimality implies the normal equations (necessity in part 1).

Assume $\hat\beta$ is a least squares estimator. Write $r=y-X\hat\beta$ and $v=X^{\top}r\in\mathbb{R}^p$, and set

$$S=v\cdot v=\sum_{i=1}^p v_i^2\ \ge 0,\qquad T=(Xv)\cdot(Xv)=\sum_{\alpha=1}^m (Xv)_\alpha^2\ \ge 0 .$$

For each real number $t$, let $\beta(t)\in\mathbb{R}^p$ be the point with coordinates $\beta(t)_i=\hat\beta_i+t\,v_i$ for $i\in\{1,\dots,p\}$. By the matrix-vector product formula and distributivity,

$$\bigl(X\beta(t)\bigr)_\alpha=\sum_{i=1}^p X_{\alpha i}\bigl(\hat\beta_i+t\,v_i\bigr)=(X\hat\beta)_\alpha+t\,(Xv)_\alpha\qquad(\alpha\in\{1,\dots,m\}),$$

so the coordinates of $y-X\beta(t)$ are $r_\alpha-t\,(Xv)_\alpha$. By Step 0(a), expanding each square,

$$\mathrm{RSS}(\beta(t))=\sum_{\alpha=1}^m\bigl(r_\alpha-t\,(Xv)_\alpha\bigr)^2=\sum_{\alpha=1}^m r_\alpha^2-2t\sum_{\alpha=1}^m r_\alpha\,(Xv)_\alpha+t^2\sum_{\alpha=1}^m (Xv)_\alpha^2=\mathrm{RSS}(\hat\beta)-2t\,\bigl((Xv)\cdot r\bigr)+t^2\,T .$$

By Step 0(b) and (d), $(Xv)\cdot r=v\cdot\bigl(X^{\top}r\bigr)=v\cdot v=S$. Since $\hat\beta$ is a least squares estimator, $\mathrm{RSS}(\beta(t))\ge\mathrm{RSS}(\hat\beta)$ for every $t$, which gives

$$-2tS+t^2T\ \ge\ 0\qquad\text{for every real }t . \tag{2}$$

Suppose, for contradiction, that $S>0$. If $T=0$, taking $t=1$ in (2) gives $-2S\ge0$, contradicting $S>0$. If $T>0$, taking $t=S/T$ in (2) gives $-2S^2/T+S^2/T=-S^2/T\ge0$, contradicting $S^2/T>0$. Hence $S=0$. Since $S$ is a finite sum of the nonnegative terms $v_i^2$, every $v_i$ equals $0$, that is,

$$X^{\top}(y-X\hat\beta)=v=0_p .$$

Together with Step 1, this proves part 1.

Step 3: Uniqueness of fitted values (part 2).

Let $\hat\beta$ and $\hat\gamma$ both be least squares estimators. Applying the definition of least squares estimator twice, $\mathrm{RSS}(\hat\beta)\le\mathrm{RSS}(\hat\gamma)$ and $\mathrm{RSS}(\hat\gamma)\le\mathrm{RSS}(\hat\beta)$, so $\mathrm{RSS}(\hat\beta)=\mathrm{RSS}(\hat\gamma)$. By part 1 (Step 2), $\hat\gamma$ satisfies the normal equations, so identity (1) of Step 1 holds with $\hat\gamma$ in the role of $\hat\beta$ and $\beta=\hat\beta$:

$$\mathrm{RSS}(\hat\beta)=\mathrm{RSS}(\hat\gamma)+d_E(X\hat\gamma,X\hat\beta)^2 .$$

Subtracting $\mathrm{RSS}(\hat\gamma)=\mathrm{RSS}(\hat\beta)$ gives $d_E(X\hat\gamma,X\hat\beta)^2=0$, and by the third fact in Step 0(a), $X\hat\beta=X\hat\gamma$.

Step 4: Uniqueness of the estimator (part 3).

Assume that the only $v\in\mathbb{R}^p$ with $Xv=0_m$ is $v=0_p$, and let $\hat\beta$ and $\hat\gamma$ both be least squares estimators. By part 2 (Step 3), $X\hat\beta=X\hat\gamma$, so every coordinate of $X\hat\beta-X\hat\gamma$ is $0$, that is, $X\hat\beta-X\hat\gamma=0_m$. By Step 0(c), $X(\hat\beta-\hat\gamma)=0_m$, so the hypothesis forces $\hat\beta-\hat\gamma=0_p$. Hence $\hat\beta_i-\hat\gamma_i=0$, i.e. $\hat\beta_i=\hat\gamma_i$, for every $i\in\{1,\dots,p\}$, so $\hat\beta=\hat\gamma$. $\blacksquare$