Desigualdade do rearranjo

Em matemática, a desigualdade do rearranjo afirma que

$x_{n}y_{1}+\cdots +x_{1}y_{n}\leq x_{\sigma (1)}y_{1}+\cdots +x_{\sigma (n)}y_{n}\leq x_{1}y_{1}+\cdots +x_{n}y_{n}$

para cada escolha de números reais

$x_{1}\leq \cdots \leq x_{n}\quad {\text{e}}\quad y_{1}\leq \cdots \leq y_{n}$

e cada permutação

$x_{\sigma (1)},\dots ,x_{\sigma (n)}\,$

de x₁, . . ., x_n. Se todos os números são diferentes, ou seja

$x_{1}<\cdots <x_{n}\quad {\text{e}}\quad y_{1}<\cdots <y_{n},$

então o valor mínimo é atingido apenas para a permutação que reverte a ordem, isto é, σ(i) = n − i + 1 para todo i = 1, ..., n, e o valor máximo é atingido apenas para a identidade, isto é, σ(i) = i para todo i = 1, ..., n.

Observe que a desigualdade do rearranjo não faz hipótese sobre o sinal dos números reais envolvidos.

Aplicações

Muitas desigualdades famosas podem ser provadas através da desigualdade do rearranjo, como a desigualdade das médias, a desigualdade de Cauchy-Schwarz e a desigualdade da soma de Chebyshev

Demonstração

A cota inferior pode ser obtida aplicando a cota superior a

$-x_{n}\leq \cdots \leq -x_{1}.$

Portanto, basta provas a cota superior. Como há um número apenas finito de permutações, existe pelo menos uma para a qual

$x_{\sigma (1)}y_{1}+\cdots +x_{\sigma (n)}y_{n}$

é maximal. No caso de haver mais de uma permutação com esta propriedade, escolhemos σ sendo uma das com o máximo número de pontos fixos.

Procedemos agora com uma prova por absurdo para provar que σ precisa ser a permutação identidade. Assuma, portanto, por absurdo, que σ não seja a identidade. Então existe um j em {1, ..., n − 1} tal que σ(j) ≠ j e σ(i) = i para todo i em {1, ..., j − 1}. Então σ(j) > j existe k em {j + 1, ..., n} com σ(k) = j. Agora

$j<k\Rightarrow y_{j}\leq y_{k}\qquad {\text{e}}\qquad j=\sigma (k)<\sigma (j)\Rightarrow x_{j}\leq x_{\sigma (j)}.\quad (1)$

Portanto,

$0\leq (x_{\sigma (j)}-x_{j})(y_{k}-y_{j}).\quad (2)$

Expandingo este produto e rearranjando termos, temos

$x_{\sigma (j)}y_{j}+x_{j}y_{k}\leq x_{j}y_{j}+x_{\sigma (j)}y_{k}\,,\quad (3)$

Portanto a permutação

$\tau (i):={\begin{cases}i&{\text{para }}i\in \{1,\ldots ,j\},\\\sigma (j)&{\text{para }}i=k,\\\sigma (i)&{\text{para }}i\in \{j+1,\ldots ,n\}\setminus \{k\},\end{cases}}$

produzida de σ pela troca dos valores σ(j) e σ(k), tem pelo menos um ponto fixo a mais que σ, pois σ(j)= j e também atinge o máximo. Isto contradiz a escolha de σ.

Ademais, se

$x_{1}<\cdots <x_{n}\quad {\text{e}}\quad y_{1}<\cdots <y_{n},$

então temos a desigualdade estrita em (1), (2) e (3) e, portanto, o máximo só pode ser atingido pela identidade.