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.
From: Péter Madarasi [view email]
[v1]
Fri, 20 Feb 2026 18:48:42 UTC (72 KB)
[v2]
Tue, 18 Aug 2026 19:32:27 UTC (104 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。