Doubly Stochastic Matrices and the Bruhat Order

Abstract

The Bruhat order is defined in terms of an interchange operation on the set of permutation matrices of order n which corresponds to the transposition of a pair of elements in a permutation. We introduce an extension of this partial order, which we call the stochastic Bruhat order, for the larger class Ωn of doubly stochastic matrices (convex hull of n×n permutation matrices). An alternative description of this partial order is given. We define a class of special faces of Ωn induced by permutation matrices, which we call Bruhat faces. Several examples of Bruhat faces are given and several results are presented. This research was first published in Czechoslovak Mathematical Journal. © Springer Verlag.