Correlation matrix inequality conjecture

Question

Let $A_{ij}$ be a correlation matrix, in other words it has the properties that

• $\forall i\, A_{ii}=1$
• $|A_{ij}|\leq1$
• $A_{ij}=A_{ji}$
• $A_{ij}$ is positive semi-definite, ie. $\forall y_i\,\sum_{ij}A_{ij}y_iy_j\geq 0$

I conjecture that if $x_i$ is any vector of positive values, ie. $\forall i\,x_i\geq 0$, then $$ \forall i\quad\sum_jA_{ij}x_j\leq\sqrt{\sum_{jk}A_{jk}x_jx_k} $$ provided that the RHS is greater than 0 (not sure whether this last condition can be relaxed).

Can someone please point me to a proof of this conjecture, or provide a counterexample?

Answer 1

It's true. Let $v=A^{1/2}x$. The inequality means that $A^{1/2}v$ is entrywise bounded above by $\|v\|$, i.e. $u^Tv\le\|v\|$ for every row $u^T$ of $A^{1/2}$. Now the latter is true because of Cauchy-Schwarz inequality and the fact that $\|u\|^2=u^Tu=\text{a diagonal entry of } A = 1$.