Householder Transformations for Vector Zeroing

The Goal: Reflecting a Vector onto an Axis

The core task in tridiagonalization is to introduce zeros into a matrix. We achieve this by targeting columns of the matrix, one vector at a time. The goal is to take a vector $\mathbf{x}\in {\mathbb{R}}^n$ and find a Householder matrix $P$ that transforms it into a vector $\mathbf{y}$ that is simpler—specifically, one that points along the first standard basis vector, ${\mathbf{e}}_1=[1,0,\dots ,0{]}^T$.

Since Householder transformations are reflections, they are orthogonal transformations, which means they preserve length (the Euclidean norm). Therefore, the target vector $\mathbf{y}$ must have the same norm as the original vector $\mathbf{x}$. This means our target vector $\mathbf{y}$ must be of the form:

where $|\sigma |=||\mathbf{x}|{|}_2$. This leaves two choices for the target vector: $\mathbf{y}=||\mathbf{x}|{|}_2{\mathbf{e}}_1$ or $\mathbf{y}=-||\mathbf{x}|{|}_2{\mathbf{e}}_1$.

The following video explains this setup beautifully, showing how to determine the reflection needed to map a vector $\mathbf{x}$ to a multiple of ${\mathbf{e}}_1$.

The Recipe for Construction

As the video established, the vector normal to the reflection hyperplane is the key. Let's formalize the process. Given a vector $\mathbf{x}$, we want to find a Householder matrix $P$ such that $P\mathbf{x}=\sigma {\mathbf{e}}_1$.

1. Define the target: Let the target vector be $\mathbf{y}=\sigma {\mathbf{e}}_1$, where $\sigma =\pm ||\mathbf{x}|{|}_2$.
2. Find the reflection vector: The vector $\mathbf{u}$ that defines the reflection is the difference between the start and end points: $\mathbf{u}=\mathbf{x}-\mathbf{y}$.
3. Construct the matrix: The Householder matrix is then given by $P=I-2\frac{\mathbf{u}{\mathbf{u}}^T}{{\mathbf{u}}^T\mathbf{u}}$. This form is convenient as you don't need to normalize $\mathbf{u}$ to a unit vector separately.

The image below, which you may recognize from your course materials, illustrates this reflection process. The vector $\mathbf{x}$ is reflected across the hyperplane defined by the normal vector $\mathbf{u}$. The component of $\mathbf{x}$ along $\mathbf{u}$ is projected and subtracted twice to get the final reflected vector.

The following reading provides a concise summary of the formulas we need.

A Note on Choosing the Sign

You have two choices for the target vector: $+||\mathbf{x}|{|}_2{\mathbf{e}}_1$ or $-||\mathbf{x}|{|}_2{\mathbf{e}}_1$. While both are mathematically valid, one choice is better for numerical stability. To avoid subtracting two nearly equal numbers (which can lead to a loss of precision in floating-point arithmetic), a standard convention is to choose the sign of $\sigma$ to be the same as the sign of the first component of $\mathbf{x}$, $x_1$. This ensures that the first component of $\mathbf{u}=\mathbf{x}-\sigma {\mathbf{e}}_1$ is a sum, not a difference, maximizing its magnitude.

So, the robust formula for our reflection vector is:

Or, if you prefer to avoid subtractions, you can define the target vector $\mathbf{y}$ with the opposite sign, leading to $\mathbf{u}=\mathbf{x}+(\text{sign}(x_1)||\mathbf{x}|{|}_2){\mathbf{e}}_1$. The resulting Householder matrix will be the same. Let's use this second, addition-based form for our example.

Worked Example

Let's apply this recipe to construct a Householder matrix that transforms the vector $\mathbf{x}=[1,2,2{]}^T$ into the form $[\sigma ,0,0{]}^T$.

1. Given Vector

2. Calculate the Norm

3. Determine the Reflection Vector $\mathbf{u}$
The first component, $x_1=1$, is positive. Following the stability convention, we use the formula $\mathbf{u}=\mathbf{x}+\text{sign}(x_1)||\mathbf{x}|{|}_2{\mathbf{e}}_1$.

4. Construct the Householder Matrix $P$
The formula is $P=I-2\frac{\mathbf{u}{\mathbf{u}}^T}{{\mathbf{u}}^T\mathbf{u}}$. First, we need the scalar ${\mathbf{u}}^T\mathbf{u}$ and the matrix $\mathbf{u}{\mathbf{u}}^T$.

Now, substitute these into the formula for $P$:

This is the Householder matrix we sought.

5. Verification (Optional but Recommended)
Let's check if $P\mathbf{x}$ gives the expected result, which should be $-||\mathbf{x}|{|}_2{\mathbf{e}}_1=[-3,0,0{]}^T$.

The result is exactly as expected. We have successfully constructed a Householder matrix to zero out the second and third components of our vector.

Conclusion

In this lesson, you've learned the practical mechanics of building a Householder matrix for a specific purpose. This is a crucial skill that transforms the Householder matrix from an abstract concept into a functional numerical tool.

The key takeaways are:

• To zero out elements of a vector $\mathbf{x}$, we reflect it to a target vector $\mathbf{y}$ that lies on a standard basis axis, such as $\mathbf{y}=\sigma {\mathbf{e}}_1$.
• The reflection is defined by the vector $\mathbf{u}=\mathbf{x}-\mathbf{y}$.
• A numerically stable choice for the reflection vector is $\mathbf{u}=\mathbf{x}+\text{sign}(x_1)||\mathbf{x}|{|}_2{\mathbf{e}}_1$.
• The final Householder matrix is constructed using the formula $P=I-2\frac{\mathbf{u}{\mathbf{u}}^T}{{\mathbf{u}}^T\mathbf{u}}$.

Now that you can transform a single vector, you are ready for the next step. In the upcoming lesson, we will apply this technique to the columns of a symmetric matrix, performing the first full iteration of the Householder method to begin its transformation into tridiagonal form.