On the number of matrices and a random matrix with prescribed row and column sums and 0-1 entries

摘要

We consider the set Sigma(R,C) of all m x n matrices having 0-1 entries and prescribed row sums R = (r(1), ... , r(m)) and column sums C = (c(1), ... , c(n)). We prove an asymptotic estimate for the cardinality vertical bar Sigma(R, C)vertical bar via the solution to a convex optimization problem. We show that if Sigma(R, C) is sufficiently large, then a random matrix D is an element of Sigma(R, C) sampled from the uniform probability measure in Sigma(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.