Let's suppose I have a matrix $A$ that is only composed of $0$'s and $1$'s. It has $k$ rows and $n$ columns where $n < k$. I want to find the number of solutions such that $Ax = b$ where the entries of $x$ are only zeroes and ones. And, $b$ is the all ones vector. All the algebra is over $\mathbb{F}_2$.
Someone in a paper recently claimed that the number of solutions is divisible by $2^{k-n}$ but I cannot see why this is the case. Any help would be great.
Let $n$ be the number of rows and $k$ be the number of columns. The rank $r$ of the system satisfies $r\le \min(n,k)$. The system can be reduced to row echelon form by Gaussian elimination. The number of free variables is $k−r$, which is necessarily larger than $k−n$. So if the system has a solution, it has exactly $2^{k−r}$ solutions (a multiple of $2^{k-n}$) obtained by giving the free variables all the possible boolean values, but it may also be unsolvable, as the system \begin{equation} \begin{bmatrix} 1&0&1&0\\ 0&1&1&0\\ 1&1&0&0 \end{bmatrix} x = \begin{bmatrix} 1\\1\\1 \end{bmatrix} \end{equation} Observe that if the system is unsolvable, it has 0 solutions, which is also a multiple of $2^{k-n}$. So the result is true in general.