4
$\begingroup$

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!

Improve this question
$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$
    – Brian Borchers
    Commented Aug 21, 2011 at 21:07
  • $\begingroup$ Which is the motivation of that specific constraint? $\endgroup$
    – Qfwfq
    Commented Aug 21, 2011 at 23:17
  • $\begingroup$ The motivation is to turn this problem into a semidefinite programming problem. This is a standard construction in SDP. $\endgroup$
    – Brian Borchers
    Commented Aug 23, 2011 at 4:49

3 Answers 3

Reset to default
7
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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! $\endgroup$
    – Kostas
    Commented Aug 21, 2011 at 17:18
  • 1
    $\begingroup$ @Kostas. Btw, my first name contains only one N. This is the french spelling. $\endgroup$
    – Denis Serre
    Commented Feb 20, 2018 at 12:20
4
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ Yep, you've got to give up on $C\geq 0$. $\endgroup$
    – Brian Borchers
    Commented Aug 23, 2011 at 4:50
1
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Kostas
    Commented Aug 21, 2011 at 17:38
  • $\begingroup$ 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. $\endgroup$
    – Brian Borchers
    Commented Aug 21, 2011 at 21:00

You must log in to answer this question.

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