Householder Reflection

Householder Reflections

Concept Overview

A Householder reflection is a linear transformation that reflects a vector across a specific hyperplane. Geometrically, if you think of the hyperplane as a mirror, the Householder reflection maps any point to its mirror image on the other side. This operation is defined by a Householder matrix, which is both orthogonal and symmetric. These properties make Householder transformations extremely stable and efficient for numerical computations.

Mathematical Definition

Given a non-zero normal vector v, we first normalize it to obtain a unit vector u = v / ||v||. The Householder matrix H corresponding to the hyperplane orthogonal to u is defined as:

H = I - 2uu^T

Or, in terms of the original vector v:

H = I - 2(vv^T) / (v^Tv)

When applied to a vector x, the reflection is computed as:

Hx = x - 2(u^Tx)u

Key Concepts

Properties of Householder Matrices

Symmetric: H = H^T
Orthogonal: H^-1 = H^T = H. Since H is its own inverse, applying the reflection twice brings the vector back to its original position (H² = I).
Determinant: det(H) = -1, indicating that it reverses orientation.
Eigenvalues: H has one eigenvalue of -1 (corresponding to the normal vector u) and n-1 eigenvalues of 1 (corresponding to vectors lying on the hyperplane).

Historical Context

The concept was introduced by Alston Scott Householder in 1958. Householder reflections revolutionized numerical linear algebra by providing a highly stable method for computing the QR decomposition of matrices, outperforming older methods like the Gram-Schmidt process in terms of numerical precision on finite-precision machines.

Real-world Applications

QR Decomposition: Used extensively to factorize matrices into orthogonal (Q) and upper triangular (R) components for solving linear systems and eigenvalue problems.
Least Squares Solutions: Enhances numerical stability when solving overdetermined systems compared to forming the normal equations.
Tridiagonalization: Householder reflections are used to reduce symmetric matrices to tridiagonal form, a crucial precursor step in computing eigenvalues efficiently.

Related Concepts

QR Decomposition — Often computed using a series of Householder reflections.
Gram-Schmidt Process — An alternative, but less numerically stable, method for orthogonalization.
Linear Transformations — Householder reflection is a foundational example of a linear map.
Eigenvalues and Eigenvectors — Understanding the invariant subspaces of the reflection matrix.

Householder Reflection