I am trying to prove that an $n \times m$ matrix $A$ with a rank $< m$ can always be written in the form $A = QR$ given that $Q$ is an $n \times m$ matrix with orthonormal columns and R is an upper triangular.
I really am not sure how to start this.
[Math] QR Factorization Proof
linear algebramatrices
Best Answer
Ordinarily we would specify more about a $QR$ factorization than simply $Q$ orthogonal and $R$ upper triangular, but this is a way to set out some basic ideas.
A good approach mimics the use of elementary matrices to effect a reduction to row-echelon form, but using instead a product of orthogonal matrices to achieve the same effect.
Induction is our friend. We dispose of columns one by one, starting with the first. If the first column is zero, we skip to the next one. If the first column is nonzero, we multiply by an orthogonal matrix that maps it to a column with all zeros except for the top entry.
A Householder transformation is convenient for this purpose. Given nonzero vector $\vec{u}$, we choose a unit vector $\vec{v}$ such that $\vec{u} - 2(\vec{u}^T \vec{v})\vec{v}$ is of the desired form (all zeros below the top entry). This transformation, an "elementary reflection", is achieved by multiplying by the orthogonal matrix $Q_1 = I - 2\vec{v}\vec{v}^T$.
With each successive column we limit our transformation to the successively lower rows, leaving the upper rows "fixed" as we needed in the preceding columns.
Working our way from left to right, we zero out all entries below the diagonal with the product of orthogonal matrices, thus getting an upper triangular result:
$$ Q_m \ldots Q_1 A = R $$
Using the orthogonality of these matrix factors, $Q_i^T = Q_i^{-1}$, the above is easily rearranged to the desired decomposition $A = QR$.