From expensive search to Integer Programming or Constraint Programming?

Question

Consider m by n matrices M, all of whose entries are 0 or 1. For a given M, the question is whether there exists a non zero vector v, all of whose entries are -1, 0 or 1 for which Mv = 0. For example,

      [0 1 1 1]
M_1 = [1 0 1 1]
      [1 1 0 1]

In this example, there is no such vector v.

      [1 0 0 0]
M_2 = [0 1 0 0]
      [0 0 1 0]

In this example, the vector (0,0,0,1) gives M_2v = 0.

Given an m and n, I would like to find if there exists such an M so that there is no non-zero v such that Mv = 0.

If m = 3 and n = 4 then the answer is yes as we can see above.

I am currently solving this problem by trying all different M and v which is very expensive.

However, is it possible to express the problem as an integer programming problem or constraint programming problem so I can use an existing software package, such as SCIP instead which might be more efficient.

Answer 1

This question is probably more mathematical than progamming. I haven't found the final answer yet, but at least some ideas are here:

We can re-state the problem in the following way.

Problem A: Fix positive integers m and n. Let S be the set of n-dimensional vectors whose entries are 0 or 1. Does there exist any m by n matrix M whose entries are 0 or 1, such that, for any two different vectors v_1 and v_2 in S, the vectors Mv_1 and Mv_2 are different. (Or, you may say that, the matrix M, considered as an application from n-dimensional vectors to m-dimensional vectors, is injective on the set S.)

In brief: given the pair (m, n), does there exist such an injective M?

Problem A is equivalent to the original problem. Indeed, if Mv_1 = Mv_2 for two different v_1 and v_2 in S, then we have M(v_1 - v_2) = 0, and the vector v_1 - v_2 will have only 0, 1, - 1 as entries. The inverse is obviously also true.

Another reinterpretation is:

Problem B: Let m, n be a positive integer and S be the set of n-dimensional vectors whose entries are 0 and 1. Can we find m vectors r_1, ..., r_m in S, such that, for any pair of different vectors v_1 and v_2 in S, there exists an r_i, which satisfies <v_1, r_i> != <v_2, r_i>? Here <x, y> is the usual inner product.

In brief: can we choose m vectors in S to distinguish everyone in S by taking inner product with the chosen ones?

Problem B is equivalent to Problem A, because you can identify the matrix M with m vectors in S.

In the following, I will use both descriptions of the problem freely.

Let's call the pair (m, n) a "good pair" if the answer to Problem A (or B) is yes.

With the description of Problem B, it is clear that, for a given n, there is a minimal m such that (m, n) is a good pair. Let us write m(n) for this minimal m associated to n.

Similarly, for a given m, there is a maximal n such that (m, n) is good. This is because, if (m, n) is good, i.e. there is an injective M as stated in Problem A, then for any n' <= n, erasing any n - n' columns of M will give an injective M'. Let us write n(m) for this maximal n associated to m.

So the task becomes to calculate the functions m(n) and/or n(m).

We first prove several lemmas:

Lemma 1: We have m(n + k) <= m(n) + m(k).

Proof: If M is an m(n) by n injective matrix for the pair (m(n), n) and K is an m(k) by k injective matrix for the pair (m(k), k), then the (m(n) + n(k)) by (n + k) matrix

[M 0]
[0 K]

works for the pair (m(n) + 1, n + 1). To see this, let v_1 and v_2 be any pair of different (n + k)-dimensional vectors. We may cut both of them into two pieces: the first n entries, and the last k entries. If the first pieces of them are not equal, then they can be distinguished by one of the first m(n) rows of the above matrix; if the first pieces of them are equal, then the second pieces of them must be different, hence they can be distinguished by one of the last m(k) rows of the above matrix.

Remark: The sequence m(n) is thus a subadditive sequence.

A simple corollary:

Corollary 2: We have m(n + 1) <= m(n) + 1, hence m(n) <= n.

Proof: Take k = 1 in Lemma 1.

Note that, from other known values of m(n) you can get better upper bounds. For example, since we know that m(4) <= 3, we have m(4n) <= 3n. Anyway, these always give you O(n) upper bounds.

The next lemma gives you a lower bound.

Lemma 3: m(n) >= n / log2(n + 1).

Proof: Let T be the set of m(n)-dimensional vectors whose entries lie in {0, 1, ..., n}. Any m(n) by n matrix M gives a map from S to T, sending v to Mv.

Since there exists an M such that the above map is injective, then necessarily the size of the set T is at least the size of the set S. The size of T is (n + 1)^m, and the size of S is 2^n, thus we have:

(n + 1)^m(n) >= 2^n

or equivalently, m(n) >= n / log2(n + 1).

Back to programming

I have to say that I haven't figured out a good algorithm. You might restate the problem as a Set Cover Problem, as follows:

Let U be the set of n dimensional vectors with entries 1, 0 or - 1, and let S be as above. Every vector w in S gives a subset C_w of U: C_w = {v in U: <w, v> != 0}. The question is then: can we find m vectors w such that the union of the subsets C_w is equal to U.

The general Set Cover Problem is NP complete, but in the above Wiki link there is an integer linear program formulation.

Anyway, this cannot take you much further than n = 10, I guess.

I'll keep editting this answer if I have further results.