Show that $R\!\left(X^T\right)\subseteq R\!\left(X^TX\right).$

Question

I need to show that if $c\in R\!\left(X^T\right),$ then $c\in R\!\left(X^T X\right).$ Here, assume that $X$ is a finite matrix, not necessarily square, and that $c$ is a vector of the appropriate shape to make the matrix multiplications valid. Also, for notation: $R\!\left(X^T\right)$ is the range space of $X^T,$ which in turn is the transpose matrix of $X.$ Assume everything in sight is real, not complex.

I know that $c\in R\!\left(X^T\right)$ if and only if there exists $z$ s.t. $X^Tz=c.$ Also, $c\in R\!\left(X^T X\right)$ if and only if there exists a vector $\lambda$ such that $c=X^TX\lambda.$ So it appears, somehow, that I must show $z=X\lambda.$ It doesn't seem obvious to me that $z$ should be in the range of $X,$ which is essentially what that's saying.

Important note: I just realized that if $X$ is not square, then we have the possible objection that the dimensions don't work out. That is, the number of components in a vector in $R\!\left(X^T\right)$ is not necessarily the same as the number of components in a vector in $R\!\left(X^TX\right).$ (Notice I'm not using the term "dimension" here - that's deliberate.) That's certainly true, but let's assume that this is not an objection - which, for all I know, might be tantamount to saying that $X$ is square. Or maybe we can simply consider that $X\lambda$ can be considered equal to $z$ if we can lop off enough components from one or the other such that what remains is equal.

How do I continue?

Answer 1

This question has come up in various forms many times on this site. In general, we know that $R(AB) \subset R(A)$ for any matrices $A$ and $B$. However, in your case, you get the reverse inclusion by dimension considerations.

The claim is that $R(X^\top) = R(X^\top X)$ because you have the inclusion $R(X^\top X)\subset R(X^\top)$ and the two subspaces have the same dimension. To see this, we apply the nullity-rank theorem. We observe instead that $N(X)\subset N(X^\top X)$ (why?) and note that if $X^\top Xv = 0$, then $0 = X^\top Xv\cdot v = Xv\cdot Xv = \|Xv\|^2$, so $Xv=0$. This shows that $N(X^\top X)\subset N(X)$ and therefore that $N(X^\top X) = N(X)$. It follows from nullity-rank that $\text{rank} (X^\top X) = \text{rank}(X)$. Since $\text{rank} (X^\top) = \text{rank}(X)$, we have $ \text{rank}(X^\top) = \text{rank}(X^\top X)$, so $\dim(R(X^\top)) = \dim(R(X^\top X))$, as required.

Answer 2

This might be helpful for future visitors:
$col(\cdot) = range(\cdot)$ denotes columnspace, $row(\cdot)$ denotes rowspace, $N(\cdot)$ denotes nullspace, $\cdot^{\perp} $ denotes orthogonal complement

consider arbitrary $X \in \mathbb{R}^{n \times m}$

Observation 1: $row(X) = col(X^{T})$
proof:
$v \in row(X) \implies v = X^T \mu$ for some $\mu \in \mathbb{R}^{n} \implies v \in col(X^{T})$
conversely, $v \in col(X^{T}) \implies v = X^T \mu$ for some $\mu \in \mathbb{R}^{n} \implies v \in row(X)$

Observation 2 $N(X)^{\perp} = row(X)$
proof:
proceed with $N(X)^{\perp} = row(X) \iff N(X) = row(X)^{\perp}$ [as $(U^{\perp})^{\perp} = U$]
$v \in N(X) \implies Xv = 0 \implies X_i \cdot v = 0 \text{ for all rows } X_i \text{ of } X$
therefore $ \mu \cdot v = 0, \forall \mu \in row(X)^{\perp} \implies v \in row(X)^{\perp}$
converse follows.

Observation 3: $N(X^TX) = N(X)$
proof: $v \in N(X^TX) \implies X^TXv = 0 \implies v^TX^TXv = 0 \implies ||Xv||_2^2 = 0 \implies Xv = 0 \implies v \in N(X)$, conversely $v \in N(X) \implies Xv = 0 \implies X^TXv = 0 \implies v \in N(X^TX)$

Claim: $col(X^TX) = col(X)$
short proof:
$N(X) = row(X)^{\perp} = col(X^T)^{\perp}$
$N(X^TX) = row(X^TX)^{\perp} = col(X^TX)^{\perp}$ [as $(X^TX)^T = X^TX$]
$N(X^TX) = N(X) \implies col(X^TX)^{\perp} = col(X^T)^{\perp} \implies col(X^TX) = col(X^T)$

alternative:
$v \in col(X^TX) \implies v = X^TX \mu = X^T(X \mu) \text{ for some $ \mu \in \mathbb{R}^m$} \implies v \in col(X^T)$

$v \in col(X^T) \implies v \in row(X) \implies v \in N(X)^{\perp} \implies v \in N(X^TX)^{\perp}$ \ $\implies v \in row(X^TX) \implies v \in col(X^TX)$ [as $(X^TX)^T = X^TX$]

$range(X) \subseteq range(X^TX)$ folows from claim