0
$\begingroup$

Here all matrices are square $n \times n$ with integer entries. If you prefer, all entries are $0-1$.

Observation: the discrete logarithm for permutation matrices is polynomial in $n$, since the largest prime factor of the order is small and we can apply small subgroup attack.

Let $P$ be permutation matrix.

What is the complexity of the following problem: Given matrices $A,B,Q$, such that $B=P A P^T=P A P^{-1}$ and $Q=P^x$, and $P$ and $Q$ are of equal multiplicative order, find $P$.

$x$ is unknown. In the graph isomorphism problem we are not given $Q$.

Improve this question
$\endgroup$
5
  • $\begingroup$ Couldn't $Q$ be the identity matrix and then this is as hard as the usual graph isomorphism? $\endgroup$
    – David Roberson
    Commented Mar 19, 2023 at 13:56
  • $\begingroup$ @DavidRoberson Thanks, you are right. It is still GI hard if $P=Q$. Do you have an idea how to avoid these cases? I am trying to define the permutation group of $P$. $\endgroup$
    – joro
    Commented Mar 19, 2023 at 14:13
  • $\begingroup$ Well if you know that $P=Q$, then obviously it is trivial, and otherwise I am not sure the question makes sense. I am not an expert on complexity theory but I think you need to define a specific class of problems to ask if it is GI-hard, and it is assumed that knowledge of the class can be used to construct algorithms. So I don't think it makes sense to ask how hard is your problem when $P = Q$ but you don't know that $P=Q$. Apologies if I am wrong here. $\endgroup$
    – David Roberson
    Commented Mar 19, 2023 at 14:26
  • $\begingroup$ By "permutation group of $P$, do you mean the cyclic subgroup generated by $P$? You could give the whole subgroup but this has size at most $n$ and then the problem becomes easy (simply try everything in the subgroup). You could add the promise that $Q \ne I$. But I think something more clever is needed. Otherwise $Q$ could be the matrix of the transposition $(1,2)$, and your two graphs could be any two arbitrary graphs that both have vertices $1$ and $2$ isolated. Then $Q$ doesn't really give you any information. Or maybe it tells you that the part of $P$ not acting on $\{1,2\}$ has odd order $\endgroup$
    – David Roberson
    Commented Mar 19, 2023 at 14:32
  • $\begingroup$ Upon further reflection, my statement that the subgroup generated by $P$ has size at most $n$ was remarkably stupid. math.stackexchange.com/questions/221211/… So maybe it makes sense to give the subgroup generated by $P$, though I suppose just generators should be given. $\endgroup$
    – David Roberson
    Commented Mar 19, 2023 at 14:48

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .