这个问题可能更多是数学而不是编程。我还没有找到最终答案,但至少有一些想法在这里:
我们可以用以下方式重新陈述问题。
问题A: 固定正整数 m
和 n
。设 S
为由 0
或 1
组成的 n
维向量集合。是否存在任何一个 m
行 n
列的由 0
或 1
组成的矩阵 M
,使得对于 S
中的任意两个不同向量 v_1
和 v_2
,向量 Mv_1
和 Mv_2
都不同。(或者说,将矩阵 M
视为从 n
维向量到 m
维向量的函数,在集合 S
上是单射的。)
简言之:给定一对(m,n),是否存在这样的单射M?
问题A等同于原问题。确实,如果对于集合S中的两个不同的v1和v2,Mv1 = Mv2,则我们有M(v1-v2)= 0,并且向量v1-v2将只具有0,1,-1作为条目。反之亦然。
另一种重新解释是:
问题B:设
m
、
n
为正整数,
S
为由0和1组成的n维向量集合。我们能否在
S
中找到
m
个向量
r_1, ..., r_m
,使得对于
S
中任意两个不同的向量
v_1
和
v_2
,都存在一个
r_i
,满足
<v_1, r_i> != <v_2, r_i>
?其中
<x, y>
是通常的内积。
简而言之:
我们能否选择m
个向量在S
中,通过与这些向量的内积来区分S
中的每个向量?
问题B等价于问题A,因为你可以用
S
中的
m
个向量来识别矩阵
M
。
接下来,我将自由使用问题的两种描述。
让我们称对偶 (m, n) 为“好对”,如果问题A(或B)的答案是“是”。根据问题B的描述,对于给定的n,存在一个最小的m使得(m, n)是一个好对。我们将写m(n)表示与n相关联的这个最小的m。同样,对于给定的m,存在一个最大的n,使得(m, n)是好的。这是因为,如果(m, n)是好的,即存在一个如问题A所述的单射M,那么对于任何n' <= n,擦除M的任何n-n'列将给出一个单射M'。让我们写n(m)表示与m相关联的这个最大的n。因此,任务变成了计算函数m(n)和/或n(m)。
We first prove several lemmas:
Lemma 1: 我们有
m(n + k) <= m(n) + m(k)
。
Proof: 如果
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
。
证明:在引理1中取
k = 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)
。
回到编程问题
我必须说我还没有想出一个好的算法。你可以将问题重新表述为集合覆盖问题,如下所示:
设 U
为由元素为 1
、0
或 -1
的向量组成的 n
维向量集合,S
如上所述。对于集合 S
中的每个向量 w
,都会有一个由 U
中的向量构成的子集 C_w
: C_w = {v in U: <w, v> != 0}
。问题是:我们是否可以找到 m
个向量 w
,使得所有 C_w
的并集等于 U
。
一般的集合覆盖问题是 NP 完全问题,但在上面的维基链接中提供了整数线性规划公式。
无论如何,我猜这不能让你更进一步,当 n = 10
时,我会继续编辑此答案,如果有更多结果。
M
可能是方的和规则的,并且问题要求一个具有非零元素的向量。必须检查M
是否有一个非平凡的核,其中包含来自{0,1,-1}
的非零向量元素。 - Codor