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?