재배열부등식, Rearrangement Inequality

서로 같은 개수의 두 숫자 모임에 있는 수를 서로 짝지어서 곱할 때 어떻게 짝을 지어야 최대, 최소의 값을 얻을 수 있는지를 설명하는 부등식이 재배열 부등식(Rearrangement Inequality)이다. 여기서는 이 부등식을 증명하고 기하학적 의미를 살펴본다.

1. 재배열부등식

재배열 부등식을 표현하는 방식은 크게 두 가지가 있다. 다음은 그 형식 중 하나다.

실수 $x_1$, $x_2$, $x_3$, $\cdots$, $x_n$과 $y_1$, $y_2$, $\cdots$, $y_n$($n \geq 2$)이 $$x_1 \leq x_2 \leq x_3 \leq \cdots \leq x_n, \quad y_1 \leq y_2 \leq y_3 \leq \cdots \leq y_n$$ 을 만족한다고 하자. 그러면 임의의 일대일대응 $\sigma : \{1,2, \cdots , n\} \to \{1,2, \cdots , n\}$에 대해 다음 부등식이 성립한다. $$\begin{align} x_n y_1 &+ x_{n-1} y_2 + \cdots + x_2 y_{n-1} + x_1 y_n \nonumber \\ &\leq x_{\sigma(1)} y_1 + x_{\sigma(2)} y_2 + \cdots + x_{\sigma(n-1)} y_{n-1} + x_{\sigma(n)} y_n \nonumber \\ &\leq x_1 y_1 + x_2 y_2 + \cdots + x_{n-1}y_{n-1} x_n y_n \end{align}$$

위 식의 일대일 대응 $\sigma : \{1,2, \cdots , n\} \to \{1,2, \cdots , n\}$를 치환이라고 하며, 이 뜻으로 $\sigma(n)$ 대신에 $\pi(n)$을 사용하기도 한다. 어찌됐든, 재배열 부등식은 대소관계를 동일하게 유지해서 곱했을 때 가장 큰 값이 얻어지고, 역순으로 곱했을 때 가장 작은 값이 얻어진다는 의미를 가진다. 위에서와 같이 등호가 있는 부등식에서는 $x_i$, $y_i$들 중에 같은 숫자도 있을 수 있기 때문에 최대를 만드는 다양한 배열이 있을 수 있다. 같은 숫자가 없는 경우에는 최대, 최소를 얻는 방법이 하나밖에 없다는 것을 다음과 같은 식으로 강조해 표현할 수 있다.

실수 $x_1$, $x_2$, $x_3$, $\cdots$, $x_n$과 $y_1$, $y_2$, $\cdots$, $y_n$($n \geq 2$)이 $$x_1 < x_2 < x_3 < \cdots < x_n, \quad y_1 < y_2 < y_3 < \cdots < y_n$$ 을 만족한다고 하자. 그러면 임의의 치환 $\sigma : \{1,2, \cdots , n\} \to \{1,2, \cdots , n\}$에 대해 다음 부등식이 성립하며, 최대, 최소를 만드는 치환은 각각 단 하나 뿐이다. $$\begin{align} x_n y_1 &+ x_{n-1} y_2 + \cdots + x_2 y_{n-1} + x_1 y_n \nonumber \\ &\leq x_{\sigma(1)} y_1 + x_{\sigma(2)} y_2 + \cdots + x_{\sigma(n-1)} y_{n-1} + x_{\sigma(n)} y_n \nonumber \\ &\leq x_1 y_1 + x_2 y_2 + \cdots + x_{n-1}y_{n-1} x_n y_n \label{th} \end{align}$$

2. 증명

등호가 있는 버전과 없는 버전의 증명방식은 같다. 같은 증명을 복제할 필요는 없으므로 여기서는 등호가 없는 버전만 증명한다. 증명에는 수학적 귀납법을 사용하겠다.

$n=2$일 때는 $x_1 < x_2$, $y_1 < y_2$이므로 $$(x_2 - x_1)(y_2 - y_1) >0$$ 이다. 위 식을 정리하면 $$x_1 y_2 + x_2 y_1 < x_1 y_1 + x_2 y_2$$ 를 얻을 수 있다. 정의역을 $\{1,2\}$로 하는 치환이 단 두 개 뿐이므로 위 식은 $n=2$일 때 식 ($\ref{th}$)가 성립함을 말한다.

이제, $n=k$($n \ge 2$)일 때 식 ($\ref{th}$)가 성립한다고 가정하자. 실수 $x_1$, $x_2$, $\cdots$, $x_{k+1}$과 $y_1$, $y_2$, $\cdots$, $y_{k+1}$이 $x_1 < x_2 < \cdots < x_{k+1}$, $y_1 < y_2 < \cdots < y_{k+1}$을 만족할 때 식 $$\begin{equation} \label{eq} x_{\sigma(1)} y_1 + x_{\sigma(2)} y_2 + \cdots + x_{\sigma(k)} y_k + x_{\sigma(k+1)} y_{k+1} \end{equation}$$ 의 값을 최대로 만드는 치환을 $\pi$라 하자. 이제 $\pi(k+1) = k+1$이라는 것을 증명하면 귀납법에 의해 식 ($\ref{th}$)의 최대부분의 증명이 끝난다. 이 사실은 귀류법으로 증명하겠다.

$\pi(k+1) \neq k+1$이라 하자. 그러면 $k+1$이 아닌 어떤 자연수 $i$, $j$에 대해 $\pi(k+1) = i$, $\pi(j) = k+1$이 성립하게 된다. 그러면 $x$, $y$들의 정의에 의해 $x_i < x_{k+1}$, $y_j < y_{k+1}$이 성립하게 된다. 따라서, $$(x_{k+1} - x_i) (y_{k+1}-y_j) > 0$$ 가 된다. 이 식을 정리하면 $$x_{k+1} y_j + x_i y_{k+1} < x_i y_j + x_{k+1} y_{k+1}$$ 즉, $$x_{\pi(j)} y_j + x_{\pi(k+1)} y_{k+1} < x_i y_j + x_{k+1} y_{k+1}$$ 이 된다. 따라서, 치환 $$\begin{equation} \pi^* (m) = \begin{cases} \pi(m) & (m \neq j \text{ and } m \neq k+1 ) \\ i & (m = j) \\ k+1 & (m = k+1) \end{cases} \end{equation}$$ 를 식 ($\ref{eq}$)의 $\sigma$에 대입하면 $\sigma = \pi$일 때보다 더 큰 값이 얻어진다. 이것은 치환 $\pi$의 정의와 모순되므로 $\pi(k+1) = k+1$이다.

여기까지의 증명으로 식 ($\ref{th}$)의 최대 부분이 모든 자연수 $n$에 대해 성립한다는 것이 설명된다.

$x_1 < x_2 < \cdots < x_{k+1}$이면 $-x_{k+1} < \cdots < -x_2 < -x_1$이므로 좀전에 증명된 최대 부분의 정리에 의해 $$-x_{\sigma(1)} y_1 - x_{\sigma(2)} y_2 - \cdots - x_{\sigma(k+1)} y_{k+1} \leq -x_{k+1} y_1 -x_k y_2 - \cdots -x_1 y_{k+1}$$ 이 성립하고 등식을 만족하는 치환은 식에 노출된 치환 하나 뿐이다. 위 식의 양변에 $-1$을 곱하면 최소 부분의 부등식이 얻어진다.

Note. 증명의 마지막 부분을 보면 알 수 있지만, 최소 부분은 최대 부분만 증명하면 자연스럽게 나오는 이야기다. 최대 부분만 증명하고 최소 부분은 따름정리로 처리해도 된다.

3. 기하학적 의미

재배열 부등식의 각 변은 벡터의 내적 모양을 띠고 있다. 또한, 치환 $\sigma$에 관계없이 벡터 $(x_{\sigma(1)}, x_{\sigma(2)}, \cdots , x_{\sigma(n)})$의 크기는 일정하다. 재배열부등식은 벡터 $(x_{\sigma(1)}, x_{\sigma(2)}, \cdots , x_{\sigma(n)})$와 $(y_1 , y_2 , \cdots, y_n)$의 내적이 언제 최대, 최소가 되는지를 설명하는 부등식이라고 볼 수 있다. 임의의 차원에 대한 설명이므로 좀 감을 잡기 위해 3차원에서 이 식을 생각해 보기로 하자. 실수 $x_1$, $x_2$, $\cdots$, $x_n$에 주어진 대소관계를 결정하는 부등식을 3차원에서 표현하면 $x < y< z$라고 볼 수 있는데, 이 식의 경계에 해당하는 식인 $x=y$, $y=z$, $z=x$를 공간에 그려보면 다음과 같다.

세 평면에 의해 공간은 여섯 부분으로 나눠지는데, 각 영역은 $x<y<z$, $x<z<y$, $y<x<z$, $y<z<x$, $z<x<y$, $z<y<x$중 하나로 표현된다. 재배열 부등식을 3차원에서 해석하면 벡터 $(x_*)$와 $(y_*)$가 같은 영역에 있을 때 내적이 최대가 됨을 의미한다. 또한, $x<y<z$를 만족하는 영역과 $z<y<x$를 만족하는 영역이 교선에 대해 대칭인데, 이 두 영역에 있는 경우끼리 내적이 가장 작음을 의미한다.

3차원보다 더 높은 차원에서도 비슷한 맥락에서 설명이 가능하다. 차원이 높아져도 정확하지는 않지만 다음과 같은 다이어그램을 통해 재배열부등식을 이해해 볼 수 있다.

 

4. 응용

재배열 부등식을 응용해서 다른 여러 부등식을 증명할 수도 있다. 대표적인 것은 산술-기하-조화평균 부등식이다. 이 증명은 여러 곳에서 증명되어 있으니 검색으로 해결하기로 하자.