I am not sure whether you are going to solve the system on ordinary $\mathbb{R}^n$ with usual rules of addition and multiplication (Case A), or on the two-element Boolean algebra i.e. $\{0,1\}^n$ with Boolean arithmetic (Case B), so here I study both cases. My conclusion (roughly stated) is "In the case B, the only way to meet the requirement is a trivial one (or its permutation), while we may be able to improve more in the Case A."
If my understanding is correct, you are asking how to find an invertible matrix $A^{\prime}\in X^{m\times m}$ ($X=\mathbb{R}$ for the Case A, or $X=\{0,1\}$ for the Case B) and a binary matrix $B\in X^{n\times m}$ such that $A^{\prime}B=A$, for a given undetermined linear system $Ax=b$, where $x\in X^n$ and $A\in X^{n\times m}\ (n>m)$. In addition, the first requirement to minimize the overlap in the use of $x_i$ in constructing $x_i^{\prime}$ (clearer definition will be given below) makes the problem somewhat nontrivial.
First, notice that if we set $A^{\prime}$ to be a permutation matrix (which is obviously invertible), we can easily construct a binary matrix $B$ by $B=A^{\prime T}A$. However, a permutation of rows does not change the number of occurences of $1$ for each column. It means that a permutation does not change the following quantity (whom we would like to minimize, to my understanding) either:$$n(B):=\sum_{i<j}g_i\cdot g_j=\sum_{i=1}^n\frac{||h_i||_1(||h_i||_1-1)}{2};$$ where $g_i\ (i=1,2,\cdots,m)$ is the $i$th row vector of $B$, $||h_i||_1\ (i=1,2,\cdots,n)$ is 1-norm (sum of the elements in this case) of the $i$th column vector of $B$, and $\cdot$ denotes a usual inner product. Unfortunately, in the Case B, it is known that permutation matrices are the only matrices which have inverses (see e.g. Section 4 of K. H. Kim and F. W. Roush, Linear Algebra and its Applications 22, 247 (1978) for some known results about an inverse of Boolean matrix) and therefore we cannot decrease $n(B)$ any further. Note that the example you provided, if defined on a two-element Boolean algebra, violates the requirement that $A^{\prime}x^{\prime}=b$ be determined (Consider e.g. $b=(0,1,1)^T$).
In the Case A, on the other hand, $n(B)$ can be decreased if there exists $i\in \{1,2,\cdots,m\}$, a subset $U\subset \{1,2,\cdots,i-1,i+1,\cdots,m\}$, and non-zero $e^{\prime T}\in \{0,1\}^n$ such that $$e_i=\sum_{j\in U}e_j+e^{\prime};$$ where $e_i$ is the $i$th row vector of $A$, all of which are linearly independent from each other (otherwise a requirement "$A^{\prime}$ should be invertible" will be violated). When this condition is satisfied, we can decrease $n(B)$ (starting from $A^{\prime}=I$ and $B=A$) by using $e^{\prime}$ instead of $e_i$ for $i$th column vector of $B$ and putting 1 to $j(\in U)$th element of the $i$th row vector of $A^{\prime}$ (note that $e^{\prime}$ has fewer non-zero elements than $e_{i}$ by construction). Since the requirements that both $A^{\prime}$ and $B$ should be a binary matrix are strong in the Case A, repeating the forementioned procedure until there no longer exists a pair $i,j\in\{1,2,\cdots,m\}$ such that $(g_i)_k\ge(g_j)_k\ \mathrm{for}\ \forall k\in\{1,2,\cdots,n\}$ suffices for obtaining an optimal $n(B)$.
I show one example: consider a undetermined system $Ax=b$ with $$A=\left(\begin{array}{ccccc}1 & 1 & 0 & 0 & 0\\1 & 1 & 1 & 0 & 1\\0 & 1 & 0 & 1 & 0\\1 & 1 & 1 & 0 & 0\end{array}\right).$$ While the trivial (identical) transformation $A^{\prime}=I,\ B=A$ gives $n(B)=10$, $$A^{\prime}=\left(\begin{array}{cccc}1 & 0 & 0 & 0 \\1 & 1 & 0 & 1\\0 & 0 & 1 & 0\\1 & 1 & 0 & 0\end{array}\right),\ B=\left(\begin{array}{ccccc}1 & 1 & 0 & 0 & 0\\0 & 0 & 1 & 0 & 0\\0 & 1 & 0 & 1 & 0\\0 & 0 & 0 & 0 & 1\end{array}\right)$$ gives $n(B)=1$. We can see from $B$ that the appropriate $x^{\prime}$ which fully satisfies the requirements is $x_1^{\prime}=x_1+x_2$, $x_2^{\prime}=x_3$, $x_3^{\prime}=x_2+x_4$ and $x_4^{\prime}=x_5$. Of course, this is one of the "luckiest" case. There are cases where we cannot reduce $n(B)$ at all (the limitation may be more or less relaxed if we allow the elements of $B$ to take $-1$).
I apologize for a very long reply... I hope this helps!
