6
$\begingroup$

Suppose we are given a linear equation $Ax = b$, where $A \in Z_{q}^{m \times n}$ and $b \in Z_{q}^{m}$.

Note that $q$ is NOT necessarily a prime here. I wonder whether the following can be done in $poly(n, m ,q)$ time:

  1. Check whether there exists $x \in Z_{q}^{n}$ such that $Ax = b$.

  2. Suppose there exists $x$ such that $Ax = b$, find such $x$.

Thanks.

$\endgroup$
  • 1
    $\begingroup$ This paper by Arkadev Chattopadhyay and Avi Widgerson may be relevant. $\endgroup$ – Bruno May 28 '13 at 8:54
6
$\begingroup$

Yes, it is well known it can be done by diagonalizing the matrix using row and column operations. An outline of the procedure is given in the paper The Complexity of Solving Equations over Finite Groups by Goldmann and Russell.

$\endgroup$
  • $\begingroup$ Thank you so much. :) It appears that their proof relies on the fact that Abelian group decomposition can be found efficiently, I wonder whether this is indeed the case. $\endgroup$ – chiwangc Jul 22 '13 at 7:00

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.