Does QR decomposition always exist ? Are there any caveats to be aware of?

256 Views Asked by At

I've checked previous questions, especially this one Matrices admit a QR decomposition

Yet, Wikipedia's page indicates something different:

More generally, we can factor a complex m×n matrix A, with m ≥ n, as the product of an m×m unitary matrix Q and an m×n upper triangular matrix R.

(And I assume this is valid for real matrices as well.)

Source: https://en.wikipedia.org/wiki/QR_decomposition

I've checked that the QR decomposition is calculated for at least some matrices with m<n, but is that in Wikipedia an error, or what is the cause ?

1

There are 1 best solutions below

0
On

The existence of the QR decomposition is essentially equivalent to the ability to execute the Gram-Schmidt process. More precisely, the decomposition comes from regarding the columns of your matrix as vectors and then performing the Gram-Schmidt process. The matrix $R$ records the operations that you perform while doing the Gram-Schmidt process. This matrix is upper triangular because during Gram-Schmidth, whenever you modify the $i$th vector you only do so using linear combinations of the previous $i-1$ vectors. That fact that the end result of the process is an orthonormal collection is why the matrix $Q$ is orthogonal

If you have $n$ vectors in an $m$-dimensional space with $m\geq n$ then it is always possible to orthonormalize them using Gram Schmidt and so it is still possible to define the $QR$ decomposition in this case. In order to get $Q$, one just arbitrarily extend the original collection to a basis and then do Gram-Schmidt.

This goes wrong when $m<n$, since in general, it is not possible to orthonormalize $n$ vectors in an $m$-dimensional space. This is easy to see since orthormalize collections are automatically linearly independent. It is possible to orthonormalize the first $m$ vectors in the collection, but then you are stuck.