이번 글에서는 그래프 (graph)의 Laplacian matrix (라플라시안 행렬)과 Laplacian matrix의 성질들을 알아보겠다. Laplacian matrix는 positive definite matrix이고 이에 따라 eigen value가 0보다 크거나 같으며 Laplacian matrix의 eigen value에는 무조건 0이 있다는 것까지 알아보자.
Laplacian matrix의 정의
방향이 없는 undirected simple graph $G=(V,E)$가 있다고 하자. 편하게 $V=\{1,2,3,…,n\}$이라 표현하겠다. $\mathbf{D}$를 이 graph $G$의 degree matrix라 하고 $\mathbf{A}$를 adjacency matrix 라고 하자. $D$의 $i$번째 row, $j$번째 column의 원소 $D_{ij}$에 대하여 $i\neq j$이면 $D_{ij}=0$ 이고 $D_{ii}$는 $i$번째 vertex의 degree ($i$를 원소로 갖는 edge의 수)로 정의한다. $A$의 $i$번째 row, $j$번째 column의 원소 $A_{ij}$는 $i$와 $j$가 edge로 이어져 있다면 $A_{ij}=1$이라 정의하고 아니라면 $A_{ij}=0$이라고 정의한다. Laplacian matrix는 $D$와 $A$를 이용해서 아래와 같이 정의한다.
$$L := D – A \tag{Laplacian matrix}\label{Laplacian Matrix} $$
Laplacian matrix는 그래프 $G$에 대한 정보를 담고 있는데 이것에 대해서는 추후 다뤄보기로 하고 Laplacian matrix의 성질부터 알아보자.
Laplacian matrix의 성질
Laplacian matrix를 구성하는 $\mathbf{D}$와 $\mathbf{A}$가 symmetric matrix이므로 Laplacian matrix $L$또한 symmetric matrix임을 알 수 있다. 여러 계산을 통해 Laplacian matrix $L$이 positive definite matrix임을 알 수 있다.
Laplacian matrix는 positive definite matrix
$D_{ii} = \sum_{j} A_{ij}$라는 사실과 $\mathbf{D}$와 $\mathbf{A}$가 symmetric matrix라는 사실을 이용하면 아래와 같이 Laplacian matrix $L$이 positive definite matrix 임을 알 수 있다. $x= (x_1,x_2,..,x_n)^T$라고 하면$$\begin{align} x^T L x &= x^T D x – x^T A x \\ & = \sum_{i} D_{ii} x_i^2 – \sum_{i,j} A_{ij} x_ix_j \\ &= \sum_{i} x_i^2 \sum_{j} A_{ij} -\sum_{i,j} A_{ij} x_ix_j \\ &=\frac{1}{2}\left( \sum_{i} x_i^2 \sum_{j} A_{ij} + \sum_{j} x_j^2 \sum_{i} A_{ij} – 2 \sum_{i,j} A_{ij} x_ix_j \right)\\ &=\frac{1}{2}\sum_{i,j} A_{ij} (x_i – x_j)^2 \geq 0 \end{align}$$
Laplacian matrix의 eigen value의 범위
위에서 Laplacian matrix $L$이 positive semi definite 임을 보였다. 따라서 $L$의 eigen value는 0보다 크거나 같다.
0이 Laplacian matrix의 eigen value인 이유
$u = (1,1,…,1)^T$이라 하자. 그러면 $D_{ii} = \sum_{j} A_{ij}$라는 사실을 이용하면 $Lu = \mathbf{0}$이라는 것을 금방 알 수 있다.
Reference