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

For given $n$, the following $n\times n$ real matrix $M=M^{T}$ is called positive, if

$x^{T}M x\geq 0$

holds for all non-negative real $x_1,x_2,\cdots,x_n$, where $x=(x_1,x_2,\cdots,x_n)^T$.

Notice here, the definition of positive is not the same as usual defination of positive semidefinite.

Now the goal is to characterize the set of all such $M$. In particular, I would like to show the following statement:

Such $M$ can always written as positive combination of some positive semidefinite matrix and some $E_{ij}$s, where $E_{ij}$ is the $n\times n$ matrix with the only non zero element 1 lies in the position $(i,j)$.

share|improve this question
    
For symmetric 2-by-2-matrices the claim is easily checked directly: the assumption implies the diagonal entries to be nonnegative. Then either the off-diagonal entry is nonnegative, hence the Matrix has nonnegative entries, or the off-diagonal entry is negative, in which case the Matrix must be positive semidefinite. (Indeed then $x^TMx\ge 0$ whenever the entries of $x$ have opposite sign. Moreover by assumption $x^TMx\ge 0$ when the entries of $x$ have same sign.) –  ThiKu Aug 30 at 21:55
    
@ThiKu Thank you! –  gondolf Aug 30 at 22:11
    
@ Will No, I do not! –  gondolf Aug 30 at 22:12
2  
IIRC, the minimal size for counterexample is $n=5$. –  Dima Pasechnik Aug 30 at 22:18
1  
yes, it is true for $n\leq 4$. This was shown by P.Diananda in 1962 (Proc. Cambridge Phil.Soc., vol 58). The counterexample for n=5 (see my answer) is also from this text. –  Dima Pasechnik Aug 30 at 22:49

1 Answer 1

up vote 13 down vote accepted

Such matrices are called copositive in the literature.

Moreover, the statement you want to show is known to be false. While I don't recall a counterexample right away, an intuition for this is that it's NP-hard to check copositivity, but computationally easy to check the condition in your statement, via semidefinite programming, see e.g. this text by Pablo Parrilo.

EDIT: here is an explicit counterexample: the matrix $$ M=\begin{pmatrix} 1&-1& 1& 1&-1\\ -1& 1&-1& 1& 1\\ 1&-1& 1&-1& 1\\ 1& 1&-1& 1&-1\\ -1& 1& 1&-1& 1 \end{pmatrix} $$ is copositive, but not equal to the sum of a positive semidefinite matrix $P$ and a nonnegative matrix $N$. It is taken from an old paper by P.Diananda in 1962 (Proc. Cambridge Phil.Soc., vol 58(1962)), where it is also shown that $n=5$ is minimal size for which one has such a counterexample.

A quick way to see that $M\neq P+N$ is as follows. First of all notice that $N$ can be assumed to have 0s on the main diagonal. This the condition $M=P+N$, that we want to bring to a contradiction, is equivalent to the existence of a positive semidefinite $P$ with all 1s on the diagonal, and satisfying the conditions $M_{ij}-P_{ij}\geq 0$, for all $1\leq i<j\leq 5$.

As $P$ is p.s.d., also for $i<j$ one has $|P_{ij}|\leq 1$, as can be checked by computing $x^\top P x$ for $x$ with $x_i=x_j=1$ and the remaining entries 0. Thus $P_{ij}=-1$ for all $i,j$ s.t. $M_{ij}=-1$. Further, all $P$'s satisfying these condition form a convex set $\Sigma$.

Thus if $P\in\Sigma$ then $\Pi P\Pi^\top\in\Sigma$, for any permutation matrix $\Pi$ commuting with $M$, as $M=\Pi M\Pi^\top=P+N=\Pi (P+N)\Pi^\top$, i.e. $\Pi (P+N)\Pi^\top$ is another representation of $M$. Hence, by an averaging argument over the group $G$ of permutation matrices commuting with $M$, we can select $P$ to commute with all such $\Pi$'s. (More explicitly, take $\frac{1}{|G|}\sum_{\Pi\in G}\Pi P\Pi^\top$.) It follows that there must exist $P$ of the form $$ P=\begin{pmatrix} 1&-1& p& p&-1\\ -1& 1&-1& p& p\\ p&-1& 1&-1& p\\ p& p&-1& 1&-1\\ -1& p& p&-1& 1 \end{pmatrix}, \quad -1\leq p\leq 1 $$ But none of such $P$'s are p.s.d., as its eigenvalues are $$2 \, p - 1, -\frac{1}{2} \, p {\left(\sqrt{5} + 1\right)} - \frac{1}{2} \, \sqrt{5} + \frac{3}{2}, \frac{1}{2} \, p {\left(\sqrt{5} - 1\right)} + \frac{1}{2} \, \sqrt{5} + \frac{3}{2}. $$

share|improve this answer
    
Thank you! How can one check the conditions in my statement? –  gondolf Aug 30 at 22:14
1  
This computational technique is called semi-definite programming. –  Dima Pasechnik Aug 30 at 22:16
    
How do you prove the example is indeed a counterexample? –  Hans Aug 31 at 3:56
1  
@gondolf - you're welcome. Please click on "accept this answer" if you're happy with it. –  Dima Pasechnik Aug 31 at 20:03
1  
The vector space of matrices commuting with G has a basis {$I$,$\pi+\pi^4$,$\pi^2+\pi^3$}, where $\pi$ is the permutation matrix corresponding to the cyclic permutation (1,2,3,4,5). Thus $P$ will be a linear combination of these 3 matrices. –  Dima Pasechnik Sep 3 at 9:13

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.