Showing $B-A$ is positive semidefinite

Question

Let $A$ and $B$ be two symmetric $n\times n$ matrices. Suppose that $A,B\preceq I/2$ ($C \preceq D$ means $D - C$ is positive semidefinite) and $$A(I-A)\preceq B(I-B),$$prove that $A\preceq B$.

My try: By assumptions for every vector $x$ we have: $$x^T(I/2 - B)x\ge 0 \\ x^T(I/2 - A)x\ge 0 \\ x^T(B-B^2-A+A^2)x\ge 0$$ By adding the two first equations, we get $$x^T(I-A-B)x = ||x||^2-x^T(A+B)x\ge 0$$ I don't see how this inequality can be used for showing the desired inequality: $$x^T(B-A)x\ge 0$$

Answer 1

Notice that we can write $$ B(I - B) - A(I - A) = \Bigl(\frac{I}{2} - A\Bigr)^2 - \Bigl(\frac{I}{2} - B\Bigr)^2, $$ and so it follows from the fact that $B(I-B) \succeq A(I - A)$ that $(I/2 - A)^2 \succeq (I/2 - B)^2$ (convince yourself of this!).

But now $(I/2 - A)$ and $(I/2 - B)$ are each positive semidefinite by assumption, from which it follows that $$ \frac{I}{2} - A \succeq \frac{I}{2} - B, $$ and so finally that $A \preceq B$.

Answer 2

I'm writing this answer using Damian Pavlyshyn's and user8675309's answers (also see this question).

---

Lemma: Let $A$ and $B$ be $n\times n$ real symmetric matrices. If $A^2 \preceq B^2$ and $A,B \succeq 0$ then $A \preceq B$.

Proof: Fix $\epsilon \gt 0$. We have: $$(B + A + \epsilon I)(B - A + \epsilon I) + (B - A + \epsilon I)(B + A + \epsilon I) = (B^2-BA+\epsilon B+AB-A^2+\epsilon A+\epsilon B-\epsilon A+\epsilon^2I) + (B^2+BA+\epsilon B-AB-A^2-\epsilon A+\epsilon B+\epsilon A+\epsilon^2I)=2B^2 +4\epsilon B-2A^2 +2 \epsilon^2 I $$ We know that $2B^2-2A^2$ is PSD and $4\epsilon B $ is PSD, so their sum is PSD: $$2B^2 +4\epsilon B-2A^2 \succeq 0$$ This shows that: $$2B^2 +4\epsilon B-2A^2 +2 \epsilon^2 I \succeq 2\epsilon^2I \implies (B + A + \epsilon I)(B - A + \epsilon I) + (B - A + \epsilon I)(B + A + \epsilon I) \succeq 2\epsilon^2I$$ Let $C := (B - A + \epsilon I)$. It's obvious that $C^T = C$. We will show that $C$ has a trivial null space. By contradiction suppose that $\mathbf x \neq \mathbf 0$ exists such that $C \mathbf x = \mathbf 0$. Using the previous result we have: $$\mathbf x^T[(B + A + \epsilon I)C + C(B+A+\epsilon I) - 2\epsilon^2I]\mathbf x\ge0$$ Also by assumption we have: $$\mathbf x^T(B + A + \epsilon I)C \mathbf x = \mathbf 0 \ \ \text{and} \ \ \mathbf x^TC(B+A+\epsilon I)\mathbf x = \mathbf 0$$ This shows that: $$2\epsilon^2||\mathbf x||^2\le 0 $$ which is a contradiction. So we conclude $C$ is invertible and $\det(C) \not = 0$. Therefore: $$\det(B - A + \epsilon I) = \det(B-A-(-\epsilon I)) = (-1)^n \det((-\epsilon I) - (B-A)) \not = 0 \implies p(-\epsilon) \not = 0$$ where $p$ is the characteristic polynomial of $B-A$. Note that $B-A$ is a symmetric matrix, so all of the eigenvalues are real and by $p(-\epsilon) \not = 0$ the eigenvalues are nonnegative. This shows $A \preceq B$.

Main question: Notice that we can write: $$B(I - B) - A(I - A) = \Bigl(I/2 - A\Bigr)^2 - \Bigl(I/2 - B\Bigr)^2$$ So we know that: $$(I/2 - A)^2 \succeq (I/2 - B)^2$$Let $X = I/2 - A$ and $Y = I/2 - B$. By assumption $X,Y \succeq 0$ and $X,Y$ are real symmetric matrices. Also $X^2 \succeq Y^2$, thus the lemma can be applied: $$X \succeq Y$$ This result implies that: $$I/2 - A \succeq I/2 - B \implies B - A \succeq 0 \implies B \succeq A$$