Householder Transformation

A Householder transformation is a linear map that reflects vectors across a hyperplane through the origin. In real Euclidean space, it is represented by a symmetric orthogonal matrix differing from the identity by a rank-one matrix. Its principal computational use is to eliminate selected components of a vector while preserving lengths, making it a fundamental tool in numerical linear algebra, especially for QR decomposition and reductions preceding eigenvalue and singular-value computations. The transformation is named after Alston S. Householder, whose 1958 paper described its use in matrix triangularization. (web.stanford.edu)

Definition and geometric interpretation

For a nonzero vector $v\in\mathbb{R}^n$ , the Householder matrix is

H=I-2\frac{vv^T}{v^Tv},

where $I$ is the identity matrix and $v^T$ denotes the transpose of $v$ . Equivalently, with the unit vector $u=v/\|v\|_2$ ,

H=I-2uu^T.

This is the real reflection form of the elementary-reflector representation used in matrix algorithms. (web.stanford.edu)

The geometry follows directly from the formula. Decompose any vector $x$ as

x=x_\perp+x_\parallel, \qquad x_\parallel=u(u^Tx), \qquad u^Tx_\perp=0.

Then

Hx=x_\perp-x_\parallel.

Thus, $H$ reverses the component parallel to $v$ and leaves its orthogonal complement unchanged. The fixed hyperplane is $v^\perp=\{x:v^Tx=0\}$ . In terms of orthogonal projection, $H=I-2P$ , where $P=uu^T$ projects onto the line spanned by $v$ . (web.stanford.edu)

Algebraic properties

Direct calculation gives

H^T=H, \qquad H^2=I, \qquad H^TH=I.

Consequently, the transformation is symmetric, orthogonal, and its own inverse. Orthogonality implies preservation of the inner product:

(Hx)^T(Hy)=x^Ty.

It therefore preserves the Euclidean norm, angles, and distances. These identities explain why reflections are useful for transforming numerical problems without amplifying errors simply through the transformation itself. (web.stanford.edu)

Further consequences of the defining formula include:

$Hv=-v$ , so $v$ is an eigenvector with eigenvalue $-1$ .
Every vector perpendicular to $v$ has eigenvalue $+1$ .
The determinant is $-1$ .
$I-H$ has rank one.
Replacing $v$ by any nonzero scalar multiple produces the same $H$ .

For $n>1$ , the eigenvalues are therefore $-1$ once and $+1$ with multiplicity $n-1$ . A product of Householder matrices remains orthogonal, although it need not itself be a single reflection. (web.stanford.edu)

Constructing a reflector to eliminate components

Given a nonzero $x\in\mathbb{R}^n$ , a common objective is to construct $H$ such that

Hx=\alpha e_1,

where $e_1=(1,0,\ldots,0)^T$ . Length preservation requires $|\alpha|=\|x\|_2$ . In exact arithmetic, setting

v=x-\alpha e_1

and using the defining Householder formula achieves this whenever $v\ne0$ . All components except the first are then annihilated in one operation. (web.stanford.edu)

For computation in floating-point arithmetic, the conventional choice is

\alpha=-s\|x\|_2, \qquad s= \begin{cases} 1,&x_1\ge0,\\ -1,&x_1<0. \end{cases}

Then

v=x+s\|x\|_2e_1.

The first component of $v$ is formed by adding quantities of the same sign, avoiding the cancellation that could occur with the opposite choice when $x$ is nearly parallel to $e_1$ . Practical implementations also rescale intermediate quantities when necessary to avoid underflow or overflow. If the components to be eliminated are already zero, software may use the identity transformation rather than perform a reflection; this is a computational convention, not a nontrivial geometric reflection. (netlib.org)

Example

Let

x=\begin{pmatrix}3\\4\end{pmatrix}.

Since $\|x\|_2=5$ , choose $\alpha=-5$ and $v=(8,4)^T$ . Substitution gives

H= I-\frac{2}{80} \begin{pmatrix} 64&32\\ 32&16 \end{pmatrix} = \begin{pmatrix} -\frac35&-\frac45\\ -\frac45&\frac35 \end{pmatrix}.

Multiplication verifies that $Hx=(-5,0)^T$ : the second component is eliminated and the length remains $5$ .

Efficient application and storage

Explicitly forming the dense matrix $H$ is usually unnecessary. With

H=I-\tau vv^T, \qquad \tau=\frac{2}{v^Tv},

its action on a vector is

Hx=x-\tau v(v^Tx).

This requires a dot product and a scaled vector update, taking $O(n)$ operations rather than the $O(n^2)$ work of a general dense matrix–vector multiplication. For a matrix $A$ , multiplication from either side can likewise be expressed as a rank-one update:

HA=A-\tau v(v^TA), \qquad AH=A-\tau(Av)v^T.

These are direct computational consequences of the elementary-reflector representation. (netlib.org)

Software often normalizes the stored reflector vector so that its first active component is $1$ , retaining only its remaining components and the scalar $\tau$ . A sequence of reflectors can represent an orthogonal matrix implicitly, allowing multiplication by that matrix or its transpose without constructing it explicitly. (netlib.org)

For blocked computations, a product can be represented as

H_1H_2\cdots H_b=I-VTV^T,

where the columns of $V$ contain reflector vectors and $T$ is upper triangular. This compact WY representation permits application through matrix–matrix operations, improving the use of high-performance numerical kernels. The product is sometimes called a block reflector, but it generally is not symmetric or involutory like an individual reflection. (netlib.org)

QR factorization and least-squares problems

For a real $m\times n$ matrix $A$ , with $m\ge n$ , Householder QR successively eliminates entries below the diagonal. At step $k$ , a reflector acts only on rows $k,\ldots,m$ , leaving previously established zeros undisturbed. If the embedded reflectors are $H_1,\ldots,H_p$ , then

R=H_p\cdots H_2H_1A, \qquad Q=H_1H_2\cdots H_p,

so that $A=QR$ , with $Q$ orthogonal and $R$ upper trapezoidal. A reduced factorization retains only the first $n$ columns of $Q$ and the corresponding square triangular factor. (web.stanford.edu)

The connection to linear least squares follows from norm preservation. Writing

Q^Tb= \begin{pmatrix}c_1\\c_2\end{pmatrix}, \qquad R= \begin{pmatrix}R_1\\0\end{pmatrix},

gives

\|Ax-b\|_2^2 = \|R_1x-c_1\|_2^2+\|c_2\|_2^2.

When $A$ has full column rank, the minimizer is obtained by solving the triangular system $R_1x=c_1$ . The identity illustrates why orthogonal triangularization can solve least-squares problems without explicitly forming $A^TA$ . (web.stanford.edu)

Eigenvalue and singular-value computations

Householder transformations also provide structured reductions before iterative spectral computations:

A real symmetric matrix can be reduced to tridiagonal form by orthogonal similarity transformations.
A general square matrix can be reduced to upper Hessenberg form, with zeros below the first subdiagonal, as a preliminary step for algorithms such as the QR algorithm.
A rectangular matrix can be reduced to bidiagonal form using transformations from both sides, preparing it for singular value decomposition.

These reductions preserve the relevant spectral information: similarity preserves eigenvalues, while orthogonal multiplication from the left and right preserves singular values. A general nonsymmetric matrix is not, in general, reducible to tridiagonal form by the same orthogonal-similarity procedure used for symmetric matrices. (netlib.org)

Complex transformations

For vectors over the complex numbers, the direct reflection analogue is

H=I-2\frac{vv^*}{v^*v},

where $v^*$ is the conjugate transpose. This matrix is Hermitian and unitary, and satisfies $H^2=I$ . (netlib.org)

Numerical libraries also use a broader complex elementary-reflector convention,

H=I-\tau vv^*,

with complex $\tau$ . Unitarity requires

\tau+\overline{\tau} = |\tau|^2(v^*v).

Such an $H$ need not be Hermitian or involutory. For example, LAPACK’s complex reflector generator constructs $H$ so that $H^*$ maps the input vector to a real leading component followed by zeros. Thus, in complex computations, “Householder reflector” may denote a unitary rank-one modification rather than a literal order-two reflection. (netlib.org)

Numerical stability and limitations

Properly implemented Householder QR has strong numerical stability properties. In backward-error terms, its computed factors can be interpreted as the factors of a nearby input matrix, with small normwise perturbation and a numerically orthogonal computed $Q$ . This does not ensure small relative errors in every individual matrix entry or in every solution derived from the factorization. (netlib.org)

Nor do orthogonal transformations cure an ill-conditioned problem. In exact arithmetic, they preserve the spectral-norm condition number of an invertible matrix. Accurate transformation and sensitivity of the original problem are therefore separate issues. (web.stanford.edu)

Householder reflectors eliminate an entire group of components at once, making them well suited to dense matrix reductions. Givens rotations, by contrast, act on two coordinates at a time and provide more localized transformations. Householder’s original triangularization paper explicitly compared the two approaches, emphasizing the reduction in arithmetic work achieved by replacing sequences of plane rotations with reflections. (web.stanford.edu)

References

Unitary Triangularization of a Nonsymmetric Matrixweb.stanford.edu
Representation of Orthogonal or Unitary Matricesnetlib.org
Non-Negative Diagonals and High Performance onnetlib.org
LAPACK: SRC/dlarfgp.f Source Filenetlib.org
LAPACK: zlarfgnetlib.org
LAPACK: larf: apply Householder reflectornetlib.org
QR Factorizationnetlib.org
LAPACK: clarftnetlib.org
LAPACK Working Note #2: Block Algorithms for Reducing Symmetric and General Matrices to Tridiagonal, Bidiagonal and Hessenberg Formsnetlib.org
LAPACK Users’ Guide: Block Algorithms for Eigenvalue Problemsnetlib.org
LAPACK Working Note #176netlib.org