Michel Broniatowski
email: michel.broniatowski@sorbonne-universite.fr

Jana Jurečková
email: jureckova@utia.cas.cz

Jan Kalina
email: kalina@cs.cas.cz

Likelihood Ratio Testing under Measurement Errors

Keywords: measurement errors, robust testing, two-sample test, misspecified hypothesis and alternative, 2-alternating capacities Methodology, M

. A numerical experiment illustrates the principles and performance of the novel test.

Introduction

Measurement technologies are often affected by random errors; if the goal of the experiment is to compare two probability distributions using data, then the conclusion can be distorted if the data are affected by some measurement errors. If the data are mismeasured due to the presence of measurement errors, the statistical inference performed with them is biased and trends or associations in the data are deformed. This is common for a broad spectrum of applications e.g., in engineering, physics, biomedicine, molecular genetics, chemometrics, econometrics etc. Some observations can be even undetected, e.g., in measurements of magnetic or luminous flux in analytical chemistry when the flux intensity falls below some flux limit. Actually, we can hardly imagine real data free of measurement errors; the question is how severe the measurement errors are and what their influence on the data analysis is [START_REF] Boyd | Measuring test measurement error: A general approach[END_REF][START_REF] Brakenhoff | Measurement error is often neglected in medical literature: A systematic review[END_REF][START_REF] Edwards | All your data are always missing: Incorporating bias due to measurement error into the potential outcomes framework[END_REF].

A variety of functional models have been proposed for handling measurement errors in statistical inference. Technicians, geologists, and other specialists are aware of this problem, and try to reduce the effect of measurement errors with various ad hoc procedures. However, this effect cannot be completely eliminated or substantially reduced unless we have some additional knowledge on the behavior of measurement errors.

There exists a rich literature on the statistical inference in the error-in-variables (EV) models as is evidenced by the monographs of Fuller [START_REF] Fuller | Measurement Error Models[END_REF], Carroll et al. [START_REF] Carroll | Measurement Error in Nonlinear Models: A Modern Perspective[END_REF], and Cheng and van Ness [START_REF] Cheng | Statistical Regression with Measurement Error[END_REF], and the references therein. The monographs [START_REF] Fuller | Measurement Error Models[END_REF] and [START_REF] Cheng | Statistical Regression with Measurement Error[END_REF] deal mostly with classical Gaussian set up while [START_REF] Carroll | Measurement Error in Nonlinear Models: A Modern Perspective[END_REF] discusses numerous inference procedure under semi-parametric set up. Nonparametric methods in EV models are considered in [START_REF] Carroll | Nonparametric regression in the presence of measurement error[END_REF][START_REF] Carroll | Non-parametric regression estimation from data contaminated by a mixture of Berkson and classical errors[END_REF] and in references therein, and in [START_REF] Fan | Nonparametric regression estimation involving errors-in-variables[END_REF], among others. The regression quantile theory in the area of EV models was started by He and Liang [START_REF] He | Quantile regression estimate for a class of linear and partially linear errors-in-variables models[END_REF]. Arias [START_REF] Arias | Individual heterogeneity in the returns to schooling: Instrumental variables quantile regression using twins data[END_REF] used an instrumental variable estimator for quantile regression, considering biases arising from unmeasured ability and measurement errors. The papers dealing with practical aspects of measurement error models include [START_REF] Hyk | Quantifying uncertainty of determination by standard additions and serial dilutions methods taking into account standard uncertainties in both axes[END_REF][START_REF] Kelly | Some aspects of measurement error in linear regression of astronomical data[END_REF][START_REF] Marques | Predicting and correcting bias caused by measurement error in line transect sampling using multiplicative error model[END_REF][START_REF] Rocke | A two-component model for measurement error in analytical chemistry[END_REF][START_REF] Akritas | Linear regression for astronomical data with measurement errors and intrinsic scatter[END_REF], among others. Recent developments in treating the effect of measurement errors on econometric models was presented in [START_REF] Hausman | Mismeasured variables in econometric analysis: Problems from the right and problems from the left[END_REF] or [START_REF] Hyslop | Bias from classical and other forms of measurement error[END_REF] The advantage of rank and signed rank procedures in the measurement errors models was discovered recently in [START_REF] Jurečková | Rank tests and regression rank scores tests in measurement error models[END_REF][START_REF] Jurečková | Behavior of R-estimators under Measurement Errors[END_REF][START_REF] Navrátil | Rank tests of symmetry and R-estimation of location parameter under measurement errors[END_REF][START_REF] Navrátil | Rank tests and R-estimates in location model with measurement errors[END_REF][START_REF] Saleh | R-estimation of the parameters of a multiple regression model with measurement errors[END_REF][START_REF] Sen | Rank tests for corrupted linear models[END_REF]. The problem of interest in the present paper is to study how the measurement errors can affect the conclusion of the likelihood ratio test.

The distribution function of measurement errors is considered unknown, up to zero expectation and unit variance. When we use the the likelihood ratio test while ignoring the possible measurement errors, we can suffer a loss in both errors of the first and second kind. However, we show that under a small variance of measurement errors, the original likelihood ratio test is still most powerful, only on a slightly changed significance level.

On the other hand, we may consider the situation that H 0 or H 1 are classes of distributions of random variables Z + √ δV. Hence, both hypothesis and alternative are composite as families H 0 and H 1 ; if they are bounded by alternating Choquet capacities of order 2, then we can look for a minimax test based on the ratio of the capacities, and/over on the ratio of the pair of the least favorable distributions of H 0 and H 1 , respectively (cf. Huber and Strassen [START_REF] Huber | Minimax tests and the Neyman-Pearson lemma for capacities[END_REF]).

Likelihood Ratio Test under Measurement Errors

Our primary goal is to test the null hypothesis H 0 that independent observations X = (X 1 , . . . , X n ) come from a population with a density f against the alternative H 1 that the true density is g, where f and g are fixed densities of our interest. For the identifiability, we shall assume that f and g are continuous and symmetric around 0. Although the alternative is the main concern of the experimenter, some measurement errors or just the nature may cause the situation that the true alternative should be considered as composite. Specifically, X 1 , . . . , X n , can be affected by additive measurement errors, what appears in numerous fields, as illustrated in Section 1.

Hence the alternative is H 1,δ under which the observations are Z i,δ = X i + √ δV i , identically distributed with continuous density g δ . Here, both under the hypothesis and under the alternative, V i are independent random variables, unobservable with unknown distribution, independent of X i ; i = 1, . . . , n. The parameter δ > 0 is also unknown, only we assume that I E V i = 0 and I EV 2 i = 1, for simplicity. The mismeasured, hence unobservable, X i are assumed to have the density g under the alternative. Quite analogously, the mismeasured observations lead to a composite hypothesis H 0,δ under which the density of observations Z i,δ = X i +

√ δV i is f δ while the X i are assumed to have density f .
If we knew f δ and g δ , we would use the Neyman-Pearson critical region

W = z : n ∑ i=1 ln g δ (z i ) f δ (z i ) ≥ u (1)
with u determined so that

P f δ n ∑ i=1 ln g δ (z i ) f δ (z i ) ≥ u = α,
with a significance level α. Evidently

I n ∑ i=1 ln g δ (z i ) f δ (z i ) ≥ u n ∏ i=1 g δ (z i )dz i = I n ∑ i=1 ln g(x i ) f (x i ) ≥ u n ∏ i=1 g(x i )dx i I n ∑ i=1 ln g δ (z i ) f δ (z i ) ≥ u n ∏ i=1 f δ (z i )dz i = I n ∑ i=1 ln g(x i ) f (x i ) ≥ u n ∏ i=1 f (x i )dx i .
Indeed, notice that

I E g δ I n ∑ i=1 ln g δ (Z i ) f δ (Z i ) ≥ u V 1 = v 1 , . . . , V n = v n = I E g I n ∑ i=1 ln g(X i ) f (X i ) ≥ u V 1 = v 1 , . . . , V n = v n ∀v i ∈ R, i = 1, . . . , n,
where the expectations are considered with respect to the conditional distribution; a similar equality holds for f δ .

Combining the integration transmission in the conditional distribution, we obtain

I n ∑ i=1 ln g δ (x i + √ δV i ) f δ (x i + √ δV i ) ≥ u n ∏ i=1 f (x i )dx i = I n ∑ i=1 ln g(x i ) f (x i ) ≥ u n ∏ i=1 f (x i )dx i = α, (2)
hence the size of the critical region W when used for testing H 0 against H 1 differs from α. Then we ask how the critical region W in (1) behaves when it is used as a test of H 0 . This problem we shall try to attack with an expansion of f δ , g δ in δ close to zero.

Approximations of Densities

Put f = f 0 , g = g 0 the densities of X under the hypotheses and alternative, respectively. For the identifiability, we shall assume that f 0 and g 0 are continuous and symmetric around 0. Denote f δ the density of Z δ = X + √ δV. This means that X is affected by an additive measurement error √ δ V, where V is independent of X and I EV = 0, I EV 2 = 1, I EV 4 < ∞. Notice that if densities of X and V are strongly unimodal, then that of Z is also strongly unimodal (see [START_REF] Ibragimov | On the composition of unimodal distributions[END_REF]). Under some additional conditions on f 0 , g 0 , we shall derive approximations of f δ and g δ for small δ > 0. More precisely, we assume that both f 0 and g 0 have differentiable and integrable derivatives up to order 5. Then we have the following expansion of f δ and a parallel result for g δ : Theorem 1. Assume that f 0 and g 0 are symmetric around 0, strongly unimodal with differentiable and integrable derivatives, up to the order 5. Then, as δ ↓ 0,

f δ (z) = f 0 (x + √ δV) = f 0 (x) + δ 2 d 2 dz 2 f 0 (x) + δ 2 4! d 4 dz 4 f 0 (x)I E(V 4 ) + o(δ 2 ), (3)
g δ (z) = g 0 (x + √ δV) = g 0 (x) + δ 2 d 2 dz 2 g 0 (x) + δ 2 4! d 4 dz 4 g 0 (x)I E(V 4 ) + o(δ 2 ) Proof. Let ϕ(u, δ) = I E{e iuZ } be the characteristic function of Z. Then ϕ(u, δ) = I E{e iuX }I E{e iu √ δV } = ϕ(0, 0)ϕ V (u √ δ) = ϕ(u, 0) 1 + 1 2 δ(iu) 2 + 1 4! δ 2 (iu) 4 I E(V 4 ) + o(δ 2 ) = ϕ(u, 0) 1 - δ 2 u 2 + 1 4! δ 2 u 4 I E(V 4 ) + o(δ 2 ) ,
where ϕ V denotes the characteristic function of V. Taking the inverse Fourier transform on both sides, we obtain (3), taking the above assumptions on V into account.

Consider the problem of testing the hypothesis H 0 that the observations are distributed according to density f 0 against the alternative H 1 that they are distributed according to density g 0 . Parallelly, we consider the hypothesis H 0,δ that observations are distributed according the g δ against the alternative H 1,δ that the true density is g δ . Let Φ(x) be the likelihood ratio test with critical region

W = x : ∑ n i=1 ln g 0 (x i )
f 0 (x i ) > u and the significance level α, and Φ * = Φ * (z) be the test with critical region W * = z : ∑ n i=1 ln

g 0 (z i )) f 0 (z i ) > u based on observations z i = x i + √ δV i , i = 1, . . . , n.
We know neither δ nor V, hence the test Φ * is just an application of the critical region W for contaminated data Z 1 , . . . , Z n . Thus, due to our lack of information, we use the test Φ even for testing H 0,δ against H 1,δ , and the performance of this test is of interest. This is described in the following theorem: Theorem 2 (Assume the conditions of Theorem 1). Then, as δ ↓ 0, the test Φ * is the most powerful even for testing H 0,δ against H 1,δ , with a modified significance level satisfying

α δ ≤ α + δ 2 | f 0 (0)| + δ 2 24 I EV 4 | f (3) 0 (0)| + O(δ).
Proof.

I E f 0 Φ * (X) = I ln g 0 (x + √ δV) f 0 (x + √ δV) > u f 0 (x)dx = I ln g 0 (x + √ δV) f 0 (x + √ δV) > u f 0 (x) f 0 (x + √ δV) f 0 (x + √ δV)dx = I ln g 0 (x) f 0 (x) > u f 0 (x - √ δV) f 0 (x) f 0 (x)dx.
If f 0 is symmetric, then the derivative f

I E f 0 Φ * (X) = I E f 0 Φ(X) + I ln g 0 (x) f 0 (x) > u δ 2 f 0 (x) + δ 2 24 I EV 4 f (4) (x)dx + o(δ 2 ) ≤ I E f 0 Φ(X) + δ 2 | f 0 (0)| + δ 2 24 I EV 4 | f (3) 0 (0)| + o(δ 2 ) = α + O(δ) as δ ↓ 0.

Robust Testing

If the observations are missmeasured or contaminated, we observe Z δ = Z + √ δV with unknown δ and unobservable V instead of Z. Hence, instead of simple f 0 and g 0 , we are led to composite hypothesis and alternative H and K. Following [START_REF] Huber | Minimax tests and the Neyman-Pearson lemma for capacities[END_REF], we can try to find suitable 2-alternating capacities, dominating H and K and to construct a pertaining minimax test. As before, we assume that Z and V are independent, I EV = 0, I EV 2 = 1, and I EV 4 < ∞. Moreover, we assume that f 0 and g 0 are symmetric, strongly unimodal and differentiable up to order 5, with derivatives integrable and increasing distribution functions F 0 and G 0 , respectively. The measurement errors V are assumed to satisfy

1 ≤ I EV 4 ≤ K (4)
with a fixed K, 0 < K < ∞. Hence the distribution of V is restricted to have the tails lighter than t-distribution with 4 degrees of freedom. We shall construct a pair of 2-alternating capacities around specific subfamilies of f 0 and g 0 .

Let us determine the capacity around g 0 ; that for f 0 is analogous. By Theorem 1 we have

g δ (z) = g 0 (z) + δ 2 d 2 dz 2 g 0 (z) + δ 2 4! d 4 dz 4 g 0 (z)I E(V 4 ) + o(δ 2 ), as δ ↓ 0.
We shall concentrate on the following family K * of densities (similarly for f 0 ):

K * = g * δ,κ : g * δ,κ (z) = g 0 (z) + δ 2 g 0 (z) + κ δ 2 24 g (4) 0 (z) δ ≤ ∆, 1 ≤ κ ≤ K (5)
with fixed suitable ∆, K > 0. Indeed, under our assumptions, each g * δ,κ ∈ K * is a positive and symmetric density satisfying

sup δ≤∆,κ≤K sup z∈{R g * δ,κ (z) -g 0 (z) ≤ CK∆ 2 + o(∆ 2 ) for some C, 0 < C < ∞.
Let G * δ,κ (B), B ∈ B, be the probability distribution induced by density g * δ,κ ∈ K * , with B being the Borel σ-algebra. Then the set function

w(B) =      sup {G * (B) : G * ∈ K * } if B = ∅ 0 if B = ∅ (6)
is a pseudo-capacity in the sense of Buja [START_REF] Buja | On the Huber-Strassen theorem[END_REF], i.e., satisfying

(a) w(∅) = 0, w(Ω) = 1 (b) w(A) ≤ w(B) ∀A ⊂ B (c) w(A n ) ↑ w(A) ∀A n ↑ A (d) w(A n ) ↓ w(A) ∀A n ↓ A = ∅ (e) w(A ∪ B) + w(A ∩ B) ≤ w(A) + w(B).
Analogously, consider a density f 0 , symmetric around 0 and satisfying the assumptions of Theorem 1 as a simple hypothesis. Construct the family H * of densities and the corresponding family of distributions F * δ,κ (•), δ ≤ ∆, κ ≤ K similarly as above. Then the set function

v(B) =      sup {F * (B) : F * ∈ H * } if B = ∅ 0 if B = ∅ (7)
is a pseudo-capacity in the sense of Buja [START_REF] Buja | On the Huber-Strassen theorem[END_REF]. Buja [START_REF] Buja | On the Huber-Strassen theorem[END_REF] showed that on any Polish space exists a (possibly different) topology which generates the same Borel algebra and on which every pseudo-capacity is a 2-alternating capacity in the sense of [START_REF] Huber | Minimax tests and the Neyman-Pearson lemma for capacities[END_REF].

Let us now consider the problem of testing the hypothesis

H = {F * ∈ H * |F * (•) ≤ v(•)} against the alternative K = {G * ∈ K * |G * (•) ≤ w(•)} , based on an independent random sample Z 1 , . . . , Z n .
Assume that H * and K * satisfy (5). Then, following [START_REF] Buja | On the Huber-Strassen theorem[END_REF] and [START_REF] Huber | Minimax tests and the Neyman-Pearson lemma for capacities[END_REF], we have the main theorem providing the minimax test of H against K with significance level α ∈ (0, 1) :

Theorem 3. The test φ(z 1 , . . . , z n ) = 1 if ∏ n i=1 π(z i ) > C γ if ∏ n i=1 π(z i ) = C 0 if ∏ n i=1 π(z i ) < C
where π(•) is a version of dw dv (•) and C and γ are chosen so that I E v φ(Z) = α, is a minimax test of H against K of level α.

Numerical Illustration

We assume to observe independent Z 1,δ , . . , Z n,δ for i = 1, . . . , n, where Z i,δ = X i + √ δV i as described in Section 3, where X 1 , . . . , X n are independent identically distributed (with a distribution function F) but unobserved. Let us further denote by Φ the distribution function of N(0, 1) and by Φ * σ the distribution function of N(0, σ 2 ). The primary task here is to test H 0 :

F ≡ Φ against H 1 : F(x) = (1 -λ)Φ(x) + λΦ * σ (x), x ∈ I R,
with a fixed σ > 1 and λ ∈ (0, 1). We perform all the computations using the R software [START_REF] Core | R: A Language and Environment for Statistical Computing[END_REF].

To describe our approach to computing the test, we will need the notation for the set of pseudo-distribution functions corresponding to the set of pseudo-densities H * denotes as

H * = F * δ,κ : F * δ,κ (z) = Φ(z) + δ 2 f 0 (z) + κ δ 2 24 f (3) 0 (z) δ ≤ ∆, 1 ≤ κ ≤ K ,
where Φ denotes the distribution function of N(0, 1) distribution. Under the alternative, the set analogous to K * is defined as

K * = G * δ,κ : G * δ,κ (z) = G 0 (z) + δ 2 g 0 (z) + κ δ 2 24 g (3) 0 (z) 0 ≤ δ ≤ ∆, 1 ≤ κ ≤ K . Our task is to approximate v ((-∞, z)) = sup{F * δ,κ (z); F * δ,κ ∈ H * }, z ∈ I R, (8)
and

w ((-∞, z)) = sup{G * δ,κ (z); G * δ,κ ∈ K * }, z ∈ I R. (9)
Here, the functions F * δ,κ (z) and G * δ,κ (z) are evaluated over a grid with step 0.05. Then, the maximization in ( 8) and ( 9) is performed for values of z over the grid and over four boundary values of (δ, κ) T , which are equal to (0, 0) T , (0, K) T , (∆, 0) T , and (∆, K) T . Additional computations with 10 randomly selected pairs of (δ, κ) T over δ ∈ [0, ∆] and κ ∈ [0, K] revealed that the optimum is attained in one of the boundary values. Further, the Radon-Nikodym derivatives of V and W are estimated by a finite difference approximation in order to compute the test statistic.

The test rejects H 0 if the test statistics ∏ n i=1 π(z i ) exceeds a critical value, which (as well as the p-value) can be approximated by a Monte Carlo simulation, i.e., by a repeated random generating random variables X 1 , . . . , X n under H 0 , and we generate them 10,000 times here.

We perform the following particular numerical study. We compute the critical value of the α-test for n = 20 (or n = 40), λ = 0.25, σ 2 = 3, ∆ = 0.2, K = 1.1, and α = 0.05. Further, we are interested in evaluating the probability of rejecting this test for data generated from

F(x) = (1 -λ)Φ(x) + λΦ * σ(x), x ∈ I R, (10)
with different values of λ and σ2 . Its values are shown in Table 1 (for n = 20) and Table 2 (for n = 40), which are approximated using (again) 10,000 randomly generated variables from [START_REF] He | Quantile regression estimate for a class of linear and partially linear errors-in-variables models[END_REF]. The boldface numbers are equal to the power of the test (under the simple H 1 ). The proposed test seems meaningful, while its power is increased for n = 40 compared to n = 20; in addition, the power increases with an increasing λ if σ2 is retained; and the power also increases with an increasing σ2 if λ is retained.

Conclusion

The likelihood ratio test of f 0 against g 0 is considered in the situation that observations X i are mismeasured due to the presence of measurement errors. Thus instead of X i for i = 1, . . . , n, we observe Z i = X i + √ δV i with unobservable parameter δ and unobservable random variable V i . When we ignore the presence of measurement errors and perform the original test, the probability of type I error becomes different from the nominal value, but the test is still the most powerful among all tests on the modified level.

Under some assumptions on f 0 and g 0 and for δ < ∆, I EV 4 ≤ K, we further construct a minimax likelihood ratio test of some families of distributions of the Z i = X i + √ δV i , based on the capacities of the Huber-Strassen type. The test treats the composite null and alternative hypotheses, which cover all possible measurement errors satisfying the assumptions. The advantage of the novel test is that it keeps the probability of type I error below the desired value (α = 0.05) across all possible measurement errors. The test is performed in a straightforward way, while the user must specify particular (not excessively large) values of ∆ and K. We do not consider this a limiting requirement, because parameters corresponding to the severity of measurement errors are commonly chosen in a similar way in numerous measurement error models [START_REF] Carroll | Measurement Error in Nonlinear Models: A Modern Perspective[END_REF][START_REF] Saleh | R-estimation of the parameters of a multiple regression model with measurement errors[END_REF] or robust optimization procedures [START_REF] Xanthopoulos | Robust Data Mining[END_REF]. The critical value of the test can be approximated by a simulation. The numerical experiment in Section 4 illustrates the principles and performance of the novel test.

  for k even and skew-symmetric for k odd, k = 1, . . . , 4. Moreover, because | f 0 (x)| and | f (3) 0 (x)| are integrable, then lim x→±∞ | f 0 (x)| = 0 and lim x→±∞ | f (3) 0 (x)| = 0. Hence, using the expansion (3), we obtain

Table 1 .

 1 Probability of rejecting the test in the simulation with n = 20.

	Value of	λ	3	Value of σ2 4 5	6
	0.25		0.39 0.52 0.61 0.67
	0.35		0.50 0.67 0.75 0.81
	0.45		0.61 0.76 0.85 0.89

Table 2 .

 2 Probability of rejecting the test in the simulation with n = 40.

	Value of	λ	3	Value of σ2 4 5	6
	0.25		0.55 0.73 0.82 0.87
	0.35		0.72 0.86 0.93 0.96
	0.45		0.82 0.94 0.97 0.99

Acknowledgments:

The authors would like to thank two anonymous referees for constructive advice.

Conflicts of Interest:

The authors declare no conflict of interest.

The research of Jana Jurečková was supported by the Grant 18-01137S of the Czech Science Foundation. The research of Jan Kalina was supported by the Grant 17-01251S of the Czech Science Foundation.


Khalil Ghorbal
email: khalil.ghorbal@inria.fr

Christelle Kozaily
email: christelle.kozaily@inria.fr

On Covering Smooth Manifolds with a Q-arrangement of Simplicies: An inductive Characterization of Q-matrices

Keywords: Simplicial covering, degeneracy and overlaps, spherical geometry, low-dimensional topology, linear complementarity problem

This paper is concerned with a covering problem of smooth manifolds of dimension n -1 by stitching 2 n n-simplices formed with 2 n-lists of points along their common (n -1)-facets. The n-simplices are in bijective correspondence with the vertices of an n-dimensional hypercube; they could be degenerate and are allowed to overlap. We leverage the underlying inductive nature of the problem to give a (non-constructive) topological characterization. We show that for low dimensions such characterization reduces to studying the local geometry around the specific points serving to form the simplices, solving thereby the problem for n ≤ 3. This covering problem provides a geometric equivalent reformulation of a relatively old, yet unsolved, problem that originated in the optimization community: under which conditions on the n × n matrix M , does the so called linear complementarity problem given by w -M z = q, w, z ≥ 0, and w.z = 0, have a solution (w, z) for all vectors q ∈ R n . If the latter property holds, the matrix M is said to be a Q-matrix.

Introduction

Given a vector q ∈ R n and an n × n matrix M over the reals, the linear complementarity problem [START_REF] Cottle | The Linear Complementarity Problem[END_REF] asks whether there exist w, z ∈ R n satisfying w -M z = q, w, z ≥ 0, and w.z = 0, where x ≥ 0 means that x belongs to R n + , the non-negative orthant (or cone) of R n , and w.z is the scalar product of w and z. Let LCP(q, M ) denote the set of solutions for q. When LCP(q, M ) is non-empty for every vector q in R n , the matrix M is called a Q-matrix. When LCP(q, M ) is reduced to a singleton, that is there exists a unique solution for every q, M is called a P-matrix. While a satisfying characterization for P-matrices has been known since the late fifties [START_REF] Samelson | A partition theorem for Euclidean n-space[END_REF], the same cannot be said for Q-matrices despite several insights and serious attempts over the past sixty years.

To better appreciate the Q-matricity problem, and consequently its inherent difficulty, let us proceed by revisiting the related literature while applying Occam's razor to remove the unnecessary structure present in the original formulation, but superfluous for the existence of solutions.

The first step would be to interpret the existence of solutions as a covering problem of R n , thereby stepping away from thinking of Q-matricity as a property of the linear application represented by M [START_REF] Samelson | A partition theorem for Euclidean n-space[END_REF][START_REF] Katta | On the number of solutions to the complementarity problem and spanning properties of complementary cones[END_REF]. 1 To do so, let us start by inverting the original question: instead of fixing q ∈ R n and asking what are its solutions, we rather fix (w, z) and ask what are the vectors q that could be solved by (w, z)? The constraint w.z = 0 implies that at least n components of w and z must vanish, whereas the constraints w, z ≥ 0 force the n remaining components to be non-negative. Let J denote the subset of indices corresponding to those non-negative components and let M J denote the n × n square matrix obtained by restricting the n × 2n matrix I n -M to J. Then, any q in the image set M J (R n + ) must have a solution by construction. Therefore, asking for a solution for each q ∈ R n is equivalent to asking whether the 2 n cones M J (R n + ), called complementary cones, cover R n . The second step would be to notice that one can drop the positive homogeneity of cones [START_REF] Kelly | Q-matrices and spherical geometry[END_REF]. Indeed, as soon as q ∈ R n has a solution (w, z), the vector λq, for any positive scalar λ has a solution as well, namely (λw, λz). Moreover, the null vector has the trivial solution (0, 0) regardless of M . Thus, instead of R n , one can rather focus on a sphere S n-1 , where each (proper) ray of R n is represented uniquely by one point of the sphere. Thus complementary cones are represented by spherical (n -1)-simplices and each two neighbors share a common (spherical) (n -2)-simplex.

It now becomes clear that the choice of R as the base field as well as the entire vector space structure of R n can be dropped all together for they do not play any particular role when interpreting Q-matricity as a covering problem. One therefore should not expect a decomposition exploiting the vector space structure of R n to be insightful or useful to better understand the covering problem.

Contributions. We formally state the Q-covering problem (Definition 1) as an abstract, yet equivalent, formulation of Q-matricity. The key insight of such a reformulation resides in its inductive nature on which we rely to state a non-constructive topological characterization (Theorem 1). We show that in low dimensions such characterization reduces to studying the local geometry around the points serving to form the simplices, solving thereby the problem for n ≤ 3. In particular, Section 3 lists exhaustively under which conditions the Qarrangement is covering for the 2-sphere (Proposition 4). Conjecture 1 is a challenging quest that asks whether our current understanding of the problem still hold for n ≥ 4. It pertains to understanding the vertex set of the holes left after laying all the simplices on the sphere.

Q-covering: definition and inductive characterization

We start by formally stating the original covering problem before stating the formulation we will be interested in. Let E n be the n-dimensional Euclidean space and let s 1 , . . . , s n and t 1 , . . . , t n be two n-lists of non-vanishing vectors in E n . A complementary cone is a cone spanned by n vectors {a 1 , . . . , a n } satisfying a i ∈ {s i , t i } for all i, that is the set {x ∈ E n | ∃λ 1 , . . . , λ n ≥ 0. x = i λ i a i }. A complementary cone is non-degenerate if its generators are linearly independent. The two n-lists are said to be non-degenerate if all complementary cones are non-degenerate. The original covering problem asks whether E n is included in the union of all complementary cones. 2The arrangement of complementary cones, known as the Q-arrangement, is not arbitrary: each cone has n neighbors where two cones are neighbors if and only if they have n -1 common generators. In fact, the cones are in correspondence with the vertices of an n-dimensional hypercube graph Q n where the neighboring relationship is represented by the adjacency of the vertices of Q n . Stitching together all the cones, one at a time, along their common (n -1)-facet amounts to following the longest Hamiltonian cycle of Q n (of length 2 n ). Notice that the collection of simplices need not form a simplicial set [START_REF] Goerss | Simplicial Homotopy Theory[END_REF] as the intersections of simplices need not be reduced to lower dimensional simplices.

As alluded to in the introduction, it is relevant to observe that as soon as a non-zero vector q is covered, then so is λq for any positive scalar λ. Thus by introducing the equivalence relation over E n defined by u v if and only if u = λv for some positive scalar λ, one can equivalently study the covering problem on the quotient space E n / instead of E n . Since q = 0 is trivially covered as it belongs to all complementary cones, it suffices to study the covering of (E n \ {0}) / which can be represented by S n-1 (indeed, the space obtained by puncturing a single point from the Euclidean space E n is homeomorphic to the sphere S n-1 ). Although removed, the center of the sphere S n-1 plays a role in fixing the representatives of the original vectors s i and t i on S n-1 . It is therefore still needed to properly define the problem. In summary, in order to define the covering problem, the basic data that one needs consists of: a smooth manifold X of dimension n, a point o ∈ X, a neighborhood U (o) ⊆ X of o and two n-lists of points on the boundary of U (o). For convenience, we fix X to the sphere S n in the sequel. The Q-covering problem is formally stated next and can be thought of as an abstract, yet equivalent, formulation of the original covering problem.

Definition 1 (Q-covering). Let o be a point in the unit sphere S n , and let B(o) ⊆ S n be an open ball of radius 1 centered at o. Let S n-1 (o) = ∂B(o), the boundary of B(o) (which, as the notation suggests, is itself a sphere of dimension n -1). Given two n lists of points {s 1 , . . . , s n } and {t 1 , . . . , t n } on S n-1 (o), consider the 2 n spherical (n -1)-simplices C j = a 1 , . . . , a n where a i ∈ {s i , t i }. The Q-covering decision problem asks whether the Q-arrangement of the simplices C j covers entirely S n-1 (o)? That is whether the inclusion S n-1 (o) ⊆ Σ(o) holds, where

Σ(o) = ai∈{si,ti} a 1 , . . . , a n .
One says that a point q ∈ S n-1 (o) is covered if it belongs to a simplex C j .

We will prefer the more concise notation n i=1 [s i , t i ] to denote the union Σ(o) of the simplices in Definition 1. Remark 1. While the use of the ⊕ operator is introduced and subsequently used as a notation convenience, it found its origin as (yet another) equivalent formulation of the original covering problem as the following Minkowski sum. Each pair {s i , t i } encodes a generalized line L i denoted [s i , t i ] and defined as L i = {x ∈ E n | ∃λ, β ≥ 0; x = λs i +βt i and λβ = 0}. The union of all complementary cones is therefore equal to the Minkowski sum

n i=1 [s i , t i ].
Once the points s i and t i are fixed on S n-1 (o), drawing all the facets of all the simplices partitions the sphere S n-1 (o) into cells. Definition 2 (Cell). A cell is a closed non-empty connected subset of S n-1 (o) delimited by an (n -2)-facet in each direction and such that its interior does not intersect any other facet.

A cell is not necessarily simplicial nor convex. In general, an (n -1)-simplex does not correspond to a unique cell, but could be partitioned into several cells. Figure 1 shows two possible configurations for n = 3. As shown below, however, a cell cannot be partially covered, it either belongs to Σ(o) or it is entirely not covered. Lemma 1. Let p, q ∈ Σ(o) such that there exists a continuous path from p to q that does not intersect any (n -2)-facet of all the (n -1)-simplices defined by the two n-lists of points s i and t i . Then any point in that path is also in Σ(o).

Proof. Without loss of generality, we can write the continuous path from p to q as r(t) = n i=1 α i (t)v i where t is a real parameter in the interval [0, 1], v i ∈ {s 1 , . . . , s n , t 1 , . . . , t n }, α i (t) > 0 for all t, p = r(0), and q = r(1). Since p is in Σ(o), it must be in the interior of a (n -1)-simplex, C p say, and likewise, q must belong to the interior of a (n-1)-simplex C q . If there exists t such that r(t) ∈ Σ(o), then the path must exit C p ∪ C q crossing a (n -2)-facet and thereby contradicting the hypothesis. Thus no such t exists and the entire path must be in Σ(o).

Thus, it suffices to consider one point in the interior of a cell to check whether the cell is covered: if the point is covered, then the entire cell is in Σ(o), otherwise, the entire cell is not covered. This means that the hole left uncovered once all the simplices are laid down on the sphere are a union of cells. Definition 3 (Surrounded Point). We say that a point q ∈ S n-1 (o) is surrounded if and only if there exists an (open) neighborhood U ⊆ S n-1 (o) of q such that U is covered, i.e. U ⊆ Σ(o).

Theorem 1 (Localization).

If each cell has at least one surrounded vertex (0-simplex), then S n-1 (o) is covered.

Proof. Fix q in S n-1 (o). If q belongs to a (n-2)-facet of any cell, then it must belong to Σ(o) since, by construction, those facets are subsets of facets of the involved complementary (n -1)-simplices.

If q belongs to the interior of a cell C, then by hypothesis,

C has a surrounded vertex v, that is an (open) neighborhood U ⊆ Σ(o) that intersects C • . Let p ∈ U ∩ C • denote a point in this intersection. Since p, q ∈ C • ,
which is a connected open set, one can construct a continuous path starting and ending at p, passing through q and entirely in C • . Thus, by lemma 1, q is also in Σ(o). We thus proved, as required, that for any q ∈ S n-1 (o), q ∈ Σ(o).

The characterization provided by Theorem 1 requires a test for at least one vertex per cell in order to check that the entire sphere is covered. Since a vertex is necessarily common to several cells, this already reduces the number of points to check at the cost of checking a stronger property (surrounding) than the simple covering. A natural question therefore arises: what would be the minimal set of such vertices? In order to answer this question, let V (C) denote the set of vertices of a cell C. The set V (C) may not contain any of the original points a i . In this case, such cells are called ghost cells as they are not accessible from any a i (in the sense that any path starting within a ghost cell must cross a boundary in order to reach one of the a i 's). In dimension 2, ghost cells do not exist. While it is possible to construct such cells in higher dimensions (for instance, the cell G in Figure 1), we remarked that ghost cells enjoy the following interesting property.

Proposition 1. Let n = 3. Ghost cells are covered whenever they exist.

Proof. Let K denote a ghost cell and let A be a 1-facet of K (edge). Assume without loss of generality that A is generated by a 1 and a 2 . A divides the sphere into two hemispheres, one containing K, denoted by H A (K) and (the closure of) its complement. Let a 3 ∈ {s 3 , t 3 }. If a 3 ∈ H A (K) then K is covered by the 2-simplex given by a 1 , a 2 , a 3 as otherwise K would be cut by a facet, contradicting the assumption of K being a cell. We are thus left with the case where s 3 , t 3 ∈ H A (K) c . To form K, A must be crossed by another 1-facet B of K. For this crossing to hold, at least one generator g of B must be in H A (K) c . We distinguish three cases depicted below following the same order from left to right: (i) g = a 1 , (ii) g = a 2 and (iii) g = a 3 .

Case (i): If g = a 1 , at least one generator of B must be in H A (K) as otherwise B won't be crossing A and it must be a 2 (the only vector left) since s 3 , t 3 ∈ H A (K) c . As discussed above, if s 3 or t 3 belong to H B (K) then K is covered. Thus, suppose next that s 3 , t 3 ∈ H A (K) c ∩ H B (K) c . Consider the 1-facet C = a 1 , a 2 (which may support or not a 1-facet of K). None of A nor B are crossing C (they only touch in shared ends), and as A crosses B, both A and B must be in

H C (K). So K ⊆ H A (K)∩H B (K)∩H C (K). If an a 3 ∈ H C (K) then K ⊆ a 1 , a 2 , a 3
and is therefore covered (this relies on the specific position of a 3 regardless of whether C serves to form a 1-facet of K). Finally, if

s 3 , t 3 ∈ H C (K) c , then Σ(o) ⊆ H A (K) c ∪ H B (K) c ∪ H C (K) c = (H A (K) ∩ H B (K) ∩ H C (K)) c
and therefore it is impossible to complete the construction of K (as a ghost cell) because a 1 , a 2 ∈ V (K), the set of vertices of K.

Case (ii): If g = a 2 , at least one generator of B must be in H A (K) as otherwise B won't be crossing A and it must be a 1 (the only vector left) since

s 3 , t 3 ∈ H A (K) c . If an a 3 ∈ H B (K) then K is covered. Thus, suppose next that s 3 , t 3 ∈ H A (K) c ∩ H B (K) c . Then K ⊆ H A (K) ∩ H B (K) and Σ(o) ⊆ H A (K) c ∪ H B (K) c = (H A (K) ∩ H B (K)) c
and therefore, like in the previous case, K cannot be a ghost cell. (So the only difference with the previous case is that in this case, one simply cannot construct a ghost cell, whereas in the previous case, we showed constructively that it is covered if it exists.) Case (iii): g = a 3 with a 3 ∈ {s 3 , t 3 }. The 1-facet B has a 3 ∈ H A (K) c as a generator and must have another generator a i ∈ H A (K), i ∈ {1, 2}. Thus we distinguish two sub-cases. Sub-case(1):

a i = a 1 . If a 2 ∈ H B (K), then K ⊂ a 1 , a 2 , a 3 . If a 2 ∈ H B (K) c ∩ H A (K) then K ⊆ a 1 , a 2 , a 3 . If a 3 ∈ H A (K) c ∩ H B (K) then K ⊆ a 1 , a 2 , a 3 . We are thus left with a 2 , a 3 ∈ H A (K) c ∩ H B (K) c , but then Σ(o) ⊆ H A (K) c ∪ H B (K) c whereas K ⊆ H A (K) ∩ H B (K)
and once more K cannot be a ghost cell. Sub-case (2): a i = a 2 and K ⊆ a 1 , a 2 , a 3 .

We conjecture that the property holds for any finite dimension n. Conjecture 1. Ghost cells are covered whenever they exist.

Remark 2. Among all the proofs we had for n = 3, the proof detailed above seems to be the best candidate for a possible generalization in higher dimensions, perhaps with the help of a proof assistant (like Coq [START_REF]The coq proof assistant[END_REF]), to overcome the inherent combinatorial explosion.

Assuming Conjecture 1, Theorem 1 tells us that Q-covering is equivalent to checking whether the points s i and t i are surrounded. A key observation to understand under which conditions a point s i (or t i ) is surrounded is that, it suffices to "zoom in" on that point and analyze the (local) contributions of the different involved (n -1)-simplices. We formalize below this intuition. Since the index i is irrelevant for the upcoming discussion, we carry on with i = n for simplicity.

Let a n denote s n or t n and assume that a n ∈ S n-1 (o). Consider a ball B(a n ) ⊆ S n-1 (o) of radius 1 centered at a n . Let S n-2 (a n ) denote ∂B(a n ). and let o(a n ) denote the opposite of a n with respect to the point o. 3 Any point v ∈ S n-1 (o) has a unique representative v on S n-2 (a n ): it suffices to take the (unique) path of length π on S n-1 (o) that starts at a n , goes through v and ends at o(a n ), which necessarily intersects S n-2 (a n ) in a unique point v. For completeness, we set o(a n ) to a n .

Proposition 2. The point a n is surrounded if and only if S n-2 (a n ) ⊆ Σ(a n ) ∪ Σ (a n ) where Σ(a n ) = n-1 i=1 [s i , ti ] and Σ (a n ) = a1,...,an-1 s.t. an∈ a1,...,an-1,a n n-1 j=1 [ā j , ā n ] .
Proof. The sum Σ(a n ) encodes precisely the representatives of the (n -1)-simplices having a n as a vertex. The sum Σ (a n ) encodes subsets of all the remaining (n -1)-simplices (precisely those having a n as a vertex) participating in surrounding a n . Indeed, as soon as a n belongs to an (n -1)-simplex a 1 , . . . , a n-1 , a n , one has to account for exactly n -1 additional (n -1)-simplices contributing in surrounding a n , namely those obtained from a 1 , . . . , a n-1 , a n by substituting each a i by a n regardless of whether a n is in the interior or the boundary of the simplex (cf. to the gray regions shown in Figure 2 for an illustration in n = 3). All can be encoded using the same sum [ā

a 3 a 1 a 2 a 3 ′ a 3 a 1 a 2 a 3 ′ a 3 a 1 a 2 a 3 ′
1 , ā 3 ] ⊕ [ā 2 , ā 3 ] (as in Σ (a 3 )).
Remark 3. Once the n-lists of points are fixed on S n-1 (o), the Q-covering decision is independent from the point o in the following sense: only the relative positions of the involved simplices is relevant. This means that the Q-covering decision is invariant under any translation or uniform scaling of the sphere S n-1 (o). This invariance is also valid for the inclusion S n-2 (a n ) ⊆ Σ(a n ) ∪ Σ (a n ) of Proposition 2 and can be leveraged to symbolically compute the representative v: it suffices to take the orthogonal projection of v on T an , the tangent space to S n-1 (o) at a n , and consider in T an the equivalence classes with respect to . Indeed, such a projection amounts to simply translate the entire S n-2 (a n ) to T an . This observation becomes relevant when it comes to checking Q-matricity algorithmically: it is easier to compute an orthogonal projection of a symbolic vector than to compute the intersection of a spherical path and a (hyper) circle.

The main interest of proposition 2 resides in the inductive character it exhibits. Indeed, to solve the covering problem of S n-1 (o), one is lead to solve finitely many surrounding problems which are themselves similar (but in general not identical) to covering problems in S n-2 (a i ). Under some extra conditions, the inductive character becomes even more apparent. For instance, the following theorem states that when the considered collection of the 2 n simplices define a simplicial complex, the Q-covering is fully characterized inductively: whenever one zooms in around the points s i and t i , the same geometric structure is preserved.

Theorem 2 (Simplicial complex covering). The Q-covering defines a non-degenerate partition of S n-1 (o) if and only if for all i = 1, . . . , n, S n-2 (s i ) ⊆ Σ(s i ), S n-2 (t i ) ⊆ Σ(t i ), and Σ (s i ) = Σ (t i ) = ∅ .

Proof. Recall that in [START_REF] Samelson | A partition theorem for Euclidean n-space[END_REF], it is shown that under the non-degeneracy assumption, the n-simplices partition the sphere if and only if, each pair {s i , t i } is separated by all the great circles defined by dropping the index i in a 1 , . . . , a n , where a j ∈ {s j , t j } (that is all the boundary simplices obtained by dropping the ith index).

Necessity. Under the stated separation condition, ghost cells do not exist as the (n-2)-simplices intersect only on their common vertices [START_REF] Samelson | A partition theorem for Euclidean n-space[END_REF]. Therefore it suffices to focus on the s i and t i . By Theorem 1 and Proposition 2, S n-2 (s i ) ⊆ Σ(s i )∪Σ (s i ) (and similarly for t i ). If Σ (s i ) = ∅, then either two simplices overlap or some simplices are degenerate. Each case, however, contradicts the separation hypothesis according to [START_REF] Samelson | A partition theorem for Euclidean n-space[END_REF]. This leads to the stated condition.

Sufficiency. We have S n-2 (s i ) ⊆ Σ(s i ). If there exists a great circle that doesn't separate t i and s i , then Σ (t i ) would not be empty as t i belongs to a simplex having s i as a vertex. This clearly contradicts the hypothesis. Thus, for all pairs, the separation condition must hold.

We end this section by stating the following simple, yet useful, necessary condition on pairs {s i , t i } for a Q-covering to hold. We will assume that this condition holds in the sequel. Lemma 2. If s i = t i for an index i, then S n-1 (o) cannot be covered. Proof. If s i = t i then the point o(s i )(= o(t i )) cannot be covered by any simplex as the length of all 1-facets (spherical paths) is less than π.

Characterizing Q-covering for n = 3

In this section we present a full characterization of Q-covering for n = 3. This means that we are able to provide a set of constraints on the involved vectors t i , s i that are satisfied if and only if all the sphere is covered by a Q-arrangement. Consequently, this also provides a set of constraints on the entries of a matrix M to be a Q-matrix. We start by characterizing the simpler planar case to showcase how the method works.

Planar Q-covering

For n = 2, ghost cells do not exist. Theorem 3. S 1 (o) is covered if and only if the four involved vectors s 1 , s 2 and t 1 , t 2 are surrounded.

Proposition 2 states that to check if a 2 ∈ {s 2 , t 2 } is surrounded, one has to check whether the following inclusion holds S 0 (a 2 ) ⊆ Σ(a 2 ) ∪ Σ (a 2 ) where

Σ(a 2 ) = [s 1 , t1 ] and Σ (a 2 ) = a1 s.t. a2∈ a1,a 2 [ā 1 , ā 2 ] .
The inclusion above can be interpreted as follows: either a 2 does not participate in covering a 2 , thus Σ (a 2 ) = ∅ and the inclusion S 0 (a 2 ) ⊆ [s 1 , t1 ] must hold, or a 2 does play a role in covering a 2 totally or partially. If a 2 is in the interior of a simplex C = a 1 , a 2 , then a 2 is clearly surrounded. If a 2 is on the boundary of C, then either a 2 = a 2 or a 2 = a 1 . If a 2 = a 2 , the global covering of S 1 (o) fails (see Lemma 2). If, however, a 2 = a 1 , then the simplices with vertex a 1 can be also used to surround a 2 . Out of the four simplices, one is redundant and degenerate (namely a 1 , a 2 ), and surrounding with the two remaining simplices ( a 1 , a 2 and a 1 , a 2 ) can be equivalently encoded as S 0 (a 2 ) ⊆ [ā 1 , ā 2 ]. In summary: Proposition 3. For S 1 (o) to be covered, the point a 2 must be surrounded in one of the following ways:

1. S 0 (a 2 ) ⊆ [s 1 , t1 ] (Σ(a 2 ) suffices), 2. a 2 ∈ a 1 , a 2 • (a 2 is in the interior of a 1 , a 2 ), 3. a 2 = a 1 ∧ S 0 (a 2 ) ⊆ [ā 1 , ā 2 ]
(a 2 coincides with a 1 ).

In light of Remark 3, the inclusions S 0 (a 2 ) ⊆ [s 1 , t1 ] and S 0 (a 2 ) ⊆ [ā 1 , ā 2 ] can be effectively checked using orthogonal projections on the tangent space T a2 to S 1 (o) at a 2 . If v denotes the orthogonal projection of v on T a2 , this amounts to verify the respective inequalities ŝ1 t1 < 0 and â 1 â 2 < 0. Moreover, checking a 2 ∈ a 1 , a 2 • amounts simply to check that the determinants of the three matrices a 1 a 2 , a 2 a 2 , and a 1 a 2 have the same sign. As an immediate application, these conditions give a symbolic characterization of Q-matricity for n = 2. As custom in the literature, assuming s 1 = e 1 , s 2 = e 2 , and t 1 , t 2 are the columns of the matrix -m1 m2 m3 m4 , with m 2 1 + m 2 3 = m 2 2 + m 2 4 = 1, the conditions of Proposition 3 translate, for a 2 = e 2 , to the following set of constraints on the entries of M :

1. -m 1 < 0 2. -m 4 > 0 ∧ m 2 > 0 (if a 1 = e 1 ) or -det(M ), m 2 , -m 1 have the same sign (if a 1 = t 1 ) 3. -m 1 = 0 ∧ -m 3 = 1 ∧ -m 4 < 0
A similar reasoning applies to t 2 , e 1 , and t 1 and combining together all the constraints (5 at most per point) leads to a full symbolic characterization for Q-matricity in the plane. For instance, we can readily use such a characterization to state that if two points a 1 and a 2 are opposite (with respect to o) then the Q-covering of S 1 (o) fails. As we shall see in the next section, it is possible to have a Q-covering of S 2 (o) with degenerate 3-simplices that are reduced to an arc of length π (equivalently non-pointed complementary cones with respect to the original covering problem).

Spacial Q-covering

For n = 3, by Proposition 1, ghost cells are covered whenever they exist. It follows that Theorem 4. S 2 (o) ⊆ Σ(o) if and only if the 6 points s 1 , s 2 , s 3 and t 1 , t 2 , t 3 are surrounded.

According to Proposition 2, checking whether a 3 is surrounded amounts to check the inclusion S 1 (a 3 ) ⊆ Σ(a 3 ) ∪ Σ (a 3 ) where

Σ(a 3 ) = [s 1 , t1 ] ⊕ [s 2 , t2 ] and Σ (a 3 ) = a1,a2 s.t. a3∈ a1,a2,a 3 [ā 1 , ā 3 ] ⊕ [ā 2 , ā 3 ] . Proposition 4. If S 2 (o) ⊆ Σ(o)
then a 3 is surrounded in one of the following ways (where i ∈ {1, 2} and j = i):

1. S 1 (a 3 ) ⊆ [s 1 , t1 ] ⊕ [s 2 , t2 ] (Σ(a 3 ) suffices) 2. a 3 ∈ a 1 , a 2 , a 3 • (interior of a simplex) 3. a 3 ∈ a i , a 3 • ∧ S 1 (a 3 ) ⊆ [ā i , ā 3 ] ⊕ [ā j , ā j ] (two simplices from Σ(a 3 )) 4. a 3 = a i ∧ S 1 (a 3 ) ⊆ [ā i , ā 3 ] ⊕ [ā j , ā j ] (a 3 coincides with a i ) 5. a 3 ∈ a i , a 3 • ∧ ā j = ā 3 ∧ S 1 (a 3 ) ⊆ [ā i , āj ] ⊕ [ā 3
, āj ] (a mix from Σ(a 3 ) and Σ (a 3 ), cf. Figure 3 left)

6. a 3 ∈ a 1 , a 2 • ∧ a 3 (ā i ) ∈ āj , ā j ∧ S 1 (a 3 ) ⊆ [ā 1 , ā2 ] ⊕ [ā j , ā 3 ] (a mix from Σ(a 3 ) and Σ (a 3 ), cf. Figure 3 right) Proof.
In what follows, a i ∈ {s i , t i }, and a 12 ∈ {a 1 , a 2 }. If a 3 doesn't belong to any simplex a 1 , a 2 , a 3 then a 3 is surrounded if and only if S 1 (a 3 ) ⊆ [s 1 , t1 ] ⊕ [s 2 , t2 ]. Assume a 3 belongs to one or several simplices having a 3 as a vertex. Recall that a 3 = a 3 by Lemma 2. If a 3 belongs to the interior of any simplex a 1 , a 2 , a 3 , then it is surrounded. Otherwise it belongs to one or several boundaries (1-facets) without being in the interior of any simplex. There are three possible cases (a simplex in n = 3 is a spherical triangle): (i) a = a 12 , (ii) a 3 belongs to the interior of a 12 , a 3 , (iii) a 3 belongs to the interior of a 1 , a 2 .

Case (i). Fix a 12 to a 1 . (otherwise, it suffices to swap a 1 and a 2 in what follows). The four simplices having a 1 as a vertex can contribute to cover a 3 . Out of the 8 available simplices having a 3 as a vertex, two are redundant and two are degenerate. Thus only four can be effectively used to surround a 3 , namely a 1 , a 2 , a 3 , a 1 , a 2 , a 3 , a 1 , a 2 , a 3 , and a 1 , a 2 , a 3 . Since a 3 = a 1 , the problem can be equivalently encoded as

S 1 (a 3 ) ⊆ [ā 2 , ā 2 ] ⊕ [ā 1 , ā 3 ].
Case (ii). Fix a 12 to a 1 (otherwise, it suffices to swap a 1 and a 2 in what follows). If the great circle C = (a 1 , a 3 ) separates a 2 and a 2 , then a 3 is surrounded. This case can be equivalently encoded as

S 1 (a 3 ) ⊆ [ā 1 , ā 3 ] ⊕ [ā 2 , ā 2 ].
Otherwise a 2 and a 2 are on the same hemisphere. If both belong to C, then surrounding a 3 is impossible (all simplices belong to one hemisphere). So one of them, a 2 say, has to be in the interior of one of the hemispheres. For a 3 to be surrounded, C must separate a 2 and a 1 . If ā2 = a 3 (ā 1 ): then either ā 2 ∈ ā2 , ā 3 and thus a 3 cannot be surrounded, or ā 2 ∈ ā1 , ā2

• and thus if a covering holds, it would mean that a 3 belongs to the interior of the simplex given by a 1 , a 2 , a 3 , a case we treated already; or ā 2 = ā 1 and

S 1 (a 3 ) ⊆ [ā 2 , ā 3 ] ⊕ [ā 1 , ā2 ]. If ā2 ∈ ā 3 , a 3 (ā 1 ) • : then necessarily ā 2 /
∈ ā 3 , a 3 (ā 1 ) • , and since ā2 and ā 2 are not separated by C then either ā 2 ∈ a 3 (ā 1 ), ā1

• or ā 2 = ā1 . But in both cases Σ(a 3 ) suffices to surround a 3 , a case we also treated already. Finally, if ā2 ∈ ā1 , a 3 (ā 1 ) • , then in order to cover ā 1 , ā 3 (the only remaining simplex contributing to surrounding a 3 ), either ā 2 = ā 3 or ā 2 ∈ a 3 (ā 1 ), ā 3

• . In the latter case, Σ(a 3 ) suffices to surround a 3 on its own. We are thus left with ā 2 = ā 3 . This can be equivalently encoded as Case (iii). Let C denote the great circle (a 1 , a 2 ). If a 3 belongs to C, then we're back to case (ii). Suppose a 3 belongs to the interior of one hemisphere. If Both a 1 and a 2 are both on the same hemisphere as a 3 , then a 3 cannot be surrounded. Thus, a 1 say, must belong to the interior of the other hemisphere (otherwise, it suffices to swap the indices 1 and 2 in what follows). This separation can be equivalently encoded as

S 1 (a 3 ) ⊆ [ā 1 , ā2 ] ⊕ [ā 3 , ā2 ] (cf. to
S 1 (a 3 ) ⊆ [ā 1 , ā2 ] ⊕ [ā 1 , ā 3 ]
. It remains to cover ā1 , ā 1 with the only two remaining simplices involving a 2 which fails precisely when a 3 (ā 2 ) ∈ ā1 , ā 1 (cf. to Figure 3 (right) to help visualize the different contributions).

a 3 a 1 a 2 a 1 ′ a 2 ′ a 3 ′ a 3 a 1 a 2 a 1 ′ a 2
. S 1 (a 3 ) ⊆ [s 1 , t1 ] ⊕ [s 2 , t2 ] (Σ(a 3 ) suffices) 2. a 3 ∈ a 1 , a 2 , a 3 • (interior of a simplex) 3. a 3 ∈ a i , a 3 • ∧ S 1 (a 3 ) ⊆ [ā i , ā 3 ] ⊕ [ā j , ā j ] (two simplices from Σ(a 3 ))
As explained for n = 2, all these conditions could be easily translated to conditions on the entries of a 3 × 3 symbolic matrix M (25 at most per point in the general case) to get a symbolic characterization of Q-matricity for n = 3. (Notice that this requires to compute the orthogonal space of a symbolic vector, which can be done symbolically be selecting which components of the vector are non-vanishing.)

Related work

The current work is part of an extensive and rich literature, initiated almost seventy years ago, about characterizing and/or efficiently recognizing a Q-matrix. Below we restrict our attention to topological and geometric approaches that are not specific to particular sub-classes of the problem. Spherical Geometry. In the late seventies, Kelly and Watson applied spherical geometry in their paper [START_REF] Kelly | Q-matrices and spherical geometry[END_REF] providing a (non-constructive) characterization of non-degenerate Q-matrices. More precisely, the authors established that if -s i and -t i are in different components of the complement of the complex formed by the (complementary) (n -1)-simplices obtained when removing the index i, then one gets a Q-matrix. While the reasoning is simple, the characterization doesn't provide a uniform property that all the pairs (or points) need to satisfy. Moreover, Q-covering is specifically about understanding whether the complex formed by the complementary n-simplices is covering, and one is left with studying a different problem (namely two points being in different components) for (at most) n complexes involving each 2 n-1 simplices.

Relaxations and Triangulation. By dropping the (only) non-linear condition w.z = 0, one gets a standard linear program which is well understood and easier to solve. Geometrically, such relaxation amounts to consider all n-simplices, complementary and non-complementary. If the non-complementary simplices are included in the complementary ones, the matrix M is known as a K-matrix. If moreover all the simplices are covering, then one immediately gets a characterization for Q-matrices. It is easy to see that if the opposite cone formed by the s i intersects the interior of the cone formed by the t i , then the entire space is covered by the union of all simplices (the feasible set is the entire space for each q). It thus remains to study under which conditions the non-complementary cones are included in the complementary ones. This was performed by Fredricksen, Watson and Murty in [START_REF] John T Fredricksen | A finite characterization of K-matrices in dimensions less than four[END_REF]Theorem 9] for n = 3. The main theorem states that if some specific set of finite points (precisely 3 × 5! = 360) are covered, then M is a Q-matrix. A similar generic approach consists in using all the points (s i and t i ) at once to build a regular triangulation then check for inclusions in complementary simplices [START_REF] Jesús | Q-matrix recognition via secondary and universal polytopes[END_REF]Theorem 1].

Simplicial Homology. Given the problem at hand, it is very reasonable to investigate the usefulness and insights of standard homology groups to understand Q-covering. As the considered set of simplices need not define a simplicial complex (degeneracy and overlaps are allowed), in [START_REF] Daniel | A homological characterization of Q-matrices[END_REF], Naiman and Stone exploited a related abstract simplicial complex called the nerve of the covering. Let V = {1, . . . , m} denote a set of vertices (0simplices) where m ≤ 2 n denotes the number of the non-degenerate n-simplices involved in the covering. An (abstract) simplex of the nerve is a subset W ⊆ V such that ∩ j∈W C j is non-empty. Unsurprisingly, the simplicial homology group H n-1 of the nerve is isomorphic to Z whenever the S n-1 (o) is covered and is isomorphic to the trivial group 0 otherwise ([13, Corollary 13]). Apart from the fact that the effective computation of the simplicial homology group has a non-elementary complexity (given the exponential number of the n-simplices involved), such approach doesn't exploit the underlying structure of Q-covering. The nerve can be defined for any collection of subsets which makes it a powerful theoretical tool, totally non-insightful to capture the topological properties of the Q-covering. Something this paper strives to investigate from a pure geometrical view point.

Monotonicity. Several attempts tackled successfully either sub-classes or larger ones with computationally practical properties hoping it would lead to a better understanding of Q-matrices. For instance, following the very first characterization of P-matrices [START_REF] Samelson | A partition theorem for Euclidean n-space[END_REF], the sign of principle minors of M were extensively studied. In [START_REF] Katta | On the number of solutions to the complementarity problem and spanning properties of complementary cones[END_REF], it has been shown that when M ≥ 0, M ∈ Q if and only if all the diagonal entries of M are positive. However in [START_REF] Walter | Counterexamples to Q-matrix conjectures[END_REF], Morris ended this quest by showing that Q-matrices cannot be characterized by signs of sub-determinants. As we have seen in Section 3, while checking the surrounding does require computing determinants, it involves non-trivial sets of vectors obtained by projecting on tangent spaces. Solutions' Multiplicities. Another interesting direction tackled the number of solutions and/or their parity which shed some light on the inherent difficulty of the problem. For instance, R 0 matrices (also known as superregular matrices) for which the LCP has a unique solution at q = 0 caught the attention of many. Karamardian [START_REF] Karamardian | An existence theorem for the complementarity problem[END_REF] first proved that if in addition, for some strictly positive q the LCP has also a unique solution, then M is a Q-matrix. Shortly after, Saigal strengthened Karamardian's result in [START_REF] Saigal | A characterization of the constant parity property of the number of solutions to the linear complementarity problem[END_REF] by proving that if the LCP has a unique solution for q = 0 and an odd number of non-degenerate solutions for some other vector q, then M is necessarily a Q-matrix. Later in the same decade, in their paper [START_REF] Aganagic | A note on Q-matrices[END_REF], Aganagic and Cottle proved that among P 0 matrices (i.e. matrices for which all principal minors are non-negative), the subclass of Q-matrices is equal to the subclass of regular matrices. Not long after, Pang showed in [START_REF] Pang | On Q-matrices[END_REF] that a similar characterization to that of P 0 matrices, holds for L-matrices. It is interesting to notice that this direction was particularly fruitful and lead to several non-trivial conjectures generalizing known facts for larger well known classes like for semi-monotone matrices. Some turned out to be false like in [START_REF] Jeter | An example of a nonregular semimonotone Q-matrix[END_REF] where Jeter and Pye provided a counterexample showcasing a semi-monotone 5 × 5-matrix that is Q but not R 0 . Using our characterization, we were able to generate an example in n = 3 showcasing that a covering with (flat) non-pointed complementary cones is actually possible starting from dimension 3. For instance, consider s 1 , s 2 , s 3 as the vectors of the standard basis, and t 1 = (-2, -4, -3), t 2 = -e 1 , and t 3 = (1, 1, 1). The cones s 1 , t 2 , s 3 and s 1 , t 2 , t 3 are two flat non-pointed cones and therefore the following 3 × 3 matrix is a Q-matrix but not an R 0 -matrix.

  2 1 -1 4 0 -1 3 0 -1   .

Conclusion

To the best of our knowledge, no established theory in algebraic topology deals with the covering problem of Definition 1. On an abstract level, we regard the problem as a (strict) generalisation of the standard simplicial sets allowing for degeneracy and overlaps. Apart from using the nerve of the covering (which is possible but not insightful), our attempts to unravel a more specific algebraic structure were so far, unfortunately, unsuccessful. We thus tackled the problem from a purely geometric point of view hoping to pave the way towards an adequate "homology" where overlaps are built-in in the theory. We firmly believe that without such theory, no satisfactory answer could be stated for higher dimensions.

One advantage of the current line of work on the application side is its ability to provide a symbolic characterization for Q-matrices in full generality (regardless of degeneracy) in the three dimensional case which, up to our knowledge, did not exist before. We found such a characterization useful in order to generate automatically counter-examples for serious conjectures out of reach with our understanding of Q-covering. For instance, while we knew that non-pointed cones are not allowed in dimension 2 and possible in dimension 5, it wasn't clear whether they can occur in dimensions 3 or 4. More importantly perhaps, is that the point of view we presented sheds some light on the quest for a Murty-like test for Q-matrices (requiring to only test the covering of a finite set of vectors) regardless of the correctness of Conjecture 1: if it holds, the initial points are all one needs to check Q-matricity, otherwise, we know precisely what are the additional points one needs to consider and the inherent difficulty in checking whether they are surrounded or not. While we lean towards the correctness of the conjecture, we measure the difficulty (if not impossibility) for a human being to exhaustively enumerate all the possible cases to provide a formal proof for any finite n (like we did in Proposition 1 for n = 3). This is where a proof assistant (like Coq [START_REF]The coq proof assistant[END_REF]) might be useful, with undoubtedly a mitigated satisfaction. This being said, we feel that bypassing this brute force approach requires a completely novel angle to attack the problem, which is yet to be found (algebraic insights are clearly missing).

Figure 1 :

 1 Figure 1: Cells (n = 3). The colored dots on the sphere represent the points s i and t i where each pair has a different color. The paths between them are the (spherical) 1-simplices. Complementary 2-simplices have three different colored dots as vertices (0-simplices). The cell G is a ghost cell. The cell C is not simplicial nor convex.

Figure 2 :

 2 Figure 2: Three configurations where a 3 ∈ a 1 , a 2 , a 3 together with their (local) contribution depicted in gray. All can be encoded using the same sum [ā 1 , ā 3 ] ⊕ [ā 2 , ā 3 ] (as in Σ (a 3 )).

Figure 3 (

 3 left) to help visualize the different contributions).

′ a 3 ′Figure 3 :Proposition 5 .

 335 Figure 3: Cases 5 (left) and 6 (right) of Proposition 4. Black arcs are simplices from Σ(a 3 ) whereas dashed arcs are from Σ (a 3 ). The red region in the left figure shows where ā 2 should not be for a 3 to be surrounded.

1

 1

From this perspective, the terminology Q-matricity itself might seem to be a misnomer. Nonetheless, thinking of Q-matricity as a property of the linear application M proved to be useful[START_REF] Cottle | On spherically convex sets and Q-matrices[END_REF].

The requirement that all the vectors s i and t i are non-vanishing becomes justified since as soon as s i (or t i ) vanishes for an index i, the covering problem asks whether finitely many degenerate cones can cover a full dimensional open set in E n , which is impossible.

The point o(an) should not be confused with -an in general since B(an) is a ball on a sphere and not a ball on an Euclidean flat space.