# How to uniformly sample a square (0,1)-matrix whose trace is 0 and whose row sums and column sums are the same?

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!

• Presumably you want to sample it quickly as well? Because otherwise, there's a very easy answer: sample all (0,1) matrices and throw away the ones that don't fit your criteria. – user44191 Jan 2 at 16:10
• Yes indeed. I am interested in the optimal way to sample it. Thanks a lot! – KPU Jan 2 at 16:24

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.

• Thank you so much for the very helpful information! I am indeed looking for the algorithm for small m. Is there a way to generate the matrix with the additional constraint of a 0 trace? I guess I can permute the rows and columns, but I would like to know if there is a more efficient way. Thank you so much again! – KPU Jan 3 at 18:53