Happy New Year!
Suppose I would like to sample a $n \times n$ (0,1)-matrix whose trace is 0, and whose row sums and column sums are all $m$ with $1 \le m \le n-1.$ How can I sample this matrix uniformly?
Thank you very much!
[Update based on the suggestion from user 44191] I am interested in the optimal way to sample such a matrix. What is the complexity of the problem as a function of $n$ and $m$? Thank you all!
The answer depends on how large $m$ is compared to $n$.
For very low $m$: Consider a $mn\times nm$ matrix as an $n\times n$ matrix of cells, where each cell is an $m\times m$ matrix. Generate random $mn\times nm$ permutation matrices until each cell contains at most one 1. Then replace each cell by a single element. The result is an exactly uniform random $n\times n$ matrix with each row and column summing to $m$. The catch is that the expected number of trials before a suitable permutation matrix is found is $\Omega(e^{m^2/4})$, so this is only useful for tiny $m$.
For moderate $m$, say $m=o(n^{1/3})$ Nick Wormald and I published a method that takes expected time $O(nm^3)$, see this paper.
Nick and Jane Gao recently figured out how to get up to $m=o(n^{1/2})$ but I don't know if they published the bipartite version. See https://arxiv.org/abs/1511.01175.
For larger $m$, I think there are no known polynomial-time exact samplers. There are methods like Markov chains that converge to a uniform distribution.
ADDED: To impose zero trace in the "very low $m$" case, just keep generating permutation matrices until the diagonal cells are empty. It will not greatly change the $m$ that is plausible (in practice only up to about $m=5$, or $m=6$ if you are patient). For larger $m$, I don't know anything. It should be easy to adjust the Markov chains.
