A8 Linear algebra problems 595
Dense matrices: the Householder methodThe majority of the matrices to be diagonalised in computational physics are Her-
mitian – the elementshijof an Hermitian matrixHsatisfyhij=h∗ji. If a physical
problem leads to a non-Hermitian matrix to be diagonalised, it is always advisable
to try casting the problem in a form such that the matrix becomes Hermitian, as the
diagonalisation is generally more efficient for this case.
Here we restrict ourselves to the subclass of real symmetric matricesSbecause
this procedure is completely analogous to that for the complex Hermitian case.
Diagonalising the matrix involves finding an orthogonal matrixOwhich bringsS
to diagonal forms:
s=OTSO. (A.120)The columns ofOare the eigenvectors, which form an orthonormal set. We first
construct a sequence of matricesOiwhich, when applied one after another in a
fashion as indicated by (A.120), transformSto a tridiagonal form. In the same spirit
as the treatment of the elimination procedure described in the previous section, we
assume that we have brought the matrix to tridiagonal form except for the upper
lefti×iblock and construct the matrixOiwhich tridiagonalisesSone step further.
S′=
sjk ccT sii bi
bi di+ 1 bi+ 1
bi+ 1... ...
... ...
bN− 1
bN− 1 dN
(A.121)
The matrixOiwhich does the job is given by
Oi=I− 2 uuT/(|u|^2 ), (A.122)whereIis theN×Nunit matrix anduis the vector of sizei−1 given in terms
of the vectorcoccurring at the right end and the bottom of the nontridiagonalised
part ofS′with zeroes at positionsi...N:
u=c−|c|ei− 1. (A.123)