Gale-Ryser theorem

The Gale-Ryser theorem is a fundamental result in combinatorial matrix theory that characterizes when a binary matrix with prescribed row and column sums exists. Given two sequences of non-negative integers — a row sum vector and a column sum vector — the theorem provides necessary and sufficient conditions, in the form of a set of inequalities, for the existence of a binary matrix whose row and column sums match the given sequences.

The theorem was proved independently by David Gale and by H. J. Ryser in 1957. The conditions are a majorization inequality: the conjugate partition of the row sums must dominate the column sums in the sense of Hardy-Littlewood-Pólya. This reveals that the feasibility of a binary matrix is not a matter of trial and error but a structural property of the degree sequences themselves.

The Gale-Ryser theorem is the ancestor of modern results in graph realization, network flow theory, and discrete tomography. The problem of determining whether a given degree sequence can be realized as a graph is a special case, and the theorem's conditions are the foundation of the Havel-Hakimi algorithm for graph realization. The theorem also connects to the theory of contingency tables in statistics, where the question is whether observed marginal distributions could arise from a joint distribution with certain structural properties.

The deeper significance of the theorem is that it transforms an existence problem into an inequality problem. Instead of searching for a matrix, one checks a set of inequalities. This is a characteristic move in Gale's work: the replacement of search by structure, of construction by constraint. The theorem is a proof that complexity is sometimes a surface effect, and that beneath it lies a simpler order waiting to be named.