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$
3
  • $\begingroup$ Is $2^{(\text{number of free variables})}$ not correct? That'd be my naive guess. $\endgroup$
    – G. Bach
    Dec 8, 2015 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, 2015 at 14:14
  • $\begingroup$ @Raphael I have already answered my own question - I'm no longer stuck. $\endgroup$
    – orlp
    Dec 8, 2015 at 14:53

1 Answer 1

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 and acknowledge you have read our privacy policy.

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