An Algorithm to Find the Lineality Space of the Positive Hull of a Set of Vectors

The positive hull of a finite set of vectors, $calV$ , in d‐dimensional space may or may not contain a lineality space $calL$ . This article presents an algorithm that identifies the vectors of $calV$ that belong to $calL$ . This is done by means of a sequence of supporting hyperplanes because every supporting hyperplane of the positive hull of $calV$ contains $calL$ . Computational results show the effectiveness of the algorithm, which is compared to the best procedure currently available (to the best knowledge of the author) that solves the same problem. The algorithm introduced here is especially efficient in the case of large problems, where cardinality and/or dimensions are large.