<p>Yes, it is well known it can be done by diagonalizing the matrix using row <em>and</em> column operations. An outline of the procedure is given in the paper <a href="http://dx.doi.org/10.1006/inco.2002.3173">The Complexity of Solving Equations over Finite Groups</a> by Goldmann and Russell.</p>

CC BY-SA 3.0
2013-07-22T07:00:06.280Z
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.
chiwangc
CC BY-SA 3.0
2013-05-28T09:06:29.173Z
2013-05-28T09:06:29.173Z
Kristoffer Arnsfelt Hansen
<p>Suppose we are given a linear equation $Ax = b$, where $A \in Z_{q}^{m \times n}$ and $b \in Z_{q}^{m}$.</p>

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

<ol>
<li><p>Check whether there exists $x \in Z_{q}^{n}$ such that $Ax = b$.</p></li>
<li><p>Suppose there exists $x$ such that $Ax = b$, find such $x$.</p></li>
</ol>

<p>Thanks.</p>

CC BY-SA 3.0
2013-05-28T08:54:10.487Z
This [paper](http://www.cs.toronto.edu/~arkadev/singleLayer2G.pdf) by Arkadev Chattopadhyay and Avi Widgerson may be relevant.
Bruno
<linear-equations>
Solving Linear Equations over $Z_q$
chiwangc
# Solving Linear Equations over $Z_q$

(Asked by: username_0 on 2013-05-28)

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.

**Tags:** linear-equations

> **Comments:**
> **username_1**: This [paper](http://www.cs.toronto.edu/~arkadev/singleLayer2G.pdf) by Arkadev Chattopadhyay and Avi Widgerson may be relevant.  

---

## 1 answers

### Answer by username_2 on 2013-05-28. Score: 7 | Accepted answer

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](http://dx.doi.org/10.1006/inco.2002.3173) by Goldmann and Russell.

> **Comments:**
> **username_0**: 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.  

---

