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.
Proposition 16.11.
Let \(V=(v_1,v_2,\dots,v_m)\) and \(W=(w_1,w_2,\dots,w_n)\) be partitions of an integer \(t\text{.}\) If \(V\) covers \(W\) in the poset \(\cgP(t)\text{,}\) then \(n\le m+1\) and there exist integers \(i\) and \(j\) with \(1\le i\lt j\le n\) so that the following statements hold.
\(v_\alpha=w_\alpha\text{,}\) when \(1\le \alpha\lt i\text{.}\)
\(v_\beta=w_\beta\text{,}\) when \(j\lt \beta\le m\text{.}\)
\(v_i=1+w_i\text{.}\)
Either (a) \(j\le m\) and \(w_j=1+v_j\text{,}\) or (b) \(j=n=m+1\) and \(w_j=1\text{.}\)
If \(j>i+1\text{,}\) then \(w_\gamma=v_\gamma=v_i-1\) when \(i\lt \gamma\lt j\text{.}\)
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.
Subsection 16.5.1 The 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.
Theorem 16.12. Gale-Ryser.
Let \(R\) and \(C\) be partitions of a positive integer \(t\text{.}\) Then there exists a zero–one matrix with row sum string \(R\) and column sum string \(C\) if and only if \(R^d\ge C\) in the poset \(\cgP(t)\text{.}\)
Proof.
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.
