Page 222 - Matrix Analysis & Applied Linear Algebra

4.5 More about Rank 217

Proof. Suppose rank (A)= r, and let P and Q be nonsingular matrices
0
that reduce A to rank normal form—i.e., PAQ = I r . If P and Q are
0 0

applied to E to form PEQ = E 11 E 12 , where E 11 is r × r, then
E 21 E 22

I r + E 11 E 12
P(A + E)Q = . (4.5.10)
E 21 E 22
If the magnitude of the entries in E are small enough to insure that E k 11 → 0
as k →∞, then the discussion of the Neumann series on p. 126 insures that
I + E 11 is nonsingular. (Exercise 4.5.14 gives another condition on the size of
E 11 to insure this.) This allows the right-hand side of (4.5.10) to be further
reduced by writing
−1
I 0 I + E 11 E 12 I −(I + E 11 ) E 12 I − E 11 0
−E 21 (I + E 11 ) −1 I E 21 E 22 0 I = 0 S ,

−1
where S = E 22 − E 21 (I + E 11 ) E 12 . In other words,

I − E 11 0
A + E ∼ ,
0 S
and therefore

rank (A + E)= rank (I r + E 11 )+ rank (S) (recall Example 3.9.3)
= rank (A)+ rank (S) (4.5.11)
≥ rank (A).

Example 4.5.3
A Pitfall in Solving Singular Systems. Solving Ax = b with floating-
point arithmetic produces the exact solution of a perturbed system whose coeffi-
cient matrix is A+E. If A is nonsingular, and if we are using a stable algorithm
(an algorithm that insures that the entries in E have small magnitudes), then
(4.5.9) guarantees that we are finding the exact solution to a nearby system that
is also nonsingular. On the other hand, if A is singular, then perturbations of
even the slightest magnitude can increase the rank, thereby producing a system
with fewer free variables than the original system theoretically demands, so even
a stable algorithm can result in a significant loss of information. But what are
the chances that this will actually occur in practice? To answer this, recall from
(4.5.11) that

−1
rank (A + E)= rank (A)+ rank (S), where S = E 22 − E 21 (I + E 11 ) E 12 .