2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – user1551
    Nov 24, 2019 at 15:46
  • $\begingroup$ 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. $\endgroup$
    – matt
    Nov 25, 2019 at 0:56

1 Answer 1

2
$\begingroup$

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.$$

$\endgroup$

Your Answer

By clicking β€œPost Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.