Constructing integral matrices with given line sums (Q840652): Difference between revisions

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.