Householder TransformationEdit

The Householder transformation is a fundamental tool in linear algebra, used to reflect vectors across hyperplanes in n-dimensional space. Named after Alston S. Householder, it provides a simple, robust way to construct orthogonal transformations that simplify matrices without distorting lengths and angles. In practical computing, these reflections underpin many widely used algorithms, especially for decomposing matrices and solving systems of equations.

At its core, a Householder transformation is a reflection across a hyperplane orthogonal to a chosen nonzero vector. If we denote the hyperplane by the set of all vectors orthogonal to a vector u, the Householder transformation H is defined by H = I − 2 (u u^T) / (u^T u), where I is the identity matrix, and u is a nonzero vector. This construction yields a matrix H that is both orthogonal (H^T H = I) and symmetric (H^T = H). Applying H to a vector x yields a new vector Hx that is the mirror image of x about the hyperplane. In particular, H leaves every vector in the hyperplane untouched in direction, while flipping the component along u.

From a mathematical standpoint, the Householder transformation has several key properties: - It is an orthogonal transformation, meaning it preserves inner products and norms: ∥Hx∥ = ∥x∥ for all x. - It is a reflection, with eigenvalues 1 on the subspace orthogonal to u (the hyperplane) and −1 in the direction of u. - Its determinant is −1, reflecting the fact that a reflection changes orientation. - It is self-adjoint, since H^T = H.

Definition and basic properties

Construction: Given a nonzero vector u, the map x ↦ Hx with H as above reflects x across the hyperplane perpendicular to u. The vector u itself is mapped to a scalar multiple of itself, specifically H u = −u.
Variants: In practice, one may choose u to achieve a desired effect on a specific vector, such as sending a given column of a matrix to a multiple of a standard basis vector. This flexibility is central to how Householder reflections are used to introduce zeros into matrices.
Relation to reflections: The transformation is a concrete realization of a geometric reflection in high-dimensional space, and it can be viewed as a special case of a broader set of reflection operators in reflection theory.

Construction and variants

A common use of the Householder construction is to zero out subdiagonal components of a column of a matrix, paving the way for a QR decomposition. Given a column x, one selects u such that Hx equals a vector with zeros below the top entry. A typical choice is to set u = x ± ∥x∥ e1, where e1 is the first standard basis vector. With this choice, Hx becomes a multiple of e1, simplifying the column reduction process.

There are several practical considerations in constructing u: - Numerical stability: The choice of sign in ∥x∥ and the exact form of u are made to avoid subtractive cancellation in floating-point arithmetic. - Bandwidth and sparsity: For sparse matrices, variants of the transformation can be employed to preserve sparsity patterns when possible, or to target specific entries for elimination. - Multiple reflections: In QR decomposition and other algorithms, a sequence of Householder reflections is applied to successive columns to transform a matrix into an upper triangular form.

Applications in numerical linear algebra

QR decomposition: Householder reflections are a standard method to factor a matrix A into A = QR, where Q is a product of Householder matrices and R is upper triangular. Each step constructs a reflection to zero out subdiagonal elements of a column, updating the matrix accordingly. See QR decomposition for a detailed treatment, and compare with alternative approaches such as Givens rotation.
Least squares problems: By reducing the coefficient matrix to an upper triangular form, Householder-based QR decomposition provides a stable and efficient route to solve least squares problems.
Eigenvalue computations and tridiagonal reduction: For symmetric matrices, a series of Householder reflections can reduce the matrix to a tridiagonal matrix form, which simplifies the computation of eigenvalues via subsequent algorithms on a simpler matrix. See symmetric matrix and eigenvalue algorithm for related topics.

Computational aspects

Storage and implementation: A single Householder reflection can be represented compactly by the vector u, avoiding the need to form the full matrix H explicitly. When multiple reflections are composed, they are typically stored as a sequence of vectors, with the overall product forming the orthogonal matrix Q.
Stability and performance: Householder transformations are known for numerical stability, a desirable property when working with floating-point arithmetic. They tend to be robust against rounding errors in comparison with some heritage approaches and work well on modern hardware.

Historical notes

The method is attributed to Alston S. Householder, who introduced the reflection as a practical device for orthogonalization in the context of matrix computations. His development significantly influenced the numerical linear algebra toolkit, establishing a reliable alternative to Gram-Schmidt-type processes in many applications.