 # Applied Combinatorics

## 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 [provisional cross-reference: 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 [provisional cross-reference: 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.