15
$\begingroup$

I am trying to construct all inequivalent $8\times 8$ matrices (or $n\times n$ if you wish) with elements 0 or 1. The operation that gives equivalent matrices is the simultaneous exchange of the i and j row AND the i and j column. eg. for $1\leftrightarrow2$ \begin{equation} \left( \begin{array}{ccc} 0 & 0 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 0 \end{array} \right) \sim \left( \begin{array}{ccc} 1 & 0 & 1 \\ 0 & 0 & 0 \\ 0 & 1 & 0 \end{array} \right) \end{equation}

Eventually, I will also need to count how many equivalent matrices there are within each class but I think Polya's counting theorem can do that. For now I just need an algoritmic way of constructing one matrix in each inequivalence class. Any ideas?

Improve this question
$\endgroup$
9
  • 2
    $\begingroup$ There are at least $2^{64}/8! \geq 2^{48}$ of these. That's a really large number. $\endgroup$
    – Yuval Filmus
    Commented Dec 25, 2013 at 1:05
  • $\begingroup$ @Yuval : These are indeed large numbers and for my calculation it really makes a difference if it's $2^{48}$ or $2^{52}$. It could take weeks more to run! This is the reason I am trying to use all the symmetries of the problem at hand. As an aside, this problem originates from model building in String Theory! :) $\endgroup$
    – Heterotic
    Commented Dec 27, 2013 at 10:07
  • $\begingroup$ What do you intend to do with all these matrices? Where are you going to store them? What's the application? $\endgroup$
    – Yuval Filmus
    Commented Dec 27, 2013 at 12:24
  • 1
    $\begingroup$ idea: isnt this very similar to graph isomorphism problem? where matrices are graph edge matrices? except those are symmetric... maybe can be leveraged somehow, there is tons of theory on that... $\endgroup$
    – vzn
    Commented Aug 31, 2014 at 15:13
  • 2
    $\begingroup$ math.stackexchange.com/questions/924745/… $\endgroup$
    – orezvani
    Commented Sep 9, 2014 at 12:35

1 Answer 1

Reset to default
1
$\begingroup$

I have made some progress towards answering this question. I am posting here in case anyone else is interested and also because this construction might have some usefulness for (directed) graphs.

Count the number of 1s in each row. Let $a_0$ be the number of rows with zero 1s, $a_1$ the number of rows with one 1 and so on up to $a_8$ which is the number of rows that have eight 1s. Obviously $\sum a_i=8$. The proposed parametrization that I have come to after trial and error is: $$(a_1,\cdots, a_8; T, S)$$ where T is the trace of the matrix and S is $1$ if the matrix is symmetric and $0$ otherwise. T runs from $0$ to $\sum_{i=1}^8 a_i=8-a_0$.

From my trials and errors it looks like that if two matrices are different in this parametrization then they belong to different equivalence classes, so to construct a representative in each class we just scan through the space of parameters as described above.

(Update) It turns out that this parametrization works fine for n=2 but not for n=3 as it can be seen by a brute force calculation. I still think it provides some insight on the structure of the answer and I invite people to try and modify/extend it to cover the most general case.

Improve this answer
$\endgroup$
7
  • 2
    $\begingroup$ It would be surprising and interesting if this worked. I don't see any obvious reason why this should be sufficient (i.e., why we're guaranteed that if two matrices have the same parameters, then they will be in the same equivalence class). Without some proof, I am skeptical. As a starting point, you could try verifying this conjecture on smaller matrices ($1 \times 1$, $2\times 2$, ..., $7 \times 7$) exhaustively. A better test would be to try using a SAT solver to look for counterexamples to your conjecture. $\endgroup$
    – D.W. ♦
    Commented Dec 30, 2013 at 0:47
  • $\begingroup$ @D.W. : Indeed it is the proof that this condition is sufficient that troubles me and the one I would like some help with. I'll try verifying it exhaustively for the smaller cases and see what happens. Thanks for the advice! Unfortunately, I have no idea how to use a SAT solver to look for counterexamples. If the conjecture, holds for the smaller matrices, I might start learning about it... $\endgroup$
    – Heterotic
    Commented Dec 30, 2013 at 11:06
  • $\begingroup$ Makes sense, Heterotic! Actually, I take back my statement about using a SAT solver. I don't know how to use a SAT solver to look for counterexamples, either (it's harder than I thought at first) -- so please ignore that part of my comment. Sorry about that! $\endgroup$
    – D.W. ♦
    Commented Dec 31, 2013 at 6:03
  • 2
    $\begingroup$ There are unequivalent matrices with the same parametrization. Note that by changing the $a_i$ to count the 1's in the columns you also get a parametrization that is invariant under the equivalence operation. From this we can conclude that the matrices with 1's in $(1,4)$ and $(2,3)$ resp. in $(1,4)$ and $(2,4)$ (all remaining entries 0 for both) are not equivalent but have the same parametrization. (Of course this immediately leads to an improved parametrization that also takes the columns into account.) $\endgroup$
    – FrankW
    Commented Jan 28, 2014 at 23:38
  • 1
    $\begingroup$ Heterotic, now that you know your answer doesn't work, I'd suggest deleting your answer so it doesn't confuse others... $\endgroup$
    – D.W. ♦
    Commented Jan 31, 2014 at 4:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.