# 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?

-

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.

-
There is no need to check what the degree is. The Lagrange interpolation formula produces the polynomial of least degree that interpolates through the $k$ points. The apparent degree is $k-1$ since $L(x)$ is the weighted sum of polynomials of degree $k-1$, but the sum can have smaller degree, and indeed has the minimal degree. – Dilip Sarwate May 8 '13 at 20:52
@DilipSarwate: You are correct, but I thought OP wanted to know the exact degree of the polynomial. If not, there is no need. – Ross Millikan May 8 '13 at 21:30

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.

-
This is sometimes called Newtonian interpolation. – Dilip Sarwate May 8 '13 at 20:21
thank you for your answer – user2128547 May 8 '13 at 20:25

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) = \dfrac{\prod_{i \neq k}(a-a_i)}{(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}$$

-
yes n - 1 might not be the minimum degree – user2128547 May 8 '13 at 20:21
"might not be of minimum degree" Err no. The Lagrange interpolation formula does give the polynomial of least degree that interpolates through the $k$ points. Each $L_j(a)$ is of degree $k-1$ but their weighted sum $L(a)$ can have smaller degree. Indeed, if $M(a)$ is the polynomial of least degree (assumed to be smaller than $k-1$) that interpolates through the $k$ points, then $L(a)-M(a)$ of degree $k-1$ has $k$ roots $a_1, a_2, \ldots, a_k$ and so must be identically $0$. So the weighted sum $\sum_j b_jL_j(a)$ does have smaller degree than its constituent parts in this case. – Dilip Sarwate May 8 '13 at 20:46
thank you...I understand now! – user2128547 May 9 '13 at 10:09