1

The question is: Given two permutation of $n$ natural numbers,what linear combination of them will have the most value? And we are asked to provide 3 different proofs.

My 2 proofs: 1)suppose we have 2 $ n$ dimensional vectors,whose coordiante values are permutations of a set of natural numbers.

The linear combination can be interpreted as their dot product

Since they have the same size,only the angle between them can change. And the dot product will have its most value if $\cos(\theta)= 1$ or if they are parrallel. So the maximum value will be when each number is multiplied by it self.

2)we write the sum of the squares of each number on the left, And other Linear combination on the left.

$$z^2 +u^2+.... =<> uv+....$$

We multiply every thing by 2,subtract by everything on the left, And complete the square on the right. Since the expressions on the right are all squares,they are bigger than the zero left on the left hand side,there fore any combination on the right will be smaller than the given left expression.

What else can be done ?what other proffs there are? Why the constraint on natural numbers? Hints of number theory? Help will be appreciated.

Logan Luther
  • 612
  • 1
    To clarify: given a set ${x_1, x_2, \ldots, x_n}$, do you want the permutations $\sigma, \tau$ such that $\sum_{i=1}^\infty x_{\sigma(i)} x_{\tau(i)}$ is maximized? – Connor Harris Apr 04 '17 at 20:15
  • 1
    Reference title:The Re-Arrangement Theorem; For non-negative $x_1,...,x_n$ and $y_1,....,y_n$ and for all permuations $s_1 , s_2$ of $ {1,...,n}$, the value of $S(s_1,s_2)=\sum_j x_{s_1(j)}y_{s_2(j)}$ is maximized when $(x_{s_1(j)}))j$ and $(y{s_2(j)})j$are both increasing (or both decreasing) sequences. And $S(s_1,s_2$) is minimized when $(x{s_1(j)})j$ is increasing and $(y{s_2(j)})_j$ is decreasing (or vice-versa). – DanielWainfleet Apr 04 '17 at 23:57

1 Answers1

1

It suffices to consider $\sum_{j=1}^nx_jx_{s(j)}$ where $s$ is a permutation of $\{1,..., n\}.$

Now WLOG $x_n=\max \{x_1,...x_n\}.$

Suppose $s(n)\ne n.$ Then there are two terms $x_nx_{s(n)}$ and $x_{s^{-1}(n)}x_n$ in the sum. But then we can replace these terms with the terms $$x_n^2\;\text {and } \;x_{s(n)}x_{s^{-1}(n)}$$ and get a sum that's at least as large. Because $$(1).\quad x_n^2+x_{s(n)}x_{s^{-1}(n)}\geq x_nx_{s(n)}+x_{s^{-1}(n)}x_n\iff $$ $$\iff (x_n-x_{s(n)})(x_n-x_{s^{-1}(n)})\geq 0$$ which holds because of the maximality of $x_n.$

Note that if $x_{s(n)}<x_n$ we have strict inequality in (1).

I leave the rest of the proof to you.

DanielWainfleet
  • 57,985