arXiv:1704.08563v2 [] 29 Sep 2017

THE SET OF UNATTAINABLE POINTS FOR THE RATIONAL
HERMITE INTERPOLATION PROBLEM
TERESA CORTADELLAS BENÍTEZ, CARLOS D’ANDREA, AND EULÀLIA MONTORO
Abstract. We describe geometrically and algebraically the set of unattainable points for the Rational Hermite Interpolation Problem (i.e. those points
where the problem does not have a solution). We show that this set is a
union of equidimensional complete intersection varieties of odd codimension,
the number of them being equal to the minimum between the degrees of the
numerator and denominator of the problem. Each of these equidimensional varieties can be further decomposed as a union of as many rational (irreducible)
varieties as input data points. We exhibit algorithms and equations defining
all these objects.

1. Introduction
Let K be a field, k, l, n1 , . . . , nl ∈ Z>0 with k ≤ n := n1 +. . .+nl . For u1 , . . . , ul ∈
K with ui 6= uj if i 6= j, and vi,j ∈ K with i = 1, . . . , l, j = 0, . . . , ni − 1, The
Rational Hermite Interpolation Problem (RHIP) associated with this data as stated
in [Sal62, Kah69, Sal84, SW91], is the following: decide if there exist -and if so
compute- polynomials A(x), B(x) ∈ K[x] of degrees bounded by k − 1 and n − k
respectively such that B(ui ) 6= 0 for all i = 1, . . . , l, and
 (j)
A
(ui ) = j!vi,j , i = 1, . . . , l, j = 0, . . . , ni − 1.
(1)
B

The factorial in the equation above is introduced to simplify some of the formulas
that will appear later. For (1) to be as general as possible, we need to impose
Char(K) = 0 or Char(K) ≥ max{n1 , . . . , nl }. When l = n (i.e. n1 = . . . =
nl = 1), the RHIP coincides with the classical Rational Interpolation Problem
[Cau41, Wuy75, SW86]. If k = n, the RHIP descends to the well-known Hermite
Interpolation Problem. But in contrast with it, there is not always a solution for
the RHIP for any input data. For instance, if we set k = 2, l = 2, n1 = 2, n2 =
1, u1 = 1, u2 = 2, v1,0 = 1, v1,1 = 0, v2,0 = 0, one can check straightforwardly that
there is no solution for (1), see Example 1.2 below.
The standard approach to this problem from both an algorithmic and complexity point of view is via the Extended Euclidean Algorithm as it is explained in
[vzGG13] (see also [Ant88], and §2.1 in this text). There are also alternative approaches by using structured matrices ([VBB92, BL00]), barycentric coordinates
Date: October 3, 2017.
2010 Mathematics Subject Classification. Primary 14Q15 ; Secondary 13P05, 68W30.
Key words and phrases. Rational Hermite Interpolation, Unattainable Points, Equidimensional
Varieties, Rational Varieties, Complete Intersections, Structured Matrices.
Cortadellas and D’Andrea are supported by the Spanish MEC research project MTM201340775-P, Montoro by the Spanish MINECO/FEDER research project MTM 2015-65361-P .
1

2

TERESA CORTADELLAS BENÍTEZ, CARLOS D’ANDREA, AND EULÀLIA MONTORO

([SW86, SW91]), orthogonal polynomials ([EK89, Gem93]), and computation of
syzygies ([Rav97]). Barycentric coordinates seem to be stable when working with
approximate data, but not very fast, while the use of orthogonal polynomials is
efficient thanks to the use of Jacobi’s method for inverting matrices, but their results are limited to the rational interpolation problem (without multiplicities) only.
Parametric representations of the solutions in general situations can be found in
[Las03, DKS15].
In all the previous results, optimal bounds of complexity are achieved, and parametric expressions for A(x) and B(x) are given when they exist, but an explicit
description of the set of the so called unattainable points for the RHIP, i.e. the set
of data {ui , vi,j } such that the RHIP does not have solutions, cannot be obtained
straightforwardly from these approachs. The purpose of this paper is to characterize them both geometrically and algebraically. Our main result, given in Theorems
1.1 and 1.4 states that the set of ill-posed point is a union of min{k − 1, n − k}
equidimensional complete intersection varieties of odd codimension. Moreover, each
of these l varieties can be further decomposed as a union of l rational (irreducible)
varieties. As a by-product, we will produce explicit expressions for the solution for
this problem valid in different regions of the space of parameters, and alternative
algorithms based only in elementary Linear Algebra, without the need of applying
neither barycentric coordinates, nor the Euclidean Division Algorithm. The complexity of solving these problems as well as the extension of the methods in [EK89]
to the RHIP will be the subject of a future paper.
To deal with the input data properly, we set n = (n1 , . . . , nl ), u = (u1 , . . . , ul ), vi =
(vi,0 , . . . , vi,ni −1 ), 1 ≤ i ≤ l, and v = (v1 , . . . , vl ). For j, t ∈ N, we define the tth Pochhammer symbol as follows: (j)0 = 1, (j)t = j · (j − 1) . . . (j − t + 1).
The Weak Hermite Interpolation Problem (WHIP), asks to compute polynomials
Au,v,n,k−1 (x), Bu,v,n,n−k (x) ∈ K[x] of degrees bounded by k − 1 and n − k respectively such that
(2)

(j)
Au,v,n,k−1 (ui )

=

j
X

(j−t)

(j)t vi,t Bu,v,n,n−k (ui ), i = 1, . . . , l, j = 0, . . . , ni − 1.

t=0

It is easy to verify that any solution of (1) also satisfies (2), but not the other
way around as Bu,v,n,n−k (x) may vanish at some of the ui ’s; that is, if B(ui ) 6= 0
for i = 1, . . . , l, then WHIP and RHIP are equivalents. In contrast, given the
input data (u, v) as before, (2) leads to a homogeneous linear system of equations
in the coefficients of the polynomials Au,v,n,k−1 (x), Bu,v,n,n−k (x) of n equations
with n + 1 unknowns, so there is always a non trivial solution of it. Indeed, let
Mu,v,n,k ∈ Kn×(n+1) be the matrix of the linear system (2). Computing it explicitly,
we have


Mu1 ,v1 ,k,n


..
(3)
Mu,v,n,k = 
,
.
Mul ,vl ,k,n

where
(4)

and

Mui ,vi ,k,n =

M Lui ,vi ,k,n

| M Rui ,vi ,k,n



∈ Kni ×(n+1)

UNATTAINABLE POINTS FOR RATIONAL HERMITE INTERPOLATION





M Lui ,vi ,k,n = 


(5)

1
0
..
.

ui
1
..
.

u2i
2ui
..
.

0

0

0

...
...
...
...

(6)


M Rui ,vi ,k,n = 






,


−vi,0 uin−k

− t=0 n−k
vi,1−t un−k−t
i
t
..
.
...
Pni −1 n−k
−(vi,ni −1 ui + vi,ni −2 ) . . . − t=0
vi,ni −1−t un−k−t
i
t

−vi,0
−vi,1
..
.



uik−1

k−1 k−2
1 ui
..
.

k−1
k−ni
ni −1 ui

3

−vi,0 ui
−(vi,1 ui + vi,0 )
..
.

−vi,ni −1


k

...
...

P1

with j = 0 if j > k. Note that the coefficients of a solution of the WHIP, sorted
properly, are elements of the kernel of (3). We will see in Proposition 2.1 that all
the nontrivial pairs Au,v,n,k−1 (x), Bu,v,n,n−k (x) ∈ K[x] solving the WHIP, up to a
Au,v,n,k−1 (x)
constant, produce the same fraction Bu,v,n,n−k
(x) ∈ K(x), which will be the solution
of the RHIP if the “reduced” fraction is also a solution of the WHIP (Theorem 2.6).
So, finding non trivial solutions of the WHIP “almost” solves the RHIP. And it is
of interest of course to get the “minimal” solution (the one with minimal degree) of
this problem, which it is known (see Proposition 2.5) to be unique up to a constant.
If Mu,v,n,k has maximal rank, then the solution to the WHIP is given by the
maximal minors of this matrix. Otherwise, some non trivial Linear Algebra must be
performed in order to find a non-zero vector in the kernel of this matrix. Our aim is
to give an explicit algebraic formulation in terms of the input data (u, v) which will
allow us to produce solutions of the WHIP in all the cases as functions of minors of
suitable matrices. This approach will also give us a full description of the unattainable points for the RHIP. To do this, we need to consider matrices like (3), but in a
more general setting: denote with U1 , . . . , Ul , V1,0 , . . . , V1,n1 −1 , . . . , Vl,0 , . . . , Vl,nl −1
a set of l + n indeterminates over K, and set U = (U1 , . . . , Ul ), V = (V1 , . . . , Vl ).
For α, β, ∈ Z≥0 , and n := (n1 , . . . , nl ) ∈ Zl≥0 , we set


Mα,β,n1 (U1 , V1 )


..
(7)
Mα,β,n (U, V) = 
,
.





,


Mα,β,nl (Ul , Vl )

where for i = 1, . . . , l, Mα,β,ni (Ui , Vi ) stands for

(8)






=




1

Ui

Ui2

...

0

1

2Ui

.
.
.

.
.
.

.
.
.

...

0

0

0

...

...

α
 Ui
α
Uiα−1
1

−Vi,1

−(Vi,1 Ui + Vi,0 )

.
.
.

.
.
.

.
.
.

...

−Vi,ni −1

−(Vi,ni −1 Ui + Vi,ni −2 )

...

α−(ni −1)
α
Ui
ni −1





−Vi,0 Ui

−Vi,0

β

...
...

−

−V
 i,0
 Ui
β−t
β
t=0 t Vi,1−t Ui

P1

.
.
.
−

Pni −1 β 
t=0

t

For (u, v) ∈ Kl × Kn , note that Mu,v,n,k = Mk−1,n−k,n (u, v). In the case α + β =
n − 1, for i = 1, . . . , n + 1, we set ∆n
α+1,i to be the signed i-th maximal minor of
Mα,β,n (U, V). Let Z ⊂ Kl be the algebraic set defined by
Y
Z = {(u1 , . . . , ul ) ∈ Kl :
(ui − uj ) = 0}.
1≤i<j≤n

β−t

Vi,ni −1−t Ui







.




4

TERESA CORTADELLAS BENÍTEZ, CARLOS D’ANDREA, AND EULÀLIA MONTORO

l
Our input
 u nwill be an element of K \ Z. So, the initial data can be taken from
l
K \ Z × K . Our first main result is the following:

Theorem 1.1. Let k, n1 , . . . , nl ∈ N, 1 ≤ k ≤ n1 + . . . + nl =: n, and K a field
with Char(K) = 0 or Char(K) ≥ max{n1 , . . . , nl }. Set m := min{k − 1, n − k}. The
set of unattainable points for the RHIP is a disjoint union B1 ⊔ B3 ⊔ . . . ⊔ B2m−1 ,
where, for j = 1, . . . , m, B2j−1 is the union of the following 2l constructible sets in
(Kl \ Z) × Kn with the Zariski topology:

(9)
Pn−2j+2
ℓ−k+j−1
n
n
∆n
= 0, ∆n
k−j+2,k−j+2 = · · · = ∆k+j−1,k+j−1 =
k−j+1,k−j+1 6= 0
ℓ=k−j+1 ∆k−j+1,ℓ+1 Ui
and
Pn
ℓ−k−j+1
n
n
∆n
= 0, ∆n
k−j+2,k−j+2 = · · · = ∆k+j−1,k+j−1 =
k+j,k+j 6= 0,
ℓ=k+j−1 ∆k+j−1,ℓ+1 Ui

for 1 ≤ i ≤ l (if j = 1 there is only one equation, and two inequalities above). The
n
two sets in (9) coincide in {∆n
k−j+1,k−j+1 6= 0} ∩ {∆k+j,k+j 6= 0}. If K is algebraically closed, B2j−1 is the union of l rational irreducible varieties of codimension
2j − 1 in (Kl \ Z) × Kn .
This result follows immediately from Theorems 3.13 and 4.11.
Example 1.2. For our example above, we have k = 2, l = 2, n = (2, 1). So, n = 3,
and m = 1. According to Theorem 1.1, the set of unattainable points coincide with
B1 . Computing it explicitly from (9), we get

 

n
n
n
n
n
B1 = {∆n
+
∆
U
=
0}
∪
{∆
+
∆
U
=
0}
∩
{∆
=
6
0}
∪
{∆
=
6
0}
,
1
2
2,3
2,4
2,3
2,4
2,2
3,3

where the minors ∆n
2,j , j = 2, 3, 4, are extracted from


1 U1
M1,1,n (U, V) =  0 1
1 U2

−V1,0
−V1,1
−V2,0


−V1,0 U1
−V1,1 U1 − V1,0  ,
−V2,0 U2

while ∆n
3,3 is the minor obtained by deleting the third column in


1 U1
M2,0,n (U, V) =  0 1
1 U2

U12
2U1
U22


−V1,0
−V1,1  .
−V2,0

Computing all these expressions, we get
∆n
2,2
∆n
3,3
n
∆n
2,3 + ∆2,4 U1
n
n
∆2,3 + ∆2,4 U2

=
=
=
=

2
− V1,0 V2,0 − U1 V1,1 V2,0 + U2 V1,1 V2,0
V1,0
(U2 − U1 )2
.
(V2,0 − V1,0 )(U2 − U1 )
V1,1 (U1 − U2 )2

From the above we deduce that B1 = {V1,0 = V2,0 , V1,1 6= 0} ∪ {V1,1 = 0, V1,0 6=
V2,0 }, a union of two rational (actually linear) varieties. In the situation above, we
have that v1,1 = 0, and hence we conclude that (1, 2; (1, 0), (0)) is an unattainable
point for the RHIP.

UNATTAINABLE POINTS FOR RATIONAL HERMITE INTERPOLATION

5

Example 1.3. Set n = 5, k = 3, l = 1, so we have n = (5), and m = 2. To compute
their equations, the matrices to be considered are
(10)
 1 U1 −V1,0
−V1,0 U1
−V1,0 U 2
−V1,0 U 3
1

M1,3,(5) (U, V) = 





M2,2,(5) (U, V) = 







M3,1,(5) (U, V) = 



0
0
0
0

1
0
0
0

−V1,1
−V1,2
−V1,3
−V1,4

−V1,1 U1
−V1,2 U1
−V1,3 U1
−V1,4 U1

1 U1
0 1
0 0
0 0
0 0
1 U1
0 1
0 0
0 0
0 0

U12
2U1
1
0
0
U12
2U1
1
0
0

−V1,0
−V1,1
−V1,2
−V1,3
−V1,4
U13
3U12
3U1
1
0

1 U1
0 1
0 0
0 0
0 0

U12
2U1
1
0
0

U13
3U12
3U1
1
0

and





M4,0,(5) (U, V) = 



−
−
−
−

V1,0
V1,1
V1,2
V1,3

−V1,1 U12 − 2V1,0 U1
−V1,2 U12 − 2V1,1 U1 − V1,0
−V1,3 U12 − 2V1,2 U1 − V1,1
−V1,4 U12 − 2V1,3 U1 − V1,2

1

−V1,1 U13
−V1,2 U13
−V1,3 U13
−V1,4 U13

− 3V1,0 U12
− 3V1,1 U12 − 3V1,0 U1
− 3V1,2 U12 − 3V1,1 U1 − V1,0
− 3v1,3 U12 − 3V1,2 U1 − V1,1

−V1,0 U1
−V1,0 U12
−V1,1 U1 − V1,0
−V1,1 U12 − 2V1,0 U1
−V1,2 U1 − V1,1 −V1,2 U12 − 2V1,1 U1 − V1,0
−V1,3 U1 − V1,2 −V1,3 U12 − 2V1,2 U1 − V1,1
−V1,4 U1 − V1,3 −V1,4
U12 − 2V1,3 U1 − V1,2
−V1,0
−V1,0 U1
−V1,1 −V1,1 U1 − V1,0 

−V1,2 −V1,2 U1 − V1,1 
,
−V1,3 −V1,3 U1 − V1,2 
−V1,4 −V1,4 U1 − V1,3
U14
4U 13
6U12
4U1
1

−V1,0
−V1,1
−V1,2
−V1,3
−V1,4





.



From Theorem 1.1 we know that the set of unattainable points B decomposes as
B1 ⊔ B3 , where


(5)
(5)
(5)
(5)
(5)
B1 = {∆3,4 + ∆3,5 U1 + ∆3,6 U12 = 0} ∩ {∆3,3 6= 0} ∪ {∆4,4 6= 0} ,
(5)

(5)

is a rational variety of codimension 1, while B3 ⊂ {∆2,2 6= 0} ∪ {∆5,5 6= 0} can be
described as follows:
(5)

(5)

(5)

(5)

(5)

(5)

(5)

(5)

(5)

(5)

B3 ∩ {∆2,2 6= 0} = {∆3,3 = ∆4,4 = ∆2,3 + ∆2,4 U1 = 0},

(11)
and

B3 ∩ {∆5,5 6= 0} = {∆3,3 = ∆4,4 = ∆4,5 + ∆4,6 U1 = 0}.

(12)

We compute explicitly two of the polynomials defining this set:
(5)

(5)

∆4,5 + ∆4,6 U1
(5)
(5)
∆2,3 + ∆2,4 U1

=
=

V1,3 ,
2
2
3
3
− V1,0
V1,3
+ 2U13 V1,2
−V1,1
+ 2V1,0 V1,1 V1,2 + U12 V1,1 V1,2
2 2
2
3
2
−U1 V1,1 V1,3 − U1 V1,0 V1,2 V1,3 − 4U1 V1,1 V1,2 V1,3 + 2U13 V1,0 V1,3
2
3 2
3
+U1 V1,0 V1,1 V1,4 + 2U1 V1,1 V1,4 − 2U1 V1,0 V1,2 V1,4 .

Even though they are both very different expressions, an explicit computation shows
(5)
(5)
that in {∆5,5 6= 0 6= ∆2,2 }, both (11) and (12) are equal to:
V1,1 = 0, V1,2 = 0, V1,3 = 0,
which confirms the claim of Theorem 1.1 for this case. From this latter expression
we also deduce that B3 is a rational (linear) variety of codimension 3.





,





,

6

TERESA CORTADELLAS BENÍTEZ, CARLOS D’ANDREA, AND EULÀLIA MONTORO

The fact that several minors of different matrices as in (10) should be considered
is a consequence of the whole Extended Euclidean Algorithm one should perform
to deal with this problem (see Proposition 2.10). Being in the j-th component Bj
essentially means that the corresponding polynomials in the Bézout identity that
would solve the RHIP fail to reach their expected degree in at least j steps, and
hence one should test up to this number of “vanishing instances”.
Interestingly, one does not need to use several matrices to deal with the stratification of the set of unattainable points appearing in Theorem 1.1. Just the the
rank of Mu,v,n,k is enough. This is the content of our second main result:
Theorem 1.4. With notations and hypothesis as above, for (u, v) ∈ (Kl \ Z) × Kn,
and 1 ≤ j ≤ m + 1, (u, v) is such that the minimal solution of the WHIP associated
with this data has degrees bounded by k − j and n − k + 1 − j respectively if and
only if dimK (ker(Mu,v,n,k )) ≥ j. Moreover, dimK (ker(Mu,v,n,k )) = j if and only if
the degree bound turns into an equality.
The first situation is given by the following equations
n
n
∆n
k−j+2,k−j+2 = ∆k−j+3,k−j+3 = · · · = ∆k+j−1,k+j−1 = 0

(13)

(if j = 1, the above set of equations is empty), while the second one is the intersecn
tion of (13) with {∆n
k−j+1,k−j+1 6= 0} ∪ {∆k+j,k+j 6= 0}. A minimal solution for
the WHIP is given in this region by
(14)
 P

Pn−2j+2
k−j
n
ℓ
n
ℓ−k+j−1

in ∆n
k−j+1,k−j+1 6= 0,
ℓ=0 ∆k−j+1,ℓ+1 x ;
ℓ=k−j+1 ∆k−j+1,ℓ+1 x

P
P
n
k−j
ℓ−k−j+1
ℓ
n
n

in ∆n
k+j,k+j 6= 0.
ℓ=k+j−1 ∆k+j−1,ℓ+1 x
ℓ=0 ∆k+j−1,ℓ+1 x ;
If K is algebraically closed, (13) is a rational irreducible complete intersection variety in (Kl \ Z) × Kn of codimension 2(j − 1) in (Kl \ Z) × Kn .

This result follows from Theorems 2.6, 3.12, 4.8, and Proposition 4.9. Note that
for j = 1, both representations in (14) are the same up to a constant.
To illustrate Theorem 1.4 in our Example 1.2 above, as l = 2, k = 2, n = 3, n =
(2, 1), and m = 1, we have

(2,1)
(2,1)
• dimK ker(Mu,v,(2,1),2 ) = 1 ⇐⇒ {∆2,2 6= 0} ∪ {∆3,3 6= 0},

(2,1)
(2,1)
(2,1)
• dimK ker(Mu,v,(2,1),2 ) = 2 ⇐⇒ {∆2,2 = ∆3,3 = 0}, and {∆1,1 6=
(2,1)

0} ∪ {∆4,4 6= 0}.

Computing the last two minors, we get:

−V1,0
−V1,0 U1
(2,1)
∆1,1 = det  −V1,1 −V1,1 U1 − V1,0
−V2,0
−V2,0 U2
(2,1)

∆4,4
(2,1)



1
= det  0
1

(2,1)

U1
1
U2


−V1,0 U12
−V1,1 U12 − 2V1,0 U1  = 0,
−V2,0 U22


U12
2U1  = (U1 − U2 )2 ,
U22

6= 0} is actually equal to the whole ambient space (Kl \

(2,1)
Z) × Kn , and we have that dimK ker(Mu,v,(2,1),2 ) = 2 if and only if {∆2,2 =

so {∆1,1
(2,1)

6= 0} ∪ {∆4,4

∆3,3 = 0}. In the “generic” case, when the dimension is equal to one, a solution

UNATTAINABLE POINTS FOR RATIONAL HERMITE INTERPOLATION

7

(14) is given by the maximal minors of Mu,v,(2,1),2,3 , i.e.
(2,1) 
(2,1)
(2,1)
(2,1)
∆2,1 + ∆2,2 x; ∆2,3 + ∆2,4 x .

When dim = 2, (14) gives as solutions for the WHIP the nontrivial constant functions
(2,1)
(2,1)
(2,1) 
in ∆1,1 6= 0,
∆1,1 ; ∆1,2
(2,1)
(2,1)
(2,1) 
in ∆4,4 6= 0
∆3,1 ; ∆3,4
(2,1)

(2,1)

(The fact that ∆4,4 = ∆3,4 -see Lemma 4.1- shows that the second expression
above is also not identically zero).
The paper is organized as follows: in Section 2 we show that all the solutions
of the WHIP are polynomial multiples of a “minimal solution,” in the sense that
all other solutions are polynomial multiples of this one. We show in Theorem 2.6
that a minimal solution solves the RHIP if and only if its components are coprime
polynomials, and give an algorithm (Algorithm 2.7) to compute the minimal solution and verify if the RHIP is solvable based on these facts. We end that section by
reviewing the Extended Euclidean Algorithm’s classical method to deal with this
problem in light of our results in §2.1. All these theoretical results are well known
and documented in the literature (see [Wuy75, vzGG13]), we include them here to
set the notation within the context of the following statements, and also to set the
basis for the algorithms produced therein.
In Section 3 we look at the geometry of the problem. In Theorems 3.12 and 3.13
we show that the sets
 described above are proper union of open irreducible rational
varieties in Kl \ Z × (K× )n . Our proof is constructive, so we can develop an
algorithm (Algorithm 3.14) to deal with the RHIP without the need of computing
any solution of the WHIP.
In Section 4 we produce the equations which appear in (13) and (14), and complete with the proofs of the main theorems.
2. minimal solutions
All along the text we will assume that Char(K) = 0 or Char(K) ≥ max{n1 , . . . , nl }.
In this section, we look at the structure of solutions of the WHIP. We will see that
all of them are multiple of a so-called “minimal solution”, give an algorithm for
computing this minimal solution, and decide by looking at its decomposition if the
RHIP has a solution or not. We will compare our results with the classical standard
procedure for solving the RHIP via the Extended Euclidean Algorithm.

Proposition 2.1. Let (u, v) ∈ Kl \ Z ×Kn . For any solution (Au,v,n,k−1 (x), Bu,v,n,n−k (x))
Au,v,n,k−1 (x)
of the WHIP (2) with Bu,v,n,n−k (x) 6= 0, the rational function Bu,v,n,n−k
(x) is
unique.
Proof. If both (Au,v,n,k−1 (x), Bu,v,n,n−k (x)) and (Ãu,v,n,k−1 (x), B̃u,v,n,n−k (x)) satisfy (2), the polynomial
P (x) = Au,v,n,k−1 (x)B̃u,v,n,n−k (x) − Ãu,v,n,k−1 (x)Bu,v,n,n−k (x) ∈ K[x]
has degree bounded by n − 1, and its derivatives P (j) (x) vanishes in the different
points ui , i = 1 . . . , l for j = 0, . . . , ni − 1. Hence, P (x) must be identically zero.
This concludes with the proof of the claim.


8

TERESA CORTADELLAS BENÍTEZ, CARLOS D’ANDREA, AND EULÀLIA MONTORO

We will study now the structure of the solutions of the WHIP (2). For ℓ ∈ N,
we denote with K[x]ℓ the subspace of polynomials in K[x] of degree bounded by
ℓ. For n, k ∈ N, 1 ≤ k ≤ n, and (u, v) ∈ Kl \ Z × Kn , denote with Vu,v,n,k ⊂
K[x]k−1 ⊕ K[x]n−k the set defined as
Vu,v,n,k = {(Ak−1 (x), Bn−k (x)) satisfying (2)}.

Note that it is actually the nullspace of the matrix Mu,v,n,k , and hence the following
claim holds straightforwardly.
Proposition 2.2. Vu,v,n,k is a K-vector subspace of K[x]k−1 ⊕ K[x]n−k of positive
dimension.
0
Lemma 2.3. Up to a nonzero constant in K, there is a unique (A0k−1 (x), Bn−k
(x)) ∈
Vu,v,n,k such that

deg(A0k−1 (x)) = min{deg(Ak−1 (x)), (Ak−1 (x), Bn−k (x)) ∈ Vu,v,n,k }.
0
0
Proof. If there are two (A0k−1 (x), Bn−k
(x)), (Ã0k−1 (x), B̃n−k
(x)) ∈ Vu,v,n,k such
0
0
that Ak−1 (x) and Ãk−1 (x) are not proportional, then a nontrivial linear combination of these polynomials will produce an element in Vu,v,n,k of strictly lower
degree.

0
Definition 2.4. A pair (A0k−1 (x), Bn−k
(x)) ∈ Vu,v,n,k satisfying the hypothesis of
Lemma 2.3 will be called a minimal element of Vu,v,n,k .

The minimal element is unique if we require A0k−1 (x) to be monic. The following
result gives some light on the structure of the K-vector space Vu,v,n,k .
Proposition 2.5. Any element in Vu,v,n,k is a polynomial multiple of a minimal
element of this space.
Proof. Clearly any polynomial multiple of an element of Vu,v,n,k (as long as the
degrees of each of the two components do not go above k − 1 and n − k respectively)
is an element of Vu,v,n,k .
00
Let (Ak−1 (x), Bn−k (x)) ∈ Vu,v,n,k with Bn−k (x) 6= 0 and A00
k−1 (x), Bn−k (x) ∈
A00
Ak−1 (x)
k−1 (x)
00 (x) .
Bn−k (x) = Bn−k
00
(A00
k−1 (x), Bn−k (x)) is a minimal

00
K[x] be such that gcd(A00
k−1 (x), Bn−k (x)) = 1 and

00
If (A00
element
k−1 (x), Bn−k (x)) ∈ Vu,v,n,k then
in Vu,v,n,k and the claim follows from Proposition 2.1. Otherwise, let I be the set of
00
those i ∈ {1, . . . , l} such that there is j = 0, . . . , ni −1 such that (A00
k−1 (x), Bn−k (x))
P
(j)
(j−t)
j
does not satisfy the identity Au,v,n,k−1 (ui ) = t=0 (j)t vi,t Bu,v,n,n−k (ui ) coming
P
j
00
(j−t)
(j)
(ui )}.
from (2). For i ∈ I, let ji = min{j | (A00
k−1 ) (ui ) 6=
t=0 (j)t vi,j (Bn−k )
Thanks to Proposition 2.1, for any (Ak−1 (x), Bn−k (x)) ∈ Vu,v,n,k there exists
C(x) ∈ K[x] such that
00
Ak−1 (x) = C(x)A00
k−1 (x), Bn−k (x) = C(x)Bn−k (x).

We claim that C (j) (ui ) = 0 for all i ∈ I and j = 0, . . . , ni − ji . Then, from
0
the claim, we deduce that a minimal element in Vu,v,n,k is (A0k−1 (x), Bn−k
(x)) =
Q
ni −ji
00
|C(x).
(x
−
u
)
(C̃(x)A00
(x),
C̃(x)B
(x))
with
C̃(x)
=
i
k−1
n−k
i∈I
To prove the claim we use induction on j. For j = 0, we have
ji
ji  
X
X
ji
(ji )
(ji −t)
(ji )s vi,s (Bn−k )(ji −s) (ui )
C (t) (ui )(A00
(ui ) =
Ak−1 (ui ) =
k−1 )
t
s=0
t=0

UNATTAINABLE POINTS FOR RATIONAL HERMITE INTERPOLATION

=

ji
X

(ji )s vi,s

s=0
ji 
X

=

t=0

9

jX
i −s 
t=0


ji − s
00
C (t) (ui )(Bn−k
)(ji −s−t) (ui ) =
t


jX
i −t
ji
00
C (t) (ui )
(ji − t)s vi,s (Bn−k
)(ji −t−s) (ui ),
t
s=0

and we deduce from the definition of ji that C(ui ) = 0. Assume now 1 ≤ j ≤
ni − ji − 1. Hence,
(15)
Pji +j ji +j  (t)
(ji +j)
(ji +j−t)
Ak−1
(ui ) = t=0
C (ui )(A00
(ui )
k−1 )
Pji +j t
= s=0 (ji + j)s vi,s (Bn−k )(ji +j−s) (ui )
Pji +j−s ji +j−s (t)
Pji +j
00
(j + j) v
= s=0
C (ui )(Bn−k
)(ji +j−s−t) (ui )
Pji +j jii +j  s(t)i,s t=0
Pji +j−t t
00
(ji +j−t−s)
= t=0
C (ui ) s=0 (ji − t)s vi,s (Bn−k )
(ui ).
t

By the inductive hypothesis, we have that C (t) (ui ) = 0 for 0 ≤ t ≤ j − 1, and hence
(15) above becomes


jiX
+j−t
jX
jX
i +j 
i +j 
ji + j
ji + j
00
(t)
(ji +j−t)
)(ji +j−t−s) (ui ).
(ji −t)s vi,s (Bn−k
C
(u
)
C (t) (ui )(A00
)
(u
)
=
i
i
k−1
t
t
s=0
t=j
t=j

Due to the conditions imposed on the characteristic of K, we have ji j+j 6= 0, and
hence we deduce that C (j) (ui ) = 0.

All the previous claims imply the following
Theorem 2.6. Let K be a field
with Char(K) = 0 or Char(K) ≥ max{n1 , . . . , nl }.

For a given (u, v) ∈ Kl \ Z × Kn , let dA (resp. dB ) denote the degree of A0k−1 (x)
0
0
(resp. Bn−k
(x)) for a minimal element (A0k−1 (x), Bn−k
(x)) ∈ Vu,v,n,k , and set
s0 := min{k − 1 − dA , n − k − dB }. Then
0
• Vu,v,n,k = (A0k−1 (x), Bn−k
(x)) · K[x]s0 .
• dimK (Vu,v,n,k ) = s0 + 1.
0
• The RHIP is solvable if and only if gcd(A0k−1 (x), Bn−k
(x)) = 1.
Proof. The first two claims follow straightforwardly from Proposition 2.5. For the
0
last, following the notation of the proof of Proposition 2.5, note that (A0k−1 (x), Bn−k
(x))
solves the RHIP if and only if the set of indexes I is the empty set, which is equiv0
alent to gcd(A0k−1 (x), Bn−k
(x)) = 1.

Thanks to Theorem 2.6 we can produce the following algorithm.
Algorithm 2.7.
Input: (u, v) ∈ Kl \ Z) × Kn , K being a field with Char(K) = 0 or Char(K) ≥
max{n1 , . . . , nl }.
Output: A reduced solution of the RHIP associated to (u, v), or message that it does
not have a solution.
(1) Compute a nontrivial element of the kernel of the matrix Mu,v,n,k associated
to the linear system (2).
(2) Extract polynomials Ak−1 (x) and Bn−k (x) from the coordinates of the element computed in (1).
(3) Remove the common factors of these two polynomials. Denote the reduced
00
polynomials by A00
k−1 (x) and Bn−k (x).

10

TERESA CORTADELLAS BENÍTEZ, CARLOS D’ANDREA, AND EULÀLIA MONTORO
00
00
00
(4) if (A00
k−1 (x), Bn−k (x)) ∈ ker(Mu,v,n,k ), then return (Ak−1 (x), Bn−k (x)),
otherwise return “no solution”.

Remark 2.8. If instead of “a reduced solution” one simply looks for “a solution”,
step (3) in Algorithm 2.7 can be replaced with “remove the common factors that
these two polynomials have of the type (x − ui ), i = 1, . . . , l”.
2.1. Euclidean Algorithm Revisited. We review here the standard computational method used to deal with the RHIP, and compare it with our explorations. A
good reference for this part of the text is [vzGG13, §5.8]. It turns out that the key
connection to deal efficiently with this problem is the classical Euclidean Algorithm
as Proposition 2.10 below show. Recall that for polynomials F (x), G(x) ∈ K[x], the
Extended Euclidean Algorithm consists of a finite matrix of 5 columns (i, qi , ri , si , ti )
such that
• the zeroth row is (0, 0, F (x), 1, 0),
• the first row is (1, Q1 (x), G(x), 0, 1), Q1 (x) being the Euclidean quotient
between F (x) and G(x),
• for i ≥ 2, the i-th row is (i, Qi (x), Ri (x), Si (x), Ti (x)), where Ri (x) is the
remainder of the Euclidean division between Ri−2 (x) and Ri−1 (x), and
Si (x), Ti (x) are the coefficients of the Bézout identity satisfying
Si (x)F (x) + Ti (x)G(x) = Ri (x).
Note that for i ≥ 2, we have deg(Ri (x)) < deg(Ri−1 (x)). In addition, we have that
([vzGG13, Lemmas 3.8 & 3.10])
(16)

deg(Si (x))
deg(Ti (x))
gcd(Ri (x), Ti (x))

≤
=
=

deg(G) − deg(Ri−1 (x))
deg(F ) − deg(Ri−1 (x)),
gcd(F (x), Ti (x)) ∀i ≥ 0.

One of the interesting features of the EEA is that it produces “short” (in degree)
Bézout identities in the following sense:
Lemma 2.9. ([vzGG13, Lemma 5.15]) Let R(x), S(x), T (x) be such that S(x)F (x)+
T (x)G(x) = R(x) with deg(R(x)) + deg(T (x)) < deg(F (x)), and ℓ ∈ N the index
that
deg(Rℓ (x)) ≤ deg(R(x)) < deg(Rℓ−1 (x)).
Then, there exists C(x) ∈ K[x] such that
R(x) = C(x)Rℓ (x), S(x) = C(x)Sℓ (x), T (x) = C(x)Tℓ (x).
We conclude this section by recovering the fundamental result in [vzGG13] which
essentially states that one can solve the RHIP by looking at a specific row in the
Extended Euclidean Algorithm.
Proposition 2.10. ([vzGG13, Exercise 5.42]]) With notation as above, for a given

Q
Q
data (u, v) ∈ Kl \ Z × Kn , set F (x) = li=1 Fi (x) = li=1 (x − ui )ni , and let
G(x) ∈ K[x] be the unique interpolating polynomial of degree less than n which
(j)
satisfies Gi (ui ) = j! vi,j , i = 0, . . . , l, j = 1, . . . , ni − 1. Denote with ℓ the minimal index such that deg(Rℓ (x)) ≤ k − 1. The RHIP is solvable if and only if
gcd(Rℓ (x), Tℓ (x)) = 1. If this is the case, then the pair (Rℓ (x), Tℓ (x)) is a solution
of it.

UNATTAINABLE POINTS FOR RATIONAL HERMITE INTERPOLATION

11

Proof. Given A(x), B(x) ∈ K[x] with deg(A(x)) ≤ k − 1 and deg(B(x)) ≤ n − k we
have that the pair (A(x), B(x)) gives a solution for the WHIP iff
A(j) (ui ) = (G(x)B(x))(j) (ui ) for i = 1, . . . , l and j = 0, . . . , ni − 1, equivalently
if (A(x) − G(x)B(x))(j) (ui ) = 0 for i = 1, . . . , l and j = 0, . . . , ni − 1; that is, iff
F (x) divides A(x) − G(x)B(x) and so, iff A(x) = S(x)F (x) + B(x)G(x) for some
S(x) ∈ K[x].
0
Let (A0k−1 (x), Bn−k
(x)) be a minimal element in Vu,v,n,k . Then, since the pair
(Rℓ (x), Tℓ (x)) gives a solution for the WHIP, we have, by Proposition 2.5, that
0
(Rℓ (x), Tℓ (x)) = (C(x)A0k−1 (x), C(x)Bn−k
(x)) for some C(x) ∈ K[x]. In particular,
0
deg(Bn−k (x)) ≤ deg(Tℓ (x)).
0
On the other hand, since A0k−1 (x) = S(x)F (x) + Bn−k
(x)G(x) for some S(x) ∈
0
0
K[x], deg(Ak−1 (x)) + deg(Bn−k (x)) < deg(F (x)) and deg(A0k−1 (x)) ≤ deg(Rℓ (x))
we have, by Lemma 2.9, that there exist ℓ′ ≥ ℓ and D(x) ∈ K[x] such that
0
(A0k−1 (x), Bn−k
(x)) = (D(x)Rℓ′ (x), D(x)Tℓ′ (x)). In particular, we have that
0
(x)).
deg(Tℓ′ (x)) ≤ deg(Bn−k
0
(x)) ≤ deg(Tℓ (x)) and, deg(Tℓ′ (x)) ≥ deg(Tℓ (x))
Thus, deg(Tℓ′ (x)) ≤ deg(Bn−k
0
′
(x)) and (Rℓ (x), Tℓ (x)) are unique
by (16). So, ℓ = ℓ and the pairs (A0k−1 (x), Bn−k
up to a constant in K. The statement now follows from Theorem 2.6.


3. Geometric Description
In this section we will study the geometry of the RHIP. We start by showing
that all the matrices which are of interest in our problem have “generic” maximal
rank if the field is large enough and its characteristic is zero or also large enough.
Recall that we are always under the assumption that Char(K) = 0 or Char(K) ≥
max{n1 , . . . , nl }.
Proposition 3.1. Let α, β, n1 , . . . , nl ∈ Z≥0 . If K is a field such that #(K) ≥ l.
Then, there are elements (u, v) ∈ (Kl \ Z)× Kn such that Mα,β,n (u, v) has maximal
rank.
Proof. For arbitrary u1 , . . . , ul ∈ K, we specialize


α + 1 α−j+1
(17)
Ui 7→ ui , Vi,j 7→ −
ui
, 1 ≤ i ≤ l, 0 ≤ j ≤ ni − 1
j
in (3) and the matrix become a confluent Vandermonde one, which is known to
have maximal rank for any u ∈ Kl \ Z.

We would also need to show that for generic solutions of the RHIP, the denominator B(x) is such that B(ui ) 6= 0, i = 1, . . . , l.
Lemma 3.2. Let n1 , . . . , nl ∈ Z≥0 , and x, U1 , . . . , Ul indeterminates over K. The
polynomial
(18)

(x − U1 )n1 . . . (x − Ul )nl =

n
X
j=0

satisfies cj (U1 , . . . , Ul ) 6= 0 for all j = 0, . . . , l.

cj (U1 , . . . , Ul )xj

12

TERESA CORTADELLAS BENÍTEZ, CARLOS D’ANDREA, AND EULÀLIA MONTORO

Proof. We expand the left hand side of (18) to get
 
 
X
nl
n−β1 −...−βl n1
U β1 . . . Ulβl xβ1 +...+βl .
...
(−1)
βl 1
β1
0≤βi ≤ni , 1≤i≤l

From here, we deduce straightforwardly that
X
cj (U1 , . . . , Ul ) = (−1)n−j
0≤βi ≤ni ,

P

βi =j

 
 
nl
n1
U β1 . . . Ulβl ,
...
βl 1
β1

is a nonzero polynomial, which concludes with the proof of the claim.



Proposition 3.3. Let α, β, n1 , . . . , nl ∈ N be such that α+β +1 ≥ n1 +. . .+nl , and
K a field of large cardinality. Then, there exists (u, v) ∈ (Kl \ Z) × Kn such that the
RHIP has a solution (i.e. the denominator B(t) satisfies B(ui ) 6= 0, ∀i = 1, . . . , n).
Proof. We can assume w.l.o.g. that α + β + 1 = n1 + . . . + nl and, similarly
to (17), do the substitution Vi,j 7→ − α+1
Uiα−j+1 , 1 ≤ i ≤ l, 0 ≤ j ≤ ni −
j
1. We do the substituion (17), and have a matrix of maximal rank of confluent
Vandermonde type, We call it Vα,β (U). Note that if we add the following row to
Vα,β (U) : (1, x . . . , xα+β+1 ), we then get a square matrix whose determinant is
Ql
equal to w i=1 (x − Ui )ni , with w ∈ K \ {0}. Write the latter as A(x) + xα+1 B(x),
and note that the pair (A(x), B(x)) solves the WHIP for k = α + 1. We must have
(A(x), B(x)) 6= (0, 0) as the coefficients of these two polynomials are the maximal
minors of Vα,β (U) which -thanks to Proposition 3.1- is of maximal rank.
Due to the fact that K is large enough, the proof will be completed if we show
that B(Ui ) 6= 0 for all i = 1, . . . , n. Suppose that for some i0 we have B(Ui0 ) = 0.
Then we must have that A(Ui0 ) = 0, and hence we deduce that
Ql
w i=1 (x − Ui )ni
= Ã(x) + xα+1 B̃(x),
(19)
x − Ui0

with deg Ã(x) ≤ α − 1. This shows that the right hand side of (19) has the
coefficient of xα equal to zero, which is a contradiction with Lemma 3.2 applied to
the data (n1 , . . . , ni0 − 1, . . . , nl ), and completes the proof of the Proposition. 
j
Recall that m = min{k − 1, n − k}. We will fix j ∈ {0, . . . , m}. Let Fk,n
⊂
K[U, V] be the ideal of (n − 2j) × (n − 2j) minors of Mk−j−1,n−k−j,n (U, V). For
−1
convenience, we set Fk,n
:= h0i. As Mk−(j+1)−1,n−k−(j+1),n (U, V) is a submatrix of
Mk−j−1,n−k−j,n (U, V), the following claim holds by performing a suitable Laplace
expansion on the minors of the latter matrix.
j
j+1
Lemma 3.4. For j = 0, . . . , m − 1, Fk,n
⊂ Fk,n
.

From Theorem 2.6, we deduce that 1 ≤ dimK (Vu,v,n,k ) ≤ m + 1. We will look at
a geometric description of this stratification. For 0 ≤ j ≤ m, consider the algebraic
j
j
set V (Fk,n
) ⊂ Kl \ Z) × Kn defined by the vanishing of the elements of Fk,n
. No
further assumptions on the field K are required for the following statements.
Theorem 3.5. For j = 1, . . . , m + 1, (u, v) is such that dimK (Vu,v,n,k ) = j if and
j−2
j−1
only if (u, v) ∈ V (Fk,n
) \ V (Fk,n
).

UNATTAINABLE POINTS FOR RATIONAL HERMITE INTERPOLATION

13

Proof. Recall from Proposition 2.2 that Vu,v,n,k can be identified with ker(Mu,v,n,k ).
Its dimension equal to one if and only if this matrix has maximal rank, which is
0
equivalent to (u, v) ∈
/ V (Fk,n
). This proves the claim for j = 1.
Suppose now that dimK (Vu,v,n,k ) = j + 1, with j > 0. It is easy to see that
the (n − 2j + 1)-th dimensional vector of the coefficients of the minimal solution
0
(A0k−1 (x), Bn−k
(x)) actually belongs to ker(Mk−j−1,n−k−j,n (u, v)), and hence the
0
0
coefficients of both (A0k−1 (x), Bn−k
(x)) and (xA0k−1 (x), xBn−k
(x)) belong to the
kernel of Mk−(j−1)−1,n−k−(j−1),n (u, v), which implies that the dimension of the
j−1
kernel of this matrix is larger than one, and hence we deduce that (u, v) ∈ V (Fk,n
).
j
If in addition we had (u, v) ∈ V (Fk,n ), then there would be another element in
ker(Mk−j−1,n−k−j,n (u, v)) linearly independent with the vector of coefficients of
0
(A0k−1 (x), Bn−k
(x)), and encoding a pair of polynomials of degrees bounded by
k − j − 1 and n − k − j respectively, which also belongs to Vu,v,n,k . As we have that
0
either deg(A0k−1 (x)) = k − j − 1 or deg(Bn−k
(x)) = n − k − j, we conclude that
0
(x)), which is
this other element would then be a scalar multiple of (A0k−1 (x), Bn−k
a contradiction.
j−1
Reciprocally, if (u, v) ∈ V (Fk,n
), then
dimK (ker(Mk−(j−1)−1,n−k−(j−1),n (u, v)) ≥ 2.
As all the polynomials (A(x), B(x)) coming from the coordinates of elements in this
kernel belong to Vu,v,n,k , we deduce that the minimal solution of this space is of the
0
form (A0k−1 (x), Bn−k
(x)) of degrees bounded by k − j − 1 and n − k − j respectively.
Note that this vector also produces an element in ker(Mk−j−1,n−k−j,n (u, v)). If
j
0
(x)) must be
in addition (u, v) ∈
/ V (Fk,n
), then the coordinates of (A0k−1 (x), Bn−k
the only -up to a constant- element of this kernel, which implies straightforwardly
0
(x)). The fact that
that either k − j − 1 = deg(A0k−1 (x)), or n − k − j = deg(Bn−k
dimK (Vu,v,n,k ) = j + 1 follows now straightforwardly from Theorem 2.6.

From the proof of Theorem 3.5, we deduce immediately the following characterizations.
j−1
Corollary 3.6. For j = 0, . . . , m, V (Fk,n
) is equal to set of all (u, v) ∈ (Kl \ Z) ×
n
K such that the minimal solution of Vu,v,n,k has degrees bounded by k − 1 − j and
n − k − j respectively.

Corollary 3.7. For j = 0, . . . , m,

j−1
j
(u, v) ∈ V (Fk,n
) \ V (Fk,n
) ⇐⇒ dimK ker Mk−j−1,n−k−j,n (u, v) = 1.

To study irreducibility and rationality of our objects of interest, we will need
to use the language of and tools from Algebraic Geometry. So we will assume for
the rest of this section that our field K is contained in an algebraically closed field
K, which is where our geometric statements will take place. Given α, β ∈ Z≥0 ,
n = (n1 , . . . , nl ) ∈ Z>0 let Wn,α,β ⊂ K l \ Z × K n × Pα+β+1 (K) be the incidence
variety given by
(20)

(u, v, a0 : . . . : aα : b0 : . . . : bβ ) ∈ Wn,α,β
⇐⇒
Pj
A(j) (ui ) = t=0 (j)t vi,t B (j−t) (ui ), i = 1, . . . , l, j = 0, . . . , ni − 1;

14

TERESA CORTADELLAS BENÍTEZ, CARLOS D’ANDREA, AND EULÀLIA MONTORO

where A(x) and B(x) are defined as
(21)

A(x) =

α
X

ℓ

aℓ x , B(x) =

ℓ=0

β
X

bℓ xℓ .

ℓ=0

Theorem 3.8. Wn,α,β is an irreducible variety of dimension l + α + β + 1, defined
over K.
Proof. The proof will be done by induction on n = |n|, the initial case being obvious,
as W1,α,β is an irreducible hypersurface defined by one polynomial with coefficients
in K ⊂ K. Suppose then n > 1, Let Ai , Bj , Uk , and Vk,t with 0 ≤ i ≤ α, 0 ≤ j ≤
β, 1 ≤ k ≤ l, 0 ≤ t ≤ nk − 1, be distinct indeterminates over K. We will work in
the localized ring
R := K[U1 , . . . , Ul , V1,0 , . . . , Vl,nl −1 , A0 , . . . , Aα , B0 , . . . , Bβ ]Q1≤i<j≤n (Ui −Uj ) .
Pα
Pβ
ℓ
ℓ
Set A(x) :=
ℓ=0 Aℓ x , and B(x) :=
ℓ=0 Bℓ x , which are elements in R[x].
Denote with I the ideal of R defined by
(j)

A

(Ui ) −

j
X

(j)t Vi,t B(j−t) (Ui ), i = 1, . . . , l, j = 0, . . . , ni − 1.

t=0

Note that Wn,α,β = V (I). Let J ⊂ R be the kernel of the map
R
Aj
Bk
Ui
Vi,t

(22)

→
7→
7→
7→
7→

K(U1 , . . . , Ul , A0 , . . . , Aα , B0 , . . . , Bβ )
Aj , j = 0, . . . , α
Bk , k = 0, . . . , β
Ui , i = 1, . . . , l

1 A (t)
(Ui ), t = 0, . . . , ni − 1.
t! B

From its definition, we deduce straightforwardly that J is a prime ideal,
and

homogeneous in the variables Ai , Bj . It is also clear that V (J) ⊂ K l \ Z × K n ×
Pα+β+1 (K) is irreducible of dimension l + α + β + 1. In addition, we have
I ⊂J =I :h

l
Y

B(Ui )iN

i=1

Q
for a suitable N ∈ N, and hence we deduce that V (I : h li=1 B(Ui )iN ) = V (J) ⊂
V (I). In particular, the dimension of V (I) is at least l + α + β + 1. As
V (I : h

l
Y

B(Ui )iN ) = V (I) \ V (

i=1

l
Y

B(Ui )) = V (I) \ ∪li=1 V (B(Ui )) = ∩li=1 V (I) \ V (B(Ui ))

i=1

(the first equality follows because K is algebraically closed, see for instance [CLO15,
Section 4, Theorem 7]), the claim will hold if we show that the dimension of V (I) ∩
V (B(Ui )) is strictly smaller than l + α + β + 1 for some i = 1, . . . , l. We will actually
show that this will happen for all i. Indeed, suppose w.l.o.g. that i = 1, and set
I1 := I + hB(U1 )i. We clearly have that V (I1 ) = V (I) ∩ V (B(U1 )), and moreover
(u, v, a0 : . . . : aα : b0 : . . . : bβ ) ∈ V (I1 ) if and only if (x − u1 ) divides both A(x)
and B(x), and by setting A(x) = (x − u1 )Ã(x) and B(x) = (x − u1 )B̃(x), we have
that
j
X
(j)t Vi,t B̃ (j−t) (ui ), i = 2, . . . , l, j = 0, . . . , ni − 1,
(23)
Ã(j) (ui ) =
t=0

UNATTAINABLE POINTS FOR RATIONAL HERMITE INTERPOLATION

15

and, if n1 ≥ 2,
(24)

(j)

Ã

(u1 ) =

j
X

(j)t V1,t B̃ (j−t) (u1 ), j = 0, . . . , n1 − 2.

t=0

If either α or β is equal to zero, these conditions imply A(x) = B(x) = 0, and hence
V (I1 ) = ∅, so the claim follows for this case straightforwardly. Otherwise, we have

(25)
V (I1 ) ≃ K 2 × Wn2 ,...,nl ,α−1,β−1 \ (Z × K n )

if n1 = 1 (as u1 and v1,0 can be chosen arbitrarily), or
(26)

V (I1 ) ≃ (K × Wn1 −1,n2 ,...,nl ,α−1,β−1 ) \ (Z × K n )

as the only “choice” here is given by v1,n1 −1 .
By the Induction Hypothesis, in both cases we have that the dimension of these
varieties is l + α + β, which is strictly smaller than dim(V (I)). This completes the
proof of the Theorem.


Let π : Wn,α,β → K l \ Z × K n be the projection onto the first factor. By the
Elimination Theorem, we have that π(Wn,α,β ) is an irreducible variety, also defined
over K.
Theorem 3.9. With notation as above, π(Wn,α,β ) is a rational variety of dimension l + min{n, α + β + 1}, defined over K.
Proof. Thanks to Theorem 3.8, we have

dim π(Wn,α,β ) ≤ l + α + β + 1 = dim(Wn,α,β ).

Let Mα,β,n (U, V) be the n × (α + β + 2) matrix defined in (7). It is straightforward
to check that

(27)
(u, v) ∈ π(Wn,α,β ) ⇐⇒ dimK ker(Mα,β,n (u, v)) ≥ 1.
If n < α+β +2 the right hand
 side of (27) holds straightforwardly, hence π(Wn,α,β )
is the whole space K l \ Z × K n . So, the claim holds for this case. Otherwise, we
will have that the rank of Mα,β,n (u, v) will be less than or equal to α + β + 1 for
those (u, v) satisfying (27). Let n := (n1 , . . . , nl ) ∈ Nl be such that ni ≤ ni for
Pl
i = 1, . . . , l, and n := i=1 ni = α + β + 1 < n.
Thanks to Proposition 3.1 applied to the field
K, the matrix Mα,β,n (U, V) gener
ically has maximal rank. Let U0 ⊂ K l \ Z × K α+β+1 be the nonempty open set
consisting of all the data (u, v) such that Mα,β,n (u, v) has maximal rank. We set
now the following rational map
(28)

U0
(u, v)

99K
7→

u, v, t!1

π(Wn,α,β )

1 ≤ i ≤ l, ni ≤ t < ni ,


A (t)
(ui ),
B

where the coefficients of the polynomials A(x) and B(x) are extracted from the
signed maximal minors of Mα,β,n (u, v). The image of this map is clearly contained
in π(Wn,α,β ), and the first coordinates of the map define an inverse, so it will be
birational with an open subset of π(Wn,α,β ) provided that we can show that it is
regular in a nonempty open subset of U0 . But for this to happen, we need that
Q
n
0. This holds thanks to Proposition 3.3, hence the map (28) is
ni <ni B(ui ) 6= Q

n
regular in U0 ∩ { ni <ni B(ui ) 6= 0}, a nonzero empty set of K l \ Z × K α+β+1 .
This concludes with the proof of the Theorem.


16

TERESA CORTADELLAS BENÍTEZ, CARLOS D’ANDREA, AND EULÀLIA MONTORO

Next result will help us characterize the set of unattainable points for the RHIP.
Corollary 3.10. With notation as in the proof of Theorem 3.8, if α = 0 or β = 0,
π(V (I1 )) = ∅, otherwise it is a rational variety of dimension l + min{n, α + β}.
Proof. From (25) and (26), we deduce that if π(V (I1 )) is not empty, then it is
birational to either K 2 ×π (Wn2 ,...,nl ,α−1,β−1 ) or K ×π (Wn1 −1,n2 ,...,nl ,α−1,β−1 ) . The
claim now follows straightforwardly by applying Theorem 3.9 to these varieties. 
For i = 1, . . . , l, let Ii := I +hB(Ui )i, and Miα,β,n (U, V) be the (n−1)×(α+β+2)
submatrix of Mα,β,n (U, V) made by removing the last row in the block containing
the Ui ’s.
Proposition 3.11. For α, β ≥ 1, i = 1, . . . , l, we have

(u, v) ∈ π(V (Ii )) ∩ (Z × K n ) ⇐⇒ dimK ker(Miα−1,β−1,n (u, v)) ≥ 1.

Proof. The matrix of the homogeneous linear system given by (23) and (24) to
compute the coefficients of (Ã, B̃) is actually Miα,β,n (U, V). The claim now follows
straightforwardly.

We now come back to the Rational Interpolation Problem.
j−1
Theorem 3.12. For j = 0, . . . , m + 1, V (Fk,n
) = π(Wn,k−j−1,n−k−j ). It is a
rational irreducible variety defined over K, of codimension 2j if j ≤ m, or the
empty set if j = m + 1.
j−1
Proof. From Corollary 3.6, we have that (u, v) ∈ V (Fk,n
) if and only if the matrix
Mk−j−1,n−k−j,n is rank deficient. From (27) we deduce then that
j−1
π(Wn,k−j−1,n−k−j ) = V (Fk,n
).

The rest of the claim now follows from Theorem 3.9.



Theorem 3.13. Let 1 ≤ k ≤ n. The set of unattainable points for the RHIP is a
union B1 ⊔ B3 ⊔ . . . ⊔ B2m−1 , where for j = 1, . . . , m, B2j−1 is a disjoint union of l
j−2
j−1
rational irreducible varieties defined over K of codimension 1 in V (Fk,n
)\V (Fk,n
)
(i.e. of codimension 2j − 1 in the ambient space).
Proof. For j ∈ {1, . . . , m + 1}, thanks to Theorem 3.12 we have that
j−2
j−1
V (Fk,n
) \ V (Fk,n
) = π(Wn,k−j,n−k−j+1 ) \ π(Wn,k−j−1,n−k−j ).
j−2
j−1
Let B2j−1 be the set of unattainable points of the RHIP lying in V (Fk,n
)\V (Fk,n
).
i
If (u, v) ∈ B2j−1 , there must be i ∈ {1, . . . , l} such that (u, v) ∈ π(Wn,k−j,n−k−j+1 ),
where
i
Wn,k−j,n−k−j+1
= Wn,k−j,n−k−j+1 ∩ V (B(Ui )).
We deduce that j must be at most m + 1. Corollary 3.10 implies that each of the
i
π(Wn,k−j,n−k−j+1
), i = 1, . . . , n, is rational (in particular irreducible), of dimension
2(n − j) + 1. This concludes with the proof of the Theorem.


Based on Theorems 3.12 and 3.13, we can design an incremental algorithm to
decide the solvability of the RHIP without computing any element of the kernel of
a matrix.

UNATTAINABLE POINTS FOR RATIONAL HERMITE INTERPOLATION

17

Algorithm 3.14.
Input: n ∈ Nl , k ∈ N, (u, v) ∈ Kl \ Z) × Kn
Output: A message saying that (u, v) is unattainable or not for the RHIP associated
to n.
j := min{k − 1, |n| − k}.
Compute the matrix Mk−1−j,n−k−j,n (u, v).
If rank(Mk−1−j,n−k−j,n (u, v)) = n − 2j + 1, then j − 1 7→ j, and goto (2).
i := 1.
If i = l + 1 then print “not unattainable” and stop the algorithm.
Compute the (n − 1) × (n − 2j − 1) submatrix Mik−1−j,n−k−j,n (u, v) by
removing the last row in the block indexed by ui ’, and the columns k − j
and n − 2j + 1 of Mk−1−j,n−k−j,n (u, v).
(7) If rank(Mik−1−j,n−k−j,n (u, v)) = n − 2j − 1, then i + 1 7→ i and goto (5),
else print “unattainable”.
(1)
(2)
(3)
(4)
(5)
(6)

Remark 3.15. One could add an extra step at the end of (3) in Algorithm 3.14 to
compute a nontrivial vector in the kernel of Mk−1−j,n−k−j,n (u, v) whose coordinates
will encode the minimal solution of the WHIP.

4. Equations and Proof of the main Theorems
j−1
In this section we will give explicit equations for the varieties V (Fk,n
) and
j−1
j
descriptions for the open sets V (Fk,n )\V (Fk,n ). They will arise as maximal minors
of matrices of the form Mα,β,n (U, V), with α + β = n − 1. We start by fixing
(u, v) ∈ (Kl \ Z) × Kn . Recall from the Introduction that, for i = 1, . . . , n + 1, and
1 ≤ k ≤ n, we denote by ∆n
k,i the i-th maximal signed minor of Mk−1,n−k,n (U, V).
The following result is an easy verification.
n
Lemma 4.1. Up to a sign, ∆n
k−1,n+1 = ∆k,k .

Proposition 4.2.
n
dimK (Vu,v,n,k ) = 1 ⇔ ∆n
k,k (u, v) 6= 0 or ∆k,n+1 (u, v) 6= 0.

Proof. From Theorem 2.6 we deduce that dimK (Vu,v,n,k ) = 1 if and only if the rank
of Mu,v,n,k is maximal, so ⇐] is clear. Reciprocally, if dimK (Vu,v,n,k ) = 1, then by
n
n
n
Hilbert-Burch (∆n
k,1 , . . . , ∆k,k ; ∆k,k+1 , . . . , ∆k,n+1 )(u, v) generates ker(Mu,v,n,k ),
and hence must encode a minimal element in Vu,v,n,k . We must have ∆n
k,k (u, v) 6= 0
or ∆n
(u,
v)
=
6
0
thanks
to
Theorem
2.6
again.

k,n+1
From Lemma 4.1 we can express Proposition 4.2 in a more symmetric way.
Corollary 4.3.
n
dimK (Vu,v,n,k ) = 1 ⇔ ∆n
k,k (u, v) 6= 0 or ∆k+1,k+1 (u, v) 6= 0.

Proposition 4.4. If 2 ≤ k ≤ n − 1, then
 n
∆k,k (u, v) = ∆n
k,n+1 (u, v) = 0, and
dimK (Vu,v,n,k ) = 2 ⇔
∆n
(u,
v)
6= 0 or ∆n
k−1,k−1
k+1,n+1 (u, v) 6= 0.

18

TERESA CORTADELLAS BENÍTEZ, CARLOS D’ANDREA, AND EULÀLIA MONTORO

n
Proof. Suppose first that dimK (Vu,v,n,k ) = 2. Then, ∆n
k,k (u, v) = ∆k,n+1 (u, v) = 0
by Proposition 4.2. Let (a0 , . . . , ak−2 , 0; b0 , . . . , bn−k−1 , 0) be the vector of coefficients of a minimal element in Vu,v,n,k , with ak−2 6= 0 or bn−k−1 6= 0. If ak−2 6= 0
then (a0 , . . . , ak−2 ; b0 , . . . , bn−k−1 , 0, 0) gives a minimal element in Vu,v,n,k−1,n and
n
so, by Proposition 4.2 again, and using that ∆n
k−1,n+1 (u, v) = ∆k,k (u, v) = 0, we
n
have that ∆k−1,k−1 (u, v) 6= 0.
If bn−k−1 6= 0 then (a0 , . . . , ak−2 , 0, 0; b0 , . . . , bn−k−1 ) gives a minimal element in
Vu,v,n,k+1,n and now ∆n
k+1,n+1 (u, v) 6= 0.
n
n
Reciprocally, if we assume ∆n
k,k (u, v) = ∆k,n+1 (u, v) = 0 and ∆k−1,k−1 (u, v) 6=
0, then dimK (Vu,v,n,k ) > 1 by Proposition 4.2. Let (a0 , . . . , ak−2 , 0; b0 , . . . , bn−k−1 , 0)
be the coefficients of a minimal element in Vu,v,n,k . We sort them to produce
(a0 , . . . , ak−2 ; b0 , . . . , bn−k−1 , 0, 0), a minimal element of Vu,v,n,k−1,n , a vector space
of dimension 1 since ∆n
k−1,k−1 (u, v) 6= 0, and so ak−2 6= 0. By Theorem 2.6 we
deduce then that dimK (Vu,v,n,k ) = 2.
n
n
For the case ∆n
k,k (u, v) = ∆k,n+1 (u, v) = 0 and ∆k+1−1,n+1 (u, v) 6= 0, the coefficients of a minimal element (a0 , . . . , ak−2 , 0; b0 , . . . , bn−k−1 , 0) in Vu,v,n,k will give a
minimal element of the form (a0 , . . . , ak−2 , 0, 0; b0 , . . . , bn−k−1 ) of the 1-dimensional
vector space Vu,v,n,k−1,n and hence bn−k−1 6= 0.


From Lemma 4.1 we get the following equivalent result.
Corollary 4.5. If 2 ≤ m + 1, then
 n
∆k,k (u, v) = ∆n
k+1,k+1 (u, v) = 0, and
dimK (Vu,v,n,k ) = 2 ⇔
(u,
v)
6= 0 or ∆n
∆n
k+2,k+2 (u, v) 6= 0.
k−1,k−1

Proposition 4.6. If 2 ≤ j ≤ m + 1 (that is, 2 ≤ j ≤ k ≤ n − j + 1), then
 n
n
 ∆k,k (u, v) = · · · = ∆k−j+2,k−j+2 (u, v) = 0
n
(u, v) = · · · = ∆n
∆
dimK (Vu,v,n,k ) = j ⇔
k+j−2,n+1 (u, v) = 0, and
 k,n+1
n
∆k−j+1,k−j+1 (u, v) 6= 0 or ∆n
k+j−1,n+1 (u, v) 6= 0.

Proof. By induction on j, the initial case j = 2 following from Proposition 4.4.
Let j > 2. Assume that dimK (Vu,v,n,k ) = j. By the induction hypothesis, we
n
n
must have ∆n
k,k (u, v) = · · · = ∆k−j+2,k−j+2 (u, v) = 0, and ∆k,n+1 (u, v) = · · · =
n
∆k+j−2,n+1 (u, v) = 0, as otherwise it would be equivalent to dimK (Vu,v,n,k ) =
j0 < j.
Let (a0 , . . . , ak−j , 0, . . . , 0; b0 , . . . , bn−k−j+1 , 0 . . . , 0) be the coefficients of a minimal element of this space. If ak−j 6= 0, then
(a0 , . . . , ak−j ; b0 , . . . , bn−k−j+1 , 0 . . . , 0, . . . , 0)
encodes the coefficients of a minimal element in Vu,v,n,k−(j−1),n , a vector space
of dimension 1 and, by Proposition 4.2, ∆n
k−(j−1),k−(j−1) (u, v) 6= 0 (note that
n
∆n
(u,
v)
=
∆
(u,
v)
=
0). If bn−k−j+1 6= 0, then
k−(j−1),n+1
k−(j−2),k−(j−2)
(a0 , . . . , ak−j , 0 . . . , 0, . . . , 0; b0 , . . . , bn−k−j+1 )
are the coefficients of a minimal element in Vu,v,n,k+j−1,n , and hence ∆n
k+j−1,n+1 (u, v) 6=
0 in this case.
n
n
Assume now that ∆n
k,k (u, v) = · · · = ∆k−j+2,k−j+2 (u, v) = 0, ∆k,n+1 (u, v) =
n
· · · = ∆k+j−2,n+1 (u, v) = 0. By the induction hypothesis, we have that dimK (Vu,v,n,k ) >
j − 1. Let
(a0 , . . . , ak−j , 0, . . . , 0; b0 , . . . , bn−k−j+1 , 0 . . . , 0)

UNATTAINABLE POINTS FOR RATIONAL HERMITE INTERPOLATION

19

be the coefficients of a minimal element of Vu,v,n,k . If ∆n
k−j+1,k−j+1 (u, v) 6= 0,
then the element
(a0 , . . . , ak−j ; b0 , . . . , bn−k−j+1 , 0 . . . , 0, . . . , 0)
encodes a non zero element of the one dimensional space Vu,v,n,k−j+1,n which
implies that ak−j 6= 0 and therefore that dimK (Vu,v,n,k ) = j. If ∆n
k+j−1,n+1 (u, v) 6=
0, then
(a0 , . . . , ak−j , 0 . . . , 0, . . . , 0; b0 , . . . , bn−k−j+1 )
corresponds to a non trivial element in the one-dimensional vector space Vu,v,n,k+j−1,n
and so dimK (Vu,v,n,k ) = j also in this case.

By using again Lemma 4.1, we get the following equivalent result.
Corollary 4.7. If 2 ≤ j ≤ m + 1, then
 n
n
 ∆k,k (u, v) = · · · = ∆k−j+2,k−j+2 (u, v) = 0
n
∆k+1,k+1 (u, v) = · · · = ∆n
dim(Vu,v,n,k ) = j ⇔
k+j−1,k+j−1 (u, v) = 0, and
 n
∆k−j+1,k−j+1 (u, v) 6= 0 or ∆n
k+j,k+j (u, v) 6= 0.
We summarize our results with the following

j−2
Theorem 4.8. For j = 1, . . . m + 1, V (Fk,n
) ⊂ (Kl \ Z) × Kn is given by the
equations

(29)

n
n
∆n
k−j+2,k−j+2 = ∆k−j+3,k−j+3 = · · · = ∆k+j−1,k+j−1 = 0.

j−2
j−1
The open set V (Fk,n
) \ V (Fk,n,n
) is defined by cutting the above equations with
n
{∆n
k−j+1,k−j+1 6= 0} ∪ {∆k+j,k+j 6= 0}.

Proof. The second part of the claim follows from From Corollary 4.7 and the charj−1
j
acterization of V (Fk,n
) \ V (Fk,n
) given in Theorem 3.5. The first part follows
straightforwardly by noticing that

 

j−2
j−2
j−1
j−1
j
V (Fk,n
) = V (Fk,n
) \ V (Fk,n
) ⊔ V (Fk,n
) \ V (Fk,n,n
) ⊔...
and applying the first part of the claim to each of these pieces. This concludes with
the proof of the Theorem.

It turns out that this procedure also helps build minimal solutions of the WHIP
as follows:
j−2
j−1
Proposition 4.9. If (u, v) ∈ V (Fk,n
) \ V (Fk,n
) then the following expressions
are minimal solutions of the WHIP:
(30)
 P

Pn−2j+2
k−j
n
ℓ−k+j−1
n
ℓ

∆
(u,
v)x
∆
(u,
v)x
;
if ∆n
k−j+1,ℓ+1
k−j+1,k−j+1 (u, v) 6= 0,
ℓ=k−j+1

Pℓ=0 k−j+1,ℓ+1
P
k−j
n
n
ℓ
n
ℓ−k−j+1

if ∆n
k+j,k+j (u, v) 6= 0.
ℓ=0 ∆k+j−1,ℓ+1 (u, v)x ;
ℓ=k+j−1 ∆k+j−1,ℓ+1 (u, v)x

n
If ∆n
k−j+1,k−j+1 (u, v) = 0 (resp. ∆k+j,k+j (u, v) = 0), the first (resp. second)
vector in (30) vanishes identically.

Remark 4.10. From the previous claim we deduce that, as both vectors in (30) are
minimal solutions of the same WHIP, up to a non-zero constant they must coincide
n
in {∆n
k−j+1,k−j+1 6= 0} ∩ {∆k+j,k+j 6= 0}.

20

TERESA CORTADELLAS BENÍTEZ, CARLOS D’ANDREA, AND EULÀLIA MONTORO

Proof of Proposition 4.9. If ∆n
k−j+1,k−j+1 (u, v) 6= 0 then, by computing the maximal minors of the matrix Mu,v,n,k−j+1 , we deduce that


k−j
n
X
X
ℓ−k+j−1 
ℓ

(31)
∆n
∆n
k−j+1,ℓ+1 (u, v)x ;
k−j+1,ℓ+1 (u, v)x
ℓ=0

ℓ=k−j+1

is -up to a constant- a minimal solution of the WHIP with parameters (k − j + 1, n)
as the kernel of this matrix has dimension one, and hence all solutions must be
n
multiples of (31). As ∆n
k−j+1,n+1 (u, v) = ±∆k−j+2,k−j+2 (u, v) thanks to Lemma
4.1, and the last expression equal to zero due to Theorem 4.8, we deduce that the
second coordinate of (31) has degree d0 < n − k + j − 1. Note that (31) is also a
minimal solution of the WHIP with parameters (n − d0 , n) (if it were not minimal,
there would be one of smaller degree which would contradict the minimality of (31)
as a solution of the WHIP with parameters (k − j + 1, n). Due to Corollary 4.3,
n
we deduce then that either ∆n
n−d0 ,n−d0 (u, v) 6= 0 or ∆n−d0 +1,n−d0 +1 (u, v) 6= 0.
From (29), we must have that either n − d0 ≤ k − j + 1 or n − d0 + 1 ≥ k + j.
The first one cannot happen as we have d0 < n − k + j − 1 above, so it should be
d0 ≤ n− k − j + 1, which shows that (31) is a solution of the WHIP with parameters
(k, n) (as the denominator has degree smaller than n−k), and moreover, we actually
have
n
X

ℓ=k−j+1

ℓ−k+j−1
∆n
k−j+1,ℓ+1 (u, v)x

=

n−2j+2
X

ℓ−k+j−1
∆n
,
k−j+1,ℓ+1 (u, v)x

ℓ=k−j+1

so the first part of the claim follows for ∆n
k−j+1,k−j+1 (u, v) 6= 0. A similar argument
show that (30) also holds when ∆n
k+j,k+j (u, v) 6= 0.
For the second part, suppose that ∆n
k−j+1,k−j+1 (u, v) = 0. As we also have
n
∆n
(u,
v)
=
±∆
(u,
v)
= 0 (due to Lemma 4.1 and Theorem
k−j+1,n+1
k−j+2,k−j+2
4.8), we claim that all the maximal minors of Mu,v,n,k−j+1 vanish identically, and
hence (31) is the zero vector. To see this, if there is a non trivial minor of this matrix, then (31) would compute a non trivial solution of the kernel of Mu,v,n,k−j+1
which has both leading coefficients (numerator and denominator) vanish. So, by
multiplying by a polynomial of degree 1 the two polynomials in (31), we would
obtain another vector in ker Mu,v,n,k−j+1 linearly independent with it. This implies that the dimension of this kernel is at least two and hence all the maximal
minors of the matrix vanish, a contradiction which concludes with the proof of the
Proposition.

As in Theorem 3.13, we set B2j−1 to be the set of unattainable points of the
j−2
j−1
RHIP lying in V (Fk,n
) \ V (Fk,n
). The following result gives equations for this set.
Theorem 4.11. With notation as in the statement of Theorem 1.1, for 1 ≤ j ≤
m, B2j−1 is a union of n components, each of them being defined, for a fixed i ∈
{1, . . . , l}, by cutting the 2(j − 1) equations from (29) with
( P
n−2j+2
ℓ−k−j+1
∆n
= 0 if ∆n
k−j+1,ℓ+1 Ui
k−j+1,k−j+1 6= 0
Pℓ=k−j+1
n
ℓ−k−j+1
n
= 0 if ∆n
k+j,k+j 6= 0.
ℓ=k+j−1 ∆k+j−1,ℓ+1 Ui
Up to a nonzero constant, these two polynomials coincide in the intersection of (29)
n
with {∆n
k−j+1,k−j+1 6= 0} ∩ {∆k+j,k+j 6= 0}.

UNATTAINABLE POINTS FOR RATIONAL HERMITE INTERPOLATION

21

Proof. Recall from the proof of Theorem 3.13 that B2j−1 is the set of unattainable
j−2
j−1
points of the RHIP lying in V (Fk,n
) \ V (Fk,n
). Theorem 4.8 gives the description
j−2
j−1
of V (Fk,n ) \ V (Fk,n ), the unattainable points of the RHIP are those where the
denominator vanishes after setting x 7→ ui for some i ∈ {1, . . . , l}, which means that
Pn−2j+2
ℓ−k−j+1
=0
-thanks to (30)- we need to add the equation ℓ=k−j+1 ∆n
k−j+1,ℓ+1 Ui
P
n
ℓ−k−j+1
n
n
for ∆n
=
6
0,
or
∆
U
=
0
for
∆
=
6
0.
k−j+1,k−j+1
k+j−1,ℓ+1 i
k+j,k+j
ℓ=k+j−1
This concludes with the proof of the claim.


References
[Ant88]

Antoulas, A.C. Rational interpolation and the Euclidean algorithm. Linear Algebra
Appl. 188 (1988), 157–171.
[BL00]
Beckermann, Bernhard; Labahn, George. Fraction-free computation of matrix rational
interpolants and matrix GCDs. SIAM J. Matrix Anal. Appl. 22 (2000), no. 1, 114–144.
[Cau41]
Cauchy, A. L. Mémoire sur les fonctions alternées et les sommes alternées. Exercices
d’analyse et de phys. math. (1841) 151–159.
[CLO15] Cox, David A.; Little, John; O’Shea, Donal. Ideals, varieties, and algorithms. An
introduction to computational algebraic geometry and commutative algebra. Fourth
edition. Undergraduate Texts in Mathematics. Springer, Cham, 2015.
[DKS15] D’Andrea, Carlos; Krick, Teresa; Szanto, Agnes. Subresultants, Sylvester sums and the
rational interpolation problem. J. Symbolic Comput. 68 (2015) 72–83.
[EK89]
Eg̃eciog̃lu, Ömer; Koç, Çetin K. A fast algorithm for rational interpolation via orthogonal polynomials. Math. Comp. 53 (1989), no. 187, 249?264.
[Gem93] Gemignani, Luca. Rational interpolation via orthogonal polynomials. Comput. Math.
Appl. 26 (1993), no. 5, 27–34.
[Kah69]
Kahng, S. W. Osculatory interpolation. Math. Comp. 23 1969 621–629.
[Las03]
Lascoux, Alain. Symmetric functions and combinatorial operators on polynomials.
CBMS Regional Conference Series in Mathematics, 99. Published for the Conference
Board of the Mathematical Sciences, Washington, DC; by the American Mathematical
Society, Providence, RI, 2003.
[Pred53] Predonzan, Arno. Su una formula d’interpolazione per le funzioni razionali. Rend.
Sem. Mat. Univ. Padova 22, (1953). 417–425.
[Rav97]
Ravi, M. S. Geometric methods in rational interpolation theory. Linear Algebra Appl.
258 (1997), 159–168.
[Sal62]
Salzer, Herbert E. Note on osculatory rational interpolation. Math. Comp. 16 1962
486–491.
[Sal84]
Salzer, H. E. An osculatory extension of Cauchy’s rational interpolation formula. Z.
Angew. Math. Mech. 64 (1984), no. 1, 45–50.
[SW86]
Schneider, Claus; Werner, Wilhelm. Some new aspects of rational interpolation. Math.
Comp. 47 (1986), no. 175, 285–299.
[SW91]
Schneider, C.; Werner, W. Hermite interpolation: the barycentric approach. Computing 46 (1991), no. 1, 35–51.
[VBB92] Van Barel, Marc; Bultheel, Adhemar. A new formal approach to the rational interpolation problem. Numer. Math. 62 (1992), no. 1, 87–122.
[vzGG13] von zur Gathen, Joachim; Gerhard, Jürgen. Modern computer algebra. Third edition.
Cambridge University Press, Cambridge, 2013.
[Wuy75] Wuytack, Luc. On the osculatory rational interpolation problem. Math. Comput. 29
(1975), 837–843.

22

TERESA CORTADELLAS BENÍTEZ, CARLOS D’ANDREA, AND EULÀLIA MONTORO

Universitat de Barcelona, Facultat de Educació. Passeig de la Vall d’Hebron 171,
08035 Barcelona, Spain
E-mail address: terecortadellas@ub.edu
Universitat de Barcelona, Departament de Matemàtiques i Informàtica, Universitat
de Barcelona (UB), Gran Via de les Corts Catalanes 585, 08007 Barcelona, Spain
E-mail address: cdandrea@ub.edu
URL: http://www.ub.edu/arcades/cdandrea.html
Universitat de Barcelona, Departament de Matemàtiques i Informàtica, Universitat
de Barcelona (UB), Gran Via de les Corts Catalanes 585, 08007 Barcelona, Spain
E-mail address: eula.montoro@ub.edu

