Graph Laplacian

$\mathcal{G=\{V,E\}}$, node set $\mathcal{V}=\{v_1, ..., v_n\}$ and the undirected edge set $\mathcal{E}=\{e_1, ..., e_m\}$.

Cause edge is undircted, for edge $e=(i,j)$, we let $i < j$.

adjacency matrix $\bold{A}$, graph Laplacian matrix $\bold{L}$. incidence matrix $\Delta$ as $m\times n$, define as if $e_{\ell}=(i,j)$ ($i < j$), then $\ell$-th row is:

$$\Delta_{\ell} = (0, ..., -1, ..., 1, ..., 0)$$

From node $i$ to node $j$, edge $\ell$ leaves node $i$, and enters node $j$.

Then

$$\bold{L} = \Delta^{\top} \Delta$$

Proof

$$\bold{L}_{ij} = \sum_{k=1}^m \Delta_{ki} \Delta_{kj}$$

• If $i = j$, then $\bold{L}_{ij}= \sum_{k=1}^m \Delta_{ki}^2$, since $\Delta_{ki}=-1$ if edge $k$ leaves node $i$, $\Delta_{ki}=1$ if edge $k$ enters node $i$, $\bold{L}_{ij}$ is degree of node $i$
• If $i \not= j$, and there is an edge $k$ from node $i$ to node $j$, then $\Delta_{ki}=-1$, $\Delta_{kj}=1$, thus $\bold{L}_{ij}=-1$
• If $i \not= j$, and there is no edge from node $i$ to node $j$, for any edge $k$, at least one of $\Delta_{ki}$ and $\Delta_{kj}$ is 0, thus $\bold{L}_{ij}=0$