Algebraic combinatorics, semigroup representations and random walks on hyperplane chambers after Ken Brown
by
Benjamin Steinberg
Carleton University

Ken Brown observed that the eigenvalues with multiplicity for certain random walks on the chambers of a hyperplane arrangement could be calculated using the representation theory of finite semigroups and Rota's theory of Möbius inversion. The underlying idea is the same as Diaconis' approach to random walks on finite abelian groups: both rely on the fact that the semigroup algebras in question are triangularizable and so the eigenvalues of the Markov operator are certain character sums.

Inspired by this we have developed algebraic-combinatorial tools to compute multiplicities of irreducible representations for a large class of finite semigroups including inverse semigroups, semigroups with commuting idempotents and semigroups with triangularizable algebras. In particular eigenvalues can be calculated (with multiplicity), via character sums, for random walks on finite semigroups with abelian subgroups whose von Neumann regular elements satisfy an identity of the form x^m=x.

Date received: March 6, 2006