<p>This problem is precisely the canonization problem for isomorphism of bipartite undirected graphs. While the lexicographically maximum form may be harder, <em>any</em> 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).</p>

<p>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.</p>

CC BY-SA 3.0
2016-04-06T22:39:38.553Z
Thanks for the answer. I have to think about this. Do you know if the triangulization problem or equivalently two processor scheduling problem which was asked about [here](http://mathoverflow.net/questions/191963/transforming-a-binary-matrix-into-triangular-form-using-permutation-matrices) is also GI-hard or is this still unknown?
0123456789
CC BY-SA 3.0
2016-04-06T20:22:03.213Z
2016-04-06T20:22:03.213Z
Joshua Grochow
<p>This kind of problem has been studied, e.g. in the exploitation of symmetries in model-checking and in satisfaction constraint problems.</p>

<p>The short answer is that it is $NP$-hard.</p>

<p>I suggest this draft by Junttila as a starting point: <a href="https://users.ics.aalto.fi/tjunttil/publications/orbit.ps" rel="nofollow">A note on the computational complexity of a string orbit problem</a>.
It addresses the complexity question (in the subcase of vectors), and references important related work.</p>

CC BY-SA 3.0
2016-04-06T15:45:12.640Z
Wow, thanks for the link. I have read the draft, but it only proves that the general problems Constructive String Orbit (CSO), where the group that acts on the strings is part of the input and could be any group is $FP^{NP}$ complete and the same for the decision problem variant CSO(D) which is NP complete because Max-Clique can be reduced to it. The group that is used in the proof isn't the same as mine. It applies the same permutation of row and column, whereas in my group rows and columns can be permuted independently from each other. Does that make a difference?
0123456789
CC BY-SA 3.0
2016-04-06T06:24:32.903Z
2016-04-06T06:24:32.903Z
Boson
<p>$O(p!)$ where $p$ is the largest prime less than or equal to $n$. <a href="https://oeis.org/A186202" rel="nofollow">https://oeis.org/A186202</a></p>

<p>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).</p>

CC BY-SA 3.0
2016-04-06T07:16:43.440Z
Cool. Although p would be at least n/2 then, because there is always a prime between n and 2n. Do you have a link to the algorithm?
0123456789
CC BY-SA 3.0
2016-04-06T12:39:08.283Z
Test one non-trivial member of each prime period permutation in parallel.
Chad Brewbaker
CC BY-SA 3.0
2016-04-06T06:26:10.640Z
2016-04-06T06:36:45.613Z
2016-04-06T06:36:45.613Z
Chad Brewbaker
<p>Consider the equivalence relation $\sim$ on boolean matrices $A,B\in\{0,1\}^{m\times n}$ which is defined as follows:</p>

<p>$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$ </p>

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

<p>A <strong><em>canonisation function for $\sim$</em></strong> 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:</p>

<ol>
<li>$N(A)\sim A$ for every $A$</li>
<li>$A\sim B \Leftrightarrow N(A)=N(B)$ for all $A,B\in\{0,1\}^{m\times n}$</li>
</ol>

<p>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$.</p>

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

<p>$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)$)</p>

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

<p>$A&lt;_{lex}B$ iff $w_A&lt;_{llex}w_B$</p>

<p>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$.</p>

<p>Then $\mathrm{MaxLex}(A):=\max_{&lt;_{lex}} \{ B : A\sim B\}$</p>

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

<p>Now my questions are:</p>

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

<p>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 <a href="https://mathoverflow.net/questions/191963/transforming-a-binary-matrix-into-triangular-form-using-permutation-matrices">this posting</a> is in NP, but not known to be NP-hard nor in P.</p>

<cc.complexity-theory><ds.algorithms><matrices><boolean-matrix>
Canonisation of boolean matrices under row and column permutations
0123456789
# Canonisation of boolean matrices under row and column permutations

(Asked by: username_0 on 2016-04-06)

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](https://mathoverflow.net/questions/191963/transforming-a-binary-matrix-into-triangular-form-using-permutation-matrices) is in NP, but not known to be NP-hard nor in P.

**Tags:** cc.complexity-theory, ds.algorithms, matrices, boolean-matrix


---

## 3 answers

### Answer by username_1 on 2016-04-06. Score: 5 | Accepted answer

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.

> **Comments:**
> **username_0**: Thanks for the answer. I have to think about this. Do you know if the triangulization problem or equivalently two processor scheduling problem which was asked about [here](http://mathoverflow.net/questions/191963/transforming-a-binary-matrix-into-triangular-form-using-permutation-matrices) is also GI-hard or is this still unknown?  

---

### Answer by username_2 on 2016-04-06. Score: 1

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](https://users.ics.aalto.fi/tjunttil/publications/orbit.ps).
It addresses the complexity question (in the subcase of vectors), and references important related work.

> **Comments:**
> **username_0**: Wow, thanks for the link. I have read the draft, but it only proves that the general problems Constructive String Orbit (CSO), where the group that acts on the strings is part of the input and could be any group is $FP^{NP}$ complete and the same for the decision problem variant CSO(D) which is NP complete because Max-Clique can be reduced to it. The group that is used in the proof isn't the same as mine. It applies the same permutation of row and column, whereas in my group rows and columns can be permuted independently from each other. Does that make a difference?  

---

### Answer by username_3 on 2016-04-06. Score: 0

$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).

> **Comments:**
> **username_0**: Cool. Although p would be at least n/2 then, because there is always a prime between n and 2n. Do you have a link to the algorithm?  
> **username_3**: Test one non-trivial member of each prime period permutation in parallel.  

---

