# How to determine Isomorphism of Non-Symmetric Matrix when Permutation-Set is given?

Consider, two $m \times n$ matrices $A, B$ such that there is a permutation $\kappa$ that such that such that $A^{\kappa}=B$ (Wielandt's notation), i.e. $A, B$ are isomorphic but not equal.

Since, permutations of rows are independent of permutations of columns, so $\kappa = \sigma \pi$ where $\sigma$ is a row permutation that acts on rows of non-symmetric matrix and $\pi$ acts on columns of matrix.

A set of column-permutations $\beta_k$ is a subset of the set of all possible permutations of columns of $A$. So, $\beta_k \subseteq S_n$.

A set of column-permutations $\gamma_k$ is a subset of the set of all possible permutations of columns of $B$. So, $\gamma_k \subseteq S_n$.

We consider 2 different set due to different labeling of columns in $A, B$ .

$\pi$ is in the set $\beta_k, \gamma_k$ but with different label.

Problem: $A,B, \beta_k, \gamma_k$ are given where $A \neq B$ and $\sigma$ is unknown.

How can we show that A and B are isomorphic using $\beta_k, \gamma_k$ ?

In other words, can we construct an algorithm to show $A, B$ are isomorphic?

Edit:

1. Consider that $\beta_k \subset S_n$ instead of $\beta_k \subseteq S_n$ where size of $\beta_k$ is not as big as exponential.

2. Note that we can $partition$ sets of permutation $\beta_k, \gamma_k$ based on $automorphism$ of matrices $A, B$.

Some help will be appreciated !

• What if $\beta_k = S_n$? Then you get bipartite graph isomorphism, which is GI-complete. Also, what do you mean by "construct an algorithm to show $A,B$ are isomorphic"? Do you mean an algorithm which finds $\kappa$ given the promise that it exists? – Yuval Filmus May 20 '16 at 13:59
• @YuvalFilmus , 1.yes then it is , GI complete. 2. " Do you mean an algorithm which finds κ given the promise that it exists?" - yes, thought we have no idea about $\kappa$, we only know about a set of column permutations, $\beta_k$ . because id you find the $\pi$ or a permutation that arranges columns of one matrix exactly like another, then you can find $\kappa$ or a permutation , that arranges rows of matrix exactly like $\kappa$. – Michael May 20 '16 at 14:11
• What do you mean by "the size of $\beta_k$ is not as big as exponential"? What exact bound do you have in mind? This is important, since by padding we can make $\beta_k$ much smaller than all of $S_n$ while not changing the problem at all. – Yuval Filmus May 20 '16 at 15:00
• @YuvalFilmus $|\beta_k|=|\gamma_k| \leq n^{\log(n)}$, I am actually not worried about size. I have a procedure to generate the permutation sets. In the procedure size varies from polynomial to quasipolynomial. I am more concerned about the algorithm/solution than the size. Please, note that you can $partition$ $\beta_k, \gamma_k$ based on automorphism of $A,B$. What kind of padding are you referring to? – Michael May 20 '16 at 15:22
• When the graphs are regular there is no unique columns. This approach can be improved, but has been shown not to work in general. I suggest reviewing the GI literature. – Yuval Filmus May 21 '16 at 14:19