Householder Transformations

The element denoted is changed because of premultiplication by , and is changed because of postmultiplication by ; since is symmetric, we have .The changes to the elements denotedhave been affected by both premultiplication and postmultiplication.Also, since is the first column of , equation (1) implies that.

The second Householder transformation is applied to the matrix defined in (2) and is denoted,where is constructed by applying the Corollary with the vector being the second column of the matrix .The form of is



where stands for some element in .The 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 .The outcome of this transformation is

(3).

The elements and were affected by premultiplication and postmultiplication by .Additional changes have been introduced to the other elements by the transformation.The third Householder transformation,,is applied to the matrix defined in (3) where the Corollary is used with being the third column of .The form of is



Again, the identity block ensures thatdoes not affect the elements of , which lie in the upper corner, and we obtain


.

Thus it has taken three transformations to reduce to tridiagonal form.

In general, for efficiency, the transformationis 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 is a Householder matrix, the transformationis accomplished as follows.Let

Letand compute


and
,

then.

Reduction to Tridiagonal Form

Suppose that is a symmetric matrix.Start with

.

Construct the sequenceof Householder matrices, so that

for,

where has zeros below the subdiagonal in columns .Then is a symmetric tridiagonal matrix that is similar to .This process is called Householder's method.