I'm interested in the equivalence relation $\sim$ on $m\times n$ binary matrices where $(a_{ij})_{ij}=A\sim A'$ if there exists one permutation for the rows and one for the columns of $A$ to make the two identical, i.e. there is $\sigma\in{\cal S}_m,\tau\in{\cal S}_n$ such that $(a_{\sigma(i)\tau(j)})_{ij}=A'$.

My questions:

(i) How can one effectively compute whether two given matrices belong to the same equivalence class?

(ii) How can one, given a finite class ${\cal M}$ of matrices, e.g. all $m\times n$ binary matrices, effectively generate a set of representations of ${\cal M}/\sim$, i.e. a set of matrixes which contains exactly one element in every equivalence class of ${\cal M}/\sim$?

  • $\begingroup$ I would recommend including everything from "My thoughts so far" downward into a self-answer to this question. As it stands you have the question combined with the answer, with the implied question "Is there a better answer?" $\endgroup$ – Wildcard Jan 5 '17 at 11:04
  • 1
    $\begingroup$ Done, thanks for the input. $\endgroup$ – fweth Jan 5 '17 at 11:06

My thoughts so far:

For any given matrix $A$ there is a function $f_A:{\cal P}([m])\to[n]$ (where $[m]$ denotes $\{1,\dots,m\}$) such that $f_A(X)$ is the size of the set $\{j\in[n]:\forall i\in X.a_{ij}=1\}$, i.e. the number of ones in the bitwise conjunction of the rows $A_i$ for $i\in X$. One can define the equivalence relation $f\sim^* f'$ whenever $f\circ(X\mapsto\{\sigma(i):i\in X\})=f'$ for some $\sigma\in{\cal S}_m$. Then whenever $A\sim A'$ we have $f_A\sim^*f_{A'}$ and my intuition says also vice versa. So (i) would reduce to study the equivalence relation $\sim^*$ and for (ii) one could ask which functions $f:{\cal P}([m])\to[n]$ actually yield a matrix $A$ with $f=f_A$.

Then I had another idea, one can just sort matrices lexicographically, interpreting them as concatenation of all their rows. I wrote a Haskell script to find the minimal $A'$ in $[A]_\sim$ w.r.t. this ordering, I don't know how efficient it is but it should be more efficient than brute forcing through all $\sigma$-$\tau$-combinations. Here foo is some helper function finding the minimal element out of all column only permutations of a given matrix, so getMinEqu is only brute forcing through the row permutations. It works by first ordering the columns such that the first row looks like [f,...,f,t,...,t] and then applying itself to the two submatrices sitting below the fs and below the ts.

import Data.List



getInd ks xs=[xs!!k|k<-ks]

getMinEqu xs=head$sort$map foo$permutations xs where
    foo []=[]
      =zipWith(++)((map(const f)falPos)
      :(foo$map(getInd falPos)$tail xs))
      ((map(const t)truPos)
      :(foo$map(getInd truPos)$tail xs))
      |otherwise=x:xs where
        n=length x
        falPos=elemIndices f x
        truPos=elemIndices t x

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.