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.
Best Answer
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.