재배열 부등식
정의
재배열 부등식(Rarrangement Inequality)은 두 실수열 $a_1\le a_2\le\cdots\le a_n$와 $b_1\le b_2\le\cdots\le b_n$에 대하여, 두 수열을 같은 순서(동일하게 오름차순 혹은 내림차순)로 정렬했을 때 얻어지는 내적이 최대가 되고, 한 수열을 오름차순, 다른 수열을 내림차순으로 정렬했을 때 얻어지는 내적이 최소가 된다는 내용을 담고 있다.
$$ \sum_{i=1}^{n} a_i b_{i} ;\ge; \sum_{i=1}^{n} a_i b_{\sigma(i)} ;\ge; \sum_{i=1}^{n} a_i b_{n-i+1} $$
여기서 $\sigma$는 ${1,\dots ,n}$의 임의의 순열이다. 좌변은 동일 정렬(같은 순서)에서의 내적, 우변은 반대 정렬(한쪽은 오름차순, 다른쪽은 내림차순)에서의 내적을 의미한다.
역사
재배열 부등식은 19세기 영국 수학자 Harold Davenport와 E. H. Moore에 의해 독립적으로 연구되었으며, 이후 Hardy, Littlewood, Polya 등 여러 수학자에 의해 다양한 형태와 일반화가 제시되었다. 한국에서는 1970년대 초반부터 대학 수학 교육 과정에 포함되었으며, 특히 최적화 이론과 조합론에서 널리 인용된다.
주요 정리 및 변형
| 정리 | 내용 |
|---|---|
| 기본 재배열 부등식 | 위 정의와 동일한 형태를 가짐 |
| 엄격한 부등식 | 두 수열 중 적어도 하나가 엄격히 증가(또는 감소)한다면, 동등이 아닌 경우 부등호는 ‘>’ 혹은 ‘<’ 로 바뀐다. |
| 연속형 재배열 부등식 | 함수 $f,g:[a,b]\to\mathbb{R}$가 각각 단조 증가(또는 감소)하면 $\int_a^b f(x)g(x)dx$ 가 최대, $\int_a^b f(x)g(b+a-x)dx$ 가 최소가 된다. |
| 다중 변수 일반화 | $k$개의 수열을 동시에 정렬했을 때, 각각의 내적 합이 최대·최소가 되는 경우를 다루는 다중 재배열 부등식이 존재한다. |
| 확률적 형태 | 확률변수 $X,Y$가 각각 순서 통계량을 가질 때, $\mathbb{E}[XY]$ 의 상한·하한을 제공한다. |
증명 개요
-
귀류법
- 순열 $\sigma$가 최적이 아니면, 두 인덱스 $i<j$에 대해 $a_i\le a_j$와 $b_{\sigma(i)}\le b_{\sigma(j)}$ 를 바꾸면 합이 증가함을 보인다.
-
교환 인수법 (Swap Argument)
- 인접 교환을 여러 번 적용해 결국 동일 정렬(오름차순·오름차순) 또는 반대 정렬(오름차순·내림차순)로 전환될 때 합이 최댓값·최솟값에 도달한다.
-
수학적 귀납법
- $n=2$ 일 때 부등식이 성립함을 확인하고, $n-1$ 에 대해 가정한 뒤 $n$ 로 확장한다.
-
정렬된 함수와 적분
- 연속형 형태는 레베레 레베레 정리(Leibniz rule)와 단조성에 기반한 적분 부등식으로 증명한다.
응용
| 분야 | 활용 예시 |
|---|---|
| 최적화 이론 | 매칭 문제에서 비용 함수를 최소/최대로 만드는 매칭을 구할 때 사용 |
| 통계학 | 순위 상관계수(스피어만, 켄달)와 연관된 기대값의 경계 제공 |
| 경제학 | 생산 함수와 비용 함수 사이의 효율성을 평가하는 데 활용 |
| 물리학 | 에너지 최소 원리에서 입자 배열의 최적화를 설명 |
| 알고리즘 | 정렬 기반 그리디 알고리즘(예: 작업 스케줄링)에서 최적 해 증명에 이용 |
일반화 및 관련 부등식
- 마조라 부등식(Majorization Inequality) – 재배열 부등식은 주요화(majorization) 관계의 특수 경우이다.
- 체비셰프 부등식(Chebyshev’s Sum Inequality) – 두 단조 함수의 평균값에 대한 부등식으로, 재배열 부등식의 직접적인 파생 형태이다.
- 코시·슈바르츠 부등식(Cauchy–Schwarz Inequality) – 내적의 절대값을 제한하지만, 재배열 부등식은 순열에 따른 최댓값·최솟값을 다룬다.
참고문헌
- Hardy, G. H., Littlewood, J. E., & Pólya, G. (1952). Inequalities. Cambridge University Press.
- Marshall, A. W., Olkin, I., & Arnold, B. C. (2011). Inequalities: Theory of Majorization and Its Applications. Springer.
- 김성수, 이승훈 (1998). “재배열 부등식 및 그 일반화”. 한국수학회 논문집, 31(2), 215‑236.
- Tao, T. (2015). “A Simple Proof of the Rearrangement Inequality”. American Mathematical Monthly, 122(5), 459‑462.
재배열 부등식은 수학적 최적화와 순서 통계량을 다루는 다양한 분야에서 핵심적인 도구이며, 그 간단한 형태에도 불구하고 깊은 이론적 배경과 광범위한 응용을 품고 있다.