Algebraic Combinatorics Seminar - Darij Grinberg

Title: The one-sided cycle shuffles in the symmetric group algebra

Abstract:

Elements in the group algebra of a symmetric group S_n are known to have an interpretation in terms of card shuffling. I will discuss a new family of such elements, recently constructed by Nadia Lafrenière: Given a positive integer n, we define n elements t_1, t_2, ..., t_n in

the group algebra of S_n by

t_i = the sum of the cycles (i), (i, i+1), (i, i+1, i+2), ..., (i, i+1, ..., n),

where the cycle (i) is the identity permutation. 

The first of them, t_1, is known as the top-to-random shuffle and has been studied by Diaconis, Fill, and Pitman (among others). The n elements t_1, t_2, ..., t_n do not commute. However, we show that they can be simultaneously triangularized in an appropriate basis

of the group algebra (the "descent-destroying basis"). As a

consequence, any rational linear combination of these n elements has rational eigenvalues. The maximum number of possible distinct eigenvalues turns out to be the Fibonacci number f_{n+1}, and underlying this fact is a filtration of the group algebra connected to "lacunar subsets" (i.e., subsets containing no consecutive integers).

This talk will include an overview of other families (both well-known and exotic) of elements of these group algebras. I will also briefly discuss the probabilistic meaning of these elements as well as some tempting conjectures.

This is joint work with Nadia Lafrenière.