Skip to content
Dec 6, 2010

计数问题一则

我在考虑一个优化算法的时候遇到了下面的问题:

问题 1:假定 m<n,在 \mathbb{R}^n 中一个处于一般位置的 m 维子空间会经过 \mathbb{R}^n 的多少个象限?在这里「一般位置」的意思是 \mathbb{R}^n 的坐标轴全都不落在这个子空间内。

这个问题有一个几乎等价的问法:

问题 1′:假定 m<n,在 \mathbb{R}^n 中一个处于一般位置的 m 维线性流形(不经过原点)会经过 \mathbb{R}^n 的多少个象限?在这里「一般位置」的意思是 \mathbb{R}^n 的坐标轴全都不平行于这个线性流形。

如果问题 1 的解记作 F(m,n),问题 1′ 的解记作 G(m,n),通过升维,容易看出问题 1′ 可以化归为高一阶的问题 1:

F(m,n)=2\cdot G(m-1,n-1).

我一开始以为这个问题并不困难,经过了一番努力才发现它远比我想象的复杂。我所能找到的文献对这个问题的回答不早于上世纪五十年代(e.g. Schläfli 1950)。它的答案是:

 F(m,n) = 2\cdot\sum_{i=0}^{m-1} {{n-1}\choose{i}}.

有趣的是,这个数值也是下面这些问题的答案:

问题 2 (Winder 1964): 假定 m<n,在 \mathbb{R}^m 中 n 个处于一般位置的过原点的余维为 1 的超平面把 \mathbb{R}^m 划分成多少块?在这里「一般位置」的意思是其中任意 m 个超平面的法向量线性无关。

问题 3 (Cover 1965): 假定 m<n,在 \mathbb{R}^m 中给定一般位置的 n 个向量,将它们由过原点的某个余维为 1 的超平面分成黑白两组,有多少种分组方法?在这里「一般位置」的意思是其中任意 m 个向量线性无关。

在上面两个问题中,如果把「过原点」的条件去掉,即得到问题 2′ 和 3′,容易看出它们可以类似地通过升维化归为高一阶的原问题。

另一个相关的问题是:

问题 4 (Wendel 1962): 假定 m<n,在 \mathbb{R}^m 中随机给定一般位置的 n 个向量,存在一个通过原点的余维为 1 的超平面使得这些向量处于这个超平面的同一侧的概率是多少?在这里「一般位置」的意思是其中任意 m 个向量线性无关。

这个问题的答案是  F(m,n)/2^n

这些问题之间的等价性并不是特别明显,我自己花了一段时间才找到下面的直观理解(我不排除可能有更好的方式来让这些等价性变得更为显然)。

问题 1 ↔ 问题 2:记 \mathbb{R}^n 中一般位置的 m 维子空间为 \mathbb{M},容易看出 \mathbb{R}^n 的所有余维为 1 的坐标平面同 \mathbb{M} 的交集即构成 \mathbb{M} 上 n 个处于一般位置的过原点的超平面,并且它们将 \mathbb{M} 划分的块数即等于 \mathbb{M} 在 \mathbb{R}^n 中所经过的象限数。

问题 2 ↔ 问题 3:记 \mathbb{R}^m 中一般位置的 n 个向量为 \{p_i\},每个向量所对应的正交法平面为 \{P_i\},则 \{P_i\} 构成 \mathbb{R}^m 中 n 个处于一般位置的过原点的超平面,而它们把 \mathbb{R}^m 划分成的每一块中的点所对应的法平面都构成对 \{p_i\} 的一种特定的划分。

问题 1 ↔ 问题 4:在 \mathbb{M}=\mathbb{R}^m 中给定一般位置的 n 个向量 \{p_i\},它们可以被提升为 \mathbb{R}^n 的 n 个正交向量 \{\tilde p_i\} 在 \mathbb{M} 中的投影(通过对满秩 m\times n 矩阵做 SVD 分解可以很显然地看出这一点,但是我想不出有没有更直观的几何解释)。通过简单的向量计算可以看到,「存在一个通过原点的超平面使得 \{p_i\} 处于它的同一侧」这件事等价于「 \mathbb{M} 在 \{\tilde p_i\} 所张成的 n 维空间中经过第一象限」这件事。很显然这个概率等于 \mathbb{M} 所经过的所有象限数  F(m,n)  除以总象限数 2^n

有趣的是,直到现在为止,无论采用上面哪一种问题表述,我都还没有发现任何一个直观的理解能够解释为什么  F(m,n)  等于前面给出的那个数值。所有上面所列的文献中的证明几乎都基于归纳法,但是我强烈觉得某种更直接的证明应当是存在的。

Leave a Comment