A Householder transformation of a vector is its reflection with
respect a plane (or hyper-plane) through the origin represented by its normal
vector of unit length
, which can
be found as

where is the projection of onto . In general, the projection of onto any vector is

The reflection of can be considered as a linear transformation represented by a matrix applied to :

where is a

Obviously is symmetric

and it is also the inverse of its own:

We therefore have

i.e., is an orthogonal matrix (satisfying ).

As any vector can be normalized
to
have a unit norm, the Householder matrix defined above can be written as:

We define specifically a vector

where is any N-D vector and is the first standard basis vector with all elements equals zero except the first one. The norm squared of this vector can be found to be

When the Householder matrix based on this particular vector is applied to the vector itself, it produces its reflection

We see that all elements in except the first one are eliminated to zero. This feature of the Householder transformation is the reason why it is widely used.

The Householder transformation finds many applications in numerical computation.
For example, it can be used to convert a given matrix into either a
bidiagonal or tridiagonal form, which is needed in the algorithms for solving SVD
and eigenvalue problems. The Householder transformation can also be used to carry
out
QR decomposition
of an by square matrix :

where is an orthogonal matrix and is an upper triangular matrix. Specifically, we first construct a Householder matrix based on the first column vector of , i.e., , by which the last elements of the first column of will become zero:

We then construct second transformation matrix

where is an ()-dimensional Householder matrix constructed based on the first column of , to zero the last elements of this column:

This process is repeated with the kth transformation matrix

where is an ()-dimensional Householder matrix constructed based on the first column of the sub-matrix of the same dimension obtained from the previous step.

After such iterations becomes an upper triangular matrix:

Pre-multiplying on both sides we get QR decomposition of :

Here satisfies

i.e., is orthogonal and so is .

QR decomposition is widely used in different algorithms (e.g., SVD, eigenvalue
problems, etc.), and it can also be used to solve the linear system
:

where can be obtained as:

Then we can find by solving

As is an upper triangular matrix, can be obtained by back-substitution.

The Householder transformation can also be used to carry out tridiagonalization
of an by matrix . Specifically we first define an
matrix as shown below:

where the lower-right part of is an dimensional Householder matrix based on an dimensional vector containing the last elements of the first column of . We first pre-multiply to to get:

where is an dimensional matrix containing the lower-right by elements of , and the lower-left block of the resulting matrix only has a non-zero element as the result of the application of the Householder matrix. We next post-multiply to the result above to get

We next multiply both sides of the above by

to get

This process is recursively repeated until after iterations the by matrix is converted into a tridiagonal matrix.