# An inequality for positive definite matrices

Let $K$ and $K^\prime$ positive definite $n \times n$ matrices, such that for all vectors $f \ge 0$ with nonnegative coordinates we have

$$\sum_{i,j} K_{ij} f_i f_j \le \sum_{ij} K^\prime_{ij} f_i f_j$$

Can someone prove the following inequality?

$$\sum_{i,j} \exp K_{ij} \le \sum_{i,j} \exp K^\prime_{ij}$$

The reason why I believe it is true is that I have a proof using Slepian-Kahane-type comparison for Wick exponentials of Gaussian random vectors with covariance $K$ and $K^\prime$, which might look like a perverse way of doing something as simple-looking as this. Ideally, I'd like to see a more straightforward proof, or maybe some general suggestions on how to use that weird positivity condition on $K^\prime - K$.

Upd: The "weird positivity condition" is nothing but dual to something known by the name "complete positivity".

-
This one essentially follows because for positive definite matrices $K, K'$ such that $K \preceq K'$, it follows that $K \circ K \preceq K' \circ K'$, where $\circ$ denotes the Schur (Hadamard) product. – Suvrit Mar 23 '14 at 18:57
@Suvrit: Actually, I don't see how to show even that unless the difference $K^\prime - K$ is positive definite. – Alexander Shamov Mar 23 '14 at 19:21
Ah, your first inequality has an extra nonnegativity hypothesis, which (despite its being bold), I missed seeing... – Suvrit Mar 23 '14 at 19:33
@Suvrit: That's the whole point. :) – Alexander Shamov Mar 23 '14 at 19:34
The dual to the completely positive cone is called the "copositive cone", i.e. your assumption is that $K'-K$ be copositive. – Noah Stein Mar 24 '14 at 12:25

Here is a simple proof (thanks to the OP for a proof that the Hadamard exponential is CP).

I'll write $K$ and $H \equiv K'$ to keep the notation simpler.

As $K \succeq 0$, it follows that its Schur exponent $[e^{k_{ij}}]$ is also psd. Thus, in particular, we can write the following factorization: \begin{equation*} [e^{k_{ij}}] = \sum\nolimits_l u_l u_l^T. \end{equation*}

Theorem. The Schur-Hadamard exponential $[e^{k_{ij}}]$ is completely positive, i.e., in the above factorization we can select the vectors $u_1,\ldots,u_n$ to be elementwise nonnegative.

In addition to the OP's elegant argument (see comments below), another proof to this theorem may also be found as Theorem 2.30 (pp 131) in Completely Positive Matrices, by Berman and ‎Shaked-Monderer.

Then, consider \begin{equation*} \sum\nolimits_{ij} e^{k_{ij}}(h_{ij}-k_{ij}) = \mbox{tr}[(H-K)\sum\nolimits_l u_lu_l^T] = \sum\nolimits_l u_l^T (H-K)u_l \ge 0, \end{equation*} where the final inequality follows from our hypothesis since $u_l \ge 0$.

Since $\exp(x)$ is a convex function, we have \begin{equation*} e^h \ge e^k + e^k(h-k),\qquad\forall h, k. \end{equation*} Thus, it follows that \begin{equation*} \sum_{ij} e^{h_{ij}} \ge \sum_{ij} e^{k_{ij}} + \sum_{ij} e^{k_{ij}}(h_{ij}-k_{ij}). \end{equation*} But the above argumentation showed that the last term on the rhs is nonnegative.$\qquad\blacksquare$

-
Actually, it is true that $\exp K$ is completely positive for every positive definite $K$. And guess what, this has a probabilistic reason: $\exp K_{ij} = \mathsf{E} \exp[X_i - \frac{1}{2} K_{ii}] \exp[X_j - \frac{1}{2} K_{jj}]$, where $X$ is the Gaussian with covariance $K$. – Alexander Shamov Mar 23 '14 at 20:39
So if exp is CP, we are done! – Suvrit Mar 23 '14 at 20:42
Very nice, thanks! – Alexander Shamov Mar 23 '14 at 20:49
I find your proof of CP of exp much nicer than using a bruteforce argument based on decomposing $K=\sum_l v_lv_l^T$, etc. – Suvrit Mar 23 '14 at 20:54
Actually, my original motivation was to avoid Gaussian tricks - and instead we arrived at special properties of exponential... – Alexander Shamov Mar 23 '14 at 21:00