Top to random and reverse: analysis of a new descent algebra shuffle
Preprint
Abstract
We study the "top-to-random-and-reverse shuffle", defined as the top-to-random shuffle in the symmetric group algebra composed with the permutation $w_0$ (which sends each $i$ to $n+1-i$). More generally, we analyze the composition of any B-basis element of the descent algebra with $w_0$. We show that the minimal polynomial of any such composition (over $\mathbb{Q}$) factors into distinct linear factors, which correspond to the "signed knapsack numbers" of set compositions. This is a counterpart to an analogous property of the B-basis elements themselves, which was proved by Brown using Bidigare's face monoid. In the case of the top-to-random-and-reverse shuffle, the minimal polynomial turns out to be $\prod_{k \in \set{-n+2} \cup \interval{-n+4, n-3} \cup \set{0} \cup \set{n}} \tup{x-k}$.
Keywords
All Related Versions
This publication has 14 references indexed in Scilit:
- The Miracle of Integer EigenvaluesFunctional Analysis and Its Applications, 2024
- The Mathematics of Shuffling Cards2023
- A Tour of Representation Theory2018
- Spectral analysis of random-to-random Markov chainsAdvances in Mathematics, 2018
- Spectra of symmetrized shuffling operatorsMemoirs of the American Mathematical Society, 2013
- Noncommutative Character Theory of the Symmetric Group2005
- Semigroups, Rings, and Markov ChainsJournal of Theoretical Probability, 2000
- On the matrix occurring in a linear search problemJournal of Applied Probability, 1991
- Generating a random permutation with random transpositionsProbability Theory and Related Fields, 1981
- A Mackey formula in the group ring of a Coxeter groupJournal of Algebra, 1976