4

Let $a_{1},b_{1},a_{2},b_{2},\cdots,a_{n},b_{n}$ be real numbers such that $$\min{(a_{1},a_{2},\cdots,a_{n})}\ge 0$$

show that

$$\color{#0a0}{\text{$\max{(a_{1},a_{2},\cdots,a_{n})}\left(\displaystyle\sum_{1\le i,j\le n}\min{(a_{i},a_{j})}b_{i}b_{j}\right)\ge\left(\displaystyle\sum_{1\le i\le n}a_{i}b_{i}\right)^2$}}$$

I have done the proof of the $n=2,3$

$$\min{(a_{1},a_{2},\cdots,a_{n})}\ge 0\Longrightarrow a_{i}\ge 0,i=1,2,\cdots,n$$ Without loss of generality,Let $a_{1}\ge a_{2}\ge\cdots\ge a_{n}\ge 0$.then we can $$2a_{1}\sum_{1\le i<j\le n}a_{j}b_{i}b_{j}\ge \left(\sum_{1\le i\le n}a_{i}b_{i}\right)^2$$ but I'm having a problem in proving this inequality.

badskjapanses
  • 218
  • 4
    This can be phrased as a matrix problem: define $w_i = \frac{a_i}{\max{a_1,\ldots,a_n}} \in [0,1]$ and consider the matrix $W_{ij} = \min(w_i,w_j)-w_iw_j$. Your statement is equivalent to $b^TWb \geq 0$ for all vectors $b$, i.e. that $W$ is positive definite. – Winther Mar 02 '15 at 04:08
  • 1
    can you post detail? – badskjapanses Mar 02 '15 at 10:20

3 Answers3

3

Assume that $a_1\geq a_i$ for $i>1$, and then

$$ \max{(a_1,...,a_N)}=a_1 $$

$$ \min{(a_1,a_i)}=a_i $$

The inequality for $(a_1,...,a_N)$ can be transformed into a similar one for $(a_2,...,a_N)$:

$$ a_1 \sum_{i,j=1}^N \min{(a_i, a_j)}b_i b_j \geq \left(\sum_{i=1}^N a_i b_j\right)^2 $$

$$ a_1 \sum_{i,j=2}^N \min{(a_i, a_j)}b_i b_j + 2a_1 b_1 \sum_{i=2}^N a_j b_j+ a_1^2 b_1^2\geq \left(\sum_{i=2}^N a_i b_j\right)^2 + 2a_1b_1\sum_{i=2}^Na_ib_i+a_1^2b_1^2 $$

$$ a_1 \sum_{i,j=2}^N \min{(a_i, a_j)}b_i b_j\geq \left(\sum_{i=2}^N a_i b_j\right)^2 $$

The last inequality is satisfied if $a_1\geq a_i$ and if the initial inequality is satisfied for $(a_2,...,a_N)$. By induction it completes the proof.

atarasenko
  • 576
  • 4
  • 10
0

Your final inequality is wrong as you forgot the case $i=j$. In fact the true inequality is: $$2a_{1}\sum_{1\le i<j\le n}a_{j}b_{i}b_{j}+a_{1}\sum_{1\le i=j\le n}a_{j}b_{i}b_{j}\ge \left(\sum_{1\le i\le n}a_{i}b_{i}\right)^2$$which becomes $$2a_{1}\sum_{i<j}a_{j}b_{i}b_{j}+a_{1}\sum_ia_{i}b_i^2\ge \left(\sum_ia_ib_i\right)^2$$ Now a proof sounds easy. Just note that$$\left(\sum_ic_i\right)^2=\sum_ic_i^2+2\sum_{i<j}c_ic_j$$for example $(c_1+c_2+c_3)^2=c_1^2+c_2^2+c_3^2+2(c_1c_2+c_1c_3+c_2c_3)$. Now by substituting $c_i=a_ib_i$ we obtain$$\left(\sum_ia_{i}b_{i}\right)^2=\sum_ia_{i}^2b_{i}^2+2\sum_{i<j}a_{i}a_{j}b_{i}b_{j}$$Now since $a_1\ge a_2\ge \cdots\ge a_n\ge 0$ we have$$a_1a_jb_ib_j\ge a_ia_jb_ib_j\\a_1a_ib_i^2\ge a_i^2b_i^2$$therefore$$\left(\sum_ia_{i}b_{i}\right)^2=\sum_ia_{i}^2b_{i}^2+2\sum_{i<j}a_{i}a_{j}b_{i}b_{j}\le \sum_ia_1a_{i}b_{i}^2+2\sum_{i<j}a_{1}a_{j}b_{i}b_{j}$$which is the same result we wanted to prove $\blacksquare$

Mostafa Ayaz
  • 31,924
0

There is a 1-line probabilistic proof of Winther's reformulation of this problem.

Claim. Given any $t_1,\ldots,t_n\in [0,1]$, the matrix $W_{ij}=\min(t_i,t_j)-t_it_j$ is positive semidefinite.

Proof. Let $(B_t)_{t\in [0,1]}$ be a Brownian bridge pinned at $t=0$ and $t=1$, which is a stochastic process satisfying $\mathbb E(B_sB_t)=\min(s,t)-st$ for all $s,t\in [0,1]$. Then for any vector $b\in\mathbb R^n$, $$ b^TWb=\sum_{i,j}b_iW_{ij}b_j=\sum_{i,j}b_i\mathbb E(B_{t_i}B_{t_j})b_j=\mathbb E\Biggl[\Bigl(\sum_i b_i B_{t_i}\Bigr)^2\Biggr]\geq 0. $$

pre-kidney
  • 30,223