Random walk on upper triangular matrices mixes rapidly

We present an upper bound O(n ² ) for the mixing time of a simple random walk on upper triangular matrices. We show that this bound is sharp up to a constant, and find tight bounds on the eigenvalue gap. We conclude by applying our results to indicate that the asymmetric exclusion process on a circle indeed mixes more rapidly than the corresponding symmetric process. Received: 25 January 1999 / Revised version: 17 September 1999 / Published online: 14 June 2000