For $n$ a positive integer, let $(a_1 a_2 ,\ldots, a_n)$ and $(b_l, b_2 ,\ldots, b_n)$ be two (not necessarily distinct) permutations of $(1,2, ... ,n)$. Find sharp lower and upper bounds for $a_1b_1 + \ldots + a_nb_n$

My upper bound and lower bounds are (resp):

$$ \sqrt{\sum{a_i^2b_i}\sum {b_i}} $$

$$\dfrac{\bigg(\sum \sqrt{a_ib_i}\bigg)^2}{\sum \sqrt{a_i}} $$

I would love to know if we can improve on these bounds. Moreover, I was hoping that I can prove the rearrangement inequality from this but I don't think that's possible since Cauchy-Schwarz doesn't care about the order of the inner product terms.


1 Answer 1


Using Cauchy-Schwarz we get:

$$ \begin{align} \sum_{i=1}^{n}{a_{i}b_{i}}&\leq\sqrt{\left(\sum_{i=1}^{n}{a_{i}^{2}}\right)\left(\sum_{i=1}^{n}{b_{i}^{2}}\right)}\\ &\leq\sum_{i=1}^{n}{i^{2}} \end{align} $$

Equality occurs when $a_{i}=b_{i}$ i.e. when $a_{i}$ and $b_{i}$ are in the same order. This align with upper bound and equality condition of rearrangement inequality.

$$ \rule{8cm}{0.4pt} $$

We now need to find the lower bound. Define $c_{i}$ such that $b_{i}=n+1-c_{i}$. Easy to see that $\left(c_{1},...,c_{n}\right)$ is also a permutation of $\left(1,...,n\right)$.

$$ \begin{align} \sum_{i=1}^{n}{a_{i}b_{i}}&=\left(n+1\right)\sum_{i=1}^{n}{a_{i}}-\sum_{i=1}^{n}{a_{i}c_{i}}\\ &\geq\left(n+1\right)\sum_{i=1}^{n}{i}-\sum_{i=1}^{n}{i^{2}} \end{align} $$

Equality occurs when $a_{i}=c_{i}$ i.e. when $a_{i}$ and $b_{i}$ are in reverse order. Once again, align with rearrangement inequality.

  • $\begingroup$ I guess in this special case it is possible to obtain a bound that aligns with the RI $\endgroup$
    – user675768
    Aug 29, 2020 at 2:44

You must log in to answer this question.