Lecture
The Householder transformation (Householder operator) is a linear transformation 
of a vector space 
that describes its reflection with respect to a hyperplane passing through the origin.
It was used in a 1958 paper by the American mathematician Alston Scott Householder.
It is widely used in linear algebra for the QR decomposition of a matrix.
Let the hyperplane be described by a unit vector 
orthogonal to it, and let 
be the scalar product in , then
is called the Householder operator.
The Householder matrix has the form:
In the Russian-language literature it is also called the reflection matrix.
.
, corresponding to the eigenvector ; all its other eigenvalues equal 
..
In geometric optics, specular reflection can be expressed in terms of the Householder matrix (see “ Specular reflection” § Vector formulation ).
Householder transformations are widely used in numerical linear algebra, for example, to annihilate the entries below the main diagonal of a matrix, to carry out QR decomposition, and at the first stage of the QR algorithm. They are also widely used to convert a matrix to Hessenberg form. For symmetric or Hermitian matrices, symmetry can be preserved, which leads to tridiagonalization.
Householder reflections can be used to compute the QR decomposition by reflecting the first column of the matrix onto a multiple of the standard basis vector, computing the transformation matrix, multiplying it by the original matrix, and then recursively examining
the minors of that product.
This procedure is presented in “Numerical Analysis by Burden and Faires”. At the first step, in order to form the Householder matrix at each stage, we need to determine
and 
, which are:
From and , construct the vector 
:
where 
, 
, and
for each 
Then compute:
Having found 
and computed 
the process is repeated for 
as follows:
Continuing in this way, a tridiagonal, symmetric matrix is formed.
In this example, also taken from Burden and Faires , the given matrix is transformed into a similar tridiagonal matrix A 3 using the Householder method.
Following these steps in the Householder method, we obtain:
The first Householder matrix:
Used 
to form
As we can see, the final result is a tridiagonal symmetric matrix similar to the original. The process terminates after two steps.
The Householder transformation is a reflection in a hyperplane with unit normal vector , as stated earlier. An 
-by- unitary transformation 
satisfies 
. Taking the determinant (the -th power of the geometric mean) and the trace (proportional to the arithmetic mean) of a unitary matrix shows that its eigenvalues 
have unit modulus. This can be seen directly and quickly:
Since the arithmetic and geometric means are equal only when the variables are constant (see the Inequality of arithmetic and geometric means), we establish the requirement of unit modulus.
For the case of real-valued unitary matrices, we obtain orthogonal matrices: 
. From this it follows fairly easily (see Orthogonal matrix) that any orthogonal matrix can be decomposed into a product of 2-by-2 rotations, called Givens rotations, and Householder reflections. This is intuitively appealing, since multiplying a vector by an orthogonal matrix preserves the length of that vector, and rotations and reflections exhaust the set of (real) geometric operations that leave a vector's length unchanged.
It has been shown that the Householder transformation bears a one-to-one relationship to the canonical coset decomposition of unitary matrices defined in group theory, which can be used for a very efficient parameterization of unitary operators.
Finally, note that a single Householder transformation, unlike an individual Givens transformation, can act on all the columns of a matrix at once and, as such, exhibits the lowest computational cost for QR decomposition and tridiagonalization. The price of this “computational optimality” is, of course, that Householder operations cannot be parallelized as deeply or as efficiently. Thus Householder is preferable for dense matrices on sequential machines, while Givens is preferable for sparse matrices and/or parallel machines.
Comments