Page 233 - Advanced Linear Algebra

Real and Complex Inner Product Spaces 217

Theorem 9.12 Let ( C ²-³ , where - ~ d Á or - ~ s . There exists a
²-³ with orthonormal columns and an upper triangular
matrix 8 C Á
matrix 9 C ²-³ with nonnegative real entries on the main diagonal for
which
(~ 89
8
Moreover, if ~ , then is unitary/orthogonal. If is nonsingular, then 9
(
can be chosen to have positive entries on the main diagonal, in which case the
factors 8 and 9 are unique. The factorization ( ~ 8 9 is called the 89
factorization of the matrix . If is real, then and may be taken to be
(
9
8
(
real.
Proof. As to uniqueness, if is nonsingular and 9 8 ~ 8 9 then
(
c
88 ~ 9 9 c

and the right side is upper triangular with nonzero entries on the main diagonal
and the left side is unitary. But an upper triangular matrix with positive entries
on the main diagonal is unitary if and only if it is the identity and so 8~ 8

and 9~ 9 . Finally, if is real, then all computations take place in the real
(

8
field and so and are real.
9
The 89 decomposition has important applications. For example, a system of
linear equations (% ~ " can be written in the form
89% ~ "
and since 8 c ~ 8 i , we have
i
9% ~ 8 "
This is an upper triangular system, which is easily solved by back substitution;
that is, starting from the bottom and working up.
We mention also that the 89 factorization is associated with an algorithm for
approximating the eigenvalues of a matrix, called the 89 algorithm .
Specifically, if (~ ( is an d matrix, define a sequence of matrices as
follows:

1) Let (~ 8 9 be the 89 factorization of ( and let (~ 9 8 .

2) Once ( has been defined, let ( ~ 8 9 be the 9 8 factorization of (
and let ( ~ b 9 8 .
Then ( is unitarily/orthogonally similar to , since
(
8 ( c 8 i c ~ 8 ² c 9 8 c ³ c 8 i c ~ 8 9 c ~ c ( c
For complex matrices, it can be shown that under certain circumstances, such as
when the eigenvalues of have distinct norms, the sequence ( converges
(