Prove that matrix is positive definite 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.
 A: 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})
$
A: 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.
