3
$\begingroup$

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 !

$\endgroup$
  • 3
    $\begingroup$ 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? $\endgroup$ – Yuval Filmus May 20 '16 at 13:59
  • $\begingroup$ @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$. $\endgroup$ – Jim May 20 '16 at 14:11
  • 1
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus May 20 '16 at 15:00
  • $\begingroup$ @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? $\endgroup$ – Jim May 20 '16 at 15:22
  • 1
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus May 21 '16 at 14:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.