Leontief Substitution Systems and Matroid Complexes

A (pre-) Leontief substitution system is a linear system Ax = b, x > 0, where b is a nonnegative vector and A is a matrix containing at most one positive element in each column. We investigate the face structure of nondegenerate Leontief substitution systems by looking at the corresponding dual simplicial complex. A characterization of the face structure is given for the bounded case (called a totally pre-Leontief substitution system by Dantzig and Veinott), and it is shown that the dual complex always comprises the independent sets of a matroid. Conversely, a characterization is given for the class of matroids whose independent sets form the dual complex to a polyhedron, and it is shown that this polyhedron can always be chosen to be a (not necessarily bounded) Leontief substitution system. The number of such matroids is also given as functions of the rank and the cardinality of the base set. and the number of nondegenerate totally (pre-) Leontief substitution systems is given as functions of the number of equalities and the number of variables.