Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Majorization"

m
Line 1: Line 1:
−
A [[finite]] [[sequence]] of [[real number]]s <math>\displaystyle A=a_1,a_2,\cdots,a_n</math> is said to '''majorize''' a sequence <math>\displaystyle B=b_1,b_2,\cdots,b_n</math> if and only if all of the following are true:
+
== Definition ==
  
−
<math>\displaystyle a_1\geq b_1</math>  
+
We say a [[nonincreasing]] [[sequence]] of [[real number]]s <math> a_1, \ldots ,a_n</math> '''majorizes''' another nonincreasing sequence <math>b_1,b_2,\ldots,b_n</math>, and write <math>\{a_i\}_{i=1}^n</math>[[Image:succ.gif]]<math>\{b_i\}_{i=1}^n </math> if and only if all for all <math> 1 \le k \le n </math>, <math> \sum_{i=1}^{k}a_i \ge \sum_{i=1}^{k}b_i </math>, with equality when <math> \displaystyle k = n </math>.  If <math> \displaystyle \{a_i\} </math> and <math> \displaystyle \{b_i\} </math> are not necessarily nonincreasing, then we still write <math> \displaystyle \{a_i\} </math>[[Image:succ.gif]]<math> \displaystyle \{b_i\} </math> if this is true after the sequences have been sorted in nonincreasing order.
  
−
<math>\displaystyle a_1+a_2\geq b_1+b_2</math>
+
=== Minorization ===
  
−
<math>\displaystyle \vdots</math>  
+
We will occasionally say that <math> b_1, \ldots, b_n </math> ''minorizes'' <math> a_1, \ldots, a_n </math>, and write <math> \displaystyle \{b_i\} </math>[[Image:prec.gif]]<math> \displaystyle \{a_i\} </math>, if <math> \displaystyle \{a_i\} </math>[[Image:succ.gif]]<math> \displaystyle \{b_i\} </math>.
  
−
<math>\displaystyle a_1+a_2+\cdots+a_{n-1}\geq b_1+b_2+\cdots+b_{n-1}</math>
+
== Alternative Criteria ==
  
−
<math>\displaystyle a_1+a_2+\cdots+a_n=b_1+b_2+\cdots+b_n</math>
+
It is also true that <math> \{a_i\}_{i=1}^n </math>[[Image:succ.gif]]<math> \{b_i\}_{i=1}^n </math> if and only if for all <math> 1\le k \le n </math>, <math>\sum_{i=k}^n a_i \le \sum_{i=k}^n b_i</math>, with equality when <math> \displaystyle k=1 </math>.  An interesting corrollary of this is that the finite sequence <math> \displaystyle \{a_i\} </math> majorizes <math> \displaystyle \{b_i\} </math> if and only if
 +
 
 +
We can also say that this is the case if and only if for all <math> t \in \mathbb{R} </math>,
 +
<center>
 +
<math>
 +
\sum_{i=1}^{n}|t-a_i| \ge \sum_{i=1}^{n}|t-b_i|
 +
</math>.
 +
</center>
 +
 
 +
Both of these conditions are equivalent to our original definition.
 +
 
 +
== See Also ==
 +
 
 +
* [[Inequalities]]
 +
* [[Karamata's Inequality]]
 +
* [[Convexity]]
  
 
{{stub}}
 
{{stub}}

Revision as of 21:22, 8 April 2007

Definition

We say a nonincreasing sequence of real numbers $a_1, \ldots ,a_n$ majorizes another nonincreasing sequence $b_1,b_2,\ldots,b_n$, and write $\{a_i\}_{i=1}^n$Succ.gif$\{b_i\}_{i=1}^n$ if and only if all for all $1 \le k \le n$, $\sum_{i=1}^{k}a_i \ge \sum_{i=1}^{k}b_i$, with equality when $\displaystyle k = n$. If $\displaystyle \{a_i\}$ and $\displaystyle \{b_i\}$ are not necessarily nonincreasing, then we still write $\displaystyle \{a_i\}$Succ.gif$\displaystyle \{b_i\}$ if this is true after the sequences have been sorted in nonincreasing order.

Minorization

We will occasionally say that $b_1, \ldots, b_n$ minorizes $a_1, \ldots, a_n$, and write $\displaystyle \{b_i\}$Prec.gif$\displaystyle \{a_i\}$, if $\displaystyle \{a_i\}$Succ.gif$\displaystyle \{b_i\}$.

Alternative Criteria

It is also true that $\{a_i\}_{i=1}^n$Succ.gif$\{b_i\}_{i=1}^n$ if and only if for all $1\le k \le n$, $\sum_{i=k}^n a_i \le \sum_{i=k}^n b_i$, with equality when $\displaystyle k=1$. An interesting corrollary of this is that the finite sequence $\displaystyle \{a_i\}$ majorizes $\displaystyle \{b_i\}$ if and only if

We can also say that this is the case if and only if for all $t \in \mathbb{R}$,

$\sum_{i=1}^{n}|t-a_i| \ge \sum_{i=1}^{n}|t-b_i|$.

Both of these conditions are equivalent to our original definition.

See Also

This article is a stub. Help us out by expanding it.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Majorization&oldid=14430"