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.



Prove that matrix is positive definite
**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.


