0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ @EmilJeřábek first sentence follows from here rjlipton.wordpress.com/2014/12/21/modulating-the-permanent right? $\endgroup$ – T.... Aug 4 '17 at 11:35
  • $\begingroup$ @EmilJeřábek done including. $\endgroup$ – T.... Aug 4 '17 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$ – Joshua Grochow Aug 9 '17 at 5:23
  • $\begingroup$ Interesting I did not know that but 2. still remains $\endgroup$ – T.... Aug 9 '17 at 5:32
  • 1
    $\begingroup$ @777 oops, my bad. didn't realise you were asking about char 3. Now it makes sense! $\endgroup$ – Nikhil Aug 9 '17 at 17:05

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.