Let finite number of $x_i$'s be reals. Define matrix $M_{ij} = \sqrt{|x_i+x_j|} - \sqrt{|x_i-x_j|}$. Is this matrix positive semidefinite?

I am reading this year's IMO problem number 2, which would be trivially true if we prove that $M_{ij}$ is positive semidefinite.

Problem $\boldsymbol2$. Show that the inequality $$\sum_{i=1}^{n}\sum_{j=1}^{n}\sqrt{\left|x_i - x_j\right|} \leqslant \sum_{i=1}^{n}\sum_{j=1}^n\sqrt{\left|x_i + x_j\right|}$$ holds for all real numbers $x_1,...,x_n$.

  • $\begingroup$ After trying a few random examples in MATLAB, it appears that $M$ is in fact PSD, although I suspect proving it will be harder than solving the IMO problem. I wonder if the techniques in this answer are useful here. $\endgroup$
    – JimmyK4542
    Jul 25, 2021 at 4:27
  • 1
    $\begingroup$ See: #58 in artofproblemsolving.com/community/… $\endgroup$
    – River Li
    Jul 26, 2021 at 3:57
  • $\begingroup$ A matrix is positive semidefinite iff all principal minors are nonnegative (according to this paper: prussing.ae.illinois.edu/semidef.pdf). It would be enough to prove that $det(M) \geq 0$. $\endgroup$ Jul 27, 2021 at 13:13

1 Answer 1


Define $f(x, y) = \sqrt{|x + y|} - \sqrt{|x-y|}$. Then we want to prove that \begin{align*} \mathbb{E}[f(X, Y)] \ge 0 \end{align*} where $X, Y$ independent and uniformly distributed over the set of values $\{x_1, \cdots, x_n\}$.

[Remark 1: I know the IMO is motivated to use techniques only available at the secondary school level, but the probabilistic notation allows me to naturally represent a bunch of summation notations in a succinct form, and can be translated easily to the summation notation in the original problem.]

First, let's observe the region in the Cartesian plane where $f(x, y) \ge a$ and $f(x, y) \le -a$, respectively:

enter image description here

And therefore \begin{align*} \mathbb{P}(f(X, Y) \ge a) &= \mathbb{P}\left(X \ge \frac{a}{2}, Y \ge \frac{a}{2}\right) + \mathbb{P}\left(X \le -\frac{a}{2}, Y \le -\frac{a}{2}\right) \\ &= \mathbb{P}\left(X \ge \frac{a}{2}\right)^2 + \mathbb{P}\left(X \le -\frac{a}{2}\right)^2 \end{align*} and \begin{align*} \mathbb{P}(f(X, Y) \le a) &= \mathbb{P}\left(X \ge \frac{a}{2}, Y \le -\frac{a}{2}\right) + \mathbb{P}\left(X \le -\frac{a}{2}, Y \ge \frac{a}{2}\right) \\ &= 2\mathbb{P}\left(X \ge \frac{a}{2}\right) \left(X \le -\frac{a}{2}\right) \end{align*} Then, we need the lemma that \begin{align*} \mathbb{E}[A] = \int_0^\infty [\mathbb{P}(A \ge a) - \mathbb{P}(A \le -a)]da \end{align*}

which can be proved by noticing that $\mathbb{E}[A] = \mathbb{E}[A^+] - \mathbb{E}[A^-]$, where $A^+ = \max(A, 0)$ and $A^- = -\min(A, 0)$ and then applying the proof for the tail sum formula. Letting $A = f(X, Y)$,

\begin{align*} \mathbb{E}[f(X, Y)] &= \int_0^\infty[\mathbb{P}(f(X, Y) \ge a) - \mathbb{P}(f(X, Y) \le -a)]da \\ &= \int_0^\infty\left[\mathbb{P}\left(X \ge \frac{a}{2}\right) - \mathbb{P}\left(X \le -\frac{a}{2}\right)\right]^2da \\ &\ge 0 \end{align*}

Remark 2: Note this proof works for any $f(x, y) = g(|x+y|) - g(|x - y|)$ for non-decreasing $g: \mathbb{R}_{\ge 0} \rightarrow \mathbb{R}$ and general distributions for $X, Y$. For example, we also have the result \begin{align*} \sum_{i,j} w_i w_j \log(1 + |x_i - x_j|) \le \sum_{i,j} w_i w_j \log(1 + |x_i + x_j|) \end{align*} for weights $w_1, \cdots, w_n \ge 0$.

Remark 3: Completely forgot to answer the original problem. Note that if we choose $g(x) = \sqrt{x}$ and define $X, Y$ to be random variables distributed over $x_1, \cdots, x_n$ with weights $w_1, \cdots, w_n \ge 0$, then we effectively get, for $\mathbf{M} = [M_{ij}]_{ij}$, \begin{align*} \mathbf{w}^\intercal \mathbf{M}\mathbf{w} \ge 0 \end{align*} for $\mathbf{w} \in \mathbb{R}^n_{\ge 0}$; we need $\mathbf{w} \in \mathbb{R}^n$ in order to get genuine positive semidefiniteness. But it appears that if we replace $\mathbb{P}$ with quasiprobability distribution (e.g. negative measures are allowed), everything in the proof still seems to go through.

  • $\begingroup$ See my Remark 3. I believe everything still works with the final tweeking. $\endgroup$
    – Tom Chen
    Jul 25, 2021 at 7:24

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.