Editing Birkhoff interpolation (section)

==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 <math>P(x)</math> such that <math>P(-1)=P(1)=0</math> and <math>P^{(1)}(0)=1</math>. On the other hand, the Birkhoff interpolation problem where the values of <math>P^{(1)}(-1), P(0)</math> and <math>P^{(1)}(1)</math> are given always has a unique solution.<ref>{{Cite web |title=American Mathematical Society |url=https://www.ams.org/journals/bull/1983-09-03/S0273-0979-1983-15204-7/home.html |access-date=2022-05-19 |website=American Mathematical Society |language=en}}</ref>

An important problem in the theory of Birkhoff interpolation is to classify those problems that have a unique solution. [[Isaac Jacob Schoenberg|Schoenberg]]<ref>{{Cite journal |last=Schoenberg |first=I. J |date=1966-12-01 |title=On Hermite-Birkhoff interpolation |journal=Journal of Mathematical Analysis and Applications |language=en |volume=16 |issue=3 |pages=538–543 |doi=10.1016/0022-247X(66)90160-0 |issn=0022-247X|doi-access=free }}</ref> formulates the problem as follows. Let <math>d</math> denote the number of conditions (as above) and let <math>k</math> be the number of interpolation points. Given a <math>d\times k</math> matrix <math>E</math>, all of whose entries are either <math>0</math> or <math>1</math>, such that exactly <math>d</math> entries are <math>1</math>, then the corresponding problem is to determine <math>P(x)</math> such that
:<math> P^{(j)}(x_i) = y_{i,j} \qquad\forall (i,j) / e_{ij} = 1 </math>
The matrix <math>E</math> is called the '''incidence matrix'''. For example, the incidence matrices for the interpolation problems mentioned in the previous paragraph are:
:<math> \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \end{pmatrix} \qquad\mathrm{and}\qquad \begin{pmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{pmatrix}. </math>
Now the question is: Does a Birkhoff interpolation problem with a given incidence matrix <math>E</math> have a unique solution for any choice of the interpolation points?


The case with <math>k=2</math> interpolation points was tackled by [[George Pólya]] in 1931.<ref>{{Cite journal |last=Pólya |first=G. |date=1931 |title=Bemerkung zur Interpolation und zur Näherungstheorie der Balkenbiegung |url=https://onlinelibrary.wiley.com/doi/10.1002/zamm.19310110620 |journal=ZAMM - Zeitschrift für Angewandte Mathematik und Mechanik |language=de |volume=11 |issue=6 |pages=445–449 |doi=10.1002/zamm.19310110620|bibcode=1931ZaMM...11..445P }}</ref> Let <math>S_m</math> denote the sum of the entries in the first <math>m</math> columns of the incidence matrix:
:<math> S_m = \sum_{i=1}^k \sum_{j=1}^m e_{ij}. </math>
Then the Birkhoff interpolation problem with <math>k=2</math> has a unique solution if and only if <math>S_m\geqslant m \quad\forall m</math>. Schoenberg showed that this is a necessary condition for all values of <math>k</math>.