Canonisation of boolean matrices under row and column permutations 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:


$N(A)\sim A$ for every $A$
$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&lt;_{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)&gt;c(i)$ for the first index $i$ with $b(i)\neq c(i)$)

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

$A&lt;_{lex}B$ iff $w_A&lt;_{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_{&lt;_{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:


Is there a more efficient algorithm that computes $\mathrm{MaxLex}$ than my $\mathcal{O}(m!)$ algorithm?
Is there a polynomial time algorithm that computes  $\mathrm{MaxLex}$
Is there a canonisation function for $\sim$ that is computable in polynomial time?
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.
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.