Prove for any matrix $X$ that $C(X) \subseteq C(XX^{T})$ without using SVD My task is to prove for any matrix $X$ that $C(X)  \subseteq C(XX^{T})$ without using SVD, where $C(A)$ denotes the column space of matrix $A$. This may be accomplished by proving $$ x \in C(X) \implies x \in C(XX^{T})$$ After struggling with just chugging out the inner product mathematics, I thought I may be able to use proof by contrapositive and came up with this:
Suppose there exits a vector $ u \notin C(XX^{T})$, which is to say there exists no vector $v$ such that $$ u = XX^{T}v $$ We may write, however, $X^{T}v = b$ by simple matrix/vector multiplication. Thus, there exists no vector $b$ such that $$ u = Xb $$ Hence, $ u \notin C(X) $ by definition. Thus, $$ x \notin C(XX^{T}) \implies x \notin C(X)$$ which is equivalent to $$ x \in C(X) \implies x \in C(XX^{T})$$ by contraposition. QED
Are there faults in my reasoning, and if so how may I improve my proof or obtain the desired result by other means?
 A: Here is an extended hint where we just try to reason about what's happening at every step. I give away the first big step of the proof but not the second.
We want to show that if a vector $x$ can be written $x = Xw$ for some $w$, then it can be written $x = X X^T u$ for some $u$. If $X$ is invertible this is easy, since $X^T$ will also be invertible so we can just take $u = (X^T)^{-1} w$. More generally we are fine if $X^T$ is surjective. So the entire difficulty of the problem is that $X^T$ might not be surjective and we can't guarantee that $w$ lies in the image of $X^T$.
So what can we do about this? Well, if $x = Xw$ and also $x = X X^T u$, then subtracting gives $X(w - X^T u) = 0$, or equivalently $w - X^T u \in \text{Nul}(X)$. So if $X^T$ isn't surjective and $\text{Nul}(X) = 0$ then we're screwed. But we must not be screwed, so the assumption that $X^T$ isn't surjective must somehow imply that $\text{Nul}(X) \neq 0$, which would provide some room for us to find $u$ such that $w - X^T u \in \text{Nul}(X)$. In fact it does and this is why (here we actually use the assumption that $X^T$ is the transpose for the first time!):

Claim: $\text{Nul}(X) = \text{Col}(X^T)^{\perp}$. That is, the nullspace $\{ v : Xv = 0 \}$ of $X$ is the orthogonal complement of the column space of $X^T$.

Proof. $Xv = 0$ iff $\langle v', Xv \rangle = 0$ for all $v'$ iff $\langle X^T v', v \rangle = 0$ for all $v'$ iff $v \in \text{Col}(X^T)^{\perp}$. $\Box$
Now we have the freedom to replace $w$ with another vector $w'$ such that $Xw = Xw'$, or equivalently such that $w - w' \in \text{Nul}(X) = \text{Col}(X^T)^{\perp}$. Now the question becomes: can we find a vector $w'$ such that

*

*$w - w' \in \text{Nul}(X) = \text{Col}(X^T)^{\perp}$, and

*$w' \in \text{Col}(X^T)$?

Can you finish from here?
