谱图理论

现在我们想用线性代数的方法来研究组合数学问题。

邻接矩阵的特征值

对于任意的无向图\(G=(V,E)\)（假设不带边权），它可以用邻接矩阵\(A_G\)来表示。\(A_G\)是一个对称矩阵，因此它一定有\(n\)个实数特征值。我们把它们记为\(\mu_1 \geq \mu_2 \geq \cdots \geq \mu_n\)。（这里我们不用\(\lambda\)而是用\(\mu\)是因为我们之后还要把\(\lambda\)用到别的地方）

比如，我们来解完全图\(K_n\)的特征值。此时的邻接矩阵除了对角线以外是全1的。我们当然可以采取解特征方程\(|A_G-\mu I|=0\)的方法来暴力解出特征值，但在这里我们有更简单的方法。我们立即观察到\(A_G x=\mu x\)在\(x\)全1时是成立的，因为乘以全1的向量相当于给矩阵的每行求和，而此时矩阵每行的和都为\(n-1\)。因此我们发现了特征向量\((1,1,\cdots,1)\)和特征值\(n-1\)。如果存在其它的特征向量，那么它必须垂直于\((1,1,\cdots,1)\)，因为不同的特征子空间是正交的。这样的向量必须满足\(x_1+\cdots+x_n=0\)，代入\(A_Gx\)得到的向量正好是\((-x_1,-x_2,\cdots,-x_n)\)。因此我们又发现\(-1\)是特征值，并且这个矩阵只有\(n-1\)和\(-1\)这两个特征值，不可能再有别的特征值了。

\(\mu_1\)与图的度数

\(K_n\)恰好是一个每个点度数都相等的图，也就是\(d\)-regular graph。我们在上学期的线性代数课上其实已经证明过\(d-\)regular graph的最大特征值\(\mu_1\)就一定等于\(d\)。当时我们用的方法直接深入到了底层的运算当中，用放缩和夹逼的方法证明了我们的结论。现在我们从更高的角度来给出一种更简单的证明方法，为了使用这种方法，我们首先要引入范数的概念。

向量的\(p\)范数定义为\(\|x\|_p=\left(\sum\limits_{i=1}^{n}|x_i|^p\right)^\frac{1}{p}\)，当\(p=0\)时，特别地定义为非零位的个数。 当\(p=1\)时，这就是向量间的曼哈顿距离。当\(p=2\)时，它就是我们最熟悉的Euclid距离。当\(p=+\infty\)时，我们利用放缩和夹逼定理（我们将会看到这就是为什么“巧合地”我们在上学期的线性代数课的证明中也用到了放缩和夹逼）可以证明它就等于最大的\(|x_i|\)，即\(\|x\|_\infty=\max\limits_{1\leq i\leq n}|x_i|\)。所谓“范数”就是给出对象的一种长度的度量，p-范数是我们所熟悉的“Euclid距离（2-范数）”的一般情形。

现在我们希望能给矩阵也定义一个“范数”。怎么理解矩阵的“长度”呢？我们知道矩阵对应着一个线性映射， 因此我们把矩阵的范数定义为这个线性映射最多可以把某个向量拉长多少倍，而对向量长度的度量可以采用上面定义的向量的范数。因此矩阵的p-范数就定义为\(\|A\|_p=\max\limits_{x}\dfrac{\|Ax\|_p}{\|x\|_p}\)。由于\(x\)的数乘不会影响放大的倍数，所以我们完全只需要取单位向量就能定义矩阵的范数了，所以它可以更简单地写为\(\|A\|_p=\max\limits_{\|\omega\|_p=1}\|A\omega\|_p\)。基于这样的定义我们也直接地得到了一个不等式\(\forall x\)，\(\|A\|_p \geq \dfrac{\|Ax\|_p}{\|x\|_p}\)，也就是\(\|Ax\|_p \leq \|A\|_p\|x\|_p\)。

对于矩阵的无穷范数，可以直接计算得到一个简单的结果：由于\(\|A\|_\infty=\max\limits_{\|\omega\|_\infty=1}\|A\omega\|_\infty\)，其中\(\|A\omega\|_\infty\)就是指向量\(A\omega\)中绝对值最大的那一个坐标，也就是\(A\)中特定某一行与\(\omega\)的内积的绝对值。而\(\|\omega\|_\infty=1\)要求的就是最大那一维坐标的绝对值为1，也就是每一维坐标的绝对值都不能超过1，因此\(A\omega\)的最大坐标一定不能超过\(A\)中某一行元素的绝对值之和，而显然我们是可以取到这样一个\(\omega\)使得\(A\omega\)恰好就是这行元素的绝对值之和的。因此我们证明了\(\|A\|_\infty\)就是\(A\)的绝对值之和最大的那一行元素的绝对值之和，即\(\|A\|_\infty=\delta=\max\limits_{i}\sum\limits_{j=1}^{n}|A_{ij}|\)。

由此可见，对于任意一个邻接矩阵，它的无穷范数就是图的最大度数，因为邻接矩阵的每一行的元素绝对值之和就是这个点的度数，其最大值就是图的最大度数。那么对于邻接矩阵\(A_G\)，假设它的\(\mu\)对应特征向量\(x_0\)，那么\(A_Gx_0=\mu x_0\)。两边同时取无穷范数，得\(\|A_Gx_0\|_\infty=\|\mu x\|_\infty\)。根据我们不等式放缩，左边\(\leq \|A_G\|_\infty\|x_0\|_\infty\)，而右边就等于\(|\mu| \cdot \|x_0\|_\infty\)，同时约去\(\|x_1\|_{\infty}\)，我们就得到了一个有趣的结论：\(|\mu| \leq \|A_G\|_{\infty}\)。最大的特征值一定不超过图的最大度数！

那么我们就直接可以证明\(d\)-regular情形下的结论了。此时有\(|\mu| \leq d\)，而显然对于向量\(x=(1,1,\cdots,1)\)来说一定满足\(A_Gx=dx\)，因此最大的特征值就等于\(d\)，即\(\mu_1 =d\)。