In this article we shall describe something called Gram-matrix method which can decompose a polynomial into sum of squares. The notation means is a square symmetric positive semidefinite matrix.
Proposition 1. Let , be a polynomial of degree at most . Then the following are equivalent:
(a) is SOS
(b) for some positive semidefinite matrix . The matrix is called the Gram matrix of the SOS decomposition of .
(c) The following system in the matrix variable is feasible:
Before we prove it we do some counting. First, the cardinality of is . This is because the cardinality is indeed the number of nonnegative integer solutions of
Using stars and bars argument, it is . Thus is a matrix. By similar reasoning (1) has equations. So (1) has polynomial size if is fixed.
Proof of Proposition 1. Set . For polynomials define as the sequence of coefficients in the monomial basis of . Then . It follows that . The matrix is positive semidefinite.
Thus, is SOS if and only if for some positive semidefinite matrix . The system (1) comes from equating the coefficients of polynomials and .
Proposition 1 is useful because computing SOS decomposition of is equivalent to finding such that (1) holds. This feasibility problem is indeed a semidefinite program (SDP), which can be solved in polynomial time. Let’s recall SDP.
We first associate the Frobenius inner product to the space of matrices given by
Denote by the vector space of symmetric matrices. Given and . A (primal) semidefinite program (SDP) is in the form
(2) subject to , for
where the decision variable is only matrix .
By setting and choosing correct ‘s (What are they?), (2) is equivalent to finding so that (1) holds.
Let us illustrate Proposition 1 using examples.
Example 1. Consider the degree 4 univariate polynomial . Is SOS? Let’s try to find a decomposition. Set . By equating coefficients for where , system (1) is:
Then by some SDP solver or by hand one solution is
Thus, if we set , and then
Example 2. Consider the degree 4 bivariate polynomial . Want to find such that
Equating coefficients, (1) becomes:
Thus . One can check if and only if . Setting and and factorizing we obtain two SOS decompositions of :