12
HOUSEHOLDER ORTHONORMAL
TRANSFORMATION
In the preceding chapter we showed how the elementary Givens orthonormal
transformation triangularized a matrix by successfully zeroing out one element
at a time below the diagonal of each column. With the Householder
orthonormal transformation all the elements below the diagonal of a given
column are zeroed out simultaneously with one Householder transformation.
Specifically, with the first Householder transformation H
1
, all the elements
below the first element in the first column are simultaneously zeroed out,
resulting in the form given by (11.1-4). With the second Householder
transformation H
2
all the elements below the second element of the second
column are zeroed out, and so on.
The Householder orthonormal transformation requires fewer multiplies and
adds than does the Givens transformation in order to obtain the transformed
upper triangular matrix of (10.2-8) [103]. The Householder transformation,
however, does not lend itself to a systolic array parallel-processor type of
implementation as did the Givens transformation. Hence the Householder may
be preferred when a centralized processor is to be used but not if a custom
systolic signal processor is used.
12.1 COMPARISON OF HOUSEHOLDER AND GIVENS
TRANSFORMATIONS
Let us initially physically interpret the Householder orthonormal transformation
as transforming the augmented matrix T
0
to a new coordinate system, as we did
for the Givens transformations. For the first orthonormal Householder trans-

formation H
1
the s rows are unit vectors, designated as h
i
for the ith row, onto
315
Tracking and Kalman Filtering Made Easy. Eli Brookner
Copyright # 1998 John Wiley & Sons, Inc.
ISBNs: 0-471-18407-1 (Hardback); 0-471-22419-7 (Electronic)
which the columns of T
0
are projected. The first-row vector h
1
is chosen to line
up with the vector formed by the first column of T
0
; designated as t
1
. Hence, the
projection of t
1
onto this coordinate yields a value for the first coordinate in the
transformed space equal to the full length of t
1
, that is, equal to k t
1
k. The
remaining s À 1 unit row vectors of H
i
, designated as h

i
, i ¼ 2; ...; s, are
chosen to be orthonormal to h
1
: As a result they are orthonormal to t
1
since h
1
lines up with t
1
. Hence the projections of t
1
onto the h
i
; i ¼ 2; ...; s, are all
zero. As a result H
1
T
0
produce a transformed matrix of the form given by
(11.1-4) as desired. This is in contrast to the simple Givens transformations
G
1
; G
2
; ...; G
sÀ1
of the left-hand side of (11.1-4), which achieves the same
outcome as H
1

does but in small steps. Here, G
1
first projects the column
vector t
1
of T
0
onto a row space that is identical to that of the column space of
T
0
with the exception of the first two coordinates. The first two coordinates,
designated in Figure 11.1-2a as the x, y coordinates, are altered in the new
coordinate system defined by G
1
. The first of these two new coordinates, whose
direction is defined by the first-row unit vector g
1
,ofG
1
, is lined up with
the vector formed by the first two coordinates of t
1
, designated as

t
0
; see
(11.1-1) and Figure 11.1-2a. The second of these new coordinates,
whose direction is defined by the second-row unit vector g
2

of G
1
,is
orthogonal to g
1
and in turn

t
0
, but in the plane defined by the first two
coordinates of t
1
, that is, the x, y plane. As a result G
1
T
0
gives rise to the
form given by (11.1-2).
The second Givens transformation G
2
projects the first-column vector ðt
1
Þ
1
of G
1
T
0
onto a row space identical to that of ðt
1

Þ
1
except for the first and third
coordinates. The first-row unit vector ðg
1
Þ
2
of G
2
is lined up with the direction
defined by the vector formed by the first and third coordinates of G
1
T
0
. This
vector was designated as

t
2
; see (11.1-16) and Figures 11.1-2b,c. From the
definition of

t
2
recall also that it is lined up with the first three coordinates of t
1
.
The third-row unit vector ðg
3
Þ

2
is lined up in a direction orthogonal to ðg
1
Þ
2
in
the two-dimensional space formed by the first and third coordinates of the
vector ðt
1
Þ
2
; see Figures 11.1-2b,c. As a result the projection of ðt
1
Þ
1
onto the
row space of G
2
gives rise to the form given by (11.1-3). Finally, applying the
third Givens transformation G
3
yields the desired form of (11.1-4) obtained
with one Householder transformations H
1
: For this example T
0
is a 4 Â 3
matrix, that is, s ¼ 4: For arbitrary s; s À 1 simple Givens transformations
G
1

; ...; G
sÀ1
achieve the same form for the transformed matrix that one
Householder transformation H
1
does, that is,
H
1
 G
sÀ1
ÁÁÁG
2
G
1
ð12:1-1Þ
Elements on the right and left hand sides of (12.1-1) will be identical except the
sign of corresponding rows can be different if the unit row transform vectors of
these transforms have opposite directions; see Section 13.1.
Let us recapitulate what the Givens transformations are doing. The first, G
1
,
projects T
0
onto a space whose first coordinate unit vector g
1
(defined by the
316
HOUSEHOLDER ORTHONORMAL TRANSFORMATION
first row of G
1

; see Section 11.1) lines up with the direction of the two-
dimensional vector formed by the first two coordinates of t
1
. The second
coordinate of the new space is along the unit vector g
2
(defined by the
second row of G
1
) orthogonal to the first coordinate but in the plane defined
by the first two coordinates of t
1
. The remaining coordinates of the space
defined by G
1
are unchanged. In this transformed space the second coordinate
of t
1
is zero; see (11.1-2). This in effect replaces two coordinates with one
for the first two coordinates of t
1
, the other coordinate being zero. The next
Givens transformation now projects the transformed t
1
, which is ðt
1
Þ
1
, onto
the row space of G

2
. Here the first-row unit vector ðg
1
Þ
2
of G
2
is lined up
with the vector formed by first and third coordinates of ðt
1
Þ
1
, which is
designated as

t
2
in (11.1-16) and Figures 11.1-2b,c. Again the second
coordinate is orthogonal to the first but in the plane defined by the first
and third coordinates of ðt
1
Þ
1
. In this new coordinate system the second
and the third coordinates of t
1
are zero; see (11.1-3). This simple Givens
transformation again replaces two coordinates of ðt
1
Þ

1
, the first and third,
with one, the second being zero. The first and second simple Givens transfor-
mations together in effect line up the first row of G
1
G
2
with the vector
formed by the first three coordinates of t
1
. This continues until on the
s À 1 Givens transformation the unit vector formed by the first row of
G
sÀ1
ÁÁÁG
2
G
1
lines up with the vector formed by t
1
to produce the form
given by (11.1-4). In a similar way, the first Householder transformation
H
1
does in one transformation what s À 1 simple Givens transformations
do. Similarly H
2
does in one transformation what s À 2 Givens transfor-
mations do; and so on.
12.2 FIRST HOUSEHOLDER TRANSFORMATION

We now develop in equation form the first Householder transformation H
1
.A
geometric development [80, 102, 109, 114] is used in order to give further
insight into the Householder transformation. Consider the s Âðm
0
þ 1Þ
dimensional augmented matrix T
0
whose columns are of dimension s.As
done previously, we will talk of the columns as s-dimensional vectors in
s-dimensional hyperspace. Designate the first column as the vector t
1
. Form
h
0
given by
h
0
¼ t
1
þkt
1
k i ð12:1-2Þ
where i is the unit vector along the x axis of this s-dimensional hyperspace,
that is, the column space of T
0
; see Figure 12.1-1. The vector i is given by
(4.2-38) for s ¼ 3. Physically let us view the first Householder transformation
H

1
as a rotation of t
1
. Then i in Figure 12.1-1 is the direction into which we
want to rotate t
1
in order to have the transformed t
1
, designated as ðt
1
Þ
1H
,be
FIRST HOUSEHOLDER TRANSFORMATION
317
given by
ðt
1
Þ
1H
¼ H
1
t
1
¼½kt
1
k 00 ÁÁÁ 0
T
ð12:1-3Þ
that is, in order for the first column of H

1
T
0
to have the form given by the
first column of (11.1-4). In Figure 12.1-1, the vector h
0
forms the horizontal
axis, which is not the x axis that is along the unit vector i. Because H
1
t
1
in
Figure 12.1-1 is the mirror image of t
1
about this horizontal axis, the
Householder transformation is called a ‘‘reflection.’’
Let h be the unit vector along h
0
; then
h ¼
h
0
k h
0
k
ð12:1-4Þ
Let t
1c
be the component of t
1

along the direction h. Then
t
1c
¼ðt
T
1
hÞh ð12:1-5Þ
Designate t
1s
as the component of t
1
along the direction perpendicular to h but
in the plane formed by t
1
and i. Then
t
1s
¼ t
1
À t
1c
¼ t
1
Àðt
T
1
hÞh
ð12:1-6Þ
Figure 12.1-1 Householder reflection transformation H
1

for three-dimensional space.
318
HOUSEHOLDER ORTHONORMAL TRANSFORMATION
Then from geometry (see Figure 12.1-1)
H
1
t
1
¼ t
1c
À t
1s
¼ðt
T
1
hÞh À½t
1
Àðt
T
1
hÞh
¼ 2ðt
T
1
hÞh À t
1
¼ 2hðt
T
1
hÞÀt

1
¼ 2hh
T
t
1
À t
1
¼ 2hh
T
À I
ÂÃ
t
1
ð12:1-7Þ
Hence
H
1
¼ 2hh
T
À I ð12:1-8Þ
By picking h as given by (12.1-2) and (12.1-4), the vector t
1
is rotated (actually
reflected) using (12.1-8) onto i as desired. After the reflection of t
1
the vector
has the same magnitude as it had before the reflection, that is, its magnitude is
given by k t
1
k. Moreover, as desired, the magnitude of the first element of

the transformed vector ðt
1
Þ
1H
has the same magnitude value as the original
vector t
1
with the value of the rest of the coordinate elements being zero.
Specifically
H
1
t
1
¼ H
1
t
11
t
21
.
.
.
t
s1
2
6
6
6
6
4

3
7
7
7
7
5
¼
k t
1
k
0
0
.
.
.
0
2
6
6
6
6
4
3
7
7
7
7
5
¼ðt
1

Þ
1H
ð12:1-9Þ
where
k t
1
k¼ ðjt
11
j
2
þjt
11
j
2
þÁÁÁþjt
s1
j
2
Þ
1=2
ð12:1-9aÞ
The subscript 1 on H is used to indicate that this is the first House-
holder transformation on the matrix T
0
, with more Householder transforms
to follow in order to zero out the elements below the remaining diagonal
elements.
In the above we have only talked about applying the s  s Householder
transformation H
1

matrix to the first column of T
0
. In actuality it is applied to
all columns of T
0
. This is achieved by forming the product H
1
T
0
. Doing this
yields a matrix of the form given by the right-hand side of (11.1-4) as desired.
In this way we have physically reflected the first column of T
0
onto the first
coordinate of the column space of T
0
(the x coordinate) by the use of the
Householder transformation H
1
.
FIRST HOUSEHOLDER TRANSFORMATION
319