Recursive structure of S-matrices and an \(O(m^ 2)\) algorithm for recognizing sign solvability (Q1093326)

An S-matrix is an \(m\times (m+1)\) real matrix B such that for each matrix C of the same sign pattern as B, C's columns are the vertices of an m- simplex that has the origin in its interior. An \(S^*\)-matrix is one that can be made into an S-matrix by replacing some columns with their negatives. This paper establishes new results on the recursive structure of the class of all S-matrices and the class of all \(S^*\)-matrices. The results form the basis of algorithms of time complexity \({\mathcal O}(m^ 2)\) for recognizing S-matrices, \(S^*\)-matrices and strong sign solvability of linear systems.