2
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – user44191 Jan 2 at 16:10
  • $\begingroup$ Yes indeed. I am interested in the optimal way to sample it. Thanks a lot! $\endgroup$ – KPU Jan 2 at 16:24
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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! $\endgroup$ – KPU Jan 3 at 18:53

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.