Perron eigenvectors and the symmetric transportation polytope

AbstractLet x and y be positive vectors in Rn. The set of all n × n nonnegative matrices having x and yT as their right and left Perron eigenvectors is a polyhedral convex cone. A cross section of this cone is the polytope P(x,y) consisting of all n × n nonnegative matrices C such that Cx=x and yTC=yT. The set of doubly stochastic matrices is obtained as a special case when x=y=(1,1,…,1)T. Our purpose is to investigate the structure of P(x,y) and especially its extreme points. This is done by transforming the problem into a symmetric transportation polytope, which contains all n × n nonnegative matrices having the same vector z as their row and column sum vector. Using graph-theoretic methods, we investigate the number of extreme points of this polytope. In particular we study vectors z that yield the maximum number of extreme points