Appears in collection : Combinatorics and Arithmetic for Physics : Special Days
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)
