Gale–Ryser theorem

Statement

Let $t$ be a positive integer, and let $R = (r_1 \ge r_2 \ge \dots)$ and $C = (c_1 \ge c_2 \ge \dots)$ be two partitions of $t$. A $0$-$1$ matrix has row sums $R$ and column sums $C$ when it has one row for each part of $R$ and one column for each part of $C$, its entries are all $0$ or $1$, row $i$ adds up to $r_i$, and column $j$ adds up to $c_j$.

Let $R^d$ be the conjugate partition of $R$. Its $j$-th part is the number of parts of $R$ that are at least $j$.

Then a $0$-$1$ matrix with row sums $R$ and column sums $C$ exists if and only if $R^d$ dominates $C$ in the dominance order on partitions of $t$. That is, for each $k \ge 1$, the sum of the $k$ largest parts of $R^d$ is at least the sum of the $k$ largest parts of $C$, where missing parts count as $0$.