计数问题一则 – Imaginary

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

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

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

问题 1′：假定 m<n ，在 $\mathbb{R}^n$ 中一个处于一般位置的维线性流形（不经过原点）会经过 $\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$ 中个处于一般位置的过原点的余维为 1 的超平面把 $\mathbb{R}^m$ 划分成多少块？在这里「一般位置」的意思是其中任意个超平面的法向量线性无关。

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

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

另一个相关的问题是：

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

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

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

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

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

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

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