How can I obtain some random connections matrices between nodes if I have 10 nodes and I know the number of transceivers at each node ?

I have 10 nodes .. each node has known number of transceivers as indicated in this vector:

[6 3 3 3 3 3 3 2 1 1]

where: 6 is the number of transceivers at the 1st node, 3 is the number of transceivers at the 2nd node and so on ..

Each transceiver can only receive from one source at a time .. it is required that all transceivers must be in use simultaneously .. it is permitted for the same node to use more than one transceiver to transmit to another node that has enough transceivers to receive with .. it is not possible for a single transceiver to be considered to be transmitting to multiple transceivers ..

I want to know How can I obtain some random connections matrices between nodes and each obtained connection matrix identify the number of transceivers used between the connected nodes ?

[Walter Roberson]

Is it legal for a node to use a transceiver to transmit to the same node?

[Mahmoud Ahmed]

The node can't use transceiver to transmit to itself .. If you ask about is it legal for a node to use more than one transceiver to transmit to the same destination node, it's legal.

Answer 1

[Walter Roberson]

Let T = [6 3 3 3 3 3 3 2 1 1] (the transceiver count).

Now, since the transceivers for each node are not all going to be transmitting to the same place, number the transceivers sequentially, so we can talk about transceiver #8 transmitting to transceiver #22 (for example), like

[[1 2 3 4 5 6], [7 8 9], [10 11 12], [13 14 15], [16 17 18], [19 20 21], [22 23 24], [25 26], [27], [28]]

Let N be the total number of transceivers, sum(T)

Now construct a square adjacency matrix A that is N x N, with A(I,J) set to 1 if transceiver #I is transmitting to transceiver #J. Because each transmitter can only transmit to one receiver and each receiver can only receive from one transmitter, we know that for any given row I, A(I,:) will have exactly one entry that is 1, with the rest 0, and for any given column J, A(:,J) will have exactly one entry that is 1, with the rest 0.

considering that each row and column has exactly one entry that is 1, the situation corresponds to an N x N Permutation matrix.

As a bit of a generalization, suppose that any given transceiver was permitted to transmit to itself or to another transceiver at the same node. Under that generalization, we would be needing to consider the entire set of N x N Permutation matrices -- which would be factorial(N) of them, so factorial(28) = 28! = 304888344611713860501504000000 of them in this situation.

As it is not permitted for any node to transmit to itself, the actual number of matrices to consider will be less than that. But will it be much less than that?

Without working through the reduction, we can guess that out of the 28!, that the prohibited fraction might be on the order of 6! * (3!)^6 * 2! = 67184640 -- that is, prod( factorial(T) ). If so, then that would leave us with about 304888344611713860501504000000 / 67184640 = 4538066209950873600000, which is roughly 4.5E21 matrices. Each matrix would require 28*28, but logical (1 byte) could be used, so it might require 784 bytes each plus any header overhead. That gives about 3.5E24 bytes, or 3 1/2 Yottabytes . I suspect you do not have access to that much memory.

Now, I did not work through the count analytically, so I could certainly be off on my guess. How far off would I have to be for the calculation to be feasible? Well, suppose the prohibited fraction was not just prod( factorial(T) ) but was instead roughly the square of that, leaving about 28! / (6! * (3!)^6 * 2!)^2 valid arrangements. That would be about 67546186300185 and at 784 bytes each (excluding any header overhead), that would be about 5.3E16 bytes, which would be about 53 petabytes. I suspect you do not have access to that much memory either.

You could work through the counting more analytically, but I think you will find that it is going to be impractical to do what you are asking.

[Mahmoud Ahmed]

I got your idea .. If I want to generate random connection matrices that match with the above constraints. How can I do this ?

[Walter Roberson]

https://stackoverflow.com/questions/14381770/random-permutation-matrix suggests

A = eye(N);
A = A(randperm(N), :);

After that you could check whether nodes transmit to themselves, and if so then generate a new matrix.