When does $A^TAX = A^TB$?

Question

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

Answer 1

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$.

Answer 2

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$.