Householder QR

Somewhere deep inside your spreadsheet solver, your least-squares fit, and your eigenvalue routine lives a single workhorse: QR factorization. Every matrix $A$ can be written as $A = QR$, where $Q$ is orthogonal ($Q^T Q = I$) and $R$ is upper triangular. That decomposition turns messy simultaneous equations into a clean back-substitution.

The challenge is computing $Q$ and $R$ without accumulating the floating-point errors that plague naive approaches like Gram–Schmidt. The answer, developed by Alston Scott Householder in 1958, is disarmingly geometric: take the first column of $A$ and reflect it onto the first coordinate axis, killing every entry below the diagonal in one shot. Repeat column by column and you are done.

Each reflection is an orthogonal transformation — it preserves lengths and angles, so it cannot amplify rounding errors. That one insight made Householder QR the algorithm of choice for dense matrices in numerical software for the next seven decades.

The demo below shows a random $4 \times 4$ matrix. At each step one Householder reflection zeroes out everything below the diagonal in the current column. Click Next step to apply each reflection and watch the matrix march toward upper-triangular form.

<!-- {{c_html_intro}} -->
<p class="hint">{{hint_para}}</p>
<div class="matrix-area">
  <div class="mat-label">{{label_matrix_a}}</div>
  <table id="matA" class="mat"></table>
</div>
<div class="status" id="status">{{status_ready}}</div>
<div class="btns">
  <button id="btnStep" type="button">{{btn_step}}</button>
  <button id="btnReset" type="button" class="ghost">{{btn_reset}}</button>
</div>
<div class="step-info" id="stepInfo"></div>

/* {{c_css_intro}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; font-size: 14px; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.matrix-area { margin: .5rem 0; }
.mat-label { font-size: .8rem; font-weight: 700; color: #1d3557; margin-bottom: .2rem; letter-spacing: .04em; }
.mat { border-collapse: separate; border-spacing: 3px; }
.mat td {
  width: 54px; height: 36px; text-align: right; padding: 0 6px;
  font: 600 12px ui-monospace, monospace; border-radius: 5px;
  transition: background .35s, color .35s;
}
.cell-normal { background: #e8eef3; color: #1d3557; border: 1px solid #cdd9e3; }
.cell-zero   { background: #d4edda; color: #0a7d33; border: 1px solid #b8dbc3; }
.cell-pivot  { background: #fff3cd; color: #856404; border: 1px solid #ffe08a; }
.cell-active { background: #f8d7da; color: #842029; border: 1px solid #f5c2c7; }
.status { font-size: 1rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; }
.status.ok   { color: #0a7d33; }
.status.info { color: #1d3557; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .5rem; }
button { font: 600 14px system-ui; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .4; cursor: not-allowed; }
.step-info { font-size: .82rem; color: #555; min-height: 1.2em; line-height: 1.5; }

// Code not found

Notice that after step $k$ the entries below the diagonal in column $k$ are exactly zero (up to floating-point rounding). The matrix never needs to store $Q$ explicitly — the reflection vectors are enough to reconstruct it later. By the final step the matrix has become $R$, and the accumulated reflections give $Q^T$.

How expensive is Householder QR, and how much should you trust the answer?

• Cost. Factoring an $m \times n$ matrix ($m \ge n$) requires roughly $2n^2(m - n/3)$ floating-point operations — $O(n^3)$ for square matrices. That is the same order as Gaussian elimination, but with a constant factor about twice as large. The extra work buys something valuable.
• Backward stability. Householder reflections are orthogonal transformations: they rotate and reflect but never stretch. A theorem due to Wilkinson shows that the computed $\hat{Q}$ and $\hat{R}$ satisfy $\hat{Q}\hat{R} = A + \delta A$ where $\|\delta A\| / \|A\| = O(\varepsilon_{\text{machine}})$. In plain terms: the result is the exact QR of a matrix that differs from $A$ by a tiny rounding-error perturbation. No other QR method offers this guarantee as cleanly.
• Gram–Schmidt comparison. Classical Gram–Schmidt is cheaper per column but can lose orthogonality catastrophically when columns are nearly dependent. Modified Gram–Schmidt is better but still only conditionally stable. Householder wins on stability for any well-posed problem.
• LAPACK's choice. The routine dgeqrf in LAPACK — the reference for nearly all scientific computing — implements Householder QR with blocked updates for cache efficiency.

The algorithm is solved: it has the optimal stability class for this problem, and its cost is within a constant of the information-theoretic minimum.

QR factorization by Householder reflections is one of the most-called subroutines in all of scientific software:

• Least-squares regression. To fit a model $Ax \approx b$ in the least-squares sense, form the QR factorization of $A$ and solve $Rx = Q^T b$ by back-substitution. This is numerically far superior to forming the normal equations $A^T A x = A^T b$, which square the condition number.
• Eigenvalue algorithms. The QR algorithm — the standard method for computing all eigenvalues of a dense matrix — applies Householder QR at every iteration. Without a stable QR step the iteration would diverge in finite precision.
• Signal and image processing. Orthogonal projections computed via QR appear in beamforming, noise removal, and the discrete cosine transform used in JPEG compression.
• Compressed sensing and sparse recovery. Many algorithms for recovering sparse signals (LASSO, OMP) rely on QR to maintain numerical orthogonality as columns are selected greedily.
• Quantum chemistry. Self-consistent field methods (Hartree–Fock, DFT) iterate on large dense matrices; QR stabilizes each step.

Householder's 1958 paper solved the stability problem so thoroughly that its approach has barely changed. The blocked variant in LAPACK is a tuning detail; the mathematical core is exactly what Householder wrote.

Householder QR is a rare case in numerical computing where a single geometric idea — reflect a vector onto an axis — solved a problem so completely that the field has not had to revisit it. Chain $n$ such reflections, accumulate them implicitly, and you have an orthogonal $Q$ and upper-triangular $R$ whose product is your original matrix, accurate to machine precision.

The next time you call a least-squares solver, run a dimensionality reduction, or compute eigenvalues, a Householder reflection is almost certainly doing the heavy lifting — quietly, stably, and exactly as Alston Scott Householder intended in 1958.