Enumerating extreme points of the polytopes of stochastic tensors: an optimization approach

ABSTRACT

This paper is concerned with the extreme points of the polytopes of stochastic tensors. By a tensor we mean a multi-dimensional array over the real number field. A line-stochastic tensor is a nonnegative tensor in which the sum of all entries on each line (i.e. one free index) is equal to 1; a plane-stochastic tensor is a nonnegative tensor in which the sum of all entries on each plane (i.e. two free indices) is equal to 1. In enumerating extreme points of the polytopes of line- and plane-stochastic tensors of order 3 and dimension n, we consider the approach by linear optimization and present new lower and upper bounds. We also study the coefficient matrices that define the polytopes.

KEYWORDS:

• Birkhoff polytope
• Birkhoff-von Neumann theorem
• extreme point
• line-stochastic tensor
• plane-stochastic tensor
• polytope
• tensor
• vertex

AMS CLASSIFICATIONS:

• Primary 52B11
• 15B51

Acknowledgments

The authors thank the anonymous referee for suggestion and Chi-Kwong Li for his comments in the early stage of the project. Fuzhen Zhang thanks the SKKU Applied Algebra & Optimization Research Center of South Korea for the hospitality during the May 2017 Workshop on Matrix/Operator Theory.

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Funding

Fuzhen Zhang's work was partially supported by an NSU PFRDG Research Scholar grant and by National Natural Science Foundation of China (NNSF) No. 11571220 via Shanghai University. Xiao-Dong Zhang's work was partially supported by NNSF No. 11531001, No. 11271256, NSFC-ISF Research Program (No. 11561141001) and the Montenegrin-Chinese Science and Technology Cooperation Project (No. 3-12).