1. 問題背景

在 Ball 和 Coxeter 《數學遊戲與欣賞》 固定值 的"組合設計"一章中, 有一個稱為"圖像傳送"的有趣問題。 我們發現, 作為實對稱矩陣譜定理 (spectral theorem) 的一個自然作用, 它可以用線性代數乾淨俐落地解決。 考慮到該問題的趣味性及所應用的代數結果 (譜定理) 的重要性, 在此作一詳細介紹。

問題1 (正方形問題). 如圖 1, 設正方形的四個頂點依次為 \(v_0\), \(v_1\), \(v_3\), \(v_2\)。 借用圖論的記號, 我們將整個正方形記為 \(G=(V,E)\), 其中頂點的集合為 \(V=\{v_0,v_1,v_2,v_3\}\), 邊的集合為 \(E=\{(v_0,v_1),(v_2,v_3),(v_0,v_2),(v_1,v_3)\}\)。 現在將 \(0\), \(1\), \(2\), \(3\) 四個數一對一地指定給各個頂點, 得到一個雙射 \(\phi\colon V\to W\), 其中 \(W=\{0,1,2,3\}\)。 容易看出, 這樣的雙射一共有 \(4!=24\) 個。 我們感興趣的是使得

\begin{equation} \label{eq:D} D(\phi)=\sum_{(v_i,v_j)\in E}\bigl(\phi(v_i)-\phi(v_j)\bigr)^2 \end{equation}

取得最小值的雙射 \(\phi\)。

 

我們用列向量 \(\boldsymbol{x}_{\phi} =[\phi(v_0),\phi(v_1),\phi(v_2),\phi(v_3)]^\intercal\) 來表示 \(\phi\), 並將其全體記為 \(\mathcal S(V,W)\)。 作為 \(\mathcal S(V,W)\) 上的泛函, \(D(\cdot)\) 稱為 \(G\) 上的 Dirichlet 和 $($Dirichlet sum$)$。 它可以視為位勢論中的 Dirichlet 能量 $($Dirichlet's energy$)$ 的離散版本。

Ball 和 Coxeter 介紹了問題的圖像傳送背景 (The optimum mean-square-error decoder), 亦可參見 固定值。 取而代之, 我們以電路理論來說明。

設想有一正方形電路, 每一條邊上放置一等值電阻, 不妨設其阻值為 \(1\) 歐姆。 現在我們在四個頂點施加電壓, 設頂點 \(v_i\) 上的電勢為 \(\phi(v_i)\) 伏特, 於是 \eqref{eq:D} 式表示整個線路的功率之和 (單位為瓦特)。 因此, 選取位元勢函數 \(\phi\) 將 \eqref{eq:D} 式極小化, 就相當於極小化功率; 在給定的時間內, 就相當於極小化能量, 這是非常合理的。 事實上現實的電路確實會極小化能量, 這就是著名的 Dirichlet 原理 (Dirichlet's principle)。 ^{1 1} 本文末尾給出了 Dirichlet 原理的數學表述, 並提供了一道基於這一原理的有趣練習。 電路中的一些基本結果, 例如 Kirchhoff 定律 (Kirchhoff's laws), 就可以從 Dirichlet 原理這一角度來理解。

回到問題 1, 如果我們僅僅滿足於回答這個問題, 那是非常容易的。 最笨的方法是, 對 \(24\) 個位勢函數算出各自的 Dirichlet 和 \(D(\phi)\), 再從中挑出最小的一個即可。 事實上, 我們只要稍微動動手就會發現, 本質上這裡只有 \(3\) 種不同的位元勢函數, 因為正方形有 \(8\) 重對稱性 (\(4\) 個 \(90\) 度旋轉, \(4\) 個關於對稱軸的反射), 所以 \(24/8=3\)。 事實上, 我們不妨指定 \(\phi(v_0)=0\) (根據旋轉對稱性, 這總是可以做到的), 並且可以認為 \(D(\phi)\) 由其對頂點 \(v_3\) 處的值 \(\phi(v_3)\) 確定 (這是因為存在關於對角線的反射對稱)。 於是我們只需考慮以下三種情況, 與之對應的 Dirichlet 和 \(D(\phi)\) 容易算出:

\begin{align*} \boldsymbol{x}_{\phi_0}&=[0,1,2,3]^\intercal, \qquad D(\phi_0)=(0-1)^2+(2-3)^2+(0-2)^2+(1-3)^2=10,\\ \boldsymbol{x}_{\phi_1}&=[0,1,3,2]^\intercal, \qquad D(\phi_1)=(0-1)^2+(3-2)^2+(0-3)^2+(1-2)^2=12,\\ \boldsymbol{x}_{\phi_2}&=[0,2,3,1]^\intercal, \qquad D(\phi_2)=(0-2)^2+(3-1)^2+(0-3)^2+(2-1)^2=18. \end{align*}

因此 \(\phi_0\) 以及與之等價的位元勢函數 (即經過旋轉和反射得到的 \(8\) 個位勢函數) 即為所求。

從解決問題的目標說, 問題 1 到此就結束了。 然而, 從這個解法完全看不出問題的關鍵所在。 就像數學家 Rota 經常強調的, "A problem is interesting only when it leads to ideas; nobody solves problems for their own sake, not even chess problems. You solve a problem because you know that by solving the problem you may be led to see new ideas that will be of independent interest. A mathematical proof should not only be correct, but insightful." (參見 固定值) 上述計算雖然給出答案, 卻沒有揭示問題的本質, 從追求理解 (而非答案) 的目標而言, 這個解法並不可取。

據說, 正是 Dirichlet 本人強調了"要以清晰的思想取代盲目的計算"的原則, ^{2 2} Weyl 在 固定值 中寫道: "在紀念 Dirichlet 的演講中, Minkowski 將極小原理與他稱為真正的 Dirichlet 原理的原則相比較: 前者是由 William Thompson (即 Kelvin 勳爵) 首先系統陳述並付諸五花八門的應用, 但自 Riemann 開始, 人們卻冠以 Dirichlet 的名字; 而後者則是這樣的原則, 即用最少的盲目計算, 用最多的清晰思想來解決問題。 Minkowski 說, 從這個原則開始, 數學的歷史進入了一個新的時代。" 而 Poincaré 也提出"人們應該通過思想而不是計算取得勝利"。 遵循這樣的原則, 我們重新考察問題 1, 力求給出一個基於思想而非計算的解法。

確實, 我們要求解的是一個最優化問題, 但注意到 \eqref{eq:D} 式本質上是一個二次型

$$ D(\phi)=\boldsymbol{x}_{\phi}^\intercal\boldsymbol{L}_G\boldsymbol{x}_{\phi}, $$

其中 \(\boldsymbol{L}_G\) 是一個 \(4\times4\) 的實對稱矩陣

\begin{equation} \label{eq:L_G} \boldsymbol{L}_G=\begin{bmatrix} 2 & -1 & -1 & 0 \\ -1 & 2 & 0 & -1 \\ -1 & 0 & 2 & -1 \\ 0 & -1 & -1 & 2 \end{bmatrix}. \end{equation}

我們的問題就是求二次型

\begin{equation} \label{eq:Q_G} Q_G(\boldsymbol{x})=\boldsymbol{x}^\intercal\boldsymbol{L}_G\boldsymbol{x} \end{equation}

在約束條件 \(\boldsymbol{x}\in\mathcal S(V,W)\) 下的最小值。

注意到, \(\boldsymbol{L}_G\) 是一個實對稱矩陣, 而且 \(\boldsymbol{L}_G\) 作為一個二次型 \eqref{eq:Q_G} 的係數矩陣是半正定矩陣。 應用譜定理, 我們可以將 \(Q_G\) 化成平方和。 設 \(0\leq \lambda_0\leq \lambda_1\leq \lambda_2\leq \lambda_3\) 是 \(\boldsymbol{L}_G\) 的特徵值, 而 \(\boldsymbol{u}_0\), \(\boldsymbol{u}_1\), \(\boldsymbol{u}_2\), \(\boldsymbol{u}_3\) 是對應的單位特徵向量。 (下一節我們會看到這裡的下標從 \(0\) 開始計的便利之處。) 容易看出 \(\lambda_0=0\), 對應的單位特徵向量為 \(\boldsymbol{u}_0=\frac12[1,1,1,1]^\intercal\) (因為 \(\boldsymbol{L}_G\) 每行的元素之和都等於 \(0\)), 即其特徵子空間是一維的, 這就意味著 \(\lambda_1\gt0\)。 於是, 對任意給定的 \(\boldsymbol{x}\in\mathbb R^4\), 我們有相應的 Fourier 分解 (Fourier decomposition)

$$ \boldsymbol{x}=\sum_{i=0}^3\boldsymbol{u}_i(\boldsymbol{u}_i^\intercal\boldsymbol{x}), $$

以及關於 \(Q_G\) 的譜分解 (spectral decomposition)

$$ Q_G(\boldsymbol{x})=\sum_{i=0}^3\lambda_i(\boldsymbol{u}_i^\intercal\boldsymbol{x})^2. $$

當 \(\boldsymbol{x}\in \mathcal S(V,W)\) 時, 顯然有

\begin{align*} \boldsymbol{x}^\intercal\boldsymbol{x}&=0^2+1^2+2^2+3^2=14,\\ \boldsymbol{u}_0^\intercal\boldsymbol{x}&=\frac12(0+1+2+3)=3. \end{align*}

因此, 根據 Parseval 恒等式 (Parseval's identity), 我們有

\begin{equation} \label{eq:Parseval} \sum_{i=1}^3(\boldsymbol{u}_i^\intercal\boldsymbol{x})^2 =\boldsymbol{x}^\intercal\boldsymbol{x}-(\boldsymbol{u}_0^\intercal\boldsymbol{x})^2 =14-3^2 =5. \end{equation}

而我們的目標是要最小化

\begin{equation} \label{eq:Q_G2} Q_G(\boldsymbol{x}) =\sum_{i=0}^3\lambda_i(\boldsymbol{u}_i^\intercal\boldsymbol{x})^2 =\sum_{i=1}^3\lambda_i(\boldsymbol{u}_i^\intercal\boldsymbol{x})^2, \end{equation}

這樣的問題幾乎已經是標準的線性代數問題了。 我們先把 \(\boldsymbol{L}_G\) 的譜分解求出來。 考慮到特徵值與特徵向量的求解是線性代數的基本功, 此處我們略去計算過程, 學過線性代數的讀者可自行推導。 不難解出, \(\boldsymbol{L}_G\) 餘下的三個特徵值和對應的單位特徵向量為

\begin{align*} &\lambda_1=2,\qquad \boldsymbol{u}_1=\frac12[1,1,-1,-1]^\intercal,\\ &\lambda_2=2,\qquad \boldsymbol{u}_2=\frac12[1,-1,1,-1]^\intercal,\\ &\lambda_3=4,\qquad \boldsymbol{u}_3=\frac12[1,-1,-1,1]^\intercal, \end{align*}

從而在約束條件 \eqref{eq:Parseval} 下

$$ Q_G(\boldsymbol{x}) =2(\boldsymbol{u}_3^\intercal\boldsymbol{x})^2+2\sum_{i=1}^3(\boldsymbol{u}_i^\intercal\boldsymbol{x})^2 =2(\boldsymbol{u}_3^\intercal\boldsymbol{x})^2+2\cdot5 =2(\boldsymbol{u}_3^\intercal\boldsymbol{x})^2+10 \geq10. $$

要使得 \eqref{eq:Q_G2} 最小, 當且僅當使得 \((\boldsymbol{u}_3^\intercal\boldsymbol{x})^2\) 最小, 最理想的情況當然是選取與 \(\boldsymbol{u}_3\) 正交的 \(\boldsymbol{x}\)。 對於 \(\boldsymbol{x}\in\mathcal S(V,W)\) 而言,

$$ \boldsymbol{u}_3^\intercal\boldsymbol{x}=\frac12\bigl(\phi(0)-\phi(1)-\phi(2)+\phi(3)\bigr)=0 $$

是可以辦到的, 只需取 \(\boldsymbol{x}=[0,1,2,3]^\intercal\) 即可得到 \(Q_G(\boldsymbol{x})\) 的最小值為 \(10\), 這與我們前面的答案 \(\phi_0\) 吻合。 可以看出, 若將 \(W\) 改為由任意四個給定實數構成的集合, 即 \(W\!=\!\{w_0,w_1,w_2,w_3\}\), 通過選取 \(\boldsymbol{x}\in\mathcal S(V,W)\) 使得 \((\boldsymbol{u}_3^\intercal\boldsymbol{x})^2\) 最小 (簡單地說, 就是將 \(w_0\), \(w_1\), \(w_2\), \(w_3\) 分成兩組, 每一組兩個數, 使得各組的和數盡可能均勻), 我們就可以得到使其 Dirichlet 和最小的位元勢函數 \(\phi\)。

這個方法比前面的直接計算當然要複雜, 但它的好處是讓我們對問題有了新的認識。 特別是, 我們更容易理解問題與方法的本質。 下一節我們將問題與解法推廣到高維空間的立方體 ⸺ 超立方體。

2. 推廣: 從正方形到超立方體

Ball 和 Coxeter 在《數學遊戲與欣賞》中介紹的例子其實是 \(3\) 維空間的立方體, 而一般空間的問題是類似的:

問題 2 ($n$維超立方體問題). 設 \(Q_n(V, E)\) 是 \(n\) 維空間中的超立方體構圖, 其中 \(V\), \(E\) 分別是頂點和棱的集合。 設 \(W=\{0,1,2,\dotsc,2^n-1\}\), 並考慮從 \(V\) 到 \(W\) 的所有雙射的集合 \(\mathcal S(V,W)\)。 ^{3 3} 注意, 這個集合現在非常大了, 一共包含 \((2^n)!\) 個函數。 當 \(n=3\) 時, 就是 \(8!=40320\) 個函數; 即便只考慮其對稱群 (即立方體的對稱群, 一共 \(48\) 個變換, 其描述可見 固定值) 作用下的函數, 也有 \(40320/48=840\) 個等價類。 更一般地, \(n\) 維空間中的超立方體的對稱群, 其階數則為 \(2^n\cdot n!\), 其描述可見 固定值。 問: 對哪些 \(\phi\in\mathcal S(V,W)\), 其 Dirichlet 和

$$ D(\phi)=\sum_{(v_i,v_j)\in E}\bigl(\phi(v_i)-\phi(v_j)\bigr)^2 $$

可以取到最小?

據《數學遊戲與欣賞》中的介紹, 這一問題有一個自然的解。 為描述這個解, 我們先將 \(Q_n\) 的 \(2^n\) 個頂點按照二進位標號, 在二進位編號下 \((v_i,v_j)\in E\) 當且僅當 \(i\) 和 \(j\) 的二進位表示中 僅有一個二進位位元不相同。 例如, 對於 \(n=2\) 和 \(n=3\) 的情形, 正方形 \(Q_2\) 的 \(4\) 個頂點與 立方體 \(Q_3\) 的 \(8\) 個頂點分別如圖 1 和 圖 2 標號。

 

在此標號下, 我們有下述定理。

定理 1 (Crimmins-Horwitz-Palermo-Palermo, 1969). 問題 2 的一個解由 \(\phi(v_i)=i\) 給出。

Ball 和 Coxeter 在《數學遊戲與欣賞》中給出了 \(n=3\) 情形下的證明, 並指出文獻 固定值 解決了一般情況。 然而 固定值 的證明採用了群表示論 (representation theory of groups) 的系統理論, 相對於 Ball 和 Coxeter 在書中給出的 \(n=3\) 的簡單證明, 過程太繁瑣了。 事實上, 上一節我們對 \(n=2\) 的情況採用的線性代數方法,可以毫無困難地推廣到一般的 \(n\)。 考慮到文章篇幅, 而我們重在說明方法, 以下我們僅對 \(n=3\) 的情況進行詳細展開。 一般情形的討論是類似的, 我們僅提供證明要點, 把細節留給有興趣的讀者去補全。

首先, 我們要寫出此時代表 Dirichlet 和 \(D(\phi)\) 的矩陣 \(\boldsymbol{L}_G\)。 在圖論中, 它有一個專門的名稱, 叫做圖 \(G\) 的 {Laplace 矩陣 $($Laplacian matrix$)$}, 它是分析學中作用於函數上的 Laplace 運算元的離散類比。 記 \(\boldsymbol{e}_i\) 為單位陣 \(\boldsymbol{I}\) 的第 \(i\) 列 (這裡的列指標也從零開始計), 那麼 \(\phi(v_i)=\boldsymbol{e}_i^\intercal\boldsymbol{x}_{\phi}\), 由此可得

$$ D(\phi)=\sum_{(v_i,v_j)\in E}\bigl(\phi(v_i)-\phi(v_j)\bigr)^2 =\sum_{(v_i,v_j)\in E}\boldsymbol{x}_{\phi}^\intercal \bigl((\boldsymbol{e}_i-\boldsymbol{e}_j)(\boldsymbol{e}_i-\boldsymbol{e}_j)^\intercal\bigr)\boldsymbol{x}_{\phi}, $$

因此圖 \(G\) 的 Laplace 矩陣就是

$$ \boldsymbol{L}_G =\sum_{(v_i,v_j)\in E}(\boldsymbol{e}_i-\boldsymbol{e}_j)(\boldsymbol{e}_i-\boldsymbol{e}_j)^\intercal =\sum_{(v_i,v_j)\in E} (\boldsymbol{e}_i\boldsymbol{e}_i^\intercal+\boldsymbol{e}_j\boldsymbol{e}_j^\intercal) -\sum_{(v_i,v_j)\in E} (\boldsymbol{e}_i\boldsymbol{e}_j^\intercal+\boldsymbol{e}_j\boldsymbol{e}_i^\intercal). $$

一般地, 對任意一個具有 \(m\) 個頂點 \(v_0\), \(\dotsc\), \(v_{m-1}\) 的簡單無向圖 \(G\), 其 Laplace 矩陣 \(\boldsymbol{L}_G\) 有一簡單表示

$$ \boldsymbol{L}_G=\boldsymbol{D}_G-\boldsymbol{A}_G, $$

其中

$$ \boldsymbol{D}_G=\sum_{(v_i,v_j)\in E} (\boldsymbol{e}_i\boldsymbol{e}_i^\intercal+\boldsymbol{e}_j\boldsymbol{e}_j^\intercal) $$

是對角矩陣, 稱為 \(G\) 的度數矩陣 (degree matrix), 其第 \(i\) 個對角元代表頂點 \(v_i\) 所在的邊的數目 (稱為度數); 而

$$ \boldsymbol{A}_G=\sum_{(v_i,v_j)\in E} (\boldsymbol{e}_i\boldsymbol{e}_j^\intercal+\boldsymbol{e}_j\boldsymbol{e}_i^\intercal) $$

稱為 \(G\) 的鄰接矩陣 (adjacency matrix), 依據頂點 \(v_i\) 與 \(v_j\) 是否相連, 其 \((i,j)\) 位置的元素分別取值 \(1\) 或 \(0\)。

現在回到立方體的構圖 \(G=Q_3\), 從圖 2 不難確定 \(\boldsymbol{L}_{Q_3}\) 的運算式為

$$ \boldsymbol{L}_{Q_3}=\begin{bmatrix} 3 & -1 & -1 & 0 & -1 & 0 & 0 & 0 \\ -1 & 3 & 0 & -1 & 0 & -1 & 0 & 0 \\ -1 & 0 & 3 & -1 & 0 & 0 & -1 & 0 \\ 0 & -1 & -1 & 3 & 0 & 0 & 0 & -1 \\ -1 & 0 & 0 & 0 & 3 & -1 & -1 & 0 \\ 0 & -1 & 0 & 0 & -1 & 3 & 0 & -1 \\ 0 & 0 & -1 & 0 & -1 & 0 & 3 & -1 \\ 0 & 0 & 0 & -1 & 0 & -1 & -1 & 3 \end{bmatrix}. $$

注意到 \(\boldsymbol{L}_{Q_3}\) 實際上是一個分塊矩陣

$$ \boldsymbol{L}_{Q_3} =\begin{bmatrix} \boldsymbol{L}_{Q_2}+\boldsymbol{I} & -\boldsymbol{I}\\ -\boldsymbol{I} & \boldsymbol{L}_{Q_2}+\boldsymbol{I} \end{bmatrix}, $$

其中 \(\boldsymbol{L}_{Q_2}\) 是上一節由 \eqref{eq:L_G} 式給出的矩陣 \(\boldsymbol{L}_G\) (也就是正方形 \(G=Q_2\) 的 Laplace 矩陣)。 如果我們再引進單位線段 \(Q_1\) (即一維立方體) 的 Laplace 矩陣

$$ \boldsymbol{L}_{Q_1}=\begin{bmatrix} 1 & -1 \\ -1 & 1 \end{bmatrix}, $$

那麼借助矩陣 Kronecker 乘積 (Kronecker product) 的記號, 我們可以將 \(\boldsymbol{L}_{Q_2}\) 和 \(\boldsymbol{L}_{Q_3}\) 簡記成

\begin{align*} \boldsymbol{L}_{Q_2}&=\boldsymbol{I}_2\otimes\boldsymbol{L}_{Q_1}+\boldsymbol{L}_{Q_1}\otimes\boldsymbol{I}_2,\\ \boldsymbol{L}_{Q_3}&=\boldsymbol{I}_2\otimes\boldsymbol{L}_{Q_2}+\boldsymbol{L}_{Q_1}\otimes\boldsymbol{I}_4 =\boldsymbol{I}_2\otimes\boldsymbol{I}_2\otimes\boldsymbol{L}_{Q_1} +\boldsymbol{I}_2\otimes\boldsymbol{L}_{Q_1}\otimes\boldsymbol{I}_2 +\boldsymbol{L}_{Q_1}\otimes\boldsymbol{I}_2\otimes\boldsymbol{I}_2. \end{align*}

利用 Kronecker 乘積的基本性質 \((\boldsymbol{A}\boldsymbol{B})\otimes(\boldsymbol{C}\boldsymbol{D}) =(\boldsymbol{A}\otimes\boldsymbol{C})(\boldsymbol{B}\otimes\boldsymbol{D})\) 以及 \((\boldsymbol{A}\otimes\boldsymbol{B})^\intercal=\boldsymbol{A}^\intercal\otimes\boldsymbol{B}^\intercal\), 我們不難發現, 矩陣 \(\boldsymbol{L}_{Q_3}\) 的譜分解可以利用 \(\boldsymbol{L}_{Q_1}\) 的譜分解 \(\boldsymbol{L}_{Q_1}=\boldsymbol{u}_{Q_1}\boldsymbol{\Lambda}_{Q_1}\boldsymbol{u}_{Q_1}^\intercal\) 直接進行構造。 事實上, 只需從

$$ \boldsymbol{u}_{Q_1}=\frac{1}{\sqrt2}\begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix}, \qquad \boldsymbol{\Lambda}_{Q_1}=\begin{bmatrix} 0 & 0 \\ 0 & 2 \end{bmatrix} $$

出發, 定義

$$ \boldsymbol{u}_{Q_3} =\boldsymbol{u}_{Q_1}\otimes\boldsymbol{u}_{Q_1}\otimes\boldsymbol{u}_{Q_1} =\frac{1}{2\sqrt2}\begin{bmatrix} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & -1 & 1 & -1 & 1 & -1 & 1 & -1 \\ 1 & 1 & -1 & -1 & 1 & 1 & -1 & -1 \\ 1 & -1 & -1 & 1 & 1 & -1 & -1 & 1 \\ 1 & 1 & 1 & 1 & -1 & -1 & -1 & -1 \\ 1 & -1 & 1 & -1 & -1 & 1 & -1 & 1 \\ 1 & 1 & -1 & -1 & -1 & -1 & 1 & 1 \\ 1 & -1 & -1 & 1 & -1 & 1 & 1 & -1 \end{bmatrix} $$

以及

\begin{align*} \boldsymbol{\Lambda}_{Q_3} &=\boldsymbol{I}_2\otimes\boldsymbol{I}_2\otimes\boldsymbol{\Lambda}_{Q_1} +\boldsymbol{I}_2\otimes\boldsymbol{\Lambda}_{Q_1}\otimes\boldsymbol{I}_2 +\boldsymbol{\Lambda}_{Q_1}\otimes\boldsymbol{I}_2\otimes\boldsymbol{I}_2\\ &=\rm{diag}\{0,2,2,4,2,4,4,6\}, \end{align*}

即可驗證

$$ \boldsymbol{L}_{Q_3} =\boldsymbol{u}_{Q_3}\boldsymbol{\Lambda}_{Q_3}\boldsymbol{u}_{Q_3}^{-1} =\boldsymbol{u}_{Q_3}\boldsymbol{\Lambda}_{Q_3}\boldsymbol{u}_{Q_3}^\intercal. $$

為了便於使用, 我們特徵值按從小到大編號, 得到

$$ \boldsymbol{\Lambda}_{Q_3} =\rm{diag}\{\lambda_0,\lambda_1,\lambda_2,\lambda_4, \lambda_3,\lambda_5,\lambda_6,\lambda_7\}, \qquad \boldsymbol{u}_{Q_3} =[\boldsymbol{u}_0,\boldsymbol{u}_1,\boldsymbol{u}_2,\boldsymbol{u}_4,\boldsymbol{u}_3,\boldsymbol{u}_5,\boldsymbol{u}_6,\boldsymbol{u}_7]. $$

現在回到本節一開頭提出的問題。 當 \(\phi\in\mathcal S(V,W)\) 時, 相應的 \(\boldsymbol{x}_{\phi}\) 顯然滿足

\begin{align*} \boldsymbol{x}_{\phi}^\intercal\boldsymbol{x}_{\phi}&=0^2+1^2+\cdots+7^2=140,\\ \boldsymbol{u}_0^\intercal\boldsymbol{x}_{\phi}&=\frac{1}{2\sqrt2}(0+1+2+\cdots+7)=7\sqrt2. \end{align*}

因此, 我們的目標是在約束條件

$$ \sum_{i=1}^7(\boldsymbol{u}_i^\intercal\boldsymbol{x}_{\phi})^2 =\boldsymbol{x}_{\phi}^\intercal\boldsymbol{x}_{\phi}-(\boldsymbol{u}_0^\intercal\boldsymbol{x}_{\phi})^2 =140-98 =42 $$

下最小化

$$ Q_G(\boldsymbol{x}_{\phi}) =\sum_{i=1}^7\lambda_i(\boldsymbol{u}_i^\intercal\boldsymbol{x}_{\phi})^2. $$

注意到 \(\lambda_1=\lambda_2=\lambda_3\lt\lambda_4=\lambda_5=\lambda_6\lt\lambda_7\), 因此對任意的 \(\phi\in\mathcal S(V,W)\) 我們總有

$$ \sum_{i=1}^7\lambda_i(\boldsymbol{u}_i^\intercal\boldsymbol{x})^2 \geq\lambda_1\sum_{i=1}^7(\boldsymbol{u}_i^\intercal\boldsymbol{x})^2 =42\lambda_1 =84, $$

並且等號成立當且僅當對一切 \(\lambda_i\gt\lambda_1\) 總有 \(\boldsymbol{x}_{\phi}\perp \boldsymbol{u}_i\), 即 \(\boldsymbol{x}_{\phi}\perp \rm{span}\{\boldsymbol{u}_4,\boldsymbol{u}_5,\boldsymbol{u}_6,\boldsymbol{u}_7\}\), 亦即 \(\boldsymbol{x}_{\phi}\) 屬於子空間 \( \rm{span}\{\boldsymbol{u}_0,\boldsymbol{u}_1,\boldsymbol{u}_2,\boldsymbol{u}_3\}\)。

注意到, 對於自然碼給出的函數

$$ \phi\colon v_i\mapsto i\qquad (\text{\(i=0\), \(1\), \(\dotsc\), \(7\)}), $$

其表示向量 \(\boldsymbol{x}_{\phi}=[0,1,2,3,4,5,6,7]^\intercal\) 恰好屬於零特徵值和最小 正特徵值對應的不變子空間 \( \rm{span}\{\boldsymbol{u}_0,\boldsymbol{u}_1,\boldsymbol{u}_2,\boldsymbol{u}_3\}\), 這是因為

\begin{equation} \label{eq:linear_combination} \boldsymbol{x}_{\phi} =\sum_{i=0}^3\boldsymbol{u}_i\boldsymbol{u}_i^\intercal\boldsymbol{x}_{\phi} =\sqrt2\,(\boldsymbol{u}_0-\boldsymbol{u}_1) +2\sqrt2\,(\boldsymbol{u}_0-\boldsymbol{u}_2) +4\sqrt2\,(\boldsymbol{u}_0-\boldsymbol{u}_3). \end{equation}

事實上只要將 \(\boldsymbol{u}_0-\boldsymbol{u}_1\), \(\boldsymbol{u}_0-\boldsymbol{u}_2\), \(\boldsymbol{u}_0-\boldsymbol{u}_3\) 這三個向量視覺化 (如圖 3 所示) 便可看出 \eqref{eq:linear_combination} 式與二進位的關係。

   

至此, 三維情形下的問題 2 就解決了。 回過頭看, 我們所用到的最重要的資訊就是 \(\boldsymbol{L}_{Q_3}\) 的譜分解。

我們補充幾點評論:

1. 上面我們僅僅證明了自然碼確實是原問題的一個解, 事實上自然碼及其等價類 (此時要考慮的是立方體的對稱群, 這是一個 \(48\) 階的群, 見 固定值) 也是僅有的解。 這個問題我們不擬討論, 留給有興趣的讀者。 建議的一個途徑是將正交性條件 \(\boldsymbol{x}_{\phi}\perp \rm{span}\{\boldsymbol{u}_4,\boldsymbol{u}_5,\boldsymbol{u}_6,\boldsymbol{u}_7\}\) 視為線性方程組並討論 \(\phi\in\mathcal S(V,W)\) 的解的個數: 如果除了群作用之外得到的解, 再沒有其它的解, 則唯一性就確立了。

2. 上述方法可以推廣到一般的 \(Q_n\)。 事實上, 一個基本的觀察是 \(Q_n\) 是 \(Q_1\) 的 \(n\) 次冪, 這裡冪次所採用的乘積是{圖的 Descartes 乘積 (Cartesian product of graphs)}, 是從兩個圖出發構造出一個新圖的最簡單運算。 我們之所以能夠歸納得到 \(Q_n\) 的譜資訊, 是因為我們有下述一般的結果 (例如, 見 固定值[p. 1, 引理 3.26] 以及 固定值[p. 62]):

定理 2. 設 \(G_1\) 和 \(G_2\) 是兩個圖, 分別具有 \(m\) 和 \(n\) 個頂點, 其鄰接矩陣 (或 Laplace 矩陣) 分別為 \(\boldsymbol{A}_1\) 和 \(\boldsymbol{A}_2\)。 則它們的 Descartes 乘積 \(G_1\times G_2\) 的鄰接矩陣 (或 Laplace 矩陣) 為 \(\boldsymbol{A}_1\) 與 \(\boldsymbol{A}_2\) 的 Kronecker 和 (Kronecker sum) \(\boldsymbol{A}_1\otimes\boldsymbol{I}_n+\boldsymbol{I}_m\otimes\boldsymbol{A}_2\)。

由此不難推出下述結論: 若 \(G_1\) 和 \(G_2\) 的鄰接矩陣 (或 Laplace 矩陣) 的特徵對分別為 \((\lambda_i,\boldsymbol{u}_i)\) 和 \((\mu_j,\boldsymbol{v}_j)\), (\(i=1\), \(\dotsc\), \(m\), \(j=1\), \(\dotsc\), \(n\)), 則它們的 Descartes 乘積 \(G_1\times G_2\) (頂點按照 \(G_1\) 和 \(G_2\) 的頂點指標字典排序) 鄰接矩陣的特徵對為 \((\lambda_i+\mu_j,\boldsymbol{u}_i\otimes\boldsymbol{v}_j)\) (\(i=1\), \(\dotsc\), \(m\), \(j=1\), \(\dotsc\), \(n\))。

關於 \(Q_n\) 的其它圖論性質, 可瀏覽維基百科條目 Hypercube graph。 為了解決問題 2, 唯一的關鍵是, \(\boldsymbol{x}_n=[0,1,2,3,\dotsc,2^n-1]^\intercal\) 這個向量可以表示為屬於 零特徵值和最小正特徵值的特徵向量的線性組合 (當 \(n=3\) 時即為 \eqref{eq:linear_combination} 式)。 一般的情形下可用歸納法證明: 設 \(\boldsymbol{x}_{n-1}=[0,1,2,3,\dotsc,2^{n-1}-1]^\intercal\) 屬於 \(\boldsymbol{L}_{Q_{n-1}}\) 的零特徵值和最小正特徵值對應的不變子空間。 注意到

\begin{align*} \boldsymbol{x}_{n}&=[0,1,2,3,\dotsc,2^{n}-1]^\intercal\\ &=\boldsymbol{x}_{n-1}\otimes[1,1]^\intercal+2^{n-1}[0,\dotsc,0,1,\dotsc,1]^\intercal\\ &=\boldsymbol{x}_{n-1}\otimes[1,1]^\intercal+2^{n-2}[-1,\dotsc,-1,1,\dotsc,1]^\intercal +2^{n-2}[1,1,\dotsc,1]^\intercal. \end{align*}

顯然, 第三項 \(2^{n-2}[1,1,\dotsc,1]^\intercal\) 屬於 \(\boldsymbol{L}_{Q_{n}}\) 的 零特徵值的特徵子空間, 又根據定理 2 之推論, 第一項 \(\boldsymbol{x}_{n-1}\otimes[1,1]^\intercal\) 屬於 \(\boldsymbol{L}_{Q_{n}}\) 最小 正特徵值對應的特徵子空間。 現在只要說明, 第二項 \([-1,\dotsc,-1,1,\dotsc,1]^\intercal\) 也屬於 \(\boldsymbol{L}_{Q_{n}}\) 最小 正特徵值對應的特徵子空間, 而

$$ [-1,\dotsc,-1,1,\dotsc,1]^\intercal =[-1,1]^\intercal\otimes[1,1]^\intercal\otimes\cdots\otimes[1,1]^\intercal, $$

根據定理 2 之推論, 這是顯然的。

附帶說一句, 這一歸納構造實際上還給出了 \(2^n\) 階的 Hadamard 矩陣 (Hadamard matrix)。 若一個 \(n\) 階矩陣 \(\boldsymbol{H}\) 的每個元素都取自 \(\{1,-1\}\), 且滿足 \(\boldsymbol{H}^\intercal\boldsymbol{H}=n\boldsymbol{I}_n\), 則稱 \(\boldsymbol{H}\) 為 Hadamard 矩陣。 關於 Hadamard 矩陣, 有著名的 Hadamard 猜想 (Hadamard conjecture)\textemdash 對任意 正整數 \(k\) 總存在 \(4k\) 階的 Hadamard 矩陣。 這一猜想至今仍懸而未決。 有興趣的讀者可瀏覽維基百科條目 Hadamard matrix。

3. 與群表示論的方法相比, 矩陣方法的優點是突出了問題的本質: 求對應的 Laplace 矩陣的最小正特徵值及其特徵向量。 應該指出的是, 一個連通圖(即任意兩個頂點可以通過一條道路連接的圖)的 Laplace 矩陣的最小特徵值為零, 且其重數恰好為 \(1\) (這一點很容易證明, 也可見 固定值[p. 63])。 因此, 對我們此處所討論的最小化問題, 零特徵值的資訊用處不大, 最重要的資訊都反映在最小正特徵值及其特徵向量上。

3. 一個電路問題

最後, 我們想給讀者拋出一個類似的問題。 多年以前, 這類問題一直令筆者之一 (林) 困惑不已。 最近在考慮本文的問題時, 筆者才發現, 這無非也只是基本的線性代數, 而且更簡單。

問題 3. 如圖 4, 有一個四面體電路, 每條棱上的電阻都一樣大。 若在一個頂點加電壓 \(V\), 另一個頂點接地, 則餘下兩個頂點的電勢是多大?

 

讀者也許可以提出自己的解法。 我們想到的一個想法是利用 Dirichlet 原理 ⸺ 電勢的分佈使得總功率最小。 Dirichlet 原理的詳細敘述如下 (見 固定值[p. 299, 定理 1]):

定理 3 (Dirichlet原理). 設 \(G=(V,E)\) 是一個無向圖, \(V\), \(E\) 分別是頂點與邊的集合; 設在每條邊 \((v_i,v_j)\in E\) 上給定一個電阻 \(r_{i,j}\gt0\)。 又設在某些頂點 \(v_1\), \(\dotsc\), \(v_k\) 處施加了電壓, 則由所有頂點的電壓值所確定的位元勢函數 \(\phi\) 使得

$$ E(\phi)=\sum_{(v_i,v_j)\in E}\frac{\bigl(\phi(v_i)-\phi(v_j)\bigr)^2}{r_{i,j}} $$

取得最小值。

最後我們指出, 圖和網路其實是線性代數的一個重要應用領域, 參見 Strang 的經典著作《線性代數導論》 固定值 第 10 章"線性代數的應用"第 1 節。 ^{4 4} 電子版可見 https://math.mit.edu/~gs/linearalgebra/ila5/linearalgebra5_10-1.pdf .

致謝

感謝上海交通大學吳耀琨教授和西北工業大學郭佳教授對初稿提出寶貴建議。

參考文獻

本文作者林開亮任教西北農林科技大學理學院, 邵美悅任教復旦大學大數據學院