目录
Spielman D. A. Spectral and Algebraic Graph Theory.
概
设计 Hypercube 的特征值和特征向量的证明着实有趣, 特此记录.
Hypercube
-
对于两个加权图 \(G = (V, E, v)\) 和 \(H = (W, F, w)\) 而言, \(G \times H\) 表示点集为 \(V \times W\), 边集为:
\[\Big((a, b), (\hat{a}, b)\Big) \text{ with weight } v_{a, \hat{a}}, \quad \forall (a, \hat{a}) \in E, \: b \in W, \\ \Big((a, b), (a, \hat{b})\Big) \text{ with weight } w_{b, \hat{b}}, \quad \forall (b, \hat{b}) \in F, \: a \in V \\ \]的图.
-
倘若 \(G\) 的(拉普拉斯矩阵)特征值和特征向量分别为 \(\lambda_1, \ldots, \lambda_n\), \(\bm{\alpha}_1, \ldots, \bm{\alpha}_n\), \(H\) 的(拉普拉斯矩阵)特征值和特征向量分别为 \(\mu_1, \ldots, \mu_m\), \(\bm{\beta}_1, \ldots, \bm{\beta}_m\). 那么 \(G \times H\) 具有特征值和特征向量:
\[\gamma_{ij} = \lambda_i + \mu_j \\ \bm{\eta}_{ij} = \bm{\alpha}_i \otimes \bm{\beta}_j \]其中 \(\otimes\) 表示克罗内克积.
proof:
\[\begin{array}{ll} L\bm{\eta} &= [(L_G \otimes I_W) + (I_V \otimes L_H)] \bm{\eta} \\ &= (L_G \otimes I_W) \bm{\eta} + (I_V \otimes L_H) \bm{\eta} \\ &= (L_G \otimes I_W) (\bm{\alpha}_i \otimes \bm{\beta}_j) + (I_V \otimes L_H) (\bm{\alpha}_i \otimes \bm{\beta}_j) \\ &= (L_G \otimes I_W) (\bm{\alpha}_i \otimes \bm{\beta}_j) + (I_V \otimes L_H) (\bm{\alpha}_i \otimes \bm{\beta}_j) \\ &= (L_G \bm{\alpha}_i) \otimes (I_W \bm{\beta}_j) + (I_V \bm{\alpha}_i) \otimes (L_H \bm{\beta}_j) \\ &= \lambda_i \bm{\alpha}_i \otimes (I_W \bm{\beta}_j) + \mu_j (I_V \bm{\alpha}_i) \otimes \bm{\beta}_j \\ &= (\lambda_i + \mu_j) \bm{\alpha}_i \otimes \bm{\beta}_j. \end{array} \]-
Hypercude 实际上就是点集 \(V = \{0, 1\}^d\), 然后边集为:
\[\tag{1} \{(\bm{x}, \bm{y}): \text{nonzero}(\bm{x} - \bm{y}) = 1, \forall \bm{x, y} \in V \}. \] -
在不考虑 weight 的情况下, 它实际上就是 one-edge graph \(\times_{n-1}\) 的结果.
-
注意到 \(H_1\) 有特征值 \(0, 2\), 和对应的特征向量:
\[\left ( \begin{array}{c} 1 \\ 1 \end{array} \right ), \left ( \begin{array}{c} 1 \\ -1 \end{array} \right ). \]根据上面的结论可知, 给定 \(H_{d-1}\) 的特征向量 \(\bm{\psi}\) 和它的特征值 \(\lambda\), 我们有特征向量:
\[\left ( \begin{array}{c} \bm{\psi} \\ \bm{\psi} \end{array} \right ), \left ( \begin{array}{c} \bm{\psi} \\ -\bm{\psi} \end{array} \right ), \]以及其对应的特征值: \(\lambda, \lambda + 2\).
-
通过归纳法容易证明, \(H_d\) 的有特征值 \(2i, 0 \le i \le d\), 且重数为 \(C_d^i\), 特征向量为:
\[\bm{\psi_y(x)} = (-1)^{\bm{y}^T\bm{x}}, \quad \forall \bm{y} \in \{0, 1\}^d. \]
Generalizing Hypercubes
-
之前的 hypercube 要求满足 (1) 这一硬性要求, 接下来我们考虑更加广义上 hypercube. 假设我们有一些 generators \(\{\bm{g}_i \in \{0, 1\}^d: i=1,2,\cdots, k\}\), 则广义的 hypercube 定义为 \(G = (V, E)\) 其中:
\[E := \{(\bm{x}, \bm{x} + \bm{g}_i): \bm{x} \in V, 1\le i \le k\}. \] -
之前 hypercube 可以认为是:
\[\bm{g}_i[j] = 1 \text{ if } j = i, \text{ else } 0, \quad i=1,2,\ldots, d. \] -
接下来我们证明, 对于任意的 \(\bm{b} \in \{0, 1\}^d\), 向量
\[\bm{\psi_b}: \bm{\psi_b}(\bm{x}) = (-1)^{\bm{b}^T\bm{x}} \]为 \(G\) 的(拉普拉斯矩阵的)特征向量, 且特征值为:
\[k - \sum_{i=1}^k (-1)^{\bm{b}^T \bm{g}_i}. \]
proof:
首先注意到:
\[\bm{\psi_b}(\bm{x + y}) = \bm{\psi_b}(\bm{x}) \bm{\psi_b}(\bm{y}). \]令 \(L\) 为 \(G\) 的拉普拉斯矩阵, 则有
\[\begin{array}{ll} (L \bm{\psi_b})(\bm{x}) &= k \bm{\psi_b(\bm{x})} - \sum_{i=1}^k \bm{\psi_b(x + g_i)} \\ &= k \bm{\psi_b(\bm{x})} - \sum_{i=1}^k \bm{\psi_b(x) \psi_b(g_i)} \\ &= \bm{\psi_b(\bm{x})}(k - \sum_{i=1}^k \bm{\psi_b(g_i)}). \end{array} \]注: 上面的证明中, 我们用着 \(L\bm{\psi_b}(\bm{x})\) 这种表示方式, 我们可以把 \(\bm{x}\) 看成是一个结点的序, 而不要拘泥于其本身的数值, 这是非常有意思的概念.
标签：psi,bm,beta,alpha,otimes,array,Hypercube From： https://www.cnblogs.com/MTandHJ/p/17295812.html