Article ID Journal Published Year Pages File Type
4667148 Advances in Mathematics 2010 24 Pages PDF
Abstract

We consider the set Σ(R,C) of all m×n matrices having 0–1 entries and prescribed row sums R=(r1,…,rm) and column sums C=(c1,…,cn). We prove an asymptotic estimate for the cardinality |Σ(R,C)| via the solution to a convex optimization problem. We show that if Σ(R,C) is sufficiently large, then a random matrix D∈Σ(R,C) sampled from the uniform probability measure in Σ(R,C) with high probability is close to a particular matrix Z=Z(R,C) that maximizes the sum of entropies of entries among all matrices with row sums R, column sums C and entries between 0 and 1. Similar results are obtained for 0–1 matrices with prescribed row and column sums and assigned zeros in some positions.

Related Topics
Physical Sciences and Engineering Mathematics Mathematics (General)