6

I have an old test question that I am not sure about and would like some idea. It is from a Numerical Analysis class.

Suppose that $A$ is an invertible $n$-by-$n$ matrix. Prove that for every $n$-by-$n$ matrix $B$, the inequality $$ \|\mathbf{B} - \mathbf{A}\| \lt \frac{1}{\|\mathbf{A}^{-1}\|}$$ implies that $B$ is invertible.

I answered the test question correctly, but am also interested in what this particular equation could be used for.

EDIT: Here is what I did on my test (the test did give a hint to use the contrapositive):

Suppose $A$ is invertible and $B$ is singular. Then for some $x \ne 0$, we have $Bx = 0$

Note that $$\begin{align} 0 \ne & \| x\| & = & \| A^{-1}Ax\| \\ && = & \|A^{-1}(Ax - Bx)\| \\ && = & \|A^{-1}(A-B)x\| \\ && \le & \|A^{-1}\|\cdot\|(A-B)x\| \\ \implies & \|x\| & \le & \|A^{-1}\|\cdot\|A-B\| \cdot \|x\|\\ \\ \implies & \frac{ \|x\|}{\|x\|} & \le & \|A^{-1}\|\cdot\|A-B\| \cdot \frac{\|x\|}{\|x\|} \,\,\,\,\text{since $\|x\| \ne 0$} \\ \implies & 1 & \le & \|A^{-1}\|\cdot\|A-B\| \\ \implies & \frac{ 1}{\|A^{-1}\|} & \le & \|A-B\| \\ \therefore & B \;\text{singular} \implies && \|A-B\| \ge \frac{1}{A^{-1}} \\ \text{By contrapositive argument,}&\text{ we have} \\ &\|A-B\|& \lt &\frac{1}{\|A^{-1}\|} \implies \text{$B$ is invertible}\\ \end{align} $$

Shaza
  • 61

3 Answers3

4

It shows that the set of invertible matrices is an open set: If a matrix $A$ is invertible, there exists a neighborhood such that all matrices $B$ in this neighborhood are invertible as well.

Furthermore this proof can fairly easily be generalized to the infinite-dimensional case, where $A$ and $B$ are bounded linear operators on a Banach space.

Florian
  • 5,243
4

This is a standard result. If $\|\Delta\| <1$, and $\|\cdot\|$ is a sub-multiplicative norm, then we have $\|I+\Delta+...+\Delta^n\| \le 1 +\|\Delta\| + ... + \|\Delta\|^n = { 1-\|\Delta\|^{n+1} \over 1-\|\Delta\|} \le { 1 \over 1-\|\Delta\|}$. Hence we have that $D = \sum_{k=0}^\infty \Delta^k$ exists, and furthermore, since $(I-\Delta) (I+\Delta+...+\Delta^n) = I-\Delta^{n+1}$, we see that $(I-\Delta) D = I$. That is, $D$ is the inverse of $I-\Delta$.

Now suppose $A$ is invertible, and $\|H\| < {1 \over \|A^{-1}\|}$. Then, since we have $A+H = A(I+A^{-1}H)$, we see that $A+H$ is invertible iff $(I+A^{-1}H)$ is invertible. Furthermore, since $\|A^{-1}H\| \le \|A^{-1}\| \|H\|$, we have $\|A^{-1}H\| < 1$. Hence $(I+A^{-1}H)$ is invertible.

In the question, let $H=B-A$.

copper.hat
  • 172,524
  • How does bounding a matrix's norm prove that it exists? For $D$, I mean. – Zduff Jun 06 '18 at 20:06
  • 1
    @Zduff: It doesn't, it was a sloppy argument. What I meant to show is that the sum $\sum_{k=0}^\infty \Delta^k$ is Cauchy, hence completeness shows that $D$ exists. I was lax because it is a standard geometric series sort of argument. – copper.hat Jun 06 '18 at 20:58
2

This result is from Ortega and Rheinboldt, 1970, Iterative Solution of Nonlinear Equations in Several Variables (Lemma 2.3.2). There are sure to be other proofs, but I like this one.

We start with the following preliminary result (which you can find in the above book).

$\textbf{Lemma 1}$ Let $B \in L(\mathbb{R}^{n})$ and assume that $\rho(B) < 1$, where $\rho(B)$ is the spectral radius of $B$. Then $(I - B)^{-1}$ exists.

Using this we now use the fact that

$\displaystyle || A - B || < \frac{1}{|| A ||^{-1}}$

and note that

$|| I - A^{-1}B || = || A^{-1}(A - B) || \leq || A^{-1} ||\,|| A - B || < 1.$

Hence, using Lemma 1 we have that

$A^{-1}B = I - (I - A^{-1}B)$

is invertible, so therefore $B$ must also be invertible

Keeran Brabazon
  • 787
  • 3
  • 11