Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
    
What if a row is not completely zero, just the coefficient $a_{k,k}$ is? In this case, it depends on how you set the free variables, whether the equation in row $k$ becomes $0=0$ or $0=1$... I don't know how to prevent that. If the row is full of zeroes, it is easy. Consider this system: $$\begin{array}{cccc|c}1&1&0&0&1\\0&0&1&0&1\\0&0&1&1&1\\0&0&0&0&0\\\end{array}$$ If you set the rightmost variable to $1$, it has no solutions. How to deal with such a case? –  FUZxxl Oct 4 '11 at 20:42
    
Thank you. That was a missconception of mine. I thought that the echelon form would allow constructs like above. –  FUZxxl Oct 4 '11 at 20:47

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.