Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4667148 | Advances in Mathematics | 2010 | 24 Pages |
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)