Extreme points of general transportation polytopes
Patrice Koehl

The Directed Landscape is a Black Noise
    [
    April 29, 2024
=======================================








Transportation matrices are m× n non-negative matrices whose row sums
and row columns are equal to, or dominated above with given integral vectors R and C.
Those matrices belong to a convex polytope whose extreme points have been previously characterized.
In this article, a more general set of non-negative transportation matrices is considered,
whose row sums are bounded by two integral non-negative vectors R_min and R_max and column sums
are bounded by two integral non-negative vectors C_min and C_max.
It is shown that this set is also a convex polytope whose extreme points are then fully characterized.










§ INTRODUCTION





Imagine that there are n agents that are assigned to perform m tasks, and assume that each agent can perform an integer number of tasks and each task can only be assigned to an integer number of agents.
A manager in charge of the assignment agent / task will consider the “cost" of assigning each agent to each task and will
design an “optimal assignment", namely an assignment that leads to a minimal overall cost.
Finding a solution to this seemingly simple practical problem has led to the development of a gem in the mathematics and statistics communities, namely the optimal transport (OT) problem.

A mathematical formulation of the problem is to consider two sets of points S_1 of size n (the agents) and S_2 of size m (the tasks).
Each point k in S_1 (resp S_2) is assigned a “mass" m_1(k), the amount of tasks it can perform (resp m_2(k), the number of agents needed to perform this task). 
The cost of an assignment between S_1 and S_2 is encoded as a non-negative matrix T=[T(i,j)] with i∈{1…,n} and j∈{1…,m}.
The OT problem can then be
formulated as finding a matrix G of correspondence between points in S_1 and points in S_2 that minimizes the total transport cost
 U defined as 
 
    U(G)= ∑_i=1^n∑_j=1^m T(i,j) G(i,j).
 
The minimum of U is to be found for the values of G(i,j) that satisfy the following constraints



    ∀ (i,j),    G(i,j) ≥ 0, 
       ∀ i,     ∑_j G(i,j) =m_1(i), 
       ∀ j,     ∑_i G(i,j) =m_2(j).

  
What makes the OT problem so interesting is that its solution includes two essential components.
First, it defines a distance between the distributions considered (m_1 and m_2). 
These distances have enabled statisticians and mathematicians to derive a geometric structure
on the space of probability distributions (<cit.>).
Second, it also provides the optimal transportation plan G between the distributions; this optimal plan defines a
registration, thereby enabling alignment between the distributions.
Applications of OT have exploded in the recent years, in domains such as applied mathematics, machine learning, computer vision, 
and linguistics (see <cit.>, among others).

The formulation defined above corresponds to the Monge-Kantorovich version of the optimal transport problem (<cit.>). 
A simplified version of the OT problem is to set the masses to 1 (i.e. each agent can only perform one task and each task is performed by one agent) and to assume
balance (same number of agents and tasks). The transportation matrix A then becomes integral (its values are integers) and satisfies the following constraints:



    ∀ (i,j),    A(i,j) ∈{0,1}, 
       ∀ i,     ∑_j A(i,j) = 1, 
       ∀ j,     ∑_i A(i,j) = 1.

  
This simplified problem that has its root in Monge's original transport problem <cit.> is itself a classical problem in combinatorial optimization referred to as the assignment problem or alternatively, using the language of graph theory, as the bipartite weighted matching problem (for a comprehensive analysis of assignment problems, see for example <cit.>).

Our focus in this paper is on the structures of the set of matrices that either satisfy the constraints <ref> or <ref>.
Those sets of matrices belong to so-called transportation polytopes that have been studied extensively in the literature (see for example, <cit.>).
In the special case n=m and m_1(i)=m_2(j) = 1   ∀ (i,j), the matrices G are doubly stochastic.
The set of all those matrices form a convex polytope Ω_n. Under the same conditions, the set of matrices A is the set of permutations P_n.
The set P_n is the set of extreme points of Ω_n; as such, any matrix G in Ω_n can be expressed as a linear combination of
permutation matrices in P_n:

 

(<cit.>) An n× n matrix G is doubly stochastic if and only if there is a finite set of permutations matrices P_1,…,P_N and corresponding non-negative real numbers α_1, …, α_N with α_1+…+α_N=1 such that A=α_1 P_1 + … + α_N P_N.


There are many proofs available for this theorem, referred to as the Birkhoff - von Neumann theorem; we only refer here to the original proofs <cit.>. This theorem has proved useful to establish convergence for algorithms developed to solve the assignment problem (see for example <cit.>.

The equations <ref> refer to a very specific balanced assignment problem.
There are, however many more types of assignment problems, usually referred to as unbalanced problems.
They consider a number of agents that differ from the number of tasks (using the example and terminology from above).
The most common formulation assigns a single agent to one task, leaving some agents and/or some task unmatched.
It is referred to in the literature as the k-cardinality assignment problem (<cit.>).
Some other formulations allow for multiple jobs to be assigned to the same agent to compensate
for the imbalance (when the number of tasks is bigger than the number of agents), with possibly additional constraints
such as each agent is allocated at least one task.
Transportation matrices for such problems belong to a more general class of transportation polytopes than the doubly stochastic matrices and doubly substochastic matrices.
In this paper, we propose to characterize those transportation polytopes.

We define these more general assignment problems as follows. The cost of transport between S_1 and S_2 is still encoded 
as a non-negative matrix T=[T(i,j)] with i∈{1…,n} and j∈{1…,m}.
The general assignment problem is formulated as finding a matrix G of correspondence between points in S_1 and points in S_2 that minimizes the total transport cost U = ∑_i=1^n∑_j=1^m T(i,j) G(i,j)
whose values G(i,j) satisfy the following constraints



    ∀ (i,j),      G(i,j) ∈{0,1}, 
       ∀ i,      r_i ≤∑_j G(i,j) ≤ R_i ,
       ∀ j,      c_j ≤∑_i G(i,j) ≤ C_j,

  
where r_i and R_i are given positive integers satisfying 0 ≤ r_i ≤ R_j and similarly c_j and C_j are given positive
integers satisfying 0 ≤ c_j ≤ C_j.
A relaxed version of these constraints is to replace equation <ref> with 0 ≤ G(i,j) ≤ 1, i.e. allowing G(i,j) to be fractional.
Finally, a possible additional constraint is to preset the total number of assignments between S_1 and S_2 to a given integer value k, i.e.
∑_i=1^n∑_j=1^m G(i,j) = k.
Possible solutions of the relaxed general assignment problem belong to sets of matrices that are defined below.


Let R_min = (r(1),…, r(n)), R_max = (R(1),…, R(n)), C_min = (c(1),…, c(m)), and C_max = (C(1),…, C(m)) be four
non-negative integral vectors satisfying

    ∀ i,      0 ≤ r(i) ≤ R(i),
       ∀ j,      0 ≤ c(j) ≤ C(j).

Let A be a non-negative matrix of size n× m and let us denote the row sum vector of A as RA and the column sum vector of A as CA.
Let us also define σ(A) to be the sum of all elements of A, i.e. σ(A) = ∑_i=1^n∑_j=1^m A(i,j).
The transportation polytope 𝒰(R_min^max,C_min^max) is the set of n× m matrices A that satisfy

    ∀ (i,j),      0 ≤ A(i,j) ≤ 1,
       ∀ i,      r(i) ≤ RA(i) ≤ R(i), 
       ∀ j,      c(j) ≤ CA(j) ≤ C(j) .

The transportation polytope 𝒰^k(R_min^max,C_min^max) is the set of n× m matrices A that satisfy

    𝒰^k(R_min^max,C_min^max) = { A ∈𝒰(R_min^max,C_min^max) |   σ(A) = k }.


Denote 𝒫(R_min^max,C_min^max) the set of all matrices in 𝒰(R_min^max,C_min^max) whose entries are either 0 or 1 with a similar definition for 𝒫^k(R_min^max,C_min^max) with respect to 𝒰^k(R_min^max,C_min^max).
We now state our main result.

 

The transportation polytopes 𝒰(R_min^max,C_min^max) and 𝒰^k(R_min^max,C_min^max) satisfy the following properties:


  a) 𝒰(R_min^max,C_min^max) is the convex hull of all matrices in 𝒫(R_min^max,C_min^max),

  b) 𝒰^k(R_min^max,C_min^max) is the convex hull of all matrices in 𝒫^k(R_min^max,C_min^max).





  
Remarks:


  i) If R_min=R_max=1_n, C_min=C_max=1_m (where 1_n and 1_m are vectors of one of size n and m, respectively), n=m=k, 𝒰^k(R_min^max,C_min^max)= Ω_n and 𝒫^k(R_min^max,C_min^max)= P_n and theorem <ref> is then equivalent to the Birkhoff-Von Neuman theorem for doubly stochastic matrices, theorem <ref>.

  ii) If R_min=0_n, C_min=0_m, R_max=1_n, C_max=1_m, 𝒰(R_min^max,C_min^max) is the set of doubly substochastic matrices, 𝒫(R_min^max,C_min^max) is the set of subpermutation matrices; a specific version of theorem <ref> was established (see for example <cit.>).

  iii) Similar to case ii), if R_min=0_n, C_min=0_m, R_max=1_n, C_max=1_m, 𝒰^k(R_min^max,C_min^max) is the set of doubly substochastic matrices with total sum k, and 𝒫(R_min^max,C_min^max) is the set of subpermutation matrices of rank k; a specific version of theorem <ref> was established by Mendelsohn and Dulmage for square matrices (<cit.>), and later by Brualdi and Lee for rectangular matrices (<cit.>).







§ A SIMPLE PROOF OF BIRKHOFF - VON NEUMANN THEOREM




As mentioned above, there are many proofs available for the Birkhoff - von Neumann theorem, some of which belong now  to textbooks. 
Here we describe a simple proof.
It is not original, but will serve as the basis for elements of the proof of theorem <ref>.

First, we note that it is straightforward to show that Ω_n is a non-empty compact convex set in ℝ^n× m 
and that any matrix in P_n is an extreme point of Ω_n. Since any non-empty compact convex set is the convex hull of its extreme points,
to finish the proof, we only need to show that any matrix A ∈Ω_n∖ P_n  is not an extreme point of Ω_n.

We prove first the following claim.

Let A ∈Ω_n. If a row or column of A contains a fractional value, then it contains at least two.



Let A(i,j) be a fractional value of A. Since

    ∑_k A(i,k) = 1,

there exists j_2 ∈ [1,n]∖{j} such that A(i,j_2) is fractional. Similarly, since

    ∑_k A(k,j) = 1,

there exists i_2 ∈ [1,n]∖{i} such that A(i_2,j) is fractional.


Let now A be a matrix in Ω_n∖ P_n. 
There exists a pair (i_1,j_1) such that A(i_1,j_1) is fractional.
Based on claim <ref>, there exists j_2 ∈ [1,n] with j_2  j_1 such that A(i_1,j_2) is non integral.
Similarly, we can find i_2 ∈ [1,n] with i_2  i_1 such that A(i_2,j_2) is fractional.
We can continue in this manner, leading to a path ( (i_1, j_1), (i_1 j_2), …) with fractional values in A. 
As n and m are finite, we will ultimately reach a pair that we have already visited. This means that we have identified a loop L among all edges between S_1 and S_2; the cardinality of this cycle is even (bipartite graph). We write this cycle as

    L = { (a_1, b_1), (a_2, b_2), …, (a_2M, b_2M)},

where 2M = |L|. 
We define the matrix N

    N(i,j)    = 0    (i,j) ∉ C 
    
    	N(a_2k,b_2k)    = 1    k∈{1,…, M}
    
    	N(a_2k-1,b_2k-1)    = -1    k∈{1,…, M}.

Let us now define

    ϵ_max = min{ A(a_1,b_1), …, A(a_2M, b_2M), 1 - A(a_1,b_1), …,1-A(a_2M, b_2M) }.

As all elements in the loop L are fractional, 0 < ϵ_max < 1. For ϵ∈ (0, ϵ_max], we define E_1 = A + ϵ N and E_2 = A - ϵ N.
As two consecutive pairs in L lead to the addition and subtraction of the same quantity ϵ on one row or one column of A, it is easy to verify 
that E_1 and E_2 are doubly stochastic and therefore belong to Ω_n.
Since A = 1/2(E_1+E_2), A is not an extreme point of Ω_n.






§ THE POLYTOPES 𝒰(R,C) AND 𝒰^K(R,C)




Let us start with the simple case for which R_min=R_max=R and C_min=C_max=C. We rewrite 𝒰(R_min^max,C_min^max) and 𝒰^k(R_min^max,C_min^max) as simply 𝒰(R,C) and 𝒰^k(R,C). Those polytopes have been studied extensively (see for example <cit.>).
We prove first the following lemma.

The polytope 𝒰(R,C) is non-empty if and only if ∑_i=1^n R(i) = ∑_j=1^m C(j). In addition,
𝒰^k(R,C) is non empty if and only if k = ∑_i=1^n R(i), in which case 𝒰^k(R,C) = 𝒰(R,C).


Let A be a matrix in 𝒰(R,C). Then,

    σ(A)    =   ∑_i=1^n∑_j=1^m A(i,j) = ∑_i=1^n( ∑_j=1^m A(i,j) ) = ∑_i=1^n R(i) 
       =   ∑_j=1^m( ∑_i=1^n A(i,j) ) = ∑_j=1^m C(j).

Therefore, ∑_i=1^n R(i) = ∑_j=1^m C(j). Conversely, if S=∑_i=1^n R(i) = ∑_j=1^m C(j), it is straightforward
to build a matrix A that belongs to 𝒰(R,C) (for example A=1/S RC^T).

Let A be a matrix in 𝒰^k(R,C). By definition, k=σ(A). Since 𝒰^k(R,C) ⊂𝒰(R,C), we get k=∑_i=1^n R(i).
In addition, let A be a matrix in 𝒰(R,C). Then σ(A)=∑_i=1^n R(i) = k, therefore A ∈𝒰^k(R,C). 


In the case considered here, theorem <ref> is reduced to the following lemma:


The transportation polytopes 𝒰(R,C) and 𝒰^k(R,C) satisfy the following properties:


  a) 𝒰(R,C) is the convex hull of all matrices in 𝒫(R,C),

  b) 𝒰^k(R,C) is the convex hull of all matrices in 𝒫^k(R,C).


The proof of property a) of lemma <ref> is similar to the simple proof provided above for the Birkhoff - von Neumann theorem, once we replace claim <ref> with the following claim:

Let A ∈𝒰(R,C). If a row or column of A contains a fractional value, then it contains at least two.



Let A(i,j) be a fractional value of A. Since

    ∑_k A(i,k) = R(i)

and R(i) is a non-negative integer, necessarily R(i)  0 and there exists j_2 ∈ [1,n]∖{j} such that A(i,j_2) is fractional. Similarly, since

    ∑_k A(k,j) = C(j)

and C(j) is a non-negative integer, necessarily C(j)  0 there exists i_2 ∈ [1,n]∖{i} such that A(i_2,j) is fractional.


The proof of part b) requires in addition that the matrices E_1 and E_2 built from the matrix A in 𝒰^k(R,C) also belong to 𝒰^k(R,C). This is a direct consequence of the fact that the loop identified in the matrix A has en even number of elements. As such  the matrix N defined in equation <ref> satisfies σ(N)=0, and therefore σ(E_1)=σ(E_2)=σ(A)=k, i.e. E_1 and E_2 belong to 𝒰^k(R,C).





§ THE POLYTOPE 𝒰(R_MIN^MAX,C_MIN^MAX)




We start with the following lemma:

 𝒰(R_min^max,C_min^max) is convex.
 
 
 
 The proof of lemma <ref> is relatively straightforward. We provide it here for sake of completeness.
Let A and B be two matrices belonging to 𝒰(R_min^max,C_min^max), α a real number in [0,1], and E = α A + (1-α) B. 
We have:

    E(i,j) = α A(i,j) + (1-α) B(i,j).

As both A(i,j) and B(i,j) belong to [0,1] and [0,1] is convex, E(i,j) ∈ [0,1]. Also, for i ∈ [1,n],

    ∑_j=1^m E(i,j) = α∑_j=1^m A(i,j) + (1-α) ∑_j=1^n B(i,j).

 As ∑_j=1^m A(i,j) and ∑_j=1^m B(i,j) belong to [r(i), R(i)] and this interval is convex,  ∑_j=1^n E(i,j) ∈[r(i), R(i)]. This is true for all i ∈[1, n].
 
 Similarly, 
 
    ∑_i=1^n E(i,j) = α∑_i=1^n A(i,j) + (1-α) ∑_1=1^n B(i,j).

As ∑_i=1^n A(i,j) and ∑_i=1^n B(i,j) belong to [c(j),C(j)] and this interval is convex,  ∑_i=1^n E(i,j) ∈ [c(j),C(j)]. This is true for all j ∈[1, m].
  
 Therefore, α A + (1-α) B belongs to 𝒰(R_min^max,C_min^max) and this set is convex.
 
 

 If A belongs to 𝒫(R_min^max,C_min^max), then A is an extreme point of 𝒰(R_min^max,C_min^max).
 
 
 
 Again, the proof of lemma <ref> is relatively straightforward. We provide it here for sake of completeness.
 Let A be a matrix of 𝒫(R_min^max,C_min^max) and let us suppose that A = 1/2(E+F) where E and F are two distinct matrices in 𝒰(R_min^max,C_min^max). 
 
 For any entry A(i,j)=0, we have:
 
    1/2( E(i,j) + F(i,j)) = 0.

 Since E(i,j)≥ 0 and F(i,j)≥ 0, we have E(i,j)=F(i,j)=0.
 
 For any entry A(i,j)=1, we have:
  
    1/2( E(i,j) + F(i,j)) = 1,

 i.e.,
   
    E(i,j) + F(i,j) = 2.

Since 0≤ E(i,j)≤ 1 and 0≤ F(i,j)≤ 1, we have E(i,j)=F(i,j)=1.

Therefore, A=E=F, which is in contradiction with the hypothesis that E and F are distinct. Therefore, A is not the midpoint of a line segment whose endpoints are in 
𝒰(R_min^max,C_min^max), and so A is an extreme point of 𝒰(R_min^max,C_min^max).


Finally, we prove the following lemma:

If a matrix A is an extreme point of 𝒰(R_min^max,C_min^max) then it belongs to 𝒫(R_min^max,C_min^max).
 
 
 
 We use a proof by contrapositive, loosely inspired by the proof in <cit.> for doubly substochastic matrices. Let A be a matrix in 𝒰(R_min^max,C_min^max). 
 
 We start with some definitions. An entry in A  being neither 0 nor 1 is called a fractional entry, and a row (resp. column) containing at least one fractional entry is called a fractional row (resp. column). 
 A fractional line is either a fractional row or a fractional column. 
 
 As A ∈𝒰(R_min^max,C_min^max) ∖𝒫(R_min^max,C_min^max), 
it has at least one fractional entry and therefore one fractional line. We consider two cases.


  Case 1) All fractional lines include at least two fractional values.

The proof is then very similar to the simple proof provided above for the Birkhoff - von Neumann theorem, with no need for claim <ref>.
This means that we can find a loop L within A whose cardinality  is even (bipartite graph). As before, we write this cycle as

    L = { (a_1, b_1), (a_2, b_2), …, (a_2M, b_2M)},

where 2M = |L|. 
We then define the matrix N

    N(i,j)    = 0    (i,j) ∉ C 
    
    	N(a_2k,b_2k)    = 1    k∈{1,…, M}
    
    	N(a_2k-1,b_2k-1)    = -1    k∈{1,…, M}.

We also define

    ϵ_max = min{ A(a_1,b_1), …, A(a_2M, b_2M), 1 - A(a_1,b_1), …,1-A(a_2M, b_2M) }.

As all elements in the loop L are fractional, 0 < ϵ_max < 1. For ϵ∈ (0, ϵ_max], we define E_1 = A + ϵ N and E_2 = A - ϵ N.
As two consecutive pairs in L leads to the addition and subtraction of the same quantity ϵ on one row or one column, it is easy to verify 
that the row sums and column sums of E_1 and E_2 are equal to the row sums and row columns A, and therefore E_1 and E_2 belong to 𝒰(R_min^max,C_min^max).
Since A = 1/2(E_1+E_2), A is not an extreme point of 𝒰(R_min^max,C_min^max).


  Case 2) There exists at least one fractional line that includes a single fractional value.

Let us assume that one such fractional line is a column j_1 (the proof would be the same if it were a row) and let  A(i_1,j_1) be the only fractional value on j_1. If row i_1 only contains one fractional value, we terminate. Otherwise i_1 includes at least two fractional values and therefore we can find j_2 j_1 such that A(i_1,j_2) is fractional. We continue in this manner, until either (a) we have reached a pair that we have already visited,  or (b) we have reached a line that only contains one fractional value. If we are in case (a), we have identified a loop of fractional values whose cardinality is even and the proof is then similar to Case 1. If we are in case (b), we have identified an incomplete loop, i.e. a cycle. If the cycle ends because the following column had a single fractional entry, the cardinality of the cycle is even, and we can again follow exactly the proof from Case 1. Otherwise, the cycle has an odd number of elements; we write it as

    C = { (i_1, j_1), (i_2, j_2), …, (i_2K-1, j_2K-1)},

where 2K-1 = |C|. We define the matrix N as:

    N(i,j)    = 0    (i,j) ∉ C 
    
                            N(i_2k,j_2k)     = 1      k∈{1,…, K-1}
    
                            N(i_2k-1,j_2k-1)     = -1      k∈{1,…, K} .

Let ϵ_max=min{ A(i_1,j_1), …, A(i_2K-1,j_2K-1), 1-A(i_1,j_1), …, 1-A(i_2K-1,j_2K-1)}. Since all the values A(i,j) when (i,j)∈ C are fractional, 0 < ϵ_max <1.

Let us define E_1(ϵ)=A+ϵ N and E_2(ϵ)=A-ϵ N. 
If 0 < ϵ < ϵ_max, all values in E_1(ϵ) and E_2(ϵ) are in the interval [0,1]. In addition, by construction, any line sum of E_1(ϵ) and E_2(ϵ) is equal to 
the sum of the same line of A, with the exception of column j_1 and row i_2K-1 . Those two lines, however, include a single fractional value. As such, the column sum CA(j_1)  and the row sum RA(i_2K-1) in A are fractional. Since the bounds on those row / column are integer values, 

    r(i_2K-1)     < RA(i_2K-1) < R(i_2K-1), 
    
     c(j_1)     < CA(j_1) < C(j_1),

and it is possible to modify the values of  A(i_1, j_1) and A(i_2K-1, j_2K-1) without compromising the constraints on the corresponding column and row, respectively. Let us define ϵ_2 = min{CA(j_1)-c(j_1), RA(i_2K-1)-r(i_2K-1), C(j_1)-CA(j_1), R(i_2K-1)-RA(i_2K-1)}; note the ϵ_2 is strictly fractional, i.e. 0 < ϵ_2 < 1.
 If we set  ϵ such that 0 < ϵ < min(ϵ_max, ϵ_2), then E_1(ϵ) and E_2(ϵ) belong to 𝒰(R_min^max,C_min^max). Since A = 1/2(E_1(ϵ)+E_2(ϵ)), A is not an extreme point of 𝒰(R_min^max,C_min^max).
 
 
Note that there are no other cases, as any such case would imply that the matrix A does not contain any fractional line, and therefore would belong to  𝒫(R_min^max,C_min^max). This concludes the proof of lemma <ref>.



The proof of theorem <ref> a)  is then directly the consequence of lemma <ref>, <ref>, and <ref>.






§ THE POLYTOPE 𝒰^K(R_MIN^MAX,C_MIN^MAX)



The set of matrices 𝒰^k(R_min^max,C_min^max) is the subset of the polytope 𝒰(R_min^max,C_min^max),
whose members A satisfy the additional constraint that the total sum of  their elements, σ(A) is set to a given positive integer value k. Note that this
set is non empty only if 0 < k ≤∑_i=1^n R(i) and k ≤∑_j=1^n C(j). Here we show that 𝒰^k(R_min^max,C_min^max) forms a convex polytope whose extreme values are the matrices in 𝒫^k(R_min^max,C_min^max) using the same strategy we used for 𝒰(R_min^max,C_min^max).


 𝒰^k(R_min^max,C_min^max) is convex.
 
 

The proof  is straight forward. Briefly, let A and B be two matrices belonging to 𝒰^k(R_min^max,C_min^max), α a real number in [0,1], and E = α A + (1-α) B.  To prove that E ∈𝒰^k(R_min^max,C_min^max), we need to show that:


  1) E(i,j) ∈ [0,1]: this comes from the convexity of [0,1] (see proof of lemma <ref>).

  2) r(i) ≤∑_j=1^m E(i,j) ≤ R(i) for all i∈ [1,n]: this comes from the convexity of [r(i),R(i)] (see proof of lemma <ref>).

  3) c(j) ≤∑_i=1^n E(i,j) ≤ C(j) for all j∈ [1,m]: this comes from the convexity of [c(j),C(j)] (see proof of lemma <ref>).

  4) σ(E) = ∑_i=1^n∑_j=1^m E(i,j) = k: this comes from the linearity of the operator σ.




 If A belongs to 𝒫^k(R_min^max,C_min^max), then A is an extreme point of 𝒰^k(R_min^max,C_min^max).
 
 
 
 Again, the proof of lemma <ref> is straightforward and identical to the proof of lemma <ref>.
 
 
 Finally, we prove:
 
If a matrix A is an extreme point of 𝒰^k(R_min^max,C_min^max) then it belongs to 𝒫^k(R_min^max,C_min^max).
 
 
 
 We use a proof by contrapositive with similar ideas as those used for the equivalent proof for lemma <ref>. Let A ∈𝒰^k(R_min^max,C_min^max) ∖𝒫^k(R_min^max,C_min^max). As such, it has at least one fractional entry and therefore one fractional line. We consider two cases.


  Case 1) All fractional lines include at least two fractional values.
The proof is then equivalent to the proof of Case 1 for lemma <ref>.


   Case 2) There exists at least one fractional line that includes a single fractional value.

Let us assume that one such fractional line is a column j_1 (the proof would be the same if it were a row) and let  A(i_1,j_1) be the only fractional value on j_1. Just like in Case 2 of lemma <ref>, we proceed from this value to generate a cycle of fractional values. If the cardinality of this cycle is even, we are done. A problem arises, however, if the cardinality of the cycle is odd:

    C = { (i_1, j_1), (i_2, j_2), …, (i_2K-1, j_2K-1)},

where 2K-1 = |C|. We could still define the matrix N as:

    N(i,j)    = 0    (i,j) ∉ C 
    
                            N(i_2k,j_2k)     = 1      k∈{1,…, K-1}
    
                            N(i_2k-1,j_2k-1)     = -1      k∈{1,…, K} .

However, if we define E_1(ϵ)=A+ϵ N and E_2(ϵ)=A-ϵ N, even with an ϵ small enough, we have σ(E_1(ϵ))=σ(A) -ϵ and σ(E_2(ϵ))=σ(A)+ϵ, i.e. E_1(ϵ) and E_2(ϵ) do not belong to 𝒰^k(R_min^max,C_min^max).

To address this issue, let us first define that a row i (resp. a column j) is mutable if and only if r(i) < RA(i) < R(i) (resp.  c(j) < CA(j) < C(j)) where RA(i) is the sum of the elements of row i and CA(j) is the sum of the elements of column j.
In other word, a row or column is mutable if it is possible to add or remove a well chosen small non-zero value to one of its elements without violating the constraints on its sum.
For example, the column j_1 of A defined above is mutable: it contains a single fractional value, hence CA(j_1) is fractional and therefore satisfies the definition of mutable.
We now make the following claim:

If the matrix A contains one mutable column, then it contains at least 2 mutable columns.



Let l be a mutable column of A. 
if all other columns j of A were non mutable, then their column sums CA(j) would all be integer values, and σ(A)=CA(l) + ∑_j=1, j l^mCA(j) would then be fractional, which is a contradiction with the fact that σ(A)=k. Therefore, there exists a least another column of A that is mutable.


Based on claim <ref>, as j_1 is mutable, there exists another column j_2  j_1 that is mutable. We consider then two cases:


  a) The cycle C include j_2. 

We truncate the cycle to the first vertex that belongs to the column j_2. This truncated cycle, C', includes an even number of vertices.
We can then conclude as in Case 1 by considering this cycle.


  b) The cycle C does not include j_2. 

Let  A(i_2,j_2) be a fractional value on j_2. We build a second cycle D in A starting from this value. If the cardinality of this cycle is even, we can follow exactly the proof from Case 1. Otherwise, the cycle has an odd number of elements; we write it as

    D = { (i'_1, j'_1), (i'_2, j'_2), …, (i'_2M-1, j'_2M-1)},

where 2M-1 = |D|. We define the matrix N' as:

    N'(i,j)    = 0    (i,j) ∉ C 
    
                            N'(i_2k,j_2k)     = -1      k∈{1,…, M-1}
    
                            N'(i_2k-1,j_2k-1)     = 1      k∈{1,…, M} .

For ϵ small enough (i.e. smaller than the characteristic ϵ for the two cycles),  we define E_1(ϵ)=A+ϵ N + ϵ N' and E_2(ϵ)=A-ϵ N - ϵ N' where the matrix N was previously defined in equation <ref>. 
With the right choice of ϵ, All values in E_1(ϵ) and E_2(ϵ) are in the interval [0,1]. In addition, by construction, any row/column sum of E_1(ϵ) and E_1(ϵ) are equal to 
to that of A, with the exception of columns j_1, j'_1 and rows i_2K-1, , and i'_2M-1. Those four lines, however, are mutable: as j_1, i_2K-1, and i'_2M-1 contain a single fractional value, there are mutable, and j'_1=j_2 was chosen as it is mutable.  The constraints on the sums of all rows and columns of E_1(ϵ) and E_2(ϵ) are therefore satisfied. In addition, 

    σ(E_1(ϵ))   =   σ(A) + ϵσN + ϵσ(N') 
       =    k + ϵ (1 × (K-1) + (-1) × K) + ϵ ( -1 × (M-1) + 1 × M) 
       =    k - ϵ + ϵ = k, 
    σ(E_2(ϵ))   =   σ(A) - ϵσN - ϵσ(N') 
       =   k - ϵ (1 × (K-1) + (-1) × K) - ϵ ( -1 × (M-1) + 1 × M) 
       =   k + ϵ - ϵ = k.

Therefore, E_1(ϵ) and E_2(ϵ) belong to 𝒰^k(R_min^max,C_min^max. Since A = 1/2(E_1(ϵ)+E_2(ϵ)), A is not an extreme point of 𝒰^k(R_min^max,C_min^max).


 
This concludes the proof of lemma <ref>.



The proof of theorem <ref> b)  is then just the consequence of lemma <ref>, <ref>, and <ref>.






Acknowledgment. 


The work discussed here originated from a visit by P.K. at the Institut de Physique Théorique, CEA Saclay, France, during the fall of 2022. He thanks them for their hospitality and financial support.





§ REFERENCES










32


urlstyle

[Villani(2008)]Villani:2008
Cédric Villani.
Optimal Transport: Old and New.
Grundlehren der mathematischen Wissenschaften. Springer, 2008.

[Peyré and Cuturi(2018)]Peyre:2018
Gabriel Peyré and Marco Cuturi.
Computational optimal transport.
arXiv e-prints, art. arXiv:1803.00567, 2018.

[Cotar et al.(2013)Cotar, Friesecke, and Klüppelberg]Cotar:2013
Codina Cotar, Gero Friesecke, and Claudia Klüppelberg.
Density functional theory and optimal transportation with coulomb
  cost.
Communications on Pure and Applied Mathematics, 66:0
  548–599, 2013.

[Santambrogio(2015)]Santambrogio:2015
F. Santambrogio.
Optimal Transport for applied mathematicians.
progress in nonlinear differential equations and their applications.
  Springer, 2015.

[Kantorovich(1942)]Kantorovich:1942
L. Kantorovich.
On the transfer of masses.
Dokl. Acad. Nauk. USSR, 37:0 7–8, 1942.

[Monge(1781)]Monge:1781
G. Monge.
Mémoire sur la théorie des déblais et des remblais.
Histoire de l'Académie Royale des Sciences et Mémoires
  de Mathématique et de Physique tirés des registres de cette
  Académie, 1784:0 666–704, 1781.

[Burkard et al.(2009)Burkard, Dell'Amico, and Martello]Burkard:2009
R. Burkard, M. Dell'Amico, and S. Martello.
Assignment problems.
Society for Industrial and Applied Mathematics (SIAM),
  Philadelphia, PA, United States, 2009.

[Birkhoff(1946)]Birkhoff:1946
Garrett Birkhoff.
Tres observaciones sobre el algebra lineal.
Univ. Nac. Tucuman, Ser. A, pages 147–154, 1946.

[Brualdi and Gibson(1976)]Brualdi:1976
Richard A Brualdi and Peter M Gibson.
Convex polyhedra of doubly stochastic matrices—iv.
Linear Algebra and Its Applications, 15:0 153–172,
  1976.

[Brualdi(1980)]Brualdi:1980
Richard A Brualdi.
Matrices of zeros and ones with fixed row and column sum vectors.
Linear algebra and its applications, 33:0 159–231,
  1980.

[Muchlis(1992)]Muchlis:1992
Ahmad Muchlis.
On the extremal points of a class of polytopes of matrices.
Linear algebra and its applications, 162:0 369–383,
  1992.

[Gill and Linusson(2009)]Gill:2009
Jonna Gill and Svante Linusson.
The k-assignment polytope.
Discrete Optimization, 6:0 148–161, 2009.

[Ziegler(2012)]Ziegler:2012
Günter M Ziegler.
Lectures on polytopes, volume 152.
Springer Science & Business Media, 2012.

[De Loera and Kim(2013)]Loera:2013
Jesús A De Loera and Edward D Kim.
Combinatorics and geometry of transportation polytopes: An update.
Discrete geometry and algebraic combinatorics, 625:0
  37–76, 2013.

[Cao and Chen(2019)]Cao:2019
Lei Cao and Zhi Chen.
Partitions of the polytope of doubly substochastic matrices.
Linear Algebra and its Applications, 563:0 98–122,
  2019.

[Chen et al.(2021)Chen, Zhu, Li, Yang, and Cao]Chen:2021
Zhi Chen, Zelin Zhu, Jiawei Li, Lizhen Yang, and Lei Cao.
Extreme points of certain transportation polytopes with fixed total
  sums.
The Electronic Journal of Linear Algebra, 37:0
  256–271, 2021.

[Von Neumann(1953)]Neumann:1953
John Von Neumann.
A certain zero-sum two-person game equivalent to the optimal
  assignment problem.
Contributions to the Theory of Games, 2:0 5–12, 1953.

[Kosowsky and Yuille(1994)]Kosowsky:1994
J. Kosowsky and A. Yuille.
The invisible hand algorithm: Solving the assignment problem with
  statistical physics.
Neural Networks, 7:0 477–490, 1994.

[Koehl and Orland(2021)]Koehl:2021b
P. Koehl and H. Orland.
Fast computation of exact solutions of generic and degenerate
  assignment problems.
Phys. Rev. E, 103:0 042101, 2021.

[Dell'Amico and Martello(1997)]Dell:1997
Mauro Dell'Amico and Silvano Martello.
The k-cardinality assignment problem.
Discrete Appl. Math., 76:0 103–121, 1997.

[Mirsky(1959)]Mirsky:1959
L. Mirsky.
On a convex set of matrices.
Archiv der Mathematik, 10:0 88–92, 1959.

[Čihák(1970)]Cihak:1970
Pavel Čihák.
Remarks on doubly substochastic rectangular matrices.
Commentationes Mathematicae Universitatis Carolinae,
  110 (2):0 385–391, 1970.

[Mendelsohn and Dulmage(1958)]Mendelsohn:1958
Nathan S Mendelsohn and A Lloyd Dulmage.
The convex hull of sub-permutation matrices.
Proceedings of the American Mathematical Society, 9:0
  253–254, 1958.

[Brualdi and Lee(1978)]Brualdi:1978
Richard A Brualdi and Geoffrey M Lee.
On the truncated assignment polytope.
Linear Algebra and its Applications, 19:0 33–62,
  1978.

[Jurkat and Ryser(1967)]Jurkat:1967
WB Jurkat and HJ Ryser.
Term ranks and permanents of nonnegative matrices.
Journal of Algebra, 5:0 342–357, 1967.

[Rothblum and Schneider(1989)]Rothblum:1989
Uriel G Rothblum and Hans Schneider.
Scalings of matrices which have prespecified row sums and column sums
  via optimization.
Linear Algebra and its Applications, 114:0 737–764,
  1989.

[Brualdi and Hwang(2005)]Brualdi:2005
Richard Brualdi and Suk-Geun Hwang.
A bruhat order for the class of (0, 1)-matrices with row sum vector r
  and column sum vector s.
The Electronic Journal of Linear Algebra, 12:0 6–16,
  2005.

[daFonseca and Mamede(2009)]Fonseca:2009
Carlos M daFonseca and Ricardo Mamede.
On (0, 1)-matrices with prescribed row and column sum vectors.
Discrete mathematics, 309:0 2519–2527, 2009.

[Brualdi(2006)]Brualdi:2006
Richard A Brualdi.
Algorithms for constructing (0, 1)-matrices with prescribed row and
  column sum vectors.
Discrete Mathematics, 306:0 3054–3062, 2006.

[Cavenagh(2013)]Cavenagh:2013
Nicholas J Cavenagh.
Defining sets and critical sets in (0, 1)-matrices.
Journal of Combinatorial Designs, 21:0 253–266, 2013.

[Chen et al.(2016)Chen, Mo, Qiu, and Varaiya]Chen:2016
Wei Chen, Yanfang Mo, Li Qiu, and Pravin Varaiya.
Constrained (0, 1)-matrix completion with a staircase of fixed zeros.
Linear Algebra and its Applications, 510:0 171–185,
  2016.

[Deng(2019)]Deng:2019
Lei Deng.
Convex set of doubly substochastic matrices.
In 2019 Ninth International Workshop on Signal Design and its
  Applications in Communications (IWSDA), pages 1–4. IEEE, 2019.



