Postive-semidefiniteness of matrix with entries $1/(a_i+a_j)$

Question

Let $a_1, \ldots, a_n$ be a set of positive numbers. Define a matrix $M_{ij} = \frac{1}{a_i+a_j}$. I'm trying to prove that $M$ is positive-semidefinite. The hint says to use the fact that $\int_{0}^{\infty} e^{-sx}\; dx = \frac{1}{s}$ if $s > 0$. However I don't know how this hint is useful. I've tried choosing an arbitrary vector $x$ and substituting $x^{\intercal}Mx = \sum_{i}\sum_{j} \frac{x_ix_j}{a_i+a_j}$ into $s$ and using properties of exponents to simplify the equation into something that is clearly positive, but without any luck. The denominator $\frac{1}{a_i+a_j}$ is simply too difficult to work with. At this point I think I'm just missing some trick that I don't know. Any help would be appreciated.

Answer 1

Use the hint as follows:

For each $x = (x_1, \ldots, x_n)^T \in \mathbb{R}^n$, \begin{align} & x^TMx \\ = & \sum_i\sum_j x_ix_j\frac{1}{a_i + a_j} \\ = & \sum_i\sum_j \int_0^\infty x_i x_j e^{-(a_i + a_j)t}dt \\ = & \int_0^\infty \left[\sum_i\sum_j x_i x_j e^{-(a_i + a_j)t} \right] dt \\ = & \int_0^\infty \left[\sum_i\sum_j x_ie^{-a_i t}x_je^{-a_jt} \right] dt \\ = & \int_0^\infty \left(\sum_k x_ke^{-a_kt}\right)^2 dt \\ \geq & 0. \end{align} Thus $M$ is positive-semidefinite.