Number of symmetric matrix with fixed margins

Question

I'm looking for the cardinality of the set of symmetric matrices with entries in $\mathbb{Z}^*$ (the nonnegative integers) and fixed margins $\mathbf{k}=(k_1,k_2,...,k_q)$. I've also seen them called line sum symmetric matrices.

I have not found any known result, but I have found upper bounds.

One possibility is to drop the symmetry constraint and to focus on the set of matrices with fixed row and column margins. Miller and Harrison [1] give an exact recursive formula that does not scale to large matrices, while Barvinok gives an asymptotic result for dense enough margins, as the solution of a convex optimization problem [2].

Another possibility is to upper bound the cardinality of the set as the number of $m$ combinations with repetitions, on a set of size $q$, with $m=\sum_j k_j$. This second alternative enforces symmetry in the counting of matrices by construction, but let the margins be arbitrary as long as they sum to $m$. This yield the simple $\binom{q+m-1}{m}$ which appears tighter, in most case I tried, than the first.

---

[1] Miller, Jeffrey W., and Matthew T. Harrison. "Exact sampling and counting for fixed-margin matrices." The Annals of Statistics 41.3 (2013): 1569-1592.

[2] Barvinok, Alexander. "Matrices with prescribed row and column sums." Linear Algebra and its Applications 436.4 (2012): 820-844.

Answer 1

There is no simple exact formula known, nor prospect of one in my opinion.

Here are two relevant asymptotic results.

(A) In this paper, Catherine Greenhill and I gave the asymptotic count in the case that $K=o(M^{1/3})$, where $K$ is the maximum row sum and $M$ is the total of all the entries. (Journal reference: Adv. Appl. Math., 41 (2008) 459–481.)

(B) In this paper, Jeanette McLeod and I gave the asymptotic count in the case that all the row sums are equal and at least $cn/\log n$ for $c\gt\frac23$. In this paper the diagonal is assumed zero. We also give the exact values (the Ehrhart polynomial) for matrices up to order 9 and a conjecture for all row sums that has strong experimental backing. (Journal reference: J. Australian Math. Soc., 92 (2012) 367–384.)

A file of exact values corresponding to (B) is here.

The methods used in (B) would allow nonzero diagonal entries and mixed row sums, but the calculation has only been done in rough notes (by Mikhail Isaev).

There are now two different techniques available for closing the large gap between (A) and (B), but as far as I know neither has been carried out.