Matrices with Prescribed Row and Columns Sums-1

MATRICES WITH PRESCRIBED ROW AND COLUMN SUMS 2010 Abstract. This is a survey of the recent progress and open questions on the structure of the sets of 0-1 and non-negative integer matrices with prescribed row and column sums. We discuss cardinality estimates, the structure of a random matrix from the set, discrete versions of the Brunn-Minkowski inequality and the statistical dependence between row and column sums. 1. Introduction Let R = (r1 , . . . , rm ) and C = (c1 , . . . , cn ) be positive integer vectors such that (1.1) r1 + . . . + rm = c1 + . . . + cn = N. We consider the set A0 (R, C) of all m × n matrices D = (dij ) with 0-1 entries, row sums R and column sums C: A0 (R, C) = ( D = (dij ) : n X j=1 m X dij = ri for i = 1, . . . , m dij = cj for j = 1, . . . , n i=1 ) dij ∈ {0, 1} . 1 We also consider the set A+ (R, C) of non-negative integer m × n matrices with row sums R and column sums C: ( n X dij = ri for i = 1, . . . , m A+ (R, C) = D = (dij ) : j=1 m X dij = cj for j = 1, . . . , n i=1 ) dij ∈ Z+ . Vectors R and C are called margins of matrices from A0 (R, C) and A+ (R, C). We reserve notation N for the sums of the coordinates of R and C in (1.1) and write |R| = |C| = N . While the set A+ (R, C) is non-empty as long as the balance condition (1.1) is satisfied, a result of Gale and Ryser (see, for example, Section 6.2 of [BR91]) provides a necessary and sufficient criterion for set A0 (R, C) to be non-empty. Let us assume that m ≥ c1 ≥ c2 ≥ . . . ≥ cn ≥ 0 and that n ≥ ri ≥ 0 for i = 1, . . . , n. Set A0 (R, C) is not empty if and only if (1.1) holds and m X i=1 min {ri , k} ≥ k X cj for k = 1, . . . , n. j=1 Assuming that A0 (R, C) 6= ∅, we are interested in the following questions: • What is the cardinality |A0 (R, C)| of A0 (R, C) and the cardinality |A+ (R, C)| of A+ (R, C)? • Let us us consider A0 (R, C) and A+ (R, C) as finite probability spaces with the uniform measure. What a random matrix D ∈ A0 (R, C) and a random matrix D ∈ A+ (R, C) are likely to look like? The paper is organized as follows. In Section 2 we estimate of |A0 (R, C)| within an (mn)O(m+n) factor and in Section 3 we estimate |A+ (R, C)| within an N O(m+n) factor. In all but very sparse cases this way we obtain asymptotically exact estimates of ln |A0 (R, C)| and ln |A+ (R, C)| respectively. The estimate of Section 2 is based on a representation of |A0 (R, C)| as the permanent of a certain mn × mn matrix of 0’s and 1’s, while the estimate of Section 3 is based on a representation of |A+ (R, C)| as the expectation of the 2 permanent of a certain N × N random matrix with exponentially distributed entries. In the proofs, the crucial role is played by the van der Waerden inequality for permanents of doubly stochastic matrices. The cardinality estimates are obtained as solutions to simple convex optimization problems and hence are efficiently computable, although they cannot be expressed by a “closed formula” in the margins (R, C). Our method is sufficiently robust as the same approach can be applied to estimate the cardinality of the set of matrices with prescribed margins and with 0’s in prescribed positions. In Sections 4 and 5 we discuss some consequences of the formulas obtained in Sections 2 and 3. In particular, in Section 4, we show that the numbers |A0 (R, C)| and |A+ (R, C)| are both approximately log-concave as functions of the margins (R, C). We note an open question whether these numbers are genuinely log-concave and give some, admittedly weak, evidence that it may be the case. In Section 5, we discuss statistical dependence between row and column sums. Namely, we consider finite probability spaces of m × n non-negative integer or 0-1 matrices with the total sum N of entries and two events in those spaces: event R consisting of the matrices with row sums R and event C consisting of the matrices with column sums C. It turns out that 0-1 and non-negative integer matrices exhibit opposite types of behavior. Assuming that the margins R and C are sufficiently far away from sparse and uniform, we show that for 0-1 matrices the events R and C repel each other (events R and C are negatively correlated) while for non-negative integer matrices they attract each other (the events are positively correlated). In Section 6, we discuss what random matrices D ∈ A0 (R, C) and D ∈ A+ (R, C) look like. We show that in many respects, a random matrix D ∈ A0 (R, C) behaves like an m×n matrix X of independent Bernoulli random variables such that E X = Z0 where Z0 is a certain matrix, called the maximum entropy matrix, with row sums R, column sums C and entries between 0 and 1. It turns out that Z0 is the solution to an optimization problem, which is convex dual to the optimization problem of Section 2 used to estimate |A0 (R, C)|. On the other hand, a random matrix D ∈ A+ (R, C) in many respects behaves like an m × n matrix X of independent geometric random variables such that E X = Z+ where Z+ is a certain matrix, also called the maximum entropy matrix, with row sums R, column sums C and nonnegative entries. It turns out that Z+ is the solution to an optimization problem which is convex dual to the optimization problem of Section 3 used to estimate |A+ (R, C)|. It follows that in various natural metrics matrices D ∈ A0 (R, C) concentrate about Z0 while matrices D ∈ A+ (R, C) concentrate about Z+ . We note some open questions on whether individual entries of random D ∈ A0 (R, C) and random D ∈ A+ (R, C) are asymptotically Bernoulli, respectively geometric, with the expectations read off from Z0 and Z+ . In Section 7, we discuss asymptotically exact formulas for |A0 (R, C)| and |A+ (R, C)|. Those formulas are established under essentially more restrictive conditions than cruder estimates of Sections 2 and 3. We assume that the entries of the maximum entropy matrices Z0 and Z+ are within a constant factor, fixed in 3 advance, of each other. Recall that matrices Z0 and Z+ characterize the typical behavior of random matrices D ∈ A0 (R, C) and D ∈ A+ (R, C) respectively. In the case of 0-1 matrices our condition basically means that the margins (R, C) lie sufficiently deep inside the region defined by the Gale-Ryser inequalities. As the margins approach the boundary, the number |A0 (R, C)| gets volatile and hence cannot be expressed by an analytic formula like the one described in Section 7. The situation with non-negative integer matrices is less clear. It is plausible that the number |A+ (R, C)| experiences some volatility when some entries of Z+ become abnormally large, but we don’t have a proof of that happenning. In Section 8, we mention some possible ramifications, such as enumeration of higher-order tensors and graphs with given degree sequences. The paper is a survey and although we don’t provide complete proofs, we often sketch main ideas of our approach. 2. The logarithmic asymptotic for the number of 0-1 matrices The following result is proven in [Ba10a]. (2.1) Theorem. Given positive integer vectors R = (r1 , . . . , rm ) and C = (c1 , . . . , cn ) , let us define the function m Y F0 (x, y) = i=1 for   ! n Y Y −c yj j   (1 + xi yj ) xi−ri  i,j j=1 x = (x1 , . . . , xm ) and y = (y1 , . . . , yn ) and let α0 (R, C) = inf x1 ,... ,xm >0 y1 ,... ,yn >0 F0 (x, y). Then the number A0 (R, C) of m×n zero-one matrices with row sums R and column sums C satisfies α0 (R, C) ≥ |A0 (R, C)| ≥ (mn)! (mn)mn m n−r Y (n − ri ) i i=1 (n − ri )! Using Stirling’s formula,    √ s! 1 −s 2πse , = 1 + O ss s 4 !  c n Y cj j   α0 (R, C). c ! j j=1 one can notice that the ratio between the upper and lower bounds is (mn)O(m+n) . Indeed, the “e−s ” terms cancel each other out, since  ! n m Y Y ecj  = 1. en−ri  e−mn j=1 i=1 Thus, for sufficiently dense 0-1 matrices, where we have |A0 (R, C)| = 2Ω(mn) , we have an asymptotically exact formula ln |A0 (R, C)| ≈ ln α0 (R, C) as m, n −→ +∞. (2.2) A convex version of the optimization problem. Let us substitute xi = esi for i = 1, . . . , m and yj = etj for j = 1, . . . , n in F0 (x, y). Denoting (2.2.1) G0 (s, t) = − for m X i=1 ri s i − n X tj cj + ln 1 + esi +tj i,j j=1 s = (s1 , . . . , sm ) X and t = (t1 , . . . , tn ) ,
we obtain ln α0 (R, C) = s ,... inf,s G0 (s, t). 1 m t1 ,... ,tn We observe that G0 (s, t) is a convex function on Rm+n . In particular, one can compute the infimum of G0 efficiently by using interior point methods, see, for example, [NN94]. (2.3) Sketch of proof of Theorem 2.1. The upper bound for |A0 (R, C)| is immediate: it follows from the expansion Y X (1 + xi yj ) = |A0 (R, C)|xR yC , ij where R,C xR = xr11 · · · xrmm and yC = y1c1 · · · yncn for R = (r1 , . . . , rm ) and C = (c1 , . . . , cn ) and the sum is taken over all pairs of non-negative integer vectors R = (r1 , . . . , rm ) and C = (c1 , . . . , cn ) such that r1 + . . . + rm = c1 + . . . + cn ≤ mn. To prove the lower bound, we express |A0 (R, C)| as the permanent of an mn×mn matrix. Recall that the permanent of a k × k matrix B = (bij ) is defined by per B = k X Y σ∈Sk i=1 5 biσ(i) , where the sum is taken over the symmetric group Sk of all permutations σ of the set {1, . . . , k}, see, for example, Chapter 11 of [LW01]. One can show, see [Bar10a] for details, that  ! n m Y Y 1  1  per B, (2.3.1) |A0 (R, C)| = (n − ri )! c ! j=1 j i=1 where B is the mn × mn matrix of the following structure: the rows of B are split into distinct m + n blocks, the m blocks of type I having n − r1 , . . . , n − rm rows respectively and n blocks of type II having c1 , . . . , cn rows respectively; the columns of B are split into m distinct blocks of n columns each; for i = 1, . . . , m, the entry of B that lies in a row from the i-th block of rows of type I and a column from the i-th block of columns is equal to 1; for i = 1, . . . , m and j = 1, . . . , n, the entry of B that lies in a row from the j-th block of rows of type II and the j-th column from the i-th block of columns is equal to 1; all other entries of B are 0. Suppose that the infimum of function G0 (s, t) defined by (2.2.1) is attained at a particular point s = (s1 , . . . , sm ) and t = (t1 , . . . , tn ) (the case when the infimum is not attained is handled by an approximation argument). Let xi = exp {si } for i = 1, . . . , m and yj = exp {tj } for j = 1, . . . , n. Setting the gradient of G0 (s, t) to 0, we obtain (2.3.2) n X j=1 m X i=1 xi y j = ri 1 + xi y j for i = 1, . . . , m xi y j = cj 1 + xi y j for j = 1, . . . , n. Let us consider a matrix B ′ obtained from matrix B as follows: for i = 1, . . . , m we multiply every row of B in the i-th block of type I by 1 ; xi (n − ri ) for j = 1, . . . , n, we multiply every row of B in the j-th block of type II by yj ; cj 6 for i = 1, . . . , m and j = 1, . . . , n we multiply the j-th column in the i-th block of columns of B by xi . 1 + xi y j Then per B = m Y i=1 n−ri xi−ri (n − ri ) !  n Y j=1   Y −c c yj j cj j   (1 + xi yj ) per B ′ . ij On the other hand, equations (2.3.2) imply that the row and column sums of B ′ are equal to 1, that is, B ′ is doubly stochastic. Applying the van der Waerden bound for permanents of doubly stochastic matrices, see, for example, Chapter 12 of [LW01], we conclude that (mn)! per B ′ ≥ , (mn)mn which, together with (2.3.1) completes the proof.  One can prove a version of Theorem 2.1 for 0-1 matrices with prescribed row and column sums and prescribed zeros in some positions. 3. The logarithmic asymptotics for the number of non-negative integer matrices The following result is proven in [Ba09]. (3.1) Theorem. Let R = (r1 , . . . , rm ) and C = (c1 , . . . , cn ) be positive integer vectors such that r1 + . . . + rm = c1 + . . . + cn = N . Let us define a function   ! n m Y Y −c Y 1  yj j   xi−ri  F+ (x, y) = 1 − x y i j ij j=1 i=1 for x = (x1 , . . . , xm ) and y = (y1 , . . . , yn ) . Then F+ (x, y) attains its minimum α+ (R, C) = min 0 0 is an absolute constant. 7 For sufficiently dense matrices, where min ri = Ω(n) and i=1,... ,m min cj = Ω(m) j=1,... ,n we have |A+ (R, C)| = (N/mn)Ω(mn) and hence we obtain an asymptotically exact formula ln |A+ (R, C)| ≈ ln α+ (R, C) as m, n −→ +∞. (3.2) A convex version of the optimization problem. Let us substitute xi = e−si for i = 1, . . . , m and yj = e−tj for j = 1, . . . , n in F+ (x, y). Denoting G+ (s, t) = (3.2.1) m X ri s i + i=1 for n X j=1 tj cj − s = (s1 , . . . , sm ) and ln α+ (R, C) = min X i,j ln 1 − e−si −tj t = (t1 , . . . , tn ) ,
we obtain s1 ,... ,sm >0 t1 ,...tn >0 G+ (s, t). We observe that G+ (s, t) is a convex function on Rm+n . In particular, one can compute the minimum of G+ efficiently by using interior point methods [NN94]. (3.3) Sketch of proof of Theorem 3.1. The upper bound for |A+ (R, C)| follows immediately from the expansion Y ij where X 1 = |A+ (R, C)|xR yC 1 − xi y j for 0 < x1 , . . . , xm , y1 , . . . , yn < 1 R,C xR = xr11 · · · xrmm and yC = y1c1 · · · yncn for R = (r1 , . . . , rm ) and C = (c1 , . . . , cn ) and the sum is taken over all pairs of non-negative integer vectors R = (r1 , . . . , rm ) and C = (c1 , . . . , cn ) such that r1 + . . . + rm = c1 + . . . + cn . To prove the lower bound, we express |A+ (R, C)| as the integral of the permanent of an N × N matrix with variable entries. For an m × n matrix Z = (zij ) we define the N × N matrix B(Z) as follows: the rows of B(Z) are split into m distinct blocks of sizes r1 , . . . , rm respectively; the columns of B(Z) are split into n distinct blocks of sizes c1 , . . . , cn respectively; 8 for i = 1, . . . , m and j = 1, . . . , n, the entry of B(Z) that lies in a row from the i-th block of rows and in a column from the j-th block of columns is zij . Then there is a combinatorial identity  ! n m Y Y cj ! ri !  per B(Z) = j=1 i=1 X dij Y zij D∈A+ (R,C) ij D=(dij ) dij ! , cf. [Be74], which implies that |A+ (R, C)| = m Y 1 ri ! i=1    ! n  X  Y 1 Z   per B(Z) exp − zij dZ.   cj ! Rmn + ij j=1 Here the integral is taken over the set Rmn of m × n matrices Z with positive + entries. Let ∆mn−1 ⊂ Rmn be the standard (mn − 1)-dimensional simplex defined + by the equation X zij = 1. ij Since per B(Z) is a homogeneous polynomial in Z of degree N , we have  ! n Z m Y Y 1  (N + mn − 1)! 1  √ per B(Z) dZ, (3.3.1) |A+ (R, C)| = mn r ! c ! i j ∆ mn−1 j=1 i=1 where dZ is the Lebesgue measure on ∆mn−1 induced from Rmn . Let s = (s1 , . . . , sm ) and t = (t1 , . . . , tn ) be the minimum point of function G+ (s, t) defined by (3.2.1). Let xi = exp {si } for i = 1, . . . , m and yj = exp {tj } for j = 1, . . . , m. Setting the gradient of G+ (s, t) to 0, we obtain n X j=1 m X (3.3.2) i=1 xi y j = ri 1 − xi y j for i = 1, . . . , m xi y j = cj 1 − xi y j for j = 1, . . . , n. Let us consider the affine subspace L ⊂ Rmn of m × n matrices Z = (zij ) defined by the system of equations (3.3.3) n X j=1 m X i=1 xi yj zij = ri N + mn for i = 1, . . . , m and xi yj zij = cj N + mn for j = 1, . . . , n. 9 We note that dim L = (m − 1)(n − 1). Suppose that Z ∈ ∆mn−1 ∩L and consider the corresponding matrix B(Z). If we √ multiply every row in the i-th block√of rows by xi N + mn/ri and every column in the j-th block of columns by yj N + mn/cj , by (3.3.3) we obtain a doubly stochastic matrix B ′ (Z) for which we have per B ′ (Z) ≥ N !/N N by the van der Waerden inequality. Summarizing,  ! n m Y Y N! c cj j  per B(Z) ≥ N r ri  N (N + mn)N i=1 i j=1   (3.3.4) ! n m Y Y −c −ri  for all Z ∈ ∆mn−1 ∩ L. yj j  × xi i=1 j=1 It remains to show that the intersection ∆mn−1 ∩ L is sufficiently large, so that the contribution of a neighborhood of the intersection to the integral (3.3.1) is sufficiently large. It follows by (3.3.2)–(3.3.3) that ∆mn−1 ∩ L contains matrix Z = (zij ) where 1 zij = for all i, j. (N + mn) (1 − xi yj ) In [Ba09], we prove a geometric lemma which states that if ∆d−1 ⊂ Rd+ is the standard (d − 1)-dimensional simplex that is the intersection of the affine hyperplane H defined by the equation x1 +. . .+xd = 1 and the positive orthant x1 > 0, . . . , xd > 0 and if L ⊂ H is an affine subspace of codimension k in H such that L contains a point a ∈ ∆d−1 , a = (α1 , . . . , αd ), then for the volume of the intersection ∆d−1 ∩ L we have the lower bound γ d− 1 d 2 α 1 . . . αd , vold−k−1 (∆d−1 ∩ L) ≥ d!ωk where π k/2 ωk = Γ(k/2 + 1) is the volume of the k-dimensional unit ball and γ > 0 is an absolute constant. Applying this estimate in our situation, we conclude that Y emn 1 1 , volmn−k (∆mn−1 ∩ L) ≥ mn O(m+n) (N + mn) 1 − xi y j (mn) ij where k = m + nP− 1 or k = m + n depending whether or not L lies in the affine hyperplane ij zij = 1. This allows us to obtain a similar bound for the volume of a small neighborhood of the intersection ∆mn−1 ∩ L. Because per B(Z) is a homogeneous polynomial in Z of degree N , inequality (3.3.4) holds in the ǫneighborhood of the intersection ∆mn−1 ∩ L for ǫ = N −O(m+n) up to an N O(m+n) factor. Using it together with (3.3.1), we complete the proof of Theorem 3.1.  One can prove a version of Theorem 3.1 for non-negative integer matrices with prescribed row and column sums and with prescribed zeros in some positions. 10 4. Discrete Brunn - Minkowski inequalities Theorems 2.1 and 3.1 allow us to establish approximate log-concavity of the numbers A0 (R, C) and A+ (R, C). For a non-negative integer vector B = (b1 , . . . , bp ), we denote |B| = p X bi . i=1 (4.1) Theorem. Let R1 , . . . , Rp be positive integer m-vectors and let C1 , . . . , Cp be positive integer n-vectors such that |R1 | = |C1 |, . . . , |Rp | = |Cp |. Let β1 , . . . , βp ≥ 0 be real numbers such that β1 + . . . + βp = 1 and such that R = β1 R1 + . . . + βp Rp is a positive integer m-vector and C = β1 C1 + . . . + βp Cp is a positive integer n-vector. Let N = |R| = |C|. Then for some absolute constant γ > 0 we have (1) p Y β γ(m+n) |A0 (Rk , Ck )| k (mn) |A0 (R, C)| ≥ k=1 and (2) N γ(m+n) |A+ (R, C)| ≥ p Y k=1 βk |A+ (Rk , Ck )| . Proof. Let us denote function F0 of Theorem 2.1 for the pair (Rk , Ck ) by Fk and for the pair (R, C) just by F . Then (4.1.1) F (x, y) = p Y Fkβk (x, y) k=1 and hence α0 (R, C) ≥ p Y (α0 (Rk , Ck )) βk . k=1 Part (1) now follows by Theorem 2.1. Similarly, we obtain (4.1.1) if we denote function F+ of Theorem 3.1 for the pair (Rk , Ck ) by Fk and for the pair (R, C) just by F . Hence α+ (R, C) ≥ p Y (α+ (Rk , Ck )) βk . k=1 Part (2) now follows by Theorem 3.1.  11 Teorem 2.1 implies a more precise estimate  ! n p m mn Y Y Y (mn) cj !  (n − ri )! β  |A0 (R, C)| ≥ |A0 (Rk , Ck )| k , cj n−ri (mn)! c (n − ri ) j=1 j i=1 k=1 where R = (r1 , . . . , rm ) and C = (c1 , . . . , cn ). In [Ba07] a more precise estimate   p m n  N Y Y Y ri ! cj !  N β |A+ (R, C)| ≥ |A+ (Rk , Ck )| k min cj ri ,  N! ri cj  i=1 j=1 k=1 is proven under the additional assumption that |Rk | = |Ck | = N for k = 1, . . . , p. Theorem 4.1 raises a natural question whether stronger inequalities hold. (4.2) Brunn-Minkowski inequalities. (4.2.1) Question. Is it true that under the conditions of Theorem 4.1 we have |A0 (R, C)| ≥ p Y k=1 β |A0 (Rk , Ck )| k ? (4.2.2) Question. Is it true that under the conditions of Theorem 4.1 we have |A+ (R, C)| ≥ p Y k=1 β |A+ (Rk , Ck )| k ? Should they hold, inequalities of (4.2.1) and (4.2.2) would be natural examples of discrete Brunn-Minkowski inequalities, see [Ga02] for a survey. Some known simpler inequalities are consistent with the inequalities of (4.2.1)– (4.2.2). Let X = (x1 , . . . , xp ) and Y = (y1 , . . . , yp ) be non-negative integer vectors such that x1 ≥ x2 ≥ . . . ≥ xp and y1 ≥ y2 ≥ . . . ≥ yp . We say that X dominates Y if k X i=1 xi ≥ k X i=1 yi for k = 1, . . . , p − 1 and p X i=1 xi = p X yi . i=1 Equivalently, X dominates Y if Y is a convex combination of vectors obtained from X by permutations of coordinates. One can show that (4.2.3) |A0 (R, C)| ≥ |A0 (R′ , C ′ )| and |A+ (R, C)| ≥ |A+ (R′ , C ′ )| provided R′ dominates R and C ′ dominates C, see Chapter 16 of [LW01] and [Ba07]. Inequalities (4.2.3) are consistent with the inequalities of (4.2.1) and (4.2.2). 12 5. Dependence between row and column sums The following attractive “independence heuristic” for estimating |A0 (R, C)| and |A+ (R, C)| was discussed by Good [Go77] and by Good and Crook [GC76]. (5.1) The independence heuristic. Let us consider the set of all m×n matrices D = (dij ) with 0-1 entries and the total sum N of entries as a finite probability space with the uniform measure. Let us consider the event R0 consisting of the matrices with the row sums R = (r1 , . . . , rm ) and the event C0 consisting of the matrices with the column sums C = (c1 , . . . , cn ). Then  −1 Y m   n mn Pr (R0 ) = ri N and Pr (C0 ) = i=1  mn N −1 Y n   m . cj j=1 In addition, A0 (R, C) = R0 ∩ C0 . If we assume that events R0 and C0 are independent, we obtain the following independence estimate (5.1.1)  −1 Y n   m  Y m n mn I0 (R, C) = ri j=1 cj N i=1 for the number |A0 (R, C)| of 0-1 matrices with row sums R and column sums C. Similarly, let us consider the set of all m×n matrices D = (dij ) with non-negative integer entries and the total sum N of entries as a finite probability space with the uniform measure. Let us consider the event R+ consisting of the matrices with the row sums R = (r1 , . . . , rm ) and the event C+ consisting of the matrices with the column sums C = (c1 , . . . , cn ). Then  −1 Y  m  ri + n − 1 N + mn − 1 and Pr (R+ ) = n − 1 mn − 1 i=1  −1 Y  n  cj + m − 1 N + mn − 1 . Pr (C+ ) = m − 1 mn − 1 j=1 We have A+ (R, C) = R+ ∩ C+ . If we assume that events R+ and C+ are independent, we obtain the independence estimate (5.1.2)   n  −1 Y  m  ri + n − 1 Y cj + m − 1 N + mn − 1 . I+ (R, C) = m − 1 n − 1 mn − 1 j=1 i=1 13 Interestingly, the independence estimates I0 (R, C) and I+ (R, C) provide reasonable approximations to |A0 (R, C)| and |A+ (R, C)| respectively in the following two cases: in the case of equal margins, when r1 = . . . = rm = r and c1 = . . . = cn = c, see [C+08] and [C+07] in the sparse case, when max ri ≪ n i=1,... ,m and max cj ≪ m, j=1,... ,n see [G+06] and [GM08]. We will see in Section 5.4 that the independence estimates provide the correct logarithmic asymptotics in the case when all row sums are equal or all column sums are equal. However, if both row and column sums are sufficiently far away from being uniform and sparse, the independence estimates, generally speaking, provide poor approximations. Moreover, in the case of 0-1 matrices the independence estimate I0 (R, C) typically grossly overestimates |A0 (R, C)| while in the case of non-negative integer matrices the independence estimate I+ (R, C) typically grossly underestimates |A+ (R, C)|. In other words, for typical margins R and C the events R0 and C0 repel each other (the events are negatively correlated) while events R+ and C+ attract each other (the events are positively correlated). To see why this is the case, we write the estimates α0 (R, C) of Theorem 2.1 and α+ (R, C) of Theorem 3.1 in terms of entropy. The following result is proven in [Ba10a]. (5.2) Lemma. Let P0 (R, C) be the polytope of all m × n matrices X = (xij ) with row sums R, column sums C and such that 0 ≤ xij ≤ 1 for all i and j. Suppose that polytope P0 (R, C) has a non-empty interior, that is contains a matrix Y = (yij ) such that 0 < yij < 1 for all i and j. Let us define a function h : P0 (R, C) −→ R by X 1 1 h(X) = xij ln + (1 − xij ) ln for X ∈ P0 (R, C). xi,j 1 − xij i,j Then h is a strictly concave function on of P0 (R, C) and hence attains its maximum on P (R, C) at a unique matrix Z0 = (zij ), which we call the maximum entropy matrix. Moreover, (1) We have 0 < zij < 1 for all i and j; (2) The infimum α0 (R, C) of Theorem 2.1 is attained at some particular point (x, y); (3) We have α0 (R, C) = eh(Z0 ) . 14 Sketch of Proof. It is straightforward to check that h is strictly concave and that 1 − xij ∂ h(X) = ln . ∂xij xij In particular, the (right) derivative at xij = 0 is +∞, the (left) derivative at xij = 1 is −∞ and the derivative for 0 < xij < 1 is finite. Hence the maximum entropy matrix Z0 must have all entries strictly between 0 and 1, since otherwise we can increase the value of h by perturbing Z0 in the direction of a matrix Y from the interior of P0 (R, C). This proves Part (1). The Lagrange optimality conditions imply that ln 1 − zij = −λi − µj zij for all i, j and some numbers λ1 , . . . , λm and µ1 , . . . , µn . Hence (5.2.1) zij = eλi +µj 1 + eλi +µj for all i, j. In particular, (5.2.2) m X i=1 n X j=1 eλi +µj = cj 1 + eλi +µj for j = 1, . . . , n and eλi +µj = ri 1 + eλi +µj for i = 1, . . . , m. Equations (5.2.2) imply that point s = (λ1 , . . . , λm ) and t = (µ1 , . . . , µn ) is a critical point of function G0 (s, t) defined by (2.2.1) and hence the infimum α0 (R, C) of F0 (x, y) is attained at xi = eλi for i = 1, . . . , m and yj = eµj for j = 1, . . . , n. Hence Part (2) follows. Using (5.2.1) it is then straightforward to check that F0 (x, y) = eh(Z0 ) for the minimum point (x, y).  We note that h(x) = x ln 1 1 + (1 − x) ln x x for 0≤x≤1 is the entropy of the Bernoulli random variable with expectation x, see Section 6. The following result is proven in [Ba09]. (5.3) Lemma. Let P+ (R, C) be the polytope of all non-negative m × n matrices X = (xij ) with row sums R and column sums C. Let us define a function g : P+ (R, C) −→ R by X g(X) = (xij + 1) ln (1 + xij ) − xij ln xij for X ∈ P+ (R, C). i,j 15 Then g is a strictly concave function on P+ (R, C) and hence attains its maximum on P+ (R, C) at a unique matrix Z+ = (zij ), which we call the maximum entropy matrix. Moreover, (1) We have zij > 0 for all i, j and (2) For the minimum α+ (R, C) of Theorem 3.1, we have α+ (R, C) = eg(Z+ ) . Sketch of Proof. It is straightforward to check that g is strictly concave and that ∂ 1 + xij g(X) = ln ∂xij xij for all i, j. In particular, the (left) derivative is +∞ for xij = 0 and finite for every xij > 0. Since P+ (R, C) contains an interior point (for example, matrix Y = (yij ) with yij = ri cj /N ), arguing as in the proof of Lemma 5.2, we obtain Part (1). The Lagrange optimality conditions imply that ln 1 + zij = λi + µj zij for all i, j and some numbers λ1 , . . . , λm and µ1 , . . . , µn . Hence e−λi −µj zij = 1 − e−λi −µj (5.3.1) for all i, j. In particular, (5.3.2) n X i=m n X j=1 e−λi −µj = cj 1 + e−λi −µj for j = 1, . . . , n and e−λi −µj = ri 1 + e−λi −µj for i = 1, . . . , m. Equations (5.3.2) imply that the point s = (λ1 , . . . , λm ) and t = (µ1 , . . . , µn ) is a critical point of function G+ (s, t) defined by (3.2.1) and hence the minimum α+ (R, C) of F+ (x, y) is attained at xi = eλi for i = 1, . . . , m and yj = eµj for j = 1, . . . , n. Using (5.3.1), it is then straightforward to check that F+ (x, y) = eh(Z+ ) for the minimum point (x, y).  We note that g(x) = (x + 1) ln(x + 1) − x ln x for x≥0 is the entropy of the geometric random variable with expectation x, see Section 6. 16 (5.4) Estimates of the cardinality via entropy. Let H (p1 , . . . , pk ) = k X pi ln i=1 1 pi be the entropy function defined on k-tuples (probability distributions) p1 , . . . , pk such that p1 + . . . + pk = 1 and pi ≥ 0 for i = 1, . . . , k. Assuming that polytope P0 (R, C) of Lemma 5.2 has a non-empty interior, we can write   z  1 − zij ij ln α0 (R, C) =N H ; i, j + (mn − N )H ; i, j N mn − N − N ln N − (mn − N ) ln(mn − N ), where Z0 = (zij ) is the maximum entropy matrix. On the other hand, for the independence estimate (5.1.1), we have   r  n − ri i ln I0 (R, C) =N H ; i + (mn − N )H ; i N mn − N    c m − cj j ; j + (mn − N )H ; j + NH N mn − N
− N ln N − (mn − N ) ln(mn − N ) + O (m + n) ln(mn) . Using the inequality which relates the entropy of a distribution and the entropy of its margins, see, for example, [Kh57], we obtain  r  c  z i j ij ; i, j ≤ H ; i +H ; j (5.4.1) H N N N with the equality if and only if zij = ri cj N for all i, j and (5.4.2) H  1 − zij ; i, j mn − N  ≤ H     n − ri m − cj ; i +H ; j mn − N mn − N with the equality if and only if 1 − zij = (n − ri ) (m − cj ) mn − N for all i, j. Thus we have equalities in (5.4.1) and (5.4.2) if and only if (ri m − N ) (cj n − N ) = 0 17 for all i, j, that is, when all row sums are equal or all column sums are equal. In that case I0 (R, C) estimates |A0 (R, C)| within an (mn)O(m+n) factor. In all other cases, I0 (R, C) overestimates |A0 (R, C)| by as much as a 2Ω(mn) factor as long as the differences between the right hand sides and left hand sides of (5.4.1) and
(5.4.2) multiplied by N and (mn − N ) respectively overcome the O (m + n) ln(mn) error term, see also Section 5.5 for a particular family of examples. We handle non-negative integer matrices slightly differently. For the independence estimate (5.1.2) we obtain    cj + m ri + n ; i − (N + mn)H ; j ln I+ (R, C) = − (N + mn)H N + mn N + mn m n X X − ri ln ri − cj ln cj  i=1 j=1 + N ln N + (N + mn) ln(N + mn) + O (m + n) ln N On the other hand, by Lemma 5.3 we have
ln α+ (R, C) = g (Z+ ) ≥ g(Y ), where Z+ is the maximum entropy matrix and Y = (yij ) is the matrix defined by yij = ri cj N for all i, j. It is then easy to check that  ri cj + N ; i, j g(Y ) = − (N + mn)H N (N + mn) n m X X cj ln cj ri ln ri − −  j=1 i=1 + N ln N + (N + mn) ln(N + mn). By the inequality relating the entropy of a distribution and the entropy of its margins [Kh57], we have (5.4.3) H  ri cj + N ; i, j N (N + mn)  ≤ H     ri + n cj + m ; i +H ; j N + mn N + mn with the equality if and only if (ri + n)(cj + m) ri cj + N = N (N + mn) (N + mn)2 18 for all i, j, that is, when we have (ri m − N ) (cj n − N ) = 0 for all i, j, so that all row sums are equal or all column sums are equal. In that case, by symmetry we have Y = Z+ and hence I+ (R, C) estimates |A+ (R, C)| within an N O(m+n) factor. In all other cases, I+ (R, C) underestimates |A+ (R, C)| by as much as a 2Ω(mn) factor as long as the difference between the right hand side
and left hand side of (5.4.3) multiplied by N + mn overcomes the O (m + n) ln N error term, see also Section 5.5 for a particular family of examples. (5.5) Cloning margins. Let us choose a positive integer m-vector R = (r1 , . . . , rm ) and a positive integer n-vector C = (c1 , . . . , cn ) such that r1 + . . . + rm = c1 + . . . + cn = N. For a positive integer k, let us define a km-vector Rk and a kn-vector Ck by   Rk = kr1 , . . . , kr1 , . . . , krm , . . . , krm  {z } {z } | | k times k times   and Ck = kc1 , . . . , kc1 , . . . , kcn , . . . , kcn  . {z } {z } | | k times k times We say that margins (Rk , Ck ) are obtained by cloning from margins (R, C). It is not hard to show that if Z0 and Z+ are the maximum entropy matrices associated with margins (R, C) via Lemma 5.2 and Lemma 5.3 respectively, then the maximum entropy matrices associated with margins (Rk , Ck ) are the Kronecker products Z0 ⊗ Idk and Z+ ⊗ Idk respectively, where Idk is the k × k identity matrix. One has 1/k2 lim |A0 (Rk , Ck )| lim |A+ (Rk , Ck )| k−→+∞ k−→+∞ 1/k2 = α0 (R, C) and = α+ (R, C). Moreover, if not all coordinates ri of R are equal and not all coordinates cj of C are equal then the independence estimate I0 (Rk , Ck ), see (5.1.1), overestimates the number of km × kn matrices with row sums Rk and column sums Ck and 02 1 entries within a 2Ω(k ) factor while the independence estimate I+ (Rk , Ck ), see (5.1.2), underestimates the number of km×kn non-negative integer matrices within 2 a 2Ω(k ) factor, see [Ba10a] and [Ba09] for details. 19