The Householder matrix (or elementary reflector) is a unitary matrix that is often used to transform another matrix into a simpler one. In particular, Householder matrices are often used to annihilate the entries below the main diagonal of a matrix.

Table of contents

Let us start with a definition.

Definition Let be a vector. The Householder matrix associated to is the matrix defined as follows:where is the identity matrix, is the norm of , and denotes its conjugate transpose.

Let us immediately make an example, which will also help to revise norms and conjugate transposes.

Example Define the vectorThen, its conjugate transpose isand its norm isThe elementary reflector associated to is

A matrix is said to be Hermitian if it is equal to its conjugate transpose.

Proposition An Householder matrix is Hermitian, that is,

Proof

The identity matrix is equal to its conjugate transpose and Therefore, we have

Householder reflectors are unitary.

Proposition An Householder matrix is unitary, that is,

Proof

We havewhich proves that is the inverse of .

A matrix is said to be involutory if it is equal to its inverse.

Proposition An Householder matrix is involutory, that is,

Proof

We havebecause is Hermitian, and because is unitary. Therefore,

Let be a Householder matrix and a column vector. Suppose that

If we pre-multiply both sides of the equality by , we obtain

Thus, we obtainwhich is remarkably symmetric with respect to the starting equation.

We now discuss a very important reflector.

Suppose that we are given a vector and we want to transform it into another vector by using a reflector , as follows:

Further suppose that we want the vector to have all its entries equal to zero except for the first one. In other words, we want to be proportional to the first vector of the standard basis:

We can achieve the desired result by using the vectorto construct the reflector .

The scalar is the first entry of the vector and is its modulus.

For the time being, we assume that is different from zero, an assumption which we will later relax.

We will show here the calculations for the case

The other case (with the minus sign before the ratio ) is demonstrated in a solved exercise at the end of this lecture.

Note that

Let us compute the two quantities and separately.

First, since , we have

Second, since , we have

Thus, there is a considerable simplification:so that our reflection becomes

We have achieved the desired result: is proportional to the vector , with coefficient of proportionality

Note that a complex number can be written in exponential form aswhere is the argument of .

Then, the ratio that appears in the formula for can be written equivalently as

If is a non-zero real number, then

Since we assume that , how we define the function for is not relevant.

When we choose whether to use the plus or minus sign inwe usually choose the sign that makes as large as possible.

This is done to avoid division-by-zero problems when computing the reflector

Until now, we have assumed that .

When , we can build the reflector using the vector

A solved exercise at the end of this lecture shows that this choice gives the desired result.

We have discussed how to transform into a vector proportional to (the first vector of the canonical basis). If we want to transform into (the -th vector of the canonical basis), then we need to setwhere is the -th entry of . The proof is analogous to the one we have already provided.

The Householder reflector analyzed in the previous section is often used to factorize a matrix into the product of a unitary matrix and an upper triangular matrix.

The factorization algorithm, which we illustrate below in detail, is called Householder reduction.

Suppose that is a matrix and write it as a block matrixwhere is the -th column of .

As previously illustrated, we can construct a reflector that transforms the first column of into a vector proportional to :where is a scalar, is a vector of zeros, is a vector of possibly non-zero entries, and is a matrix.

We now construct a reflector that transforms the first column of into a vector having the first entry equal to and all the other entries equal to zero.

Then, we can build a matrix

The matrix , being a reflector, is unitary. The first column of has unit norm and it is orthogonal to all the other columns. Thus, is unitary.

Therefore, we havewhere is a scalar and is a matrix.

The matrix is unitary because the product of unitary matrices is unitary.

We keep on constructing smaller reflectors and unitary matrices until we obtainwhere is an upper triangular matrix.

The matrixis unitary. Thus, the factorization of into the product of a unitary and an upper triangular matrix is

The Householder matrix analyzed in this section is often used to construct algorithms for the QR decomposition that are numerically more stable than the Gram-Schmidt algorithm.

We are not going to discuss these algorithms, but we note that, in the Householder reduction process illustrated above, if is real and full-rank, then we can always choose in which case all the diagonal entries of are strictly positive, and the factorizationmust be the QR decomposition (because the QR decomposition is the unique factorization of a full-rank matrix into a unitary matrix and an upper triangular matrix with strictly positive diagonal entries).

Below you can find some exercises with explained solutions.

Find what happens when the vectoris used to construct the Householder matrix.

Solution

First, we have

Second, we have

Thus, we have the simplificationand the reflection becomes

Find what happens when and the vectoris used to construct the Householder matrix.

Solution

First, we have

Second, we have

Thus, we have the simplificationand the reflection becomes

Please cite as:

Taboga, Marco (2017). "Householder matrix", Lectures on matrix algebra. https://www.statlect.com/matrix-algebra/Householder-matrix.

The book

Most of the learning materials found on this website are now available in a traditional textbook format.

Featured pages

- Score test
- Gamma function
- Set estimation
- Point estimation
- Maximum likelihood
- Characteristic function

Explore

Main sections

- Mathematical tools
- Fundamentals of probability
- Probability distributions
- Asymptotic theory
- Fundamentals of statistics
- Glossary

About

Glossary entries

Share