Polynomial proof

This is another problem from I.M Gelfand's book that I am stuck with.

Problem 169. Assume that $x_1,\ldots,x_{10}$ are different numbers, and $y_1,\ldots,y_{10}$ are arbitrary numbers. Prove that there is one and only one polynomial $P(x)$ of degree not exceeding $9$ such that $P(x_1)=y_1,P(x_2)=y_2,\ldots,P(x_{10})=y_{10}$.

Chapter is about polynomial interpolation. Any kind of hints would be appreciated. Thanks in advance.

-
Look up Lagrange Interpolation. –  André Nicolas Nov 10 '12 at 18:23

Because of a mild allergy to subscripts, I will solve a smaller problem. Let $a,b,c,d$ be distinct numbers, and let $p,q,r,s$ be any numbers. Find a polynomial $P(x)$ of degree $\le 3$ such that $P(a)=p$, $P(b)=q$, $P(c)=r$, and $P(d)=s$.

We use the polynomial $$P(x)=A(x-b)(x-c)(x-d)+B(x-a)(x-c)(x-d)+C(x-a)(x-b)(x-d)+D(x-a)(x-b)(x-c),$$ where the numbers $A$, $B$, $C$, and $D$ will be chosen soon.

Note that when we substitute $a$ for $x$ in our expression for $P(x)$, the last three terms die. So $$P(a)=A(a-b)(a-c)(a-d).$$ We want $P(a)=p$. That is easy to arrange by choosing $$A=\frac{p}{(a-b)(a-c)(a-d)}.$$ In essentially the same way, we can determine $B$, $C$, and $D$. It is no harder to deal with $10$ points, or $100$.

The uniqueness part is standard field theory.

Remark: If we are in a subscript mood, we can write out a solution of the problem for general $n$. Let $$Q_i(x)=\frac{\prod_{j=1}^n (x-x_j)}{x-x_i}.$$ Despite appearances, $Q_i(x)$ is a polynomial, indeed one of degree $n-1$. It is the product of all terms $x-x_j$ except $x-x_i$. Let $$P(x)=A_1Q_1(x)+A_2Q_2(x)+A_3Q_3(x)+\cdots+A_nQ_n(x),$$ where the $A_i$ are constants that will be chosen soon. If we let $$A_i=\frac{y_i}{Q(x_i)},$$ then $P(x)$ has the desired properties. Nice compact proof. But it may be hard to see what is really going on without going through a few concrete examples, or general examples but for a small $n$, like the $n=4$ we dealt with above.

-
Thank you! I think I understand this proof, especially the subscript one, I will try to work out some concrete examples to fully understand it, thanks for help Nicolas. –  Paul Dirac Nov 11 '12 at 6:27
Remark that such Lagrange interpolation is just a special case of CRT (Chinese Remainder Theorem). It is instructive to examine the relationship. –  Bill Dubuque Nov 11 '12 at 10:41
@BillDubuque I will read about it on wikipedia. Thanks. –  Paul Dirac Nov 11 '12 at 16:30

I want to thank everyone for help. I also discovered another way to prove this, by the method that @Thomas Andrews & @sperners lemma suggested in my earlier question.

Let's suppose that $q(x)$ is a polynomial of degree no greater then 9, such that $q(x_1)=y_1,\ldots ,q(x_{10})=y_{10}$, and also let $r(x)=p(x)-q(x).$ $r(x)$ is polynomial of degree no greater then 9 such that $r(x_1)=p(x_1)-q(x_1)=y_1-y_1=0,\ldots,r(x_{10})=p(x_{10})-q(x_{10})=y_{10}-y_{10}=0$. So $y_1,\ldots,y_{10}$ are all roots of $r(x)$ which is impossible since $r(x)$ is degree less then 10 unless $r(x)=0$, in which case, $p(x)-q(x)=0$, which means that $p(x)=q(x)$, this proves that there is only one polynomial of degree no greater than 9 that has such values.

-

Hint $\rm\ p(x_1) = y_1\Rightarrow\:p(x) - y_1 = (x\!-\!x_1)\, q(x)\:\Rightarrow\: y_k - y_1 = (x_k\!-\!x_1)\, q(x_k),\:$ for $\rm\:x_k\ne x_1.\:$ By induction on degree we can solve this for $\rm\:q\:$ such that $\rm\:q(x_k) = (y_k-y_1)/(x_k-x_1).$

-

Let $\mathbb R[X]_{\le 9}$ denote that the $\mathbb R$-vector space of polynomials with degree not exceeding $9$. Consider the $\mathbb R$-linear map $\Phi\colon \mathbb R[X]_{\le 9} \to \mathbb R^{10}$, $\Phi(P) = \bigl(P(x_1), \ldots, P(x_{10})\bigr)$. Then $\Phi$ is one to one: As $P \in \mathbb R[X]_{\le 9}$ with $\Phi(P) = 0$, we have $P(x_1) = \cdots = P(x_{10}) = 0$. As $P$ has degree at most 9, it can have it most 9 zeros (unless $P = 0$). As the $x_i$ are different, $P = 0$. So $\ker \Phi = \{0\}$ and $\Phi$ is one-to-one.

Note now, that we have $\dim \mathbb R[X]_{\le 9} = 10 = \dim\mathbb R^{10}$ (a basis of the former being $1 = X^0$, $X^1, \ldots$, $X^9$), so $\Phi$ is an isomorphism. So for each $y \in \mathbb R^{10}$, $P = \Phi^{-1}(y)$ is the only polynomial with $P(x_{i}) = y_i$ for $1 \le i \le 10$.

-
Thank you for your effort but as you can see, I tagged this question as [algebra-precalculus] so I can't really understand enough linear algebra to read what you wrote. but +1 anyway. –  Paul Dirac Nov 10 '12 at 18:33

In general let $P$ and $Q$ be degree $n$ polynomials that coincide in $n+1$ places, then $P-Q$ is a degree $\le n$ polynomial which is zero in $n+1$ places, but a polynomial can not have more zeros than its degree so $P-Q = 0$ and hence $P=Q$.

-
Thanks. I know that proof, I used it for previous problems but I don't understand how that applies to current problem. +1 and I will think about it, thanks for help. –  Paul Dirac Nov 10 '12 at 18:40