Constructing integral matrices with given line sums

DOI10.1016/J.LAA.2009.05.024MaRDI QIDQ840652zbMATH OpenOpenAlexFDO

Authors J. A. Dias Da Silva, Amélia Fonseca

Publication date 14 September 2009

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.laa.2009.05.024

zbMATH Keywords

construction of integral matricesintegral matrices with given line sumspartition dominationpartitions

Mathematics Subject Classification ID

Combinatorial aspects of partitions of integers (05A17) Partitions; congruences and congruential restrictions (11P83) Matrices of integers (15B36)

Review text

Around 1960, \textit{D. Gale} [Pac. J. Math. 7, 1073--1082 (1957; Zbl 0087.16303)] and \textit{H. J. Ryser} [Can. J. Math. 9, 371--377 (1957; Zbl 0079.01102)] independently proved the famous theorem bearing their names on the existence of \((0,1)\)-matrices with prescribed row and column sums given by two different partitions of the same integer. The necessary and sufficient condition stated in the theorem is: the conjugate of the row-sum partition dominates the column-sum partition. Roughly eight years later, Mirsky solved the more general problem of finding conditions for the existence of a nonnegative integer matrix with entries less than or equal to a given integer and with prescribed row and column sums. Brualdi then proved that a modified version of the Gale-Ryser domination condition is still necessary and sufficient for the existence of a matrix with the constraints mentioned above. The authors prove another extension of the Gale-Ryser theorem and present a method for constructing nonnegative integer matrices with the same constraints as in the Mirsky and Brualdi results.

Recommendations

• A canonical construction for nonnegative integral matrices with given line sums
• scientific article; zbMATH DE number 7057496
• Integral matrices with given row and column sums
• scientific article; zbMATH DE number 4059421
• Integral matrices with given row and column sums

Cites work

• A theorem on flows in networks
• Combinatorial matrix classes
• Combinatorial matrix theory
• Combinatorial Properties of Matrices of Zeros and Ones
• Combinatorial theorems and integral matrices
• Transversal theory. An account of some aspects of combinatorial mathematics

Cited in

(15)

• On joint realization of (0,1) matrices
• Integral matrices with given row and column sums
• On the existence of sequences and matrices with prescribed partial sums of elements
• The doubly graded matrix cone and Ferrers matrices
• On the largest size of an antichain in the Bruhat order for A (2k,k)
• Integral matrices with given row and column sums
• A generalization of a theorem of König
• scientific article; zbMATH DE number 4059421 (Why is no real title available?)
• A Simple Proof of the Gale-Ryser Theorem
• A canonical construction for nonnegative integral matrices with given line sums
• Construction of matrices with known sums of rows and columns
• Matrices of zeros and ones with given line sums and a zero block
• Integer matrices with constraints on leading partial row and column sums
• The maximal length of a chain in the Bruhat order for a class of binary matrices
• A \((0,1)\)-matrix existence theorem and equivalent tiling problems with dimers and monomers

This page was built for publication: Constructing integral matrices with given line sums

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q840652)