Minimizing $x_1^2+x_2^2+x_3^2+x_1x_2+x_2x_3+x_3x_1$

Question

Look at the expression $$ f(x_1,x_2,x_3) = x_1^2+x_2^2+x_3^2+x_1x_2+x_2x_3+x_3x_1. $$ The numbers $x_1,x_2,x_3$ are non-negative, and I assume that $x_1+x_2+x_3=3$. This is a sum of squares and "cyclic correlations" of consecutive variables. Then you can check that $f$ is minimized for the values $x_1=x_2=x_3=1$.

Now look at $$ g(x_1,x_2,x_3,x_4) = x_1^2+x_2^2+x_3^2+x_4^2+x_1x_2+x_2x_3+x_3x_4+x_4x_1, $$ under the assumption that $x_1+x_2+x_3+x_4=4$. Again, this is minimized by $x_1 = x_2 = x_3 = x_4=1$.

A similar thing happens if I add "second-order cyclic correlations": Let $$ h(x_1,x_2,x_3,x_4) = x_1^2+x_2^2+x_3^2+x_4^2+x_1x_2+x_2x_3+x_3x_4+x_4x_1+x_1x_3+x_2x_4+x_3x_1+x_4x_2, $$ again under the assumption that $x_1+x_2+x_3+x_4=4$. This is also minimized for the values $x_1=x_2=x_3=x_4=1$.

Is there a simple explanation for this? Is there a simple argument showing that the same will happen for, say, 12 variables and correlations of order up to 3?

Answer 1

The question is about the signature of a quadratic form $$ \sum_{i=1}^n x_i^2 + \frac12\sum_{1 \le \mathrm{dist}(i,j) \le p} x_ix_j $$ (or about the spectrum of the corresponding linear operator). The matrix is a circulant matrix, see Wikipedia, and its eigenvectors are $$ v_k = (1, \omega^k, \ldots, \omega^{k(n-1)}), $$ where $\omega = e^{\frac{2\pi i}{n}}$. The eigenvalues are easy to compute: $$ \lambda_k = \frac12 + \frac12 \sum_{i=-p}^{i = p} \omega^{ki} = \frac12 + \frac12 \frac{\omega^{\frac{(2p+1)k}{2}} - \omega^{\frac{-(2p+1)k}{2}}}{\omega^{\frac{k}2} - \omega^{-\frac{k}2}} = \frac12 + \frac12 \frac{\sin \frac{(2p+1)k\pi}{n}}{\sin \frac{k\pi}{n}}. $$ Unfortunately, there may be negative eigenvalues. For example, for $n=7$, $p=2$ we have $$ \lambda_5 = \frac12 + \frac12 \frac{\sin\frac{25\pi}7}{\sin\frac{5\pi}7} < 0. $$

Thus for seven variables and cyclic sums up to order two the minimum will not be attained at $x_1 = \cdots =x_7 = 1$.

Answer 2

Minimizing $f$ and $h$ subject to the given constraints are quadratic programs of the form

$$\begin{array}{ll} \text{minimize} & \frac 12 \mathrm x^{\top} \mathrm A \,\mathrm x\\ \text{subject to} & 1_n^{\top} \mathrm x = n\\ & \mathrm x \geq\mathrm 0_n\end{array}$$

where

$$\mathrm A := \mathrm I_n + 1_n 1_n^{\top}$$

Let us temporarily ignore the non-negativity constraints. The Lagrangian is

$$\mathcal{L} (\mathrm x, \lambda) := \frac 12 \, \mathrm x^{\top} \mathrm A \,\mathrm x - \lambda (1_n^{\top} \mathrm x - n)$$

Taking the partial derivatives and finding where they vanish, we obtain

$$\mathrm A \mathrm x = \lambda 1_n \qquad \qquad \qquad 1_n^{\top} \mathrm x = n$$

Hence, we conclude that the minimizers are

$$\bar{\mathrm x} := \left( \frac{n}{1_n^{\top} \mathrm A^{-1} 1_n} \right) \mathrm A^{-1} 1_n \qquad \qquad \qquad \bar{\lambda} := \frac{n}{1_n^{\top} \mathrm A^{-1} 1_n}$$

Using Sherman-Morrison, the inverse of $\mathrm A$ is

$$\mathrm A^{-1} = (\mathrm I_n + 1_n 1_n^{\top})^{-1} = \mathrm I_n - \left(\frac{1}{1+n}\right) 1_n 1_n^{\top}$$

Hence,

$$\mathrm A^{-1} 1_n = \frac{1}{1+n} 1_n$$

and

$$1_n^{\top} \mathrm A^{-1} 1_n = \frac{n}{1+n}$$

Thus, the minimizer is

$$\bar{\mathrm x} := \left( \frac{n}{1_n^{\top} \mathrm A^{-1} 1_n} \right) \mathrm A^{-1} 1_n = \left( \frac{n}{\frac{n}{1+n}} \right) \frac{1}{1+n} 1_n = \color{blue}{1_n}$$

which satisfies the non-negativity constraints.