Finite symmetric networks and loop removal

A network consists of a nonempty finite vertex set $V$ and a real matrix $A=(A_{xy}{)}_{x,y\in V}$ that is symmetric and entrywise nonnegative. A diagonal entry $A_{xx}$ is a loop weight. Its loop-free part is $W=A-\mathrm{diag}(A_{xx})$, where the diagonal matrix has entries $A_{xx}$ and all off-diagonal entries zero. The support graph has vertex set $V$ and edge set $\{\{x,y\}:x\mathrm{\ne }y,W_{xy}>0\}$. Define the degree $d(x)={\sum }_{y\in V}{A}_{xy}$, counting the diagonal entry once, and put $D=\mathrm{diag}(d(x))$. The network Laplacian is $D-A$.

The matrix $D-A$ is also the weighted Laplacian of $W$: $D-A=\mathrm{diag}({\sum }_y{W}_{xy})-W$. A simple unweighted graph is represented by the special case $A_{xx}=0$ and $A_{xy}\in \{0,1\}$ for all $x,y$; its edges are precisely the pairs with $A_{xy}=1$.

Given: A network $(V,A)$ as defined above.

Goal: Verify the support-graph and Laplacian constructions and the simple-graph special case.

1.1 Choose a listing $V=\{v_1,\dots ,v_n\}$, where $n=\mathrm{\mid }V\mathrm{\mid }\ge 1$. The array $A$ becomes the square real matrix with entries $A_{v_i{v}_j}$; diagonal matrices and matrix differences here are formed entrywise. The row sums in this listing agree with the sums indexed by $V$ and do not depend on the listing. The matrix $W$ is symmetric and nonnegative, has zero diagonal, and has $W_{xy}=A_{xy}$ for $x\mathrm{\ne }y$. Thus its positive off-diagonal entries define an unordered set of two-element subsets of $V$, and the support graph is a finite simple graph. After any listing of $V$, $W$ satisfies the hypotheses of the weighted-Laplacian definition. [given, F1, F2, F3, F4]

2.1 For each $x$, ${\sum }_y{W}_{xy}=d(x)-A_{xx}$. Consequently $D=\mathrm{diag}({\sum }_y{W}_{xy})+\mathrm{diag}(A_{xx})$ and $A=W+\mathrm{diag}(A_{xx})$, so the diagonal terms cancel in $D-A$. If $A$ has zero diagonal and entries in $\{0,1\}$, its support graph has adjacency matrix $A$ in any chosen vertex order; conversely every finite simple graph on nonempty $V$ gives such a matrix. This also shows that the degree $d(x)$ retains a loop weight even though the Laplacian does not. [step 1.1, F1, F2, F3, F4, algebra] ∎