Inlinear algebra, aHouseholder transformation (also known as aHouseholder reflection orelementary reflector) is alinear transformation that describes areflection about aplane orhyperplane containing the origin. The Householder transformation was used in a 1958 paper byAlston Scott Householder.^[1]

TheHouseholderoperator^[2] may be defined over any finite-dimensionalinner product space${\displaystyle V}$ withinner product${\displaystyle ⟨\cdot ,\cdot ⟩}$ andunit vector${\displaystyle u\in V}$ as

${\displaystyle H_u(x):=x-2⟨x,u⟩u.}$^[3]

It is also common to choose a non-unit vector${\displaystyle q\in V}$, and normalize it directly in the Householder operator's expression:^[4]

${\displaystyle H_q\left(x\right)=x-2\frac{⟨x,q⟩}{⟨q,q⟩}q.}$

Such an operator islinear andself-adjoint.

If${\displaystyle V={\mathbb{C}}^n}$, note that the reflection hyperplane can be defined by itsnormal vector, aunit vector$\overrightarrow{v}\in V$ (a vector with length$1$) that isorthogonal to the hyperplane. The reflection of apoint$x$ about this hyperplane is theHouseholdertransformation:

${\displaystyle \overrightarrow{x}-2⟨\overrightarrow{x},\overrightarrow{v}⟩\overrightarrow{v}=\overrightarrow{x}-2\overrightarrow{v}\left({\overrightarrow{v}}^{\ast }\overrightarrow{x}\right),}$

where${\displaystyle \overrightarrow{x}}$ is the vector from the origin to the point${\displaystyle x}$, and${\overrightarrow{v}}^{\ast }$ is theconjugate transpose of$\overrightarrow{v}$.

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

${\displaystyle P=I-2\overrightarrow{v}{\overrightarrow{v}}^{\ast }}$

is known as theHouseholder matrix, where$I$ is theidentity matrix.

The Householder matrix has the following properties:

• it isHermitian:$P=P^{\ast }$,
• it isunitary:$P^{-1}=P^{\ast }$ (via theSherman-Morrison formula),
• hence it isinvolutory:$P=P^{-1}$.
• A Householder matrix has eigenvalues$\pm 1$. To see this, notice that if$\overrightarrow{x}$ is orthogonal to the vector$\overrightarrow{v}$ which was used to create the reflector, then$P_v\overrightarrow{x}=(I-2\overrightarrow{v}{\overrightarrow{v}}^{\ast })\overrightarrow{x}=\overrightarrow{x}-2⟨\overrightarrow{v},\overrightarrow{x}⟩\overrightarrow{v}=\overrightarrow{x}$, i.e.,$1$ is an eigenvalue of multiplicity$n-1$, since there are$n-1$ independent vectors orthogonal to$\overrightarrow{v}$. Also, notice$P_v\overrightarrow{v}=(I-2\overrightarrow{v}{\overrightarrow{v}}^{\ast })\overrightarrow{v}=\overrightarrow{v}-2⟨\overrightarrow{v},\overrightarrow{v}⟩\overrightarrow{v}=-\overrightarrow{v}$ (since${\displaystyle \overrightarrow{v}}$ is by definition a unit vector), and so$-1$ is an eigenvalue with multiplicity$1$.
• Thedeterminant of a Householder reflector is$-1$, since the determinant of a matrix is the product of its eigenvalues, in this case one of which is$-1$ with the remainder being$1$ (as in the previous point), or via theMatrix determinant lemma.

consider the normalization of a vector of 1's

${\displaystyle \overrightarrow{v}=\frac{1}{\sqrt{2}}\left[\begin{array}{c}1\\ 1\end{array}\right]}$

Then the Householder matrix corresponding to this vector is

Note that if we have a vector representing a coordinate in the 2D plane

${\displaystyle \left[\begin{array}{c}x\\ y\end{array}\right]}$

Then in this case${\displaystyle P_v}$ flips and negates the x and y coordinates, in other words

${\displaystyle P_v\left[\begin{array}{c}x\\ y\end{array}\right]=\left[\begin{array}{c}-y\\ -x\end{array}\right]}$

Which corresponds to reflecting the vector across the line${\displaystyle y=-x}$, which our original vector${\displaystyle v}$ is normal to.

In geometric optics,specular reflection can be expressed in terms of the Householder matrix (seeSpecular reflection § Vector formulation).

Householder transformations are widely used innumerical linear algebra, for example, to annihilate the entries below the main diagonal of a matrix,^[5] to performQR decompositions and in the first step of theQR algorithm. They are also widely used for transforming to aHessenberg form. For symmetric orHermitian matrices, the symmetry can be preserved, resulting intridiagonalization.^[6] Because they involve only a rank-one update and make use of low-levelBLAS-1 operations, they can be quite efficient.

Householder transformations can be used to calculate aQR decomposition. Consider a matrix tridiangularized up to column${\displaystyle i}$, then our goal is to construct such Householder matrices that act upon the principal submatrices of a given matrix

via the matrix

.

(note that we already established before that Householder transformations are unitary matrices, and since the multiplication of unitary matrices is itself a unitary matrix, this gives us the unitary matrix of the QR decomposition)

If we can find a${\displaystyle \overrightarrow{v}}$ so that

${\displaystyle P_v\overrightarrow{x}={\overrightarrow{e}}_1}$

we could accomplish this. Thinking geometrically, we are looking for a plane so that the reflection about this plane happens to land directly on the basis vector. In other words,

${\displaystyle \overrightarrow{x}-2⟨\overrightarrow{x},\overrightarrow{v}⟩\overrightarrow{v}=\alpha {\overrightarrow{e}}_1}$

1

for some constant${\displaystyle \alpha }$. However, for this to happen, we must have

${\displaystyle \overrightarrow{v}\propto \overrightarrow{x}-\alpha {\overrightarrow{e}}_1}$.

And since${\displaystyle \overrightarrow{v}}$ is a unit vector, this means that we must have

${\displaystyle \overrightarrow{v}=\pm \frac{\overrightarrow{x}-\alpha {\overrightarrow{e}}_1}{\Vert \overrightarrow{x}-\alpha {\overrightarrow{e}}_1{\Vert }_2}}$

2

Now if we apply equation (2) back into equation (1), we get

$${\displaystyle \overrightarrow{x}-\alpha {\overrightarrow{e}}_1=2(⟨\overrightarrow{x},\frac{\overrightarrow{x}-\alpha {\overrightarrow{e}}_1}{\Vert \overrightarrow{x}-\alpha {\overrightarrow{e}}_1{\Vert }_2}⟩\frac{\overrightarrow{x}-\alpha {\overrightarrow{e}}_1}{\Vert \overrightarrow{x}-\alpha {\overrightarrow{e}}_1{\Vert }_2}}$$

Or, in other words, by comparing the scalars in front of the vector${\displaystyle \overrightarrow{x}-\alpha {\overrightarrow{e}}_1}$ we must have

${\displaystyle \Vert \overrightarrow{x}-\alpha {\overrightarrow{e}}_1{\Vert }_2^2=2⟨\overrightarrow{x},\overrightarrow{x}-\alpha e_1⟩}$.

Or

${\displaystyle 2(\Vert \overrightarrow{x}{\Vert }_2^2-\alpha x_1)=\Vert \overrightarrow{x}{\Vert }_2^2-2\alpha x_1+{\alpha }^2}$

Which means that we can solve for${\displaystyle \alpha }$ as

${\displaystyle \alpha =\pm \Vert \overrightarrow{x}{\Vert }_2}$

This completes the construction; however, in practice we want to avoidcatastrophic cancellation in equation (2). To do so, we choose the sign of${\displaystyle \alpha }$ as

${\displaystyle \alpha =-sign(Re(x_1))\Vert \overrightarrow{x}{\Vert }_2}$^[7]

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.

It uses a slightly altered${\displaystyle \mathrm{sgn}}$ function with${\displaystyle \mathrm{sgn}(0)=1}$.^[8]In the first step, to form the Householder matrix in each step we need to determine$\alpha$ and$r$, which are:

From$\alpha$ and$r$, construct vector$v$:

${\displaystyle {\overrightarrow{v}}^{(1)}=\left[\begin{array}{c}{v}_1\\ v_2\\ ⋮\\ v_n\end{array}\right],}$

where$v_1=0$,$v_2=\frac{a_{21}-\alpha }{2r}$, and

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

Then compute:

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

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

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

Following those steps in the Householder method, we have:

The first Householder matrix:

Used$A_2$ to form

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.

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 anoracle function represented by what turns out to be a Householder transformation:

(here the${\displaystyle |x⟩}$ is part of thebra-ket notation and is analogous to${\displaystyle \overrightarrow{x}}$ which we were using previously)

This is done via an algorithm that iterates via the oracle function${\displaystyle U_{\omega }}$ and another operator${\displaystyle U_s}$ known as theGrover diffusion operator defined by

${\displaystyle |s⟩=\frac{1}{\sqrt{N}}\sum _{x=0}^{N-1}|x⟩.}$and${\displaystyle U_s=2|s⟩⟨s|-I}$.

The Householder transformation is a reflection about a hyperplane with unit normal vector$v$, as stated earlier. An$N$-by-$N$unitary transformation$U$ satisfies$U{U}^{\ast }=I$. Taking the determinant ($N$-th power of the geometric mean) and trace (proportional to arithmetic mean) of a unitary matrix reveals that its eigenvalues${\lambda }_i$ have unit modulus. This can be seen directly and swiftly:

Since arithmetic and geometric means are equal if the variables are constant (seeinequality of arithmetic and geometric means), we establish the claim of unit modulus.

For the case of real valued unitary matrices we obtainorthogonal matrices,$U{U}^{\mathsf{\text{T}}}=I$. It follows rather readily (seeOrthogonal matrix) that any orthogonal matrix can bedecomposed into a product of 2-by-2 rotations, calledGivens 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.^[9]

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.

• Block reflector
• Givens rotation
• Jacobi rotation

• LaBudde, C.D. (1963). "The reduction of an arbitrary real square matrix to tridiagonal form using similarity transformations".Mathematics of Computation.17 (84). American Mathematical Society:433–437.doi:10.2307/2004005.JSTOR 2004005.MR 0156455.
• Morrison, D.D. (1960)."Remarks on the Unitary Triangularization of a Nonsymmetric Matrix".Journal of the ACM.7 (2):185–186.doi:10.1145/321021.321030.MR 0114291.S2CID 23361868.
• Cipra, Barry A. (2000)."The Best of the 20th Century: Editors Name Top 10 Algorithms".SIAM News.33 (4): 1. (Herein Householder Transformation is cited as a top 10 algorithm of this century)
• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007)."Section 11.3.2. Householder Method".Numerical Recipes: The Art of Scientific Computing (3rd ed.). New York: Cambridge University Press.ISBN 978-0-521-88068-8. Archived fromthe original on 2011-08-11. Retrieved2011-08-13.
• Roman, Stephen (2008),Advanced Linear Algebra,Graduate Texts in Mathematics (Third ed.), Springer,ISBN 978-0-387-72828-5

• Transformation (function)
• Matrices (mathematics)
• Numerical linear algebra

• Articles with short description
• Short description is different from Wikidata