This is about a modified Gaussian elimination approach on attempting linear algebra modulo a composite.

If we assume an $n \times n$ matrix of random integers, taken modulo a composite $c=p_1 \cdot p_2 \cdot p_3 \cdots p_m$, composed of $m$ primes, where each prime is greater than $\alpha$.

My question is how far can we get by attempting Gaussian elimination, modulo $c$?

Let me explain my attempt at modified Gaussian elimination, with the hopes that someone can confirm it works, and that someone else can get closer to reduced row echelon form than I can.

The modified Gaussian elimination algorithm works similarly to Gaussian elimination, in that it proceeds by attempting to zero out all matrix entries in the current column of a matrix, except for a single entry. This entry should have the value one. The modified algorithm thus attempts to proceed column by column, zeroing out all entries except for one.

The major difference is that the algorithm must be able to find an entry in the current column that has an inverse modulo $c$. If it cannot find an element that has an inverse, I believe that it must terminate, leaving a matrix that is somewhere between a matrix of random integers and a matrix in reduced row echelon form.

Can someone confirm that this algorithm will generate partial solutions, proceeding until it cannot find an inverse?

  • $\begingroup$ Lookup Hermite / Smith normal form $\endgroup$ – Bill Dubuque Dec 21 '16 at 2:45

Attempt Gaussian elimination, optimistically. At each step, check whether each number you compute has any common factor with $c$ (i.e., if you obtain a new number $x$, check whether $\gcd(c,x)=1$). If you never encounter a number that has a factor in common with $c$ -- if all intermediate results are relatively prime to $c$ -- then Gaussian elimination works fine.

Alternatively, suppose that some intermediate value $x$ has a non-trivial factor in common with $c$: say $\gcd(c,x)=c_1$. Then you can immediately factor $c$ as $c=c_1 c_2$. Now apply the Chinese remainder theorem, and separately work modulo $c_1$ and $c_2$. You may be able to continue from there.

If at any point you need to compute the inverse of $x$ where $\gcd(x,c)\ne 1$, then I think it follows that the matrix is not invertible. I think that's the only thing that can go wrong. As a result, I think in this way you obtain an algorithm that will successfully invert the matrix, if it is invertible.


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.