Poset and polytope perspectives on alternating sign matrices.

Abstract

Alternating sign matrices (ASMs) are square matrices with entries 0, 1, or -1 whose rows and columns sum to 1 and whose nonzero entries alternate in sign. We put ASMs into a larger context by studying a certain tetrahedral poset and its subposets. We prove the order ideals of these subposets are in bijection with a variety of interesting combinatorial objects, including ASMs, totally symmetric self--complementary plane partitions (TSSCPPs), Catalan objects, tournaments, and totally symmetric plane partitions. We prove product formulas counting these order ideals and give the rank generating function of some of the corresponding lattices of order ideals. We also reformulate a known expansion of the tournament generating function as a sum over ASMs and prove a new expansion as a sum over TSSCPPs. We define the alternating sign matrix polytope as the convex hull of nxn alternating sign matrices and prove its equivalent description in terms of inequalities. We count its facets and vertices and describe its projection to the permutohedron as well as give a complete characterization of its face lattice in terms of modified square ice configurations. Furthermore we prove that the dimension of any face can be easily determined from this characterization.