n維空間里的n個向量的最小夾角的最大值是什麼？

01-12

二維的話是180，三維是120（正三角形的中心到三個頂點），四維看上去是正四面體的中心到四個頂點，大概109？
一個平凡的下界是90，即兩兩垂直。利用一些小技巧，可以歸納證明對任意n，這個最大值都嚴格大於90.
可以猜測當n趨於無窮時，這個最大值趨於90.
另外，題目中的n維空間似乎可以改成n-1維。
這道題的背景是，n個隨機變數，兩兩間最大相關係數的最小值是什麼。

答案區里有個類似問題：n維空間里最多存在幾個向量，使兩兩夾角大於90°？
有興趣的答主不妨一起算了。

求最小夾角可以改成求單位向量內積的最大值，也就是

$min max_{i,j,i e j} X_i cdot X_j$

大膽放縮一下

$max_{i,j,i e j} X_i cdot X_j ge frac{1}{n(n-1)}sum_{i,j,i e j} X_i cdot X_j$

$= frac{1}{n(n-1)}left((sum_i X_i)^2 - sum_i X_i^2 ight) = frac{1}{n(n-1)}left((sum_i X_i)^2 - n ight) ge -frac{1}{n-1}$

等號成立條件是任意 $X_i cdot X_j, i e j$ 都相等，且 $sum_i X_i = 0$ ，也就是所有向量夾角兩兩相等，且和為0，下面我們構造一個讓等號成立的向量組，可以將條件改寫成矩陣：

$X^T X = left(egin{array}{cccc}1 -frac{1}{n-1} ... -frac{1}{n-1} \ -frac{1}{n-1} 1 ... -frac{1}{n-1} \ ... \ -frac{1}{n-1} -frac{1}{n-1} ... 1end{array} ight)$

右邊這個矩陣的n-1重特徵值是 $frac{n}{n-1}$ ，剩下一個特徵值是0，0對應的特徵向量是 $V_n = frac{1}{sqrt{n}} (1 ... 1)^T$ ，剩下n-1個特徵向量比較簡單的一種構造方法是：

$V_k = frac{1}{sqrt{k^2 + k}}(egin{array}{ccccccc}1 1 ... -k 0 ... 0end{array})^T$

括弧內由k個1，1個-k，剩下為0的向量組成。很容易驗證它們是相互正交的。

令

$Q = left(egin{array}{cccc}V_1 V_2 ... V_nend{array} ight)^T$

則

$X^T X = Q^T left(egin{array}{ccccc}frac{n}{n-1} \ frac{n}{n-1} \ ... \ frac{n}{n-1} \ 0end{array} ight)Q$

$(QX^T)^T(QX^T) = left(egin{array}{ccccc}frac{n}{n-1} \ frac{n}{n-1} \ ... \ frac{n}{n-1} \ 0end{array} ight)$

直接簡單讓

$QX^T = left(egin{array}{ccccc}sqrt{frac{n}{n-1}} \ sqrt{frac{n}{n-1}} \ ... \ sqrt{frac{n}{n-1}} \ 0end{array} ight)$

則

$X = left(egin{array}{ccccc}sqrt{frac{n}{n-1}} \ sqrt{frac{n}{n-1}} \ ... \ sqrt{frac{n}{n-1}} \ 0end{array} ight)Q$

這是一個簡單的行操作，將Q的前n-1行乘以 $sqrt{frac{n}{n-1}}$ ，最後一個坐標置0，注意到Q的每一行就是我們前面求出的 $V_k$ ，所以結果就是

$X = sqrt{frac{n}{n-1}}left(egin{array}{ccccc}V_1 V_2 ... V_{n-1} 0end{array} ight)^T$

也可以求出具體的表達式，留作課後習題（？），不過這裡還有一個更簡單的方法：

我們改讓

$QX^T = left(egin{array}{ccccc}sqrt{frac{n}{n-1}} \ sqrt{frac{n}{n-1}} \ ... \ sqrt{frac{n}{n-1}} \ 0end{array} ight)Q$

這樣

$X = Q^Tleft(egin{array}{ccccc}sqrt{frac{n}{n-1}} \ sqrt{frac{n}{n-1}} \ ... \ sqrt{frac{n}{n-1}} \ 0end{array} ight)Q$

$sqrt{frac{n-1}{n}}X = Q^Tleft(egin{array}{ccccc}1 \ 1 \ ... \ 1 \ 0end{array} ight)Q$

是個對稱陣，而且特徵向量也是 $V_k$ 。由於 $V_n$ 對應的特徵值為0，也就是說有：

$sqrt{frac{n-1}{n}}X_k cdot V_n = 0$

我們還可以注意到， $sqrt{frac{n-1}{n}}X$ 是冪等的，這說明它是個投影矩陣。又由於它的秩是n-1，又剛好滿足 $sqrt{frac{n-1}{n}}X_k cdot V_n = 0$ ，所以它就是往 $V_n$ 的正交子空間上投影的矩陣。

這可就有意思了，那我們還需要用Q來計算X嗎？直接通過投影的內積關係，就可以寫出：

$sqrt{frac{n-1}{n}}X_k = old i_k - (old i_k cdot V_n)V_n = (egin{array}{cccccc}-frac{1}{n} -frac{1}{n} ... frac{n-1}{n} -frac{1}{n} ...end{array})^T$

驗證一下內積：

$X_i cdot X_j = frac{n}{n-1}(frac{n-2}{n^2} - frac{n-1}{n^2} - frac{n-1}{n^2}) = -frac{1}{n-1}$

不考慮歸一化的話，最簡單的向量表達式就是：

n個坐標中，有 $n-1$ 個-1，最後一個為 $n-1$ 。
比如4維的情況下，就是(3,-1,-1,-1), (-1,3,-1,-1), (-1,-1,3,-1), (-1,-1,-1,3)

夾角為 $arccosleft(-frac{1}{n-1} ight)$

不難發現這個X和我們最開始得到的內積結果的矩陣只差一個係數，這也是跟投影導致的冪等性相關聯的。

從幾何意義上來解釋最終這個結論：

我們在n維空間中任取n個兩兩垂直的單位向量（一般也可以叫做單位正交基），求出它們的和的向量，作與這個向量垂直的超平面，然後將所有的單位向量投影到這個超平面上，得到的就是n維空間中n個向量兩兩成的角最大的情況。比如說，將一個直角投影到y = -x上，就得到了平面上成的角最大的情況；將一個立方體某個角上的三條邊，沿立方體對角線投影到垂直的平面上，就得到了一個互成120°角的三維空間中成角最大的情況。

等價於

$ext{min} ; s$ , $ext{s.t.} ; s geq X_{ij} ; (i eq j)$ , $X_{ii} = 1$ , $X succeq 0$ , $X in mathbb{R}^{n imes n}$

猜一個，答案應該是 $X_{ij} = s ; (i eq j)$

所以現在變成

$ext{min} ; s$ , $ext{s.t.} ; s = X_{ij} ; (i eq j)$ , $X_{ii} = 1$ , $X succeq 0$ , $X in mathbb{R}^{n imes n}$

注意到 $|X| = (1-s)^{n-1} (1+(n-1)s)$

所以要保證 $X succeq 0$ 的最小 $s$ 為 $-frac{1}{n-1}$ , 所以答案是 $arccos left( -frac{1}{n-1} ight)$

計算一下n維空間中n+1個單位向量兩兩點積的和然後不等式放縮一下就知道了。我得到的上界是acos(-1/n)。等號取到的條件是向量和為0，而且兩兩夾角相等，這個可以用歸納法構造出來。

======================================================

考慮 $n$ 維空間的 $n+1$ 個單位向量 $v_1, v_2, cdots, v_{n+1}$ ,

我們有

$2 sum_{i<j} langle v_i, v_j angle = |sum_i v_i|^2 - sum_i |v_i|^2 geq -sum_i |v_i|^2 = -(n+1)$ .

假設向量之間兩兩夾角的最小值是 $heta$ ，那麼

$n(n+1)cos heta geq 2 sum_{i<j} langle v_i, v_j angle geq -(n+1)$ .

從而

$heta leq arccos(-1/n)$ .

等號取到的條件是 $sum_i v_i = 0$ ，且所有的 $langle v_i, v_j angle$ 相等。

構造：

一維的就是 -1 和 +1。假設我們已經構造了 $n$ 維空間的 $n+1$ 個單位向量 $v_1, v_2, cdots, v_{n+1}$ , 滿足上述兩個條件，假設所有的 $langle v_i, v_j angle=K$ 。我們對這 $n+1$ 個向量加上第 $n+1$ 維的分量 $x$ ，即 $v_i = (v_{i,1}, v_{i,2},dots, v_{i,n},x)$ ，並新增加一個向量 $v_{n+2}=(0, 0, dots, -ncdot x)$ 。取 $x$ 滿足 $K+x^2=-n x^2$ ,這樣的 $x$ 是能找到的，因為 $K<0$ 。最後單位化一下向量，可以驗證這樣的向量組在 $n+1$ 維空間滿足條件。

靈魂畫手又來了！貢獻一個高中生都能看懂的方法。

首先用直覺想一下，n 維空間中的 n 個向量，至少可以做到兩兩成直角。

所以，本題的答案至少是直角，很有可能是鈍角。

那麼，如果 n 個向量兩兩成鈍角，它們在空間中大約應該排成什麼樣子呢？

大約應該排成下圖中各個粗箭頭的樣子。