Page 130 - Matrix Analysis & Applied Linear Algebra

124 Chapter 3 Matrix Algebra
3.8 INVERSES OF SUMS AND SENSITIVITY

The reverse order law for inversion makes the inverse of a product easy to deal
with, but the inverse of a sum is much more difficult. To begin with, (A + B) −1
may not exist even if A −1 and B −1 each exist. Moreover, if (A + B) −1 exists,
then, with rare exceptions, (A + B) −1
= A −1 + B −1 . This doesn’t even hold
for scalars (i.e., 1 × 1 matrices), so it has no chance of holding in general.
There is no useful general formula for (A+B) −1 , but there are some special
sums for which something can be said. One of the most easily inverted sums is
T
I + cd T in which c and d are n × 1 nonzero columns such that 1 + d c
=0.
It’s straightforward to verify by direct multiplication that
T −1 cd T
I + cd = I − . (3.8.1)
T
1+ d c
T
If I is replaced by a nonsingular matrix A satisfying 1 + d A −1 c
=0, then
the reverse order law for inversion in conjunction with (3.8.1) yields
−1
T
T −1
T −1
(A + cd ) = A(I + A −1 cd ) =(I + A −1 cd ) A −1
−1 T −1 T −1
A cd −1 −1 A cd A
= I − A = A − .
T
T
1+ d A −1 c 1+ d A −1 c
21
This is often called the Sherman–Morrison rank-one update formula because
T
it can be shown (Exercise 3.9.9, p. 140) that rank (cd ) = 1 when c
= 0
= d.
Sherman–Morrison Formula
• If A n×n is nonsingular and if c and d are n × 1 columns such
T
that 1 + d A −1 c
=0, then the sum A + cd T is nonsingular, and
T
−1 A −1 cd A −1
T −1
A + cd = A − . (3.8.2)
T
1+ d A −1 c
• The Sherman–Morrison–Woodbury formula is a generalization. If C
T
and D are n × k such that (I + D A −1 C) −1 exists, then
T −1
T
T
(A + CD ) = A −1 − A −1 C(I + D A −1 C) −1 D A −1 . (3.8.3)
21
This result appeared in the 1949–1950 work of American statisticians J. Sherman and W. J.
Morrison,but they were not the first to discover it. The formula was independently presented
by the English mathematician W. J. Duncan in 1944 and by American statisticians L. Guttman
(1946),Max Woodbury (1950),and M. S. Bartlett (1951). Since its derivation is so natural,it
almost certainly was discovered by many others along the way. Recognition and fame are often
not afforded simply for introducing an idea,but rather for applying the idea to a useful end.