Gale–Ryser Binary Matrix Margins

Worked Example

Consider a matrix margin problem with row sums r = (2, 2, 1) and column sums c = (2, 2, 1). The row sum and column sum are equal (2 + 2 + 1 = 5). The Gale-Ryser theorem checks if the sum of the first k largest row sums is at most the sum of min(k, c_j) over all columns j, for every k.

1. For k1 LHS 2 ≤ RHS 3.
2. For k2 LHS 4 ≤ RHS 5.
3. For k3 LHS 5 = RHS 5, equal totals 5. Expected result: Realizable.

An example witness is [[1,1,0],[1,0,1],[0,1,0]], and independently enumerating all 512 labeled binary 3x3 matrices gives 5 realizations.

Experiment

In the Gale–Ryser Binary Matrix Margins module, you can explore whether a binary matrix can be formed with given margins:

1. Set Margins to "Equal total impossible".
2. Observe that the Status is "Inequality violation", even though the row and column totals are equal.
3. Look at the chart and see the red row sum line crosses above the blue capacity curve, showing at which k the violation occurs.
4. Switch Transpose to "Yes" and note how the first violated k changes.

Limitations

The Gale-Ryser theorem only determines whether a valid configuration is possible. Finding an actual configuration might still require a search or network flow algorithm. Additionally, it applies specifically to bipartite graphs (or binary matrices), unlike the Havel-Hakimi theorem which deals with simple graphs (symmetric binary matrices with zero diagonal). The total number of solutions is not specified by the theorem and requires explicit counting.

References

The mathematical properties of these sequences are closely related to integer partitions and majorization.

• SageMath: Integer Vectors