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.

A degree-$d$ polynomial is uniquely characterized by its values at any $d+1$ distinct points.

Could someone explain why the statement above is necessarily true?

share|improve this question
    
Look up polynomial interpolation and the Vandermonde matrix. –  J. M. May 12 '12 at 16:12
4  
This is equivalent to saying that a degree-$d$ polynomial which is equal to zero at $d + 1$ distinct points is identically zero. To prove this you can use the factor theorem (if $p(a) = 0$ then $p(x) = (x - a) q(x)$ for some polynomial $q$). There's no need to use the Vandermonde matrix. –  Qiaochu Yuan May 12 '12 at 16:18
    
You can show it using linear algebra. The system $$\underbrace{V}_{(d+1)\times (d+1)}\overbrace{x}^{(d+1)\times 1} = \underbrace{b}_{(d+1)\times 1}$$ has a unique solution if $V$ has full rank. –  user2468 May 12 '12 at 16:19

1 Answer 1

up vote 7 down vote accepted

If you write down a general polynomial of degree $d$, i.e. with $d+1$ coefficients $a_i$ and plug in your $d+1$ given points, you will get $d+1$ independent equations in $d+1$ variables.

Edit 1: Another, less constructive, proof is to assume there are two different polynomials $f$ and $g$ of degree $d$ which have the same value at $d+1$ points. Then their difference $f-g$ is a non zero polynomial of degree $\leq d$ with at least $d+1$ zeros. But if $x_0$ is a zero, then $(x-x_0)|(f-g)$. You can easily show that this is a contradiction.

Edit 2: Or you could prove it by induction. Assume you have a unique polynomial $f$ of degree $d-1$ which has the desired value at $d$ distinct points (the case d=1 is easy). For a polynomial $g$ of degree $d$ which has the requested value at all of you $d+1$ points you have $g-f$ is of degree $d$ and has $d$ given zeros. Therefore it has $d$ fixed linear factors and has only a degree of freedom in the scalar factor. This factor is then uniquely determined by the $(d+1)^{st}$ point.

share|improve this answer

Your Answer

 
discard

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