Let \(A\) be a real \(n\times n\) matrix. Prove that \(A^TA\) and \(A^T\) have the same range. Equivalently, prove that for every \(y\), \[ y=A^TAx \] has a solution \(x\) if and only if \[ y=A^Tz \] has a solution \(z\).
Solution
1. One has\[ \operatorname{ran}(A^TA) \subseteq \operatorname{ran}(A^T). \]
Every vector in the range of \(A^TA\) has the form \[ A^TAx = A^T(Ax) \] for some \(x\). Hence it lies in the range of \(A^T\).
2. One has\[ \ker(A^TA)=\ker A. \]
If \(Ax=0\), then certainly \(A^TAx=0\), so \[ \ker A\subseteq\ker(A^TA). \] Conversely, if \(A^TAx=0\), then \[ 0 = x^TA^TAx = \norm{Ax}^2. \] Thus \(Ax=0\), proving the reverse inclusion.
3. The ranges of \(A^TA\) and \(A^T\) have the same dimension.
By step 2 and rank–nullity, \[ \operatorname{rank}(A^TA) = n-\dim\ker(A^TA) = n-\dim\ker A = \operatorname{rank}A. \] The rank of a matrix equals the rank of its transpose, so \[ \operatorname{rank}(A^T)=\operatorname{rank}A. \] Hence \[ \dim\operatorname{ran}(A^TA) = \dim\operatorname{ran}(A^T). \]
4. Therefore\[ \boxed{ \operatorname{ran}(A^TA) = \operatorname{ran}(A^T) }. \]
Step 1 gives an inclusion between two finite-dimensional subspaces, and step 3 shows that they have the same dimension. Therefore the inclusion is equality.
5. Equivalently, for every \(y\), the equation\[ y=A^TAx \]has a solution if and only if\[ y=A^Tz \]has a solution.
The first equation is solvable exactly when \(y\in\operatorname{ran}(A^TA)\), and the second is solvable exactly when \(y\in\operatorname{ran}(A^T)\). Step 4 identifies these two ranges.
6. Q.E.D.
Steps 4 and 5 give the two equivalent formulations requested.