Characterising semi-definite positiveness on vectors with non-negative entries - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-20T10:46:52Z http://mathoverflow.net/feeds/question/103018 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/103018/characterising-semi-definite-positiveness-on-vectors-with-non-negative-entries Characterising semi-definite positiveness on vectors with non-negative entries Raphael L 2012-07-24T16:10:33Z 2012-07-25T07:51:17Z <p>My problem is to characterise (or find useful information on) the cone $C$ of $N\times N$ matrices $M$ ($N\geq 1$) such that $$V^t M V\geq 0$$ for every vector $V$ with non-negative entries. Is this cone of matrices familiar to anyone?</p> <p>Remark 1: $C$ clearly contains the convex cone $S$ of semi-definite positive matrices, and that of matrices $P$ with non-negative entries. Even though it looks too easy, I could not prove that $C$ is not the convex hull of $S$ and $P$.</p> <p>Remark 2: My original problem is to characterise the dual cone of $C$, containing the covariances of random vectors of $\mathbb{R}^N$ with a.s. non-negative entries.</p> http://mathoverflow.net/questions/103018/characterising-semi-definite-positiveness-on-vectors-with-non-negative-entries/103024#103024 Answer by Brian Borchers for Characterising semi-definite positiveness on vectors with non-negative entries Brian Borchers 2012-07-24T17:10:28Z 2012-07-24T17:10:28Z <p>Your cone $C$ is the cone of copositive matrices. The dual of C is the cone of compeltely positive matrices. See e.g.</p> <p><a href="http://mathworld.wolfram.com/CopositiveMatrix.html" rel="nofollow">http://mathworld.wolfram.com/CopositiveMatrix.html</a></p> http://mathoverflow.net/questions/103018/characterising-semi-definite-positiveness-on-vectors-with-non-negative-entries/103029#103029 Answer by Noah Stein for Characterising semi-definite positiveness on vectors with non-negative entries Noah Stein 2012-07-24T17:37:51Z 2012-07-24T17:37:51Z <p>The cone $C$ is called the cone of copositive matrices and its dual $C^*$ is called the cone of completely positive matrices. Here are some references.</p> <p>The paper most relevant to your question is probably "On Non-Negative Forms In Real Variables Some Or All Of Which Are Non-Negative," in which P. H. Diananda shows that $C$ does in fact take the simple form you stated in Remark 1 in the case $n\leq 4$. As mentioned in a note at the end of that paper, a counterexample called the Horn Form shows that $C$ does not have this form when $n\geq 5$.</p> <p>Another important paper in this area is "Some NP-Complete Problems In Quadratic And Nonlinear Programming" by K. G. Murty and S. N. Kabadi. There the authors show that checking membership in $C$ is co-NP-complete. In "Semidefinite programming based tests for matrix copositivity," P. A. Parrilo constructs a hierarchy of outer approximations to $C$ defined via SDPs; their duals give inner approximations to $C^*$. By combining these ideas one can easily construct semidefinite program approximations to a variety NP-complete optimization problems.</p> http://mathoverflow.net/questions/103018/characterising-semi-definite-positiveness-on-vectors-with-non-negative-entries/103077#103077 Answer by Denis Serre for Characterising semi-definite positiveness on vectors with non-negative entries Denis Serre 2012-07-25T07:06:22Z 2012-07-25T07:51:17Z <p>(After Noah Stein's answer) By definition, the dual cone $C^\star$ is spanned by matrices $v\otimes v$ with $v\ge0$. The following counter-example is due to Hall. The $5\times5$ symmetric matrix $$S=\begin{pmatrix} 4 &amp; 0 &amp; 0 &amp; 2 &amp; 2 \\ 0 &amp; 4 &amp; 3 &amp; 0 &amp; 2 \\ 0 &amp; 3 &amp; 4 &amp; 2 &amp; 0 \\ 2 &amp; 0 &amp; 2 &amp; 4 &amp; 0 \\ 2 &amp; 2 &amp; 0 &amp; 0 &amp; 4 \end{pmatrix}$$ has non-negative entries and is positive semi-definite. Therefore, it belongs to $(S\cup P)^\star$. Yet, it cannot be written as the sum of $v_j\otimes v_j$ where the vectors $v_j$ are non-negative. Therefore $A\not\in C^\star$. By duality, this proves that $C$ is not the convex hull of $S\cup P$.</p> <p>The example is analyzed in details in Exercise 347 of my <a href="http://www.umpa.ens-lyon.fr/~serre/DPF/exobis.pdf" rel="nofollow">list</a>.</p>