1 Definition and basic properties

A Householder transformation is an orthogonal linear map that reflects vectors across a hyperplane through the origin. In numerical linear algebra, it is used to alter selected components of a vector while preserving length and inner products. The associated matrix is called a Householder matrix.

1.1 Householder matrix

For a nonzero vector \(v\), the Householder matrix is commonly written as

\[ H = I - 2\frac{vv^T}{v^T v}. \]

Here \(I\) is the identity matrix, \(v^T\) is the transpose of \(v\), and \(vv^T\) is a rank-one matrix. The formula defines a linear transformation that depends only on the direction of \(v\), not on its scale.

1.2 Reflection interpretation

The matrix \(H\) acts as a reflection. Vectors parallel to \(v\) are reversed, while vectors orthogonal to \(v\) are unchanged. This makes the transformation especially useful for eliminating components of vectors in a controlled way.

1.3 Orthogonality and symmetry

Householder matrices are both orthogonal and symmetric. Orthogonality means \(H^T H = I\), so the transformation preserves lengths and angles. Symmetry means \(H^T = H\), which reflects the fact that the map is its own inverse.

1.4 Eigenvalues and determinant

A Householder matrix has eigenvalue \(-1\) in the direction of \(v\) and eigenvalue \(1\) on the orthogonal complement of \(v\). Thus, most directions are fixed, while one direction is reversed. Its determinant is \(-1\), consistent with the fact that it reverses orientation.

2 Construction of a Householder transformation

Householder transformations are often built to send one vector to another, typically to simplify matrix columns or rows. The construction is chosen so that the resulting reflector is numerically stable and easy to apply.

2.1 Mapping one vector to another

Given a vector \(x\), one may choose a reflector so that \(Hx\) becomes a scalar multiple of a standard basis vector. In practice, this is done to zero out all but the first component of a column. The same idea can be used to map one vector to another vector with the same norm.

2.2 Choice of reflector vector

The reflector vector is commonly selected from the difference between the target vector and the vector to be transformed. A careful choice of sign is usually made so that the formula avoids loss of precision and yields a large, stable first component in the transformed vector. This reduces sensitivity to roundoff error.

2.3 Handling numerical stability

Direct subtraction of nearly equal numbers can cause cancellation. For that reason, implementations often choose the sign of the leading component to maximize numerical separation. This helps maintain accuracy when the vector being transformed is already close to the desired direction.

3 Geometric interpretation

A Householder transformation has a simple geometric meaning: it is a mirror reflection in a hyperplane. This viewpoint explains both its orthogonality and its effect on vectors and subspaces.

3.1 Reflection across a hyperplane

The hyperplane is the set of vectors orthogonal to the reflector vector \(v\). Points on this hyperplane remain fixed, while points off the hyperplane are mirrored to the opposite side at equal distance. The transformation therefore preserves Euclidean distance exactly.

3.2 Action on vectors and subspaces

If a vector is decomposed into components parallel and orthogonal to \(v\), the parallel component changes sign and the orthogonal component stays unchanged. Any subspace contained in the reflecting hyperplane is fixed pointwise. This makes the map easy to analyze in terms of orthogonal decompositions.

3.3 Special cases in low dimensions

In two dimensions, a Householder transformation is a reflection across a line through the origin. In three dimensions, it reflects across a plane through the origin. These low-dimensional cases provide intuitive examples of the general hyperplane picture.

4 Algebraic properties

Householder transformations have several convenient algebraic features that make them attractive in exact derivations and numerical methods alike. Many of these follow directly from the matrix formula.

4.1 Inverse and transpose

Because a Householder matrix is orthogonal and symmetric, its inverse equals its transpose and both equal the matrix itself. Applying the same transformation twice returns the original vector. This involutory property is one reason the method is so efficient.

4.2 Composition of reflectors

Products of Householder matrices are also orthogonal matrices. By combining several reflectors, one can build more general orthogonal transformations. In practice, many algorithms represent a target orthogonal matrix as a product of Householder reflectors.

4.3 Relation to orthogonal matrices

Every Householder matrix is orthogonal, but not every orthogonal matrix is a Householder matrix. Householder transformations represent a special class of orthogonal maps: reflections rather than rotations. They are often preferred in computation because a single reflector can eliminate many entries at once.

5 Computational uses

Householder transformations are central tools in numerical linear algebra. Their efficiency and robustness make them useful whenever matrix structure must be simplified without sacrificing stability.

5.1 QR decomposition

A standard application is QR decomposition, where a matrix is factored into an orthogonal matrix \(Q\) and an upper triangular matrix \(R\). Householder reflectors are often used to zero out entries below the diagonal column by column.

5.1.1 Column elimination

To eliminate subdiagonal entries in a column, a reflector is constructed from the column vector below the pivot. The resulting transformation turns that portion of the column into a multiple of a basis vector. Repeating the process for each column produces an upper triangular form.

5.1.2 Full and reduced QR factorization

In the full factorization, \(Q\) is square and orthogonal, while \(R\) is upper triangular with the same shape as the input matrix. In the reduced form, only the economically relevant columns of \(Q\) are kept. Householder methods support both versions naturally.

5.2 Hessenberg reduction

For a general square matrix, Householder reflectors can reduce the matrix to Hessenberg form, where all entries below the first subdiagonal are zero. This form is easier to handle in eigenvalue computations. The reduction preserves similarity, so the eigenvalues remain unchanged.

5.3 Tridiagonalization of symmetric matrices

When the matrix is symmetric, Householder transformations can reduce it further to tridiagonal form. In that case, only the main diagonal and the first sub- and superdiagonals remain. This structure greatly accelerates many downstream algorithms, especially for symmetric eigenvalue problems.

5.4 Least squares problems

Least squares systems are often solved by first computing a QR factorization. Householder methods provide a stable way to do this without forming the normal equations. As a result, they are widely used in data fitting and regression computations.

6 Algorithmic implementation

Efficient software for Householder transformations focuses on compact storage, low memory traffic, and numerical robustness. The reflector is usually applied implicitly rather than by forming the full matrix.

6.1 Efficient storage of reflector vectors

Instead of storing a dense matrix, implementations keep only the reflector vector and a scalar coefficient. The relevant part of the vector is often stored in the matrix itself, reusing entries that are no longer needed. This compact representation reduces memory use and improves performance.

6.2 In-place matrix transformations

Householder-based algorithms commonly update matrices in place. Each reflector is applied to the remaining unreduced submatrix, and intermediate results overwrite older entries. This approach minimizes workspace and is well suited to high-performance numerical libraries.

6.3 Floating-point considerations

Because the method is used in finite precision arithmetic, attention to rounding behavior is important. Stable implementations seek to limit overflow, underflow, and cancellation while preserving the benefits of the transformation.

6.3.1 Scaling strategies

When entries are very large or very small, vectors may be rescaled before forming the reflector. Such scaling keeps intermediate values within a safe numerical range. After the transformation is computed, the scale can be incorporated back into the result.

6.3.2 Avoiding cancellation

A common source of error is subtracting nearly equal numbers when forming the reflector vector. To reduce this risk, algorithms often choose the sign of the leading term so that the subtraction is well conditioned. This simple adjustment can substantially improve accuracy.

Householder transformations are closely related to several other matrix constructions used in orthogonalization and matrix factorization. Each has different computational tradeoffs.

7.1 Householder reflector

The term Householder reflector is often used interchangeably with Householder transformation. It emphasizes the geometric meaning of the operation as a reflection. In many texts, the associated matrix is also called a reflector.

7.2 Givens rotation

A Givens rotation is another orthogonal transformation used to eliminate matrix entries. Unlike a Householder reflector, it acts on only two coordinates at a time. Givens rotations are convenient for sparse or incremental updates, while Householder reflectors are usually more efficient for dense matrices.

7.3 Gram-Schmidt orthogonalization

Gram-Schmidt orthogonalization also produces orthogonal factors, but it proceeds by projecting vectors against previously constructed basis vectors. Householder methods are generally more stable in floating-point arithmetic. For this reason, they are often preferred in high-accuracy computations.

7.4 Orthogonal similarity transformations

When a Householder matrix is used on both sides of a matrix, it produces an orthogonal similarity transformation. Such transformations preserve eigenvalues and are essential in reductions to Hessenberg or tridiagonal form. They are a major tool in matrix eigenanalysis.

8 Applications in applied mathematics

Householder transformations appear throughout applied mathematics because they simplify matrix structures while preserving key geometric properties. Their role is especially prominent in computations that depend on orthogonality.

8.1 Numerical linear algebra

In numerical linear algebra, Householder methods are a standard technique for factorization, reduction, and basis construction. They provide stable routines for solving systems, computing decompositions, and preparing matrices for iterative methods. Their reliability has made them a cornerstone of matrix software.

8.2 Eigenvalue algorithms

Many eigenvalue algorithms begin by reducing a matrix to a simpler form using Householder reflectors. Hessenberg and tridiagonal reductions shorten subsequent iterations and reduce computational cost. Because the transformations are similarity operations, they preserve the spectrum.

8.3 Scientific computing

Scientific computing frequently involves large matrices arising from discretized differential equations, optimization models, and simulation codes. Householder transformations help restructure these matrices for efficient computation. They are valued for their balance of simplicity, stability, and generality.

8.4 Signal processing and data analysis

In signal processing and data analysis, orthogonal transformations are useful for regression, filtering, and dimensionality reduction. Householder methods can support stable least squares solvers and orthogonal basis construction. They also appear in algorithms that require compact, numerically robust matrix updates.