7.5 Similarity Transformations with Householder’s method 221
where the primed quantities represent a matrixA′of dimensionn− 1 which will subsequentely
be transformed byS 2. The factore 1 is a possibly non-vanishing element. The next transforma-
tion produced byS 2 has the same effect asS 1 but now on the submatirxA′only
(S 1 S 2 )TAS 1 S 2 =
a 11 e 1 0 0 ... 0 0
e 1 a′ 22 e 2 0 ... ... 0
0 e 2 a′′ 33 ... ... ...a′′ 3 n
0 ... ... ... ... ...
0 0 a′′n 3 ... ... ...a′′nn
Note that the effective size of the matrix on which we apply the transformation reduces for
every new step. In the previous Jacobi method each similarity transformation is in principle
performed on the full size of the original matrix.
After a series of such transformations, we end with a set of diagonal matrix elements
a 11 ,a′ 22 ,a′′ 33 ...annn−^1 ,and off-diagonal matrix elements
e 1 ,e 2 ,e 3 ,...,en− 1.
The resulting matrix reads
STAS=
a 11 e 1 0 0 ... 0 0
e 1 a′ 22 e 2 0 ... 0 0
0 e 2 a′′ 33 e 3 0 ... 0
... ... ... ... ... ... ...
0 ... ... ... ...a(nn−− 11 n−) 1 en− 1
0 ... ... ... ... en− 1 a(nnn−^1 )
.
It remains to find a recipe for determining the transformationSn. We illustrate the method
forS 1 which we assume takes the form
S 1 =(
10 T
0 P
)
,
with 0 Tbeing a zero row vector, 0 T={ 0 , 0 ,···}of dimension(n− 1 ). The matrixPis symmetric
with dimension ((n− 1 )×(n− 1 )) satisfyingP^2 =IandPT=P. A possible choice which fulfills
the latter two requirements is
P=I− 2 uuT,
whereIis the(n− 1 )unity matrix anduis ann− 1 column vector with normuTu= 1 , that is
its inner product.
Note thatuuTis an outer product giving a dimension ((n− 1 )×(n− 1 )). Each matrix element
ofPthen reads
Pi j=δi j− 2 uiuj,
whereiandjrange from 1 ton− 1. Applying the transformationS 1 results in
ST 1 AS 1 =(
a 11 (Pv)T
Pv A′)
,
wherevT={a 21 ,a 31 ,···,an 1 }andPmust satisfy (Pv)T={k, 0 , 0 ,···}. Then
Pv=v− 2 u(uTv) =ke, (7.6)