The reflection hyperplane can be defined by a unit vector that is orthogonal to the hyperplane. The reflection of a point about this hyperplane is the linear transformation: where is given as a column unit vector with Hermitian transpose.
Householder matrix
The matrix constructed from this transformation can be expressed in terms of an outer product as: is known as the Householder matrix, where is the identity matrix
Properties
The Householder matrix has the following properties:
it is Hermitian:,
it is unitary:,
hence it is involutory:.
A Householder matrix has eigenvalues. To see this, notice that if is orthogonal to the vector which was used to create the reflector, then, i.e., is an eigenvalue of multiplicity, since there are independent vectors orthogonal to. Also, notice, and so is an eigenvalue with multiplicity.
The determinant of a Householder reflector is, since the determinant of a matrix is the product of its eigenvalues, in this case one of which is with the remainder being .
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 transforming to a Hessenberg form. For symmetric or Hermitian matrices, the symmetry can be preserved, resulting in tridiagonalization.
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 minors of that product.
Tridiagonalization
This procedure is presented in Numerical Analysis by Burden and Faires. In the first step, to form the Householder matrix in each step we need to determine and, which are: From and, construct vector : where,, and Then compute: Having found and computed the process is repeated for as follows: Continuing in this manner, the tridiagonal and symmetric matrix is formed.
Examples
In this example, also from Burdern and Faires, the given matrix is transformed to the similar tridiagonal matrix A3 by using the Householder method. Following those steps in the Householder method, we have: The first Householder matrix: Used to form 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 hyperplane with unit normal vector, as stated earlier. An -by- unitary transformation satisfies. Taking the determinant and trace of a unitary matrix reveals that its eigenvalues have unit modulus. This can be seen directly and swiftly: Since arithmetic and geometric means are equal if the variables are constant, we establish the claim of unit modulus. For the case of real valued unitary matrices we obtain orthogonal matrices,. It follows rather readily that any orthogonal matrix can be decomposed into a product of 2 by 2 rotations, called Givens Rotations, and Householder reflections. This is appealing intuitively since multiplication of a vector by an orthogonal matrix preserves the length of that vector, and rotations and reflections exhaust the set of geometric operations that render invariant a vector's length. 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.
