How to create a symmetric matrix of 1's and 0's with constant row and column sum

Question

I'm trying to find an elegant algorithm for creating an N x N matrix of 1's and 0's, under the restrictions:

• each row and each column must sum to Q (to be picked freely)
• the diagonal must be 0's
• the matrix must be symmetrical.

It is not strictly necessary for the matrix to be random (both random and non-random solutions are interesting, however), so for Q even, simply making each row a circular shift of the vector

[0 1 1 0 ... 0 0 0 ... 0 1 1] (for Q=4)

is a valid solution.

However, how to do this for Q odd? Or how to do it for Q even, but in a random fashion?

For those curious, I'm trying to test some phenomena on abstract networks.

I apologize if this has already been answered before, but none of the questions I could find had the symmetric restriction, which seems to make it much more complicated. I don't have a proof that such a matrix always exists, but I do assume so.

Answer 1

The object that you're trying to construct is known more canonically as an undirected d-regular graph (where d = Q). By the handshaking theorem, N and Q cannot both be odd. If Q is even, then connect vertex v to v + k modulo N for k in {-Q/2, -Q/2 + 1, ..., -1, 1, ..., Q/2 - 1, Q/2}. If Q is odd, then N is even. Construct a (Q - 1)-regular graph as before and then add connections from v to v + N/2 modulo N.

If you want randomness, there's a Markov chain whose limiting distribution is uniform on d-regular graphs. You start with any d-regular graph. Repeatedly pick vertices v, w, x, y at random. Whenever the induced subgraph looks like

v----w

x----y ,

flip it to

v    w
|    |
x    y .