The volume of the polytope of doubly stochastic matrices and some of its faces
David Robbins
Center for Communications Research
October 15,
4:15pm
refreshments at 3:45pm
2338
ABSTRACT

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 (nonnegative 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
onetoone 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(atsign)ccrp.ida.org
Return to seminar home page
Page loaded on September 10, 1999 at 04:02 PM.

Copyright © 199899, Sara C. Billey.
All rights reserved.

