Spectra of symmetrized shuffling operators

Victor Reiner, Franco Saliola, Volkmar Welker

Research output: Contribution to journalArticlepeer-review

15 Scopus citations


For a finite real reflection group W and a W-orbit O of flats in its reflection arrangement - or equivalently a conjugacy class of its parabolic subgroups - we introduce a statistic noninv O(w) on w in W that counts the number of "O-noninversions" of w. This generalizes the classical (non-)inversion statistic for permutations w in the symmetric group S n. We then study the operator νO of right-multiplication within the group algebra ℂW by the element that has noninvO(w) as its coefficient on w. We reinterpret ν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, νO corresponds to a Markov chain on the chambers of the arrangement. We show that νO is self-adjoint and positive semidefinite, via two explicit factorizations into a symmetrized form φtφ. In one such factorization, the matrix φ 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 νO as φtφ, the matrix φ 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 {ν( κ,1n-κ) }κ=1,2,...,n, corresponding to the case where O is the conjugacy classes of Young subgroups in W = Sn of type (κ, 1n-κ). The κ = n-1 special case within this family is the operator ν(n-1,1) corresponding to random-to-random shuffling, factoring as φtφ where φ corresponds to random-to-top shuffling. We show in a purely enumerative fashion that this family of operators {ν(κ,1n-κ) } pairwise commute. We furthermore conjecture that they have integer spectrum, generalizing a conjecture of Uyemura-Reyes for the case κ = 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 ℂW-module structure on each block. We further use representation theory to show that if O is a conjugacy class of rank one parabolics in W, multiplication by νO has integer spectrum; as a very special case, this holds for the matrix (inv(στ-1))σ,τεSn. 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 {±1}-valued character χ of the centralizer subgroup ZW(s) given by its action on the line H⊥ has the property that χ is multiplicity-free when induced up to W. In other words, (W, ZW(s), χ) forms a twisted Gelfand pair. We also closely study the example of the family of operators {ν(2κ,1n-2κ) } k=0,1,2,..., ⌊ n/2 ⌋ corresponding to the case where O is the conjugacy classes of Young subgroups in W = Sn of type (2 κ, 1n-2κ). Here the construction of a Gelfand model for Sn shows both that these operators pairwise commute, and that they have integer spectrum. We conjecture that, apart from these two commuting families {ν(κ,1n-κ) } and {ν(2κ, 1n-2κ) } and trivial cases, no other pair of operators of the form νO commutes for W = Sn.

Original languageEnglish (US)
Pages (from-to)1-121
Number of pages121
JournalMemoirs of the American Mathematical Society
Issue number1072
StatePublished - Mar 1 2014


Dive into the research topics of 'Spectra of symmetrized shuffling operators'. Together they form a unique fingerprint.

Cite this