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

DOI10.1016/J.AIM.2009.12.001zbMATH Open1191.15031arXiv0806.1480OpenAlexW2150635973MaRDI QIDQ962158FDOQ962158

Alexander Barvinok

Publication date: 6 April 2010

Published in: Advances in Mathematics (Search for Journal in Brave)

Abstract: We consider the set Sigma(R,C) of all mxn 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 |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.

Full work available at URL: https://arxiv.org/abs/0806.1480

Recommendations

• Publication:4945030
• On the number of possible row and column sums of \(0,1\)-matrices
• On (0, 1)-matrices with prescribed row and column sum vectors
• An asymptotic formula for the number of non-negative integer matrices with prescribed row and column sums
• The class of \((0,1,\dots,r)\)-matrices with prescribed row and column sums
• Enumeration of \((0,1)\)-matrices with constant row and column sums
• Asymptotic enumeration of 0-1 matrices with equal row sums and equal column sums
• Asymptotic enumeration of dense 0-1 matrices with equal row sums and equal column sums
• scientific article
• The class of matrices of zeros, ones, and twos with prescribed row and column sums

zbMATH Keywords

entropyconvex optimizationrandom matrixasymptotic estimates0-1 matricesinteger flows

Mathematics Subject Classification ID

Convex programming (90C25) Random matrices (algebraic aspects) (15B52) Matrices of integers (15B36) Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Inverse problems in linear algebra (15A29)

Cites Work

• Title not available (Why is that?)
• A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
• Title not available (Why is that?)
• A course in combinatorics.
• Van der Waerden/Schrijver-Valiant like conjectures and stable (aka hyperbolic) homogeneous polynomials: one theorem for all
• Title not available (Why is that?)
• Title not available (Why is that?)
• Two Algorithmic Results for the Traveling Salesman Problem
• The enumeration of arrays and a generalization related to contingency tables
• A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents
• Fast uniform generation of regular graphs
• Asymptotic Estimates for the Number of Contingency Tables, Integer Flows, and Volumes of Transportation Polytopes
• Sequential Monte Carlo Methods for Statistical Analysis of Tables
• Asymptotic enumeration of sparse 0--1 matrices with irregular row and column sums
• Random dense bipartite graphs and directed graphs with specified degrees
• Hamiltonian cycles in Dirac graphs
• Maximum entropy Gaussian approximations for the number of integer points and volumes of polytopes
• Asymptotic enumeration of dense 0-1 matrices with specified line sums
• Asymptotic enumeration of dense 0-1 matrices with equal row sums and equal column sums
• Entropy bounds for perfect matchings and Hamiltonian cycles
• Asymptotics and random matrices with row-sum and column sum-restrictions
• The asymptotic number of non-negative integer matrices with given row and column sums
• Classical complexity and quantum entanglement
• Integration and optimization of multivariate polynomials by restriction onto a random subspace
• Sampling binary contingency tables with a greedy start

Cited In (30)

• On the largest size of an antichain in the Bruhat order for \(\mathcal A (2k,k)\)
• Phase transition in random contingency tables with non-uniform margins
• Random graphs with a given degree sequence
• Boolean matrices with prescribed row/column sums and stable homogeneous polynomials: combinatorial and algorithmic applications
• Characterizing optimal sampling of binary contingency tables via the configuration model
• Limiting properties of an equiprobable sampling scheme for 0-1 matrices
• Rank relations between a \(\{0, 1\}\)-matrix and its complement
• On the number of possible row and column sums of \(0,1\)-matrices
• The number of graphs and a random graph with a given degree sequence
• Bootstrapping on undirected binary networks via statistical mechanics
• Asymptotic properties of random contingency tables with uniform margin
• Battleship, tomography and quantum annealing
• Estimating parameters of a probabilistic heterogeneous block model via the EM algorithm
• Asymptotic enumeration of digraphs and bipartite graphs by degree sequence
• MAX-plus objects to study the complexity of graphs
• Title not available (Why is that?)
• Analysis of local search landscapes for \(k\)-SAT instances
• Matrices with prescribed row and column sums
• Chains and Antichains in the Bruhat Order for Classes of (0, 1)-Matrices
• On the number of contingency tables and the independence heuristic
• The maximal length of a chain in the Bruhat order for a class of binary matrices
• Threshold functions for small subgraphs in simple graphs and multigraphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• The class of matrices of zeros, ones, and twos with prescribed row and column sums
• Lower bounds for contingency tables via Lorentzian polynomials
• Maximum entropy Gaussian approximations for the number of integer points and volumes of polytopes
• Title not available (Why is that?)
• Block-regularized repeated learning-testing for estimating generalization error
• Short proofs of the Gale \& Ryser and Ford \& Fulkerson characterizations of the row and column sum vectors of (0, 1)-matrices

This page was built for publication: On the number of matrices and a random matrix with prescribed row and column sums and 0-1 entries

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q962158)