Symmetric Positive Definite Matrix Plus Symmetric Matrix is again Positive Definite

Let $$|| \cdot ||$$ be a matrix norm (need not to be induced or submultiplicative), $$A \in \mathbb{R}^{n \times n}$$ a symmetric, positive definite, (therefore invertible) matrix and $$B \in \mathbb{R}^{n \times n}$$ be just a symmetric matrix.

Show that if $$||A^{-1}|| \cdot ||B|| < 1$$ then $$A + B$$ is positive definite.

Hint: If $$t \mapsto A(t) \in \mathbb{R}^{n \times n}$$ is a continuous function, there are continuous functions which maps $$t$$ to each Eigenvalues of $$A$$.

I just don't have much of an idea where to start. Since the norm need not to be submultiplicative, I can't say $$||A^{-1}|| \geq (||A||)^{-1}$$. I don't know how to use the hint and using the diagonalization of the matrices doesn't seem to help.

EDIT: The things I wrote below, I don't think that even holds because you probably need again the submultiplicative property to conclude that.

Only thing I noticed was that $$||A^{-1}|| \cdot ||B|| < 1 \\ \Rightarrow ||D_{A^{-1}}|| \cdot ||D_B|| < 1$$

where $$D_{A^{-1}}$$ and $$D_B$$ are the diagonal form of the matrices with Eigenvalues as their entries, but since the norm is not induced, I don't know how this could help.

Thank you very much for your help.

• This isn't true. For any matrices $A$ and $B$, we can always pick a norm such that $\|A^{-1}\|\|B\|<1$ (e.g. pick $\|X\|=\epsilon\|X\|_F$ for some sufficiently small $\epsilon>0$), but clearly, $A+B$ is not always positive definite. Nov 24 '19 at 15:46
• Thank you and I think you are right. The problem didn't specify it, but the given norm must be induced (and submultiplicative). I'll try to prove the statement with that condition.
– matt
Nov 25 '19 at 0:56

As already pointed out, this is not true for a general matrix norm. We can develop an elementary proof and see what assumptions come up. We will show, using the hint, that if $$A+B$$ is not SPD, then $$\|A^{-1}\|\|B\|\geq 1$$.
Assume that $$A+B$$ is not positive definite, that is, it has at least one non-positive eigenvalue. Let $$f(t):=A+tB$$ where $$t$$ is a real scalar. Note that $$A=f(0)$$ is positive definite and $$A+B=f(1)$$ is not. Since the eigenvalues of $$f$$ are continuous functions of $$t$$, there is a $$t_*\in(0,1]$$ such that $$f(t_*)$$ has a zero eigenvalue.
Let $$\|\cdot\|_😈$$ be a vector norm. There exists an $$x$$ such that $$\|x\|_😈=1$$ and $$(A+t_*B)x=0$$, so $$x=-t_*A^{-1}Bx$$ and $$1=\|x\|_😈=|t_*|\|A^{-1}Bx\|_😈\leq\|A^{-1}Bx\|_😈.$$ Now if a matrix norm $$\|\cdot\|_😃$$ is consistent with the vector norm $$\|\cdot\|_😈$$, we have that $$1\leq\|A^{-1}B\|_😃.$$
This means that if $$\|A^{-1}B\|_😃<1$$, then $$A+B$$ is SPD.
If you add sub-multiplicativity to your assumptions on the matrix norm, a sufficient condition is that $$\|A^{-1}\|_😃\|B\|_😃<1.$$