Reading an image processing (image segmentation paper) entitled Normalized Cuts and Image Segmentation, the goal is to create a partition of a weighted graph $V$ into two sets $A,B$ such that $Ncut(A,B)$ is minimal.
Let $x$ be an $N=|V|$ dimensional indicator vector $x_i = 1$ if $i \in A$, and $-1$ otherwise. Let $d(i) = \sum_{j} w(i,j)$ be the total connection from node $i$ to all other nodes.
Define $Ncut(A,B) = \frac {cut(A,B)}{assoc(A,V)} + \frac {cut(B,A)}{assoc(B,V)}$ where $cut(A,B)$ is the weight of all edges connecting sets $A,B$, and $assoc(A,V)$ is the weight of all edges from $A$ to all nodes in the graph.
Let $D$ be an $N \times N$ diagonal matrix $[D_{ii}] = d(i)$, and let $W$ be an $N \times N$ symmetrical matrix $W(i,j) = w_{ij}$ giving the weights of our graph. Further let $k = \frac{\sum_{x_i > 0} d_i} {\sum_{i} d_i}$ (the sum of weights coming out from elements in $A$ normalized by the overall sum of weights leaving all nodes).
Writing $Ncut(A,B) = \frac {cut(A,B)}{assoc(A,V)} + \frac {cut(B,A)}{assoc(B,V)}$ $ = \frac{\sum_{x_i > 0, x_j < 0}-w_{ij}x_ix_j}{\sum_{x_i > 0} d_i} + \frac{\sum_{x_i < 0, x_j > 0}-w_{ij}x_ix_j}{\sum_{x_i < 0} d_i}$.
The authors state without proof that $4 \times Ncut(x) = \frac {(1+x)^T (D-W)(1+x)}{k1^TD1} + \frac {(1-x)^T(D-W)(1-x)}{(1-k)1^TD1}$, noting that $\frac{1+x}{2}$ and $\frac{1-x}{2}$ are indicator vectors for $x_i>0$ and $x_i<0$ respectively.
I'm a bit confused how this formula was arrived at. I tried coming up with my own example to see why this was true for the first part of the addition on the RHS. Imagining for a graph with two nodes, $x=(x_1,x_2)$, then $\frac{(1+x)^T(D-W)(1+x)}{k1^TD1} = \frac{((1,1)+(x_1,x_2))^T (\begin{bmatrix} d(1)&0 \\0 & d(2) \end{bmatrix} - \begin{bmatrix} w_{11} & w_{12} \\ w_{21} & w_{22} \end{bmatrix}) ((1,1)+(x_1,x_2))} { \frac {\sum_{x_i>0}d_i} {\sum_{i}d_i} (1, 1)^T \begin{bmatrix} d(1)&0 \\0 & d(2) \end{bmatrix} (1, 1)}$,
I can see the denominator equals $\sum_{x_i>0}d_i$, but I'm not seeing the relationship with the numerator between the two expressions.
For instance, (assuming that $w(i,j)$ is the same as $w_{ij}$ and $D-W=\|(D-W)_{ij}\|$), the numerator of $\frac {(1+x)^T (D-W)(1+x)}{k1^TD1}$ equals $$\sum_{i,j}(1+x_i)(D-W)_{ij}(1+x_j)=$$ $$\sum_{i}(1+x_i)^2d(i)-\sum_{i,j}(1+x_i) (1+x_j)w_{i,j}=$$ $$\sum_{i,j}(1+x_i)^2w_{i,j}-\sum_{i,j}(1+x_i) (1+x_j)w_{i,j}=$$ $$\sum_{i,j}(1+x_i)(x_i-x_j)w_{i,j}=$$ $$\sum_{x_i>0,\,x_j<0}4w_{i,j}=$$ $$\sum_{x_i>0,\,x_j<0}-4x_ix_jw_{i,j}.$$