Author |
Topic: Non-negative Polynomial Decomposition (Read 848 times) |
|
william wu
wu::riddles Administrator
Gender: 
Posts: 1291
|
 |
Non-negative Polynomial Decomposition
« on: Oct 29th, 2007, 10:02pm » |
 Quote  Modify
|
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.
|
|
 IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Non-negative Polynomial Decomposition
« Reply #1 on: Oct 30th, 2007, 12:28pm » |
Quote Modify
|
Interesting problem William...
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)
|
| « Last Edit: Oct 30th, 2007, 12:33pm by Aryabhatta » |
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Non-negative Polynomial Decomposition
« Reply #2 on: Oct 31st, 2007, 5:36am » |
Quote Modify
|
on Oct 30th, 2007, 12:28pm, Aryabhatta wrote:| Interesting problem William... |
|
... and very elegant solution, Aryabhatta!
|
|
IP Logged |
|
|
|
Pietro K.C.
Full Member
 
Gender:
Posts: 213
|
|
Re: Non-negative Polynomial Decomposition
« Reply #3 on: Oct 31st, 2007, 6:23pm » |
Quote Modify
|
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.
|
|
IP Logged |
"I always wondered about the meaning of life. So I looked it up in the dictionary under 'L' and there it was --- the meaning of life. It was not what I expected." (Dogbert)
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Non-negative Polynomial Decomposition
« Reply #4 on: Nov 1st, 2007, 4:17pm » |
Quote Modify
|
on Oct 31st, 2007, 5:36am, Barukh wrote:
... and very elegant solution, Aryabhatta!
|
|
Thanks!
on Oct 31st, 2007, 6:23pm, 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.
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Non-negative Polynomial Decomposition
« Reply #5 on: Nov 2nd, 2007, 1:53am » |
Quote Modify
|
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)
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Non-negative Polynomial Decomposition
« Reply #6 on: Nov 2nd, 2007, 2:08am » |
Quote Modify
|
on Nov 2nd, 2007, 1:53am, 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.
|
|
IP Logged |
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: Non-negative Polynomial Decomposition
« Reply #7 on: Nov 3rd, 2007, 12:07pm » |
Quote Modify
|
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.
|
|
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print