Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have been wondering about this for some time, and I haven't been able to answer the question myself. I also haven't been able to find anything about it on the internet. So I will ask the question here:

Question: Assume that $A$ and $B$ both are positive semi-definite. When is $C = (A-B)$ positive semi-definite?

I know that I can figure it out for given matrices, but I am looking for a necessary and sufficient condition.

It is of importance when trying to find solutions to conic-inequality systems, where the cone is the cone generated by all positive semi-definite matrices. The question I'm actually interested in finding nice result for are:

Let $x \in \mathbb{R}^n$, and let $A_1,\ldots,A_n,B$ be positive semi-definite. When is

$(\sum^n_{i=1}x_iA_i) - B$

positive semi-definite?

I feel the answer to my first question should yield the answer to the latter. I am looking for something simpler than actually calculating the eigenvalues.

share|improve this question

2 Answers 2

up vote 1 down vote accepted

There's a form of Sylvester's criterion for positive semi-definiteness, which unfortunately requires a lot more computations than the better known test for positive definiteness. Namely, all principal minors (not just the leading ones) must be nonnegative. Principal minors are obtained by deleting some of the rows and the same-numbered columns. Source

The book Matrix Analysis by Horn and Johnson is the best reference for positive (semi)definiteness that I know.

share|improve this answer
    
Of course, $A$ is positive semidefinite if and only if $A+\epsilon I$ is positive definite for all $\epsilon>0$. If your approach is computational, you can try using Sylvester's criterion for a $A+\epsilon I$ where $\epsilon$ is small compared to the entries of your matrix. There is a risk of false positives, though. –  user31373 Jun 16 '12 at 18:11
    
I will try looking that book up then. Thanks a lot :) –  Undreren Jun 16 '12 at 19:42

There's no easy answer. The relation is usually denoted $B\leq A$. The most useful test I can think of is that $A\leq B$ if and only if $$ x^TBx\leq x^TAx, \ \ x\in\mathbb{R}^n. $$

share|improve this answer
    
Yes, this follows from the definition of positive semi-definiteness, but it is onfortunately of almost no use since I can not efficiently do this test for all real non-zero vectors. Or do you have a suggestion? –  Undreren Jun 17 '12 at 7:22
    
I see you are looking for a numerical test. I'm of not use there. In the abstract world, the relation above is used often as a good test. –  Martin Argerami Jun 17 '12 at 14:46
    
@Martin Argerami: If $A=(a_{i,j})_{i,j=1}^n$ and $B=(b_{i,j})_{i,j=1}^n$ are two positive semidefinite matrices with real values and $a_{i,j}\geq b_{i,j} \geq 0$ for every $i,j$. Can we say anything about $A-B$? –  User3060 Jul 12 at 4:17
    
I dont'think so: $\begin{bmatrix}0&1\\1&0\end{bmatrix}=\begin{bmatrix}1&1\\1&1\end{bmatrix}-\begin{‌​bmatrix}1&0\\0&1\end{bmatrix}.$ –  Martin Argerami Jul 12 at 14:49

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.