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$ Aug 29, 2020 at 2:44

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.