5
$\begingroup$

Given integers $n,m$, I want to find a $m \times n$ binary matrix $X$ such that there does not exist any non-zero vector $y \in \{-1,0,1\}^n$ with $Xy=0$ (all operations performed over $\mathbb{Z}$). What algorithm could I use for this?

In more detail: We are given parameters $n$ and $m$. The problem is to determine if there exists $x$ such that $x_{i,j} \in \{0,1\}$, and there does not exist $y\ne (0,0,\dots,0)$ where $y_j \in \{-1,0,1\}$ for all $j$ and for all $1 \leq i \leq m$,

$$\sum_{1 \leq j \leq n} x_{i,j} y_j = 0.$$

(Notice that we require that at least one of the $y_j \ne 0$ to avoid the trivial solution.)

For example, consider $m=3,n=4$. Then, expressing $x_{i,j}$ as a matrix $X$,

$$ X=\begin{pmatrix} 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 \\ \end{pmatrix} $$

is a valid solution for $m=3$ and $n=4$.

What algorithm can I use to solve this problem? Can I formulate this as an integer linear programming problem or maybe as a constraint programming problem?

|cite|improve this question
$\endgroup$
  • 2
    $\begingroup$ What makes you think integer linear programming is a good way to solve this problem? What makes you ask for a formulation as an integer linear program? Is there some requirement to formulate it that way? Perhaps it is an exercise that requires you to formulate it in that way? To be honest, this sounds like an instance of an XY problem to me. $\endgroup$ – D.W.♦ Dec 27 '13 at 23:49
  • $\begingroup$ @D.W. My motivation was simply to find a way to use existing software tools to solve this hard problem. $\endgroup$ – marshall Dec 28 '13 at 7:53
  • $\begingroup$ What would be a typical size for $n$ and $m$, in your application? This will affect which algorithms are efficient enough. $\endgroup$ – D.W.♦ Dec 28 '13 at 8:11
  • $\begingroup$ @D.W. Both $n$ and $m$ will be under $20$ typically although of course it would be great to be able to solve larger instances too. $\endgroup$ – marshall Dec 28 '13 at 8:12
  • $\begingroup$ @marshall is $X$ valid if the only solution to $Xy=0$ is $y=0$ or must it have a non-trivial solution ($y\neq0$)? Also see the discussion under D.W. solution. $\endgroup$ – bcorso Dec 30 '13 at 4:38
4
$\begingroup$

I have a method for you that will help you find valid solutions (matrices) for many possible values of $m,n$. However, it is not a complete answer to your question. It can try to find a matrix for a particular value of $m,n$, but it might fail, and if it fails, you've learned nothing; my method cannot prove that no such matrix exists.

The method is based upon the following observation:

Theorem. If we have a valid $m_1\times n_1$ matrix $X_1$ that meets all your requirements (for parameters $m_1,n_1$) and a valid $m_2\times n_2$ matrix $X_2$ that meets all your requirements (for parameters $m_2,n_2$), then we can find a valid $m\times n$ matrix that meets all your requirements (for parameters $m,n$), where $m=m_1+m_2$ and $n=n_1+n_2$.

Proof. Use the following matrix:

$$X = \begin{pmatrix} 0 &X_1 \\ X_2 &Z \end{pmatrix},$$

where $Z$ is arbitrary. Suppose $Xy=0$, where $y \in \{-1,0,1\}^n$. Then since the last $m_1$ coefficients of $Xy$ are zero, and since $X_1 y_1 =0$ implies $y_1=0$, it follows that the last $n_1$ coefficients of $y$ are zero. Thus by letting $y_2$ be the restriction of $y$ to its first $m_2$ coefficients, we find that $X_2 y_2 = 0$. But this implies $y_2 = 0$, i.e., $y=0$. In other words, if $Xy=0$, then $y=0$. This proves that $X$ is a valid matrix.

Now this lets us find many values of $m,n$ where it is possible to find a valid matrix $X$. In particular, seed things with some small matrices for various small values of $m,n$ (using any convenient method); then you can derive some larger values of $m,n$ that also have such a matrix.

Here are some observations that will help you identify seed values $m,n$ where such a matrix $X$ exists:

  • First, a trivial observation: Obviously, if $n \le m$, it is easy to find a valid solution $x$: just use the identity matrix (if $n<m$, fill in the extra rows arbitrarily). No need to use integer linear programming. So this problem is only interesting when $n>m$.

  • Second, if $n$ is small enough, you can express this as a SAT instance and apply an off-the-shelf SAT solver. The SAT instance will be of exponential size: it will have more than $3^n$ constraints, so this is only helpful for very small values of $n$, but it will still help you construct some values of $m,n$ where you can find a valid matrix $X$.

  • Third, you can use bcorso's answer to handle all cases where $n=m+1$ (there is always a valid solution, for $m\ge 3$).

    In particular, you can construct a SAT instance where the $x_{i,j}$ are the variables. Now, for each possible non-zero vector $y \in \{-1,0,1\}^n$, you can add a complicated constraint enforcing the requirement that $Xy \ne 0$. (You'll need to have $m$ adders, each of which adds up to $n$ 0-or-1 values, and then a comparison to test whether the results of all of the $m$ adders are all zero or not.)

In this way, I would expect that, for each $n\le 8$ (or so), you can probably find the largest value of $m$ such that there exists a valid $m\times n$ matrix. Now once you have those seed values, you can use the Theorem above to help you find additional values of $m,n$ where such a matrix exists.

As I stated above, this is not a complete solution, but it might help you solve your problem at least some of the time.

For general $m,n$, I doubt that there's any straightforward formulation of this as a polynomial-size integer linear program (unless $\text{NP} = \text{NP}^\text{co-NP}$ or the polynomial hierarchy collapses or something like that, which is not expected to hold; or unless you use some special knowledge about the solution to this problem).

Just telling whether a candidate value of $x$ is indeed a valid solution to this problem is $\text{co-NP}$-complete. See https://cstheory.stackexchange.com/q/20277/5038. In other, recognizing a solution to this problem can't be done in polynomial time (as far as we know); just recognizing a valid solution is $\text{co-NP}$-complete. This means that the problem of finding a valid solution is in $\text{NP}^\text{co-NP}$. In contrast, integer linear programming is in $\text{NP}$. Therefore, without using some special knowledge about this problem, I don't think you can find a generic reduction from your problem to integer linear programming unless $\text{NP}^\text{co-NP} = \text{NP}$ (something that most complexity theorists believe is not likely to hold).

Don't take this too seriously. I'm not trying to prove a formal theorem or anything like that; I'm just trying to give some weak evidence why this problem does not look like it has a straightforward, generic formulation as an instance of integer linear programming.

Of course, you can probably get a formulation as an integer linear program with a number of constraints that is exponential (say, in $m$), similar to how we got a SAT instance. It'll be uglier, because expressing the constraint that some vector (namely, $Xy$) is not identically zero is ugly in ILP. But it's doable. See, e.g., Express boolean logic operations in zero-one integer linear programming (ILP). However, I'm not sure this will be any better than the SAT-based method. If I were implementing this, I would start by trying the SAT-based method, because (if you use a suitable front end, like STP) I think it will be easier to implement and might work just as well or better than an ILP-based formulation.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ You may be right that integer programming is the wrong tool but that would be a shame. I want to avoid naive enumeration of all possibilities. $\endgroup$ – marshall Dec 28 '13 at 7:51
  • $\begingroup$ @marshall, thank you! I had $n$ and $m$ backwards; thank you for the correction. I've corrected my answer accordingly. Incidentally, do look at the CSTheory question I looked at; there's a (remote) chance that the reductions considered there might be helpful to you. $\endgroup$ – D.W.♦ Dec 28 '13 at 8:01
  • $\begingroup$ Not sure what you mean by, "if $n≤m$, it is easy to find a valid solution $X$: just use the identity matrix." A simple example of this failing is if $n=m$, then $X=I$ would give $y=0$, so it not a valid solution to the problem. $\endgroup$ – bcorso Dec 30 '13 at 1:50
  • $\begingroup$ @bcorso, thanks for the comment. I'm sorry, but I don't understand your comment. What do you mean by "$X=I$ would give $y=0$"? The definition of what it means for $X$ to be valid is that (a) all entries of $X$ are $0$ or $1$, and (b) if $Xy=0$ and all entries of $y$ are $-1$, $0$, or $1$, then $y=0$ (then all entries of $y$ are $0$). The identity matrix satisfies both of these requirements, so it is a valid solution to the problem. $\endgroup$ – D.W.♦ Dec 30 '13 at 1:55
  • $\begingroup$ @D.W. the OP specifies in his question, "we require that at least one of the $y_j≠0$ to avoid the trivial solution." $\endgroup$ – bcorso Dec 30 '13 at 2:00
2
$\begingroup$

Below is an exact solutions for the case of $3 \leq n-1 \leq m$ . Thus, you would only need to manually check cases where $m < n-1$, ($n>3$).

$\mathbf{Theorem:}$ for $3 \leq n-1 \leq m$ there always exists a binary matrix $X$ such that no (non-trivial) solution exists to the equation $Xy=0$. Furthermore, $X$ has the form:

$$ X_{(m\ \times\ n)}=\begin{pmatrix} M_{(n-1\ \times\ n)} \\ 0_{(m-n-1\ \times\ n)} \\ \end{pmatrix} $$

Where $0_{(m-n-1\ \times\ n)}$ is a matrix of zeros and:

$$ M_{(n-1 \ \times\ n)}=\begin{pmatrix} 1 & 1 & 0 & 0 & 0 & \cdots & 0 \\ 1 & 0 & 1 & 0 & 0 & \cdots & 0 \\ 1 & 0 & 0 & 1 & 0 & \cdots & 0 \\ \vdots & \vdots & \vdots & \vdots & \ddots & \cdots & \vdots \\ 1 & 0 & 0 & 0 & \cdots & 1 & 0 \\ 0 & 1 & 1 & 0 & \cdots & 0 & 1 \\ \end{pmatrix}, $$

$\mathbf{Proof:}$ Using the above definitions of $X$, $Xy=0$ reduces to $My=0$, which produces the following system of equation:

$$ \begin{pmatrix} y_1 = t \\ y_1 + y_2 = 0 \\ y_1 + y_3 = 0 \\ y_1 + y_4 = 0 \\ \vdots \\ y_1 + y_{n-1} = 0 \\ y_2 + y_3 + y_n = 0 \\ \end{pmatrix} \Rightarrow y=t\ \begin{pmatrix} 1 \\ -1 \\ -1 \\ -1 \\ \vdots \\ -1 \\ 2 \\ \end{pmatrix} $$ Which will never have a solution for all $y_i \in \{-1,0,1\}$ for any choice of $t$ except the trivial solution $t=0$. $\Box$

|cite|improve this answer
$\endgroup$
  • $\begingroup$ The case $n \le m$ is trivial and already covered in my answer. It is only $n>m$ that is interesting. So this only provides a characterization for $n=m+1$. That's incrementally helpful, but it leaves all the rest ($n>m+1$) uncharacterized. Basically, your solution is primarily the easy cases; it leaves most of the space of non-trivial cases unanswered. $\endgroup$ – D.W.♦ Dec 30 '13 at 0:14
  • $\begingroup$ @D.W. saying it is trivial is not a proof. I applaud you for taking a stab at the harder case, but I still believe this case will be useful for others so I'll keep it up, Thanks! $\endgroup$ – bcorso Dec 30 '13 at 1:46

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.