Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

How can I prove, that a polynomial function $$f(x) = \sum_{0\le k \le n}a_k x^k\qquad n\in\mathbb N,\ a_k\in\mathbb C$$ is zero for at most $n$ different values of $x$? (Except $n=0$ where $f(x)$ is $0$ in all cases)

share|improve this question
4  
Induction. If it has a root r, divide by (x - r). –  Qiaochu Yuan Mar 8 '11 at 19:56
1  
Isn't this the fundamental theorem of algebra? Wikipedia (en.wikipedia.org/wiki/Fundamental_theorem_of_algebra) gives several proofs. –  please delete me Mar 8 '11 at 19:56
2  
Hint: First show that $f(\alpha) = 0$ iff $x-\alpha$ divides $f(x)$ and then use induction on the degree of $f$ –  kahen Mar 8 '11 at 19:57
    
Is there any background one needs to consider? For instance, is this some problem assigned in some course? If so, which course? –  Aryabhata Mar 8 '11 at 20:01
1  
@Fuz: No, it is not "part" of fundamental theorem. It might be what you call a "Corollary", but it has other easier proofs. –  Aryabhata Mar 8 '11 at 20:13
show 7 more comments

5 Answers 5

up vote 6 down vote accepted

Using Linear Algebra,

If the $n+1$ distinct roots are $\alpha_i$, then we have that $x = [a_0, a_1, \dots, a_n]^{T}$ is a solution of $Ax = 0$ where $A$ is the Vandermonde matrix using the $\alpha_i$.

Since the Vandermonde matrix is invertible for distinct $\alpha_i$, it follows that $x = [0, 0, \dots, 0]$.

Thus if $a_j \neq 0$ for some $j$, then your polynomial can have at most $n$ different roots.

Note: This is basically saying that given a field $K$, any polynomial of degree $n$ in $K[x]$ has at most $n$ distinct roots.

Fundamental Theorem of Algebra is an assertion of the fact that $\mathbb{C}$ is algebraically closed, and the $K$ above need not be algebraically closed.

share|improve this answer
add comment

You don't need the fundamental theorem of algebra or the Vandermonde determinant, only the factor theorem.

Proposition: A polynomial of degree at most n with more than n roots vanishes identically.

Proof: By induction. The base case is $n=0$, which is obvious. Now take a polynomial f of degree at most n, and let $x_1,\ldots,x_{n+1}$ be distinct roots of f. By the factor theorem, we can write $$f(x) = (x-x_{n+1})g(x)$$ where g plainly has degree at most $n-1$. Now substitute $x = x_i$ for $i=1,\ldots,n$. For all these values of x the left hand side vanishes and the factor $(x_i-x_{n+1})$ is nonzero. Hence all these $x_i$ must be roots of g and by induction g is identically zero. QED

This same proof works over any field (or even integral domain).

share|improve this answer
    
for polynomials $f,g\in K[x]$ there are $q,r\in K[x]$ such that $f=qg+r$ with $\text{deg}(r)<\text{deg}(g)$ or $r=0$ (polynomial division). if $f(\alpha)=0$, take $g(x)=x-\alpha$ to get $0=f(\alpha)=r$. Hence $r=0$ and $f(x)=q(x)(x-\alpha)$. –  yoyo Mar 8 '11 at 21:18
add comment

The following literature may be of use here:

Theorem. A polynomial $\text{f}$ of degree $\text{n}$ over a field $\text{F}$ has at most $\text{n}$ roots in $\text{F}$.*

Proof. The results is obviously true for polynomials of degree $0$ and degree $1$. We assume it to be true for polynomials of degree $n-1$. If $a$ is a root of $f$, $f=(x-a)q$ wehere $q$ has degree $n-1$. Since $f(b)=0$ if and only if $a=b$ or $q(b)=0$, it follows by our inductive assumption that $f$ has at most $n$ roots. $\Box$

share|improve this answer
    
Most elegant proof of the lot. –  Noldorin Apr 30 at 17:25
add comment

Just a clarification here. The Fundamental Theorem of Algebra says that a polynomial of degree n will have exactly n roots (counting multiplicity). This is not the same as saying it has at most n roots. To get from "at most" to "exactly" you need a way to show that a polynomial of degree n has at least one root. Then you can proceed by induction.

There are lots of different kinds of proofs that a polynomial must have at least one root. None of them are totally trivial.

share|improve this answer
add comment

There's probably a simple proof based on the fact that every polynomial of degree n has at most (n - 1) turning points. Clearly and without rigorous proof this points directly to the more general quality of a polynomial of degree n : it can only take on at most n identical values. And since the roots are a specific case when the value is 0, there clearly can be at most n roots.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.