0
$\begingroup$

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

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

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}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.