Majorization ordering

Let and be -tuples of non-negative real numbers of the same -norm, i.e.

Then is said to be majorized by if and only if , , where is a reordering of the -tuple such that . This defines a partial order which occurs under various names in various parts of mathematics: majority ordering, majorization ordering, specialization ordering, Snapper ordering, Ehresmann ordering, dominance ordering, mixing ordering, natural ordering, .

The symbol denotes that majorizes . A few results involving the majorization ordering are as follows.

If , then for all continuous convex functions of one variable, .

A matrix of non-negative real numbers is said to be doubly stochastic if all its rows and all its columns sum to : , for all . Then if and only if there is a doubly-stochastic matrix such that .

Let be a Hermitian -matrix, its -tuple of eigen values, and its -tuple of diagonal elements. Then , [a1]. Conversely, if , then there exists a real symmetric -matrix with eigen values and diagonal elements , [a2], [a3]. The Schur result, [a1], can be reformulated to say that is in the convex hull of . In this form the result generalizes as follows. Let be a compact Lie group with Lie algebra ; let be a maximal torus in and the corresponding Weyl group. Consider the adjoint action of on . Then -orbits in correspond to -orbits in . Fix a -invariant metric on . Then the orthogonal projection of a -orbit onto is the convex hull of the corresponding -orbit, [a18]. For a more general result in the context of symplectic geometry cf. [a19].

A function , where is an open interval in , is said to be Schur convex if , , implies . Then is Schur convex if and only if it is symmetric, i.e. for all permutations , and

for all . This condition is often called the Schur condition.

For each -tuple of non-negative real numbers , define a function by

where the sum is over all permutations of . Then Muirhead's inequality says that if and only if for all -tuples of non-negative real numbers . The arithmetic-mean geometric-mean inequality corresponds to the special case .

Let be a partition of . The corresponding Young subgroup of the symmetric group is , where permutes the elements . Let be the trivial representation of and the alternating or sign representation, which assigns to a permutation its sign , i.e. if can be written as a product of transpositions then .

Let and be two partitions of , extended with zeros if necessary to make up a vector of length .

The Snapper–Liebler–Vitale–Lam–Young theorem says that the representation is a subrepresentation of if and only if , [a13].

The Rugh–Schönhofer theorem says that the intertwining number is non-zero if and only if . Here is the dual partition (conjugate partition) of , i.e. is the number of elements in , [a10].

The Gale–Ryser theorem says that there exists a matrix of zeros and ones whose rows sum to the vector and whose columns sum to the vector if and only if (or, equivalently, ), [a12].

Consider the space of all complex nilpotent -matrices. Let act on by similarity, and for each partition of , let be the orbit containing the Jordan matrix with Jordan blocks of size and zero eigen value. Then the Gerstenhaber–Hesselink theorem says that the closure of an orbit contains an orbit , , if and only if , [a6].

Let be a pair consisting of an -matrix and an -matrix . The pair is called completely reachable if the column vectors of the matrices , , span all of . This is equivalent to the property that in the linear control system the origin can be steered to any point in by suitable controls . The Kronecker indices or controllability indices of a completely-reachable pair are defined as follows. Let be the dimension of the space spanned by the column vectors of , . Let , , , . Then the Kronecker indices of are the elements of the partition dual to . (This concept of a Kronecker index should not be confused with the Kronecker index of a function at a point, cf. Lefschetz formula). The partition is invariant under the following transformations of : , where is an arbitrary -matrix; , where is an invertible -matrix; and , where is an invertible -matrix. Together these transformations make up the feedback group (of the control system ) and the Brunowski–Kalman–Morse–Wonham theorem says that is a complex invariant of the action of the feedback group, i.e. the orbits of the action are labelled by partitions of . Moreover, the closure of the orbit labelled by contains the orbit if and only if , [a6].

Let be a holomorphic vector bundle (cf. also Vector bundle, analytic) over the Riemann sphere . Then by Grothendieck's theorem, splits as a direct sum of complex line bundles , where is the unique (up to isomorphism) complex line bundle of first Chern number . Now consider a holomorphic family of complex vector bundles over . Then by Shatz' theorem, for small enough, and, conversely, if , then there is a holomorphic family such that for small and and .

All these manifestations of the majorization order are far from unrelated, cf. [a4], [a6], [a9]. There are generalizations of certain of the theorems above to the case of other Weyl groups (than ) and relations with the Bruhat ordering on the Weyl group defined by the inclusions of the closure of the parts of the Bruhat decomposition of a simple Lie group, [a5], [a7].

Let be a directed graph (cf. Graph, oriented). For a vertex , let the out-degree (demi-degree outwards), , be defined as the number of arcs starting in , and the in-degree (demi-degree inwards), , as the number of arcs terminating in . The degree at , , is . A -graph is a graph with for all vertices . Let be pairs of elements of and . Define . Then there exists a graph with if and only if in the majorization ordering, [a17].

References

[a1]	I. Schur, "Ueber ein Klasse von Mittelbildungen mit Anwendungen auf der Determinantentheorie" Sitzungsber. Berliner Math. Ges. , 22 (1923) pp. 9–20
[a2]	A. Horn, "Doubly stochastic matrices and the diagonal of a rotation matrix" Amer. J. Math. , 76 (1954) pp. 620–630
[a3]	L. Mirsky, "Matrices with prescribed characteristic roots and diagonal elements" J. London Math. Soc. , 33 (1958) pp. 14–21
[a4]	A.W. Marshall, J. Olkin, "Inequalities: majorization and its applications" , Acad. Press (1979)
[a5]	H.-P. Kraft, "Conjugacy classes and Weyl group representations" Astérisque , 87/88 (1981) pp. 191–206
[a6]	M. Hazewinkel, C.F. Martin, "Representations of the symmetric group, the specialization order, systems, and Grassmann manifolds" Enseign. Math. , 29 (1983) pp. 53–87
[a7]	C. de Cocini, C. Procesi, "Symmetric functions, conjugacy classes and the flag variety" Invent. Math. , 64 (1981) pp. 203–220
[a8]	G.H. Hardy, J.E. Littlewood, G. Pólya, "Inequalities" , Cambridge Univ. Press (1952)
[a9]	A. Kerber, "The diagram lattice as structural principle in mathematics" P. Kramer (ed.) A. Rieckers (ed.) , Group Theoretical Methods in Physics (Tübingen, 1977) , Springer (1978) pp. 53–71
[a10]	A. Mead, E. Ruch, A. Schönhofer, "Theory of chirality functions, generalized for molecules with chiral ligands" Theor. Chin. Acta , 29 (1973) pp. 269–304
[a11]	D.S. Mitrinović, J.E. Pečarić, V. Volenec, "Recent advances in geometric inequalities" , Kluwer (1989)
[a12]	H.J. Ryser, "Combinatorial mathematics" , Math. Assoc. Amer. (1963)
[a13]	R.A. Liebler, M.R. Vitale, "Ordering the partition characters of the symmetric group" J. of Algebra , 25 (1973) pp. 487–489
[a14]	J.G. Macdonald, "Symmetric functions and Hall polynomials" , Oxford Univ. Press (1979)
[a15]	P.S. Bullen, D.S. Mitrinović, P.M. Vasić, "Means and their inequalities" , Reidel (1988)
[a16]	T. Brylawski, "The lattice of integer partitions" Discrete Math. , 6 (1973) pp. 201–209
[a17]	C. Berge, "Graphs et hypergraphes" , Dunod (1970) pp. Chapt. 6
[a18]	B. Kostant, "On convexity, the Weyl group and the Iwasawa decomposition" Ann. Sci. Ec. Norm. Sup. , 6 (1973) pp. 413–455
[a19]	M.F. Atiyah, "Convexity and commuting Hamiltonians" Bull. London Math. Soc. , 14 (1982) pp. 1–15