Weighted projections of alternating sign matrices: Latin-like squares and the ASM polytope

Cian O'Brien¹

¹Mary Immaculate College

The electronic journal of combinatorics, Tome 31 (2024) no. 1

Résumé

The weighted projection of an alternating sign matrix (ASM) was introduced by Brualdi and Dahl (2018) as a step towards characterising a generalisation of Latin squares they defined using alternating sign hypermatrices. Given row-vector $z_n = (n,\dots,2,1)$, the weighted projection of an ASM $A$ is equal to $z_nA$. Brualdi and Dahl proved that the weighted projection of an $n \times n$ ASM is majorized by the vector $z_n$, and conjectured that any positive integer vector majorized by $z_n$ is the weighted projection of some ASM. The main result of this paper presents a proof of this conjecture, via monotone triangles. A relaxation of a monotone triangle, called a row-increasing triangle, is introduced. It is shown that for any row-increasing triangle $T$, there exists a monotone triangle $M$ such that each entry of $M$ occurs the same number of times as in $T$. A construction is also outlined for an ASM with given weighted projection. The relationship of the main result to existing results concerning the ASM polytope $ASM_n$ is examined, and a characterisation is given for the relationship between elements of $ASM_n$ corresponding to the same point in the regular $n$-permutohedron. Finally, the limitations of the main result for characterising alternating sign hypermatrix Latin-like squares are considered.

Détail

DOI : 10.37236/11741

Classification : 05B15, 05B20, 52B05
Mots-clés : alternating sign matrix, alternating sign hypermatrix, ASM polytope, Latin-like square, weighted projection, monotone triangle, permutohedron