GENERALIZED TRANSITIVE TOURNAMENTS AND DOUBLY STOCHASTIC MATRICES

We show that a doubly stochastic matrix is a convex combination of nonidentity permutation matrices if and only if it can be written as the sum of a nonnegative matrix and a convex combination of cycle matrices. We use this result to give a shorter proof of the theorem of Cruse which asserts that a doubly stochastic matrix is a convex combination of nonidentity permutation matrices if and only if its inner product with each generalized transitive tournament matrix is at least 1. The generalized transitive tournaments of order n form a convex polytope T(n) which contains the convex hull T(n)* (also called the linear ordering polytope) of the transitive tournaments. Each transitive tournament matrix of order n is an extreme point of T(n), but for n greater-than-or-equal-to 6 there are other extreme points. With each generalized tournament matrix T of order n we associate a graph whose edges correspond to the nonintegral entries of T. We investigate which graphs can arise from generalized transitive tournaments and which can arise from extreme generalized transitive tournaments. We briefly discuss a generalization of the linear ordering polytope to arbitrary posets.