# Householder Method for Tridiagonalization: Ver. 1.0

Taisuke Ozaki, RCIS, JAIST

The Householder method [1] is a way of transforming a Hermitian matrix to a real symmetric tridiagonalized matrix . Let be a column vector of , and consider that the vector consists of the real part and the imaginary part as
 (1)

Also let us introduce a vector of which real part has just one non-zero component and imaginary part is a zero vector as
 (2)

Then, consider a mirror transform bridging the two vectors and by
 (3)

where let us assume that
 (4)

Putting Eq. (3) into Eq. (4), and solving it with respect to , we have
 (5)

Thus, Eq. (5) allows us to write as
 (6)

If is normalized, is given by
 (7)

Comparing Eqs. (5) with (6) and making use of Eq. (7), we have
 (8)

with and given by
 (9)

and
 (10)

Then, it is verified that
 (11)

Thus, the transformation for the Hermitian matrix is a similarity transformation, and given by
 (12)

By defining
 (13)

Eq. (12) becomes
 (14)

Moreover, by defining
 (15)

we have a compact form:
 (16)

For the numerical stability, we furthermore modify Eq. (16) as shown below. Let us introduce a vector as.
 (17)

Then, can be written by as
 (18)

Also, noting that
 (19)

can be rewritten by
 (20)

Putting Eqs. (19) and (20) into Eq. (16), we have
 (21)

with defined by
 (22)

where
 (23)

The transformation by Eq. (21) can be applied to each column vector step by step in which the place occupied by in Eq. (2) is shifted one by one. Then, the tridiagonalized matrix is given by
 (24)

## Bibliography

1
A. S. Householder, J. ACM 5, 339 (1958).

2007-08-18