Mathematics Faculty Articles

The extreme points of centrosymmetric transportation polytopes

Document Type

Article

Publication Date

1-1-2021

Publication Title

Linear Algebra and Its Applications

Keywords

Centrosymmetric matrices, Doubly stochastic matrices, Transportation polytopes

ISSN

00243795

Volume

608

First Page

214

Last Page

235

Abstract

Denote by Uπ(R,S) the convex set of nonnegative centrosymmetric matrices with given row sum vector R and column sum vector S, and denote by U≤π(R,S) the convex set of nonnegative centrosymmetric matrices with the row sum vector componentwisely dominated by R and the column sum vector componentwisely dominated by S respectively. We characterize all extreme points of Uπ(R,S) and U≤π(R,S). In addition, we show that the extreme points of Ωnπ, the polytope of all n×n centrosymmetric doubly stochastic matrices, and the extreme points of ωnπ, the polytope of all n×n centrosymmetric doubly substochastic matrices, can be obtained by letting R=S=(1,1,…,1) in Uπ(R,S) and U≤π(R,S) respectively.

ORCID ID

0000-0001-7613-7191

ResearcherID

G-7341-2019

DOI

10.1016/j.laa.2020.08.029

Link to Full Text

Share

COinS