I'm reading this paper, and I have a some questions about a property of the graph Laplacian matrix.
Definitions
Let $G\triangleq\langle V,E \rangle$ be a graph (without loops for simplicity), where $V\triangleq\{1,2,\dots, n\}$ is the set of nodes and $E \subseteq V\times V$ is the set of edges. Moreover, for every node $i\in V$ define the set of neighbors of $i$ as $$N_i\triangleq\{j\in V:(i,j)\in E\} \qquad i=1,2,\dots,n$$ and the degree of node $i$ as $d_i\triangleq |N_i|$, i.e. the cardinality of $N_i$.
Now, denote as $t$ the time variable and let $x_i:t\in[0,\infty)\mapsto x_i(t)\in\mathbb{R}$ be the state of node $i\in V$. Suppose that the dynamic of every node is given by $$\dot{x}_i = \sum_{j\ \in N_i} x_j-x_i \qquad i=1,2,\dots,n \tag{1}$$ here I'm denoting as $\dot{x_i}$ the time derivative of $x_i$, i.e. $$\dot{x}_i \triangleq \frac{\text{d}x_i}{\text{d} t}\qquad i=1,2,\dots,n$$
By introducing the collective state as the $n$-variate column vector $x\triangleq[x_1\, \dots\, x_n]'$ ($'$ is the transpose operator), the $n$ equations in $(1)$ can be rewritten in a compact form as $$\dot{x}=-Lx$$ where $L=[\ell_{ij}]$ is the graph Laplacian matrix, whose entries are given by $$\ell_{ij}\triangleq \begin{cases} -1 & \text{if }\, j \in N_i\\ d_i & \text{if }\, j = i \\ 0 & \text{else} \end{cases}$$
The graph Laplacian can be decomposed in the difference $$L=D-A$$ where $D\triangleq \text{diag}(d_1, \dots, d_n)$ is the degree matrix and $A=[a_{ij}]$ is the adjacency matrix, whose elements are defined as $$a_{ij}\triangleq \begin{cases} 1 & \text{if }\, (i,j) \in E\\ 0 & \text{else} \end{cases}$$
Questions
The graph Laplacian $L$ satisfies the following SOS (sum of squares) property (equation 10 of the paper) $$x'L x = \frac{1}{2}\sum_{(i,j)\in E} a_{ij} (x_j-x_i)^2$$
whatever it is the collective state vector $x\in\mathbb{R}^n$
IMHO, the notation is quiet redundant. Since the definitions of $a_{ij}$, I think that one can write more concisely $$x'L x = \frac{1}{2}\sum_{(i,j)\in E}(x_j-x_i)^2$$ without loosing any information. On the other hand, if one desires to use the $a_{ij}$ coefficients, then can discard the edges from the sum subscript, i.e. $$x'L x = \frac{1}{2} \sum_{i=1}^n \sum_{j=1}^n a_{ij}(x_j-x_i)^2$$ obtaining another equivalent expression for the SOS equation. Am I right or I'm missing something?
The SOS property holds for any kind of graphs? Am I missing some hypotheses?
Provided the suitable hypotheses, how can be proved the SOS property?
Edit
By reading the post suggested by Mao, I think I have found a proof. However, in my derivation there is a passage, which I'd like to discuss with someone more expert than me, that is not very clear. For this reason I'm going to show my proof.
preliminary observation
The graph Laplacian $L$ is a matrix whose all row sums are null. From this fact follows that $$d_i=\sum_{j=1}^n a_{ij} \qquad \forall i=1,2,\dots,n \tag{2}$$
theorem (SOS property)
Let $G$ be a undirected graph, which means $$(i,j)\in E \rightarrow (j,i) \in E$$ then the graph Laplacian $L$ satisfies the SOS formula $$x'L x =\frac{1}{2} \sum_{(i,j)\in E} (x_i-x_j)^2 \qquad \forall x \in \mathbb{R}^n$$
proof
It is clear that the quadratic form in $L$ can be written as $$x'L x = x'D x-x'Ax \tag{3}$$ so there are two different quadratic forms to be computed: one in the degree matrix $D$ and one in the adjacency matrix $A$.
Now, for the quadratic form in $A$ we can consider for the moment the general explicit expression $$x'A x = \sum_{i=1}^n \sum_{j=1}^n a_{ij} x_i x_j \tag{4}$$
On the other hand, recalling that the degree matrix $D$ is diagonal, we can write the quadratic form in $D$ as $$x'D x=\sum_{i=1}^n d_i x_i^2$$ which, due to $(2)$, can be also written as $$\begin{aligned} x'D x &=\sum_{i=1}^n\left(\sum_{j=1}^n a_{ij}\right) x_i^2 \\ &=\sum_{i=1}^n \sum_{j=1}^n a_{ij}x_i^2 \end{aligned} \tag{5}$$
By combining $(4)$ and $(5)$ in $(3)$ we get
$$x'L x = \sum_{i=1}^n \sum_{j=1}^n a_{ij} x_i^2 - \sum_{i=1}^n \sum_{j=1}^n a_{ij} x_i x_j$$
Now the main trick of the proof: trivially we can write $$ \begin{aligned} x'L x &= \frac{1}{2}\left[2\left(\sum_{i=1}^n \sum_{j=1}^n a_{ij} x_i^2 - \sum_{i=1}^n \sum_{j=1}^n a_{ij} x_i x_j\right)\right] \\ &=\frac{1}{2}\left[2\sum_{i=1}^n \sum_{j=1}^n a_{ij} x_i^2-2\sum_{i=1}^n \sum_{j=1}^n a_{ij} x_i x_j\right] \\ &=\frac{1}{2}\left[\left(\sum_{i=1}^n \sum_{j=1}^n a_{ij} x_i^2+\sum_{i=1}^n \sum_{j=1}^n a_{ij} x_i^2\right)-2\sum_{i=1}^n \sum_{j=1}^n a_{ij} x_i x_j\right] \end{aligned}\tag{6} $$
and, at this point, there is the aforementioned passage that it is not so clear. The idea is to show that one of the two identical sums $\sum_{i=1}^n \sum_{j=1}^n a_{ij} x_i^2$ can be written as $\sum_{i=1}^n \sum_{j=1}^n a_{ij} x_j^2$. In order to do that, we can observe, if I'm not wrong, that $$\begin{aligned} \sum_{i=1}^n \sum_{j=1}^n a_{ij} x_i^2 &= \sum_{j=1}^n \sum_{i=1}^n a_{ji} x_j^2 \\ &=\sum_{i=1}^n \sum_{j=1}^n a_{ji} x_j^2 \end{aligned} $$ I'm not 100% sure that the equality between the second and third member holds, BTW taking for granted this the proof gives the final result, so it seems that such equality is true.
The graph is assumed to be undirected, which means that $A$ is symmetric (i.e. $a_{ij}=a_{ji}$). Thanks to this property of $A$, we can substitute $a_{ij}$ with $a_{ji}$ in the last RHS of the previous equalities, obtaining $$\sum_{i=1}^n \sum_{j=1}^n a_{ij} x_i^2= \sum_{i=1}^n \sum_{j=1}^n a_{ij} x_j^2 \tag{7}$$
Equation $(7)$ allows to write $(6)$ in the following nice form $$ \begin{aligned} x'L x &=\frac{1}{2}\left[\left(\sum_{i=1}^n \sum_{j=1}^n a_{ij} x_i^2+\sum_{i=1}^n \sum_{j=1}^n a_{ij} x_j^2\right)-2\sum_{i=1}^n \sum_{j=1}^n a_{ij} x_i x_j\right] \\ &=\frac{1}{2}\sum_{i=1}^n \sum_{j=1}^n a_{ij} (x_i^2+x_j^2-2x_i x_j) \\ &=\frac{1}{2}\sum_{i=1}^n \sum_{j=1}^n a_{ij} (x_i-x_j)^2 \\ &=\frac{1}{2}\sum_{(i,j)\in E} (x_i-x_j)^2 \\ \end{aligned} $$ as claimed.