Generating a matrix of 0s and 1s with constrained domains

Hi all,

I'd like to generate an n x n matrix of 0s and 1s with the constraint that the number of domain walls is equal to m. I define a domain wall by isolating the 1s in the matrix and then counting how many of its adjacent partners (left, right, up, down) are 0. The only way I can think of doing this so far is just iterating over all 2^(n*n) possible matrices and then picking out the right ones but I'm wondering if there is some pattern that I can exploit here. If it helps, we can assume periodic boundary conditions so that the edges of the matrix are connected to each other.

Any thoughts appreciated!

[Torsten]

Can you give an example ? I don't understand how you count the number of domain walls of an nxn matrix made up of 0s and 1s.

[DGM]

I misread this on the phone earlier. I assumed that the goal was to just count the empty 4-neighbors like so:

% the filter (the four-neighbors only)
fk = [0 1 0; 1 0 1; 0 1 0];

% the input
A = [1 0 0 0 0;
    0 0 1 1 1;
    1 1 1 1 1;
    1 1 1 1 0;
    0 0 0 0 0];

% circular padding (periodic boundary condition)
Ap = padarray(1-A,[1 1],'circular','both');

% apply the filter to the padded array
B = conv2(Ap,fk,'valid').*A

B = 5×5

4 0 0 0 0 0 0 2 1 2 1 1 0 0 1 2 1 1 2 0 0 0 0 0 0

<mw-icon class=""></mw-icon>

<mw-icon class=""></mw-icon>

With this interpretation, m is an integer between 0 and 4. The problem is that I'm not sure that "empty neighbors" and "domain walls" are the same thing here or if there's something else involved. Of the three responses here, it seems there are three interpretations of what was meant.

I also completely missed the point that we're trying to generate the array instead of just analyze it -- but there aren't any other constraints given. Surely there are other constraints, and there's not much point starting to solve that problem until they're known.

[bil]

Ah sorry, I should have been more specific by my definition of a domain wall. If you write out your matrix and imagine drawing lines separating 0s and 1s, then each of those lines counts as a wall. So we can isolate the 1s in our matrix and just ask how many of its neighbors are 0s. For example, something like [0,0,0;0,1,0;0,0,0] will have 4 domain walls because all 4 nearest neighbors for the 1 are zero. The periodic boundary conditions is just to address the edges and corner elements. I don't have any other constraints, I was hoping to just write a function that would take an input number of domain walls and then spit out a matrix that has that many domain walls, nothing else.

[Torsten]

So the number of domain walls is the sum of all instances where a zero is adjacent to a one in your definition ?

Answer 1

[Umar]

Hi @bil,

You mentioned, “I'd like to generate an n x n matrix of 0s and 1s with the constraint that the number of domain walls is equal to m. I define a domain wall by isolating the 1s in the matrix and then counting how many of its adjacent partners (left, right, up, down) are 0. The only way I can think of doing this so far is just iterating over all 2^(n*n) possible matrices and then picking out the right ones but I'm wondering if there is some pattern that I can exploit here. If it helps, we can assume periodic boundary conditions so that the edges of the matrix are connected to each other.Any thoughts appreciated!”

Please see my response to your comments below.

To efficiently generate the matrix with the specified number of domain walls, you can utilize combinatorial design rather than brute force. One approach is to construct the matrix iteratively while keeping track of the number of domain walls. Here are steps for implementation, Start with a zero matrix. Add 1s in such a way that each addition either creates a new domain wall or maintains existing ones. After each addition, check if the total number of domain walls matches m. If it exceeds m, backtrack and adjust placements. Make sure that when checking neighbors for domain walls, you consider wrapping around the edges. Here is a MATLAB function that generates such a matrix while ensuring that the number of domain walls equals m.

function matrix = generateMatrixWithDomainWalls(n, m)
  % Initialize an n x n zero matrix
  matrix = zeros(n);

    % Function to calculate current number of domain walls
    function numWalls = countDomainWalls(mat)
        numWalls = 0;
        for i = 1:n
            for j = 1:n
                % Check right neighbor (with periodic conditions)
                if mat(i,j) == 1 && mat(i, mod(j,n)+1) == 0
                    numWalls = numWalls + 1;
                end
                % Check down neighbor (with periodic conditions)
                if mat(i,j) == 1 && mat(mod(i,n)+1,j) == 0
                    numWalls = numWalls + 1;
                end
            end
        end
      end

      % Randomly place ones until we reach desired wall count
      while true
        % Randomly fill the matrix with ones and zeros
        matrix = randi([0, 1], n, n);

        % Count the current number of domain walls
        currentWalls = countDomainWalls(matrix);

        % If it matches m, break; otherwise, repeat
        if currentWalls == m
            break;
        end
    end

    disp('Generated Matrix:');
    disp(matrix);
    disp(['Number of Domain Walls: ', num2str(countDomainWalls(matrix))]);
  end

% Example usage:
n = 5; % Size of the matrix
m = 8; % Desired number of domain walls
generateMatrixWithDomainWalls(n, m);

So, in the above code, my method uses random generation until a valid configuration is found, which may not be optimal for large matrices or high values of m. Further optimizations could involve backtracking or more intelligent placements based on existing configurations. Also, when you try to experiment with different values of n and m, you might notice certain statistical properties emerge regarding how densely packed the ones are relative to their adjacency constraints. However, by implementing this approach, you should be able to generate matrices efficiently while satisfying your constraints on domain walls. Feel free to modify and expand upon this code according to your specific needs!

Please let me know if you have any further questions.

[Umar]

Hi @bil,

Please let me know if my answer helped resolve your query. If you are still facing issues, let me know to assist you further.

Answer 2

[John D'Errico]

Are you saying you want to break the matrix into a set of regions, where within the region, the matrix contains zeros, and the region is wholly bounded by elements that are 1? Making it worse, not easier, is you also want the matrix to be connected in a periodic way, so the right and left and top and bottom elements are seen as touching each other.

For example, it seems, based on what I hear, that the matrix:

M = [0 0 0 0 0;0 1 1 1 0;0 1 0 1 0;0 1 1 1 0;0 0 0 0 0]

Has 2 domains, with one wall splitting them apart, so one domain inside the wall, and the second domain outside the wall.

Then logically M2 has only 1 domain, since all zero elements are connected.

M2 = [0 0 0 0 0;0 1 0 1 0;0 1 0 1 0;0 1 1 1 0;0 0 0 0 0]

A question very confusingly stated.

If I am correct however in my understanding, then you can form a graph from any such matrix. For an nxn matrix, the graph will have n^2 elements. Two nodes are connected if and only if they are both zero, and they are adjacent to each other (horizontally or vertically.) Now, using the CONNCOMP utility, it should give you a list of all connected components.

You should also be able to use the graph tools to identify all closed walls, since they will form a cycle.

However, building such a matrix, with the constraint that there are exactly m walls will be far more difficult, as there can easily be some fairly complex structures you could create, with connected walls. We have heard only a very vague statement about what properties a "wall" can have.

[Umar]

Hi @ John D'Errico,

Your understanding of the matrix domain problem is indeed correct. In MATLAB, you can represent the matrix as a graph where nodes correspond to zero elements, and edges connect adjacent zeros. The conncomp function from the MATLAB graph toolbox can effectively identify connected components, allowing you to discern distinct domains.

For example, consider the following MATLAB code snippet to analyze the matrix:

M = [0 0 0 0 0; 0 1 1 1 0; 0 1 0 1 0; 0 1 1 1 0; 0 0 0 0 0];
[row, col] = find(M == 0); % Find zero elements
G = graph(); % Create an empty graph

% Add edges for adjacent zeros
for i = 1:length(row)
  for j = -1:1:1
      for k = -1:1:1
          if abs(j) ~= abs(k) % Ensure horizontal or vertical             adjacency
              continue;
          end
          neighbor_row = row(i) + j;
          neighbor_col = col(i) + k;
          if neighbor_row > 0 && neighbor_row <= size(M, 1) && 
          ...
             neighbor_col > 0 && neighbor_col <= size(M, 2) && 
             ...
             M(neighbor_row, neighbor_col) == 0
              G = addedge(G, sub2ind(size(M), row(i), col(i)), 
               ...
                          sub2ind(size(M), neighbor_row, 
                          neighbor_col));
          end
      end
  end
end

% Find connected components
components = conncomp(G);
disp(components);

Please see attached.

This code constructs a graph from the matrix and identifies connected components, effectively addressing your query. However, creating a matrix with a specific number of walls introduces complexity, as it requires careful design to maintain connectivity while adhering to the wall constraints. I do agree with you that further clarification on the properties of walls would be beneficial for a more tailored solution.

You are extremely knowledgeable and I do respect and appreciate your knowledge being shared with all of us. Great teamwork.