Polytopes of alternating sign matrices with dihedral symmetries

Read full text
Authors: Péter Madarasi
Cited by: 0

Abstract

We study the convex hulls of $n \times n$ alternating sign matrices invariant under subgroups of the dihedral group of the square. For each non-trivial symmetry class, the symmetry determines the full matrix affinely from a smaller set of entries, allowing us to study the corresponding convex hull in a lower-dimensional space. For the vertical, vertical$\unicode{x2013}$horizontal, half-turn, diagonal, diagonal$\unicode{x2013}$antidiagonal, and total symmetry classes, we give polynomial-size linear inequality descriptions, determine the dimensions, identify all facets, and give exact facet counts. For the quarter-turn class, the natural fixed-point relaxation is not integral. We obtain the exact hull by adding parity-type Chvátal$\unicode{x2013}$Gomory inequalities, determine its dimension, and construct a family of facets indexed by Ferrers diagrams of Catalan-number cardinality, while the complete facet structure remains open. The formulations yield strongly polynomial-time algorithms for linear optimization over every non-empty symmetry class. We also show that the full-matrix polytopes of all classes except the quarter-turn class have the integer Carathéodory property and hence the integer decomposition property.

Fields of Study & Subjects

Advanced Combinatorial Mathematics Complexity and Algorithms in Graphs Advanced Optimization Algorithms Research

Publication details

Journal / source
arXiv (Cornell University)
Publication date
20 February 2026
Language
EN
Document type
Preprint