Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Is there some polynomial upper-bound for Gauss elimination over ring $Z_n$? I'm interested in polynomial bound depending from size of matrix and $\log n$.

I also have the same question about the consistency of a linear system over ring $Z_n$.

P.S. I think, it's not so hard question if we have factorization of $n$. But what can we do without it?

share|cite|improve this question

I don't think you need factorization. To do Gaussian elimination, you may need inverses modulo $n$, but you can get those by the Euclidean algorithm, without factorization, and the Euclidean algorithm is fast.

share|cite|improve this answer
Yes, inverting modulo n is simple. But what if we have to invert non-invertible element? How much partial solutions we need to care about? We can consider only the question about consistency of the system. – Vsevolod Oparin Dec 9 '11 at 11:27
As long as you have a column where some element is invertible, you can use that element as a pivot. If every entry is non-invertible, but there is a column such that there is no $d$ dividing $n$ and every entry in that column, you can do row operations to get an invertible entry in that column. So we've reduced it to the case where for each column there's a $d\gt1$ such that $d$ divides $n$ and every entry in the column. I think you can still bring the matrix to a reduced form, and from that reduced form decide consistency. – Gerry Myerson Dec 9 '11 at 22:12
Yes, thank you! It looks very simple for consistency. – Vsevolod Oparin Dec 10 '11 at 10:09

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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