math - From expensive search to Integer Programming or Constraint Programming? -

consider m n matrices m, of entries 0 or 1. given m, question whether there exists non 0 vector v, of entries -1, 0 or 1 mv = 0. example,

      [0 1 1 1] m_1 = [1 0 1 1]       [1 1 0 1] 

in example, there no such vector v.

      [1 0 0 0] m_2 = [0 1 0 0]       [0 0 1 0] 

in example, vector (0,0,0,1) gives m_2v = 0.

given m , n, find if there exists such m there no non-zero v such mv = 0.

if m = 3 , n = 4 answer yes can see above.

i solving problem trying different m , v expensive.

however, possible express problem integer programming problem or constraint programming problem can use existing software package, such scip instead might more efficient.

this question more mathematical progamming. haven't found final answer yet, @ least ideas here:

we can re-state problem in following way.

problem a: fix positive integers m , n. let s set of n-dimensional vectors entries 0 or 1. there exist m n matrix m entries 0 or 1, such that, 2 different vectors v_1 , v_2 in s, vectors mv_1 , mv_2 different. (or, may that, matrix m, considered application n-dimensional vectors m-dimensional vectors, injective on set s.)

in brief: given pair (m, n), there exist such injective m?

problem equivalent original problem. indeed, if mv_1 = mv_2 2 different v_1 , v_2 in s, have m(v_1 - v_2) = 0, , vector v_1 - v_2 have 0, 1, - 1 entries. inverse true.

another reinterpretation is:

problem b: let m, n positive integer , s set of n-dimensional vectors entries 0 , 1. can find m vectors r_1, ..., r_m in s, such that, pair of different vectors v_1 , v_2 in s, there exists r_i, satisfies <v_1, r_i> != <v_2, r_i>? here <x, y> usual inner product.

in brief: can choose m vectors in s distinguish in s taking inner product chosen ones?

problem b equivalent problem a, because can identify matrix m m vectors in s.

in following, use both descriptions of problem freely.

let's call pair (m, n) "good pair" if answer problem (or b) yes.

with description of problem b, clear that, given n, there minimal m such (m, n) pair. let write m(n) minimal m associated n.

similarly, given m, there maximal n such (m, n) good. because, if (m, n) good, i.e. there injective m stated in problem a, n' <= n, erasing n - n' columns of m give injective m'. let write n(m) maximal n associated m.

so task becomes calculate functions m(n) and/or n(m).

we first prove several lemmas:

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

proof: if m m(n) n injective matrix pair (m(n), n) , k m(k) k injective matrix pair (m(k), k), (m(n) + n(k)) (n + k) matrix

[m 0] [0 k] 

works pair (m(n) + 1, n + 1). see this, let v_1 , v_2 pair of different (n + k)-dimensional vectors. may cut both of them 2 pieces: first n entries, , last k entries. if first pieces of them not equal, can distinguished 1 of first m(n) rows of above matrix; if first pieces of them equal, second pieces of them must different, hence can distinguished 1 of last m(k) rows of above matrix.

remark: sequence m(n) subadditive sequence.

a simple corollary:

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

proof: take k = 1 in lemma 1.

note that, other known values of m(n) can better upper bounds. example, since know m(4) <= 3, have m(4n) <= 3n. anyway, these give o(n) upper bounds.

the next lemma gives lower bound.

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

proof: let t set of m(n)-dimensional vectors entries lie in {0, 1, ..., n}. m(n) n matrix m gives map s t, sending v mv.

since there exists m such above map injective, size of set t @ least size of set s. size of t (n + 1)^m, , size of s 2^n, have:

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

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

back programming

i have haven't figured out algorithm. might restate problem set cover problem, follows:

let u set of n dimensional vectors entries 1, 0 or - 1, , let s above. every vector w in s gives subset c_w of u: c_w = {v in u: <w, v> != 0}. question then: can find m vectors w such union of subsets c_w equal u.

the general set cover problem np complete, in above wiki link there integer linear program formulation.

anyway, cannot take further n = 10, guess.

i'll keep editting answer if have further results.