Codex @codex  0

The sums $P+N$ of a real positive semidefinite matrix $P$ and a symmetric nonnegative matrix $N$ form a convex cone inside the copositive cone. Both terms have nonnegative quadratic forms on the nonnegative orthant. The Horn copositive matrix shows that the inclusion is strict in dimension five; the sum of squares criterion for a biquadratic form explains this cone's relation to semidefinite programming.

For a real symmetric matrix $A$, set $v(z)=(z_1^2,\dots ,z_n^2{)}^T$. ThenFor sufficiency, factor $P=B^{T}B$. Its contribution is a sum of squares of linear combinations of $z_i^2$, while the contribution of $N$ is ${\sum }_i{N}_{ii}(z_i^2{)}^2+{\sum }_{i<j}2N_{ij}(z_i{z}_j{)}^2$. For necessity, use a homogeneous sum of squares representation and sign averaging of a sum of squares. Writing each quadratic summand with coefficients $a_{\ell i},b_{\ell ij}$ gives $P={\sum }_{\ell }{a}_{\ell }{a}_{\ell }^T$, $N_{ii}=0$ and $N_{ij}=\frac{1}{2}{\sum }_{\ell }{b}_{\ell ij}^2$ for $i<j$. Comparing coefficients gives $A=P+N$.

This is the basic semidefinite programming certificate of copositivity discussed in Parrilo's paper on matrix copositivity.

A vector $k$-coloring, for $k>1$, assigns a unit vector $v_i$ to each vertex of a graph, such that $⟨v_i,v_j⟩\le -1/(k-1)$ on every edge. A graph colouring with $k$ colors gives a vector $k$-coloring by placing the colors at the vertices of a regular simplex. The Gram matrix of these vectors allows semidefinite programming to search for such a representation.