The one-sided cycle shuffles in the symmetric group algebra

Darij Grinberg; Nadia Lafreniere

doi:10.5802/alco.346

We study an infinite family of shuffling operators on the symmetric group Sn, which includes the well-studied 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 position chosen uniformly at random among the positions below. Rewritten in terms of the group algebra R[S-n], our shuffle corresponds to right multiplication by a linear combination of the elements t(& ell;): = cyc(& ell;)+cyc(& ell;,& ell;+1)+cyc(& ell;,& ell;+1,& ell;+2)+& ctdot;+cyc(& ell;,& ell;+1),...,n is an element of R [S-n] for all & ell; is an element of {1,2,...,n} (where cyc(i1,i2,...,ip) denotes the permutation in Sn that cycles through i(1),i(2),...,i(p)). 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 1t1+lambda 2t2+& ctdot;+lambda(n)tn (with lambda(1),lambda(2),...,lambda(n) is an element of R) are the numbers lambda(1)m(I,1)+lambda(2)m(I,2)+& ctdot;+lambda(n)mI,n, where I ranges over the lacunar subsets of 1,2,...,n-1 (i.e., over the subsets that contain no two consecutive integers), and where mI, & ell; denotes the distance from & ell; to the next-higher element of I (this "next-higher element" is understood to be & ell; itself if & ell;is an element of I, and to be n+1 if & ell; > maxI). 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),...,t(n) onRS(n) are simultaneously triangularizable, and in fact there is a combinatorially defined basis (the "descent-destroying basis", as we call it) of RSn in which they are represented by upper-triangular matrices. The results stated here over & Ropf; for convenience are actually stated and proved over an arbitrary commutative ring 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.

The one-sided cycle shuffles in the symmetric group algebra

Files and links (1)

Abstract

Metrics

Details

The one-sided cycle shuffles in the symmetric group algebra

Files and links (1)

Abstract

Metrics

Details

Drexel University Social media