4
$\begingroup$

Linear systems of equations over the reals have either 0, 1 or infinitely many solutions. However, when applied to finite fields (specifically GF(2)), infinitely many is not an option.

Is there a fast general method to calculate the number of distinct solutions to a linear system of equations over GF(2)?

You can assume that Gaussian elimination has already been performed, so an example augmented matrix would be:

$$ \left[ \begin{array}{ccccccccc|c}1&0&0&0&1&1&1&0&0&1\\ 0&1&0&0&1&0&1&0&1&1\\ 0&0&1&0&0&1&1&1&0&0\\ 0&0&0&1&1&1&1&1&1&1\\ 0&0&0&0&0&0&0&0&0&0\\ 0&0&0&0&0&0&0&0&0&0\\ 0&0&0&0&0&0&0&0&0&0\\ 0&0&0&0&0&0&0&0&0&0\\ 0&0&0&0&0&0&0&0&0&0\\ \end{array} \right] $$

$\endgroup$
  • $\begingroup$ Is $2^{(\text{number of free variables})}$ not correct? That'd be my naive guess. $\endgroup$ – G. Bach Dec 8 '15 at 14:10
  • $\begingroup$ @G.Bach I just realized that you can 'correct' any resulting sum from the free variables using the fixed variables, thus it is indeed $2^f$. $\endgroup$ – orlp Dec 8 '15 at 14:14
  • $\begingroup$ @Raphael I have already answered my own question - I'm no longer stuck. $\endgroup$ – orlp Dec 8 '15 at 14:53
2
$\begingroup$

You can take any subset of the free variables, and then correct any resulting sum using the fixed variables.

Thus, after Gaussian elimination the total number of solutions is $2^f$ where $f$ is the number of free variables.

$\endgroup$

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.