AoPSWiki
Want to learn how to tackle those tough AMC/AIME/Olympiad counting and probability problems? Check out Art of Problem Solving's Intermediate Counting & Probability by David Patrick.
Personal tools

Majorization

From AoPSWiki

Contents

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}^nImage: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\}Image: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\}Image:prec.gif\displaystyle \{a_i\}, if \displaystyle \{a_i\}Image:succ.gif\displaystyle \{b_i\}.

Alternative Criteria

It is also true that \{a_i\}_{i=1}^nImage: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 consequence of this is that the finite sequence \displaystyle \{a_i\} majorizes \displaystyle \{b_i\} if and only if \displaystyle \{-a_i\} majorizes \displaystyle \{-b_i\}.

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 "http://www.artofproblemsolving.com/Wiki/index.php/Majorization"
Want to learn how to tackle those tough AMC/AIME/Olympiad algebra problems? Check out Art of Problem Solving's Intermediate Algebra by Richard Rusczyk and Mathew Crawford. Over 1600 problems!
© Copyright 2008 AoPS Incorporated. All Rights Reserved. • Foundation • Privacy • Contact Us