6
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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.) $\endgroup$ – ThiKu Aug 30 '14 at 21:55
  • $\begingroup$ @ Will No, I do not! $\endgroup$ – gondolf Aug 30 '14 at 22:12
  • 2
    $\begingroup$ IIRC, the minimal size for counterexample is $n=5$. $\endgroup$ – Dima Pasechnik Aug 30 '14 at 22:18
  • $\begingroup$ @Dima So, for $n<5$, my statement is true? $\endgroup$ – gondolf Aug 30 '14 at 22:38
  • 1
    $\begingroup$ 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. $\endgroup$ – Dima Pasechnik Aug 30 '14 at 22:49
16
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thank you! How can one check the conditions in my statement? $\endgroup$ – gondolf Aug 30 '14 at 22:14
  • 1
    $\begingroup$ This computational technique is called semi-definite programming. $\endgroup$ – Dima Pasechnik Aug 30 '14 at 22:16
  • $\begingroup$ How do you prove the example is indeed a counterexample? $\endgroup$ – Hans Aug 31 '14 at 3:56
  • $\begingroup$ @Hansen - see my latest edit for a proof and a reference. $\endgroup$ – Dima Pasechnik Aug 31 '14 at 9:19
  • 1
    $\begingroup$ 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. $\endgroup$ – Dima Pasechnik Sep 3 '14 at 9:13

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.