Semigroups, Rings, and Markov Chains
By Kenneth S. Brown. 2000
167 citations recorded by the source corpus.
We analyze random walks on a class of semigroups called “left-regular bands.” These walks include the hyperplane chamber walks of Bidigare, Hanlon, and Rockmore. Using methods of ring theory, we show that the transition matrices are diagonalizable and we calculate the eigenvalues and multiplicities. The methods lead to explicit formulas for the projections onto the eigenspaces. As examples of these semigroup walks, we construct a random walk on the maximal chains of any distributive lattice, as well as two random walks associated with any matroid. The examples include a q-analogue of the Tsetlin library. The multiplicities of the eigenvalues in the matroid walks are “generalized derangement numbers,” which may be of independent interest.
Subfields: Computational Theory and Mathematics, Discrete Mathematics and Combinatorics
View Paper: https://www.semanticscholar.org/paper/0bc98564d90cf1457ea194d28c12f2568309cce1
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Computational Theory and Mathematics
- Ben Steinberg
- John L. Rhodes
- Stuart W. Margolis
- Volodymyr Mazorchuk
- Olexandr Ganyushkin
- Jorge Almeida
- Mikhail Volkov
- Marcelo Aguiar
In Discrete Mathematics and Combinatorics
- Ben Steinberg
- Stuart W. Margolis
- Swapneel Mahajan
- Volodymyr Mazorchuk
- Olexandr Ganyushkin
- John L. Rhodes
- Marcelo Aguiar
- Franco V. Saliola
Citations in the corpus
- The q-theory of Finite Semigroups (2008, background): “(See also [1,55,56,325,326] for recent connections of finite semigroup representation theory with Probability Theory, random walks, hyperplane arrangements and Coxeter groups.”
- Möbius functions and semigroup representation theory II: Character formulas and multiplicities (2006, background): “Our results therefore extend to this domain, and in particular we recover the case of idempotent semigroups [8, 9, 29] and semigroups with basic algebras [45].”
- Combinatorial Topology and the Global Dimension of Algebras Arising in Combinatorics (2012, background): “The second author [80] computed the Ext-spaces between simple modules in the case of the algebras of face monoids of hyperplane arrangements using the resolutions of Brown and Diaconis coming from the topology of hyperplane arrangements.”
- HOPF MONOIDS IN THE CATEGORY OF SPECIES (2012, methodology): “Kenneth S. Brown.”
- On the irreducible representations of a finite semigroup (2007, methodology): “As an application, we provide the description of the irreducible representations of an idempotent semigroup that was rediscovered by Brown [1, 2] and put to good effect in the study of random walks.”
- Representation theory of finite semigroups, semigroup radicals and formal language theory (2007, background): “Recent work of Bidigaire et al. [10]and Brown [12,13],for instance,spendsquite som e tim e in redeveloping basic aspects ofthe representation theory ofidem potent sem igroups (known as bands)thatwerealready in theliterature[28,56,31,26],butperhapsnotin a form accessible to m ostm athem aticians.”