The Extreme Points of the Convex Polytope of Doubly Substochastic Matrices with Fixed Row Sums and Column Sums
9th Shanghai Conference on Combinatorics, Shanghai, China, May 24-28, 2017
Let Ωn be the set all of n × n doubly stochastic matrices. It is well-known that Ωn is a polytope whose extreme points are the n × n permutation matrices. Let Ωsn, Ωhsn and Ωπn,denote the sets of symmetric doubly stochastic matrices, Hankel symmetric doubly stochastic matrices and centrosymmetric doubly stochastic matrices respectively. It is clear that Ωsn , Ωhsn and Ωπn are sub-polytopes of Ωn : The extreme points of Ωsn and Ωhsn were discovered, while the extreme points of Ωπn were not characterized completely. We determine all the extreme points and give characterizations of the permutation matrices which generated the extreme points.
Cao, Lei and Brualdi, Richard, "The Extreme Points of the Convex Polytope of Doubly Substochastic Matrices with Fixed Row Sums and Column Sums" (2017). Mathematics Faculty Proceedings, Presentations, Speeches, Lectures. 399.