QR factorization: Show column spaces of $A$ and $Q$ are equal.

Question

If I have a $A=QR$ factorization by doing the Gram-Schmidt process, how can I prove that the column space of $A$ and the column space of $Q$ are same?

Answer 1

Let $A := (v_1, \ldots, v_k)$ with $\det(A) \neq 0$, so that the columns vector family $(v_n)_{n \in \{1, \ldots, k\}}$ is linear independent.

Now, proceed by induction over $k \in \mathbb{N}$, I will just show you the induction step.

Firstly, we set $\tilde{w}_{k+1} := v_{k + 1} - \sum_{j = 1}^{k} \langle v_{k+1}, w_j \rangle w_j \neq 0$. Then, for all $\ell \in \{1, \ldots, k)$ we have $\langle \tilde{w}_{k+1}, w_{\ell} \rangle = 0$. Now, we set $w_{k+1} := \frac{1}{\| \tilde{w}_{k+1}\| } \tilde{w}_{k+1}$.

Now, for the interesting part: We have span$(w_1, \ldots, w_{k}) =$span$(v_1, \ldots, v_{k})$ and \begin{equation*} w_{k+1} \in \text{span}(w_1, \ldots, w_k, v_{k+1}) \implies w_{k+1} \in \text{span}(v_1, \ldots, v_{k+1}), \end{equation*} Therefore, we have span$(w_1, \ldots, w_{k+1}) \subset$span$(v_1, \ldots, v_{k+1})$.

Because span$(v_1, \ldots, v_{k+1})$ is linearly independent (because it's an orthonormal system), we have \begin{equation*} \dim \text{span}(w_1, \ldots, w_{k+1}) = k + 1 = \dim \text{span}(v_1, \ldots, v_{k+1}), \end{equation*} which concludes the proof.