Ανισότητα της αναδιάταξης

Στα μαθηματικά, η ανισότητα της αναδιάταξης δίνει ότι για κάθε $n$ πραγματικούς αριθμούς $x_{1}\leq x_{2}\leq \ldots \leq x_{n}$ και $y_{1}\leq y_{2}\leq \ldots \leq y_{n}$ και οποιαδήποτε μετάθεση $\pi \colon [n]\to [n]$, ισχύει ότι

$x_{1}y_{1}+x_{2}y_{2}+\ldots +x_{n}y_{n}\geq x_{1}y_{\pi (1)}+x_{2}y_{\pi (2)}+\ldots +x_{n}y_{\pi (n)}\geq x_{1}y_{n}+x_{2}y_{n-1}\ldots +x_{n}y_{1}$.

Ή πιο απλά, το εσωτερικό γινόμενο $x^{T}y$ μεγιστοποιείται όταν $x$ και $y$ έχουν την ίδια διάταξη, και ελαχιστοποιείται όταν έχουν αντίθετη διάταξη.

Η ανισότητα αυτή χρησιμοποιείται για την απόδειξη άλλων βασικών ανισοτήτων, όπως η ανισότητα Κωσύ-Σβαρτς και η ανισότητα αριθμητικού-γεωμετρικού μέσου), καθώς επίσης και σε διάφορες αποδείξεις ορθότητας για άπληστους αλγορίθμους.

Παράδειγμα

Έστω ότι έχουμε $x_{1}=3,x_{2}=5,x_{3}=9$ και $y_{1}=4,y_{2}=7,y_{3}=12$. Από τον παρακάτω πίνακα επιβεβαιώνουμε ότι όταν πάρουμε το άθροισμα των γινομένων με την ίδια διάταξη μεγιστοποιείται το άθροισμα (δίνεται με μπλε χρώμα στον πίνακα), ενώ όταν το πάρουμε με την αντίθετη διάταξη ελαχιστοποιείται (δίνεται με κόκκινο χρώμα).

Μετάθεση $\pi$	Άθροισμα	Αποτέλεσμα
$(1\;2\;3)$	$3\cdot 4+5\cdot 7+9\cdot 12$	$\color {blue}155$
$(1\;3\;2)$	$3\cdot 4+5\cdot 12+9\cdot 7$	$135$
$(2\;1\;3)$	$3\cdot 7+5\cdot 4+9\cdot 12$	$149$
$(2\;3\;1)$	$3\cdot 7+5\cdot 12+9\cdot 4$	$117$
$(3\;1\;2)$	$3\cdot 12+5\cdot 4+9\cdot 7$	$119$
$(3\;2\;1)$	$3\cdot 12+5\cdot 7+9\cdot 4$	$\color {red}107$

Απόδειξη

Θα αποδείξουμε ότι καμία μετάθεση $\pi$ δεν δίνει μεγαλύτερο άθροισμα από την μετάθεση $\pi =(1\;2\;\ldots \;n)$. Έστω ότι $\pi$ είναι μία μετάθεση με το μέγιστο άθροισμα. Θα αποδείξουμε ότι δεν μπορούν να υπάρχουν $i>j$ τέτοια ώστε $y_{\pi (i)}<y_{\pi (j)}$. Τότε θεωρούμε την μετάθεση $\pi '$ που αντιμεταθέτει τους δείκτες $i,j$, δηλαδή $\pi '(i)=j$ και $\pi '(j)=i$ και $\pi '(k)=\pi (k)$ για κάθε $k\neq i,j$.

Τότε το άθροισμα αλλάζει κατά

${\begin{aligned}\Delta &=x_{1}y_{\pi '(1)}+\ldots +x_{n}y_{\pi '(n)}-(x_{1}y_{\pi (1)}+\ldots +x_{n}y_{\pi (n)})\\&=x_{i}y_{\pi '(i)}+x_{j}y_{\pi '(j)}-(x_{i}y_{\pi (i)}+x_{j}y_{\pi (j)})\\&=x_{i}y_{\pi (j)}+x_{j}y_{\pi (i)}-(x_{i}y_{\pi (i)}+x_{j}y_{\pi (j)})\\&=x_{i}(y_{\pi (j)}-y_{\pi (i)})+x_{j}(y_{\pi (i)}-x_{j}y_{\pi (j)})\\&=(y_{\pi (j)}-y_{\pi (i)})(x_{i}-x_{j}).\end{aligned}}$

Από την υπόθεση ότι $i>j$ (δηλαδή $x_{i}\geq x_{j}$) και $y_{\pi (i)}<y_{\pi (j)}$, έχουμε ότι $\Delta >0$. Επομένως, η μετάθεση $\pi '$ οδηγεί σε μεγαλύτερο άθροισμα από την $\pi$. Άρα οποιαδήποτε μετάθεση έχει το μέγιστο άθροισμα δεν μπορεί να έχει τέτοια $i,j$ άρα πρέπει να έχει την ίδια διάταξη $x$.

Αντίστοιχα, θεωρώντας την $y'_{i}=-y_{i}$, προκύπτει το κάτω φράγμα.

Εφαρμογές

Απόδειξη της ανισότητας Νέσμπιττ

Η ανισότητα Νέσμπιττ λέει ότι για οποιοσδήποτε θετικούς πραγματικούς αριθμούς $a,b,c$,

${\frac {a}{b+c}}+{\frac {b}{a+c}}+{\frac {c}{a+b}}\geq {\frac {3}{2}}.$

Χωρίς βλάβη της γενικότητας, αφού η ανισότητα είναι συμμετρική ως προς τα $a,b,c$ μπορούμε να θεωρήσουμε ότι $a\geq b\geq c$, και επομένως έχουμε ότι $a+b\geq a+c\geq b+c$ και ότι

${\frac {1}{b+c}}\geq {\frac {1}{a+c}}\geq {\frac {1}{a+b}}.$

Επομένως από την ανισότητα της αναδιάταξης έχουμε ότι

${\frac {a}{b+c}}+{\frac {b}{a+c}}+{\frac {c}{a+b}}\geq {\frac {b}{b+c}}+{\frac {c}{a+c}}+{\frac {a}{a+b}},$

και

${\frac {a}{b+c}}+{\frac {b}{a+c}}+{\frac {c}{a+b}}\geq {\frac {c}{b+c}}+{\frac {a}{a+c}}+{\frac {b}{a+b}}.$

Αθροίζοντας της δύο ανισότητες, λαμβάνουμε

$2\cdot \left({\frac {a}{b+c}}+{\frac {b}{a+c}}+{\frac {c}{a+b}}\right)\geq {\frac {b+c}{b+c}}+{\frac {a+c}{a+c}}+{\frac {a+b}{a+b}}=3.$

Τέλος, αναδιατάσσοντας λαμβάνουμε την ζητούμενη.

Απόδειξη της ανισότητας Κωσύ-Σβαρτς

Θα αποδείξουμε την εξής μορφή της ανισότητας Κωσύ-Σβαρτς για $2n$ θετικούς πραγματικούς αριθμούς $a_{1},\ldots ,a_{n}$ και $b_{1},\ldots ,b_{n}$,

$\left(a_{1}^{2}+\ldots +a_{n}^{2}\right)\cdot \left(b_{1}^{2}+\ldots +b_{n}^{2}\right)\geq \left(a_{1}b_{1}+\ldots +a_{n}b_{n}\right)^{2}.$

Αναπτύσσοντας τα δύο μέλη έχουμε ότι η ανισότητα είναι ισοδύναμη με την

$\sum _{i=1}^{n}\sum _{j=1}^{n}a_{i}^{2}b_{i}^{2}\geq \sum _{i=1}^{n}\sum _{j=1}^{n}a_{i}b_{i}a_{j}b_{j}.$

Θεωρώντας την ακολουθία με $n^{2}$ στοιχεία,

$x=\left(a_{1}b_{1},\ldots ,a_{1}b_{1},a_{2}b_{2},\ldots ,a_{2}b_{2},\ldots ,a_{n}b_{n},\ldots ,a_{n}b_{n}\right),$

και την αναδιάταξή της

$y=\left(a_{1}b_{1},\ldots ,a_{1}b_{n},a_{2}b_{1},\ldots ,a_{2}b_{n},\ldots ,a_{n}b_{1},\ldots ,a_{n}b_{n}\right),$

έχουμε ότι από την ανισότητα της αναδιάταξης

$\sum _{i=1}^{n}\sum _{j=1}^{n}a_{i}^{2}b_{i}^{2}=x^{T}x\geq x^{T}y=\sum _{i=1}^{n}\sum _{j=1}^{n}a_{i}b_{i}a_{j}b_{j},$

αφού $x$ και $y$ δεν έχουν πάντα την ίδια διάταξη, ενώ η $x$ έχει την ίδια διάταξη με τον εαυτό της.

Απόδειξη της ανισότητας αριθμητικού-γεωμετρικού μέσου

Η ανισότητα αριθμητικού-γεωμετρικού μέσου δίνει ότι για κάθε $n$ θετικούς πραγματικούς αριθμούς $a_{1},\ldots ,a_{n}$

${\frac {a_{1}+\ldots +a_{n}}{n}}\geq {\sqrt[{n}]{a_{1}+\ldots +a_{n}}}.$

Η ανισότητα αυτή είναι ομογενής, δηλαδή αν θεωρήσουμε $b_{i}=\lambda a_{i}$ για οποιαδήποτε σταθερά $\lambda >0$, τότε η μορφή της ανισότητας δεν αλλάζει, δηλαδή,

${\frac {b_{1}+\ldots +b_{n}}{n}}={\frac {\lambda a_{1}+\ldots +\lambda a_{n}}{n}}=\lambda \cdot {\frac {a_{1}+\ldots +a_{n}}{n}},\quad$ και $\quad {\sqrt[{n}]{b_{1}\cdot \ldots \cdot b_{n}}}={\sqrt[{n}]{(\lambda a_{1})\cdot \ldots \cdot (\lambda a_{n})}}=\lambda \cdot {\sqrt[{n}]{a_{1}\cdot \ldots \cdot a_{n}}}.$

Επομένως,

${\frac {a_{1}+\ldots +a_{n}}{n}}\geq {\sqrt[{n}]{a_{1}+\ldots +a_{n}}}$ αν και μόνο αν ${\frac {b_{1}+\ldots +b_{n}}{n}}\geq {\sqrt[{n}]{b_{1}+\ldots +b_{n}}}$.

Συνεπώς, χωρίς βλάβη της γενικότητας θεωρούμε $a_{1}\leq \ldots \leq a_{n}$ με γινόμενο $a_{1}\cdot \ldots \cdot a_{n}=1$. Θεωρούμε επίσης

${\begin{aligned}x_{1}&=a_{1},\\x_{2}&=a_{1}a_{2},\\&\vdots \\x_{n}&=a_{1}\cdots \ldots \cdot a_{n}=1.\end{aligned}}$

Από την ανισότητα της αναδιάταξης

$a_{1}+\ldots +a_{n}={\frac {x_{1}}{x_{n}}}+{\frac {x_{2}}{x_{1}}}+\ldots +{\frac {x_{n}}{x_{n-1}}}\geq {\frac {x_{1}}{x_{1}}}+\ldots +{\frac {x_{n}}{x_{n}}}=n$.

Δηλαδή,

${\frac {a_{1}+\ldots +a_{n}}{n}}\geq 1={\sqrt[{n}]{a_{1}\cdot \ldots \cdot a_{n}}}.$

Εφαρμογή σε πρόβλημα βελτιστοποίησης

Έστω ότι θέλουμε να τοποθετήσουμε $n$ ανεμογεννήτριες με αποδόσεις $\eta _{1},\ldots ,\eta _{n}$ σε $n$ πιθανές θέσεις με ροή ανέμου $r_{1},\ldots ,r_{n}$. Αν τοποθετήσουμε την $i$-οστή ανεμογεννήτρια στην $j$-οστή θέση τότε λαμβάνουμε $\eta _{i}\cdot r_{j}$ ενέργεια. Πώς πρέπει να βάλουμε τις ανεμογεννήτριες στις θέσεις που έχουμε ώστε να μεγιστοποιήσουμε την συνολική ενέργεια που θα λάβουμε;

Πρέπει να βρούμε την μετάθεση $\pi$, ώστε να μεγιστοποιήσουμε το άθροισμα,

$\sum _{i=1}^{n}\eta _{i}\cdot r_{\pi (i)}.$

Από την ανισότητα της αναδιάταξης, το άθροισμα μεγιστοποιείται όταν η $\pi$ έχει την ίδια διάταξη με την $\eta$, που οδηγεί στον απλό αλγόριθμο: τοποθετούμε την ανεμογεννήτρια με την μέγιστη απόδοση στην θέση με την μέγιστη ροή, μετά την ανεμογεννήτρια με την δεύτερη μέγιστη απόδοση στην θέση με την δεύτερη μέγιστη ροή, κ.ο.κ.