# Schur complement and “negative definite”!

Hi I have the following problem. Let the symmetric matrix M of the form: \begin{bmatrix} A & B \newline B^T & C \newline \end{bmatrix}

We have that $C$ is positive semidefinite. Is there a way to transform the constraint $A-BC^{-1}B^T \leq 0$ to a constraint using matrix $M$?

I know that in case the constraint was $A-BC^{-1}B^T \geq 0$ the answer is $M \geq 0$. But can we say something similar for the negative definite constraint? (I have already checked that $A-BC^{-1}B^T \leq 0 \Leftrightarrow M \leq 0$ Does not hold.) Is there another way to transform this constraint to a linear over the matrix B?

Thank you very much!

-
Just to be clear, you want to find a matrix $M$ (linearly dependent on $B$), so that $M \ge 0$ iff $A-BC^{-1}B^{T} \leq 0$, right? – Brian Borchers Aug 21 '11 at 21:07
Which is the motivation of that specific constraint? – Qfwfq Aug 21 '11 at 23:17
The motivation is to turn this problem into a semidefinite programming problem. This is a standard construction in SDP. – Brian Borchers Aug 23 '11 at 4:49

$M$ is congruent to ${\rm diag}(A-BC^{-1}B^T,C)$. Therefore the condition $A-BC^{-1}BT\le0$ amounts to saying that the maximal dimension of positive subspace is the size $p$ of $C$.If $A-BC^{-1}BT<0$, this is saying that the signature of $M$ is $(p,0,q)$, where $q$ is the size of $A$.

-
Hi Dennis, thank for the answer! I understood your answer. That is: you say that the condition $A−BC^{-1}B^T \leq 0$ is equivalent as saying that $M$ has at maximum $p$ positive eigenvalues. Yet, can I write this down as a convex constraint? My variable is matrix $B$. Thank you very much! – Kostas Aug 21 '11 at 17:18

Its not completely clear what you are asking: what does it mean to "transform this constraint to a linear over the matrix B?" But perhaps it will be helpful to note that the set of matrices of your form satisfying $$C \geq 0, ~~A - B C^{-1} B^T \leq 0$$ is not convex: just consider what happens when you take the average of two $2 \times 2$ matrices, one with $A=2,C=1/2,B=1$ and the other with $A=1/2, C=2, B=1$. So it is impossible to express these two constraints in terms of linear inequalities on matrices $A,B,C,D$.

-
Yep, you've got to give up on $C\geq 0$. – Brian Borchers Aug 23 '11 at 4:50

No, that's not quite the generalization that you'll get when you extend the Schur complement theorem for positive definite matrices to negative definite matrices. Try using the fact that a matrix $X$ is negative definite if and only if $-X$ is positive definite and then follow the sign changes through- you'll end up with a slightly different $M$ matrix.

-
Hi Brian, thank you for your answer! I tried to do what you proposed, but I havent managed to work it out. You say that: $A+BC^{-1}B^T \leq 0 \Leftrightarrow -A+BC^{-1}B^T \geq 0$. But then how can I continue? I want to get a matrix inequality that is linear on the matrix $B$. Even if I assume that $A \geq 0$ then I get a matrix $M$ that is not not linear on B. – Kostas Aug 21 '11 at 17:38
No, I didn't say that. You've made a sign change error in what you wrote: $A-BC^{-1}B^{T} \leq 0$ iff $-A+BC^{-1}B^{T} \geq 0$. The signs on both terms have to change. – Brian Borchers Aug 21 '11 at 21:00