wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Non-negative Polynomial Decomposition
        
(Message started by: william wu on Oct 29th, 2007, 10:02pm)
Title: Non-negative Polynomial Decomposition
Post by william wu on Oct 29th, 2007, 10:02pm
Suppose f(x) is a polynomial with real coefficients that is non-negative for all x. Show that there exist polynomials g(x) and h(x) also with real coefficients such that f(x) = g(x)2 + h(x)2.
Title: Re: Non-negative Polynomial Decomposition
Post by Aryabhatta on Oct 30th, 2007, 12:28pm
Interesting problem William...

[hide]

Assume f is not identically zero and has degree n.

We can assume that f(x) is a polynomial with leading coefficient 1.  (Consider  xnf(1/x) >= 0 as x -> oo)

We proceed by induction on degree of f(x). Assume the hypothesis is true for lower degree polynomials.

We have two cases to consider:

1) f(x) has a real root r.

In that case f(x) = (x-r) m(x)

where m(x) is a polynomial with real coefficients.

Now since m(x) >= 0 if x > r and m(x) <= 0 if x < r, we must have that m(r) = 0.

i.e f(x) = (x-r)2n(x).

by induction assumption n(x) can be written as sum of two squares, and we are done.

2) f(x) has no real root.

We use the fact that if c is a complex root of f, then so is the conjugate c' of c.

Say the roots are ci and ci'

Write f(x) as the product of two (complex) polynomials m(x)* n(x)

where m(x) = (x - c1)...(x-ck)
n(x) = (x - c1')...(x-ck')

We can easily see that m(x) = h(x) + i g(x)
and n(x) = h(x) - i g(x)

for some real polynomials h and g.

i.e f(x) = h2(x) + g2(x)

[/hide]
Title: Re: Non-negative Polynomial Decomposition
Post by Barukh on Oct 31st, 2007, 5:36am

on 10/30/07 at 12:28:41, Aryabhatta wrote:
Interesting problem William...

... and very elegant solution, Aryabhatta!

:D
Title: Re: Non-negative Polynomial Decomposition
Post by Pietro K.C. on Oct 31st, 2007, 6:23pm
A cute relation that pops up in elementary number theory but is valid in any commutative ring is

(a2 + b2)(c2 + d2) = (ac + bd)2 + (ad - bc)2

In plain english, if two things can be written as the sum of two squares, so can their product. Now, a strictly positive real polynomial is a product of irreducible quadratic factors, ie stuff like

(x-a)2 + b2

To deal with the possible linear factors of a non-negative polynomial, we may do as Aryabhatta. Alternatively, notice that if

f(x) = (x-a)mq(x)

with q(a) not zero, then, in a small neightborhood of x=a, f behaves like a constant multiple of (x-a)m, which notoriously goes both above and below the x-axis for odd m.
Title: Re: Non-negative Polynomial Decomposition
Post by Aryabhatta on Nov 1st, 2007, 4:17pm

on 10/31/07 at 05:36:49, Barukh wrote:
... and very elegant solution, Aryabhatta!

:D


Thanks!


on 10/31/07 at 18:23:03, Pietro K.C. wrote:
A cute relation that pops up in elementary number theory but is valid in any commutative ring is

(a2 + b2)(c2 + d2) = (ac + bd)2 + (ad - bc)2


Nice!

And this can be proved for reals (probably same proof generalizes) by considering the complex numbers p = a+ib, q =  c + id, p' = a-ib, q' = c - id

The product of sum of squares (LHS) is pp'qq' and by rewriting it as (pq)(p'q') you get the RHS.
Title: Re: Non-negative Polynomial Decomposition
Post by Grimbal on Nov 2nd, 2007, 1:53am
It is just algebra:
 (ac + bd)2 + (ad - bc)2
 = (ac)2 + 2acbd + (bd)2 +  (ad)2 - 2adbc + (bc)2
 = a2c2 + b2d2 + a2d2 + b2c2
 = (a2 + b2)(c2 + d2)
Title: Re: Non-negative Polynomial Decomposition
Post by Aryabhatta on Nov 2nd, 2007, 2:08am

on 11/02/07 at 01:53:58, Grimbal wrote:
It is just algebra:
 (ac + bd)2 + (ad - bc)2
 = (ac)2 + 2acbd + (bd)2 +  (ad)2 - 2adbc + (bc)2
 = a2c2 + b2d2 + a2d2 + b2c2
 = (a2 + b2)(c2 + d2)


Yes it is easy to prove it once you are given the identity, but the point is that you can _arrive_ at the identity if you think in terms of complex numbers.

Anyway, we are drifting off-topic.
Title: Re: Non-negative Polynomial Decomposition
Post by william wu on Nov 3rd, 2007, 12:07pm
Nice job Aryabhatta :)

So to summarize:

1. The polynomial f(x) is strictly non-negative, so any real roots must have even multiplicity. (Odd multiplicity roots will cross the x-axis.) Also, any complex roots occur in complex conjugate pairs.

2. Writing f(x) as a product of terms of the form (x-r) where r is a root, we can rearrange these terms into two groups such that all the terms in one group are conjugates of all the terms in the other group. Hence, f(x) = g(x) conjugate(g(x)), where g(x) is a polynomial.

3. Recall that for a complex number z = a+bi, z * conjugate(z) = ||z||^2 = a^2 + b^2. Extend to polynomials.


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board