从昂贵的搜索到整数编程或约束编程？

Question

考虑m乘n矩阵M,其所有条目都是0或1.对于给定的M,问题是是否存在非零向量v,其所有条目都是-1,0或1,其中Mv = 0.例如,

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

在这个例子中,没有这样的向量v.

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

在此示例中,向量(0,0,0,1)给出M_2v = 0.

给定m和n,我想找到是否存在这样的M,使得不存在非零v,使得Mv = 0.

如果m = 3和n = 4那么答案是肯定的,因为我们可以在上面看到.

我目前通过尝试所有不同的M和v来解决这个问题,这是非常昂贵的.

但是,是否可以将问题表达为整数编程问题或约束编程问题,因此我可以使用现有的软件包,例如SCIP,这可能更有效.

Answer 1

这个问题可能比编程更具数学性.我还没有找到最终答案,但至少有一些想法在这里:

我们可以通过以下方式重新陈述问题.

问题A:修复正整数m和n.我们S是集合n维向量,其条目是0或1.是否存在任何m由n矩阵M,其元素是0或1,例如,对于任何两个不同的载体v_1和v_2在S,所述载体Mv_1和Mv_2是不同的.(或者,您可以说,矩阵M,被视为从n维向量到m维向量的应用,在集合上是单射的S.)

简而言之:鉴于这对(m, n),是否存在这样的内射M？

问题A等同于原始问题.事实上,如果Mv_1 = Mv_2两个不同的v_1和v_2在S,那么我们就M(v_1 - v_2) = 0和载体v_1 - v_2将只0,1,- 1作为条目.反过来显然也是如此.

另一个重新解释是:

问题B:让m,n是一个正整数并且S是集合n维向量,其条目是0和1.我们可以发现m载体r_1, ..., r_m中S,这样,对于任何一对不同的载体v_1和v_2中S,存在一个r_i,满足<v_1, r_i> != <v_2, r_i>？这<x, y>是通常的内在产品.

简而言之:我们可以选择m向量S来区分每个人,S将内在产品与所选产品区分开来吗？

问题B等同于问题A,因为你可以M用m向量来识别矩阵S.

在下文中,我将自由地使用这两个问题的描述.

让我们把对(m, n)一个" 好一对 ",如果回答问题A(或B)是肯定的.

通过对问题B的描述,很明显,对于给定的n,存在最小的m这(m, n)是一对良好的对.让我们写一下m(n)这个最小的m关联n.

类似地,对于给定的m,存在最大值n,这(m, n)是好的.这是因为,如果(m, n)是好的,即存在M问题A中所述的单射,那么对于任何一个n' <= n,擦除任何n - n'列的M将给出一个单射M'.让我们n(m)为这个最大n相关联写m.

因此,任务变为计算功能m(n)和/或n(m).

我们首先证明了几个引理:

引理1:我们有m(n + k) <= m(n) + m(k).

证明:如果M是m(n)由n射矩阵的一对(m(n), n)和K是一个m(k)由k射矩阵的一对(m(k), k),则(m(n) + n(k))通过(n + k)矩阵

[M 0]
[0 K]

适合这对(m(n) + 1, n + 1).看到这一点,让v_1并且v_2是任何一对不同的(n + k)维向量.我们可以将它们分成两部分:第一个n条目和最后一个k条目.如果它们的第一部分不相等,那么它们可以通过m(n)上述矩阵的第一行之一来区分; 如果它们的第一部分相等,那么它们的第二部分必须是不同的,因此它们可以通过m(k)上述矩阵的最后一行来区分.

备注:序列m(n)因此是一个子加法序列.

一个简单的推论:

推论2:m(n + 1) <= m(n) + 1因此,我们有m(n) <= n.

证据:k = 1引入引理1.

请注意,从其他已知值m(n)可以获得更好的上限.例如,既然我们知道m(4) <= 3,我们就知道了m(4n) <= 3n.无论如何,这些总是给你O(n)上限.

下一个引理会给你一个下限.

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

证明:T设为m(n)其条目所在的维数向量集{0, 1, ..., n}.任何m(n)通过n矩阵M给出从地图S到T,发送v到Mv.

由于存在M上述映射是单射的,因此集合的大小必须T至少是集合的大小S.的大小T是(n + 1)^m和的大小S就是2^n,因此,我们有:

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

或等同地,m(n) >= n / log2(n + 1).

回到编程

我不得不说我还没有找到一个好的算法.您可以将问题重新设置为Set Cover Problem,如下所示:

让U是集合n的条目维向量1,0或者- 1,让S是如上.每个向量w中S给出了一个子集C_w的U:C_w = {v in U: <w, v> != 0}.那么问题是:我们能找到这样的m向量w,使得子集的并集C_w相等U.

一般的集合覆盖问题是NP完整的,但在上面的Wiki链接中有一个整数线性程序公式.

无论如何,n = 10我想这不会比你更进一步.

如果我有进一步的结果,我会继续编辑这个答案.

Answer 2

我认为使用布尔矩阵乘法将允许您更有效地解决仅使用 1 和 0 的 Mv=0 问题。使用此方法，您应该能够解决问题，而不必担心由于 RHS 等于零而导致的排名不足。以下是有关使用 BMM 的一些算法的文档链接：

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