Canonisation of boolean matrices under row and column permutations

Question

Consider the equivalence relation $\sim$ on boolean matrices $A,B\in\{0,1\}^{m\times n}$ which is defined as follows:

$A\sim B$ :iff there are permutation matrices $P\in\{0,1\}^{n\times n}, Q\in\{0,1\}^{m\times m}$, so that $B=QAP$

In other words two matrices are equivalent, if they are equal up to permutation of rows and columns.

A canonisation function for $\sim$ is any function $N$ on the set of all boolean matrices with $N(A)\in \{0,1\}^{m\times n}$ for all $m,n\geq 1$ and $A\in \{0,1\}^{m\times n}$ with the following two properties:

1. $N(A)\sim A$ for every $A$
2. $A\sim B \Leftrightarrow N(A)=N(B)$ for all $A,B\in\{0,1\}^{m\times n}$

Now i want to find a canonisation function for $\sim$ that is most efficiently computable. One possible canonisation function is the function $\mathrm{MaxLex}$ which maps every matrix $A$ to the lexicographically largest $B$ that is equivalent to $A$.

For this i first define a linear order on bitvectors as follows: For $b,c\in\{0,1\}^k$

$b<_{llex} c$ iff: the number of ones in $c$ is larger than in $b$ or ($b$ and $c$ have the same number of ones and $b(i)>c(i)$ for the first index $i$ with $b(i)\neq c(i)$)

Then a lexicographic order $<_{lex}$ on matrices of equal dimension is defined as follows:

$A<_{lex}B$ iff $w_A<_{llex}w_B$

where $w_X=X(1,-)X(2,-)\ldots X(m,-)\in\{0,1\}^{mn}$ denotes the bit vector that results from the concatenation of the rows $X(i,-)$ of $X$.

Then $\mathrm{MaxLex}(A):=\max_{<_{lex}} \{ B : A\sim B\}$

I have found a simple recursive algorithm that computes $\mathrm{MaxLex}$, which has however a worst case runtime of $\mathcal{O}(m!)$.

Now my questions are:

1. Is there a more efficient algorithm that computes $\mathrm{MaxLex}$ than my $\mathcal{O}(m!)$ algorithm?
2. Is there a polynomial time algorithm that computes $\mathrm{MaxLex}$
3. Is there a canonisation function for $\sim$ that is computable in polynomial time?
4. Is anything known about the computational complexity of this problem?

I am thankful for any tips, pointers or comments. I have already googled this problem but couldn't find anything. The only thing i found which resembles this is the decision problem of whether a boolean matrix is equivalent to a triangle matrix, which according to this posting is in NP, but not known to be NP-hard nor in P.

Answer 1

This problem is precisely the canonization problem for isomorphism of bipartite undirected graphs. While the lexicographically maximum form may be harder, any canonical form will be GI-hard (and so, in particular, it doesn't matter whether the $P$ and $Q$ are restricted to satisfy $P=Q^{-1}$ or not, as asked in a comment above).

In particular, there is a canonization procedure that takes only $2^{\tilde{O}(\sqrt{n})}$ time (much better than $n! \sim 2^{\Theta(n \log n)}$), by Babai-Luks 1983, though in practice I'd recommend just using nauty.

Answer 2

This kind of problem has been studied, e.g. in the exploitation of symmetries in model-checking and in satisfaction constraint problems.

The short answer is that it is $NP$-hard.

I suggest this draft by Junttila as a starting point: A note on the computational complexity of a string orbit problem. It addresses the complexity question (in the subcase of vectors), and references important related work.

Answer 3

$O(p!)$ where $p$ is the largest prime less than or equal to $n$. https://oeis.org/A186202

MAXLEX is equivalent to MAX-CLIQUE if you read the entries starting at the upper left and read them in an increasing frontier (and put 1's down the main diagonal).