Householder reflection

A Householder reflection is a mirror. Pick a unit vector v defining a hyperplane (the plane perpendicular to v), and the transformation H = I - 2 v v^T reflects every vector across that hyperplane. Geometrically it is the cleanest possible orthogonal map other than the identity: it flips the component along v and leaves everything in the plane untouched.

Its power for factorization is that you can choose the mirror to do exactly one useful job: take a given column vector x and reflect it onto a coordinate axis, so that the result is (+/- ||x||, 0, 0, ..., 0). One well-chosen reflection zeros every entry of a column below the pivot at a single stroke. Apply n-1 of these, one per column, and you have driven A to upper triangular form, which is exactly the R of a QR factorization.

Because H is symmetric and orthogonal (H = H^T, H H = I, so H = H^-1), it preserves all lengths and angles, and applying it does not amplify rounding error. That is why Householder QR is backward stable, in sharp contrast to Gram-Schmidt. You never form the full H matrix; you store only v and apply H x = x - 2 v (v^T x), which costs order n per column.

One careful detail: to avoid catastrophic cancellation when x already nearly points along the target axis, you choose the reflection that maps x to -sign(x1) ||x|| e1, sending it to the far axis direction rather than the near one. This sign choice is what makes the algorithm robust.