On the number of matrices and a random matrix with prescribed row and column sums and 0-1 entries
On the number of matrices and a random matrix with prescribed row and column sums and 0-1 entries
复制标题
DOI：
10.1016/j.aim.2009.12.001
复制
发表时间：
2010-05-01
影响因子：
1.7
通讯作者：
Barvinok, Alexander
中科院分区：
文献类型：
--
作者：
Barvinok, Alexander
我们考虑具有 0-1 个条目的所有 m x n 矩阵的集合 Sigma(R,C) 以及规定的行和 R = (r(1), ... , r(m)) 和列和 C = (c(1), ... , c(n))。我们通过凸优化问题的解证明了基数竖条 Sigma(R, C)竖条的渐近估计。我们证明，如果 Sigma(R, C) 足够大，则随机矩阵 D 是从 Sigma(R, C) 中的均匀概率测度采样的 Sigma(R, C) 的元素，以高概率接近特定矩阵 Z = Z(R, C)，该矩阵最大化行和 R、列和 C 以及 0 和 1 之间的条目的所有矩阵中条目的熵之和。对于具有规定行和列和的 0-1 矩阵，可以获得类似的结果并在某些位置分配了零。 (C) 2009 Elsevier Inc. 保留所有权利。
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. (C) 2009 Elsevier Inc. All rights reserved.