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?

$\endgroup$
  • 2
    $\begingroup$ There are at least $2^{64}/8! \geq 2^{48}$ of these. That's a really large number. $\endgroup$ – Yuval Filmus Dec 25 '13 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 Dec 27 '13 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 Dec 27 '13 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 Aug 31 '14 at 15:13
  • 2
    $\begingroup$ math.stackexchange.com/questions/924745/… $\endgroup$ – orezvani Sep 9 '14 at 12:35
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.

$\endgroup$
  • 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. Dec 30 '13 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 Dec 30 '13 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. Dec 31 '13 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 Jan 28 '14 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. Jan 31 '14 at 4:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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