Isomorphism of Non-Symmetric Matrices

Question

$A, B$ are non-symmetric matrices of dimension $m \times n$ where $m=n$ or $m \neq n$.

Example: An example of $6 \times 3$ non-symmetric matrix is

$$ \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{pmatrix}. $$

$A \simeq B$ and $g(h(A))=B$ where

$g$ is a permutation that acts on $n$ columns and $h$ is a permutation that acts on $m$ rows.

Problem: How to construct a non exponential algorithm to test such isomorphism?

Note: I have an idea to construct such algorithm which is based on less rigorous argument. Therefore, I would like to have a formal (i.e. mathematically rigorous) solution .

Answer 1

Some quick (definitely true) observations:

• $A \cong B$ if and only if there are permutation matrices $P,Q$ such that $A = PBQ$.
• $A \cong B$ implies that $A$ and $B$ have the same total number of $1$s
• $A \cong B$ implies that $A$ and $B$ have the same rank.

Here's my first thought at an algorithm; I'm not sure whether it works. The fundamental idea I'm operating on is that given a matrix $A$, we should find an algorithm that selects a member of the equivalence class of $A$ (that is, a second matrix $M \cong A$) such that if $A \cong B$, the algorithm will produce the same matrix $M$ if either $A$ or $B$ are given as an input to the algorithm.

Start with your $A$, and sort the rows from top to bottom in numerical order, reading each row as a binary number. So, $$ A =\pmatrix{ 1&&\\ &1\\ &1&1\\ 1\\ &&1\\ &1} \to \pmatrix{ &&1\\ &1\\ &1\\ &1&1\\ 1\\ 1 } $$ Then, sort the columns in decreasing order from left to right (in this case, this means nothing happens).

The algorithm repeats this sort of row and column if the matrix is still not sorted by row and by column in this fashion. The algorithm terminates either when the matrix is sorted or when the same matrix is attained twice.

The output of the algorithm is the last matrix obtained.

There are probably several things wrong with this algorithm, but I thought it might be a useful staring point nevertheless.

Answer 2

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$

Answer 3

This is the bipartite graph isomorphism problem. This problem is known to be GI complete, so

to construct a non exponential algorithm to test such isomorphism

is exactly as difficult as to construct a non exponential algorithm for graph isomorphism. László Babai recently constructed such an algorithm for the first time...