13
$\begingroup$

Let $\{v_i\}_{i=1}^N$ be a set of $n$-dimensional real vectors and let $X=X^\top\in\mathbb{R}^{n\times n}$ be a positive definite trace-one matrix. I would like to prove (or disprove) the following inequality: $$ \sum_{i=1}^N \log \left(\frac{1}{N}\sum_{j=1}^N \frac{v_i^\top X^{1/2}v_j v_j^\top X^{1/2}v_i}{v_j^\top X v_j}\right) - \sum_{i=1}^N \log v_i^\top X v_i \geq 0,\qquad (*) $$ where $X^{1/2}=(X^{1/2})^\top$ denotes the principal square root of $X$. Note that the previous inequality holds for $N=1$. Indeed, $$ \log \frac{\left(v_1^\top X^{1/2}v_1\right)^2}{v_1^\top X v_1} - \log v_1^\top X v_1 = 2 \log\frac{v_1^\top X^{1/2}v_1}{v_1^\top X v_1}\geq 0, $$ where the last step follows from the fact that, since $X$ is a trace-one matrix, $v^\top(X^{1/2}-X)v\geq 0$ for all $v\in\mathbb{R}^n$. I carried out a large series of numerical simulations for $N>1$ in order to find a counterexample to $(*)$, but I couldn't find it. Hence my guess is that $(*)$ is true.

Thanks for your help!

Some comments. Notice that $(*)$ can be written as $$ \sum_{i=1}^N \log \left(\frac{1}{N}\sum_{j=1}^N \frac{v_i^\top X^{1/2}v_j v_j^\top X^{1/2}v_i}{v_j^\top X v_jv_i^\top X v_i }\right) \geq 0. $$ A lower bound to the LHS of previous inequality can be found by using the inequality $\log(x)\geq 1-1/x$, which yields, $$ \sum_{i=1}^N \log \left(\frac{1}{N}\sum_{j=1}^N \frac{v_i^\top X^{1/2}v_j v_j^\top X^{1/2}v_i}{v_j^\top X v_jv_i^\top X v_i }\right) \geq N -N\sum_{i=1}^N \left(\sum_{j=1}^N \frac{v_i^\top X^{1/2}v_j v_j^\top X^{1/2}v_i}{v_j^\top X v_jv_i^\top X v_i }\right)^{-1}. $$ Hence if we prove that $$ \sum_{i=1}^N\left(\sum_{j=1}^N \frac{v_i^\top X^{1/2}v_j v_j^\top X^{1/2}v_i}{v_j^\top X v_jv_i^\top X v_i }\right)^{-1}\leq 1 $$ we are done. Numerical simulations suggest that the latter inequality holds.


EDIT. A follow-up of this question has been posted here.

$\endgroup$
  • 1
    $\begingroup$ Without loss of generality, $X^{1/2}$ is a diagonal matrix with positive $c_1,\dots,c_n$ on the diagonal such that $\sum_{k=1}^n c_k^2=1$. Letting then $v_i=[v_{i1},\dots,v_{in}]^T$ and $y_{ik}:=v_{ik}\sqrt{c_k}(\sum_{q=1}^n c_q^2v_{iq}^2)^{-1/2}$, one rewrites $(*)$ as $\prod_{i=1}^N\sum_{j=1}^N(\sum_{k=1}^n y_{ik}y_{jk})^2\ge N^N$ given that $\sum_{k=1}^n c_k^2=\sum_{k=1}^n c_k y_{ik}^2=1$ for all $i=1,\dots,N$. Then one could perhaps use Lagrange multipliers. $\endgroup$ – Iosif Pinelis Mar 18 '16 at 14:31
  • 2
    $\begingroup$ For $N=2$ this reduces (If I am not mistaken) to equivalent inequality $(\sum a_i^2)(\sum b_i^2)+(\sum a_ib_i)^2\geqslant \sqrt{(\sum a_i^4)(\sum b_i^4)}+\sum a_i^2b_i^2$ for arbitrary reals $a_i,b_i$. $\endgroup$ – Fedor Petrov Mar 19 '16 at 7:49
  • $\begingroup$ It looks probable (and holds for $n=2$). $\endgroup$ – Fedor Petrov Mar 20 '16 at 22:07
9
$\begingroup$

The proof of the general case, in a strong form suggested in the end of OP.

Denote $X^{1/4} v_i=u_i$, $X^{1/2}=S$, then we have ${\rm tr}\,S^2=1$ and need to prove that $$ {\rm tr}\,S^2\geqslant \sum_i \frac{(Su_i,u_i) (Su_j,u_j)}{\sum_j (u_i,u_j)^2}, $$ then the very original inequality follows by applying AM-GM to $N$ summands in RHS.

By homogeneity in $u$'s we may suppose that $(Su_i,u_i)=1$ for all $i$. On the set of symmetric operators on $\mathbb{R}^n$ we have an inner product $(Y,Z)={\rm tr}\, YZ$, so ${\rm tr}\,S^2=\|S\|^2$. Our restriction on $S$ may be rewritten as $(S,u_i\otimes u_i)=1$, where we naturally identify $u\otimes u$ with the (rank at most 1) operator $x\rightarrow (u,x)u$. For operators $T_i=u_i\otimes u_i$, $i=1,\dots,N$ we have $(u_i,u_j)^2=(T_i,T_j)$. That is, we get the following problem: given that $(T_i,T_j)\geqslant 0$ for all $i,j$ and $(S,T_i)=1$ prove that $$ \|S\|^2 \geqslant \sum_{i=1}^N (T_i,T_1+\dots+T_N)^{-1} $$ For $c_i=(T_i,\sum T_j)$ we choose numbers $\mu_1,\dots,\mu_N$ such that $\sum 1/c_i=(\sum \mu_i)^2/\sum \mu_i^2c_i$, for example take $\mu_i=1/c_i$. Then $$ \|S\|^2\sum \mu_i^2c_i=\|S\|^2 \sum_i \sum_j \mu_i^2 (T_i,T_j)\geqslant \|S\|^2\|\sum \mu_iT_i\|^2\geqslant (S,\sum \mu_iT_i)^2=(\sum \mu_i)^2 $$ as desired (we have used that $\mu_i^2 (T_i,T_j)+\mu_j^2 (T_j,T_i)\geqslant 2\mu_i\mu_j (T_i,T_j)$ for all pairs $i\ne j$.)

$\endgroup$
  • $\begingroup$ Can you also prove the last inequality of the question ? $\endgroup$ – jjcale Mar 23 '16 at 18:41
  • $\begingroup$ Yes, only the last step changes: for numbers $c_i=(T_i,\sum T_j)$ we may find positive numbers $\mu_i$ such that $\sum \mu_i=1$ and $\sum 1/c_i=1/\sum \mu_i^2 c_i$. $\endgroup$ – Fedor Petrov Mar 23 '16 at 19:12
  • $\begingroup$ Very nice proof! (minor point: seems like the very first inequality has a minor typo in the location of $(Su_i,u_i)$, but it is inconsequential...) $\endgroup$ – Suvrit Mar 24 '16 at 3:07
6
$\begingroup$

Here is the proof for $N=2$. It contains also some, well, you may call it 'ideas', which theoretically may help in further cases. Here is a straightforward proof that for two-dimensional vectors $x=(x_1,x_2),y=(y_1,y_2)$ we have $$(x_1^2+x_2^2)(y_1^2+y_2^2)+(x_1y_1+x_2y_2)^2\geqslant \sqrt{(x_1^4+x_2^4)(y_1^4+y_2^4)}+x_1^2y_1^2+x_2^2y_2^2.$$ We use notations $\|x\|^2=\sum x_i^2$ for $x=(x_1,\dots,x_d)\in \mathbb R^d$, $(x,y)=\sum_{i=1}^d x_iy_i$ denotes the standard inner product. Next, I need an easy

Lemma. For vectors $p,q,a$ in $\mathbb{R}^d$ we have $$2\frac{(p,a)\cdot (q,a)}{\|a\|^2}\leqslant \|p\|\cdot \|q\|+(p,q)$$

Proof. At first, replacing $a$ to its projection onto 2-plane containing $x$, $y$ increases LHS and does not change RHS. So we may suppose that $p,q,a$ lie in a 2-plane. Then if we denote angles between $p,a$ by $\alpha$ and $q,a$ by $\beta$ we have to prove $2\cos \alpha \cos \beta\leqslant 1+\cos(\alpha\pm \beta)$, this follows from identity $2\cos \alpha \cos \beta=\cos(\alpha+\beta)+\cos(\alpha-\beta)$.

More involved observation is the following. Assume that $L$ is a subspace in $\mathbb{R}^d$ $T$ is a self-adjoint operator on $\mathbb{R}^d$. Then there exists a non-negative definite self-adjoint operator $S:L\rightarrow L$ such that $\|Su\|=\|Tu\|$ for any $u$ in $L$.

Proof. Let $Q$ be any linear isometry from $T(L)$ to $L$ (if $T(L)$ has dimension less than that of $L$, $Q$ is defined on some extension of $T(L)$). Then $QT:L\rightarrow L$ and $\|QTu\|=\|Tu\|$ for $u\in L$. But $QT$ is not self-adjoint, well, take $S=\sqrt{(QT)^*QT}$.

Now come to your question for $N=2$. Denote $x=X^{1/4} v_1$, $y=X^{1/4}v_2$, $T=X^{1/4}$, ${\rm tr}\, T^4=1$. Your inequality may be rewritten as $$ \left(\frac{\|x\|^4}{\|Tx\|^4}+\frac{(x,y)^2}{\|Tx\|^2 \|Ty\|^2}\right) \left(\frac{\|y\|^4}{\|Ty\|^4}+\frac{(x,y)^2}{\|Tx\|^2 \|Ty\|^2}\right)\geqslant \frac 4{({\rm tr}\, T^4)^2}, $$ where last denominator is added for making it homogeneous in $T$. We check it in two steps: at first, prove it for $S$ instead $T$, next, prove that ${\rm tr}\, S^4\leqslant {\rm tr}\, T^4$. The second step is a standard application of variational principle. If $\alpha\geqslant \beta\geqslant 0$ are eigenvalues of $S$, $\lambda_1\geqslant \dots \geqslant \lambda_n>0$ are eigenvalues of $T$, we see that there exists non-zero vector $u\in L$ such that $\lambda_1 \|u\|\geqslant\|Tu\|=\|Su\|=\alpha\cdot \|u\|$. It follows that $\alpha\leqslant \lambda_1$. Next, we choose a non-zero vector $u$ which lies both in $L$ and in a subspace $W$ of codimension 1 generated by all eigenvectors of $T$ corresponded to $\lambda_2,\lambda_3,\dots,\lambda_n$. Then $\lambda_2 \|u\|\geqslant \|Tu\|=\|Su\|\geqslant \beta\cdot \|u\|$, thus $\lambda_2\geqslant \beta$. The claim ${\rm tr}\, S^4\leqslant {\rm tr}\, T^4$ follows.

Now the first step. By Cauchy-Bunyakovsky-Schwarz Inequality we have $$ \left(\frac{\|x\|^4}{\|Sx\|^4}+\frac{(x,y)^2}{\|Sx\|^2 \|Sy\|^2}\right) \left(\frac{\|y\|^4}{\|Sy\|^4}+\frac{(x,y)^2}{\|Sx\|^2 \|Sy\|^2}\right)\geqslant \left(\frac{\|x\|^2\cdot \|y\|^2+(x,y)^2}{\|Sx\|^2 \|Sy\|^2}\right)^2, $$ and it remains to prove that $$ \frac{\|x\|^2\cdot \|y\|^2+(x,y)^2}{\|Sx\|^2 \|Sy\|^2}\geqslant \frac2{{\rm tr}\, S^4}. $$ We may suppose that $S$ is diagonal with diagonal elements $\alpha,\beta$. Also denote $x=(x_1,x_2),y=(y_1,y_2)$. For $a=(k_1^2,k_2^2),b=(x_1^2,x_2^2),p=(k_1^2,k_2^2)$ our lemma says that $$ 2\frac{\|Sx\|^2 \|Sy\|^2}{{\rm tr}\, S^4}\leqslant \sqrt{(x_1^4+x_2^4)(y_1^4+y_2^4)}+x_1^2y_1^2+x_2^2y_2^2, $$ and it remains to use out starting inequality.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.