Tridiagonal and Householder Matrices

Welcome to the second module of our course. In the previous module, we explored iterative techniques, like the Power Method and its variants, for finding specific eigenvalues of a matrix. While effective, these methods can be slow. A common and more efficient strategy in numerical linear algebra is to first transform a complex matrix into a simpler one that has the same eigenvalues.

In this lesson, we will begin our exploration of this strategy. Our goal is to define two key components of this process: the tridiagonal matrix, which is our target simplified form, and the Householder matrix, which is the tool we'll use to get there. We will define what a Householder matrix is, explore its geometric meaning as a reflection, and establish its crucial properties of symmetry and orthogonality.

The Target: Tridiagonal Matrices

The first step in many advanced eigenvalue algorithms is to reduce a symmetric matrix to a form that is "mostly zero". One of the most useful of these forms is the tridiagonal matrix.

A tridiagonal matrix is a matrix where the only non-zero entries are on the main diagonal, the first diagonal below it (the subdiagonal), and the first diagonal above it (the superdiagonal). All other entries are zero.

This image shows the structure of a tridiagonal matrix. The elements $a_i$ form the main diagonal, $b_i$ form the superdiagonal, and $c_i$ form the subdiagonal. All other positions are zero.

The value of this form lies in its simplicity. The large number of zero entries dramatically reduces the computational cost of finding eigenvalues. Algorithms exist that can find the eigenvalues of a tridiagonal matrix very quickly, a topic we will touch upon later. For now, our focus is on how to transform a general symmetric matrix into this desirable form.

The Tool: Householder Transformations

The primary tool for this transformation is the Householder matrix, which performs a geometric operation known as a reflection.

Geometric Intuition: A Reflection in Space

Imagine a vector $x$ in a 2D plane and a line passing through the origin. A reflection maps $x$ to its mirror image on the other side of the line. A Householder transformation is the generalization of this idea to $n$ -dimensional space. It reflects a vector $x$ across a hyperplane (a subspace of dimension $n - 1$ ).

The orientation of this "mirror" hyperplane is defined by a vector $v$ that is orthogonal (perpendicular) to it.

Here, the vector $\mathbf{x}$ is reflected across the hyperplane perpendicular to $\mathbf{v}$. The resulting vector is $\mathbf{x} - 2\langle\mathbf{x}, \mathbf{v}\rangle\mathbf{v}$ (assuming $\mathbf{v}$ is a unit vector).

The following video provides an excellent visual introduction to this concept of reflection.

03.3.2 Householder transformations, part 1

This video from the Advanced LAFF channel introduces the Householder transformation as a geometric reflection and then derives its matrix form.

First, watch the introductory segment that uses a 3D mirror analogy to build your intuition for what a reflection does. This section sets up the geometry of the problem. The mirror analogy. Next, see how this geometric picture is translated into a matrix equation. Pay close attention to how the vector \mathbf{x} is decomposed into components parallel and perpendicular to the vector \mathbf{u} (which defines the hyperplane), leading to the final matrix formula. Watch from the formula derivation. The video concludes by formally naming this matrix a Householder transformation.

The Definition and Key Properties

As derived in the video, the reflection of a vector $x$ can be represented by a matrix multiplication, $y = P x$ . This matrix $P$ is the Householder matrix.

The following reading provides the formal definition and a concise list of its essential properties.

What Is a Householder Matrix? - Nick Higham

This article by Nick Higham, a leading expert in numerical linear algebra, gives a crisp, formal definition of the Householder matrix and its properties.

Read the first few paragraphs, starting from the main definition. The formula presented uses a vector \mathbf{v} which is not necessarily a unit vector. The formula from your course notes and the video, P = I - 2\mathbf{w}\mathbf{w}^T, assumes \mathbf{w} is a unit vector (\mathbf{w}^T\mathbf{w}=1). The two forms are equivalent, since \mathbf{w} = \mathbf{v}/\sqrt{\mathbf{v}^T\mathbf{v}}.

As stated in the reading, and in your course notes (§9.3 Householder’s method), a Householder matrix $P$ constructed with a real unit vector $w$ is defined as:

P = I - 2 w w^{T}

This matrix has two fundamental properties that make it perfect for numerical algorithms:

It is symmetric: $P^{T} = P$ .
It is orthogonal: $P^{T} P = I$ .

Let's quickly prove these, as these proofs are fundamental.

Proof of Symmetry:
We take the transpose of $P$ :

P^{T} = (I - 2 w w^{T})^{T} = I^{T} - (2 w w^{T})^{T}

Since $I^{T} = I$ and $(A B)^{T} = B^{T} A^{T}$ , this becomes:

P^{T} = I - 2 (w^{T})^{T} w^{T} = I - 2 w w^{T} = P

Thus, the matrix is symmetric.

Proof of Orthogonality:
To prove orthogonality, we show that $P^{T} P = I$ . Since we just proved $P^{T} = P$ , this is the same as showing $P^{2} = I$ .

P^{2} = P P = (I - 2 w w^{T}) (I - 2 w w^{T})

Expanding this out gives:

P^{2} = I \cdot I - I (2 w w^{T}) - (2 w w^{T}) I + (2 w w^{T}) (2 w w^{T})

P^{2} = I - 4 w w^{T} + 4 w (w^{T} w) w^{T}

The term $w^{T} w$ is the dot product of the unit vector $w$ with itself, which is simply the scalar 1. So, the expression simplifies:

P^{2} = I - 4 w w^{T} + 4 w (1) w^{T} = I - 4 w w^{T} + 4 w w^{T} = I

This proves that $P$ is orthogonal. It also shows $P$ is involutory ( $P^{2} = I$ ), meaning applying the transformation twice returns you to the original vector, which makes perfect sense for a reflection.

The key consequence of these properties is that $P^{- 1} = P^{T} = P$ . This makes Householder transformations numerically stable and easy to work with, as their inverse is the matrix itself.

Conclusion

In this lesson, we have laid the conceptual groundwork for the matrix tridiagonalization process. We introduced our destination—the simple and computationally efficient tridiagonal matrix—and our vehicle, the Householder matrix.

The key takeaways are:

A tridiagonal matrix has non-zero elements only on its main diagonal and the adjacent sub- and superdiagonals. Transforming a matrix to this form simplifies finding its eigenvalues.
A Householder matrix $P = I - 2 w w^{T}$ performs a reflection across a hyperplane.
This matrix has two critical properties: it is symmetric ( $P = P^{T}$ ) and orthogonal ( $P^{T} P = I$ ), which implies it is its own inverse ( $P = P^{- 1}$ ).

We now understand what a Householder matrix is and why its properties are useful. In our next lesson, we will put this tool to use. We will learn how to construct a specific Householder matrix that transforms a given vector into a new vector with zeros in desired positions. This is the fundamental step in the algorithm for matrix tridiagonalization.

Recommended resources

The Target: Tridiagonal Matrices

The Tool: Householder Transformations

Geometric Intuition: A Reflection in Space

The Definition and Key Properties

Conclusion