#### How to Order

For AMS eBook frontlist subscriptions or backfile collection purchases:

2. Complete and sign the license agreement.

3. Email, fax, or send via postal mail to:

Customer Services
American Mathematical Society
201 Charles Street Providence, RI 02904-2213  USA
Phone: 1-800-321-4AMS (4267)
Fax: 1-401-455-4046
Email: cust-serv@ams.org

Visit the AMS Bookstore for individual volume purchases.

Browse the current eBook Collections price list

# memo_has_moved_text();Spectra of symmetrized shuffling operators

Victor Reiner, Franco Saliola and Volkmar Welker

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: http://dx.doi.org/10.1090/memo/1072
Published electronically: July 24, 2013

View full volume PDF

View other years and numbers:

Chapters

• Chapter 1. Introduction
• Chapter 2. Defining the operators
• Chapter 3. The case where $\mathcal {O}$ contains only hyperplanes
• Chapter 4. Equivariant theory of BHR\xspace random walks
• Chapter 5. The family $\nu _{(2^k,1^{n-2k})}$
• Chapter 6. The original family $\nu _{(k,1^{n-k})}$
• Chapter 7. Acknowledgements
• Appendix 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 $(\ensuremath {\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

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$.