Why $x^TLx = \sum_{(u,v)\in E} w_{uv}(x(u)-x(v))^2$ for Laplacian L?

Question

Question from paper "Graph Sparsification by Effective Resistances" by Daniel A. Spielman and Nikhil Srivastava again. I was trying to find some notes/lectures on this topic and for instance I found this: The link for some notes regarding Laplacian

Could someone please explain me:

1. In the equation $x^{T}Lx = \sum_{(u,v)\in E} w_{uv}(x(u)-x(v))^2$, what $x_u,x_v$ stands for? and how did we get this equality $x^TLx = \sum_{(u,v)\in E} w_{uv}(x_u-x_v)^2$? on page N5 in paper

Answer 1

First definitions $$x = \begin{bmatrix}x_{u}&x_{v}\end{bmatrix}^T ,L = \begin{bmatrix}w_{uv}&-w_{uv}\\-w_{uv}&w_{uv}\end{bmatrix}$$ So we expand:

$$\begin{bmatrix}x_{u}&x_{v}\end{bmatrix}\begin{bmatrix}w_{uv}&-w_{uv}\\-w_{uv}&w_{uv}\end{bmatrix} \begin{bmatrix}x_{u}\\x_{v}\end{bmatrix} = \begin{bmatrix}x_{u}&x_{v}\end{bmatrix}\begin{bmatrix}w_{uv}(x_{u}-x_v)\\w_{uv}(-x_{u}+x_v)\end{bmatrix} =$$$$ w_{uv}(x_u^2 -x_ux_v -x_vx_u +x_v^2)=w_{uv}(x^2_u-2x_ux_v + x^2_v) = w_{uv}(x_u- x_v)^2$$

The last one uses the square-law $$(a-b)^2 = a^2-2ab+b^2$$ if we set $a=x_u, b=x_v$

Answer 2

We have $L=B^TWB$ where $B \in \{0,-1,1\}^{m\times n}$ and $W(e,e)$ is the diagonal matrix with $w_e$.

$$B(e,v)=\begin{cases}1 & \text{if } v \text{ is } e's \text{ head} \\ -1 & \text{if } v \text{ is } e's \text{ tail} \\0 & \text{otherwise}\end{cases}$$

Hence

\begin{align} x^TLx&=\|W^\frac12 Bx\|^2\\ \end{align}

Let's examine what is $Bx$, $Bx$ would gives us a vector of length $m$. The row of $B$ consists of exactly one $1$ and exactly one $-1$. Suppose $e=(u,v)$, the $e$-th entry of $Bx$ would be $x(v)-x(u)$ and it will be weighted by $\sqrt{w_{uv}}$.

Hence \begin{align} x^TLx&=\|W^\frac12 Bx\|^2\\&=\sum_{(u,v) \in E} (\sqrt{w_{u,j}})^2(x(v)-x(u))^2\\ &=\sum_{(u,v) \in E} w_{u,j}(x(v)-x(u))^2\\\end{align}

$x$ can be arbitrary vector that is being assigned to a node, I personally call it potential. I'm from the optimization community.