Explanation in a step of proving the positive semidefinite property of the graph Laplacian

Question

Here, $W$ is the adjacency matrix, $D$ is the diagonal matrix with entries $D_{ii} = \sum_{j \neq i} w_{ij} $. I'm not so sure of the second step from the last line. In particular, I can't see how

$$\sum_{i<j} w_{ij} u_i^2 = \sum_{i<j} w_{ij}u_j^2$$

I've tried drawing the summations for visualisation of the double sums, but it doesn't seem to help. Can someone provide a proof of why this is the case?

Answer 1

Visual hint: consider the way the integration limits of a double integral change when swapping the order of integration: $$\int_0^1 \int_0^x f(x,y) \, \mathrm dy \, \mathrm dx = \int_0^1 \int_y^1 f(x,y) \, \mathrm dx \, \mathrm dy. \tag{*}$$

I would use double sums for clarity:\begin{align} \sum_i \Bigl(\sum_{j \neq i} w_{ij} \Bigr) u_i^2 &= \sum_i \Bigl(\sum_{j<i} +\sum_{j>i} \Bigr) w_{ij} u_i^2 \\ &= \sum_i \sum_{j<i} w_{ij} u_i^2 +\sum_i \sum_{j>i} w_{ij} u_i^2 . \end{align}

For the first sum: rewrite it so that $j$ is the outermost index (*); then, swap the “$i$” and “$j$” labels (they are dummy variables); lastly, recall that $W$ is symmetric ($w_{ji} = w_{ij}$). \begin{align} \sum_i \sum_{j<i} w_{ij} u_i^2 &= \sum_j \sum_{i>j} w_{ij} u_i^2 \\ &= \sum_i \sum_{j>i} w_{ji} u_j^2 \\ &= \sum_i \sum_{j>i} w_{ij} u_j^2. \end{align}

Now the two sums have the same structure: $$\sum_i \Bigl(\sum_{j \neq i} w_{ij} \Bigr) u_i^2 = \sum_i \sum_{j>i} w_{ij} (u_i^2 +u_j^2).$$