# Showing a matrix decomposition is unique using a least squares problem?

Suppose $M$ is an invertible matrix with a $QR$ decomposition. Because $M$ is invertible this $QR$ decomposition will be unique. I want to show it is unique via a least squares problem.

Say $Ax = b$ and as $A$ is invertible we will have an exact solution for the least squares problem. This (I think) should ultimately lead to showing $Q$ and $R$ are unique in the $QR$ decomposition of $A$. An exact solution means there exists $x$ such that $\Vert Ax - b \Vert_2 = 0$. Rewriting as

$$\Vert QRx - b \Vert_2 = 0$$

Ortogonal transformations are invariant under the 2-norm so multiplying by $Q^T$ gives

$$\Vert Rx - Q^Tb \Vert_2 = 0$$

Well that's as far as I got. I don't know if I'm even on the right track. Any ideas how to show the $QR$ decomposition is unique (via least squares) or is this actually not possible?

• The QR decomposition is not unique even for invertible matrices. For example $1 = 1\times 1 = -1\times -1$. – Pawel Kowal Aug 28 '16 at 20:48
• It says here it is unique in particular cases - en.wikipedia.org/wiki/QR_decomposition – eurocoder Aug 29 '16 at 7:58

Suppose $\mathbf{A}\in\mathbb{R}^{m\times n}$ has full column rank. The thin $\mathbf{Q}\mathbf{R}$ factorization $$\mathbf{A} = \mathbf{Q}_{1}\mathbf{R}_{1}$$ is unique where $\mathbf{Q}_{1}\in\mathbb{R}^{m\times n}$ has orthonormal columns and $\mathbf{R}_{1}$ is upper triangular with positive diagonal entries. Moreover, $\mathbf{G}=\mathbf{R}_{1}^{T}$ where $\mathbf{G}$ is the lower triangular Cholesky factor of $\mathbf{A}^{T}\mathbf{A}.$
Since $\mathbf{A}^{T}\mathbf{A} = \left(\mathbf{Q}_{1} \mathbf{R}_{1}\right)^{T} \left(\mathbf{Q}_{1} \mathbf{R}_{1}\right) = \mathbf{R}_{1}^{T}\mathbf{R}_{1}$ we see that $\mathbf{G}=\mathbf{R}_{1}^{T}$ is the Cholesky factor of $\mathbf{A}^{T}\mathbf{A}$. This factor is unique by Theorem 4.2.5. Since $\mathbf{Q}_{1} = \mathbf{A}\mathbf{R}_{1}^{-1}$ it follows that $\mathbf{Q}_{1}$ is also unique.