# Birkhoff interpolation

In mathematics, Birkhoff interpolation is an extension of polynomial interpolation. It refers to the problem of finding a polynomial p of degree d such that certain derivatives have specified values at specified points:

${\displaystyle p^{(n_{i})}(x_{i})=y_{i}\qquad {\mbox{for }}i=1,\ldots ,d,}$

where the data points ${\displaystyle (x_{i},y_{i})}$ and the nonnegative integers ${\displaystyle n_{i}}$ are given. It differs from Hermite interpolation in that it is possible to specify derivatives of p at some points without specifying the lower derivatives or the polynomial itself. The name refers to George David Birkhoff, who first studied the problem in Birkhoff (1906).

## Existence and uniqueness of solutions

In contrast to Lagrange interpolation and Hermite interpolation, a Birkhoff interpolation problem does not always have a unique solution. For instance, there is no quadratic polynomial ${\displaystyle \textstyle p}$ such that ${\displaystyle \textstyle p(-1)=p(1)=0}$ and ${\displaystyle \textstyle p'(0)=1}$. On the other hand, the Birkhoff interpolation problem where the values of ${\displaystyle \textstyle p'(-1)}$, ${\displaystyle \textstyle p(0)}$ and ${\displaystyle \textstyle p'(1)}$ are given always has a unique solution (Passow 1983).

An important problem in the theory of Birkhoff interpolation is to classify those problems that have a unique solution. Schoenberg (1966) formulates the problem as follows. Let d denote the number of conditions (as above) and let k be the number of interpolation points. Given a d-by-k matrix E, all of whose entries are either 0 or 1, such that exactly d entries are 1, then the corresponding problem is to determine p such that

${\displaystyle p^{(j)}(x_{i})=y_{i,j}\qquad {\text{for all }}(i,j){\text{ with }}e_{ij}=1.}$

The matrix E is called the incidence matrix. For example, the incidence matrices for the interpolation problems mentioned in the previous paragraph are:

${\displaystyle {\begin{bmatrix}1&0&0\\0&1&0\\1&0&0\end{bmatrix}}\quad {\text{and}}\quad {\begin{bmatrix}0&1&0\\1&0&0\\0&1&0\end{bmatrix}}.}$

Now the question is: does a Birkhoff interpolation problem with a given incidence matrix have a unique solution for any choice of the interpolation points?

The case with k = 2 interpolation points was tackled by Pólya (1931). Let Sm denote the sum of the entries in the first m columns of the incidence matrix:

${\displaystyle S_{m}=\sum _{i=1}^{k}\sum _{j=1}^{m}e_{ij}.}$

Then the Birkhoff interpolation problem with k = 2 has a unique solution if and only if Smm for all m. Schoenberg (1966) showed that this is a necessary condition for all values of k.