3
$\begingroup$

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?

  • 0
    Look up polynomial interpolation and the Vandermonde matrix.2012-05-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.2012-05-12
  • 0
    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.2012-05-12

1 Answers 1

9

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.