Integral Matrices with Given Row and Column Sums

Let \(m\) and \(n\) be positive integers, and let \(\mathbf{R} = (r_1, \ldots, r_m)\) and \(\mathbf{S} = (s_1, \ldots, s_n)\) be nonnegative integral vectors with \(r_1 + \cdots + r_m = s_1 + \cdots + s_n\). Let \(\mathbf{Q} = (q_{ij})\) be an \(m \times n\) nonnegative integral matrix. Denote by \(\mathcal{U}^Q(\mathbf{R}, \mathbf{S})\) the class of all \(m \times n\) nonnegative integral matrices \(\mathbf{A} = (a_{ij})\) with row sum vector \(\mathbf{R}\) and column sum vector \(\mathbf{S}\) such that \(a_{ij} \leq q_{ij}\) for all \(i\) and \(j\). We study a condition for the existence of a matrix in \(\mathcal{U}^Q(\mathbf{R}, \mathbf{S})\). The well known existence theorem follows from the max-flow-min-cut theorem. It contains an exponential number of inequalities. By generalizing the Gale-Ryser theorem, we obtain some conditions under which this exponential number of inequalities can be reduced to a polynomial number of inequalities. We build a kind of hierarchy of theorems: under weaker and weaker conditions, a (larger and larger) polynomial (in \(n\)) number of inequalities yield a necessary and sufficient condition for the existence of a matrix in \(\mathcal{U}^Q(\mathbf{R}, \mathbf{S})\).