Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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!

share|improve this question
2  
A matrix $N$ is positive semidefinite if and only if $-N$ is negative semidefnite. –  Chris Godsil Jan 4 '13 at 13:48
add comment

1 Answer 1

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.

share|improve this answer
    
Actually, with $C>0$, since we need to invert it. –  Federico Poloni Jan 4 '13 at 17:51
    
Yep, you are right, thanks. I will edit my post. –  Uwe Franz Jan 4 '13 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 '13 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 '13 at 21:58
1  
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 '13 at 23:17
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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