Does $A^Tb$ lie in the column space of $A^TA$? If it does, why? 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.
 A: 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).$ 
A: 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$.
A: 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.
