The Extreme Points of the Convex Polytope of Doubly Substochastic Matrices with Fixed Row Sums and Column Sums

Event Name/Location

9th Shanghai Conference on Combinatorics, Shanghai, China, May 24-28, 2017

Presentation Date

5-27-2017

Document Type

Conference Proceeding

Presenters / Authors

Lei Cao, Georgian Court UniversityFollow
Richard Brualdi, University of Wisconsin-Madison

ORCID ID

0000-0001-7613-7191

ResearcherID

G-7341-2019

Description

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 Ω^s_n, Ω^hs_n 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 Ω^s_n , Ω^hs_n and Ω^π_n are sub-polytopes of Ω_n : The extreme points of Ω^s_n and Ω^hs_n 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.

NSUWorks Citation

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.
https://nsuworks.nova.edu/cnso_math_facpres/399