Reduced QR Factorization And Its Dimensions

What “Reduced” Means

A QR factorization expresses a matrix as a product: the letter \(Q\) denotes a matrix whose columns are orthonormal, and \(R\) denotes an upper-triangular matrix. When the original matrix has more rows than columns, choosing the dimensions of these factors matters. In reduced QR, the factor \(Q\) has the same number of columns as the original matrix, and \(R\) is square. This keeps the factorization compact while retaining the original matrix’s shape through the product.

Throughout, the scalars are real. Let \(\mathbf{A}\in\mathbb{R}^{m\times n}\), where \(1\le n\le m\), and write its columns as \(\mathbf{a}_1,\dots,\mathbf{a}_n\). The matrix has full column rank when these columns are linearly independent: the equation \(c_1\mathbf{a}_1+\cdots+c_n\mathbf{a}_n=\mathbf{0}\) then forces every coefficient \(c_j\) to be zero. Two vectors are orthogonal when their dot product is zero, and a list is orthonormal when its vectors are pairwise orthogonal and each has norm \(1\).

The dimensions make the product possible: an \(m\times n\) matrix multiplied by an \(n\times n\) matrix gives an \(m\times n\) matrix. The triangular shape of \(\mathbf{R}\) records the order in which the columns are built. For a full-column-rank matrix, Gram–Schmidt constructs each new column of \(\mathbf{Q}\) from the corresponding column of \(\mathbf{A}\) after removing its components in earlier directions.

Why Full Column Rank Gives These Factors

The construction uses the dot product and norm in \(\mathbb{R}^m\). At stage \(j\), subtract from \(\mathbf{a}_j\) its projections onto the previously constructed orthonormal columns. The remaining vector is the part not already accounted for by those columns. Full column rank ensures that this remainder is not zero, so it can be normalized to have norm \(1\).

Proof. We construct the columns \(\mathbf{q}_1,\dots,\mathbf{q}_n\) in order. Set \(\mathbf{u}_1=\mathbf{a}_1\), \(r_{11}=\|\mathbf{u}_1\|\), and \(\mathbf{q}_1=\mathbf{u}_1/r_{11}\). Because the columns of \(\mathbf{A}\) are independent, \(\mathbf{a}_1\ne\mathbf{0}\), so \(r_{11}>0\) and \(\mathbf{q}_1\) is defined with norm \(1\).

For each \(j=2,\dots,n\), assuming \(\mathbf{q}_1,\dots,\mathbf{q}_{j-1}\) have been constructed as an orthonormal list, set \(r_{ij}=\mathbf{q}_i\cdot\mathbf{a}_j\) for \(1\le i<j\), and define

For any \(k<j\), orthonormality gives

Thus \(\mathbf{u}_j\) is orthogonal to all the earlier \(\mathbf{q}_i\). The construction also gives \(\operatorname{span}\{\mathbf{q}_1,\dots,\mathbf{q}_{j-1}\}=\operatorname{span}\{\mathbf{a}_1,\dots,\mathbf{a}_{j-1}\}\): at each previous stage, \(\mathbf{a}_i\) is a combination of \(\mathbf{q}_1,\dots,\mathbf{q}_i\), and \(\mathbf{q}_i\) is a combination of \(\mathbf{a}_1,\dots,\mathbf{a}_i\). If \(\mathbf{u}_j=\mathbf{0}\), its defining equation would express \(\mathbf{a}_j\) as a combination of earlier \(\mathbf{q}_i\), hence of earlier columns of \(\mathbf{A}\). That contradicts independence. Therefore \(r_{jj}=\|\mathbf{u}_j\|>0\), and we can set \(\mathbf{q}_j=\mathbf{u}_j/r_{jj}\). This extends the orthonormal list.

For each \(j\), the construction rearranges to \(\mathbf{a}_j=\sum_{i<j}r_{ij}\mathbf{q}_i+r_{jj}\mathbf{q}_j\). Define \(\mathbf{Q}\) to have columns \(\mathbf{q}_1,\dots,\mathbf{q}_n\), and define \(\mathbf{R}\) by these \(r_{ij}\) for \(i\le j\), with \(r_{ij}=0\) for \(i>j\). Then \(\mathbf{Q}\) has orthonormal columns, \(\mathbf{R}\) is upper triangular, and the column equations give \(\mathbf{A}=\mathbf{Q}\mathbf{R}\). Its dimensions are \(m\times n\) and \(n\times n\), respectively. \(\square\)

Computing and Checking the Factors

What the Dimensions Tell You

For an \(m\times n\) matrix with \(m>n\), reduced \(Q\) is tall: it has \(m\) rows and \(n\) columns. Its columns provide exactly \(n\) orthonormal directions in \(\mathbb{R}^m\). The matrix \(R\) is \(n\times n\), not \(m\times n\), and its upper-triangular entries store the coefficients needed to rebuild each column of \(\mathbf{A}\) from those directions. When \(m=n\), reduced \(Q\) and \(R\) are both square. In either case, their product has the same dimensions as \(\mathbf{A}\).

A useful check on the construction is that each diagonal entry \(r_{jj}\) is the norm of a residual vector. Full column rank guarantees that each such residual is nonzero, so the construction produces \(r_{jj}>0\). This conclusion belongs to the stated Gram–Schmidt construction; it does not require treating the signs of all possible QR factors as a separate question.

Proof. Suppose \(\mathbf{A}\mathbf{x}=\mathbf{0}\) for some \(\mathbf{x}\in\mathbb{R}^n\). Since the columns of \(\mathbf{Q}\) are orthonormal, the \((i,j)\) entry of \(\mathbf{Q}^{\top}\mathbf{Q}\) is \(\mathbf{q}_i\cdot\mathbf{q}_j\), so \(\mathbf{Q}^{\top}\mathbf{Q}=\mathbf{I}_n\). Therefore \(\mathbf{0}=\mathbf{Q}^{\top}\mathbf{A}\mathbf{x}=\mathbf{Q}^{\top}\mathbf{Q}\mathbf{R}\mathbf{x}=\mathbf{R}\mathbf{x}\). The last row of this triangular system gives \(r_{nn}x_n=0\), hence \(x_n=0\). The row above then gives \(r_{n-1,n-1}x_{n-1}+r_{n-1,n}x_n=0\), hence \(x_{n-1}=0\). Continuing upward, each row gives \(r_{ii}x_i=0\) once \(x_{i+1},\dots,x_n\) are zero, so every \(x_i=0\). Thus \(\mathbf{A}\mathbf{x}=\mathbf{0}\) has only the zero solution, which means its columns are independent. \(\square\)

Common Pitfall: Mixing the Two Dimension Choices

For a \(3\times2\) matrix, a common mistake is to write a reduced \(Q\) of size \(3\times2\) and an \(R\) of size \(3\times2\), then claim their product equals the original matrix. This is not a valid multiplication: the two inner dimensions are \(2\) and \(3\), so \((3\times2)(3\times2)\) is undefined. In reduced QR, \(Q\) is \(3\times2\) and \(R\) is \(2\times2\), making \((3\times2)(2\times2)\) a \(3\times2\) product.

There is also a full QR convention in which \(Q\) is \(m\times m\) and \(R\) is \(m\times n\). Those dimensions can give a valid factorization, but they describe a different choice of factors. Do not mix the full-size \(Q\) with the reduced-size \(R\), or vice versa. Before computing entries, write down the intended dimensions and check that the number of columns of the first factor equals the number of rows of the second.

Reduced QR is useful whenever a tall matrix needs a representation that separates orthonormal directions from triangular coefficients. Its factor dimensions are compact, and the defining properties give direct checks: verify the shape of each factor, verify orthonormality of \(Q\)’s columns, verify that entries below the diagonal of \(R\) vanish, and multiply \(QR\) to recover \(A\). These checks catch both arithmetic errors and dimension errors.