Extremal Doubly Stochastic Measures and Optimal Transportation

Robert McCann, University of Toronto`

Abstract. Square N by N matrices with non-negative entries whose columns and rows all sum to one form a convex set with N! vertices. Each vertex corresponds to a permutation on N letters, according to a theorem of Birkhoff and von Neumann. In 1948 Birkhoff asked what the infinite dimensional analogue of this theorem should be. We resolve this problem by giving a condition on the support of a measure on the square which characterizes extremality among non-negative measures with the same x- and y-marginal projections. Our condition is used to derive a new sufficient condition for uniqueness of the minimizer in Kantorovich's optimal transportation problem in terms of the topology of the transportation cost.