Welcome back. In our last session, we mastered the art of constructing a Householder matrix to transform a single vector into a much simpler form with trailing zeros. Today, we will apply that powerful tool to its intended purpose: reducing a symmetric matrix to a tridiagonal form.
This lesson focuses on the crucial first step of the algorithm. You will learn how to perform the complete first iteration of Householder's method on a symmetric 4x4 matrix. This involves identifying the correct vector to target, building the appropriate Householder matrix P_1, and carrying out the similarity transformation A_1 = P_1 A P_1 to introduce zeros into the first column and row. This process is the core of the tridiagonalization technique, which simplifies the matrix while preserving its all-important eigenvalues.
The Game Plan: Iterative Reduction
The Householder method reduces an n x n symmetric matrix A to tridiagonal form in n-2 steps. For a 4x4 matrix, this means we'll need two iterations.
Iteration 1 (Our focus today):
We construct a Householder matrix P_1 to zero out the elements in the first column below the sub-diagonal, i.e., a_{31} and a_{41}. Because the similarity transformation P_1 A P_1 is applied to a symmetric matrix with a symmetric P_1, the corresponding elements in the first row, a_{13} and a_{14}, will also be zeroed out automatically.
Iteration 2 (Next lesson):
We will then focus on a smaller submatrix and construct a second matrix P_2 to zero out the last remaining off-tridiagonal element.
The final tridiagonal matrix T will be T = P_2 P_1 A P_1 P_2. Since P_1 and P_2 are orthogonal, this is a similarity transformation, and T has the same eigenvalues as A.
First Iteration: A Step-by-Step Guide
Let's break down the first iteration. The key insight is that we don't need a transformation that acts on the entire R^4 space at once. To zero out elements a_{31} and a_{41}, we only need to transform the sub-vector [a_{21}, a_{31}, a_{41}]^T. The Householder matrix for this 3x3 problem is then embedded into a 4x4 identity matrix to form P_1.
The following video provides an excellent, detailed walkthrough of this entire first iteration for a 4x4 matrix. We will follow its steps closely. The notation in the video (alpha, R, W or omega) is slightly different from the u vector we used in the last lesson, but the underlying principle is identical. The vector W in the video is a unit vector, equivalent to the w in our previous formula P = I - 2ww^T.
Householder's Method 4 by 4 Matrix
This video by Reindolf Boadu meticulously demonstrates the first iteration of the Householder method on a 4x4 matrix, which is exactly our goal for this lesson.
Watch the video from the beginning to the end. The key stages are: Setup and alpha calculation : The instructor identifies the target vector x = [a_{21}, a_{31}, a_{41}]^T and calculates its norm, which he incorporates into the alpha term. R and W vector calculation : He calculates the components of the reflection vector W. This corresponds to calculating our vector u and normalizing it. Constructing P_1 : He builds the 4x4 Householder matrix P_1 (which he calls H_1) using the formula P_1 = I - 2WW^T. Notice that P_1 has a 1 in the top-left corner and zeros in the rest of the first row and column, as the reflection only acts on the last three coordinates. The Similarity Transformation : He computes the new matrix A_1 = P_1 A P_1 (he writes it as H_1 * A_0 * H_1).
Let's recap the process shown in the video with our established terminology.
1. Isolate the Target Vector
Given the matrix A from the video:
Our goal is to zero out a_{31} = -2 and a_{41} = 2. The reflection we design will operate on the subspace spanned by the 2nd, 3rd, and 4th basis vectors. The vector we need to transform within this subspace is:
2. Construct the 3x3 Householder Matrix P_hat
Following the recipe from our last lesson for this vector :
- Norm: .
- Reflection vector
u: Using the stable formulau = x + sign(x_1) ||x||_2 e_1: - Construct
P_hat: Using :
3. Form the 4x4 Householder Matrix P_1
We embed P_hat into a 4x4 identity matrix:
This is the final matrix H_1 computed in the video at
4. Perform the Similarity Transformation
The final step is to compute A_1 = P_1 A P_1. This is a standard matrix multiplication. The video calculates this and arrives at the result:
Notice the structure: the desired zeros have appeared in the first column and, by symmetry, the first row. The matrix is now one step closer to being tridiagonal.
The image below, from a different resource, illustrates this same idea. After multiplying by the first Householder matrix (Q1 in the image), the result Q1A has zeros in the first column. The next iteration will then work on the smaller A' submatrix.
For a text-based walkthrough of another 4x4 example, you can refer to the following document.
[PDF] Householder (tridiagonal) Technique:
This document provides a worked example of tridiagonalizing a 4x4 matrix. It serves as a good text-based companion to the video.
Focus on the second example in the PDF, which starts with the heading "Tridiagonalize the real symmetric matrix". Follow the calculations for the first iteration (k=1), which computes the first Householder matrix p_1 and the resulting transformed matrix A_2.
Conclusion
Today you've bridged the gap between theory and practice, applying the Householder transformation to a full-sized matrix. You have successfully performed the first complete iteration of the Householder method.
The key takeaways from this lesson are:
- The Householder tridiagonalization method proceeds in
n-2iterations for ann x nmatrix. - The first iteration targets the sub-vector
[a_{21}, ..., a_{n1}]^Tto zero out elements below the sub-diagonal in the first column. - The
(n-1)x(n-1)Householder matrixP_hatis constructed for this sub-vector and then embedded in ann x nidentity matrix to formP_1. - The similarity transformation
A_1 = P_1 A P_1produces the new matrix, which is one step closer to tridiagonal form and has the same eigenvalues asA.
In our next lesson, we will perform the second and final iteration on our 4x4 matrix. You will see how the process neatly repeats itself on the smaller submatrix we have created, leading us to the final tridiagonal form.