On the recognition of \(S\)-systems (Q1311323)

A sequence \({\mathcal A} = (A_ 1, \dots, A_ n)\) of nonempty subsets of \(\mathbb{R}^ m\) is called an \(m \times n\) system. Here every point of \(\mathbb{R}^ m\) is represented by a column vector of length \(m\). Now \({\mathcal M} ({\mathcal A})\) is the set of all \(m \times n\) matrices \(A = [a_ 1, \dots, a_ n]\), where \(a_ j \in A_ j\). An \(m \times n\) system is called an \(S\)-system if for each \(A \in {\mathcal M} ({\mathcal A})\), the columns of \(A\) are the vertices of an \((n-1)\)-simplex whose relative interior includes the origin of \(\mathbb{R}^ m\). An equivalent definition is that the nullspace \(N(A)\) is a line through the origin that penetrates the strictly positive orthant of \(\mathbb{R}^ m\). One could consider \(S\)-systems where each \(A_ j\) is one of the \(3^ m\) sign cones in \(\mathbb{R}^ m\). These systems have proved to be essential for the sign-solvability of linear systems. The paper considers \(S\)-systems and algorithms for recognition of them of arbitrary finitely represented convex cones. A number of different algebraic characterizations of \(S\)-systems is given, one of which is used in the recognition algorithm. The recognition algorithm is based on algorithms for the following two questions for an \(m \times n\) system \({\mathcal A}\), where each \(A_ j\) is a finitely represented convex cone: (1) Does the origin belong to the vector sum \(\sum^ n_{j=1} A_ j\)? (2) Does the origin belong to the convex hull \(H^ n_{j=1} A_ j\)? Algorithms for these questions are based on the feasibility test of systems of linear inequalities. Hence, they require at most polynomial time. The recognition algorithm of \(S\)-systems for finitely represented convex cones is based on repeatedly answering these questions for appropriate subsets of the cones.