Majorization, polyhedra and statistical testing problems

UNIVERSITY OF OSLO Department of Informatics

Majorization, polyhedra and statistical testing problems.

Geir Dahl

Report 240,

ISBN 82-7368-155-6

February 1997

Majorization, polyhedra and statistical testing problems.

Geir Dahl

∗

February 1997

Abstract

There are important connections between majorization and convex polyhedra. Both weak majorization and majorization are preorders related to certain simple convex cones. We investigate the facial struc- ture of a polyhedral cone ^C associated with a layered directed graph.

A generalization of weak majorization based on ^C is introduced. It denes a preorder of matrices. An application in statistical testing theory is discussed in some detail.

Keywords: Majorization, polyhedra, cone ordering, statistical testing.

1 Introduction

In this paper we study some problems related to majorization. For ^{z ∈IRn} we let ^z[j] denote the ^jth largest number among the components of ^z. If

x,y ∈ IRⁿ one says that ^x is weakly majorized by ^y, denoted by ^{x ≺w y}, provided that

Xk j=1

x_[j] ≤ Xk

j=1

y_[j] for^k = 1, . . . , n.

If, in addition, equality holds for ^{k = n}, then ^x is majorized by ^y and we write ^x≺y. Both ^≺ and ^≺w are preorderings that reect how spread out the components of the vectors are. These concepts play an important role in dierent areas of mathematics and statistics, see [10], [1] and other papers

∗Institute of Informatics, University of Oslo, P.O.Box 1080, Blindern, 0316 Oslo, Nor- way (Email:[email protected])

1

in the special issue of Linear Algebra and Its Appl. (Volume 199, 1994) in honor of I. Olkin.

There are interesting (convex) polyhedra that are related to (weak) ma- jorization. This applies to the polytope^Ωn of^n×ndoubly-stochastic matri- ces as one has the well-known characterization of Hardy-Littlewood-Polya:

x ≺ y if and only if there exists an ^{S ∈ Ωn} with ^{x = Sy}. For a given majorization, say ^{x ≺ y}, the polytope ^{Ω(x ≺ y)} consisting of all ^{S ∈ Ωn} satisfying ^x=Sywas studied in [5]. Several combinatorial properties of this polytope were established. As another example, [6] and [7] contains a study of the concept of weak^k-majorization from a polyhedral point of view. Both

≺w and ^≺ are cone orderings corresponding to certain simple polyhedral cones (see [10]). For instance, consider the convex cone ^Dn+ of nonincreasing and nonnegative vectors

Dⁿ+={x∈IRⁿ:x₁ ≥. . .≥x_n≥0}.

Assume that both the vectors ^xand ^y are nonincreasing. Then ^xis weakly majorized by ^y if and only if ^y−x lies the polar cone of ^D+n (consisting of the vectors^zsatisfying^wTz≥0for all^{w∈ Dn+}). Now, due to the simplicity of the cone ^Dn+ one can explicitly determine a nite set of generators (a frame) so that ^Dn+ is the set of nonnegative linear combinations of these generators. From this fact one may derive nice characterizations of Schur- convex functions and also dierent characterizations of weak majorization.

In this paper we study from a polyhedral point of view a class of convex cones that contains ^Dn+ as a special case. The motivation comes from sta- tistical testing theory, and this application is discussed in some detail. The paper is organized as follows. In section 2 we introduce a polyhedral cone

C associated with layered directed graphs. In a special case ^C consists of nonnegative ^m×n matrices where no entry is smaller than any entry in a preceding row. Thus, for ^{n= 1} we have ^{C =Dm+}. The faces of ^C are stud- ied (in the general case) and characterized by means of certain partitions in the graph. In section 3 we relate ^C to weak majorization and introduce a new preorder based on ^C. The application in statistical testing theory is presented in section 4. It concerns optimal tests for certain testing problems in discrete experiments.

We describe our notation. ^Sn denotes the group of permutations on ⁿ elements and ^Kn is the standard simplex in ^IRn, i.e., ^{Kn = {x ∈ IRn+ :}

P_n

j=1x_j = 1}. For a nite set ^V we let ^IRV denote the vector space of real valued functions from ^V to ^IR. ⁰ denotes the vector with all components being zero. If ^{S ⊆V} the vector^χS is the incidence vector of^S (so ^χSv equals 1 if^v∈S and 0 otherwise) and we also dene^{x(S) =P}v∈Sx_v for^x∈IRV. If

2

A⊆ IR^V the convex hull (conical hull) of^Ais denoted by conv^(A)(cone^(A)).

The relative interior of a convex set ^C is denoted by rint^(C). For polyhedral theory, we refer to [4], [12], [14]. Some graph terminology is used, but is is fairly standard.

2 A cone of row-ordered vectors

Let ⁿⁱ for ⁱ= 1, . . . , m be given positive integers. Let ^{Ri ={(i, j) : 1≤ j ≤}

ni}forⁱ= 1, . . . , mand dene the index set (or node set)^{V =R1∪. . .∪Rm}. Each set ^Ri is called a row. We let ^{D = (V, E)} denote the directed graph with node set ^V and with an arc from each node in the row^Ri to each node in the next row ^Ri+1 for ⁱ = 1, . . . , m−1. Thus, ^{E ={(u, v) : u ∈ Ri, v ∈}

R_i+1 for some ^i≤m−1}. ^Dis a layered digraph. In the special case where

n₁ = . . . = n_m = n, the nodes correspond to the entries (or indices) of an

m×n-matrix. We shall study certain problems in the vector space ^IRV of real valued functions from ^V to the reals. In the matrix special case above this vector space may be identied with ^IRm,n.

We are interested in the polyhedral cone^{C ⊂IRV} consisting of the vectors

x∈IR^V that satisfy the following set of homogeneous linear inequalities (i) ^{xu≥ xv} for all^{(u, v)∈E;}

(ii) ^{xv ≥0} for all^{v∈V .} (1)

Thus a nonnegative vector ^{x≥ 0} lies in ^C i no component of ^x is smaller than a component in the next row. The cone ^C is full dimensional. If^x∈C we say that ^x is row-ordered.

Our main task in this section is to study the facial structure of ^C. The faces and, in particular, the extreme rays of ^C are of interest in two dierent contexts in the subsequent sections; majorization and statistical testing.

The faces of ^C are related to partitions of ^V as discussed in the fol- lowing. Consider a partition ^{N = {N0, N1}, . . . , N_p} of ^V where the sets

N₁, . . . , N_p are nonempty while ^N0 may be empty. (A more concise no- tation would be ^{N = (N0,{N1}, . . . , N_p})). We say that partitions ^{N =}

{N₀, N₁, . . . , N_p} and ^{M= {M0, M1}, . . . , M_q} are equal and write ^{N = M} if ^p=q,^{N0 =M0} and^{N1, . . . , Np}={M1, . . . , Mq}, so ^N1, . . . , Np is just a renumberingof the sets^M1, . . . , Mp. (This is consistent with^(N0,{N1, . . . , Np}) = (M₀,{M₁, . . . , M_q})). The partition ^N induces an equivalence relation ^≡N on ^N in the usual way, that is,^{i≡N j} if and only if^{i, j ∈Nk}for some^{k ≤p}. We write ^{u≡N 0} if ^{i ∈N0}. If no confusion should arise, we may write^≡ in stead of ^≡N.

3

Partitions with a certain relation to the rows ^R1, . . . , Rm are of interest below, and to dene these some more terminology is useful. For integers

l and ^r with ^{l ≤ r} we call the set ^{I = {l, l} + 1, . . . , r− 1, r} an interval and dene ^{l(I) := l}, ^{r(I) := r}. A family of intervals ^It, ^t = 0, . . . , p is called cross-free if there is a permutation^{π ∈Sp+1} with ^{π(0) = 0} such that

r(I_π(t+1)) ≤ l(I_π(t)) for ^{t = 0,}1, . . . , p−1. Let ^{N = {N0, N1}, . . . , N_p} be a partition and dene the associated sets (projections)

I(N_t) ={i ≤m :R_i∩N_t6=∅}

for ^t = 0, . . . , p. We say that ^N is cross-free if ^{I(N0), I(N1}), . . . , I(N_p) is a family of cross-free intervals. It is not dicult to verify that ^N is cross-free if and only if the following conditions hold

CF(i) if ^u≡v where^u∈Ri1, ^v∈Ri2 and ⁱ¹ < i < i2 then ^{u ≡w} for each ^w∈Ri;

CF(ii) for each ^{i < m} there is at most one ^k such that ^Nk intersects both row ^Ri and ^Ri+1;

CF(iii) ^{Rk∩N0 6=∅} implies that ^{Rt ⊂N0} for all^{t > k.}

Roughly, this means, e.g. in the matrix case, that the sets ^{N0, N1}, . . . , N_p

are stacked on top of each other with ^N0 at the bottom of the matrix, see Figure 1. Let ^Pbe the set of all cross-free partitions (with equality as dened above).

N0

N1 N2

N3 N4

Figure 1: A cross-free partition in the matrix case, ^{m= 3}and ^{n= 4}. We dene a polyhedral cone ^C(N) associated with the partition ^N:

C(N) ={x∈C :x_u =x_v when ^{u≡v; xv = 0} when ^v≡0}. (2) A crucial property of ^C(N) holds when^N is a cross-free partition.

4

Lemma 2.1

^{Let N ∈ P}. Then there is a point ^x∈C(N) such that for each

u, v∈V one has that ^{xu =xv} if and only if ^{u≡ v}.

Proof.

Assume that the partition ^{N = {N0, N1}, . . . , Np} is cross-free.

Then the sets^{I(N0), I(N1}), . . . , I(N_p)are intervals and for some permutation

π ∈S_p+1 with ^{π(0) = 0} we have^{r(Iπ(t+1))≤l(Iπ(t))} for ^t= 0, . . . , p−1. Let

x ∈ IR^V denote the vector with ^{xv = t} when ^{v ∈ Nπ(t)}, ^t = 0, . . . , p. Then, due to the construction, ^{x ∈ C}, and furthermore ^{xu = xv} if and only if

u≡v.

There is a bijection between^P and the set of faces of^C. This is described in the following proposition.

Proposition 2.2

(i) For each ^{N ∈ P} the cone ^C(N) is a face of ^C. (ii) If ^F is a nonempty face of ^C, there is an ^{N ∈ P} with^{F =C(N)}. (iii) Let ^{N,M ∈ P}. Then ^{C(N) =C(M)} if and only if ^{N =M}.

(iv) If ^{N = {N0, N1}, . . . , Np} is a cross-free partition the face ^C(N) has dimension ^p.

Proof.

(i). Let ^{N = {N0, N1}, . . . , N_p} be a cross-free partition of ^N. We prove that ^C(N) (as dened in (2)) is a face of ^C by nding an equivalent system describing ^C(N) and consisting of valid inequalities for ^C set to equality.

From property CF(i) it follows that if ^{(i1, j1) = u ≡ v = (i2, j2)} and

i₁ < i₂ then there is a path from ^u to ^v in ^D, say ^{u = u0, u1}, . . . , u_t = v, where each ^{ui ≡u} for each ⁱ. This means that each equality^{xu =xv} in (2) is equivalent to the equalities ^{xui = xui+1} for ⁱ = 0, . . . , t−1. Similarly, by CF(iii), if ^{u ≡ 0} there is a path in ^D consisting of nodes ^{u =u0, u1}, . . . , u_t

with ^{ut ∈ Rm} and ^{ui ≡ u} for all ⁱ. Thus, ^{xu = 0} is equivalent to ^{xu =}

xu1, . . . , xut−1 = xut, xut = 0. We may therefore replace all the equalities in (2)) by an equivalent system of valid inequalities for ^C set to equality, and therefore ^C(N) is a face of^C.

(ii). Observe that all the inequalities ^{xv ≥ 0} for ^{v ∈ V \Rm} may be removedin the denition of^C; they are impliedby the remaining inequalities.

Let ^F be a face of ^C. Then

F ={x∈IR^V :x_u =x_v when ^{(u, v)∈E0, xv = 0} when ^v∈V0}

for suitable^{E0 ⊆E}and^{V0 ⊆Rm}. Dene for each^v∈V the set^N(v)⊆V by

N(v) = {u ∈ V : x_u = x_v for all ^x∈F}. Since ^{v ∈N(v)} all these sets are nonempty. Moreover, it is easy to see any two sets^N(v1)and^N(v2)are either

5

equal or disjoint. Consider the set^{T ={u∈V :xu= 0} for all^x∈F}. This set may be empty, but if it is nonempty, say^v∈T, then^{T =N(v)}. It follows that the sets^N(v),^v∈V constitute a partition^{N ={N0, N1}, . . . , N_p}where

N0 = T is possibly empty. As usual, let ^≡ denote the equivalence relation induced by this partition. We prove that

F =C(N).

Let ^{x ∈ F}. If ^{u ≡ v}, then ^{u ∈ N(v)} and therefore, due to the denition of

N(v), ^{xu = xv} holds. Also, if ^{x ∈ F} and ^{v ∈ T}, then ^{xv = 0}. It follows that ^{F ⊆ C(N)}. To prove the converse inclusion, let ^{(u, v) ∈ E0}. Then each ^{x ∈ F} satises ^{xu = xv}, so ^{u ∈ N(v)}, i.e., ^{u ≡ v}. Thus each arc in

E₀ has both endnodes in the same equivalence class. Consequently all the equalities dening ^F are also valid equalities for ^C(N) (because we clearly have ^{V0 ⊆T}). This proves that ^{F =C(N)}, as desired.

It remains to prove that the partition^N is cross-free. Assume rst that

i1 < i < i2 and ^{u∈ Ri1}, ^{v ∈Ri2},^{w ∈Ri} with ^{u≡ v}. Then, by denition of

N, we have that^{xu = xv} for all ^{x∈ F} (and ^F is assumed nonempty). But for ^{x∈ F ⊆C}, we have ^{xu ≥xw ≥ xv}, and therefore ^{xu =xw} for all ^x∈F so ^u≡w. This proves that CF(i) holds. Next, assume ^{(u1, v1),(u2, v2)∈E0} where^{u1, u2 ∈Ri}. Let^x∈F. Then^{xu1 ≥xv2 =xu2 ≥xv1 =xu1} so all these numbers are equal and ^{u1 ≡u2}. This proves CF(ii). Finally, let ^u∈Rk∩N0 and let ^{x ∈ F}. Thus, ^{xu = 0} and therefore, if ^{v ∈ Rt} with ^{t > k}, we get

0 = xu ≥xv ≥0 and ^v∈N0. This proves that ^N is cross-free.

(iii). Consider two cross-free partitions ^{N ={N0, N1}, . . . , N_p} and ^M=

{M0, M1, . . . , Mq}such that^{C(N) = C(M)}. Assume that there are nodes ^u and ^vwith^{u≡N v}and^{u6≡M v}. Using Lemma 2.1 we can nd an ^x∈C(M) with^{xu 6=xv}. But^{C(N) =C(M)}so^x∈C(N)which gives (as^{u≡N v}) that

x_u = x_v; a contradiction. It follows that the equivalence classes induced by

N and those induced by ^Mcoincide. Similar arguments give that^N0=M0. Therefore ^{N = M}. (The converse, that ^{C(N) = C(M)} when ^{N = M} is trivial).

(iv). Let^{N ={N0, N1}, . . . , N_p}be a cross-free partition and consider the face ^C(N). It follows from Lemma 2.1 that no inequality ^{xu ≥ xv} where

u 6≡ v is an implicit equality for ^C(N). Thus the dimension of ^C(N) may be found from the rank ^r of the equalities in (2). It is easy to check that

r =|N₀|+P_p

t=1(|N_t|−1) and from the dimension formula for polyhedra (see [12]) we get ^{dim(C(N)) =|V| −r=p}.

The cone ^C(N) for the cross-free partition ^N shown in Figure 1 has dimension 4.

Note that there are many subsystems of (1) that induce the same face of ^C. In fact two such subsystems induce the same face if and only if they

6

dene the same cross-free partition according to the procedure described in the proof of property (ii) of Proposition 2.2.

We present some further relations between cross-free partitions and the faces of ^C. Let ^{N = {N0, N1}, . . . , Np} and ^{M= {M0, M1}, . . . , Mq} be two cross-free partitions. We say that ^N is ner than ^M, and write ^{N ⊆ M}, if ^{N0 ⊆ M0} and each set ^Nt is contained in some set ^Ms. It is easy to see

(P,⊆) is a partially ordered set.

Remark 2.3

It is useful to see what this partial ordering corresponds to in the digraph ^D. For^{N ⊆ P} dene the arc set

E(N) ={(u, v)∈E :u≡N v}.

consisting of arcs with both endnodes in the same equivalence class. Con- versely, for any subset ^E0 of ^E the connected components of the subgraph

(V, E⁰) (ignoring arc directions) gives rise to a partition of ^V, although it may not be cross-free. We observe that ^{N ⊆ M} if and only if^{N0 ⊆M0} and

E(N)⊆E(M).

The following result is a strengthening of Proposition 2.2 (iii).

Proposition 2.4

^{Let N and M} be cross-free partitions. Then ^{N ⊆ M} if and only if ^C(N)⊇C(M).

Proof.

Assume that ^{N ⊆ M} and let ^x∈C(M). If ^{u≡N v}, then ^{u≡M v} and therefore ^{xu = xv}. If ^{u ≡N 0}, then ^{u ≡M 0} and ^{xu = 0}. This proves that ^x∈C(N), and we conclude that ^C(N)⊇C(M).

Conversely, assume that ^{C(N) ⊇ C(M)}. Assume that there are nodes

u and ^v with ^{u ≡N v} and ^{u 6≡M v}. Due to Lemma 2.1) we may nd an

x ∈ C(M) such that ^{xu 6= xv}. This implies that ^{x 6∈ C(N)} (for ^{u ≡N v}) which contradicts that ^{C(N) ⊇ C(M)}. It follows that whenever ^{u ≡N v} we also have ^{u 6≡M v}. Furthermore, if ^{u≡N 0}, the each^{x∈ C(N)} satises

x_u= 0and, in particular, this holds for each^x∈C(M)(as ^C(N)⊇C(M)).

This proves that ^{N ⊆ M}.

Let ^FC denote the set of all faces of the cone ^C. It is well known that

(FC,⊆)is a lattice, called the face-lattice of^C(the partial ordering is setwise containment), see [4], [14]. We let, in any lattice,^{F ∨G}(^{F ∧G}) denote the smallest upper bound or join (greatest lower bound or meet) of the elements

F and ^G.

Corollary 2.5

^(P,⊆)is a lattice which is anti-isomorphic to the face lattice

(FC,⊆).

7

Proof.

This may be proved directly, but it also follows from Proposition 2.5 as follows. Due to Proposition 2.2 the function ^{f : P → FC} given by

f(N) =C(N) is a bijection. From Proposition 2.5 it follows that ^{N ∨ U =}

f⁻¹(C(N)∧C(M)) and ^{N ∧ U = f−1(C(N)∨C(M))}. This proves that both meet and join exist in ^P so this is a lattice and, in addition, ^f is a lattice anti-isomorphism from ^P into^FC.

We may also give an explicit description of how the lattice operations act on ^P. Let ^{N = {N0, N1}, . . . , Np} and ^{M ={M0, M1}, . . . , Mq} be cross-free partitions. We rst determine ^{N ∧ M}. The sets ^{Ni ∩Mj} for ^{1 ≤ i ≤ p},

i ≤ j ≤ q dene a partition^{U = {U0, U1}, . . . , Ur} where ^{U0 = N0∩M0} and

U₁, . . . , U_rare the remaining nonempty sets^Ni∩Mj. It is easy to see that^U is cross-free (all the properties CF(i)(iii) hold) and that it must be the greatest lower bound of^N and^M, i.e.,^{U =N ∧M}. It is somewhat more complicated to determine^{N ∨M}. Let^{U ={U0, U1}, . . . , U_r}be an upper bound (in^P) for two cross-free partitions^N and^M. Thus, due to Remark 2.3,^{N0∪M0 ⊆U0} and^{E(N)∪E(M)⊆E(U)}. Let^{W ={W0, W1}, . . . , Wt}denote the partition induced by the connected components in the subgraph ^{(V, E(N)∪E(U))} of

D, and let ^W0 be the union of the (one or two) components intersecting either^N0 or ^M0. Observe that^{W ⊆ U}. ^W may not be cross-free, but we can modify it into a cross-free partition as follows. If we can nd arcs ^{(u1, v1)} and ^{(u2, v2)} with ^{u1 ≡W v1}, ^{u2 ≡W v2} and ^{u1 6≡W u2}, then we replace these two equivalence classes (containing ^u1 resp. ^u2) by their union. We repeat this procedure until there is no arc pair left with the mentioned properties.

Next, if there are two equivalence classes, say ^W1 and ^W2, with all the sets

W1∩Ri−1,^W1∩Ri+1 and ^W2∩Ri nonempty, then we replace^W1 and ^W2 by their union ^{W1 ∪W2}. This is repeated until there is no pair of equivalence classes with these properties. Let ^W0 denote the new partition obtained by this procedure. It is not dicult to check that ^W0 is cross-free and that

W⁰ ⊆ U. Thus, we must have ^{W0 =N ∨ M}.

Observe that the construction of the meet and join in the lattice ^P also translates (via the bijection^f) to nding the meet and join for a pair of faces of the cone ^C.

Let ^{k ∈ {}1, . . . , m− 1}. We call a subset ^S of ^V a ^k-block in ^D if

S = R1∪ · · · ∪Rk ∪S⁰ for some nonempty subset ^S0 of ^Rk+1. A block is a

k-block for some ^k.

Corollary 2.6

The extreme rays of ^C are the faces ^C(N) constructed from cross-free partitions ^{N = {N0, N1}}, i.e. ^{p = 1}. Moreover, ^C is generated by the incidence vectors ^χS where ^S is either a block in ^D or ^S consist of a single node in ^R1, i.e., each vector in ^C may be written as a nonnegative linear combination of the mentioned vectors.

8

Proof.

The extreme rays have dimension 1 so the rst part follows from Proposition 2.2. The second form follows from the cross-free property of the partition ^N.

Each of the inequalities ^{xv ≥ 0} for ^{v ∈ Rm} and ^{xu ≥ xv} for ^{(u, v) ∈ E} denes a facet of ^C. This is easy to prove directly, and it also follows from Proposition 2.2. Let ^e and ^f denote the number of extreme rays and facets of ^C, respectively. We see that

e=n₁+ Xm

i=2

(2ⁿⁱ −1), f =

mX−1 i=1

n_in_i+1+n_m.

In the matrix case with ^{ni =n}for all ⁱ, we obtain ^{e =n+ (m−1)(2n−1)} and ^{f = (m −1)n2 +n}. In particular, the number of extreme rays grows exponentially in ⁿ except when^{n= 1}.

The generators of ^C determined in Corollary 2.6 may be used to give a parametric form of each face of^C. Consider a face^F of^C, so (by Proposition 2.2) ^{F =C(P)}for some cross-free partition^{N ={N0, N1}, . . . , N_p}. The sets

I(N0), I(N1), . . . , I(Np) are intervals and there is a permutation ^{π ∈ Sp+1} with ^{π(0) = 0} and ^{r(Iπ(t+1)) ≤ l(Iπ(t))} for ^t = 0, . . . , p −1. Dene, for

t = 0, . . . , p the node set ^{Gt = ∪pk=tNπ(k)}. Then each ^Gt is either a block or consist of a single node in ^R1. Moreover, ^χGt, ^t = 0, . . . , p are anely independent and they generate the face ^F, i.e.,

F =cone^{({χGt :t} = 1, . . . , p}).

We omit the proof of these facts.

Finally, let us consider the two-dimensional faces of ^C. Each such face is spanned by two generators of ^C. We say that that two distinct generators^z and^wareadjacentif^{F =}cone^({z,w})is a face of^C (and then^{dim(F) = 2}).

One may derive from Corollary 2.6 that (i) ^χv for each^v∈R1 is adjacent to all other generators, and (ii) for distinct blocks ^S and ^T the generators ^χS and ^χT are adjacent if and only if ^{S ⊂ T} or ^{T ⊂ S}. This implies that the diameter of ^C is two: any two generators are either adjacent or they are both adjacent to some other generator.

As an application of the results above we consider a polytope obtained by intersecting^C with a certain hyperplane. Let^{p ∈IRV} be a vector satisfying

p_v > 0 for ^{v ∈ V} and ^Pv∈V p_v = 1. Later, ^p will be viewed as a discrete probability distribution on the node set ^V. Consider the polyhedron

C(p) ={x∈C :X

v∈V

p_vx_v = 1} (3)

9

Observe that ^C(p)is bounded as^{C ⊂IRn+}and each^pv is positive. Therefore,

C(p)is a polytope. The faces of ^C(p)are the intersection between the faces of ^C and the hyperplane ^{{x ∈ IRV : Pv}∈V p_vx_v = 1}. In particular, we may determine the vertices of ^C(p) from Corollary 2.6. Recall the notation

p(S) = P

v∈Sp_v for each subset ^S of ^V.

Corollary 2.7

The vertices of ^C(p) are the points ^(1/p(S))χS where ^S is either a block in ^D or ^S consist of a single node in ^R1.

3 Row-ordered majorization

In this section we introduce a vector ordering which may be seen as a gen- eralization of weak majorization. Some properties of the new ordering are given.

We consider again the digraph^Dintroduced in section 2, but restrict the attention to the matrix case where ^|Ri|=n forⁱ= 1, . . . , m. Thus each ^x∈

IR^V may be viewed as a real^m×n-matrix with ^{(i, j)}th entry^xi,j, and this is done throughout the present section. The results below also hold for a general node set ^V, but the matrix case is of special interest. We identify the vector spaces ^IRV and ^IRm,n. This space is equipped with the usual inner product for vectors which in matrix form is ^{hx,yi= P}i,jx_i,jy_i,j = Trace^(xTy). We let ⁰denote the matrix (suitably dimensioned) with all zeros.

Let^K denote the the set of generators for the cone ^C, that is (see Corol- lary 2.6) ^K contains ^χv for^{v ∈R1} and the incidence vectors of blocks in^D. Thus we have

C=cone^(K).

The polar cone (sometimes called the dual cone) of ^C is the convex cone

C^◦ ={x∈IR^m,n:hy,xi ≥0 for all ^y∈C}.

Consider an ^{m ×n}-matrix ^x. We say that ^{x C}-majorizes ⁰ and write

x C 0, or ^{0 ≺C x}, provided that ^{x ∈ C◦}. Since ^K generates ^C, ^{x C 0} holds if and only if

hg,xi ≥0 for all ^g∈K. (4)

If ^y∈IRm,n we say that ^xC-majorizes by ^yand write ^{xC y} or ^{y≺C x} if

x−yC 0.

We may write the concept of^C-majorization in a more transparent form.

For a real number^a we write^{a− :=}max^{−a,0}.

10