Let $G=(V,E)$ be a weighted undirected graph of $n$ nodes. Let $W$ be the weight matrix of $G$ and $D$ be a diagonal weight matrix (the entries are row/column sums of ). Let $L:=D-W$, the Laplacian (basically $L$ is a diagonally dominant matrix). I read from a paper that there are $n$ generalized eigenvalues/eigenvectors of $L$ given as follow:
$$Lf_k=\lambda_k Df_k, k=0,1,2,\dots n-1$$
with $0=\lambda_0\le\lambda_1\le\dots \le \lambda_{n-1}.$ (I know why $0=\lambda_0$)
I wonder how to prove the existence of $n$ nonnegative generalized eigenvalues.
Best Answer
I assume that we have no zero-rows, so that $D$ is invertible. Note that $$ Lx = \lambda Dx \iff\\ D^{-1/2}Lx = \lambda D^{1/2}x \iff\\ (D^{-1/2}LD^{-1/2})(D^{1/2}x) = \lambda (D^{1/2}x) $$ That is: the generalized eigenvectors of $L$ correspond to the (standard) eigenvectors of $M = D^{-1/2}LD^{-1/2}$. Because $M$ is symmetric and positive semidefinite, it must have $n$ linearly independent eigenvectors. Correspondingly, $L$ has $n$ linearly independent generalized eigenvectors.