Uniqueness And Sign Choices In QR Factorization

What Makes a QR Factorization Unique?

A full-column-rank matrix has a reduced QR factorization in which the columns of \(\mathbf{Q}\) are orthonormal and \(\mathbf{R}\) is upper triangular. The product \(\mathbf{Q}\mathbf{R}\) reconstructs the original matrix. But these conditions alone do not specify the signs of the columns of \(\mathbf{Q}\): reversing a column of \(\mathbf{Q}\) and making a matching change to a row of \(\mathbf{R}\) leaves the product unchanged. Requiring positive diagonal entries in \(\mathbf{R}\) removes that ambiguity. We will prove both the resulting uniqueness and the precise form of the remaining sign choices when positivity is not required.

Throughout, matrices and vectors are real. Let \(\mathbf{A}\in\mathbb{R}^{m\times n}\), where \(m\ge n\). Full column rank means that the columns of \(\mathbf{A}\) are linearly independent. A matrix \(\mathbf{Q}\in\mathbb{R}^{m\times n}\) has orthonormal columns when \(\mathbf{Q}^{\top}\mathbf{Q}=\mathbf{I}_n\). An \(n\times n\) matrix is upper triangular when its entries below the main diagonal are zero.

For a full-column-rank matrix, the diagonal entries of an upper-triangular factor in a reduced QR factorization cannot be zero. Indeed, if \(\mathbf{R}\mathbf{x}=\mathbf{0}\), then \(\mathbf{A}\mathbf{x}=\mathbf{Q}\mathbf{R}\mathbf{x}=\mathbf{0}\). Independence of the columns of \(\mathbf{A}\) forces \(\mathbf{x}=\mathbf{0}\), so the square matrix \(\mathbf{R}\) is invertible. An invertible upper-triangular matrix has nonzero diagonal entries: solving \(\mathbf{R}\mathbf{x}=\mathbf{y}\) from the last row upward would otherwise fail to determine a unique solution at a zero diagonal entry. We will use that such a matrix has an upper-triangular inverse, whose diagonal entries are the reciprocals of those of \(\mathbf{R}\).

Why Positive Diagonal Entries Give Uniqueness

The key observation is that the difference between two candidate factorizations must act on the orthonormal columns by an upper-triangular matrix. Orthonormality then forces that matrix to be a diagonal sign matrix. Positive diagonal entries leave only the identity sign choice.

Proof. We prove the claim by induction on \(n\). For \(n=1\), the equation \(u_{11}^2=1\) gives \(u_{11}=1\) or \(u_{11}=-1\), and positivity selects \(u_{11}=1\). Now suppose \(n>1\). The first column of \(\mathbf{U}\) has no nonzero entries below its first entry because \(\mathbf{U}\) is upper triangular. Its squared length is \(1\), since \(\mathbf{U}^{\top}\mathbf{U}=\mathbf{I}_n\). Therefore \(u_{11}^2=1\). For each \(j>1\), the inner product of columns 1 and \(j\) is zero, so \(u_{11}u_{1j}=0\). Since \(u_{11}\ne0\), this gives \(u_{1j}=0\). Thus the first row and first column have no off-diagonal entries. The submatrix formed from rows and columns 2 through \(n\) is upper triangular and also has orthonormal columns, as follows from the corresponding entries of \(\mathbf{U}^{\top}\mathbf{U}=\mathbf{I}_n\). The induction hypothesis shows that this submatrix is diagonal with entries \(1\) or \(-1\). Hence \(\mathbf{U}\) has the claimed form. If all its diagonal entries are positive, they are all \(1\), so \(\mathbf{U}=\mathbf{I}_n\). \(\square\)

Proof. Both triangular matrices are invertible because their diagonal entries are positive. Define \(\mathbf{U}=\mathbf{Q}_2^{\top}\mathbf{Q}_1\). Multiplying the equality \(\mathbf{Q}_1\mathbf{R}_1=\mathbf{Q}_2\mathbf{R}_2\) on the left by \(\mathbf{Q}_2^{\top}\), and using \(\mathbf{Q}_2^{\top}\mathbf{Q}_2=\mathbf{I}_n\), gives \(\mathbf{U}\mathbf{R}_1=\mathbf{R}_2\). Therefore \(\mathbf{U}=\mathbf{R}_2\mathbf{R}_1^{-1}\), which is upper triangular. Also, \[ \mathbf{Q}_1=\mathbf{A}\mathbf{R}_1^{-1} =\mathbf{Q}_2\mathbf{R}_2\mathbf{R}_1^{-1} =\mathbf{Q}_2\mathbf{U}. \] Using the orthonormal columns of \(\mathbf{Q}_1\) and \(\mathbf{Q}_2\), we obtain \[ \mathbf{I}_n=\mathbf{Q}_1^{\top}\mathbf{Q}_1 =\mathbf{U}^{\top}\mathbf{Q}_2^{\top}\mathbf{Q}_2\mathbf{U} =\mathbf{U}^{\top}\mathbf{U}. \] The diagonal entries of \(\mathbf{U}=\mathbf{R}_2\mathbf{R}_1^{-1}\) are \(r_{2,ii}/r_{1,ii}>0\). The lemma gives \(\mathbf{U}=\mathbf{I}_n\). Thus \(\mathbf{Q}_1=\mathbf{Q}_2\), and the original equality then gives \(\mathbf{R}_1=\mathbf{R}_2\). \(\square\)

How Column-Sign Changes Preserve the Product

A diagonal sign matrix is a diagonal matrix \(\mathbf{D}\in\mathbb{R}^{n\times n}\) whose diagonal entries are each \(1\) or \(-1\). It satisfies \(\mathbf{D}^2=\mathbf{I}_n\). Starting from \(\mathbf{A}=\mathbf{Q}\mathbf{R}\), set \(\mathbf{Q}'=\mathbf{Q}\mathbf{D}\) and \(\mathbf{R}'=\mathbf{D}\mathbf{R}\). Multiplication by \(\mathbf{D}\) reverses the selected columns of \(\mathbf{Q}\); multiplying \(\mathbf{R}\) on the left by \(\mathbf{D}\) makes the matching sign changes to its rows.

Proof. For the first assertion, both \(\mathbf{R}_1\) and \(\mathbf{R}_2\) are invertible because \(\mathbf{A}\) has full column rank. Set \(\mathbf{U}=\mathbf{Q}_2^{\top}\mathbf{Q}_1\). As in the previous proof, \(\mathbf{R}_2=\mathbf{U}\mathbf{R}_1\), so \(\mathbf{U}=\mathbf{R}_2\mathbf{R}_1^{-1}\) is upper triangular, and \(\mathbf{Q}_1=\mathbf{Q}_2\mathbf{U}\). Orthonormality gives \(\mathbf{U}^{\top}\mathbf{U}=\mathbf{I}_n\). By the lemma, \(\mathbf{U}\) is diagonal with entries \(1\) or \(-1\); call it \(\mathbf{D}\). The equations become \(\mathbf{Q}_1=\mathbf{Q}_2\mathbf{D}\) and \(\mathbf{R}_2=\mathbf{D}\mathbf{R}_1\). Conversely, \((\mathbf{Q}\mathbf{D})^{\top}(\mathbf{Q}\mathbf{D})=\mathbf{D}\mathbf{I}_n\mathbf{D}=\mathbf{I}_n\), and \(\mathbf{D}\mathbf{R}\) is upper triangular. Their product is \(\mathbf{Q}\mathbf{D}\mathbf{D}\mathbf{R}=\mathbf{Q}\mathbf{R}=\mathbf{A}\). Thus they meet every condition of a reduced QR factorization. \(\square\)

The theorem also counts the possibilities: there are \(2^n\) diagonal sign matrices, one for each choice of signs on \(n\) diagonal entries. Exactly one of these choices makes every diagonal entry of the triangular factor positive. The theorem does not claim that a rank-deficient matrix has the same uniqueness property; its full-column-rank hypothesis is essential to the invertibility used in the proof.

Worked Examples

Common Mistake: Changing Only One Factor

A sign change must be made in both factors. For the first example, reversing the first column of \(\mathbf{Q}\) but leaving \(\mathbf{R}\) unchanged gives a first product column of \((-\sqrt{2})(\mathbf{q}_1)=(-1,-1,0)^{\top}\), rather than the original \((1,1,0)^{\top}\). The product is no longer \(\mathbf{A}\). The correction is to reverse the corresponding row of \(\mathbf{R}\) as well: \(\mathbf{Q}'=\mathbf{Q}\mathbf{D}\) and \(\mathbf{R}'=\mathbf{D}\mathbf{R}\). Since \(\mathbf{D}^2=\mathbf{I}_n\), the two sign changes cancel in the product.

A second potential confusion is to treat “upper triangular with orthonormal columns” as if it automatically meant the identity. The lemma shows the precise conclusion: the matrix must be diagonal with entries \(1\) or \(-1\). Positivity is the extra condition that forces every sign to be \(1\). Without that condition, there are genuine alternative factorizations.