Page 357 - Matrix Analysis & Applied Linear Algebra

5.7 Orthogonal Reduction 353
Example 5.7.6
49
Jacobi Reduction. Given a real-symmetric matrix A, the result of Example
5.7.4 shows that Householder reduction can be used to construct an orthogonal
T
matrix P such that P AP = T is tridiagonal. Can we do better?—i.e., can we
T
construct an orthogonal matrix P such that P AP = D is a diagonal matrix?
Indeed we can, and much of the material in Chapter 7 concerning eigenvalues and
eigenvectors is devoted to this problem. But in the present context, this fact can
be constructively established by means of Jacobi’s diagonalization algorithm.
n×n
Jacobi’s Idea. If A ∈ is symmetric, then a plane rotation matrix can
be applied to reduce the magnitude of the off-diagonal entries. In particular,
suppose that a ij =0 is the off-diagonal entry of maximal magnitude, and let

A denote the matrix obtained by setting each a kk =0. If P ij is the plane
rotation matrix described on p. 333 in which c = cos θ and s = sin θ, where
T
cot 2θ =(a ii − a jj )/2a ij , and if B = P AP ij , then
ij
(1) b ij = b ji =0 (i.e., a ij is annihilated),
2
2
2
(2) B = A − 2a ,
F F ij

2 2 2
(3) B ≤ 1 − A .
F n − n F
2
T
Proof. The entries of B = P AP ij that lay on the intersection of the i th and
ij
j th rows with the i th and j th columns can be described by

T ˆ
ˆ
B = b ii b ij = cos θ sin θ a ii a ij cos θ − sin θ = P AP.
b ji b jj − sin θ cos θ a ij a jj sin θ cos θ
2
2
Use the identities cos 2θ = cos θ − sin θ and sin 2θ =2 cos θ sin θ to verify
ˆ
ˆ
T ˆ
b ij = b ji =0, and recall that B F = P AP F = A F (recall Exercise
49
Karl Gustav Jacob Jacobi (1804–1851) first presented this method in 1846, and it was popular
for a time. But the twentieth-century development of electronic computers sparked tremendous
interest in numerical algorithms for diagonalizing symmetric matrices, and Jacobi’s method
quickly fell out of favor because it could not compete with newer procedures—at least on the
traditional sequential machines. However, the emergence of multiprocessor parallel computers
has resurrected interest in Jacobi’s method because of the inherent parallelism in the algorithm.
Jacobi was born in Potsdam, Germany, educated at the University of Berlin, and employed as
a professor at the University of K¨onigsberg. During his prolific career he made contributions
that are still important facets of contemporary mathematics. His accomplishments include the
development of elliptic functions; a systematic development and presentation of the theory
of determinants; contributions to the theory of rotating liquids; and theorems in the areas of
differential equations, calculus of variations, and number theory. In contrast to his great con-
temporary Gauss, who disliked teaching and was anything but inspiring, Jacobi was regarded
as a great teacher (the introduction of the student seminar method is credited to him), and
he advocated the view that “the sole end of science is the honor of the human mind, and that
under this title a question about numbers is worth as much as a question about the system
of the world.” Jacobi once defended his excessive devotion to work by saying that “Only cab-
bages have no nerves, no worries. And what do they get out of their perfect wellbeing?” Jacobi
suffered a breakdown from overwork in 1843, and he died at the relatively young age of 46.