Householder transformation
In linear algebra, a Householder transformation (also known as a Householder reflection or elementary reflector) is a linear transformation that describes a reflection about a plane or hyperplane containing the origin.
[1] Its analogue over general inner product spaces is the Householder operator.
is given as a column unit vector with conjugate transpose
The Householder matrix has the following properties: consider the normalization of a vector of 1's
Note that if we have a vector representing a coordinate in the 2D plane
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,[2] to perform QR decompositions and in the first step of the QR algorithm.
For symmetric or Hermitian matrices, the symmetry can be preserved, resulting in tridiagonalization.
[3] Householder transformations can be used to calculate a QR decomposition.
, then our goal is to construct such Householder matrices that act upon the principal submatrices of a given matrix
Thinking geometrically speaking, we are looking for a plane so that the reflection of
about the plane happens to land directly on the basis vector.
Or, in other words, by comparing the scalars in front of the vector
This completes the construction; however, in practice we want to avoid catastrophic cancellation in equation (2).
[4] This procedure is presented in Numerical Analysis by Burden and Faires, and works when the matrix is symmetric.
In the non-symmetric case, it is still useful as a similar procedure can result in a Hessenberg matrix.
as follows: Continuing in this manner, the tridiagonal and symmetric matrix is formed.
to form As we can see, the final result is a tridiagonal symmetric matrix which is similar to the original one.
As unitary matrices are useful in quantum computation, and Householder transformations are unitary, they are very useful in quantum computing.
One of the central algorithms where they're useful is Grover's algorithm, where we are trying to solve for a representation of an oracle function represented by what turns out to be a Householder transformation:
which we were using previously) This is done via an algorithm that iterates via the oracle function
The Householder transformation is a reflection about a hyperplane with unit normal vector
-th power of the geometric mean) and trace (proportional to arithmetic mean) of a unitary matrix reveals that its eigenvalues
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.
It follows rather readily (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 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 (real valued) 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.
[6] 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.
