The one-sided cycle shuffles in the symmetric group algebra

Grinberg, Darij; Lafrenière, Nadia

doi:10.5802/alco.346

Grinberg, Darij ¹; Lafrenière, Nadia ²

¹ Drexel University Korman Center 15 S 33rd Street Office #263 Philadelphia, PA 19104 (USA)
² Concordia University J.W. McConnell Building (LB) 1400 De Maisonneuve Blvd. W. Montreal, QC H3G 1M8 (Canada)

Algebraic Combinatorics, Volume 7 (2024) no. 2, pp. 275-326.

Abstract

We study an infinite family of shuffling operators on the symmetric group $S_{n}$ , 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 $ℝ [S_{n}]$ , our shuffle corresponds to right multiplication by a linear combination of the elements

t_{ℓ} : = {cyc}_{ℓ} + {cyc}_{ℓ, ℓ + 1} + {cyc}_{ℓ, ℓ + 1, ℓ + 2} + \dots + {cyc}_{ℓ, ℓ + 1, ..., n} \in ℝ [S_{n}]

for all $ℓ \in \{1, 2, ..., n\}$ (where ${cyc}_{i_{1}, i_{2}, ..., i_{p}}$ denotes the permutation in $S_{n}$ 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 $λ_{1} t_{1} + λ_{2} t_{2} + \dots + λ_{n} t_{n}$ (with $λ_{1}, λ_{2}, ..., λ_{n} \in ℝ$ ) are the numbers $λ_{1} m_{I, 1} + λ_{2} m_{I, 2} + \dots + λ_{n} m_{I, 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 $m_{I, ℓ}$ denotes the distance from $ℓ$ to the next-higher element of $I$ (this “next-higher element” is understood to be $ℓ$ itself if $ℓ \in I$ , and to be $n + 1$ if $ℓ > max I$ ). 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}$ on $ℝ [S_{n}]$ are simultaneously triangularizable, and in fact there is a combinatorially defined basis (the “descent-destroying basis”, as we call it) of $ℝ [S_{n}]$ in which they are represented by upper-triangular matrices. The results stated here over $ℝ$ 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.

Received: 2023-03-17
Revised: 2023-10-21
Accepted: 2023-11-07
Published online: 2024-04-29

DOI: 10.5802/alco.346

Classification: 05E99, 20C30, 60J10
Keywords: symmetric group, permutations, card shuffling, top-to-random shuffle, group algebra, substitutional analysis, Fibonacci numbers, filtration, representation theory, Markov chain

Author's affiliations:

Grinberg, Darij ¹; Lafrenière, Nadia ²

¹ Drexel University Korman Center 15 S 33rd Street Office #263 Philadelphia, PA 19104 (USA)
² Concordia University J.W. McConnell Building (LB) 1400 De Maisonneuve Blvd. W. Montreal, QC H3G 1M8 (Canada)

License:

CC-BY 4.0

Copyrights: The authors retain unrestricted copyrights and publishing rights

@article{ALCO_2024__7_2_275_0,
     author = {Grinberg, Darij and Lafreni\`ere, Nadia},
     title = {The one-sided cycle shuffles in the symmetric group algebra},
     journal = {Algebraic Combinatorics},
     pages = {275--326},
     publisher = {The Combinatorics Consortium},
     volume = {7},
     number = {2},
     year = {2024},
     doi = {10.5802/alco.346},
     language = {en},
     url = {https://alco.centre-mersenne.org/articles/10.5802/alco.346/}
}

TY  - JOUR
AU  - Grinberg, Darij
AU  - Lafrenière, Nadia
TI  - The one-sided cycle shuffles in the symmetric group algebra
JO  - Algebraic Combinatorics
PY  - 2024
SP  - 275
EP  - 326
VL  - 7
IS  - 2
PB  - The Combinatorics Consortium
UR  - https://alco.centre-mersenne.org/articles/10.5802/alco.346/
DO  - 10.5802/alco.346
LA  - en
ID  - ALCO_2024__7_2_275_0
ER  -

%0 Journal Article
%A Grinberg, Darij
%A Lafrenière, Nadia
%T The one-sided cycle shuffles in the symmetric group algebra
%J Algebraic Combinatorics
%D 2024
%P 275-326
%V 7
%N 2
%I The Combinatorics Consortium
%U https://alco.centre-mersenne.org/articles/10.5802/alco.346/
%R 10.5802/alco.346
%G en
%F ALCO_2024__7_2_275_0

Grinberg, Darij; Lafrenière, Nadia. The one-sided cycle shuffles in the symmetric group algebra. Algebraic Combinatorics, Volume 7 (2024) no. 2, pp. 275-326. doi : 10.5802/alco.346. https://alco.centre-mersenne.org/articles/10.5802/alco.346/

References
Cited by

[1] Aguiar, Marcelo; Nyman, Kathryn; Orellana, Rosa New results on the peak algebra, J. Algebraic Combin., Volume 23 (2006) no. 2, pp. 149-188 | DOI | MR

[2] Aldous, David; Diaconis, Persi Shuffling cards and stopping times, Amer. Math. Monthly, Volume 93 (1986) no. 5, pp. 333-348 | DOI | MR

[3] Bate, Michael E.; Connor, Stephen B.; Matheau-Raven, Oliver Cutoff for a one-sided transposition shuffle, Ann. Appl. Probab., Volume 31 (2021) no. 4, pp. 1746-1773 | DOI | MR | Zbl

[4] Bayer, Dave; Diaconis, Persi Trailing the dovetail shuffle to its lair, Ann. Appl. Probab., Volume 2 (1992) no. 2, pp. 294-313 | DOI | MR

[5] Bidigare, Pat; Hanlon, Phil; Rockmore, Dan A combinatorial description of the spectrum for the Tsetlin library and its generalization to hyperplane arrangements, Duke Math. J., Volume 99 (1999) no. 1, pp. 135-174 | DOI | MR | Zbl

[6] Chu, Hùng Viêt The Fibonacci sequence and Schreier-Zeckendorf sets, J. Integer Seq., Volume 22 (2019) no. 6, Paper no. 19.6.5, 12 pages | MR

[7] Diaconis, Persi; Fill, James Allen; Pitman, Jim Analysis of top to random shuffles, Combin. Probab. Comput., Volume 1 (1992) no. 2, pp. 135-155 | DOI | MR | Zbl

[8] Diaconis, Persi; Pang, C. Y. Amy; Ram, Arun Hopf algebras and Markov chains: two examples and a theory, J. Algebraic Combin., Volume 39 (2014) no. 3, pp. 527-585 | DOI | MR

[9] Diaconis, Persi; Shahshahani, Mehrdad Generating a random permutation with random transpositions, Z. Wahrsch. Verw. Gebiete, Volume 57 (1981) no. 2, pp. 159-179 | DOI | MR

[10] Dieker, A. B.; Saliola, F. V. Spectral analysis of random-to-random Markov chains, Adv. Math., Volume 323 (2018), pp. 427-485 | DOI | MR

[11] Donnelly, Peter The heaps process, libraries, and size-biased permutations, J. Appl. Probab., Volume 28 (1991) no. 2, pp. 321-335 | DOI | MR

[12] Fill, James Allen An exact formula for the move-to-front rule for self-organizing lists, J. Theoret. Probab., Volume 9 (1996) no. 1, pp. 113-160 | DOI | MR | Zbl

[13] Grinberg, Darij Answers to “Is this sum of cycles invertible in $ℚ S_{n}$ ?”, 2018 https://mathoverflow.net/questions/308536/ (MathOverflow thread #308536)

[14] Grinberg, Darij The Elser nuclei sum revisited, Discrete Math. Theor. Comput. Sci., Volume 23 (2021) no. 1, Paper no. 15, 25 pages | MR | Zbl

[15] Grinberg, Darij Enumerative Combinatorics, 2022 http://www.cip.ifi.lmu.de/~grinberg/t/19fco/n/n.pdf (unpublished notes)

[16] Grinberg, Darij Commutator nilpotency for somewhere-to-below shuffles, 2023 | arXiv

[17] Grinberg, Darij; Lafrenière, Nadia The one-sided cycle shuffles in the symmetric group algebra, 2022 | arXiv

[18] Grinberg, Darij; Lafrenière, Nadia The somewhere-to-below shuffles in the symmetric group and Hecke algebras, 2023 (extended abstract accepted in the FPSAC 2024 conference)

[19] Hendricks, W. J. The stationary distribution of an interesting Markov chain, J. Appl. Probability, Volume 9 (1972), pp. 231-233 | DOI | MR

[20] Hoffman, Kenneth; Kunze, Ray Linear algebra, Prentice-Hall, Inc., Englewood Cliffs, NJ, 1971, viii+407 pages | MR

[21] Lafrenière, Nadia Valeurs propres des opérateurs de mélange symétrisés, PhD thesis, Université du Québec à Montréal (2019), xvi+160 pages | arXiv

[22] Levin, David A.; Peres, Yuval; Wilmer, Elizabeth L Markov chains and mixing times, American Mathematical Society, Providence, RI, 2017, xvi+447 pages | MR

[23] Mathas, Andrew Iwahori-Hecke algebras and Schur algebras of the symmetric group, University Lecture Series, 15, American Mathematical Society, Providence, RI, 1999, xiv+188 pages | DOI | MR

[24] Meusburger, Catherine Hopf Algebras and Representation Theory of Hopf Algebras, 2021 https://en.www.math.fau.de/lie-groups/scientific-staff/prof-dr-catherine-meusburger/teaching/lecture-notes/ (unpublished lecture notes)

[25] Nestoridi, Evita; Peng, Kenny Mixing times of one-sided $k$ -transposition shuffles, 2021 | arXiv

[26] Palmes, Christian Top-to-Random-Shuffles, diploma thesis, Westfälische Wilhelms-Universität Münster (2010), ii+110 pages https://www.uni-muenster.de/stochastik/alsmeyer/diplomarbeiten/palmes.pdf

[27] Pang, C. Y. Amy The eigenvalues of hyperoctahedral descent operators and applications to card-shuffling, Electron. J. Combin., Volume 29 (2022) no. 1, Paper no. 1.32, 50 pages | DOI | MR

[28] Phatarfod, R. M. On the matrix occurring in a linear search problem, J. Appl. Probab., Volume 28 (1991) no. 2, pp. 336-346 | DOI | MR

[29] Reiner, Victor; Saliola, Franco; Welker, Volkmar Spectra of symmetrized shuffling operators, Mem. Amer. Math. Soc., Volume 228 (2014) no. 1072, p. vi+109 | MR | Zbl

[30] Reizenstein, Jeremy Francis Iterated-Integral Signatures in Machine Learning, PhD thesis, University of Warwick (2019), ix+107 pages http://wrap.warwick.ac.uk/131162/

[31] The Sagemath developers SageMath, (Version 9.4) (2022) (https://www.sagemath.org)

Cited by Sources: