# On Covering Euclidean Space with Q-arrangements of Cones

Khalil Ghorbal, Christelle Kozaily

► To cite this version:

Khalil Ghorbal, Christelle Kozaily. On Covering Euclidean Space with Q-arrangements of Cones. 2025. hal-04444572v2

HAL Id: hal-04444572

https://inria.hal.science/hal-04444572v2

Preprint submitted on 6 Jul 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# On Covering Euclidean Space with Q-arrangements of Cones

Khalil Ghorbal and Christelle Kozaily

INRIA, France

## Abstract

This paper is concerned with a covering problem of Euclidean space by a particular arrangement of cones that are not necessarily full and are allowed to overlap. The problem provides an equivalent geometric reformulation of the solvability of the linear complementarity problem defining the class of Q-matrices. Assuming feasibility, we rely on standard tools from convex geometry to study maximal connected uncovered regions, we term *holes*. We then use our approach to fully characterize the problem for dimension 3, regardless of degeneracy. We further provide, for $n \le 3$, an algebraic characterization for the class of Q-matrices. That is, we show that, $M$ is a Q-matrix if and only if its entries belong to an explicit semi-algebraic set (in dimension 9) where all the involved polynomials are subdeterminants of $M$. We showcase the usefulness of such a characterization by generating 3-by-3 Q-matrices with specific interesting properties on the involved cones.

**Keywords.** linear complementarity problem, Q-matrix, covering of Euclidean space, convex geometry, algebraic characterization, symbolic computation.

AMS/MSC. 90C33, 68W30, 03C10.

## Introduction

Given a vector $q \in \mathbb{R}^n$ and an $n \times n$ matrix $M$ over the reals, the *linear complementarity problem*, LCP$(q, M)$, asks whether there exists a pair $w, z \in \mathbb{R}^n$ satisfying $w - Mz = q$, $w, z \ge 0$, and $w.z = 0$, where $w, z \ge 0$ means that $w$ and $z$ belong to $\mathbb{R}_+^n$, the nonnegative orthant of $\mathbb{R}^n$, and $w.z$ is the scalar product of $w$ and $z$ (cf. [Cottle et al., 2009]). When LCP$(q, M)$ admits a solution, it is said to be *solvable*. When a solution satisfying only $w, z \ge 0$ exists (i.e. when dropping the scalar product requirement), LCP$(q, M)$ is said to be *feasible*. Related to the solvability and feasibility concepts, several classes of matrices were defined in the literature. Three classes are in particular relevant to this work. When LCP$(q, M)$ is feasible for all $q, M$ is called an *S-matrix*. When LCP$(q, M)$ is solvable for all $q, M$ is called a *Q-matrix*. If furthermore such a solution is unique for all $q, M$ is called a *P-matrix*.

The solvability of linear complementarity problems was tackled from different angles.

In [Cottle et al., 1981a], a focus on the linear application represented by $M$ proved to be useful. Degree theory [Pang, 1979, Chapter 6] was exploited for certain classes of structured matrices (e.g. [Garcia et al., 1983]), and more recently a new sufficient condition was provided in [Radons and Tonelli-Cueto, 2023]. More in line with this work, [Murty, 1972] pointed out an insightful geometric interpretation for LCP$(q, M)$. Instead of fixing $q \in \mathbb{R}^n$ and solving for $w$ and $z$, one could instead fix the pair $(w, z)$ and solve for the vectors $q$. The constraints $w, z \ge 0$ and $w.z = 0$ imply that, for each $i$, either $w_i$ or $z_i$ has to vanish and the remaining component has to be nonnegative making $q$ an element of a cone spanned by some columns of $-M$ and $I$ (the identity matrix in dimension $n$). In turn, asking for a solution for each $q \in \mathbb{R}^n$ becomes equivalent to asking whether $\mathbb{R}^n$ is covered by the union of these cones.

In the late fifties, [Samelson et al., 1958] characterized a partition of Euclidean space with $2^n$ full cones using a separation condition. Their characterization provides a geometric reformulation of what later became known as the class of P-matrices (with the separation being captured as the positiveness of the principal minors of $M$). Several serious attempts have been subsequently made to characterize the class of Q-matrices concisely and, despite the rich literature devoted to the problem, it remains open even for low dimensions, see e.g. [Fredricksen et al., 1986]. [Kelly and Watson, 1979] proved that, while the set of non-degenerate Q-matrices is open for $n = 3$, it is not for $n = 4$. Some subclasses of Q-matrices with adequate structures were easier to tackle. The problem of recognizing a P-matrix was shown to be co-NP-complete by [Coxson, 1994]. A larger class than P-matrices relies on oriented matroids realized by $I$ and $-M$ was also studied in [Watson, 1974, Morris Jr, 1986]. [Morris Jr, 1988] provided a (counter) example for $n = 4$ showing that the signs of subdeterminants of $M$ alone are not enough to characterize Q-matrices. As of today, the cost of checking generic Q-matrices remains prohibitive in practice, see [Aganagić and Cottle, 1978, Naiman and Stone, 1998], and the best known practical approach presented in [De Loera and Morris Jr., 1999] uses secondary and universal polytopes and is limited to dimensions less than 10. It's worth noting that these theoretical facts about the hardness of the problem are in contrast
with the complexity of solving LCP($q, M$) for a fixed $q$ and $M$. Indeed, while the general problem (over the integers) has been shown to be NP-complete by [Chung, 1989], there are specific practical instances for which one can go beyond thousands of variables (cf. e.g. [Brugnano and Casulli, 2008]).

The rest of the paper is organized as follows. After a formal introduction of the problem (Section 1), we investigate the relatively simpler feasibility problem to arrive at useful cones we term minimal (Section 2). Section 3 focuses on solvability where we revisit the original separation condition by [Samelson et al., 1958] in Section 3.1 and show a similar necessary (but not sufficient) condition for Q-matrices. This condition insinuates a lead to refine the standard concept of separation using intersections of some specific cones instead of hyperplanes separating vectors (Sections 3.2 and 3.3). These different ingredients are leveraged in Section 4 to give a complete characterization of Q-matrices in dimension 3 regardless of degeneracy. Finally, section 5 provides an equivalent algebraic characterization in terms of signs of the subdeterminants of the involved matrix.

**Contributions.** To the best of our knowledge, the following are novel results related to Q-matrices. Proposition 1 gives a necessary condition useful to characterize S-matrices, i.e. the feasibility problem, by triangulating the space. Proposition 4 provides a necessary separation condition for the Q-covering problem (cf. Definition 2). Proposition 5 gives an interesting covering property of particular relevant cones we term minimal cones. The remaining results concern only dimension 3. Theorem 1 characterizes uncovered regions assuming feasibility. Corollary 1 strengthens [Garcia et al., 1983, Theorem 4.7] by dropping the strong non-degeneracy assumption. Theorem 2 gives necessary and sufficient conditions for the Q-covering problem. The algorithms in Section 5 provide an explicit algebraic characterization for Q-matrices as sign conditions of the subdeterminants of the involved matrix (Theorem 6). Such a characterization turned out to be very convenient to generate Q-matrices with interesting properties (cf. Examples 1 and 2).

# 1 Q-covering

Let $g_1, \dots, g_m \in \mathbb{R}^n$. The polyhedral cone or simply cone (resp. linear subspace) spanned by the vectors $g_i$ will be denoted by $\langle g_1, \dots, g_m \rangle$ (resp. $(g_1, \dots, g_m)$). A cone is said to be non-degenerate if its generators are linearly independent (as vectors in $\mathbb{R}^n$). It is degenerate otherwise. A non-degenerate cone is said to be full (or simplicial) if its generators form a basis of $\mathbb{R}^n$.<fnref n="1" /> When $C = \langle g_1, \dots, g_m \rangle = (g_1, \dots, g_m)$, $C$ is said to be flat. Flatness and degeneracy should not be confused. A degenerate cone is not necessarily flat (e.g. the half line $\langle g_1, g_1 \rangle$, with $g_1 \neq 0$). Recall that a cone is said to be non-pointed if it contains both a nonzero vector and its opposite. It is pointed otherwise. Thus, while a flat cone is necessarily non-pointed, the converse is not necessarily true: for instance, a (closed) half-plane is both non-pointed and non-flat. The relative interior of a cone $C$ will be denoted by $C^\circ$.<fnref n="2" /> One proves that $\langle g_1, \dots, g_m \rangle^\circ$ is the set spanned by the positive linear combination of $g_1, \dots, g_m$.

Let $\{a_1, a'_1\}, \dots, \{a_n, a'_n\}$ denote $n$ pairs, or dyads, of vectors in $\mathbb{R}^n$. Let the matrices $A$ and $A'$ denote respectively $(a_1 \dots a_n)$ and $(a'_1 \dots a'_n)$. Consider the mapping

$$ [A, A'] : \quad \{0, 1\}^n \to \mathbb{R}^{n \times n} \\ b \mapsto [A, A']_b $$

where the ith column vector of the matrix $[A, A']_b$ is $a_i$ if $b_i = 1$ and $a'_i$ otherwise. A complementary cone, or c-cone, $C$ is the cone spanned by the column vectors of $[A, A']_b$ for some valuation of $b$, that is $C = [A, A']_b(\mathbb{R}_+^n)$, the image set of $\mathbb{R}_+^n$ through the linear application represented by $[A, A']_b$. We call the column vectors of $[A, A']_b$, the generators of the c-cone $C$. A complementary face, or a c-face, is a face of a c-cone [Rockafellar, 1997, Section 18]. An element of a c-face is a nonnegative combination of $m$, $1 \le m \le n$, column vectors of $[A, A']_b$ [Rockafellar, 1997, Corollary 18.3.1]. When the subspace spanned by a face $F$ has dimension $n-1$, $F$ is called a facet. We define similarly a complementary linear subspace, or c-subspace, as the set of linear combinations of $m$, $1 \le m \le n$, columns of $[A, A']_b$ for some $b \in \{0, 1\}^n$.

**Definition 1** (Covered and surrounded sets). A vector is said to be covered if it belongs to a c-cone. A subset of $\mathbb{R}^n$ is said to be covered if all its vectors are covered. A vector is said to be surrounded if it has a covered neighborhood. A subset of $\mathbb{R}^n$ is said to be surrounded if all its vectors are surrounded.

In this work we investigate what conditions the pair $\{a_i, a'_i\}$ has to satisfy for Euclidean space to be covered. Formally, we are interested in the following problem.

**Definition 2** (Q-covering). Let $\{a_i, a'_i\}$, $i = 1, \dots, n$ denote a list of $n$ dyads of vectors in $\mathbb{R}^n$. The Q-covering decision problem asks whether $\mathbb{R}^n$ is covered, that is whether $\Sigma = \mathbb{R}^n$ where

$$ \Sigma = \{a_1, a'_1\} \oplus \dots \oplus \{a_n, a'_n\} := \bigcup_{b \in \{0, 1\}^n} [A, A']_b(\mathbb{R}_+^n). $$

We adopt the sum notation for $\Sigma$ in the sequel. We observe that $\Sigma$ is invariant under any permutation of the indices ($\oplus$ is commutative). We think of the vector $a'_i$ as the dual or the symmetric partner of $a_i$ in

<footnote n="1">¹We warn the reader that, some authors, e.g. [Cottle et al., 2009], refer to simplicial complementary cones as non-degenerate.</footnote>

<footnote n="2">²In classical textbooks, e.g. [Rockafellar, 1997], $\langle g_1, \dots, g_m \rangle$ is denoted by cone$\{g_1, \dots, g_m\}$ and the relative interior of $C$ is denoted by ri $C$.</footnote>
the sense that Σ remains invariant when swapping $a_i$ and $a'_i$ for any $i$. The prime ‘’ can be thought of as an involutive operator providing the symmetric partner of $a_i$. For instance, the opposite is a very special ‘’ operator: when $a'_i = -a_i$, for all $i$, Σ is the partition of $\mathbb{R}^n$ into the $2^n$ standard orthants.

If $L$ is a non-singular matrix, then $q \in \mathbb{R}^n$ is covered if and only if $q$ belongs to a c-cone $\langle a_1, \dots, a_n \rangle$ say, which is equivalent to $Lq \in \langle La_1, \dots, La_n \rangle$. Therefore, the Q-covering problem is invariant under non-singular linear transformations of the involved vectors. If all c-cones are degenerate, $\mathbb{R}^n$, as a Baire space, cannot be covered. So for $\Sigma$ to be covering, at least one c-cone must be full. There is thus no loss of generality in considering the standard basis $e_1, \dots, e_n$ of $\mathbb{R}^n$ respectively for $a_1, \dots, a_n$ (equivalently $A$ is the identity matrix) as required in the standard definition of the linear complementarity problem. Said differently, with respect to Definition 2, $\{e_1, -M_1\} \oplus \dots \oplus \{e_n, -M_n\} = \mathbb{R}^n$ if and only if $M = (M_1 \dots M_n)$ is a Q-matrix.

**Remark 1.** Regardless of the exact geometric intersection between two c-cones, each c-cone has $n$ (abstract) neighbors where two c-cones respectively generated by the column vectors of $[A, A']_b$ and $[A, A']_{b'}$ are neighbors if and only if the Hamming distance between $b$ and $b'$ is exactly one. Therefore, the c-cones can be put 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 in $Q_n$. Stitching together all c-cones along their common abstract facets, one at a time, following their neighborhood relationship, amounts to following the longest Hamiltonian cycle of $Q_n$ (of length $2^n$). In general, a family of convex sets that covers the space and for which the aforementioned neighboring relation makes sense is said to form a Q-arrangement. In [Kelly and Watson, 1979], Q-arrangements of full c-cones are studied.

By introducing the equivalence relation $\simeq$ over $\mathbb{R}^n \setminus \{0\}$ defined by $u \simeq v$ if and only if $u = \lambda v$ for some positive scalar $\lambda$, one observes that if a nonzero vector $q$ is covered then so is $q' \simeq q$. Thus one can equivalently study the covering problem of the quotient space $(\mathbb{R}^n \setminus \{0\})/\simeq$ instead of $\mathbb{R}^n$ (observing that $q = 0$ is trivially covered as it belongs to all c-cones). The quotient space $(\mathbb{R}^n \setminus \{0\})/\simeq$ is homeomorphic to the unit sphere $S_{n-1}$ where each half-line is represented by its unit generator. Similarly, each c-cone is represented by the (possibly degenerate) spherical $(n-1)$-simplex formed by the representatives of the $n$ generators of the cone. The spherical covering was for instance instrumental in [Kelly and Watson, 1979, Morris Jr, 1988, Cottle et al., 1981b]. (Notice, however, that the collection of the so obtained complementary simplices does not necessarily form a simplicial complex, see [Goerss and Jardine, 2012], since degeneracy and full dimensional intersections are allowed.)

In the sequel, we will find it useful to fix one or several coordinates of the Boolean vector $b$. We define

$$ \Sigma(a_i) := \bigcup_{b \in \{0,1\}^n} [A, A']_b(\mathbb{R}_+^n), \quad \Sigma(a'_i) := \bigcup_{b \in \{0,1\}^n} [A, A']_b(\mathbb{R}_+^n). $$

Clearly, for all $i$, $\Sigma = \Sigma(a_i) \cup \Sigma(a'_i)$. We say that $\Sigma(a_i)$ is the set of c-cones rooted at $a_i$ to make the syntactic requirement of the definition salient. (Indeed, $a_i$ could be among the generators of a c-cone without necessarily having $b_i = 1$. For instance when $a_2 \simeq a_1$, $a_1$ qualifies as a generator for $\langle a'_1, a_2 \rangle$ while $b_1 = 0$.) The set of c-cones will be denoted by $\text{cones}(\Sigma)$. Similarly, $\text{cones}(\Sigma(a_i))$ will denote the set of c-cones rooted at $a_i$. We further let $\Sigma_k$, $1 \le k \le n$, denote the union of all c-faces with $m \le k$ generators: for instance $\Sigma_1$ is the set of cones $\langle a_i \rangle$, $\langle a'_i \rangle$, $i = 1, \dots, n$. By convention, we let $\Sigma_0$ denote the set of vectors $a_1, \dots, a_n, a'_1, \dots, a'_n$.

**Definition 3** (Self surrounding). The vector $a_i$ is said to be self surrounded if it has a neighborhood covered by $\Sigma(a_i)$.

**Definition 4** (Lazy covering and surrounding). We say that $a_i$ is lazily covered if it belongs to $\Sigma(a'_i)$. It is lazily surrounded if it belongs to the topological interior of a c-cone rooted at $a'_i$.

We end this section by a simple definition which will be instrumental in the sequel. We use $\subseteq$ for set inclusion and $\subset$ for proper (or strict) set inclusion.

**Definition 5** (Hole). A hole is a non-empty open connected region in $\Sigma^c := \mathbb{R}^n \setminus \Sigma$, the complement of $\Sigma$ with respect to $\mathbb{R}^n$. A maximal hole is a hole $K$ such that if $K'$ is another hole, $K \subseteq K'$ implies $K' = K$.

Since $\Sigma$ is a union of finitely many closed sets, $\Sigma^c$ is an open set. In general, $\Sigma^c$ is a union of disconnected maximal holes. In this work, we will consider only maximal holes and refer to them simply as holes. For instance, for $n = 2$, $\Sigma = \{e_1, -e_2\} \oplus \{e_2, -e_1\}$, $\Sigma^c$ has two disconnected holes, namely $\langle e_1, -e_2 \rangle^\circ$ and $\langle -e_1, e_2 \rangle^\circ$. A hole is not necessarily convex. For instance, when $\Sigma = \{e_1, e_1\} \oplus \{e_2, e_2\} = \langle e_1, e_2 \rangle$, $\Sigma^c = \mathbb{R}^2 \setminus \langle e_1, e_2 \rangle$ is a non-convex hole.

## 2 Feasibility

When $\mathbb{R}^n$ is covered by c-cones, some necessary conditions are intuitively clear and plausible. For instance, one can easily see that Euclidean space cannot be covered by $\Sigma$ when the $2^n$ c-cones are all not full or when all vectors of $\Sigma_0$ belong to the same half-space. These conditions among others, collectively insinuate a broader necessary condition requiring the vectors of $\Sigma_0$ to be “well scattered” in the space to form enough full c-cones that are in turn sufficiently distributed to achieve a covering. For instance, it is well known that
at least $n+1$ full cones are required to cover $\mathbb{R}^n$: a full cone $C$ with an additional vector in the topological interior of $-C$ partition the space in $n+1$ full cones. <fnref n="3" /> We shall see that, in the context of this paper, a similar separation property follows from Proposition 4. Let $\Gamma = \langle a_1, a'_1, \dots, a_n, a'_n \rangle$. As we are working in dimension $n$, $\Gamma$ can be seen as the union of $(2n)$ cones generated by any $n$ vectors in $\Sigma_0$. The set of such cones will be denoted by cones($\Gamma$). We proceed to investigate under which conditions $\Gamma$ covers $\mathbb{R}^n$ ensuring feasibility. We do this in Proposition 1 after stating a technical lemma (akin to fan and barycentric triangulation) characterizing flat cones as those having 0 in their relative interior.

**Lemma 1.** Suppose that $0 \in \langle g_1, \dots, g_{m+1} \rangle^\circ$, $1 \le m \le n$, then $\langle g_1, \dots, g_{m+1} \rangle$ is flat of dimension at most $m$. Moreover, $\langle g_1, \dots, g_{m+1} \rangle = \cup_i G_i$ where $G_i$, $1 \le i \le m+1$, is the cone generated by $\{g_1, \dots, g_{m+1}\} \setminus \{g_i\}$.

*Proof.* There exist $\alpha_1, \dots, \alpha_{m+1} > 0$ such that $0 = \sum_{i=1}^{m+1} \alpha_i g_i$. Thus $(g_1, \dots, g_{m+1}) = (g_1, \dots, g_m)$. Let $x \in (g_1, \dots, g_m)$. Then $x = \sum_{i=1}^m \lambda_i g_i$ where $\lambda_i \in \mathbb{R}$. If $\lambda_i \ge 0$ for all $1 \le i \le m$, then $x \in \langle g_1, \dots, g_m \rangle \subseteq \langle g_1, \dots, g_{m+1} \rangle$. Otherwise, there exists a non-empty set of indices $J$ such that $\lambda_j < 0$ for all $j \in J$. Let $\lambda = \max_{j \in J} \{\frac{-\lambda_j}{\alpha_j}\} > 0$. So, for all $i$, $\lambda_i + \lambda \alpha_i \ge 0$. Then

$$x = x + \lambda \times 0 = \sum_{i=1}^{m} \lambda_i g_i + \lambda \sum_{i=1}^{m+1} \alpha_i g_i = \lambda \alpha_{m+1} g_{m+1} + \sum_{i=1}^{m} (\lambda_i + \lambda \alpha_i) g_i$$

and $x \in \langle g_1, \dots, g_{m+1} \rangle$. Therefore $(g_1, \dots, g_{m+1}) = (g_1, \dots, g_m) \subseteq \langle g_1, \dots, g_{m+1} \rangle \subseteq (g_1, \dots, g_{m+1})$. This proves the first part of the lemma. For the second part, if $J$ is empty, then $x \in G_{m+1}$, otherwise, if we let $k \in J$ denotes the index for which $\lambda = \frac{-\lambda_k}{\alpha_k}$, then one sees that $x \in G_k$. Thus $\langle g_1, \dots, g_{m+1} \rangle \subseteq G_{m+1} \cup (\cup_{j \in J} G_j) \subseteq \cup_{i=1}^{m+1} G_i$. The converse inclusion is immediate and the equality holds as stated. $\square$

**Proposition 1.** Let $k \ge n+1$ and $g_1, \dots, g_k$ denote $k$ nonzero vectors of $\mathbb{R}^n$. If $\mathbb{R}^n = \langle g_1, \dots, g_k \rangle$ then there exist $i_1, \dots, i_{m+1}$ with $1 \le m \le n$ such that $\langle g_{i_1}, \dots, g_{i_{m+1}} \rangle$ is a flat of dimension $m$.

*Proof.* The proof is by induction on $n$. For $n=1$, suppose $\mathbb{R} = \langle g_1, \dots, g_k \rangle$ with $k \ge 2$. Then $0 \in \langle g_1, \dots, g_k \rangle^\circ$ and there exist $\lambda_1, \dots, \lambda_k > 0$ such that $\sum_i \lambda_i g_i = 0$. If $g_i < 0$ for all $i$ we get a contradiction, so there exists $g_j > 0$. Similarly, if $g_i > 0$ for all $i$ we also get a contradiction, so there exists $g_\ell < 0$ and we have $\mathbb{R} = \langle g_j, g_\ell \rangle$ and $m=n=1$. Let $\pi$ denote the orthogonal projection onto the hyperplane $g_1^\perp$ ($g_1 \ne 0$ by hypothesis). Let $x \in g_1^\perp$ which is a subset of $\mathbb{R}^n = \langle g_1, \dots, g_k \rangle$. Then $x = \sum_{i=1}^k \lambda_i g_i$ with $\lambda_i \ge 0$. Thus $x = \pi(x) = \sum_{i=2}^k \lambda_i \pi(g_i)$ and therefore $g_1^\perp \subseteq \langle \pi(g_2), \dots, \pi(g_k) \rangle$. The converse inclusion is immediate by definition of $\pi$. Thus $g_1^\perp = \langle \pi(g_2), \dots, \pi(g_k) \rangle$. By the induction hypothesis, there exists $1 \le m \le n-1$ such that $\langle \pi(g_{i_2}), \dots, \pi(g_{i_{m+2}}) \rangle$ is a flat of dimension $m$. In particular $\pi(g_{i_2}), \dots, \pi(g_{i_{m+1}})$ are linearly independent. Assume without loss of generality that $i_j = j$. We have $0 = \sum_{j=2}^{m+2} \alpha_j \pi(g_j)$, with $\alpha_j > 0$. Moreover, for each $g_i$, there exists $\theta_i \in \mathbb{R}$ such that $g_i = \theta_i g_1 + \pi(g_i)$. Thus $0 = \sum_{j=2}^{m+2} \alpha_j (g_j - \theta_j g_1) = (-\sum_{j=2}^{m+2} \alpha_j \theta_j)g_1 + \sum_{j=2}^{m+2} \alpha_j g_j$. Let $\gamma = -\sum_{j=2}^{m+2} \alpha_j \theta_j$. If $\gamma > 0$, then by Lemma 1, $(g_1, \dots, g_{m+2}) = (g_1, \dots, g_{m+1}) = \langle g_1, \dots, g_{m+2} \rangle$. We further prove that $g_1, \dots, g_{m+1}$ are linearly independent. Suppose $0 = \sum_{i=1}^{m+1} \sigma_i g_i$ then $0 = \sum_{i=2}^{m+1} \sigma_i \pi(g_i)$ and since $\pi(g_2), \dots, \pi(g_{m+1})$ are linearly independent, $\sigma_i = 0$ for all $2 \le i \le m+1$. Thus $0 = \sigma_1 g_1$, $\sigma_1 = 0$, and $\langle g_1, \dots, g_{m+2} \rangle$ is a flat of dimension $m+1$, which is what we wanted to prove. If $\gamma = 0$, then by Lemma 1, $(g_2, \dots, g_{m+1}) = (g_2, \dots, g_{m+2}) = \langle g_2, \dots, g_{m+2} \rangle$. Thus $\langle g_2, \dots, g_{m+2} \rangle$ is a flat of dimension $m$. If $\gamma < 0$, then $g_1 \in \langle g_2, \dots, g_{m+2} \rangle$ and $\mathbb{R}^n = \langle g_2, \dots, g_k \rangle$. We repeat the same reasoning with $g_2$ and either we find a flat of dimension $m$ or $m+1$ or $g_2$ can be also removed from the list of generators till eventually reaching $n+1$ generators for $\mathbb{R}^n$ at which point $m=n$ and we are done. $\square$

**Proposition 1** will be used in Section 5 to characterize the feasibility in dimension 3. In the sequel, assuming $\Gamma = \mathbb{R}^n$, we show in Proposition 2 that the space can be covered by what we term minimal cones. Lemma 2 is akin to the anti-exchange property of $\mathbb{R}^n$ [Coppel, 1998, Chapter I, §3] and Lemma 3 can be seen as an application of the conical version of Caratheodory's theorem.

**Lemma 2.** Let $u, v, g_1, \dots, g_m \in \mathbb{R}^n$, $1 \le m \le n-1$, such that $u, g_1, \dots, g_m$ or $v, g_1, \dots, g_m$ are linearly independent. Then $u \in \langle v, g_1, \dots, g_m \rangle$ and $v \in \langle u, g_1, \dots, g_m \rangle$ if and only if $u \simeq v$. When $m=1$, the linear independence condition can be dropped.

*Proof.* There exist $\alpha, \lambda, \alpha_i, \lambda_i \ge 0$ such that $u = \alpha v + \sum_{i=1}^m \alpha_i g_i$ and $v = \lambda u + \sum_{i=1}^m \lambda_i g_i$. Assume $v, g_1, \dots, g_m$ are linearly independent (otherwise, swap $u$ and $v$ in what follows). We get $(1-\lambda\alpha)v = \sum_{i=1}^m (\lambda\alpha_i + \lambda_i)g_i$. The linear independence implies $1-\alpha\lambda = 0$ and $\alpha\lambda_i + \alpha_i = 0$ for all $i$. Thus $\alpha, \lambda > 0$ and $\alpha_i = \lambda_i = 0$ for all $i$ proving the statement. For $m=1$, dropping the linear independence hypothesis, the proof is by case distinction. If $\lambda\alpha_1 + \lambda_1 = 0$ then $\alpha, \lambda > 0$ and $\alpha_1 = \lambda_1 = 0$ and therefore $v \simeq u$. Likewise, if $\alpha\lambda_1 + \alpha_1 = 0$, $u \simeq v$. Suppose $\lambda\alpha_1 + \lambda_1 > 0$ and $\alpha\lambda_1 + \alpha_1 > 0$. If $1-\lambda\alpha < 0$ then $u \simeq -g_1$ and $v \simeq -g_1$ so $u \simeq v$. Otherwise $u \simeq v \simeq g_1$. $\square$

<footnote n="3">³This fact can be seen as a corollary of Stiemke's theorem [Cottle et al., 2009, Theorem 2.7.12].</footnote>
**Lemma 3.** Let $G = \langle g_1, \dots, g_n \rangle$ denote a cone in $\mathbb{R}^n$. Let $g$ be a nonzero vector in $G$ and let $G_i$ denote the cone generated by $\{g, g_1, \dots, g_n\} \setminus \{g_i\}$, $1 \le i \le n$. Then $G = \cup_i G_i$. If moreover $G$ is full then there exists a non-empty set of indices $J \subseteq \{1, \dots, n\}$ such that $G = \cup_{j \in J} G_j$, $G_j$ is full, and $G_j \subseteq G$, for all $j \in J$. Moreover $G_j = G$ if and only if $g \simeq g_j$.

*Proof.* We have $g = \sum_{i=1}^n \alpha_i g_i$ for some nonnegative coefficients $\alpha_i$ and, since $g \ne 0$, there exists a non-empty set of indices $J \subseteq \{1, \dots, n\}$ such that $\alpha_j > 0$ for all $j \in J$. Let $x \in G$, i.e. $x = \sum_{i=1}^n \beta_i g_i$ for some nonnegative coefficients $\beta_i$. Let $\lambda = \min_{j \in J} \{\frac{\beta_j}{\alpha_j}\} = \frac{\beta_k}{\alpha_k}$ for some $k \in J$. We then have, for all $i = 1, \dots, n$, $\beta_i - \lambda \alpha_i \ge 0$ and

$$x = \sum_{i=1}^{n} \beta_i g_i = \lambda g + \sum_{i=1}^{n} (\beta_i - \lambda \alpha_i) g_i = \lambda g + \sum_{i \neq k} (\beta_i - \lambda \alpha_i) g_i.$$

Thus $x \in G_k$ and $G \subseteq \cup_{j \in J} G_j \subseteq \cup_i G_i$. This proves the first statement. Suppose $G$ is full and $G_j$ is degenerate for an index $j \in J$, then $g$ belongs to the hyperplane $H_j$ generated by $g_i$, $i \ne j$.<fnref n="4" /> But then $g_j \in H_j$ (because $\alpha_j > 0$) and $G$ is itself degenerate, a contradiction. Thus $G_j$ is full for all $j \in J$. Since $g \in G$, $G_j \subseteq G$ for all $j$. If in addition $G \subseteq G_j$ for some index $j$, then by Lemma 2 (applied to $g$ and $g_j$ as $u$ and $v$), this is equivalent to $g \simeq g_j$. □

**Proposition 2.** Assume $\Gamma = \mathbb{R}^n$. Then for any $x \in \mathbb{R}^n$, there exists a minimal cone $G \in \text{cones}(\Gamma)$ containing $x$, that is $G$ is full and for any other full cone $G' \in \text{cones}(\Gamma)$, $G' \subseteq G$ implies $G' = G$.

*Proof.* Since $\Gamma = \mathbb{R}^n$, by the Caratheodory theorem, there exists a full cone $G_1$ with $n$ generators in $\Sigma_0$ such that $x \in G_1$ ($G_1$ needs not be unique). Let $g_1, \dots, g_n \in \Sigma_0$ denote the $n$ generators of $G_1$ and suppose there exists a nonzero vector $g_{n+1} \in \Sigma_0 \setminus \{g_1, \dots, g_n\}$ such that $g_{n+1} \in G_1$ and $g_{n+1} \ne g_i$ for all $1 \le i \le n$. By Lemma 3, there exists a full cone $G_2 \subset G_1$ containing $x$. Suppose without loss of generality that $g_1 \notin G_2$ (such a vector must exist by construction of $G_2$), so $G_2 = \langle g_2, \dots, g_{n+1} \rangle$. If $G_2$ itself contains a vector $g_{n+2} \in \Sigma_0 \setminus \{g_1, \dots, g_{n+1}\}$ such that $g_{n+2} \ne g_i$ for all $2 \le i \le n+1$, then again by Lemma 3, there exists a full cone $G_3 \subset G_2$ containing $x$. At step $k$, we ask if $G_k$ contains a vector $g_{n+k} \in \Sigma_0 \setminus \{g_1, \dots, g_{n+k-1}\}$ such that $g_{n+k} \ne g_i$ for all $k \le i \le n+k-1$. The process must terminate after at most $n$ steps since $\Sigma_0 \setminus \{g_1, \dots, g_{n+n}\}$ is empty. We let $G = G_k$, $1 \le k \le n$, where $G_k$ does not contain any vector from $\Sigma_0$ (apart from those in the equivalence classes of its generators with respect to $\simeq$). In particular there is no other cone $G' \in \text{cones}(\Gamma)$ such that $G' \subset G$. □

Minimal cones play an important role in locating holes. They will be for instance instrumental in Section 4 to characterize Q-covering for $n = 3$.

**Proposition 3.** Assume $\Gamma = \mathbb{R}^n$. If $\Sigma \subset \mathbb{R}^n$ then there exists a minimal cone $G \in \text{cones}(\Gamma) \setminus \text{cones}(\Sigma)$ such that $G \cap \Sigma^c$ is non-empty.

*Proof.* Let $x \in \Sigma^c$. By Proposition 2, there exists a minimal cone $G \in \text{cones}(\Gamma)$ containing $x$. The cone $G$ cannot be a c-cone since it contains $x$. So $G \notin \text{cones}(\Sigma)$. Clearly we have $x \in G \cap \Sigma^c$ and the intersection is non-empty. □

**Remark 2.** One can tighten the statement of Proposition 3 by saying that $G^\circ \cap \Sigma^c$ is a non-empty open set. If $x$ belongs to the interior of $G$ then $G^\circ \cap \Sigma^c$ is non-empty. Otherwise, since $\Sigma^c$ is an open set, a small perturbation of $x$ remains in $\Sigma^c$ while avoiding the boundaries of $G$. Thus $G^\circ \cap \Sigma^c$ is also non-empty.

While $\Gamma$ and $\Sigma$ are both finite unions of closed convex cones, they are only seemingly similar. An important difference between the two being convexity: $\Gamma$ is convex by definition, but $\Sigma$ is not. This difference introduces a substantial complexity to the covering problem. For instance, the extreme rays of $\Gamma$ (if any) are necessarily among the generators of $\Gamma$ [Rockafellar, 1997, Corollary 18.3.1]. This same property is far from obvious for $\Sigma$ as we shall see in Section 4. The next section investigates some interesting properties of $\Sigma$.

## 3 Solvability

We start by proving a necessary condition for $\mathbb{R}^n$ to be covered, namely, that for all $i$, $a_i$, $a'_i \ne 0$ and $a'_i \ne a_i$ (geometrically, this means that $\langle a_i, a'_i \rangle$ is not reduced to the origin nor is it a half-line).

**Lemma 4.** Assume there exists at least one full c-cone. If all full c-cones meet at a nonzero vector then $\Sigma \subset \mathbb{R}^n$. Moreover, if there exists an index $i$ such that $a_i = 0$ or $a'_i \simeq a_i$ then $\Sigma \subset \mathbb{R}^n$.

*Proof.* If $a_i = a'_i = 0$ for some index $i$, then all c-cones are degenerate contradicting the assumption. Assume next that, there exists at least one full c-cone and that for all $i$, either $a_i \ne 0$ or $a'_i \ne 0$. Suppose there exists a vector $p \ne 0$ that belongs to all full c-cones. The full c-cones cannot cover $-p$ as this would contradict the non-degeneracy assumption. This means that an open neighborhood $U$ of $-p$ is left to be covered by a finite number of degenerate cones, which is impossible ($\mathbb{R}^n$ is a Baire space).<fnref n="5" /> In particular, if $a_i = 0$ and $a'_i \ne 0$,

<footnote n="4">⁴In this paper, a hyperplane denotes a linear (or vector) subspace of dimension $n-1$.</footnote>

<footnote n="5">⁵Every complete metric space (such as Euclidean space) is a Baire space in which countable unions of closed sets with empty interior have also an empty interior.</footnote>
then all full c-cones meet at $p \simeq a'_i$ and the covering is impossible. Moreover, when $a_i \neq 0$ and $a'_i \simeq a_i$ then all c-cones meet at $p \simeq a_i$ and the covering is also impossible. $\square$

**Proposition 4** below states a necessary condition on pairs $\{a_i, a'_i\}$ drawing upon an existing result by [Samelson et al., 1958] characterizing the partition of Euclidean space into c-cones using separation which we now define.

**Definition 6 (Separation).** Let $H$ denote a hyperplane and let $h$ denote a nonzero vector orthogonal to $H$. Two vectors $u, v$ are said to be separated by $H$ if and only if the scalar products $u.h$ and $v.h$ are not zero and have opposite signs. (Geometrically, $u$ and $v$ belong each to a distinct open half-space bounded by $H$.)

## 3.1 A Necessary Separation Condition

**Proposition 4.** If $\Sigma = \mathbb{R}^n$ then for each index $i = 1, \dots, n$ there must exist a complementary hyperplane (that is a c-subspace of dimension $n-1$) separating the pair $\{a_i, a'_i\}$.

*Proof.* By Lemma 4, for all $i, a_i, a'_i \neq 0$ and $a_i \neq a'_i$. The proof is by contradiction. Fix $i$ and let $V_r, r = 1, \dots, 2^{n-1}$, denote the c-subspaces generated by the remaining $(n-1)$ vectors $a_j, a'_j, j \neq i$. If $\dim(V_r) < n-1$ for all $r$, then all c-cones are degenerate and $\Sigma \subset \mathbb{R}^n$. Thus, there must exist a non-empty subset of indices $S \subseteq \{1, \dots, 2^{n-1}\}$ such that $V_s$ is a hyperplane for all $s \in S$. Assume that the pair $\{a_i, a'_i\}$ is not separated by any hyperplane $V_s, s \in S$. If $a_i, a'_i \in V_s$ for all $s$, then again, all c-cones are degenerate and $\Sigma \subset \mathbb{R}^n$. Thus, there must exist a set of indices $K \subseteq S$ such that $a_i \notin V_k$ or $a'_i \notin V_k$ for all $k \in K$. Let $V_k(i), k \in K$, denote the closed half-space bounded by $V_k$ and containing either $a_i$ or $a'_i$ in its interior. We thus have $a_i, a'_i \in V := \cap_{k \in K} V_k(i)$. The boundary of $V$, denoted $\partial V$, is a subset of the union of the boundaries of $V_k(i)$. Since $V$ is a (closed) convex cone then $\langle a_i, a'_i \rangle \subseteq V$. We show by contradiction that the topological interior of $V$ is non-empty. Assume it is empty. Then $V$ is equal to its boundary $\partial V$ and $V = \partial V \subseteq \cup_{k \in K} V_k$. Since $a'_i \in V$, there exists an index $k_1 \in K$ such that $a'_i \in V_{k_1}$ and $a_i \notin V_{k_1}$. Thus $\dim(a_i, a'_i) = 2$ and we construct a sequence of vectors $p_j \neq 0, 1 \le j \le |K|$, such that $p_j \in \langle a_i, p_{j-1} \rangle^\circ$ with $p_1 = a'_i$. For each $j, p_j \in V$, so there exists an index $k_j \in K$ such that $p_j \in V_{kj}$. If $k_j = k_\ell$ for $1 \le j, \ell \le |K|$, $j \neq \ell$, then $p_j, p_\ell \in V_{kj} = V_{k_\ell}$, and $(a_i, a'_i) = (p_j, p_\ell) \subseteq V_{kj}$. But then $a_i, a'_i \in V_{kj}$, contradicting the fact that $k_j \in K$. Thus $k_1, \dots, k_{|K|}$ are all distinct making $K = \{k_1, \dots, k_{|K|}\}$. Now consider a vector $p \neq 0$ in $\langle a_i, p_{|K|} \rangle^\circ$. Then there exists $k_j \in K$ such that $p \in V_{kj}$ and therefore $(a_i, a'_i) = (p, p_j) \subseteq V_{kj}$, a contradiction. So the topological interior of $V$ is non-empty. We denote it by $V^\circ$. We show next that $-V^\circ$ is a hole. First, by definition of $V^\circ, V^\circ \subseteq V_k(i)$, thus $-V^\circ \subseteq V_k(i)^c$, for each $k \in K$. Therefore $-V^\circ \subseteq \cap_k V_k(i)^c = (\cup_k V_k(i))^c$. Second, let $C(a_i, V_r)$ denote the c-cone spanned by $a_i$ and the generators of $V_r$. For $k \in K$, since $V_k$ does not separate the pair $\{a_i, a'_i\}$ then $C(a_i, V_k) \cup C(a'_i, V_k) \subseteq V_k(i)$. Thus

$$ \Sigma_K := \cup_{k \in K} (C(a_i, V_k) \cup C(a'_i, V_k)) \subseteq \cup_{k \in K} V_k(i), $$

and $(\cup_{k \in K} V_k(i))^c \subseteq (\Sigma_K)^c$. Thus $-V^\circ \subseteq (\Sigma_K)^c$. Finally, all is left to cover $-V^\circ$ is a finite set of degenerate c-cones, namely $C(a_i, V_r)$ and $C(a'_i, V_r)$, $r \notin K$. Covering an open set with a finite number of degenerate cones is impossible (by Baire's theorem). So there must exist an index $s \in S$ such that $V_s$ is a hyperplane separating the pair $\{a_i, a'_i\}$. $\square$

With respect to the notations of the proof of Proposition 4, the seminal work of [Samelson et al., 1958] shows that $\Sigma$ partitions $\mathbb{R}^n$ if and only if, for each index $i = 1, \dots, n$ and for each $r = 1, \dots, 2^{n-1}$, the c-subspace $V_r$ is a hyperplane separating the pair $\{a_i, a'_i\}$. Proposition 4 shows that, for $\Sigma$ to be (only) covering, it is necessary that for each index $i$ at least one c-subspace $V_r$ is a complementary hyperplane separating the pair $\{a_i, a'_i\}$. We know that this necessary condition is not sufficient in general to prove that $\Sigma$ is covering. For instance, in the plane, let $a'_1 = -e_1 + e_2$ and $a'_2 = -e_1$. Then $\Sigma = \{e_1, a'_1\} \oplus \{e_2, a'_2\}$ covers only the closed upper half-plane. The pair $\{e_1, a'_1\}$ is separated by the line $(e_2)$ and the pair $\{e_2, a'_2\}$ is separated by the line $(a'_1)$.

In the next section we shift focus on how c-facets (instead of c-hyperplanes) might “separate” pairs via intersections.

## 3.2 Dyadic Covering

We shall see several interesting properties concerned with intersections of c-facets with the cone $\langle a_i, a'_i \rangle$. We start by stating three generic relevant intersections (all depicted in Fig. 1) that will be instrumental in the rest of the paper. Lemmas 5 and 6 play a role in the forthcoming Propositions 5 and 6. Lemma 7 shall be used in Section 4.

**Lemma 5 (Front Intersection (cf. Fig 1a)).** Fix $m \ge 2$ and let $C = \langle v_1, v_2, \dots, v_m \rangle$ and $C' = \langle v'_1, v_2, \dots, v_m \rangle$. If there exists a nonzero vector in $\langle v'_1, v_1 \rangle \cap \langle v_2, \dots, v_m \rangle$ then $\langle v'_1, v_1, v_2, \dots, v_m \rangle = C \cup C'$.

*Proof.* Let $c \in \langle v'_1, v_1, v_2, \dots, v_m \rangle$. There exist $\alpha'_1, \alpha_1, \dots, \alpha_m \ge 0$ such that $c = \alpha_1 v_1 + \alpha'_1 v'_1 + \sum_{i \ge 2} \alpha_i v_i$. By assumption, there exist $\lambda'_1, \lambda_1, \dots, \lambda_m \ge 0$, $(\lambda_1, \lambda'_1) \neq (0, 0)$, such that $\lambda_1 v_1 + \lambda'_1 v'_1 = \sum_{i \ge 2} \lambda_i v_i$. Suppose
<figure><img src="image_2.png" /></figure>

<figure><img src="image_3.png" /></figure>

<figure><img src="image_4.png" /><figcaption>Figure 1: Conical intersections</figcaption></figure>

$\lambda_1, \lambda'_1 > 0$ and let $\beta = \min\{\frac{\alpha_1}{\lambda_1}, \frac{\alpha'_1}{\lambda'_1}\} \ge 0$. Then

$$c = c + \beta \times 0 = \alpha_1 v_1 + \alpha'_1 v'_1 + \sum_{i \ge 2} \alpha_i v_i + \beta(-\lambda_1 v_1 - \lambda'_1 v'_1 + \sum_{i \ge 2} \lambda_i v_i) \\ = (\alpha_1 - \beta \lambda_1) v_1 + (\alpha'_1 - \beta \lambda'_1) v'_1 + \sum_{i \ge 2} (\alpha_i + \beta \lambda_i) v_i .$$

By definition of $\beta$, the coefficients of $v_1$ and $v'_1$ are both nonnegative and one of them has to vanish. Thus $c \in C \cup C'$. The same holds when $\lambda_1 = 0$ (resp. $\lambda'_1 = 0$) by taking $\beta$ as $\frac{\alpha'_1}{\lambda'_1}$ (resp. $\frac{\alpha_1}{\lambda_1}$). The converse inclusion is immediate. $\square$

**Lemma 6** (Side Intersection (cf. Fig 1b)). Fix $m \ge 2$ and let $C = \langle v_1, v_2, \dots, v_m \rangle$ and $C' = \langle v'_1, v_2, \dots, v_m \rangle$. If $\langle -v_1, v'_1 \rangle^{\diamond} \cap \langle v_2, \dots, v_m \rangle$ is non-empty then $\langle v_1, v'_1, v_2, \dots, v_m \rangle \subseteq C$.

*Proof.* By assumption, there exist $\alpha'_1, \alpha_1, \dots, \alpha_m \ge 0$ such that $\alpha_1(-v_1) + \alpha'_1 v'_1 = \sum_{i \ge 2} \alpha_i v_i$ with $\alpha_1, \alpha'_1 > 0$. Thus $v'_1 \in C$ and $\langle v_1, v'_1, v_2, \dots, v_m \rangle \subseteq C$. $\square$

**Lemma 7** (Back Intersection (cf. Fig 1c)). Let $G = \langle v_1, v'_1, v_2, \dots, v_{n-1} \rangle$ denote a full cone in $\mathbb{R}^n$. Suppose there exists a vector $p \ne 0$ such that $p \in \langle -v_1, -v'_1 \rangle \cap \langle v_2, \dots, v_n \rangle$ then $G^{\diamond} \subseteq (\langle v_1, v_2, \dots, v_n \rangle \cup \langle v'_1, v_2, \dots, v_n \rangle)^c$.

*Proof.* There exist $\lambda_1, \lambda'_1, \lambda_2, \dots, \lambda_n \ge 0$, $(\lambda_1, \lambda'_1) \ne (0, 0)$ such that

$$p = \lambda_1(-v_1) + \lambda'_1(-v'_1) = \sum_{i=2}^{n} \lambda_i v_i . \qquad (1)$$

If $\lambda_n = 0$ then $G$ is degenerate. Thus $\lambda_n > 0$. Let $g \in G^{\diamond}$. Then $g = \alpha_1 v_1 + \alpha'_1 v'_1 + \sum_{i=2}^{n-1} \alpha_i v_i$ with $\alpha_1, \alpha'_1, \alpha_2, \dots, \alpha_{n-1} > 0$. Suppose that $g \in \langle v_1, \dots, v_n \rangle$, then there exist $\beta_i \ge 0$ such that $g = \sum_{i=1}^n \beta_i v_i$. Thus $\alpha_1 v_1 + \alpha'_1 v'_1 + \sum_{i=2}^{n-1} \alpha_i v_i = \sum_{i=1}^n \beta_i v_i$ and

$$\alpha'_1 v'_1 + \sum_{i=1}^{n-1} (\alpha_i - \beta_i) v_i = \beta_n v_n . \qquad (2)$$

If $\beta_n = 0$ then $\alpha'_1 = 0$ (because $v_1, v'_1, v_2, \dots, v_{n-1}$ are linearly independent), which contradicts $\alpha'_1 > 0$. Thus $\beta_n > 0$. Since $\lambda_n, \beta_n > 0$ we can eliminate $v_n$ in Eq. 1 and Eq. 2. We get

$$(\beta_n \lambda'_1 + \lambda_n \alpha'_1)(-v'_1) + \sum_{i=1}^{n-1} (\beta_n \lambda_i + \lambda_n (\alpha_i - \beta_i))(-v_i) = 0 .$$

As $v_1, v'_1, v_2, \dots, v_{n-1}$ are linearly independent, all the coefficients must vanish. In particular, $\beta_n \lambda'_1 + \lambda_n \alpha'_1 = 0$ which implies $\lambda_n \alpha'_1 = 0$, a contradiction. Thus $g \notin \langle v_1, \dots, v_n \rangle$. Swapping $v_1$ and $v'_1$ in the discussion above, we prove that $g \notin \langle v'_1, v_2, \dots, v_n \rangle$ and therefore $G^{\diamond} \subseteq (\langle v_1, \dots, v_n \rangle \cup \langle v'_1, v_2, \dots, v_n \rangle)^c$ as stated. $\square$

**Proposition 5** states an interesting covering property of the cone $\langle a_i, a'_i \rangle$. Its proof requires the following technical lemma.<fnref n="6" />

**Lemma 8.** Let $G = \langle g_1, \dots, g_m \rangle$, $m \ge 2$, denote a cone in $\mathbb{R}^n$ and let $q \notin G$ be such that $\langle g_1, q \rangle$ is non-flat. Suppose there exists a nonzero vector in $\langle g_1, q \rangle^{\diamond} \cap G$ then there exists a nonzero vector in $\langle g_2, \dots, g_m \rangle \cap \langle g_1, q \rangle^{\diamond}$.

*Proof.* Let $p' \ne 0$ be in $\langle g_1, q \rangle^{\diamond} \cap G$. Then there exists $\lambda_1, \lambda > 0$ and $\alpha_1, \dots, \alpha_m \ge 0$ such that $p' = \lambda_1 g_1 + \lambda q = \sum_{i=1}^m \alpha_i g_i$. Since $q \notin G$ then $0 < \lambda_1 - \alpha_1$. Let $p = (\lambda_1 - \alpha_1)g_1 + \lambda q$. Then, $p \in \langle g_2, \dots, g_m \rangle \cap \langle g_1, q \rangle^{\diamond}$. If $p = 0$ then $-g_1 \simeq q$ ($q \ne 0$ because $q \notin G$), making $\langle g_1, q \rangle$ flat. Thus $p \ne 0$. $\square$

**Proposition 5.** The cone $\langle a_i, a'_i \rangle$ cannot be partially covered, i.e. either $\langle a_i, a'_i \rangle \subseteq \Sigma$ or $\langle a_i, a'_i \rangle^{\diamond} \subseteq \Sigma^c$.

<footnote n="6">⁶The original proof was by induction on $m$. The provided shorter constructive proof was suggested by Jean-Charles Gilbert in a private communication with the first author.</footnote>
**Proof.** We fix $i$ to $1$ for clarity. If $\dim(a_1, a'_1) \le 1$, then $\langle a_1, a'_1 \rangle \subseteq \Sigma$. Assume next that $\dim(a_1, a'_1) = 2$ (in particular $a'_1 \not\cong -a_1$). Suppose there exists $a \in \langle a_1, a'_1 \rangle^{\circ}$ such that $a \in \Sigma$. So $a$ belongs to a c-cone $C = \langle a_1, \dots, a_n \rangle$ say (otherwise swap $a_1$ and $a'_1$ in what follows). If $a'_1 \in C$ then, by convexity of $C$, $\langle a_1, a'_1 \rangle \subseteq C \subseteq \Sigma$. Assume $a'_1 \notin C$. By Lemma 8, $\langle a_1, a'_1 \rangle^{\circ}$ intersects the face $\langle a_2, \dots, a_n \rangle$ of $C$ in a nonzero vector. By Lemma 5, $\langle a'_1, a_1, \dots, a_n \rangle \subseteq \langle a_1, a_2, \dots, a_n \rangle \cup \langle a'_1, a_2, \dots, a_n \rangle$ which implies $\langle a_1, a'_1 \rangle \subseteq \Sigma$. Finally, if such an $a$ does not exist then $\langle a_1, a'_1 \rangle^{\circ} \subseteq \Sigma^c$, which ends the proof. $\square$

We further characterize when the cone $\langle a_i, a'_i \rangle$ is covered. It turns out that such a covering requires specific intersections with c-faces.

**Proposition 6.** Let $a_i, a'_i \in \mathbb{R}^n$. Then $\langle a_i, a'_i \rangle \subseteq \Sigma$ if and only if either $\dim(a_i, a'_i) \le 1$ or $\dim(a_i, a'_i) = 2$ and there exists a c-face $F_i := \langle a_1, \dots, a_{i-1}, a_{i+1}, \dots, a_n \rangle$ and a vector $p \ne 0$ such that one of the following conditions occurs:

$$1. \ p \in \langle a_i, a'_i \rangle \cap F_i, \quad 2. \ p \in \langle -a_i, a'_i \rangle^{\circ} \cap F_i, \quad 3. \ p \in \langle a_i, -a'_i \rangle^{\circ} \cap F_i.$$

In all cases, one has $\langle a'_i, a_1, \dots, a_n \rangle \subseteq \Sigma$.

**Proof.** We fix $i$ to $1$ for clarity. Suppose $\langle a_1, a'_1 \rangle \subseteq \Sigma$ and that $\dim(a_1, a'_1) = 2$. Let $a = \alpha_1 a_1 + \alpha'_1 a'_1$, $\alpha_1, \alpha'_1 > 0$. Since $a \in \Sigma$, then either (i) $a \in \langle a_1, \dots, a_n \rangle$ or (ii) $a \in \langle a'_1, \dots, a_n \rangle$ for some c-face $F_1 = \langle a_2, \dots, a_n \rangle$. For (i), one gets $\alpha_1 a_1 + \alpha'_1 a'_1 = \sum_{i=1}^n \beta_i a_i$ with $\beta_1, \dots, \beta_n \ge 0$. Thus $(\alpha_1 - \beta_1)a_1 + \alpha'_1 a'_1 = \sum_{i=2}^n \beta_i a_i$. Let $p = (\alpha_1 - \beta_1)a_1 + \alpha'_1 a'_1$. Then $p \ne 0$ as otherwise $\dim(a_1, a'_1) \le 1$.

* If $\alpha_1 - \beta_1 \ge 0$ then $p \in \langle a_1, a'_1 \rangle \cap F_1$ (case 1 of the statement).

* If $\alpha_1 - \beta_1 < 0$ then $p \in \langle -a_1, a'_1 \rangle^{\circ} \cap F_1$ (case 2 of the statement).

The same discussion holds by swapping $a_1$ and $a'_1$ for (ii), leading to case 3. For the converse, if $\dim(a_1, a'_1) \le 1$ then it is immediate that $\langle a_1, a'_1 \rangle \subseteq \Sigma$. Otherwise, one of the stated conditions holds. If the first condition holds, then by Lemma 5 $\langle a_1, a'_1, a_2, \dots, a_n \rangle \subseteq \langle a_1, a_2, \dots, a_n \rangle \cup \langle a'_1, a_2, \dots, a_n \rangle \subseteq \Sigma$. If the second condition holds, then by Lemma 6, $\langle a_1, a'_1, a_2, \dots, a_n \rangle \subseteq \langle a_1, \dots, a_n \rangle \subseteq \Sigma$. If the third condition holds, then by Lemma 6 $\langle a_1, a'_1, a_2, \dots, a_n \rangle \subseteq \langle a'_1, \dots, a_n \rangle \subseteq \Sigma$ and $\langle a_1, a'_1 \rangle \subseteq \Sigma$, as stated. $\square$

### 3.3 Surrounding

When the cone $\langle a_i, a'_i \rangle$ is degenerate, its front, side and back intersections with c-faces become ill-defined. We argue that these intersections are only relevant whenever $\langle a_i, a'_i \rangle$ is non-degenerate. We have already seen in Lemma 4 that $a_i \not\cong a'_i$ for all $i$ is a necessary condition for $\Sigma$ to be covering. We shall see next that when $\langle a_i, a'_i \rangle$ is flat, we can drop the pair altogether and reduce the dimension of the Q-covering problem by 1.

**Proposition 7.** Assume that $a_i \ne 0$ and suppose that $\langle a_i, a'_i \rangle$ is flat. Let $a_i^{\perp}$ denote the hyperplane orthogonal to $a_i$, and let $\bar{v}$ denote the orthogonal projection of a vector $v$ onto $a_i^{\perp}$. Then $\Sigma = \mathbb{R}^n$ if and only if the sum $\{\bar{a}_1, \bar{a}'_1\} \oplus \dots \oplus \{\bar{a}_{i-1}, \bar{a}'_{i-1}\} \oplus \{\bar{a}_{i+1}, \bar{a}'_{i+1}\} \oplus \dots \oplus \{\bar{a}_n, \bar{a}'_n\}$ covers $a_i^{\perp}$ (which is isomorphic to $\mathbb{R}^{n-1}$).

**Proof.** For clarity we fix $i$ to $1$. Let $h \in a_i^{\perp}$. Since $\mathbb{R}^n \subseteq \Sigma$, the vector $x_h := \alpha_1 a_1 + h$ with $\alpha_1 \in \mathbb{R}$, belongs to a c-cone $\langle a_1, \dots, a_n \rangle$ say. Thus $x_h = \sum_{i=1}^n \lambda_i a_i$, $\lambda_1, \dots, \lambda_n \ge 0$, and $h = x_h - \alpha_1 a_1 = (\lambda_1 - \alpha_1)a_1 + \sum_{i \ge 2} \lambda_i a_i$, and $h = \bar{h} = \sum_{i \ge 2} \lambda_i \bar{a}_i$ as stated. The same occurs if $x_h \in \langle a'_1, a_2, \dots, a_n \rangle$ since $a_1 \simeq -a'_1$. To prove the converse, let $x \in \mathbb{R}^n$ and decompose $x = \alpha_1 a_1 + h$ with $h \in a_i^{\perp}$. Thus $h$ belongs to some cone $\langle \bar{a}_2, \dots, \bar{a}_n \rangle$. Equivalently, there exist $\lambda_i \ge 0$ such that $h = \sum_{i \ge 2} \lambda_i \bar{a}_i$. We have $a_i = \gamma_i a_1 + \bar{a}_i$, $\gamma_i \in \mathbb{R}$, for each $i$. Therefore

$$x = \alpha_1 a_1 + h = \alpha_1 a_1 + \sum_{i \ge 2} \lambda_i \bar{a}_i = \alpha_1 a_1 + \sum_{i \ge 2} \lambda_i (a_i - \gamma_i a_1) \\ = \underbrace{(\alpha_1 - \sum_{i \ge 2} \lambda_i \gamma_i)}_{\alpha} a_1 + \sum_{i \ge 2} \lambda_i a_i$$

If $\alpha \ge 0$ then $x \in \langle a_1, \dots, a_n \rangle \subseteq \Sigma$ as required. If $\alpha < 0$ then there exists $\alpha' \ge 0$ such that $\alpha a_1 = \alpha' a'_1$ (using $a_1 \simeq -a'_1$) and $x \in \langle a'_1, \dots, a_n \rangle$ proving that $x \in \Sigma$ as well. $\square$

Self surrounding (cf. Definition 3) is in fact equivalent to a Q-covering problem in lower dimension.

**Proposition 8.** Assume that $a_i \ne 0$ and let $\bar{v}$ denote the orthogonal projection of a vector $v$ onto $a_i^{\perp}$, the hyperplane orthogonal to $a_i$. Then $a_i$ is self-surrounded if and only if $\{\bar{a}_1, \bar{a}'_1\} \oplus \dots \oplus \{\bar{a}_{i-1}, \bar{a}'_{i-1}\} \oplus \{\bar{a}_{i+1}, \bar{a}'_{i+1}\} \oplus \dots \oplus \{\bar{a}_n, \bar{a}'_n\}$ defines a Q-covering of $a_i^{\perp}$.

**Proof.** Let's fix $i$ to $1$. If there exists a neighborhood $U$ of $a_1$ such that $U \subseteq \Sigma(a_1)$, then its projection $\bar{U}$ onto $a_i^{\perp}$ contains 0 in its relative interior and must be included by definition of $\Sigma(a_1)$ in $\{\bar{a}_2, \bar{a}'_2\} \oplus \dots \oplus \{\bar{a}_n, \bar{a}'_n\}$. Any nonzero vector in $a_i^{\perp}$ has a representative (with respect to $\simeq$) in $\bar{U}$ and is therefore covered. Thus $a_i^{\perp} \subseteq \{\bar{a}_2, \bar{a}'_2\} \oplus \dots \oplus \{\bar{a}_n, \bar{a}'_n\}$. For the converse, consider $\Sigma' = \{a_1, -a_1\} \oplus \{a_2, a'_2\} \oplus \dots \oplus \{a_n, a'_n\}$. By Proposition 7, $\mathbb{R}^n \subseteq \Sigma'$ and therefore $a_1$ is surrounded with respect to $\Sigma'$. Moreover, $a_1$ can only be
self-surrounded (with respect to $\Sigma'$) since if it belongs to any c-cone in cones($\Sigma'(-a_1)$) then such a c-cone must be degenerate and therefore it does not effectively contribute in surrounding $a_1$. Thus there exists a neighborhood $U$ of $a_1$ such that $U \subset \Sigma'(a_1)$. By definition of $\Sigma'$, $\Sigma'(a_1) = \Sigma(a_1)$. Thus $U \subset \Sigma(a_1)$ and $a_1$ is self-surrounded with respect to $\Sigma$ as desired. $\square$

**Remark 3.** In light of Proposition 8, Proposition 7 can be reformulated as follows. Suppose that there exists an index $i$ such that $a_i \neq 0$ and that $\langle a_i, a'_i \rangle$ is flat. Then $\mathbb{R}^n$ is covered if and only if $a_i$ is self surrounded.

In general, the Q-covering problem does not enjoy an inductive property, that is, if $\Sigma = \mathbb{R}^n$, it is not necessary that $a_i$ is self surrounded for all $i$. It is worth mentioning that, in [Cottle, 1980], a subclass of Q-matrices, coined completely Q-matrices, was introduced in which the inductive nature is preserved.

Similar to self surrounding, lazy surrounding (cf. Definition 4) can be also seen as a Q-covering problem in dimension $n-1$. The next proposition is stated for $a_1$ for clarity. The statement holds however for any $a_i$ with appropriate changes.

**Proposition 9.** Suppose $a_1$ belongs to the topological interior of a c-cone $C = \langle a'_1, a_2, \dots, a_n \rangle$. Then $\{\tilde{a}'_1, \tilde{a}_2\} \oplus \dots \oplus \{\tilde{a}'_1, \tilde{a}_n\}$ defines a Q-covering of $a_1^\perp$. The converse holds only when $\det(\tilde{a}_1 \tilde{a}_2 \dots \tilde{a}_n) \det(\tilde{a}'_1 \tilde{a}'_2 \dots \tilde{a}'_n) > 0$.<fnref n="7" />

*Proof.* Suppose $a_1$ belongs to the topological interior of a c-cone $C = \langle a'_1, a_2, \dots, a_n \rangle$, then $a_1 \neq 0$ and $0 \in \langle -a_1, a'_1, a_2, \dots, a_n \rangle^\circ$. By Lemma 1, $\langle -a_1, a'_1, a_2, \dots, a_n \rangle = (-a_1, a'_1, a_2, \dots, a_n) = (a'_1, a_2, \dots, a_n) = \mathbb{R}^n$ (because $C$ is non-degenerate) and

$$ \langle -a_1, a'_1, a_2, \dots, a_n \rangle = C \cup \langle -a_1, a_2, \dots, a_n \rangle \cup \bigcup_{i=2}^n \langle -a_1, a'_1, a_2, \dots, a_{i-1}, a_{i+1}, \dots, a_n \rangle = \mathbb{R}^n. $$

Moreover, by Lemma 3, $C = \langle a_1, \dots, a_n \rangle \cup \bigcup_{i=2}^n \langle a'_1, a_1, a_2, \dots, a_{i-1}, a_{i+1}, \dots, a_n \rangle$. Let $\Sigma' = \{a_1, -a_1\} \oplus \{a'_1, a_2\} \oplus \dots \oplus \{a'_1, a_n\}$. Then by definition of $\Sigma'$ one has

$$ \begin{aligned} \Sigma'(a_1) &= \langle a_1, \dots, a_n \rangle \cup \bigcup_{i=2}^n \langle a_1, a'_1, a_2, \dots, a_{i-1}, a_{i+1}, \dots, a_n \rangle = C \\ \Sigma'(-a_1) &= \langle -a_1, a_2, \dots, a_n \rangle \cup \bigcup_{i=2}^n \langle -a_1, a'_1, a_2, \dots, a_{i-1}, a_{i+1}, \dots, a_n \rangle \end{aligned} $$

Therefore, $\Sigma'(a_1) \cup \Sigma'(-a_1) = \mathbb{R}^n$. By Proposition 7, $\{\tilde{a}'_1, \tilde{a}_2\} \oplus \dots \oplus \{\tilde{a}'_1, \tilde{a}_n\}$ defines a Q-covering of $a_1^\perp$. Conversely, if $\{\tilde{a}'_1, \tilde{a}_2\} \oplus \dots \oplus \{\tilde{a}'_1, \tilde{a}_n\}$ defines a Q-covering of $a_1^\perp$ then either $a_1$ or $-a_1$ is in the topological interior of $C$. To ensure the former, $a_1$ and $a'_1$ must not be separated by the hyperplane $(a_2, \dots, a_n)$ which is equivalent to saying that $\det(\tilde{a}_1 \tilde{a}_2 \dots \tilde{a}_n)$ and $\det(\tilde{a}'_1 \tilde{a}_2 \dots \tilde{a}'_n)$ are both nonzero and have the same sign (if $a_1$ and $a'_1$ are separated by the hyperplane $(a_2, \dots, a_n)$ then surely $a_1 \notin \langle a'_1, a_2, \dots, a_n \rangle$). $\square$

Both Propositions 8 and 9 will be used in Section 5 to arrive at an algebraic characterization of Q-matrices in dimension 3.

# 4 Q-covering for $n=3$

A cone in cones($\Gamma$) \ cones($\Sigma$) must be necessarily rooted at both $a_i$ and $a'_i$ for some indices $i$. Following [Garcia et al., 1983], when such an index is unique, the cone is called an almost c-cone. Assuming $\Gamma = \mathbb{R}^n$, it is clear that $\Sigma$ is covering if and only if all minimal cones are covered (necessity is obvious and sufficiency is a corollary of Proposition 3). This section investigates in depth the case $n=3$ with the objective of a complete understanding of when minimal cones are not covered. For this dimension, all cones in cones($\Gamma$) \ cones($\Sigma$) are almost c-cones and have the form $\langle a_i, a'_i, a_j \rangle$, $j \neq i$. Thus for $n=3$, assuming $\Gamma = \mathbb{R}^3$, $\Sigma$ is covering if and only if all (full) almost c-cones are covered. This investigation leads to a complete understating of holes for this dimension (Theorem 1) as well as a characterization of the Q-covering problem for $n=3$ (Theorem 2) which is amenable to an algebraic characterization as we shall see in Section 5. It is worth mentioning that Corollary 1 reduces the Q-covering problem to the surrounding of the vectors in $\Sigma_0$. It strengthens [Garcia et al., 1983, Theorem 4.7] by dropping the strong non-degeneracy assumption (which requires the non-degeneracy of all c-cones and almost c-cones). We start by a useful sufficient condition for minimal cones to be covered.

**Proposition 10.** Let $i, j, k$ denote three distinct indices and let $G = \langle a_i, a'_i, a_j \rangle \subset \mathbb{R}^3$ denote a minimal cone. Assume $\langle a_i, a'_i \rangle$ is covered. If $-a_k \notin G$ then $G \subseteq \Sigma$.

*Proof.* The proof is by case distinction following a partition of $\mathbb{R}^3$ suggested by $G$. Namely, $-G = \langle -a_i, -a'_i, -a_j \rangle$, the interior of 7 full cones $C_i$, the relative interior of 9 facets $F_i$ and 3 rays $R_i$ where $C_1 = G^\circ$, $C_2 = \langle a'_i, -a_i, a_j \rangle^\circ$, $C_3 = \langle -a'_i, a_i, a_j \rangle^\circ$, $C_4 = \langle -a_i, -a'_i, a_j \rangle^\circ$, $C_5 = \langle a_i, a'_i, -a_j \rangle^\circ$, $C_6 = \langle a'_i, -a_i, -a_j \rangle^\circ$, and $C_7 = \langle -a'_i, a_i, -a_j \rangle^\circ$; $F_1 = \langle a_i, a_j \rangle^\circ$, $F_2 = \langle a_i, a'_i \rangle^\circ$, $F_3 = \langle a'_i, a_j \rangle^\circ$, $F_4 = \langle -a_i, a'_i \rangle^\circ$, $F_5 = \langle -a_i, a_j \rangle^\circ$, $F_6 = \langle -a'_i, a_j \rangle^\circ$, $F_7 = \langle a_i, -a'_i \rangle^\circ$, $F_8 = \langle a_i, -a_j \rangle^\circ$, and $F_9 = \langle a'_i, -a_j \rangle^\circ$; $R_1 = \langle a_i \rangle$, $R_2 = \langle a'_i \rangle$, and $R_3 = \langle a_j \rangle$. Cf. Fig. 2. By minimality of $G$, $a_k$ cannot be in $C_1, F_1, F_2, F_3$. If $a_k \in C_5, C_6, C_7, F_4, F_7, F_8, F_9, R_1, R_2$, then $G \subseteq \langle a_i, a'_i, a_j, a_k \rangle \subseteq \Sigma$ where the last inclusion is a consequence of Proposition 6. If $a_k \in C_4, F_5, F_6, R_3$, then $G \subseteq G' = \langle a_i, a'_i, a_k \rangle$. Since $\langle a_i, a'_i \rangle$ is covered, by Proposition 6, a c-face must intersect $\langle a_i, a'_i \rangle$ or $\langle -a_i, a'_i \rangle$ or $\langle a_i, -a'_i \rangle$ (such a c-face must have either $a_j$ or $a_k$ as generator) and either $G \subseteq \Sigma$ or $G' \subseteq \Sigma$.

<footnote n="7">⁷In this case, the hyperplane $(a_2, \dots, a_n)$ is sometimes said to be reflective.</footnote>
<figure><img src="image_5.png" /><figcaption>Figure 2: Decomposition of $\mathbb{R}^3$ in the proof of Proposition 10.</figcaption></figure>

In both cases, $G$ is covered. If $a_k \in C_2$ then $G \subseteq \langle a_i, a_j, a_k \rangle \cup G'$. Since $\langle a_i, a'_i \rangle$ is covered, as discussed above, a c-face having either $a_j$ or $a_k$ as generator satisfies the hypothesis of Proposition 6, and either $G$ is covered or $G'$ is covered. Thus, in all cases $G \subseteq \Sigma$. The same holds when $a_k \in C_3$ by swapping $a_i$ and $a'_i$. $\square$

The following proposition is akin to the case of the so called self intersecting 3 starlike components [Kelly and Watson, 1979, Fig. 1]. We give below a direct (analytic) proof in line with our purposes.

**Proposition 11.** Let $G = \langle a_i, a'_i, a_j \rangle$ denote a full cone in $\mathbb{R}^3$ and suppose that there exists a nonzero vector $q \neq a_j$ in $\langle a_i, a'_i \rangle \cap \langle a'_i, a_j \rangle$. Let $Q = \langle a_i, a_j, q \rangle$. If $-a_k \in Q$ then $Q^\circ \subseteq \Sigma(a_k)^c$.

*Proof.* For clarity we fix $\{i, j, k\}$ to $\{1, 2, 3\}$. It suffices to permute the indices to match any other configuration. We first observe that $Q$ is non-degenerate because $q \neq 0$, $q \in \langle a'_1, a_2 \rangle$ and $q \neq a_2$. By hypothesis, (i) $-a_3 = \lambda_1 a_1 + \lambda_2 a_2 + \lambda q$ with $\lambda_1, \lambda_2, \lambda \ge 0$. Moreover, there exist $\gamma_1, \gamma'_1 \ge 0$ and $\gamma_2, \gamma'_2 > 0$ such that (ii) $q = \gamma'_1 a'_1 + \gamma_2 a_2$ and (iii) $q = \gamma_1 a_1 + \gamma'_2 a'_2$. Using (i) and (ii), one gets $-a_3 = \lambda_1 a_1 + \lambda_2 a_2 + \lambda(\gamma'_1 a'_1 + \gamma_2 a_2)$ or equivalently $(\lambda_2 + \lambda \gamma_2)a_2 + a_3 = \lambda_1(-a_1) + \lambda \gamma'_1(-a'_1)$. Thus $\langle -a_1, -a'_1 \rangle \cap \langle a_2, a_3 \rangle$ is not reduced to zero. By Lemma 7, $Q^\circ \subseteq (\langle a_1, a_2, a_3 \rangle \cup \langle a'_1, a_2, a_3 \rangle)^c$ and $Q^\circ \subseteq \Sigma(a_2, a_3)^c$. Moreover, let $x \in \langle a_1, a_2, q \rangle^\circ$, that is $x = \alpha_1 a_1 + \alpha_2 a_2 + \alpha q$, with $\alpha_1, \alpha_2, \alpha > 0$.

* If $x \in \langle a_1, q, a_3 \rangle$ then $x = \beta_1 a_1 + \beta q + \beta_3 a_3 = \alpha_1 a_1 + \alpha_2 a_2 + \alpha q$ with $\beta_1, \beta, \beta_3 \ge 0$. Thus $(\beta - \alpha)q + \beta_3 a_3 = (\alpha_1 - \beta_1)a_1 + \alpha_2 a_2$. If $\beta_3 = 0$ then $\alpha_2 = 0$ because $a_1, a_2, q$ are independent, contradicting $\alpha_2 > 0$. Thus $\beta_3 > 0$ and (iv) $-\beta_3 a_3 = -(\alpha_1 - \beta_1)a_1 - \alpha_2 a_2 + (\beta - \alpha)q = \beta_3 \lambda_1 a_1 + \beta_3 \lambda_2 a_2 + \beta_3 \lambda q$. Using (i) and (iv) one gets $-\alpha_2 = \beta_3 \lambda_2$, a contradiction.

* If $x \in \langle a'_2, q, a_3 \rangle$ then $x = \beta'_2 a'_2 + \beta q + \beta_3 a_3 = \alpha_1 a_1 + \alpha_2 a_2 + \alpha q$ with $\beta'_2, \beta, \beta_3 \ge 0$. Thus $(\beta - \alpha)q + \beta_3 a_3 = \alpha_1 a_1 + \alpha_2 a_2 - \beta'_2 a'_2$. If $\beta_3 = 0$. Then $\beta - \alpha$ cannot be zero since $a_1, a'_2, a_2$ are independent ($q \neq a_2$). Moreover, if $\beta - \alpha \neq 0$, $q \in \langle a_1, a'_2 \rangle$ forces $\alpha_2$ to be zero contradicting $\alpha_2 > 0$. So $\beta_3 > 0$ and (v) $-\beta_3 a_3 = -\alpha_1 a_1 - \alpha_2 a_2 + \beta'_2 a'_2 + (\beta - \alpha)q = \beta_3 \lambda_1 a_1 + \beta_3 \lambda_2 a_2 + \beta_3 \lambda q$. Using (iii), one substitutes $a'_2$ for a linear combination of $a_2$ and $q$. Thus (i) and (v) lead to $-\alpha_1 = \beta_3 \lambda_1$, a contradiction.

Since $q \in \langle a'_1, a_2 \rangle$, $\langle a_1, a'_2, a_3 \rangle = \langle a_1, q, a_3 \rangle \cup \langle a'_2, q, a_3 \rangle$. Therefore $x \notin \langle a'_1, a'_2, a_3 \rangle$. Finally, if $x \in \langle a'_1, a'_2, a_3 \rangle$ then $x = \beta'_1 a'_1 + \beta'_2 a'_2 + \beta_3 a_3 = \alpha_1 a_1 + \alpha_2 a_2 + \alpha q$ with $\beta'_1, \beta'_2, \beta_3 \ge 0$. Using $q = \gamma_1 a_1 + \gamma'_2 a'_2 = \gamma'_1 a'_1 + \gamma_2 a_2$, if $\gamma'_1 = 0$ then $q \simeq a_2$, contradicting the hypothesis on $q$. Thus $\gamma'_1 > 0$. If $\gamma'_2 = 0$ then $G$ would be degenerate, also a contradiction. Thus $\gamma'_2 > 0$. One then gets (v) $\alpha_1 a_1 + \alpha_2 a_2 + \alpha q = \frac{\beta'_1}{\gamma'_1}(q - \gamma_2 a_2) + \frac{\beta'_2}{\gamma'_2}(q - \gamma_1 a_1) + \beta_3 a_3$. If $\beta_3 = 0$ then $\alpha_1 + \frac{\beta'_1}{\gamma'_2}\gamma_1 = 0$ contradicting $\alpha_1 > 0$. Thus $\beta_3 > 0$ and using (i) and (v) one gets $-(\alpha_1 + \frac{\beta'_1}{\gamma'_2}\gamma_1) = \beta_3 \lambda_1$ which is impossible. Thus $x \notin \langle a'_1, a'_2, a_3 \rangle$ and $Q^\circ \subseteq \Sigma(a'_2, a_3)^c$. Therefore $Q^\circ \subseteq \Sigma(a_2, a_3)^c \cap \Sigma(a'_2, a_3)^c = \Sigma(a_3)^c$. $\square$

**Proposition 5** showed that the cone $\langle a_i, a'_i \rangle$ enjoys a special property: it cannot be partially covered. When it is covered, Theorem 1 below gives a necessary condition for a minimal cone $\langle a_i, a'_i, a_j \rangle$ to contain a hole. Its proof requires the following technical lemma.

**Lemma 9.** Let $i, j, k$ denote distinct indices in $\{1, 2, 3\}$, $G = \langle a_i, a'_i, a_j \rangle$ denote a full cone in $\mathbb{R}^3$ such that $-a_k \in G$. Suppose there exist vectors $p, q \neq 0$ such that $p \in \langle -a_i, a'_i \rangle^\circ \cap \langle a'_j, a_k \rangle^\circ$ and $q \in \langle a_i, a'_j \rangle^\circ \cap \langle a'_i, a_j \rangle^\circ$. Then $-a_k \in \langle a_i, a_j, q \rangle$.

*Proof.* For clarity we fix $\{i, j, k\}$ to $\{1, 2, 3\}$. It suffices to permute the indices to match any other configuration. Since $p \in \langle -a_1, a'_1 \rangle^\circ \cap \langle a'_2, a_3 \rangle^\circ$, there exist $\lambda_1, \lambda'_1 > 0$ and $\lambda'_2, \lambda_3 > 0$ such that (i) $p = \lambda_1(-a_1) + \lambda'_1 a'_1 = \lambda'_2 a'_2 + \lambda_3 a_3$. Moreover since $q \in \langle a_1, a'_2 \rangle^\circ \cap \langle a'_1, a_2 \rangle^\circ$, there exist $\gamma'_1, \gamma_2, \gamma_1, \gamma'_2 > 0$, such that (ii) $q = \gamma'_1 a'_1 + \gamma_2 a_2 = \gamma_1 a_1 + \gamma'_2 a'_2$. We can eliminate $a'_2$ from (i) and (ii) to get

$$-\gamma'_2 \lambda_3 a_3 = \underbrace{(-\gamma'_2 \gamma_1 + \gamma'_2 \lambda_1)}_{\theta_1} a_1 + \underbrace{(-\gamma'_2 \lambda'_1 + \lambda'_2 \gamma'_1)}_{\theta'_1} a'_1 + \lambda'_2 \gamma_2 a_2$$

with $\theta_1, \theta'_1 \ge 0$ (because $-a_3 \in G$). Thus $\frac{\gamma'_1}{\lambda'_1} \ge \frac{\gamma'_2}{\lambda'_2} \ge \frac{\gamma_1}{\lambda_1}$ and $\rho_1 = \gamma'_1 \lambda_1 - \lambda'_1 \gamma_1 \ge 0$. We further eliminate $a'_1$ from (i) and (ii) to get

$$\rho_1 a_1 + \lambda'_1 \gamma_2 a_2 + \theta'_1 a'_2 = -\gamma'_1 \lambda_3 a_3$$

Thus $-a_3 \in G \cap \langle a_1, a_2, a'_2 \rangle = \langle a_1, a_2, q \rangle$. $\square$
**Theorem 1.** Let $G = \langle a_i, a'_i, a_j \rangle$, $j \neq i$, denote a minimal cone such that $\langle a_i, a'_i \rangle \subseteq \Sigma$. If $G$ contains a hole $K$ then, up to swapping $a_i, a'_i$, there exists a nonzero vector $q \in \langle a_i, a'_j \rangle \cap \langle a'_i, a_j \rangle$ such that $K = \langle a_i, q, a_j \rangle^{\circ}$.

*Proof.* If $-a_k$ or $-a'_k$ is not in $G$ then, by Proposition 10, $G \subseteq \Sigma$. By hypothesis $G$ contains a hole so we can assume that $-a_k, -a'_k \in G$. Since $\langle a_i, a'_i \rangle$ is covered, by Proposition 6, one c-face must intersect $\langle a_i, a'_i \rangle$ or $\langle -a_i, a'_i \rangle^{\circ}$ or $\langle a_i, -a'_i \rangle^{\circ}$. In this case, such a c-face must have $a'_j$ as a generator (as both $\langle a_j, a_k \rangle$ and $\langle a_j, a'_k \rangle$ intersect $\langle -a_i, -a'_i \rangle$). With respect to the partition of the space used in the proof of Proposition 10 (cf. Fig 2), and since $G$ is a minimal cone, for $\langle a_i, a'_i \rangle$ to be covered, $a'_j$ must belong to one of the following $C_2, C_3, F_4, F_7, R_1, R_2$. In all cases there exists a nonzero vector $q \neq 0$ in $\langle a_i, a'_j \rangle \cap \langle a'_i, a_j \rangle$ (when $a'_j$ is in $C_2, F_4, R_2$) or in $\langle a_i, a_j \rangle \cap \langle a'_i, a'_j \rangle$ (when $a'_j$ is in $C_3, F_7, R_1$). (Observe that both cases are symmetric by swapping $a_i$ and $a'_i$.) Suppose the former, and let $Q = \langle a_i, a_j, q \rangle$. If $a'_j \in R_2$ or $a'_j \in F_4$ then $q \simeq a'_i$ and $Q = G$. By Proposition 11, $G^{\circ} = Q^{\circ} \subseteq \Sigma(a_k)^c \cap \Sigma(a'_k)^c = \Sigma^c$. Suppose $a'_j \in \tilde{C}_2$, then there exists $p \in \langle -a_i, a'_i \rangle^{\circ} \cap \langle a'_j, a_k \rangle^{\circ}$. By Lemma 9, $-a_k \in Q$ and by Proposition 11, $Q^{\circ} \subseteq \Sigma(a_k)^c$. If $\langle a'_j, a'_k \rangle$ does not intersect $\langle -a_i, a'_i \rangle^{\circ}$ then it intersects $\langle -a_i, -a'_i \rangle$ and therefore $G^{\circ} \subseteq \Sigma(a'_k)^c$ by Lemma 7. Thus $Q^{\circ} \subseteq \Sigma^c$. Otherwise $\langle a'_j, a'_k \rangle$ intersect $\langle -a_i, a'_i \rangle^{\circ}$ and $-a'_k \in Q$ and by Proposition 11, $Q^{\circ} \subseteq \Sigma(a'_k)^c$, $Q^{\circ} \subseteq \Sigma^c$. As $Q^{\circ}$ is the maximal hole contained in $G$, it follows that $K = Q^{\circ}$ as stated. $\square$

**Corollary 1.** $\Sigma = \mathbb{R}^3$ if and only if, for all $i$, both $a_i$ and $a'_i$ are surrounded.<fnref n="8" />

*Proof.* Necessity is immediate. For sufficiency, we prove the contrapositive, that is if $\Sigma^c$ is non-empty then there exists an index $i$ for which either $a_i$ or $a'_i$ is not surrounded. Assume first that $\Gamma \subset \mathbb{R}^3$. Then $\Gamma$ is a closed proper convex cone of $\mathbb{R}^3$ with a boundary that is non-empty. If for all $a \in \Sigma_0$, $a \in \Gamma^{\circ}$ then $\Gamma \subseteq \Gamma^{\circ} \subseteq \Gamma$. So $\Gamma$ is both open and closed and its boundary must be empty, a contradiction.<fnref n="9" /> Thus, there exists a vector $a \in \Sigma_0$ such that $a$ is a boundary ray of $\Gamma$ and therefore $a$ cannot be surrounded (if $U$ is a neighborhood of $a$, then $U \not\subseteq \Gamma$ and since $\Sigma \subseteq \Gamma$, $U \not\subseteq \Sigma$). Next, assume that $\Gamma = \mathbb{R}^3$. Since $\Sigma \subset \mathbb{R}^3$, by Proposition 3, there must exist a minimal cone $G = \langle a_i, a'_i, a_j \rangle$, $j \neq i$, such that $K = G \cap \Sigma^c$ is non-empty. By Proposition 5, either $\langle a_i, a'_i \rangle^{\circ} \subseteq \Sigma^c$ or $\langle a_i, a'_i \rangle^{\circ} \subseteq \Sigma$. If the former holds then both $a_i$ and $a'_i$ are not surrounded. If the latter holds, then by Theorem 1, either $a_i$ is not surrounded or $a'_i$ is not surrounded. $\square$

Corollary 1 strengthens [Garcia et al., 1983, Theorem 4.7] by dropping the strong non-degenerate assumption. The latter result was moreover established using degree theory while in this work we solely used convex geometry. The statement of Corollary 1 does not hold for $n > 3$. In [Morris Jr, 1988, Theorem 3], the author gives an example in $n = 4$ where both $a_i$ and $a'_i$ are (lazily) surrounded for all $i$ without having a Q-covering. The (counter)example in $n = 4$ thus shows that it is possible for a minimal cone to have surrounded generators while still having a hole in it.

Another (more practical) issue with the statement of Corollary 1 is that, in general, surrounding is not straightforward to transpose algebraically. Under the assumption $\Gamma = \mathbb{R}^3$, in the sequel we alleviate the need for checking surrounding: we show that self surrounding and lazy covering are enough to characterize the Q-covering for $n = 3$. We start by proving some special cases before stating the main theorem (cf. Theorem 2 below).

**Lemma 10.** Suppose that $a_i \in \langle a'_i, a_j \rangle$, $i \neq j$. If $a'_i$ is self surrounded or lazily covered then all minimal cones rooted at $a_i, a'_i$ are covered.

*Proof.* For clarity we fix $(i, j)$ to $(1, 2)$. (It suffices to permute the indices accordingly for any other configuration.) Since $a_1 \in \langle a'_1, a_2 \rangle$, then $\langle a_1, a'_1, a_2 \rangle \subseteq \langle a'_1, a_2 \rangle \subseteq \Sigma$, $\langle a_1, a'_1, a_3 \rangle \subseteq \langle a'_1, a_2, a_3 \rangle \subseteq \Sigma$, and $\langle a_1, a'_1, a'_3 \rangle \subseteq \langle a'_1, a_2, a'_3 \rangle \subseteq \Sigma$. Only $G = \langle a_1, a'_1, a'_2 \rangle$ is left out. Assume $a'_1$ is self surrounded. Thus $\langle a_1, a'_1 \rangle$ is covered by Proposition 5. Suppose $-a_3, -a'_3 \in G$, then by Proposition 11, $G^{\circ} \subseteq \Sigma(a_3)^c \cap \Sigma(a'_3)^c = \Sigma^c$, contradicting the self surrounding of $a'_1$. Thus either $-a_3 \notin G$ or $-a'_3 \notin G$ and by Proposition 10, $G$ is covered as desired. Assume $a'_1 \in \Sigma(a_1)$. If $a'_1 \in \langle a_1, a'_2, a_3 \rangle$, then $G \subseteq \langle a_1, a'_2, a_3 \rangle \subseteq \Sigma$. The same occurs if $a'_1 \in \langle a_1, a'_2, a'_3 \rangle$ by swapping $a_3$ and $a'_3$. If $a'_1 \in \langle a_1, a_2, a_3 \rangle$ then either $a_3 \simeq a'_1$ or $a_3 \in \langle -a_1, a'_1 \rangle^{\circ}$. The former makes $G$ a c-cone. If the latter occurs, then by Lemma 6, $G$ is covered. The same discussion holds if $a'_1 \in \langle a_1, a_2, a'_3 \rangle$ by swapping $a_3$ and $a'_3$. We thus proved that all minimal cones rooted at $a_1, a'_1$ are covered. $\square$

**Lemma 11.** Suppose $a_i \in \langle a_j, a_k \rangle^{\circ}$ with $i, j, k$ distinct. Then all minimal cones rooted at $a_i, a'_i$ are covered.

*Proof.* For clarity we fix $i, j, k$ to 1, 2, 3 respectively. (It suffices to permute the indices accordingly for any other configuration.) Since $a_1 \in \langle a_2, a_3 \rangle$ then $\langle a_1, a'_1, a_3 \rangle \subseteq \langle a'_1, a_2, a_3 \rangle \subseteq \Sigma$ and $\langle a_1, a'_1, a_2 \rangle \subseteq \langle a'_1, a_2, a_3 \rangle \subseteq \Sigma$. It remains to prove that $\langle a_1, a'_1, a'_2 \rangle$ and $\langle a_1, a'_1, a'_3 \rangle$ are covered. We first prove that $G = \langle a_1, a'_1, a'_2 \rangle$ is covered. If $a_2 \simeq a'_2$, then $G$ is also covered as discussed above. If $a_2 \simeq a'_1$ then $G \subseteq \langle a'_1, a'_2, a_3 \rangle \subseteq \Sigma$. In addition $a_2 \not\simeq a_1$ (because $a_1 \in \langle a_2, a_3 \rangle^{\circ}$). Using the minimality of $G$, we can thus assume in the sequel that $a_2 \notin G$. Suppose that $-a_3 \in G$, then there exists $\lambda_1, \lambda'_1, \lambda'_2 \ge 0$ such that $-a_3 = \lambda_1 a_1 + \lambda'_1 a'_1 + \lambda'_2 a'_2$.

<footnote n="8">⁸In [Kelly and Watson, 1979], the authors relied heavily on visualization to characterize 3 × 3 non-degenerate Q-matrices. Interested readers can find a proof in the same spirit in [Kozaily, 2024, Proposition 4].</footnote>

<footnote n="9">⁹Another way to arrive at a contradiction would be to use the fact that $\mathbb{R}^n$ is a connected topological space, thus the only clopen subsets are $\mathbb{R}^n$ and its complement, excluding $\Gamma$.</footnote>
Moreover there exists $\gamma_2, \gamma_3 > 0$ such that $a_1 = \gamma_2 a_2 + \gamma_3 a_3$. By eliminating $a_3$ from both equations, one gets

$$ \gamma_2 a_2 = (\gamma_3 \lambda_1 + 1) a_1 + \gamma_3 \lambda'_1 a'_1 + \gamma_3 \lambda'_2 a'_2 $$

and therefore $a_2 \in G$, a contradiction. Thus $-a_3 \notin G$. By hypothesis $\langle a_1, a'_1 \rangle \subseteq \langle a'_1, a_2, a_3 \rangle \subseteq \Sigma$. Thus Proposition 10 applies and $G \subseteq \Sigma$. The exact same discussion holds to prove that $\langle a_1, a'_1, a'_3 \rangle$ is covered by swapping the indices 2 and 3. $\square$

**Theorem 2.** Assume $\Gamma = \mathbb{R}^3$. Then $\Sigma = \mathbb{R}^3$ if and only if, all vectors in $\Sigma_0$ are either self surrounded or lazily covered. (Observe that necessity holds for any finite dimension.)

*Proof.* (Necessity) If $\Sigma = \mathbb{R}^3$, then $a_i$ must be surrounded for all $i$. If $a_i$ is not self surrounded then necessarily $a_i \in \Sigma(a'_i)$ (otherwise $a_i$ cannot be surrounded). The same holds for $a'_i$. (Sufficiency) We prove the contrapositive, i.e. if $\Sigma \subset \mathbb{R}^3$ then there exists a vector in $\Sigma_0$ which is not self surrounded nor lazily covered. The proof is by contradiction. Suppose that $\Sigma \subset \mathbb{R}^3$ and all vectors in $\Sigma_0$ are either self surrounded or lazily covered. Thus, there exists a hole $K$. Since $\Gamma = \mathbb{R}^3$, then by Proposition 3 there exists a minimal cone $G = \langle a_i, a'_i, a_j \rangle$, $j \neq i$, such that $K = G \cap \Sigma^c$ is non-empty. By Proposition 5, either $\langle a_i, a'_i \rangle^\circ \subset \Sigma^c$ or $\langle a_i, a'_i \rangle \subset \Sigma$. If the former holds, then $a_i$ (or $a'_i$) leads to a contradiction as it is not self surrounded nor lazily covered (cf. the proof of Proposition 5). If the latter holds, by Theorem 1, $a_i$, say, is not surrounded (otherwise it suffices to swap $a_i$ and $a'_i$ in what follows). In particular $a_i$ is not self nor lazily surrounded. Therefore $a_i \in \Sigma_2(a'_i)$ (i.e. a face of a c-cone rooted at $a'_i$). If $a_i \in \langle a'_i, a_j \rangle$, $j \neq i$, then by Lemma 10, $G$ is covered. If $a_i \in \langle a_j, a_k \rangle^\circ$, with $i, j, k$ distinct, then by Lemma 11, $G$ is also covered. Both cases lead to a contradiction since $K$ is non-empty. Thus $K$ does not exist and $\Sigma = \mathbb{R}^3$. $\square$

Unlike Corollary 1, Theorem 2 is amenable to an algebraic characterization of Q-matrices for $n = 3$ as we shall detail in the next section.

# 5 Algebraic Characterization

Theorem 2 characterizes the Q-covering via three requirements: (1) Feasibility or S-matricity (i.e. $\Gamma = \mathbb{R}^3$), (2) self surrounding (i.e. the Q-covering of $a'_i$), and (3) lazy covering (i.e. $a_i \in \Sigma(a'_i)$). We detail next how each requirement can be equivalently translated into sign conditions on the subdeterminants of the matrix $(a_1 a_2 a_3 a'_1 a'_2 a'_3)$.

## 5.1 S-matricity

Proposition 1 provides an effective mean to characterize S-matrices for $n = 3$.

**Corollary 2.** Let $\Gamma = \langle g_1, \dots, g_6 \rangle$. Then $\Gamma = \mathbb{R}^3$ if and only if

* either there are 4 vectors such that $\mathbb{R}^3 = \langle g_{i_1}, \dots, g_{i_4} \rangle$,

* or there are 3 vectors such that $\langle g_{i_1}, g_{i_2}, g_{i_3} \rangle$ is a plane that separates two other vectors $g_{i_4}$ and $g_{i_5}$,

* or there are 2 vectors such that $\langle g_{i_1}, g_{i_2} \rangle$ is a line and the plane $g_{i_1}^\perp$ is equal to $\langle \pi(g_{i_3}), \dots, \pi(g_{i_6}) \rangle$, where $\pi$ denotes the orthogonal projection onto the hyperplane $g_{i_1}^\perp$.

*Proof.* Sufficiency is immediate. For necessity, by Proposition 1, there exists $1 \le m \le 3$ such that $m+1$ vectors among $g_1, \dots, g_6$ span a flat of dimension $m$. The provided conditions enumerate all cases ($m = 3$ first, then $m = 2$, and finally $m = 1$). $\square$

When the four cones $\langle g_1, g_2, g_3 \rangle$, $\langle g_2, g_3, g_4 \rangle$, $\langle g_1, g_3, g_4 \rangle$, and $\langle g_1, g_2, g_4 \rangle$ are full and have the same orientation, then $\Gamma = \langle g_1, g_2, g_3, g_4 \rangle = \mathbb{R}^3$. The orientation can be retrieved using the sign of the determinant of the matrix formed by the generators. For instance, the orientation of the cone $\langle g_1, g_2, g_3 \rangle$ is given by the sign of $\det(g_1 g_2 g_3)$. However, while the cone, as a geometric object, is invariant under any permutation of its generators, the sign of the determinant is not. One thus has to be careful when ordering the vectors to get a coherent orientation of the involved cones [Jeanneret and Lines, 2014, Section 18]. We do this by fixing a global order of the involved vectors and making sure that the orientation of the common facet of any two adjacent cones is inverted w.r.t. the fixed global order. For instance the cones spanned by the lists $\{g_1, g_2, g_3\}$ and $\{g_2, g_3, g_4\}$ are adjacent cones having in common $\{g_2, g_3\}$. With respect to the global ordering $g_1, g_2, g_3, g_4$, the lists $\{g_1, g_2, g_3\}$ and $\{g_3, g_2, g_4\}$ are coherently oriented.

Similarly, when $\mathbb{R}^3$ is nonnegatively spanned by five vectors, assuming any 4 of them do not span the space, then three of them span a plane that separates the two remaining ones. This implies that the space is partitioned into six distinct cones that have the same orientation (i.e. all pairs of adjacent cones are coherently oriented). For a list of 5 vectors, we misuse the $\oplus$ notation (cf. Def. 2) and write $\Gamma$ as $\{g_1, g_2, g_3\} \oplus \{g_4, g_5\}$, where the first three vectors span the plane separating the two remaining ones. Finally, when the six vectors are required to span $\mathbb{R}^3$, they must form 3 lines in a generic position (no one is in the plane formed by the two others). This implies that the space is partitioned into eight distinct cones that have the same orientation. In this case, we write $\Gamma$ as $\{g_1, g_2\} \oplus \{g_3, g_4\} \oplus \{g_5, g_6\}$ where each pair form a
**Algorithm 1:** $\Gamma_4$: $\mathbb{R}^3 = \langle g_1, g_2, g_3, g_4 \rangle$.

**Data:** Four symbolic vectors $g_1, \dots, g_4$.

$$1 \{d_1, d_2, d_3, d_4\} \leftarrow \{\det(g_1 g_2 g_3), \det(g_2 g_1 g_4), \det(g_3 g_4 g_1), \det(g_4 g_3 g_2)\}$$

$$2 \text{ return } (\bigwedge_{i=1}^{4} d_i > 0) \lor (\bigwedge_{i=1}^{4} d_i < 0)$$

**Algorithm 2:** $\Gamma_5$: $\mathbb{R}^3 = \langle g_1, \dots, g_5 \rangle = \{g_1, g_2, g_3\} \oplus \{g_4, g_5\}$.

**Data:** Five symbolic vectors $g_1, \dots, g_5$.

$$1 \{d_1, d_2, d_3\} \leftarrow \{\det(g_1 g_2 g_4), \det(g_2 g_3 g_4), \det(g_3 g_1 g_4)\}$$

$$2 \{d_4, d_5, d_6\} \leftarrow \{\det(g_1 g_3 g_5), \det(g_3 g_2 g_5), \det(g_2 g_1 g_5)\}$$

$$3 \text{ return } (\bigwedge_{i=1}^{6} d_i > 0) \lor (\bigwedge_{i=1}^{6} d_i < 0)$$

line. The notation here is suggestive of the Q-covering problem. In fact it is a very special case where one gets a partition of the space. Equivalently, $(g_1 g_3 g_5)^{-1}(g_2 g_4 g_6)$ is a P-matrix.

We say that a vector is *symbolic* if all its components are non-fixed reals or variables or *symbols*. For instance the vector $(m_1, m_2, m_3)$ is symbolic whereas $(1, 0, 0)$ is not. Algorithm 1 makes explicit the conditions that the components of 4 vectors have to satisfy to span $\mathbb{R}^3$. Algorithm 2 makes explicit the conditions that a list of 5 vectors have to satisfy to span $\mathbb{R}^3$ assuming the first three vectors span a plane and the remaining two vectors are separated by that plane. To avoid checking whether the first three vectors actually form a plane, the algorithm relies on partitioning the space into 6 coherently oriented cones. The so obtained conditions may thus have some redundancy with the ones obtained from Algorithm 1. Finally, Algorithm 3 makes explicit the conditions that a list of 6 vectors have to satisfy to span $\mathbb{R}^3$ (where all the vectors are required). As discussed earlier, we also implement the partition of the space into 8 cones for simplicity at the cost of redundancy with the conditions provided by the two other algorithms.

Given 6 symbolic vectors $g_1, \dots, g_6$, one can characterize $\Gamma = \langle g_1, \dots, g_6 \rangle = \mathbb{R}^3$ as follows: apply Algorithm 1 to any sublist of four vectors among the ones provided, apply Algorithm 2 to all distinct pairs of sublists of 3 and 2 vectors, and finally apply Algorithm 3 to all distinct tuples formed each by three pairs of vectors.

## 5.2 Self Surrounding

By Proposition 8, self surrounding for $n = 3$ amounts to characterizing the Q-covering for $n = 2$. The following theorem is the analogue of Corollary 1 for dimension 2. It relies solely on surrounding which is easy to characterize for this dimension, alleviating the need for feasibility.

**Theorem 3.** $\Sigma = \mathbb{R}^2$ if and only if, for all $i$, $a_i$ and $a'_i$ are surrounded.

*Proof.* Necessity is immediate. For sufficiency, we prove the contrapositive. Suppose $\Sigma \subset \mathbb{R}^2$. If $\Gamma \subset \mathbb{R}^2$ then by [Rockafellar, 1997, Corollary 18.3.1], there exists a vector in $\Sigma_0$ which is a face of $\Gamma$. Since $\Sigma \subseteq \Gamma$, such a vector cannot be surrounded. Next, suppose that $\Gamma = \mathbb{R}^2$. By proposition 3, there must exist a minimal cone $G = \langle a_i, a'_i \rangle$ such that $G \cap \Sigma^c$ is non-empty and, by proposition 5, $G^\circ \subseteq \Sigma^c$ proving that both $a_i$ and $a'_i$ are not surrounded. $\square$

**Proposition 12.** Suppose $n = 2$ and let $i, j$ denote two distinct indices. Let $\bar{v}$ denote the orthogonal projection of $v \in \mathbb{R}^2$ onto $a_i^\perp$. Then $a_i$ is surrounded if and only if it is either self or lazily surrounded or $a_i \simeq a_j$ and the pair $\{\bar{a}'_i, \bar{a}'_j\}$ form a 1-dimensional Q-covering or $a_i \simeq a'_j$, and the pair $\{\bar{a}'_i, \bar{a}_j\}$ form a 1-dimensional Q-covering.

*Proof.* Sufficiency is immediate using Proposition 8. For necessity, assume that $a_i$ is not self nor lazily surrounded. Thus $a_i \in \Sigma_1(a'_i)$. If $a_i \simeq a'_i$, then $\Sigma$ reduces to $\langle a_i, a_j \rangle \cup \langle a_i, a'_j \rangle$ and $a_i$ is surrounded if and only if it is self surrounded, contradicting the assumption. So $a_i \not\simeq a'_i$. If $a_i \simeq a_j$ and $a_j \simeq a'_j$ then the surrounding is impossible as $\Sigma$ reduces to one cone having $a_i$ as generator. If $a_j \not\simeq a'_j$, then $a_i$ must be surrounded by $\langle a_i, a'_j \rangle \cup \langle a'_i, a_j \rangle$ which is effectively equivalent to checking that $\{\bar{a}'_i, \bar{a}'_j\}$ form a 1-dimensional Q-covering by Proposition 8. The same discussion holds when $a_i \simeq a'_j$ and one needs to check that $\{\bar{a}'_i, \bar{a}_j\}$ form a 1-dimensional Q-covering. $\square$

Proposition 12 is amenable to an algebraic characterization of the Q-covering problem in $n = 2$. For lazy surrounding, checking if $a_i \in \langle a'_i, a_j \rangle^\circ$, $j \neq i$, amounts to simply checking that the determinants of the three matrices $(a'_i \ a_j)$, $(a'_i \ a_i)$, and $(a_i \ a_j)$ have the same sign. Likewise, checking if $a_i$ is self surrounded amounts to verifying that the determinants of $(a_i \ a_j)$ and $(a_i \ a'_j)$, $j \neq i$, have opposite signs. We observe that this condition should not be confused with $a_i \in \langle a_j, a'_j \rangle^\circ$, which is only a special case ($a_i$ needs not be in the interior of $\langle a_j, a'_j \rangle$ to be self surrounded). As stated in Proposition 8, self surrounding can be equivalently checked by projecting on the orthogonal space of $a_i$ and appealing to the following simple fact.
**Algorithm 3:** $\Gamma_6$: $\mathbb{R}^3 = \langle g_1, \dots, g_6 \rangle = \{g_1, g_2\} \oplus \{g_3, g_4\} \oplus \{g_5, g_6\}$.

**Data:** Six symbolic vectors $g_1, \dots, g_6$.

1. $\{d_1, d_2, d_3, d_4\} \leftarrow \{\det(g_1 g_3 g_5), \det(g_3 g_2 g_5), \det(g_2 g_4 g_5), \det(g_4 g_1 g_5)\}$

2. $\{d_5, d_6, d_7, d_8\} \leftarrow \{\det(g_1 g_4 g_6), \det(g_4 g_2 g_6), \det(g_2 g_3 g_6), \det(g_3 g_1 g_6)\}$

3. return $(\bigwedge_{i=1}^8 d_i > 0) \lor (\bigwedge_{i=1}^8 d_i < 0)$

**Algorithm 4:** Surrounding of $a_i$ ($n = 2$).

**Data:** Two pairs $\{a_1, a'_1\}, \{a_2, a'_2\}$ of vectors in $\mathbb{R}^2$.

1. $\{u_1, u_2\} \leftarrow a_i$

2. $u^{\perp} \leftarrow \{-u_2, u_1\}$

▷ Orthogonal vector if $a_i \neq 0$

3. $c_1 \leftarrow (u^{\perp} \cdot a_j)(u^{\perp} \cdot a'_j) < 0$

▷ Self surrounding

4. $c_2 \leftarrow \det(a'_i a_i) \det(a_i a_j) > 0 \lor \det(a'_i a_i) \det(a_i a'_j) > 0$

▷ Lazy surrounding

5. $c_3 \leftarrow \det(a_i a_j) = 0 \land a_i \cdot a_j > 0 \land (u^{\perp} \cdot a'_i)(u^{\perp} \cdot a'_j) < 0$

▷ $a_i \simeq a_j$

6. $c'_3 \leftarrow \det(a_i a'_j) = 0 \land a_i \cdot a'_j > 0 \land (u^{\perp} \cdot a'_i)(u^{\perp} \cdot a'_j) < 0$

▷ $a_i \simeq a'_j$

7. return $c_1 \lor c_2 \lor c_3 \lor c'_3$

**Theorem 4.** Let $a, a' \in \mathbb{R}$. The pair $\{a, a'\}$ defines a Q-covering of $\mathbb{R}$ if and only if $aa' < 0$, providing thereby a partition for $\mathbb{R}$.

*Proof.* The cones generated by $a$ and $a'$ cover, or more precisely partition, $\mathbb{R}$ if and only if $a, a'$ are both nonzero and have opposite signs. $\square$

**Remark 4.** Observe that, for $n = 1$, $\Gamma$ and $\Sigma$ coincide and that $a$ is surrounded if and only if $a \neq 0$. Interestingly, Corollary 1 does not hold for $n = 1$ since $a$ and $a'$ can be both (lazily) surrounded (for instance when $a' \simeq a$) and $\Sigma = \Gamma \subset \mathbb{R}$. Intuitively, when $a'_i$ is lazily surrounded, it is somehow 'redundant' with $a_i$ (with $a'_i \simeq a_i$ being the simplest-and perhaps strongest-form of redundancy). So when $a'_i$ is redundant for all $i$, $\Sigma$ is unlikely to be covering.

Algorithm 4 outputs the set of conditions required for $a_i$ to be surrounded according to Proposition 12. When $a_i$ is identically zero, all conditions fail as desired ($a_i = 0$ cannot be surrounded). Applying the algorithm to the four involved vectors outputs an algebraic characterization for $\Sigma$ to be covering for $n = 2$; we will denote it in the sequel by QCovering$\{\{a_1, a'_1\}, \{a_2, a'_2\}\}$. In particular, one gets the following characterization for Q-matrices in dimension 2.

**Theorem 5.** The matrix $(\begin{smallmatrix} m_1 & m_2 \\ m_3 & m_4 \end{smallmatrix})$ is a Q-matrix if and only if

$$ \begin{align} & (m_1 < 0 \land m_2 > 0 \land m_3 > 0 \land m_4 < 0 \land m_1 m_4 - m_2 m_3 < 0) \notag \\ \lor & (m_1 < 0 \land m_2 > 0 \land m_3 < 0 \land m_4 > 0 \land m_1 m_4 - m_2 m_3 > 0) \notag \\ \lor & (m_1 = 0 \land m_2 > 0 \land m_3 < 0 \land m_4 > 0) \notag \\ \lor & (m_1 > 0 \land m_3 = 0 \land m_4 > 0) \tag{3} \\ \lor & (m_1 > 0 \land m_2 \ge 0 \land m_4 > 0) \notag \\ \lor & (m_1 > 0 \land m_2 < 0 \land m_3 > 0 \land m_1 m_4 - m_2 m_3 > 0) \notag \\ \lor & (m_1 > 0 \land m_2 < 0 \land m_3 < 0 \land m_1 m_4 - m_2 m_3 > 0) . \notag \end{align} $$

For the sake of comparison, we give below the relatively much simpler conditions for $M$ to be a P-matrix requiring that all the principal minors of $M$ to be positive:

$$ m_1 > 0 \land m_4 > 0 \land m_1 m_4 - m_2 m_3 > 0 . $$

One observes that P-matrices are a special case of Q-matrices since $m_1 > 0 \land m_4 > 0 \land m_1 m_4 - m_2 m_3 > 0$ implies (without being equivalent to) the last four conjunctions of (3).

**Remark 5.** The fact that Theorem 5 involves only sign conditions on the subdeterminants of the matrix $M$ is not a coincidence. In fact, Algorithm 4 can be equivalently stated in terms of sign conditions of the subdeterminants of the matrix $(a_1 a_2 a'_1 a'_2)$. Indeed, on one hand, the scalar product $u^{\perp} \cdot a_j$ in Line 3 is equal to $\det(a_i a_j)$. The same holds for the other scalar products involving $u^{\perp}$. On the other hand, for $v, w \in \mathbb{R}^2$, the equivalence $v \simeq w$ characterized by $\det(v w) = 0 \land v \cdot w > 0$ in Algorithm 4, can be reformulated as

$$ (\det(v w) = 0) \land (v_1 w_1 > 0 \lor v_2 w_2 > 0), \quad (4) $$

making explicit the subdeterminants. Therefore, the conditions $c_3$ (Line 5) and $c'_3$ (Line 6) are also amenable to sign conditions on appropriate subdeterminants.
**Algorithm 5: SelfSurrounding:** self surrounding of $a_i$ ($n = 3$).

**Data:** Three pairs $\{a_1, a'_1\}, \{a_2, a'_2\}, \{a_3, a'_3\}$ of vectors in $\mathbb{R}^3$.

1. $\{u_1, u_2, u_3\} \leftarrow a_i$

2. $c \leftarrow \pi_u = \begin{pmatrix} u_2 & -u_1 & 0 \\ u_3 & 0 & -u_1 \end{pmatrix} \lor \pi_u = \begin{pmatrix} u_2 & -u_1 & 0 \\ 0 & u_3 & -u_2 \end{pmatrix} \lor \pi_u = \begin{pmatrix} 0 & u_3 & -u_2 \\ u_3 & 0 & -u_1 \end{pmatrix}$

3. **return** $c \land QCovering[\{\pi_u a_j, \pi_u a'_j\}, \{\pi_u a_k, \pi_u a'_k\}]$

To get an algebraic characterization for self surrounding for $n = 3$, in addition to the aforementioned characterization of the Q-covering problem for $n = 2$, we further need means to perform the projection on the orthogonal space of a vector $u = (u_1, u_2, u_3) \neq 0$. To do so, we use one of the following generic projectors:

$$ \pi_u = \begin{pmatrix} u_2 & -u_1 & 0 \\ u_3 & 0 & -u_1 \end{pmatrix}, \text{ or } \pi_u = \begin{pmatrix} -u_2 & u_1 & 0 \\ 0 & u_3 & -u_2 \end{pmatrix}, \text{ or } \pi_u = \begin{pmatrix} 0 & -u_3 & u_2 \\ -u_3 & 0 & u_1 \end{pmatrix}. \quad (5) $$

Setting $u$ to $a_i$, one gets that $a_i$ is self surrounded if and only if $\mathbb{R}^2 \subseteq \{\pi_u a_j, \pi_u a'_j\} \lor \{\pi_u a_k, \pi_u a'_k\}$ as shown in Algorithm 5. Notice that, when $u = 0$, $\pi_u = 0$ and the algorithm returns False as expected (the vector $0$ cannot be self surrounded).

**Lemma 12.** Let $u, v, w \in \mathbb{R}^3$ and let $\pi_u$ denote a generic projector (cf. Eq. (5)). Deciding the sign of $\det(\pi_u v \pi_u w)$ and the equivalence $\pi_u v \simeq \pi_u w$ reduce to sign conditions on the subdeterminants of the matrix $(u v w)$.

*Proof.* Suppose (a similar discussion holds for the other projectors)

$$ \pi_u = \begin{pmatrix} u_2 & -u_1 & 0 \\ u_3 & 0 & -u_1 \end{pmatrix}, \quad s_1 = u_2 v_1 - u_1 v_2, \quad s_3 = u_2 w_1 - u_1 w_2 \\ s_2 = u_3 v_1 - u_1 v_3, \quad s_4 = u_3 w_1 - u_1 w_3 $$

Then, one has

$$ \pi_u v = \begin{pmatrix} s_1 \\ s_2 \end{pmatrix}, \quad \pi_u w = \begin{pmatrix} s_3 \\ s_4 \end{pmatrix}, \quad \det(\pi_u v \pi_u w) = u_1 \det(u v w), $$

Thus, as mentioned in Remark 5, Eq. (4), the condition

$$ \det(\pi_u v \pi_u w) = 0 \land (\pi_u v)(\pi_u w) > 0, $$

becomes equivalent to

$$ u_1 \det(u v w) = 0 \land (s_1 s_3 > 0 \lor s_2 s_4 > 0), $$

making therefore explicit the sign conditions on the subdeterminants of $(u v w)$. $\square$

As already observed, self surrounding for $n = 3$ reduces to a planar Q-covering problem (Proposition 8) which is in turn equivalent to four surrounding problems for $n = 2$ (Theorem 3), each characterized in Proposition 12, and implemented in Algorithm 4. Lemma 12 is the last ingredient to show that self surrounding for $n = 3$ reduces to sign conditions on the subdeterminants of the matrix $(a_1 a_2 a_3 a'_1 a'_2 a'_3)$.

## 5.3 Lazy Covering

To get an algebraic characterization for the Q-covering problem for $n = 3$, we still need to translate the condition $a_i \in \Sigma(a'_i)$ into an equivalent explicit set of constraints on the involved vectors. This task reduces to checking whether a vector belongs to a cone spanned by three vectors. First, the equivalence relation $u \simeq v$ is encoded as $u \times v = 0 \land u \cdot v > 0$ where $u \times v$ denotes the cross product. To check whether $u \in (a_1, a_2, a_3)^\dagger$, we simply verify that $\det(a_1 a_2 a_3)$, $\det(u a_2 a_3)$, $\det(a_1 u a_3)$, $\det(a_1 a_2 u)$ are all positive or all negative (the ordering of the column vectors of the matrices ensure the coherence of the orientation; cf. the discussion at the beginning of Section 5); We can alternatively regard lazy surrounding as a Q-covering problem as stated in Proposition 9. It remains to check whether $u$ belongs to the faces of the cone, namely cones of the form $\langle v, w \rangle$. We do so by checking whether $u$ is equivalent to the generators, $v, w$, or it belongs to the relative interior of $\langle v, w \rangle$ as detailed in Algorithm 6. Finally, Algorithm 7 returns an equivalent characterization for $a'_i$ to be in a c-cone rooted at $a_i$.

**Remark 6.** The conditions of Algorithm 6 are also amenable to equivalent conditions on the sign of the subdeterminants of the matrix $(u v w)$. For $u \simeq v$, the components of the cross product are subdeterminants by definition. Moreover, the condition $u \times v = 0 \land u \cdot v > 0$ is equivalent to $u \times v = 0 \land (u_1 v_1 > 0 \lor u_2 v_2 > 0 \lor u_3 v_3 > 0)$, making explicit the subdeterminants. For condition $c_3$ (Line 3), one first observes that $\det(v w v \times w) > 0$ is equivalent to $v \times w \neq 0$.¹⁰ When in addition $\det(u v w) = 0$, $u = \alpha v + \beta w$ for some scalars $\alpha, \beta$, and $\det(v u v \times w) = \beta \det(v w v \times w)$ (the determinant is multilinear and alternating). Thus, assuming $v \times w \neq 0$, $\det(v u v \times w) > 0$ if and only if $\beta > 0$. As $u \cdot v^\perp = \beta w \cdot v^\perp$, one can then reformulate $\beta > 0$ as $\pi_u v \simeq \pi_u w$, which has been shown in Lemma 12 to reduce to sign conditions on the subdeterminants of the matrix $(u v w)$. The same discussion holds for $\det(u w v \times w) > 0$. Summing up, condition $c_3$ of Algorithm 6 becomes equivalent to $\det(u v w) = 0 \land v \times w \neq 0 \land \pi_u v \simeq \pi_u w \land \pi_u v \simeq \pi_u w$.
**Algorithm 6:** InFace: symbolic characterization of $u \in \langle v, w \rangle$ ($n = 3$).

**Data:** Three symbolic vectors of dimension 3.

1 $c_1 \leftarrow u \times v = 0 \land u.v > 0$

▷ $u \simeq v$

2 $c_2 \leftarrow u \times w = 0 \land u.w > 0$

▷ $u \simeq w$

3 $c_3 \leftarrow \det(u v w) = 0 \land \det(v w v \times w) > 0 \land \det(v u v \times w) > 0 \land \det(u w v \times w) > 0$

4 **return** ($u = 0$) $\lor$ $c_1 \lor c_2 \lor c_3$

**Algorithm 7:** InCone: symbolic characterization of $a'_i \in \langle a_i, a_j, a_k \rangle$ ($n = 3$).

**Data:** Four symbolic vectors of dimension 3.

1 $\{d_1, d_2, d_3, d_4\} \leftarrow \{\det(a_i a_j a_k), \det(a'_i a_j a_k), \det(a_i a'_i a_k), \det(a_i a_j a'_i)\}$

2 $c_1 \leftarrow (\bigwedge_{i=1}^4 d_i > 0) \lor (\bigwedge_{i=1}^4 d_i < 0)$

3 $c_2 \leftarrow \text{InFace}[a'_i, \{a_i, a_j\}] \lor \text{InFace}[a'_i, \{a_i, a_k\}] \lor \text{InFace}[a'_i, \{a_j, a_k\}]$

4 **return** ($a'_i = 0$) $\lor$ $c_1 \lor c_2$

As an immediate corollary of Remark 5, Lemma 12, and Remark 6, we get the following nontrivial result which, until now, was considered an open problem to the best of our knowledge.

**Theorem 6.** For $n = 3$, the Q-covering is characterized by sign conditions on the subdeterminants of the matrix $(a_1 a_2 a_3 a'_1 a'_2 a'_3)$. In particular, deciding if a 3-by-3 matrix $M$ is a Q-matrix reduces to sign conditions on the subdeterminants of $M$ effectively constructed by Algorithms 1–7.

It's worth mentioning, however, that [Garcia et al., 1983] showed that for super-regular matrices (cf. Section 5.4), when the conical degree of the piecewise linear mapping associated to $M$ is not zero, $M$ is Q-matrix. While the conical degree is determined using the signs of the subdeterminants of $M$, it was unclear whether the signs of subdeterminants were enough for the cases where the conical degree is zero, and more generally, for matrices that are not super-regular (for which the concept of conical degree is not well defined).

All algorithms were implemented to arrive at an algebraic characterization of the Q-covering problem when $n = 3$.<fnref n="11" /> When $\Sigma_0 = \{e_1, e_2, e_3, -M_1, -M_2, -M_3\}$ for a matrix $M = (M_1 M_2 M_3)$, one gets a list of sign conditions on the subdeterminants of $M$ for $M$ to be a Q-matrix. Checking if a given instance is a Q-matrix is thus performed in constant time: it suffices to substitute the values and check the conditions. For instance, for

$$M = \begin{pmatrix} m_1 & m_2 & m_3 \\ m_4 & m_5 & m_6 \\ m_7 & m_8 & m_9 \end{pmatrix}, \qquad (6)$$

any specialization of $m_1, \dots, m_9$ that satisfies

$$m_1 > 0 \land m_2 = 0 \land m_3 = 0 \land m_5 < 0 \land m_6 > 0 \land m_8 > 0 \land m_9 < 0 \land m_5 m_9 - m_6 m_8 < 0$$

is a Q-matrix (which is clearly not a P-matrix as $m_5 < 0$). Such a characterization turned out to be very useful to automatically find counter examples to sharpen our intuitions and help answering certain conjectures as we shall see next.

## 5.4 Generating Special Q-matrices

[Karamardian, 1972] drew a specific attention to $R_0$ matrices (also known as super-regular matrices) for which LCP($0, M$) has a unique solution. It subsequently played an important role in LCP theory.

[Aganagic and Cottle, 1979] proved later that among $P_0$ matrices (i.e. matrices for which all principal minors are nonnegative), the subclasses of Q-matrices and $R_0$-matrices are equivalent.

We wanted to know whether a Q-matrix that is not super-regular exists for $n = 3$. It was previously known [Kelly and Watson, 1979, p. 177] that Q-matrices with flat c-cones are possible for $n = 3$. We were thus interested in finding a Q-matrix with non-pointed and non-flat c-cones. To do so we fixed $a'_2$ to $-e_1$ and found that the following conditions (among others) on the subdeterminants of $M$ (cf. Eq. (6)) have to hold

$$m_1 > 0 \land m_3 < 0 \land m_6 < 0 \land m_7 > 0 \land m_9 < 0 \land m_1 m_9 - m_3 m_7 > 0 \land m_4 m_9 - m_6 m_7 < 0.$$

The following instance is a particular case.

<footnote n="10">¹⁰Indeed, $\det(v w v \times w) = \|v \times w\|^2$ for any vectors $v, w$. Requiring the strict inequality ensures that the relative interior $\langle v, w \rangle^{\diamond}$ is not empty.</footnote>

<footnote n="11">¹¹We used Mathematica. Notebook available here https://gitlab.inria.fr/kghorbal/qmatrices.</footnote>
**Example 1.** Consider $-M_1 = (-2, -4, -3)$, $-M_2 = -e_1$, and $-M_3 = (1, 1, 1)$. The c-cones $\langle e_1, -M_2, e_3 \rangle$ and $\langle e_1, -M_2, -M_3 \rangle$ are non-pointed and therefore the following 3-by-3 matrix $M$ is not super-regular. It is however a Q-matrix.<fnref n="12" />

$$M = (M_1 \quad M_2 \quad M_3) = \begin{pmatrix} 2 & 1 & -1 \\ 4 & 0 & -1 \\ 3 & 0 & -1 \end{pmatrix}.$$

We can also easily check that there are no Q-matrices of the form $(v e_1 e_2)$ for any vector $v$ (which would have lead to 4 degenerate c-cones that are non-pointed and non-flat).

[Murty, 1972] gave the symmetric matrix $M_{Murty}$ (see below) for which all vectors in $\Sigma_0$ are both self and lazily surrounded. Using the algebraic characterization presented in this work, we checked that when all vectors are lazily surrounded, then they are necessarily also self surrounded (the converse isn't true, it suffices to consider any P-matrix). Enforcing lazy surrounding of all vectors in $\Sigma_0$ is unrelated to the symmetry of the matrix $M$. It turns out that Murty's example is an instance of the following conjunction:

$$m_1 < 0 \land m_3 > 0 \land m_4 > 0 \land m_5 < 0 \land m_6 > 0 \land m_7 > 0 \land m_8 > 0 \land m_9 < 0 \\ \land m_1 m_5 - m_2 m_4 < 0 \land m_1 m_9 - m_3 m_7 < 0 \land m_5 m_9 - m_6 m_8 < 0. \quad (7)$$

We give below several non symmetric instances.

**Example 2.** The following two matrices are Q-matrices for which all vectors in $\Sigma_0$ are both self and lazily surrounded (the space is covered twice by the c-cones). They both satisfy the conditions of Eq. (7).

$$M_{Murty} = \begin{pmatrix} -1 & 2 & 2 \\ 2 & -1 & 2 \\ 2 & 2 & -1 \end{pmatrix}, \quad M = \begin{pmatrix} -5 & 4 & 3 \\ 2 & -1 & 1 \\ 2 & 2 & -1 \end{pmatrix}.$$

Moreover, there are precisely 3 additional conjunctions, each involving strict sign conditions on the subdeterminants of $M$, such that all vectors in $\Sigma_0$ are both self and lazily surrounded. We give below one instance for each such conjunction (the sign conditions could be retrieved from the examples).

$$\begin{pmatrix} -7 & 5 & 1 \\ -6 & 4 & 1 \\ -8 & 8 & 1 \end{pmatrix}, \quad \begin{pmatrix} 3 & -9 & 1 \\ 4 & -10 & 1 \\ 16 & -16 & 1 \end{pmatrix}, \quad \begin{pmatrix} 7 & 5 & -1 \\ 12 & 2 & -1 \\ 8 & 4 & -1 \end{pmatrix}.$$

## Conclusion

We believe that using minimal cones to better understand holes is worth pursuing. An important question with this regard is whether the particular case of almost c-cones is all one needs in dimensions $\ge 4$. The approach is also appealing as it doesn't require particular assumptions on degeneracy (but does assume feasibility). It thus provides an interesting geometric alternative to degree theory. For $n \le 3$, one gets in addition an algebraic characterization involving only the signs of the subdeterminants of the involved matrix. So far, however, no particular pattern emerged from these conditions (unlike the elegant characterization for P-matrices requiring only the positivity of principal minors). From a computational standpoint, although getting an algebraic characterization was relatively easy (the presented algorithms are straightforward to implement), rewriting the so obtained condition into conjunctions on the signs of subdeterminants was computationally involved as many subcases are either redundant or empty. It would be really interesting to try to push the same reasoning for dimension $n = 4$ to get yet an additional hint about the polynomials involved as well as potential patterns on their sign conditions. We do believe that algebraic characterizations are really helpful to sharpen our intuitions and avoid pitfalls by automatically generating instances with the help of a computer.

**Acknowledgments** We would like to sincerely thank Prof. Walter Morris for his valuable comments and several related references he pointed out while reading an earlier draft of this work. We are also in debt to Jean-Charles Gilbert for his thorough reading and the several technical improvements he suggested. We finally thank the anonymous reviewers for their substantial feedback and several suggestions to help improve the clarity and readability of the paper.

## References

[Aganagic and Cottle, 1979] Aganagic, M. and Cottle, R. W. (1979). A note on Q-matrices. *Mathematical Programming*, 16(1):374–377.

[Aganagić and Cottle, 1978] Aganagić, W. and Cottle, R. W. (1978). On Q-matrices. Technical report, Systems Optimization Laboratory, Department of Operations Research, Stanford University, Stanford, California. SOL 78-9.

<footnote n="12">¹²The fact that the provided matrix is a Q-matrix can be checked independently using for instance a quantifier elimination procedure over the reals, like the Cylindrical Algebraic Decomposition or Gale's algorithm [Aganagić and Cottle, 1978, p. 4].</footnote>
[Brugnano and Casulli, 2008] Brugnano, L. and Casulli, V. (2008). Iterative solution of piecewise linear systems. *SIAM Journal on Scientific Computing*, 30(1):463-472.

[Chung, 1989] Chung, S. J. (1989). Np-completeness of the linear complementarity problem. *J. Optim. Theory Appl.*, 60(3):393-399.

[Coppel, 1998] Coppel, W. A. (1998). *Foundations of Convex Geometry*. Cambridge University Press, Cambridge, UK.

[Cottle et al., 2009] Cottle, R., Pang, J., and Stone, R. (2009). *The Linear Complementarity Problem*. Classics in Applied Mathematics. Society for Industrial and Applied Mathematics, Philadelphia, United States.

[Cottle, 1980] Cottle, R. W. (1980). Completely-Q matrices. *Mathematical Programming: Series A and B*, 19(1):347-351.

[Cottle et al., 1981a] Cottle, R. W., von Randow, R., and Stone, R. E. (1981a). On spherically convex sets and Q-matrices. *Linear Algebra and its Applications*, 41:73-80.

[Cottle et al., 1981b] Cottle, R. W., von Randow, R., and Stone, R. E. (1981b). On spherically convex sets and q-matrices. *Linear Algebra and its Applications*, 41:73-80.

[Coxson, 1994] Coxson, G. E. (1994). The P-matrix problem is co-np-complete. *Mathematical Programming*, 64:173-178.

[De Loera and Morris Jr., 1999] De Loera, J. A. and Morris Jr., W. D. (1999). Q-matrix recognition via secondary and universal polytopes. *Mathematical Programming*, 85:259-276.

[Fredricksen et al., 1986] Fredricksen, J. T., Watson, L. T., and Murty, K. G. (1986). A finite characterization of K-matrices in dimensions less than four. *Mathematical programming*, 35(1):17-31.

[Garcia et al., 1983] Garcia, C. B., Gould, F. J., and Turnbull, T. R. (1983). Relations between pl maps, complementary cones, and degree in linear complementarity problems. In Curtis Eaves, B., Gould, F. J., Peitgen, H.-O., and Todd, M. J., editors, *Homotopy Methods and Global Convergence*, pages 91-144. Springer US, Boston, MA.

[Goerss and Jardine, 2012] Goerss, P. and Jardine, J. (2012). *Simplicial Homotopy Theory*. Progress in Mathematics. Birkhäuser Basel, Basel, Switzerland.

[Jeanneret and Lines, 2014] Jeanneret, A. and Lines, D. (2014). *Invitation à la topologie algébrique Tome II : Cohomologie - Variétés*. Éditions Cépaduès, France.

[Karamardian, 1972] Karamardian, S. (1972). The complementarity problem. *Mathematical programming*, 2:107-129.

[Kelly and Watson, 1979] Kelly, L. and Watson, L. (1979). Q-matrices and spherical geometry. *Linear Algebra and its Applications*, 25:175-189.

[Kozaily, 2024] Kozaily, C. (2024). *On the existence of solutions for Linear Complementarity Problems*. PhD thesis, Dept. of Mathematics, University of Rennes, France.

[Morris Jr, 1986] Morris Jr, W. D. (1986). Oriented matroids and the linear complementarity problem. Technical report, Cornell University Operations Research and Industrial Engineering.

[Morris Jr, 1988] Morris Jr, W. D. (1988). Counterexamples to Q-matrix conjectures. *Linear Algebra and its Applications*, 111:135-145.

[Murty, 1972] Murty, K. G. (1972). On the number of solutions to the complementarity problem and spanning properties of complementary cones. *Linear Algebra and its Applications*, 5(1):65-108.

[Naiman and Stone, 1998] Naiman, D. Q. and Stone, R. E. (1998). A homological characterization of Q-matrices. *Mathematics of Operations Research*, 23(2):463-478.

[Pang, 1979] Pang, J.-S. (1979). On Q-matrices. *Mathematical Programming*, 17(1):243-247.

[Radons and Tonelli-Cueto, 2023] Radons, M. and Tonelli-Cueto, J. (2023). Generalized perron roots and solvability of the absolute value equation. *SIAM Journal on Matrix Analysis and Applications*, 44(4):1645-1666.

[Rockafellar, 1997] Rockafellar, R. (1997). *Convex Analysis*. Princeton Landmarks in Mathematics and Physics. Princeton University Press, NJ, USA.

[Samelson et al., 1958] Samelson, H., Thrall, R. M., and Wesler, O. (1958). A partition theorem for Euclidean n-space. In *Proceedings of the American Mathematical Society*.

[Watson, 1974] Watson, L. T. (1974). *A Variational Approach To The Linear Complementarity Problem*. PhD thesis, Dept. of Mathematics, University of Michigan, Ann Arbor, MI.