1
$\begingroup$

In graph theory the Laplacian matrix, $L$, is given by $$L=D-A$$

For simple graphs $D$ is a diagonal matrix where $$D_{ii}=deg(v_i)$$ and $A$ is its adjacency matrix.

Suppose we now consider the more general case of a weighted graph such that $$A_{ij}=w_{ij}$$ where $w_{ij} \in \mathbb{C}$. Define $D$ such that $$D_{ii}=\sum_j w_{ij}.$$ We will also require that $L$ is hermitian which implies $D$ is real and $A$ is also hermitian ($w_{ij} = w^*_{ji}$).

How do we prove that $L$ is still positive semi-definite? I've looked at proofs online but most only cover the case of simple graphs. My thought process is to approach this using the quadratic form of $L$. That is

$$x^\dagger L x= \sum_{(i,j)\in E(G)} w_{ij}(x_i-x_j)^2$$ but not too sure where to go from here.

$\endgroup$
1
  • 1
    $\begingroup$ Choose $D_{ii}=\sum_j|w_{ij}|$ instead, then by Gershgorin theorem it will always work. If you choose $\sum w_{ij}$, then $D_{ii}$ may not be always real. But you need a Hermitian matrix. $\endgroup$
    – G_0_pi_i_e
    Sep 5, 2018 at 4:43

1 Answer 1

2
$\begingroup$

If you assume $\Re(w_{ij})\geq 0$, then as you said, assume $x$ is real-valued, $$\begin{split} x^T L x &= \sum_{i,j}w_{ij}(x_i-x_j)^2\\ &= \bigg(\sum_{i < j} w_{ij}(x_i-x_j)^2\bigg) + \bigg(\sum_{i > j} w_{ij}(x_i-x_j)^2\bigg) \\ &= \bigg(\sum_{i < j} w_{ij}(x_i-x_j)^2\bigg) + \bigg(\sum_{i > j} w_{ji}^\star(x_i-x_j)^2\bigg) \\ &= \bigg(\sum_{i < j} w_{ij}(x_i-x_j)^2\bigg) + \bigg(\sum_{i < j} w_{ij}^\star(x_j-x_i)^2\bigg) \\ &= \bigg(\sum_{i < j} w_{ij}(x_i-x_j)^2\bigg) + \bigg(\sum_{i < j} w_{ij}^\star(x_i-x_j)^2\bigg) \\ &= \sum_{i<j} (w_{ij}+w_{ij}^\star)(x_i-x_j)^2\\ &= 2\sum_{i<j} \Re(w_{ij})(x_i-x_j)^2\\ &\geq 0 \end{split} $$

$\endgroup$
2
  • $\begingroup$ Doesn't this argument only guarantee that $L$ is positive semi-definite in the case when $\mathcal{R}(w_{ij})\geq 0$ for all $(i,j) \in E(G)$? $\endgroup$
    – asett
    Sep 4, 2018 at 12:45
  • 1
    $\begingroup$ Yeah, it does. Good point. I edited my answer accordingly. $\endgroup$ Sep 4, 2018 at 12:47

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .