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.


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.

  • $\begingroup$ 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. $\endgroup$ – user31373 Jun 16 '12 at 18:11
  • $\begingroup$ I will try looking that book up then. Thanks a lot :) $\endgroup$ – Undreren Jun 16 '12 at 19:42
  • $\begingroup$ The link for the Source is down, I think. $\endgroup$ – user120404 Jul 25 '16 at 15:40

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

  • $\begingroup$ 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? $\endgroup$ – Undreren Jun 17 '12 at 7:22
  • $\begingroup$ 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. $\endgroup$ – Martin Argerami Jun 17 '12 at 14:46
  • $\begingroup$ @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$? $\endgroup$ – Mahmood Al Jul 12 '14 at 4:17
  • $\begingroup$ 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}.$ $\endgroup$ – Martin Argerami Jul 12 '14 at 14:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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