Desigualdade do rearranjo

Predefinição:Uma-fonte Em matemática, a desigualdade do rearranjo afirma que

$x_n{y}_1+\cdots +x_1{y}_n\le x_{\sigma (1)}{y}_1+\cdots +x_{\sigma (n)}{y}_n\le x_1{y}_1+\cdots +x_n{y}_n$

para cada escolha de números reais

$x_1\le \cdots \le x_n\text{e}{y}_1\le \cdots \le 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\text{e}{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 de Chebyshev.

Demonstração

A cota inferior pode ser obtida aplicando a cota superior a

$-x_n\le \cdots \le -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\le y_k\text{e}j=\sigma (k)<\sigma (j)\Rightarrow x_j\le x_{\sigma (j)}.(1)$

Portanto,

$0\le (x_{\sigma (j)}-x_j)(y_k-y_j).(2)$

Expandingo este produto e rearranjando termos, temos

$x_{\sigma (j)}{y}_j+x_j{y}_k\le x_j{y}_j+x_{\sigma (j)}{y}_k,(3)$

Portanto a permutação

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

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\text{e}{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.