AMS eBook CollectionsOne of the world's most respected mathematical collections, available in digital format for your library or institution

Spectra of symmetrized shuffling operators

About this Title

Victor Reiner, School of Mathematics, University of Minnesota, Minneapolis, Minnesota 55455, Franco Saliola, Laboratoire de Combinatoire et d’Informatique Mathématique (LaCIM), Université du Québec à Montréal, CP 8888, Succ. Centre-ville, Montréal (Québec) H3C 3P8, Canada and Volkmar Welker, Fachbereich Mathematik und Informatik, Philipps-Universität Marburg, 35032 Marburg, Germany

Publication: Memoirs of the American Mathematical Society
Publication Year: 2014; Volume 228, Number 1072
ISBNs: 978-0-8218-9095-0 (print); 978-1-4704-1484-9 (online)
DOI: https://doi.org/10.1090/memo/1072
Published electronically: July 24, 2013
MSC: Primary 05E15, 20F55, 60J10

View full volume PDF

Table of Contents

Chapters

• 1. Introduction
• 2. Defining the operators
• 3. The case where $\mathcal {O}$ contains only hyperplanes
• 4. Equivariant theory of BHR\xspace random walks
• 5. The family $\nu _{(2^k,1^{n-2k})}$
• 6. The original family $\nu _{(k,1^{n-k})}$
• 7. Acknowledgements
• A. $\mathfrak {S}_n$-module decomposition of $\nu _{(k,1^{n-k})}$

Abstract

For a finite real reflection group $W$ and a $W$-orbit $\mathcal {O}$ of flats in its reflection arrangement – or equivalently a conjugacy class of its parabolic subgroups – we introduce a statistic $\operatorname {noninv}_\mathcal {O}(w)$ on $w$ in $W$ that counts the number of “$\mathcal {O}$-noninversions” of $w$. This generalizes the classical (non-)inversion statistic for permutations $w$ in the symmetric group $\mathfrak {S}_n$. We then study the operator $\nu _\mathcal {O}$ of right-multiplication within the group algebra $\mathbb {C} W$ by the element that has $\operatorname {noninv}_\mathcal {O}(w)$ as its coefficient on $w$.

We reinterpret $\nu _\mathcal {O}$ geometrically in terms of the arrangement of reflecting hyperplanes for $W$, and more generally, for any real arrangement of linear hyperplanes. At this level of generality, one finds that, after appropriate scaling, $\nu _\mathcal {O}$ corresponds to a Markov chain on the chambers of the arrangement. We show that $\nu _\mathcal {O}$ is self-adjoint and positive semidefinite, via two explicit factorizations into a symmetrized form $\pi ^t \pi$. In one such factorization, the matrix $\pi$ is a generalization of the projection of a simplex onto the linear ordering polytope from the theory of social choice.

In the other factorization of $\nu _\mathcal {O}$ as $\pi ^t \pi$, the matrix $\pi$ is the transition matrix for one of the well-studied Bidigare-Hanlon-Rockmore random walks on the chambers of an arrangement. We study closely the example of the family of operators $\{ \nu _{(k,1^{n-k})} \}_{k=1,2,\ldots ,n}$, corresponding to the case where $\mathcal {O}$ is the conjugacy classes of Young subgroups in $W=\mathfrak {S}_n$ of type $(k,1^{n-k})$. The $k=n-1$ special case within this family is the operator $\nu _{(n-1,1)}$ corresponding to random-to-random shuffling, factoring as $\pi ^t \pi$ where $\pi$ corresponds to random-to-top shuffling. We show in a purely enumerative fashion that this family of operators $\{ \nu _{(k,1^{n-k})} \}$ pairwise commute. We furthermore conjecture that they have integer spectrum, generalizing a conjecture of Uyemura-Reyes for the case $k=n-1$. Although we do not know their complete simultaneous eigenspace decomposition, we give a coarser block-diagonalization of these operators, along with explicit descriptions of the $\mathbb {C} W$-module structure on each block.

We further use representation theory to show that if $\mathcal {O}$ is a conjugacy class of rank one parabolics in $W$, multiplication by $\nu _\mathcal {O}$ has integer spectrum; as a very special case, this holds for the matrix $(\operatorname {inv}(\sigma \tau ^ {-1}))_{\sigma ,\tau \in \mathfrak {S}_n}$. The proof uncovers a fact of independent interest. Let $W$ be an irreducible finite reflection group and $s$ any reflection in $W$, with reflecting hyperplane $H$. Then the $\{\pm 1\}$-valued character $\chi$ of the centralizer subgroup $Z_W(s)$ given by its action on the line $H^\perp$ has the property that $\chi$ is multiplicity-free when induced up to $W$. In other words, $(W, Z_W(s), \chi )$ forms a twisted Gelfand pair.

We also closely study the example of the family of operators \[ \{ \nu _{(2^k,1^{n-2k})} \}_{k=0,1,2,\ldots ,\lfloor \frac {n}{2} \rfloor }\]

corresponding to the case where $\mathcal {O}$ is the conjugacy classes of Young subgroups in $W=\mathfrak {S}_n$ of type $(2^k,1^{n-2k})$. Here the construction of a Gelfand model for $\mathfrak {S}_n$ shows both that these operators pairwise commute, and that they have integer spectrum.

We conjecture that, apart from these two commuting families $\{ \nu _{(k,1^{n-k})} \}$ and $\{ \nu _{(2^k,1^{n-2k})} \}$ and trivial cases, no other pair of operators of the form $\nu _\mathcal {O}$ commutes for $W=\mathfrak {S}_n$.