Transdesigualdad

La desigualdad de permutación , o desigualdad sobre secuencias de un solo tono , o " trans -desigualdad ", establece que el producto escalar de dos conjuntos de números es el máximo posible si los conjuntos son de un solo tono (es decir, ambos son simultáneamente no decrecientes). o simultáneamente no crecientes), y el menor posible si los conjuntos son de monotonicidad opuesta (entonces uno es no decreciente y el otro no creciente).

En otras palabras, si y , entonces para una permutación arbitraria de números , se cumple la siguiente desigualdad: $x_1\leqslant x_2 \leqslant\dots\leqslant x_n$ $y_1\leqslant y_2 \leqslant\dots\leqslant y_n$ $\sigma$ $\{1,2,\puntos,n\}$

x_1 y_n + x_2 y_{n-1} + \cdots + x_n y_1 \leqslant x_1 y_{\sigma(1)} + x_2 y_{\sigma(2)} + \cdots + x_n y_{\sigma(n)} \leqslant x_1 y_1 + x_2 y_2 + \cdots + x_n y_n

En particular, si , entonces independientemente del orden . $y_{i}=x_{i}$ $x_{1}x_{\sigma (1)}+\puntos +x_{n}x_{\sigma (n)}\leq {x_{1}}^{2}+\puntos {x_{n }}^{2}$ $x_{1},\puntos,x_{n}$

Una consecuencia de la desigualdad de permutación es la desigualdad de Chebyshev para las sumas .

Prueba

Denotemos . Para la demostración conviene reformular un poco la afirmación: $V(\sigma)=\sum \limits _{i=1}^{n}{x_{i}y_{\sigma (i)))$

\arg \max \limits _{\sigma \in S_{n}}{V(\sigma )}=\sigma _{0}

Aquí está el conjunto de todas las permutaciones posibles , y es la permutación idéntica . $S_{n}$ $\sigma _{0}:\x\mapstox$

La idea principal de la prueba es que si para algunos , al intercambiar los valores de y , no disminuiremos el valor de la suma . ${\ estilo de visualización \ sigma (i)> \ sigma (j)}$ $yo<j$ ${\ estilo de visualización \ sigma (i)}$ ${\ estilo de visualización \ sigma (j)}$ $V(\sigma)$

Considere la suma indicada para alguna permutación y tal par . Considere la permutación formada a partir de las inversiones de este par. ${\ estilo de visualización \ sigma \ not = \ sigma _ {0))$ $yo, j$ $\sigma$

\sigma ':x\mapsto \left\{{\begin{matriz}\sigma (j),&x=i,\\\sigma (i),&x=j,\\\sigma (x), &x\no \en \{{i,j}\}.\end{matriz}}\right.

Por definición,

V(\sigma ')=V(\sigma )-x_{i}y_{\sigma (i)}-x_{j}y_{\sigma (j)}+x_{i}y_{\sigma (j)}+x_{j}y_{\sigma (i)}=V(\sigma )+(x_{j}-x_{i})(y_{\sigma (i)}-y_{\sigma ( j)})

Por elección y la suposición de ordenamiento , la desigualdad es verdadera , por lo que . $yo, j$ $x, y$ $(x_{j}-x_{i})(y_{\sigma (i)}-y_{\sigma (j)})\geq 0$ ${\ Displaystyle V (\ sigma ') \ geq V (\ sigma)}$

Por lo tanto, podemos reducir el número de inversiones sin disminuir el valor (por ejemplo, fijando las inversiones en orden de clasificación de burbuja ). Como resultado, dicho proceso conducirá a la transformación en , por lo que . $V(\sigma)$ $\sigma$ $\sigma _{0}$ ${\ Displaystyle V (\ sigma) \ leq V (\ sigma _ {0})}$

Generalizaciones

Para múltiples permutaciones

Sea secuencias ordenadas dadas . Denotemos . La permutación idéntica aún se denotará como . $s$ $x_{1}^{(i)}\leq x_{2}^{(i)}\leq \dots \leq x_{n}^{(i)},\ i=1,\dots , s$ ${\displaystyle V(\sigma_{1},\dots,\sigma_{s})=x_{\sigma_{1}(1)}^{(1)}x_{\sigma_{2}( 1)}^{(2)}\puntos x_{\sigma _{s}(1)}^{(s)}+\puntos +x_{\sigma_{1}(n)}^{(1) }x_{\sigma_{2}(n)}^{(2)}\dots x_{\sigma_{s}(n)}^{(s)))$ $\sigma _{0}$

Entonces para cualquier conjunto . ${\ Displaystyle V (\ sigma _ {1}, \ puntos, \ sigma _ {s}) \ leq V (\ sigma _ {0}, \ puntos, \ sigma _ {0})}$ ${\ estilo de visualización (\ sigma _ {1}, \ puntos, \ sigma _ {s})}$

Prueba

Se demuestra de manera similar a la desigualdad de permutación habitual (un caso especial de esto para ). $s = 2$

Sin pérdida de generalidad, supondremos que , porque de lo contrario podemos simplemente multiplicar todas las permutaciones por sin cambiar el valor de la suma. ${\ estilo de visualización \ sigma _ {1} = \ sigma _ {0}}$ ${\ estilo de visualización \ sigma _ {1} ^ {-1}}$

Si al menos una de las permutaciones es diferente de , entonces para ella (la denotamos por ) existen tales que . ${\ estilo de visualización \ sigma _ {1}, \ puntos, \ sigma _ {s}}$ $\sigma _{0}$ ${\ estilo de visualización \ sigma _ {k}}$ $yo<j$ ${\ estilo de visualización \ sigma _ {k} (i)> \ sigma _ {k} (j)}$

Entonces, si en todas las permutaciones del conjunto para el cual \sigma (i) > \sigma (j) los valores y se intercambian , entonces el valor no disminuirá, pero el número total de inversiones entre sí será menor. $\sigma$ ${\ estilo de visualización (\ sigma _ {1}, \ puntos, \ sigma _ {s})}$ ${\ estilo de visualización \ sigma (i)}$ ${\ estilo de visualización \ sigma (j)}$ $V$ ${\ estilo de visualización (\ sigma _ {1}, \ puntos, \ sigma _ {s})}$

Realizando tales acciones el número necesario (finito) de veces, llegamos al conjunto sin disminuir el valor de . ${\ estilo de visualización (\ sigma _ {0}, \ puntos, \ sigma _ {0})}$ $V$

Para funciones convexas

La idea de la prueba mediante la corrección paso a paso de las inversiones es aplicable a una clase de casos más amplia que solo el producto escalar.

Sea una función convexa y esté ordenada en orden no decreciente. Después $F$ $X$ $y$

f(x_{1}+y_{\sigma (1)})+\dots +f(x_{n}+y_{\sigma (n)})\leq f(x_{1}+y_{ 1})+\puntos f(x_{n}+y_{n})

Prueba

Por definición de una función convexa, si , entonces , eso es . Sustituyendo y sumando a ambos el valor , obtenemos . En otras palabras, cuanto mayor sea el argumento, mayor será la inclinación hacia arriba de la función y más valioso será agregar un valor mayor allí para maximizar la suma. $x_{1}<x_{2},\c>0$ $f(x_{1}+c)-f(x_{1})\leq f(x_{2}+c)-f(x_{2})$ $f(x_{1}+c)+f(x_{2})\leq f(x_{1})+f(x_{2}+c)$ ${\displaystyle c=c_{2}-c_{1))$ ${\ estilo de visualización x_{1},x_{2))$ $c_{1}$ $f(x_{1}+c_{2})+f(x_{2}+c_{1})\leq f(x_{1}+c_{1})+f(x_{2}+ c_{2})$

Como en la prueba de la desigualdad de permutación habitual, elegimos tal que . $yo<j$ ${\ estilo de visualización \ sigma (i)> \ sigma (j)}$

Entonces, como se describió anteriormente, . Esto nos permite realizar una inducción similar al caso habitual. $f(x_{i}+y_{\sigma (i)})+f(x_{j}+y_{\sigma (j)})\leq f(x_{i}+y_{\sigma ( j)})+f(x_{j}+y_{\sigma(i)})$

Multiplicando todos los valores por , podemos derivar una desigualdad similar, pero con signo en sentido contrario, para funciones cóncavas . $F$ $-una$

Consecuencias

for (función convexa): la desigualdad de permutación habitual para conjuntos y $f(x)=e^{x}$ $e^{x_{1)),\dots,e^{x_{n))$ $e^{y_{1}},\puntos,e^{y_{n}}$

en (función convexa): $f(x)=x^{2}$ $\sum \limits _{i}^{n}{(x_{i}^{2}+2x_{i}y_{\sigma (i)}+y_{\sigma (i)}^{2 })}\leq \sum \limits _{i}^{n}{(x_{i}^{2}+2x_{i}y_{i}+y_{i}^{2})}$

Después de reducir ambas partes por , obtenemos nuevamente la desigualdad de permutación habitual. ${\displaystyle \sum \limits _{i=1}^{n}{(x_{i}^{2}+y_{i}^{2)))))$

para (función cóncava): ${\ estilo de visualización f (x) = \ registro {x))$ $\sum \limits _{i=1}^{n}{\ln(x_{i}+y_{\sigma (i)})}\geq \sum \limits _{i=1}^{ n}{\ln(x_{i}+y_{i})}$

Después de tomar el exponente de ambas partes: ; $\prod_{i=1}^{n}{(x_{i}+y_{\sigma (i)})}\geq \prod_{i=1}^{n}{(x_{ i}+y_{i})}$

para (función cóncava): $f(x)={\frac {1}{x}}$ ${\displaystyle \sum \limits _{i=1}^{n}{\frac {1}{x_{i}+y_{\sigma (i)))}\geq \sum \limits _{i=1 }^{n}{\frac{1}{x_{i}+y_{i))))$

Intentos fallidos de generalización

En 1946, se publicó un intento (Scripta Mathematica 1946, 12(2), 164-169) de generalizar la desigualdad de la siguiente manera:

Para y dos conjuntos de números reales y , $número 3$ $x_1\leqslant\cdots\leqslant x_n$ $y_1\leqslant\cdots\leqslant y_n$

x_1 y_{\sigma (1)} + \cdots + x_n y_{\sigma (n)} \leqslant x_1 y_{\pi(1)} + \cdots + x_n y_{\pi(n)}

si el número de inversiones en la permutación es menor que en la permutación . $\Pi$ $\sigma$

Sin embargo, más tarde resultó que esta generalización es cierta solo para . Ya que hay contraejemplos para esta generalización, tales como: $n=3$ $n=4$

{\textstyle 0\cdot 0+1\cdot 1+2\cdot 10+3\cdot 2=27<31=0\cdot 2+1\cdot 1+2\cdot 0+3\cdot 10.}

Consecuencias

La desigualdad de permutación es interesante porque le permite combinar intuitivamente sobre una base común desigualdades numéricas completamente diferentes que se usan en diferentes áreas de las matemáticas.

Esta sección trata sobre conjuntos de números de longitud y asume que la notación para denota , es decir, bucles de índice. $norte$ $x_{yo}$ ${\ estilo de visualización i> n}$ ${\ Displaystyle x_ {pulgadas}}$

La desigualdad de Cauchy-Bunyakovsky

De acuerdo con la desigualdad de permutación, para cualquier , . $k$ $\sum \limits _{i=0}^{n-1}{a_{i}a_{i+k}}\leq \sum \limits _{i=0}^{n-1}{ a_{yo}^{2}}$

De aquí se deriva un caso especial de la desigualdad de Cauchy-Bunyakovsky:

\left({\sum \limits _{i=0}^{n-1}{a_{i))}\right)^{2}=\sum \limits _{i=0}^{ n-1}\sum \limits _{j=0}^{n-1}{a_{i}a_{j}}=\sum \limits _{i=0}^{n-1}\sum \ límites _{j=0}^{n-1}{a_{i}a_{i+j}}\leq \sum \limits _{j=0}^{n-1}{\sum \limits _{ i=1}^{n}{a_{i}^{2}}}=n\sum \limits _{i=1}^{n}{a_{i}^{2}}

De manera similar, dividiendo la suma entre todos los posibles cambios de índice dimensional y usando una generalización sobre varias permutaciones, se obtiene una desigualdad más general para números enteros : ${\ Displaystyle n^{k-1}}$ $(k-1)$ $k$

\left({\sum \limits _{i=0}^{n-1}{a_{i))}\right)^{k}\leq n^{k-1}\sum \limits _{i=0}^{n-1}{a_{i}^{k}}

La desigualdad general de Cauchy-Bunyakovsky

2(a_{1}b_{1}+\puntos +a_{n}b_{n})=a_{1}b_{1}+\puntos +a_{n}b_{n}+b_{ 1}a_{1}+\puntos +b_{n}a_{n}\leq a_{1}^{2}+\puntos +a_{n}^{2}+b_{1}^{2}+ \puntos +b_{n}^{2}

Si los valores de y se normalizan de tal manera que , entonces como consecuencia se obtiene la desigualdad de Cauchy-Bunyakovsky. Para hacer esto, basta con dividir todo por , y todo por . Dado que la desigualdad de Cauchy-Bunyakovsky permite tales divisiones sin cambiar la verdad, esto prueba la afirmación. $ai}$ $bi}$ $a_{1}^{2}+\puntos +a_{n}^{2}=b_{1}^{2}+\puntos +b_{n}^{2}=1$ $ai}$ ${\displaystyle {\sqrt {a_{1}^{2}+\dots +a_{n}^{2))))$ $bi}$ ${\displaystyle {\sqrt {b_{1}^{2}+\dots +b_{n}^{2))))$

Desigualdades medias

Cuadrática y aritmética

La desigualdad entre la media cuadrática y la media aritmética se deriva elementalmente del caso particular de la desigualdad de Cauchy-Bunyakovsky demostrada anteriormente.

Aritmética y geométrica

La desigualdad entre la media aritmética y geométrica establece que

{\sqrt[{n}]{x_{1}\dots x_{n}}}\leq {\frac {x_{1}+\dots +x_{n}}{n}}

Multiplicando ambas partes por y considerando las potencias de las variables, vemos que esto es lo mismo que $norte$ $norte$

{\displaystyle nx_{1}\puntos x_{n}\leq x_{1}^{n}+\puntos x_{n}^{n))

x_{1}x_{2}\puntos x_{n-1}x_{n}+x_{2}x_{3}\puntos x_{n}x_{1}+\puntos +x_{n} x_{1}\puntos x_{n-2}x_{n-1}\leq x_{1}^{n}+\puntos x_{n}^{n}

La última desigualdad se obtiene fácilmente de la generalización de la desigualdad de permutaciones a varias permutaciones para ${\ estilo de visualización \ sigma _ {k} (i) = i + (k-1)}$

Geométrica y armónica

Llevamos la desigualdad a la misma forma que la anterior:

{\sqrt[{n}]{x_{1}\dots x_{n))}\geq {\frac {n}({\frac {1}{x_{1))}+\dots { \frac{1}{x_{n}}}}}

{\frac {1}{x_{1}}}+\dots {\frac {1}{x_{n}}}\geq {\frac {n}{\sqrt[{n}]{x_ {1}\puntos x_{n}}}}

Considerando las potencias enésimas de las variables, obtenemos $norte$

n\left({\frac {1}{x_{1))}\right)\dots \left({\frac {1}{x_{n))}\right)\leq \left({ \frac {1}{x_{1}}}\derecha)^{n}+\puntos \left({\frac {1}{x_{n}}}\derecha)^{n}

La última desigualdad es fácil de obtener mediante la aplicación directa de la desigualdad de permutación para varias permutaciones.

Enlaces

L. V. Radzivilovskiy. Generalización de la desigualdad de permutación y la desigualdad de Mongolia // Educación Matemática . - 2006. - Nº 10 .
V. I. Murashko, S. M. Gorsky, Ya. I. Sandrygailo. Funciones KφKψ-convexas y generalizaciones de desigualdades clásicas // PFMT. - 2018. - Emisión. 37 , n º 4 . — S. 98–102 .
Yue Kwok Choy, Desigualdad de reordenamiento