◄ WORLD V · SONNY 5DART 089 · a helldive at the net

HOUSEHOLDER QR zero a column with one clean reflection

To factor a matrix into an orthogonal Q and an upper-triangular R — the stable heart of least-squares and eigenvalue solvers — Householder reflects each column so everything below the diagonal becomes zero in one stroke. A mirror, not the slow one-vector-at-a-time orthogonalisation, and far more numerically stable.

THE TECHNIQUE reflect a column onto an axis

For a column x, choose the reflection that maps it exactly onto the first axis — length −‖x‖ in the diagonal slot, zeros below. The mirror is H = I − 2 vvᵀ/vᵀv, applied as a cheap rank-1 update so the full matrix is never built. Repeat per column to reach R. Watch a vector snap to the axis. live demo

HISTORY & CREDIT the stable one, and its older cousins

“QR = Gram-Schmidt” — classical Gram-Schmidt is the method the unstable one; Householder’s reflections are what solvers actually run. cited

1820 / 1907 · Laplace uses the orthogonalisation (in the supplements to his probability treatise); Erhard Schmidt formalises it — “Gram-Schmidt,” but Gram (1883) and Laplace preceded the name.
1958 · Alston Householder introduces the reflection — one orthogonal transform zeros a whole sub-column, and it is backward-stable where classical Gram-Schmidt loses orthogonality.
the sign trick · aim at −sign(x₁)‖x‖, not +, to avoid catastrophic cancellation — the detail Wilkinson made famous; get it wrong and the whole factorisation degrades.
the rank-1 form · apply x’ = x − 2(vᵀx / vᵀv) v — never materialise the n×n matrix; O(n) per column.

Givens rotations zero one entry at a time; Householder zeros a column at a time — the workhorse of dense QR. Householder 1958

RECOMMEND FOR I-13 dot products and one sqrt

A reflection is dot products, a norm (stdlib sqrt / isqrt), and a rank-1 update — all f64, and it runs on the compiler:

$ i13 run hh.i13 # reflect x=[3,4] to the axis (v=[8,4]) Hx = [-5, 0] # below-diagonal 4 zeroed; diagonal -> -||x|| = -5
Recommend: the reflection runs — dot products (a multiply-add loop), the norm via std/bignum_isqrt’s cousin sqrt, and the rank-1 apply x − 2(vᵀx/vᵀv)v so the n×n matrix is never built (verified Hx = [−5, 0]). The wall is the matrix itself — PS-004, the 2-D array want — hand-flattened row-major idx = r*ncols + c, a third concrete case after Smith-Waterman, knapsack, Hungarian.
Note: the sign choice must be written explicitly (aim at −‖x‖); the compiler will not catch the classic instability bug — a place where the language trusts the author.