14.4. THE CONDITION NUMBER∗ 341

Lemma 14.4.2 Let A,B be m× n matrices such that A−1 exists, and suppose ||B|| <1/∣∣∣∣A−1

∣∣∣∣ . Then (A+B)−1 exists and∥∥∥(A+B)−1∥∥∥≤ ∥∥A−1∥∥∣∣∣∣ 1

1−||A−1B||

∣∣∣∣ .The above formula makes sense because

∥∥A−1B∥∥< 1.

Proof: By Lemma 14.4.1,∥∥A−1B∥∥≤ ∥∥A−1∥∥∥B∥< ∥∥A−1∥∥ 1

∥A−1∥ = 1

Suppose (A+B)x = 0. Then 0 = A(I +A−1B

)x and so since A is one to one,(

I +A−1B)

x = 0.

Therefore,

0 =∥∥(I +A−1B

)x∥∥≥ ∥x∥−∥∥A−1Bx

∥∥≥ ∥x∥−

∥∥A−1B∥∥∥x∥= (1−∥∥A−1B

∥∥)∥x∥> 0

a contradiction. This also shows(I +A−1B

)is one to one. Therefore, both (A+B)−1 and(

I +A−1B)−1 exist. Hence

(A+B)−1 =(A(I +A−1B

))−1=(I +A−1B

)−1A−1

Now ifx =

(I +A−1B

)−1 y

for ∥y∥ ≤ 1, then (I +A−1B

)x = y

and so∥x∥

(1−∥∥A−1B

∥∥)≤ ∥∥x+A−1Bx∥∥≤ ∥y∥= 1

and so||x||=

∥∥∥(I +A−1B)−1 y

∥∥∥≤ 11−∥A−1B∥

Since ||y|| ≤ 1 is arbitrary, this shows∥∥∥(I +A−1B)−1∥∥∥≤ 1

1−∥A−1B∥

Therefore,∥∥∥(A+B)−1∥∥∥ =

∥∥∥(I +A−1B)−1

A−1∥∥∥

≤∥∥A−1∥∥∥∥∥(I +A−1B

)−1∥∥∥≤ ∥∥A−1∥∥ 1

1−∥A−1B∥■