## Monday, February 1, 2010

### Householder's Method

If and are vectors with the same norm, there exists an orthogonal symmetric matrix such that

,
where

and
.

Since is both orthogonal and symmetric, it follows that

.

Corollary ( Householder Matrix)

Let be an matrix, and any vector. If is an integer with , we can construct a vector and matrix so that

(1) .

Householder Transformations

Suppose that
is a symmetric matrix. Then a sequence of transformations of the form will reduce to a symmetric tridiagonal matrix. Let us visualize the process when . The first transformation is defined to be , where is constructed by applying the above Corollary with the vector being the first column of the matrix . The general form of is

where the letter
stands for some element in . As a result, the transformation does not affect the element of :

(2) .

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 denoted have 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 that does 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 transformation 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 is a Householder matrix, the transformation is accomplished as follows. Let

Let
and compute

and
,

then
.

Reduction to Tridiagonal Form

Suppose that
is a symmetric matrix. Start with

.

Construct the sequence
of 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.