Properties of Laplacian matrix [closed]

$\begingroup$

Prove that the Laplacian matrix $L$ of a graph $G$ satisfies the following:

1. For every vector $v \in \mathbf{R}^n$ we have $$v^TLv=\frac{1}{2}\sum_{i,j=1}^nw_{i,j}(v_i-v_j)^2$$

2. $L$ is symmetric and positive semi-definite.

3. The smallest eigenvalue of $L$ is $0$, the corresponding eigenvector is the constant vector $1$.

4. $L$ has $n$ no-negative eigenvalues $0=\lambda_1 \leq \lambda_2 \leq \cdots \leq \lambda_n$.

I don't know the proof for 3 and 4

$\endgroup$

3 Answers

$\begingroup$

You should know that Laplacian matrix $L = D D^T$ where $D$ is the incidence matrix of the graph with respect to any orientation, and $\operatorname{rank}(D) = n -\#\operatorname{components}(G)$. Thus, $L$ is positive semi-definite and eigenvalue $0$ has multiplicity $\#\operatorname{components}(G)$. The eigenvector is easy to check since each row of $D^T$ has two non-zero entries, a $1$ and a $-1$.

$\endgroup$ $\begingroup$

If it can be useful for anybody, for 1) assuming you have an undirected graph with N nodes, that $w_{i,j}$ are the coefficients of the weight matrix $W$, $d_{i,j}$ the ones of the degree matrix $D$ and that the Laplacian matrix equals to $D-W$ :

$$v^TLv=\sum_{i,j \leq N} l_{i,j}f_if_j=\sum_{i,j \leq N} (d_{i,j}-w_{i,j})f_if_j=\frac{1}{2} (\sum_id_if_i^2 - 2\sum_{i,j}w_{i,j}f_if_j+\sum_jd_jf_j^2)$$because $D$ is diagonal. Now we can use the fact that the sum of each row of $W$ equals to the degree of the matrix ie $d_i = \sum_j w_{i,j}$ :$$v^TLv=\frac{1}{2} (\sum_i \sum_j w_{i,j}f_i^2 - 2\sum_{i,j}w_{i,j}f_if_j+\sum_j \sum_i w_{i,j}f_j^2)=\frac{1}{2}\sum_{i,j}w_{i,j}(fi-fj)^2$$

For 4) L, as said before L is semi-definite positive, it's spectrum is in $R^+$

$\endgroup$ $\begingroup$

$L$ is positive semi-definite so the $L$ has no negative eigenvalues.

Take constant vector $v = 1$, $v^T Lv=0$, then we can conclude that $Lv=0$, which means that $0$ is a eigenvalue of $L$, and $1$ is the corresponding eigenvector.

$\endgroup$