Files and links (1)
Preprint (Author's original)arXiv.org - Non-exclusive license to distribute, Open
Preprint
The one-sided cycle shuffles in the symmetric group algebra
arXiv (Cornell University)
12 Dec 2022
Abstract
We study a family of shuffling operators on the symmetric group $S_n$, which
includes the top-to-random shuffle. The general shuffling scheme consists of
removing one card at a time from the deck (according to some probability
distribution) and re-inserting it at a (uniformly) random position further
below. Rewritten in terms of the group algebra $\mathbb{R}[S_n]$, our shuffle
corresponds to right multiplication by a linear combination of the elements
\[t_i:=\text{cyc}_{i}+\text{cyc}_{i,i+1}+\text{cyc}_{i,i+1,i+2}+\cdots+\text{cyc}_{i,i+1,\ldots,n}\in
\mathbb{R}[S_n]\] for all $i\in\{1,2,\ldots,n\}$ (where
$\text{cyc}_{j_1,j_2,\ldots,j_p}$ stands for a $p$-cycle).
We compute the eigenvalues of these shuffling operators and of all their
linear combinations. In particular, we show that the eigenvalues of right
multiplication by a linear combination
$\lambda_1t_1+\lambda_2t_2+\cdots+\lambda_nt_n$ are the numbers
$\lambda_1m_{I,1}+\lambda_2m_{I,2}+\cdots+\lambda_nm_{I,n}$, where $I$ ranges
over the subsets of $\{1,2,\ldots,n-1\}$ that contain no two consecutive
integers; here $m_{I,i}$ are certain integers. We compute the multiplicities of
these eigenvalues and show that if they are all distinct, the shuffling
operator is diagonalizable. To this purpose, we show that the operators of
right multiplication by $t_1,t_2,\ldots,t_n$ on $\mathbb{R}[S_n]$ are
simultaneously triangularizable (via a combinatorially defined basis). The
results stated here over $\mathbb{R}$ for convenience are actually stated and
proved over an arbitrary commutative ring $\mathbf{k}$.
We finish by describing a strong stationary time for the random-to-below
shuffle, which is the shuffle in which the card that moves below is selected
uniformly at random, and we give the waiting time for this event to happen.
Metrics
5 Record Views
Details
- Title
- The one-sided cycle shuffles in the symmetric group algebra
- Creators
- Darij GrinbergNadia Lafrenière
- Publication Details
- arXiv (Cornell University)
- Resource Type
- Preprint
- Language
- English
- Academic Unit
- Mathematics
- Other Identifier
- 991021862234304721