Didier Henrion

Simone Naldi

Mohab Safey El Din

Real root finding for rank defects in linear Hankel matrices

Let H 0 , . . . , H n be m × m matrices with entries in Q and Hankel structure, i.e. constant skew diagonals. We consider the linear Hankel matrix

and the problem of computing sample points in each connected component of the real algebraic set defined by the rank constraint rank(H(x)) ≤ r, for a given integer r ≤ m -1. Computing sample points in real algebraic sets defined by rank defects in linear matrices is a general problem that finds applications in many areas such as control theory, computational geometry, optimization, etc. Moreover, Hankel matrices appear in many areas of engineering sciences. Also, since Hankel matrices are symmetric, any algorithmic development for this problem can be seen as a first step towards a dedicated exact algorithm for solving semi-definite programming problems, i.e. linear matrix inequalities. Under some genericity assumptions on the input (such as smoothness of an incidence variety), we design a probabilistic algorithm for tackling this problem. It is an adaptation of the so-called critical point method that takes advantage of the special structure of the problem. Its complexity reflects this: it is essentially quadratic in specific degree bounds on an incidence variety. We report on practical experiments and analyze how the algorithm takes advantage of this special structure. A first implementation outperforms existing implementations for computing sample points in general real algebraic sets: it tackles examples that are out of reach of the state-of-the-art.

Introduction

Problem statement and motivation Let Q, R, C be respectively the fields of rational, real and complex numbers, and let m, n be positive integers. Given m × m matrices H 0 , H 1 , . . . , H n with entries in Q and Hankel structure, i.e. constant skew diagonals, we consider the linear Hankel matrix H(x) = H 0 + x 1 H 1 + . . . + x n H n , denoted H for short, and the algebraic set H r = {x ∈ C n : rank H(x) ≤ r}.

The goal of this paper is to provide an efficient algorithm for computing at least one sample point per connected component of the real algebraic set H r ∩ R n .

Such an algorithm can be used to solve the matrix rank minimization problem for H. Matrix rank minimization mostly consists of minimizing the rank of a given matrix whose entries are subject to constraints defining a convex set. These problems arise in many engineering or statistical modeling applications and have recently received a lot of attention. Considering Hankel structures is relevant since it arises in many applications (e.g. for model reduction in linear dynamical systems described by Markov parameters, see [START_REF] Markovsky | Low rank approximation: algorithms, implementation, applications[END_REF]Section 1.3]).

Moreover, an algorithm for computing sample points in each connected component of H r ∩ R n can also be used to decide the emptiness of the feasibility set S = {x ∈ R n : H(x) 0}. Indeed, considering the minimum rank r attained in the boundary of S, it is easy to prove that one of the connected components of H r ∩ R n is actually contained in S. Note also that such feasibility sets, also called Hankel spectrahedra, have recently attracted some attention (see e.g. [START_REF] Blekherman | Extreme rays of the Hankel spectrahedra for ternary forms[END_REF]).

The intrinsic algebraic nature of our problem makes relevant the design of exact algorithms to achieve reliability. On the one hand, we aim at exploiting algorithmically the special Hankel structure to gain efficiency. On the other hand, the design of a special algorithm for the case of linear Hankel matrices can bring the foundations of a general approach to e.g. the symmmetric case which is important for semi-definite programming, i.e. solving linear matrix inequalities.

Related works and state-of-the-art

Our problem consists of computing sample points in real algebraic sets. The first algorithm for this problem is due to Tarski but its complexity was not elementary recursive [START_REF] Tarski | A decision method for elementary algebra and geometry[END_REF]. Next, Collins designed the Cylindrical Algebraic Decomposition algorithm [START_REF] Collins | Quantifier elimination for real closed fields by cylindrical algebraic decompostion[END_REF]. Its complexity is doubly exponential in the number of variables which is far from being optimal since the number of connected components of a real algebraic set defined by n-variate polynomial equations of degree ≤ d is upper bounded by O(d) n . Next, Grigoriev and Vorobjov [START_REF] Grigoriev | Solving systems of polynomial inequalities in subexponential time[END_REF] introduced the first algorithm based on critical point computations computing sample point in real algebraic sets within d O(n) arithmetic operations. This work has next been improved and generalized (see [START_REF] Basu | Algorithms in real algebraic geometry[END_REF] and references therein) from the complexity viewpoint. We may apply these algorithms to our problem by computing all (r + 1)-minors of the Hankel matrix and compute sample points in the real algebraic set defined by the vanishing of these minors. This is done in time ( m r+1 n+r r

) O (1) + r O(n) however since the constant in the exponent is rather high, these algorithms did not lead to efficient implementations in practice. Hence, another se-ries of works, still using the critical point method but aiming at designing algorithms that combine asymptotically optimal complexity and practical efficiency has been developed (see e.g. [1,[START_REF] El Din | Polar varieties and computation of one point in each connected component of a smooth real algebraic set[END_REF][START_REF] Greuet | Probabilistic algorithm for polynomial optimization over a real algebraic set[END_REF] and references therein).

Under regularity assumptions, these yield probabilistic algorithms running in time which is essentially O(d 3n ) in the smooth case and O(d 4n ) in the singular case (see [START_REF] Din | Finding sampling points on real hypersurfaces is easier in singular situations[END_REF]). Practically, these algorithms are implemented in the library RAGlib which uses Gröbner bases computations (see [START_REF] Faugère | Critical points and Gröbner bases: the unmixed case[END_REF][START_REF] Spaenlehauer | On the complexity of computing critical points with Gröbner bases[END_REF] about the complexity of computing critical points with Gröbner bases).

Observe that determinantal varieties such as H r are generically singular (see [START_REF] Bruns | Determinantal rings[END_REF]). Also the aforementioned algorithms do not exploit the structure of the problem. In [START_REF] Henrion | Real root finding for determinants of linear matrices[END_REF], we introduced an algorithm for computing real points at which a generic linear square matrix of size m has rank ≤ m -1, by exploiting the structure of the problem. However, because of the requested genericity of the input linear matrix, we cannot use it for linear Hankel matrices. Also, it does not allow to get sample points for a given, smaller rank deficiency.

Methodology and main results

Our main result is an algorithm that computes sample points in each connected component of H r ∩ R n under some genericity assumptions on the entries of the linear Hankel matrix H (these genericity assumptions are made explicit below). Our algorithm exploits the Hankel structure of the problem. Essentially, its complexity is quadratic in a multilinear Bézout bound on the number of complex solutions. Moreover, we find that, heuristically, this bound is less than m r+1 n+r r n+m r

. Hence, for subfamilies of the real root finding problem on linear Hankel matrices where the maximum rank allowed r is fixed, the complexity is essentially in (nm) O(r) .

The very basic idea is to study the algebraic set H r ⊂ C n as the Zariski closure of the projection of an incidence variety, lying in C n+r+1 . This variety encodes the fact that the kernel of H has dimension ≥ mr. This lifted variety turns out to be generically smooth and equidimensional and defined by quadratic polynomials with multilinear structure. When these regularity properties are satisfied, we prove that computing one point per connected component of the incidence variety is sufficient to solve the same problem for the variety H r ∩ R n . We also prove that these properties are generically satisfied. We remark that this method is similar to the one used in [START_REF] Henrion | Real root finding for determinants of linear matrices[END_REF], but in this case it takes strong advantage of the Hankel structure of the linear matrix, as detailed in Section 2. This also reflects on the complexity of the algorithm and on practical performances.

Let C be a connected component of H r ∩ R n , and and Π 1 , π 1 be the canonical projections Π 1 : (x 1 , . . . , x n , y 1 , . . . , y r+1 ) → x 1 and π 1 : (x 1 , . . . , x n ) → x 1 . We prove that in generic coordinates, either (i) π 1 (C) = R or (ii) there exists a critical point of the restriction of Π 1 to the considered incidence variety. Hence, after a generic linear change of variables, the algorithm consists of two main steps: (i) compute the critical points of the restriction of Π 1 to the incidence variety and (ii) instantiating the first variable x 1 to a generic value and perform a recursive call following a geometric pattern introduced in [START_REF] El Din | Polar varieties and computation of one point in each connected component of a smooth real algebraic set[END_REF]. This latter step (i) is actually performed by building the Lagrange system associated to the optimization problem whose solutions are the critical points of the restriction of π 1 to the incidence variety. Hence, we use the algorithm in [START_REF] Jeronimo | Deformation techniques for sparse systems[END_REF] to solve it. One also observes heuristically that these Lagrange systems are typically zero-dimensional. However, we were not able to prove this finiteness property, but we prove that it holds when we restrict the optimization step to the set of points x ∈ H r such that rank H(x) = p, for any 0 ≤ p ≤ r. However, this is sufficient to conclude that there are finitely many critical points of the restriction of π 1 to H r ∩ R n , and that the algorithm returns the output correctly. When the Lagrange system has dimension 0, the complexity of solving its equations is essentially quadratic in the number of its complex solutions. As previously announced, by the structure of these systems one can deduce multilinear Bézout bounds on the number of solutions that are polynomial in nm when r is fixed, and polynomial in n when m is fixed. This complexity result outperforms the state-of-the-art algorithms. We finally remark that the complexity gain is reflected also in the first implementation of the algorithm, which allows to solve instances of our problem that are out of reach of the general algorithms implemented in RAGlib.

Structure of the paper

The paper is structured as follows. Section 2 contains preliminaries about Hankel matrices and the basic notation of the paper; we also prove that our regularity assumptions are generic. In Section 3 we describe the algorithm and prove its correctness. This is done by using preliminary results proved in Sections 5 and 6. Section 4 contains the complexity analysis and bounds for the number of complex solutions of the output of the algorithm. Finally, Section 7 presents the results of our experiments on generic linear Hankel matrices, and comparisons with the state-of-the-art algorithms for the real root finding problem.

Notation and preliminaries

Basic notations We denote by GL(n, Q) (resp. GL(n, C)) the set of n × n non-singular matrices with rational (resp. complex) entries. For a matrix M ∈ C m×m and an integer p ≤ m, one denotes with minors (p, M) the list of determinants of p × p sub-matrices of M. We denote by M ′ the transpose matrix of M.

Let Q[x] be the ring of polynomials on n variables x = (x 1 , . . . , x n ) and let f = (f 1 , . . . , f p ) ∈ Q[x] p be a polynomial system. The common zero locus of the entries of f is denoted by Z(f ) ⊂ C n , and its dimension with dim Z(f ). The ideal generated by f is denoted by f , while if V ⊂ C n is any set, the ideal of polynomials vanishing on V is denoted by I(V), while the set of regular (resp. singular) points of V is denoted by reg V (resp. sing V).

If f = (f 1 , . . . , f p ) ⊂ Q[x],
we denote by D f = (∂f i /∂x j ) the Jacobian matrix of f . We denote by reg (f ) ⊂ Z(f ) the subset where D f has maximal rank.

A set E ⊂ C n is locally closed if E = Z ∩ O where Z is a Zariski closed set and O is a Zariski open set. Let V = Z(f ) ⊂ C n
be a smooth equidimensional algebraic set, of dimension d, and let g : C n → C p be an algebraic map. The set of critical points of the restriction of g to V is the solution set of f and of the (nd + p)-minors of the matrix D (f , g), and it is denoted by crit (g, V). Finally, if E ⊂ V is a locally closed subset of V, we denote by crit (g, E) = E ∩ crit (g, V). We define in the following the main algebraic sets appearing during the execution of our algorithm, given

Finally, for M ∈ GL(n, C) and f ∈ Q[x], we denote by f M (x) = f (M x), and if f = (f 1 , . . . , f p ) ⊂ Q[x] and V = Z(f ), by V M = Z(f M ) where f M = (f M 1 , . . . , f M p ).

Hankel structure

H ∈ C (2m-1)(n+1) , 0 ≤ p ≤ r, M ∈ GL(n, C) and u = (u 1 , . . . , u p+1 ) ∈ Q p+1 .
Incidence varieties. We consider the polynomial system

f (H M , u, p) : C n × C p+1 -→ C 2m-p-1 × C (x, y) -→ ( H(M x) y) ′ , u ′ y -1
where H has been defined in the previous section. We denote by J (H M , u, p) = Z(f p (H M , u)) ⊂ C n+p+1 and simply J = J (H M , u, p) and f = f (H M , u, p) when p, H, M and u are clear. We also denote by

K(H M , u, p) = J (H M , u, p) ∩ {(x, y) ∈ C n+p+1 : rank H(x) = p}.
Fibers. Let α ∈ Q. We denote by f α (H M , u, p) (or simply f α ) the polynomial system obtained by adding x 1α to f (H M , u, p). The resulting algebraic set Z(f α ), denoted by J α , equals J ∩ Z(x 1α).

Lagrange systems. Let v ∈ Q 2m-p . Let D 1 f denote the matrix of size c × (n + p) obtained by removing the first column of D f (the derivative w.r.t. x 1 ), and define ℓ = ℓ(H M , u, v, p) as the map ℓ :

C n+2m+1 → C n+2m+1 (x, y, z) → ( H(M x) y, u ′ y -1, z ′ D 1 f , v ′ z -1)
where z = (z 1 , . . . , z 2m-p ) stand for Lagrange multipliers. We finally define

Z(H M , u, v, p) = Z(ℓ(H M , u, v, p)) ⊂ C n+2m+1 .
Regularity property G We say that a polynomial system f ∈ Q[x] c satisfies Property G if the Jacobian matrix D f has maximal rank at any point of Z(f ). We remark that this implies that:

1. the ideal I(f ) is radical;

2. the set Z(f ) is either empty or smooth and equidimensional of co-dimension c.

We say that ℓ(H M , u, v, p) satisfies G over K(H M , u, p) if the following holds: for (x, y, z) ∈ Z(H M , u, v, p) such that (x, y) ∈ K(H M , u, p), the matrix D (ℓ(H M , u, v, p)) has maximal rank at (x, y, z).

Let u ∈ Q p+1 . We say that H ∈ C (2m-1)(n+1) satisfies Property G if f (H, u, p) satisfies Property G for all 0 ≤ p ≤ r.
The first result essentially shows that G holds for f (H M , u, p) (resp. f α (H M , u, p)) when the input parameter H (resp. α) is generic enough.

Proposition 1 Let M ∈ GL(n, C). (a) There exists a non-empty Zariski-open set

H ⊂ C (2m-1)(n+1) such that, if H ∈ H ∩ Q (2m-1)(n+1) , for all 0 ≤ p ≤ r and u ∈ Q p+1 -{0}, f (H M , u, p) satisfies Property G; (b) for H ∈ H , and 0 ≤ p ≤ r, if J (H M , u, p) = ∅ then dim H p ≤ n -2m + 2p + 1; (c) For 0 ≤ p ≤ r and u ∈ Q p+1 , if f (H M , u, p) satisfies G, there exists a non-empty Zariski open set A ⊂ C such that, if α ∈ A , the polynomial system f α satisfies G;
Proof : Without loss of generality, we can assume that M = I n . We let 0 ≤ p ≤ r, u ∈ Q p+1 -{0} and recall that we identify the space of linear Hankel matrices with C (2m-1)(n+1) . This space is endowed by the variables h k,ℓ with 1 ≤ k ≤ 2m -1 and 0 ≤ ℓ ≤ n; the generic linear Hankel matrix is then given by

H = H 0 + x 1 H 1 + • • • + x n H n with H i = Hankel(h 1,i , . . . , h 2m-1,i ).
We consider the map

q : C n+(p+1)+(2m-1)(n+1) -→ C 2m-p (x, y, H) -→ f (H, u, p)
and, for a given H ∈ C (2m-1)(n+1) , its section-map q H : C n+(p+1) → C 2m-p sending (x, y) to q(x, y, H). We also consider the map q which associates to (x, y, H) the entries of Hy and its section map qH ; we will consider these latter maps over the open set

O = {(x, y) ∈ C n+p+1 | y = 0}.
We prove below that 0 is a regular value for both q H and qH . Suppose first that q -1 (0) = ∅ (resp. q-1 (0)). We deduce that for all

H ∈ C (2m-1)(n+1) , q -1 H (0) = ∅ (resp q-1 H (0) = ∅)
and 0 is a regular value for both maps q H and qH . Note also that taking H = C (2m-1)(n+1) , we deduce that f (H, u, p) satisfies G. Now, suppose that q -1 (0) is not empty and let (x, y, H) ∈ q -1 (0). Consider the Jacobian matrix D q of the map q with respect to the variables x, y and the entries of H, evaluated at (x, y, H). We consider the submatrix of D q by selecting the column corresponding to:

• the partial derivatives with respect to h 1,0 , . . . , h 2m-1,0 ;

• the partial derivatives with respect to y 1 , . . . , y p+1 .

We obtain a (2mp) × (2m + p) submatrix of D q; we prove below that it has full rank 2mp. Indeed, remark that the 2mp -1 first lines correspond to the entries of Hy and last line corresponds to the derivatives of u ′ y -1. Hence, the structure of this submatrix is as below

         y 1 . . . y p+1 0 . . . 0 0 • • • 0 0 y 1 . . . y p+1 . . . 0 . . . . . . . . . . . . . . . . . . y 1 . . . y p+1 0 0 0 • • • • • • 0 u 1 • • • u p+1         
Since this matrix is evaluated at the solution set of u ′ y -1 = 0, we deduce straightforwardly that one entry of u and one entry of y are non-zero and that the above matrix is full rank and that 0 is a regular value of the map q.

We can do the same for D q except the fact that we do not consider the partial derivatives with respect to y 1 , . . . , y p+1 . The (2m-p -1) ×(2m-1) submatrix we obtain corresponds to the upper left block containing the entries of y. Since q is defined over the open set O in which y = 0, we also deduce that this submatrix has full rank 2mp -1.

By Thom's Weak Transversality Theorem one deduces that there exists a non-empty Zariski open set H p ⊂ C (2m-1)(n+1) such that if H ∈ H p , then 0 is a regular value of q H (resp. qH ). We deduce that for H ∈ H p , the polynomial system f (H, u, p) satisfies G and using the Jacobian criterion [START_REF] Eisenbud | Commutative algebra with a view toward algebraic geometry[END_REF]Theorem 16.19], J (H, u, p) is either empty or smooth equidimensional of dimension n -2m + 2p + 1. This proves assertion (a), with H = 0≤p≤r H p .

Similarly, we deduce that q-1 H (0) is either empty or smooth and equidimensional of dimension n -2m + 2p + 2. Let Π x be the canonical projection (x, y) → x; note that for any x ∈ H r , the dimension of Π -1

x (x) ∩ q-1 H (0) is ≥ 1 (by homogeneity of the y-variables). By the Theorem on the Dimension of Fibers [21, Sect.6.3,Theorem 7], we deduce that n -2m + 2p + 2 -dim(H p ) ≥ 1. We deduce that for H ∈ H , dim(H p ) ≤ n -2m + 2p + 1 which proves assertion (b).

It remains to prove assertion (c). We assume that f (H, u, p) satisfies G. Consider the restriction of the map Π 1 : C n+p+1 → C, Π 1 (x, y) = x 1 , to J (H, u, p), which is smooth and equidimensional by assertion (a). By Sard's Lemma [20, Section 4.2], the set of critical values of the restriction of Π 1 to J (H, u, p) is finite. Hence, its complement A ⊂ C is a non-empty Zariski open set. We deduce that for α ∈ A , the Jacobian matrix of f α (H, u, p) satisfies G.

Algorithm and correctness

In this section we present the algorithm, which is called LowRankHankel, and prove its correctness.

Description

Data representation The algorithm takes as input a couple (H, r), where H = (H 0 , H 1 , . . . , H n ) encodes m × m Hankel matrices with entries in Q, defining the linear matrix H(x), and 0 ≤ r ≤ m -1.

The output is represented by a rational parametrization, that is a polynomial system q = (q 0 (t), q 1 (t), . . . , q n (t),

q(t)) ⊂ Q[t]
of univariate polynomials, with gcd(q, q 0 ) = 1. The set of solutions of

x i -q i (t)/q 0 (t) = 0, i = 1 . . . n q(t) = 0
is clearly finite and expected to contain at least one point per connected component of the algebraic set H r ∩ R n .

Main subroutines and formal description

We start by describing the main subroutines we use.

ZeroDimSolve. It takes as input a polynomial system defining an algebraic set Z ⊂ C n+k and a subset of variables x = (x 1 , . . . , x n ). If Z is finite, it returns a rational parametrization of the projection of Z on the x-space else it returns an empty list.

ZeroDimSolveMaxRank. It takes as input a polynomial system f = (f 1 , . . . , f c ) such that

Z = {x ∈ C n+k | rank(D f (x)) = c} is finite and a subset of variables x = (x 1 , . . . , x n )
that endows C n . It returns fail: the assumptions are not satisfied if assumptions are not satisfied, else it returns a rational parametrization of the projection of Z on the x-space.

Lift. It takes as input a rational parametrization of a finite set Z ⊂ C N and a number α ∈ C, and it returns a rational parametrization of {(α, x) : x ∈ Z}.

Union. It takes as input two rational parametrizations encoding finite sets Z 1 , Z 2 and it returns a rational parametrization of Z 1 ∪ Z 2 .

ChangeVariables. It takes as input a rational parametrization of a finite set Z ⊂ C N and a non-singular matrix M ∈ GL(N, C). It returns a rational parametrization of Z M .

The algorithm LowRankHankel is recursive, and it assumes that its input H satisfies Property G.

LowRankHankel(H, r):

1. If n < 2m -2r -1 then return [ ]. 2. Choose randomly M ∈ GL(n, Q), α ∈ Q and u p ∈ Q p+1 , v p ∈ Q 2m-p for 0 ≤ p ≤ r. 3. If n = 2m -2r -1 then return ZeroDimSolve(f (H, u r , r), x)).

Correctness

The correctness proof is based on the two following results that are proved in Sections 5 and 6.

The first result states that when the input matrix H satisfies G and that, for a generic choice of M and v, and for all 0 ≤ p ≤ r, the set of solutions (x, y, z) to ℓ(H M , u, v, p) at which rank H(x) = p is finite and contains crit (π 1 , K(H M , u, p)).

Proposition 2 Let H be the set defined in Proposition 1 and let H ∈ H and u ∈ Q p+1 -{0} for 0 ≤ p ≤ r. There exist non-empty Zariski open sets M 1 ⊂ GL(n, C) and

V ⊂ C 2m-p such that if M ∈ M 1 ∩ Q n×n and v ∈ V ∩ Q 2m-p ,
∈ M 2 ∩ Q n×n , u ∈ U ∩ Q p+1 , the following holds: (a) for i = 1, . . . , d p , π i (C M ) is closed; (b) for any α ∈ R in the boundary of π 1 (C M ), π -1 1 (α) ∩ C M is finite; (c) for any x ∈ π -1 1 (α) ∩ C M and p such that rank Hp (x) = p, there exists (x, y) ∈ R n × R p+1 such that (x, y) ∈ J (H M , u, p).
Our algorithm is probabilistic and its correctness depends on the validity of the choices that are made at Step 2. We make this assumption that we formalize below.

We need to distinguish the choices of M, u and v that are made in the different calls of LowRankHankel; each of these parameter must lie in a non-empty Zariski open set defined in Propositions 1, 2 and 3.

We assume that the input matrix H satisfies G; we denote it by H (0) , where the super script indicates that no recursive call has been made on this input; similarly α (0) denotes the choice of α made at Step 2 on input H (0) . Next, we denote by H (i) the input of LowRankHankel at the i-th recursive call and by A (i) ⊂ C the non-empty Zariski open set defined in Proposition 1 applied to H (i) . Note that if α (i) ∈ A (i) , we can deduce that H (i+1) satisfies G.

Now, we denote by

M (i) 1 , M (i)
2 and U (p,i) , V (p,i) the open sets defined in Propositions 1, 2 and 3 applied to H (i) , for 0 ≤ p ≤ r and where i is the depth of the recursion.

Finally, we denote by M (i) ∈ GL(n, Q), u (i) p ∈ Q p+1 and v (i) p , for 0 ≤ p ≤ r, respectively the matrix and the vectors chosen at Step 2 of the i-th call of LowRankHankel.

Assumption A. We say that A is satisfied if M (i) , α (i) , u (i) p and v (i) p satisfy:

• M (i) ∈ (M (i) 1 ∩ M (i) 2 ) ∩ Q i×i ;
• α (i) ∈ A (i) .

• u (i)

p ∈ U (p,i) ∩ Q p+1 -{0}, for 0 ≤ p ≤ r; • v (i) p ∈ V (p,i) ∩ Q 2m-p -{0} for 0 ≤ p ≤ r;
Theorem 4 Let H satisfy G. Then, if A is satisfied, LowRankHankel with input (H, r), returns a rational parametrization that encodes a finite algebraic set in H r meeting each connected component of H r ∩ R n .

Proof : The proof is by decreasing induction on the depth of the recursion.

When n < 2m -2r -1, H r is empty since the input H satisfies G (since A is satisfied). In this case, the output defines the empty set.

When n = 2m-2r-1, since A is satisfied, by Proposition ??, either H r = ∅ or dim H r = 0. Suppose H r = ∅. Hence J r = ∅, since the projection of J r on the x-space is included in H r . Suppose now that dim H r = 0: Proposition 3 guarantees that the output of the algorithm defines a finite set containing H r . Now, we assume that n > 2m -2r -1; our induction assumption is that for any i ≥ 1 LowRankHankel(H (i) , r) returns a rational parametrization that encodes a finite set of points in the algebraic set defined by rank(H (i) ) ≤ r and that meets every connected component of its real trace.

Let C be a connected component of H r ∩ R n . To keep notations simple, we denote by M ∈ GL(n, Q), u p and v p the matrix and vectors chosen at Step 2 for 0 ≤ p ≤ r. Since A holds one can apply Proposition 3. We deduce that the image

π 1 (C M ) is closed. Then, either π 1 (C M ) = R or it is a closed interval. Suppose first that π 1 (C M ) = R. Then for α ∈ Q chosen at Step 2, π -1 1 (α) ∩ C M = 0. Remark that π -1 1 (α) ∩ C M is the union of some connected components of H (1) r ∩ R n-1 = {x = (x 2 , . . . , x n ) ∈ R n-1 : rank H (1) (x) ≤ r}.
Since A holds, assertion (c) of Proposition 1 implies that H (1) satisfies G. We deduce by the induction assumption that the parametrization returned by Step 6 where LowRankHankel is called recursively defines a finite set of points that is contained in H r and that meets C.

Suppose now that π 1 (C M ) = R. By Proposition 3, π 1 (C M ) is closed. Since C M is connected, π 1 (C M ) is a connected interval, and since π 1 (C M ) = R there exists β in the boundary of π 1 (C M ) such that π 1 (C M ) ⊂ [β, +∞) or π 1 (C M ) ⊂ (-∞, β].
Suppose without loss of generality that π 1 (C M ) ⊂ [β, +∞), so that β is the minimum value attained by π 1 on C M . Let x = (β, x 2 , . . . , x n ) ∈ C M , and suppose that rank( H(x)) = p. By Proposition 3 (assertion (c)), there exists y ∈ C p+1 such that (x, y) ∈ J (H, u, p). Note that since rank( H(x)) = p, we also deduce that (x, y) ∈ K(H, u, p).

We claim that there exists z ∈ C 2m-p such that (x, y, z) lies on reg (ℓ(H M , u, v, p)).

Since A holds, Proposition 2 implies that ℓ(H M , u, v, p) satisfies G over K(H M , u, p). Also, note that the Jacobian criterion implies that reg (ℓ(H M , u, v, p)) has dimension at most 0. We conclude that the point x ∈ C M lies on the finite set encoded by the rational parametrization P obtained at Step 5 of LowRankHankel and we are done.

It remains to prove our claim, i.e. there exists z ∈ C 2m-p such that (x, y, z) lies on reg (ℓ(H M , u, v, p)).

Let C ′ be the connected component of J (H, u, p) M ∩ R n+m(m-r) containing (x, y). We first prove that β = π 1 (x, y) lies on the boundary of π 1 (C ′ ). Indeed, suppose that there exists ( x, y) ∈ C ′ such that π 1 ( x, y) < β. Since C ′ is connected, there exists a continuous semi-algebraic map τ : [0, 1] → C ′ with τ (0) = (x, y) and τ (1) = ( x, y). Let ϕ : (x, y) → x be the canonical projection on the x-space.

Note that ϕ • τ is also continuous and semi-algebraic (it is the composition of continuous semi-algebraic maps), with (ϕ

• τ )(0) = x, (ϕ • τ )(1) = x. Since (ϕ • τ )(θ) ∈ H p for all θ ∈ [0, 1], then x ∈ C. Since π 1 ( x) = π 1 ( x,
y) < α we obtain a contradiction. So π 1 (x, y) lies on the boundary of π 1 (C ′ ).

By the Implicit Function Theorem, and the fact that f (H, u, p) satisfies Property G, one deduces that (x, y) is a critical point of the restriction of Π 1 : (x 1 , . . . , x n , y 1 , . . . , y r+1 ) → x 1 to J (H, u, p).

Since rank(H M (x)) = p by construction, we deduce that (x, y) is a critical point of the restriction of Π 1 to K(H M , u, p) and that, by Proposition 2, there exists z ∈ C 2m-p such that (x, y, z) belongs to the set reg (ℓ(H M , u, v, p)), as claimed.

Degree bounds and complexity

We first remark that the complexity of subroutines Union, Lift and ChangeVariables (see [START_REF] El Din | A nearly optimal algorithm for deciding connectivity queries in smooth and bounded real algebraic sets[END_REF]Chap. 10]) are negligible with respect to the complexity of ZeroDimSolveMaxRank. Hence, the complexity of LowRankHankel is at most n times the complexity of ZeroDimSolveMaxRank, which is computed below.

Let (H, r) be the input, and let 0 ≤ p ≤ r. We estimate the complexity of ZeroDimSolveMaxRank with input (H M , u p , v p ). It depends on the algorithm used to solve zero-dimensional polynomial systems. We choose the one of [START_REF] Jeronimo | Deformation techniques for sparse systems[END_REF] that can be seen as a symbolic homotopy taking into account the sparsity structure of the system to solve. More precisely, let p ⊂ Q[x 1 , . . . , x n ] and s ∈ Q[x 1 , . . . , x n ] such that the common complex solutions of polynomials in p at which s does not vanish is finite. The algorithm in [START_REF] Jeronimo | Deformation techniques for sparse systems[END_REF] builds a system q that has the same monomial structure as p has and defines a finite algebraic set. Next, the homotopy system t = tp + (1t)q where t is a new variable is built. The system t defines a 1-dimensional constructible set over the open set defined by s = 0 and for generic values of t. Abusing notation, we denote by Z(t) the curve defined as the Zariski closure of this constructible set.

Starting from the solutions of q which are encoded with a rational parametrization, the algorithm builds a rational parametrization for the solutions of p which do not cancel s. Following [START_REF] Jeronimo | Deformation techniques for sparse systems[END_REF], the algorithm runs in time O˜(Ln O (1) δδ ′ ) where L is the complexity of evaluating the input, δ is a bound on the number of isolated solutions of p and δ ′ is a bound on the degree of Z(t) defined by t.

Below, we estimate these degrees when the input is a Lagrange system as the ones we consider.

Degree bounds. We let (( H y) ′ , u p

′ y -1), with y = (y 1 , . . . , y p+1 ) ′ , defining J p (H, u p ). Since y = 0, one can eliminate w.l.o.g. y p+1 , and the linear form u p ′ y -1, obtaining a system f ∈ Q[x, y] 2m-p-1 . We recall that if x (1) , . . . , x (c) are c groups of variables, and f ∈ Q[x (1) , . . . , x (c) ], we say that the multidegree of f is (d 1 , . . . , d c ) if its degree with respect to the group x (j) is d j , for j = 1, . . . , c.

Let ℓ = ( f , g, h) be the corresponding Lagrange system, where (g, h) = (g 1 , . . . , gn-1 , h1 , . . . , hp ) = z ′ D 1 f with z = [1, z 2 , . . . , z 2m-p-1 ] a non-zero vector of Lagrange multipliers (we let z 1 = 1 w.l.o.g.). One obtains that ℓ is constituted by

• 2mp -1 polynomials of multidegree bounded by (1, 1, 0) with respect to (x, y, z),

• n -1 polynomials of multidegree bounded by (0, 1, 1) with respect to (x, y, z),

• p polynomials of multidegree bounded by (1, 0, 1) with respect to (x, y, z), that is by n + 2m -2 polynomials in n + 2m -2 variables.

Lemma 5 With the above notations, the number of isolated solutions of Z(ℓ) is at most

δ(m, n, p) = ℓ 2m -p -1 n -ℓ n -1 2m -2p -2 + ℓ p ℓ
where ℓ ∈ {max{0, n -2m + p + 1}, . . . , min{p, n -2m + 2p + 1}}.

Proof : By [START_REF] El Din | A nearly optimal algorithm for deciding connectivity queries in smooth and bounded real algebraic sets[END_REF]Proposition 11.1], this degree is bounded by the multilinear Bézout bound δ(m, n, p) which is the sum of the coefficients of

(s x + s y ) 2m-p-1 (s y + s z ) n-1 (s x + s z ) p ∈ Q[s x , s y , s z ] modulo I = s n+1 x , s p+1 y , s 2m-p-1 z
. The conclusion comes straightforwardly by technical computations.

With input ℓ, the homotopy system t is constituted by 2m-p-1, n-1 and p polynomials of multidegree respectively bounded by (1, 1, 0, 1), (0, 1, 1, 1) and (1, 0, 1, 1) with respect to (x, y, z, t). We prove the following.

Lemma 6 deg Z(t) ∈ O(pn(2mp)δ(m, n, p)).

Proof of Lemma 6:

We use Multilinear Bézout bounds as in the proof of Lemma 5. The degree of Z(t) is bounded by the sum of the coefficients of

(s x + s y + s t ) 2m-p-1 (s y + s z + s t ) n-1 (s x + s z + s t ) p modulo I = s n+1 x , s p+1 y , s 2m-p-1 z , s 2 t ⊂ Q[s x , s y , s z , s t ]
. Since the variable s t can appear up to power 1, the previous polynomial is congruent to P 1 + P 2 + P 3 + P 4 modulo I, with

P 1 = (s x + s y ) 2m-p-1 (s y + s z ) n-1 (s x + s y ) p P 2 = (2m -p -1)s t (s x + s y ) 2m-p-2 (s y + s z ) n-1 (s x + s z ) p , P 3 = (n -1)s t (s y + s z ) n-2 (s x + s y ) 2m-p-1 (s x + s z ) p P 4 = p s t (s x + s z ) p-1 (s x + s y ) 2m-p-1 (s y + s z ) n-1 .
We denote by ∆(P i ) the contribution of P i to the previous sum.

Firstly, observe that ∆(P 1 ) = δ(m, n, p) (compare with the proof of Lemma 5). Defining

χ 1 = max{0, n -2m + p + 1} and χ 2 = min{p, n -2m + 2p + 1}, one has ∆(P 1 ) = δ(m, n, p) = χ 2 ℓ=χ 1 γ(ℓ) with γ(ℓ) = 2m-p-1 n-ℓ n-1 2m-2p-2+ℓ p ℓ . Write now P 2 = (2m -p -1)s t P2 , with P2 ∈ Q[x, y, z]. Let ∆( P2 ) be the contribution of P2 , that is the sum of the coefficients of P2 modulo I ′ = s n+1 x , s p+1 y , s 2m-p-1 z , so that ∆(P 2 ) = (2m -p -1)∆( P2 ). Then ∆( P2 ) = i,j,ℓ 2m -p -2 i n -1 j p ℓ
where the sum runs in the set defined by the inequalities

i + ℓ ≤ n, 2m -p -2 -i + j ≤ p, n -1 -j + p -ℓ ≤ 2m -p -2.
Now, since P2 is homogeneous of degree n + 2m -3, only three possible cases hold:

Case (A). i + ℓ = n, 2m -p -2 -i + j = p and n -1 -j + p -ℓ = 2m -p -3. Here the contribution is δ a = α 2 ℓ=α 1 ϕ a (ℓ) with ϕ a (ℓ) = 2m -p -2 n -ℓ n -1 2m -2p -3 + ℓ p ℓ ,
and

α 1 = max{0, n -2m + p + 2}, α 2 = min{p, n -2m + 2p + 2}.
Suppose first that ℓ is an admissible index for ∆(P 1 ) and δ a , that is max{χ

1 , α 1 } = α 1 ≤ ℓ ≤ χ 2 = min{χ 2 , α 2 }.
Then:

ϕ a (ℓ) ≤ 2m -p -1 n -ℓ n -1 2m -2p -3 + ℓ p ℓ = = Ψ(ℓ)γ(ℓ) with Ψ(ℓ) = 2m -2p -2 + ℓ n -(2m -2p -2 + ℓ) .
The rational function ℓ -→ Ψ(ℓ) is piece-wise monotone (its first derivative is positive), and its unique possible pole is ℓ = n -2m + 2p + 2. Suppose that this value is a pole for Ψ(ℓ). This would imply α 2 = n -2m + 2p + 2 and so χ 2 = n -2m + 2p + 1; since ℓ is admissible for ∆(P 1 ), then one would conclude a contradiction. Hence the rational function Ψ(ℓ) has no poles, its maximum is atteined in χ 2 and its value is Ψ(χ 2 ) = n -1. Hence ϕ a (ℓ) ≤ (n -1)γ(ℓ). Now, we analyse any possible case:

(A1) χ 1 = 0, α 1 = 0. This implies χ 2 = n -2m + 2p + 1, α 2 = n -2m + 2p + 2. We deduce that δ a = χ 2 ℓ=0 ϕ a (ℓ) + ϕ a (α 2 ) ≤ (n -1) χ 2 ℓ=0 γ(ℓ)+ + ϕ a (α 2 ) ≤ (n -1)∆(P 1 ) + ϕ a (α 2 ).
In this case we deduce the bound δ a ≤ n∆(P 1 ).

(A2) χ 1 = 0, α 1 = n -2m + p + 2. This implies χ 2 = n -2m + 2p + 1, α 2 = p.
In this case all indices are admissible, and hence we deduce the bound δ a ≤ (n -1)∆(P 1 ).

(A3) χ 1 = n -2m + p + 1. This implies α 1 = n -2m + p + 2, χ 2 = p, α 2 = p. Also in this case all indices are admissible, and δ a ≤ (n -1)∆(P 1 ).

Case (B).

i + ℓ = n, 2m -p -2 -i + j = p -1 and n -1 -j + p -ℓ = 2m -p -2. Here the contribution is δ b = ℓ ϕ b (ℓ)
where

ϕ b (ℓ) = 2m -p -2 n -ℓ n -1 2m -2p -2 + ℓ p ℓ .
One gets δ b ≤ ∆(P 1 ) since the sum above is defined in max{0, n2m + p + 2} ≤ ℓ ≤ min{p, n -2m + 2p + 1}, and the inequality ϕ b (ℓ) ≤ γ(ℓ) holds term-wise.

Case (C) i + ℓ = n -1, 2m -p -2 -i + j = p and n -1 -j + p -ℓ = 2m -p -2.
Here the contribution is δ c = ℓ ϕ c (ℓ) where

ϕ c (ℓ) = 2m -p -2 n -1 -ℓ n -1 2m -2p -2 + ℓ p ℓ .
One gets δ c ≤ ∆(P 1 ) since the sum above is defined in max{0, n2m + p + 1} ≤ ℓ ≤ min{p, n -2m + 2p + 1}, and the inequality ϕ c (ℓ) ≤ γ(ℓ) holds term-wise. We conclude that δ a ≤ n∆(P 1 ), δ b ≤ ∆(P 1 ) and δ c ≤ ∆(P 1 ). Hence ∆(P

2 ) = (2m-p-1)(δ a +δ b +δ c ) ∈ O(n(2m -p)∆(P 1 )).
Analogously to ∆(P 2 ), one can conclude that ∆(P 3 ) ∈ O(n(n + 2mp)∆(P 1 )) and ∆(P 4 ) ∈ O(pn(n + 2mp)∆(P 1 )).

Estimates.

We provide the whole complexity of ZeroDimSolveMaxRank.

Theorem 7 Let δ = δ(m, n, p) be given by Lemma 5. Then ZeroDimSolveMaxRank with input ℓ(H M , u p , v p ) computes a rational parametrization within

O˜(p(n + 2m) O(1) (2m -p)δ 2 ),
arithmetic operations over Q.

Proof :

The polynomial entries of the system t (as defined in the previous section) are cubic polynomials in n + 2m -1 variables, so the cost of their evaluation is in O((n + 2m) 3 ). Applying [15, Theorem 5.2] and bounds given in Lemma 5 and 6 yield the claimed complexity estimate.

From Lemma 5, one deduces that for all 0 ≤ p ≤ r, the maximum number of complex solutions computed by ZeroDimSolveMaxRank is bounded above by δ(m, n, p). We deduce the following result. where δ(m, k, p) is the bound defined in Lemma 5.

Proof : The maximum number of complex solutions computed by ZeroDimSolve is the degree of J (H, u, r). Using, the multilinear Bézout bounds, this is bounded by the coefficient of the monomial s n x s r y in the expression (s x +s y ) 2m-r-1 , that is exactly 2m-r-1 r . The proof is now straightforward, since ZeroDimSolveMaxRank runs r + 1 times at each recursive step of LowRankHankel, and since the number of variables decreases from n to 2m -2r.

Proof of Proposition 2

We start with a local description of the algebraic sets defined by our Lagrange systems. This is obtained from a local description of the system defining J (H, u, p). Without loss of generality, we can assume that u = (0, . . . , 0, 1) in the section: such a situation can be retrieved from a linear change of the y-variables that leaves invariant the x-variables.

Local equations

Let (x, y) ∈ K(H, u, p). Then, by definition, there exists a p × p minor of H(x) that is non-zero. Without loss of generality, we assume that this minor is the determinant of the upper left p × p submatrix of H. Hence, consider the following block partition

H(x) = N Q P R (1)
with N ∈ Q[x] p×p , and

Q ∈ Q[x] p , P ∈ Q[x] (2m-2p-
y i -q i (x) = 0 1 ≤ i ≤ p qi (x) = 0 1 ≤ i ≤ 2m -2p -1 y p+1 -1 = 0. Proof : Let c = 2m -2p -1.
The proof follows by the equivalence

N Q P R y = 0 iff I p 0 -P I c N -1 0 0 I c N Q P R y = 0 in the local ring Q[x, y] det N , that is if and only if I p N -1 Q 0 R -P N -1 Q y = 0
Recall that we have assumed that u = (0, . . . , 0, 1); then the equation uy = 1 is y p+1 = 1.

Denoting by q i and qi respectively the entries of vectors -N -1 Q and -(R -P N -1 Q) ends the proof.

The above local system is denoted by f ∈ Q[x, y] 2m-p det N . The Jacobian matrix of this polynomial system is

D f = D x q ⋆ 0 I p+1
with q = (q 1 (x), . . . , q2m-2p-1 (x)). Its kernel defines the tangent space to K(H, u, p) ∩ O N . Let w = (w 1 , . . . , w n ) ∈ C n be a row vector; we denote by π w the projection π w (x, y) = w 1 x 1 + • • • + w n x n . Given a row vector v ∈ C 2m-p+1 , we denote by wlagrange( f , v) the following polynomial system

f , (g, h) = [z 1 , . . . , z 2m-p , z 2m-p+1 ] D f w 0 , v ′ z -1. (2)
For all 0 ≤ p ≤ r, this polynomial system contains n + 2m + 2 polynomials and n + 2m + 2 variables. We denote by L p ( f, v, w) the set of its solutions whose projection on the (x, y)space lies in O N .

Finally, we denote by wlagrange(f , v) the polynomial system obtained when replacing f above with f = f (H, u, p). Similarly, its solution set is denoted by L p (f , v, w). Proof : We start with Assertion (a). The statement to prove holds over K(H, u, p); hence it is enough to prove it on any open set at which one p × p minor of H is non-zero. Hence, we assume that the determinant of the upper left p × p submatrix N of H is non-zero; O N ⊂ C n+p+1 is the open set defined by det N = 0, and we reuse the notation introduced in this section. We prove that there exist non-empty Zariski open sets V ′ N ⊂ C 2m-p and W N ⊂ C n such that for v ∈ V ′ N and w ∈ W N , L p ( f , v, w) is finite and that the Jacobian matrix associated to wlagrange( f , v) has maximal rank at any point of L p ( f , v, w). The Lemma follows straightforwardly by defining V ′ (resp. W ) as the intersection of V ′ N (resp. W N ) where N varies in the set of p × p minors of H(x).

Intermediate result

Equations h yield z j = 0 for j = 2m -2p, . . . , 2mp, and can be eliminated together with their z variables from the Lagrange system wlagrange( f, v). It remains z-variables z 1 , . . . , z 2m-2p-1 , z 2m-p+1 ; we denote by Ω ⊂ C 2m-2p the Zariski open set where they don't vanish simultaneously. Now, consider the map

q : O N × Ω × C n -→ C n+2m-p (x, y, z, w) -→ ( f , g)
and, for w ∈ C n , its section map q w (x, y, z) = q(x, y, z, w). We consider ṽ ∈ C 2m-p and we denote by z the remaining z-variables, as above. Hence we define

Q : O N × Ω × C n × C 2m-2p -→ C n+2m-p+1 (x, y, z, w, ṽ) -→ ( f, g, ṽ′ z -1)
and its section map Q w,ṽ (x, y, z) = q(x, y, z, w, ṽ). We claim that 0 ∈ C n+2m-p (resp. 0 ∈ C n+2m-p+1 ) is a regular value for q (resp. Q). Hence we deduce, by Thom's Weak Transversality Theorem, that there exist non-empty Zariski open sets W N ⊂ C n and ṼN ⊂ C 2m-2p such that if w ∈ W N and ṽ ∈ ṼN , then 0 is a regular value for q w and Q w,ṽ .

We prove now this claim. Recall that since H ∈ H , the Jacobian matrix D x,y f has maximal rank at any point (x, y) ∈ Z( f ). Let (x, y, z, w) ∈ q -1 (0) (resp. (x, y, z, w, ṽ) ∈ Q -1 (0)). Hence (x, y) ∈ Z( f ). We isolate the square submatrix of D q(x, y, z, w) obtained by selecting all its rows and

• the columns corresponding to derivatives of x, y yielding a non-singular submatrix of D x,y f (x, y);

• the columns corresponding to the derivatives w.r.t. w 1 , . . . , w n , hence this yields a block of zeros when applied to the lines corresponding to f and the block I n when applied to g.

For the map Q, we consider the same blocks as above. Moreover, since (x, y, z, w, ṽ) ∈ Q -1 (0) verifies ṽ′ z -1 = 0, there exists ℓ such that z ℓ = 0. Hence, we add the derivative of the polynomial ṽ′ z -1 w.r.t. ṽℓ , which is z ℓ = 0. The claim is proved.

Note that q -1 w (0) is defined by n+2m-p polynomials involving n+2m-p+1 variables. We deduce that for w ∈ W N , q -1 w (0) is either empty or it is equidimensional and has dimension 1. Using the homogeneity in the z-variables and the Theorem on the Dimension of Fibers [21, Sect. 6.3, Theorem 7], we deduce that the projection on the (x, y)-space of q -1 w (0) has dimension ≤ 0. We also deduce that for w ∈ W N and ṽ ∈ ṼN , Q -1 w,ṽ (0) is either empty or finite.

Hence, the points of Q -1 v,w (0) are in bijection with those in L( f, v, w) forgetting their 0-coordinates corresponding to z j = 0. We define V ′ N = ṼN × C p ⊂ C 2m-2p . We deduce straightforwardly that for v ∈ V ′ N and w ∈ W N , the Jacobian matrix of wlagrange( f , v) has maximal rank at any point of L p ( f , v, w). By the Jacobian criterion, this also implies that the set L p ( f , v, w) is finite as requested.

We prove now Assertion (b).

Let W ⊂ C n and V ′ ⊂ C 2m-p be the non-empty Zariski open sets defined in the proof of Assertion (a). For w ∈ W and v ∈ V ′ , the projection of L p ( f, v, w) on the (x, y)-space is finite. Since H ∈ H , K(H, u, p) is smooth and equidimensional. where N runs over the set of p × p minors of H(x). We prove below that there exists a non-empty Zariski open set V ⊂ C 2m-p such that if v ∈ V , for all N and for w ∈ W , the set crit (π w , O N ∩ K(H, u, p)) is finite and contained in the projection of L p (f , v, w). This straightforwardly implies that the same holds for crit (π w , K(H, u, p)). Suppose w.l.o.g. that N is the upper left p × p minor of H(x). We use the notation f , g, h as above. Hence, the set crit (π w , O N ∩ K(H, u, p)) is the image by the projection π x,y over the (x, y)-space, of the constructible set defined by f , g, h and z = 0. We previously proved that, if w ∈ W N , q -1 (0) is either empty or equidimensional of dimension 1. Hence, the constructible set defined by f , g, h and z = 0, which is isomorphic to q -1 (0), is either empty or equidimensional of dimension 1.

Moreover, for any (x, y) ∈ crit (π w , O N ∩ K(H, u, p)), π -1 x,y (x, y) has dimension 1, by the homogeneity of polynomials w.r.t. variables z. By the Theorem on the Dimension of Fibers [21, Sect. 6.3, Theorem 7], we deduce that crit (π w , O N ∩ K(H, u, p)) is finite.

For (x, y) ∈ crit (π w , O N ∩K(H, u, p)), let V (x,y),N ⊂ C 2m-p be the non-empty Zariski open set such that if v ∈ V (x,y),N the hyperplane v ′ z -1 = 0 intersects transversely π -1

x,y (x, y). Recall that V ′ N ⊂ C 2m-p has been defined in the proof of Assertion (a). Define

V N = V ′ N ∩ (x,y)
V (x,y),N and V = N V N . This concludes the proof, since V is a finite intersection of non-empty Zariski open sets.

Conclusion

We denote by We conclude that the set of solutions of the system f (H, u, p), z ′ D f (H, u, p)

w 0 • • • 0 , v ′ z -1 (3)
is the image by the map (x, y) → M-1 (x, y) of the set S of solutions of the system f (H, u, p), z ′ D f (H, u, p)

e 1 0 • • • 0 , v ′ z -1 . ( 4
)
Now, let ϕ be the projection that eliminates the last coordinate z 2m-p+1 . Remark that ϕ(S) = L p (f M , v, e 1 ). Now, applying Lemma 10 ends the proof.

Proof of Proposition 3

The proof of Proposition 3 relies on results of [14, Section 5] and of [START_REF] El Din | Polar varieties and computation of one point in each connected component of a smooth real algebraic set[END_REF]. We use the same notation as in [14, Section 5], and we recall them below.

Notations For Z ⊂ C n of dimension d, we denote by Ω i (Z) its i-equidimensional component, i = 0, . . . , d. We denote by S (Z) the union of:

• Ω 0 (Z) ∪ • • • ∪ Ω d-1 (Z)
• the set sing (Ω d (Z)) of singular points of Ω d (Z).

Let π i be the map (x 1 , . . . , x ) → (x 1 , . . . , x i ). We denote by C (π i , Z) the Zariski closure of the union of the following sets:

• Ω 0 (Z) ∪ • • • ∪ Ω i-1 (Z);

• the union for r ≥ i of the sets crit (π i , reg (Ω r (Z))).

For M ∈ GL(n, C) and Z as above, we define the collection of algebraic sets {O i (Z M )} 0≤i≤d as follows:

• O d (Z M ) = Z M ; • O i (Z M ) = S (O i+1 (Z M )) ∪ C (π i+1 , O i+1 (Z M )) ∪ ∪ C (π i+1 , Z M ) for i = 0, . . . , d -1.
We finally recall the two following properties:

Property P(Z). Let Z ⊂ C n be an algebraic set of dimension d. We say that M ∈ GL(n, C) satisfies P(Z) when for all i = 0, 1, . . . , d:

4 .

 4 Let P = ZeroDimSolve(ℓ(f (H, u r , r), v)) 5. If P = [] then for p from 0 to r do (a) P ′ = ZeroDimSolveMaxRank(ℓ(H M , u p , v p ), x); (b) P = Union(P, P ′ ) 6. Q = Lift(LowRankHankel(Subs(x 1 = α, H M ), r), α); 7. return(ChangeVariables(Union(Q, P), M -1 )).

Proposition 8

 8 Let H be a m × m, nvariate linear Hankel matrix, and let r ≤ m -1. The maximum number of complex solutions computed by LowRankHankel with input (H, r) is 2mr -1 r + n k=2m-2r r p=0 δ(m, k, p).

Lemma 10

 10 Let H ⊂ C (2m-r)(n+1) be the non-empty Zariski open set defined by Proposition 1, H ∈ H and 0 ≤ p ≤ r. There exist non-empty Zariski open sets V ⊂ C 2m-p and W ⊂ C n such that if v ∈ V and w ∈ W , the following holds: (a) the set L p (f , v, w) = L(f , v, w) ∩ {(x, y, z) | rank H(x) = p} is finite and the Jacobian matrix of wlagrange(f , v) has maximal rank at any point of L p (f , v, w); (b) the projection of L p (f , v, w) in the (x, y)-space contains the critical points of the restriction of π w restricted to K(H, u, p).

  Since we work on K(H, u, p), one of the p × p minors of H(x) is non-zero. Hence, suppose to work in O N ∩ K(H, u, p) where O N ⊂ C n+p+1 has been defined in the proof of Assertion (a). Remark that crit (π w , K(H, u, p)) = N crit (π w , O N ∩ K(H, u, p))

M 1 ⊂

 1 GL(n, C) the set of non-singular matrices M such that the first row w of M -1 lies in the set W given in Lemma 10: this set is non-empty and Zariski open since the entries of M -1 are rational functions of the entries of M. Let V ⊂ C 2m-p be the non-empty Zariski open set given by Lemma 10 and let v ∈ V . Let e 1 be the row vector (1, 0, . . . , 0) ∈ Q n and for all M ∈ GL(n, C), Remark that for any M ∈ M 1 the following identity holds:D f (H M , u, p) e 1 0 • • • 0 = D f (H, u, p) w 0 • • • 0 M .

  Let H ∈ H , 0 ≤ p ≤ r and d p = n -2m + 2p + 1 and C be a connected component of H p ∩ R n . Then there exist non-empty Zariski open sets M 2 ⊂ GL(n, C) and U ⊂ C p+1 such that for any M

the following holds: (a) ℓ(H M , u, v, p) satisfies G over K(H M , u, p); (b) the projection of reg (ℓ(H M , u, v, p)) on the (x, y)-space contains crit (Π 1 , K(H M , u, p)) Proposition 3

  1)×p , and R ∈ Q[x] 2m-2p-1 . We are going to exhibit suitable local descriptions of K(H, u, p) over the Zariski open set O N ⊂ C n+p+1 defined by det N = 0; we denote by Q[x, y] det N the local ring of Q[x, y] localized by det N. Let N, Q, P, R be as above, and u ∈ Q p+1 -{0}. Then there exist{q i } 1≤i≤p ⊂ Q[x] det N and {q i } 1≤i≤2m-2p-1 ⊂ Q[x] det N such that the constructible set K(H, u, p) ∩ O N is defined by the equations

	Lemma 9

Proof : We start with assertion (a). Let M 2 ⊂ GL(n, C) be the non-empty Zariski open set of [START_REF] Henrion | Real root finding for determinants of linear matrices[END_REF]Proposition 17] for Z = H p : for M ∈ M 2 , M satisfies P(H p ). Remark that the connected components of H p ∩ R n and are in bijection with those of H M p ∩ R n (given by

Let π 1 be the projection on the first variable π 1 : R n → R, and consider its restriction to H M r ∩R n . Since M ∈ M 2 , by [START_REF] Henrion | Real root finding for determinants of linear matrices[END_REF]Proposition 16]

1 (α) ∩ C M , the linear system y → f (H M , u, p) has at least one solution. We deduce that there exists a non-empty Zariski open set U C,x ⊂ C p+1 such that if u ∈ U C,x ∩ Q p+1 , there exists y ∈ Q p+1 such that (x, y) ∈ J (H M , u, p). One concludes by taking

which is non-empty and Zariski open since:

• the collection {C ⊂ H p ∩ R n connected component} is finite;

It remains to prove the claim we made. For x ∈ π -1 1 (α) ∩ C M , the matrix H(x) is rank defective, and let p ′ ≤ p be its rank. The linear system

and the rank of the second matrix is p ′ + 1. Denoting by U C,x ⊂ C p+1 the complement in C p+1 of the p ′ -dimensional linear space spanned by the rows of H(x), proves the claim and concludes the proof.

Experiments

The algorithm LowRankHankel has been implemented under Maple. We use the FGb [START_REF] Faugère | FGb: a library for computing gröbner bases[END_REF] library implemented by J.-C. Faugère for solving solving zero-dimensional polynomial systems using Gröbner bases. In particular, we used the new implementation of [START_REF] Faugère | Fast algorithm for change of ordering of zero-dimensional Gröbner bases with sparse multiplication matrices[END_REF] for computing rational parametrizations. Our implementation checks the genericity assumptions on the input.

We test the algorithm with input m × m linear Hankel matrices

where the entries of H 0 , . . . , H n are random rational numbers, and an integer 0 ≤ r ≤ m -1. None of the implementations of Cylindrical Algebraic Decomposition solved our examples involving more that 3 variables. Also, on all our examples, we found that the Lagrange systems define finite algebraic sets.

We compare the practical behavior of LowRankHankel with the performance of the library RAGlib, implemented by the third author (see [START_REF] Din | Real Algebraic Geometry Library)[END_REF]). Its function PointsPerComponents, with input the of (r + 1)-minors of H(x), returns one point per connected component of the real counterpart of the algebraic set H r , that is it solves the problem presented in this paper. It also uses critical point methods. The symbol ∞ means that no result has been obtained after 24 hours. The symbol matbig means that the standard limitation in FGb to the size of matrices for Gröbner bases computations has been reached. We report on timings (given in seconds) of the two implementations in the next table.

The column New corresponds to timings of LowRankHankel. Both computations have been done on an Intel(R) Xeon(R) CPU E7540 @2.00GHz 256 Gb of RAM. We remark that RAGlib is competetitive for problems of small size (e.g. m = 3) but when the size increases LowRankHankel performs much better, especially when the determinantal variety has not co-dimension 1. It can tackle problems that are out reach of RAGlib.

Note that for fixed r, the algorithm seems to have a behaviour that is polynomial in nm (this is particularly visible when m is fixed, e.g. to 5).

Finally, we report in column TotalDeg the degree of the rational parametrization obtained as output of the algorithm, that is the number of its complex solutions. We observe that this value is definitely constant when m, r are fixed and n grows, as for the maximum degree (column MaxDeg) appearing during the recursive calls.

The same holds for the multilinear bound given in Section 4 for the total number of complex solutions.

(m, r, n) RAGlib New