2
$\begingroup$

This is related to graph isomorphism.

Here matrices are square $n \times n$ with non-negative integer entries.

Two matrices $A,B$ are permutation similar if there exist permutation matrix $P$ such that $P A P^T=B$.

Assume $A,B$ have $k$ distinct entries where $k$ is large.

Q1 What is the complexity of finding $P$ as function of $n,k$?

In graph isomorphism the matrices are $0-1$ with $k=2$.

I expect large $k$ to help.

Improve this question
$\endgroup$
2
  • $\begingroup$ If the diagonal entries are all distinct (so, e.g., if $k = n^2$) then this can be done in polynomial time by noticing that $PAP^T = B$ forces $A$ and $B$ to have the same diagonal entries (not necessarily in the same order) and there is only one permutation that could possibly work: the one that re-arranges the diagonal entries of $A$ to match the order of those of $B$. A similar argument gives a polynomial-time method for $k \geq n^2 - c$, where $c$ is constant. $\endgroup$
    – Nathaniel Johnston
    Commented Jun 9, 2023 at 14:22
  • $\begingroup$ @NathanielJohnston Thanks. Related question with code: mathoverflow.net/questions/449492/… $\endgroup$
    – joro
    Commented Jun 26, 2023 at 15:26

0

Reset to default

You must log in to answer this question.