Jean-Pierre Dussault
email: jean-pierre.dussault@usherbrooke.ca

Jean Charles Gilbert

Baptiste Plaquevent-Jourdain
email: baptiste.plaquevent-jourdain@usherbrooke.ca

On the B-differential of the componentwise minimum of two affine vector functions -The full report *

Keywords: B-differential q Bipartition of a finite set q C-differential q Complementarity problem q Complexity q Componentwise AMS MSC 2020: 05A18, 05C40, 26A24, 26A27, 46N10, 47A50, 47A63, 49J52, 49N15, 52C35, 65Y20, 65K15, 90C33, 90C46

This paper focuses on the description and computation of the B-differential of the componentwise minimum of two affine vector functions. This issue arises in the reformulation of the linear complementarity problem with the Min C-function. The question has many equivalent formulations and we identify some of them in linear algebra, convex analysis and discrete geometry. These formulations are used to state some properties of the Bdifferential, like its symmetry, condition for its completeness, its connectivity, bounds on its cardinal, etc. The set to specify has a finite number of elements, which may grow exponentially with the range space dimension of the functions, so that its description is most often algorithmic. We present first an incremental-recursive approach avoiding to solve any optimization subproblem, which is based on the notion of matroid circuit and the related introduced concept of stem vector. Next, we propose modifications, adapted to the problem at stake, of an algorithm introduced by Rada and Černý in 2018 for determining the cells of an arrangement in the space of hyperplanes having a point in common. Measured in CPU time on the considered test-problems, the mean acceleration ratios of the proposed algorithms, with respect to the one of Rada and Černý, are in the range 7..15, and this speed-up can exceed 30, depending on the problem and the approach.

Introduction

Let E and F be two real vector spaces of finite dimension n := dim E and m := dim F. The B-differential at x ∈ E of a function H : E → F is the set denoted and defined by ∂ B H(x) := {J ∈ L(E, F) : H ′ (x k ) → J for a sequence {x k } ⊆ D H converging to x}, where L(E, F) is the set of linear (continuous) maps from E to F and D H is the set of points at which H is (Fréchet) differentiable (its derivative at x is denoted by H ′ (x), an element of L(E, F)). Recall that a locally Lipschitz continuous function is differentiable almost everywhere in the sense of the Lebesgue measure (Rademacher's theorem [START_REF] Evans | Measure Theory and Fine Properties of Functions[END_REF][START_REF] Federer | Geometric Measure Theory[END_REF][START_REF] Heinonen | Lectures on Lipschitz Analysis[END_REF][START_REF] Rademacher | Über partielle und totale differenzierbarkeit[END_REF]) and this property has the consequence that the B-differential of a locally Lipschitz function is nonempty everywhere [START_REF] Clarke | Optimization and Nonsmooth Analysis[END_REF]. The B-differential is an intermediate set used to define the Cdifferential (C for Clarke [START_REF] Clarke | Optimization and Nonsmooth Analysis[END_REF]) of H at x, which is denoted and defined by

∂ C H(x) := co ∂ B H(x), (1.1)
where co S denotes the convex hull of a set S [START_REF] Borwein | Convex Analysis and Nonlinear Optimization -Theory and Examples[END_REF][START_REF] Hiriart-Urruty | Fundamentals of Convex Analysis[END_REF][START_REF] Rockafellar | Convex Analysis[END_REF]. Both intervene in the specification of conditions ensuring the local convergence of the semismooth Newton algorithm [START_REF] Qi | Convergence analysis of some algorithms for solving nonsmooth equations[END_REF][START_REF] Qi | A nonsmooth version of Newton's method[END_REF][START_REF] Marek | On a new exponential iterative method for solving nonsmooth equations[END_REF], which can be a motivation for being interested in that concept.

In this paper, we focus on the description of the B-differential of H at x when H : R n → R m is the componentwise minimum of two affine functions x → Ax + a and x → Bx + b, where A, B ∈ R m×n and a, b ∈ R m . Hence, H is defined at x by

H(x) = min(Ax + a, Bx + b), (1.2)
where the minimum operator "min" acts componentwise (for two vectors u, v ∈ R m and i ∈ [1 : m] := {1, . . . , m}: [min(u, v)] i := min(u i , v i )). A motivation to look at the B-differential of that function H comes from the fact that, when m = n and H is given by (1.2), as explained below, the equation

H(x) = 0 (1.3)
is a reformulation of the balanced [START_REF] Dussault | Exact computation of an error bound for the balanced linear complementarity problem with unique solution[END_REF] Linear Complementarity Problem (LCP) 0 (Ax + a) ⊥ (Bx + b) 0.

(1.4)

This system expresses the fact that a point x ∈ R n is sought such that Ax + a 0, Bx + b 0 and (Ax + a) T (Bx + b) = 0 (the superscript " T " is used here and below to denote vector or matrix transposition). Problem (1.4) is a special case of the so-called (extended) vertical LCP, which uses more than two matrices and vectors in its formulation [START_REF] Cottle | A generalization of the linear complementarity problem[END_REF][START_REF] Sznajder | The generalized order linear complementarity problem[END_REF][START_REF] Zhang | Global error bounds for the extended vertical LCP[END_REF]. In the standard LCP, A is the identity matrix and a = 0 [START_REF] Cottle | The Linear Complementarity Problem[END_REF][START_REF] Murty | Linear Complementarity, Linear and Nonlinear Programming[END_REF].

The reformulation (1.3) of (1.4) is based on the fact that, for two real numbers α and β, min(α, β) = 0 if and only if α 0, β 0 and αβ = 0 [1,[START_REF] Pang | A B-differentiable equation-based, globally and locally quadratically convergent algorithm for nonlinear programs, complementarity and variational inequality problems[END_REF]. This reformulation serves as the basis for a number of solving methods and investigations [1, 7-9, 25-27, 34, 45, 47, 52-54]. If (1.4) stands alone, it is appropriate to have m = n, but (1.4) may be part of a system with other constraints to satisfy [START_REF] Ben Gharbia | Gas phase appearance and disappearance as a problem with complementarity constraints[END_REF][START_REF] Marchand | Fully coupled generalised hybrid-mixed finite element approximation of two-phase two-component flow in porous media. Part II: numerical scheme and numerical results[END_REF][START_REF] Marchand | Fully coupled generalised hybrid-mixed finite element approximation of two-phase two-component flow in porous media. Part I: formulation and properties of the mathematical model[END_REF], in which case m n. In the computation of the B-differential of the Min function (1.2), m and n may be unrelated.

Occasionally, we shall refer to the nonlinear version of the above problem, in which a function H : E → R m is defined at x ∈ E by H(x) := min(F (x), G(x)), (1.5) where F and G : E → R m are two functions and the "min" operator still acts componentwise.

The equation H(x) = 0 is then a reformulation of the complementarity problem "0 F (x) ⊥ G(x) 0". As a first general remark, let us quote the fact that the B-differential of H cannot be deduced from the knowledge of the B-differential of its scalar components H i : x ∈ E → H i (x) ∈ R, for i ∈ [1 : m], which is trivial in the present context (lemma 2.1(4)). Indeed, if [19; proposition 2.6.2(e)]

∂ B H(x) ⊆ ∂ B H 1 (x) × • • • × ∂ B H m (x), (1.6)
equality in this inclusion may not always hold (see [34; § 7.1.15] and almost all the examples and test-cases below). Therefore, all the components of H must be taken into account simultaneously.

The B-differential of H at x is a finite set, made of Jacobians J whose ith row is A i, : or B i, : (proposition 2.2). Consequently, its cardinal can be exponential in m and it occurs that its full mathematical description is a tricky task, essentially when there are many indices i for which (Ax + a) i = (Bx + b) i and A i, : = B i, : , a situation that makes H nondifferentiable (lemma 2.1). Then, a rich panorama of configurations appears, which is barely glimpsed in this contribution.

The paper starts with a background section (section 2), which recalls a basic property of the minimum of two functions (lemma 2.1) and gives us a first perception of the structure of the B-differential of the function H, in particular its finite nature (proposition 2.2). A useful technical lemma is also presented (lemma 2.5).

In section 3, it is shown that the problem of computing ∂ B H(x) has a rich panel of equivalent formulations, related to various areas of mathematics. We have quoted two forms of the problem in linear algebra, which are dual to each other (section 3.2), two equivalent problems in convex analysis (section 3.3) and a last equivalent problem, which arises in computational discrete geometry and deals with the arrangement of hyperplanes having the zero point in common (section 3.4).

Section 4 gives some properties of the B-differential of H, recalls Winder's formula of its cardinal, to which an analytic proof mimicking the original one is given, provides some lower and upper bounds on this one, proves necessary and sufficient conditions so that two extreme configurations occur and highlights two links between the B-differential and C-differential.

Section 5 presents algorithms for computing one (section 5.1) or all (section 5.2) the Jacobians of ∂ B H(x). In the latter case, the algorithms construct a tree incrementally and recursively (section 5.2.2), as proposed by Rada and Černý [START_REF] Rada | A new algorithm for enumeration of cells of hyperplane arrangements and a comparison with Avis and Fukuda's reverse search[END_REF]. On the one hand (section 5.2.3), an algorithm based on the notion of matroid circuit of the matrix V expressing the gap of differentiability is proposed; it has the nice feature of requiring no linear optimization (LO) problem to solve. On the other hand (section 5.2.5), various modifications of the algorithm of Rada and Černý [START_REF] Rada | A new algorithm for enumeration of cells of hyperplane arrangements and a comparison with Avis and Fukuda's reverse search[END_REF] are proposed with the goal of decreasing the number of LO problems to solve. The complexity of one proposed algorithm is analyzed, bounding the number linear optimization problems to solve by a multiple of the cardinal of the B-differential. Numerical experiments are reported (section 5.2.8), showing that the proposed algorithms significantly improve the performance of the Rada and Černý method, with mean (resp. median) acceleration ratios in the range 7.. 15 (resp. 3..14), measured by the computing time. This speed-up exceeds 30, for some algorithms and test-problems.

An abridged version of this report can be found in [START_REF] Dussault | On the B-differential of the componentwise minimum of two affine vector functions[END_REF].

Notation

We denote by |S| the number of elements of a set S (i.e., its cardinal). The power set of a set S is denoted by P(S). The set of bipartitions (I, J) of a set K is denoted by B(K): I ∪ J = K and I ∩ J = ∅. The sets of nonzero natural and real numbers are denoted by N * and R * , respectively. The sign of a real number is the multifunction sgn : R ⊸ R defined by sgn(t) = {1} if t > 0, sgn(t) = {-1} if t < 0 and sgn(0) = [-1, 1]. We note R n + := {x ∈ R n : x 0} and R n ++ := {x ∈ R n : x > 0} (strict inequalities must also be understood componentwise; hence x > 0 means x i > 0 for all indices i). For a subset S of a vector space, we denote by vect(S) the subspace spanned by S. The vector of all one's, in a real space whose dimension is given by the context, is denoted by e. The Hadamard product of u and v ∈ R n is the vector u q v ∈ R n whose ith component is u i v i . The range space of an m × n matrix A is denoted by R(A), its null space by N (A), its rank is rank(A) := dim R(A) and its nullity is null(A) := dim N (A) = n-rank(A) by the rank-nullity theorem. The ith row (resp. column) of A is denoted by A i, : (resp. A : ,i ). Transposition operates after a row/column selection: A T i, : is a short notation for the column vector (A i, : ) T and A T : ,i is a short notation for the row vector (A : ,i ) T . For a vector α, Diag(α) is the square diagonal matrix with the α i 's on its diagonal.

Background

Recall that F : E → F is said to be (Fréchet ) differentiable at x if F (x+d) = F (x)+Ld+o( d ) for some L ∈ L(E, F), in which case one denotes by F ′ (x) = L the derivative of F at x. It is said that F is Gâteaux-differentiable (or G-differentiable) at x if its directional derivative at x along d ∈ E, namely F ′ (x; d) := lim t↓0 [F (x + td) -F (x)]/t, exists for all d ∈ E and is linear in d; this linear map is then also denoted by F ′ (x). A differentiable function is Gdifferentiable. We say below that F is continuously differentiable at x if it is differentiable near x (like in [START_REF] Clarke | Optimization and Nonsmooth Analysis[END_REF], "near" means here and below "in a neighborhood of" in the topological sense) and if its derivative is continuous at x. If F is continuously differentiable at x, then ∂ B F (x) = {F ′ (x)}.

The next famous lemma recalls a necessary and sufficient condition guaranteeing the differentiability of the minimum of two scalar functions (see [55; 1993, final remarks (1)] and [17; 2011, theorem 2.1], for the differentiability); it will be frequently used. We give it a proof that includes the G-differentiability property.

Lemma 2.1 (differentiability of the Min function) Let f and g : E → R be two functions and h : E → R be defined by h(•) := min(f (•), g(•)). Suppose that f and g are G-differentiable (resp. differentiable) at a point x ∈ E. 1) If f (x) < g(x), then h is G-differentiable (resp. differentiable) at x and h ′ (x) = f ′ (x).

2) If f (x) > g(x), then h is G-differentiable (resp. differentiable) at x and h ′ (x) = g ′ (x).

3) If f (x) = g(x), then h is G-differentiable (resp. differentiable) at x ⇐⇒ f ′ (x) = g ′ (x).

In this case, h ′ (x) = f ′ (x) = g ′ (x). 4) If f and g are continuously differentiable at x, then

∂ B h(x) =    {f ′ (x)} if f (x) < g(x), {f ′ (x), g ′ (x)} if f (x) = g(x), {g ′ (x)} if f (x) > g(x).
Proof. 1) This results from the fact that, when f (x) < g(x), h = f near x.

2) Switch f and g in point 1.

3) [G-differentiability] Suppose first that f and g are G-differentiable at x. Since f (x) = g(x), one has for any d ∈ R n :

h ′ (x; d) = min(f ′ (x)d, g ′ (x)d).
(2.1)

[⇒] Since f , g and h are G-differentiable at x, d ∈ R n → (f ′ (x; d), g ′ (x; d), h ′ (x; d)) is linear. Then, using (2.1):

h ′ (x; d) = -h ′ (x; -d) = -min(f ′ (x)(-d), g ′ (x)(-d)) = max(f ′ (x)d, g ′ (x)d).
Hence min(f

′ (x)d, g ′ (x)d) = max(f ′ (x)d, g ′ (x)d) or f ′ (x)d = g ′ (x)d. Since d is arbitrary, it follows that f ′ (x) = g ′ (x) = h ′ (x). [⇐] If f ′ (x) = g ′ (x), then one has from (2.1): h ′ (x; d) = f ′ (x)d for all d ∈ R n . Therefore, h ′ (x; d) is linear in d, implying that h is G-differentiable at x and h ′ (x) = f ′ (x).
[Differentiability] Suppose now that f and g are differentiable at x. If h is differentiable at x, it is also G-differentiable at x and, by the first part of the proof,

h ′ (x) = f ′ (x) = g ′ (x). Conversely, if f ′ (x) = g ′ (x), one has for d → 0, h(x + d) = min(f (x + d), g(x + d)) = min(f (x) + f ′ (x)d + o( d ), g(x) + g ′ (x)d + o( d )) = f (x) + f ′ (x)d + min(o( d ), o( d )) [f (x) = g(x), f ′ (x) = g ′ (x)] = f (x) + f ′ (x)d + o( d ).
Therefore h is differentiable at x and h

′ (x) = f ′ (x). 4) Let J ∈ ∂ B h(x). Then, there exists a sequence {x k } → x such that x k ∈ D h and h ′ (x k ) → J.
If f (x) < g(x) (switch f and g to deal with the case where

f (x) > g(x)), h(x k ) = f (x k ) and h ′ (x k ) = f ′ (x k ) for k sufficiently large (continuity of f and g at x), so that J = f ′ (x) by the continuity of f ′ at x. If f (x) = g(x)
, by points 1-3 and

x k ∈ D h , h ′ (x k ) ∈ {f ′ (x k ), g ′ (x k )}. Since h ′ (x k ) → J, f ′ (x k ) → f ′ (x) and g ′ (x k ) → g ′ (x), we get at the limit that J ∈ {f ′ (x), g ′ (x)}, which proves the inclusion ∂ B h(x) ⊆ {f ′ (x), g ′ (x)}.
Let us now prove the inclusion

∂ B h(x) ⊇ {f ′ (x), g ′ (x)} when f (x) = g(x). This one holds if f ′ (x) = g ′ (x), since ∂ B h(x)
is nonempty and contains either f ′ (x) or g ′ (x) by the preceeding argument. Suppose now that f ′ (x) = g ′ (x), so that there is a direction d such that

f ′ (x)d < g ′ (x)d. Take y k = x+t k d with t k ↓ 0 (resp. t k ↑ 0). Then, f (y k )-g(y k ) = t k [f ′ (x)d- g ′ (x)d] + o(t k ) by the differentiability of f and g at x. Therefore, h(y k ) = f (y k ) < g(y k ), h ′ (y k ) = f ′ (y k ) (resp. f (y k ) > g(y k ) = h(y k ), h ′ (y k ) = g ′ (y k )) and y k ∈ D h for k sufficiently large. Taking the limit in k shows that f ′ (x) ∈ ∂ B h(x) (resp. g ′ (x) ∈ ∂ B h(x)), as desired.
The previous lemma shows the relevance of the following index sets, when the differentiability of the function H is at stake:

A(x) := {i ∈ [1 : m] : (Ax + a) i < (Bx + b) i }, (2.2a) B(x) := {i ∈ [1 : m] : (Ax + a) i > (Bx + b) i }, (2.2b) E(x) := {i ∈ [1 : m] : (Ax + a) i = (Bx + b) i }. (2.2c)
The lemma also shows that it is meaningful to distinguish the indices i ∈ E(x) for which A i, : = B i, : from those for which A i, : = B i, : :

E = (x) := {i ∈ E(x) : A i, : = B i, : }, (2.2d)
E = (x) := {i ∈ E(x) : A i, : = B i, : }. (2.2e)
To simplify the presentation, we assume in the sequel that

E = (x) = [1 : p],
for some p ∈ [0 : m] (p = 0 if and only if

E = (x) = ∅). The next proposition describes the superset ∂ B H(x) of ∂ B H(x)
given in the right-hand side of (1.6) (see [46; 1998, § 2] in a somehow different context, [24; 2000, before (8)]). This Cartesian product actually reads

∂ B H(x) := {J ∈ L(E, R m ) : J i, : = A i, : , if i ∈ A(x), J i, : = A i, : = B i, : , if i ∈ E = (x), J i, : ∈ {A i, : , B i, : }, if i ∈ E = (x), J i, : = B i, : , if i ∈ B(x)}. (2.3) Note that ∂ B H(x) may differ from ∂ B H(x): if n = 1, m = 2, F (x) ≡ 0 and G(x) ≡ xe, one has ∂ B H(0) = { 0 0 , 1 1 }, while ∂ B H(0) = { 0 0 , 1 0 , 0 1 , 1 1 }. Proposition 2.2 (superset of ∂ B H(x)) One has ∂ B H(x) ⊆ ∂ B H 1 (x) × • • • × ∂ B H m (x) = ∂ B H(x).
(2.4)

In particular, |∂ B H(x)| 2 p .
Proof. The inclusion in (2.4) is clear since, when

H ′ (x k ) converges to some J, H ′ i (x k ) → J i, : , for all i ∈ [1 : m].
The equality is also clear as a consequence of lemma 2.1(4).

The last claim is a straightforward consequences of the fact that J i, : can take two different values, A i, : or B i, : , only for the indices i ∈

E = (x) (recall that |E = (x)| = p).
The previous proposition shows that ∂ B H(x) is a finite set. It also naturally leads to the next definition.

Definition 2.3 (complete B-differential) We say that the B-differential of H at x ∈ R n is complete if ∂ B H(x) = ∂ B H(x) or, equivalently, if |∂ B H(x)| = 2 p . Definitions 2.4 (symmetry in ∂ B H(x)) For x ∈ E, we say that the Jacobian J ∈ ∂ B H(x) is symmetric to the Jacobian J ∈ ∂ B H(x) if Ji,: = A i, : if i ∈ E = (x) and J i, : = B i, : , B i, : if i ∈ E = (x) and J i, : = A i, : . The B-differential ∂ B H(x) itself is said to be symmetric if each Jacobian J ∈ ∂ B H(x) has its symmetric Jacobian J in ∂ B H(x).
We shall use the following lemma, which, for the sake of generality, is written in a slightly more abstract formalism than the one we need below (one could take E = R n and the Euclidean scalar product for

•, • ). It is a refinement of [17; lemma 2.1]. Lemma 2.5 (discriminating covectors) Suppose that (E, •, • ) is a Euclidean vector space, p ∈ N * and v 1 , . . . , v p are p distinct vectors of E. Then, the set of vectors ξ ∈ E such that |{ ξ, v i } i∈[1 : p] | = p is dense in E. Proof. Denote by Ξ the set of vectors ξ ∈ E such that |{ ξ, v i } i∈[1 : p] | = p (i.e., { ξ, v i } i∈[1 : p] contains p distinct values in R). We have to show that Ξ is dense in E.
Take ξ 0 / ∈ Ξ, so that ξ 0 , v i = ξ 0 , v j for some i = j in [1 : p]. By continuity of the scalar product, for any ε 0 > 0 sufficiently small, the vector

ξ 1 := ξ 0 -ε 0 (v i -v j ) guarantees ξ 1 , v i 1 < ξ 1 , v i 2 for all i 1 and i 2 ∈ [1 : p] such that ξ 0 , v i 1 < ξ 0 , v i 2 (
in other words, ξ 1 maintains strict the inequalities that are strict with ξ 0 ). In addition

ξ 1 , v i -ξ 1 , v j = ξ 0 , v i -v j =0 -ε 0 v i -v j 2 >0 < 0.
Therefore, one gets one more strict inequality with ξ 1 than with ξ 0 . Pursuing like this, one can finally obtain a vector ξ in Ξ. This vector is arbitrarily close to ξ 0 by taking the ε i 's positive and sufficienty small.

Equivalent problems

The problem of determining the B-differential of the piecewise affine function, that is the minimum (1.2) of two affine functions, appears in various contexts, sometimes with non straightforward connections with it (this one is recalled in section 3.1). We review some equivalent formulations in this section (see also [START_REF] Avis | Reverse search for enumeration[END_REF][START_REF] Baldi | Polynomial threshold functions, hyperplane arrangements, and random tensors[END_REF][START_REF] Winder | Partitions of N-space by hyperplanes[END_REF] and the references therein) and give a few properties of the B-differential in this piecewise affine case. As suggested by proposition 2.2, these problems have an enumeration nature, since a finite list of mathematical objects has to be determined. This list may have a number of elements exponential in p, which makes its content difficult to specify (in this respect, the particular case where the B-differential is complete is a trivial exception). Some formulations, such as the one related to the arrangement of hyperplanes containing the origin (section 3.4), have been extensively explored, others much less. Each formulation sheds a particular light on the problem and is therefore, as such, interesting to mention and keep in mind. It also offers the possibility of introducing new algorithmic approaches to describe the B-differential.

B-differential of the minimum of two affine functions

The problem of this section was already presented in the introduction and is sometimes referred to, in this paper, as the original problem. When E = (x) = ∅, the rows of B -A with indices in E = (x) will play a key role below. We denote its transpose by

V := (B -A) T E = (x), : ∈ R n×p . (3.1)
Note that, due to their indices in E = (x) = [1 : p] and the definition of this index set, the columns of V are nonzero. This matrix may not always have full rank, however.

3.2 Linear algebra problems

S := {s ∈ {±1} p : s q V T d > 0 is feasible for d ∈ R n }. (3.2)
The link between the two problems is established by the following map

σ : J ∈ ∂ B H(x) → s ∈ {±1} p , where s i = +1 if i ∈ E = (x), J i, : = A i, : , -1 if i ∈ E = (x), J i, : = B i, : . (3.3a)
The map is well defined since A i, : = B i, : when i ∈ E = (x). Furthermore, σ is bijective since two Jacobians in ∂ B H(x) only differ by their rows with index in E = (x) and that these rows can take any of the values A i, : or B i, : . Actually, its reverse map is

σ -1 : s ∈ {±1} p → J ∈ ∂ B H(x), where J i, : = A i, : if i ∈ E = (x), s i = +1, B i, : if i ∈ E = (x), s i = -1. (3.3b)
The question that arises is whether σ is also a bijection between ∂ B H(x) and S.

Proposition 3.3 (bijection ∂ B H(x) ↔ S)
Let H : R n → R m be given by (1.2), x be a point in R n such that p = 0 and V be given by (3.1). Then, the map σ is a bijection from ∂ B H(x) onto S. In particular, the following properties hold.

1) If J ∈ ∂ B H(x), then ∃ d ∈ R n such that σ(J) q V T d > 0. 2) If s ∈ {±1} p and ∃ d ∈ R n is such that s q V T d > 0, then σ -1 (s) ∈ ∂ B H(x). 3) Let J ∈ ∂ B H(x). Then, J ∈ ∂ B H(x) ⇐⇒ σ(J) q V T d > 0 is feasible for d ∈ R n .
Proof. The properties 1, 2 and 3 in the statement of the proposition are straightforward consequences of the bijectivity of σ : ∂ B H(x) → S. Now, the discussion before the proposition has shown that σ : ∂ B H(x) → {±1} p is a bijection. Therefore, σ : ∂ B H(x) → {±1} p is injective and it suffices to prove that

σ(∂ B H(x)) = S. (3.4a) [⊆ or point 1] Let J ∈ ∂ B H(x).
We have to show that σ(J) ∈ S. By J ∈ ∂ B H(x), there exists a sequence {x k } ⊆ D H converging to x such that

H ′ (x k ) → J.
(3.4b)

For i ∈ E = (x), one cannot have (Ax k + a) i = (Bx k + b) i , since A i, : = B i, : would imply that x k / ∈ D H (lemma 2.1
). Therefore, one can find a subsequence K of indices k and a partition (A 0 , B 0 ) of E = (x) such that for all k ∈ K:

(Ax k + a) A 0 < (Bx k + b) A 0 and (Ax k + a) B 0 > (Bx k + b) B 0 . (3.4c) Now, fix k ∈ K and set d := x k -x. Since (Ax + a) i = (Bx + b) i for i ∈ E = (x), one deduces from (3.4c) that (B -A) A 0 , : d > 0 and (B -A) B 0 , : d < 0.
Recalling the definitions of V in (3.1) and of S in (3.2), we see that, to conclude the proof of the membership σ(J) ∈ S, it suffices to show that [σ(J)] A 0 = +1 and [σ(J)] B 0 = -1 or, equivalently, by the definition of σ, (J i, : = A i, : for i ∈ A 0 ) and (J i, : = B i, : for i ∈ B 0 ). This is indeed the case, since by (3.4c), for all k ∈ K, one has (H ′ i (x k ) = A i, : for i ∈ A 0 ) and (H ′ i (x k ) = B i, : for i ∈ B 0 ); now, use the convergence (3.4b) to conclude.

[⊇ or point 2] Let s ∈ S. We have to find a J ∈ ∂ B H(x) such that σ(J) = s, that is, which satisfies

(J i, : = A i, : if s i = +1) and (J i, : = B i, : if s i = -1). (3.4d) Since s ∈ S, there is a d ∈ R n such that s q V T d > 0. (3.4e)
Take a real sequence {t k } ↓ 0 and define the sequence {x k } ⊆ R n by

x k := x + t k d.
Then, x k → x. We claim that, for k sufficiently large, x k ∈ D H and H ′ (x k ) is a constant matrix J satisfying (3.4d), which will conclude the proof. Let i ∈ [1 : m].

r If i ∈ A(x), (Ax k + a) i < (Bx k + b) i for k large, so that x k ∈ D H and H ′ i (x k ) = A i, : . r If i ∈ B(x), (Ax k + a) i > (Bx k + b) i for k large, so that x k ∈ D H and H ′ i (x k ) = B i, : . r If i ∈ E = (x), then A i, : = B i, : , so that x k ∈ D H and H ′ i (x k ) = A i, : = B i, : . r If i ∈ E = (x), subtract side by side (Ax k + a) i = (Ax + a) i + t k A i, : d and (Bx k + b) i = (Bx + b) i + t k B i, : d, use (Ax + a) i = (Bx + b) i and next (3.4e) to get (Bx k + b) i -(Ax k + b) i = t k (B i, : -A i, : )d = t k V T i, : d > 0 if s i = +1, < 0 if s i = -1.
Hence,

x k ∈ D H , (H ′ i (x k ) = A i, : if s i = +1) and (H ′ i (x k ) = B i, : if s i = -1).
Equivalence 3.4 (B-differential ↔ signed feasibility of strict inequality systems)

The equivalence between the original problem 3.1 and the signed feasibility of strict inequality system problem 3.2 is a consequence of the previous proposition with V given by (3.

I := {I ⊆ [1 : p] : N (V ) ∩ O p I = {0}}. Note that, if I ∈ I, then I c ∈ I (because y ∈ (N (V ) ∩ O p I ) \ {0} implies that -y ∈ (N (V ) ∩ O p I c ) \ {0})
, so that |I| is even (just like |S| and |S c |, see proposition 4.1). The equivalence between problems 3.2 and 3.5 is obtained thanks to the following bijection

ı : s ∈ {±1} p → ı(s) := {i ∈ [1 : p] : s i = +1} ∈ P([1 : p]), (3.5)
whose reverse map is ı -1 :

I ∈ P([1 : p]) → s ∈ {±1} p , where s i = +1 if i ∈ I and s i = -1 if i / ∈ I.
As announced above, this equivalence relies on Gordan's theorem of the alternative [38; 1873]: for a matrix A ∈ R m×n , Proof. Let s ∈ {±1} p and set I := ı(s) = {i ∈ [1 : p] : s i = +1}. Define A := Diag(s)V T to make the link with Gordan's alternative (3.6). One has the equivalences

∃ x ∈ R n : Ax > 0 ⇐⇒ ∄ α ∈ R m + \ {0} : A T α = 0. ( 3
s ∈ S c ⇐⇒ ∄ x ∈ R n : Ax > 0 [definition of S in (3.2)] ⇐⇒ ∃ α ∈ R m + \ {0} : A T α = 0 [Gordan's alternative (3.6)] ⇐⇒ ∃ α ∈ R m + \ {0} : s q α ∈ N (V ) ⇐⇒ N (V ) ∩ O p I = {0} [see below] (3.7) ⇐⇒ I ∈ I [definition of I].
The implication "⇒" in (3.7) is due to the fact that s q α is nonzero and belongs to both N (V ) and O p I . The reverse implication "⇐" in (3.7) is due to the fact that there is a nonzero y ∈ N (V ) ∩ O p I , implying that α := s q y is nonzero and 0 and is such that s q α = y ∈ N (V ). Since ı : {±1} p → P([1 : p]) is a bijection, the above equivalences show that ı is also a bijection from S c onto I. Equivalence 3.7 (S c ↔ I) The equivalence between problems 3.2 and 3.5 is a consequence of the bijectivity of ı : S c → I, established in proposition 3.6: to determine S, it suffices to determine S c = ı -1 (I), hence to determine I.

Recall that the nullity of a matrix A, denoted by null(A), is the dimension of its null space. Let us introduce the following collection of index sets (from now on, J usually denotes a set of indices rather than a Jacobian matrix):

C := {J ⊆ [1 : p] : J = ∅, null(V : ,J ) = 1, V : ,J 0 is injective if J 0 J}, (3.8)
where " " is used to denote strict inclusion. In the terminology of the vector matroid formed by the columns of V and its subsets made of linearly independent columns [51; proposition 1.1.1], the elements of C are called the circuits of the matroid [51; proposition 1.3.5(iii)]. The particular expression (3.8) of the circuit set is interesting in the present context, since it readily yields the following implication:

J ∈ C =⇒ any nonzero α ∈ N (V : ,J ) has none zero component. (3.9)
From (3.8) and (3.9), one can associate with J ∈ C a pair of sign vectors ±s ∈ {±1} J by s := sgn(α) for some nonzero α ∈ N (V : ,J ); the sign vectors ±s do not depend on the chosen α ∈ N (V : ,J ) \ {0} since null(V : ,J ) = 1. We call such a sign vector a stem vector, because of proposition 3.9 below, which shows that any s ∈ S c can be generated from such a stem vector.

Definition 3.8 (stem vector) A stem vector is a sign vector s = sgn(α), where α ∈ N (V : ,J ) for some J ∈ C.

Note that there are twice as many stem vectors as circuits and that the stem vectors do not have all the same size.

Proposition 3.9 (generating S c from the stem vectors) For s ∈ {±1} p , s ∈ S c ⇐⇒ s J = s for some J ⊆ [1 : p] and some stem vector s.

(3.10)

Proof.

[⇒] The index set J ⊆ [1 : p] in the right-hand side of (3.10) can be determined as the one satisfying the following two properties:

{d ∈ R n : s j v T j d > 0 for all j ∈ J} = ∅, (3.11a)
∀ J 0 J, {d ∈ R n : s j v T j d > 0 for all j ∈ J 0 } = ∅. (3.11b)
To determine such a J, start with J = [1 : p], which verifies (3.11a), since s ∈ S c . Next, remove an index j from [1 : p] if (3.11a) holds for J = [1 : p] \ {j}. Pursuing the elimination of indices j in this way, one arrives to an index set J satisfying (3.11a) and {d ∈ R n : s j v T j d > 0 for all j ∈ J \ {j 0 }} = ∅ for all j 0 ∈ J. Then, (3.11b) clearly holds. We claim that, for the J thus defined, s J is a stem vector, which will conclude the proof of the implication.

We first show that J is a matroid circuit, sticking to definition 3.8. By (3.11a), J = ∅. By Gordan's alternative (3.6), (3.11a) and (3.11b) read

∃ α ∈ R J + \ {0} such that j∈J s j v j α j = 0, (3.11c)
∀ J 0 J, ∄ α ′ ∈ R J 0 + \ {0} such that j∈J 0 s j v j α ′ j = 0. (3.11d)
From these properties, one deduces that α > 0 and that null(V : ,J ) 1. To show that null(V : ,J ) = 1, we proceed by contradiction. Suppose that there is a nonzero α ′′ ∈ R J that is not colinear with α and that verifies j∈J s j v j α ′′ j = 0. One can assume that t := max{α ′′ j /α j : j ∈ J} is > 0 (take -α ′′ otherwise). Set J 0 := {j ∈ J : α ′′ j /α j < t}. By the non-colinearity of α and α ′′ , on the one hand, and the definition of t, on the other hand, one has ∅ J 0 J. Furthermore, α ′ := αα ′′ /t 0, α ′ j > 0 for j ∈ J 0 and α ′ j = 0 for j ∈ J \ J 0 . Since j∈J 0 s j v j α ′ j = 0, we have a contradiction with (3.11d). To show that J ∈ C, we still have to show that V : ,J 0 is injective when J 0 J. Let J 0 J and suppose that j∈J 0 s j v j β j = 0 for some β ∈ R J 0 . We only have to show that β = 0. The cases when β 0 or β 0 are easy since then, (3.11d) readily implies that β = 0. Suppose now that β has positive (> 0) and negative (< 0) components. Set t := min{-α j /β j : j ∈ J 0 , β j < 0} > 0. Then, α ′ := α J 0 + tβ 0 and j∈J 0 s j v j α ′ j = 0. By (3.11d), α ′ = 0, implying that β 0. Like previously, (3.11d) implies that β = 0. Now, since J is a matroid circuit of V , since s J q α ∈ N (V : ,J ) \ {0} by (3.11c) and since s J = sgn(s J q α), s J is a stem vector.

[⇐] Since s is a stem vector with indices in J ⊆ [1 : p], s := sgn(α) for some α ∈ R J with nonzero components that satisfies V : ,J α = 0. Let J + := {j ∈ J : α j > 0} = {j ∈ J : s j = +1}, which may be empty. Since one has α ∈ N (V : ,J ) ∩ O J J + , the bijection ı in (3.5), restricted to {±1} J , tells us that ı -1 (J + ) = sgn(α) = s is such that there is no

d ∈ R n such that si v T i d > 0 or s i v T i d > 0 for i ∈ J, hence certainly not for i ∈ [1 : p], meaning that s ∈ S c .
To determine the stem vectors, which are based on the matroid circuits defined by (3.8), one has to select subsets of columns of V forming a rank one matrix, whose strict subsets form injective matrices. Actually, this last condition can be simplified by the following property. Proposition 3.10 (matroid circuit detection) Suppose that I ⊆ [1 : p] is such that null(V : ,I ) = 1 and that α ∈ N (V : ,I ) \ {0}. Then, J := {i ∈ I : α i = 0} is a matroid circuit of V and the unique one included in I.

Proof. 1) Let us show that J is a matroid circuit. Since α = 0, J = ∅.

Let us show that null(V : ,J ) = 1. Since J ⊆ I, one has null(V : ,J ) null(V : ,I ) = 1. Furthermore, α J ∈ N (V : ,J ) \ {0} implies that null(V : ,J ) 1.

Now, let J 0 J and suppose that V : ,J 0 β = 0. We have to show that β = 0. Since V : ,J (β, 0 J\J 0 ) = 0, it follows that (β, 0 J\J 0 ) ∈ N (V : ,J ), which is of dimension 1, so that (β, 0 J\J 0 ) is colinear to α. Since the components of α are = 0, we get that β = 0.

2) Let us now show that J is the unique matroid circuit of V included in I.

Let J ′ be a matroid circuit of V included in I. Then null(V : ,J ′ ) = 1 and there is a nonzero α ′ ∈ N (V : ,J ′ ). By (3.9), α ′ has nonzero components. Furthermore, (α ′ , 0 I\J ′ ) ∈ N (V : ,I ), which has unit dimension and contains α. Therefore, α and (α ′ , 0 I\J ′ ) are colinear. Since the components of α are = 0, we get that J ′ = J.

Convex analysis problems

The formulation of the original problem 3.1 in the form of the convex analysis problems 3.11 and 3.14 below may be useful to highlight some properties of ∂ B H(x), thanks to the tools of that discipline. We take this point of view to introduce the notion of extremality (definition 4.6) and to propose other proofs of propositions 4.5 and 4.17 below.

Pointed cones by vector inversions

Recall that a convex cone K of R n is a convex set verifying R ++ K ⊆ K (or, more explicitly, tx ∈ K when t > 0 and x ∈ K). A closed convex cone K is said to be pointed if K ∩ (-K) = {0} [15; p. 54], which amounts to saying that K does not contain a line (i.e., an affine subspace of dimension one) or that K has no nonzero direction z such that -z ∈ K. For P ⊆ R n , we also denote by "cone P " the smallest convex cone containing P . Problem 3.11 (pointed cones by vector inversions) Let be given two positive integers n and p ∈ N * and p vectors v 1 , . . . ,

v p ∈ R n \ {0}. It is requested to determine all the sign vectors s ∈ {±1} p such that cone{s i v i : i ∈ [1 : p]} is pointed.
The equivalence between the original problem 3.1 and this problem 3.11 is obtained thanks to the next proposition, which gives another property ("cone pointedness") that is equivalent to those in (3.6) and that is adapted to the present concern. See also [39; theorem 2.3.29]. Proposition 3.12 (pointed polyhedral cone) For a finite collection of nonzero vectors {v i : i ∈ [1 : p]} ⊆ R n , the following properties are equivalent:

(i) cone{v i : i ∈ [1 : p]} is pointed, (ii) ∄ α ∈ R p + \ {0} : i∈[1 : p] α i v i = 0, (iii) ∃ d ∈ R n , ∀i ∈ [1 : p] : v T i d > 0.
Proof. The equivalence (ii) ⇔ (iii) follows from Gordan's alternative (3.6) (with A = V T ), so that it remains to prove (i) ⇔ (ii).

Set K := cone{v i : i ∈ [1 : p]}. [(i) ⇒ (ii)]
One can assume that p 2, since when p = 1, both (i) and (ii) hold. We prove the contrapositive. Assume that there is an α

∈ R p + \ {0} such that i∈[1 : p] α i v i = 0. Without loss of generality, one can assume that α 1 = 0. Set z := α 1 v 1 ∈ K \ {0}. One also has -z = i∈[2 : p] α i v i ∈ K. Hence, K is not pointed. [(ii) ⇒ (i)]
We prove the contrapositive. If K is not pointed, there exists a nonzero

vector z ∈ K ∩ (-K). Therefore, z = i∈[1 : p] α ′ i v i and -z = i∈[1 : p] α ′′ i v i for some α ′ and α ′′ ∈ R p + \ {0}.
Adding the two identities side by side, we get i∈[1

: p] α i v i = 0, with α := α ′ + α ′′ . Since α ∈ R p + \ {0}, this contradicts (ii).
Equivalence 3.13 (signed linear system feasibility ↔ pointed cone by vector inversion) The equivalence (i) ⇔ (iii) of the previous proposition shows that the set S defined by (3.2) is also given by

S = {s ∈ {±1} p : cone{s i v i : i ∈ [1 : p]} is pointed}. (3.12)
To put it in words, denoting by v 1 , . . . , v p the columns of the matrix V defined by (3.1), the original problem of section 3.1 is equivalent to problem 3.11.

Linearly separable bipartitions of a finite set

This section extends section 3.3.1 and adopts its concepts and notation. The point of view presented in this section was also shortly considered by Zaslavsky [72;1975, § 6A].

Problem 3.14 (linearly separable bipartitioning) Let be given an affine space A and p ∈ N * vectors v1 , . . . , vp ∈ A. Let A 0 := A -A be the vector space parallel to A, endowed with a scalar product •, • . It is requested to find all the ordered bipartitions (i.e., the partitions made of two subsets) (I, J) of [1 : p] for which there exists a vector ξ ∈ A 0 (also called separating covector below) such that

∀ i ∈ I, ∀ j ∈ J : ξ, vi < ξ, vj .
Of course, if (I, J) is an appropriate ordered bipartition to which a separating covector ξ corresponds, then (J, I) is also an appropriate ordered bipartition with separating covector -ξ. Therefore, only half of the appropriate ordered bipartitions (I, J) must be identified, a fact that is related to the symmetry of ∂ B H(x) (proposition 4.1). Figure 3.1 shows the solution to this problem by drawing the separating hyperplanes {v ∈ A : ξ T v = t} corresponding to some separating covector ξ and some t ∈ R, for three examples with n -1 = 2 and p = 4. Since it will be shown that |S| is the number of these searched linearly separable bipartitions, this one is denoted that way in the figure. Obviously, |S| not only depends on p and r := dim(vect{v 1 , . . . , vp }) + 1, but it also depends on the arrangement of the vi 's in the affine space A. We also see that |S| cannot take all the even values (proposition 4.1) between its lower bound 2p = 8 and its upper bounds 8 (if r = 2) and 14 (if r = 3) given by propositions 4.11 and 4.14.

The equivalence between the linearly separable bipartitioning problem 3.14 of this section and the vector inversion problem 3.11 (hence, with the original problem 3.1) is grounded on the following construction and proposition.

v p ∈ R n such that K := cone{v k : k ∈ [1 : p]} is a pointed cone. From proposition 3.12, there is a direction d ∈ R n such that d = 1 and ∀ k ∈ [1 : p] : v T k d > 0 . Define A := {v ∈ R n : d T v = 1}, A 0 := A -A = {v ∈ R n : d T v = 0}, ∀ k ∈ [1 : p] : vk := v k /(v T k d) ∈ A.
2) For a given bipartition (I, J) of [1 : p], define

K I := cone{v i : i ∈ I} and K J := cone{v j : j ∈ J}, (3.13a)
C I := K I ∩ A and C J := K J ∩ A. (3.13b)
Proposition 3.16 (pointed cone after vector inversions) Let be given two integers n and p ∈ N * and p nonzero vectors v 1 , . . . ,

v p ∈ R n such that K := cone{v k : k ∈ [1 : p]} is a pointed cone. Let (I, J) be a partition of [1 : p].
Adopt the construction 3.15. Then, the following properties are equivalent:

(i) cone((-K I ) ∪ K J ) is pointed, (ii) K I ∩ K J = {0}, (iii) C I ∩ C J = ∅, (
iv) there exists a vector ξ ∈ A 0 such that max i∈I ξ T vi < min j∈J ξ T vj .

Proof.

[(i) ⇒ (ii)] We show the contrapositive. If there is v ∈ (K I ∩ K J ) \ {0}, then -v ∈ (-K I ) ⊆ cone((-K I ) ∪ K J ) and v ∈ K J ⊆ cone((-K I ) ∪ K J ). Therefore, cone((-K I ) ∪ K J ) is not pointed. [(ii) ⇒ (iii)] ∅ = A ∩ {0} = A ∩ K I ∩ K J [(ii)] = (A ∩ K I ) ∩ (A ∩ K J ) = C I ∩ C J . [(iii) ⇒ (iv)] We claim that C I is nonempty, convex and compact.
Indeed, since C I is nonempty (it contains the vectors vi for i ∈ I = ∅), convex (because K I and A are convex) and closed (because K I and A are closed), it suffices to show that C I is bounded or that its asymptotic cone (or recession cone in [60; p. 61]), namely

C ∞ I = K I ∩ A 0 , is reduced to {0} [60; theorem 8.4]. This is indeed the case since v T d > 0 for all v ∈ K I \{0} ⊆ K \ {0}.
For the same reason, C J is nonempty, convex and compact. Now, since C I ∩ C J = ∅ by (iii), one can strictly separate the convex sets C I and C J in A [60; corollary 11.4.2]: there exists ξ ∈ A 0 such that ξ T v < ξ T w, for all v ∈ C I and all w ∈ C J . This shows that (iv) holds.

[(iv)

⇒ (i)] Since cone((-K I ) ∪ K J ) = cone({-v i : i ∈ I} ∪ {v j : j ∈ J}), by proposi- tion 3.12, it suffices to find d (I,J) ∈ R n such that -v T i d (I,J) > 0, ∀ i ∈ I and v T j d (I,J) > 0, ∀ j ∈ J . (3.14)
By (iv) and the fact that θ

∈ (0, π) → cot θ ∈ R is surjective, one can determine θ ∈ (0, π) such that max i∈I ξ T v i v T i d < -cot θ < min j∈J ξ T v j v T j d . (3.15) Since sin θ > 0 for θ ∈ (0, π) and since v T k d > 0 for all k ∈ [1 : p], this is equivalent to max i∈I v T i [(cos θ)d + (sin θ)ξ] < 0 < min j∈J v T j [(cos θ)d + (sin θ)ξ].
Therefore, (3.14) is satisfied with d (I,J) := (cos θ)d + (sin θ)ξ.

One can now establish the link between the pointed cone problem of section 3.3.1 (problem 3.11) and the linearly separable bipartitioning problem (problem 3.14).

Equivalence 3.17 (pointed cone ↔ linearly separable bipartitioning) Let be given a matrix V ∈ R n×p with nonzero columns denoted by v 1 , . . . , v p and take s ∈ S, which is nonempty. By (3.12),

cone{s i v i : i ∈ [1 : p]} is pointed. Use the construction 3.15(1) with v i s i v i . For s ∈ {±1} p , define a partition (I, J) of [1 : p] by I := {i ∈ [1 : p] : si s i = -1} and J := {i ∈ [1 : p] : si s i = +1}.
Define also K I and K J by (3.13a) with v i s i v i . We claim that

cone{s i v i : i ∈ [1 : p]} is pointed ⇐⇒ ∃ ξ ∈ A 0 : max i∈I ξ T vi < min j∈J ξ T vj . (3.16)
Indeed, one has

cone{s i v i : i ∈ [1 : p]} is pointed ⇐⇒ cone{s i s i (s i v i ) : i ∈ [1 : p]} is pointed ⇐⇒ cone((-K I ) ∪ K J ) is pointed ⇐⇒ ∃ ξ ∈ A 0 : max i∈I ξ T vi < min j∈J ξ T vj ,
where we have used the equivalence (i) ⇔ (iv) of proposition 3.16 (v i s i v i ). The equivalence (3.16) establishes the expected equivalence between the pointed cone problem 3.11 (in which one looks for all the s ∈ {±1} p such that cone{s i v i : i ∈ [1 : p]} is pointed) and the linearly separable bipartitioning problem 3.14 of the vectors vi = s

i v i /(s i v T i d) = v i /(v T i d), i ∈ [1 : p],
where d is associated with the pointed cone cone{s i v i : i ∈ [1 : p]} by the equivalence (i) ⇔ (iii) of proposition 3.12.

Discrete geometry: hyperplane arrangements

The equivalent problem examined in this section has a long history, going back at least to the XIXth century [59,[START_REF] Steiner | Einige Gesetze über die Theilung der Ebene und des Raumes[END_REF]. More recently, it appears in Computational Discrete Geometry (the discipline has many other names), under the name of hyperplane arrangements. Contributions to this problem, or a more general version of it, with a discrete mathematics point of view, has been reviewed in [2,[START_REF] Edelsbrunner | Algorithms in Combinatorial Geometry[END_REF][START_REF] Grünbaum | Arrangements and Spreads[END_REF][START_REF] Halperin | Arrangements[END_REF][START_REF] Stanley | An introduction to hyperplane arrangements[END_REF]. It has many applications [START_REF] Černý | A class of optimization problems motivated by rank estimators in robust regression[END_REF][START_REF] Edelsbrunner | Constructing arrangements of lines and hyperplanes with applications[END_REF][START_REF] Helena | Hyperplane arrangements -Construction, visualization and application[END_REF]. Problem 3.18 (arrangement of hyperplanes containing the origin) Let be given two positive integers n and p ∈ N * and p nonzero vectors v 1 , . . . , v p ∈ R n . Consider the hyperplanes containing the origin:

H i := {d ∈ R n : v T i d = 0}. (3.17)
It is requested to list the regions of R n that are separated by these hyperplanes. Such a region is called a cell or a chamber, depending on the authors [2,[START_REF] Avis | Reverse search for enumeration[END_REF][START_REF] Helena | Output-sensitive cell enumeration in hyperplane arrangements[END_REF]. More specifically, let us define the half-spaces

H + i := {d ∈ R n : v T i d > 0} and H - i := {d ∈ R n : v T i d < 0}.
The problem is to determine the following set of open sectors or cells of R n , indexed by the bipartitions (I + , I -) of [1 : p]:

C := (I + , I -) ∈ B([1 : p]) : (∩ i∈I + H + i ) ∩ (∩ i∈I -H - i ) = ∅ , (3.18)
where B([1 : p]) denotes the set of bipartitions of [1 : p].

The link between problem 3.18 and the signed feasibility of strict linear inequality systems of section 3.2.1 is obtained from the bijection

η : (I + , I -) ∈ B([1 : p]) → s ∈ {±1} p , where s i = +1 if i ∈ I + , -1 if i ∈ I - (3.19)
and the setting Proof. Let (I + , I -) ∈ B([1 : p]) and s := η((I + , I -)). Then,

V = v 1 • • • v p ,
(I + , I -) ∈ C ⇐⇒ ∃ d ∈ (∩ i∈I + H + i ) ∩ (∩ i∈I -H - i ) ⇐⇒ ∃ d ∈ R n : (v T i d > 0 for i ∈ I + ) and (v T i d < 0 for i ∈ I -) ⇐⇒ ∃ d ∈ R n : s q V T d > 0 ⇐⇒ s ∈ S.
These equivalences show the bijectivity of η from C onto S. Equivalence 3.20 (signed linear system feasibility ↔ hyperplane arrangement) The equivalence between problems 3.2 and 3.18 follows from the bijection of the map η : C → S claimed in proposition 3.19.

Description of the B-differential

This section gives some elements of description of the B-differential ∂ B H(x), when H is the piecewise affine function given by (1.2) and x ∈ R n . This description is often carried out in terms of the matrix V defined by (3.1), whose p columns are denoted by v 1 , . . . , v p ∈ R n and are assumed to be nonzero. Some properties of ∂ B H(x) are given in section 4.1, including those that are useful in [START_REF] Dussault | Partial description of the Bdifferential of the componentwise minimum of two vector functions by linearization[END_REF]. Section 4.2 deals with the cardinal |∂ B H(x)| of the B-differential. Section 4.3 analyzes more precisely two particular configurations. Section 4.4 highlights two links between the B-differential and the C-differential of H.

Some properties of the B-differential

Let us start with a basic property of ∂ B H(x), which is its symmetry in the sense of definitions 2.4. This property has been observed by many in other contexts [2; § 1.1.4]. The equivalence 3.4 allows us to give a straightforward proof.

Proposition 4.1 (symmetry of ∂ B H(x)) Suppose that p > 0. Then, the B-differen- tial ∂ B H(x) is symmetric and |∂ B H(x)| is even.
Proof. Let J ∈ ∂ B H(x) and s := σ(J), where σ is defined by (3.3). By proposition 3.3, s q V T d > 0 is feasible for d. Now, (-s) q V T d > 0 is obviously also feasible for d (take the opposite of the previous d as solution), so that -s ∈ S. By the definition of the bijection σ : ∂ B H(x) → S, we see that J = σ -1 (s) and J := σ -1 (-s) are symmetric to each other in ∂ B H(x). This shows the symmetry of ∂ B H(x). It follows immediately that |∂ B H(x)| is even.

We now give a necessary and sufficient condition ensuring the completeness of ∂ B H(x) in the sense of definition 2.3. The condition was shown to be sufficient in [17; corollary 2.1(i)] for the nonlinear case (1.5), using a different proof, but we shall see in [START_REF] Dussault | Partial description of the Bdifferential of the componentwise minimum of two vector functions by linearization[END_REF] that it is an easy consequence of that property in the affine case (1.2). Thanks to the equivalence 3.4, the present proof is short.

Proof. [⇒]

We show the contrapositive. Assume that V is not injective, so that V α = 0 for some nonzero α ∈ R p . With s ∈ sgn(α), one can write

i∈[1 : p] |α i |s i v i = 0.
By Gordan's alternative (3.6), it follows that there is no d ∈ R n such that s q V T d > 0. By (3.2), this implies that s / ∈ S. According to the equivalence 3.4, σ -1 (s) / ∈ ∂ B H(x), showing that the B-differential is not complete.

[⇐] Assume the injectivity of V . Let s ∈ {±1} p . Since V T is surjective, the system V T d = s is feasible for d ∈ R n . For this d, s q V T d = e, so that s q V T d > 0 is feasible for d ∈ R n , so that the selected s is in S. We have shown that

S = {±1} p or that ∂ B H(x) = σ -1 ({±1} p ) (σ -1 is defined by (3.3b)) is complete.
We focus now on the connectivity of ∂ B H(x), a notion that is more easily presented in {±1} p but that can be transferred straightforwardly to ∂ B H(x) by the bijection σ defined in (3.3). Definition 4.3 (adjacency in {±1} p ) Two sign vectors s 1 and s 2 ∈ {±1} p are said to be adjacent if they differ by a single component (i.e., the vertices s 1 and s 2 of the cube co{±1} p can be joined by a single edge). Definitions 4.4 (connectivity in {±1} p ) A path of length l in a subset S of {±1} p is a finite set of sign vectors s 0 , . . . , s l ∈ S such that s i and s i+1 are adjacent for all i ∈ [0 : l -1]; in which case the path is said to be joining s 0 to s l . One says that a subset S of {±1} p is connected if any pair of points of S can be joined by a path in S.

Proof. [⇒]

We prove the contrapositive. Suppose that the columns v i and v j of V are colinear: v j = αv i , for some α ∈ R * . Assume that α > 0 (resp. α < 0). By (3.2), for any s ∈ S, one can find d ∈ R n such that s q V T d > 0, implying that s i = s j (resp. s i = -s j ). Therefore, one cannot find a path in S joining s ∈ S and -s ∈ S (proposition 4.1), since one would have to change the two components with index in {i, j} and that these components must be changed simultaneously for the sign vectors in S, while the adjacency property along a path prevents from changing more than one sign at a time.

[⇐] Let s and s ∈ S. It suffices to show that there is a path of length l in S joining s to s. By the expression (3.2) of S, one can find d and d ∈ R n such that

s q V T d > 0 and s q V T d > 0.
Note that, since the vectors {v i : i ∈ [1 : p]} are not colinear, by assumption, the vectors

{v i := v i /(v T i d) : i ∈ [1 : p]} are all different. Set ξ := d -d.
Since a small modification of d preserves the inequality s q V T d > 0 and since the vectors vi 's are all different, lemma 2.5 tells us that, at the cost of a small change of ξ, one can assume that

|{v T i ξ/(v T i d) : i ∈ [1 : p]}| = p. (4.2a) 20
Since, one could have added v 0 = 0 to the list of vectors v i 's, one can also assume that

v T i ξ = 0, ∀ i ∈ [1 : p]. (4.2b) Then, one can set t i := -(v T i d)/(v T i ξ), for i ∈ [1 : p],
which are p distinct values by (4.2a). It results that the following equivalent expressions hold for all i ∈ [1 : p]:

v T i d + t i v T i ξ = 0 or (1 -t i )v T i d + t i v T i d = 0 or v T i [(1 -t i )d + t i d] = 0. (4.2c)
For each i ∈ [1 : p], we are interested in the change of sign of v T i [(1t)d + t d] when t goes through the interval (0, 1) (i.e., when (1t)d + t d goes through the relative interior of the segment [d, d]). From the middle identity in (4.2c), we see that t i ∈ (0, 1) if and only if s i si = -1 (i.e., v T i d and v T i d have opposite signs). Therefore, the number of

t i ∈ (0, 1) is equal to l = i∈[1 : p] |s i -s i |/2 p. Let us denote them by 0 < t i 1 < . . . < t i l < 1. When t ∈ (0, 1) crosses a t j ∈ (0, 1), a single v T i [(1 -t)d + t d], for i ∈ [1 : p],
changes its sign (since all the t j 's are different, see the last identity in (4.2c)). Therefore, there are sign vectors s i j ∈ {±1} p , for j ∈ [1 : l], such that

s i j q V T [(1 -t)d + t d] > 0, for t ∈ (t i j , t i j+1 ),
and each of these sign vectors is different from the previous one by a single component (they are adjacent in the sense of definition 4.4). Therefore, we have defined a path of length l p in S, namely s i 0 = s, s i 1 , . . . , s i l = s, joining s to s. This proves the implication. This connectivity property is also stated in [2; section 1.10.4] as a simple observation with a very different point of view, related to graph theory. One can also give a proof of the implication "⇐" of proposition 4.5, using linearly separable bipartitioning (problem 3.14). This one consists in dragging a separating hyperplane, thus separating successively from 1 to l points from the others in a set of p points lying in an affine space. Let us give the details.

For k ∈ [1 : p], define ν k ∈ {±1} p by

ν k i := -1 if i = k, +1 otherwise. (4.3)
Hence, "ν k q " applied to a vector reverses the sign of its kth component. Another proof of proposition 4.5 [⇐]. Let s and s ∈ S. It suffices to show that there is a path of length l in S joining s to s.

The affine space A in which points vi are going to be seperated is given by the construction 3.15(1) with v i s i v i . This one yields a direction d, the affine space A := {v :

d T v = 1}, its associated vector space A 0 = {v : d T v = 0} and the vectors vi := s i v i /(s i v T i d) = v i /(v T i d) ∈ A for i ∈ [1 : p].
Let us now define a separating covector ξ ∈ A 0 . For this purpose, one introduces the following bipartition (I, J) of

v i : i ∈ [1 : p]} and cone{s i v i : i ∈ [1 : p]} are pointed. Now, cone{s i v i : i ∈ [1 : p]} = cone(K I ∪ K J ) and cone{s i v i : i ∈ [1 : p]} = cone((-K I ) ∪ K J ).
The pointedness of cone(K I ∪ K J ) and cone((-K I ) ∪ K J ) and the implication (i) ⇒ (iv) of proposition 3.16 imply that there exists a covector ξ ∈ A 0 such that ξ T vi < ξ T vj for all i ∈ I and j ∈ J. By their strictness, these inequalities, in finite number, are not modified by a small perturbation of ξ and, by lemma 2.5, ξ can be chosen such that all the ξ T vi for i ∈ one can assume that

ξ T vi 1 < ξ T vi 2 < • • • < ξ T vi l < ξ T vj 1 < ξ T vj 2 < • • • < ξ T vj p-l . (4.4b)
Let us now define the path in S from s to s. For k ∈ [0 : l], define s i k ∈ {±1} p as follows

s i 0 := s and s i k := ν i k q s i k-1 , for k ∈ [1 : l],
where ν k is defined by (4.3). We claim that s i 0 , s i 1 , . . . , s i l is a path of length l in S, that s = s i 0 and that s = s i l . This claim will prove the implication. The fact that (s i 0 , s i 1 , . . . , s i l ) is a path of length l in {±1} p is clear since s i k+1 is obtained from s i k by changing a single of its components (s i k and s i k+1 are adjacent in the sense of definition 4.4). Furthermore s = s i 0 by definition and s = s i l since s i l is obtained from s by changing the sign of all its components with index in I (definition of the i k 's). Hence, the path (s i 0 , s i 1 , . . . , s i l ) joins s to s. It remains to show that the s i k 's are in S. Define, for k ∈ [1 : l]:

α k := ξ T vi k + ξ T vi k+1 2 , I k := {i 1 , . . . , i k } and J k := [1 : p] \ I k .
By (4.4b), the hyperplane {v ∈ A : ξ T v = α k } separates the vectors {v i : i ∈ I k } and {v j : j ∈ J k } in A. Therefore, with the notation (3.13b), C I k ∩ C J k = ∅. By the implication (iii) ⇒ (i) of proposition 3.16, this implies that cone((-K I k ) ∪ K J k ) is pointed. By the implication (i) ⇒ (iii) of proposition 3.12, the system

-s i v T i d > 0 for i ∈ I k , s i v T i d > 0 for i ∈ J k has a solution d ∈ R n . By (3.
2), this amounts to saying that

s i k = (-s I k , s J k ) is in S, as expected. Definition 4.6 (extremality in {±1} p ) A point vk of a finite set V := {v i ∈ R n : i ∈ [1 : p]} of R n is said to be an extreme point of V if vk / ∈ co{v i : i ∈ [1 : p] \ {k}}.
The next proposition shows that the sign vectors (resp. the Jacobians in ∂ B H(x)) that are adjacent to a given s ∈ S (resp. to a given Jacobian σ -1 (s) ∈ ∂ B H(x)) are those of the form ν k q s, where ν k is defined by (4.3) and k ∈ [1 : p] is such that vk is an extreme point of the set of vectors vi (i ∈ [1 : p]) defined by the construction 3.15(1), with v i s i v i . Note that these vectors vi 's depend on s ∈ S by this construction. Proposition 4.7 (adjacency and extremality) Let s ∈ S and adopt the construction 3.15(1) with v i s i v i , which yields the set V := {v i : i ∈ [1 : p]}. For some k ∈ [1 : p], let ν k be defined by (4.3). Then, the following properties are equivalent:

(i) ν k q s ∈ S, (ii) vk is an extreme point of V.

Proof. Since s ∈ S, (3.12) implies that cone{s i v i : i ∈ [1 : p]} is pointed. Define s := ν k q s. We have the following equivalences

s ∈ S ⇐⇒ cone{s i v i : i ∈ [1 : p]} is pointed [(3.12)] ⇐⇒ vk / ∈ co{v i : i ∈ [1 : p] \ {k}} [(i) ⇔ (iii) in proposition 3.16] ⇐⇒ vk is an extreme point of V [definition].
For k ∈ [1 : p], we introduce

S k := {s ∈ {±1} k : ∃ d ∈ R n such that s i v T i d > 0 for i ∈ [1 : k]}. (4.5)
We also note S c k := {±1} k \ S k . Hence S = S p and S c = S c p . Point 1 of the next proposition will be used to motivate an improvement of algorithm 5.6 in section 5.2.5 and its points 2 and 3 will be used to get the equivalence in proposition 4.17, related to a fan arrangement. Proof.

1) If s ∈ S c k , there is no d ∈ R n such that s i v T i d > 0 for i ∈ [1 : k]. Therefore, there is no d ∈ R n such that (s i v T i d > 0 for i ∈ [1 : k]) and ±v T k+1 d > 0. Therefore, (s, ±1) ∈ S c k+1 . This implies that |S c k+1 | 2|S c k |.
2) Let P be the orthogonal projector on vect{v 1 , . . . , v k } ⊥ for the Euclidean scalar product. By assumption, P v k+1 = 0. Let s ∈ S k , so that there is a direction d ∈ R n such that

s i v T i d > 0 for i ∈ [1 : k]. For any t ∈ R and i ∈ [1 : k], the directions d ± := d ± t P v k+1 verify s i v T i d ± = s i v T i d > 0 (because v T i P v k+1 = 0).
In addition, for t > 0 sufficiently large, one has ±v T k+1 d ± = ±v T k+1 d + t P v k+1 2 > 0 (because P 2 = P and P T = P). We have shown that both (s, +1) and (s, -1) are in S k+1 . Therefore,

|S k+1 | 2|S k |. Now, |S k | + |S c k | = 2 k , |S k+1 | + |S c k+1 | = 2 k+1 and |S c k+1 | 2|S c k | by point 1. Therefore, one must have |S k+1 | = 2|S k | and |S c k+1 | = 2|S c k |. 3) We claim that one can find a direction d ∈ R n such that ∀ i ∈ [1 : k] : v T i d = 0 and v T k+1 d = 0. (4.6)
Let us show this by induction. One can find a direction

d 1 such that v T 1 d 1 = 0 and v T k+1 d 1 = 0 (otherwise N (v T 1 ) ⊇ N (v T k+1 ) or R(v 1 ) ⊆ R(v k+1
), which would imply that v k+1 and v 1 are colinear). Suppose now that, for some j ∈ [1 : k -1], one can find a direction d j ∈ R n such that v T i d j = 0 for i ∈ [1 : j] and v T k+1 d j = 0. Like above, one can find a direction p j ∈ R n such that v T j+1 p j = 0 and v T k+1 p j = 0 (because v k+1 and v j+1 are not colinear). Then, for ε > 0 sufficiently small,

d j+1 := d j + εp j satisfies v T i d j+1 = 0 for i ∈ [1 : j + 1] and v T k+1 d j+1 = 0. Taking s i := sgn(v T i d) for i ∈ [1 : k], one deduces from (4.6) that there is a direction d ∈ R n such that ∀ i ∈ [1 : k] : s i v T i d > 0 and v T k+1 d = 0. It follows that, for ε > 0 sufficiently small, the directions d ± := d ± εv k+1 satisfy ∀ i ∈ [1 : k] : s i v T i d ± > 0 and ± v T k+1 d ± > 0.
This means that (s, ±1) ∈ S k+1 . By symmetry (proposition 4.1), one also has (-s, ±1) ∈ S k+1 , so that we have found 4 vectors in S k+1 . Now, since, for any

s ′ ∈ S k \{±s} (in number |S k |-2), either (s ′ , +1) ∈ S k+1 or (s ′ , -1) ∈ S k+1 , it follows that |S k+1 | 4 + (|S k | -2) = |S k | + 2.

Cardinal of the B-differential

Winder's formula

Giving the exact number of elements in 1966] (see [START_REF] Stanley | Enumerative and algebraic combinatorics in the 1960's and 1970's[END_REF] for a recent and short review) and reads for the matrix V with nonzero columns given by (3.1)

∂ B H(x), that is |∂ B H(x)| = |S| = |C| = 2 p - |S c | = 2 p -|I|,
|∂ B H(x)| = I⊆[1 : p] (-1) null(V : ,I ) , (4.7)
where null(V : ,I ) is the nullity of V : ,I and the term in the right-hand side corresponding to I = ∅ is 1 (one takes the convention that null(V : ,∅ ) = 0). Note that, in this formula, the columns of V can be colinear with each other. This amazing expression, with its only algebraic nature, potentially made of positive and negative terms, is explicit but, to our knowledge, has not been at the origin of a method to list the elements of ∂ B H(x).

We give below a proof of (4.7) that follows the same line of reasoning as the one of Winder [START_REF] Winder | Partitions of N-space by hyperplanes[END_REF], but that is more analytic in that it uses the sign vectors introduced in section 3.2.1 rather than geometric arguments. The proof uses the following lemma of general interest. For k ∈ [1 : p -1], one defines

V k := V : ,[1 : k] , S(V k ) := {s ∈ {±1} k : ∃ d ∈ R n such that s i v T i d > 0, for i ∈ [1 :
k]} and denotes by P k+1 the orthogonal projector on v ⊥ k+1 . Below, P k+1 is also the matrix representation of the projector, hence P k+1 V k is the product of two matrices. The term "descendant" used in the following proposition will find an explanation in the algorithmic part of the paper, in section 5.2.3. Proposition 4.9 (sign vector with two descendants) Suppose that s ∈ S(V k ). Then, (s, +1) and (s, -1) ∈ S(V k+1 )

⇐⇒ ∃ d ∈ R n : s i v T i d > 0, for i ∈ [1 : k], and v T k+1 d = 0, (4.8a)
⇐⇒ s ∈ S(P k+1 V k ). (4.8b)

Proof. One has the following equivalences ((4.9a) and (4.9b) are justified afterwards):

(s, +1) and (s, -1) ∈ S(V k+1 )

⇐⇒ ∃ d + ∈ R n : s i v T i d + > 0, for i ∈ [1 : k], and +v T k+1 d + > 0 ∃ d -∈ R n : s i v T i d -> 0, for i ∈ [1 : k], and -v T k+1 d -> 0 ⇐⇒ ∃ d ∈ R n : s i v T i d > 0, for i ∈ [1 : k], and v T k+1 d = 0 (4.9a) ⇐⇒ ∃ d ∈ R n : s i (P k+1 v i ) T d > 0, for i ∈ [1 : k] (4.9b) ⇐⇒ s ∈ S(P k+1 V k ).
The equivalence in (4.9a) is shown as follows:

[⇒] d = (-v T k+1 d -)d + + (v T k+1 d + )d -∈ v ⊥ k+1 is appropriate; [⇐] take d ± = d ± εv k+1 for a sufficiently small ε > 0.
The equivalence in (4.9b) is shown as follows:

[⇒] d = P k+1 d (since v T k+1 d = 0) and P T k+1 = P k+1 (since P k+1 is an orthogonal projector), so that 0

< s i v T i d = s i v T i (P k+1 d) = s i (P k+1 v i ) T d; [⇐] take d := P k+1 d 0 in (4.9a)
, where d 0 is the d given by (4.9b).

Knowing a direction d such that s i v T i d > 0 for all i ∈ [1 : k], the equivalence (4.8a) questions the validity of the following equivalence (s, +1) and (s, -1) ∈ S(V k+1 )

? ⇐⇒ s i v T i (P k+1 d) > 0, for i ∈ [1 : k].
The implication "⇐" is certainly true by the implication "⇐" in (4.8a) (with d P k+1 d), but the reverse implication "⇒" is not true in general, as shown by the following counterexample.

Counter-example 4.10 (no double descendant test with

P k+1 d) Suppose that k = 1, v 1 = 1 1 , v 2 = 0 1 , s = +1 and d = -1 2 . One has indeed sv T 1 d = 1 > 0. Now, (s, ±1) ∈ S(V 2 ) since v T 1 d + = 1 > 0 and v T 2 d + = 2 > 0 with d + = d = -1 2 and v T 1 d -= 1 > 0 and -v T 2 d -= 1 > 0 with d -= 2 -1 . However, P 2 d = -1 0 , so that v T 1 P 2 d = -1 < 0.
Proof of (4.7) along Winder's proof [START_REF] Winder | Partitions of N-space by hyperplanes[END_REF]. The proof is by induction on p. The result is true for p = 1, since then the right-hand side of (4.7) is 2 (I can be ∅ and {1} and, in each of these cases, null(V : ,I ) = 0), which is indeed the number of regions seperated by the hyperplane v ⊥ 1 . Suppose now that the identity (4.7) holds for V k , with k ∈ [1 : p -1], and let us prove it for V k+1 . We do this in three steps.

1) Observe first that

|S(V k+1 )| = |S(V k )| + |S(P k+1 V k )|, (4.10a)
where P k+1 is the orthogonal projector on v ⊥ k+1 . Indeed, if s ∈ S(V k ), then (s, +1) and/or (s, -1) ∈ S(V k+1 ). According to proposition 4.9, the number of times both (s, +1) and (s, -1) are in S(V k+1 ) is |S(P k+1 V k )| and this brings 2|S(P k+1 V k )| elements to |S(V k+1 )|. As a result, the number of times only one descendant (s, +1) or (s, -1)

is in S(V k+1 ) is |S(V k )| - |S(P k+1 V k )| and this brings |S(V k )| -|S(P k+1 V k )| elements to |S(V k+1 )|. We conclude that |S(V k+1 )| = (2|S(P k+1 V k )|) + (|S(V k )| -|S(P k+1 V k )|) = |S(V k )| + |S(P k+1 V k )|.
2) We claim now that we can assume that, for any i ∈ [1 : k], v k+1 is not colinear to v i or, equivalently, P k+1 v i = 0. Suppose indeed that v k+1 is colinear to v i , for some i ∈ [1 : k]. One has

I⊆[1 : k+1] (-1) null(V : ,I ) = I⊆[1 : k] (-1) null(V : ,I ) + I⊆[1 : k+1] i / ∈I k+1∈I (-1) null(V : ,I ) + I⊆[1 : k+1] i∈I k+1∈I (-1) null(V : ,I ) .
The second term in the right-hand side is equal to the first one, since one has the same vectors (up to a multiplicative factor) by taking I ⊆ [1 : k + 1] with i / ∈ I and k + 1 ∈ I or by taking I ⊆ [1 : k]. Furthermore, the last term in the right-hand side is equal to

I⊆[1 : k] (-1) |I|+1-rank(V : ,I ) = - I⊆[1 : k] (-1) null(V : ,I ) .
Therefore, the last two terms in the right-hand side of the first identity cancel each other. In conclusion adding a vector v k+1 that is colinear to a previous v i does not modify the righthand side of (4.7), which is the expected behavior since such a vector does not modify S(V k ) and can be discarded.

3) By the induction assumption and the fact that V k and (P k+1 V k ) have k nonzero columns (by assumption and point 2), one has

|S(V k )| = I⊆[1 : k] (-1) null(V : ,I )
and

|S(P k+1 V k )| = I⊆[1 : k]
(-1) null((P k+1 V ) : ,I ) .

Therefore, due to (4.10a), the proof will be complete if we establish that Taking the orthogonal of both sides of (4.10c), one gets R(V : ,I∪{k+1} ) = R(P k+1 V : ,I ) + Rv k+1 .

I⊆[1 : k] (-1) null((P k+1 V ) : ,I ) = I⊆[1 : k+1] k+1∈I (-1) null(V : ,I ) . (4.10b) Let us show that, for I ⊆ [1 : k], N (V T : ,I∪{k+1} ) = N (V T : ,I P k+1 ) ∩ v ⊥ k+1 . ( 4
Since R(P k+1 V : ,I ) and Rv k+1 are orthogonal to each other, one deduces successively that rank(V : ,I∪{k+1} ) = rank(P k+1 V : ,I ) + 1,

|I ∪ {k + 1}| -null(V : ,I∪{k+1} ) = |I| -null(P k+1 V : ,I ) + 1, null(V : ,I∪{k+1} ) = null((P k+1 V ) : ,I ).
Using this last equality, we see that the identity (4.10b) holds.

Bounds

When The upper bound was already mentioned in proposition 2.2.

Recall that a function ϕ : x ∈ M → ϕ(x) ∈ R, defined on a metric space M, is said to be lower semicontinuous if, for any x ∈ M and any sequence {x k } converging to x, one has ϕ(x) lim inf k→∞ ϕ(x k ). It is known that the rank of a matrix can only increase in the neighborhood of a given matrix, which implies its lower semicontinuity. The next lemma shows that the same property holds for |S| ∈ N * , viewed as a function of V . Recall that the bijection σ is defined by (3.3).

Proposition 4.12 (lower semicontinuity of |∂

B H(x)|) Suppose that the set S = σ(∂ B H(x)) is viewed as a function of V ∈ R n×p given by (3.1). Then, S(V ) ⊆ S( Ṽ ) for Ṽ near V in R n×p . In particular, |∂ B H(x)| ∈ N * is a lower semicontinuous function of V ∈ R n×p .
Proof. Suppose that s ∈ S(V ). Then, by the definition (3.2) of S, s q V T d > 0 is feasible for d ∈ R n . Clearly, it follows that, for Ṽ near V , s q Ṽ T d > 0 is also feasible for d ∈ R n . Since S is finite, for any Ṽ near V and any s ∈ S, s q Ṽ T d > 0 is also feasible for d ∈ R n . We have shown that S(V ) ⊆ S( Ṽ ) for Ṽ near V .

As a direct consequence of this inclusion, we have that

|S(V )| |S( Ṽ )| for Ṽ near V . The lower semicontinuity of V → |∂ B H(x)| = |S| follows.
Proposition 4.2 established a necessary and sufficient condition to have completeness of ∂ B H(x). Here follows a less restrictive assumption, called general position, which is equivalent to have equality in (4.13) below. In connexion with this assumption, it is worth noting that, for a matrix V ∈ R n×p of rank r, one has

∀ I ⊆ [1 : p] : rank(V : ,I ) min(|I|, r).
V := v 1 • • • v p verifies ∀ I ⊆ [1 : p] : rank(V : ,I ) = min(|I|, r), (4.12)
where r := rank(V ).

This notion is used by Winder [START_REF] Winder | Partitions of N-space by hyperplanes[END_REF] when r = n; this is not a restriction since one can work in R(V ) rather than in R n , observe that the regions in R(V ) are the regions in R n , projected on R(V ), and that the assumption is satisfied in R(V ). The notion is also specific to arrangements of hyperplanes having a point in common; it has an adapted formulation otherwise [START_REF] Stanley | An introduction to hyperplane arrangements[END_REF].

Example of vectors in general position are those in the left-hand side and right-hand side panes in figure 3.1 (the points are the normalized vectors vi 's so that the v i 's are actually in R 3 ); note that in the first case 2 = r < n = 3. Those in the middle pane are not in general position. This is due to the fact that r := rank(V ) = 3 while for the 3 bottom vectors, with indices in I say, one has min(|I|, r)rank(V : ,I ) = 3 -2 = 0. Equality in the upper estimate (4.13) of the next proposition was shown by Winder [71;1966, corollary] when the columns of V are in general position and r = n, thanks to the identity (4.7). Long before him, the Swiss mathematician Ludwig Schläfli [62; p. 211] established the identity under the same assumptions, before 1852 [62; p. 174], without reference to (4.7), which was probably not known at that time. Note that equality does not hold in (4.13) for the middle configuration in figure 3.1 since |∂ B H(x)| = 12, while the right-hand side of (4.13) reads 2[ 3 0 + 3 1 + 3 2 ] = 14 (we have seen that the vectors in this pane are not in general position).

|∂ B H(x)| 2 i∈[0 : r-1] p -1 i , (4.13)
with equality if and only if (4.12) holds.

Proof. 1) The proof of the implication "(4.12) ⇒ (4.13) with equality" is established in [71; corollary], using the identity (4.7). For the reader's convenience, we give a proof with our notation. One has

|S| = I⊆[1 : p] (-1) null(V : ,I ) [Winder's formula (4.7)] = I⊆[1 : p] |I| r (-1) null(V : ,I ) + I⊆[1 : p] |I|>r (-1) null(V : ,I ) = I⊆[1 : p] |I| r 1 + I⊆[1 : p] |I|>r (-1) |I|-r [rank(V : ,I ) = min(|I|, r)] = i∈[0 : r] p i + i∈[r+1 : p] (-1) i-r p i = i∈[0 : p] p i -2 i∈{r+1,r+3,...} p i = 2   i∈[0 : p-1] p -1 i - i∈{r+1,r+3,...} p i   , (4.14a)
where the first sum in the brakets has the value 2 p-1 and the last sum in the brakets is zero if r = p. If r < p and pr is odd, the last sum in (4.14a) has at least the term p p = 1. If r < p and pr is even, then r + 1 p -1. With these particular cases in mind, one can evaluate the last sum in (4.14a) as follows i∈{r+1,r+3,...}

p i =            i∈{r+1,r+3,...,p-2} p -1 i -1 + p -1 i + 1 if p -r is odd i∈{r+1,r+3,...,p-1} p -1 i -1 + p -1 i if p -r is even = i∈[r : p-1]
p -1 i .

Using (4.14a), we get immediately (4.13) with equality.

2) Let us now show that (4.13) holds. Below, we systematically identify ∂ B H(x) and S, thanks to the equivalence 3.4. We also note S ≡ S(V ) to stress the dependence of S on V . Let β be the right-hand side of (4.13). We proceed by contradiction, assuming that there is a matrix

V ∈ R n×p such that |S(V )| > β. (4.14b)
It certainly suffices to show that one can find a sequence

{V k } ⊆ R n×p converging to V that satisfies |S(V k )| = β, (4.14c)
since then one would have the expected contradiction with the lower semicontinuity of V → |S(V )| ensured by proposition 4.12:

lim inf k→∞ |S(V k )| = β < |S(V )|.
To find V k arbitrarily close to V verifying (4.14c), we proceed as follows. Since (4.14b) holds, the first part of the proof implies that V does not satify (4.12). Our goal is to construct from V a matrix V k arbitrarily close to V with columns in general position and rank not exceeding r = rank(V ), hence satisfying (4.14c) by the first part of the proof. To get rank(V k ) r, we arrange for R(V k ) ⊆ R(V ).

In view of (4.11), since V does not satify (4.12), there is some I ⊆ [1 : p] such that rank(V : ,I ) < min(|I|, r). We consider two complementary cases.

r If |I| < r, then, for an arbitrary small perturbation of the vectors v i ṽi , with i ∈ I, one can get the ṽi 's linearly independent in R(V ). If one takes ṽi = v i for i / ∈ I, the matrix Ṽ formed of the vectors ṽi 's verifies rank( Ṽ:,I ) = |I| = min(|I|, r).

r If |I| r, then, for an arbitrary small perturbation of the vectors v i ṽi , with i ∈ I, one can get the ṽi 's generate R(V ), which is of dimension r. If one takes ṽi = v i for i / ∈ I, the matrix Ṽ formed of the vectors ṽi 's verifies rank( Ṽ:,I ) = r = min(|I|, r).

The perturbation of V : ,I into Ṽ:,I also perturbs V : ,I ′ for other index sets I ′ ⊆ [1 : p]. However, one has rank( Ṽ:,I ′ ) min(|I ′ |, r) by (4.11) and R( Ṽ ) ⊆ R(V ). Now, by the property of the rank, which can only increase in a neighborhood of a given matrix, if the perturbation taken above is sufficiently small, one has rank(V : ,I ′ ) rank( Ṽ:,I ′ ) min(|I ′ |, r) for any

I ′ ⊆ [1 : p].
Therefore, rank(V : ,I ′ ) = min(|I ′ |, r) implies that rank( Ṽ:,I ′ ) = min(|I ′ |, r). As a result, the modification of V to get Ṽ described above increases by at least one the number of intervals I ′ ⊆ [1 : p] such that rank( Ṽ:,I ′ ) = min(|I ′ |, r). Since the number of such intervals is finite, proceeding similarly with all the nonempty index sets I ′′ ⊆ [1 : p] such that rank( Ṽ:,I ′′ ) < min(|I ′′ |, r), one finally obtains a matrix V k , arbitrary close to V , such that (4.12) holds: rank((V k ) : ,I ) = min(|I|, r) for all I ⊆ [1 : p]. By taking smaller and smaller perturbations of V , one also has V k → V .

3) One still has to show that "(4.13) with equality ⇒ (4.12)". We proceed by contradiction, assuming that (4.13) holds with equality for ∂ B H(x) = σ -1 (S) and V given by (3.1), but that (4.12) does not hold. By (4.11), there exists I ⊆ [1 : p] such that rank(V : ,I ) < min(|I|, r).

(4.14d)

Let β be the right-hand side of (4.13). It certainly suffices to show that, thanks to (4.14d), one can find a matrix Ṽ ∈ R n×p such that rank( Ṽ ) r and |S( Ṽ )| > β, since this would be in contradiction with what has been shown in part 2 of the proof. This matrix Ṽ is obtained by perturbing V . By proposition 4.12, if the perturbation is sufficiently small, one has S(V ) ⊆ S( Ṽ ), so that it suffices to show that S( Ṽ ) contains a sign vector s that is not in S(V ).

We claim that (4.14d) implies that one can find an index set J ⊆ I such that

V : ,J is not injective and |J| r. (4.14e)
Indeed, if |I| r, one can take J = I to satisfy (4.14e), since rank(V : ,I ) < |I| by (4.14d), so that V : ,I is not injective. If |I| > r, then rank(V : ,I ) < r by (4.14d), which implies that any J ⊆ I such that |J| = r satisfies (4.14e). Since V : ,J is not injective, one can find α J ∈ R J \ {0} such that

0 = j∈J α j v j = j∈J sj |α j |v j ,
for some sJ ∈ {±1} J satisfying sj ∈ sgn(α j ) for all j ∈ J. Then, by Gordan's alternative (3.6),

∄ d ∈ R n : sj v j d > 0, for all j ∈ J.
This implies that there is no s ∈ S(V ) such that s J = sJ . To conclude the proof, it suffices now to show that one can construct an arbitrary small perturbation Ṽ of V , such that R( Ṽ ) ⊆ R(V ) and with an s ∈ S( Ṽ ) satisfying s J = sJ . Let J c := [1 : p] \ J. By (4.14e), |J| r n so that one can find vectors {ṽ j : j ∈ [1 : p]}, such that ṽj = v j for j ∈ J c , the vectors {ṽ j : j ∈ J} are linearly independent, ṽjv j is arbitrary small and {ṽ j : j ∈ [1 : p]} ⊆ R(V ). Since the vectors {ṽ j : j ∈ J} are linearly independent, one can find a direction d 0 ∈ R n such that ṽT j d 0 = sj for j ∈ J, hence

sj ṽT j d 0 > 0, ∀ j ∈ J.
Let d be a discriminating vector given by lemma 2.5 (with an additional v 0 = 0, v i si ṽi and ξ d) sufficiently close to d 0 . It results that sj ṽT j d > 0 for j ∈ J and sj ṽT j d = 0 for j ∈ J c . Finally, we see that the sign vector s ∈ {±1} p defined by s i = sgn(ṽ T i d) for all i ∈ [1 : p] is in S( Ṽ ) and satisfies s J = sJ , as desired.

Particular configurations

We consider in this section some particular matrices V given by (3.1), which may be useful to get familiar with the B-differential of H. For these V 's, |∂ B H(x)| can be computed easily. We consider two matrices V with the property that r := rank(V ) takes the value 2 or p; they yield the lower and upper bounds on |∂ B H(x)| given by proposition 4.11. The lower bound 2p applies to the left-hand side pane of figure 3

rank(V : ,I ) = |I| if |I| 2 2 if |I| > 2.
Therefore (4.12) holds. By proposition 4.14, this implies that equality holds in (4.13), that is, with r = 2:

|∂ B H(x)| = 2 i∈[0 : 1] p-1 i = 2p. [⇐]
The rank(V ) =: r cannot be 1, since p 2 and the v i 's are not two by two colinear. We proceed by contradiction, assuming the r > 2. Then, one can find k ∈ Another proof of proposition 4.17[⇒] using the bipartitioning of section 3.3.2. Let s ∈ S, so that cone{s i v i : i ∈ [1 : p]}, called the original cone in this proof, is pointed by (3.12). Adopt the construction 3.15 (with s i s i v i ). Since r = 2, the vectors vi 's are arranged along a line and one can assume that v1 , . . . , vp follow each other in that order along this line (the vi 's are all different since the v i 's are not colinear). The proposed proof consists in determining the complementary set of S in {±1} p . By proposition 3.16, this amounts to identifying the partitions (I, J) ∈ B([1 : p]) such that K I ∩ K J = {0} (then, the inversion of the vectors {v i } i∈I does not preserve the pointedness of the resulting cone, implying that (-s I , s J ) / ∈ S and σ -1 ((-s I , s J )) / ∈ ∂ B H(x)). Clearly, any group of k vectors, with k ∈ [1 : p -1], that is not one of the sets {v 1 , . . . , vk } and {v p-k+1 , . . . , vp } cannot be linearly separated from the other vectors and there are

p k - 2
such groups. Hence, the total number of groups of vectors, whose inversion does not yield a pointed cone, is

k∈[1 : p-1] p k -2 = (2 p -2) -2(p -1) = 2 p -2p, ( 4

A glance at the C-differential

The section presents two links between the B-differential and the C-differential of the function H given by (1.2). The first proposition tells us that, whilst ∂ C H(x) can be obtained from ∂ B H(x) by taking its convex hull (it is its definition (1.1)), the latter can be obtained from the former by taking its extreme points. Proof. Observe first that, since S given by (3.2) is contained in {±1} p , one has S = ext(co S). To get the result, it suffices now to carry this identity into R p×n thanks to the affine map τ : R p → R p×n defined at s ∈ R p by

τ (s) = 1 2 (I -Diag(s))B E = (x), : + (I + Diag(s))A E = (x), :
. The result now follows from the fact that τ

The restriction of τ to S is τ | S = σ -1 ,
(S) = σ -1 (S) = ∂ B H(x) (proposition 3.3) and ∂ C H(x) = co ∂ B H(x).
The second proposition restates theorem 2.2 of Chen and Xiang [17; 2011], which applies to the more general nonlinear function (1.5). The interest of this restatement comes from its proof that is short, thanks to the use of the symmetry of the B-differential (proposition 4.1), and from the fact that proposition 4.19 can be used, straightforwardly, to recover Chen and Xiang's Jacobian, when H is given by (1.5); see [START_REF] Dussault | Partial description of the Bdifferential of the componentwise minimum of two vector functions by linearization[END_REF]. Recall the notation (2.2) of the index sets.

Proposition 4.19 (a particular C-Jacobian) One has J ∈ ∂ C H(x) for the Jacobian whose ith row, i ∈ [1 : m], is defined by

J i, : =    A i, : if i ∈ A(x), 1 2 [A i, : + B i, : ] if i ∈ E(x), B i, : if i ∈ B(x).
Proof. Let M ∈ ∂ B H(x), which is known to be nonempty. By proposition 2.2, M i, : = A i, : for i ∈ A(x), M i, : = B i, : for i ∈ B(x) and M i, : = A i, : = B i, : for i ∈ E = (x). By the symmetry of

∂ B H(x) (proposition 4.1), M ′ defined by M ′ : ,i = M : ,i if i ∈ A(x) ∪ E = (x) ∪ B(x)
and by

M ′ i, : = B i, : if i ∈ E = (x) and M i, : = A i, : A i, : if i ∈ E = (x) and M i, : = B i, : is also in ∂ B H(x). Therefore, J = (M + M ′ )/2 is in co ∂ B H(x) = ∂ C H(x)
, by (1.1). This is the formula of J given in the statement of the proposition.

Instead of taking J 1/2 := 1 2 (M + M ′ ) in the preceeding proof, one could also have taken

J t := (1-t)M +tM ′ , which is also in co ∂ B H(x) = ∂ C H(x) for any t ∈ [0, 1].
The inconvenient of this latter choice, when t = 1/2, is that M is usually not known. In particular, it is not necessarily known whether M i, : may be A i, : or B i, : , for a particular i ∈ E = (x), while J t depends on this value when t = 1/2. In contrast, J 1/2 has an explicit formula that does not require the knowledge of the value of M i, : for i ∈ E = (x).

Computation of the B-differential

This section describes techniques to compute a single Jacobian (section 5.1) or all the Jacobians (section 5.2) of the B-differential ∂ B H(x), in exact arithmetic, when H is the piecewise affine function given by (1.2). The complexity of a proposed algorithm for computing ∂ B H(x) is also analyzed. Let us mention that, once the B-differential is known, it is possible to verify whether a particular Jacobian J is in the C-differential ∂ C H(x) by checking whether J is a convex combination of the elements of ∂ B H(x), which can be realized by checking the compatibillity of a linear system with inequalities. The piece of software isf has been written to test the algorithms.

Computation of a single Jacobian

An interest of the problem equivalence highlighted in proposition 3.3(3) is to provide a method to find rapidly an element of ∂ B H(x), which complements Qi's [55; 1993, final remarks (1)]. It is shown in [START_REF] Dussault | Partial description of the Bdifferential of the componentwise minimum of two vector functions by linearization[END_REF], that this method extends to the computation of an element of the Bdifferential in the nonlinear case, i.e., when H is given by (1.5). The method is based on the following algorithm, which associates with p nonzero vectors v 1 , . . . , v p , which may be identical or colinear, a direction d such that v T i d = 0 for all i ∈ [1 : p]; it is a variant of the technique used in the proof of [17; lemma 2.1]. When the v i 's are also distinct, the direction d can also be derived from lemma 2.5, by adding the vector v 0 = 0. Algorithm 5.1 (computes d ∈ R n such that v T i d = 0 for all i) Let be given p nonzero vectors v 1 , . . . , v p in R n and take d ∈ R n \ {0}. Repeat:

1. If I := {i ∈ [1 : p] : v T i d = 0} = ∅, exit. 2. Let i ∈ I. 3. Take t > 0 sufficiently small such that, for all j / ∈ I, (v T j d)(v T j [d + tv i ]) > 0. 4. Update d := d + tv i .
Explanation. In step 3, any sufficiently small t > 0 is appropriate (the proof of [17; lemma 2.1] computes bounds explicitely), since

(v T j d)(v T j [d+tv i ]) is positive for t = 0. The new direction d set in step 4 is such that v T i (d + tv i ) = t v i 2
> 0, so that this direction makes at least one more v T j d nonzero than the previous one. This implies that the algorithm finds an appropriate direction in at most p loops.

The next procedure uses a direction d computed by algorithm 5.1 to obtain a single element of ∂ B H(x). Recall that the map σ is defined by (3.3a) and is a bijection from ∂ B H(x) onto S, defined by (3.2) (proposition 3.3).

Computation of all the Jacobians

This section presents several algorithms, and some variants, for computing all the B-differential of H. They use the notion of S-tree presented in section 5.2.2(A). The brute force algorithm of section 5.2.1 is out of the game due to its lack of efficiency, but it can be used to get a relatively safe list of all the elements of ∂ B H(x). The second algorithm is grounded on the notion of stem vector (section 3.2.2) and is described in section 5.2.3. The third algorithm is the culmination of a series of improvements brought to an algorithm by Rada and Černý [57; 2018] (section 5.2.2(B)) for computing the cells of a hyperplane arrangement, which is known to be an equivalent problem to the one of computing the B-differential of H when the hyperplanes contain zero (see section 3.4). The improvements are detailed in section 5.2.5 and the resulting algorithm is described in section 5.2.6. Finally, numerical experiments are presented in section 5.2.8 to compare the efficiency of the algorithms.

Algorithms for listing the elements of the finite set ∂ B H(x) can be designed by looking at one of the various forms of the problem, those described in section 3 and others [START_REF] Avis | Reverse search for enumeration[END_REF]; this is what we shall do. Nevertheless, the only algorithms we have found in the scientific literature take the point of view of hyperplane arrangements of section 3.4 and can usually be used for more general arrangements than those needed to describe ∂ B H(x) (i.e., in which case the hyperplanes pass through zero). One can quote the contributions by Bieri and Nef [12; 1982], Edelsbrunner, O'Rourke and Seidel [31; 1986], Avis and Fukuda [5; 1996], improved Sleumer [63; 1998], and, more recently, Rada and Černý [57; 2018], which is described in section 5.2.2(B).

Brute-force algorithm

We call brute-force algorithm the one that uses the sign system feasibility formulation of section 3.2.1 and examines all the sign vectors s ∈ {±1} p that make the system s q V T d > 0 feasible for d ∈ R n , where V is defined by (3.1). Recall the map σ defined by (3.3). Algorithm 5.3 (brute-force) For each s ∈ {±1} p , determine whether s q V T d > 0 is feasible for d ∈ R n . If so, select s as one element of S or, equivalently, σ -1 (s) as one element of ∂ B H(x).

Since the feasibility of s q V T d > 0 in d is equivalent to the one of s q V T d e, this problem can be solved by considering the feasible linear optimization (LO) problem min (d,t)∈R n ×R {t ∈ [-1, ∞]) : s q V T d + te 0} (one has s ∈ S if and only if the problem has a feasible point (d, t) with t < 0, hence the minimization should not be undertaken to completion). Algorithm 5.3 requires to solve approximately 2 p LO problems with n + 1 variables and p constraints. We use this expensive algorithm in the numerical experiments to have a reference list of the elements of S for each test-problem.

Incremental-recursive algorithms

The algorithms described in this section are incremental in the sense that the considered sign vectors have their length increased by one at each step. Furthermore, the algorithms explore the S-tree described in subsection A below by recursive procedures, whose names are recognizable by their suffix "-rec". All the procedures end by returning to their calling program.

A. The S-tree

A common feature of the algorithms considered in this paper is the construction of the S-tree described below, incrementally and recursively. This idea was probably introduced by Rada and Černý [57; 2018].

The level k of the S-tree is formed of a set of sign vectors denoted by

S 1 k := {s ∈ S k : s 1 = +1}
, where S k is the subset of {±1} k defined by (4.5). In particular, the level 1 or root of the S-tree contains the unique sign vector +1 ∈ {±1} 1 . There is indeed no reason to compute {s ∈ S : s 1 = -1} since this part of S is equal to -{s ∈ S : s 1 = 1} by the symmetry property of S (proposition 4.1). The S-tree has p levels, where p is the number of vectors v i , or columns of the given matrix V ∈ R n×p . In order to avoid the memorization of the elements of S 1 k , the S-tree is constructed by a depth-first search, which can be schematized as follows.

Algorithm 5.4 (stree) Let be given V ∈ R n×p , with n and p ∈ N * , having nonzero columns.

1. Execute the recursive procedure stree-rec(V, +1). Algorithm 5.5 (stree-rec) Let be given V ∈ R n×p , with n and p ∈ N * , having nonzero columns, and a sign vector

s ∈ S 1 k for some k ∈ [1 : p]. 1. If k = p, print s and return. 2. If (s, +1) ∈ S 1 k+1 , execute stree-rec(V, (s, +1)). 3. If (s, -1) ∈ S 1
k+1 , execute stree-rec(V, (s, -1)).

The method used to determine whether (s, ±1) is in S 1 k+1 depends on the specific algorithm and may or may not use a direction d intervening in (4.5). Note that, as emphasized in proposition 4.8(3), at least one of the sign vectors (s, +1) and (s, -1) belongs to S 1 k+1 (maybe both). It is justified not to explore the S-tree below an (s, ±1) that is not in S 1 k+1 , since then (s, ±1, s ′ ) / ∈ S for any s ′ ∈ {±1} p-k-1 . By construction, the algorithm stree prints all the elements of S 1 p ≡ S 1 := {s ∈ S : s 1 = +1} in step 1 of the stree-rec procedure.

B. Rada and Černý's algorithm

The algorithm proposed by Rada and Černý [57; 2018], which is referenced below as the rc algorithm, deals with the determination of the cells associated with a general hyperplane arrangement. We describe it below for an arrangement that results from the computation of the B-differential ∂ B H(x), whose hyperplanes all contain zero (see section 3.4). We also use the linear algebra language of section 3.2.1, viewing the problem as the one of determining the set S of sign vectors s ∈ {±1} p such that s q V T d > 0 is feasible for d ∈ R n (V is the matrix defined by (3.1)); in contrast, the language used in [START_REF] Rada | A new algorithm for enumeration of cells of hyperplane arrangements and a comparison with Avis and Fukuda's reverse search[END_REF] is more geometric. The algorithm builds the S-tree of the previous section A and, for each s ∈ S 1 k , it solves a single LO problem to determine whether (s, +1) or (s, -1) is in S 1 k+1 . The rc algorithm succeeds in solving only one LO problem to determine whether (s, +1) and (s, -1) are in S 1 k+1 , at the node s ∈ S 1 k , thanks to the memorization of a direction d such that s q V T k d > 0 (we note

V k := V : ,[1 : k]
). Indeed, one has

v T k+1 d < 0 =⇒ (s, -1) ∈ S 1 k+1 , v T k+1 d > 0 =⇒ (s, +1) ∈ S 1 k+1 ,
and one of these two cases takes place if we exclude the case where v T k+1 d = 0. In [57; Algorithm 1], the case where v T k+1 d = 0 is not dealt with completely since (s, +1) is declared to belong to S 1 k+1 in that case, while it is clear that (s, -1) is also in S 1 k+1 . Indeed, in our implementation of the rc algorithm, we modify slightly d by adding a small positive or negative multiple of v k+1 to d when v T k+1 d = 0, so that both (s, ±1) are accepted in S 1 k+1 in that case. This choice may be at the origin of the differences that one observes in table 5.1 below between the statistics of the original rc algorithm in [START_REF] Rada | A new algorithm for enumeration of cells of hyperplane arrangements and a comparison with Avis and Fukuda's reverse search[END_REF] and those of our implementation.

Next, when (s, s k+1 ) ∈ {±1} k+1 is observed to belong to S 1 k+1 , the question of whether (s, -s k+1 ) also belongs to S 1 k+1 arises. In the rc algorithm, the answer to this question is obtained by solving a LO problem similar to

       min (d,t)∈R n ×R t s i v T i d 1, ∀ i ∈ [1 : k] -s k+1 v T k+1 d -t t -1.
(5.1) When s ∈ S 1 k , this problem is feasible (take d satisfying s i v T i d 1, for all i ∈ [1 : k], and t sufficiently large) and bounded (its optimal value is -1), so that it has a solution [START_REF] Bonnans | Optimisation Numérique -Aspects théoriques et pratiques[END_REF][START_REF] Bonnans | Numerical Optimization -Theoretical and Practical Aspects[END_REF][START_REF] Chvátal | Linear Programming[END_REF][START_REF] Ch | Selected Topics on Continuous Optimization -Version 2[END_REF]. Solving these LO problems is a time consuming part of the algorithms and in the numerical experiments of section 5.2.8, in particular in table 5.2, following [START_REF] Rada | A new algorithm for enumeration of cells of hyperplane arrangements and a comparison with Avis and Fukuda's reverse search[END_REF], we measure the efficiency of the algorithms by the number of LO problems they solve.

One can now formally describe our version of the rc algorithm (the change is in step 2 of the rc-rec algorithm, which is not considered in the original rc algorithm). Algorithm 5.6 (rc) Let be given V ∈ R n×p , with n and p ∈ N * , having nonzero columns.

1. Execute the recursive procedure rc-rec(V, v 1 , +1).

  0, min i∈[1 : k] s i v T i v k+1 <0 -v T i d v T i v k+1    .
2.2. Execute rc-rec(V, d -, (s, -1)), where

d -:= d + t -v k+1 with t -< 0 chosen in the nonempty open interval    max i∈[1 : k] s i v T i v k+1 >0 -v T i d v T i v k+1 , 0    . 3. Else s k+1 := sgn(v T k+1 d). 3.1. Execute rc-rec(V, d, (s, s k+1 )). 3.2.
Solve the LO problem (5.1) and denote by (d, t) a solution.

If t = -1, execute rc-rec(V, d, (s, -s k+1 )).

The test v T k+1 d ≃ 0 done at the beginning of step 2 is supposed to take into account floating point arithmetic. In steps 2.1 and 2.2, the minimum and maximum are supposed to be infinite if their feasible set is empty. It is easy to see that the directions d ± computed in steps 2.1 and 2.2 are such that s i v T i d ± > 0 for i ∈ [1 : k + 1] and s k+1 = ±1, which justifies the recursive call to rc-rec with the given arguments. The most time-consuming part of the rc algorithm comes from the possible numerous LO problems to solve in step 3.2 of rc-rec.

An algorithm using stem vectors

When s ∈ S k , it is conceptually easy to check whether (s, ±1) is in S k+1 , provided a list of all the stem vectors associated with V is known. Indeed, by proposition 3.9, if no subvector of (s, +1) (resp. (s, -1)) is a stem vector, then (s, +1) (resp. (s, -1)) belongs to S k+1 . Note also that, because any s ∈ S k has at least one descendant in the S-tree (proposition 4.8(3)), if it is observed that (s, +1) / ∈ S k+1 , then, necessarily, (s, -1) ∈ S k+1 . This observation prevents the algorithm from checking whether (s, -1) contains a stem vector, which is a time consuming operation when the list of stem vectors is large. For future reference, we formalize this algorithm below. Algorithm 5.8 (stem) Let be given V ∈ R n×p , with n and p ∈ N * , having nonzero Let σ i , i ∈ [1 : k + 1], be the multipliers associated with the first k + 1 constraints of (5.1) and τ be the multiplier associated with its last constraint. Then, the Lagrangian dual of (5.1) reads [START_REF] Bertsekas | Nonlinear Programming[END_REF][START_REF] Bonnans | Optimisation Numérique -Aspects théoriques et pratiques[END_REF][START_REF] Bonnans | Numerical Optimization -Theoretical and Practical Aspects[END_REF][START_REF] Ch | Fragments d'Optimisation Différentiable -Théorie et Algorithmes[END_REF]]

             max (σ,τ )∈R k+1 ×R i∈[1 : k] σ i -τ σ 0 τ 0 σ k+1 + τ = 1 σ k+1 s k+1 v k+1 = i∈[1 : k] σ i s i v i . ≡          max σ∈R k+1 i∈[1 : k+1] σ i -1 σ 0 σ k+1 1 σ k+1 s k+1 v k+1 = i∈[1 : k] σ i s i v i , (5.2)
where the second form of the dual is obtained by eliminating τ from the first form. By strong duality in linear optimization, the dual problems in (5.2) are feasible, have a solution and have the same optimal value as the primal problem. Let (σ, τ ) ∈ R k+1 × R be a dual solution. Then, (s, -s k+1 ) ∈ S k+1 if and only if t = -1 if and only if i∈[1 : k] σ i = 0 and σ k+1 = 0. We have shown that (s, -s k+1 ) ∈ S k+1 ⇐⇒ σ = 0.

Therefore, (s, -s k+1 ) / ∈ S k+1 if and only if σ = 0 if and only if σ k+1 = 1 (if σ k+1 = 0, one can make the dual objective value as large as desired by multiplying σ by a factor going to +∞; if σ k+1 ∈ (0, 1), the dual objective would by increased by replacing σ by σ/σ k+1 ; in both cases the optimality of σ would be contradicted) if and only if τ = 0. We have shown that

(s, -s k+1 ) / ∈ S k+1 ⇐⇒ s k+1 v k+1 ∈ cone{s i v i : i ∈ [1 : k]}.
The next proposition shows how a matroid circuit can be detected from the dual solution σ when (s, -s k+1 ) / ∈ S k+1 .

Proposition 5.10 (matroid circuit detection) Suppose that (s, -s k+1 ) / ∈ S k+1 and that (σ, τ ) is a solution to the dual problem in the left-hand side of (5.2) located at an extreme point of its feasible set. Then, {i ∈ [1 : k + 1] : σ i > 0} is a matroid circuit of V .

Proof. Necessarily, τ = 0 and σ k+1 = 1 when (s, -s k+1 ) / ∈ S k+1 . The fact that (σ, 0) is an extreme point of the feasible set of the problem in the left-hand side of (5.2) implies that the vectors [START_REF] Chvátal | Linear Programming[END_REF][START_REF] Ch | Fragments d'Optimisation Différentiable -Théorie et Algorithmes[END_REF]

0 s i v i i∈[1 : k], σ i >0 , 1 -s k+1 v k+1
are linearly independent.

In particular, the vectors

{s i v i : i ∈ [1 : k], σ i > 0} are linearly independent. Since s k+1 v k+1 = i∈[1 : k] σ i s i v i , it follows that {s i v i : i ∈ [1 : k + 1], σ i > 0} has nullity one.
The conclusion of the proposition follows from proposition 3.10.

Recall that the dual-simplex algorithm finds a dual solution at an extreme point of the dual feasible set. For this reason, we use this approach in the isf algorithm.

{±1} k verifies s q V T k d > 0, that v k+1 = 0 and that max i∈[1 : k] s i v T i v k+1 >0 -v T i d v T i v k+1 < -v T k+1 d v k+1 2 < min i∈[1 : k] s i v T i v k+1 <0 -v T i d v T i v k+1
.

(5.5)

1) The direction d

+ := d + t + v k+1 verifies s q V T k d + > 0 and v T k+1 d + > 0 if and only if t + is in the nonempty open interval    -v T k+1 d v k+1 2 , min i∈[1 : k] s i v T i v k+1 <0 -v T i d v T i v k+1    .
(5.6a)

2) The direction

d -:= d + t -v k+1 verifies s q V T k d -> 0 and -v T k+1 d -> 0 if and only if t -is in the nonempty open interval    max i∈[1 : k] s i v T i v k+1 >0 -v T i d v T i v k+1 , -v T k+1 d v k+1 2    .
(5.6b)

Proof. Clearly, (5.5) implies that the open intervals (5.6a) and (5.6b) are nonempty. The direction d + := d + t + v k+1 verifies s q V T k d + > 0 and v T k+1 d + > 0 if and only if

s i v T i (d + t + v k+1 ) > 0, ∀ i ∈ [1 : k] and v T k+1 (d + t + v k+1 ) > 0.
(5.7a) This is equivalent to taking t + in the interval (5.6a).

The direction d -:= d + t -v k+1 verifies s q V T k d -> 0 and -v T k+1 d -> 0 if and only if

s i v T i (d + t -v k+1 ) > 0, ∀ i ∈ [1 : k] and -v T k+1 (d + t -v k+1 ) > 0. (5.7b)
This is equivalent to taking t -in the interval (5.6b).

C. Changing the order of the vectors v i 's

Each node s of the S-tree described in section 5.2.2(A) has one or two descendants: (s, +1) and/or (s, -1). Since there is at most one LO problem solved per node of the S-tree, decreasing the number of nodes should decrease the number of LO problems to solve, which significantly count in the computing time. To reach that goal, one can try to get as much as possible at the top of the tree the nodes having a single descendant. As shown below, this can be achieved by changing the order in which the vectors v i 's, the columns of V , are considered in the depth-first search of the tree; previously, the order was imposed by the modification A, taking into account the rank of V .

To implement this strategy, one associates with each node s ∈ S 1 k of the S-tree, k ∈ [1 : p -1], the list of vectors considered so far at that node, denoted by T s := {i 1 , . . . , i k } ⊆ [1 : p]. Hence, we have to choose the next vector v i k+1 be selecting an index i k+1 in T c s := [1 : p] \ T s . Now, a natural idea is to restrict the set of possible indices to T b s , the set of indices j of T c s for which one of the intervals (5.6a) or (5.6b), with v k+1 ≡ v j , is empty (implying that the technique used in the modification B will not give two descendants), if there is such an index, or T c s otherwise. To determine the index in T b s , we take

i k+1 = arg max i∈T b s |v T i d| v i , (5.8)
which favors the vectors v i for which |v T i d|/ v i is away from zero. As table 5.2 indicates (section 5.2.8(C.3)), this modification has a significant impact on the decrease of LO to solve.

D. Using stem vectors

We present in this section various modifications that use the concept of stem vector, introduced in the second part of section 3.2.2. These stem vectors are used to detect infeasible sign vectors, i.e., elements of S c , thanks to proposition 3.9. If s ∈ S 1 k and (s, s k+1 ) ∈ S c for s k+1 ∈ {±1}, s has no descendant in S along (s, s k+1 ), so that this part of the S-tree does not need to be explored. From this point of view, computing all the stem vectors looks attractive, but, to our knowledge, this is a time consuming process, so that this option is not necessarily the most efficient one. The modifications presented below use more and more stem vectors, which require more and more computing time. D 1 ) Natural candidates as stem vectors are those obtained from the matroid circuits I made of r + 1 columns of V (r = rank(V )) formed of the r linear independent columns selected by the QR factorization of section 5.2.5(A) and one of the remaining pr columns of V . By proposition 3.10, such I contains exactly one circuit. Therefore, one detects in this way pr circuits and 2(pr) stem vectors. This is not much compared to the total number of stem vectors, which may depend exponentially on p, so that the number of infeasible sign vectors detected by these stem vectors is usually relatively small (see table 5.2).

D 2 ) With this option, when a LO problem (5.1) is solved at a certain node s ∈ S 1 k to see whether (s, s k+1 ) belongs to S 1 k+1 , for s k+1 ∈ {±1}, the dual solution is used to determine a stem vector, as shown by proposition 5.10. For this purpose, the isf code solves the LO problems with the dual-simplex algorithm, so that the computed dual solution is at a vertex of the dual feasible set. D 3 ) With this option, all the stem vectors are computed, before running the recursive process that builds the S-tree. At each note s ∈ S 1 k , the algorithm still computes a direction d ∈ R n such that s i v T i d > 0 for all i ∈ T s (the set of vector indices considered so far at s). The advantage of this direction is to allow the algorithm to use the beneficial modifications B and C and to easily determine one or two signs s k+1 ∈ {±1} such that (s, s k+1 ) ∈ S 1 k+1 . If a single sign s k+1 ∈ {±1} is selected, the stem vectors can decide whether (s, -s k+1 ) ∈ S 1 k+1 . If this is the case, this option D 3 has the inconvenient of still requiring to solve a LO problem to get a direction associated with (s, -s k+1 ). These LO problems (5.1) have an optimal value -1 and should not be solved exactly. Indeed, as soon as a feasible direction d for (5.1) gives a negative value to the objective of the problem, one could stop solving it, since this d verifies s i v T i d > 0 for all i ∈ T (s,-s k+1 ) . We have not implemented that inexact solve of the LO problems, by lack of flexibility of the solver Linprog in Matlab. D 4 ) Like with the option D 3 , all the stem vectors are computed, before running the recursive process that builds the S-tree. But now, unlike with option D 3 , the algorithm computes no direction d ∈ R n . The approach can be viewed as an improvement of the algorithm 5.8 (stem) presented in section 5.2.3, in the sense that option A is also activated.

Note that, knowing all the stem vectors, one could compute the complementary set S c rather easily by completing with ±1 the unspecified components of the stem vectors.

Next, S could be obtained from S c by taking its complementary set in {±1} p , but a straightforward implementation of this last operation looks rather expensive, so that we have not experimented it numerically.

Isf algorithm

We have named isf (for Incremental Signed Feasibility) the algorithm that improves the rc algorithm 5.6 or the stem algorithm 5.8 with the enhancements described in section 5.2.5.

For the purpose of precision and reference, we formally state it in this section. It would be cumbersome and confusing, hence inappropriate, to mention all the options in its description, in particular because all of them have been specified separately in the previous section. As an example of algorithm, we provide a description with the options ABCD 2 . It starts with a hat procedure isf, similar to that of the rc algorithm but with the additional easy determination of S r (modification A) and the computation of some stem vectors (modification D 1 ). Then, the hat procedure calls the recursive procedure isf-rec.

Algorithm 5.12 (isf, with options ABCD 2 ) Let be given V ∈ R n×p , with n and p ∈ N * , having nonzero columns.

Complexity

This section briefly analyzes the complexity of the isf(A) algorithm, i.e., with only option A of section 5.2.5.A, knowing that, in practice, the other options improve the performance of the algorithm. This one is similar to algorithm 5.12 from which the options BCD 2 have been discarded. As shown by the next proposition, algorithm isf(A) is output-sensitive, in the sense that its computation effort is bounded above by a number proportional to the size |∂ B H(x)| of the output (recall that this one may be exponential in p). The computation effort is measured in terms of the number of LO problems that must be solved in the worst case. The next result is very similar to [57; theorem 3.2], although its proof is slightly different. The given upper bound on the number of LO problems to solve takes also into account steps 1 and 3 of algorithm 5.12, which is not present in the rc algorithm and from which comes the use of the rank r of V . The bound 2 p -2 r is also new, but is unlikely to be active when p ≫ r.

Proposition 5.14 (complexity of algorithm isf(A)) Suppose that V ∈ R n×p has no colinear columns and denote by r its rank. Then, the number of linear optimization problems solved by algorithm isf(A) does not exceed min 2 p -2 r , (pr)|S| .

(5.9)

Proof. In its steps 1 and 3, algorithm 5.12 specifies the 2 r sign vectors associated with r linearly independent columns of V , which may be assumed to be v 1 , . . . , v r . This step does not require to solve any LO problem. One has r The number of circuits is also predictable for the random problems. Indeed, by the random generation of V , a subset of columns is likely to have nullity 1 (i.e., to form a circuit, in the matroid terminology) if and only if it contains r + 1 columns (r being the rank of V ). Therefore, their number should be p r+1 (see also [41; footnote 1]), which is indeed the number displayed in the 5th column of table 5.1 for the randomly generated problems.

|S r | = 2 r . ( 5
2) One observes that when r = 2, one has |∂ B H(x)| = 2p (proposition 4.17).

3) The number of matroid circuits, given in the column labeled by ς, depends on the determination of the nonzero elements of the normalized vector α ∈ N (V : ,I ) \ {0} for the selected index set I (proposition 3.10). This operation is sensitive to a threshold value that is set to 10 5 ε, where ε > 0 is the machine epsilon; smaller values for this threshold have occasionally given larger numbers of matroid circuits. In other words, due to the floating point calculation, there is no certainty that the given number of circuits is the one that would be obtained in exact arithmetic. 4) A comparison between the "Original rc code" in Python and its "Simulated rc code"

in Matlab shows that the latter is slightly more effective in terms of the number of LO problems solved. This is probably due to the special treatment in step 2 of the case where v T k+1 d ≃ 0 in algorithm 5.7, which is not considered in the original code.

C. Observations on table 5.2 Table 5.2 shows the effect of the modifications discussed in section 5.2.5 on the number of LO problems (LOP) solved, which significantly counts in the computing time. This will lead us to select three algorithms, those which bring the best profit on the LOP counter. The columns labeled "Ratio" show the acceleration ratio with respect to the simulated rc code in terms of LOP, that is the ratio of the LOP counter of the considered algorithm divided by the LOP counter of the simulated rc algorithm. On the last two lines of the table, one finds the mean and median values of these acceleration ratios, which may be viewed as a summary of the effect of the considered modification.

1) The modification A, proposed in section 5.2.5(A), which uses the QR factorization to get r linearly independent columns of V , does not bring a large benefit ("Ratio" is close to 1) and sometimes increases the number of LO problems to solve. The benefit is not important since it prevents "only" i∈[0 : r] 2 i = 2 r+1 -1 nodes to run the LO solver, which is usually a small fraction of the total number of nodes of the S-tree. One also observes that the number of solved LOP may increase (acceleration ratio < 1), which is sometimes due to the fact that the number 2 r of nodes at level r with modification A is larger than the one without modification A, which contributes to an increase in the total number of nodes of the constructed S-tree and, therefore, tends to increase the number of LO to solve. Furthermore, the order in which the vectors are considered without/with modification A is not identical, which has also an impact on the number of solved LOP (see section 5.2.5(C)).

2) The modification B, proposed in section 5.2.5(B), which is able to detect two descendants of an S-tree node, without solving any LO problem, has a significant impact on the total number of these problems. We see, indeed, that the (mean, median) acceleration ratio is raised to (1.24, 1.18). 3) Consider now the modification C, described in section 5.2.5(C), which changes the order in which the vectors v i 's are considered. We use the test-problem rand-7-13-5 to show this effect in the next table. The table gives the number of nodes for each level in the S-tree, with the modifications AB and with the modifications ABC. Since rank(V ) = 5 for this problem and since the modification A is used in both cases, the number of nodes per level, only starts to differ from level 6 (before that it is equal to 2 l-1 , where l is the S-tree level). The final level is 13 (since there are p = 13 vectors) and its number of leaves is |S|/2 = 794 (an observation from the table above or from table 5.2), necessary identical in both cases. The effect of the modification C can be seen on the smaller number of nodes per level and in all the S-tree (rightmost column). This contributes to the decrease of the number of LO to solve: the (mean, median) acceleration ratio is raised to (2.35, 2.03). 4) The modifications D, described in section 5.2.5(D), deal with the contribution of the computed stem vectors, whose number increases from modification D 1 (2(pr) stem vectors after the QR factorization of V ), D 2 (more stem vectors from the dual solution of the LO problem (5.1) when this one has a nonnegative optimal value), D 3 and D 4 (all the stem vectors).

r We see that the option D 1 yields already some improvement (less LO to solve), but not much, raising the (mean, median) acceleration ratio from (2.35, 2.03) to (2.63, 2.15).

r The use of the option D 2 is more beneficial since the (mean, median) acceleration ratio now goes up to (23.75, 3.29). We understand this fact to have its origin in the increase in the number of stem vectors detected from the dual solutions of some solved LO problems. Note that this last operation does not require much computation time.

r With option D 3 , only the LO problems (5.1) with the optimal value -1 are solved. This reduces even more significantly the number of LO to solve, with a (mean, median) acceleration ratio that now reaches (27.91, 4.63).

r With option D 4 , no LO problem is solved. In conclusion of these observations, one could retain the following three solvers: r isf(ABCD 2 ) is the most efficient solver that does not compute all the stem vectors, r isf(ABCD 3 ) has room for improvement in a compiled language (compared to an interpreter, like Matlab) and therefore should not be discarded, r isf(AD 4 ) is the option combination without optimization problem to solve, which is an interesting feature (it is also the solver described in section 5.2.3 with the modification A of section 5.2.5 in addition). As we shall see in section 5.2.8(D), it is the solver that has usually the lowest (mean, median) CPU time on the considered test problems, but this good property is sometimes invalidated on problems with many stem vectors.

D. Observations on table 5.3

Measuring the efficiency of the algorithms by the number of LO solved during execution, like in table 5.2, is sometimes misleading. If this is the main cost item for some algorithms, it is no longer the case when a large amount of stem vectors is computed. For two reasons. First, the time spent in the computation of these stem vectors is not negligible, far from it, at least in our implementation, in which each of them requires the computation of the nullity of a matrix and a null space vector. Next, verifying that a sign vector contains a stem vector (proposition 3.9) is also time consuming when there are many stem vectors. Therefore a comparison of the CPU time of the runs is welcome. This is done for a selection of versions of the isf codes in table 5.3, those selected at the end of section 5.2.8(C). Here are some observations on the statistics of this table.

1) A first observation is that the good behavior of the selected versions of the isf codes is confirmed, even though the acceleration ratios are not as large as the one based on the number of LO problems solved. This can be explained by the fact that the time spent in solving LO problems is counterbalanced by the handling of stem vectors for the version ABCD 3 and AD 4 . Anyway, one observes that the CPU time acceleration ratios have (mean, median) values in the ranges (7..15, 3..14), which is significant.

2) The most effective combination of code options depends actually on the considered problems. It is difficult to state a rule that would predict which code behaves best because some solvers are better on some phases of the run, but worse on others (the three main phases are the detection of the stem vectors, the execution of LO problems and the search for stem vectors covered by a given sign vector). Actually, this multicriterion problem has no clear solution and we leave this question open for future numerical experiments.

A numerical example

Consider the LCP in standard form (1.4), which reads 0 x ⊥ (M x + q) 0, where x ∈ R n , M ∈ R n×n and q ∈ R n . Suppose that n = 3 and that M and q are given by M =   2 0 0 0 2 1 1 1 2   and q = 0.

Since M is a P-matrix (i.e., all its principal minors are positive), the problem has a unique solution [START_REF] Samelson | A partition theorem for the Euclidean n-space[END_REF], which is x = 0. With the notation (2.2), one has A(x) = B(x) = ∅ and E(x) = E = (x) = {1, 2, 3}, so that V T given by (3.1) reads

V T = M -I =   1 0 0 0 1 1 1 1 1   .
Note that p = 3, while rank(V ) = 2, so that |∂ B H(x)| = 2p = 6, by proposition 4.17. The sign vectors s ∈ {±1} 3 that make s q V T d > 0 feasible for d are gathered in the set denoted by S, are the columns of the matrix S below and possible feasible directions d ∈ R 3 are the columns of the matrix D: From the matrix S given above, we see that S c := {±1} 3 \S = {s, -s}, where s = 1 1 -1 T . Observe also that, since

S =   1 -1 1 -1 -1 1 1 -1 -1 1 1 -1 1 -1 1 -1 1 -1   and D =   1 -1 2 -2 -1 1 1 -1 -1 1
± Diag(s)V T = ±   1 0 0 0 1 1 -1 -1 -1   ,
there is no d ∈ R 3 such that ±s q (V T d) > 0, as expected.

Discussion

This paper deals with the description and computation of the B-differential of the componentwise minimum of two affine vector functions. The fact that this problem has many equivalent formulations, some of them being highlighted in section 3, implies that the present contribution has an impact on several domains, including on the description of the arrangement of hyperplanes in the space. To this respect, a singular aspect of this contribution is to propose a dual approach to solve the problem, using some or all the stem vectors, a concept made useful thanks to the convex analysis tool that is Gordan's alternative. Besides this contribution, the paper also brings various improvements of an algorithm of Rada and Černý [START_REF] Rada | A new algorithm for enumeration of cells of hyperplane arrangements and a comparison with Avis and Fukuda's reverse search[END_REF], which was designed to determine the cells of an arrangement of hyperplanes in the space.

Even in the spirit of the methods proposed in this article, there is still room for improvement, in relation to three identified bottlenecks: (i) we have mentioned that with the option D 3 , the LO problem (5.1) can be solved inexactly, since, in that case, the optimal value is -1, while any negative objective value for a feasible unknown would suffice, but this requires a better tuning of the linear optimization solver, (ii) computing more efficiently all the stem vectors (or matroid circuits) of the matrix V is certainly a source of improvement, (iii) a better storage of the stem vectors that would allow the algorithm to decide more rapidly that a sign vector contains a stem vector is also welcome. Some of these possible improvements are also linked to a better choice of programming language, probably one using a compilation phase.

This contribution has also various possible extensions. One would be to develop a dual approach to the problem of the arrangement in the space of hyperplanes having no point in common [START_REF] Dussault | Arrangement of hyperplanes in the space by a dual approach[END_REF]. Another natural extension would be to see the implications of this work for computing the B-differential of the componentwise minimum of nonlinear vector functions [START_REF] Dussault | Partial description of the Bdifferential of the componentwise minimum of two vector functions by linearization[END_REF].

Problem 3 . 1 (

 31 B-differential of the minimum of two affine functions) Let be given two positive integers n and m ∈ N * , two matrices A, B ∈ R m×n and two vectors a, b ∈ R m . It is requested to compute the B-differential at some x ∈ R n of the function H : R n → R m defined by (1.2).

. 6 )

 6 Proposition 3.6 (bijection S c ↔ I) The map ı defined by (3.5) is a bijection from S c onto I.

r = 2 , |S| = 8 r = 3 , 3 , |S| = 14 Figure 3 . 1 :

 28331431 Figure 3.1: Linearly separable bipartitions of a set of p = 4 points vi in R 2 (the dots in the figure). Possible separating hyperplanes are the drawn lines. We have not represented any separating line associated with the partition (∅, [1 : p]) or ([1 : p], ∅), so that |S| = 2(n s + 1), where n s is the number of represented separating lines. We have set r := dim(vect{v 1 , . . . , vp }) + 1.

Proposition 4 . 2 (

 42 completeness of the B-differential) The B-differential of H at x, ∂ B H(x), is complete if and only if the matrix V ∈ R n×p in (3.1) is injective. Hence, this property can hold only if p n.

Proposition 4 . 5 (

 45 connectivity of the B-differential) The set S defined by (3.2) is connected if and only if V has no colinear columns. In this case, any points s and s of S can be joined by a path of length l := i∈[1 : p] |s is i |/2 p in S.

  [1 : p]: I := {i ∈ [1 : p] : si = -s i } and J := {j ∈ [1 : p] : sj = s j }. (4.4a) Clearly, |I| = l (the number given in the statement of the proposition) and |J| = pl. Let us now apply the construction 3.15(2) to get the cones K I and K J . Since s and s ∈ S, (3.12) tells us that cone{s i

[ 1 :

 1 p] are distinct (the vi are all distinct by the assumption on the non-colinearity of the v i 's). If the indices in I are denoted by i k , for k ∈ [1 : l] and those in J are denoted by j k , for k ∈ [1 : pl],

Proposition 4 . 8 (incrementation) 1 ). 2 ). 3 )

 48123 If s ∈ S c k , then (s, ±1) ∈ S c k+1 . In particular, |S c k+1 | 2|S c k |If v k+1 / ∈ vect{v 1 , . . . , v k }, then, (s, ±1) ∈ S k+1 for all s ∈ S k . In particular, |S k+1 | = 2|S k | and |S c k+1 | = 2|S c k |If v k+1 is not colinear to any of the vectors v 1 , . . . , v k , then, (s, ±1) and (-s, ±1) ∈ S k+1 for one s ∈ S k and (s ′ , +1) or (s ′ , -1) ∈ S k+1 for any s ′ ∈ S k . In particular, |S k+1 | |S k | + 2.

  .10c) [⊆] If V T : ,I∪{k+1} d = 0, one has V T : ,I d = 0 and v T k+1 d = 0. Therefore d ∈ v ⊥ k+1 and d = P k+1 d. It follows that V T : ,I P k+1 d = 0, meaning that d ∈ N (V T : ,I P k+1 ). [⊇] If V T : ,I P k+1 d = 0 and d ∈ v ⊥ k+1 , one has P k+1 d = d and v T k+1 d = 0. Therefore V T : ,I∪{k+1} d = 0.

Proposition 4 .

 4 11 (lower and upper bounds on |∂ B H(x)|) For V given by (3.1) and r := rank(V ), one has max(2p, 2 r ) 2 r + 2(pr) |∂ B H(x)| 2 p . Proof. The first inequality is clear since p r 1 and 2r 2 r . Consider the second inequality. One can assume that the first r columns of V are linearly independent, so that |S r | = 2 r (notation (4.5) and proposition 4.8(2)). Next, by proposition 4.8(3), |S r+1 | 2 r + 2. By induction, the given lower bound holds for |S p | = |S| = |∂ B H(x)|.

(4. 11 )

 11 Definition 4.13 (general position) The vectors v 1 , . . . , v p ∈ R n are said to be in general position, if the matrix

Proposition 4 .

 4 14 (upper bound on |∂ B H(x)|) For V given by (3.1) and r := rank(V ), one has

Corollary 4 .

 4 [START_REF] Borwein | Convex Analysis and Nonlinear Optimization -Theory and Examples[END_REF] (stability of the sign vector set) The sign vector set S ⊆ {±1} p defined by (3.2) is unchanged by small variations of the matrix V ∈ R n×p preserving its rank, provided the columns v 1 , . . . , v p ∈ R n of V are in general position in the sense of definition 4.13.Proof. If Ṽ is near V , S(V ) ⊆ S( Ṽ ) by proposition 4.12. If the columns of V are in general position, proposition 4.14 tells us that |S(V )| = β, where β is the right-hand side of Winder's bound (4.13) with r = rank(V ). Now, by the fact that rank( Ṽ ) = r, proposition 4.14 ensures that |S( Ṽ )| β. Therefore, one must have S( Ṽ ) = S(V ).

. 1 .

 1 As shown by the intermediate pane in figure 3.1, however, with 2 < r < p, |∂ B H(x)| does not only depend on r.

Proposition 4 .

 4 16 (injective matrix) The matrix V ∈ R n×p given by (3.1) is injective if and only if |∂ B H(x)| = 2 p . Proof. Indeed, by proposition 4.2, the B-differential ∂ B H(x) is complete (meaning that it is equal to ∂ B H(x), given by (2.3)) if and only if V is injective. Clearly, the completeness of∂ B H(x) is equivalent to |∂ B H(x)| = 2 p .More algebraically, this result can be deduced from Winder's formula (4.7) and the bound (4.13). [⇒] If V is injective, then, for any I ⊆ [1 : p], one has null(V : ,I ) = 0. Therefore, there are 2 p terms in the right-hand side of (4.7), each of them of value 1. This yields |∂ B H(x)| = 2 p . [⇐] Conversely, if |∂ B H(x)| = 2 p , one must have r = p in (4.13), meaning the V is injective. The next result applies to the left-hand side example of figure 3.1. Proposition 4.17 (fan arrangement) If p 2 and the vectors v i 's are not two by two colinear, one has rank(V ) = 2 if and only if |∂ B H(x)| = 2p. Proof. [⇒] A short proof leverages Winder's bound (4.13) with equality. Since the v i 's are not two by two colinear, one has for any I ⊆ [1 : p]:

  [2 : p -1] such that dim vect{v 1 , . . . , v k } = 2 and dim vect{v 1 , . . . , v k+1 } = 3. For any k ∈ [1 : p], denote by S k the set defined by (4.5). By the first part of the proof, |S k | = 2k. Since v k+1 / ∈ {v 1 , . . . , v k }, proposition 4.8(2) tells us that |S k+1 | = 4k. Now, for j ∈ [k + 2 : p], proposition 4.8(3) tells us that |S j | |S j-1 | + 2. As a result, we get |S p | 4k + 2(pk -1) = 2p + 2(k -1) 2p + 2 (since k 2), which contradicts the assumption |S p | = 2p.

. 15 )k = 2 p and p 0 = p p = 1 .

 151 where we have used k∈[0 : p] p Since there are 2 p subsets I of [1 : p] (including I = ∅ and I = [1 : p], describing the cases where there is no change of sign and p changes of signs, respectively), the total number of sign changes that preserve the pointedness of the original cone is 2 p -(2 p -2p) = 2p, which yields |∂ B H(x)| = 2p.

Proposition 4 .

 4 18 (a link with the C-differential) ∂ B H(x) = ext ∂ C H(x).

Algorithm 5 . 7 ( 1 . 2 . 1 .

 57121 rc-rec) Let be given V ∈ R n×p , with n and p ∈ N * , having nonzero columns, a direction d ∈ R n and a sign vector s ∈ {±1} k for some k ∈ [1 : p], such thats i v T i d > 0 for all i ∈ [1 : k]. If k = p,print s and return. If v T k+1 d ≃ 0, then 2.Execute rc-rec(V, d + , (s, +1)), where d + := d + t + v k+1 with t + > 0 chosen in the nonempty open interval

  .10a) Next, algorithm 5.13 considers the remaining pr columns v r+1 , . . . , v p of V recursively. Let us show that for k ∈ [r + 1 : p]: |S k-1 | ⊆ |S k | ⊆ |S|. (5.10b) The first inclusion in (5.10b) comes from the fact that algorithm builds a sign vector in S k for each sign vector in S k-1 , in any of its step 3 or 4 (proposition 4.8(3)). The second inclusion in (5.10b) is deduced by induction and from the fact that S p = S. To compute S k , for any k ∈ [r + 1 : p], the number of LO problems to solve is bounded by |S k-1 |, since at most one LO problem is solved (in step 4.3 of the algorithm) for each sign vector in S k-1 . This bound |S k-1 | is itself bounded by min(2 k-1 , |S|) (the first bound comes from the upper bound in proposition 4.11 and the fact that there are k -1 vectors in V : ,[1 : k-1] ;

  whose columns are nonzero by assumption here and in section 3.2.1. Recall the definition (3.2) of the set of sign vectors S.

Proposition 3.19 (bijection C ↔ S) For the matrix V ∈ R n×p , with nonzero columns v i 's, the map η given by (3.19) is a bijection from C onto S.

  p is large, computing the cardinal |∂ B H(x)| from (4.7) by evaluating the 2

p ranks rank(V : ,I ) for I ⊆ [1 : p] could be excessively expensive. Therefore, having simple-to-compute lower and upper bounds on |∂ B H(x)| may be useful in some circumstances, including theoretical ones. Actually, such bounds can be obtained very easily, using one of the formulations of the problem given in section 3. Proposition 4.11 gives elementary lower and upper bounds, while proposition 4.14 reinforces the upper bound, thanks to a lower semicontinuity argument (proposition 4.12). Necessary and sufficient conditions ensuring equality in the left-hand side or right-hand side inequalities in the next proposition are given in section 4.3.

  4.1. Execute isf-rec(V, T k+1 , d, (s, s k+1 )). 4.2. If (s, -s k+1 ) contains a stem vector, return. 4.3. Solve the LO problem (5.1) (with [1 : k] changed into T k and k + 1 into i k+1 ) by the dual-simplex algorithm and denote by (d, t) a solution. 4.3.1. If t = -1, execute isf-rec(V, T k+1 , d, (s, -s k+1 )). 4.3.2. Else, use the dual solution to store two more stem vectors by option D 2 .

Table 5 .

 5 3: Comparison of the computing times.52The Jacobians of the B-differential ∂ B H(x) are obtained for the s's in S given above by the bijection σ defined by(3.3). One gets a set of 6 Jacobians out of the 2 3 = 8 Jacobians in ∂ B H(x), namely

Acknowledgments

We thank Rada and Černý for providing their code and test problems, those used in [57]; part of these were used in the numerical experiments.

This algorithm is improved below, as the option AD 4 of the isf algorithm (see paragraphs A and D of section 5.2.5).

Note that, this algorithm need not generate directions d satisfying s q V T k d > 0, like the rc algorithm and need not solve any LO problem. Nevertheless, regarding the computation time, the algorithm has two bottlenecks that we now describe. Despite them, algorithm 5.8 is often the fastest in the numerical experiments of section 5.2.8.

The first bottleneck comes from the fact that the algorithm must compute all the stem vectors (or the set C of matroid circuits in (3.8)) associated with V . This is usually an expensive operation. For example, if V is randomly generated and of rank r, like in the testcases data_rand_* in the experiments of section 5.2.8, any selection of r columns of V is likely to form an independent set of vectors, so that C is likely to be the sets of column indices of size r + 1. Therefore, in this case, the number of circuits is likely to be the combination p r+1 (and it is actually that number, see section 5.2.8(B.1)), which can be exponential in p (this number is bounded below by 2 p/2 /(p + 1) if p is even and r + 1 = p/2 [23; (11.52)]). In the implemented isf code, numerically tested in section 5.2.8, only the sets of columns whose cardinal is in [3 : r + 1] are examined (since any group of two columns of V is supposed to be linearly independent and a group of r + 2 columns or more is of nullity 2, hence such group cannot form a matroid circuit; see (3.8)). In addition, the exploration is made using a tree structure for the column subsets, in order to discard the descendants of a circuit, which, by construction of the tree, contain this circuit and has more columns than this one. These two provisions are not sufficient, however, to prevent generating a lot of redundant circuits and, therefore, useless computation.

The second bottleneck is linked to the detection of a stem vector is the current sign vectors (s, ±1). This operation requires to search the long list of stem vectors, which is a time consuming operation.

Linear optimization problem and stem vector

The property described in this section will be useful for the improvement D 2 of the isf algorithm, described in section 5.2.5(D). It shows that a stem vector can be obtained easily from the dual solution of the LO problem (5.1), when (s, -s k+1 ) / ∈ S k+1 . Consider indeed the LO problem (5.1) and denote by (d, t) one of its solutions (these have been shown to exist). Then, either t 0 (equivalently, (s, -s k+1 ) / ∈ S k+1 ) or t = -1 (equivalently, (s, -s k+1 ) ∈ S k+1 ).

Improvements of the rc and stem algorithms

This section presents several modifications of the rc algorithm and one modification of the stem algorithm that significantly improve their performance. The modifications are indicated by the letters A, B, C and D, with reference to the sections where they are introduced. Additional numeric indices specify variants of the D option. The version AD 4 (modifications A and D 4 ) can be considered as an improvement of the new algorithm 5.8.

A. Taking the rank of V into account Instead of starting with the vector s = +1, one can take into account the rank r := rank(V ) to determine 2 r initial vectors s, hence avoiding to solve LO problems to determine these initial s's. This is especially useful when pr is small. In particular, when p = r, S is straightforwardly determined. The algorithm selects r := rank(V ) linearly independent vectors v i , among the columns of V ∈ R n×p . These vectors can be obtained by a QR factorization of

where P ∈ {0, 1} p×p is a permutation matrix, Q ∈ R n×n is orthogonal (i.e., Q T Q = I n ) and R ∈ R n×p is upper triangular with R [r+1 : n], : = 0. To simplify the presentation, one can assume, without loss of generality, that P = I, in which case the vectors v 1 , . . . , v r are linearly independent (in practice, the vectors are symbolically reordered by using the permutation matrix P ). By proposition 4.2, S r = {±1} r .

(

Furthermore, for each s ∈ S r , we have, using

is such that s q V T : ,[1 : r] d s = e > 0, as desired. For each s ∈ S r and the associated d s given by (5.4), the modified algorithm 5.6 will run the recursive function rc-rec(V, d s , s) (see algorithm 5.12 below).

B. Special handling of the case where v T k+1 d ≃ 0 The equivalence (4.8a) shows that the existence of a direction d such that s i v T i d > 0 for all i ∈ [1 : k] and v T k+1 d = 0 is a necessary and sufficient condition for s ∈ S k to have two descendants. This property underlies the following modification.

Directions

of the rc-rec algorithm 5.7, but also when v T k+1 d is in the interval specified by (5.5) below. Note that the left-hand side in (5.5) is negative and the right-hand side is positive (this can be seen by multiplying numerators and denominators by s i and by using s i v T i d > 0 for all i ∈ [1 : k]), so that these inequalities are verified when v T k+1 d = 0. With the additional flexibility that (5.5) offers, the isf algorithm can sometimes avoid solving a significant number of LO problems of the form (5.1). Proposition 5.11 (two descendants without optimization) Suppose that s ∈ while the second bound comes from (5.10b)). Therefore, the total number of LO problems solved by the algorithm is bounded by

This is the announced bound (5.9).

Numerical experiments

A. Computer and problem presentations

We present in tables 5.1, 5.2 and 5.3 the results obtained by running the isf algorithm 5.12 (with several variants) on a small number of problems and compare it with our implementation of the rc algorithm 5.6, simulating the algorithm 1 (IE) in [START_REF] Rada | A new algorithm for enumeration of cells of hyperplane arrangements and a comparison with Avis and Fukuda's reverse search[END_REF]. The implementations have been done in Matlab (version "9.11.0.1837725 (R2021b) Update 2") on a MacBookPro18,2/10cores with the system macOS Monterey, version 12.6.1.

We have assessed the codes on randomly generated problems (function rand in Matlab, names prefixed by rand and srand in the first part of table 5.1) and problems adapted from [START_REF] Rada | A new algorithm for enumeration of cells of hyperplane arrangements and a comparison with Avis and Fukuda's reverse search[END_REF] (names prefixed by rc). The rand-n-p-r problems have their data formed of a randomly generated matrix V ∈ R n×p with prescribed rank r := rank(V ). The matrix V of problem srand-n-p-q (s for structured) has its n first columns formed of the n basis vectors of R n and the last pn > 0 columns have q nonzero random integer elements, randomly positioned, which induces many matroid circuits. The rc problems are adapted from [START_REF] Rada | A new algorithm for enumeration of cells of hyperplane arrangements and a comparison with Avis and Fukuda's reverse search[END_REF] and given in the second part of table 5.1.

B. Observations on table 5.1

The dimensions n, p and r of the problems are given in columns 2-4 of table 5.1. Column 5 gives the number ς of matroid circuits of V . In column 6 and 7, one finds the cardinal |∂ B H(x)| = |S| of the B-differential ∂ B H(x) and the Winder upper bound (the right-hand side of (4.13)). The codes will be compared on the number of LO problems they solve, which is a good image of their computation effort, measured independently of the computer used to run the codes and the features of the LO solvers. A first example of comparison is given in columns 8 and 9 of table 5.1, where one finds the number of LO problems solved by the original rc algorithm and the simulated rc algorithm implemented in the isf code respectively. The latter code will be used next, in the comparison with its improved versions, both regarding the LO problem counters (table 5.2) and the CPU times (table 5.3).

1)

The randomly generated problems rand are likely to provide vectors v i 's (the columns of V ) in general position, in the sense of definition 4.13. This can be seen indirectly on the numbers in table 5.1.

r It is known from proposition 4.14 that (4.12) implies equality in (4.13). This equality indeed holds, as we can observe by comparing columns 6 and 7.

r Incidentally, one can compute mentally Winder's bound β when p is even and r = p/2.

In that case, the right-hand side of (4.13) reads

This is what one observes in the table; for example when p = 8 and r = 4, one has β = 128, which is indeed 2 Table 5.1: Description of the test-problems and comparison of the "original rc algorithm in [START_REF] Rada | A new algorithm for enumeration of cells of hyperplane arrangements and a comparison with Avis and Fukuda's reverse search[END_REF]", written in Python, and the "simulated rc algorithm 5.6", written in Matlab: "(n, p, r, ς)" are the dimensions of the problem (V ∈ R n×p is of rank r and has ς circuits), "Winder's bound" is the right-hand side of (4.13), "|∂ B H(x)|" is the cardinal of the B-differential of H given by (1.2), "Original rc" gives the number of LO problems solved by the original piece of software in Python of Rada and Černý [START_REF] Rada | A new algorithm for enumeration of cells of hyperplane arrangements and a comparison with Avis and Fukuda's reverse search[END_REF], "Simulated rc" gives the number of LO problems solved by the implementation in the Matlab code isf of the Rada and Černý algorithm (see algorithm 5.6), "Difference" is the difference between the two previous columns. Table 5.2: Improvement brought by the modifications described in section 5.2.5, in terms of the number of LO problems to solve: A (taking the rank of V into account), B (special handling of the case where v T k+1 d ≃ 0), C (changing the order of the vectors v i 's by taking i k+1 by (5.8)), D 1 (pre-computation of 2(pr) stem vectors after the QR factorization), D 2 (D 1 and 2 additional stem vectors computed after solving a LO problem, whose optimal value is nonnegative), D 3 (all the stem vectors are first computed and, for (s, ±1) ∈ S k+1 , a LO problem is solved to get a handle d), D 4 (all the stem vectors are first computed and no LO is solved). The "Ratio" (acceleration ratio) columns give for each considered problem the ratio (LOP of the considered isf version)/(LOP of the simulated rc). Note: (1) failure of the LO solver Linprog-'dual-simplex', which exceeds 5000 iterations.