2
$\begingroup$

We study equivalence classes of ternary matrices of size $m\times n$, where equivalence is defined via row permutations, column permutations, and negation of entire columns. Our goal is to define and efficiently compute a canonical representative for each equivalence class.

Let $\mathbb T=\{-1,0,1\}^{m\times n}$ denote the set of ternary matrices with $m$ rows and $n$ columns. Consider the group $\mathcal B$ of transformations acting on $\mathbb T$ generated by:

  • $\mathcal R$: permutations of rows
  • $\mathcal C$: permutations of columns
  • $\mathcal N$: negation of entire columns (e.g. multiplying entire columns by $-1$)

Transformations in $\mathcal R$ and $\mathcal C$ commute; likewise for $\mathcal R$ and $\mathcal N$. Transformations in $\mathcal C$ and $\mathcal N$ do not commute in general, but it can be shown that every transformation $B\in\mathcal B$ can be uniquely expressed as $B=R\circ C\circ N$ with $(R,C,N)\in\mathcal R\times\mathcal C\times\mathcal N$. Hence, the size of the group is: $$|\mathcal B|\,=\,|\mathcal R|\cdot|\mathcal C|\cdot|\mathcal N|\,=\,m!\cdot n!\cdot2^n$$

Is there a polynomial-time algorithm to find a canonical representative $\hat t$ of the equivalence class of a given $t\in\mathbb T$ under action of group $\mathcal B$ ?

Incidentally, how many such equivalence classes are there?

Motivation: when $t$ represents a boolean SATisfiability problem in Conjunctive Normal Form with $m$ clauses and $n$ variables, transformations in $\mathcal B$ do not change satisfiability. Applying a random such transformation is easy and sometime used to randomize a problem.

$\endgroup$
2
  • 1
    $\begingroup$ Sorry but what do you mean by negation? Multiply by $-1$? To compute the class, studying the sabiliser of well chosen matrices seems like a good idea $\endgroup$ Commented Aug 22 at 10:38
  • $\begingroup$ @julio_es_sui_glace: I clarified. If I get it correctly, the stabilizer of $t$ for a transformation in $\mathcal N$ thus would be negation of columns restricted to those columns that are all-zero in $t$. I also see what stabilizers of $t$ for transformation in $\mathcal R$ or $S$ would be. Pardon me but I do not see how to proceed. $\endgroup$ Commented Aug 22 at 10:52

1 Answer 1

Reset to default
4
$\begingroup$

This is as hard as graph isomorphism, and a polynomial-time canonical form algorithm is not known.

First, note that for matrices with entries in $\{0, 1\}$ the transformations in $\mathcal{N}$ are useless, in the following sense: for two matrices $A, B \in \{0, 1\}^{m \times n}$ we have $B = RACN$ with $R, C$ permutation matrices and $N$ diagonal with entries from $\{\pm1\}$ if and only if $B = RAC$. Indeed, $B$ and $RAC$ have entries in $\{0, 1\}$, so if $B = RAC \cdot N$, then $N$ acts with $-1$ only on zero columns, and can be replaced with identity.

Now, two graphs are isomorphic if and only if their incidence matrices are equivalent under permutation of rows and columns. Incidence matrices have entries in $\{0, 1\}$, so if we have the canonical form algorithm for the equivalence in the question, then by applying it to incidence matrices of two graphs and comparing canonical forms we can solve graph isomorphism.

Conversely, any bipartite graph isomorphism canonical form algorithm can be adapted for your problem: first apply the algorithm to the binary matrices which do not distinguish between $+1$ and $-1$, and then flip columns in such a way that the first nonzero entry in every column is positive.

$\endgroup$
3
  • $\begingroup$ The method in the last paragraph is spot on, and very much simplifies the problem, thank you. We only need to study transformation of binary matrices under row permutations and column permutations; and these two actions commute. $\endgroup$ Commented Aug 22 at 11:26
  • 3
    $\begingroup$ Suppose you have your algorithm. Apply in to the incidence matrices of two graphs. The graphs are isomorphic if and only if their canonical forms coincide. I'll try to expand the answer later when I have more time. $\endgroup$ Commented Aug 22 at 11:50
  • 1
    $\begingroup$ I tried to clarify the answer a bit. $\endgroup$ Commented Aug 23 at 10:19

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.