GraphMath

Householder reflection

QR factorization by hyperplane reflections

How can one reflection zero all entries below a pivot?

Householder QR uses orthogonal reflection matrices H₁, …, Hₙ₋₁ to transform A into an upper triangular matrix R. At each step, a reflector leaves previous coordinates unchanged and sends the active column into the coordinate span needed for triangular form. The accumulated reflections give A = QR.

Open chapter PDF Key ideas Chapter index Back to Linear Algebra

Key ideas

A Householder step is a reflection chosen to move one column into triangular position.

  • At step i, Hᵢ acts as identity on the first i−1 coordinates, so previously finished columns stay unchanged
  • The target vector aᵢ′ keeps the first i−1 entries and has zeros below entry i
  • The sign of the i-th target entry is usually chosen opposite to the current i-th entry to use a longer reflector vector and reduce numerical error
  • A reflector fixes one subspace S and negates the one-dimensional orthogonal direction S⊥ = span(v)
  • The reflector can be computed from v by H = I − 2vvᵀ / (vᵀv)
  • After all Householder steps, Hₙ₋₁ … H₁ A = R, so A = QR with Q = (Hₙ₋₁ … H₁)ᵀ

Compared with Givens rotations, which eliminate entries by coordinate-plane rotations, Householder reflections use hyperplane reflections to move a whole column into place at once.

What is the geometric action of a Householder reflector?

It splits every vector into a fixed component in S and a perpendicular component in S⊥. The fixed component stays the same and the perpendicular component changes sign. Choosing S⊥ = span(aᵢ′ − aᵢ) makes the reflection send the active column aᵢ to the target column aᵢ′.

Related chapters

  • QRF, Gram-Schmidt, part 1 introduces QR factorization, orthonormal columns and the projection viewpoint behind Q
  • QRF, Gram-Schmidt, part 2 develops the structure of R and geometric views of A = QR
  • QRF, Gram-Schmidt, part 3 gives the stepwise Gram-Schmidt route to QR, useful for comparing with the Householder route
  • Givens rotations gives the rotation-based QR route that the PDF compares directly with Householder reflection
  • QRF & equations shows how the triangular factor R is used to solve consistent and inconsistent systems
  • Projection supplies the projection matrix idea behind the reflector formula H = I − 2P

Examples with visualizations

Householder reflection visualized

Animated reflection that aligns a column with a coordinate direction in QR factorization

Animated geometric visualization of Householder reflection in QR factorization
Open visual page Open in PDF

Three geometric routes to QR

Gram-Schmidt, Givens rotations and Householder reflections compared on the same matrix

Thumbnail comparing three geometric routes to QR factorization
Open visual page Open in PDF

Chapter contents

The PDF is a single document. The page links below are best-effort: most browsers support them, but some viewers may ignore the page hint.

Topic Pages
Algorithm endpoint 1–4
Reflector matrix Hᵢ: reflection across fixed subspace S in ℝⁿ 5–7
Summary 8
Three geometric routes to QR decomposition 9–10
Comparison of QR factorization algorithms 10–11
Open PDF

Why use Householder reflections for QR?

Each Householder step is orthogonal, so it preserves lengths and angles while moving the active column into triangular position. It is stable and efficient for dense matrices, because one reflection can eliminate several lower entries of a column in a single step.

Was this chapter helpful?

Quick feedback helps us improve the site.

Yes No