Does the Schur complement preserve the partial order?

Question

Let

$$\begin{bmatrix} A_{1} &B_1 \\ B_1' &C_1 \end{bmatrix} \quad \text{and} \quad \begin{bmatrix} A_2 &B_2 \\ B_2' &C_2 \end{bmatrix}$$

be symmetric positive definite and conformably partitioned matrices. If

$$\begin{bmatrix} A_{1} &B_1 \\ B_1' &C_1 \end{bmatrix}-\begin{bmatrix} A_2 &B_2 \\ B_2' &C_2 \end{bmatrix}$$

is positive semidefinite, is it true

$$(A_1-B_1C^{-1}_1B_1')-(A_2-B_2C^{-1}_2B_2')$$ also positive semidefinite? Here, $X'$ means the transpose of $X$.

Answer 1

Yes, it does. The assumption $$\begin{bmatrix} A_{1} &B_1 \\ B_1^T &C_1 \end{bmatrix}-\begin{bmatrix} A_2 &B_2 \\ B_2^T &C_2 \end{bmatrix} \geq 0$$ implies that for any vector $\begin{pmatrix} x & y \end{pmatrix}$,

$$ \begin{pmatrix} x^T & y^T \end{pmatrix} \begin{bmatrix} A_{1} &B_1 \\ B_1^T &C_1 \end{bmatrix} \begin{pmatrix} x \\ y \end{pmatrix} \geq \begin{pmatrix} x^T & y^T \end{pmatrix} \begin{bmatrix} A_2 &B_2 \\ B_2^T &C_2 \end{bmatrix} \begin{pmatrix} x \\ y \end{pmatrix}~~~~~(*)$$ But for any partitioned matrix,

$$\begin{pmatrix} x^T & y^T \end{pmatrix} \begin{bmatrix} A &B \\ B^T &C \end{bmatrix} \begin{pmatrix} x \\ y \end{pmatrix} = (x + A^{-1} B y)^T A (x + A^{-1} B y) + y^T(C-B^T A^{-1} B)y.$$ Moreover, if the partitioned matrix on the left-hand side is positive definite, then each of the two terms on the right=hand side is positive. Thus picking arbitrary $y$ and $x = -A_1^{-1}B_1y$ in (*) gives

$$y^T(C_1-B_1^T A_1^{-1} B_1)y \geq \mbox{ something positive} + y^T(C_2-B_2^T A_2^{-1} B_2)y,$$ which implies

$$y^T(C_1-B_1^T A_1^{-1} B_1)y \geq y^T(C_2-B_2^T A_2^{-1} B_2)y,$$

which implies the conclusion you want.

Answer 2

For a general block matrix $X=\begin{pmatrix}A&B\\C&D\end{pmatrix}$, the Schur complement $S$ to the block $D$ satisfies $$ \begin{pmatrix}A&B\\C&D\end{pmatrix} =\begin{pmatrix}I&BD^{-1}\\&I\end{pmatrix} \begin{pmatrix}S\\&D\end{pmatrix} \begin{pmatrix}I\\D^{-1}C&I\end{pmatrix}. $$ So, when $X$ is Hermitian, $$ \begin{pmatrix}A&B\\B^\ast&D\end{pmatrix} =\begin{pmatrix}I&Y^\ast\\&I\end{pmatrix} \begin{pmatrix}S\\&D\end{pmatrix} \begin{pmatrix}I\\Y&I\end{pmatrix}\ \textrm{ for some } Y. $$ Hence $$ \begin{eqnarray} &&\begin{pmatrix}A_1&B_1\\B_1^\ast&D_1\end{pmatrix} \ge\begin{pmatrix}A_2&B_2\\B_2^\ast&D_2\end{pmatrix} \\ &\Rightarrow& \begin{pmatrix}S_1\\&D_1\end{pmatrix} \ge \begin{pmatrix}I&Z^\ast\\&I\end{pmatrix} \begin{pmatrix}S_2\\&D_2\end{pmatrix} \begin{pmatrix}I\\Z&I\end{pmatrix}\ \textrm{ for some } Z\\ &\Rightarrow& (x^\ast,0)\begin{pmatrix}S_1\\&D_1\end{pmatrix}\begin{pmatrix}x\\0\end{pmatrix} \ge (x^\ast,\ x^\ast Z^\ast) \begin{pmatrix}S_2\\&D_2\end{pmatrix} \begin{pmatrix}x\\Zx\end{pmatrix},\ \forall x\\ &\Rightarrow& x^\ast S_1 x \ \ge\ x^\ast S_2 x + (Zx)^\ast D_2 (Zx) \ \ge\ x^\ast S_2 x,\ \forall x\\ &\Rightarrow& S_1\ge S_2. \end{eqnarray} $$

Edit: In hindsight, this is essentially identical to alex's proof.

Answer 3

In control theory, this kind of inequalities is ubiquitous and handled via going back and forth using Schur complements. For completeness, here is the non-strict version of Schur complement formula, it is an overkill but the question is a particular special case, so here it goes:

Formula: Let $Q,R$ be symmetric matrices. Then following are equivalent:

1. $$ \begin{pmatrix} Q &S\\ S^T &R \end{pmatrix} \succeq 0 $$

2. $$\begin{align} R &\succeq 0\\ Q -SR^\dagger S^T &\succeq 0\\ S(I-RR^\dagger) &= 0 \end{align} $$ where $R^\dagger$ is the Pseudoinverse of $R$.

---

Now if renaming your hypothesis involving the matrix difference as $$ M_1 - M_2 := \begin{pmatrix} A_1 &B_1\\ B_1^T &C_1 \end{pmatrix} - \begin{pmatrix} A_2 &B_2\\ B_2^T &C_2 \end{pmatrix}\succeq 0$$

we can reformulate the hypothesis as the following via the second item of the formula ($Q=M_1,S=I,R=M_2^{-1}$): $$\begin{align} M_2^{-1} &\succeq 0 \quad \text{by definition}\\ M_1 - M_2 &\succeq 0\\ I (I-M_2M_2^{-1}) &= 0 \end{align} $$ hence we have $$ \begin{pmatrix} M_1 &I\\I&M_2^{-1} \end{pmatrix}\succeq 0 $$ Also, from the inverse of a matrix formula, we have $$ M_2^{-1} = \begin{pmatrix} (A_2 - B_2C_2^{-1}B_2^T)^{-1} &\star\\ \star &\star \end{pmatrix} $$ As user1551 showed, you can bring the matrix $M_1$ in the form of the following by a congruence transformation and some reshuffling: $$\begin{pmatrix} M_1 &I\\I&M_2^{-1} \end{pmatrix} \leadsto \left( \begin{array}{cc|cc} (A_1 - B_1C_1^{-1}B_1^T) &I &0 &0\\ I &(A_2 - B_2C_2^{-1}B_2^T)^{-1} &0 &\star\\ \hline 0 &0 &C_1 &I\\ 0&\star&I&\star \end{array}\right) \succeq 0 $$ The $(1,1)$ block matrix has the desired result if we apply the nonstrict Schur complement formula again but in the reverse direction.

Last minute addition: Now that I look at it, it is not as good as I thought it to be initially but I did not want to waste the whole thing so I hope it helps an $\epsilon$.