Didier Henrion

Simone Naldi

Mohab Safey

El Din

Mohab Safey El Din

Real root finding for determinants of linear matrices

Keywords: Computer algebra, real algebraic geometry, determinantal varieties

Introduction 1.Problem statement

Let A 0 , A 1 , . . . , A n be given square matrices of size m with coefficients in the field of rationals Q. Consider the affine map defined as

x = (x 1 , . . . , x n ) → A(x) = A 0 + x 1 A 1 + • • • + x n A n .
Consistently with the technical literature, we use the terminology linear matrix to refer to A(x), even though the constant term A 0 is not necessarily zero. The determinant of A(x), denoted by det A(x), lies in the polynomial ring Q[x] and it has degree at most m. This polynomial defines the complex determinantal variety

D = x ∈ C n : det A(x) = 0 .
In other words, D ⊂ C n is the set of complex vectors x at which rankA(x) ≤ m -1. The goal of this paper is to provide a computer algebra algorithm with explicit complexity estimates for computing at least one point in each connected component of the real determinantal variety D ∩ R n .

Motivations

First notice that when n = 1 our problem is called the real algebraic eigenvalue problem [START_REF] Wilkinson | The algebraic eigenvalue problem[END_REF], and hence that the case n > 1 can be seen as a multivariate generalization.

Non-symmetric square matrices depending linearly on parameters arise in many problems of systems control and signal processing. For example, the Hurwitz matrix is used in stability criteria for systems described by linear ordinary differential equations, and vanishing of the determinant of the Hurwitz matrix corresponds to a bifurcation between stability and instability, see e.g. [START_REF] Barmish | New tools for robustness of linear systems[END_REF]. Alternatively, finding points on the real determinantal variety of the Hurwitz matrix amounts to finding parameters (e.g. corresponding to a feedback control law, or to structured uncertainty affecting the system) corresponding to a system configuration at the border of stability.

Another classical example of non-symmetric square linear matrix arising in signals and systems is the Sylvester matrix ruling controllability of a linear differential equation. In this context, vanishing of the determinant of the Sylvester matrix corresponds to a loss of controllability of the underlying system [START_REF] Kucera | Discrete linear control: the polynomial approach[END_REF].

Linear matrices and optimization on determinantal varieties arise also in statistics [START_REF] Draisma | Maximum likelihood duality for determinantal varieties[END_REF][START_REF] Hauenstein | Maximum likelihood for matrices with rank constraints[END_REF] and in computational algebraic geometry [START_REF] Draisma | The Euclidean distance degree of an algebraic variety[END_REF].

Under the assumption that the matrices A 0 , . . . , A n are symmetric, the matrix A(x) is symmetric, and hence it has only real eigenvalues for all x ∈ R n . The condition A(x) 0, meaning that A(x) is positive semidefinite, is called a linear matrix inequality, or LMI. It is a convex condition on the space of variables x which appears frequently in diverse problems of applied mathematics and especially in systems control theory, see e.g. [START_REF] Boyd | Linear matrix inequalities in system and control theory[END_REF]. A classical example is the Lyapunov stability condition for a linear ordinary differential equation which is an LMI in the parameters of a Lyapunov function (a certificate or proof of stability) depending quadratically on the system state.

When the matrix A(x) is symmetric, the set

S = x ∈ R n A(x) 0 (1)
is called a spectrahedron. Spectrahedra are affine sections of the cone of positive semidefinite matrices and they represent closed convex basic semialgebraic sets, i.e. convex sets that can be defined by the common nonnegativity locus of a finite set of polynomials; they are the object of active studies mainly in optimization theory, real algebraic geometry and Figure 1: A spectrahedron (red) with its real determinantal variety.

control theory [START_REF] Laurent | Sums of squares, moment matrices and optimization over polynomials[END_REF][START_REF] Lasserre | Moments, positive polynomials and their applications[END_REF][START_REF] Blekherman | Semidefinite optimization and convex algebraic geometry[END_REF]. Following a question posed in [39, Section 4.3.1], the authors of [START_REF] Helton | Sufficient and necessary conditions for semidefinite representability of convex hulls and sets[END_REF] conjectured that every convex semialgebraic set is the projection of a spectrahedron. On Figure 1 is represented a spectrahedron (for n = 3 and m = 5) together with its real determinantal variety.

The minimization of a given function, for example a polynomial, over real convex sets is a central problem in optimization theory. If the function is linear and the set is a spectrahedron, this is exactly the aim of semidefinite programming (SDP), see [START_REF] Ben-Tal | Lectures on modern convex optimization[END_REF]. If the input data of a semidefinite program are defined over Q, the solutions are algebraic numbers, and the authors in [START_REF] Nie | The algebraic degree of semidefinite programming[END_REF] investigated their algebraic degree: giving explicit formulas or bounds for this value is a measure of the complexity of the given program.

Convex LMIs and SDP are also widely used for solving nonconvex polynomial optimization problems. Indeed, these optimization problems are linearized in the space of moments of nonnegative measures (which is infinite-dimensional) and a suitable sequence of LMI relaxations, or truncations (the so-called Lasserre hierarchy), that can be solved via SDP, provides the solution to the original problem. The feasible set of every truncated problem is a spectrahedron in the space of moments, for more details see [START_REF] Laurent | Sums of squares, moment matrices and optimization over polynomials[END_REF][START_REF] Lasserre | Moments, positive polynomials and their applications[END_REF] and references therein.

So far, the problem of (deciding the existence and) computing such solutions has been addressed via several numerical methods, the most successful of which are primal-dual interior-point algorithms [START_REF] Ben-Tal | Lectures on modern convex optimization[END_REF] implemented in floating-point arithmetic in different SDP solvers [START_REF] Mittelmann | The state-of-the-art in conic optimization software[END_REF].

In this paper, the problem of computing points on spectrahedra is linked to polynomial systems solving over the reals. In fact, we are interested in the developement of an exact computer algebra algorithm to compute real points on hypersurfaces defined by the zero locus of determinants of affine matrix expressions. By exact algorithm we mean that we do not content ourselves with approximate floating-point computations. Our main motivation starts from the geometrical aspects of SDP as explained above: boundaries of spectrahedra are subsets of determinantal hypersurfaces, and so solving this problem efficiently is a necessary step to address the associated positivity problem A(x) 0, since the rank of the matrix A(x) at a point in the boundary of the spectrahedron S drops at least by one, while a point in the interior corresponds to a positive definite matrix.

Finding such a point is a certificate of strict feasibility.

State of the art

Modern computer algebra algorithms for solving our problem require at most m O(n) arithmetic operations in Q, see [START_REF] Basu | Algorithms in real algebraic geometry[END_REF]Ch.11,Par.6] and references therein. The core idea is to reduce the input problem to a polynomial optimization problem whose set of optimizers is expected to be finite and to meet every connected component of the solution set under study. Such a reduction must be done carefully, especially for unbounded sets or singular situations. So far, it is an open problem to get a competitive implementation of the algorithms in [START_REF] Basu | Algorithms in real algebraic geometry[END_REF]: unbounded and singular cases imply algebraic manipulations that have no impact on the complexity class but require to work over Puiseux series fields, and this increases the constant hidden by the big-O notation in the exponent.

During the past decade, tremendous efforts have been made to obtain algorithms that are essentially quadratic in m n and linear in the complexity of evaluation of the input polynomials when dealing with one n-variate polynomial equation of degree m, see e.g. [START_REF] Bank | Polar varieties and efficient real elimination[END_REF][START_REF] Bank | Polar varieties and efficient real equation solving: the hypersurface case[END_REF][START_REF] Bank | Generalized polar varieties: geometry and algorithms[END_REF][START_REF] Bank | Generalized polar varieties and efficient real elimination procedure[END_REF][START_REF] El Din | Polar varieties and computation of one point in each connected component of a smooth real algebraic set[END_REF]. The goal is to get an implementation that reflects the theoretical complexity gains. Most of these algorithms are probabilistic: some random choices independent of the input are performed to ensure genericity properties. Our contribution shares these features and it is inspired by some geometric ideas in [START_REF] El Din | Polar varieties and computation of one point in each connected component of a smooth real algebraic set[END_REF].

A main limitation is that the algorithms in [START_REF] El Din | Polar varieties and computation of one point in each connected component of a smooth real algebraic set[END_REF] are dedicated to the smooth case. In our case, it turns out that D is in general a singular variety -see e.g. [START_REF] Bruns | Determinantal rings[END_REF] and recall Figure 1 -which makes our problem more difficult from a geometric point of view.

Algorithms in [START_REF] Bank | Bipolar varieties and real solving of a singular polynomial equation[END_REF] deal with singular situations but do not return sample points in the connected components that are contained in the singular locus of the variety. As a consequence, one cannot use them to decide the emptiness of D ∩ R n . The algorithm in [START_REF] Din | Finding sampling points on real hypersurfaces is easier in singular situations[END_REF] may be used but it suffers from an extra-cost due to the introduction of an infinitesimal (see also [START_REF] Jeronimo | On sign conditions over real multivariate polynomials[END_REF]Section 6.2] for a similar approach).

Moreover, in [START_REF] Faugère | Computing loci of rank defects of linear matrices using Gröbner bases and applications to cryptology[END_REF][START_REF] Faugère | Critical points and Gröbner bases: the unmixed case[END_REF][START_REF] Faugère | On the complexity of the Generalized MinRank Problem[END_REF], the authors have developed algorithms and complexity estimates to isolate the real solutions of determinantal systems (see also [START_REF] Faugère | Gröbner bases of bihomogeneous ideals generated by polynomials of bidegree (1,1): algorithms and complexity[END_REF] for related works on a bilinear setting). Beyond the interest of solving our problem for the aforementioned applications, it is of interest to extend these works to the real and positive dimensional case.

In practice, one can observe that, when a determinantal equation is given as input to software implementing singly exponential algorithms [START_REF] Din | Raglib (real algebraic geometry library)[END_REF], its behaviour is significantly different and worse than the one observed on generic equations.

Basic definitions

Before describing the main results of this paper and the basic ideas on which they rely, we need to introduce some notations and basic definitions that are used further. We refer to [START_REF] Perrin | Algebraic geometry: an introduction[END_REF][START_REF] Shafarevich | Basic algebraic geometry 1[END_REF] for details.

We use the notations

Q * = Q \ {0} and C * = C \ {0}.
We also denote C m the set of complex vectors of length m and C m * = C m \ {0}. Given two vectors x, y ∈ C m , with x y we denote their scalar product x 1 y 1 + . . . + x m y m .

A subset V ⊂ C n is said to be an affine algebraic variety defined over Q if there exists a system (i.e. a finite set) of polynomials

f = (f 1 , . . . , f p ) ∈ Q[x] p such that V is the locus of their common complex solutions, i.e. V = {x ∈ C n : f (x) = 0} = {x ∈ C n : f 1 (x) = • • • = f p (x) = 0}.
In this case we write V = Z(f ) = f -1 (0). Algebraic varieties are the closed sets in the Zariski topology, hence any set defined by a polynomial inequation f = 0 defines an open set for the Zariski topology. We also consider the closure V of a set V ⊂ C n for the Zariski topology, that is the smallest algebraic subset of C n containing V.

The set of polynomials that vanish on an algebraic set V generates an ideal of Q[x] associated to V, denoted by I(V). This ideal is radical (i.e. f k ∈ I(V) for some integer k implies that f ∈ I(V)) and it is generated by a finite set of polynomials, say f = (f 1 , . . . , f p ), and we write

I(V) = f 1 , . . . , f p = f . Let V ⊂ C n be an affine algebraic variety. Then the quotient ring C[V] = C[x]/I(V) is the coordinate ring of the variety V: the elements of C[V] are called regular functions on V. A map f : V → W ⊂ C p defined over V with values in W, such that f ∈ C[V] p ,
is called a regular map, and if f is a bijection and its inverse is also a regular map, then f is an isomorphism of affine algebraic varieties.

Let GL(n, Q) denote the set of non-singular matrices of size n with coefficients in Q. Its identity matrix is denoted by Id n . Given a matrix M ∈ GL(n, Q) and a polynomial system

x ∈ C n → f (x) ∈ C p we denote by f •M the polynomial system x ∈ C n → f (M x) ∈ C p . If V = Z(f ), the image set Z(f • M ) = {x ∈ C n : f (M x) = 0} = {M -1 x ∈ C n : f (x) = 0} is denoted by M -1 V. Let ∂f ∂x k =    ∂f 1 ∂x k . . . ∂fp ∂x k   
denote the vector of Q[x] p containing partial derivatives of f w.r.t. variable x k , for some k = 1, . . . , n. The co-dimension c of V is the maximum rank of the Jacobian matrix

Df = ∂f ∂x k k=1,...,n =    ∂f 1 ∂x 1 . . . . . . ∂f 1 ∂xn . . . . . . ∂fp ∂x 1 . . . . . . ∂fp ∂xn    evaluated at x ∈ V. The dimension of V ⊂ C n is n -c.
Let V ⊂ C n be an algebraic set. We say that V is irreducible if it is not the union of two sets that are closed for the Zariski topology and strictly contained in V. Otherwise V is the union of finitely many irreducible algebraic sets, its irreducible components.

Most of the time, we will consider equidimensional algebraic sets: these are algebraic sets whose irreducible components share the same dimension. An algebraic set V of dimension d is the union of equidimensional sets of dimensions k = 0, 1, . . . , d: this is the so-called equidimensional decomposition of V. Suppose that V is d-equidimensional, that is, equidimensional of dimension d. Given a polynomial system f : C n → C p such that f is radical and equidimensional, and a point x ∈ V = Z(f ), we say that x is regular if Df (x) has rank n -d, and singular otherwise. Note that this definition does not depend on the generators of I(V). An algebraic set whose points are all regular is called smooth, and singular otherwise. The set of singular points of an algebraic set V is denoted by sing V, while the set of its regular points is denoted by reg V.

Given a polynomial system f : C n → C p defining a radical and equidimensional ideal, suppose that V = Z(f ) ⊂ C n is a smooth d-equidimensional algebraic set, and let g : C n → C m be a polynomial system. Then the set of critical points of the restriction of g to V is defined by the zero set of f and the minors of size n -d + m of the matrix

Df Dg

and we denote it by crit(g, f ). In particular, the critical points of the restriction to V of the projection map π i : (x 1 , . . . , x n ) → (x 1 , . . . , x i ) is the zero set of f and the minors of size n -d of the truncated Jacobian ∂f ∂x k k=i+1,...,n obtained by removing the first i columns in the Jacobian of f . The same definition applies to the equidimensional components of a generic algebraic set.

Data representation and genericity assumptions 1.5.1 Input

We assume that the linear matrix

A(x) = A 0 +x 1 A 1 +• • •+x n A n is
described via the square matrices A 0 , A 1 , . . . , A n of size m with coefficients in Q, which can also be understood as a point in Q (n+1)m 2 . To refer to this input we use the short-hand notation A.

Output

Our goal is to compute exactly sample points in each connected component of the real variety D ∩R n . Our algorithm consists of reducing the initial problem to isolating the real solutions of an algebraic set Z ⊂ C n of dimension at most 0. To this end, we compute a rational parametrization of Z that is given by a polynomial system q = (q 0 , q 1 , . . . , q n , q n+1 ) ∈ Q[t] n+2 such that q 0 , q n+1 are coprime (i.e. with constant greatest common divisor), Z is in one-to-one correspondence with the roots of q n+1 and

Z = x = q 1 (t) q 0 (t) , • • • , q n (t) q 0 (t) ∈ C n : q n+1 (t) = 0 .
This allows to reduce real root counting isolation to a univariate problem. Note also that the cardinality of Z is the degree of polynomial q n+1 , provided it is square-free; we denote it by deg q.

Note that since q 0 and q n+1 are co-prime, one can obtain a rational parametrization with q 0 = 1, but as observed in [START_REF] Alonso | Zeros, multiplicities, and idempotents for zero-dimensional systems[END_REF], choosing q 0 equal to the derivative of q n+1 leads, most of the time, to rational parametrizations to coefficients of smaller size in q 1 , . . . , q n . Given a polynomial system defining a finite algebraic set Z ⊂ C n , there exist many algorithms for computing such a parametrization of Z. In the experiments reported in Section 6, we use implementations of algorithms based on Gröbner bases [START_REF] Faugère | A new efficient algorithm for computing Gröbner bases (F4)[END_REF][START_REF] Faugère | A new efficient algorithm for computing Gröbner bases without reductions to zero (F5)[END_REF] and the so-called change of ordering algorithms [START_REF] Faugère | Efficient computation of zerodimensional Gröbner bases by change of ordering[END_REF][START_REF] Faugère | Polynomial systems solving by fast linear algebra[END_REF] because they have the current best practical behavior. Nevertheless, our complexity analyses are based on the geometric resolution algorithm given in [START_REF] Giusti | A Gröbner-free alternative for polynomial system solving[END_REF].

1.6 Genericity assumptions 1.6.1 Singular locus of the determinant Throughout the paper, we suppose that the singular locus of the algebraic set

D = {x ∈ C n : det A(x) = 0} is included in the set {x ∈ C n : rank A(x) ≤ m -2}, that is if x ∈ D is such that rank A(x) = m -1, then D x det A = 0 at
x. This property is generic in the space of input matrices C m 2 (n+1) . This fact can be proved easily via Bertini's theorem (see for example the proof of [10, Theorem 5.50]).

In the sequel, we say that A satisfies G 1 if the singular locus of det A is exactly the set of points at which the rank deficiency of this matrix is greater than 1.

Smoothness and equidimensionality

We define

f (A) : C n+m → C m (x, y) → A(x)y
as a polynomial system of size m in the variables x = (x 1 , . . . , x n ) and y = (y 1 , . . . , y m ). Given u = (u 1 , . . . , u m , u m+1 ) ∈ C m+1 with u m+1 = 0, define

f (A, u) : C n+m → C m+1 (x, y) → (A(x)y, u (y, -1))
where u (y, -1) = u 1 y 1 + • • • + u m y m -u m+1 denotes the inner product of vectors u and (y, -1) ∈ C m+1 , and let

V(A, u) = Z(f (A, u)) ⊂ C n+m .
In the sequel, we will assume that the system f (A, u) satisfies the following assumption G 2 .

Assumption G 2 . We say that a polynomial system f ∈ Q

[x] p satisfies G 2 if
• f is radical, and

• Z(f ) is either empty or smooth and equidimensional of co-dimension p.

We also say that a linear map A satisfies G 2 if the polynomial system f (A, u) satisfies G 2 for all u ∈ C m * . We will prove later that for a generic choice of A, this property holds. We say that A (or equivalently f (A, u)) satisfies G when A satisfies G 1 and f (A, u) satisfies G 2 .

Main results and organization of the paper

The main result of the paper is sketched in the following. Its detailed statement is in Proposition 5 and it will be proved in Section 2.3.

Let A 0 , A 1 , . . . , A n be square matrices of size m with coefficients in Q satsifying the above genericity assumptions. There exists a probabilistic exact algorithm with input A 0 , A 1 , . . . , A n and output a rational parametrization encoding a finite set of points with non-empty intersection with each connected component of D ∩ R n .

In case of success, the complexity of the algorithm is within

O˜ n 2 m 2 (n + m) 5 n + m n 6
arithmetic operations, where O˜(s) = O(s log k s) for some k ∈ N.

We also analyze the practical behaviour of a first implementation of this algorithm. Our experiments show that it outperforms the state-of-the-art implementations of general algorithms for grabbing sample points in real algebraic sets.

The paper is organized as follows.

Section 2 contains a detailed description of the algorithm and of its subroutines. Moreover, its formal description is provided. Section 2.2 contains all regularity results, that is Propositions 1, 2 and 3, proved in the following sections. It also contains the proof of correctness of the algorithm (Theorem 4). As already mentioned, the proof of the main result is given in Section 2.3. Section 3 contains the proof of Proposition 1. Section 4 contains the proof of Proposition 2. Section 5 contains the proof of Proposition 3. Finally, Section 6 contains numerical data of practical experiments and some examples.

2 Algorithm: correctness and complexity

Description of the algorithm

Our algorithm is guaranteed to return an output under some genericity assumptions on the input. If the genericity assumptions are not satisfied, the algorithm raises an error. The algorithm consists of computing critical points of the restriction of linear projections to a given algebraic variety after a randomly chosen linear change of variables. These points are the solutions of a Lagrange system to be defined in this section.

Notations

Before giving an overview of the algorithm, we need to introduce some notations that partly extend those introduced in Subsection 1.6.2.

Change of variables. We denote by A • M the affine map x → A(M x) obtained by applying a change of variables with matrix M ∈ GL(n, C). In particular A = A • Id n .

Incidence variety. Given a matrix M ∈ GL(n, C), define

f (A • M ) : C n+m → C m (x, y) → A(M x)y
as a polynomial system of size m in the variables x = (x 1 , . . . , x n ) and y = (y 1 , . . . , y m ). Given u = (u 1 , . . . , u m , u m+1 ) ∈ C m+1 with u m+1 = 0, define

f (A • M, u) : C n+m → C m+1 (x, y) → (A(M x)y, u (y, - 1))
where u (y, -1) = u 1 y 1 + • • • + u m y m -u m+1 denotes the inner product of vectors u and (y, -1) ∈ C m+1 , and let

V(A • M, u) = Z(f (A • M, u)) ⊂ C n+m .
We will see that under some genericity assumptions, the algebraic variety V = V(A • M, u) is equidimensional and smooth. Remark finally that, by definition, for all M ∈ GL(n, C), the projection of V(A • M, u) on the x-space is included in the determinantal hypersurface M -1 D.

Fibers. Given w ∈ C, define

f w (A • M, u) : C n+m → C m+2 (x, y) → (A(M x)y, u (y, -1), x 1 -w) and let V w (A • M, u) = Z(f w (A • M, u)) ⊂ C n+m .
We also define A w the matrix obtained by instantiating x 1 to w in A. The hypersurface defined by det A w = 0 is denoted by D w .

Lagrange system. Given v ∈ C m+1 , let J(x, y) = D 1 f (A • M, u)
denote the matrix of size m + 1 by n + m -1 obtained by removing the first column of the Jacobian matrix of f (A • M, u), and define

l(A • M, u, v) : C n+2m+1 → C n+2m+1 (x, y, z) → (A(M x)y, u (y, -1), J(x, y) z, v z -1)
where variables z = (z 1 , . . . , z m+1 ) stand for Lagrange multipliers, and let

Z(A • M, u, v) = Z(l(A • M, u, v)) ⊂ C n+2m+1 .

Formal description

The algorithm takes as input A which is assumed to satisfy G. Then, it chooses randomly

M ∈ GL(n, Q), v ∈ Q m+1 and w ∈ Q and computes a rational parametrization of Z(A • M, u, v) ⊂ C n+2m+1 .
Its projection on the (x, y)-space is expected to be the set of critical points of the restriction to V(A • M, u) of the projection on the x 1 -coordinate. Next, a recursive call is performed with input A•M where the x 1 -coordinate is instantiated to w. The new input should satisfy the same genericity properties as the one satisfied by A. Before giving a detailed description of the algorithm, we describe basic subroutines required by our algorithm.

Main subroutines. The algorithm uses the following subroutines:

• IsSing: it takes as input the polynomial system f (A • M, u) and it returns false if A • M satisfies G. It returns true otherwise;

• RatPar: it takes as input a polynomial system with coefficients in Q defining a finite set and it returns a rational parametrization of the set, as defined in Section 1.5.2.

It also uses the following subroutines that perform basic operations on rational parametrizations of finite sets:

• Image: it takes as input a rational parametrization of a finite set Z ⊂ C N and a matrix M ∈ GL(N, C) and it returns a rational parametrization of the image set M -1 Z corresponding to a change of variables;

• Union: it takes as input two rational parametrizations of finite sets Z 1 , Z 2 and returns a rational parametrization of Z 1 ∪ Z 2 ;

• Project: it takes as input a rational parametrization of a finite set Z and a subset of variables, and it computes a rational parametrization of the projection of Z on the linear subspace generated by these variables;

• Lift: it takes as input a rational parametrization of a finite set Z ⊂ C N and a number w ∈ C, and it returns a rational parametrization of

Z = {(x, w) : x ∈ Z} ⊂ C N +1 .
We can now describe more precisely our algorithm RealDet. It uses a recursive subroutine RealDetRec that takes as input A satisfying G, and returns a rational parametrization of a finite set which meets all connected components of D ∩ R n .

The main algorithm RealDet checks that the input satisfies G, in which case it calls Re-alDetRec. Using the Jacobian criterion [START_REF] Eisenbud | Commutative algebra with a view toward algebraic geometry[END_REF]Theorem 16.19], this check is easily done by verifying that the complex solution set to f (A, u) and the maximal minors of its Jacobian matrix is empty.

RealDet(A):

1. Choose randomly u ∈ Q m+1 ;

2. If IsSing(f (A, u)) = true then output an error message saying that the genericity assumptions are not satisfied;

else return RealDetRec(A).

RealDetRec(A):

1. If n = 1 then return (1, t, det A(t));
2. Choose randomly

• M ∈ GL(n, Q) • v ∈ Q m+1 • w ∈ Q; 3. P = Project(RatPar(l(A • M, u, v)), (x 1 , . . . , x n )); 4. Q = RealDetRec(Substitute(x 1 = w, A • M ))); 5. Q = Lift(Q, w);
6. return Image(Union(Q, P), M -1 ).

Proof of correctness

It is immediate that it is sufficient to prove the correctness of RealDetRec to obtain the correctness of RealDet. This algorithm takes as input an affine map A satisfying G.

The result below shows that Assumption G is generic in the sense that there a exists a non-empty Zariski open set of C m 2 (n+1) contained in the set of linear matrices satisfying G. It is also useful to ensure that recursive calls are valid, i.e. the inputs in recursive calls satisfy the genericity assumption. The proof is given in Section 3.

Proposition 1 Let u = (u 1 , . . . , u m+1 ) ∈ Q m+1 such that u m+1 = 0. Then: 1. There exists a non-empty Zariski open set A ⊂ C m 2 (n+1) such that for all A ∈ A , f (A, u) satisfies G. 2. If f (A, u) satisfies G then there exists a non-empty Zariski open set W ⊂ C such that for any w ∈ W f w (A, u) satisfies G.
Note that random choices are performed by algorithm RealDetRec at Step 2. These are needed to ensure some genericity properties. The first one ensures that set

Z(A • M, u, v) is finite; it is proved in Section 4.
Proposition 2 Assume that A ∈ A (see Section 1.6.1) and u = 0. Then there exist nonempty Zariski open sets M 1 ⊂ GL(n, C) and V ⊂ C m+1 such that for all M ∈ M 1 ∩Q m×m and v ∈ V ∩ Q m+1 , the following properties hold:

1. Z(A • M, u, v) is a finite set;
2. the Jacobian matrix Dl(A•M, u, v) has maximal rank at any point of Z(A•M, u, v);

3. the projection of Z(A • M, u, v) on the (x, y)-space contains the set of critical points of the restriction to V(A • M, u) of the projection on the x 1 -coordinate.

The proposition below states that, for M ∈ GL(n, Q) generically chosen, and for any connected component

C of D ∩ R n , π i (M -1 C) is closed for i = 1, . . . , n -1. This is proved in Section 5.
Proposition 3 Assume that A ∈ A . Then there exist two non-empty Zariski open sets

M 2 ⊂ GL(n, C) and U ⊂ C m such that for any M ∈ M 2 ∩ Q n×n , u ∈ (U ∩ Q m ) × Q * and any connected component C of D ∩ R n , the following holds: 1. for i = 1, . . . , n -1, π i (M -1 C
) is closed for the Euclidean topology;

2. for any w ∈ R lying on the boundary of

π 1 (M -1 C), π -1 1 (w) ∩ M -1 C is finite and there exists (x, y) ∈ R n × R m such that (x, y) ∈ V(A • M, u) and π 1 (x, y) = w.
Note that, starting with an n-variate affine map, there are n calls to RealDetRec, among which n -1 are recursive.

The random choices performed at Step 2 of every recursive call to RealDetRec can be organized in an array (M (1) , v (1) , w (1) ), . . . , (M (n-1) , v (n-1) , w (n-1) )

(

where the upperscripts indicate the depth of the recursion. There are n -1 choices of these data because when n = 1 the recursive subroutine directly returns a rational parametrization without making such a choice. To ensure the correctness of RealDetRec, we need to assume that these choices are random enough so that data (M (j) , v (j) , w (j) ) lie in some prescribed non-empty Zariski open set O (j) for j = 1, . . . , n -1 as suggested by the previous propositions. Because of the recursive calls, a priori the set O (j) depends on the previous choices. This is formalized by the following assumption.

Assumption H. We use the notations for sets introduced in Propositions 1, 2, 3, with the upperscript (j) to indicate the depth of recursion. We say that H holds if the array (2) satisfies the following conditions:

• A satisfies assumption G;

• M (j) ∈ M (j) 1 ∩ M (j) 2 ∩ Q n×n , for j = 1, . . . , n -1; • u ∈ (U (j) × Q * ) ∩ Q m+1 for j = 1, . . . , n -1; • v (j) ∈ V (j) ∩ Q m+1 , for j = 1, . . . , n -1; • w (j) ∈ W (j) ∩ Q, for j = 1, . . . , n -1.
We can now prove the following correctness statement.

Theorem 4 Assume that A ∈ A and that H holds. Then, RealDet(A) returns a rational parametrization encoding a finite set of points with non-empty intersection with each connected component of D ∩ R n .

Proof : Our reasoning is by induction on n, the number of variables. We start with the initialization. When n = 1, D ⊂ C is finite. Then a rational parametrization of D is the triple (1, t, detA(t)), which is the output result. Now, our induction assumption is that for any linear map

x → A(x) = A 0 + x 1 A 1 + • • • + x n-1 A n-1 that satisfies G, the algorithm
RealDetRec returns a correct answer provided that H holds. Now, let A be a linear map and let C be a connected component of D ∩ R n . We let M, v and w be respectively the matrix, vector and rational number chosen at Step 2 of RealDetRec, with input A.

First assume that the projection on the x 1 -coordinate of M -1 C is the whole x 1 -axis.

Since A satisfies G, we deduce that A • M satisfies G. Since H holds, we conclude by Proposition 1 that f w (A • M, u) generates a radical ideal and defines an algebraic variety which is either empty or smooth (n -2)-equidimensional. Moreover the singular locus of the determinant of the matrix A (n-1) obtained by instantiating x 1 to w in A•M , is exactly the set of points at which the rank deficiency is greater than 1. Hence f w satisfies G and by the induction hypothesis, RealDetRec returns one point per connected component of

D (n-1) ∩ R n-1 where D (n-1) = {x ∈ R n-1 : det A (n-1) (x) = 0}. The claim is proved in this case.
Now, assume that the projection π 1 on the x 1 -coordinate of M -1 C is not the whole x 1axis. Since H is satisfied, we deduce by Proposition 3 that π

1 (M -1 C) is closed for the Euclidean topology. Since π 1 (M -1 C) = R by assumption and since π 1 (M -1 C) is closed, there exists x = (x 1 , . . . , x n ) ∈ M -1 C such that w = x 1 lies in the boundary of π 1 (M -1 C).
Without loss of generality, we assume below that π

1 (M -1 C) is contained in [w, +∞[.
Recall that H holds. Then, by Proposition 3, π -1

1 (w) ∩ M -1 C is finite and for all x ∈ π -1 1 (w) ∩ M -1 C there exists y ∈ R m such that (x, y) ∈ V(A • M, u)
. Below, we reuse the notations of the algorithm and we prove that there exists z ∈ C m+1 such that (x, y, z) is a point lying in Z(A • M, u, v). Combined with Proposition 2, we also deduce that the above polynomial system defines a finite set which contains (x, y, z). Thus, the calls to RatPar and Project are valid and (x, y, z) lies in the finite set of points computed at Step 3 of RealDetRec. Correctness of the algorithm follows straightforwardly. Thus, it remains to prove that there exists z ∈ C m+1 such that (x, y, z) lies in Z(A • M, u, v). Let M -1 C be the connected component of V(A • M, u) ∩ R n+m which contains (x, y). We claim that w = π 1 (x, y) lies on the boundary of π 1 (M -1 C ). Indeed, assume by contradiction that this is not the case, i.e. w ∈ π 1 (M -1 C ) but does not lie in the boundary of π 1 (M -1 C ). This implies that there exists ε > 0 such that the interval (w -ε, w + ε) lies in π 1 (M -1 C ). As a consequence, there exists (x , y ) ∈ M -1 C such that that π 1 (x , y ) < w. Moreover, since (x , y ) ∈ M -1 C and M -1 C is connected, we deduce that there exists a continuous semi-algebraic function τ : [0, 1] → M -1 C with τ (0) = (x, y) and τ (1) = (x , y ). Let π x be the projection map π x (x, y) = x. Since π x and τ are continuous semi-algebraic functions, γ = π x • τ is continuous and semi-algebraic (since it is the composition of semi-algebraic continuous functions). Finally, note that γ(0) = x and γ(1) = x ; we deduce that x ∈ M -1 C with π 1 (x ) < w = π 1 (x). This contradicts the fact that w lies in the boundary of π 1 (M -1 C) and that π 1 (M -1 C) lies in [w, +∞[. We conclude that w = π 1 (x, y) lies on the boundary of

π 1 (M -1 C ).
As a consequence of the implicit function theorem [8, Section 3.5], and since A satisfies G, we deduce that (x, y) is a critical point of the restriction of the projection

π 1 to M -1 C . Since M -1 C is a connected component of V(A • M, u) ∩ R n
and since the input satisfies G 2 , we deduce that the truncated Jacobian matrix D 1 f (A • M, u) (defined jointly with the Lagrange system in paragraph 2.1.1) is rank defective at (x, y) (see [45, Sections 2.1.4 and 2.1.5]). Moreover, since H holds, we deduce by Proposition 2 that (x, y) lies in the projection of Z(A • M, u, v). Thus, there exists z ∈ C m+1 such that (x, y, z) lies in Z(A • M, u, v) as requested.

Complexity analysis and degree bounds

In this section, we estimate the complexity of the algorithm RealDet and we give an explicit formula for a bound on the number of complex solutions computed by the algorithm.

We assume that G holds, so that we do not need to estimate the complexity of the subroutine IsSing and we focus on the complexity of the algorithm RealDetRec.

We assume in the sequel that H holds. On input A satisfying G, RealDetRec computes a rational parametrization of the solutions set of l(A • M, u, v) (Step 3) and performs a recursive call with input Substitute(x 1 = w, A • M ) (Step 4). On input l(A • M, u, v), our routine for computing rational parametrization of its solution set starts by building an equivalent system.

The complexity results stated below depend on degrees of geometric objects defined by systems which are equivalent to the Lagrange systems we consider. We need to introduce some notations.

The sequence of linear matrices considered during the recursive calls is denoted by A (0) , . . . , A (n-1) , where A (i) is a linear matrix in n -i variables; the systems f (A (i) • M (i) , u (i) ) for 0 ≤ i ≤ n -1 are respectively denoted by

f i = (f i,1 , . . . , f i,m+1 )
where f i,m+1 : y → y u (i) -1. Note that the f i involve n + m -i variables. The Lagrange systems l(A (i) • M (i) , u (i) , v (i) ) are denoted by

l i = (f i , g i,1 , . . . , g i,n+m-i ) where g i,n+m-i : z → v (i) z n+m-i+1 -1.
Using f i,m+1 , one can eliminate one of the y-variables, say y m , in f i . We denote by fi = ( fi,1 , . . . , fi,m ) the polynomial system obtained this way. Recall that the polynomials g i,1 , . . . , g i,n+m-i express that there is a nonzero vector in the left kernel of the truncated Jacobian matrix D 1 f i . Hence, one can equivalently express the existence of a non-zero vector in the left kernel of the truncated Jacobian matrix D 1 fi . This yields a new polynomial system li = ( fi,1 , . . . , fi,m , gi,m+1 , . . . , gi,n-i-1 , gi,n-i , . . . , gi,n+2m-i-2 ).

Note that since we have assumed that H holds, one can deduce using Proposition 2 that the Jacobian matrix D li has maximal rank at any complex solution of li . This new polynomial system contains:

• m polynomials which are bilinear in (x 1 , . . . , x n ) and (y 1 , . . . , y m-1 );

• m -1 polynomials which are bilinear in (x 1 , . . . , x n ) and (z 1 , . . . , z m-1 );

• n -1 polynomials which are bilinear in (y 1 , . . . , y m-1 ) and (z 1 , . . . , z m-1 ).

In the sequel, we denote by V i,j the algebraic set defined by fi,1 , . . . , fi,j , when 1 ≤ j ≤ m and fi,1 , . . . , fi,m , gi,m+1 , . . . , gi,j when m + 1

≤ j ≤ n + 2m -i -2.
The algebraic set W i,j is the subset of V i,j at which the Jacobian matrix of its above defining system has maximal rank. For 0 ≤ i ≤ n -1, we denote by

δ i = max{degW i,j : 1 ≤ j ≤ n + 2m -i -2}
and by δ the maximum of the δ i . Remark that since H holds, Proposition 2 implies that

W i,n+2m-i-2 = Z( li ).
We start by estimating the complexity of the main subroutines called by RealDetRec. We prove the following result. Assume that A satisfies G and that M , u and v lies in the non-empty Zariski open sets defined in Propositions 2 and 3.

Lemma 6 Under the above notations and assumptions, there exists a probabilistic algorithm which, on input l i , computes a rational parametrization of the complex solution set of it within

O˜ n 2 m 2 (n + m) 5 δ 2 arithmetic operations in Q with δ ≤ n+m m 3 .
Proof of Proposition 5: Through its recursive calls, the algorithm RealDetRec computes rational parametrizations of the solution sets of the Lagrange systems l 0 , . . . , l n-1 .

Lemma 6 shows that these computations are done within

O˜ (n + m) 2 (nm 2 + (n + m) 3 )δ 2
arithmetic operations in Q with δ ≤ n+m m 3 . Since there are n Lagrange systems to solve, all these parametrizations are computed within

O˜ n 2 m 2 (n + m) 5 δ 2
arithmetic operations in Q. Note that in all systems l 0 , . . . , l n-1 the number of variables is bounded by n + 2m + 1 and the cardinality of their solution set is bounded by δ. Proof of Lemma 6: It is sufficient to describe the proof for l = l 0 only. We use the geometric resolution algorithm given in [START_REF] Giusti | A Gröbner-free alternative for polynomial system solving[END_REF] to compute a rational parametrization of the complex solution set of the system l obtained following the construction in Paragraph 2.3. Note that since H holds by assumption, we deduce that l is a reduced regular system, in the sense defined in the introduction of [START_REF] Giusti | A Gröbner-free alternative for polynomial system solving[END_REF].

Note that all polynomials of l have degree ≤ 2 and that evaluating l requires O˜(nm 2 ) arithmetic operations.

Thus, one can apply [28, Theorem 1]. When l is a reduced regular sequence, it states that one can compute a rational parametrization of the complex solution set of l in probabilistic time O˜(ñ 2 (õ + ñ3 )δ 2 )

where

• ñ = n + 2m -2 is the total number of variables involved in l,
• õ is the complexity of evaluating l,

• and δ is the quantity introduced in Paragraph 2. [START_REF] Bank | Polar varieties and efficient real elimination[END_REF].

We obtain that one can compute a rational parametrization of the complex solution set of l in probabilistic time

O˜((n + m) 2 (nm 2 + (n + m) 3 )δ 2 ).
Our conclusion follows and the bound on δ is proved in the following lemma.

Lemma 7 Under the above notations and assumptions the following inequality holds:

δ ≤ n + m m 3 .
Proof : To prove degree bounds on δ, we take into account the multi-linear structure in x, y, z of the intermediate systems fi,1 , . . . , fi,t , for 1 ≤ j ≤ t and fi,1 , . . . , fi,m , gi,m+1 , . . . , gi,m+t for 1

≤ t ≤ n + 2m -i -2.
We define ∆(m, n; t) as follows:

• when 1 ≤ t ≤ m, ∆(m, n; t) is the sum of the coefficients of the polynomial (s 1 + s 2 ) t modulo the ideal generated by (s n+1

1 , s m 2 ); • when m + 1 ≤ t ≤ n + m -1, ∆(m, n; t)
m i t-m j t ∈ {m + 1, . . . , n + m -1}, (i,j, )∈Ft m i n-1 j t-m-n+1 t ∈ {n + m, . . . , n + 2m -2}.
for every m and n, where:

F t =      (i, j) ∈ {1, . . . , m} × {0, . . . , n -1}, 1 ≤ i ≤ min(m, n), max(0, t -2m + 1) ≤ j ≤ min(t -m, i -1), if t ∈ {m + 1, . . . , n + m -1}, and
F t =      (i, j, ) ∈ {1, . . . , m} × {0, . . . , n -1} × {0, . . . , t -m -n + 1}, max(0, t -2m + 1) ≤ j + ≤ n -1, max(1, t -2m + 2) ≤ i + ≤ min(n, t -n + 1).
if t ∈ {n + m, . . . , n + 2m -2}. Let us remark that relations defining F n+2m-2 become linear contraints, which yields the following equality for the case t = n + 2m -2:

∆(m, n; n + 2m -2) = m-1 i=0 m n -i n -1 i m -1 i . (3)
One can easily check that for all

k ∈ N n + m n k = n i 1 ,...,i k =0 m i 1 n i 1 • • • m i k n i k .
Moreover, for all m, n and for t ∈ {1, . .

a i = j:(i,j)∈Ft t -m j = min(t-m,i-1) j=max(0,t-2m+1) t -m j ≤ n j=0 n i m j n j .
and so ∆(m, n; t) ≤ n+m n 2 for all t ∈ {m + 1, . . . , n + m -1}.

Finally, for t ∈ {n + m, . . . , n + 2m -2}, one gets ∆(m, n; t)

≤ n i,j, =0 m i n-1 j t-m-n+1 ≤ n i,j, =0 m i n j m ≤ n+m n 3 .

Complexity of Project.

According to [45, Lemma 9.1.6], given a rational parametrization q defining a zerodimensional set Z ⊂ C N , there exists a probabilistic algorithm computing a rational parametrization q of the projection π i (Z) whose complexity is within O ∼ (N deg q 2 ) operations. We remark here that deg q is the cardinality of Z provided that q is square-free; if not, it is an upper bound. In the case of Z(A • M, u, v), we obtain from Lemma 7 that deg q ≤ n+m n 3 .

Lemma 8

The complexity of Project in RealDetRec is

O ∼ (n + 2m -2) n + m n 6 .
Proof : It follows from the bound for δ of Lemma 7 and from [45, Lemma 9.1.6].

Complexity of Image, Union.

By [45, Lemma 9.1.1], given a rational parametrization q and a matrix M ∈ GL(N, Q), there exists an algorithm computing a rational parametrization q such that Z(q ) = M -1 Z(q) using O ∼ (N 2 δ + N 3 ) operations. Moreover, by [45, Lemma 9.1.3] if q 1 , q 2 are rational parametrizations with degree sum bounded by δ, a rational parametrization of Z(q 1 ) ∪ Z(q 2 ) can be computed in O ∼ (N δ 2 ) operations.

Lemma 9

The complexity of Image and Union in RealDetRec is

O ∼ (n + 2m -2) 2 n + m n 3 + (n + 2m -2) 3 + (n + 2m -2) n + m n 6 .
Proof : The proof of this fact follows straightforwardly from [45, Lemma 9.1.1], [45, Lemma 9.1.3] and Lemma 7.

A bound on the degree of the output

Let A be a n-variate linear matrix of size m and apply algorithm RealDet to A. Recall that the number ∆(m, n, n+2m-2) computed in ( 3) is a bound on the number of complex solutions computed by the first call of RealDetRec.

The following result, whose proof is straightforward, counts the maximum number of complex solutions computed by RealDet.

Lemma 10

The number of complex solutions computed by RealDet with input a linear matrix A satisfying Assumption G, is upper-bounded by the number

b(m, n) = n j=1 ∆(m, j, j + 2m -2) = n j=1 m-1 i=0 m j -i j -1 i m -1 i .
We remark the following facts:

• ∆(m, j, j + 2m -2) = 0 if j ≥ 2m; • if m = m 0 is fixed, n → b(m 0 , n) is constant if n ≥ 2m 0 .

Regularity properties of the incidence variety

The aim of this section is to prove Proposition 1. We start with G 1 .

Indeed, the genericity of G 1 is already established in the proof of [10, Theorem 5.50] using Bertini's theorem (see Subsection 1.6.1). We denote by A 1 ⊂ C m 2 (n+1) a non-empty Zariski open set such that for any A ∈ A , A satisfies G 1 .

Moreover, Sard's theorem implies that for a generic w, a point in D w is regular if and only if it is regular in D. We deduce that at any singular point of D w the rank deficiency of A w is greater than 1. We denote by W 1 a non-empty Zariski open set such that for any w ∈ W , A w satisfies G 1 .

We focus on G 2 which requires more technical proofs. To identify the linear map

x → A(x) = A 0 + x 1 A 1 + • • • + x n A n with a point in C m 2 (n+1)
, we denote by a l,i,j the entry of matrix A l at row i and column j, for l = 0, 1, . . . , n and i, j = 1, . . . , m.

Consider the polynomial map

p : C n+m × C m 2 (n+1) -→ C m+1 (x, y, A) -→ f (A, u)
and, for a given A ∈ C m 2 (n+1) , the induced map

p A : C n+m -→ C m+1 (x, y) -→ p(x, y, A).
Our proof consists of distinguishing whether Z(p) is empty or not. When Z(p) is not empty, we first prove that 0 is a regular value of p and using Thom's Algebraic Weak Transversality theorem [START_REF] El Din | A nearly optimal algorithm for deciding connectivity queries in smooth and bounded real algebraic sets[END_REF]Sect. 4.2], we deduce the existence of a non-empty Zariski open set with the requested properties.

Proof of the first point of Proposition 1: Assume first that Z(p) is empty. This is equivalent to saying that, for any A ∈ C m 2 (n+1) , V(A, u) = Z(f (A, u)) is empty. By the Nullstellensatz [START_REF] Cox | Ideals, varieties, and algorithms: an introduction to computational algebraic geometry and commutative algebra[END_REF]Chap. 8], this implies that for any A ∈ C m 2 (n+1) , the ideal I(V(A, u)) = f (A, u) = 1 is radical. We define A 2 = C (n+1)m 2 and conclude by taking

A = A 1 ∩ A 2 .
Assume that Z(p) is non-empty. We prove below that there exists a non-empty Zariski open set A 2 ⊂ C m 2 (n+1) such that for any A ∈ A 2 , the Jacobian matrix Df (A, u) has maximal rank at any point in Z(p A ). This is sufficient to establish the requested property G 2 since by the Jacobian criterion [START_REF] Eisenbud | Commutative algebra with a view toward algebraic geometry[END_REF]Theorem 16.19] this implies that

• the ideal f (A, u) is radical;
• the algebraic set V(A, u) is either empty or smooth and equidimensional of co-dimension m + 1 in C n+m .

To prove the existence of the aforementioned non-empty Zariski open set A 2 , we first need to prove that 0 is a regular value of p, i.e. at any point of the fiber Z(p) the Jacobian matrix Dp with respect to variables x, y and a ,i,j has maximal rank. Take (x, y, A) ∈ Z(p). It suffices to prove that there exists a maximal minor of Df (A, u) which is not zero at (x, y, A).

Remark that, since y is a solution of the equation u (y, -1) = 0 and u m+1 = 0, there exists 1 ≤ s ≤ m such that y s = 0. Moreover, since (u 1 , . . . , u m ) = 0 (otherwise V = ∅), there exists 1 ≤ ≤ m such that u = 0. Now consider the submatrix of Df (A, u) obtained by selecting

• the partial derivatives with respect to y where is as above;

• the partial derivatives with respect to a 0,r,s for all 1 ≤ r ≤ m and for s as above.

Checking that this submatrix has maximal rank at (x, y, A) is straightforward since

• the partial derivatives of the entries of A(x)y with respect to a 0,r,s for 1 ≤ r ≤ m is the diagonal matrix with y s = 0 on the diagonal;

• the partial derivative of the polynomial u (y, -1) with respect to y is u = 0, while the partial derivatives of that polynomial with respect to a 0,r,s are 0.

Thus, up to reordering the columns of this submatrix, it is triangular with non-zero entries on the diagonal. Finally, we conclude that 0 is a regular value of p. Proof of the second point of Proposition 1: Let A ∈ A and consider the map

π 1 : V(A, u) → C (x, y) → x 1 .
which is the restriction to V(A, u) of the projection on the first variable. Since A ∈ A , the variety V(A, u) is either empty or smooth and equidimensional and by Sard's Lemma ([45, Section 4.2]) the image by π 1 of the set of critical points of π 1 is contained in an algebraic hypersurface of C (that is, a finite set). This implies that there exists a non-empty Zariski open set W 2 ⊂ C such that if w 2 ∈ W , at least one of the following fact holds:

• the set π -1 1 (w) = {(x, y) ∈ V(A, u) | x 1 =
w} is empty: this fact implies that the system f w (A, u) defines the empty set, and that f w (A, u) = 1 , which is a radical ideal;

• for all (x, y) ∈ π -1 1 (w), (x, y) is not a critical point of π 1 ; this fact implies that the Jacobian matrix of f w (A, u) has full rank at each point (x, y) in the zero set of f w (A, u), and so by the Jacobian criterion [START_REF] Eisenbud | Commutative algebra with a view toward algebraic geometry[END_REF]Theorem 16.19] that f w (A, u) defines a radical ideal and its zero set is a smooth equidimensional algebraic set of codimension m + 2 in C n+m . By this, we conclude that if w ∈ W 2 , the system f w (A, u) satisfies G 2 as requested. We conclude by taking

W = W 1 ∩ W 2 .
Example 11 Consider the linear matrix

A(x) =   1 x 1 x 2 x 1 1 x 3 x 2 x 3 1  
whose real determinantal variety is the Cayley cubic surface with its four singular points (x 1 , x 2 , x 3 ) ∈ {(1, 1, 1), (1, -1, -1), (-1, 1, -1), (-1, -1, 1)}, see Example 2 and Figure 3 in [START_REF] Nie | The algebraic degree of semidefinite programming[END_REF]. When evaluated at these points, A has rank one. The following Macaulay2 code shows that the incidence variety is smooth.

A(x) =     1 + x 1 x 2 0 0 x 2 1 -x 1 x 2 0 0 x 2 2 + x 1 x 2 0 0 x 2 2 -x 1    
whose real determinantal variety is a smooth quartic curve, the union of two nested ovals, see Figure 2. Here the incidence variety is a smooth variety of dimension 6 and degree 10.

Dimension properties of Lagrange systems

The goal of this section is to prove Proposition 2. First we provide a local description of the incidence variety V(A • M, u) depending on the rank of the matrix A(x), which induces a local description of the Lagrange system Z(A • M, u, v). We actually use this local description to prove that, generically, the solutions (x, y, z) of the Lagrange system are such that the rank of A(x) is m-1. This property is used to exploit a local description of the solutions to the Lagrange system which make easier the proof of Proposition 2.

Then we give a proof of it in Section 4.2. Recall that the hypotheses of Proposition 2 includes the fact that A ∈ A , where these Zariski open sets have been defined respectively in Proposition 1 and Section 1.6.1.

In the sequel, for f ∈ Q[x], we denote by Q[x] f the localized polynomial ring.

Local description

Let A(x) = A 0 + x 1 A 1 + . . . + x n A n ∈ Q[x]
m×m be a linear matrix on (x 1 , . . . , x n ), and suppose that N = N (x) ∈ Q[x] r×r is the upper-left r × r submatrix of A: r) . Consider the equations Ay = 0 and u y -u m+1 = 0 defining the incidence variety. In the following lemma, local equations are derived for the incidence variety V, relying on the above block decomposition of A.

A = N Q P R with Q ∈ Q[x] r×(m-r) , P ∈ Q[x] (m-r)×r and R ∈ Q[x] (m-r)×(m-
Lemma 13 Let A, N, Q, P, R be as above, and u = 0. Then there exist

{q i,j } 1≤i≤r,1≤j≤m-r ⊂ Q[x] det N and {q i,j } 1≤i,j≤m-r ⊂ Q[x]
det N such that the constructible set V∩{(x, y) : det N = 0} is defined by the equations

y i -q i,1 (x)y r+1 -. . . -q i,m-r (x)y m = 0 i = 1, . . . , r q i,1 (x)y r+1 + . . . + q i,m-r (x)y m = 0 i = 1, . . . , m -r u y -u m+1 = 0.
Proof : Consider the polynomial equations Ay = 0 with y ∈ C m . Localizing at det N = 0, that is looking at these equations in the local ring Q[x, y] det N , similarly to the proof of [START_REF] El Din | A nearly optimal algorithm for deciding connectivity queries in smooth and bounded real algebraic sets[END_REF]Proposition 3.2.7], one has that Ay = 0 is equivalent to

0 = y N P Q R = y N P Q R N -1 0 0 Id m-r Id r -P 0 Id m-r which equals 0 = y Id r 0 Q N -1 R -Q N -1 P that is 0 = Id r N -1 Q 0 Sch(N ) y
where Sch(N ) = R -P N -1 Q is the Schur complement of N in A. Denoting with q i,j the entries of -N -1 Q and with q i,j the entries of -Sch(N ) ends the proof.

We let A be the matrix We deduce that modulo p 1 , . . . , p r one can express y 1 , . . . , y r as functions of x and y r+1 , . . . , y m . By this, the system defining V in the open set defined by det N = 0 can be re-written in the local ring Q

A = Id r N -1 Q 0 m-r,
[x, y] det N Sch(N ) • [y r+1 . . . y m ] = 0 q(u, y r+1 , . . . , y m ) = 0
where q is a linear form on y i , i = r + 1, . . . , m, parametrized by u, and whose coefficients belong to Q[x, y] det N , obtained by substituting in u y-1 = 0 the expressions for y 1 , . . . , y r . Since q is linear w.r.t. y r+1 , . . . , y m , one deduces that one can eliminate another variable among y r+1 , . . . , y m , say w.l.o.g. y r+1 = (x, y r+2 . . . y m ), in the localization of Q[x, y] det N to e(x) = 0, where e(x) ∈ Q[x, y] det N is the coefficient of y r+1 in the polynomial q. Finally, the system defining V, in the local ring Q[x, y] (det N )•e can be re-written as

Sch(N ) • [ (y r+2 . . . y m ), y r+2 , . . . , y m ] = 0.
We call F this new system. Consider the polynomial system

[z 1 . . . z m-r ] D x F = w (4)
with w = (w 1 , . . . , w n ) ∈ C n . Next, we prove that, up to genericity assumptions on the vector w defining the projection map π w : x → w 1 x 1 + • • • + w n x n , the projection of the solutions of the above system on the x-space is contained in the locus of maximal rank m -1 (hence, in the set of regular points of D). The proof is local and relies on the above block decomposition of A.

Lemma 14 Suppose that r ≤ m -2. There exists a non-empty Zariski open set W ⊂ C n such that if w ∈ W , the system (4) defines the empty set.

Proof : Let C ⊂ C n+2(m-r)-1 be the Zariski closure of the constructible set defined by (4), det N (x) = 0 and rank A(x) = r. Consider the projections π 1 : C → C n defined by π 1 (x, y, z, w) = x and π 2 : C → C n defined by π 2 (x, y, z, w) = w. The image π 1 (C) is dense in the set {x ∈ C n : rank A(x) ≤ r} and so has dimension ≤ n-(m-r) 2 when A is generic. The fiber of π 1 over a generic point x ∈ π 1 (C) is the graph of the functions w 1 , . . . , w n of (y, z), and so it has co-dimension n and dimension [n+(m-r)+m-r-1]-n = 2(m-r)-1.

By the Theorem of the Dimension of Fibers [46, Sect. 6.3, Theorem 7] one concludes that C has dimension less than or equal to n

-(m -r) 2 + 2(m -r) -1 = n -(m -r -1) 2 and since r ≤ m -2 this dimension is ≤ n -1. Therefore π 2 (C) ⊂ C n is a set whose Zariski closure has dimension ≤ n -1 and is contained in a hypersurface H ⊂ C n . Setting W = C n \ H ends the proof.
We recall in what follows the global definition of Lagrange system for the restriction of the projection π w : (x, y) → w x to the incidence variety

V(A, u) = V(A • Id n , u). The set V(A, u
) is defined by f (A, u) which consists in the entries of A(x)y and u y -u m+1 with u m+1 = 0. We suppose that A ∈ A . The associated Lagrange system consists in the polynomial entries of

f (A, u), (g, h) = [z 1 . . . z m+1 , z • ] D x f D y f w 1 . . . w n 0 , m+1 i=1 v i z i -1 (5)
where g = (g 1 , . . . , g n ) and h = (h 1 , . . . , h m ). We denote by W w (A, u, v) the zero set of [START_REF] Bank | Generalized polar varieties: geometry and algorithms[END_REF]. Over a solution of ( 5), z • = 0, since A ∈ A and f satisfies Assumption G 2 . The polynomial system (5) consists of n + 2m + 2 polynomials in n + 2m + 2 variables. We prove in the next lemma that, up to genericity assumption, system (5) defines a finite set and satisfies property G 2 , and that its solutions contain the critical points of π w restricted to V. This is done relying on the local description of V and on techniques similar to those used in the proof of Proposition 1.

Lemma 15 Let A ∈ A (see 1.6.1) and u = 0. There exist non-empty Zariski open sets W ⊂ C n and V ⊂ C m+1 such that, if w ∈ W and v ∈ V the following holds:

1. the Jacobian matrix of (5) has maximal rank at any point of W w (A, u, v) and W w (A, u, v) is finite;

2. the projection of W w (A, u, v) in the space of x, y contains the critical points of π w : (x, y) → w x restricted to V(A, u). Hence, let N be the (m -1) × (m -1) upper-left submatrix of A(x). By Lemma 13, the local equations of V r in Q[x, y] det N are of the form

Proof of

y i -q i (x)y m = 0, i = 1, . . . , m -1 Sch(N )y m = 0 u y -u m+1 = 0.
for some

q i ∈ Q[x, y] det N .
We prove by contradiction that y m = 0; hence assume that y m = 0. By the first m -1 equations one deduces that y = 0, which is a contradiction with u y -u m+1 = 0 and u m+1 = 0. Then one can suppose y m = 1. Moreover, since N has size m -1, its Schur complement is exactly Sch(N ) = det(A) • det(N -1 ) = det(A)/ det(N ), and so in the local ring Q[x, y] det N the equation Sch(N )y m = 0 is equivalent to det(A) = 0. So one obtains that the incidence variety V(A, u) has the following local description:

det(A) = 0 y i -q i (x) = 0, i = 1, . . . , m -1 y m -1 = 0.
We call f = (f 1 , . . . , f m+1 ) these local equations. The Jacobian of f reads

Df = [D x f D y f ] = D x det(A) 0 1×m Id m
and the local equations of the associated Lagrange system are

f = 0, (g, h) = [z 1 . . . z m+1 , z • ] D x f D y f w 0 , m+1 i=1 v 1 z i -1 = 0,
which is also a square system with n + 2m + 2 polynomials and variables. Now, consider the map p :

C n+2m+2 × C n × C m+1 -→ C n+2m+2 (x, y, z, w, v) -→ (f, g, h, v i z i -1).
and its section map

p v,w : C n+2m+2 -→ C n+2m+2 (x, y, z) -→ (f, g, h, v i z i -1). for given v ∈ C m+1 , w ∈ C n . Remark that p -1 v,w (0) = W w (A, u, v
) for all v, w. Now, there are two cases: either Z(p) = ∅ or Z(p) = ∅.

In the first case, this means in particular that for all v, w, W w (A, u, v) = ∅, which implies Assertion (1) with W = C n and V = C m+1 . Suppose now that Z(p) = ∅. We claim that 0 is a regular value for p. Indeed, by Thom's Algebraic Weak Transversality theorem [START_REF] El Din | A nearly optimal algorithm for deciding connectivity queries in smooth and bounded real algebraic sets[END_REF]Sect. 4.2] there exist non-empty Zariski open sets W ⊂ C n and V ⊂ C m+1 such that if v ∈ V and w ∈ W , zero is a regular value of the map p v,w . The regularity property of p v,w at 0 implies that the rank of ( 5) is maximal (and equal to n + 2m + 2) at each point of W w (A, u, v) and, by the Jacobian Criterion [START_REF] Eisenbud | Commutative algebra with a view toward algebraic geometry[END_REF]Theorem 16.19], that W w (A, u, v) is empty or finite, implying that Assertion (1) is true.

We prove that 0 is a regular value for p. Let (x, y, z, w, v) ∈ p -1 (0) and let Dp be the jacobian matrix of the map p at (x, y, z, w, v). Remark that:

• since rank A(x) = m -1 and A ∈ A , then x is a regular point of det(A) = 0;

• since A ∈ A then z • = 0;
• since z 1 , . . . , z m+1 verifies v i z i = 1 then there exists ∈ {1, . . . , m + 1} such that z = 0;

• polynomial entries of h have the form (h 1 , . . . , h m ) = (z 2 , . . . , z m+1 ).

We consider the submatrix of Dp made by the following independent square blocks:

• the derivative ∂ ∂x j det A which is non-zero at x;

• the derivatives of y i -q i (x), i = 1, . . . , m -1 and y m -1 with respect to y 1 , . . . , y m ;

• the derivatives of g w.r.t. w 1 , . . . , w n give a non-singular diagonal matrix z • Id n ;

• the derivatives of h w.r.t. z 2 , . . . , z m+1 give a non-singular diagonal matrix Id m ;

• the derivative of v i z i -1 with respect to v with as above is z = 0.

So one obtains that Dp has a non-singular maximal minor of size n + 2m + 2 and so it has full rank. By the genericity of the point (x, y, z, w, v) ∈ p -1 (0) one deduces the claimed property.

Proof of Assertion (2) of Lemma 15:

Suppose first that W w (A, u, v) = ∅ for all w ∈ C n , v ∈ C m+1 . Fix w ∈ C n , (x, y) ∈ V(A, u
) and suppose that (x, y) is a critical point of π w restricted to V(A, u). Then, since V(A, u) is equidimensional, there exists z = 0 such that (x, y, z) verifies the equations z Df = [w, 0]. Since z = 0, there exists v ∈ C m+1 such that v z = 1. So we conclude that (x, y, [z, 1]) ∈ W w (A, u, v), which is a contradiction.

Suppose now that A ∈ A , u = 0, Z(p) is non-empty and that w ∈ W . By [START_REF] El Din | A nearly optimal algorithm for deciding connectivity queries in smooth and bounded real algebraic sets[END_REF]Sect. 3.2], the set of critical points of π w restricted to V(A, u) is the projection π x,y on x, y of the constructible set:

S = {(x, y, z) : f = g = h = 0, z = 0}
where f, g, h have been defined in [START_REF] Bank | Generalized polar varieties: geometry and algorithms[END_REF]. One can easily prove with the same techniques as in the proof of Assertion (1) that S has dimension 1. Moreover, for each (x, y) in π x,y (S), the fiber π -1 x,y (x, y) has dimension 1 (because of the homogeneity of the z-variables). By the Theorem on the Dimension of Fibers [46, Sect. 6.3, Theorem 7], we deduce that π x,y (S) is finite. Fix now (x, y) ∈ π x,y (S) and let V (x,y) ⊂ C m+1 be the non-empty Zariski open set of v such that the hyperplane v z -1 = 0 intersects transversely π -1

x,y (x, y), and recall that V ⊂ C m+1 has been defined in the proof of Assertion [START_REF] Alonso | Zeros, multiplicities, and idempotents for zero-dimensional systems[END_REF]. By defining

V = V (x,y)∈πx,y(S)
V (x,y) one concludes the proof.

Proof of Proposition 2

We prove now Proposition 2. We use Lemma 15 to show that, up to a generic change of variables, the set of critical points is finite. Remark that for any M ∈ M 1 the following identity holds:

Df (A • M, u) e 1 0 • • • 0 = Df (A, u) • M w 0 • • • 0 M 0 0 Id m .
We conclude that the set of solutions of the system

f (A, u), z D x f D y f w 0 • • • 0 , m+1 i=1 v i z i -1 (6)
is the image by the map (x, y, z) → M -1 (x, y, z) of the set S of solutions of the system

f (A • M, u), z Df (A • M, u) e 1 0 • • • 0 , m+1 i=1 v i z i -1 . (7)
Now, let π be the projection that forgets the last coordinate of z, that is z • . Remark that π(S) = Z(A • M, u, v) and that π is a bijection. Moreover, it is an isomorphism of affine algebraic varieties, since if (x, y, z) ∈ S, then its z • -coordinate is obtained by evaluating a polynomial at (x, y, z 1 . . . z m+1 ).

Thus, Assertion (1) of Lemma 15 implies that S and π(S) = Z(A • M, u, v) are finite which proves Assertion (1) of Proposition 2.

Assertion (1) of Lemma 15 also implies that the Jacobian matrix associated to [START_REF] Barmish | New tools for robustness of linear systems[END_REF] has maximal rank at any point of S. Since we already observed that π(S) = Z(A • M, u, v) and that the map is an isomorphism, Assertion (2) follows.

Assertion (3) is a straightforward consequence of Assertion (2) of Lemma 15.

Closure properties of projection maps

The goal of this section is to prove Proposition 3. We start by introducing some notations.

Notations 16 For an algebraic set Z ⊂ C n of dimension d, we denote by Ω i (Z) the i-equidimensional component of Z, for i = 0, 1, . . . , d.

We denote by S (Z) the union of the following sets:

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

and 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))) of critical points of the restriction of π i to the regular locus of Ω r (Z).

Now, take M ∈ GL(n, C) and fix Z ⊂ C n algebraic set of dimension d. We define the collection of algebraic sets {O i (M -1 Z)} 0≤i≤d with

• O d (M -1 Z) = M -1 Z; • O i (M -1 Z) = S (O i+1 (M -1 Z)) ∪ C (π i+1 , O i+1 (M -1 Z)) ∪ C (π i+1 , M -1 Z) for i = 0, . . . , d -1.
The proof of Proposition 3 consists essentially in showing closedness properties of projections of the above geometric constructions in generic coordinates. This is proved using a relationship between closedness properties and Noether position properties. We start by stating the Noether position properties we are interested in.

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

1. O i (M -1 Z) has dimension ≤ i; 2. O i (M -1 Z
) is in Noether position with respect to X 1 , . . . , X i .

Note that Point (2) of P(Z) implies Point (1) (this is an immediate consequence of [START_REF] Shafarevich | Basic algebraic geometry 1[END_REF]Chap. 1.5.3]). The following result shows that Property P(Z) holds for a generic choice of the matrix M and it will be proved later on. Because of its length, the proof of the above result is postponed to the end of this section.

We express now the closedness properties we are interested in. and π -1 i (B r ) ∩ C = ∅ and B r ∩ {R i \ π i (C)} = ∅. Since B r is connected, B r meets also the boundary of π i+1 (C). Since Q i+1 holds, for every r > 0 there exists y r ∈ O i (Z)∩C such that π i+1 (y r ) ∈ B r , and so π i (y r ) ∈ B r . Thus, x lies in the closure of the image by π i of the set O i (Z) ∩ C. This image is closed and our claim follows.

2. Second, we prove that Q i holds. Let x ∈ R i be on the boundary of π i (C). From

(1), we deduce that there exists y ∈ O i (Z) ∩ C such that π i (y) = x. Suppose by contradiction that for all y as above, J(y

) = i. Fix y ∈ O i (Z) \ O i-1 (Z) such that π i (y) = x. In particular, y ∈ O i (Z) \ S (O i (Z)),
i ) ⊂ C (π i , O i ) ⊂ O i-1
, which is a contradiction since we assumed that J(y) = i.

We conclude that Q i holds, and so all statements Q 1 , . . . , Q d hold.

The following lemma is the last ingredient we need to prove Proposition 3. It shows that, if M satisfies P(Z), the fiber over a point lying on the boundary of the projection π 1 (M -1 C) is finite, and it can be obtained by computing the set O 0 (M -1 Z).

Lemma 19 Let Z ⊂ C n be an algebraic set. Let M ∈ GL(n, C) be such that M satisfies P(Z). Let M -1 C be a connected component of M -1 Z ∩ R n and w ∈ R be on the boundary of π

1 (M -1 C). Then π -1 1 (w) ∩ M -1 C is a non-empty finite set contained in O 0 (M -1 Z) ∩ M -1 C.
Proof of Lemma 19: By Proposition 18 we deduce that if w ∈ R belongs to the boundary of π 1 (C), there exists

x ∈ O 0 (M -1 Z) ∩ M -1 C such that π 1 (x) = w. So (O 0 (M -1 Z) ∩ M -1 C) ∩ (π -1 1 (w) ∩ M -1 C) = ∅. Now, we prove that π -1 1 (w) ∩ M -1 C ⊂ O 0 (M -1 Z) ∩ M -1 C. Since M satisfies P(Z), O 0 (M -1 Z) is finite and we also deduce that π -1 1 (w) ∩ M -1 C is finite.
We use again the definition of the function x → J(x) over Z used in the proof of Proposition 18. Suppose that there exists

x ∈ π -1 1 (w)∩M -1 C such that J(x) = j > 0; this implies that x ∈ O j (Z) \ O j-1 (Z). In particular, we deduce that x ∈ reg (Ω j (O j (Z))) ∩ M -1 C. Since w = π 1 (x) is on the boundary of π 1 (M -1 C), we conclude that π j (x) is on the bound- ary of π j (Ω j (O j (M -1 Z)) ∩ M -1 C). Moreover, since x ∈ reg Ω j (O j (M -1 Z)) ∩ M -1 C, we conclude by the Implicit Function Theorem that x is a critical point of the restriction of π j to O j (M -1 Z). So x ∈ crit (π j , O j (M -1 Z)) ⊂ C (π j , O j (M -1 Z)) ⊂ O j-1 (M -1 Z).
We conclude that contradiction J(x) ≤ j -1 which is a contradiction.

We are now able to prove Proposition 3.

Proof of Proposition 3: Let M 2 ⊂ GL(n, C) be the non-empty Zariski open set of matrices satisfying Property P(D) defined in Proposition 17, and let M ∈ M 2 . Let M -1 C be a connected component of M -1 D ∩ R n , and let 1 ≤ i ≤ n -1. Then, applying Proposition 18, we conclude that M -1 D satisfies Q i . In particular the boundary of π

i (M -1 C) is contained in π i (O i-1 (D M ) ∩ M -1 C) ⊂ π i (M -1 C) which implies that π i (M -1 C) is closed.

This proves Assertion (1).

We prove now Assertion [START_REF] Bank | Polar varieties and efficient real equation solving: the hypersurface case[END_REF]. Take w ∈ R that lies in the frontier of π 1 (M -1 C). By Lemma 19, π -1 1 (w) ∩ M -1 C is a finite set, and thus there exists x ∈ M -1 D ∩ R n such that x ∈ M -1 C and π 1 (x) = w. For all such x, the matrix A(x) is rank defective. Fix x ∈ π -1 1 (w) ∩ M -1 C and let r ≤ m -1 be the rank of A(x). Consider the linear system y → f (A, u) parametrized by the vector u. This system has at least one solution y if and only if

rank A(x) u 1 • • • u m = rank A(x) 0 u 1 • • • u m u m+1 .
Now, the second matrix has rank r + 1 since u m+1 = 0, and the first matrix has rank r + 1 if and only if (u 1 , . . . , u m ) does not lie in the space generated by the rows of A. So there exists a non-empty Zariski open set U C,x such that if (u 1 , . . . , u m ) ∈ U C,x the linear system has at least one solution.

We conclude the proof by taking

U = C⊂D∩R n x∈π -1 1 (w)∩M -1 C U C,x
which is non-empty and Zariski open because of the finiteness of π -1 1 (w) ∩ M -1 C and of the number of connected components of D ∩ R n .

The remainder of this Section is dedicated to the proof of Proposition 17. We start by introducing some notations.

Notations 20 Let B be an n-by-n matrix of indeterminates. For f

∈ Q[x 1 , . . . , x n ], let f • B ∈ Q(B)[x 1 , . . . , x n ] denote the polynomial such that (f • B)(x) = f (Bx)
, and if V ⊂ C n is defined by the ideal I = f 1 , . . . , f s , let B -1 V be the algebraic set defined by

I • B = f 1 • B, . . . , f s • B ⊂ Q(B)[x 1 , . . . , x n ].
For all i = 0, 1, . . . , d, we denote by I i , I i • M and I i • B the ideals associated to the algebraic sets O i (Z), O i (M -1 Z) and O i (B -1 Z), see Notations 16.

Lemma 21 Let Z ⊂ C n be an algebraic set of dimension d and 0 ≤ i ≤ d. Let P be one of the components of the prime decomposition of I • B i and let r = dim P. Then r ≤ i and the ring extension

Q(B)[x 1 . . . x r ] -→ Q(B)[x 1 . . . x n ] / P is integral.
This Lemma is a generalization of [START_REF] El Din | Polar varieties and computation of one point in each connected component of a smooth real algebraic set[END_REF]Prop.1] to the non-equidimensional case. Its proof shares similar techniques than those used for proving [START_REF] El Din | Polar varieties and computation of one point in each connected component of a smooth real algebraic set[END_REF]Prop.1]. It exploits the properties of the geometric objects defined in Notations 16 to retrieve an equidimensional situation. We sketch below the main differences and will refer to the proof of [START_REF] El Din | Polar varieties and computation of one point in each connected component of a smooth real algebraic set[END_REF]Prop. 1] for the steps that are identical.

Proof of Lemma 21: Our reasoning is by decreasing induction on the index i.

Suppose first that

i = d, so that I d • B = I(B -1 Z) (by definition O d (B -1 Z) = B -1 Z).
Let P be a prime ideal of the prime decomposition of I d • B, and let r = dim P. Thus, the algebraic set defined by P is an irreducible component of dimension r ≤ d and then Z(P) ⊂ Ω r (B -1 Z). By the Noether normalization lemma [START_REF] Logar | A computational proof of the Noether normalization lemma[END_REF], the statement follows.

Suppose now that the statement is true for i+1. To simplify notations we write O i instead of O i (B -1 Z). In particular, we assume that O i+1 has dimension ≤ i + 1. Consider the ideal I i • B; using the definitions of the geometric objects introduced in Notations 16 one obtains the following equalities:

I i • B = I(S (O i+1 )) ∩ I(C (π i+1 , O i+1 )) ∩ I(C (π i+1 , B -1 Z)).
Now, let P be a prime ideal associated to I i • B. Then, P is a prime ideal associated to one of the three ideals in the above intersection. We investigate below the three possible cases:

1. I(S (O i+1 )) ⊂ P. Let r = dim P. In this case, we obtain

P ⊃ I(Ω 0 (O i+1 )) ∩ • • • ∩ I(Ω i (O i+1 )) ∩ I(sing (Ω i+1 (O i+1 ))).
Combined with the fact that P is prime, this implies that • either I(Ω j (O i+1 )) ⊂ P, for some 0 ≤ j ≤ i ; then one gets r ≤ i and by the induction assumption that the extension

Q(B)[x 1 . . . x r ] -→ Q(B)[x 1 . . . x n ] / P is integral ; • or I(sing (Ω i+1 (O i+1 ))) ⊂ P.
Assume that I(sing (Ω i+1 (O i+1 ))) ⊂ P. We deduce that dim(P) ≤ dim(sing (Ω i+1 (O i+1 ))).

Since dim(Ω i+1 (O i+1 )) = i + 1 by definition, it follows that dim(sing (Ω i+1 (O i+1 ))) ≤ i and we deduce that dim(P) ≤ i. Let f •B = (f 1 •B, . . . , f s •B) be a set of generators of the ideal associated to Ω i+1 (O i+1 ). Then

I(sing (Ω i+1 (O i+1 ))) = f • B, g 1 , . . . , g N
where g 1 , . . . , g N are the minors of size (n -i -1) × (n -i -1) of the Jacobian matrix Df • B. We prove below by induction on t that for any prime Q associated to f • B, g 1 , . . . , g t , the extension

Q(B)[x 1 . . . x r ] -→ Q(B)[x 1 . . . x n ] / Q
is integral. Taking t = N will conclude the proof.

For t = 0, the induction assumption implies that for any prime

Q associated to f • B , the extension Q(B)[x 1 . . . x r ] -→ Q(B)[x 1 . . . x n ] / Q is integral.
Assume now that for any prime Q associated to f • B, g 1 , . . . , g t , the extension

Q(B)[x 1 . . . x r ] -→ Q(B)[x 1 . . . x n ] / Q is integral.

Practical experiments

In this section, we report on practical experiments done with a computer implementation of our algorithm.

We have implemented the algorithm RealDet under Maple. The computation of rational parametrizations is done using Gröbner bases, see [START_REF] Faugère | A new efficient algorithm for computing Gröbner bases (F4)[END_REF][START_REF] Faugère | A new efficient algorithm for computing Gröbner bases without reductions to zero (F5)[END_REF][START_REF] Faugère | Fast algorithm for change of ordering of zero-dimensional Gröbner bases with sparse multiplication matrices[END_REF][START_REF] Faugère | Sparse FGLM algorithms[END_REF][START_REF] Faugère | Polynomial systems solving by fast linear algebra[END_REF]. We use the Gröbner basis library FGb [START_REF] Faugère | FGb: a library for computing Gröbner bases[END_REF] implemented in C by J.-C. Faugère and its interface with Maple.

We mainly compare our implementation of RealDet with the Real Algebraic Geometry Library RAGlib [START_REF] Din | Raglib (real algebraic geometry library)[END_REF] implemented by the last author. RAGlib is also a Maple library implementing algorithms based on the critical point method. It also uses Gröbner bases and the library FGb for solving polynomial systems of dimension 0. We use its command PointsPerComponents to compute sample points in each connected component of the real counterpart of the hypersurface defined by the vanishing of the determinant of the matrix under consideration. We also made some tests using implementations of the Cylindrical Algebraic Decomposition but none of them succeeded to solve the examples we report on below.

The computations we report on have been performed on an Intel(R) Xeon(R) CPU E7540@2.00GHz 256 Gb of RAM. The symbol ∞ means that the computation did not end after 24 hours.

Simple example

We first illustrate the behavior of our algorithm on the simple planar determinantal quartic of Example 12. We would like to find at least one point (x 1 , x 2 ) ∈ R 2 in each connected component of the real variety defined by the equation det

    1 + x 1 x 2 0 0 x 2 1 -x 1 x 2 0 0 x 2 2 + x 1 x 2 0 0 x 2 2 -x 1     = x 4 1 + 3x 2 1 x 2 2 + x 4 2 -x 1 x 2 2 -5x 2 1 -7x 2 2 + 4 = 0.
With input the previous linear matrix, the algorithm checks that the associated incidence variety V verifies the regularity properties. This is done by computing a Gröbner basis of the ideal generated by the polynomials defining V and by the maximal minors of the Jacobian matrix, and verifying that this Gröbner basis is 1.

Then, the algorithm recursively computes rational parametrizations of the zero-dimensional Lagrange systems encoding critical points of the projection on the first variable, restricted to the incidence varieties (or its sections). To obtain this parametrization, we use the functions implemented in the Maple package fgbrs given in input a Gröbner basis of a zero-dimensional ideal, gives in output a rational parametrization of its solution set. Once a rational parametrization of the desired output is given, we isolate the real roots which are given by isolating intervals, each of one guaranteed to contain a point on the curve. To give an idea of the output, we reproduce here one of these points, together with its approximation to 10 certified digits: We conjectured that these bounds are not sharp; these experiments support this statement. In the column "degree" we report the sum of the degrees of the rational parametrizations computed by our algorithm for generic n-variate linear matrices of size m. We remark Table 3: Matrices with an affine constraint on the entries

x 1 ∈ [
In Table 3 we report on some numerical experiments. The two subtables contains the degree of the output of RealDet and the computational times respectively when b is the vector of all ones, and when the coordinates of b are random values in Q. We remark that the values of the degree are smaller than the corresponding values for the "dense" cases (m, n) = (2, 3), [START_REF] Bank | Polar varieties and efficient real elimination[END_REF][START_REF] Basu | Algorithms in real algebraic geometry[END_REF] and (4, 15) that are respectively 6, 39 and 284, as shown in Table 2. 4 we report on experimental data. We observe the same behavior as in the previous example.

Complexity

In Figures 6 and7, we consider two fundamental subclasses of the problem: when n = m 2 (non-symmetric case) and when n = m(m + 1)/2 (symmetric case). We estimate in both cases the order of complexity C(m, n) = n 2 m 2 (n + m) 5 m + n n

Proposition 5

 5 Assume that H holds. Then, RealDetRec outputs a rational parametrization whose real zero locus meets each connected component of D ∩ R n within O˜ n 2 m 2 (n + m) 5 δ 2 arithmetic operations in Q with δ ≤ n+m m 3 and O˜(s) = O(s • log k (s)) for some k ∈ N.

Following [ 45 ,

 45 Lemma 10.1.3], the call to the routine Project at Step 3 requires at most O˜((n + m)δ 2 ) arithmetic operations in Q. Next, by [45, Lemma 10.1.1 and Lemma 10.1.3], the calls to the routines Image and Union and in Step 6 require respectively at most O˜((n + m) 2 δ + (n + m) 3 ) and O˜((n + m)δ 2 ) arithmetic operations in Q. Summing up all these complexity estimates yields to the announced complexity bounds.

  MyRand = () -> (((-1)^(random(ZZ)))*(random(QQ))) R = QQ[x_1,x_2,x_3] A = matrix{{1,x_1,x_2},{x_1,1,x_3},{x_2,x_3,1}} D = ideal det A dim D, degree D SingD = ideal singularLocus D dim SingD, degree SingD S = QQ[x_1,x_2,x_3,y_1,y_2,y_3] Y = matrix{{y_1},{y_2},{y_3}} V = ideal(sub(A,S)*Y) + ideal(1-sum(3,i->MyRand()*(y_(i+1)))) dim V, degree V SingV = ideal singularLocus V dim SingV, degree SingVThe incidence variety in this example has dimension 2 and degree 7.

Figure 2 :

 2 Figure 2: The smooth quartic curve of Example 12 with its two nested ovals.

  r Sch(N ) and p = [p 1 . . . p m ] = A [y 1 . . . y m ] the new equations given by Lemma 13. One deduces [p 1 . . . p r ] = [y 1 . . . y r ] + (N -1 Q) • [y r+1 . . . y m ] [p r+1 . . . p m ] = Sch(N ) • [y r+1 . . . y m ] .

Assertion ( 1 )

 1 of Lemma 15: The Lagrange system (5) has a local description, as shown above, when we look at its equations in the local ring Q[x, y, z] det N where N is a given square submatrix of A(x). If W ⊂ C n is the non-empty Zariski open set given by Lemma 14, when w ∈ W then if (x, y, z) is a solution of (5), one deduces that the rank of A(x) is m -1. Without loss of generality, we can assume to work in the open set det N = 0 where N is the (m -1) × (m -1) upper-left submatrix of A(x) and work in the local ring Q[x, y, z] det N .

Proof of Proposition 2 :

 2 Let M 1 ⊂ GL(n, C) be the set of invertible matrices M such that the first row w of M -1 lies in the set W given in Lemma 15. This is a non-empty Zariski open set of GL(n, C) since the entries of M -1 are rational functions of the entries of M . Let V ⊂ C m+1 be the non-empty Zariski open set given by Lemma 15 and let v ∈ V . Let e 1 = (1, 0, . . . , 0) ∈ Q n and for all M ∈ GL(n, C),

Proposition 17

 17 Let Z ⊂ C n be an algebraic set of dimension d. There exists a nonempty Zariski open set M 2 ⊂ GL(n, C) such that for all M ∈ M 2 ∩ Q n×n , M satisfies P(Z).

Figure 3 :

 3 Figure 3: The determinantal quartic curve of Example 12 (black) and eight of its points (red) as returned by RealDet.

Figure 4 :Figure 5 :.

 45 Figure 4: Timings for m = 3 and n ≤ 20

.Table 4 :

 4 Matrix A(x) has size m with m(m + 1)/2 variables and it parametrizes all symmetric matrices. It is expressed as a linear combination of matrices of rank 1 or 2. b all ones m = 2 m = 3 m = Symmetric matrices with an affine constraint on the entries We add as above a linear relation b x = 1 where b ∈ Q m(m+1)/2 , and in Table

  is the sum of the coefficients of the polynomial (s 1 + s 2 )

					generated by
	(s n+1 1	, s m 2 , s m 3 ).
		  	min(n,t) i=0	t i	t ∈ {1, . . . , m},
		 

m (s 1 + s 3 ) t-m modulo the ideal generated by (s n+1 1 , s m 2 , s m 3 ); • when n + m ≤ t ≤ n + 2m -2, ∆(m, n; t) is the sum of the coefficients of the polynomial (s 1 + s 2 ) m (s 1 + s 3 ) n-1 (s 3 + s 2 ) t-m-n+1 modulo the ideal By [45, Proposition 10.1.1], the degrees of their components of highest dimension is bounded by ∆(m, n; t). Immediate computations show that the following holds: ∆(m, n; t) = (i,j)∈Ft

  and thus, we deduce thaty ∈ reg (Ω i (O i )). Next, since x ∈ π i (Ω i (O i ) ∩ C) and lies on the boundary of π i (C), we deduce that x lies on the boundary of π i (Ω i (O i ) ∩ C). Finally, by the Implicit Function Theorem, we deduce that y ∈ crit (π i , reg O

  Lemma 22 Let Z ⊂ C n be an algebraic set of dimension d. There exists a non-empty Zariski open set M 2 ⊂ GL(n, C) such that if M ∈ M 2 ∩ Q n×n , the following holds. Let i ∈ {0, 1, . . . , d} and P be a prime component of I i • M and let r = dim(P). Then r ≤ i and the ring extension C[x 1 . . . x r ] -→ C[x 1 . . . x n ] / P is integral. Proof of Proposition 17: Let M 2 ⊂ GL(n, C) be the non-empty Zariski open set defined in Lemma 22. By Lemma 22, for M ∈ M 2 and 0 ≤ i ≤ d, any irreducible component of the algebraic set O i (M -1 Z) is in Noether position with respect to x 1 , . . . , x i . This proves Point (2) of P(Z). Now, remark that [46, Chap. 1.5.3] implies that any irreducible component of O i (M -1 Z) has dimension ≤ i. This proves Point (1) of P(Z).

	Now we can prove Proposition 17.

Table 2 :

 2 122156404883928000480132795924333 256536504662931063109335249846272 , 355364086934036023530184499052519 746288013564890365408975272280064 ] ≈ 0.4761755254 x 2 ∈ [-10810534239 4294967296 , -345937095647 137438953472 ] ≈ -2.517023645 The eight points are represented on the curve on Figure 3. Degree of the output for the generic case

Property Q. Let Z be an algebraic set of dimension d and 1 ≤ i ≤ d. We say that Z satisfies Q i if for any connected component C of Z ∩ R n the boundary of π i (C) is contained in π i (O i-1 (Z) ∩ C). We say that Z satisfies Q if it satisfies Q 1 , . . . , Q d . When Z is explicit we just say that Q holds.

The following result states closedness properties properties of projections of the connected components of the real counterpart of an algebraic set when property P(Z) holds.

Proposition 18 Let Z ⊂ C n be an algebraic set of dimension d and M ∈ GL(n, C) ∩ Q n×n . If M satisfies P(Z), then M -1 Z satisfies Q.

The relationship between Noether position and closedness properties of connected components of real counterparts in algebraic sets and critical points is already exhibited and exploited in [START_REF] El Din | Polar varieties and computation of one point in each connected component of a smooth real algebraic set[END_REF]. Actually, Propositions 17 and 18 are already proved in [START_REF] El Din | Polar varieties and computation of one point in each connected component of a smooth real algebraic set[END_REF] under the assumption that Z is smooth and equidimensional. We cannot make this assumption in our context to prove Proposition 3 since D is generically singular. Thus, this Section can be seen as a strict generalization of [START_REF] El Din | Polar varieties and computation of one point in each connected component of a smooth real algebraic set[END_REF].

As in [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 notion of proper map. A map p : U ⊂ C n → C i is proper at y ∈ C i if and only if there exists a neighbourhood B of y such that p -1 (B) ∩ U is closed and bounded where B is the closure of B for the strong topology. We simply say that p is proper when it is proper at any point of C i .

Proof of Proposition 18:

To keep notations simple, we suppose that Id n satisfies P(Z). Our reasoning is by decreasing induction on the index i. In the whole proof we also define the following function on Z: we associate to y ∈ Z the value

We start by establishing that Q d holds. Let x ∈ R d be on the boundary of π d (C). By [32, Lemma 3.10], Property P(Z) implies that the map π d restricted to O d (Z) is proper, and so closed. We deduce that the restriction of

Suppose now that Q i+1 holds. We proceed in two steps:

1. First, we prove that the boundary of π i (C) is included in π i (O i (Z) ∩ C). Indeed, let x ∈ R i be on the boundary of π i (C). Let p : R i+1 → R i be the map sending (x 1 , . . . x i+1 ) to (x 1 , . . . x i ), so that π i = p • π i+1 . For r > 0, let B r be the ball of center x and radius r in R i and B r = p -1 (B r ). We claim that B r meets both π i+1 (C) and its complementary in R i+1 .

Indeed this is a consequence of the following immediate equalities

We prove below that for any prime Q associated to f •B, g 1 , . . . , g t+1 , the extension

Remark that any prime Q associated to f • B, g 1 , . . . , g t+1 is a prime associated to Q + g t+1 . Suppose that g t+1 / ∈ Q (otherwise, the conclusion follows immediately) and let r be the Krull dimension of Q . By Krull's Principal Ideal Theorem, Q + g t+1 is equidimensional of dimension r -1. Following mutatis mutandis the same argumentation as in the proof of [44, Prop. 1], the ideal Q + g t+1 contains a monic polynomial in x r , so that the extension

) and of the sets Ω j (B -1 Z) for 0 ≤ j ≤ i. When I(Ω j (B -1 Z)) ⊂ P, one can apply the induction assumption.

Thus, we focus on the case where I(crit (π i+1 , reg (Ω i+1 (O i+1 )))) ⊂ P.

)), that g 1 , . . . , g N are the square minors of size n-i-1 of the Jacobian matrix of f •B where the first i columns are eliminated, and that J is the ideal I(sing (Ω i+1 (O i+1 ))). The following equality is immediate:

where, if K, L are two ideals in the same ring R, then K :

We deduce that the ideal P is a prime component of f • B + g 1 , . . . , g N whose zero locus is not included in sing(Ω i+1 (O i+1 )). The integral ring extension property is already proved (by induction) for every component of the ideal f • B ; so we proceed as in the first point.

I(C

Again, recall that C (π i+1 , B -1 Z) is the union of Ω j (B -1 Z) for 0 ≤ j ≤ i and the union for r ≥ i of the sets crit (π i , reg (Ω r (Z))) of critical points of the restriction of π i to the regular locus of Ω r (B 1 Z).

Let r ≥ i + 1, and Ω r (Z) be the equidimensional component of Z of dimension r . So we can assume I(crit (π i+1 , reg (Ω r (B -1 Z)))) ⊂ P. The proof follows exactly the same argumentation as the one in the second point.

The following lemma plays the same role as the one in [START_REF] El Din | Polar varieties and computation of one point in each connected component of a smooth real algebraic set[END_REF]Prop. 2]. It shows that there exists the integral extension property in Lemma 21 is maintained when specializing B to a generic matrix M of GL(n, C). The proof of the lemma below is exactly the same as the one of [START_REF] El Din | Polar varieties and computation of one point in each connected component of a smooth real algebraic set[END_REF]Prop. 2].

of RealDet as computed in Proposition 5. We recall that standard complexity bounds for these classes of problems are in m O(n) . On Figure 6 we represent in logarithmic scale the ratio of C(m, n) with m 10 √ n (where the relation n = m 2 is fixed) as a function of the matrix size m. We remark that we obtain a bound which is strictly contained in m O( √ n) since this ratio tends to zero. This numerical test shows that our complexity bound, significantly improves the previous one. The same conclusion holds for the second case (Figure 7) where n = (m 2 + m)/2, which includes the fundamental family of symmetric linear matrices), where our complexity is compared with m 5n . We also remark that similar results -not reported here for conciseness -have been obtained by imposing a linear relation between m and n, for example n = 2m or n = 3m, and allowing m to vary.

To summarize, the complexity of RealDet given by Proposition 5 is such that:

• when m is fixed, the complexity n → C(m, n) is polynomial;

• when n = m 2 or n = (m 2 + m)/2 or n = αm, its asymptotic behavior when m grows is well-controlled and improves the state-of-the-art.