Specified number of ones in the matrix (column and row)

Hi. I need to create a square matrix filled with random values of 1 and 0. Sum of each row and each column must be equal to the given condition. e.g. matrix: 5x5 ; sum of 1's: 3

Answer 1

[Bruno Luong]

I couldn't figure out how to generate k permutations that are not redundant beside test and discard until it meets the condition (technique that I really hate to use). So here is the code that does what you want but I'm far from proud of it:

n = 10; % Matrix dimension
k = 4;  % row/column sum target of 1s 

l = min(k,n-k);
J = zeros(n,l);
for i=1:l
    while true
        J(:,i) = randperm(n);
        if all(all(J(:,i)-J(:,1:i-1)~=0,2),1)
            break
        end 
    end
end
I = repmat((1:n)',1,l);
A = accumarray([I(:) J(:)],1,[n n]);
if l < k
    A = 1-A;
end

sum(A,1)
sum(A,2)

[John D'Errico]

The trick I used was to start with the complete set of permutations, thus perms. Select any of them at the start, then discard all permutations that have any overlap with those you have found already. The problem of course is things will go rapidly downhill for larger arrays, since we have

factorial(15)
ans =
   1.3077e+12

as the number of permutations for a 15x15 array. So the difficult question would be to solve this for a 25x25 or a 100x100 array, where 15 ones are desired in each row and column. My approach would fail miserably then.

[Darek Myszk]

Bruno, Can you explain how your script works?

[Bruno Luong]

The idea is to iterate for 1:k, each iteration I place one 1 for each row and column randomly.

This is carried out by

randperm(n)

which decides which column of 1s for respectively row = 1,...n (set by I).

If I do the oterative process k time then the sum(A,2) will be k.

However sum(A,1)<=k, and it is stritly <k if and only if two permulations get the same values.

So to ensure sum(A,1)==k as required, I need to make sure the new generate permutation does not have the same value with all preceding generated. This is the role of the while loop with the test all(all(J(:,i)-J(:,1:i-1)~=0,2),1).

The accumarray put everything together in A according to row/colums generated.

The trick

l = min(k,n-k);
...
if l < k
    A = 1-A;
end

is to swap the role of 0 and 1, so that I can work on the least random positions to generate.

[Bruno Luong]

I provide a much better method (without rejection) below, according to the idea of Akira Agata

Answer 2

[Bruno Luong]

From an idea by Akira Agata

n = 10; % Matrix dimension
k = 4;  % row/column sum target of 1s

r = [ones(1,k) zeros(1,n-k)];
c = circshift(r,-k+1);
A = toeplitz(c,r);
A = A(randperm(n),randperm(n))

sum(A,2)
sum(A,1)

[Darek Myszk]

Its looks very good, but next question.

Created matrix A, I put in genmat = [ I A' ], and why, when I put all this code in the loop, always minimum distance of linear block code is the same value? Using the previous script, value of minimum distance was different, depending on the iteration.

___

command to check minimum distance: wt = gfweight(genmat).

I is eye's submatrix.

[Bruno Luong]

I'm not sure I understand with verbal description, minimum distance of what? What is inear block code?

Edit: I see you mention some function that seems to be in Communication Toolbox. I'm not familiar with it or the goal you want to achieve.

It might be possible that this method of toeplitz matrix is not completely random. I do not put too much though on it.

Answer 3

[John D'Errico]

Just a quick guess...

This reduces to finding a set of 3 permutations of the numbers 1:5, such that none of them fall in the same place. So we might consider the set defined by:

p =
   3     4     5     2     1
   4     2     1     3     5
   1     3     2     5     4

Now, create your matrix as:

M = eye(5);
M = M(:,p(1,:)) + M(:,p(2,:))+ M(:,p(3,:))
M =
   1     0     1     0     1
   0     1     1     1     0
   1     1     0     1     0
   1     1     0     0     1
   0     0     1     1     1

So sort of like derangements, but not really. You could actually create M using a more efficient expression, thus with accumarray or sparse, but the way I wrote it may be more intuitively understandable.

Given all that, can you find the array p in a simple way? I can think of at least one simple way.

allperms = perms(1:5);
p = nan(3,5);
for i = 1:3
  k = randi(size(allperms,1));
  p(i,:) = allperms(k,:);
  allperms(any(allperms == p(i,:),2),:) = [];
end

which yields:

p
p =
   3     2     1     4     5
   5     1     4     3     2
   4     3     5     2     1

Note: the above will be problematic if you try to solve the problem for large matrices, since perms will explode. But you did ask for 5x5.

[Darek Myszk]

Thanks for reply. Its look good, but at every attempt matrix will be the same (p is not random, yes?) and the limit must be easy to change from program.

[Bruno Luong]

John: If I'm not mistaken, to makes it works the 3 permutations must give different values at the same index.

[John D'Errico]

Yes. Each permutation must be distinct from the others at each location.

As fas as getting a different permutation? That is trivial. As long as you do not reset the random seed before each time through, then randi will give you a different set.

For example, I just re-ran it.

p
p =
     2     3     5     4     1
     3     2     1     5     4
     4     1     2     3     5

Which corresponds to the matrix:

M =
   0     1     1     0     1
   1     1     1     0     0
   1     1     0     1     0
   1     0     0     1     1
   0     0     1     1     1

Answer 4

[Darek Myszk]

Matrix 5x5, and limit of'1s in the subject is an example. Size of matrix, and limit must be given at start of the program :/

[John D'Errico]

No need to add an answer just to make a comment.