# QR Decomposition
## What it computes
A factorization of any m×n matrix A (with m ≥ n) into:
```
A = Q · R
```
where **Q** is orthogonal (its columns are unit vectors, all perpendicular to each other,
and Qᵀ·Q = I) and **R** is upper triangular.
## Intuition
An orthogonal matrix Q is a pure rotation or reflection — it doesn't distort lengths or
angles. R is triangular, so easy to work with. Together they let you decompose any linear
transformation into "rotate/reflect first, then scale and shear".
Because Qᵀ = Q⁻¹ (a property unique to orthogonal matrices), solving Ax = b via QR becomes:
```
QRx = b → Rx = Qᵀb
```
which is a triangular system — solved immediately by back substitution.
## Methods
### Gram-Schmidt orthogonalization
Take the columns of A one by one. For each new column, subtract its projections onto all
previously processed columns to remove any component in their direction, then normalize to
unit length. The normalized columns form Q; the projection coefficients fill R.
For columns a₁, a₂, ..., aₙ:
```
u₁ = a₁
u₂ = a₂ − proj_{u₁}(a₂)
u₃ = a₃ − proj_{u₁}(a₃) − proj_{u₂}(a₃)
...
qᵢ = uᵢ / ‖uᵢ‖
where proj_u(a) = (a·u / u·u) · u
```
Simple to understand, but accumulates floating-point errors for nearly dependent columns.
**Modified Gram-Schmidt** (projecting against already-orthogonalized columns rather than the
originals) reduces this error significantly.
### Householder reflections
Rather than building Q column by column, apply a sequence of reflection matrices Hₖ that
zero out the entries below the diagonal one column at a time:
```
Hₙ · ... · H₂ · H₁ · A = R
Q = H₁ · H₂ · ... · Hₙ
```
Each Hₖ is a Householder reflector of the form:
```
H = I − 2·vvᵀ / (vᵀv)
```
chosen so that it maps a given vector onto a multiple of a coordinate axis. More
numerically stable than Gram-Schmidt and preferred in practice.
## Computational cost
O(mn²) for an m×n matrix — more expensive than LU for square systems, but applicable to
non-square matrices and more numerically stable.
## When to use it
- **Least-squares problems:** solving overdetermined systems (more equations than unknowns),
where no exact solution exists and the best approximate solution is sought.
- **Eigenvalue algorithms:** QR iteration is the basis of the standard method for computing
all eigenvalues of a matrix.
- **Arnoldi and Lanczos iterations:** QR is used internally to orthogonalize the Krylov
basis.
- When numerical stability matters more than raw speed.
## Limitations
- More expensive than LU for square systems when stability is not a concern.
- The full Q matrix is large; often only Qᵀb is needed, not Q itself.