Discrepancy of Matrices of Zeros and Ones

Richard A. Brualdi^{∗} and Jian Shen^{†} Department of Mathematics University of Wisconsin Madison, Wisconsin 53706

            brualdi@math.wisc.edu    jshen@math.wisc.edu

AMS Subject Classification: 05B20

Submitted: January 18, 1999; Accepted: February 10, 1999

Abstract

Let m and n be positive integers, and let R = (r_{1}, …, r_{m}) and S = (s_{1}, …, s_{n}) be non-negative integral vectors. Let A(R, S) be the set of all m × n (0, 1)-matrices with row sum vector R and column vector S, and let Ā be the m × n (0, 1)-matrix where for each i, 1 ≤ i ≤ m, row i consists of r_{i} 1’s followed by n − r_{i} 0’s. If S is monotone, the discrepancy d(A) of A is the number of positions in which Ā has a 1 and A has a 0. It equals the number of 1’s in Ā which have to be shifted in rows to obtain A. In this paper, we study the minimum and maximum d(A) among all matrices A ∈ A(R, S). We completely solve the minimum discrepancy problem by giving an explicit formula in terms of R and S for it. On the other hand, the problem of finding an explicit formula for the maximum discrepancy turns out to be very difficult. Instead, we find an algorithm to compute the maximum discrepancy.

∗Partially supported by NSF Grant DMS-9424346.

†Supported by an NSERC Postdoctoral Fellowship.

1 Introduction

Let m and n be positive integers, and let R = (r_{1}, …, r_{m}) and S = (s_{1}, …, s_{n}) be non-negative integral vectors. The vector R is called monotone if r_{1} ≥ ⋯ ≥ r_{m}. Let A(R, S) be the set of all m × n (0, 1)-matrices with row sum vector R and column vector S, and let Ā be the m × n (0, 1)-matrix where for each i, 1 ≤ i ≤ m, row i consists of r_{i} 1’s followed by n − r_{i} 0’s. Let the column sum vector of Ā be R^{∗} = (r_{1}^{∗}, …, r_{n}^{∗}). It follows that R^{∗} is monotone and

r_{j}^{∗} = |{i : r_{i} ≥ j, i = 1, …, m}| for j = 1, …, n.

R and R^{∗} are called conjugate partitions of τ = r_{1} + ⋯ + r_{m} = r_{1}^{∗} + ⋯ + r_{n}^{∗}.

Let S = (s_{1}, …, s_{n}) and T = (t_{1}, …, t_{n}) be two non-negative integral vectors. For convenience, we write

|T − S| := ∑_{i=1}^{n} max{0, t_{i} − s_{i}}.

(Notice that |T − S| is, in general, not equal to |S − T |.) In particular,

|T | := ∑_{i=1}^{n} t_{i}.

The vector S is said to be majorized by T, written S ≺ T, if

∑_{i=1}^{j} s_{i} ≤ ∑_{i=1}^{j} t_{i} for all j = 1, 2, …, n

with equality when j = n. We emphasis here that we do not assume the monotone properties of S and T in our definition of majorization throughout the paper. This generalizes the traditional definition of majorization in the literature. To avoid any ambiguity, we will specify in each of the lemmas and theorems which vectors are assumed to be monotone.

The set A(R, S) was the subject of intensive study during the late 1950s and early 1960s by many researchers. (See [1] for a survey paper.) For example, the following lemma of Gale-Ryser stated the conditions for the existence of a matrix in A(R, S). It was originally stated under the condition that both R and S were monotone. It is clear that the monotone property of R can be dropped from the lemma since any reordering of rows in a matrix in A(R, S) does not affect the vectors R^{∗} and S.

Lemma 1 (Gale [3], Ryser [4]) Suppose S is monotone. Then A(R, S) ≠ ∅ if and only if S ≺ R^{∗} and r_{i} ≤ n for all i = 1, …, m.

If A(R, S) ≠ ∅, then each A ∈ A(R, S) can be obtained from Ā by shifting 1’s in each row. Throughout the paper, by shifting 1’s we always means shifting 1’s to the right. If S is monotone, Brualdi and Sanderson [2] defined the discrepancy d(A) of A to be the number of positions in which Ā has a 1 and A has a 0. It equals the number of 1’s in Ā which have to be shifted to obtain A. We are interested in the discrepancy set {d(A) : A ∈ A(R, S)}. Let

d̃= d̃(R, S) = min{d(A) : A ∈ A(R, S)}

and

d̄= d̄(R, S) = max{d(A) : A ∈ A(R, S)}.

In 1957, Ryser [4] defined an interchange to be a transformation which replaces the 2 × 2 submatrix

[ \begin{matrix}1 & 0 \\ 0 & 1 \end{matrix} ]

of a matrix A of 0’s and 1’s with the 2 × 2 submatrix

[ \begin{matrix}0 & 1 \\ 1 & 0 \end{matrix} ] ,

or vice versa. Clearly an interchange (and hence any sequence of interchanges) does not alter the row and column sum vectors of a matrix, and therefore transforms a matrix in A(R, S) into another matrix in A(R, S). Ryser [4] proved the converse of the result by inductively showing that given A, B ∈ A(R, S) there is a sequence of interchanges which transforms A into B. In particular, if d(A) = d̃ and d(B) = d̄, then there is a sequence of interchanges which transforms A into B. Thus for each integer d with d̃≤ d ≤ d̄, there is a matrix in A(R, S) having discrepancy d, since an interchange can only change the discrepancy of a matrix by at most 1. Therefore

{d(A) : A ∈ A(R, S)} = {d : d̃≤ d ≤ d̄};

in other words, to determine the discrepancy set {d(A) : A ∈ A(R, S)}, it suffices to determine the minimum and maximum discrepancies among all matrices in A(R, S). Since d(A) is defined under the assumption that S is monotone, we assume that S is monotone throughout the rest of the paper.

In Section 2, we show that the minimum discrepancy of all matrices in A(R, S) is |R^{∗} − S|. On the other hand, the problem of finding an explicit formula for the maximum discrepancy turns out to be very difficult. We find an algorithm to compute the maximum discrepancy in Section 3.

2 Minimum Discrepancy

We prove in this section an explicit formula in terms of R and S for the minimum discrepancy of all matrices in A(R, S). We begin with the following lemma.

Lemma 2 Suppose S = (s_{1}, …, s_{n}) and T = (t_{1}, …, t_{n}) are monotone vectors such that S ≺ T. Then there exist k = |T − S| + 1 monotone vectors S_{i} = (s_{1}^{(i)}, …, s_{n}^{(i)}), 1 ≤ i ≤ k, such that

1. S = S_{1} ≺ S_{2} ≺ ⋯ ≺ S_{k} = T, and

2. |S_{i+1} − S_{i}| = 1 for all 1 ≤ i ≤ k − 1.

Proof. Set S_{1} = S and S_{k} = T. Lemma 2 is trivial if k ≤ 2. Now suppose k ≥ 3. Since S ≠ T, there exists a smallest index l_{0} satisfying s_{l_{0}} > t_{l_{0}}. If l_{0} ≤ n − 1, then either s_{l_{0}} > s_{l_{0}+1} or s_{l_{0}+1} = s_{l_{0}} > t_{l_{0}} ≥ t_{l_{0}+1}. Thus there exists a smallest index l_{1} satisfying s_{l_{1}} > t_{l_{1}}, and satisfying s_{l_{1}} > s_{l_{1}+1} if l_{1} ≤ n − 1. Thus l_{0} ≤ l_{1} and

s_{i} \{ \begin{matrix}> t_{i} & if l_{0} ≤ i ≤ l_{1}, \\ ≤ t_{i} & if i ≤ l_{0} − 1. \end{matrix}

Since S ≺ T, we have s_{1} ≤ t_{1} and l_{0} > 1. Let l_{2} be the smallest index i satisfying 1 ≤ i < l_{0} and s_{i} < t_{i}. (Such an i exists since S ≺ T and S ≠ T.) Since S ≺ T,

∑_{i=1}^{l_{2}} t_{i} = ∑_{i=1}^{l_{2}−1} t_{i} + t_{l_{2}} > ∑_{i=1}^{l_{2}−1} s_{i} + s_{l_{2}} = ∑_{i=1}^{l_{2}} s_{i}.

Let S_{2} be defined by

s_{j}^{(2)} = \{ \begin{matrix}s_{j} − 1 & if j = l_{1}, \\ s_{j} + 1 & if j = l_{2}, \\ s_{j} & otherwise. \end{matrix}

Thus, for all l such that l_{2} ≤ l ≤ l_{0} − 1,

∑_{i=1}^{l} t_{i} = ∑_{i=1}^{l_{2}} t_{i} + ∑_{i=l_{2}+1}^{l} t_{i} > ∑_{i=1}^{l_{2}} s_{i} + ∑_{i=l_{2}+1}^{l} s_{i} = ∑_{i=1}^{l} s_{i}  (1)

and, for all l such that l_{0} ≤ l ≤ l_{1} − 1,

∑_{i=1}^{l} t_{i} = ∑_{i=1}^{l_{1}} t_{i} − ∑_{i=l+1}^{l_{1}} t_{i} > ∑_{i=1}^{l_{1}} s_{i} − ∑_{i=l+1}^{l_{1}} s_{i} = ∑_{i=1}^{l} s_{i}.  (2)

Since S ≺ T, it follows from (1) and (2) that S_{2} ≺ T. By the choices of l_{1} and l_{2}, we have

s_{l_{1}}^{(2)} = s_{l_{1}} − 1 ≥ s_{l_{1}+1} = s_{l_{1}+1}^{(2)} if l_{1} + 1 ≤ n,

and

s_{l_{2}−1}^{(2)} = s_{l_{2}−1} = t_{l_{2}−1} ≥ t_{l_{2}} ≥ s_{l_{2}} + 1 = s_{l_{2}}^{(2)} if l_{2} − 1 ≥ 1.

Thus S_{2} is monotone. Also it can be checked that S_{1} ≺ S_{2}, |S_{2} − S_{1}| = 1 and |T − S_{2}| = k − 2. By replacing S_{2} with S, Lemma 2 follows by induction. □

Theorem 1 Suppose S_{1} and S_{2} are monotone vectors such that S_{1} ≺ S_{2}. If A ∈ A(R, S_{2}), then a matrix in A(R, S_{1}) can be obtained from A by shifting at most |S_{2} − S_{1}| 1′s in rows.

Proof. By Lemma 2, it may be supposed that |S_{2} − S_{1}| = 1. Since S_{1} ≺ S_{2}, there are l_{1}, l_{2} such that l_{2} < l_{1} and

s_{j}^{(2)} = \{ \begin{matrix}s_{j}^{(1)} − 1 & if j = l_{1}, \\ s_{j}^{(1)} + 1 & if j = l_{2}, \\ s_{j}^{(1)} & otherwise. \end{matrix}

Thus s_{l_{2}}^{(2)} = s_{l_{2}}^{(1)} + 1 ≥ s_{l_{1}}^{(1)} + 1 = s_{l_{1}}^{(2)} + 2; in other words, column l_{2} of A contains at least 2 more 1’s than column l_{1} of A. Thus a 1 can be shifted in a row from column l_{2} to column l_{1}, and so a matrix in A(R, S_{1}) is obtained. □

Corollary 1 Suppose S is monotone. If A(R, S) ≠ ∅, then

min_{A∈A(R,S)} d(A) = |R^{∗} − S|.

Proof. Since A(R, S) ≠ ∅, we have S ≺ R^{∗} by Lemma 1. Suppose that A ∈ A(R, S). Since columns i of Ā and A have r_{i}^{∗} and s_{i} 1’s, respectively, at least max{0, r_{i}^{∗} − s_{i}} 1’s in column i must be shifted in rows in order to obtain A from Ā. This implies d(A) ≥ ∑_{i} max{0, r_{i}^{∗} − s_{i}} = |R^{∗} − S|. On the other hand, by applying Theorem 1 in the case S_{1} = S and S_{2} = R^{∗}, a matrix in A(R, S) can be obtained from Ā ∈ A(R, R^{∗}) by shifting at most |R^{∗} − S| 1′s in rows; that is, min_{A∈A(R,S)} d(A) ≤ |R^{∗} − S|, from which Corollary 1 follows. □

3 Maximum Discrepancy

In this section, we find an algorithm to compute the maximum discrepancy of all matrices in A(R, S). We begin with the following lemma which will be used in Lemma 4. We comment here that Lemma 3, under the weaker condition that only S is monotone, is weaker than Theorem 1.

Lemma 3 Suppose S is monotone and A ∈ A(R, T). If S ≺ T, then A(R, S) ≠ ∅ and some matrix in A(R, S) can be obtained from A by shifting 1’s in rows.

Proof. We use induction on n, the number of components of S. If T is monotone, then the lemma follows from Theorem 1; in particular, the lemma holds for n = 2, since n = 2, S monotone and S ≺ T imply that T is monotone. We now assume that n ≥ 3 and T is not monotone, and proceed by induction on n. We define S′ = (s′_{1}, …, s′_{n}) to be a maximal monotone vector in the sense of majorization satisfying

S ≺ S′ ≺ T

By the choice of S′, there is an l, 1 ≤ l < n, such that ∑_{i=1}^{l} s′_{i} = ∑_{i=1}^{l} t_{i}. We can partition S′ and T such that S′ = (S′_{1}, S′_{2}) and T = (T_{1}, T_{2}), where S′_{1}, T_{1} are vectors with l components and S′_{2}, T_{2} are vectors with n − l components. It can be seen that S′_{1} ≺ T_{1} and S′_{2} ≺ T_{2} since ∑_{i=1}^{l} s′_{i} = ∑_{i=1}^{l} t_{i}. Also S′_{1} and S′_{2} are monotone since S′ = (S′_{1}, S′_{2}) is.

Now we consider the partition of A = [A_{1} A_{2}], where A_{1} and A_{2} are m × l and m × (n − l) matrices, respectively. Then A_{1} ∈ A(R_{1}, T_{1}) and A_{2} ∈ A(R_{2}, T_{2}) for some R_{1} and R_{2} satisfying R_{1} + R_{2} = R. By the induction hypothesis, some matrices B_{1} ∈ A(R_{1}, S′_{1}) and B_{2} ∈ A(R_{2}, S′_{2}) can be obtained by shifting 1’s in rows from A_{1} and A_{2}, respectively. Then the matrix [B_{1} B_{2}] ∈ A(R, S′) can be obtained from [A_{1} A_{2}] = A by shifting 1’s in rows. Since S ≺ S′ and S′ is monotone, by Theorem 1, some matrix in A(R, S) can be obtained by shifting 1’s in rows from [B_{1} B_{2}] and so from A. This completes the proof of the lemma. □

Suppose S is monotone. For each A ∈ A(R, S), we can partition A into two regions according to the shape of Ā; that is, region 1 consists of positions in {(i, j) : 1 ≤ i ≤ m, 1 ≤ j ≤ r_{i}}, while region 2 consists of positions in {(i, j) : 1 ≤ i ≤ m, r_{i} < j ≤ n}.

Suppose R^{(1)} = (r_{1}^{(1)}, …, r_{m}^{(1)}), R^{(2)} = (r_{1}^{(2)}, …, r_{m}^{(2)}) are two non-negative integral vectors such that r_{i}^{(1)} ≤ r_{i} and r_{i}^{(2)} ≤ n−r_{i} for all i, 1 ≤ i ≤ m. Define Ā(R^{(1)}, R^{(2)}) = (a_{ij}) to be the m × n matrix defined, for each i, by

a_{ij} = \{ \begin{matrix}1 & if 1 ≤ j ≤ r_{i}^{(1)} or r_{i} + 1 ≤ j ≤ r_{i} + r_{i}^{(2)}, \\ 0 & otherwise. \end{matrix}

In other words, Ā(R^{(1)}, R^{(2)}) is the matrix with row sum vectors R^{(i)} in region i, i = 1, 2, and with all 1’s in the leftmost possible positions. Let (R^{(1)}, R^{(2)})^{∗} denote the column sum vector of Ā(R^{(1)}, R^{(2)}). If R^{(1)} = O, a zero vector, and R^{(2)} = R, then Ā(R^{(1)}, R^{(2)}) is the matrix Ā(O, R), and (O, R)^{∗} is the column sum vector of Ā(O, R). Let

J = J (R, S) := {Ā(R^{(1)}, R^{(2)}) : R^{(1)} + R^{(2)} = R and S ≺ (R^{(1)}, R^{(2)})^{∗}}.

Lemma 4 Suppose S is monotone. Then

max_{A∈A(R,S)} d(A) = max_{Ā(R−T,T)∈J} |T |.

Proof. Let A ∈ A(R, S) with maximum d(A). Let B be the matrix obtained from A by moving all 1’s in rows to the leftmost possible positions within each of the two regions. Then the column sum vector of B majorizes S and so B ∈ J. Let B = Ā(R − T_{A}, T_{A}). Then d(A) = |T_{A}|. This implies that

max_{A∈A(R,S)} d(A) ≤ max_{Ā(R−T,T)∈J} |T |.

Now suppose that B = Ā(R − T, T) ∈ J has maximum |T | among all matrices in J. Since S ≺ (R − T, T)^{∗}, by Lemma 3, some matrix A ∈ A(R, S) can be obtained from B by shifting 1’s in rows. Since shifting 1’s in rows does not decrease the number of 1’s in region 2 (recall that shifting 1’s means shifting 1’s to the right), we have |T | ≤ d(A). Thus

max_{Ā(R−T,T)∈J} |T | ≤ max_{A∈A(R,S)} d(A),

from which Lemma 4 follows. □

For two vectors U = (u_{1}, …, u_{n}) and V = (v_{1}, …, v_{n}), we define U < V in the sense of lexicography; that is, there is some j such that u_{j} < v_{j} and u_{i} = v_{i} for all i < j. Similarly, we can define U ≤ V in the sense of lexicography; that is, either U = V or U < V holds.

Throughout the rest of the section, we select C := Ā(R − U, U) ∈ J with priority in the order: (1.) (O, U)^{∗} is lexically maximum, (2.) maximal (R − U, U)^{∗} in the sense of majorization. In other words, among all candidates Ā(R − U, U) with the property that (O, U)^{∗} is lexically maximum, we select C with maximal (R − U, U)^{∗} in the sense of majorization. We also select D := Ā(R − V, V) ∈ J with priority in the order: (1.) maximum |V |, (2.) (O, V)^{∗} is lexically maximum, (3.) maximal (R − V, V)^{∗} in the sense of majorization.

Now we focus on the structure of C and D. It is known that C, D can be obtained from Ā by shifting 1’s in rows. We may assume the following rule when shifting 1’s in rows to obtain C, D from Ā:

Shifting Rule: For each i, let (i, j_{i}) be the rightmost position having a 1 in row i in region 1, and let (i, k_{i}) be the leftmost position having a 0 in row i in region 2. If a shift takes place in row i, then the 1 at the (i, j_{i}) position is moved to the (i, k_{i}) position.

It is trivial that every matrix in J can be obtained from Ā by a sequence of 0-1 shifts satisfying the above Shifting Rule. For each position (i, j) in region 2 (thus j ≥ r_{i} + 1), we assign to it a weight w(i, j) as follow:

w(i, j) = \{ \begin{matrix}2j − 2r_{i} − 1 & if r_{i} + 1 ≤ j ≤ 2r_{i}, \\ ∞ & if 2r_{i} + 1 ≤ j ≤ n, \end{matrix}

Indeed, it can be checked that w(i, j) is the distance that a 1 has to be moved from region 1 to the position (i, j) in region 2 by the Shifting Rule. (In the case that 2r_{i} + 1 ≤ j ≤ n, the (i, j) position must have a 0 for any matrix in J. Thus it is natural to define the distance that a 1 has to be moved from region 1 to the position (i, j) as infinity.)

Lemma 5 Both matrices C and D satisfy the following: For each fixed j, the 1’s in column j that lie in region 2 appear in the positions (i, j) with w(i, j) as small as possible.

Proof. We only prove the lemma for C = (c_{ij}). A similar proof works for D. Suppose the lemma fails for C. Then there are i, j, k such that (i, j), (k, j) are in region 2, and c_{ij} = 1, c_{kj} = 0 and w(i, j) > w(k, j). By the Shifting Rule, the positions (i, j − w(i, j)) and (k, j − w(k, j)) have a 0 and a 1, respectively. Let C_{1} be obtained from C by making 0-1 switches at the four positions (i, j), (i, j −w(i, j)), (k, j), (k, j − w(k, j)). Then the column sum vector of C_{1} majorizes (R − U, U)^{∗} since j − w(i, j) < j − w(k, j). Let C_{2} = Ā(R − U_{1}, U_{1}) be obtained from C_{1} by moving all 1’s in rows within each of the two regions to the leftmost possible positions. Then |U| = |U_{1}| and (O, U)^{∗} ≤ (O, U_{1})^{∗}. Also (R − U, U)^{∗} ≺ (R − U_{1}, U_{1})^{∗} since (R − U_{1}, U_{1})^{∗} majorizes the column sum vector of C_{1}. Thus C ≠ C_{2} ∈ J. This contradicts the choice of C.

□

Theorem 2

|U| = |V |.

Proof. Let D = (d_{ij}). By the choice of D, we have |U| ≤ |V |. Now suppose |U| < |V |. Let (O, U)^{∗} = (u_{1}, …, u_{n}) and (O, V)^{∗} = (v_{1}, …, v_{n}). Since (O, U)^{∗} is lexically maximum, there is a j such that u_{j} > v_{j} and u_{i} = v_{i} for all i ≤ j − 1. Let

P := {positions (i, k) in region 2 : d_{ik} = 1 and k ≤ j}.

By Lemma 5, we may properly choose the matrix C such that c_{ik} = 1 whenever (i, k) ∈ P. Since u_{j} > v_{j}, there is a position (i, j) in region 2 such that c_{ij} = 1 and d_{ij} = 0. Let k = j − w(i, j). Then c_{ik} = 0 and d_{ik} = 1 by the Shifting Rule. Let (R − U, U)^{∗} = (c_{1}^{∗}, …, c_{n}^{∗}), (R − V, V)^{∗} = (d_{1}^{∗}, …, d_{n}^{∗}).

Claim 1: There is some l, k ≤ l < j, such that

∑_{t=1}^{l} s_{t} = ∑_{t=1}^{l} d_{t}^{∗}.

Proof of Claim 1: Otherwise ∑_{t=1}^{l} s_{t} < ∑_{t=1}^{l} d_{t}^{∗} for all l, k ≤ l < j, since S ≺ (R − V, V)^{∗}. Let D_{1} be obtained from D by making a 0-1 switch at positions (i, j) and (i, k). Then the number of 1’s that lie in region 2 in D_{1} is |V | + 1. Since S ≺ (R − V, V)^{∗}, it can be checked that S is majorized by the column sum vector of D_{1}. By moving all 1’s in rows within each of the two regions to the leftmost possible positions in D_{1}, we can obtain a matrix in J contradicting the choice of D with maximum |V |. Thus Claim 1 holds.

Now we may choose l to be the smallest index satisfying Claim 1.

Claim 2: There exists in region 2 a position (i′, j′) ∉ P such that d_{i′j′} = 1 and d_{i′k′} = 0 with k′ = j′ − w(i′, j′) ≤ l.

Proof of Claim 2: Otherwise no 1 with column index less than or equal to l is shifted in a row to a position outside of P in D. But in C, the 1 in the (i, k) position is shifted in row i to the (i, j) position which is outside of P. Thus ∑_{t=1}^{l} s_{t} = ∑_{t=1}^{l} d_{t}^{∗} > ∑_{t=1}^{l} c_{t}^{∗}, which contradicts S ≺ (R − U, U)^{∗}. Thus Claim 2 holds.

Since d_{i′j′} = 1, by the definition of P, we have j′ > j. Let D_{2} be obtained from D by making 0-1 switches at positions (i, j), (i, k), (i′, j′) and (i′, k′). Let D_{3} = Ā(R − V_{3}, V_{3}) be obtained from D_{2} by moving all 1’s in rows within each of the two regions to the leftmost possible positions. Then |V | = |V_{3}| and (O, V)^{∗} < (O, V_{3})^{∗}.

Case 1: k′ ≤ k. Then it is easy to see that (R − V, V)^{∗} ≺ (R − V_{3}, V_{3})^{∗} since j′ > j. Thus S ≺ (R − V_{3}, V_{3})^{∗} since S ≺ (R − V, V)^{∗}.

Case 2: k < k′ ≤ l. Let (R − V_{3}, V_{3})^{∗} = (e_{1}^{∗}, …, e_{n}^{∗}). Since l is the smallest index satisfying Claim 1,

∑_{t=1}^{l′} s_{t} ≤ ∑_{t=1}^{l′} d_{t}^{∗} − 1 ≤ ∑_{t=1}^{l′} e_{t}^{∗}

for all l′, k ≤ l′ < l. Then it can be verified that S ≺ (R − V_{3}, V_{3})^{∗} since j′ > j.

Since S ≺ (R − V_{3}, V_{3})^{∗} is always true in both cases above, we have D_{3} ∈ J. This contradicts the choice of D since |V | = |V_{3}| and (O, V)^{∗} ≺ (O, V_{3})^{∗}. This completes the proof of |U| ≥ |V |. Therefore |U| = |V |. □

By Lemma 4 and Theorem 2, we have the following Corollary.

Corollary 2 Suppose S is monotone. Then

max_{A∈A(R,S)} d(A) = |U|.

Since (O, U)^{∗} is lexically maximum, we can use the following greedy algorithm to construct a C = Ā(R − U, U). By Corollary 2, this yields an algorithm to compute max_{A∈A(R,S)} d(A).

Algorithm to construct a matrix C = Ā(R − U, U) ∈ A(R, S) with d(C) = d̄(R, S):

Begin with the matrix Ā with row sum vector R.

1. Let j be the smallest index i such that column i has a non-empty intersection with region 2.

2. Apply the Shifting Rule to shift a 1 to the position (i, j) in region 2 with the smallest weight w(i, j) among all positions in column j that lie in region 2 and contain a 0, under the condition that the column sum vector of the ending matrix majorizes S. If more than one shift is possible, arbitrarily choose one.

3. Repeat Step 2, shifting to the positions in column j in region 2 as many 1’s as possible. If no more shifts are possible, then go to Step 4.

4. j := j + 1.

5. If j ≤ n, then go back to Step 2; otherwise, output the current matrix.

4 Concluding Discussion

We may generalize the minimum and maximum discrepancy problems by allowing regions 1 and 2 to have a general shape not necessarily determined by the shape of Ā. For example, if we only assume that regions 1 and 2 satisfy the following:

1. Region i is connected for each i = 1, 2, and

2. The intersection of each row of A with region i is connected for each i = 1, 2,

and define, for each A ∈ A(R, S), the discrepancy d(A) of A to be the number of 1’s of A in region 2, then we have the following

Generalized Problems: Suppose S is monotone. For any two regions satisfying the above conditions, find

min_{A∈A(R,S)} d(A) and max_{A∈A(R,S)} d(A).

The above two generalized problems are equally difficult since a matrix A ∈ A(R, S) having the maximum number of 1’s in region 2 clearly has the minimum number of 1’s in region 1. By slightly modifying our techniques in Section 3, we can give similar algorithms to compute the minimum and maximum discrepancies. However, we believe that to give explicit formulas for the minimum and maximum discrepancies is almost hopeless for the general case.

Acknowledgment. We are grateful to a referee for pointing out some small mistakes in our original manuscript and for providing us with a number of helpful suggestions leading to a clearer presentation of the paper.

References

[1] R. A. Brualdi, Matrices of zeros and ones with fixed row and column sum vectors, Linear Algebra Appli. 33:159-231 (1980).

[2] R. A. Brualdi and J. G. Sanderson, Nested species subsets, gaps, and discrepancy, Oecologia, to appear.

[3] D. Gale, A theorem on flows in networks, Pacific J. Math. 7:1073-1082 (1957).

[4] H. J. Ryser, Combinatorial properties of matrices of zeros and ones, Canada. J. Math. 9:371-377 (1957).