Given $a,b,x > 0$ I know following the submodularity property holds: \begin{align} \frac{1}{a} - \frac{1}{a+x} \geq \frac{1}{a+b} - \frac{1}{a+b+x} \end{align} My question is, does this property hold for matrices? Precisely, for $A,B,X \succ 0$ is it the case that: \begin{align} A^{-1} - (A+X)^{-1} \succeq (A+B)^{-1} - (A+B+X)^{-1} \end{align} By '$\succeq$' I mean that if $A \succeq B$ then $A−B \succeq 0$, or, is positive semi-definite.
$\begingroup$
$\endgroup$
4
-
$\begingroup$ Already the version for real numbers is false -- e.g. for $a=b=x=1$ the left hand side is $1/2$, while the right hand side is $5/6$. $\endgroup$– Stefan Kohl ♦Commented Feb 9, 2015 at 17:10
-
$\begingroup$ My apologies I meant subtraction on the right side which holds 1/2 > 1/6, will fix this now $\endgroup$– OttoVonBismarckCommented Feb 9, 2015 at 17:38
-
$\begingroup$ O.k., now after your edit, the version for real numbers is correct. But which relator do you mean by $\succeq$ for matrices? -- And what entries are your matrices supposed to have? $\endgroup$– Stefan Kohl ♦Commented Feb 9, 2015 at 18:09
-
$\begingroup$ The entries of the matrices could be any real numbers. By '$\succeq$' I mean that if $A \succeq B$ then $A - B \succeq 0$, or, is positive semi-definite. $\endgroup$– OttoVonBismarckCommented Feb 9, 2015 at 19:01
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
6
Consider $$ A = \pmatrix{1 & 0\cr 0 & 1\cr},\ X = \pmatrix{1 & 0\cr 0 & 0\cr},\ B = \pmatrix{1 & 1\cr 1 & 1\cr}$$ $$ \eqalign{A^{-1} &- (A+X)^{-1} = \pmatrix{1/2 & 0\cr 0 & 0\cr}\cr &\not\succeq (A+B)^{-1} - (A+X+B)^{-1} = \pmatrix{4/15 & -2/15 \cr -2/15 & 1/15}}$$ Yes, I know $B$ and $X$ are positive semidefinite rather than positive definite; add $\epsilon I$ for $\epsilon $ sufficiently small.
answered Feb 9, 2015 at 21:14
-
$\begingroup$ Ah very good, I see. Do you know if the above inequality then holds instead for $A, B, X \succ I$, where $I$ is the identity matrix? $\endgroup$ Commented Feb 9, 2015 at 22:06
-
$\begingroup$ It does not. Take any counterexample with $A, B, X$ positive definite and scale appropriately. $\endgroup$ Commented Feb 10, 2015 at 2:20
-
$\begingroup$ I'm confused, for your example above if we define $A_2 = A + I$ and $B_2 = B + (1+\epsilon)I$ and $X_2 = X + (1+\epsilon)I$ then the inequality does hold: $A_2^{-1} - (A_2 + X_2)^{-1} \succeq (A_2 + B_2)^{-1} - (A_2 + B_2 + X_2)^{-1}$. I do not have a proof (certainly) but I could not find an epsilon for which this did not hold. $\endgroup$ Commented Feb 10, 2015 at 2:32
-
$\begingroup$ Take $A = I$, $X(\epsilon) = \pmatrix{1+\epsilon & 0\cr 0 & \epsilon\cr}$, $B(\epsilon) = \pmatrix{1+\epsilon & 1\cr 1 & 1+\epsilon\cr}$. Your inequality fails for some $\epsilon > 1/10$, say, and $A, B(\epsilon), X(\epsilon) \succeq \epsilon I$. So $10A, 10B(\epsilon), 10X(\epsilon) \succ I$, and the inequality fails for them. $\endgroup$ Commented Feb 10, 2015 at 17:01
-
$\begingroup$ Ah yes! Excellent! Thank you kindly. $\endgroup$ Commented Feb 10, 2015 at 17:25