Push relabel algorithms in flow networks

Question

In the CLRS book (http://en.wikipedia.org/wiki/Introduction_to_Algorithms) Chapter 26 (Maximum Flow) page 744 (third edition), there is the following equation -

$$ \sum_{u \in U}e(u) \;=\; \sum_{u \in U}\;\sum_{v \in U}f(v, u) \;+\; \sum_{u \in U}\;\sum_{v \in \bar{U}}f(v, u) \;-\; \sum_{u \in U}\;\sum_{v \in U}f(u, v) \;-\; \sum_{u \in U}\;\sum_{v \in \bar{U}}f(u, v) $$

where $f(u, v)$ is the flow between vertices $u$ and $v$, $e(u)$ is the excess flow at a particular vertex, $U$ is the set of vertices which are reachable from the source, and $\bar{U}$ is the set of remaining vertices.

In the next line, the first and third terms disappear. I don't understand why that holds. I do realize that those are flow values from vertex $u$ to vertex $v$ where both of them are in the same set $U$, but I don't understand why they cancel out to zero.

Answer 1

You just have to reorder the elements of $U\times U$, because the double sum contains each edge $(u,v) \in U\times U$ exactly once:

$$\sum_{u \in U}\sum\limits_{v \in U}f(v, u) = \sum_{(u,v) \in U\times U}f(v, u) = \sum_{(u,v) \in U\times U}f(u, v) = \sum_{u \in U}\sum\limits_{v \in U}f(u, v)$$

The fist sum sorts the edges by their first vertex, the third sum (of the question's equation) sorts the edges by their second vertex. This is the simplest imaginable form of a double counting argument.