Birkhoff interpolation

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.[2]

An important problem in the theory of Birkhoff interpolation is to classify those problems that have a unique solution. Schoenberg[3] 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 George Pólya.[4] Let S_m 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 S_m ≥ m for all m. Schoenberg showed that this is a necessary condition for all values of k.