AoPSWiki
Looking for a challenging algebra text? Preparing for MATHCOUNTS or the AMC exams?
Check out Art of Problem Solving's Introduction to Algebra by Richard Rusczyk.
Personal tools

Majorization

From AoPSWiki

(Redirected from Majorize)

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"
Looking for a challenging algebra text? Preparing for MATHCOUNTS or the AMC exams?
Check out Art of Problem Solving's Introduction to Algebra by Richard Rusczyk.
© Copyright 2008 AoPS Incorporated. All Rights Reserved. • Foundation • Privacy • Contact Us