Desigualdade do rearranjo

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

Em matemática, a desigualdade do rearranjo[1] afirma que

x_ny_1 + \cdots + x_1y_n
\le x_{\sigma (1)}y_1 + \cdots + x_{\sigma (n)}y_n
\le x_1y_1 + \cdots + x_ny_n

para cada escolha de números reais

x_1\le\cdots\le x_n\quad\text{e}\quad y_1\le\cdots\le y_n

e cada permutação

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

de x1, . . ., xn. 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[editar | editar código-fonte]

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[editar | editar código-fonte]

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

Portanto,

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

Expandingo este produto e rearranjando termos, temos

x_{\sigma(j)}y_j+x_jy_k\le x_jy_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.

Referências

  1. Hardy, G.H.; Littlewood, J.E.; Pólya, G. (1952), Inequalities, Cambridge Mathematical Library (2. ed.), Cambridge: Cambridge University Press, ISBN 0-521-05206-8 , Section 10.2, Theorem 368