MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

## Schur complement and negative definite matrices

Hello,

My question regards to the Schur complement lemma. Consider the matrix $M=\left( \begin{array}{cc} A & B\\ B^T & C \end{array}\right)$.

According to the lemma $M\geq0$ iff $C>0$ and $A-BC^{-1}B^T\geq 0$.

In my current research I'm working on an optimization problem over a domain of matrices; I'm trying to convert this optimization problem into it's convex form. In order to do so I need a similar relation for negative definite matrices. Can the Schur complement lemma be extended to the case of negative definite matrices? And if so, how? Namely, is it true that for a matrix $M$ of the same structure we have $M\leq 0$ iff $C<0$ and $A-BC^{-1}B^T\leq 0$?

Another similar but different problem I have regards to the following non-convex (nor linear) constraint: $A-BC^{-1}B^T\leq 0$ and $A\geq 0$. Is there some way such constraints can be converted to an equivalent constraint which is linear in these variables? For example the two constraints $A-BC^{-1}B^T\geq 0$ and $C> 0$ can be simply converted to $M\geq 0$ using the Schur complement lemma. The new constraint $M\geq 0$ is equivalent to the two old ones and is indeed linear in the matrices $A,B,C$. I'm looking for a way to do something similar to this for my case.

Best regards!

-
A matrix $N$ is positive semidefinite if and only if $-N$ is negative semidefnite. – Chris Godsil Jan 4 at 13:48

You got Schur's complement lemma wrong, the matrix $$\left(\begin{array}{cc} 1 & 1 \newline 1 & -1 \end{array}\right)$$ satisfies you conditions, $A=1\ge 0$ and $A-BC^{-1}B^T=1-(-1)\ge 0$, but it is clearly not positive semi-definite. Replace the first condition by $C > 0$ (see also http://en.wikipedia.org/wiki/Schur_complement).
 Actually, with $C>0$, since we need to invert it. – Federico Poloni Jan 4 at 17:51 Yep, you are right, thanks. I will edit my post. – Uwe Franz Jan 4 at 18:51 Ohh I'm sorry, I accidentally mixed the two version of the lemma. I've edited the original question and now I think it's fine; thanks for the remark! So you say that $M\leq 0$ iff $C<0$ and $A-BC^{-1}B^T$ holds? Any ideas regarding the second question? Thanks again! – Ziv Goldfeld Jan 4 at 20:34 Thank you. By the way, why is it important to have $C>0$ (or $C<0$ for the negative version) in order to use the lemma? Why isn't $C\neq 0$ enough? I ask it since we do not demand anything regarding the matrices $A$ and $B$ as far as non-negativeness, but we do demand it for $C$. Why is that? – Ziv Goldfeld Jan 5 at 21:58 Good point, M≥0 does not imply C>0, take, e.g. M=0, that's a positive semi-definite matrix. It implies only A≥0 and C≥0. But if one of A and C is stricly positive and therefore invertible, them M≥0 is equivalent to the other condition involving its inverse. See the Wikipedia article. – Uwe Franz Jan 5 at 23:17