Israel Journal of Mathematics General Mathematics

Support of extremal doubly stochastic arrays

Mark Mordechai Etkind, Nir Lev
Springer Nature · 2025-02-17 · DOI 10.1007/s11856-025-2722-5

Abstract

Abstract An n × m array with nonnegative entries is called doubly stochastic if the sum of its entries at each row is m and at each column is n . The set of all n × m doubly stochastic arrays is a convex polytope with finitely many extremal points. The main result of this paper characterizes the possible sizes of the supports of all extremal n × m doubly stochastic arrays. In particular we prove that the minimal size of the support of an n × m doubly stochastic array is n + m − gcd( n , m ). Moreover, for m = kn + 1 we also characterize the structure of the support of the extremal arrays.

Read at publisher →