Number of binary solutions given the rank of a matrix Let $A\in\mathbb{Z}^{n\times n}$, and consider the system of equations $Ax=b$ s.t. $x\in \{0,1\}^n$.
Assume $A$ is not full rank. Is it correct that the number of solutions is $2^{n-r}$ where $r$ is the rank of $A$?
 A: Even if we assume that $b$ is a right-hand side for which a solution exists, it does not follow that the number of solutions is $2^{n-r}$ where $r$ is the rank of $n\times n$ integer matrix $A$.
In fact we can construct a matrix $A$ of rank $1$ and a right-hand side $b$ for which the solution $x\in \{0,1\}^n$ is unique.
Let $A$ be the $n\times n$ matrix whose rows are all the same:
$$ [\;1 \; 2 \; \ldots \; 2^{n-1} \;] $$
The right-hand sides $b$ for which a binary solution $x$ exists s.t. $Ax=b$ are finite in number, as there are $2^n$ possibilities for $x$.  These vectors $b$ have of course equal entries, as the rows of $A$ are all the same.
Let $b = [\; k\; k\; \ldots \; k \;]^T$ be such a right-hand side.  That is, $0 \le k \le 2^n-1$.  Because the binary expansion of $k$ is unique, the corresponding solution $x$ is unique.
For example, $\begin{bmatrix} 1 & 2 \\ 1 & 2 \end{bmatrix} x = \begin{bmatrix} 1 \\ 1 \end{bmatrix}$ has only one binary solution $x$, not two.
Exercise: Find an integer rank one matrix $A$ such that whenever $Ax = b$ has a binary solution $x$ as above, the number of such solutions is odd.
