**for**

**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
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

.

**Proof** **Householder
Method**

**Remark.** It
should be observed that the effect of the mapping
is to reflect
through the line whose direction is ,
hence the name Householder reflection.

**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) .

**Proof** **Householder
Method**

**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 .

**Proof** **Householder
Method**

**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.

**Example
1.** Use
Householder's method to reduce the symmetric
matrix 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
symmetric matrix
to tridiagonal form by using
Householder transformations.

**Example
2.** Use the
Householder step algorithm to reduce the symmetric
matrix to
symmetric tridiagonal form.

**Solution
2.**

**Exercise
3.** Use the
Householder step algorithm to reduce the symmetric
matrix to
symmetric tridiagonal form.

**Solution
3.**

**Exercise
4.** Use the
Householder step algorithm to reduce the symmetric
matrix 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
symmetric matrix
to tridiagonal form by using
Householder transformations.

**Exercise 5.** Use
traditional Householder subroutine to reduce the symmetric
matrix 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