# Number of solutions to linear system of equations over GF(2)

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]$$

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

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