In linear algebra, a Householder transformation (also known as Householder reflection or elementary reflector) is a linear transformation that describes a reflection about a plane or hyperplane containing the origin. The Householder transformation was introduced in 1958 by Alston Scott Householder.
Contents
- Transformation
- Householder matrix
- Properties
- Geometric optics
- Numerical linear algebra
- QR decomposition
- Tridiagonalization
- Examples
- Computational and theoretical relationship to other unitary transformations
- References
Its analogue over general inner product spaces is the Householder operator.
Transformation
The reflection hyperplane can be defined by a unit vector v (a vector with length 1) which is orthogonal to the hyperplane. The reflection of a point x about this hyperplane is the linear transformation:
where
Householder matrix
The matrix constructed from this transformation as:
is known as the Householder matrix.
Properties
The Householder matrix has the following properties:
Geometric optics
In geometric optics, specular reflection can be expressed in terms of the Householder matrix.
Numerical linear algebra
Householder transformations are widely used in numerical linear algebra, to perform QR decompositions and is the first step of the QR algorithm. They are also widely used for tridiagonalization of symmetric matrices and for transforming non-symmetric matrices to a Hessenberg form.
QR decomposition
Householder reflections can be used to calculate QR decompositions by reflecting first one column of a matrix onto a multiple of a standard basis vector, calculating the transformation matrix, multiplying it with the original matrix and then recursing down the (i, i) minors of that product.
Tridiagonalization
This procedure is taken from the book: Numerical Analysis, Burden and Faires, 8th Edition. In the first step, to form the Householder matrix in each step we need to determine
From
where
Then compute:
Having found
Continuing in this manner, the tridiagonal and symmetric matrix is formed.
Examples
This example is taken from the book "Numerical Analysis" by Richard L. Burden (Author), J. Douglas Faires. In this example, the given matrix is transformed to the similar tridiagonal matrix A2 by using the Householder method.
Following those steps in the Householder method, we have:
The first Householder matrix:
Q1
A1 = Q1AQ1 =
Used A1 to form Q2 =
A2 = Q2A1Q2=
As we can see, the final result is a tridiagonal symmetric matrix which is similar to the original one. The process is finished after two steps.
Computational and theoretical relationship to other unitary transformations
The Householder transformation is a reflection about a certain hyperplane, namely, the one with unit normal vector v, as stated earlier. An N by N unitary transformation U satisfies UUH=I. Taking the determinant (N-th power of the geometric mean) and trace (proportional to arithmetic mean) of a unitary matrix reveals that its eigenvalues λi have unit modulus. This can be seen directly and swiftly:
Since arithmetic and geometric means are equal if the variables are constant (see inequality of arithmetic and geometric means), we establish the claim of unit modulus.
For the case of real valued unitary matrixes we obtain orthogonal matrices,
The Householder transformation was shown to have a one-to-one relationship with the canonical coset decomposition of unitary matrices defined in group theory, which can be used to parametrize unitary operators in a very efficient manner.
Finally we note that a single Householder transform, unlike a solitary Givens transform, can act on all columns of a matrix, and as such exhibits the lowest computational cost for QR decomposition and tridiagonalization. The penalty for this "computational optimality" is, of course, that Householder operations cannot be as deeply or efficiently parallelized. As such Householder is preferred for dense matrices on sequential machines, whilst Givens is preferred on sparse matrices, and/or parallel machines.