17
$\begingroup$

My question is to find the minimum of the following expression: $$A(x,y) = \sum_{1\leq i<j\leq n} |x_i-x_j|\ |y_i-y_j|,$$ over the set of pairs of real vectors $x=(x_1,\dots,x_n),y=(y_1,\dots,y_n)$ subject to the following conditions: $$\sum_{i=1}^n x_i^2 =\sum_{i=1}^n y_i^2 = 1, \sum_{i=1}^n x_i=\sum_{i=1}^n y_i=0.$$

It seems that $1$ is less or equal to the minimum, but don't have a proof.

$\endgroup$
5
  • $\begingroup$ Try lagrange multipliers? Doesn't look too hard $\endgroup$ Oct 7, 2018 at 13:59
  • 2
    $\begingroup$ @AlexArvanitakis the objective is not differentiable, so you cannot immediately use Lagrange multipliers. You will need to mix in some combinatorial considerations about the order of the variables. $\endgroup$ Oct 7, 2018 at 14:46
  • $\begingroup$ ah misread the bars $\endgroup$ Oct 7, 2018 at 22:04
  • 2
    $\begingroup$ What is the motivation? $\endgroup$ Oct 9, 2018 at 18:03
  • 3
    $\begingroup$ @AlexanderChervov It's a consequence of a conjecture on the eigenvalues of the Laplacian operators on graphs. I know that this is true for all $n$ less than 10. $\endgroup$
    – Mostafa
    Oct 9, 2018 at 18:30

4 Answers 4

17
+50
$\begingroup$

The minimum must occur at vectors $x,y$ where $x_i$ and $y_i$ take only two values each. This should make it easy to check Neil Strickland's experimental result (where $x$ and $y$ are indeed of this form). [EDIT: see the answer by Adam P. Goucher for this check.]

It is convenient to extend $A$ homogeneously to all nonzero $x,y$ in the zero-sum hyperplane: $$ A(x,y) = \frac1{\| x \| \, \|y\|} \sum_{1\leq i<j\leq n} |x_i-x_j|\ |y_i-y_j| $$ where $\|x\| = (x_1^2 + \cdots + x_n^2)^{1/2}$ and likewise $\|y\|$. So we seek the largest $a$ such that $$ (1)\qquad\qquad\qquad \sum_{1\leq i<j\leq n} |x_i-x_j|\ |y_i-y_j| \geq a \, \|x\| \, \|y\| \qquad\qquad\qquad\phantom{(1)} $$ for all $x,y$ such that $\sum_{i=1}^n x_i = \sum_{i=1}^n y_i = 0$.

Fix one of the $n!^2$ possible orders of the coordinates of $x$ and $y$. Such a choice limits each of $x$ and $y$ to a cone. For the order $x_1 \geq x_2 \geq \ldots \geq x_n$, the cone's extreme rays are generated by $(1,\ldots,1,1-n)$, $(2,\ldots,2,2-n,2-n)$, etc., all with $x_i$ or $y_j$ taking only two values each. In general we have the image of these generators under some coordinate permutation, so still with $x_i$ or $y_j$ taking only two values each.

Given that choice of order, $\sum_{1\leq i<j\leq n} |x_i-x_j| |y_i-y_j|$ is a bilinear form in $x,y$ because the signs of $x_i-x_j$ and $y_i-y_j$ are constant. The claim then follows by a convexity argument (so ultimately by the triangle inequality). Indeed if we fix $x$, and (1) holds for $(x,y)$ and $(x,y')$ for some $y,y'$ in the same cone, then it also holds for $(x, ty+(1-t)y')$ for all $t \in [0,1]$. So it is enough to check (1) for $y$ on an extreme ray of the cone. Likewise we can fix $y$ and reduce to the case where $x$ is on an extreme ray. QED

$\endgroup$
5
  • $\begingroup$ I like the homogenization idea, as well as the idea of fixing an order of the coordinates. However, it is unclear to me how and why "[s]uch a choice limits each of $x$ and $y$ to a cone whose extreme rays are generated by $(1,\ldots,1,1-n)$, $(2,\ldots,2,2-n,2-n)$, etc."; for any choice of "one of the $n!^2$ possible orders of the coordinates of $x$ and $y$"? In particular, the vectors $(1,\ldots,1,1-n)$, $(2,\ldots,2,2-n,2-n)$, etc. are compatible only with some of the $n!^2$ possible orders. Can you provide details on this? $\endgroup$ Oct 10, 2018 at 15:53
  • 2
    $\begingroup$ Sorry, I meant the image of those vectors $(1,\ldots,1,1-n)$ etc. under the appropriate permutation. If $x_1 \geq x_2 \geq \ldots \geq x_n$ then the map taking $x$ to $(x_1-x_2,x_2-x_3,\ldots,x_{n-1}-x_n)$ identifies the this cone with the closed positive orthant, and those extreme rays with the coordinate axes. $\endgroup$ Oct 10, 2018 at 16:10
  • $\begingroup$ Very nice, thank you for this detail! $\endgroup$ Oct 10, 2018 at 16:16
  • $\begingroup$ Thanks / you're welcome. I've now incorporated some of the explanation into my answer. $\endgroup$ Oct 10, 2018 at 17:34
  • $\begingroup$ Thanks Noam, I learnt so much from your answer! $\endgroup$
    – Mostafa
    Oct 11, 2018 at 20:33
14
$\begingroup$

Experimental investigation suggests that the minimum is $n/(n-1)$, attained when \begin{align*} x &= (1-n,1,1,\dotsc,1)/\sqrt{n^2-n} \\ y &= (1,1-n,1,\dotsc,1)/\sqrt{n^2-n} \\ \end{align*}

$\endgroup$
1
  • 1
    $\begingroup$ It seems that this number is actually the minimum, but I'm interested more in a verification of a good lower bound. $\endgroup$
    – Mostafa
    Oct 9, 2018 at 16:52
8
$\begingroup$

Using Noam Elkies' answer, we can wlog assume that the entries of $x$ are:

$$ k \textrm{ copies of } \dfrac{k - n}{\sqrt{kn(n-k)}} $$

$$ n - k \textrm{ copies of } \dfrac{k}{\sqrt{kn(n-k)}} $$

and similarly that the entries of $y$ are:

$$ l \textrm{ copies of } \dfrac{l - n}{\sqrt{ln(n-l)}} $$

$$ n - l \textrm{ copies of } \dfrac{l}{\sqrt{ln(n-l)}} $$

where wlog $1 \leq k, l \leq \frac{n}{2}$ (otherwise take complements).

We shall denote the sets of negative coordinates of $x$ and $y$, respectively, by $K$ and $L$ (so $|K| = k$ and $|L| = l$). Let their complements be $K'$ and $L'$.

Now, a pair of indices $i, j$ contributes a nonzero term to the objective if and only if exactly one of $i, j$ is in $K$, and exactly one of $i, j$ is in $L$.

The total number of such pairs (which we can view as edges in the intersection of two complete bipartite graphs) is given by:

$$ | K \cap L | | K' \cap L' | + | K \cap L' | | K' \cap L | $$

If we let $m := | K \cap L |$, this is just:

$$ m (n + m - k - l) + (k - m)(l - m) $$

This is a quadratic function of $m$ with minimiser $\frac{1}{4}(2k + 2l - n)$.


Case 1: If $2k + 2l \leq n$, this is minimised on the boundary when $m = 0$. We can take $K$ and $L$ to be disjoint and everything is much simpler. The number of nonzero terms is $kl$, and the size of each term is:

$$ \dfrac{n^2}{\sqrt{lkn^2(n-l)(n-k)}} $$

so the total value of the objective function is:

$$ n \sqrt{\dfrac{kl}{(n - l)(n - k)}} $$

It is now straightforward to see that we want $l$ and $k$ to be as small as possible, namely $1$, giving Strickland's solution as the unique optimum.


Case 2: If $n < 2k + 2l$, then the optimum $m = \lfloor \frac{1}{4}(2k + 2l - n) \rfloor$ is still small, in that we have $m \leq \frac{k}{2}$ and $m \leq \frac{l}{2}$. This implies that the number of nonzero pairs is still at least $\frac{1}{4} k l$, so if $kl \geq 4$ then we do worse than Strickland's solution in Case 1.

In the remaining subcase where $kl < 4$ and $n < 2k + 2l$, we necessarily have $n \leq 7$. But all of these small cases have been checked by the OP, so the result holds in general.

$\endgroup$
1
  • 1
    $\begingroup$ Thanks for this nice and detailed computations! $\endgroup$
    – Mostafa
    Oct 11, 2018 at 20:29
2
$\begingroup$

The lower bound $1$ easily could be obtain. Indeed, for every two zero-sum vectors $x,y \in \mathbb{R}^n$, we have

$$ \begin{eqnarray} \left(\sum_{i\leq j} |x_i-x_j||y_i - y_j|\right)^2 & \geq & \frac 12\sum_{i,j}|x_i -x_j|^2|y_i -y_j|^2 \\ & = & \frac 12\sum_{i,j} (x_i^2 -2x_i x_j+x_j^2)(y_i^2-2y_i y_j+y_j^2)\\ & = & n \sum_i (x_i y_i)^2 +2 \Big(\sum_i x_i y_i\Big)^2 + \sum_i x_i^2\sum _i y_i^2 \\ & \geq & \|x\|^2 \|y\|^2 \end{eqnarray} $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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