# How many subsets of unknowns whose sum can be determined by the underdetermined system $Ax=b$ with $A \in \{0,1\}^{m \times n}$

Consider a underdetermined system $Ax=b$ with $A \in \{0,1\}^{m \times n}$ (i.e. being a binary matrix), $x \in \mathbb{R}^n$ and $b \in \mathbb{R}^m$.

I want find a set $S$, $e \in S$ if and only if $e \in \{0,1\}^n$ and $\langle e, x\rangle$ has a unique value derived by $Ax=b$, where $\langle \cdot,\cdot \rangle$ denotes inner product.

For example, given following underdetermined system: $$\begin{pmatrix} 1&1&0&0&0&0 \\ 1&0&1&0&0&0 \\ 0&1&1&0&0&0 \\ 0&0&0&1&1&1 \\ 0&0&0&1&0&0 \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \\ x_5 \\ x_6 \end{pmatrix} = \begin{pmatrix} b_1 \\ b_2 \\ b_3 \\ b_4 \\ b_5 \end{pmatrix},$$ $(1,0,0,0,0,0)^T$, $(0,1,0,0,0,0)^T$, $(0,0,1,0,0,0)^T$, $(0,1,1,1,0,0)^T$ and $(0,0,0,0,1,1)^T$ are all in the set $S$, since: \begin{aligned} x_1 &= \frac{b_1 + b_2 - b_3}{2} \\ x_2 &= \frac{b_1 - b_2 + b_3}{2} \\ x_3 &= \frac{-b_1 + b_2 + b_3}{2} \\ x_2+x_3+x_4 &= b_3 + b_5 \\ x_5 + x_6 &= b_4 - b_5. \end{aligned}

• What do you mean when you write "as well as $⟨e,x⟩$ can be determined by $Ax=b$" ? Rewrite the definition of $S$.
– user91684
Jan 10 '16 at 16:43

I just read your edit. We write the elements of $S$ as linear forms. The rows of $A$ are elements of $S$ (we assume that $A$ has no zero-rows); moreover they generate whole $S$; that is, an element $e$ of $S$ is a linear combination of the rows of $A$: $e=[f_1,\cdots,f_m]A$ where $f_i\in\mathbb{Q}$.