Enumeration and constructions of vertices of the polytope of polystochastic matrices

Abstract

A multidimensional nonnegative matrix is called polystochastic if the sum of entries in each of its lines equals $1$. The set of all polystochastic matrices of order $n$ and dimension $d$ is a convex polytope ${\Omega }_n^d$ known as the Birkhoff polytope. In this paper, we identify all vertices of the polytopes ${\Omega }_4^3$ and ${\Omega }_3^4$ correcting the results of Ke, Li, and Xiao (2016). Additionally, we describe constructions vertices of ${\Omega }_n^d$ using multidimensional matrix products and find symmetric vertices of ${\Omega }_3^d$ for all $d\ge 4$ with large support sizes.

This is a massive upgrade of ArXiv:2311.06905 extended by enumeration of vertices of ${\Omega }_4^3$ and a direct construction of vertices of ${\Omega }_3^d$. Submitted for publication