考虑 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，这可能更有效。
这个问题可能比编程更数学。我还没有找到最终的答案，但至少有一些想法在这里：
我们可以通过以下方式重新陈述问题。
问题 A：修正正整数
m和n. 设S是其条目为或的n维向量集。是否存在其条目为或的任何by矩阵，使得对于任何两个不同的向量和在 中，向量和是不同的。（或者，您可能会说，矩阵，被认为是从维向量到维向量的应用，在集合 上是单射的。）01mnM01v_1v_2SMv_1Mv_2MnmS
简而言之：给定对(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的集合。我们能否找到中的向量，使得对于任何一对不同的向量和中，存在一个满足的？这是通常的内积。n01mr_1, ..., r_mSv_1v_2Sr_i<v_1, r_i> != <v_2, r_i><x, y>
简而言之：我们可以通过取内积来选择m向量S来区分每个人吗？S
问题 B 等价于问题 A，因为您可以用 中的M向量m来识别矩阵S。
在下文中，我将自由地使用这两种问题的描述。
如果问题 A（或 B）的答案是yes ，我们就称这对(m, n)为“好对” 。
通过对问题 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)最大值。nm
所以任务变成了计算函数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)byn矩阵M都会给出一个映射 fromS到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- 1SwSC_wUC_w = {v in U: <w, v> != 0}mwC_wU
一般的 Set Cover 问题是 NP 完全问题，但在上面的 Wiki 链接中有一个整数线性规划公式。
n = 10无论如何，我猜这不能让你走得更远。
如果我有进一步的结果，我会继续编辑这个答案。
我认为使用布尔矩阵乘法可以让您更有效地解决仅用 1 和 0 的 Mv=0 问题。使用这种方法，您应该能够解决，而不必担心由于 RHS 等于零而导致的排名不足。以下是有关使用 BMM 的一些算法的文档链接：
如果我理解了这个问题，那么您要的是给定的 m,n，如果存在一个矩阵 M，（线性变换），它具有一个微不足道的内核，即 Ker(M)={0}。
回想一下，这与 M 的 Nullspace 为零 0，Null(M)=0 相同。
对于系统 Mv=0，如果矩阵 M 的秩等于 v 的维数，则零空间为 {0}。所以您的问题归结为询问是否存在秩为 dim(v)=m 的 mxn 矩阵。这种形式的问题已在此处讨论过
您还可以根据行列式来构建这个问题，因为如果 M 的行列式 = 0，那么零空间是不平凡的。因此，您可以从构造一个矩阵的角度来考虑这个问题，该矩阵的条目在 {-1,0,1} 中具有所需的行列式。
我希望这有帮助。