The one-sided cycle shuffles in the symmetric group algebra
We study a new family of elements in the group ring of a symmetric group – or, equivalently, a class of ways to shuffle a deck of cards. Fix a positive integer n. Consider the symmetric group S_n. For each 1 ≤ ℓ ≤ n, we define an element t_ℓ := cyc_ℓ + cyc{ℓ,ℓ+1} + cyc_{ℓ,ℓ+1,ℓ+2} + · · · + cyc_{ℓ,ℓ+1,...,n} of the group ring ${\mathbb R} [S_n]$, where cyc_{i₁,i₂,...,i_k} denotes the cycle that rotates through the given elements i₁, i₂ , . . . , i_k . We refer to these n elements t₁, t₂, . . . , t_n as the somewhere-to-below shuffles, since the standard interpretation of elements of ${\mathbb R} [S_n]$ in terms of card shuffling allows us to view them as shuffling operators. Note that t₁ is the well-known top-to-random shuffle studied by Diaconis, Fill, Pitman and others, whereas t_n = id. Similar families of elements of ${\mathbb R} [S_n]$ include the Young-Jucys-Murphy el- ements, the Reiner-Saliola-Welker elements, and the Diaconis-Fill-Pitman ele- ments. Unlike the latter three families, the somewhere-to-below shuffles t₁, t₂, . . . , t_n do not commute. However, they come close to commuting: There is a basis of ${\mathbb R} [S_n]$ on which they all act as upper-triangular matrices; thus, they generate an algebra whose semisimple quotient is commutative (which entails, in particular, that their commutators are nilpotent). This basis can in fact be constructed combinatorially, and bears several un- expected connections, most strikingly to the Fibonacci sequence. One of the consequences is that any ${\mathbb R}$-linear combination λ₁ t₁ + λ₂ t₂ + · · · + λ_n t_n (with λ₁ , λ₂ , . . . , λ_n ∈ {\mathbb R}) can be triangularized and its eigenvalues explicitly computed (along with their multiplicities); the number of distinct eigenvalues is at most the Fibonacci number f_{n+1}. If all these f_{n+1} eigenvalues are indeed distinct, then the matrix is diagonalizable. While we have been working over ${\mathbb R}$ for illustrative purposes, all our proofs hold over any commutative ring (or, for the diagonalizability claim, over any field). Several open questions remain (joint work with Nadia Lafrenière)