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.

Thank you all in advance,

Best regards!

  • 3
    $\begingroup$ A matrix $N$ is positive semidefinite if and only if $-N$ is negative semidefnite. $\endgroup$ Jan 4 '13 at 13:48

This should be a comment, but I can not yet post comments.

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

Then Chris Godsil's comment shows that the answer to your first question is yes.

  • $\begingroup$ Actually, with $C>0$, since we need to invert it. $\endgroup$ Jan 4 '13 at 17:51
  • $\begingroup$ Yep, you are right, thanks. I will edit my post. $\endgroup$
    – Uwe Franz
    Jan 4 '13 at 18:51
  • $\begingroup$ 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! $\endgroup$
    – AD1984
    Jan 4 '13 at 20:34
  • $\begingroup$ 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? $\endgroup$
    – AD1984
    Jan 5 '13 at 21:58
  • 1
    $\begingroup$ 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. $\endgroup$
    – Uwe Franz
    Jan 5 '13 at 23:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.