row / column summation constraints in random binary matrix.

I want to generate a random binary matrix A(m, n) that meets two conditions:

1. The summation of each column in A is 1.
2. The summation of each row in A is less than a value in vector B={B1,...,Bm}, where B is a set of values.

Anyone knows, how can I implement it in MATLAB?

Thanks.

[John D'Errico]

This question makes no sense.

A random BINARY matrix will be composed of zeros and ones. Nothing else. Binary.

Then you say that the sum for each column is 1. So, there is exactly ONE non-zero element in any column.

Then you say that the sum of each row is less than some specified set of values, B.

Is it binary or not?

[Walter Roberson]

I do not see a problem with the specificatio. For example,

   [0 0 1 0 0 1
    0 1 0 0 0 0
    0 0 0 1 1 0
    1 0 0 0 0 0]

is a matrix with column sum 1 in each column, and varying row sum.

[Image Analyst]

But how would you generate such a matrix for m rows and n columns? I don't know of anyway other than to load a 1 into a random row in each column, then to check the overall matrix to see if the row sums are each less than B, and it any row fails, keep trying. Any systematic way of marching over column-by column will not be random, I don't think.

Answer 1

[Image Analyst]

Here's one way, just using brute force try-and-see:

rows = 5;
columns = 11;
% Get some random B value, since we don't know what else to use.
B = randi(rows, rows, 1)
loopcounter = 1; % The failsafe.
maxAttempts = 100000; % A hundred thousand attempts.
while loopcounter < maxAttempts
  A = zeros(rows, columns);
  % Get rows to put 1's into
  rowsWith1s = randi(rows, 1, columns);
  % Load those 1s into A.
  for col = 1 : columns
    A(rowsWith1s(col), col) = 1;
  end
  %   A % Print to command window
  % Get row sums:
  rowSums = sum(A, 2);
  % Bail out if all sums are less than B
  if all(rowSums < B)
    fprintf('Succeeded after %d attempts\n', loopcounter);
    break;
  end
  loopcounter = loopcounter + 1;
end
if loopcounter == maxAttempts
  fprintf('Was not able to succeed after %d attempts.\n', loopcounter);
else
  fprintf('The final A:\n');
  rowSums % Print to command window
  A % Print to command window
end

[Mohammad Shojafar]

Thanks for the response. This is a nice method, however it can not work always especially when the number of columns and row are high, or the summation of the values of B vector near to the column number. Do you have any ideas in these cases?

One question comes to my mind: Can we have same problem plus pushing some cells in the A matrix to remain 0?

[Image Analyst]

Well of course if the numbers in B are too low, then non solution is possible. For example what if the B elements are all 0? And if the number of rows and columns is very high, the method, since it's kind of a random "try-and-see" approach (not systematic) is rather inefficient and may take a long time to find an answer. I don't know of any systematic approach off the top of my head, so check out Walter's reply. And of course, like I said, it's possible there will be no solution if your B values are unreasonably low. On the other hand, if your B values are really high, like a million or a billion or so, then it will arrive at a solution on the first try since every sum will be less than a billion.

Answer 2

[Walter Roberson]

This can be reframed as being mostly an integer partitioning problem.

You have n columns. That gives you n ones, for a total sum of n.

You have m buckets which have to be filled with 1's in such a way that the total sum is n, and no bucket gets more than B(m).

This an integer partitioning problem: a fixed sum, n, has to be divided in m pieces with lower bound 0 and upper bound B(m).

Once you have partitioned to find the number, P(m) placed in each of the m buckets,

temp = repelems(1:m, P);     %total length will be n
scrambled = temp(randperm(n));
ind = sub2ind([m,n], scrambled, 1:n);
output = zeros(m,n);
output(ind) = 1;

That is, you distribute P(m) copies of m randomly and you use that as the row number to pick for placing the single 1 of each column.

This reduces the problem down to doing the integer partitioning with the constraints.

I do not have a constrained integer partitioning available at the moment. I did, though, happen to write an unconstrained integer partitioning yesterday that might be adaptable, perhaps. From https://www.mathworks.com/matlabcentral/answers/327656-conditional-random-number-generation#comment_433543

random_nonnegint_partition = @(of_what, num_rows, number_of_partitions) accumarray( [repmat((1:num_rows).',of_what, 1), randi(number_of_partitions, num_rows*of_what, 1)], 1);

The first parameter gives the number which is to be partitioned, the second parameter gives the number of different times you want the generation to be done, and the third parameter gives the number of pieces to partition into.

For your purposes you only need to do the partitioning once, so this could be simplified to

random_nonnegint_partition = @(of_what, number_of_partitions) accumarray( randi(number_of_partitions, of_what, 1), 1) .';

For your situation you would be passing n (total sum) as the first parameter and m as the second parameter:

P = random_nonnegint_partition(n, m);

This version is unconstrained: the maximums B(m) are not taken into account.

You could re-do the random generation if any(P>B) . That could potentially take a long time, though, with the likelihood of a long time varying according to how skewed the B values are. Re-doing the random generation is not an entirely satisfactory solution.

I will think more to see if I can come up with a constrained version of the technique.

[Image Analyst]

Mohammad, please give typical values for m, n, and B.

[Mohammad Shojafar]

The results of the linear programming is not feasible.

[Image Analyst]

Mohammad, please give typical values for m, n, and B.

[Walter Roberson]

Roger Stafford has posted a fairer unconstrained random integer partition routine at https://www.mathworks.com/matlabcentral/answers/327656-conditional-random-number-generation#answer_257296