谱图与代数图论读书笔记2

Jun 22, 2020 00:00 · 413 words · 2 minute read graph math spectral algerbraic graph theroy

谱图理论第二章用于描述矩阵作为自然的优化方案存在的，并给出min max theorem，并通过谱定理来证明Courant-Fischer Theorem理论，之后通过该理论证明谱定理。

第三章用于描述拉普拉斯矩阵的一些性质以及通过拉普拉斯矩阵的特征值对图进行绘制。

第二章特征值以及优化

Hermitian matrix（埃尔米特矩阵）

Hermitian matrix（埃尔米特矩阵）也被称为自伴随矩阵，矩阵的第i行第j列的元素都与第j行第i列的元素的复共轭。

由于本书并不是讨论线性代数的书，对于图所表示的矩阵，不会出现虚数，因此，我们只探求埃尔米特矩阵的特殊形式实对称矩阵，其具有以下性质：

实对称矩阵的特征值都是实数，并且不同特征值对应的特征向量相互正交
如果其特征值都是整数，称这个矩阵是正定的，若为非负，则称为半正定。
对于一个实对称矩阵，$ A^n $与逆矩阵$ A^T $都是实对称矩阵

谱定理（T 1.3.1)

如果矩阵M是一个n*n并且是一个实对称矩阵，那么存在n个特征值，使得其对应的特征向量相互正交。

Courant-Fischer Theorem（T 2.0.1）

这里引入一个瑞丽商(Rayleigh quotient)的概念，对于一个向量x，关于M的瑞丽商定义为:

$$ \dfrac {x^TMx}{x^Tx} $$

假设$ M\phi = \mu\phi $，很显然，其中的$ \mu $即M的特征值，$ \phi$为特征向量，对于$ x=\phi $我们可以知道

$$ \dfrac{\phi^TM\phi}{\phi^T\phi} = \dfrac {\phi^T \mu \phi}{\phi^T\phi} = \mu$$

CF定理所阐明的是当x是使瑞丽商最大化的向量时，其正好是M最大特征值的特征向量。

对于一个实对称矩阵，且其特征值$ \mu_1 \geq \mu_2 \geq …\geq \mu_n $，我们可以得到：

$$ \mu_k = max_{S \subseteq \mathbb{R}^n \& dim(S) = k} min_{x\in S \& x \neq 0} \dfrac {x^TMx}{x^Tx} $$

通过上面的定理我们可以知道，对于一个矩阵的最大特征值$ \mu_n = max \dfrac {x^TMx}{x^Tx} $ ，该定理在接下来的证明中具有相当重要的作用。

首先我们为了证明2.0.1引入一个引理（L 2.1.1）：

对于一个实对称矩阵M，具有特征值$ \mu_1,..,\mu_n $，以及一系列相互正交的特征向量$ \phi_1,…,\phi_n $，将x 通过这一组基向量进行表示：

$$ \textbf{x} = \sum^{n}_{i=1} c_i\phi_i $$

这样我们可以将x带入瑞丽商中：

$$ \begin{aligned} x^TMx = (\sum_ic_i\phi_i)^TM(\sum_ic_i\phi_i) \ = (\sum_ic_i\phi_i)^T(\sum_ic_i \mu_i\phi_i) \ = \sum_{i,j}c_ic_j\mu_j\phi_i^T\phi_j \end{aligned} $$

由于$ \phi $相互正交，则上式可以化简为: $ x^TMx = \sum_i c_i^2 \mu_i $

回到证明2.0.1上来，前置条件如上，设S是该向量空间的一部分，也就是说，对于$ S\subseteq\mathbb{R}^n $并且$ dim(S) = k $，我们可以扩展X得到：

$$ \textbf{x} = \sum_{i=1}^{k}c_i\phi_i $$

带入瑞丽商得到$ x^TMx = \dfrac{\sum_{i=1}^k\mu_ic_i^2}{\sum_{i=1}^kc_i^2} \geq \dfrac{\sum_{i=1}^k\mu_kc_i^2}{\sum_{i=1}^kc_i^2} = \mu_k $

所以 $ min_{x \in S} \dfrac{x^TMx}{x^Tx} \geq \mu_k $，我们可以得到在一个k维空间中，$ \mu_k $与瑞丽商之间的关系，但是我们很好的思考到，在整个n维空间中的任意k维子空间的关系：

于是，我们设T为$ \phi_k,…,\phi_n $这一系列的特征向量组成的空间，因此，其维度为$ n-k+1 $对于所有的k维子向量S，很明显，两者之间会有一个维度是重叠的，因此我们尝试比较这两者的关系：

$$ min_{x \in S}\dfrac{x^TMx}{x^Tx} \leq min_{x\in S \cap T} \dfrac{x^TMx}{x^Tx} \leq max_{x\in T} \dfrac{x^TMx}{x^Tx} $$

（上式通过类似于上面瑞丽商的展开就可以得到，至于后面这一个max基本同理。）

又对于$x \in T$上进行求证：

$$\dfrac{x^TMx}{x^Tx} \leq \mu_k$$

当S与T只在$ \mu_k $对应的特征向量上相交时，$ min_{x \in S}\dfrac{x^TMx}{x^Tx} = max_{x\in T} \dfrac{x^TMx}{x^Tx}=\mu_k $ 从而我们可以推出：

$$ \mu_k = max_{S \subseteq \mathbb{R}^n \& dim(S) = k} min_{x\in S \& x \neq 0} \dfrac {x^TMx}{x^Tx} $$

定理 T 2.2.1

对于一个实对称矩阵M，使得x作为一个非0的向量，并使得瑞丽商可以得到最大，即：

$$ x = argmax_{x \in \mathbb{R}} \dfrac{x^TMx}{x^Tx} $$

那么x满足$ Mx = \mu_1x $，其中，$ \mu_1 $是M最大的特征值。相反，瑞丽商最小时对应的是最小的特征值。

谱定理相关证明

首先对2.2.1进行证明：

为了求得瑞丽商的极值，我们计算其梯度:

$$ \nabla x^Tx = 2x $$

$$ \nabla x^TMx = 2MX$$

我们通过使$ \nabla f(x) = 0 $得到：

$$ (x^Tx)Mx = (x^TMx)x $$

$$ Mx = \dfrac{x^TMx}{x^Tx}x $$

当瑞丽商最大时，瑞丽商是M最大的特征值。

由此，我们可以扩展出定理2.2.2：

对于M的特征向量，我们可以得到：

当$ \mu_1 $的时候，$\phi_1 \in argmax_{||x||=1}x^TMx$（这里是由于x的模为1，那么分母就自然而然的等于1了）

对于 $ 2\leq \mu_i\leq n $ ，$ \phi_i \in argmax_{||x|| = 1 \& x^T\phi_i = 0,for j > i}x^TMx $

对于2.2.2的证明，这里就不赘述了，基本上是通过构造附加的矩阵来计算并且推导关于特征值与瑞丽商的关系。

更近一步，我们还能得到对于$ x_1,x_2,…,x_n $且满足

$$ x \in argmax_{||x|| = 1 \& x^Tx_j = 0,forj<i} x^TMx$$

则每一个x都是M的特征向量。

第三章拉普拉斯矩阵以及图像的绘制

第二章通过对于矩阵的几点定理来推进对于矩阵的理解，第三章开始将图与矩阵相结合，通过矩阵来得到图相关的性质以及相关的应用。

拉普拉斯矩阵

第一章曾经提到过有关拉普拉斯的定义以及证明，在这里我们对于通过二次型进行重新梳理一下，

对于一个加权图$ G = (E,V,w), w:E\rightarrow\mathbb{R}^+$，定义拉式矩阵的二次型为:

$$ x^TL_Gx = \sum_{(a,b)\in E}w_{a,b}(x(a)-x(b))^2 $$

对于上述二次型的展开，我们在第一章已经证明过了，在这里就不要再来一遍了。

我们接下来引入$ \delta_a $表示元素在方向a上面的基本单位向量，对于两个点的一张图，$ x(a)-x(b) = (\delta_1^T-\delta_2^T)x $

$$ \begin{aligned} x^TL_Gx = \sum_{(a,b)\in E}w_{a,b}((\delta_1^T-\delta_2^T)x)^2 \ = \sum_{(a,b)\in E} w_{a,b}x^T(\delta_1-\delta_2)(\delta_1^T-\delta_2^T)x \end{aligned}$$

因此，$ L_G = \sum_{(a,b)\in E}w_{a,b}(\delta_a - \delta_b)(\delta_a - \delta_b)^T = \sum_{(a,b) \in E}w_{a,b}L_{G_{a,b}} $

对于每一个向量x都有$ (L_Gx)(a) = d(a)x(a)-\sum_{(a,b)\in E}w_{a,b}x(b) $

在sagt书上写的还可以继续往下引申的式子，我认为只有在$ w_{a,b}=1 $时才成立:

$(L_Gx)(a) = \sum_{(a,b\in E)}w_{a,b}(x(a)-x(b))$

T 3.1.1 拉普拉斯矩阵对于联通图的性质

对于一个图G，其拉普拉斯矩阵的特征值为$ 0=\lambda_1\leq\lambda_2\leq…\leq\lambda_n $，如果第二个特征值不为0，那么图是联通的。

虽然很显而易见，这里还是做一些说明，对于一个非联通图，我们可以将其拉普拉斯矩阵分为两个部分：

$$ L = \begin{bmatrix} L_{G_1} \ 0 \\ 0 \ L_{G_2} \end{bmatrix} $$

所以L必定有两个相互正交的特征向量$ \begin{bmatrix} 0 \\ 1\end{bmatrix} $ 以及$ \begin{bmatrix} 1 \\ 0 \end{bmatrix} $ ，这个1代表的是全1矩阵，于是L一定会有两个特征值都等于0显然上述的特点是有效的。

关于拉普拉斯矩阵的特征值对于绘图的几点猜测

拉普拉斯矩阵根据其二次型可以看到，如果将x看作是点，那么$ (x(a) - x(b))^2 $可以看作是在平面上两点之间的距离，为了使距离最短，我们可以对其进行化简，总之最后通过拉普拉斯最小的且不等于0的特征向量所画出的图通常都是比较易得的，另外在图着色问题上，矩阵也是会取得不错的效果，详细的在第四章可以得到证明。

我有一个不成熟的猜测，对于一个二维的图，我们可以得到关于其的特征向量以及特征值，对于特征向量，一个全联通图会有n-1个特征向量并且相互正交，我们在第一章可以看到，将整个特征向量绘制会呈现出跳跃式的数据迁移，有没有可能是每一个特征值对应的特征向量都是该矩阵在某个基向量的投影，也就是说当我们画图的时候，我们可以用最小的非零特征值的向量与第二小的来进行绘制，其绘制出的图形是非常易看的。当然这只是一个猜测，并没有进行证明，嘿嘿嘿，别信这里的话哦！！！

第二章 特征值以及优化