Sum of squares polynomial

A real polynomial $p$ is a sum of squares polynomial if $p={\sum }_{\ell }{q}_{\ell }^2$ for real polynomials $q_{\ell }$. Such a representation certifies global nonnegativity. If $m(z)$ is the vector of relevant monomials, the identity $p(z)=m(z{)}^{T}Gm(z)$ with a positive semidefinite matrix $G$ encodes a sum of squares through a Gram matrix. Equating coefficients is linear in $G$, so finding a certificate is a semidefinite program.

If a degree-$2d$ homogeneous polynomial is a sum of squares polynomial, it has a representation as squares of degree-$d$ homogeneous polynomials. In any sum of squares, the highest-degree terms cannot cancel, since their homogeneous part is itself a sum of squares. Likewise the lowest nonzero degree cannot cancel. Thus every nonzero summand has only degree $d$.

A polynomial invariant under changing the sign of each coordinate can have its sum of squares representation averaged over independent Rademacher random variables ${\epsilon }_i\in \{-1,1\}$. Distinct parity patterns of monomials have zero cross terms because $\mathbb{E}[{\prod }_i{\epsilon }_i^{a_i}]$ vanishes when some exponent is odd. For a quadratic homogeneous polynomialthis givesThis identity separates the even monomials from each distinct two-coordinate parity pattern.

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.