Problem of Enumerating Integer NxN Matrices with Line Sum Equal to D

[Max]

N. J. A. Sloane wrote:

>>The third problem is to UNIFORMLY generate random distinct instances, with or without equivalence reduction.

There is a simple way to produce an uniformely distributed random matrix for the case of even N and D=N.

1. Let M[i][j]=1 for all i=1..N, j=1..N.
2. Choose random (uniformly distributed) ordered matching between cells of M.
3. Perform the following update simaltaneously for all matched pairs ((x,y),(z,t)) (or better call them ``tuples'' since they are ordered):
M[x][y]--
M[x][t]++
M[z][y]++
M[z][t]--

Uniformity of the resulting matrix is guaranteed by the equal initial filling,
and by the symmetry of all cells having equal chances to give away their values or to attain values from other cells of the same row.

Similar construction works for the case of even N and D=kN for some integer k.
Initial filling is M[i][j]=k, and steps 2,3 repeated k times.

Max





MIME-Version: 1.0