本文的拉普拉斯$L=L_{norm}=I-D^{\frac{-1}{2}}A{D}^{\frac{-1}{2}}$。

Rayleigh quotient

Defination

$$R(A,x)=\frac{x^{T}Ax}{x^{T}x}$$

Property

实对称阵$A$，假设其特征值${\lambda }_1\ge {\lambda }_2\ge \dots {\lambda }_n$，则

$$\begin{gathered} \underset{x}{max}R(A,x)={\lambda }_1 \\ \underset{x}{min}R(A,x)={\lambda }_n \end{gathered}$$

TIP

下面给出证明：

• 首先证明$R(A,x)\in [{\lambda }_n,{\lambda }_1]$:
  实对称阵存在正交分解，令$A=U\mathrm{\Lambda }{U}^T$，则

$$\begin{array}{rl}R(A,x)& =\frac{x^{T}Ax}{x^{T}x}\\ & =\frac{(U^{T}x{)}^T\mathrm{\Lambda }{U}^{T}x}{x^{T}U{U}^{T}x}\\ & =\frac{y^T\mathrm{\Lambda }y}{y^{T}y}\\ & =\frac{\sum {\lambda }_i(y_i{)}^2}{(y_i{)}^2}\end{array}$$

这里，$y=U^{T}x$。显然通过上式能够得到${\lambda }_n\le R(A,x)\le {\lambda }_1$。

• 下面证明$R(A,x)$能够取值${\lambda }_n\mathrm{和}{\lambda }_1$。
  由于$U=[u_1,u_2\dots U_n]$，其中$u_i$为一组正交基。则$x$可以表示$x=\sum k_i{u}_i=[k_1,\dots ,k_n][u_1,\dots ,u_n{]}^T$，这里令$|x|=1$。$y=U^{T}x$。

$$R(A,x)=\frac{y^T\mathrm{\Lambda }y}{y^{T}y}=\sum {\lambda }_i{k}_i^2$$

这里注意到$|x|=\sum k_i^2=1$，于是，取$k_1=1\mathrm{和}{k}_n=1$可以完成证明。

Laplacian

证明$L=I-D^{\frac{-1}{2}}A{D}^{\frac{-1}{2}}$的特征值$\lambda \in [0,2]$。

TIP

下面给出证明

• 首先证明$A_{norm}$的特征值$-1\le {\alpha }_n\le \cdots \le {\alpha }_1\le 1$。
  记$A_{norm}=D^{\frac{-1}{2}}A{D}^{\frac{-1}{2}}$，$L=I+A_{norm}$。这里，$I+A_{norm},L$可证明半正定的。

$$\begin{gathered} x^T(I+A_{norm})x=\sum x_i^2+\sum _{(i,j)\in E}(\frac{x_2}{\sqrt{d_i}}+\frac{x_j}{\sqrt{d_j}})\ge 0 \\ {x}^{T}x\ge -x^T{A}_{norm}x \\ g(A_{norm},x)\ge -1 \end{gathered}$$

同样，由$x^T(I-A_{norm})x\ge 0$可以得到$g(A_{norm},x)\le 1$。

• 接下来，证明$L$特征值$\lambda \in [0,2]$，只要证$g(L,x)\in [0,2]$即可。

$$g(L,x)=\frac{x^{T}Lx}{x^{T}x}=\frac{x^T(I-A_{norm})x}{x^{T}x}=1-g(A_{norm},x)$$

由于$g(A_{norm},x)\in [-1,1]$，可以立刻得到$g(L,x)\in [0,2]$。即$L$特征值${\lambda }_L\in [0,2]$。