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

2008/06/09 by Alexander Barvinok, Barvinok, Alexander · 1 citation
Mathematics · #05A16 #05C30 #15A15 #15A52 #60C05 #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Markov Chains and Monte Carlo Methods #Point processes and geometric inequalities #Probability (math.PR)

paper · pdf · doi:10.48550/arxiv.0806.1480

openalex publication_date 2008/06/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We consider the set Sigma(R,C) of all mxn matrices having 0-1 entries and prescribed row sums R=(r₁, ..., r_m) and column sums C=(c₁, ..., c_n). We prove an asymptotic estimate for the cardinality |Sigma(R, C)| via the solution to a convex optimization problem. We show that if Sigma(R, C) is sufficiently large, then a random matrix D in 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.

Cited by

• Maximum entropy Gaussian approximation for the number of integer points and volumes of polytopes

Related

• Contingency tables with uniformly bounded entries
• Matrices with prescribed row and column sums
• What does a random contingency table look like?
• Asymptotic estimates for the number of contingency tables, integer flows, and volumes of transportation polytopes
• Sums of random Hermitian matrices and an inequality by Rudelson