Inverse of sum of matrices has lower norm than the inverse of summand(s)

Question

For symmetric $\mathbf{A}, \mathbf{B} \in \mathbb{R}^{m\times m}$ and $\mathbf{c}\in \mathbb{R}^{m\times 1}$, when $\mathbf{A}\succ 0$ and $\mathbf{B}\succeq 0$, I want to show that \begin{align*} \|(\mathbf{A} + \mathbf{B})^{-1}\mathbf{c}\| \leq \|\mathbf{A}^{-1}\mathbf{c}\|. \end{align*} I have a feeling it would have something to do with determinants or eigenvalues, but I am not sure how to go about the proof.

Answer 1

Here's a counterexample:

$$ \mathbf A = \left[\begin{matrix}5 & -3\\-3 & 5\end{matrix}\right],\quad \mathbf B = \left[\begin{matrix}1 & 0\\0 & 0\end{matrix}\right], \quad \mathbf c = \left[\begin{matrix}3\\-4\end{matrix}\right]. $$ We find that $$ \|(\mathbf{A} + \mathbf B)^{-1}\mathbf c\|^2 \approx \|\mathbf A^{-1}\mathbf c\| + .023 $$

Here's the script I used to generate a "nice" counterexample:

import numpy as np
from numpy.random import randint, rand
from scipy.linalg import norm, inv, det, eig
from sympy import Matrix, latex

for _ in range(100):
    ran = 2
    L = randint(-ran,ran+1,size=[2,2])
    A = [email protected]
    L = randint(-ran,ran+1,size = [2,1])
    B = [email protected]
    try:
        M = inv(A@A) - inv((A+B)@(A+B)) 
    except:
        continue
    if det(M) < -1e-6:
        print(A)
        print(B)
        break
else:
    print('none found')

Once you have a suitable $A$ and $B$, a suitable vector $c$ can be found taking $c$ equal to the eigenvector of $M = A^{-2} - (A+B)^{-2}$ associated with a negative eigenvalue (why?). By rounding the entries of a multiple of this vector $c$, we can get a "nicer" suitable vector $c$.