Search for probability and statistics terms on Statlect
StatLect
Index > Matrix algebra

Householder matrix

by , PhD

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

Definition

Let us start with a definition.

Definition Let $v$ be a Kx1 vector. The Householder matrix associated to $v$ is the $K imes K$ matrix $R$ defined as follows:[eq1]where I is the $K imes K$ identity matrix, [eq2] is the norm of $v$, and $v^{st }$ denotes its conjugate transpose.

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

Example Define the $2 imes 1$ vector[eq3]Then, its conjugate transpose is[eq4]and its norm is[eq5]The elementary reflector associated to $v$ is[eq6]

Hermitian

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

Proposition An Householder matrix $R$ is Hermitian, that is,[eq7]

Proof

The identity matrix is equal to its conjugate transpose and [eq8]Therefore, we have [eq9]

Unitary

Householder reflectors are unitary.

Proposition An Householder matrix $R$ is unitary, that is,[eq10]

Proof

We have[eq11]which proves that $R^{st }$ is the inverse of $R$.

Involutory

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

Proposition An Householder matrix $R$ is involutory, that is,[eq12]

Proof

We have[eq13]because $R$ is Hermitian, and [eq14]because $R$ is unitary. Therefore,[eq15]

A curious property

Let $R$ be a $K imes K$ Householder matrix and x a Kx1 column vector. Suppose that[eq16]

If we pre-multiply both sides of the equality by $R$, we obtain[eq17]

Thus, we obtain[eq18]which is remarkably symmetric with respect to the starting equation.

An incredibly useful reflector

We now discuss a very important reflector.

Aim

Suppose that we are given a Kx1 vector x and we want to transform it into another vector $y$ by using a reflector $R$, as follows:[eq19]

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

How the aim is achieved

We can achieve the desired result by using the vector[eq21]to construct the reflector $R$.

The scalar $x_{1}$ is the first entry of the vector x and [eq22]is its modulus.

For the time being, we assume that $x_{1}$ is different from zero, an assumption which we will later relax.

Proof

We will show here the calculations for the case[eq23]

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

Note that[eq25]

Let us compute the two quantities $2v^{st }x$ and $v^{st }v$ separately.

First, since [eq26], we have[eq27]

Second, since [eq28], we have[eq29]

Thus, there is a considerable simplification:[eq30]so that our reflection becomes[eq31]

We have achieved the desired result: $y=Rx$ is proportional to the vector $e_{1}$, with coefficient of proportionality[eq32]

Comment on complex numbers

Note that a complex number $x_{1}$ can be written in exponential form as[eq33]where [eq34] is the argument of $x_{1}$.

Then, the ratio that appears in the formula for $v$ can be written equivalently as[eq35]

The real case

If $x_{1}$ is a non-zero real number, then[eq36]

Since we assume that $x_{1} eq 0$, how we define the function [eq37] for $x_{1}=0$ is not relevant.

Comment on the choice of sign

When we choose whether to use the plus or minus sign in[eq21]we usually choose the sign that makes [eq39] as large as possible.

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

The zero case

Until now, we have assumed that $x_{1} eq 0$.

When $x_{1}=0$, we can build the reflector using the vector[eq41]

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

Other vectors of the canonical basis

We have discussed how to transform x into a vector proportional to $e_{1}$ (the first vector of the canonical basis). If we want to transform x into $e_{k}$ (the k-th vector of the canonical basis), then we need to set[eq42]where $x_{k}$ is the k-th entry of x. The proof is analogous to the one we have already provided.

Householder reduction

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 A is a $K imes K$ matrix and write it as a block matrix[eq43]where $A_{ullet k}$ is the k-th column of A.

First step

As previously illustrated, we can construct a $K imes K$ reflector $R_{1}$ that transforms the first column of A into a vector proportional to $e_{1}$:[eq44]where $lpha _{1}$ is a scalar, 0 is a [eq45] vector of zeros, $st $ is a [eq46] vector of possibly non-zero entries, and $B$ is a [eq47] matrix.

Second step

We now construct a [eq48] reflector $R_{2}$ that transforms the first column of $B$ into a vector having the first entry equal to 1 and all the other entries equal to zero.

Then, we can build a $K imes K$ matrix[eq49]

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

Therefore, we have[eq50]where $lpha _{2}$ is a scalar and $C$ is a [eq51] matrix.

The matrix $S_{2}R_{1}$ is unitary because the product of unitary matrices is unitary.

Successive steps

We keep on constructing smaller reflectors $R_{k}$ and unitary matrices $S_{k}$ until we obtain[eq52]where $T$ is an upper triangular matrix.

The matrix[eq53]is unitary. Thus, the factorization of A into the product of a unitary and an upper triangular matrix is[eq54]

Householder reduction and QR decomposition

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 A is real and full-rank, then we can always choose [eq55]in which case all the diagonal entries of $T$ are strictly positive, and the factorization[eq56]must 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).

Solved exercises

Below you can find some exercises with explained solutions.

Exercise 1

Find what happens when the vector[eq57]is used to construct the Householder matrix.

Solution

First, we have[eq58]

Second, we have[eq59]

Thus, we have the simplification[eq30]and the reflection becomes[eq61]

Exercise 2

Find what happens when $x_{1}=0$ and the vector[eq62]is used to construct the Householder matrix.

Solution

First, we have[eq63]

Second, we have[eq64]

Thus, we have the simplification[eq30]and the reflection becomes[eq66]

How to cite

Please cite as:

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

The books

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

Featured pages
Explore
Main sections
About
Glossary entries
Share
  • To enhance your privacy,
  • we removed the social buttons,
  • but don't forget to share.