5

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.

David Eisenstat
  • 64,237
  • 7
  • 60
  • 120
Kaare
  • 531
  • 1
  • 7
  • 26
  • 2
    Your first restriction, up to a constant factor of Q, is called a [Doubly stochastic matrix](http://en.wikipedia.org/wiki/Doubly_stochastic_matrix). – Hooked May 20 '14 at 13:47
  • For Q odd, I think you would have to have a 1 on the diagonal, which violates your second requirement. I may be wrong on that, though. I can't think of how you would do even a 3x3 case with just one 1 in each row/column without it being on the diagnonal, though. Perhaps there are larger cases were you could have odd Q... – twalberg May 20 '14 at 13:58

2 Answers2

6

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 .
David Eisenstat
  • 64,237
  • 7
  • 60
  • 120
1

You can perhaps always follow your circular shift algorithm, when possible.

The only condition you need to follow while using the circular shift algorithm is to maintain the symmetric nature in the first row.

i.e. keeping Q 1's in the first row so that Q[0,1] to Q[0,N-1] {Assuming 0 indexed rows and cols, Q[0,0] is 0.} is symmetric, a simple example being 110010011.

Hence, N = 10, Q = 5, you can get many possible arrangements such as:

0 1 0 0 1 1 1 0 0 1 
1 0 1 0 0 1 1 1 0 0 
0 1 0 1 0 0 1 1 1 0 
0 0 1 0 1 0 0 1 1 1 
1 0 0 1 0 1 0 0 1 1 
1 1 0 0 1 0 1 0 0 1 
1 1 1 0 0 1 0 1 0 0 
0 1 1 1 0 0 1 0 1 0 
0 0 1 1 1 0 0 1 0 1 
1 0 0 1 1 1 0 0 1 0

or

0 1 1 0 0 1 0 0 1 1 
1 0 1 1 0 0 1 0 0 1 
1 1 0 1 1 0 0 1 0 0 
0 1 1 0 1 1 0 0 1 0 
0 0 1 1 0 1 1 0 0 1 
1 0 0 1 1 0 1 1 0 0 
0 1 0 0 1 1 0 1 1 0 
0 0 1 0 0 1 1 0 1 1 
1 0 0 1 0 0 1 1 0 1 
1 1 0 0 1 0 0 1 1 0

But as you can see for odd N(that means even N-1) and odd Q there can't be any such symmetric distribution.. Hope it helped.

Arkanath Pathak
  • 42
  • 1
  • 8