When does $A^TAX = A^TB$? The original question is a true-or-false question: Assume $A$ is a $m\times n$ matrix and $B$ is a $m\times p$ matrix. If $X$ is an $n\times p$ unkwown matrix, then the system $A^TAX = A^TB$ always has a solution.
To my knowledge, for $A^TAX$ to always have a solution, $A^TA$ must be invertible. For it to be invertible, $A$ must have full column rank. However, it is not specified in the question, so I would assume it is false. However, the answer is true. Am I not getting something here? Thanks for any help!
Edit: This is the suggested answer given in the question:
Let $X$ = [$X_1$ $X_2$... $X_p$], $B$ = [$b_1$ $b_2$... $b_p$]
$A^TAX = A^TB$ $\Leftarrow$$\Rightarrow$ [$A^TX_1$ $A^TX_2$... $A^TX_p$] = [$A^Tb_1$ $A^Tb_2$... $A^Tb_p$]
Because normal equation $A^TAX_i = A^Tb_i$ must have a solution for all i = 1, 2, ..., p
So $A^TAX = A^TB$ must have a solution
 A: We consider the case $p=1$ as below. 
Let $A$ be an $m\times n$ matrix and let $b\in\mathbb{R}^m$, and define 
$W=\{Ax:x\in\mathbb{R}^n\}$. 
Then it is well-known that there exists an unique vector in $W$, say $Ax_0$ where $x_0\in\mathbb{R}^n$, such that $b-Ax_0\in W^\perp$. Thus
$$0=\left\langle Ax,Ax_0-b\right\rangle
=\left\langle x,A^T(Ax_0-b)\right\rangle
=\left\langle x,A^TAx_0-A^Tb\right\rangle, \tag{1}$$
for all $x\in\mathbb{R}^n$. If taking $x=A^TAx_0-A^Tb$ into equation $(1)$,
we can get 
$$A^TAx_0-A^Tb={\it 0}\quad\mbox{or}\quad A^TAx_0=A^Tb.$$
Therefore the system $A^TAx=A^Tb$ always has a solution, and this can be easily extended to the case $p>1$.
A: Let $p=1$. What you want to find is $x$ such that $A^TAx=A^Tb$, that is,
$$
A^T(Ax-b)=0
$$
Now it is known that $\mathbb{R}^m=C(A)\oplus N(A^T)$ (explicitly, that $N(A^T)$, the null space of $A^T$ is a complement of the column space $C(A)$ of $A$). Then $b=Au+v$, for some $u\in\mathbb{R}^n$ and $A^Tv=0$. Choosing $x=u$ gives the required solution.
For the general case, write $B=[b_1\ b_2\ \dots\ b_p]$ and $X=[x_1\ x_2\ \dots\ x_p]$ and solve separately the $p$ systems $A^TAx_i=A^Tb_i$.

Proof of the claim. If $y\in C(A)\cap N(A^T)$, then $y=Az$ for some $z$ and $0=A^Ty=A^TAz$, so $0=z^TA^TAz=(Az)^T(Az)=y^Ty$, so $y=0$. Thus the two spaces are independent. Further,
$$
\dim N(A^T)=m-\operatorname{rank}A^T=m-\operatorname{rank} A
$$
so
$$
\dim C(A)\oplus N(A^T)=
\operatorname{rank}A+(m-\operatorname{rank}A)=m
$$
and so $C(A)\oplus N(A^T)=\mathbb{R}^m$.
