叶卢庆的博客分享 http://blog.sciencenet.cn/u/Yaleking 这个博客不再更新.我的新博客在 blogmath.org

博文

A geometrical proof of the rearrangement inequality

已有 2050 次阅读 2014-8-9 13:53 |个人分类:线性代数|系统分类:论文交流| The, product, inequality, dot, rearrangement

In this post,we give a geometrical proof of the rearrangement inequality via dot product of two vectors.

For vectors $mathbf{OA}=(a_1,cdots,a_n)$ and $mathbf{OB}=(b_1,cdots,b_n)$ in $mathbf{R}^n$,the dot product of $mathbf{OA}$ and $mathbf{OB}$ is denoted by $mathbf{OA}cdotmathbf{OB}$,where $mathbf{R}^n$ is a $n$ dimensional vector space over the field $mathbf{R}$.And $mathbf{OA}cdot mathbf{OB}$ is defined as $|mathbf{OA}||mathbf{OB}|costheta$,where $|mathbf{OA}|$,$|mathbf{OB}|$ are the length of $mathbf{OA}$,$mathbf{OB}$,and $theta$ is the angle between $mathbf{OA}$ and $mathbf{OB}$.

As we all know,the expression
begin{equation}
 a_1b_1+cdots+a_nb_n (1)
end{equation}
can be interpreted as the dot product $mathbf{OA}cdot mathbf{OB}$.This is because,as is shown in figure 1,
begin{equation*}
 begin{cases}
|mathbf{OA}|costheta+|mathbf{AB}|cosgamma=|mathbf{OB}|,\
|mathbf{OB}|cosgamma+|mathbf{OA}|cosbeta=|mathbf{AB}|,\
|mathbf{BO}|costheta+|mathbf{BA}|cos beta=|mathbf{AO}|.
 end{cases}
end{equation*}
Solve the simultaneous equations,we have
begin{align*}
mathbf{OA}cdot mathbf{OB}&=|mathbf{OA}||mathbf{OB}|costheta\&=frac{|mathbf{OA}|^2+|mathbf{OB}|^2-|mathbf{AB}|^2}{2}\&=a_1b_1+cdots+a_nb_n.
end{align*}


Figure 1




Now we make use of the dot product interpretation of the expression (1) to prove the rearrangement inequality.The rearrangement inequality is stated below.

(Rearrangement inequality) For every choice of real numbers $a_1leq cdotsleq a_n$,$b_1leqcdotsleq b_n$,where $a_{1}<a_{n}$ or $b_{1}<b_n$, and every permutation $a_{sigma_{1}},cdots,a_{sigma_n}$ of $a_1,cdots,a_n$,the rearrangement inequality states that
 begin{equation*}
   a_nb_1 + cdots + a_1b_n
   le a_{sigma_{1}}b_1 + cdots + a_{sigma_{n}}b_{n},
 end{equation*}
 the equality holds if and only if $sigma_1=n,cdots,sigma_n=1$.And
 begin{equation*}
   a_{sigma_{1}}b_1 + cdots + a_{sigma_{n}}b_{n}leq a_1b_1+cdots+a_nb_n,
 end{equation*}
 the equality holds if and only if $sigma_1=1,cdots,sigma_n=n$.


The classical,and easy proof of this inequality can be found in [1].Below we will give a geometrical approach to this inequality.In fact,this is more like a geometrical interpretation of the rearrangement inequality than a proof of the rearrangement inequality.


Before we prove the general theorem,we first prove the special case of $n=2$,so as to let readers get the main idea quickly.

Proof of the special case of $n=2$: As is shown in figure 2.$b_1leq b_2$,$a_1leq a_2$,points $A$ and $B$ are on the line $y=x$ or below the line $y=x$.Reflect the point $B$ about the line $y=x$ we get a point $B'=(b_2,b_1)$.Now we prove that $mathbf{OA}cdotmathbf{OB}geqmathbf{OA}cdot mathbf{OB'}$,which means that $a_1b_1+a_2b_2>a_1b_2+a_2b_1$.This is because $$mathbf{OA}cdotmathbf{OB}-mathbf{OA}cdot mathbf{OB'}=mathbf{OA}cdot(mathbf{OB-OB'})=mathbf{OA}cdot mathbf{B'B}geq 0.$$

The equality $mathbf{OAcdot OB}=mathbf{OAcdot OB'}$ holds if and only if one of the points $A$ and $B$ is on the line $y=x$.  Q.E.D


Figure 2



Now we sketch the proof of the general case.In the general case,let's see vectors $mathbf{OA}=(a_1,cdots,a_n)$,$mathbf{OB}=(b_1,cdots,b_n)$ in $mathbf{R}^n$,where $a_1leqcdots leq a_n$.And there exists $1leq i<jleq n$ such that $b_ileq b_j$.The space $mathbf{R}^n$ is separated into $n!$ parts by $nchoose 2$ hyperplanes
$$
x_1=x_2,cdots,x_1=x_n;x_2=x_3,cdots,x_2=x_n;cdots,x_{n-1}=x_n.
$$
Each part is a  closed subset of  $mathbf{R}^{n}$,and the intersection of every two parts is the subset of a hyperplane.

Reflect the point $mathbf{B}$ about the hyperplane $x_i=x_{j}$,we will get $mathbf{B}'=(b_1,cdots,b_{j},cdots,b_i,cdots,b_n)$.This is because for any point $mathbf{C}=(c_1,cdots,c_i,cdots,c_j,cdots,c_n)$ on the hyperplane $x_i=x_j$,$c_i=c_j$,so
$$
mathbf{OC}cdot (mathbf{OB}-mathbf{OB'})=mathbf{OC}cdot mathbf{B'B}=0,
$$
which means that $mathbf{BB'}$ is perpendicular to the hyperplane $x_i=x_j$.And $mathbf{|OB|}=mathbf{|OB'|}$.


It is easy to verify that points $mathbf{A}$ and $mathbf{B}$ are on the same side of the hyperplane $x_i=x_j$,while $mathbf{A}$ and $mathbf{B}'$ are on the opposite of the hyperplane $x_i=x_j$(But when $b_i=b_j$ this does not happen.In this case,both $mathbf{B}$ and $mathbf{B}'$ are on the hyperplane $x_{i}=x_j$).So it is easy to verify that
$$
mathbf{OA}cdot mathbf{B'B}geq 0 ,
$$
which means that
$$ mathbf{OA}cdot mathbf{OB}geqmathbf{OA}cdot mathbf{OB'}.$$
So
$$
a_1b_1+cdots+a_ib_i+cdots+a_jb_j+cdots+a_nb_{n}geq a_1b_1+cdots+a_ib_j+cdots+a_jb_i+cdots+a_nb_n.
$$
From the above argument,we can see that when $i<j$ and $b_ileq b_j$,$mathbf{OA}cdot mathbf{OB'}leq mathbf{OA}cdot mathbf{OB}$.Repeating the above  process of reflecting the point $B$ about those hyperplanes several times,we will prove the rearrangement inequality.

1.Manfrino R B, José Antonio Gómez Ortega, Delgado R V. Inequalities,A Mathematical Olympiad Approach[M]. Basel:Birkhäuser Verlag, 2009:13.



https://wap.sciencenet.cn/blog-604208-818291.html

上一篇:线性映射对单位正方形的作用
下一篇:我的成长照片
收藏 IP: 183.138.217.*| 热度|

0

该博文允许注册用户评论 请点击登录 评论 (0 个评论)

数据加载中...
扫一扫,分享此博文

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2022-11-30 21:30

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部