QR Factorization For Rank-Deficient Matrices

Why Rank Deficiency Needs a Careful QR Construction

Gram–Schmidt turns independent columns into orthonormal vectors. If a column is dependent on the columns already processed, however, its Gram–Schmidt residual is zero, so it cannot be normalized. That does not prevent a QR factorization: it means we must skip that residual, continue processing later columns, and then complete the orthonormal set to a basis of the ambient space.

Throughout, matrices and vectors have real entries, and vectors are columns. Let \(\mathbf{A}\in\mathbb{R}^{m\times n}\) have columns \(\mathbf{a}_1,\dots,\mathbf{a}_n\). A full QR factorization uses a square matrix \(\mathbf{Q}\) with \(m\) orthonormal columns and a matrix \(\mathbf{R}\) with \(m\) rows. The dimensions matter for wide matrices as well as tall ones.

In particular, \(\mathbf{Q}^{\top}\mathbf{Q}=\mathbf{I}_m\). The first \(r\) columns of \(\mathbf{Q}\), where \(r\) is the rank of \(\mathbf{A}\), can be chosen to span the column space of \(\mathbf{A}\). The remaining columns complete them to an orthonormal basis of \(\mathbb{R}^m\). Consequently, the last \(m-r\) rows of \(\mathbf{R}\) are zero. If \(n>m\), then \(\mathbf{R}\) is still \(m\times n\); it has no rows beyond row \(m\).

The Construction and Why It Works

Process the columns in their given order. For a column \(\mathbf{a}_j\), subtract its projections onto the orthonormal vectors already constructed. A nonzero remainder supplies a new orthonormal vector; a zero remainder is skipped. After all columns have been processed, complete the orthonormal set using vectors from the standard basis of \(\mathbb{R}^m\), applying the same projection-and-normalization step.

The zero test is essential: normalization means dividing by the norm, and \(\|\mathbf{0}\|=0\). Skipping a zero remainder does not lose information, because that column is already in the span of the vectors constructed so far. Continuing through the columns is also essential: a later column can add a new direction even when an earlier column was dependent.

Proof. The \(m\) orthonormal columns of \(\mathbf{Q}\) are linearly independent: if \(\sum_{i=1}^m c_i\mathbf{q}_i=\mathbf{0}\), taking the dot product with \(\mathbf{q}_k\) gives \(c_k=0\) for each \(k\). Since \(m\) linearly independent vectors in \(\mathbb{R}^m\) form a basis, write any column \(\mathbf{a}_j\) as \(\mathbf{a}_j=\sum_{i=1}^m c_i\mathbf{q}_i\). Taking the dot product with \(\mathbf{q}_k\) gives \(c_k=\mathbf{q}_k\cdot\mathbf{a}_j=r_{kj}\). Thus the \(j\)th column of \(\mathbf{Q}\mathbf{R}\) is \(\sum_{i=1}^m r_{ij}\mathbf{q}_i=\mathbf{a}_j\). This holds for every column, so \(\mathbf{Q}\mathbf{R}=\mathbf{A}\). \(\square\)

Proof. Process the columns using the construction above. Each new nonzero residual is orthogonal to every previously accepted vector: for any previous \(\mathbf{q}_i\), the projection-subtraction formula gives \(\mathbf{q}_i\cdot\mathbf{w}_j=0\). Normalizing such a residual therefore preserves orthonormality. Also, after processing column \(j\), the accepted vectors span \(\mathbf{a}_1,\dots,\mathbf{a}_j\): each column equals the sum of its projections onto the current vectors and its residual; that residual is either zero or is added to the list. Induction over \(j\) proves the spanning claim. Thus, after all columns are processed, the accepted vectors are an orthonormal basis for \(\operatorname{Col}\mathbf{A}\).

Now process the standard basis vectors and append every nonzero residual. Each appended vector is orthogonal to the existing list, so orthonormality is preserved. This procedure must eventually produce \(m\) vectors: if it stopped with fewer, then each standard basis vector would lie in the final span, because its residual was either zero or was appended. The final span would then contain all of \(\mathbb{R}^m\), which cannot be spanned by fewer than \(m\) linearly independent vectors. Put the resulting \(m\) vectors into \(\mathbf{Q}\), and define \(\mathbf{R}=\mathbf{Q}^{\top}\mathbf{A}\). The lemma gives \(\mathbf{Q}\mathbf{R}=\mathbf{A}\).

It remains to check the required zero entries. For each \(i\leq m\), either \(\mathbf{q}_i\) was produced from a nonzero residual at some column \(k_i\), or it was added during completion. The column indices \(k_i\) for vectors produced from columns increase with \(i\). If \(i>j\) and \(\mathbf{q}_i\) came from column \(k_i\), then \(k_i\geq i>j\). When it was constructed, \(\mathbf{q}_i\) was orthogonal to every earlier column, including \(\mathbf{a}_j\), which lies in the span of the columns before \(k_i\). If \(\mathbf{q}_i\) was added during completion, it is orthogonal to every column of \(\mathbf{A}\). In either case \(r_{ij}=\mathbf{q}_i\cdot\mathbf{a}_j=0\). Hence \(\mathbf{R}\) is upper trapezoidal, as required. \(\square\)

Worked Factorizations

Common Pitfall: Trying to Normalize Zero

For columns \(\mathbf{a}_1=(1,0)^{\top}\) and \(\mathbf{a}_2=(2,0)^{\top}\), Gram–Schmidt gives \(\mathbf{q}_1=(1,0)^{\top}\), then \(\mathbf{w}_2=\mathbf{a}_2-(\mathbf{q}_1\cdot\mathbf{a}_2)\mathbf{q}_1=(2,0)^{\top}-2(1,0)^{\top}=\mathbf{0}\). The wrong calculation is to set \(\mathbf{q}_2=\mathbf{w}_2/\|\mathbf{w}_2\|=\mathbf{0}/0\); division by zero is undefined. Skip this residual, and complete the set with \(\mathbf{e}_2\). Then \(\mathbf{Q}=\mathbf{I}_2\) and \(\mathbf{R}=\begin{bmatrix}1&2\\0&0\end{bmatrix}\). Direct multiplication gives \(\mathbf{Q}\mathbf{R}=\mathbf{A}\), and \(\mathbf{R}\) is upper triangular.

For a wide matrix, upper trapezoidal means entries below the main diagonal are zero wherever such entries exist; it does not mean that \(\mathbf{R}\) is square. Also, skipping a dependent column does not mean stopping the process: the wide example shows that a later column can contribute a new orthogonal direction. The full construction keeps these cases together by defining \(\mathbf{Q}\) to have one orthonormal column for each row of \(\mathbf{A}\), then recording every column’s coefficients in \(\mathbf{R}\).