QR decomposition

Definition: The QR decomposition of an $m \times n$ matrix $A$ (with $m \geq n$) is a factorization:

$$A = QR$$

where:

• $Q$ is an $m \times m$ orthogonal (unitary) matrix
• $R$ is an $m \times n$ upper triangular matrix (often written with zeros below the first $n$ rows)

The reduced QR has $Q$ as $m \times n$ with orthonormal columns and $R$ as $n \times n$ upper triangular.

Example:
$$\begin{pmatrix} 1 & 1 \\ 1 & 0 \\ 0 & 1 \end{pmatrix} = \begin{pmatrix} 1/\sqrt{2} & 1/\sqrt{6} \\ 1/\sqrt{2} & -1/\sqrt{6} \\ 0 & 2/\sqrt{6} \end{pmatrix} \begin{pmatrix} \sqrt{2} & 1/\sqrt{2} \\ 0 & \sqrt{3/2} \end{pmatrix}$$

Methods: Gram-Schmidt process, Householder reflections, or Givens rotations.

Applications: solving least squares problems, eigenvalue algorithms (QR algorithm), and orthogonalization.