2
$\begingroup$

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?

1 Answers 1

1

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.

  • 0
    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.2011-12-09
  • 1
    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.2011-12-09
  • 0
    Yes, thank you! It looks very simple for consistency.2011-12-10