5
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ If multiplication is commutative, why does $h$ contain both $x_1 x_3$ and $x_3 x_1$? Or, both $x_2 x_4$ and $x_4 x_2$? $\endgroup$ – Rodrigo de Azevedo Nov 27 '16 at 20:18
  • $\begingroup$ Yes, it is commutative - I wrote it this way to point out the construction of the sum in a more visible way. $\endgroup$ – Kurisuto Asutora Nov 28 '16 at 15:10
  • 1
    $\begingroup$ The problem is that you are weighting some monomials more than others. More importantly, are you sure the corresponding symmetric matrix is circulant? $\endgroup$ – Rodrigo de Azevedo Nov 28 '16 at 15:15
15
$\begingroup$

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$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Why $1/2$ on the diagonal, not 1? $\endgroup$ – Fedor Petrov Nov 23 '16 at 15:19
  • $\begingroup$ Thanks, this is brilliant - I suppose I would have needed a few years to figure that our myself. $\endgroup$ – Kurisuto Asutora Nov 23 '16 at 15:25
  • $\begingroup$ PS: I don't understand the remark on the negative eigenvalues - I am not familiar with these things. Can I deduce from the eigenvalues a lower bound for the minimal value of the quadratic form? Obviously for all variables equal to one gets $n(p+1)$ - which role do the negative eigenvalues play here, and how far below $n(p+1)$ can it go? $\endgroup$ – Kurisuto Asutora Nov 23 '16 at 15:36
  • $\begingroup$ @Fedor Petrov : because $x_1x_2$ also occurs as $x_2x_1$. $\endgroup$ – Ivan Izmestiev Nov 23 '16 at 15:51
  • 1
    $\begingroup$ @Kurisuto Asutora : From the calculus viewpoint we are computing the signature of the matrix of the second derivatives (which happens to be twice the same circular matrix). Minimum corresponds to positive definiteness corresponds to positive eigenvalues. From the linear algebra viewpoint we are finding the principal axes and determining the signature of a quadratic form. Only if all eigenvalues are positive, the level set $Q(x,x) = \mathrm{const}$ will be an ellipsoid, so its tangent hyperplane of the form $\sum_i x_i = \mathrm{const}$ will lie "on the right side" from it. $\endgroup$ – Ivan Izmestiev Nov 23 '16 at 15:59
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Hi Rodrigo, I think you misunderstood the problem asked. There are not all pairs $x_i x_j$ involed, only those whose indices are not too far apart (modulo $n$). See the way Ivan wrote it in his answer above. $\endgroup$ – Kurisuto Asutora Nov 28 '16 at 15:13
  • $\begingroup$ In the cases of $f$ and $h$, the corresponding matrix is the one above, which is not really a band matrix. One cannot use the above in the case of $g$. $\endgroup$ – Rodrigo de Azevedo Nov 28 '16 at 15:17
  • $\begingroup$ There might really be a problem unless the maximal distance $p$ (in Ivan's notation from above) is small in comparison with the dimension $n$. However, in my application this is fine: I will have $p$ fixed and $n \to \infty$. Then the matrix surely is a circulant matrix. $\endgroup$ – Kurisuto Asutora Dec 1 '16 at 12:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.