Laplacian matrix and its eigenvectors and eigenvalues

69 Views Asked by At

I am reading paper written by Newman on finding community structure in a network.

I came across with the Laplacian matrix. And there is one equation derived from some others. Before diving into that, I define some important notations. Let B be $n\times n$ laplacian matrix defined on an undirected complete graph $G=(V,E)$ and $\textbf{x}_1,\textbf{x}_2,\textbf{x}_3,...,\textbf{x}_n$ are eigenvectors correspondent to $\lambda_1,\lambda_2,\lambda_3,...,\lambda_n$ eigenvalues. And vector s in $\mathbb{R}^n$ is define as $$ s_{i} = \begin{cases} 1, & \text{vertex} \space i \space\text{belongs to group 1,}\\ -1 &\text{otherwise }. \end{cases} $$ Here, groups are (there are two groups), for the sake of simplicity, based on an arbitrary division of graph $G$.

Using properties of symmetric matrices, it is possible to state that $\textbf{B}\textbf{x}_i = \lambda_i\textbf{x}_i$ and $\textbf{x}^T_{i}\textbf{x}_i=1$. Now let us write s as a linear combination: $\textbf{s}=\sum_{i=1}^n{\alpha_i\textbf{x}_i}$, where $\alpha_i=\textbf{x}^T_i\textbf{s}$.

In a paper it was said that to find the number of required edges to disconnect graph into two groups, the following equality holds. $$ \frac{1}{4}\textbf{s}^T\textbf{B}\textbf{s}. $$

And later an author provided the further derivation: $$ \frac{1}{4}\textbf{s}^T\textbf{B}\textbf{s}= \frac{1}{4}\sum_i{}\alpha_i\textbf{x}_i^T \textbf{B}\frac{1}{4}\sum_j{}\alpha_j\textbf{x}_j= \frac{1}{4}\sum_{ij}\alpha_i\alpha_j\lambda_j\delta_{ij}= \frac{1}{4}\sum_i{\alpha_i^2\lambda_i}. $$

I wonder is it possible to derive $\frac{1}{4}\sum_i{\alpha_i^2\lambda_i}$ using the following process?

$$ \frac{1}{4}\sum_i\alpha_i\textbf{x}_i^T \textbf{B}\frac{1}{4}\sum_j\alpha_j\textbf{x}_j= \frac{1}{4}\sum_i \alpha_i\textbf{x}_i^T \textbf{B} \alpha_i\textbf{x}_i = \frac{1}{4}\sum_i \alpha_i\textbf{x}_i^T \textbf{B} \textbf{x}_i\alpha_i= \frac{1}{4}\sum_i \alpha_i\lambda_i\alpha_i = \frac{1}{4}\sum_i{\alpha_i^2\lambda_i} $$