MATLAB: How do I generate all square matrices (nxn) which meet these requirements?

How do I generate all square matrices which meet these requirements:

-All entries are either a 0 or 1

-All diagonal entries are 0

-At least a single "1" in each row and column

-Opposite Transposal Entries: IE if A(1,2) = 1, then A(2,1) = 0

[OCDER]

Homework? If yes, read:

https://www.mathworks.com/matlabcentral/answers/8626-how-do-i-get-help-on-homework-questions-on-matlab-answers

[VeeVan]

No, this isn't homework. Thank you though!

[OCDER]

Interesting. What's this for? I can't figure out where this matrix will be used for in real life...

[VeeVan]

This square matrix would be used for graph theory applications. Specifically, creating an adjacency matrix with no self loops, no double lines, all nodes connected, and no cyclical connections.

Answer 1

[OCDER]

N = 10;
Mat = tril(ones(N), -1);
Idx = find(Mat); %This gives you the index of a lower triangle. choose k = 1:sum(Mat) of these to permute and test condition 3
Mat(2:N+1:end) = Mat(N+1:N+1:end);
Mat(N+1:N+1:end) = 1;

Hm, I can't think of an obvious way to figure out all the permutations of these 1 and 0 that satisfies condition 3. But due to condition 4, you cannot have any more/less 1's than the current matrix given. So try flipping positions of output

 Mat(x,y) <=> Mat(y,x)  for y ~= x

and check if flipping the 1 and 0 still satisfies condition 3

 if all(any(Mat, 1)) && all(any(Mat, 2))
   disp('this is a valid permutation')
 end

you might have to use nchoosek to figure out how many combinations of flips are possible when you flip k = 1, 2, 3, .... (# of 1's) positions.

Answer 2

[Image Analyst]

How about this:

n = 5;
output = triu(ones(n,n), 1)

output =
     0     1     1     1     1
     0     0     1     1     1
     0     0     0     1     1
     0     0     0     0     1
     0     0     0     0     0

It meets your criteria I believe.

[OCDER]

The bottom row and 1st column doesn't have any 1.

"-At least a single "1" in each row and column"

[VeeVan]

Hello! Thank you for answering.

The first column and last row doesn't have a single "1" entry, therefore it doesn't meet that requirement.

Also, how can we generate All matrices with those properties?

Thank you again for the answer!

[OCDER]

n = 5;
output = triu(ones(n,n), 1);
output(2:n+1:end) = output(n+1:n+1:end);
output(n+1:n+1:end) = 0;

[VeeVan]

Hey OCDER, Thanks a lot! I believe this should work. However, how do I make it produce ALL Graphs that meet these requirements? Like, how would I make it create all graphs and possibly store these graphs?

[VeeVan]

Also does this adjust for "at least" meaning there can be more than a single "1" per row and column?

[OCDER]

Hm, I can't think of an obvious way to figure out all the permutations of these 1 and 0 that satisfies condition 3. But due to condition 4, you cannot have any more/less 1's than the current matrix given. So try flipping positions of output

output(x,y) <=> output(y,x)  for y ~= x

and check if flippling the 1 and 0 still satisfies condition 3

if all(any(output, 1)) && all(any(output, 2))
   disp('this is a valid permutation')
end

you might have to use nchoosek to figure out how many combinations of flips are possible when you flip k = 1, 2, 3, .... (# of 1's) positions.

[VeeVan]

Ok will do! Thanks again for answering. Also, would you like to post a formal answer so that I can accept it? (I don't know if this gives you a reward or anything like that)

[Image Analyst]

I think you at least have to specify the size of the square. How big is your square? 5 elements wide? A thousand?