# Question about a normal equation proof

How can you prove that the normal equations: $(X^TX)\beta = X^TY$ have one or more solutions without the assumption that X is invertible?

My only guess is that it has something to do with generalized inverse, but I am totally lost.

• You gain points by asking questions that provoke amazing answers. – Nikana Reklawyks Nov 2 '17 at 19:15

One is tempted to be glib and point out that because the quadratic form

$$\beta \to (Y - X\beta)'(Y - X\beta)$$

is positive semi-definite, there exists a $\beta$ for which it is minimum and that minimum is found (by setting the gradient with respect to $\beta$ to zero) with the normal equations

$$X'X(Y - X\beta) = 0,$$

whence there must be at least one solution regardless of the rank of $X'X$. However, this argument does not seem to be in the spirit of the question, which appears to be a purely algebraic statement. Perhaps it's of interest to understand why such an equation must have a solution and under precisely what conditions. So let's start over and pretend we don't know the connection with least squares.

It all comes down to the meaning of $X'$, the transpose of $X$. This will turn out to be a matter of a simple definition, appropriate notation, and the concept of a nondegenerate sesquilinear form. Recall that $X$ is the "design matrix" of $n$ rows (one for each observation) and $p$ columns (one for each variable, including a constant if any). It therefore represents a linear transformation from the vector space $\mathbb V = \mathbb{R}^p$ to $\mathbb W = \mathbb{R}^n$.

The transpose of $X$, thought of as a linear transformation, is a linear transformation of the dual spaces $X': \mathbb{W}^* \to \mathbb{V}^*$. In order to make sense of a composition like $X'X$, then, it is necessary to identify $\mathbb{W}^*$ with $\mathbb{W}$. That's what the usual inner product (sum of squares) on $\mathbb{W}$ does.

There are actually two inner products $g_V$ and $g_W$ defined on $\mathbb V$ and $\mathbb W$ respectively. These are real-valued bilinear symmetric functions that are non-degenerate. The latter means that

$$g_W(u, v) = 0\ \forall u\in \mathbb W \implies v = 0,$$

with analogous statements for $g_V$. Geometrically, these inner products enable us to measure length and angle. The condition $g(u,v)=0$ can be thought of as $u$ being "perpendicular" to $v$. Nondegeneracy means that only the zero vector is perpendicular to the entire vector space. (This generality means that the results obtained here will apply to the generalized least squares setting, for which $g_W$ is not necessarily the usual inner product given as the sum of products of components, but is some arbitrary nondegenerate form. We could dispense with $g_V$ altogether, defining $X':\mathbb W\to\mathbb V^*$, but I expect many readers to be unfamiliar or uncomfortable with dual spaces and so choose to avoid this formulation.)

With these inner products in hand, the transpose of any linear transformation $X: \mathbb V \to \mathbb W$ is defined by $X': \mathbb W \to \mathbb V$ via

$$g_V(X'(w), v) = g_W(w, X(v))$$

for all $w\in \mathbb W$ and $v\in \mathbb V$. That there actually exists a vector $X'(w) \in \mathbb V$ with this property can be established by writing things out with bases for $\mathbb V$ and $\mathbb W$; that this vector is unique follows from the non-degeneracy of the inner products. For if $v_1$ and $v_2$ are two vectors for which $g_V(v_1,v)=g_V(v_2,v)$ for all $v\in\mathbb V$, then (from the linearity in the first component) $g_V(v_1-v_2,v)=0$ for all $v$ implying $v_1-v_2=0$.

When $\mathbb U \subset \mathbb W,$ write $\mathbb{U}^\perp$ for the set of all vectors perpendicular to every vector in $\mathbb U$. Also as a matter of notation, write $X(\mathbb V)$ for the image of $X$, defined to be the set $\{X(v) | v \in \mathbb V\} \subset \mathbb W$. A fundamental relationship between $X$ and its transpose $X'$ is

$$X'(w) = 0 \iff w \in X(\mathbb V)^\perp.$$

That is, $w$ is in the kernel of $X'$ if and only if $w$ is perpendicular to the image of $X$. This assertion says two things:

1. If $X'(w) = 0$, then $g_W(w, X(v)) = g_V(X'(w),v) = g_V(0,v)=0$ for all $v\in\mathbb V$, which merely means $w$ is perpendicular to $X(V)$.

2. If $w$ is perpendicular to $X(\mathbb V)$, that only means $g_W(w, X(v)) = 0$ for all $v\in\mathbb V$, but this is equivalent to $g_V(X'(w), v) = 0$ and nondegeneracy of $g_V$ implies $X'(w)=0$.

We're actually done now. The analysis has shown that $\mathbb W$ decomposes as a direct product $\mathbb W = X(\mathbb V) \oplus X(\mathbb V)^\perp$. That is, we can take any arbitrary $y \in \mathbb W$ and write it uniquely as $y = y_0 + y^\perp$ with $y_0\in X(\mathbb V)$ and $y^\perp \in X(\mathbb V)^\perp$. That means $y_0$ is of the form $X(\beta)$ for at least one $\beta\in\mathbb V$. Notice, then, that

$$y - X\beta = (y_0 + y^\perp) - y_0 = y^\perp \in X(\mathbb V)^\perp$$

The fundamental relationship says that is the same as the left hand side being in the kernel of $X'$:

$$X'(y - X\beta) = 0,$$

whence $\beta$ solves the normal equations $X'X\beta = X'y.$

We are now in a position to give a brief geometric answer to the question (along with some revealing comments): the normal equations have a solution because any $n$-vector $y\in\mathbb W$ decomposes (uniquely) as the sum of a vector $y_0$ in the range of $X$ and another vector $y^\perp$ perpendicular to $y_0$ and $y_0$ is the image of at least one $p$-vector $\beta\in\mathbb V$. The dimension of the image $X(\mathbb V)$ (its rank) is the dimension of the identifiable parameters. The dimension of the kernel of $X$ counts the nontrivial linear relations among the parameters. All parameters are identifiable when $X$ is a one-to-one map from $\mathbb V$ to its image in $\mathbb W$.

It is ultimately useful to dispense with the space $\mathbb V$ altogether and work entirely with the subspace $\mathbb U = X(\mathbb V)\subset\mathbb W$, the "column space" of the matrix $X$. The normal equations amount to orthogonal projection onto $\mathbb U$. That frees us conceptually from being tied to any particular parameterization of the model and shows that least-squares models have an intrinsic dimension independent of how they happen to be parameterized.

One interesting outcome of this abstract algebraic demonstration is that we can solve the normal equations in arbitrary vector spaces. The result holds, say, for complex spaces, for spaces over finite fields (where minimizing a sum of squares makes little sense), and even over infinite-dimensional spaces that support suitable sequilinear forms.

• I never had the rep to accept this answer until much later. I just stumbled back on this and wanted to thank you again! – ryati Jan 23 '18 at 21:41
• I would write that quadratic form as $$\beta \mapsto (Y - X\beta)'(Y - X\beta)$$ rather than as $$\beta \to (Y - X\beta)'(Y - X\beta),$$ and use the other arrow for things like $f:A\to B. \qquad$ – Michael Hardy Nov 2 '18 at 23:11
• @Michael There must be a typographical error in you comment. Would you mind clarifying what you meant? – whuber Nov 3 '18 at 0:15
• @whuber : I find no typographical error. The point is that the two arrows $\text{“}\mapsto\text{''}$ and $\text{“}\to\text{''}$ have different meanings. $\qquad$ – Michael Hardy Nov 4 '18 at 16:38
• @Michael Forgive me for not seeing that distinction, despite many readings. Regardless, to me the first arrow refers to an injective function whereas the second refers to any function, but I suspect that's not what you intend. Would you mind explaining your notation? – whuber Nov 4 '18 at 17:18

It is easy to show (try for yourself, for an arbitrary number of points, $n$) that the inverse of $X^T X$ exists if there are at least two distinct $x$-values (predictors) in the sample set. Only if all your data have the same values $x_i=x$ (i.e., points stacked in the $y$-direction, along a vertical line), then any line drawn through their mean $\overline{y}$ will have an arbitrary slope (regression coefficient), so that the LSE regression line is then not unique.

• For completeness, $X=[1 ~x_1; 1 ~x_2; \ldots; 1 ~x_n]$ for simple linear regression, while $X=[1 ~x_{11} \ldots x_{m1}; \ldots; 1 ~x_{1n} \ldots x_{mn}]$ for multiple linear regression. – Lucozade Jul 2 '13 at 15:35
• The reference to multiple regression in the comment is puzzling, because this answer clearly applies only to the case of ordinary regression where one is fitting a "line" rather than a higher-dimensional surface. Moreover, you appear to have answered a different question: this one asks only about the case where $X'X$ is not invertible. – whuber Jul 2 '13 at 15:46

In typical regression, X is skinny and therefore certainly not invertible (though it may be left invertible.) It's straightforward to prove (ask if you need help) that if X is skinny and left invertible then X^T * X is invertible. In this case, then there will be exactly one solution. And if X doesn't have full column rank, then X^T * X will not be full rank, and therefore you will have an underdetermined system.

• These remarks do not seem to address the question: regardless of the rank of $X'X$, there will still exist a solution. As an example, consider the extreme case where $X$ is a matrix of all zeros. Then the normal equations reduce to $0\beta=0$ and any $\beta$ is a solution. – whuber Aug 1 '13 at 20:00
• whuber: of course they address the question: one soln if X is full column rank (as I mentioned), and infinite solutions if it is an underdetermined system – user542833 Aug 2 '13 at 0:10
• The fact that the system is "underdetermined" does not imply it has any solutions at all. The question is about existence of solutions. – whuber Aug 2 '13 at 2:11