1
$\begingroup$

Let $G$ be a simple and connected graph with $n$ vertices. $d_i$ is the degree of the vertex $i$. Let $L$ be the Laplacian matrix of $G$. $D$ is a $n\times n$ diagonal matrix with the elements of diagonal are $d_i$ $i=1,...,n$. The normalized Laplacian matrix of $G$ defined to be $L_{norm} =D^{-\frac12}L D^{-\frac12}$. So why are the eigenvalues of the normalized Laplacian matrix $L_{norm}$ of graph $G$ non-negative?

$\endgroup$
0
$\begingroup$

I'll assume the minimum valency of $G$ is positve, and use $N$ for the normalized Laplacian. Suppose $x$ is a vector in $\mathbb{R}^n$ and set $y=D^{-1/2}x$. Then \[ x^TNx = y^TLy. \] Since $L$ is positive semidefinite, $y^TLy\ge0$ and it follows that $x^TNx\ge0$ for any vector $x$. Hence $N$ is positive semidefinite, and so its eigenvalues are non-negative. [The one-sentence summary of all this is that conjugate matrices have the same inertia.]

$\endgroup$
  • $\begingroup$ For the interested reader, you can go here to see why $L$ is positive semidefinite. $\endgroup$ – D Poole Mar 17 '16 at 12:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.