I have an equation system with binary values ($0$ and $1$). After doing a gauss-elimination, I can calculate the determinant by anding the entries of the main diagonal.
If it is $1$, it's trivial to do a Gauss-Jordan elimination. But what if it is $0$? In this case, I don't know how to proceed. I tried applying Gauss-Jordan as far as possible and whenever I reach a line full of zeros I just randomly set the correspond variable, if the equation is not of the form $1=0$ (in that case I have no solution).
Obviously, I miss some solutions as I don't check both variants for variables that have no exact solution. I could try all combinations, but that would be something around $\cal O(2^n)$ which is too complex for me. It seems that it must be possible to find one or all solutions efficiently in this case, but I don't see how. Can somebody give me an explanation?