By $'$ I mean transpose. I gather the info here from rjlipton.wordpress.com/2014/12/21/modulating-the-permanent. We know that if $U\in\Bbb F_{3^t}^{n\times n}$ satisfies $UU'=I_n$ in $\Bbb F_{3^t}$ then we can compute $Perm(U)$ in $\Bbb F_{3^t}$ in $O(n^4)$ time.

This gives an $O(n^4)$ time algorithm for $Perm(U)\bmod 3$ for $U\in\Bbb Z^{n\times n}$ satisfying $UU'=I_n$ in $\Bbb Z$?

Can it be modified to give an $O(n^{O(t)})$ time algorithm for $Perm(U)\bmod 3^t$ for $U\in\Bbb Z^{n\times n}$ satisfying $UU'=I_n\bmod 3^r$ in $\Bbb Z$ where $r\in\Bbb N$ is fixed?

  • $\begingroup$ @EmilJeřábek first sentence follows from here rjlipton.wordpress.com/2014/12/21/modulating-the-permanent right? $\endgroup$
    – Turbo
    Commented Aug 4, 2017 at 11:35
  • $\begingroup$ @EmilJeřábek done including. $\endgroup$
    – Turbo
    Commented Aug 4, 2017 at 11:40
  • 1
    $\begingroup$ The only matrices $U \in \mathbb{Z}^{n \times n}$ satisfying $UU^T=I$ are signed permutation matrices, for which it is trivial to compute the permanent... $\endgroup$ Commented Aug 9, 2017 at 5:23
  • $\begingroup$ Interesting I did not know that but 2. still remains $\endgroup$
    – Turbo
    Commented Aug 9, 2017 at 5:32
  • 1
    $\begingroup$ @777 oops, my bad. didn't realise you were asking about char 3. Now it makes sense! $\endgroup$
    – Nikhil
    Commented Aug 9, 2017 at 17:05


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.