Generating a random binary matrix with fixed number of nonzeros

Question

I want an algorithm (just the idea, not the actual code) to generate a random $n$ by $n$ matrix with binary entries, but with the condition that the number of nonzeros must be a fixed number $c$. Any idea of how I can do that?

The obvious way I thought is starting with a matrix of zeros, and setting $k=1$, then proceeding as:

while $k<=c$

pick a random number $r$ between $1$ and $n^2$

if the entry $A_{ij}$ identified with $r$ isn't $1$, then set it to $1$. and $k \leftarrow k+1$, else pick another number $r$ and repeat the previous step.

However there's no guarantee that this procedure will end, since it could be that it always picked the same entry which is already $1$...

Answer 1

You basically want to identify the set of positions where the entry will be $1$. So you are looking to choose a random set of size $c$ from a set of size $n^2$. There are $\binom{n^2}{c}$ such possibilities, and you want to choose one of them uniformly randomly.

Look at algorithms for choosing a random subset. A simple idea would be to randomly choose a $p_1$ from $\{1,\ldots,n^2\}$ first. Then randomly choose a $p_2$ from $\{1,\ldots,\hat{p_1},\ldots n^2\}$ where the hat indicates to omit that number. Alternatively you could pick a number from $\{1,\ldots n^2-1\}$, and adjust: if the number is less than $p_1$, then it's your $p_2$, and otherwise, that number plus $1$ is your $p_2$. And so on with more $p_i$.

Also, there is actually a nice way to order the subsets represented by $\binom{n^2}{c}$ that is a bit more complicated than I would go into here. With that ordering, you could choose a random integer from $\{1,\ldots,\binom{n^2}{c}\}$ and then use the corresponding subset of the $n^2$ entries. So for example, with $n=5$ and $c=2$, we have $\binom{n^2}{2}=300$. And if you randomly chose a number, say $113$, from $\{1,\ldots,300\}$, there is a quick algorithm to identify the $113$th subset of size $2$ from among all subsets of size $2$.

Answer 2

If you use Matlab, that's already been done for you with the randsample function. You can call it to pick c values from 1 to n^2, without replacement. Those values serve as linear indices of the matrix entries that should be set to 1:

n = 5;
c = 8;
M = zeros(n,n);
M(randsample(n^2,c)) = 1;

If you want to do it more manually: generate a random permutation of the set 1, ..., n^2, and use the first c values as linear indices of the matrix entries that equal 1. The random permutation is obtained manually by generating n^2 random values with uniform distribution (rand function), sorting them, and taking note of the indexing implied by that sorting (second output of sort):

n = 5;
c = 8;
M = zeros(n,n);
[~, perm] = sort(rand(1,n^2));
M(perm(1:c)) = 1;