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?
Best Answer
By 'equation system with binary values' I presume you mean a system over $\mathbb{Z}_2$ - that is, where $1+1=0$ rather than $2$. In that case, you can't really do any better than you are doing; all combinations of your 'independent' variables (those that correspond to an 'empty row', that is, those with no constraint upon them) lead to correct solutions of your equation, and so if you wind up with $s$ rows of zeroes (this is usually expressed as the matrix having rank $r=n-s$, with $n$ the number of equations), then there will be $2^s$ solutions. Finding one solution, as you've noted, can be done efficiently - just randomly set the corresponding variable. Finding all of them is generally not too painful either (modulo the caveat about how many there are); a straightforward extension of the usual elimination procedure will allow you to express all of your variables in terms of linear combinations of the 'free' variables, and then just iterating over all $2^s$ assignments of those free variables will give you all of your solutions.