Polynomial interpolation

February 14, 2020

From Axler’s Linear Algebra Done Right, chapter 4, exercise 5:

Suppose mm is a nonnegative integer, z1,,zm+1z_1, \dots, z_{m+1} are distinct elements of F\mathbb{F}, and w1,,wm+1Fw_1, \dots, w_{m+1} \in \mathbb{F}. Prove that there exists a unique polynomial pPm(F)p \in \mathcal{P}_m(\mathbb{F}) such that p(zj)=wjp(z_j) = w_j for j=1,,m+1j = 1, \dots, m+1

[This result can be proved without using linear algebra. However, try to find the clearer, shorter proof that uses some linear algebra.]

If p0p \ne 0 then as pp is at most degree mm, there are at most mm distinct zz’s such that p(z)=0p(z)=0. Equivalently, if pp had at least m+1m+1 distinct zz’s such that p(z)=0p(z)=0, then p=0p=0. Letting

Z=[1z1z12z1m1z2z22z2m1zm+1zm+12zm+1m]Z = \begin{bmatrix} 1 & z_1 & z_1^2 & \dots & z_1^m \\ 1 & z_2 & z_2^2 & \dots & z_2^m \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & z_{m+1} & z_{m+1}^2 & \dots & z_{m+1}^m \\ \end{bmatrix}

then the previous statement implies that null Z={0}\text{null } Z = \{0\}, so ZZ is injective. As ZZ is square, [Axler 3.69] implies that ZZ is invertible. Hence, if

Z1([w1w2wm+1])=[a0a1am]\begin{aligned} Z^{-1}\left(\begin{bmatrix} w_1 \\ w_2 \\ \vdots \\ w_{m+1}\end{bmatrix}\right) = \begin{bmatrix} a_0 \\ a_1 \\ \vdots \\ a_{m}\end{bmatrix} \end{aligned}

then the polynomial p(z)=a0+a1z+a2z2++amzmp(z)=a_0 + a_1 z + a_2 z^2 + \dots + a_m z^m is the unique polynomial such that p(zj)=wjp(z_j) = w_j for j=1,,m+1j = 1, \dots, m+1.