Householder transformation ($H=I-2u{u}^T$)

A Householder transformation is a reflection that leaves every direction in a chosen hyperplane fixed and reverses its normal direction. For a real unit vector $u$, its matrix isTo understand the formula, decompose any vector into its orthogonal projection onto the normal and a perpendicular component:Then $Hx=x_{\perp }-x_{\parallel }$. Subtracting twice the normal component changes its sign while retaining everything parallel to the mirror. A nonzero normal $v$ gives the equivalent formula $H=I-2v{v}^T/(v^{T}v)$, so normalization can be deferred.

For example, take $u=(2,1{)}^T/\sqrt{5}$. Its mirror is the straight line $2x_1+x_2=0$, andThe midpoint of these two vectors is $(-1,2{)}^T$, which lies on the mirror; their connecting segment is parallel to its normal. Both vectors have Euclidean norm five.

Several useful properties follow from this decomposition. The Householder reflection is a symmetric matrix and an orthogonal matrix:Reflecting twice restores the original vector; Euclidean norms and inner products are preserved. The eigenvalue is $-1$ along $u$ and $+1$ on $u^{\perp }$, so $\det H=-1$. A reflection reverses orientation even though it preserves lengths.

The computational payoff is that the mirror can be chosen to send a whole vector onto one coordinate axis, eliminating several entries at once. Householder QR decomposition repeats this operation on the remaining parts of successive columns. For a real symmetric matrix, applying the same Householder reflection on both sides gives a matrix similarity $HAH$ that preserves symmetry and eigenvalues; this is the basis of Householder tridiagonalization.

Alston S. Householder's 1958 paper Unitary Triangularization of a Nonsymmetric Matrix develops this elimination method. Its motivation includes reducing the arithmetic needed for triangularization while retaining the conditioning advantages of orthogonal transformations. ^[ref] Over the complex numbers, $I-2u{u}^{\ast }$ for a unit $u$ is Hermitian and unitary, with the star denoting the conjugate transpose; the coordinate-axis construction below is stated for real vectors.

For real unit vectors $a,b$, the Householder reflections $H_a=I-2a{a}^T$ and $H_b=I-2b{b}^T$ commute exactly when their normals are parallel or orthogonal. Expanding their products proves the formula. If $a\cdot b\ne 0$, a zero commutator requires $b{a}^T=a{b}^T$; applying this identity to $a$ gives $b=(a\cdot b)a$, hence parallelism. Orthogonal normals make the prefactor zero.

Equality on one selected vector is weaker than equality of the operators. For nonparallel, nonorthogonal normals in three dimensions, the commutator's kernel is the line perpendicular to both normals, spanned by $a\times b$. A vector on that line is fixed by both reflections even though the operators do not commute.

For a nonzero real vector $x\in {\mathbb{R}}^n$, choose $\alpha$ with $|\alpha |=\Vert x{\Vert }_2$ and put $v=x-\alpha e_1$. When $v\ne 0$, the Householder reflectionsatisfies $Hx=\alpha e_1$: every component except the first becomes zero. Here $e_1$ is the first Cartesian basis vector. The calculation is short:If $v=0$, the vector is already at the selected target, so the identity matrix suffices.

In floating-point arithmetic, a customary choice isThen $|v_1|=|x_1|+\Vert x{\Vert }_2$, avoiding subtraction of nearly equal positive quantities in the first component. Either sign can be valid in exact arithmetic; the numerical choice protects the construction from catastrophic cancellation. ^[ref]

For $x=(3,4{)}^T$, this choice gives $\alpha =-5$ and $v=(8,4{)}^T$. Dividing $v$ by its Euclidean norm gives $u=(2,1{)}^T/\sqrt{5}$, exactly the normal in the geometric example.

Apply the preceding Householder reflection to the columns ofThe first column becomes $(-5,0{)}^T$ and the second becomes $(-11/5,2/5{)}^T$:Thus an orthogonal matrix multiplying an upper triangular matrix reconstructs $A$. The zero below the diagonal came from a geometric operation that preserves Euclidean norms and inner products.

Our positive-diagonal convention for QR decomposition is obtained by a sign adjustment. With $D=\mathrm{diag}(-1,1)$, putThen $Q^{T}Q=I$ and $\boxed{A=Q{R}_{+}}$. The intermediate sign chooses an orientation for a basis vector; the adjustment makes the diagonal positive.

For a larger matrix, the next Householder reflection acts only on the lower rows of the remaining columns, retaining the zeros already created. Store its defining vector and apply $z\mapsto z-2u(u^{T}z)$ instead of forming a dense reflection matrix. This links a simple mirror operation to efficient QR decomposition, including least-squares solutions.