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

By Alexander I. Barvinok. 2008

81 citations recorded by the source corpus.

Abstract We consider the set Σ ( R , C ) of all m × 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 | Σ ( 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.

Subfields: Applied Mathematics, Geometry and Topology, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/bdb5b2f9427efd6f7707a3f796b7b4f3da8e7fc0

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Applied Mathematics

Alexander I. Barvinok

In Geometry and Topology

In Statistics and Probability

Alexander I. Barvinok

Citations in the corpus

Matrices with prescribed row and column sums (2010, background): “paper is a survey and although we don’t provide complete proofs, we often sketch main ideas of our approach. 2. The logarithmic asymptoticforthe numberof 0-1matrices The following result is proven in [Ba10a]. (2.1) Theorem. Given positive integer vectors R= (r1,...,rm) and C= (c1,...,cn), let us deﬁ”
Random graphs with a given degree sequence (2010, unknown): “The work was initiated by Barvinok who looked at directed and bipartite graphs in [6].”