## Section16.5Zero–One Matrices

Matrices with all entries $0$ and $1$ arise in many combinatorial settings, and here we present a classic result, called the Gale-Ryser theorem. It deals with zero–one matrices with specified row and column sum strings. When $M$ is an $m\times n$ zero–one matrix, the string $R=(r_1,r_2,\dots,r_m)\text{,}$ where $r_i=\sum_{1\le j\le n}m_{i,j}\text{,}$ is called the row sum string of $M\text{.}$ The column sum string $C=(c_1,c_2,\dots,c_n)$ is defined analogously. Conversely, let $m$ and $n$ be positive integers, and let $R=(r_1,r_2,\dots,r_m)$ and $C=(c_1,c_2,\dots,c_n)$ be strings of non-negative integers. The question is whether there exists an $m\times n$ zero–one matrix $M$ with row sum string $R$ and column sum string $C\text{.}$

To attack this problem, we pause briefly to develop some additional background material. Note that we may assume without loss of generality that there is a positive integer $t$ so that $\sum_{i=1}^mr_i=\sum_{j=1}^nc_j=t\text{,}$ else there is certainly no zero–one matrix with row sum string $R$ and column sum string $C\text{.}$ Furthermore, we may assume that both $R$ and $C$ are non-increasing strings, i.e., $r_1\ge r_2\ge \dots\ge r_m$ and $c_1\ge c_2\ge\dots\ge c_n\text{.}$

To see this note that whenever we exchange two rows in a zero–one matrix, the column sum string is unchanged. Accordingly after a suitable permutation of the rows, we may assume that $R$ is non-increasing. Then the process is repeated for the columns.

Finally, it is easy to see that we may assume that all entries in $R$ and $C$ are positive integers, since zeroes in these strings correspond to rows of zeroes or columns of zeroes in the matrix. Accordingly, the row sum string $R$ and the column sum string $C$ can be viewed as partitions of the integer $t\text{,}$ a topic we first introduced in Chapter 8.

For the balance of this section, we let $t$ be a positive integer and we let $\cgP(t)$ denote the family of all partitions of the integer $t\text{.}$ There is a natural partial order on $\cgP(t)$ defined by setting $V=(v_1,v_2,\dots,v_m) \ge W=(w_1,w_2,\dots,w_n)$ if and only if $m\le n$ and $\sum_{1\le i\le j}v_j\ge \sum_{1\le i\le j}w_j$ for each $j=1,2,\dots,m\text{,}$ i.e., the sequence of partial sums for $V$ is always at least as large, term by term, as the sequence of partial sums of $W\text{.}$ For example, we show in (((fig-partitionlattice))) the partial order $\cgP(7)\text{.}$

FIGURE HERE

In the proof of the Gale-Ryser theorem, it will be essential to fully understand when one partition covers another. We state the following proposition for emphasis; the proof consists of just considering the details of the definition of the partial order on partitions.

To illustrate this concept, note that $(5,4,3)$ covers $(5,3,3,1)$ in $\cgP(12)\text{.}$ Also, we see $(6,6,4,3,3,3,1,1,1,1,)$ covers $(6,6,3,3,3,3,2,1,1,1)$ in $\cgP(29)\text{.}$

With a partition $V=(v_1,v_2,\dots,v_m)$ from $\cgP(t)\text{,}$ we associate a dual partition $W=(w_1,w_2,\dots,w_n)$ defined as follows: (1) $n=v_1$ and for each $j=1,\dots,n\text{,}$ $w_j$ is the number of entries in $V$ that are at least $n+1-j\text{.}$ For example, the dual partition of $V=(8,6,6,6,5,5,3,1,1,1)$ is $(8,7,7,6,6,4,1,1)\text{.}$ Of course, they are both partitions of $42\text{,}$ which is the secret of the universe! In what follows, we denote the dual of the partition $V$ by $V^d\text{.}$ Note that if $W=V^d\text{,}$ then $V=W^d\text{,}$ i.e., the dual of the dual is the original.

### Subsection16.5.1The Obvious Necessary Condition

Now let $M$ be a $m\times n$ zero–one matrix with row sum string $R=(r_1,r_2,\dots,r_m$ and column sum string $C=(c_1,c_2,\dots,c_n)\text{.}$ As noted before, we will assume that all entries in $R$ and $C$ are positive. Next, we modify $M$ to form a new matrix $M'$ as follows: For each $i=1,2,\dots,t\text{,}$ we push the $r_i$ ones in row $i$ as far to the left as possible, i.e., $m'_{i,j}=1$ if and only if $1\le j\le r_i\text{.}$ Note that $M$ and $M'$ both have $R$ for their row sum strings. However, if $C'$ denotes the column sum string for $M'\text{,}$ then $C'$ is a non-decreasing string, and the substring $C''$ of $C'$ consisting of the positive entries is $R^d\text{,}$ the dual partition of $R\text{.}$ Furthermore, for each $j=1,2,\dots,r_1\text{,}$ we have the inequality $\sum_{1\le i\le j} c''_i\le \sum_{1\le i\le j} c_i\text{,}$ since the operation of shift ones to the left can only increase the partial sums. It follows that $R^d\ge C$ in the poset $\cgP(t)\text{.}$

So here is the Gale-Ryser theorem.

The necessity of the condition has been established. We prove sufficiency. The proof is constructive. In the poset $\cgP(t\text{,}$ let $W_0>W_1>\dots>W_s$ be a chain so that (1) $W_0=R^d\text{,}$ (2) $W_s=C$ and (3) if $0\le p\lt s\text{,}$ then $W_p$ covers $W_{p+1}\text{.}$ We start with a zero one matrix $M_0$ having row sum string $R$ and column sum string $W_0\text{,}$ as suggested in (((fig-dualpartition))) for the partition $(8,4,3,1,1,1)\text{.}$ If $s=0\text{,}$ we are done, so we assume that for some $p$ with $0\le p\lt s\text{,}$ we have a zero–one matrix $M_p$ with row sum string $R$ and column sum string $W_p\text{.}$ Then let $i$ and $j$ be the integers from Proposition 16.11, which detail how $W_p$ covers $W_{p+1}\text{.}$ Choose a row $q$ so that the $q,i$ entry of $M_p$ is $1$ while the $q,j$ entry of $M$ is $0\text{.}$ Exchange these two entries to form the matrix $M_{p+1}\text{.}$ Note that the exchange may in fact require adding a new column to the matrix.