# Uniqueness of the QR-factorization

I'm preparing a talk about the QR-factorization.

I alredy have proved the existence of it: If $$A \in \mathbb{R}^{n \times m}$$ there exists an orthogonal matrix $$Q \in \mathbb{R}^{n \times n}$$ and an upper triangular $$R \in \mathbb{R}^{n \times m}$$ with $$A=QR$$.

There is a mistake in the following theorem, see my answer below.

Now I want to prove the following theorem: If $$A \in \mathbb{R}^{n \times m}$$ with $$rank(A)=m$$ has the QR-factorization $$A=QR$$ where $$R$$ has positive diagonal entries, then the Q and R are unique.

But all literature use proves with another factorisation. So i dont now how to handle, maybe sombody can help, thanks.

• "But all literature use proves with another factorisation." -- out of curiosity, are you referring to the Cholesky Factorization? When dealing with invertible $A$, there is a very nice correspondence between Cholesky results and QR results. Nov 24, 2021 at 0:55

Once you have one $$QR$$ factorization, say $$A=Q_1R_1$$, then it is easy to produce another one by defining $$Q_2=Q_1B$$ and $$R_2=B^{-1}R_1$$. But for $$Q_2$$ and $$R_2$$ to be orthogonal and upper triangular, respectively, $$B$$ must be orthogonal and diagonal. That means it can only have $$\pm 1$$ as elements on the diagonal. If $$R_1$$ already has positive diagonal entries, then $$B$$ must be the identity.

• I like the proof by contradiction, but it's not clear to me that all possible $Q_2$ can be achieved with $Q_1B$. Do you have any resources for this? Nov 19, 2021 at 17:16
• @rhkoulen Action of a group on itself by right multiplication is transitive Nov 19, 2021 at 18:25
• A lot of upvotes but it seems you've 'proven' a false statement to be true. Nov 24, 2021 at 0:56

There is an mistake in the Theorem of the uniqueness.

For example: If $$A= \begin{pmatrix} 1&0\\ 0&1\\ 0&0\\ \end{pmatrix}$$. We have $$A= \begin{pmatrix} 1&0&0\\ 0&1&0\\ 0&0&1 \end{pmatrix} \begin{pmatrix} 1&0\\ 0&1\\ 0&0\\ \end{pmatrix}$$ and $$A=\begin{pmatrix}1&0&0\\ 0&1&0\\ 0&0&-1 \end{pmatrix} \begin{pmatrix} 1&0\\ 0&1\\ 0&0\\ \end{pmatrix}$$. Two different QR-factrorisations.

You can fix that Theorem, by additional demanding of m=n. Then the prove above works, the problem in was the null space of R.

The answer depends on the type of QR factorization considered.

Take $$A \in \mathbb R^{n\times m}$$.

If $$n \le m$$, then you have only one QR factorization: $$A = QR$$ with $$Q \in \mathbb R^{n\times n}$$ and $$R \in \mathbb R^{n\times m}$$. This factorization is unique if $$A$$ is full-rank (its rank is $$n$$) and $$R_{ii} > 0$$, $$1 \le i \le n$$.

If $$n > m$$ ($$A$$ is thin), then you have two types of QR factorizations.

Full QR: $$Q \in \mathbb R^{n\times n}$$ and $$R \in \mathbb R^{n \times m}$$. $$R$$ has zeros from row $$m+1$$ to $$n$$. This factorization is not unique. For example, consider a square orthogonal transformation $$Q_1 \in \mathbb R^{n\times n}$$ that modifies rows $$m+1$$ to $$n$$ only. Then $$(QQ_1^T) (Q_1 R)$$ is a valid QR factorization of $$A$$.

Thin QR: $$Q \in \mathbb R^{n\times m}$$ and $$R \in \mathbb R^{m\times m}$$. This factorization is unique if $$A$$ is full-rank (its rank is $$m$$) and $$R_{ii} > 0$$, $$1 \le i \le m$$. $$R$$ is square non-singular upper triangular. $$Q$$ is thin and satisfies $$Q^T Q = I$$.

If $$A \in \mathbb R^{n\times m}$$ with $${\rm rank}(A) = m$$ has the QR-factorization $$A = QR$$ where $$R$$ has positive diagonal entries, then the $$Q$$ and $$R$$ are unique.
$${\rm rank}(A) = m$$ implies that $$n \ge m$$. If $$n=m$$, the factorization is unique. If $$n > m$$, it is unique if you consider the thin QR factorization. It is not if you consider the full QR factorization.
Bonus: proof of uniqueness. I will give the proof in the case $$n \ge m$$ with the thin QR factorization. The case $$n < m$$ is a simple extension.
Assume we have two QR factorizations: $$A = Q_1 R_1 = Q_2 R_2$$. We assume that $$R_1$$ and $$R_2$$ are square non-singular. This implies that $$A^T A = R_1^T R_1 = R_2^T R_2$$. Therefore $$R_1 R_2^{-1} = (R_2 R_1^{-1})^T$$. $$R_1 R_2^{-1}$$ is upper triangular and $$(R_2 R_1^{-1})^T$$ is lower triangular. So there is a diagonal matrix $$D$$ such that $$D = R_1 R_2^{-1}$$. From $$R_1 R_2^{-1} = (R_2 R_1^{-1})^T$$, we get that $$D = D^{-1}$$ so that $$D^2 = I$$ (identity matrix). Since the diagonals of $$R_1$$ and $$R_2$$ are positive, the diagonal of $$D$$ must be positive. So $$D=I$$ is the only solution and $$R_1 = R_2$$. Then: $$A R_1^{-1} = Q_1 = Q_2$$. The factorization is unique.
The proof breaks down for $$n>m$$ and the full QR factorization because the R factors are non-square and cannot be inverted.