For a underdetermined system $Ax=b$, $A$ is a binary matrix, for example: $$A=\left[\begin{matrix}1&1&0&0\\1&0&1&0\\1&0&1&1\end{matrix}\right],$$ and $x=[x_1, x_2, x_3, x_4]^T$.

Let $x'=[x_1', x_2', x_3']^T$, where $x_1' = x_1 + x_2$, $x_2' = x_1 + x_3$ and $x_3'=x_4$; the $$A'=\left[\begin{matrix}1&0&0\\0&1&0\\0&1&1\end{matrix}\right].$$ It can be found that $A'x'=b$ is a determined system , and $A'x' = Ax = b$ for all $x \in \mathbb{R}^4 $.

My question is how to find $x'$ that $$ \begin{aligned} & \min \sum_{i<j} |term(x_i') \cap term(x_j')| \\ s.t. \quad & A'x'= Ax, x=[x_1, x_2, ..., x_n]^T \\ & A \text{ and } A' \text{ are two binary matrices} \\ & x_i' \text{ is the sum of subset of } \{x_1, x_2, ..., x_n\} \\ & A'x'=b \text{ is a determined system} \end{aligned} $$ $x'_i$ is the sum of subset of $\{x_1, x_2, ..., x_n\}$, thus $term(x'_i)$ is that subset (i.e. terms for addition).

  • $\begingroup$ What do you mean by "find $x'$ with the given binary matrix $A$"? $\endgroup$
    – levap
    Dec 13, 2015 at 9:30
  • $\begingroup$ I have modified the question, please refer to it. $\endgroup$
    – windy
    Dec 13, 2015 at 11:49
  • $\begingroup$ This question is missing some information. What do you mean by $A'x' = b$ is equivalent to $Ax = b$? What is $term(x_i')$? Your definition of $x'$ is not clear and does not seem to make sense in your example. $\endgroup$
    – Calle
    Dec 13, 2015 at 13:24
  • $\begingroup$ There is a related question, which, in my opinion, is much clearer, maybe you will be interested. Please refer to link $\endgroup$
    – windy
    Dec 14, 2015 at 19:42

1 Answer 1


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!

  • $\begingroup$ Thank you for your time and patience. I want to solve this system on ordinary $\mathbb{R}^n$ with $A$ and $A'$ being binary matrices; moreover, $B$ is also binary matrix, but I think $A'B=A$ uses two-element Boolean algebra. And I have some questions: 1) in the 2nd paragraph, I think you mean $A,B \in X^{m \times n}$; 2) I don't quite understand the describtion of procedure to obtain $A'$, for example using $e'$ which has same size of $B$'s row vector to replace its column vector (relpacing its row vector seems cannot reproduce your example, too). $\endgroup$
    – windy
    Dec 14, 2015 at 13:50
  • $\begingroup$ May be a step-by-step explaination of how to get the $A'$ and $B$ in your example can help me understand, thanks a lot. $\endgroup$
    – windy
    Dec 14, 2015 at 13:51
  • $\begingroup$ Please refer to the example of the question link, I don't think your procedure would get the optimal answer to that $A$. I think maybe my question is neither Case A nor Case B. $\endgroup$
    – windy
    Dec 14, 2015 at 19:47
  • $\begingroup$ Thank you very much for your careful reading and quick reply. I appreciate there are many typos/mistakes, and so I will revise my answer later (I don't have enough time right now, sorry). Just a quick comment about your new question: The question you kindly linked is close to Case A; once you get $A=A^{\prime}B$, resulting row vectors of $B$ seem to be what you are looking for. Two differences are that you don't require $A^{\prime}$ to be a binary matrix and you don't (explicitly) require resulting row vectors of $B$ to have minimum overlap, if my understanding is correct. $\endgroup$ Dec 15, 2015 at 6:04
  • $\begingroup$ Yes, you are right. $A'$ is not required to be a binary matrix in the linked question. However, in my opinion, your method proposed here can't get the $[1,0,0,0,0,0]^T$ as a row vector of $B$ for that question, or may be I just don't quite understand your method. $\endgroup$
    – windy
    Dec 15, 2015 at 6:24

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.