# Minimal degree rational unimodular interpolation on the unit circle.

AMS subject classifications. 30D50, 35E05

1. Introduction. The rational functions of degree n which are unimodular on the complex unit circle O D are given by all fractions of the form

(1.1) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

The finite Blaschke products of degree n form a subset of the unimodular rational functions of degree n. An irreducible rational function of form (1.1) is a finite Blaschke product when all its zeros are in the open unit disk IID. Note that any function of form (1.1) may be written as a fraction of two finite Blaschke products. This paper investigates the following interpolation problem:

Problem I. Given distinct points [z.sub.1], ..., [z.sub.n] on O D and arbitrary points [w.sub.1], ..., [w.sub.n] on [partial derivative]D, find a rational function b(z) of the form (1.1) and of as low degree as possible satisfying the interpolation conditions

b([z.sub.j]) = [w.sub.j], j = l,...,n.

The boundary interpolation problems considered in Problem I can be classified into three categories: fragile, elastic and damaged problems. The fragile and elastic problems are uniquely solvable and a constructive characterization of the solution to Problem I in these classes was given by Glader in . In the paper at hand we will treat the remaining non-uniquely solvable damaged cases, giving in Section 3 a constructive method, based on solving a coneigenvalue problem, to determine a parametrization of all solutions to Problem I.

The above classification was introduced by Semmler and Wegert [8, 9] in boundary interpolation with finite Blaschke products. In  the interpolation problems are divided into three classes depending on the minimal degree (winding number) m of an interpolant:

1) Fragile problems where 0 [less than or equal to] m < (n - 1) /2, (unique solution),

2) Elastic problems where m = (n - 1) /2, (n is odd, unique solution),

3) Damaged problems where (n - 1)/2 < m [less than or equal to] n - 1, (non-unique solution).

This division into three classes is also relevant for the bigger class (1.1) of unimodular interpolants with the uniquely solvable elastic and fragile problems characterized by Theorems 1.1 and 1.2 below and the damaged cases with minimal degree m > (n - 1) /2 having non-unique solutions, a fact that is proved in Theorem 2.1 and Corollary 2.5.

It was noted by Glader  that the minimal degree in unimodular interpolation generically satisfies m = Ln/2 J , and in the case of even n = 2m we show in Theorem 2.1 in Section 2 that if Problem I is damaged with minimal degree m' = m = n/2, then all solutions b(z) are given by a Nevanlinna parametrization

(1.2) b(z) = P(z)[e.sup.i[theta]] + Q(z)/R(z)[e.sup.i[theta]] + S(z),

with polynomials P, Q, R, S that can be computed by a recursive procedure. This does not hold for other damaged problems, which is proved in Corollary 2.5. Also note, for instance by choosing [w.sub.l] = ... = [w.sub.n-1] [not equal to] [w.sub.n], that the minimal degree of a damaged Problem I can be m' = n - 1.

It is clear by in [2, Theorem 2.1] that if Problem I is fragile or elastic in the subclass of finite Blaschke products, then this will also be the case in the class of unimodular interpolants, but a damaged Problem I for Blaschke products may not be damaged for unimodular interpolants, for example choosing

[omega] = [e.sup.2[pi]i/3] [z.sub.j] = [[omega].sup.j] [w.sub.j] = [w.sup.2j], j = 1, 2, 3,

gives a damaged Problem I for Blaschke products and an elastic unimodular problem with the solution b(z) = 1/z. Also if we have a damaged unimodular Problem I, then the minimal degree may be strictly less than the minimal degree of the corresponding Problem I for Blaschke products, which is demonstrated in the concluding example of Section 3.

The study of interpolation problems on [partial derivative]D with unimodular rational functions has a be- ginning in the 1965 paper by Cantor and Phelps , where they nonconstructively showed that there is always a finite Blaschke product interpolating the data. Younis  showed in 1980 how to construct an interpolating Blaschke product which is of degree at most [n.sup.2] - n. In 1987, Jones and Ruscheweyh  proved nonconstructively that there always exists an interpolating Blaschke product of degree at most n - 1.

In the last few years there has been a renewed interest in both topological aspects of boundary interpolation (see Semmler and Wegert [8, 9]) and construction of (minimal degree) interpolants; see Glader , Glader and Lindstr6m , Gorkin and Rhodes , Hjelle  and Semmler and Wegert [8, 9].

Our aim is to complete the investigation started in  by considering the class of damaged interpolation problems. In order to conveniently do this we will restate some results from  that will be needed in Sections 2 and 3.

Suppose that we have n distinct points [z.sub.1], ..., [z.sub.n] and n arbitrary points [w.sub.1], ..., [w.sub.n] on the unit circle. For even n define m = n/2 and for odd n let m = (n -1) /2. We may without restriction assume that [z.sub.1] = [w.sub.1] = 1 (by choosing suitable rotations of the interpolation data). Exclude the trivial case where [w.sub.1] = [w.sub.2] = ... = [w.sub.n] = 1. For [m.sup.l] = 1, 2, ..., m we define the (2[m.sup.l] + 2) x (2[m.sup.l] + 2) square matrix [A.sub.m'], where l := 2[m.sup.l] + 1, by

(1.3) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

The following result in  gives a constructive description of the elastic cases.

THEOREM 1.1. Suppose that we have n = [2.sub.m] + 1 distinct points [z.sub.1], ..., [z.sub.n], and n arbitrary points [w.sub.1], ..., [w.sub.n], on the unit circle, such that [z.sub.1] = [w.sub.1] = 1. Problem I has a solution b(z) of irreducible degree m if and only if det [A.sub.m] [not equal to] 0 and the unique solution x = [([[alpha].sub.0], ..., [[alpha].sub.m] [[bar.[alpha].sub.m], ..., [[bar].sub.m], ..., [[bar.[alpha].sub.0]).sup.T] to the square linear system

(1.4) [A.sub.m] x = [(0, ..., 0,1).sup.T]

satisfies p([z.sub.j]) [not equal to] 0, j = 1, ..., n, where p(z) := [[alpha].sub.0] + [[alpha].sub.1] z + ... + [[alpha].sub.m], [z.sup.m].

If there exists an irreducible solution b(z) of degree m to Problem I, then it is given by

(1.5) b(z) = [[alpha].sub.0] + [[alpha].sub.1] z + ... + [[alpha].sub.m] [z.sup.m]/[[bar.[alpha]].sub.m] + [[bar.[[alpha].sub.m-1] z + ... + [[bar.[alpha]].sub.0] + [z.sub.m],

where the coefficients are obtained from the solution x to (1.4).

In the fragile cases we have to append an additional condition to the ones in Theorem 1.1. The next theorem is also found in .

THEOREM 1.2. Suppose that we have n = 2m + 1 or n = 2m distinct points [z.sub.l], ..., [z.sub.n] and n arbitrary points [w.sub.1], ..., [w.sub.n], on the unit circle, such that [z.sub.1] = [w.sub.1] = 1. Problem I has a solution b(z) of irreducible degree [m.sup.l] < m if and only if det [A.sub.m'] [not equal to] 0 and the unique solution x = [([[alpha].sub.0], ..., [[alpha].sub.m'], [[bar.[alpha].sub.0].sup.T] to the square linear system

(1.6) [A.sub.m], x = [(0'...' 0,1).sup.T]

satisfies p([z.sub.j]) [not equal to] 0, j = 1, ..., 2m' + 1, where p(z) := [[alpha].sub.0] + [[alpha].sub.1]z + ... + [[alpha].sub.m'], [z.sup.m'], and additionally the function b(z) formed by the components in x and defined by (1.7) satisfies b([z.sub.j]) = [w.sub.j], j = 2m' + 2, ..., n.

If there exists an irreducible solution b(z) to Problem I of degree m' < m in the case n = 2m + l o rn = 2m, then

(1.7) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

where the coefficients are obtained from the solution x to (1.6).

2. Parametrization through recursion. The following theorem and corollary characterizes the damaged problems having solutions representable by a Nevanlinnaparametrization and the proof of Theorem 2.1 gives a recursive procedure to construct the parametrization in (1.2). A small example with n = 5 at the end of the section demonstrates the sparsity of both fragile problems and damaged problems with minmal degree [m.sup.l] > Ln/2 J .

THEOREM 2.1. Suppose that we have n = 2m distinct points [z.sub.1], ..., [z.sub.n], and n arbitrary points [w.sub.1], ..., [w.sub.n], on the unit circle and that Problem I is damaged with minimal degree m' = m = n/2. Then we can find polynomials P, Q, R, S of degree at most m' such that all solutions b(z) to Problem I are given by the Nevanlinna parametrization (1.2) for such [theta] [member of] [0, 2[pi]) that do not produce any poles on the unit circle. There are at most n such exceptional values of 0 and zero-pole cancellation in (1.2) on [partial derivative]D occurs precisely in the set [I.sub.m] = {[z.sub.1], ..., [z.sub.n]} when [theta] runs through [0, 2[pi]).

Proof. 1. Consider first the distinct interpolation nodes [z.sub.1], [z.sub.2] and the distinct interpolation values [w.sub.1], [w.sub.2].

1.1. Assume that [w.sub.1][z.sub.2] [not equal to] [w.sub.2][z.sub.1], (i.e., the [w.sub.j]'s are not a simple rotation of the [z.sub.j]'s). Using the ansatz

b(z) = [a.sub.0] + i[b.sub.0] + ([a.sub.l] + i[b.sub.1]).sub.z]/[a.sub.1] - i[b.sub.1] + ([a.sub.0] - i[b.sub.0])z, [a.sub.j], [b.sub.j] [member of] R,

and the interpolation conditions b([z.sub.j]) = [w.sub.j], j = 1, 2, we can deduce that all rational uni-modular interpolants of exact degree 1 are obtained by the parametrization

(2.1) [B.sub.1](z) = [P.sub.1]9z)[e.sup.i[theta]] + [Q.sub.1](z)/[R.sub.1](z)[e.sup.i[theta]] + [S.sub.1](z)

for those parameter values [theta] [member of] [0, 2[pi]) that give a pole in (2.1) that is not on the unit circle, and where

(2.2) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

There are two exceptional values of [theta], namely

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

and the corresponding zeros and poles that are cancelled on the unit circle are given by z = [z.sub.2] and z = [z.sub.1], respectively.

If [w.sub.1][z.sub.1] [not equal to] [w.sub.2][z.sub.2] (or [w.sub.2][z.sub.1] = [w.sub.2] [z.sub.2]), then the set of all zeros of [B.sub.1], (z) in (2.1) when [theta] runs through all but the two exceptional values in [0, 2[pi]) form a circle (or a line) that goes through the points [z.sub.1] and [z.sub.2], but does not include them, and the circle (or the line) does not pass through z = 0.

1.2. Assume now that [w.sub.1] [z.sub.2] = [w.sub.2][z.sub.1], so the interpolation values are a rotation of the nodes. In this case, with the polynomials in (2.2), the parametrization in (2.1) breaks down to one solution, [B.sub.1](z) = [w.sub.1][[bar.z].sub.1]z, so we need to find new polynomials for the parametrization.

1.2.1. Assume further that [z.sub.2] [not equal to] - [z.sub.1]. Then with the same ansatz as in part 1.1 of the proof we obtain the polynomials

(2.3) [P.sub.1](z) = [w.sub.1][z.sub.1][z.sub.2] - ([w.sub.l] + [w.sub.2])[z.sub.1]z, [Q.sub.1](z) = [w.sub.l][w.sub.2][z.sub.1], [R.sub.1](z) = [z.sub.1]z, [S.sub.1](z) = -([w.sub.l] + [w.sub.2])[z.sub.1] + [w.sub.l]z,

in the parametrization (2.1) of all solutions. The exceptional values of [theta] are given by

[e.sup.i[theta]] = -[w.sub.1][[bar.z].sub.2] [right arrow] [B.sub.1](z) [??] [w.sub.1] and [e.sup.i[theta]] = -[w.sub.2][[bar.z].sub.1] [right arrow] [B.sub.1](z) [??] [w.sub.2],

with corresponding zero-pole cancellation in z = [z.sub.2] and z = [z.sub.1], respectively.

1.2.2. Assume now that [z.sub.2] = [z.sub.1]. With the polynomials in (2.3) the parametrization breaks down to one solution, [B.sub.1] (z) = [w.sub.1][z.sub.1]/z. To obtain all solutions we use the polynomials

(2.4) [P.sub.1](z) = [w.sub.1] (z - i[z.sub.1]) , [Q.sub.1](z) = -[w.sub.1] (i[z.sub.1] + z) , [R.sub.1](z) = [z.sub.1] - iz, [S.sub.l](z) = - [z.sub.1] - iz,

with the two exceptional values of [theta] given by

[e.sup.i[theta]] = -I [right arrow] [B.sub.1](z) [??] [w.sub.1] and [e.sup.i[theta]] = I [right arrow] [B.sub.1](z) [??] [w.sub.2](= -[w.sub.1]),

with corresponding zero-pole cancellation in z = [z.sub.2] and z = [z.sub.1], respectively.

In part 1.2 of the proof, if [z.sub.2] [not equal to] -[z.sub.1] (or [z.sub.2] = -[z.sub.1]), then the set of all zeros of [B.sub.1] (z) in (2.1) when [theta] runs through all but the two exceptional values in [0, 27r) form a circle (or a line) that goes through the points [z.sub.1] and [z.sub.2], but does not include them, and that also passes through and includes z = 0.

In part 1 of the proof we note that zero-pole cancellation in (1.2) occurs precisely in the set [I.suvb.1] = {[z.sub.1], [z.sub.2]} when [theta] runs through [0, 2[pi]).

2. Suppose now that we have n = 2m distinct nodes [z.sub.1], ..., [z.sub.n], on the unit circle and n interpolation values [w.sub.1], ..., [w.sub.n], not all identical, and that Problem I is damaged with minimal degree [m.sup.l] = m. We may then assume that the data is arranged so that [w.sub.2] [not equal to] [w.sub.1]. Our goal is to derive a recursive procedure to obtain a parametrization of form (1.2), the case n = 2 (m = 1) being solved above in part 1 of the proof.

Let 1 [less than or equal to] k < [m.sup.l] = n/2 and assume that a parametrization of all solutions of exact degree k to the interpolation problem with data {[z.sub.1], ... , [z.sub.2]k} and (w.sub.1], ..., [w.sub.2k]} is given by

(2.5) [B.sub.k](z) - [P.sub.k](z)[e.sup.i[theta]] + [Q.sub.k](z)/[R.sub.k](z)[e.sup.i[theta]] + [S.sub.k](z),

with polynomials [P.sub.k], [Q.sub.k], [R.sub.k], [S.sub.k] of degree at most k, and [theta] [member of] [0, 2[pi]) with the exception of at most 2k values on [theta] that each generate in (2.5) at least one and at most k poles, counted with multiplicity, on the unit circle. Let [I.sub.k] be the set of poles on [partial derivative]D generated by these special values of [theta] and assume that [I.sub.k] = {[z.sub.1], ..., [Z.sub.k].

If we fix z := [z.sub.Zk+1] [not member of] [I.sub.k] in (2.5), then [B.sub.k]([z.sub.2k+1]) can be interpreted as a Mobius transformation mapping the unit circle injectively onto itself when [theta] runs through [0, 2[pi]). This holds, because if we choose three different values of [theta] that are not exceptional values, say [[theta].sub.j], j = 1, 2, 3, and let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] be the three corresponding unimodular interpolants given by (2.5), then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], are three distinct numbers on the unit circle. Suppose that this does not hold and that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (z) is a rational function of degree at most 2k with zeros in the distinct points [z.sub.1], ..., [z.sub.2k+1], so it is actually identically zero, which is a contradiction. Therefore we can find a [[theta].sub.1] [member of] [0, 2[pi]) so that [B.sub.k]([z.sub.2k+1]) = [w.sub.2k+1]. The same procedure fixing z := [z.sub.2k+2] [not member of] [I.sub.k] (2.5) gives a [[bar.[theta].sub.2] [member of] [0, 2[pi]) so that [B.sub.k] ([z.sub.2k+2]) = [w.sub.2k+2]. Denoting [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] we find that

(2.6) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Suppose that [[??].w].sub.1] = [[??].w].sub.2] and [[??].sub.1] is not a special value of [theta], that is, [theta] = [[??].sub.1] in (2.5) does not generate poles on [partial derivative]D. This could occur only if k < [m.sup.l] -1, because otherwise [B.sub.k] (z) in (2.5) with [theta] = [[??].sub.1] would be an interpolant of degree k = [m.sup.l] - 1 to all of the data, which gives a contradiction. Then it is possible to find an index i [member of] {2k + 3, ..., n} so that when we interchange the data points [z.sub.2k+2] with [z.sub.i] and [w.sub.2k+2] with [w.sub.i], respectively, we have [[??].sub.1] [not equal to] [[??].sub.2] in (2.6). If this were not the case, then [B.sub.k](z) in (2.5) with [theta] = [[??].sub.l] would be a uniquely determined fragile interpolant (of degree k < [m.sup.l]) to the data {[z.sub.1], ..., [z.sub.n]}, {[w.sub.1], ..., [w.sub.n]}, which gives a contradiction.

Suppose that [[??].sub.1] = [[??].sub.2] and [[??].sub.1] is a special value of [theta] giving [k.sub.1] poles, 1 [less than or equal to] [k.sub.1] [less than or equal to] k, on the unit circle for [B.sub.k](z) in (2.5). Considering the case with poles of multiplicity one, (the case with poles of higher multiplicity is treated in an analogous manner), we may, by renumbering if necessary, assume that [z.sub.1], ..., [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] are the poles in (2.5). Suppose further, if k < [m.sup.l] - 1, that for every index i [member of] (2k+3,...,n} the interchanging of the data points [z.sub.2k+2] with [z.sub.i] and [w.sub.2k+2] with [w.sub.i], respectively, results in [[??].sub.1], = [[??].sub.2] in (2.6). Then the corresponding function [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (z) in (2.5) is of degree k - [k.sub.1], (due to zero-pole cancellation in z = [z.sub.j], j = 1, ..., [k.sub.1]), and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], ..., n. Let B (z) be one of the damaged interpolants of exact degree [m.sup.l] = n/2. Then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is a rational function of degree at most (k - [k.sub.l]) + [m.sup.l] [less than or equal to] (n/2 -1 - [k.sub.l]) + n/2 = n - [k.sub.l] - 1. Since F([z.sub.j]) = 0, j = [k.sub.1] + 1, ..., n, we have F(z) = 0, but this gives a contradiction.

Thus we conclude that when Problem I is damaged with [m.sup.l] = n/2 it is always possible to rearrange the data points {[z.sub.4], ..., [z.sub.n]}, {[w.sub.4], ..., [w.sub.n]} so that [[??].sub.1] [not equal to] [[??].sub.2] holds in (2.6).

Now consider the interpolation problem with nodes {[z.sub.2k+1], [z.sub.2k+2]} and interpolation values {[[??].sub.1], [[??].sub.2]}, where [[??].sub.1] [not equal to] [[??].sub.2]. All unimodular interpolants of degree 1 are given by

(2.7) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

for those [theta] [member of] [0, 2[pi]) that do not give a pole on the unit circle, and where [??](z), [??](z), [??](z) and [??](z) are constructed from one of the formulas (2.2), (2.3) or (2.4). According to part 1 of the proof there are two exceptional values of [theta] corresponding to the poles z = [z.sub.2k+1] and z = [z.sub.2k+2] on [partial derivative]D. Substituting [e.sup.i.[theta]] in (2.5) by [??] in (2.7) gives a parametrization

(2.8) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

where

(2.9) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

of all rational unimodular interpolants of exact degree k + 1 to the interpolation data {[z.sub.1], ..., [z.sub.2k+2]}, {[w.sub.1], ..., [w.sub.2k+2]}, with the exception of those parameters [theta] in (2.8) that give poles on the unit circle. To prove that no solutions are lost in (2.8) we choose an arbitrary interpolant B(z) of irreducible degree k + 1 and extend the interpolation problem by appending a node [??] [member of] [partial derivative]D \ {[z.sub.1], ..., [z.sub.2k+2]} and a corresponding interpolation value [??] := B([??]). Then the extended problem with 2(k + 1) + 1 nodes and minimal degree k + 1 is elastic with the unique solution B(z). If we fix z := [??] in (2.8), then there is a [??] [member of] [0, 2[pi]) such that [theta] = [??] gives [B.sub.k+1]([??]) = [??]. Assuming that [??] is an exceptional value of [??] we reach a contradiction in an analogous way to the second paragraph after (2.6) by consider- ing F(z) := [B.sub.k+1](z) - B(z) for [theta] = [theta]. Thus [theta] is not an exceptional value of [theta] and then [B.sub.k+1] - B when [theta] = [theta].

Next we determine the location of the poles on [partial derivative]D of [B.sub.k+1] constituting the set [I.sub.k+1]. Thus we have to determine the zeros of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], on the unit circle, which using (2.9) is equivalent to solving the equation

(2.10) [R.sub.k](z)([??](z)[e.sup.i[theta]] + [??](z)) + [S.sub.k](z)([??](z)[e.sup.i[theta]] + [??](z)) = 0.

Clearly [z.sub.2k+1] and [z.sub.2k+2] are solutions and belong to [I.sub.k+1] for two suitable choices of [theta] given by part 1 of the proof. Let [z.sub0] [memberof] [partial derivative]D be a solution to (2.10) such that [z.sub.2k+1] [not equal to] [z.sub.0] [not equal to] [z.sub.2k+2]. For z = [z.sub.0] equation (2.10) is equivalent to

(2.11) [R.sub.k][??]([z.sub.0])[e.sup.i[theta]] + [??]([z.sub.0])/[??]([z.sub.0])[e.sup.i[theta]] + [??]([z.sub.0]) + [S.sub.k]([z.sub.0]) = 0,

from which we conclude that [z.sub.0] [memberof] [I.sub.k]. All points [z.sub.0] [member of] [I.sub.k] are zeros for equations (2.10) and (2.11), for appropriate choices of [theta]. Thus we have [I.sub.k+1] = {[z.sub.1], ..., [z.sub.2k+2]} and at most 2k + 2 exceptional values of [theta] in [0, 2[pi]) that generate the poles in [I.sub.k+1].

REMARK 2.2. The proof of Theorem 2.1 presents a recursive construction of the Nevanlinna parametrization of all solutions to a damaged Problem I with n = 2m interpolation nodes and minimal degree [m.sup.l] = n/2. This parametrization has the advantage over the one constructed in Section 3 in that it is easy to check, by computing the solutions for different values of the parameter [thea], if there are interpolating finite Blaschke products. In each recursive step we can also keep track of how the exceptional values of [theta] are transformed by [??] when [e.sup.i[theta]] is substituted in (2.5).

REMARK 2.3. That the number of exceptional values of [theta] [member of] [0, 2[pi]) can be strictly less than n is demonstrated by a small example, (n = 4, [m.sup.l] = m = 2), where [z.sub.1] = 1, [z.sub.2] = i, [z.sub.3] = -1, [z.sub.4] = -i and [w.sub.l] = 1, [w.sub.2] = -1, [w.sub.3] = i, [w.sub.4] = i. Then the recursive procedure gives the parametrization

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

with three exceptional values of [theta], {[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]} =, that give the poles [I.sub.2] = {[z.sub.1], ..., [z.sub.4]}.

REMARK 2.4. Numerical experiments in Matlab were made with an implementation of the recursive procedure suggested by the above proof. After having computed the Nevanlinna parametrization for an interpolation problem, the parameter interval [0, 2[pi]) was discretized with step size 0.01 giving 629 values [[theta].sub.j], and the interpolation error was determined for each [[theta].sub.j]. The interpolation values [w.sub.j] were chosen randomly on the unit circle. We considered two ways of choosing the nodes [z.sub.j], either randomly or equidistantly on the unit circle. A general observation was that the closer a [[theta].sub.j] was to an exceptional value of [theta], the bigger the error was, which seems natural, since these cases correspond to nearly zero-pole cancellation in the parametrization. When looking at error plots there would typically be peaks in the vicinity of exceptional values of [theta] and the error for other [[theta].sub.j]'s would be relatively close to the minimal error. We observed that for randomly chosen [z.sub.j] about 90% of the [[theta].sub.j]'s gave an error that was less than 10 times the minimal error. For equidistant [z.sub.j]'s this figure was usually about 80%. Another way to obtain reduction in precision was to choose several nodes [z.sub.j] very closely spaced on the circle. Next we present some numerical data of typical (average) results obtained for problems with n = 20, 30, 50 and 100 nodes [z.sub.j]. We do this in the form of triplets: (n, maximal error, minimal error). As explained above, the attention should be paid to the first and last component in the triplet. For randomly chosen nodes [z.sub.j] we got the results:

(20, [10.sup.-8], [10.sup.-12]) (30, [10.sup.-7], [10.sup.-11]) (50,[10.sup.-6], [10.sup.10]), (100, [10.sup.-3], [10.sup.-7]).

For equidistantly chosen nodes the results:

(20,[10.sup.-9], [10.sup.-13]), (30,[10-.sup.-8], [10.sup.-12]), (50, [10.sup.-6], [10.sup.-9]), (100, [10.sup.0], [10.sup.-4]) .

Interestingly, the equidistant choice of nodes gave slightly better results for n [less than or equal to] 30 whereas the problems with randomly chosen nodes seemed to give more precise results when n [greater than or equal to] 50. At least for even n [less than or equal to] 100 it can be expected that the recursive procedure behaves quite well numerically. But on the other hand the precision in the implementation done by the author seems no longer satisfactory for all problems when n > 100, so it might be that the recursive procedure is numerically suited for small and middle-sized problems.

COROLLARY 2.5. Suppose that Problem I is damaged with minimal degree [m.sup.l] > [n/2J]. Then Problem I has infinitely many solutions and the set of all solutions cannot be represented by a Nevanlinna parametrization of form (1.2).

Proof. 1. Suppose that Problem I is damaged with minimal degree [m.sup.l] > [n/2] and that one arbitrarily chosen solution is given by [b.sub.1] (z). We can then extend the given interpolation data with nodes [z.sub.n+1], ..., [z.sub.2m], and interpolation values [w.sub.n+1] := [b.sub.1]([z.sub.n+l]), ..., [w.sub.2m], := [b.sub.1] ([z.sub.2m']). The extended problem must be damaged with minimal degree exactly [m.sup.l] and by Theorem 2.1 it has infinitely many solutions. All solutions of the extended problem solve the original Problem I, so it also has infinitely many solutions.

2. Assume that all solutions to the damaged Problem I are given by the Nevanlinna parametrization

b(z) = P(z)[e.sup.i[theta]] + Q (z)/R(z)[e.sup.i[theta]] + S(z),

for such [theta] [member of] [0, 2[pi]) that do not produce any poles on the unit circle and where the polyno- mials P, Q, R, S are of degree at most [m.sup.l]. Let us denote this parametrization by Npl. Then the arbitrarily chosen interpolant [b.sub.1] (z) in part 1 of the proof belongs to Npl and is given by [theta] = [[theta].sub.1]. Applying the recursive construction in the proof of Theorem 2.1 to the extended interpolation problem in part 1 of the proof we can find a Nevanlinna parametrization of solutions to the extended problem of the form (1.2) containing [b.sub.1] (z). All solutions in this parametrization are solutions to the original Problem I. Let us denote this parametrization by Np2 and choose an interpolant [b.sub.2](z) [??] [b.sub.1](z) from Np2. Then [b.sub.2](z) also belongs to Npl and is given by [theta] = [[theta].sub.2] [not equal to] [[theta].sub.1]. Define the rational function [F.sub.2](z) := [b.sub.1](z) - [b.sub.2](z) of degree at most 2[m.sup.l]. We have [F.sub.2]([z.sub.j]) = 0, j = 1, ..., 2[m.sup.l] and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

so we conclude that there is a [k.sub.1] [member of] C so that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

We make a new extension of the original Problem I by choosing nodes [[??].sub.n+1], ..., [??].sub.2m'], distinct from each other and from the nodes in the first extended problem, and interpolation values [[??].sub.n+1] := [b.sub.1]([[??].sub.zn+1]), ..., [[??].sub.2m'] := [b.sub.1] ([[??].sub.2m']). The new extended problem is damaged with minimal degree [m.sup.l] and has a Nevanlinna parametrization denoted Np3. Suppose [b.sub.3] (z) [member of] Np3 is a solution different from [b.sub.1] (z). Then [b.sub.3] (z) [member of] Npl and is obtained from Npl with [theta] = [[theta].sub.3] [not equal to] [[theta].sub.1]. In analogy with the above we have a new factorization of PS - QR,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

That the damaged problems with minimal degree [m.sup.l] > [n/2] are quite sparse in the set of all interpolation problems with n nodes is implied by the determinant criteria in Theorems 1.1 and 1.2. The easiest examples of damaged problems with minimal degree [m.sup.l] > [n/2] are those where n - [m.sup.l] of the interpolation values are equal to [w.sub.1] and [m.sup.l] values are equal to [w.sub.2], but these are of course not the only examples.

EXAMPLE 2.6. As a demonstration of the sparsity of fragile and damaged problems we consider interpolation problems with nodes [z.sub.1] = 1, [z.sub.2] = [e.sup.i[pi]/4], [z.sub.3] = i, [z.sub.4] = -1, [z.sub.5] = -i and interpolation values [w.sub.l] = 1, [w.sub.2] = -1 and [w.sub.3], [w.sub.4] and [w.sub.5] chosen freely on the unit circle. Such a problem is fragile ([m.sup.l] = 1), elastic ([m.sup.l] = 2) or damaged ([m.sup.l] > 2). The determinant criteria in Theorems 1.1 and 1.2 give that the fragile problems are obtained when [w.sub.5] is chosen freely on [partial derivative]D \ {-1} and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

The damaged problems are obtained when [w.sub.4] and [w.sub.5] are chosen arbitrarily on the circle so that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Thus we have "one degree of freedom" constructing fragile problems and "two degrees of freedom" to obtain damaged problems.

As we have seen in this section in Theorem 2.1 the damaged problems of minimal degree [m.sup.l] = [n/2] are nicely representable by a Nevanlinna parametrization that can be computed recursively and which allows an easy check if there are interpolants of degree [m.sup.l] that are finite Blaschke products. When [m.sup.l] > [n/2] the picture is more complicated and the next section offers another way to parametrize all damaged interpolants and an algorithm to determine the minimal degree [m.sup.l] and to construct a parametrization of all interpolants of minimal degree. It will however not be easy in this case to decide if the parametrization contains finite Blaschke products.

3. Parametrization of damaged solutions. Suppose that we have n = 2m + 1 or n = 2m distinct points [z.sub.1], ..., [z.sub.n] and n arbitrary points [w.sub.1], ..., [w.sub.n] on the unit circle such that Problem I is damaged, i.e., the minimal degree m' of interpolants is greater than m for odd n and at least m for even n. Thus the solution to Problem I is nonunique and our goal in this section is to present constructive algebraic criteria to determine the minimal degree [m.sup.l] and a parametrization of all solutions to Problem I. In the theorems concerning the damaged cases it is not needed to assume that we have rotated the interpolation data so that [z.sub.1] = [w.sub.1] = 1.

Suppose that b(z), not necessarily in irreducible form and given by

(3.1) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

is a solution to Problem I. We shall prove that b(z), and in fact all interpolating rational unimodular functions of degree at most n - 1, can be constructed with the aid of linear combinations of n linearly independent coneigenvectors connected to a coneigenvalue problem formed directly using the given interpolation data. To this end we define the n x n matrices [E.sub.n], [D.sub.n] and [C.sub.n] by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

and

(3.3) [C.sub.n] = [E..sup.-1.sub.n], [D.sub.n].

The matrix [C.sub.n] is well-defined because [E.sub.n] is a nonsingular Vandermonde matrix. Before we continue with our main theme we need to establish some properties of the matrices in (3.2) and (3.3).

LEMMA 3.1. Let [I.sub.n] denote the n x n identity matrix and choose [theta] [member of] [0, 2[pi]) so that [-e.sup.-i2[theta]] is not an eigenvalue of [C.sub.n]. Define further the matrix [S.sub.[theta]] by [S.sub.[theta]] := [e.sup.i[theta]] [C.sub.n] + [e.sup.-i[theta]] [I.sub.n].

Then

[C.sub.n][[bar.C].sub.n] = [I.sub.n],

the matrix [S.sub.[theta]] is nonsingular and

(3.4) [C.sub.n] = [S.sub.[theta]] [[bar.S].sup.-1.sub.[theta]].

Proof. Define diagonal matrices W and J and the permutation matrix P by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Notice that P [bar.P] = [P.sup.2] = [I.sub.n] and that since [w.sub.j] and [z.sub.j] are on the unit circle we have W [bar.W] = J [bar.J] = [I.sub.n]. It is now easily verified that we have the representations

[D.sub.n] = W[E.sub.n]P, [E.sub.n]P = J[[bar.E].sub.n].

From this we conclude that

[E.sup.-1.sub.n] = P [[bar.E].sup.-1.sub.n] [bar.J] and P [[bar.E].sup.-1.sub.n] = [E.sup.-1.sub.n] J,

and thus by (3.3) and the identities above we have

[C.sub.n][[bar.C].sub.n] = [E.sup.-1.sub.n] W [E.sub.n] [[bar.E].sub.n] [bar.W] [[bar.E].sub.n] P = [E.sup.-1.sub.n] W [E.sub.n] [E.sup.-1.sub.n] J [bar.W] [[bar.E].sub.n] P = [E.sup.-1.sub.n] W [bar.W] J [[bar.E].sub.n] P = [E.sup.-1.sub.n] J [[bar.E].sub.n] P = P [[bar.E].sup.-1.sub.n] [[bar.E].sub.n] P = [I.sub.n].

Since [S.sub.[theta]] can be written in the form [S.sub.[theta]] = [e.sup.i[theta]] ([C.sub.n] - ([-e.sup.-i2[theta]]) [I.sub.n]) and by assumption [-e.sup.-i2[theta]] is not an eigenvalue of [C.sub.n], we find that [S.sub.[theta]] is nonsingular. Furthermore

[C.sub.n] [[bar.S].sub.[theta]] = [C.sub.n] ([e.sup.-i[theta]] [[bar.C].sub.n] + [e.sup.i[theta]] [I.sub.n]) = [e.sup.-i[theta]] [C.sub.n] [[bar.C].sub.n] + [e.sup.i[theta]] [C.sub.n] = [S.sub.[theta]],

which establishes formula (3.4).

Continuing with our investigation, we restate the assumption that b(z) in (3.1) is a solution to Problem I, not necessarily in irreducible form. Letting the numerator coefficients in (3.1) define the vector y = [([[alpha].sub.0],..., [[alpha].sub.n-1]).sup.T] we find that the satisfied interpolation conditions

b([z.sub.j]) = [w.sub.j], j = 1,...,n,

can be expressed in the equivalent forms

(3.5) [E.sub.n]y = [D.sub.n][bar.y] [??] [C.sub.n][bar.y] = [mu]y, [mu] = 1,

which means that y is a coneigenvector and a solution to a so-called coneigenvalue problem with the corresponding coneigenvalue [mu] = 1. See, e.g., Horn and Johnson [6, Section 4.6] for the definition and properties of coneigenvalue problems.

Let {[e.sub.1],..., [e.sub.n]} denote the standard basis in [R.sup.n]. Then the linearly independent columns [v.sub.1],..., [v.sub.n] of [S.sub.[theta]] defined in Lemma 3.1 are given by

[v.sub.j] = [e.sup.i[theta]] [C.sub.n] [e.sub.j] + [e.sup.-i[theta]] [e.sub.j] =: [([a.sup.(j).sub.i]),..., [a.sup.(j).sub.n])).sup.T] j = 1,...,n.

These vectors supply us with n linearly independent coneigenvectors associated with the coneigenvalue [mu] = 1 in (3.5), because

[C.sub.n] [[bar.v].sub.j] = [e.sup.-i[theta]] [C.sub.n] [[bar.C].sub.n] [e.sub.j] + [e.sup.i[theta]] [C.sub.n] [e.sub.j] = [v.sub.j], J = 1,...,n.

A linear combination [c.sub.1][v.sub.1] + ... + [c.sub.n][v.sub.n] is a coneigenvector corresponding to [mu] = 1 if and only if [c.sub.1],..., [C.sub.n] [member of] R. Then we can find real numbers [c.sub.1],..., [C.sub.n] so that the numerator of b(z) in (3.1) is given by

(3.6) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Conversely, every linear combination [c.sub.1] [v.sub.1] + ... + [C.sub.n] [v.sub.n] with [c.sub.j] [member of] R will give the numerator p(z) in (3.6) of an interpolating unimodular rational function of degree at most n - 1, except for the choices of [c.sub.1],..., [C.sub.n] [member of] R which yield one or several zeros for the numerator p(z) (and the denominator of b(z)) in the set {[z.sub.1],..., [z.sub.n]} of interpolation nodes resulting in zero-pole cancellation and possibly destroying the interpolation property at such nodes. (A solution where the interpolation property is not destroyed due to zero-pole cancellation is not lost, for instance if we have zero-pole cancellation in [z.sub.1] of multiplicity one, p(z) = [??](z) (z - z1), and [??](z) is the numerator of an unimodular interpolant, then any choice of [t.sub.1] [member of] [partial derivative]D\ {[z.sub.1],..., [Z.sub.n]} will correspond to a set of real numbers [c.sub.1],..., [C.sub.n] that give p(z) = [??](z) (z - [t.sub.1]) in (3.6).) Zeros for p(z) in points on the unit circle other than nodes will cause the degree of the interpolant to drop but will not affect the interpolation property. Thus we have proved the following theorem that gives us a parametrization of all rational unimodular interpolants with the aid of the independent coneigenvectors [v.sub.j] and the parameters [c.sub.1],..., [C.sub.n] in R.

THEOREM 3.2. Suppose that we have n distinct points [z.sub.1],..., [Z.sub.n] and n arbitrary points [w.sub.1],..., [w.sub.n] on the unit circle giving a damaged Problem L Let n linearly independent coneigenvectors corresponding to the coneigenvalue [mu] = 1 for the matrix [C.sub.n] be given by the column vectors [v.sub.j] = [([a.sup.(j).sub.1],..., [a.sup.(j).sub.n]).sup.T], j = 1,..., n, of [S.sub.[theta]] in Lemma 3.1. Suppose that an arbitrarily chosen rational unimodular interpolant, not necessarily in irreducible form, is given by

(3.7) b(z) = [[alpha].sub.0] + [[alpha].sub.1] z + ... + [[alpha].sub.n-1] [z.sup.n-1]/ [[bar.[alpha]].sub.n-1] + [[bar.[alpha]].sub.n-2] z + ... + [[bar.[alpha]].sub.0] [z.sup.n-1], [[alpha].sub.0],..., [[alpha].sub.n-1] [member of] C.

Then we can find real numbers [c.sub.1],..., [C.sub.n] such that

(3.8) [[alpha].sub.j] [n.summation over (k=1)] [c.sub.k] [a.sup.(k).sub.j+1], j = 0,..., n - 1.

Conversely, every choice of [c.sub.1],..., [C.sub.n] [member of] R, that via (3.8) defines b(z) in (3.7) so that the numerator has no zeros in the set {[z.sub.1],..., [z.sub.n]}, gives a rational unimodular interpolant.

If n = 2 or n = 3 and Problem I is damaged, then the minimal degree is n - 1 and all solutions are given by the parametrization in Theorem 3.2, which is also the case if n > 3 and the minimal degree of interpolants is n - 1. To obtain all solutions to a damaged Problem I when n > 3 and the minimal degree is less than n - 1 we are led to find the subspace of [R.sup.n] giving the parameter values of [c.sub.1],..., [c.sub.n] in Theorem 3.2 that yield minimal-degree interpolants. This can be done in a systematic way by imposing zeros on the unit circle.

Suppose therefore that Problem I is damaged, that n > 3 and that there are damaged interpolants of degree at most m', where m' < n - 1. Define k := (n - 1) - m' > 0. Choose arbitrarily k distinct points [t.sub.1],..., [t.sub.k] on the unit circle such that {[t.sub.1],..., [t.sub.k]} [intersection] {[z.sub.1],..., [z.sub.n]} = [??]. Suppose that b (z) is an arbitrarily chosen damaged interpolant of degree at most m' given, not necessarily in irreducible form, by

b(z) = - [[beta].sub.0] + [[beta].sub.1] z + ... + [[beta].sub.m'] [z.sup.m']/ [[bar.[beta]].sub.m'] + [[bar.[beta]].sub.m'-1] z + ... + [[bar.[beta]].sub.0] [z.sup.m'], [[beta].sub.0],..., [[beta].sub.m'] [member of] C.

Impose k zeros, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], on [partial derivative]D obtaining [??] [equivalent to] b by

(3.9) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

We conclude that there are (damaged) interpolants of degree at most m' < n - 1 if and only if for any choice of k = (n - 1) - m' distinct points [t.sub.1],..., [t.sub.k] [member of] [partial derivative]D not coinciding with any of the nodes [z.sub.1],..., [z.sub.n], it is possible to find real numbers [c.sub.1],..., [c.sub.n] such that p(z) in (3.6) satisfies p([z.sub.j]) [not equal to] 0, j = 1,..., n, and p([t.sub.j]) = 0, j = 1,..., k.

Suppose now that we have the k points [t.sub.1],..., [t.sub.k] as specified above and the n linearly independent coneigenvectors [v.sub.j] = [([a.sup.(j).sub.1]),..., [a.sup.(j).sub.n]).sup.T], j = 1,..., n , associated with the coneigenvalue [mu] = 1 for [C.sub.n] and given by the columns of [S.sub.[theta]] in Lemma 3.1. We wish to obtain an algebraic criterion for deciding if there are damaged interpolants of degree at most m' = (n - 1) - k. We define the following homogeneous linear system with k equations and n unknowns [c.sub.1],..., [c.sub.n],

(3.10) [n.summation over (j=1)]([n.summation over (j=1)] [c.sub.k] [a.sup.(k).sub.j]) [t.sup.j-1.sub.l] = 0, l = 1,..., k.

Then (3.10) has the equivalent matrix formulation

(3.11) H c = 0,

where c = [([c.sub.1],..., [c.sub.n]).sup.T] and where the elements of H are given by

(3.12) [H.sub.l,r] = [n.summation over (j=1)] [a.sup.(r).sub.j] [t.sup.j-1.sub.l]. l = 1,..., k, r = 1,...,n.

We are interested in nontrivial real solutions to (3.11). First we establish that rank H = k. Let the independent columns of [S.sub.[theta]] define the polynomials

[[PHI].sub.j](z) = [a.sup.(j).sub.1] + ... + [a.sup.(j).sub.n] [z.sup.n-1], j = 1,..., n.

Choose arbitrarily n distinct points [x.sub.1,..., [x.sub.n] on [partial derivative]D. Let the matrix G have the elements [G.sub.i,j] = [[PHI].sub.j]([x.sub.i]), i, j = 1,..., n. Suppose that G is singular. Then there exist numbers [[lambda].sub.1],..., [[lambda].sub.n], not all zero, such that [[SIGMA].sup.n.sub.j=1] [[lambda].sub.j] [[PHI].sub.j]([x.sub.i]) = 0 for i = 1,..., n. The polynomial P(x) := [[SIGMA].sup.n.sub.j=1] [[lambda].sub.j] [[PHI].sub.j](x) [??] 0 has n distinct zeros, which gives a contradiction, so G is non-singular. We observe that the elements of H are given by [H.sub.i,j] = [[PHI].sub.j]([t.sub.i]), i = 1,..., k, j = 1,..., n, and thus the k rows of H are independent and rank H = k.

Assume now that a basis for the null space of H is given by the vectors

(3.13) [u.sub.j] = [([u.sup.(j).sub.1],..., [u.sup.(j).sub.n]).sup.T], j = 1,..., n - k.

Since H is a matrix with complex elements we cannot in general assume that the basis in (3.13) is real. To get the desired subspace of real solutions c to (3.11) we must consider all complex linear combinations of the vectors in (3.13) that result in real vectors c. Let U be the matrix with the basis vectors in (3.13) as columns,

(3.14) U = ([u.sub.1] [u.sub.2] ... [u.sub.n-k]).

Denote by [U.sup.re] and [U.sup.im] the real and imaginary parts of U. We define the n x 2(n - k) real block matrix N by

(3.15) N = ([U.sup.im] [U.sup.re]).

The null space of N corresponds to all linear combinations of the basis in (3.13) that result in real vectors. More precisely, let an arbitrary linear combination of the basis vectors in (3.13) be given by

(3.16) [n-k.summation over (j=1)] ([a.sub.j] + i [b.sub.j]) [u.sub.j], [a.sub.j], [b.sub.j] [member of] R.

The requirement that the vector in (3.16) is real is equivalent to the equation

N x = 0,

where x := [([a.sub.1],..., [a.sub.n-k], [b.sub.1],..., [b.sub.n-k]).sup.T]. Since we assume that Problem I is damaged we have m' [greater than or equal to] n/2 and k = (n - 1) - m' [less than or equal to] n/2 - 1, so 2(n - k) [greater than or equal to] n + 2 and consequently the null space of N is nontrivial and at least 2-dimensional. On the other hand it is easy to show that the rank of N is at least n - k. Let n' denote the dimension of the null space of N, where 2 [less than or equal to] n' [less than or equal to] n - k, and suppose that a real basis for this null space is given by

(3.17) [x.sub.j] = [([x.sup.(j).sub.1],..., [x.sup.(j).sub.2(n-k)]).sup.T], j = 1,..., n'.

Now we define the real vectors [y.sub.1],..., [y.sub.n'] by

(3.18) [y.sub.j] := [n-k.summation over (l=1)] ([x.sup.(j).sub.l] + i [x.sup.(j).sub.n-k+1]) [u.sub.l] =: [([y.sup.(j).sub.1],..., [y.sup.(j).sub.n]).sup.T], j = 1,..., n'.

Next we show that the vectors in (3.18) are linearly independent. Introduce the notation

[d.sup.(r).sub.l] := [x.sup.(r).sub.l] + i [x.sup.(r).sub.n-k+l], l = 1,..., n - k, r = 1,..., n'.

Then for the unknowns [a.sub.1],...,[a.sub.n'] [member of] C we have, since the vectors [u.sub.1],..., [u.sub.n-k] defined in (3.13) are linearly independent, that

(3.19) [n'.summation over (r=1)] [a.sub.r] [y.sub.r] = 0 [??] ... [??][n'.summation over (r=1)] [a.sub.r] [d.sup.(r).sub.l] = 0, l = 1,..., n-k.

We note that if n' < n - k, then the system in (3.19) is overdetermined and if n' = n - k, then the system is square. The fact that the vectors in (3.17) are independent makes it easy to show that the columns of the rightmost system in (3.19) are independent, so only the trivial solution [a.sub.1] = ... = [a.sub.n'] = 0 is possible. Thus we conclude that the real vectors in (3.18) are linearly independent and provide us with a basis for the real solutions c of (3.11).

Denote by [p.sub.j](z), for j = 1,..., n', the polynomial p(z) in (3.6) obtained by choosing [c.sub.k] = [y.sup.(j).sub.k], k = 1,..., n. Then it follows from the conclusion made after formula 3.9) = k that there are damaged interpolants of degree at most m' if and only if there is no index i [member of] {1, 2,..., n} such that [p.sub.1]([z.sub.i]) = [p.sub.2]([z.sub.i]) = ... = [p.sub.n']([z.sub.i]) = 0.

Furthermore, if there exist damaged interpolants of degree at most m', then all real linear combinations of the vectors in (3.18) giving vectors c = [([c.sub.1],..., [c.sub.n]).sup.T] that define polynomials p(z) in (3.6) with no zeros in {[z.sub.1],..., [z.sub.n]}, give rational unimodular interpolants of irreducible degree at most m'. Thus we have:

THEOREM 3.3. Suppose that we have n distinct points [z.sub.1],..., [Z.sub.n] and n arbitrary points [w.sub.1],..., [w.sub.n] on the unit circle [partial derivative]D and that Problem I is damaged. Let the integer m' be chosen so that n/2 [less than or equal to] m' < n - 1 and define k := (n - 1) - m' > 0. Choose arbitrarily the k distinct points [t.sub.1],..., [t.sub.k] on the unit circle so that {[t.sub.1],..., [t.sub.k]} [intersection] {[z.sub.1],..., [z.sub.n]} = [??]. Let n linearly independent coneigenvectors

[v.sub.j] = [([a.sup.(j).sub.1],..., [a.sup.(J).sub.n]).sup.T], j = 1,..., n,

associated with the coneigenvalue [mu] = 1 for the matrix [C.sub.n] in (3.3) be given by the columns of [S.sub.[theta]] in Lemma 3.1. Let the matrices H, U and N be defined by (3.12), (3.14) and (3.15), respectively. Then the vectors

(3.20) [y.sub.j] = [([y.sup.(j).sub.1],..., [y.sup.(j).sub.n]).sup.T], j = 1,..., n', 2 [less than or equal to] n' [less than or equal to] n - k,

obtained from (3.18), form a real basis for all real solutions c to the homogeneous equation (3.11). Define the polynomials

(3.21) [p.sub.j](z) := [n.summation over (i=1)] ([n.summation over (k=1)] [y.sup.(j).sub.k] [a.sup.(k).sub.i]) z[i.sup.-1], j = 1,..., n'.

Then there exist damaged rational unimodular interpolants of degree at most m' if and only if there is no index i [member of] {1, 2,..., n} such that [p.sub.i]([z.sub.i]) = [p.sub.2]([z.sub.i]) = ... = [P.sub.n']([z.sub.i]) = 0.

If there exist damaged interpolants of degree at most m', then all such interpolants can be constructed by considering all real linear combinations c = [([c.sub.1],..., [c.sub.n]).sup.T] := [[SIGMA].sup.n'.sub.j=1] [[beta].sub.j] [y.sub.j], [[beta].sub.j] [member of] R, of vectors in (3.20) that define polynomials p(z) by

(3.22) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

with no zeros in {[z.sub.1],..., [z.sub.n]}. All such p(z) define rational unimodular interpolants

(3.23) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

that are reducible to a degree at most m'.

Now we are in a position, using Theorems 1.1, 1.2, 3.2 and 3.3, to present an algorithm for classifying any given interpolation problem. We can determine if it is fragile, elastic or damaged. In the fragile and elastic cases we can calculate the unique solution of minimal degree. In the damaged cases we can find a parametrization of all solutions of minimal degree.

Algorithm for determining all interpolants of minimal degree

Suppose we are given n distinct points [z.sub.1],..., [z.sub.n] and n points [w.sub.1],..., [w.sub.n] on [partial derivative]D, n [greater than or equal to] 2, such that [z.sub.1] = [w.sub.1] = 1, (no restriction). Define m := [??]n/2[??] . We exclude the trivial case [w.sub.1] = ... = [w.sub.n] so the minimal degree m' satisfies 1 [less than or equal to] m' [less than or equal to] n - 1.

Step 1. If n is even, then go to Step 2, otherwise form the matrix [A.sub.m] in (1.3) and use Theorem 1.1 to decide if Problem I is elastic. If it is not elastic, then go to Step 2, otherwise calculate the unique solution b(z) in (1.5) and go to Step 7.

Step 2. If n < 4, then go to Step 4, otherwise define m' := 0.

Step 3. Set m' := m' + 1. Form the matrix [A.sub.m'] in (1.3) and use Theorem 1.2 to check if Problem I has a fragile solution of degree m'. If there is a fragile solution b(z), then obtain it from (1.7) and go to Step 7. If there is no fragile solution of degree m' and if m' = m - 1, then go to Step 4, otherwise iterate Step 3.

Step 4. Form the matrices [E.sub.n] and [D.sub.n] in (3.2) and compute the matrix [C.sub.n] in (3.3). Determine the eigenvalues of [C.sub.n] Choose [theta] [member of] [0, 2[pi]) so that [-e.sup.-2i[theta]] is not an eigenvalue of [C.sub.n]. Compute the nonsingular matrix [S.sub.[theta]] in Lemma 3.1 and let the columns of this matrix be given by [v.sub.j] = [([a.sup.(j).sub.1],..., [a.sup.(j).sub.n]).sup.T], j = 1,..., n. If n < 4, then go to Step 6. If n is even, then define m' := m - 1, otherwise define m' := m.

Step 5. Set m' := m' + 1. Define k := (n - 1) - m' and choose distinct points [t.sub.1],..., [t.sub.k] on [partial derivative]D so that {[t.sub.1],..., [t.sub.k]} [intersection] {[z.sub.1],..., [z.sub.n]} = [??]. Compute the matrix H in (3.12) and a basis [u.sub.j] = [([u.sup.(j).sub.1],..., [u.sup.(j).sub.n]).sup.T], j = 1,..., n - k, for the null space of H. Use this basis to form the matrices U and N in (3.14) and (3.15). Compute a real basis [x.sub.j] = [([x.sup.(j).sub.1],..., [x.sup.(j).sub.2(n-k)]).sup.T] j = 1,..., n', 2 [less than or equal to] n' [less than or equal to] n - k, for the null space of N. Form the real basis for all real solutions c to (3.11), given by [y.sub.j] = [([y.sup.(j).sub.1],..., [y.sup.(j).sub.n]).sup.T], j = 1,..., n', in (3.18), with the aid of [{[u.sub.j]}.sup.n-k.sub.j=1] and [{[x.sub.j]}.sup.n'.sub.j=1]. Use Theorem 3.3 to determine if there are damaged interpolants of degree at most m'. If Theorem 3.3 shows that there are interpolants of degree at most m', then Problem I is damaged and the minimal degree of interpolants is exactly m'. In this case use the vectors [{[v.sub.j]}.sup.n.sub.j=1] and [{[y.sub.j]}.sup.n'.sub.j=1] and formula (3.23) to obtain a parametrization of all damaged solutions of minimal degree m' and go to Step 7. If there are no interpolants of degree at most m' and if m' = n - 2, then go to Step 6, otherwise iterate Step 5.

Step 6. The minimal degree of the interpolants is m' = n - 1 and with the aid of the vectors [v.sub.j], j = 1,..., n computed in Step 4, and formulas (3.8) and (3.7) in Theorem 3.2, we obtain a parametrization of all solutions to Problem I.

Step 7. Terminate the algorithm.

An implementation of the algorithm in Matlab code is available upon request.

REMARK 3.4. The main problems in implementing the algorithm are found in step 4 in solving the coneigenvalue problem (3.5) and partly in step 5 in choosing the zeros [t.sub.1],..., [t.sub.k] that are imposed on the unit circle in the damaged cases. We have found that a sound way of imposing the zeros on the circle is to sort the open arcs that do not contain nodes with respect to their length, and to place the [t.sub.j]'s in the middle of the longest arcs, one [t.sub.j] in each chosen arc. We have considered two ways of implementing step 4 and done numerical experiments with randomly chosen interpolation values [w.sub.j], and either equidistant or randomly chosen nodes [z.sub.j].

a) Suppose first that the nodes [z.sub.j] are equidistant and that the [w.sub.j] are randomly chosen on the circle. Then it is numerically safe to form the matrix [C.sub.n] in (3.5) by inverting the Vandermonde matrix [E.sub.n], because we have observed that E,, has just one singular value [sigma] = [square root of n], so the condition number in the 2-norm is cond([E.sub.n]) = 1. Furthermore, the matrix C,, has all its eigenvalues on the unit circle, so in forming the matrix [S.sub.[theta]] in Lemma 3.1 we have chosen [theta] so that [-e.sup.-i2[theta]] is in the middle of the longest open arc of the circle that does not contain eigenvalues of [C.sub.n]. By this selection we have noticed that the condition number of [S.sub.[theta]] is quite small for n [less than or equal to] 100. We have conducted numerical experiments with n = 20, 30, 50 and 100. For each generated interpolation problem we have, from the numerically obtained parametrization of solutions of minimal degree, randomly chosen 500 solutions and determined the interpolation error for each solution, storing the minimal, maximal and mean interpolation error in a quadruple of the form: (n, maximal error, minimal error, mean error). For each n we have taken the averages of all generated quadruples, where attention should be paid to the third and fourth component. We obtained the following results:

(20,[10.sup.-10],[10.sup.-14],[10.sup.-12]), (30,[10.sup.-9],[10.sup.-13],[10.sup.-11]), (50,[10.sup.-4],[10.sup.-8],[10.sup.-7]), (100,[10.sup.-2],[10.sup.-6],[10.sup.-4]).

To avoid the inversion of [E.sub.n] we considered another way of generating [S.sub.[theta]]. By considering the first equation [E.sub.n]y = [D.sub.n][bar.y] in (3.5), and by separating the real and imaginary parts, we obtain the equation

G x = 0,

where the 2n x 2n real block matrix G is given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

The notation indicates the use of the real and imaginary parts of [E.sub.n] and [D.sub.n], respectively. As a consequence of the fact that [C.sub.n] has n linearly independent coneigenvectors associated with the coneigenvalue [mu] = 1, the null space of G is always n-dimensional with a real basis [u.sub.1],..., [u.sub.n], which is conveniently computed with the matlab command: null (G) . Let [u.sup.(1).sub.k] be a vector defined by the n first components in [u.sub.k] and let [u.sup.(2).sub.k] be defined by the n last components. Defining [y.sub.k] := [u.sup.(1).sub.k] + i [u.sup.(2).sub.k], k = 1,..., n, we obtain n linearly independent coneigenvectors associated to the coneigenvalue [mu] = 1, so we can define [S.sub.[theta]] to be the matrix with columns [y.sub.1],..., [y.sub.n]. When we have equidistant nodes then, independent of n and [w.sub.j], we have observed that [S.sub.[theta]] has one singular value [sigma] = 1, so cond([S.sub.[theta]]) = 1. Performing similar numerical experiments as described above with this second approach we obtained the following results:

(20,[10.sup.-10],[10.sup.-14],[10.sup.-12]) , (30,10-9,10-13,10-11) , (50,10-5,10-9,10-7) , (100,10-3,10-6,10-5).

Our conclusion is that with our implementation both numerical methods described perform in a reliable way for problems with equidistant nodes and n [less than or equal to] 100.

b) Next we consider randomly chosen nodes [z.sub.j] and interpolation values [w.sub.j] on the unit circle. Then the experiments showed that when n [greater than or equal to] 20 it is no longer wise to invert the Vandermonde matrix [E.sub.n]. The only reliable option is to compute a real basis for the null space of G, as described above, to define [S.sub.[theta]]. In doing so we obtained, after performing numerical experiments:

(20,[10.sup.-9],[10.sup.-13],[10.sup.-11]), (30,[10.sup.-7],[10.sup.-10],[10.sup.-9]), (50,[10.sup.-4],[10.sup.-8],[10.sup.-6]), (100,[10.sup.-3],[10.sup.-6],[10.sup.-5]).

As a rule one should use the second method to compute [S.sub.[theta]], and if one has the choice, then equidistant nodes would give two reliable numerical methods for problems with n [less than or equal to] 100. In the experiments above n was chosen even and [w.sub.j] randomly, which almost certainly results in damaged problems with minimal degree n/2, since the minimal degree m' generically satisfies m' = [??]n/2[??]. We have also constructed damaged problems where the minimal degree is bigger than [??]n/2[??], for instance by choosing [w.sub.1] = ... = [w.sub.m'] = 1 and [w.sub.m'+1] = ... = [w.sub.n] [not equal to] [w.sub.1], and the numerical observation was that the algorithm managed quite satisfactorily in determining the minimal degree when n [less than or equal to] 100.

For the interesting subset of interpolating finite Blaschke products the presented algorithm can determine if there are fragile or elastic solutions and in the case of a damaged Problem I it supplies us with a lower bound of the minimal degree of interpolating Blaschke products. The purpose of the following example is to show that the lower bound need not be sharp.

EXAMPLE 3.5. We choose n = 4 and [z.sub.1] = 1, [z.sub.2] = i, [z.sub.3] = -1, [z.sub.4] = -i and [w.sub.1] = [w.sub.2] = 1, [w.sub.3] = [w.sub.4] = -1. Our algorithm shows that there is no fragile solution and that the minimal degree of damaged solutions is m' = 2. Mathematica was used to symbolically compute a parametrization of all solutions to Problem I.

We have chosen [theta] = 0 in Lemma 3.1, which gives [S.sub.0] = [C.sub.4] + [I.sub.4], and explicitly

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Since k = (n -1) - m' = 1 we impose one pole on the unit circle, which we have chosen to be [t.sub.1] := (1 + i)/[square root of 2]. The matrices H, U and N in (3.12), (3.14) and (3.15) are given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

A real basis in (3.17), of dimension n' = 2, for the null space of N is given by

([x.sub.1] = [(-3, 0, 1, 0, 0, 0).sup.T], [x.sub.2] = [(-2[square root of 2],1, 0, 0, 0, 0).sup.T]}.

A real basis for all real solutions c to (3.11) is now given by (3.18),

([y.sub.1] = [(-2 [square root of 2], 1, 0, -3).sup.T], [y.sub.2] = [(-3,0,1, - 2 [square root of 2]).sup.T]}

The polynomials in (3.21) are then easily computed,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

For arbitrary [[beta].sub.1], [[beta].sub.2] [member of] R we define the polynomial p(z) in (3.22),

p(z) := [[beta].sub.1] [p.sub.1](z) + [[beta].sub.2] [p.sub.2](z)

It is easy to check that p(z) has no zeros in {[z.sub.1],..., [z.sub.4]} if and only if [[beta].sub.1] [not equal to] [+ or -] [[beta].sub.2]. Forming b(z) in (3.23) we obtain all damaged interpolants of degree m' = 2,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where

[K.sub.1] ([[beta].sub.1], [[beta].sub.2]) := (1 + 3i) [[beta].sub.1] + (1 + 2i) [square root of 2] [[beta].sub.2]/ (-2 + i) [square root of 2] [[beta].sub.1] (3 - i) [[beta].sub.2]

and

[K.sub.2] ([[beta].sub.1], [[beta].sub.2]) := (-1 + 3i) [square root of 2] [[beta].sub.1] - (2 - 4i) [[beta].sub.2]/ (1 + 3i) [[beta].sub.1] + (1 - 2i) [square root of 2] [[beta].sub.2].

If [[beta].sub.1] = [[beta].sub.2] [not equal to] 0, then b(z) - 1 and if [[beta].sub.1] = -[[beta].sub.2] [not equal to] 0, then b(z) [equivalent to] -1, so both cases give a constant unimodular function that does not interpolate the data. In the case [[beta].sub.1] = [[beta].sub.2] = 0 the function b(z) is undefined.

Let [r.sub.1] and [r.sub.2], (dependent of [[beta].sub.1,2]), denote the zeros of b(z) when we have chosen [[beta].sub.1] [not equal to] [+ or -][[beta].sub.2]. We see from the numerator of b(z) above that [r.sub.1] [r.sub.2] = i must hold and thus we conclude that exactly one of the zeros is in D and the other one is in C \ [bar.D]. Consequently, there are no interpolating Blaschke products of degree m' = 2, (they are all of degree n - 1 = 3).

Observing that [K.sub.1]([[beta].sub.1], [[beta].sub.2]) x [K.sub.2] ([[beta].sub.1], [[beta].sub.2]) = 1 - i and that |[K.sub.1]([[beta].sub.1], [[beta].sub.2])| = 1 we obtain a Nevanlinna parametrization of the solutions of minimal degree m' = 2,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

which we already knew should exist by Theorem 2.1. Numerical experiments suggest that when n is even the minimal degree is m' = n/2 if and only if the dimension of the null space of N is n' = 2.

The important subclass of finite Blaschke products still offers difficult and interesting problems: How do we determine the minimal degree of interpolants in the damaged cases in an effective way, and is it possible to construct a parametrization of all such interpolants? These questions are left for future research.

Acknowledgements. The author is indebted to Professor Elias Wegert and Dr. Gunter Semmler for nice discussions and useful comments on the manuscript, as well as to the referees for constructive suggestions that improved the quality of this paper.

* Received November 26, 2007. Accepted for publication February 18, 2008. Published online on May 29, 2008. Recommended by M. Gutknecht. This work was supported by the Research Institute of the Abo Akademi University Foundation and the Magnus Ehrnrooth Foundation.

REFERENCES

 D. G. CANTOR AND R. R. PHELPS, An elementary interpolation theorem, Proc. Amer. Math. Soc., 16 (1965), pp. 523-525.

 C. GLADER, Rational unimodular interpolation on the unit circle, Comput. Methods Funct. Theory, 6 (2006), pp. 481-492.

 C. GLADER AND M. LINDSTROM, Finite Blaschke product interpolation on the closed unit disc, J. Math. Anal. Appl., 273 (2002), pp. 417-427.

 P. GORKIN AND R. RHODES, Boundary interpolation by finite Blaschke products, Constr. Approx., 27 (2008), pp. 75-98.

 G. A. HJELLE, Constructing interpolating Blaschke products with given preimages, Comput. Methods Funct. Theory, 7 (2007), pp. 43-54.

 P. A. HORN AND C. R. JOHNSON, Matrix Analysis, Cambridge University Press, Cambridge, UK, 1985.

 W. B. JONES AND S. RUSCHEWEYH, Blaschke product interpolation and its application to the design of digital filters, Constr. Approx., 3 (1987), pp. 405-409.

 G. SEMMLER AND E. WEGERT, Nonlinear Riemann-Hilbert problems and boundary interpolation, Comput. Methods Funct. Theory, 3 (2003), pp. 179-199.

 --, Boundary interpolation with Blaschke products of minimal degree, Comput. Methods Funct. Theory, 6 (2006), pp. 493-511.

 R. YOUNIS, Interpolation by a finite Blaschke product, Proc. Amer. Math. Soc., 78 (1980), pp. 451-452.