11
$\begingroup$

I faced a hard question in kernel methods theory, which I can't answer for about one week. Initially it was formulated in terms of positive valued functions, but it could be reformulated easier:

Let $\{x_1, \dotsc, x_n\}$ and $\{y_1, \dotsc, y_n\}$ be two sets of real positive numbers. Prove that matrix $A$ is positive definite where $A_{i, j} = \min(x_i\cdot y_j, x_j\cdot y_i)$. Equivalently, I want to prove that for arbitrary $a_1, \dotsc, a_n$ the following inequality holds: $$ \sum_{i,j=1}^n a_i a_j \min(x_i\cdot y_j, x_j\cdot y_i)\ge 0. $$

I've run out of ideas on how it could be proved, so any advice is welcome.

$\endgroup$
19
$\begingroup$

Update: I originally claimed to prove that $A$ is strictly positive definite, but there was a bug in the strictness part. I have revised the proof to show that $A$ is positive semidefinite. For an example to see that $A$ need not be strictly positive definite let $x_i=y_i$ for all $i$. Then $A = xx^T$ is rank one.


For any sequence $z = (z_1,\ldots, z_n)$ of nonnegative numbers, the matrix $B(z)$ with entries $[B(z)]_{ij} = \min(z_i, z_j)$ is positive semidefinite. Given this, we set $z_i = y_i/x_i$ and obtain that $A=\operatorname{diag}(x)B(z)\operatorname{diag}(x)$ is positive semidefinite.

To see that $B(z)$ is positive semidefinite note that reordering $z$ just permutes corresponding rows and columns, so assume WLOG that $z$ is sorted in nondecreasing order. Let $w_1 = z_1$ and $w_i = z_i - z_{i-1}$ for $i>1$. Let $J$ be the matrix with ones on the upper triangle (including the diagonal) and zeros below. Then $w\geq 0$ so $B(z) = J^T\operatorname{diag}(w)J$ is positive semidefinite.

$\endgroup$
  • $\begingroup$ This proof establishes definiteness if all $w_i$ are nonzero, which is the same as saying the $z_i$ are distinct, which is the same as saying that the ratios $x_i/y_i$ and $x_j/y_j$ are distinct. $\endgroup$ – David E Speyer Jan 16 at 21:03
5
$\begingroup$

This is a very similar proof but based on $\mathbb{E}B_{z_{i}}B_{z_{j}}=\min(z_{i},z_{j})$ where $B_{z}$ is the standard brownian motion starting at zero:

$ 0\leq \mathbb{E}\left(\sum_{j} a_{j} x_{j} B_{\frac{y_{j}}{x_{j}}} \right)^{2}=\sum_{i,j}a_{i}a_{j}\min(x_{i}y_{j},x_{j}y_{i}) $

$\endgroup$

Your Answer

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