On the number of matrices and a random matrix with prescribed row and column sums and 0-1 entries
From MaRDI portal
(Redirected from Publication:962158)
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.
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; zbMATH DE number 5016698
- The class of matrices of zeros, ones, and twos with prescribed row and column sums
Cites work
- scientific article; zbMATH DE number 3143967 (Why is no real title available?)
- scientific article; zbMATH DE number 4170917 (Why is no real title available?)
- scientific article; zbMATH DE number 3766017 (Why is no real title available?)
- scientific article; zbMATH DE number 729680 (Why is no real title available?)
- A course in combinatorics.
- A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents
- A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries.
- Asymptotic Estimates for the Number of Contingency Tables, Integer Flows, and Volumes of Transportation Polytopes
- Asymptotic enumeration of dense 0-1 matrices with equal row sums and equal column sums
- Asymptotic enumeration of dense 0-1 matrices with specified line sums
- Asymptotic enumeration of sparse 0--1 matrices with irregular row and column sums
- Asymptotics and random matrices with row-sum and column sum-restrictions
- Classical complexity and quantum entanglement
- Entropy bounds for perfect matchings and Hamiltonian cycles
- Fast uniform generation of regular graphs
- Hamiltonian cycles in Dirac graphs
- Integration and optimization of multivariate polynomials by restriction onto a random subspace
- Maximum entropy Gaussian approximations for the number of integer points and volumes of polytopes
- Random dense bipartite graphs and directed graphs with specified degrees
- Sampling binary contingency tables with a greedy start
- Sequential Monte Carlo Methods for Statistical Analysis of Tables
- The asymptotic number of non-negative integer matrices with given row and column sums
- The enumeration of arrays and a generalization related to contingency tables
- Two Algorithmic Results for the Traveling Salesman Problem
- Van der Waerden/Schrijver-Valiant like conjectures and stable (aka hyperbolic) homogeneous polynomials: one theorem for all
Cited in
(31)- On the largest size of an antichain in the Bruhat order for A (2k,k)
- Phase transition in random contingency tables with non-uniform margins
- Random graphs with a given degree sequence
- Chains and antichains in the Bruhat order for classes of \((0,1)\)-matrices
- 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
- On properties of random binary contingency tables with non-uniform margin
- Rank relations between a \(\{0, 1\}\)-matrix and its complement
- Bootstrapping on undirected binary networks via statistical mechanics
- 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
- Estimating parameters of a probabilistic heterogeneous block model via the EM algorithm
- Asymptotic properties of random contingency tables with uniform margin
- Battleship, tomography and quantum annealing
- Asymptotic enumeration of digraphs and bipartite graphs by degree sequence
- MAX-plus objects to study the complexity of graphs
- Analysis of local search landscapes for \(k\)-SAT instances
- Matrices with prescribed row and column sums
- scientific article; zbMATH DE number 3906527 (Why is no real title available?)
- On the number of contingency tables and the independence heuristic
- Most binary matrices have no small defining set
- 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
- scientific article; zbMATH DE number 969973 (Why is no real title available?)
- The class of matrices of zeros, ones, and twos with prescribed row and column sums
- Maximum entropy Gaussian approximations for the number of integer points and volumes of polytopes
- Lower bounds for contingency tables via Lorentzian polynomials
- scientific article; zbMATH DE number 1420958 (Why is no real title available?)
- 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)
