# How to prove $B-A \succeq 0 \Leftrightarrow$ ellipsoid $x^TBx \leq 1$ contains $x^TAx \leq 1$?

Assume $$A \in \textbf{S}^n_{++}$$, an ellipsoid centered at the origin given by

$$\mathcal{E}_A = \{x\mid x^TA^{-1}x \leq 1\}$$

Then we have $$\mathcal{E}_A \subseteq \mathcal{E}_B$$ if and only if $$B-A \succeq 0$$.

This is the proposition in the Boyd & Vandenberghe's Convex Optimization (pages 45-46). The authors gave only the result, without proof. How to prove it?

• Take a look at this and this. Commented Aug 9, 2020 at 18:50
• Commented Aug 9, 2020 at 22:29

Assume $$\varepsilon_A = \{ x \mid x^T A^{-1}x \le 1 \}$$ is the set of points that comprise the inner ellipsoid and $$\varepsilon_B = \{ x |\; x^T B^{-1}x \le 1 \}$$ be the set of points comprising the outer ellipsoid and the two ellipsoid are distinct. Since $$B-A \succeq 0$$ is a PSD and since both $$A,B$$ have inverses $$A^{-1}$$ and $$B^{-1}$$ (the inverses exist) we can say

$$B-A \succeq 0 \Rightarrow I-B^{-1}A\succeq 0 \Rightarrow A^{-1}-B^{-1}\succeq 0$$

therefore $$A^{-1}-B^{-1}$$ is PSD and we can conclude that for every $$x$$ we have $$x^T(A^{-1}-B^{-1})x\ge 0 \Rightarrow x^TA^{-1}x\ge x^TB^{-1}x$$. This means that $$\forall x\in \varepsilon_A : 1\ge x^TA^{-1}x \ge x^TB^{-1}x \Rightarrow x\in \varepsilon_B$$.

Conversely assume $$\forall x\in \varepsilon_A \Rightarrow x\in \varepsilon_B$$ and assume that instead $$A-B \succeq 0$$ (contradiction assumption), which with a similar reasoning gives us $$\forall x\in \varepsilon_B \Rightarrow x\in \varepsilon_A$$ which states that both ellipsoids are the same and equivalent which is a contradiction (since we assumed they are distinct) and therefore the result follows.

• Thanks for answer. I can't understand why $B-A \succeq 0 \Rightarrow I-B^{-1}A\succeq 0 \Rightarrow A^{-1}-B^{-1}\succeq 0$. Can you give detailed proof about it? Since the multiplication of two PSD matrix isn't PSD all the time. Commented Aug 1, 2020 at 2:06
• Why positive semi-definite, $A,B \in \textbf{S}^n_{++}$, they are positive-definite and the product of two positive-definite is positive-definite (using Cholesky, $A = LL^H$ thus $AB = LL^HB = L (L^HBL)L^{-1}$ and therefore $AB$ is similar to $L^HBL$ and positive definite). Also if $A$ is PD then $A^{-1}$ is also PD. $$B \succeq A \Rightarrow I \succeq B^{-1}A \Rightarrow A^{-1} \succeq B^{-1}$$ Commented Aug 1, 2020 at 8:04
• I get your point. But since $I - B^{-1}A$ isn't symmetric, maybe using eigenvalues is more rigid？ $B-A \succeq 0$ and $B \succ 0$ we can get eigenvalues of $I - B^{-1}A$ are nonnegative, Similarly eigenvalues of $A^{-1} - B^{-1}$ are nonnegative. Combine with $A^{-1} - B^{-1}$ is Hermitian then PSD. Commented Aug 2, 2020 at 2:36
• Yes you are right, I did not notice $B^{-1}A$ is not symmetric therefore we can't conclude the result. It's actually the generalization of simple inequality $a>b>0 \Rightarrow \frac{1}{b}>\frac{1}{a}>0$ to generalized matrix inequality but it's not a trivial task at all and you need solid functional analysis which is above my pay grade, but if you get that result as a prove fact, then the rest follows. If you want I delete the answer and all comments will be removed too, just tell me to remove it and sorry for disappointment. Commented Aug 2, 2020 at 17:26
• No your answer is very inspiring and this fact is completely right. I found the proof here. By this I believe the answer can be perfect. If you like you can add this to your answer and I will accept it. Commented Aug 3, 2020 at 3:29