Polytopes of alternating sign matrices with dihedral-subgroup symmetry
2026-02-20 • Discrete Mathematics
Discrete Mathematics
AI summaryⓘ
The authors study special square matrices called alternating sign matrices (ASMs) that remain the same when flipped or rotated in certain ways (symmetries). They create a new method to break these large matrices into smaller parts called cores, which makes it easier to understand their shape using geometry and math tools. For most symmetry types, they describe these shapes fully using simple math rules, but one type (quarter-turn symmetry) is more complicated and needs extra conditions. Their work also helps find the smallest-cost matrix with these symmetries efficiently by linking matrix properties to geometric and optimization methods.
alternating sign matrix (ASM)dihedral symmetryconvex hullpolytopepolyhedral combinatoricsfacet descriptionlinear inequalitiesChvátal–Gomory inequalitiescombinatorial optimizationaffine map
Authors
Péter Madarasi
Abstract
We investigate the convex hulls of the eight dihedral symmetry classes of $n \times n$ alternating sign matrices, i.e., ASMs invariant under a subgroup of the symmetry group of the square. Extending the prefix-sum description of the ASM polytope, we develop a uniform core--assembly framework: each symmetry class is encoded by a set of core positions and an affine assembly map that reconstructs the full matrix from its core. This reduction transfers polyhedral questions to lower-dimensional core polytopes, which are better suited to the tool set of polyhedral combinatorics, while retaining complete information about the original symmetry class. For the vertical, vertical--horizontal, half-turn, diagonal, diagonal--antidiagonal, and total symmetry classes, we give explicit polynomial-size linear inequality descriptions of the associated polytopes. In these cases, we also determine the dimension and provide facet descriptions. The quarter-turn symmetry class behaves differently: the natural relaxation admits fractional vertices, and we need to extend the system with a structured family of parity-type Chvátal--Gomory inequalities to obtain the quarter-turn symmetric ASM polytope. Our framework leads to efficient algorithms for computing minimum-cost ASMs in each symmetry class and provides a direct link between the combinatorics of symmetric ASMs and tools from polyhedral combinatorics and combinatorial optimization.