×

Sign-restricted matrices of 0’s, 1’s, and \(-1\)’s. (English) Zbl 1459.05013

Summary: We study sign-restricted matrices (SRMs), a class of rectangular \((0, \pm 1)\)-matrices generalizing the alternating sign matrices (ASMs). In an SRM each partial column sum, starting from row 1, equals 0 or 1, and each partial row sum, starting from column 1, is nonnegative. We determine the maximum number of nonzeros in SRMs and characterize the possible row and column sum vectors. Moreover, a number of results on interchange operations are shown, both for SRMs and, more generally, for \((0, \pm 1)\)-matrices. The Bruhat order on ASMs can be extended to SRMs with the result a distributive lattice. Also, we study polytopes associated with SRMs and some relates decompositions.

MSC:

05A18 Partitions of sets
05B20 Combinatorial aspects of matrices (incidence, Hadamard, etc.)
06A07 Combinatorics of partially ordered sets
15B35 Sign pattern matrices
15B36 Matrices of integers
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Anstee, R. P., The network flows approach for matrices with given row and column sums, Discrete Math., 44, 125-138 (1983) · Zbl 0516.05036
[2] Aval, J. C., Keys and alternating sign matrices, Sémin. Lothar. Comb., 59, Article B59F pp. (2007/2010) · Zbl 1179.05117
[3] Brualdi, R. A.; Ryser, H. J., Combinatorial Matrix Theory (1991), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0746.05002
[4] Brualdi, R. A., Combinatorial Matrix Classes (2006), Cambridge University Press: Cambridge University Press Cambridge · Zbl 1106.05001
[5] Behrend, R. E.; Knight, V. A., Higher spin alternating sign matrices, Electron. J. Comb., 14, #1 (2007) · Zbl 1183.05003
[6] Brualdi, R. A.; Dahl, G., Alternating sign matrices, extensions and related cones, Adv. Appl. Math., 86, 19-49 (2017) · Zbl 1358.15023
[7] Brualdi, R. A.; Dahl, G., Alternating sign matrices and hypermatrices, and a generalization of Latin squares, Adv. Appl. Math., 95, 116-151 (2018) · Zbl 1379.05020
[8] Bressoud, D., Proofs and Confirmations. The Story of the Alternating Sign Matrix Conjecture, MAA Spectrum, Math. Assoc. America (1994), Cambridge Univ. Press: Cambridge Univ. Press Washington, DC
[9] Davey, B. A.; Priestly, H. A., Introduction to Lattices and Order (1990), Cambridge Univ. Press · Zbl 0701.06001
[10] Fortin, M., The MacNeille completion of the poset of partial injective functions, Electron. J. Comb., 15, Article #R62 pp. (2008) · Zbl 1192.06004
[11] Lascoux, A.; Schűtzenberger, M.-P., Treillis et bases des groupes de Coxeter, Electron. J. Comb., 3, Article #R27 pp. (1996) · Zbl 0885.05111
[12] Solhjem, S.; Striker, J., Sign matrix polytopes from Young tableaux, Linear Algebra Appl., 574, 84-122 (2019) · Zbl 1411.05288
[13] Striker, J., The alternating sign matrix polytope, Electron. J. Comb., 16, 1 (2009), Research paper 41, 15 pp · Zbl 1226.05168
[14] Schrijver, A., Theory of Linear and Integer Programming (1986), Wiley-Interscience: Wiley-Interscience Chichester · Zbl 0665.90063
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.