The volume of the polytope of doubly stochastic matrices and some of its faces

David Robbins

Center for Communications Research

October 15,
refreshments at 3:45pm


Two years ago, just out of curiosity, we (Clara Chan and I) studied some methods for calculating the volume of B_n, the set of n by n doubly stochastic matrices (nonnegative real square matrices with all row and column sums equal to 1). The standard method had been based on the counting of magic squares (non-negative integer square matrices with constant row and column sums). We decided to investigate a different method, based on work of Richard Stanley, which amounted to counting the simplices in a triangulation of B_n into simplices all of the same volume. A byproduct of the method was that we were able to calculate the volume of any face of B_n. While there does not appear to be any simple formula for the volume of the B_n itself, we discovered that there was a certain face, the set of doubly stochastic matrices (x_{ij}) with x_{ij}=0 for j>i+1, for which the volume was given essentially as a product of the first so many Catalan numbers. Working with David Yuen, we found a class of combinatorial objects in one-to-one correspondence with the simplices in a decomposition of our face into simplices of the same volume. We will describe an argument of Doron Zeilberger which establishes the Catalan product for the cardinality of the class of combinatorial objects by using an extension of "Morris's Constant Term Identity".

Speaker's Contact Info: robbins(at-sign)

Return to seminar home page

Combinatorics Seminar, Mathematics Department, MIT, sara(at-sign)

Page loaded on September 10, 1999 at 04:02 PM. Copyright © 1998-99, Sara C. Billey. All rights reserved.