Uniqueness of the QR-factorization

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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$.

Regarding your theorem:

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.