Mapping Vectors with Householder Reflections

Using the Difference to Build a Reflection

A Householder reflection can be chosen to send one vector to another, provided the two vectors have the same length. The useful choice of normal vector is their difference: reflecting across the hyperplane perpendicular to that difference exchanges the two vectors. This gives a direct construction from the vectors themselves, rather than requiring a separate search for a reflecting hyperplane.

Throughout, vectors are columns in \(\mathbb{R}^n\), with the usual dot product \(\mathbf{u}^{\top}\mathbf{v}\) and norm \(\|\mathbf{u}\|=\sqrt{\mathbf{u}^{\top}\mathbf{u}}\). A hyperplane through the origin with nonzero normal vector \(\mathbf{u}\) consists of the vectors \(\mathbf{z}\) satisfying \(\mathbf{u}^{\top}\mathbf{z}=0\). The reflection fixes every vector in that hyperplane and reverses the component in the direction of \(\mathbf{u}\).

The fraction involving \(\mathbf{u}\mathbf{u}^{\top}\) is an \(n\times n\) matrix: \(\mathbf{u}\mathbf{u}^{\top}\) is the outer product of the column vector with its transpose. Scaling the normal does not change the reflection. Indeed, for any nonzero real \(c\), replacing \(\mathbf{u}\) by \(c\mathbf{u}\) multiplies both the numerator and denominator by \(c^2\).

Why the Householder Matrix Is a Reflection

Before using the matrix to map vectors, we verify its defining properties. Write \(\alpha=2/(\mathbf{u}^{\top}\mathbf{u})\), so \(\mathbf{H}_{\mathbf{u}}=\mathbf{I}_n-\alpha\mathbf{u}\mathbf{u}^{\top}\). Since \(\mathbf{u}^{\top}\mathbf{u}\) is a nonzero real number, the expression is defined. The matrix is symmetric, fixes vectors perpendicular to \(\mathbf{u}\), and sends \(\mathbf{u}\) to its negative.

Proof. Because \((\mathbf{u}\mathbf{u}^{\top})^{\top}=\mathbf{u}\mathbf{u}^{\top}\), the matrix \(\mathbf{H}_{\mathbf{u}}\) is symmetric. Put \(s=\mathbf{u}^{\top}\mathbf{u}\), which is positive because \(\mathbf{u}\ne\mathbf{0}\). Then \(\alpha=2/s\), and \((\mathbf{u}\mathbf{u}^{\top})(\mathbf{u}\mathbf{u}^{\top})=\mathbf{u}(\mathbf{u}^{\top}\mathbf{u})\mathbf{u}^{\top}=s\mathbf{u}\mathbf{u}^{\top}\). Thus \(\mathbf{H}_{\mathbf{u}}^{\top}\mathbf{H}_{\mathbf{u}}=(\mathbf{I}_n-\alpha\mathbf{u}\mathbf{u}^{\top})^2=\mathbf{I}_n+(-2\alpha+\alpha^2s)\mathbf{u}\mathbf{u}^{\top}=\mathbf{I}_n\), since \(-2\alpha+\alpha^2s=-4/s+4/s=0\). This is the defining condition for an orthogonal matrix. If \(\mathbf{u}^{\top}\mathbf{z}=0\), then \(\mathbf{H}_{\mathbf{u}}\mathbf{z}=\mathbf{z}-2\mathbf{u}(\mathbf{u}^{\top}\mathbf{z})/s=\mathbf{z}\). Also, \(\mathbf{H}_{\mathbf{u}}\mathbf{u}=\mathbf{u}-2\mathbf{u}s/s=-\mathbf{u}\). The matrix therefore fixes the perpendicular hyperplane and reverses the normal direction, as claimed. \(\square\)

Orthogonality also guarantees that the transformation preserves length: if \(\mathbf{H}^{\top}\mathbf{H}=\mathbf{I}_n\), then \(\|\mathbf{H}\mathbf{x}\|^2=(\mathbf{H}\mathbf{x})^{\top}(\mathbf{H}\mathbf{x})=\mathbf{x}^{\top}\mathbf{H}^{\top}\mathbf{H}\mathbf{x}=\|\mathbf{x}\|^2\). Consequently, a Householder reflection cannot map vectors of different lengths to each other.

The Difference-Vector Construction

Proof. First assume \(\|\mathbf{x}\|=\|\mathbf{y}\|\) and \(\mathbf{x}\ne\mathbf{y}\). The difference \(\mathbf{u}=\mathbf{x}-\mathbf{y}\) is nonzero, so \(\mathbf{H}_{\mathbf{u}}\) is defined. Expanding the two dot products gives \(\mathbf{u}^{\top}\mathbf{x}=\|\mathbf{x}\|^2-\mathbf{y}^{\top}\mathbf{x}\), while \(\mathbf{u}^{\top}\mathbf{u}=\|\mathbf{x}\|^2+\|\mathbf{y}\|^2-2\mathbf{y}^{\top}\mathbf{x}\). Equality of the squared lengths therefore implies \(\mathbf{u}^{\top}\mathbf{u}=2\mathbf{u}^{\top}\mathbf{x}\). Substitute this into the reflection formula: \(\mathbf{H}_{\mathbf{u}}\mathbf{x}=\mathbf{x}-2\mathbf{u}\dfrac{\mathbf{u}^{\top}\mathbf{x}}{\mathbf{u}^{\top}\mathbf{u}}=\mathbf{x}-\mathbf{u}=\mathbf{x}-(\mathbf{x}-\mathbf{y})=\mathbf{y}\). For the reverse implication, suppose \(\mathbf{x}\ne\mathbf{y}\), set \(\mathbf{u}=\mathbf{x}-\mathbf{y}\), and assume \(\mathbf{H}_{\mathbf{u}}\mathbf{x}=\mathbf{y}\). The formula then gives \(2\mathbf{u}^{\top}\mathbf{x}/(\mathbf{u}^{\top}\mathbf{u})=1\), because \(\mathbf{x}-\mathbf{y}=\mathbf{u}\ne\mathbf{0}\). Hence \(2\mathbf{u}^{\top}\mathbf{x}=\mathbf{u}^{\top}\mathbf{u}\). Substituting the expansions above yields \(2\|\mathbf{x}\|^2-2\mathbf{y}^{\top}\mathbf{x}=\|\mathbf{x}\|^2+\|\mathbf{y}\|^2-2\mathbf{y}^{\top}\mathbf{x}\), so \(\|\mathbf{x}\|^2=\|\mathbf{y}\|^2\). Both implications are proved. \(\square\)

This proof gives a practical recipe. When the vectors differ, calculate their difference, form the Householder matrix with that difference as its normal, and apply the matrix. Equal lengths are essential: they are what make the dot-product identity in the proof hold, and orthogonality independently shows that unequal lengths could not be mapped by a reflection.

Identical and Opposite Vectors

The difference-based formula has a special case that must not be handled by substitution alone. If \(\mathbf{x}=\mathbf{y}\), then \(\mathbf{x}-\mathbf{y}=\mathbf{0}\), which cannot be used as a Householder normal. There is no need to reflect the vector to reach itself: use the identity matrix \(\mathbf{I}_n\), which maps every vector to itself. This is the identity transformation, not a nontrivial Householder reflection. In some dimensions one can also choose a nonzero normal perpendicular to \(\mathbf{x}\), but that is a different choice of normal and is unnecessary for the mapping.

If \(\mathbf{y}=-\mathbf{x}\) and \(\mathbf{x}\ne\mathbf{0}\), the two vectors have equal lengths and are distinct. Their difference is \(2\mathbf{x}\), so the normal points in the direction of \(\mathbf{x}\). The corresponding reflection reverses the vector and fixes every vector perpendicular to it. If \(\mathbf{x}=\mathbf{0}\), then \(-\mathbf{x}=\mathbf{x}\), so this is the identical-vector case instead.

Common Mistake: Omitting the Factor of Two

A frequent error is to use \(\mathbf{I}_n-\mathbf{u}\mathbf{u}^{\top}/(\mathbf{u}^{\top}\mathbf{u})\), omitting the factor \(2\). That matrix does not reverse the normal component; it subtracts only half of the required change. For the first worked example, \(\mathbf{u}=(2,-2,-2)^{\top}\) and \(\mathbf{u}^{\top}\mathbf{u}=12\). The incorrect expression sends \(\mathbf{x}=(3,0,0)^{\top}\) to \(\mathbf{x}-\mathbf{u}(\mathbf{u}^{\top}\mathbf{x})/12=(3,0,0)^{\top}-(1,-1,-1)^{\top}=(2,1,1)^{\top}\), not to \((1,2,2)^{\top}\). The correct factor gives \(\mathbf{x}-2\mathbf{u}(\mathbf{u}^{\top}\mathbf{x})/12=(3,0,0)^{\top}-2(1,-1,-1)^{\top}=(1,2,2)^{\top}\). The final multiplication is a useful check: a proposed matrix is a valid answer to a mapping problem only if applying it to the starting vector actually produces the target.