In graph theory, given a graph $G$ with $n$ nodes and an edge set $E$, the Laplacian matrix is defined as the difference of the degree matrix and the adjacency matrix:
$$ L=D-A \tag{1} $$
As shown here, the quadratic form of $L$ is as follows: ($x$ is simply a function of vertices, therefore has $n$ elements) $$ \begin{align*} x^T L x &= x^T D x - x^T Ax\\ &= \sum_{i=1}^n \text{deg}(i)x_i^2 - \sum_{\{i,j\}\in E} 2x_i x_j \tag{2}\\ &=\sum_{i=1}^n \sum_{\{i,j\}\in E} x_i^2 - \sum_{\{i,j\}\in E} 2x_i x_j \tag{3}\\ &= \sum_{\{i,j\}\in E} (x_j^2+x_i^2-2x_ix_j)\tag{4}\\ &= \sum_{\{i,j\}\in E} (x_i-x_j)^2\tag{5} \end{align*} $$
Questions:
- I feel I am missing something obvious, but how do we go from $(3)$ to $(4)$?
- Is there a simple way to see from the quadratic form that the smallest eigenvalue ought to be $0$ and that as soon as the second smallest eigenvalue is $>0$ the corresponding graph must be connected?
For 1:
The sum $$\sum_{i=1}^n\sum_{\{i,j\}\in E} x_i^2$$ does the following:
For each $i$, take all of the neighbors of $i$, and add $x_i^2$ to the sum.
This means that, given any edge $\{i',j'\}$, it will appear in the sum once when the outer sum hits $i=i'$ , and once more when the outer sum hits $i=j'$. The first time, you will add $x_{i'}^2$ to the result, the second time, you will add $x_{j'}^2$ to the result. This will happen to all of the edges, therefore,
$$\sum_{i=1}^n\sum_{\{i,j\}\in E} x_i^2=\sum_{\{i,j\}\in E} (x_i^2+x_j^2)$$
For 2:
If $\lambda$ is an eigenvalue and $x$ is its eigenvector, then $$\sum_{\{i,j\}\in E} (x_i-x_j)^2 = x^TLx=\lambda \|x\|^2$$
The left side is a sum of nonnegatives, and $\|x\|^2$ is nonnegative.