Proof of Lemma 1

The proof of this lemma is quite straightforward, but we give it for completeness. $Z$ can be rewritten as

$$Z = \sum_{j \neq k} {Z_{j, k}} \:\:,$$ (26)

with

$$\forall j \neq k, Z_{j, k} = \frac{W_{j}^+}{c-1} e^{ - \frac{1}{2} \Delta(j, k) } + \frac{W_{k}^+}{c-1} e^{\frac{1}{2} \Delta(j, k)} \:\:,$$ (27)

where $\Delta(j, k) = \vec{v}[j] - \vec{v}[k]$. Suppose for contradiction that for some $j<k$, $\Delta=\Delta(j, k)>0$. We simply permute the two values $\vec{v}[j]$ and $\vec{v}[k]$, and we show that the new value of $Z$ after, $Z_{\mbox{\bf a}}$, is not greater than $Z$ before permuting, $Z_{\mbox{\bf b}}$. The difference between $Z_{\mbox{\bf a}}$ and $Z_{\mbox{\bf b}}$ can be easily decomposed using the notation $Z_{(i, j)\mbox{\bf b}}$ ( $i,j \in \{0, 1, ..., c-1\}, i\neq j$) as the value of $Z_{i,j}$ (eq. (27)) in $Z_{\mbox{\bf b}}$, and $Z_{(i, j)\mbox{\bf a}}$ ( $i,j \in \{0, 1, ..., c-1\}, i\neq j$) as the value of $Z_{i,j}$ (eq. (27)) in $Z_{\mbox{\bf a}}$. We also define:

$$\forall i,j,k \in \{0, 1, ..., c-1\}, i\neq j\neq k, Z_{(i,j,k)\m... ... Z_{(k,i),\mbox{\bf a}} + Z_{(j,k),\mbox{\bf a}} + Z_{(k,j),\mbox{\bf a}} \:\:.$$ (28)

We define in the same way $Z_{(i,j,k)\mbox{\bf b}}$. We obtain

$$Z_{\mbox{\bf a}} - Z_{\mbox{\bf b}} = \left( Z_{(j,k)\mbox{\bf a}} - Z_{(j,k)\mbox{\bf b}} \right) + \s... ...\}}^{c} {\left( Z_{(j,k,i)\mbox{\bf a}} - Z_{(j,k,i)\mbox{\bf b}}\right)} \:\:.$$ (29)

Proving that $Z_{\mbox{\bf a}} - Z_{\mbox{\bf b}}\leq 0$ can be obtained as follows. First,

$$\begin{eqnarray*} Z_{(j,k)\mbox{\bf a}} - Z_{(j,k)\mbox{\bf b}} & = & \frac{\le... ...1}{2} \Delta}}{c-1} \left ( 1 - e^{ \Delta}\right) \leq 0 \:\:. \end{eqnarray*}$$

We also have $\forall i\in\{1, 2, ..., c\} \backslash \{j, k\}$:

$$\begin{eqnarray*} Z_{(j,k,i)\mbox{\bf a}} - Z_{(j,k,i)\mbox{\bf b}} & = & \frac... ...} \Delta_{i, j}}}{c-1} \left( 1- e^{\Delta}\right) \leq 0 \:\:. \end{eqnarray*}$$

Here we have use the fact that $\Delta_{i, k} = \Delta_{i, j} + \Delta$. This shows that $Z_{\mbox{\bf a}} - Z_{\mbox{\bf b}}\leq 0$, and ends the proof of Lemma 1.