昨晚 zhy 和我讨论这样一个问题,

假如 $n$ 维欧氏空间中有 $n$ 个向量,它们夹角最小值记为 $t$,那么 $t$ 的最大值是多少?

于是可以表述成

假如 $n$ 维欧氏空间中有 $n$ 个向量,它们内积最大值记为 $t$,那么 $t$ 的最小值是多少?

大概一眼看去,就觉得这个问题嘛,最优解一定是对称的,所以记 $n$ 个单位向量为 ${e_i}, i = 1, 2, \ldots, n$,然后记内积最大值为 $t$,那么 $<e_i, e_j>\leq t, i\neq j$。

于是

于是就可以得出 $t\geq - \frac{1}{n-1} $,然后我们证明这个最小值可以取到,假设我们有一个矩阵 ,然后

容易证明这是一个半正定矩阵(取子方阵的行列式),然后就可以求 $\sqrt{A^TA}$,结果就应该是 $A$ 矩阵。

而且这个思路应该对 $n$ 维空间取 $k$ 个向量 $(k\leq n)$ 也是成立的结果是 $-\frac{1}{k-1}$,只需要在低维空间中取点,直接延拓到高位空间即可。但是在 $k>n$ 的时候,虽然上面那个不等式可以放缩,但是在 $n$ 维空间中取这样的向量应该是取不到的,貌似是因为这个空间的维数起到了限制。

这个题目的来源是 zhy 这个学期上的自动化系的一个研究生课,叫做凸优化。他经常找我吐槽这门课,给我讲过凸集分离定理、支撑超平面定理和一点点凸优化里面的槽点。听起来就非常有趣,我也十分种草,也许以后可以上一门数学规划 II 之类的课呢。


这个问题是一个未解之谜,叫做 spherical code problem,原来的问题是说,在 $n$ 维球面上取 $k$ 个点,使得它们之间的最小距离最大化。现在,对于 $k \leq n+1$ 有解,我们已经解出来了。并且对于 $k = 2^n$ 也是有解的,应该是一个立方体。对于一般的 $k$ 是没有解的。