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

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!

share|improve this question
    
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
add comment

3 Answers 3

up vote 6 down vote accepted

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

share|improve this answer
    
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
add comment

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

share|improve this answer
    
Yep, you've got to give up on $C\geq 0$. –  Brian Borchers Aug 23 '11 at 4:50
add comment

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.

share|improve this answer
    
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
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.