# Does the Schur complement preserve the partial order

Let $\begin{bmatrix} A_{1} &B_1 \\ B_1' &C_1 \end{bmatrix}$, $\begin{bmatrix} A_2 &B_2 \\ B_2' &C_2 \end{bmatrix}$ be symmetric positive definite matrices and be conformably partitioned. 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$.

-
The more common term is "conformably partitioned". ;) – J. M. Sep 2 '11 at 15:08
Thanks, changed. – Sunni Sep 2 '11 at 15:44
My guess is either the answer is yes, or it become yes if you invert the order of subtraction. – Michael Hardy Sep 2 '11 at 18:25
This is making me realize that my understanding of Wishart matrices is rusty. If $W_1$ and $W_2$ are independent matrix valued random variables with a Wishart distribution, then their sum is Wishart-distributed as well. So if $W_1$ and $W_2-W_1$ are Wishart-distributed and independent, then $W_2$ is Wishart distributed. And Schur complements within Wishart matrices are also Wishart-distributed. That much I'm sure of, and looking at en.wikipedia.org/wiki/Wishart_distribution, I'm surprised that the term "Schur complement" does not appear anywhere in the article. – Michael Hardy Sep 2 '11 at 18:33
Note from alex' answer that the condition that the full matrices be individually positive definite can be weakened; it suffices that $C_2$ (and hence $C_1$) is positive definite. This condition, however, is required, since $$\begin{pmatrix}1&1\\1&1\end{pmatrix}-\begin{pmatrix}0&1\\1&-1\end{pmatrix}=\begi‌​n{pmatrix}1&0\\0&2\end{pmatrix}$$ would be a counterexample without it. – joriki Sep 2 '11 at 19:42

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.

-
Oops - I seem to have worked out the other Schur complement, i.e. the Schur complement of the $(2,2)$ block with respect to the $(1,1)$ block. I'm too lazy to rewrite, and this is of course equivalent to the question you ask. – alexx Sep 2 '11 at 18:38
Interesting -- if I understand correctly, "something positive" is positive because $A_2$ is positive definite -- it seems you've only used the positive definiteness of $A_2$ but not that of the full second matrix and not that of the first matrix? – joriki Sep 2 '11 at 19:19
@joriki - good catch; you are right. I hope my proof is not wrong; it seems like it proves a little too much, but I looked through it again and I do not see an error. I suppose that because $A_2 \geq 0$ implies $A_1 \geq 0$ under the assumptions of the question, it does seem plausible. – alexx Sep 2 '11 at 19:29
I wasn't implying that there's something wrong -- in fact I'd looked for counterexamples before realizing that the full matrices are individually assumed to be positive definite, and the counterexample I found did have (in your swapped version) $A_1$ and $C_2$ positive definite but $A_2$ negative definite, so it makes sense that the positive definiteness of $A_2$ is the crucial requirement. – joriki Sep 2 '11 at 19:38
Nice proof. Thanks. – Sunni Sep 2 '11 at 22:29

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.

-
This would be a standard proof. – Sunni Sep 2 '11 at 22:29

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

-
Thanks, I can see a simplest proof: Using $M_1\ge M_2$ is equivalent to $M_2^{-1}\ge M_1^{-1}$. Thus $M_2^{-1} = \begin{pmatrix} (A_2 - B_2C_2^{-1}B_2^T)^{-1} &\star\\ \star &\star \end{pmatrix}$... – Sunni Sep 6 '11 at 0:03
@Sunni : Ah, yes. That's a clever shortcut. – user13838 Sep 6 '11 at 8:35