Graph Laplacians and their basic properties

In the following we always assume that $G$ is an undirected, weighted graph with weight matrix $W$, where $w_{ij} = w_{ji} \geq 0$. When using eigenvectors of a matrix, we will not necessarily assume that they are normalized. For example, the constant vector $\Bbb1$ and $a$ multiple $a\Bbb1$ for some a 6= 0 will be considered as the same eigenvectors. Eigenvalues will always be ordered increasingly, respecting multiplicities.By "the first k eigenvectors" we refer to the eigenvectors corresponding to the k smallest eigenvalues.

1. The unnormalized graph Laplacian

   The unnormalized graph Laplacian matrix is defined as

   $L = D - W$.

   Proposition 1 (Properties of L) The matrix $L$ satisfies the following properties:
   　　 (1). For every vector $f \in \Bbb R^n$ we have 　　

   　　 $f'Df=\frac {1}{2} \sum _{i,j=1}^n w_{i,j}(f_i-f_j)^2$ 　　
   　　 (2). $L$ is symmetric and positive semi-definite.
   　　 (3). The smallest eigenvalue of $L$ is 0, the corresponding eigenvectoris the constant one vector $\Bbb1$.
   　　 (4). $L$ has $n$ non-negative, real-valued eigenvalues $0 = \lambda_1 \leq \lambda_2 \leq ...\leq \lambda_n$.

   Proposition 2 (Number of connected components and the spectrum of L) Let $G$ be an undirected graph with non-negative weights. Then the multiplicity $k$ of the eigenvalue 0 of $L$ equals the number of connected components $A_1, ... , A_k$ in the graph. The eigenspace of eigenvalue 0 is spanned by the indicator vectors $\Bbb1_{A_1}, . . . , \Bbb1_{A_k}$of those components. //证明咩看懂

2. The normalized graph Laplacians

   There are two matrices which are called normalized graph Laplacians in the literature. Both matrices are closely related to each other and are defined as

   $L_{sym} := D^{-1/2}LD^{-1/2} = I - D^{-1/2}W D^{-1/2}$
   $L_{rw} := D^{-1}L = I - D^{-1}W$.

   Proposition 3 (Properties of $L_{sym}$ and $L_{rw}$) The normalized Laplacians satisfy the following properties:
   　　 (1). For every $f \in \Bbb R^n$ we have 　　

   　　 $f'L_{sym}f = \frac{1}{2}\sum_{i,j=1}^nw_{i,j}(\frac {f_i}{\sqrt d_i}-\frac {f_j}{\sqrt d_j})^2$ 　　
   　　 (2). $\lambda$ is an eigenvalue of $L_{rw}$ with eigenvector $u$ if and only if $\lambda$ is an eigenvalue of $L_{sym}$ with eigenvector $w = D^{1/2}u$.
   　　 (3). $\lambda$ is an eigenvalue of $L_{rw}$ with eigenvector $u$ if and only if $\lambda$ and $u$ solve the generalized eigenproblem $Lu = \lambda Du.$
   　　 (4). 0 is an eigenvalue of $L_{rw}$ with the constant one vector $\Bbb 1$ as eigenvector. 0 is an eigenvalue of $L_{sym}$ with eigenvector $D^{1/2} \Bbb 1$.
   　　 (5). $L_{sym}$ and $L_{rw}$ are positive semi-definite and have n non-negative real-valued eigenvalues$0 = \lambda_1 \leq \lambda_2 \leq ...\leq \lambda_n$.
   

   Proposition 4 (Number of connected components and spectra of $L_{sym}$ and $L_{rw}$) Let $G$ be an undirected graph with non-negative weights. Then the multiplicity $k$ of the eigenvalue 0 of both $L_{rw}$ and $L_{sym}$ equals the number of connected components $A_1,..., A_k$ in the graph. For $L_{rw}$, the eigenspace of 0 is spanned by the indicator vectors $\Bbb 1_{A_i}$ of those components. For $L_{sym}$, the eigenspace of 0 is spanned by the vectors $D^{1/2} \Bbb 1_{A_i}$.