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[edit]

[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