Does $A^Tb$ lie in the column space of $A^TA$? If it does, why?

Question

This problem comes from the normal equations of linear least-squares: $$(A^TA)x=A^Tb$$ My question is whether or not $A^Tb$ lies in the column space of $A^TA$ regardless of $A^TA$'s rank will be.

Answer 1

Yes, if $A$ is a real $m \times n$ matrix and $b \in \mathbb R^m$, then $A^T b$ is in the column space of $A^T A$. Here is a proof:

Let $\hat b$ be the projection of $b$ onto $R(A)$. Notice that $b - \hat b$ is orthogonal to every vector in $R(A)$, and in particular $b - \hat b$ is orthogonal to each column of $A$. This tells us that $$ \tag{$\spadesuit$}A^T (b - \hat b) = 0. $$ Because $\hat b \in R(A)$, there exists $x$ such that $Ax = \hat b$. Plugging in for $\hat b$ in equation $(\spadesuit)$, we see that $A^T Ax = A^T b$. This shows that $A^T b$ is in the range of $A$.

Answer 2

Yes. To see this, recall that (1) $\mathrm{rank}(A^TA)=\mathrm{rank}(A^T)$, and (2) $\mathrm{col}(A^TA)\subset \mathrm{col}(A^T)$. This implies $\mathrm{col}(A^TA)= \mathrm{col}(A^T)$, so $A^Tb\in \mathrm{col}(A^TA)$, even if $b\notin \mathrm{col}(A).$

Answer 3

Usually when we do least squares, A has full column rank and nowhere near full row rank. In this case $A^T A$ is actually invertible, so the situation is simple.

In general, notice what A^T A does to each row of A, as a column vector. This will reveal to you that its column space is the whole column space of A^T (as large as the column space of $A^T B$ could ever be). Then your result follows because $A^T b$ is in this column space.