Claim: $E, F$(using instead of $A, B$) are non-symmetric 0-1 matrices of
dimension $m \times n$ where $m>n$. Given $F \neq E$, it takes maximum maximum $O( \frac {m^{log_2(m)}} { 2^{\sum log_2(m)} })$ times to check whether $F \simeq E$ or not.
Proof:
For $1^{st}$ iteration, $E_1=E;m_1=m$.
Based on each row $e_i \in E_1$ ($1 \leq i \leq m_1$), $E_1$ can be divided into 4
sub matrices. It can be denoted as-
$E_{(1,i)}=
\left( \begin{array}{cc}I_i & J_i \\K_i & L_i
\\k_i & l_i\end{array}\right) $, where
$e_i=\left( \begin{array}{c}k_i & l_i \\
\end{array}\right) $; $l_i$ is a tuple of all 1's and $k_i$ is a tuple of all 0's .there are $m_1$ possible matrices like $E_{(1,i)}$. $E_{(1,i)}$ is a matrix of all possible $m_1$ matrix(for each row of $E_1$) at $1^{st}$ iteration.Here, $L_i$ is a zero matrix. Each row of $K_i$, does not have any 1 in the position of 1 of $e_i$ , $K_i$ is made of all such rows . Either $J_i$ has rows less than $m_1/2 $(when $L_i $ has rows more than $m_1/2 $) or $K_i$ has rows less than $m_1/2$ (when $L_i$ has rows less than $ m_1/2 $) . For
$2^{nd}$ iteration, as $E_2$, choose one of $K_i,J_i$ that has minimum number of rows; $m_2$= tolal
row of $E_2$ ,less than $ m_1/2 $. Repeat the process until $m_j <6$( or less than a number where $m_j!$ is sufficiently small to ignore) .
This recursive process can be run maximum $log_2{(m_1)}$ times. So, there could be
$ \frac {m^{log_2(m)}} { 2^{\sum log_2(m)} }$ matrices using above “Divide and Conquer” method. $\sum log_2(m)= \frac{ log_2(m)(log_2(m)+1)}{2}$.
For simplicity , it is assumed that $E_j$ has following properties-
(i) Each row, column has constant number of 1.
(ii) Each row is unique (No row is repeated in a set of rows /matrix),
assuming no partition obtained from column.
If $E_j$ does not have any of the above properties, the matrix can be
partitioned again until these 2 properties are attained.
Consider the case ,$E_1 \simeq F_1$ and $g(h(E_1))=F_1$, so $E_1 \neq F_1$
where $g$ is a permutation that acts on $n$ columns and $h$ is a permutation
that acts on $m$ rows, but $g, h$ do not act on $L_i$.
Since the rows of $K_i$ and columns of $J_i$ have not been permuted(when transforming $E_1$ to $F_1$), reordering columns of $K_i$ and rows of $J_i$
would make $E_1 = F_1$. These reordering can be done in polynomial time
following the order of $K_i$ , $J_i$ of $E_{(1,i)}$.
If $g,h$ act on $L_i$, then find all permutations of all columns (or rows) of $L_i$. For each of the column permutation, reorder rows(or columns if permutation of rows are used) exactly like $L_i$. This "row- reordering" is polynomial time. There are maximum $|l_i|!$ of column-permutation($|l_i|$=length of $l_i$ tuple), one of them must reorder the transformed matrix into $L_i$. Similarly, if permutations of rows are used then there are $m_j !$ permutations to check and reorder $L_i$.
Now, consider the set of all $ \frac {m^{log_2(m)}} { 2^{\sum log_2(m)} }$
matrices of the form $E_{(j,i)}$ ($m_j <6$ or less than a number where $m_j!$ is sufficiently small to ignore). For each $E_{(j,i)}$ (where $m_j=2$ , use this technique to reorder other matrices. Each $E_{(j,i)}$ can have maximum $2!$ permutation of column/rows. For each permutation, use the above technique. Thus, it will take $O( \frac {m^{log_2(m)}} { 2^{\sum log_2(m)} })$ times to check whether $F \simeq E$ or not. $\blacksquare$
