# On the positivity of matrices

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

-
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 '14 at 21:55
@ThiKu Thank you! –  gondolf Aug 30 '14 at 22:11
@ Will No, I do not! –  gondolf Aug 30 '14 at 22:12
IIRC, the minimal size for counterexample is $n=5$. –  Dima Pasechnik Aug 30 '14 at 22:18
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 '14 at 22:49

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

-
Thank you! How can one check the conditions in my statement? –  gondolf Aug 30 '14 at 22:14
This computational technique is called semi-definite programming. –  Dima Pasechnik Aug 30 '14 at 22:16
How do you prove the example is indeed a counterexample? –  Hans Aug 31 '14 at 3:56
@gondolf - you're welcome. Please click on "accept this answer" if you're happy with it. –  Dima Pasechnik Aug 31 '14 at 20:03
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 '14 at 9:13