Minimum degree of a polynomial passing through points If $P(x)$ is a polynomial such that $P(a_{1})=b_{1}, P(a_{2})=b_{2}, \ldots , P(a_{k})=b_{k}$, how can I find the polynomial which has minimum degree and for whom the relations above are true?
 A: You can use Lagrange interpolation to find the polynomial.  It will have degree at most $k-1$  It will take some work to see if the degree is less.
A: Given $k$ distinct points, from the fundamental theorem of algebra, we can find a polynomial of degree at most $k-1$ passing through these $k$ points. This polynomial is called the Lagrange polynomial and this interpolation is known as Lagrange interpolation.
The Lagrange polynomial is found as follows: First compute
$$L_j(a)\:=\:\prod_{i \neq j}{a-a_i\over a_j-a_i}\,.$$
Note that $L_j(x)$ is a polynomial in $a$ of degree $k-1$ and has the property that $L_j(a_i) = \delta_{ij}$, where $\delta_{ij}$ is the Kronecker delta. Now, the Lagrange polynomial you are after is given by
$$L(a) = \sum_{j=1}^k b_j L_j(a)$$
The degree of this interpolating polynomial is nothing but the rank of the following matrix
$$\begin{bmatrix}1 & a_1 & a_1^2 & \cdots a_1^{k-1} & b_1\\ 1 & a_2 & a_2^2 & \cdots a_2^{k-1} & b_2\\ 1 & a_3 & a_3^2 & \cdots a_3^{k-1} & b_3\\ \vdots & \vdots & \vdots & \ddots \vdots & \vdots\\ 1 & a_k & a_k^2 & \cdots a_k^{k-1} & b_k\\\end{bmatrix}$$
A: Naively, you could construct the interpolating polynomial through the first $t$ points, and see if it passes through the others.  If not, increase $t$ by one.  By the time $t=k$ you will definitely have one.
