Matrices with prescribed row and column sums (Q763065): Difference between revisions

This is a survey of work by the author and J. A. Hartigan [see, for example, \textit{A. Barvinok} [Adv. Math. 224, No. 1, 316--339 (2010; Zbl 1191.15031)] and \textit{A. Barvinok} and \textit{J. A. Hartigan} [Adv. Appl. Math. 45, No. 2, 252--289 (2010; Zbl 1213.05015)]. Let \(R=(r_{1},\dots ,r_{m})\) and \(C=(c_{1},\dots ,c_{n})\) be fixed vectors of positive integers such that \(\sum r_{i}=\sum c_{j}\). The author defines \(A_{0} :=A_{0}(R,C)\) and \(A_{+}:=A_{+}(R,C)\) to be the sets of all real \(m\times n\) matrices with 0-1 entries and nonnegative integer entries, respectively, with row sums and column sums given by \(R\) and \(C\). Consider the following questions. Assuming \(A_{0}\neq\emptyset\): (i) what are the cardinalities of \(A_{0}\) and \(A_{+}\); (ii) if \(A_{0}\) and \(A_{+}\) are considered as probability spaces with the uniform probability, what does a random element from one of these sets look like? In this review we restrict our remarks to \(A_{0}\), but analogous results for \(A_{+}\) are also described in the paper. Let \(P_{0}\) be the set of all real \(m\times n\) matrices \(X:=[x_{ij}]\) with \(0<x_{ij}<1\) for all \(i,j\) and with row and column sums given by \(R\) and \(C\). Define the entropy \(h\) on \(P_{0}\) where \[ h(X):=\sum_{i,j}\left\{ x_{ij}\ln\frac{1}{x_{ij}}+(1-x_{ij})\ln\frac {1}{1-x_{ij}}\right\} . \] Then \(h(X)\) attains its maximum at a unique matrix \(Z_{0}\) in \(P_{0}\), and \(\ln\left| A_{0}\right| \) is asymptotic to \(\ln\alpha_{0}\) where \(\alpha_{0}:=e^{h(Z_{0})}\) (\(\alpha_{0}\) has an alternative description in Theorem 1). A more precise asymptotic expression for \(\left| A_{0}\right| \) is given in Theorem 10. Furthermore, if \(X:=[x_{ij}]\) is a random \(m\times n\) matrix of independent Boolean random variables such that the expected value \(EX=Z_{0}\), then \(\mathbf{P}(X=D)=e^{h(Z_{0})}\) for each \(D\in A_{0}\) and \(\mathbf{P}(X\in A_{0})\) is at least \((mn)^{-\gamma(m+n)}\) for some absolute constant \(\gamma>0\). Analogous results are described for \(A_{+}\). Proofs are sketched or the reader is referred to earlier work and the paper ends with some open questions.