3

I am working on a problem which requires me to find all 6x6 (0,1) matrices with some given properties:

  • The sum of a row/column must be lower than 2.
  • The matrices are not symmetrical.

I am using this code:

import numpy as np
import itertools as it

n=6
li=[]

for i in it.product([0, 1], repeat = n**2):

  if (np.reshape(np.array(i), (n, n)).sum(axis=1)  < 2).all() and (np.reshape(np.array(i), (n, n)).sum(axis=0)< 2).all() :
    if (np.transpose(np.reshape(np.array(i), (n, n))) != np.reshape(np.array(i), (n, n))).any():

      li.append(np.reshape(np.array(i), (n, n)))

The problem is that this method has to go through all 68719476736 (0,1) matrices. After this piece of code I still have to impose extra conditions.

Is there a faster algorithm to find this list of matrices?

Edit: The problem I am working on is one to find unique adjacency matrices (graph theory) up to a certain equivalence class. For instance, in the 4x4 version of the problem I wanted to find all (0,1) matrices such that:

  • The sum in a row/column is lower than 2;
  • Are not symmetrical, i.e. A^T != A;
  • Also A^T != P^T A P, where P is a matrix representation of the dihedral group D8 (order 8) which is a subgroup of S4.

After this last step I get a certain number of matrices. If A relates to B through the relation B = P^T A P, then it represents the same matrix. I follow to choose only one representative of this equivalence class.

In the 4x4 problem I go from 65536 to 3.

My estimate of the result after sorting through the first condition (sums) is 46080. In the 6x6 problem, the group of transformations P is of order 48.

M.Π.B
  • 77
  • 6
  • 1
    I don't have time to work this out, but I suspect starting with a valid matrix and finding permutations of it may be significantly faster. – user2699 Jul 23 '18 at 17:45
  • 1
    Maybe you can take some tips from this somewhat similar question: https://stackoverflow.com/questions/47019047/algorithm-for-equiprobable-random-square-binary-matrices-with-two-non-adjacent-n/47192852 – m69's been on strike for years Jul 23 '18 at 17:54
  • 3
    Could you explain some of the details a little more? The title says less than 2, the question says less than or equal to two. What symmetries are to be avoided? And maybe explain the extra conditions you'll be imposing later on; it may be useful to incorporate them into this step of the algorithm. – m69's been on strike for years Jul 23 '18 at 17:57
  • The problem does not look like a good match for python/numpy because, if optimized, it requires looking at individual matrix elements. C/C++ would be a much better choice. – DYZ Jul 23 '18 at 17:59
  • 2
    @m69's link just obviated most of the answer I was posting. Nice work! Once you have a "saturated" matrix (every row & col sums to 2), you get the other solutions by flipping '1' entries. I recommend using some dynamic programming to avoid duplicating effort on unsaturated matrices. You still need a filter to avoid the symmetries you want to exclude. – Prune Jul 23 '18 at 17:59
  • I take it that there is no requirement that each row/column must contain a one is there? – Mad Physicist Jul 24 '18 at 15:25
  • 2
    Just edited some of the valid complaints you had. – M.Π.B Jul 24 '18 at 15:39
  • @M.Π.B Just to clarify the constraint about the dihedral group: are you saying that you are only interested finding one instance of matrix from the group and ignore all others? – jdowner Jul 24 '18 at 15:47
  • Are there more than 4 of them (zero arcs, one arc, two arcs, three arcs with distinct endpoints)? – David Eisenstat Jul 25 '18 at 16:35
  • 1
    @jdowner yes I am. Basically there is an equivalence class of matrices and I am interested in one representative of this set. This is much like isomorphisms between graphs. There can be two matrices that represent the same graph. This also involves sorting lists of matrices which is another painful subject for me. – M.Π.B Jul 26 '18 at 15:09
  • @DavidEisenstat I don't think I understand your question. I consider all of the adjacency matrices that have the properties above. – M.Π.B Jul 26 '18 at 15:25
  • Let me ask differently: can you construct more than four pairwise 6x6 non-isomorphic matrices by hand? – David Eisenstat Jul 26 '18 at 16:22
  • Yes I can. I can find various solutions by hand to this problem, just not all as it would not be feasible. – M.Π.B Jul 26 '18 at 19:23

1 Answers1

2

You have trouble with your math, because if the row/column sum is less than 2, it could be 0 or 1 -- that means that in every row/column can be only one non-zero elememt, which is 7^6 = 117649 possible matrices.

100k matrices is pretty much doable by using a brute force, with additional filtering to remove vertical/horizontal flips and diagonal symmetries.

Here's a simple code that should get you started:

import numpy as np
from itertools import permutations

for perm in permutations( range(7), 6 ) :  # there are only 5040 permutations
    m = np.zeros(6, 6)        # start with an empty matrix
    for i, j in enumerate(perm) :
        if j == 6 : continue  # all zeros
        m[i][j] = 1           # put `1` in the current (i)-th row, (j) pos

        # here you check `m` for symmetry and save it somewhere or not
lenik
  • 23,228
  • 4
  • 34
  • 43
  • @MadPhysicist sure, have a go at it =) – lenik Jul 24 '18 at 15:31
  • My math was of all (0,1) 6x6 matrices, with no extra conditions. My problem is exactly how to not generate all of these before conditions as this is taking forever to compute. – M.Π.B Jul 24 '18 at 15:41
  • 1
    @M.Π.B you should use conditions and limitations to your advantage. if you know there could be only one non-zero element in the row/column -- that simplifies things quite a lot: take a `1` and start moving it along the first row, take another `1` and start moving it along the second row, and so on... there are only 7 positions for every row (6 when it's in your matrix, and #7 is when all elements are zero). – lenik Jul 24 '18 at 15:45
  • @lenik I should apologize as I know plenty of ways of computing this by hand (which would take forever nevertheless) but I am a complete amateur programming. It is true what you said, but nevertheless, how do I do it? I am very limited in working with numpy/python. – M.Π.B Jul 24 '18 at 15:51
  • @M.Π.B i have added some code to the answer, please, take a look at it? – lenik Jul 24 '18 at 16:01
  • Had to change permutations( range(7), 7 ) to permutations( range(7), 6 ) for it to work. This gives me an example of a 6x6 matrix with such condition – M.Π.B Jul 24 '18 at 16:35
  • @M.Π.B yeah, right. caught again by "off-by-one" =) – lenik Jul 25 '18 at 00:26
  • Thank you for your help. This actually got me a lot closer to solve my problem. – M.Π.B Jul 25 '18 at 14:55