How do I arrive at the form given in this paper, for the QUBO version of the number partitioning problem?

Question

In this article A new modeling and solution approach for the number partitioning problem¹, it transforms the number partition problem into a QUBO form like equation (2.1) on page 2. $$\text{diff}=\sum_{j=1}^ms_j-2\sum_{j=1}^ms_jx_j=c-2\sum_{j=1}^ms_jx_j\tag{2.1}$$ My question is how to turn (2.1) into (2.2) and (2.3)?

\begin{align} \text{diff}^2&=\left\{c-2\sum_{j=1}^ms_jx_j\right\}^2 \\ &=c^2+4xQx\tag{2.2} \end{align}

where $$q_{ii}=s_i(s_i-c),\quad q_{ij}=s_is_j\tag{2.3}$$

---

_Reference

_{[1] Alidaee, B., Glover, F., Kochenberger, G. A., Rego, C. (2005). A new modeling and solution approach for the number partitioning problem. Journal of Applied Mathematics and Decision Sciences. 2005(2):113–21.}

Answer 1

\begin{align}\text{diff}^2&=c^2+4\left(\left(\sum s_jx_j\right)^2-c\sum s_jx_j\right)\\&=c^2+4\left(\sum s_j^2x_j^2+\sum_{\rm cyc}s_ks_\ell x_kx_\ell-c\sum s_jx_j\right)\tag1\\&=c^2+4\left(\sum x_j\boldsymbol{s_j(s_j-c)}x_j+\sum_{\rm cyc}x_k\boldsymbol{s_ks_\ell}x_\ell\right)\tag2\\ &=c^2+4x^\top Qx\tag3\end{align}

---

Explanation:

$(1)$: This is a standard expansion involving a pairwise cyclic sum.

$(2)$: We use the fact that $x_j=x_j^2$ as the variable is binary, so that $\sum s_jx_j=\sum s_jx_j^2$. In the paper, it is stated directly above (2.1): "Let $x_j=1$ if $s_j$ is assigned to subset $1$, $0$ otherwise."

$(3)$: The form in $(2)$ indicates that diagonal elements of the matrix are $s_j(s_j-c)$ and off-diagonal elements $s_ks_\ell$ correspond to their row and column coordinates.