2 Majorization theory.

A total order is a binary relation on a set X. It is antisymmetric, transitive, and total. For example, the set of real numbers R can be totally ordered by the order relation less than < and greater than >. Consider the set of all vectors with two non-negative real components which sum up to one, i.e., {x [member of] [R.sup.2.sub.+] : [x.sub.1] + [x.sub.2] = 1}. Since all vectors can be parameterized by ([MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]) for 0 [less than or equal to] + [less than or equal to] 1, the corresponding order reduces to the one dimensional case. Let x and y be two dimensional non-negative real vectors. Without loss of generality, order the components of the vector in decreasing order and compare the fist component [x.sub.1] and [y.sub.l]. If [x.sub.1] [greater than or equal to] [y.sub.l] then the vector x is greater than or equal to y, e.g., [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. However, this approach does not extend to the case with three or more components.

This chapter studies a certain partial order on vectors with more than two components. We will assume that the vector has non-negative real components. The partial order "Majorization" will describe when the components of a vector x are "less spread out" or "snore nearly equal" than the components of another vector y. Further on, functions that are monotone with respect to this order are called "Schur-convex" (monotonic increasing) or "Schur-concave" (monotonic decreasing) functions. Standard results as well as novel results regarding Schurconvex functions are reviewed, presented, and discussed. In order to keep the representation simple and increase readability, many examples illustrate the definitions and results.

2.1 Definition and Examples

2.1.1 Majorization for Vectors

Definition 2.1 (Majorization for vectors). For two vectors x, y [member of] [R.sup.n] with descending ordered components [x.sub.1] [greater than or equal to] [x.sub.2] [greater than or equal to] ... [greater than or equal to] [x.sub.n] [greater than or equal to] 0 and [y.sub.1] [greater than or equal to] [y.sub.2] [greater than or equal to] ... [greater than or equal to] [y.sub.n] [greater than or equal to] 0, one says that the vector x majorizes the vector y and writes

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Example 2.1. Assume the situation in Figure (2.1). We have two different vectors. In scenario A and B the largest two components ([[lambda].sup.A.sub.1] = [[lambda].sup.B.sub.1] and [[lambda].sup.A.sub.2] = [[lambda].sup.B.sub.2]) are equal. The smallest three components in scenario B are equal ([[lambda].sup.B.sub.3] = [[lambda].sup.B.sub.4] = [[lambda].sup.B.sub.5]), but in scenario A the smallest three components are unequal ([[lambda].sup.A.sub.3] > [[lambda].sup.A.sub.4] > [[lambda].sup.A.sub.5]). In addition to this, the sum of all components in scenario A and B is equal. Applying the order which is introduced in Definition 2.1, the vector in Scenario A majorizes the vector in Scenario B ([[lambda].sup.A] > [[lambda].sup.B]).

[FIGURE 2.1 OMITTED]

Remark 2.1. Note that sometimes the definition of majorization is the other way round. For example, in [50, p. 1921, a vector x is said to majorize vector y if the sum of the smallest m components of x is greater than or equal to the sum of the smallest m components of y for all 1 [greater than or equal to] m [greater than or equal to] n. This can lead to contradictive statements.

Note that the order of the components is not important to the definition, i.e., the following vectors are equal [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] with respect to the partial order in Definition 2.1. The elements are always assumed to be ordered in decreasing order.

The strict version of Definition 2.1 is denoted by x > y and means that the sum of the largest m components of the vector x is greater than the sum of the largest m components of vector y for all 1 [greater than or equal to] m < n and [[summation].sup.n.sub.k=1] [x.sub.k] = [[summation].sup.n.sub.k=1] [y.sub.k]. For further definitions the less strict notion [greater than or equal to] and [less than or equal to] will be used.

Example 2.2. The following vectors can be compared using Majorization

(1/n, 1/n, ..., 1/n) < (1/n - 1, 1/n - 1, ..., 1/n - 1, 0) < ... < (1/2, 1/2, 0, ..., 0) < (1,0, ... 0).

Example 2.3. Since Majorization provides only a partial order, there exist vectors (with at least three components) that cannot be compared, e.g.,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Closely related to Majorization are doubly stochastic matrices.

Definition 2.2 (Doubly stochastic matrix). An n x n matrix P is doubly stochastic if [P.sub.ij] [greater than or equal to] 0 for I [less than or equal to], i, j [less than or equal to] n and

[n.summation over (i=1)] [P.sub.ij] = 1, 1 [less than or equal to] j [less than or equal to] n, [n.summation over (j=1)] [P.sub.ij] = 1, 1 [less than or equal to] I [less than or equal to] n.

Related to the two dimensional example from the introduction to this section, the 2 x 2 matrix [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is doubly stochastic for all 0 [less than or equal to] t [less than or equal to] 1. In fact, the set of all doubly stochastic matrices can be parameterized by this matrix. The properties of doubly stochastic matrices are described in the following Theorems.

Theorem 2.1(Birkhoff 1946). The permutation matrices constitute the extreme points of the set of doubly stochastic matrices. Moreover, the set of doubly stochastic matrices is the convex hull of the permutation matrices.

Theorem 2.2 (Representation of doubly stochastic matrices). Every n x n doubly stochastic matrix can be represented by a convex combination of at most [n.sup.2] - 2n + 2 permutation matrices. The number [n.sup.2] - 2n + 2 cannot be replaced by a smaller number.

The next theorem connects the partial order majorization and doubly stochastic matrices.

Theorem 2.3 (Majorization and doubly stochastic matrices). A necessary and sufficient condition for x [greater than or equal to] y is that there exist a doubly stochastic matrix P such that y = Px.

In order to illustrate this relationship the partial order itself, we provide two examples.

Example 2.4. Consider the example from the beginning, i.e., [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. The corresponding doubly stochastic matrix is given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

The following concept is used to compare vectors with different [l.sub.1] norm.

Definition 2.3 (Weak majorization). For x, y [member of] [R.sup.n] with ordered components [x.sub.1] [greater than or equal to] [x.sub.2] [greater than or equal to] ... [greater than or equal to] [x.sub.n] and [y.sub.1] [less than or equal to] [y.sub.2] [less than or equal to] ... [less than or equal to][y.sub.n], y (sub) majorizes weakly x, i.e., y [[less than or equal to].sub.w] x means

[m.summation over (k=1)] [x.sub.k] [less than or equal to] [m.summation over (k=1)] [y.sub.k] for all m = 1, ..., n.

For x, y [member of] [R.sup.n] with ordered components [x.sub.1] [greater than or equal to] [x.sub.2] [greater than or equal to] ... [greater than or equal to] [x.sub.n] and [y.sub.1] [greater than or equal to] [y.sub.2] [greater than or equal to] ... [greater than or equal to] [y.sub.n], y (super) majorizes weakly x, i.e., y [[greater than or equal to].sup.w] x means

[m.summation over (k=1)] [x.sub.n-k+1] [m.summation over (k=1)] [y.sub.n-k+1] for all m = 1, ..., n.

The connection to doubly stochastic matrices is provided after the next definition.

Definition 2.4 (Substochastic and superstochastic matrix). A nonnegative matrix P = [[p].sub.ij] for which there exists a doubly stochastic matrix D = [[d].sub.ij] with [p.sub.ij] [less than or equal to] [d.sub.ij] for all i, j is called substochastic matrix. Similarly a nonnegative matrix P = [[p].sub.ij] for which there exists a doubly stochastic matrix D = [[d].sub.ij] with [p.sub.ij] [greater than or equal to] [d.sub.ij] for all i, j is called superstochastic matrix.

Remark 2.2. Note that by Theorems from von Neumann the existence of such a doubly stochastic matrix is assured [92, Thm. 2.C.1]. The necessary and sufficient condition for weak (sub and super) majorization are

y [[greater than or equal to].sup.w] x if and only if x = [P.sub.1y]

y [[greater than or equal to].sub.w] x if and only if x = [P.sub.2y]

with superstochastic matrix [P.sub.l] and substochastic matrix [P.sub.2].

Another type of majorization is defined next.

Definition 2.5 (Log-majorization). Assume x = [[x.sub.1], ..., [x.sub.n]] and y = [[y.sub.i], ..., [y.sub.n]] with [x.sub.k] [greater than or equal to] 0 and [y.sub.k] [greater than or equal to] 0. If

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

then x is log-majorized by y, i.e., y [[greater than or equal to].sub.log] x.

Log-marjoziation is stronger than majorization. This is described in the next theorem [92, 5.A.2.b].

Theorem 2.4 (Theorem 2.7 in [166]). Let the components of x, y [member of] [R.sup.n.sub.+] be nonnegative. Then

x [[less than or equal to].sub.log] implies x [[less than or equal to].sub.w] y.

2.1.2 Schur-convexity and Schur-concavity

The next definition describes a function [PHI] which is applied to the vectors x and y with x [greater than or equal to] y. The function is "order-preserving" with respect to the partial order of Majorization if it is monotonic with respect to the partial order.