MATLAB: How to Generate Square Matrices with these properties?

Hello All, I was wondering how I would create a systematic Matrix Generator which goes element by element in order to generate All Graphs of Node Size 3 which have these properties:

1) All entries are a 0 or 1

2) Each Element where m = n (diagonal) must equal 0

3) There must exist at least a single "1" in each row and column

4) Entries across the diagonal must be opposite:

For example, If A(1,2) = 1 then A(2,1) must Equal 0

The generator must be able to store all of its generated graphs for later use and analysis

[Walter Roberson]

Isn't that only 8 different graphs?

[VeeVan]

Yes, most likely so, however, I will be expanding the program to encompass more than 3 nodes. Also, I want to congregate all the graphs as well.

Answer 1

[Walter Roberson]

N = 3;

M = N * (N-1) / 2;
numgraph = 2^M;
choices = dec2bin(0:numgraph-1, M) - '0';
graphs = cell(numgraph,1);
for K = 1 : numgraph
  sq = squareform(choices(K,:));
  sq = tril(1-sq) + triu(sq)
  graphs{K} = digraph(sq);
end

[VeeVan]

Hello Walter Roberson,

Thank you for answering! I believe this code meets all conditions 1,3, and 4, however, all the diagonal elements aren't 0. Please edit the code so that we can accommodate for this and I will promptly accept your answer!

[Walter Roberson]

N = 3;

M = N * (N-1) / 2;
numgraph = 2^M;
choices = dec2bin(0:numgraph-1, M) - '0';
graphs = cell(numgraph,1);
for K = 1 : numgraph
  sq = squareform(choices(K,:));
  sq = tril(1-sq, -1) + triu(sq);
  graphs{K} = digraph(sq);
end

[VeeVan]

Hello Walter Roberson,

This updated code DOES meet the diagonal elements equaling 0 requirement, however, now, it doesn't meet the "there must be at least a single "1" in each row and column" if you see the graphs generated:

N = 3;
M = N * (N-1) / 2;
numgraph = 2^M;
choices = dec2bin(0:numgraph-1, M) - '0';
graphs = cell(numgraph,1);
for K = 1 : numgraph
  sq = squareform(choices(K,:));
  sq = tril(1-sq, -1) + triu(sq)
  graphs{K} = digraph(sq);
end

[Walter Roberson]

N = 3;
M = N * (N-1) / 2;
numgraph = 2^M;
choices = dec2bin(0:numgraph-1, M) - '0';
graphs = cell(numgraph,1);
used = 0;
for K = 1 : numgraph
  sq = squareform(choices(K,:));
  sq = tril(1-sq, -1) + triu(sq);
  if any(sum(sq,1)<1) || any(sum(sq,2)<1); continue; end
  used = used + 1;
  graphs{used} = digraph(sq);
end
graphs(used+1:end) = [];

[VeeVan]

Hello Walter Roberson,

This updated code DOES meet the diagonal elements equaling 0 requirement, however, now, it STILL doesn't meet the "there must be at least a single "1" in each row and column" if you see the graphs generated. Many of the matrices still have all 0 columns or rows within the matrix.

[VeeVan]

Is there anyway to alter this code in order to create an all zero diagonal? in addition to meeting the other requirements?:

N = 3;
M = N * (N-1) / 2;
numgraph = 2^M;
choices = dec2bin(0:numgraph-1, M) - '0';
graphs = cell(numgraph,1);
for K = 1 : numgraph
  sq = squareform(choices(K,:));
  sq = tril(1-sq) + triu(sq)
  graphs{K} = digraph(sq);
end

[Walter Roberson]

The tril(1-sq, -1) was the correction for the all zero diagonal. The version with tril(1-sq) without the -1 will always create an all-1 diagonal. If for some reason you did not want to use the -1 argument you could use the equivalent

sq = tril(1-sq) + triu(sq) - eye(N);

but this is not going to change whether or it it has the minimum 1 in row and column.

[VeeVan]

The reason it changes whether or not it has the minimum 1 in each row and column is due to the fact that the lack of "1"s in the diagonal prevent many rows and columns from having at least one within their column:

I.E.: For a 3 x 3 matrix

sq =

     1     1     1
     0     1     0
     0     1     1

would be turned into

     0     1     1
     0     0     0
     0     1     0

Hence, no "1" in the first column or second row.

[Walter Roberson]

Yes, I know. With the diagonal eye(3) in place, the minimum number for rows and columns would always be at least 1 no matter what the contents of the rest of the matrix. Not clearing the diagonal is not an option given condition #2.

[VeeVan]

These are the graphs that this code produces for a 3x3:

N = 3;

M = N * (N-1) / 2;

numgraph = 2^M;

choices = dec2bin(0:numgraph-1, M) - '0';

graphs = cell(numgraph,1);

for K = 1 : numgraph

sq = squareform(choices(K,:));
sq = tril(1-sq) + triu(sq) - eye(N)
graphs{K} = digraph(sq);
end

sq =

       0     0     0
       1     0     0
       1     1     0
  sq =

       0     0     0
       1     0     1
       1     0     0
  sq =

       0     0     1
       1     0     0
       0     1     0
  sq =

       0     0     1
       1     0     1
       0     0     0
  sq =

       0     1     0
       0     0     0
       1     1     0
  sq =

       0     1     0
       0     0     1
       1     0     0
  sq =

       0     1     1
       0     0     0
       0     1     0
  sq =

       0     1     1
       0     0     1
       0     0     0

We need to find a way to locate only the graphs that follow all of our rules.

[VeeVan]

Hello Walter Roberson,

Here is an update:

 N = 3;
M = N * (N-1) / 2;
numgraph = 2^M;
choices = dec2bin(0:numgraph-1, M) - '0';
graphs = cell(numgraph,1);
used = 0;
for K = 1 : numgraph
  sq = squareform(choices(K,:));
  sq = tril(1-sq) + triu(sq) - eye(N);
  if any(sum(sq,1)<1) || any(sum(sq,2)<1); continue; end
  used = used + 1;
  graphs{used} = digraph(sq);
end
graphs(used+1:end) = [];

This program, provided we remove the truncation on line 9 (;) give us these graphs:

if true
sq =

     0     0     0
     1     0     0
     1     1     0

sq =

     0     0     0
     1     0     1
     1     0     0

sq =

     0     0     1
     1     0     0
     0     1     0

sq =

     0     0     1
     1     0     1
     0     0     0

sq =

     0     1     0
     0     0     0
     1     1     0

sq =

     0     1     0
     0     0     1
     1     0     0

sq =

     0     1     1
     0     0     0
     0     1     0

sq =

     0     1     1
     0     0     1
     0     0     0
  end

As the graphs indicate, there are a few rows and columns without any "1" entries which is troublesome. Please provide an update and solution so that I can accept the answer.

[Walter Roberson]

Don't remove the ; from line 9. Line 9 is still in the process of building sq. sq is not completely built and validated until after the line

    if any(sum(sq,1)<1) || any(sum(sq,2)<1); continue; end

Any sq that fails that if, which expresses condition 3, will not get recorded.

[VeeVan]

How would I be able to display the graphs visually without removing the truncation?

[Walter Roberson]

You asked for graphs and I created graphs. plot() them. For example,

subplot(1,2,1);plot(graphs{1}); subplot(1,2,2);plot(graphs{2})

If you want to see the adjacency matrix, then disp(sq) after the 'if any' line.

[VeeVan]

Hello Walter Robertson, I was wondering how I can edit the code to allow for condition 4 to be that both A(1,2) & A(2,1) cannot equal 1, but that both can equal 0?

[Walter Roberson]

Yes, just write the appropriate "if" testing sq either immediately before or immediately after the line

    if any(sum(sq,1)<1) || any(sum(sq,2)<1); continue; end

[VeeVan]

Would this be correct:

N = 3;

M = N * (N-1) / 2;

numgraph = 2^M;

choices = dec2bin(0:numgraph-1, M) - '0';

graphs = cell(numgraph,1);

used = 0;

for K = 1 : numgraph

      sq = squareform(choices(K,:));

      sq = tril(1-sq) + triu(sq) - eye(N);

      if any (sum(sq,1)<0)|| any(sum(sq,2)<0; continue; end

      if any(sum(sq,1)<1) || any(sum(sq,2)<1); continue; end

      used = used + 1;

      disp(sq)

      graphs{used} = digraph(sq);

end

graphs(used+1:end) = [];

[Walter Roberson]

No. None of your entries are negative, so the sum of them cannot possibly be less than 0.

if sq(1,2)+sq(2,1) > 1; continue; end

[VeeVan]

I believe we were able to fix it?!?

N = 3;
M = N * (N-1) / 2;
numgraph = 2^M;
choices = dec2bin(0:numgraph-1, M) - '0';
graphs = cell(numgraph,1);
used = 0;
for K = 1 : numgraph
  sq = squareform(choices(K,:));
  sq = tril(1-sq) + triu(sq) - eye(N);
  if sq(1,2)+sq(2,1) > 1; continue; end
  if any(sum(sq,1)<1) || any(sum(sq,2)<1); continue; end;
  used = used + 1;
  disp(sq)
  graphs{used} = digraph(sq);
end
graphs(used+1:end) = [];

[VeeVan]

Hello Walter Robertson, When I asked if we can change condition 4 for new requirements, I meant can we change the condition from "Entries across the diagonal must be opposite" to "Entries across the diagonal cannot both equal one". I believe this current code only accounts for this rule on A(1,2) and A(2,1) specifically. I apologize for any miscommunication.

[Walter Roberson]

if any( (sq + sq.') > 1 ); continue; end