From expensive searches to Integer Programming or Constraint Programming?

Question

Consider m on n matrices M, all entries of which are 0 or 1. For a given M, the question is whether there exists a nonzero vector v, all entries of which 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 m and n, I would like to find if M exists so that there are no nonzero 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 of a programming problem or a constraint programming problem, so I can use an existing software package such as SCIP, which can be more efficient.

Answer 1

This question is probably more mathematical than programming. I have not yet found a definitive answer, but at least some ideas here:

We can reformulate the problem as follows.

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

In short: given the pair (m, n) , is there 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, Obviously, the converse is also true.

Another interpretation:

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

In short: can we choose the vectors m in S to distinguish all in S by taking the scalar product with the ones chosen?

Problem B is equivalent to task A, since you can identify the matrix m with vectors m in S

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

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 exists a minimal m such that (m, n) is a good pair. We write m(n) for this minimal m associated with n .

Similarly, for a given m there exists a maximum n such that (m, n) is good. This is due to the fact that if (m, n) is good, i.e. There is injective m , as indicated in Problem A, then for any n' <= n erasing any columns n - n' m will give injective M' . We write n(m) for this maximal n associated with m .

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

First, we prove several lemmas:

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

Evidence. If m is an injective matrix m(n) by n for a pair (m(n), n) , and K is an injective matrix m(k) on K for a pair (m(k), k) , then (m(n) + n(k)) matrix (n + k)

 [M 0] [0 K] 

works for a 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 can cut them both into two parts: the first entries n and the last entries K If the first parts of them are not equal, then they can be distinguished by one of the first rows m(n) above matrix; if the first parts of them are equal, then their second parts must be different, so they can be distinguished by one of the last rows m(k) above matrix.

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

A simple consequence:

Corollary 2: we have m(n + 1) <= m(n) + 1 , therefore m(n) <= n .

Evidence. Take k = 1 in Lemma 1.

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

The following lemma gives you a lower bound.

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

Evidence. Let T be the set of m(n) -dimensional vectors whose elements lie in {0, 1, ..., n} . Any matrix m(n) on n m gives a mapping from S to T by sending v to Mv .

Since there exists m such that the above mapping is injective, it is imperative that the size of the set T be equal to at least the size of the set S The size of T is (n + 1)^m , and the size of S is 2^n , so 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 did not understand a good algorithm. You can reformulate the problem as Fix the coverage problem as follows:

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

The general problem with the NP coverage set is complete, but there is an integer linear programming statement in the above Wiki link.

In any case, this cannot make you much further n = 10 , I think.

I will continue to edit this answer if I get other results.

Answer 2

I think that using multiplication by a Boolean matrix will allow you to solve the problem of Mv = 0 only with an efficiency of 1 and 0. Using this method, you can solve it without worrying about the disadvantages of the ranks due to the fact that RHS is zero. Here is a link to the documentation for some BMM usage algorithms:

http://theory.stanford.edu/~virgi/cs367/lecture2.pdf

Answer 3

If I understand the question, you are asking for the given m, n if there exists a matrix M (linear transformation) with a trivial kernel, that is, Ker (M) = {0}.

Recall that this is the same as the null space M equal to zero 0, Null (M) = 0.

For the system Mv = 0, the empty space {0} if the rank of the matrix M is equal to dimension v. Therefore, your question reduces to the question of the existence of a matrix mxn with rank dim (v) = T. The problem in this form was discussed here.

Create a "random" matrix of some rank over a fixed set of elements

You can also ask this question in terms of determinants, because if M has determinant = 0, then the empty space is nontrivial. Therefore, you can think about this issue in terms of constructing a matrix with elements in {-1,0,1} with the desired determinant.

Hope this helps.