# Is this matrix positive semidefinite? $M_{ij} = \sqrt{|x_i+x_j|} - \sqrt{|x_i-x_j|}$ where $x_i$'s are reals

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

• 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. Jul 25 at 4:27
• See: #58 in artofproblemsolving.com/community/… Jul 26 at 3:57
• 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$. Jul 27 at 13:13

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:

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.

• See my Remark 3. I believe everything still works with the final tweeking. Jul 25 at 7:24