First, I would generate a matrix $M$ such that $M_{ij}$ is exponentially distributed with mean $\mu$ for all $i \ne j$ or $0$ otherwise.

Then, calculate your matrix \begin{align} X_{ij} &= \frac{e^{-M_{ij}}}{\sum_je^{-M_{ij}}} \end{align}

To efficiently sample from a categorical distribution (a list of probabilities totalling 1), just calculate the cdf and build a Huffman tree with different values of the cdf at each leaf node. Sample from a uniform distribution, and find the leaf node whose cdf is the smallest one larger than your sampled value. (This has an amortized cost of the entropy number of your categorical distribution.)

First, I would generate a matrix $M$ such that $M_{ij}$ is exponentially distributed with mean $\mu$ for all $i \ne j$ or $0$ otherwise.

Then, calculate your matrix \begin{align} X_{ij} &= \frac{e^{-M_{ij}}}{\sum_je^{-M_{ij}}} \end{align}

To efficiently sample from a categorical distribution (a list of probabilities totalling 1), just build a Huffman tree using the probabilities of each outcome keeping track of the total probability in descendants to the left of each node. Sample from a uniform distribution, and find the leaf node whose cdf is the smallest one larger than your sampled value. (This has an amortized cost of the entropy of your categorical distribution.)