Which subspace (column space, row space, null space, left null space) of A is x a part of

linear algebramatricesvector-spaces

Which of the four subspaces contains $x$, for the given equation:

$$A^T Ax=A^Tb$$
where $b$ is a column vector NOT in the column space of $A_{m\times n}$. (This equation is to find the best solution for $Ax=b$). Also, $A$ is assumed to have independent columns.

(Question is from one of the MIT OCW problem sets.)

My attempt: Null space of $A$ is just the zero vector. So $\mathbb R^n$ is entirely the row space. Since $x$ has to be a $n\times 1$ vector, it belongs in the row space.

Is there any other more intuitive way to visualize this? Can I generalize this to any $Ax=b$ also, if rank $=n$ for $A$?

Best Answer

Well, to me your attempt is as intuitive as it gets. Just a remark: you assumed that $m\neq n$ to conclude that $x$ can't be in the column space or left null space, which a priori is not given (at least, it wasn't stated in the question). But this is ok, since, if $m=n$ and $A$ has independent columns, $A$ would be an invertible square matrix, and $A^TAx=A^Tb\implies Ax=b$, but, since $b$ is assumed not to be in the column space of $A$, this case doesn't happen.

Maybe what you're asking for is a more explicit explanation? If so, Let $A=\begin{bmatrix}L_1 \\ \vdots\\ L_m\end{bmatrix}$, where $L_i$ is the $i$-th line, a $1\times n$ vector. If $b=\begin{bmatrix} b_1 \\ \vdots\\ b_m\end{bmatrix}$, we have that

\begin{align*} A^TAx=A^Tb&\implies \begin{bmatrix} L_1 & \cdots & L_m\end{bmatrix}\begin{bmatrix}L_1 \\ \vdots\\ L_m\end{bmatrix}\textbf{x}=\begin{bmatrix} L_1 & \cdots & L_m\end{bmatrix}\begin{bmatrix} b_1 \\ \vdots\\ b_m\end{bmatrix}\\ &\implies(L_1\cdot L_1+\dots+L_n\cdot L_n)\textbf{x}=b_1L_1+\dots+b_mL_m\\ &\implies\textbf{x}=\dfrac{1}{L_1\cdot L_1+\dots+L_n\cdot L_n}(b_1L_1+\dots+b_mL_m) \end{align*}

So $\textbf{x}$ is indeed in the row space of $A$ (notice that the denominator of the fraction is clearly non-zero).