Module

for

Householder Transformations

       

Householder's Method

    Each transformation in
Jacobi's method produced two zero off-diagonal elements, but subsequent iterations might make them nonzero. Hence many iterations are required to make the off-diagonal entries sufficiently close to zero.
    
    Suppose that
A is a real symmetric matrix.  Householder's method is used to construct a similar symmetric tridiagonal matrix.  Then the QR method can be used to find all eigenvalues of the tridiagonal matrix.  
    
    We now develop the method attributed to
Alston Scott Householder (May 5, 1904 - July4, 1993) which is routinely taught in courses in linear algebra, and numerical analysis. Several several zero off-diagonal elements are created with each iteration, and they remain zero in subsequent iterations. We start by developing an important step in the process.

 

Theorem (Householder Reflection)  If [Graphics:Images/HouseholderMod_gr_1.gif] and [Graphics:Images/HouseholderMod_gr_2.gif] are vectors with the same norm, there exists an orthogonal symmetric matrix [Graphics:Images/HouseholderMod_gr_3.gif] such that

            
[Graphics:Images/HouseholderMod_gr_4.gif],  
        where
            
[Graphics:Images/HouseholderMod_gr_5.gif]  
        and
            
[Graphics:Images/HouseholderMod_gr_6.gif].  

Since
[Graphics:Images/HouseholderMod_gr_7.gif] is both orthogonal and symmetric, it follows that

            
[Graphics:Images/HouseholderMod_gr_8.gif].  

Proof  Householder Method

 

Remark.  It should be observed that the effect of the mapping [Graphics:Images/HouseholderMod_gr_9.gif] is to reflect [Graphics:Images/HouseholderMod_gr_10.gif] through the line whose direction is [Graphics:Images/HouseholderMod_gr_11.gif], hence the name Householder reflection.

Corollary ([Graphics:Images/HouseholderMod_gr_12.gif] Householder Matrix)  Let [Graphics:Images/HouseholderMod_gr_13.gif] be an [Graphics:Images/HouseholderMod_gr_14.gif] matrix, and [Graphics:Images/HouseholderMod_gr_15.gif] any vector.  If [Graphics:Images/HouseholderMod_gr_16.gif] is an integer with [Graphics:Images/HouseholderMod_gr_17.gif], we can construct a vector [Graphics:Images/HouseholderMod_gr_18.gif] and matrix  [Graphics:Images/HouseholderMod_gr_19.gif]  so that  

(1)             [Graphics:Images/HouseholderMod_gr_20.gif].  

Proof  Householder Method

 

Householder Transformations

    Suppose that
[Graphics:Images/HouseholderMod_gr_21.gif] is a symmetric [Graphics:Images/HouseholderMod_gr_22.gif] matrix. Then a sequence of [Graphics:Images/HouseholderMod_gr_23.gif] transformations of the form  [Graphics:Images/HouseholderMod_gr_24.gif]  will reduce [Graphics:Images/HouseholderMod_gr_25.gif] to a symmetric tridiagonal matrix.  Let us visualize the process when [Graphics:Images/HouseholderMod_gr_26.gif].  The first transformation is defined to be  [Graphics:Images/HouseholderMod_gr_27.gif],  where [Graphics:Images/HouseholderMod_gr_28.gif] is constructed by applying the above Corollary with the vector [Graphics:Images/HouseholderMod_gr_29.gif] being the first column of the matrix [Graphics:Images/HouseholderMod_gr_30.gif].  The general form of [Graphics:Images/HouseholderMod_gr_31.gif] is

            
[Graphics:Images/HouseholderMod_gr_32.gif]  

where the letter
[Graphics:Images/HouseholderMod_gr_33.gif] stands for some element in [Graphics:Images/HouseholderMod_gr_34.gif].  As a result, the transformation  [Graphics:Images/HouseholderMod_gr_35.gif]  does not affect the element [Graphics:Images/HouseholderMod_gr_36.gif] of [Graphics:Images/HouseholderMod_gr_37.gif]:

(2)            [Graphics:Images/HouseholderMod_gr_38.gif].  

    The element denoted [Graphics:Images/HouseholderMod_gr_39.gif] is changed because of premultiplication by [Graphics:Images/HouseholderMod_gr_40.gif], and [Graphics:Images/HouseholderMod_gr_41.gif] is changed because of postmultiplication by [Graphics:Images/HouseholderMod_gr_42.gif]; since [Graphics:Images/HouseholderMod_gr_43.gif] is symmetric, we have [Graphics:Images/HouseholderMod_gr_44.gif].  The changes to the elements denoted  [Graphics:Images/HouseholderMod_gr_45.gif]  have been affected by both premultiplication and postmultiplication.  Also, since [Graphics:Images/HouseholderMod_gr_46.gif] is the first column of [Graphics:Images/HouseholderMod_gr_47.gif], equation (1) implies that  [Graphics:Images/HouseholderMod_gr_48.gif].  

    The second Householder transformation is applied to the matrix
[Graphics:Images/HouseholderMod_gr_49.gif] defined in (2) and is denoted  [Graphics:Images/HouseholderMod_gr_50.gif],  where [Graphics:Images/HouseholderMod_gr_51.gif] is constructed by applying the Corollary with the vector [Graphics:Images/HouseholderMod_gr_52.gif] being the second column of the matrix [Graphics:Images/HouseholderMod_gr_53.gif].  The form of [Graphics:Images/HouseholderMod_gr_54.gif] is

            
[Graphics:Images/HouseholderMod_gr_55.gif]  

where
[Graphics:Images/HouseholderMod_gr_56.gif] stands for some element in [Graphics:Images/HouseholderMod_gr_57.gif].  The [Graphics:Images/HouseholderMod_gr_58.gif] identity block in the upper-left corner ensures that the partial tridiagonalization achieved in the first step will not be altered by the second transformation [Graphics:Images/HouseholderMod_gr_59.gif].  The outcome of this transformation is  

(3)            [Graphics:Images/HouseholderMod_gr_60.gif].  

    The elements [Graphics:Images/HouseholderMod_gr_61.gif] and [Graphics:Images/HouseholderMod_gr_62.gif] were affected by premultiplication and postmultiplication by [Graphics:Images/HouseholderMod_gr_63.gif].  Additional changes have been introduced to the other elements [Graphics:Images/HouseholderMod_gr_64.gif] by the transformation.  The third Householder transformation,  [Graphics:Images/HouseholderMod_gr_65.gif],  is applied to the matrix [Graphics:Images/HouseholderMod_gr_66.gif] defined in (3) where the Corollary is used with [Graphics:Images/HouseholderMod_gr_67.gif] being the third column of [Graphics:Images/HouseholderMod_gr_68.gif].  The form of [Graphics:Images/HouseholderMod_gr_69.gif] is  

            
[Graphics:Images/HouseholderMod_gr_70.gif]  

Again, the
[Graphics:Images/HouseholderMod_gr_71.gif] identity block ensures that  [Graphics:Images/HouseholderMod_gr_72.gif]  does not affect the elements of [Graphics:Images/HouseholderMod_gr_73.gif], which lie in the upper [Graphics:Images/HouseholderMod_gr_74.gif] corner, and we obtain


            
[Graphics:Images/HouseholderMod_gr_75.gif].  

Thus it has taken three transformations to reduce
[Graphics:Images/HouseholderMod_gr_76.gif] to tridiagonal form.  

    In general, for efficiency, the transformation  [Graphics:Images/HouseholderMod_gr_77.gif]  is not performed in matrix form.  The next result shows that it is more efficiently carried out via some clever vector manipulations.

 

Theorem (Computation of One Householder Transformation)  If [Graphics:Images/HouseholderMod_gr_78.gif] is a Householder matrix, the transformation  [Graphics:Images/HouseholderMod_gr_79.gif]  is accomplished as follows.  Let  

        Let     
[Graphics:Images/HouseholderMod_gr_80.gif]    and compute

                
[Graphics:Images/HouseholderMod_gr_81.gif]  
        and
               
[Graphics:Images/HouseholderMod_gr_82.gif],  
    
        then       
[Graphics:Images/HouseholderMod_gr_83.gif].   

Proof  Householder Method

 

Reduction to Tridiagonal Form

    Suppose that
[Graphics:Images/HouseholderMod_gr_84.gif] is a symmetric [Graphics:Images/HouseholderMod_gr_85.gif] matrix.  Start with
    
            
[Graphics:Images/HouseholderMod_gr_86.gif].  

Construct the sequence  
[Graphics:Images/HouseholderMod_gr_87.gif]  of Householder matrices, so that

             
[Graphics:Images/HouseholderMod_gr_88.gif]    for   [Graphics:Images/HouseholderMod_gr_89.gif],

where
[Graphics:Images/HouseholderMod_gr_90.gif] has zeros below the subdiagonal in columns [Graphics:Images/HouseholderMod_gr_91.gif].  Then [Graphics:Images/HouseholderMod_gr_92.gif] is a symmetric tridiagonal matrix that is similar to [Graphics:Images/HouseholderMod_gr_93.gif].  This process is called Householder's method.

Example 1.  Use Householder's method to reduce the symmetric matrix  [Graphics:Images/HouseholderMod_gr_94.gif]  to symmetric tridiagonal form.  
Solution 1.

 

Algorithm

    Let us combine the steps used in Example 1 and make an algorithm for performing one Householder transformation.

Mathematica Subroutine (One Householder Transformation).  To reduce the [Graphics:Images/HouseholderMod_gr_137.gif] symmetric matrix [Graphics:Images/HouseholderMod_gr_138.gif] to tridiagonal form by using [Graphics:Images/HouseholderMod_gr_139.gif] Householder transformations.

[Graphics:Images/HouseholderMod_gr_140.gif]

Example 2.  Use the Householder step algorithm to reduce the symmetric matrix  [Graphics:Images/HouseholderMod_gr_141.gif]  to symmetric tridiagonal form.  
Solution 2.

 

Exercise 3.  Use the Householder step algorithm to reduce the symmetric matrix  [Graphics:Images/HouseholderMod_gr_152.gif]  to symmetric tridiagonal form.  
Solution 3.

 

Exercise 4.  Use the Householder step algorithm to reduce the symmetric matrix  [Graphics:Images/HouseholderMod_gr_170.gif]  to symmetric tridiagonal form.  
Solution 4.

 

Traditional Programming

    We now present a version of the Householder program that uses traditional more traditional loops to perform the computations.  It also takes into consideration that once a portion of the tridiagonal structure has been created one only needs to continue the process on the submatrix below and to the right.  This program will be harder to read, but might prove to be more efficient when the size of the matrix is larger.  

Computer Programs  Householder Method

Mathematica Subroutine (Householder Reduction to Tridiagonal Form).  To reduce the [Graphics:Images/HouseholderMod_gr_193.gif] symmetric matrix [Graphics:Images/HouseholderMod_gr_194.gif] to tridiagonal form by using [Graphics:Images/HouseholderMod_gr_195.gif] Householder transformations.

[Graphics:Images/HouseholderMod_gr_196.gif]
[Graphics:Images/HouseholderMod_gr_197.gif]
[Graphics:Images/HouseholderMod_gr_198.gif]
[Graphics:Images/HouseholderMod_gr_199.gif]
[Graphics:Images/HouseholderMod_gr_200.gif]

Exercise 5.  Use traditional Householder subroutine to reduce the symmetric matrix  [Graphics:Images/HouseholderMod_gr_201.gif]  to symmetric tridiagonal form.  
Solution 5.

 

Research Experience for Undergraduates

Householder Method  Internet hyperlinks to web sites and a bibliography of articles.  

 

Download this Mathematica Notebook Householder Method

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

(c) John H. Mathews 2005