Householder transformation

The reflection hyperplane can be defined by its normal vector, a unit vector ${\textstyle v}$ (a vector with length ${\textstyle 1}$) that is orthogonal to the hyperplane. The reflection of a point ${\textstyle x}$ about this hyperplane is the linear transformation:

${\displaystyle x-2\langle x,v\rangle v=x-2v\left(v^{*}x\right),}$

where ${\textstyle v}$ is given as a column unit vector with conjugate transpose ${\textstyle v^{\textsf {*}}}$.

The matrix constructed from this transformation can be expressed in terms of an outer product as:

${\displaystyle P=I-2vv^{*}}$

is known as the Householder matrix, where ${\textstyle I}$ is the identity matrix.

The Householder matrix has the following properties:

• it is Hermitian: ${\textstyle P=P^{*}}$,
• it is unitary: ${\textstyle P^{-1}=P^{*}}$,
• hence it is involutory: ${\textstyle P=P^{-1}}$.
• A Householder matrix has eigenvalues ${\textstyle \pm 1}$. To see this, notice that if ${\textstyle u}$ is orthogonal to the vector ${\textstyle v}$ which was used to create the reflector, then ${\textstyle Pu=u}$, i.e., ${\textstyle 1}$ is an eigenvalue of multiplicity ${\textstyle n-1}$, since there are ${\textstyle n-1}$ independent vectors orthogonal to ${\textstyle v}$. Also, notice ${\textstyle Pv=-v}$, and so ${\textstyle -1}$ is an eigenvalue with multiplicity ${\textstyle 1}$.
• The determinant of a Householder reflector is ${\textstyle -1}$, since the determinant of a matrix is the product of its eigenvalues, in this case one of which is ${\textstyle -1}$ with the remainder being ${\textstyle 1}$ (as in the previous point).

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. They are also widely used for transforming to a Hessenberg form. For symmetric or Hermitian matrices, the symmetry can be preserved, resulting in tridiagonalization.[3]

Householder reflections can be used to calculate QR decompositions by reflecting first one column of a matrix onto a multiple of a standard basis vector, calculating the transformation matrix, multiplying it with the original matrix and then recursing down the ${\textstyle (i,i)}$ minors of that product.

This procedure is presented in Numerical Analysis by Burden and Faires. It uses a slightly altered ${\displaystyle \operatorname {sgn} }$ function with ${\displaystyle \operatorname {sgn} (0)=1}$.[4] In the first step, to form the Householder matrix in each step we need to determine ${\textstyle \alpha }$ and ${\textstyle r}$, which are:

${\displaystyle {\begin{aligned}\alpha &=-\operatorname {sgn} \left(a_{21}\right){\sqrt {\sum _{j=2}^{n}a_{j1}^{2}}};\\r&={\sqrt {{\frac {1}{2}}\left(\alpha ^{2}-a_{21}\alpha \right)}};\end{aligned}}}$

From ${\textstyle \alpha }$ and ${\textstyle r}$, construct vector ${\textstyle v}$:

${\displaystyle v^{(1)}={\begin{bmatrix}v_{1}\\v_{2}\\\vdots \\v_{n}\end{bmatrix}},}$

where ${\textstyle v_{1}=0}$, ${\textstyle v_{2}={\frac {a_{21}-\alpha }{2r}}}$, and

${\displaystyle v_{k}={\frac {a_{k1}}{2r}}}$ for each ${\displaystyle k=3,4\ldots n}$

Then compute:

${\displaystyle {\begin{aligned}P^{1}&=I-2v^{(1)}\left(v^{(1)}\right)^{\textsf {T}}\\A^{(2)}&=P^{1}AP^{1}\end{aligned}}}$

Having found ${\textstyle P^{1}}$ and computed ${\textstyle A^{(2)}}$ the process is repeated for ${\textstyle k=2,3,\ldots ,n-2}$ as follows:

${\displaystyle {\begin{aligned}\alpha &=-\operatorname {sgn} \left(a_{k+1,k}^{k}\right){\sqrt {\sum _{j=k+1}^{n}\left(a_{jk}^{k}\right)^{2}}}\\[2pt]r&={\sqrt {{\frac {1}{2}}\left(\alpha ^{2}-a_{k+1,k}^{k}\alpha \right)}}\\[2pt]v_{1}^{k}&=v_{2}^{k}=\cdots =v_{k}^{k}=0\\[2pt]v_{k+1}^{k}&={\frac {a_{k+1,k}^{k}-\alpha }{2r}}\\v_{j}^{k}&={\frac {a_{jk}^{k}}{2r}}{\text{ for }}j=k+2,\ k+3,\ \ldots ,\ n\\P^{k}&=I-2v^{(k)}\left(v^{(k)}\right)^{\textsf {T}}\\A^{(k+1)}&=P^{k}A^{(k)}P^{k}\end{aligned}}}$

Continuing in this manner, the tridiagonal and symmetric matrix is formed.

In this example, also from Burden and Faires,[4] the given matrix is transformed to the similar tridiagonal matrix A₃ by using the Householder method.

${\displaystyle \mathbf {A} ={\begin{bmatrix}4&1&-2&2\\1&2&0&1\\-2&0&3&-2\\2&1&-2&-1\end{bmatrix}},}$

Following those steps in the Householder method, we have:

The first Householder matrix:

${\displaystyle {\begin{aligned}Q_{1}&={\begin{bmatrix}1&0&0&0\\0&-{\frac {1}{3}}&{\frac {2}{3}}&-{\frac {2}{3}}\\0&{\frac {2}{3}}&{\frac {2}{3}}&{\frac {1}{3}}\\0&-{\frac {2}{3}}&{\frac {1}{3}}&{\frac {2}{3}}\end{bmatrix}},\\A_{2}=Q_{1}AQ_{1}&={\begin{bmatrix}4&-3&0&0\\-3&{\frac {10}{3}}&1&{\frac {4}{3}}\\0&1&{\frac {5}{3}}&-{\frac {4}{3}}\\0&{\frac {4}{3}}&-{\frac {4}{3}}&-1\end{bmatrix}},\end{aligned}}}$

Used ${\textstyle A_{2}}$ to form

${\displaystyle {\begin{aligned}Q_{2}&={\begin{bmatrix}1&0&0&0\\0&1&0&0\\0&0&-{\frac {3}{5}}&-{\frac {4}{5}}\\0&0&-{\frac {4}{5}}&{\frac {3}{5}}\end{bmatrix}},\\A_{3}=Q_{2}A_{2}Q_{2}&={\begin{bmatrix}4&-3&0&0\\-3&{\frac {10}{3}}&-{\frac {5}{3}}&0\\0&-{\frac {5}{3}}&-{\frac {33}{25}}&{\frac {68}{75}}\\0&0&{\frac {68}{75}}&{\frac {149}{75}}\end{bmatrix}},\end{aligned}}}$

As we can see, the final result is a tridiagonal symmetric matrix which is similar to the original one. The process is finished after two steps.