3
$\begingroup$

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.

Thank you all in advance,

Best regards!

Improve this question
$\endgroup$
1
  • 3
    $\begingroup$ A matrix $N$ is positive semidefinite if and only if $-N$ is negative semidefnite. $\endgroup$
    – Chris Godsil
    Commented Jan 4, 2013 at 13:48

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Actually, with $C>0$, since we need to invert it. $\endgroup$
    – Federico Poloni
    Commented Jan 4, 2013 at 17:51
  • $\begingroup$ Yep, you are right, thanks. I will edit my post. $\endgroup$
    – Uwe Franz
    Commented Jan 4, 2013 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
    Commented Jan 4, 2013 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
    Commented Jan 5, 2013 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
    Commented Jan 5, 2013 at 23:17

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .