QR Decomposition

QR Decomposition

Every matrix $A$ can be factored as $A = QR$ where:

• $Q$ has orthonormal columns ($Q^T Q = I$)
• $R$ is upper triangular with positive diagonal entries

QR decomposition is the foundation for numerically stable least-squares, eigenvalue algorithms, and more.

Algorithm via Gram-Schmidt

Process each column of $A$ left-to-right:

• Apply Gram-Schmidt to produce orthonormal column $\mathbf{q}_{j}$
• $R_{ij} = \mathbf{a}_{j} \cdot \mathbf{q}_{i}$ for $i < j$ (how much of each previous $\mathbf{q}$ is in $\mathbf{a}_{j}$)
• $R_{jj} = \|\mathbf{w}_{j}\|$ (the norm of the residual)

Example

$A = \begin{pmatrix} 3 & 2 \\ 1 & 2 \end{pmatrix}, \quad Q = \begin{pmatrix} 0.9487 & -0.3162 \\ 0.3162 & 0.9487 \end{pmatrix}, \quad R = \begin{pmatrix} 3.1623 & 2.5298 \\ 0 & 1.2649 \end{pmatrix}$

Verify: $Q^T Q = I$ and $Q \times R = A$.

Your Task

Implement qr_decompose(A) returning (Q, R). Use Gram-Schmidt on the columns of A.