Sum of squares of polynomials

Today I went to a talk delivered by a postdoc in the CS department about bilinear complexity. He raised this elementary result:

Theorem. Every polynomial $f$ in $\mathbb{C}[x_1,\cdots,x_n]$ (that means, $f$ is a polynomial in $x_1,\cdots,x_n$ with complex coefficients) can be expressed as a sum of two squares of complex polynomials.

The proof follows directly from the fact:

$\displaystyle a = \left( \frac{a+1}{2}\right)^2+\left( \frac{i(a-1)}{2}\right)^2$.

Another elementary thing is that:

$g(x_1,x_2,y_1,y_2) = x_1^2 y_1^2 + x_1^2 y_2^2 + x_2^2 y_1^2 + x_2^2 y_2^2$ is a sum of squares of two polynomials with integer coefficients.

Whether a real polynomial can be written as a sum of squares of real polynomials plays an important role in polynomial optimization. If I have time I will continue this post.

Advertisements
This entry was posted in Algebra. Bookmark the permalink.

5 Responses to Sum of squares of polynomials

1. KKK says:

Do you need some extra assumptions, e.g. with even degrees? It seems that e.g. $x_1$ is not a sum of squares.

• Hon Leung says:

For real polynomials, yes, also should assume the given polynomial is nonnegative.

• KKK says:

I don’t understand. So how is $x_1$ be a sum of squares when regarded as a complex polynomial?

• KKK says:

Ah… stupid me. Let me answer my own question:
$2x=(x+1)^2 + (ix)^2 +i^2$.

• Hon Leung says:

Nice~