Number of binary solutions given the rank of a matrix

Question

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

Answer 1

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.