Nonnegative sum-symmetric matrices, optimal-score partitions, and optimal resource allocation
Iosif Pinelis





Optimal-score partitions        





I. Pinelis Department of Mathematical Sciences

Michigan Technological University

Hough­ton, Michigan 49931, USA

              Tel.: +1-906-487-2108

              Fax: +1-906-487-3133

              ipinelis@mtu.edu           










Nonnegative sum-symmetric matrices, optimal-score partitions, and optimal resource allocation 



    Iosif Pinelis       



    Received: date / Accepted: date
=================================================================================================




The main result of the note describes certain optimal-score partitions, which can be interpreted as optimal resource allocations. This result is based on the fact that any nonnegative square matrix whose column sums are the same as the corresponding row sums can be represented as the sum of circuit matrices. 



49K30  
15B48   
26D15  
90C46   

52A40   
05A05   
15A15  
15A45  
15B33  
15B36 
15B51 
90C27  








§ NONNEGATIVE SUM-SYMMETRIC MATRICES

A matrix is called nonnegative if all its entries are nonnegative.
A square matrix T=(t_ij)_i,j∈[n], where [n]:={1,…,n}, is called sum-symmetric if for each i∈[n] the row sum s_i(T):=∑_j∈[n] t_ij is the same as the corresponding column sum c_i(T):=∑_j∈[n] t_ji. A matrix (c_ij)_i,j∈[n] is called a circuit matrix if for some set J⊆[n], some cyclic permutation π of J, and all i,j in [n] we have c_ij=j=π(i)∈ J, where · denotes the indicator. 
Clearly, any circuit matrix is sum-symmetric. 
A central result here is that any nonnegative sum-symmetric real matrix is a conical combination of circuit matrices; see e.g. <cit.> or <cit.>; in <cit.>, the sum-symmetric and circuit matrices are referred to as line-sum-symmetric and simple circuit matrices, respectively. 

This result has a short and simple proof, which extends almost verbatim to the case when the entries of the matrix are from a linearly ordered Abelian group (G,+,0,≥), with a linear order ≥ on the set G such that for any a and b in G one has a≥ b a-b≥0. Write a>b to mean that a≥ b a. It is shown in <cit.> that an Abelian group can be linearly ordered iff it is torsion free, that is, iff 0 is its only element of finite order. It is also known (see e.g. <cit.>) that any linearly ordered Abelian group can be embedded into the additive group ^I endowed with a lexicographical order, where I is a certain linearly ordered set and ^I is the set of all functions from I to  vanishing outside a well-ordered subset of I. Examples of linearly ordered groups are any linearly ordered rings and, in particular, any linearly ordered fields. 

So, the additive groups of the ordered fields  and ^* of real and hyperreal numbers are linearly ordered groups. Any subgroup of any linearly ordered group is a linearly ordered group, with the inherited order. The direct product G_1× G_2×⋯ of any linearly ordered groups G_1,G_2,… is a linearly ordered group with respect to the lexicographic order. 




In this group context, let us also extend the notion of a circuit matrix, by defining it as a matrix (c_ij)_i,j∈[n]∈ G^n× n such that for some c∈ G, some set J⊆[n], some cyclic permutation π of J, and all i,j in [n] we have c_ij=c if j=π(i)∈ J and c_ij=0 otherwise; let us denote this circuit matrix by C^J,π,c. Now we can state  


Let (G,+,0,≥) be a linearly ordered Abelian group. 
Then any nonnegative sum-symmetric matrix in G^n× n is the sum of nonnegative circuit matrices in G^n× n. 






For readers' convenience, let us give here 


of Theorem <ref>.  
Take any nonnegative sum-symmetric matrix T=(t_ij)_i,j∈[n]∈ G^n× n. If s_k(T)=0 for some k∈[n], then c_k(T)=s_k(T)=0, and so, all entries of the kth row and kth column of T are 0. Crossing out these row and column, we obtain a nonnegative sum-symmetric matrix in G^(n-1)×(n-1), and the proof can be easily completed by induction on n. 

So, without loss of generality 
s_i(T)>0 for all i∈[n], that is, for each i∈[n] there is some j∈[n] such that t_ij>0. Therefore, for any i_1∈[n] we have a sequence (i_1,i_2,…) in the set [n] such that t_i_,i_+1>0 for all natural . By the pigeonhole principle, there are natural k and ℓ with the property that k<ℓ and i_k=i_ℓ. Taking such k and ℓ with the smallest value of ℓ-k, we will have i_k,…,i_ℓ-1 be pairwise distinct. So, 
the condition π(i_)=i_+1 for =k,…,ℓ-1 will define a cyclic permutation π on the set J:={i_k,…,i_ℓ-1}. Then the matrix T̃:=T-C^J,π,t, where t:=⋀_=k^ℓ-1 t_i_,i_+1, will be nonnegative and sum-symmetric, and T̃ will have strictly fewer nonzero entries than T does. Now the proof can be easily completed by induction on the number of nonzero entries of the matrix. 


The case G= of Theorem <ref> complements the famous Birkhoff–von Neumann theorem, which states that every 
doubly stochastic matrix is a convex combination of permutation matrices. 
One can similarly extend the Birkhoff–von Neumann theorem to groups: 


Let (G,+,0,≥) be a linearly ordered Abelian group. 
Then any nonnegative matrix T∈ G^n× n with s_1(T)=⋯=s_n(T)=c_1(T)=⋯=c_n(T) is the sum of nonnegative circuit matrices in G^n× n of the form C^J,π,c with J=[n]. 


For a proof of Theorem <ref>, one may take, almost verbatim (cf. the above proof of Theorem <ref>), the proof of Theorem 5.1.9 in <cit.>, which is based on Ph. Hall's theorem on distinct representatives – see e.g. Theorem 5.1.1 in <cit.>; other proofs of Ph. Hall's theorem and its extensions can be found e.g. in <cit.> and <cit.>. 

In the rest of the paper, we shall only need Theorem <ref> when G is  or . 





§ OPTIMAL-SCORE PARTITIONS
 
Let k be a natural number. Let μ and ν be finite measures on a measurable space (X,) such that μ is absolutely continuous with respect to ν, with a Radon–Nikodym derivative f=dμ/dν. Let _k denote the set of all 
partitions P=(A_1,…,A_k) of X such that A_i∈ for all i∈[k]. 


Suppose that one of the following two conditions on the group G, the -algebra , and the measure ν holds: 

	
  *  G= and ν is non-atomic; 
	
  *  G=,  is the powerset 2^X of X, and ν is the counting measure (so that the set X is finite). 

Then 

    ∀ A∈  ∀ q∈ G∩[0,ν(A)]  ∃ B∈   B⊆ A  &  ν(B)=q.

Indeed, this is obvious when condition (II) holds. In the case when (I) holds, conclusion (<ref>) follows immediately from the well-known fact that the set of all values of a non-atomic finite measure is convex; see e.g. <cit.>. 

Fix any k-tuple 

    =(_1,…,_k)∈(G∩[0,∞))^k



such that 

    _1+…+_k=ν(X).



Consider 

    _ν,
    	:={P=(A_1,…,A_k)∈_kν(A_i)=_i  ∀ i∈[k]}.

In view of (<ref>), _ν,∅. 
Moreover, let us state 


There exists a partition Q=(B_1,…,B_k)∈_ν, such that for 
any i,j in [k] 

    sup_B_if≤inf_B_jf  whenever  
    	i<j;

recall here that sup∅=-∞ and inf∅=∞. 


Also, fix arbitrary real numbers s_1,…,s_k such that 

    s_1≤…≤ s_k

and define the “score” 

    s(P):=∑_i=1^k s_iμ(A_i)

of any partition P=(A_1,…,A_k)∈_ν,. 

Now we can state the main result of this note: 


For any partition Q as in Proposition <ref> and any partition P∈_ν,, we have s(Q)≥ s(P); that is, any partition Q as in Proposition <ref> has the highest possible score among all partitions in _ν,. 


Let us now prove the above statements. 

of Proposition <ref>.   
This will be done by induction on k. The case k=1 is trivial. By writing _1+…+_k=(_1+…+_k-1)+_k, we reduce the consideration to the case k=2, so that =(_1, _2)∈(G∩[0,∞))^2 and _1+_2=ν(X). 

Consider the (right-continuous) “distribution function” F of the function f with respect to the measure ν,  

defined by the formula

    F(t):=ν(f^-1([0,t]))=ν({x∈ X f(x)≤ t})

for t∈(-∞,∞], and let 

    s:=inf{t∈[0,∞] F(t)≥_1}∈[0,∞],  so that   F(s-)≤_1≤ F(s).



Next, let D:=f^-1({s}), and then  
let D_1 be any set in  such that 
D_1⊆ D and ν(D_1)=_1-F(s-); 
such a set D_1 exists by (<ref>), in view of the inequalities in (<ref>) and the equality ν(D)=F(s)-F(s-). 
Finally, let B_1:=f^-1([0,s))∪ D_1 and B_2:=X∖ B_1=f^-1((s,∞))∪(D∖ D_1). Then, obviously, (B_1,B_2)∈_2. Also, because D_1⊆ D=f^-1({s}), the sets f^-1([0,s)) and D_1 are disjoint and hence ν(B_1)=ν(f^-1([0,s)))+ν(D_1)=F(s-)+[_1-F(s-)]=_1, so that ν(B_2)=ν(X)-ν(B_1)=_2. Therefore, (B_1,B_2)∈_ν,. 
Moreover, B_1⊆ f^-1([0,s]) and B_2⊆ f^-1([s,∞)), so that sup_B_1f≤ s≤inf_B_2f, and thus (<ref>) holds, for k=2. 







































This completes the proof of Proposition <ref>. 



















of Theorem <ref>.   
Let Π:=⋃_J⊆[k]Π_J, where Π_J stands for the set of all permutations of the set J. Let :=Π×[k]×[k]. 



Take any partition Q as in Proposition <ref> and any partition P=(A_1,…,A_k)∈_ν,. Introduce C_i,j:=A_i∩ B_j for (i,j)∈[k]^2. A crucial observation is that the matrix (ν(C_i,j))_i,j∈[k] is nonnegative and sum-symmetric, and so, by Theorem <ref>, 

    ν(C_i,j)=∑_J⊆[k]∑_π∈Π_Jw_πj=π(i)∈ J

for all (i,j)∈[k]^2, 
where 
the w_π's are some 
numbers in G∩[0,∞). 
Therefore and in view of (<ref>), 
for each (i,j)∈[k]^2 there is a partition (C_π;i,j)_π∈Π of the set C_i,j such that 
for each triple (π,i,j)∈ we have 

C_π;i,j∈ and

    ν(C_π;i,j)=w_πj=π(i)∈ J,

where, for any given π∈Π, the set J⊆[k] is uniquely determined by the condition π∈Π_J. 


Hence, 

    ν(C_i,j)=∑_π∈Πν(C_π;i,j)   and  μ(C_i,j)=∑_π∈Πμ(C_π;i,j).
 
For each triple (π,i,j)∈, let  

    r_π;i,j:=
    	{2   μ(C_π;i,j)/ν(C_π;i,j)=1/ν(C_π;i,j)∫_C_π;i,jf dν        if  ν(C_π;i,j)0, 
       sup_B_j f
    	        otherwise,  
    	.

so that 

    μ(C_π;i,j)=r_π;i,j ν(C_π;i,j);

also, in view of the set inclusions C_π;i,j⊆ C_i,j⊆ B_j, we have inf_B_j f≤ r_π;i,j≤sup_B_j f. 


Therefore, in view of inequalities (<ref>), we now arrive at the second important point in this proof: that 

for all triples (π,i_1,j_1) and (π,i_2,j_2) in  we have the implication 

    j_1<j_2 r_π;i_1,j_1≤ r_π;i_2,j_2.



By (<ref>), (<ref>), (<ref>), 
and (<ref>), 

    s(P)=∑_i∈[k] s_iμ(A_i)
    	   =∑_i,j∈[k] s_iμ(C_i,j) 
       =∑_J⊆[k]∑_π∈Π_J∑_i,j∈[k] s_iμ(C_π;i,j) 
       =∑_J⊆[k]∑_π∈Π_J∑_i,j∈[k] s_i r_π;i,jν(C_π;i,j) 
       =∑_J⊆[k]∑_π∈Π_J∑_i,j∈[k] s_i r_π;i,jw_πj=π(i)∈ J
    
       	=∑_J⊆[k]∑_π∈Π_Jw_π∑_j∈ J s_π^-1(j)  r_π;π^-1(j),j.





Similarly to 
this, 
we have 

    s(Q)=∑_i∈[k] s_jμ(B_j)
    	   =∑_i,j∈[k] s_jμ(C_i,j) 
    
    
    
    
       	=∑_J⊆[k]∑_π∈Π_Jw_π∑_j∈ J s_j  r_π;π^-1(j),j,

with the only difference that s_i in ∑_i,j∈[k] s_iμ(C_i,j) and in the two subsequent expressions in multi-line display (<ref>) is now replaced by s_j. 

So, to compete the proof of Theorem <ref>, it suffices to show that 

    ∑_j∈ J s_j u_j≥∑_j∈ J s_(j) u_j

for any permutation ∈Π_J, where u_j:=r_π;π^-1(j),j. 
Since any permutation can be obtained from the identity permutation by finitely many inversions, it is enough to verify (<ref>) in the case when the cardinality of J is 1 or 2, so that J={j,m} for some j,m in [k]. Then  

(<ref>) can be rewritten as s_ju_j+s_mu_m≥ s_mu_j+s_ju_m or, equivalently, as (s_j-s_m)(u_j-u_m)≥0, which is true – because, by 
(<ref>) and (<ref>), s_j and u_j=r_π;π^-1(j),j are each nondecreasing in j∈ J. 



This concludes the proof of Theorem <ref>. 






§ OPTIMAL RESOURCE ALLOCATION
 
Theorem <ref>, appropriately interpreted, provides a solution to an 

optimal resource allocation (ORA) 
problem. 
For simplicity, let us state here this problem and its solution for the “discrete” setting, corresponding to alternative (<ref>) on page I. 
The ORA problem is as follows. 



	
  * Each member x of a finite set X is to be subjected to exactly one of k treatments, labeled by 1,…,k, with potencies s_1,…,s_k and available in quantities q_1,…,q_k, respectively. 
	
  * In accordance with condition (<ref>), we assume that the potencies s_1,…,s_k are real numbers such that s_1≤…≤ s_k; that is, the k treatments are enumerated according to their potencies, from the lowest to the highest.  Potencies are allowed to take negative values, corresponding to negative treatment effects.
	
  * 

	In this “discrete” setting, the available quantities q_1,…,q_k of treatments 1,…,k are nonnegative integers such that the total of the quantities q_1,…,q_k equals the number ν(X) of the members of the set X. 
	
  * For each member x of the set X, the effect of any treatment i∈[k] is proportional to the potency s_i of the treatment, with a proportionality coefficient f(x)∈[0,∞), so that the just mentioned effect is f(x)s_i. It is then natural to refer to f(x) as the responsiveness of member x to treatment. 
	
  * For each i∈[k], let A_i denote the set of all members x of the set X assigned to treatment i, so that P:=(A_1,…,A_k) is a partition of X. This partition represents a treatment allocation. In accordance with what has been said, we only consider “feasible” treatment allocations, that is, the ones satisfying the conditions ν(A_i)=_i for all i∈[k]; cf. (<ref>) (recall that here ν stands for the counting measure). 
Letting now 

    μ(A):=∫_A f dν=∑_x∈ Af(x)

for any set A⊆ X, we see that the overall effect of a treatment allocation P=(A_1,…,A_k) will then be  

    ∑_i∈[k]∑_x∈ A_if(x)s_i
    	=∑_i∈[k]s_iμ(A_i)=s(P),

in accordance with (<ref>). 

 
Now Theorem <ref> tells us that the overall effect s(P) of a treatment allocation P=(A_1,…,A_k) will be the largest possible if members of the set X with higher responsiveness are assigned to higher-potency treatments. More specifically, for the optimal treatment allocation, q_k members x of the set X with the highest values of responsiveness f(x) are selected to constitute the set A_k and thus to receive treatment k, of the highest-potency, s_k; then q_k-1 members of the remaining set X∖ A_k with the highest values of responsiveness are selected to constitute the set A_k-1 and thus to receive treatment k-1, of the second highest-potency, s_k-1; etc. 

While this 
solution to this ORA 

problem 
appears to agree with intuition, we saw that it takes some effort to prove it rigorously, by using the decomposition of nonnegative sum-symmetric matrices provided by Theorem <ref>.

Let us now provide a few possible specific interpretations of the general ORA setting described above:  


	
  * The set X may be a human population to be vaccinated against a certain disease. Here, the treatments 1,…,k correspond to k kinds of a vaccine, with potencies s_1,…,s_k. The total quantity of the available vaccine, q_1+…+q_k units, is the same as the population size, so that each member of the population be able to receive exactly one unit of the vaccine. For each individual x in the population, f(x) is the individual's responsiveness to vaccination. The goal here is to maximize the overall vaccination effect s(P). 
	
  * Here X is the set of workers of a certain specialty in an industrial company. 
Now the treatments 1,…,k correspond to k kinds of equipment, with efficiencies s_1,…,s_k. The total quantity of the equipment units, q_1+…+q_k, is the same as the size of the set X of workers, and each worker will be assigned to exactly one unit of the available equipment. For each worker x, f(x) is the worker's individual productivity coefficient. The goal here is to maximize the overall production s(P). 
	
  * Now X is a set of agricultural plots. The treatments 1,…,k correspond to k grades of a fertilizer, with efficiencies s_1,…,s_k. The total quantity of the fertilizer units, q_1+…+q_k, is the same as the the number of plots, and each plot will receive exactly one unit of a fertilizer. For each plot x, f(x) is the plot's responsiveness to fertilization. The goal here is to maximize the overall response s(P) to the fertilization. 
		
  * This is a “non-atomic” modification of the latter “discrete” scenario. Here X is the set of points on an agricultural field, and the measure ν of a (measurable) part A of X is c|A|, where c is a positive real number and |A| is the area of A. The treatments 1,…,k again correspond to k grades of a fertilizer, with efficiencies s_1,…,s_k. 
The field X is partitioned into parts A_1,…,A_k so that the part A_j receive the jth grade of the fertilizer, for each j=1,…,k. 		
The corresponding quantities q_1,…,q_k of the k grades of the fertilizer may now take any nonnegative real values such that 
the total quantity of the fertilizer, q_1+…+q_k, equals ν(X)=c|X| so that the entire field be covered by 
the fertilizer with the uniform density c per unit area.  
For each point x on the field, f(x) is the corresponding local responsiveness to fertilization. The goal here is, again, to maximize the overall response s(P) to the fertilization.


In all these specific scenarios, the maximum overall effect occurs when higher levels of responsiveness are coupled with higher potencies, as specified in the general conclusion. 



A search for articles containing the phrase “optimal resource allocation” in Google Scholar reveals about 35400 results. Optimal resource allocation (ORA) problems arise in a great variety of fields and a great variety of settings. A very small sample representing such problems includes ORA studies in 
biology <cit.>, 



computing <cit.>,  



economics <cit.>, 



electrical engineering <cit.>, 

health care <cit.>, 


information theory <cit.>, 




operations research <cit.>, 



risk analysis <cit.>, and 


transportation <cit.>. 


Kantorovich was apparently the first to consider ORA problems systematically; see e.g. <cit.> and <cit.>. 
Methods used in the work by Kantorovich and his great many followers are analytical, based on separation of convex sets, with the feasible solutions being points in a finite- or infinite-dimensional linear space. 

On the other hand, the main tool used in the present paper is
the decomposition of nonnegative sum-symmetric matrices into nonnegative circuit
matrices, provided by Theorem <ref>, whose 
proof is rather combinatorial, and the feasible solutions in our setting are partitions, rather than points in linear spaces over . 

It is hoped that the simple and rather general resource allocation model considered here, as well as the corresponding results, will be of use in a variety of specific applications. 











































spmpsci      





























