Generate random binary matrix

Given the number of nodes M and number of links, I want to generate a random M by N matrix with 0 and 1 entries but with the constraints that the sum of each row is a random integer between 1 and L, and the sum of each column is a random integer between 1 and S. Here L and S are integers greater than 1.

Thanks for any hint and help.

David

Answer 1

[Jos (10584)]

Should all possibilities of such a matrix be equally likely? Then it might be very quite tricky.

Here's a brute force approach, that might not always work for specific values of S, L, M and N:

M = 5 ; N = 6 ; 
S = 3 ; L = 2 ;

% fix the number of 1's per row
X = zeros(M,N) ;
sumRow = ceil(S*rand(M,1)) ;
for k=1:M,
    X(k,1:sumRow(k)) = 1 ;
end

ntries = 0 ; 
while ntries < 1000 ;
    ntries = ntries + 1 ;
    % randomly swap columns, see RANDSWAP on the File Exchange
    for k=1:M,
        p = randperm(N) ;
        X(k,:) = X(k,p) ;
    end
    if all(sum(X,1) <= L) && all(sum(X,1)>0) 
       break ;
    end
end

if ntries < 1000
   disp(X)
   sumCol = sum(X,1)
   sumRow = sum(X,2).'
else
   disp('No matrix found within a reasonable time') ;
end

[Meng]

Thanks for your answer. When the dimension is larger, it is always "no matrix found within a reasonable time". Thanks for your answers anyway.

Also, it may get some matrix which the sum of column is zero.

[Jan]

@Meng: Please do not write "larger", but show us the typical and maximum size. The applied method depends critically on the magnitude of the problem. An efficient solution for a 8x8 matrix and S=L=4 must differ from M=N=1e6 and S=L=1e4.

[Meng]

@Simon: Typically, the matrix is very sparse. For example, M=150, N=60, L=8,S=15.

Answer 2

[Jan]

You can try a "shooting method":

1. Start with a matrix of zeros
2. Determine a line and column, which differ the most from the criteria
3. Set a 1 there
4. Loop

A genetic algorithm might be fine also:

1. Start with 100 random matrices
2. Select the 10 with the smallest sum of deviations from the criteria
3. For each of them create 10 children by setting 10% (and 9% later etc) of the elements randomly
4. Perhaps some cross-overs of blocks between the best individuals
5. Loop to 2.