The weighted Laplacian matrix element is given by
\begin{align}
L_{ij} \; = \; \Big( \sum_{k} w_{ik} A_{ik} \Big) \, \delta_{ij} – w_{ij} A_{ij}
\end{align}
$A_{ij}$ is the adjacency matrix element and $w_{ij}$ is the weight, $w_{ij} \in [0;1]$.
Is it positive definite?
Best Answer
It is not strictly positive definite because the constant vector has eigenvalue 0. But it is non-negative definite. Let D denote the diagonal matrix of total edge weights, and denote the diagonal entries by $d_i$. For any vector $v$, we have
$v^t(D-W)v=v^tDv-v^tWv=\sum_iv_i^2d_i-\sum_{ij}w_{ij}v_iv_j$
Now I assume that $w_{ii}=0$ and $w_{ij}=w_{ji}$. Then the second term is equal to $2*\sum_{i<j} w_{ij}v_iv_j$. Furthermore, we can rewrite the first term as $\sum_{i}v_i^2(\sum_{j>i}w_{ij}+\sum_{j<i}w_{ij})=\sum_{i<j} v_i^2w_{ij}+\sum_{i>j}v_i^2w_{ij}=\sum_{i<j}(v_i^2+v_j^2)w_{ij}$ where the last equality follow by interchanging i and j in the second sum. Putting it together, we see $v^tLv=\sum_{i<j} (v_i^2+v_j^2-2v_iv_j)w_{ij}=\sum_{i<j} (v_i-v_j)^2w_{ij}\ge 0$, as desired.