\documentclass[ALCO,published]{cedram}
\providecommand*\noopsort[1]{}
\usepackage{tabls}
\newenvironment{statement}{\begin{quote}}{\end{quote}}
\newcommand{\set}[1]{\left\{ #1 \right\}}
\newcommand{\abs}[1]{\left| #1 \right|}
\newcommand{\tup}[1]{\left( #1 \right)}
\newcommand{\ive}[1]{\left[ #1 \right]}
\newcommand{\kk}{\mathbf{k}}
\let\sumnonlimits\sum
\renewcommand{\sum}{\sumnonlimits\limits}
\DeclareMathOperator{\osc}{OSC}
\DeclareMathOperator{\rtb}{R2B}
\allowdisplaybreaks
\title{The one-sided cycle shuffles in the symmetric group algebra}
\author{\firstname{Darij} \lastname{Grinberg}}
\address{Drexel University\\
Korman Center\\
15 S 33rd Street\\
Office \#263\\
Philadelphia, PA 19104 (USA)}
\email{darijgrinberg@gmail.com}
\urladdr{http://www.cip.ifi.lmu.de/~grinberg/}
\author{\firstname{Nadia} \lastname{Lafreni\`{e}re}}
\address{Concordia University\\
J.W. McConnell Building (LB)\\
1400 De Maisonneuve Blvd. W.\\
Montreal, QC H3G 1M8 (Canada)}
\email{nadia.lafreniere@concordia.ca}
\urladdr{https://nadialafreniere.github.io/}
\keywords{symmetric group, permutations, card shuffling,
top-to-random shuffle, group algebra, substitutional analysis, Fibonacci
numbers, filtration, representation theory, Markov chain}
\subjclass{05E99, 20C30, 60J10}
\datepublished{2024-04-29}
\begin{document}
\begin{abstract}
We study an infinite family of shuffling operators on the symmetric group
$S_{n}$, which includes the well-studied top-to-random shuffle. The general
shuffling scheme consists of removing one card at a time from the deck
(according to some probability distribution) and re-inserting it at a position
chosen uniformly at random among the positions below. Rewritten in terms of
the group algebra $\mathbb{R}\left[ S_{n}\right] $, our shuffle corresponds
to right multiplication by a linear combination of the elements
\[
t_{\ell}:=\operatorname*{cyc}\nolimits_{\ell}+\operatorname*{cyc}
\nolimits_{\ell,\ell+1}+\operatorname*{cyc}\nolimits_{\ell,\ell+1,\ell
+2}+\cdots+\operatorname*{cyc}\nolimits_{\ell,\ell+1,\ldots,n}\in
\mathbb{R}\left[ S_{n}\right]
\]
for all $\ell\in\left\{ 1,2,\ldots,n\right\} $ (where~$\operatorname{cyc}
_{i_{1},i_{2},\ldots,i_{p}}$ denotes the permutation in $S_{n}$ that cycles
through~$i_{1},i_{2},\ldots,i_{p}$).
We compute the eigenvalues of these shuffling operators and of all their
linear combinations. In particular, we show that the eigenvalues of right
multiplication by a linear combination~$\lambda_{1}t_{1}+\lambda_{2}
t_{2}+\cdots+\lambda_{n}t_{n}$ (with $\lambda_{1},\lambda_{2},\ldots
,\lambda_{n}\in\mathbb{R}$) are the numbers $\lambda_{1}m_{I,1}+\lambda
_{2}m_{I,2}+\cdots+\lambda_{n}m_{I,n}$, where $I$ ranges over the
\emph{lacunar} subsets of $\left\{ 1,2,\ldots,n-1\right\} $ (i.e., over the
subsets that contain no two consecutive integers), and where $m_{I,\ell}$
denotes the distance from $\ell$ to the next-higher element of $I$ (this
``next-higher element'' is
understood to be $\ell$ itself if $\ell\in I$, and to be $n+1$ if
$\ell>\max I$). We compute the multiplicities of these eigenvalues and show
that if they are all distinct, the shuffling operator is diagonalizable. To
this purpose, we show that the operators of right multiplication by
$t_{1},t_{2},\ldots,t_{n}$ on $\mathbb{R}\left[ S_{n}\right] $ are
simultaneously triangularizable, and in fact there is a combinatorially
defined basis (the \textquotedblleft descent-destroying
basis\textquotedblright, as we call it) of $\mathbb{R}\left[ S_{n}\right] $
in which they are represented by upper-triangular matrices. The results stated
here over $\mathbb{R}$ for convenience are actually stated and proved over an
arbitrary commutative ring $\mathbf{k}$.
We finish by describing a strong stationary time for the random-to-below
shuffle, which is the shuffle in which the card that moves below is selected
uniformly at random, and we give the waiting time for this event to happen.
\end{abstract}
\maketitle
\section{Introduction}
Card shuffling operators have been studied both from algebraic and
probabilistic point of views. The interest in an algebraic study of those
operators bloomed with the discovery by Diaconis and Shahshahani that the
eigenvalues of some matrices could be used to bound the mixing time of the
shuffles~\cite{DiaSha81}, which answers the question \textquotedblleft how
many times should we shuffle a deck of cards to get a well-shuffled
deck?\textquotedblright. We now know a combinatorial description of the
eigenvalues of several shuffling operators, including the transposition
shuffle~\cite{DiaSha81}, the riffle shuffle~\cite{BayDia92}, the top-to-random
shuffle~\cite{Phatar91} and the random-to-random shuffle~\cite{DieSal18},
among several others. An interesting research question is to characterize
shuffles whose eigenvalues admit a combinatorial description. We contribute to
this project by describing a new family of shuffles that do so.
Given a probability distribution $P$ on the set $\left\{ 1,2,\ldots
,n\right\} $, the \emph{one-sided cycle shuffle} corresponding to $P$
consists of picking the card at position~$i$ with probability~$P\left(
i\right) $, removing it, and reinserting it at a position weakly below
position $i$, chosen uniformly at random. By varying the probability
distribution, we obtain an infinite family of shuffling operators, whose
eigenvalues can be written as linear combinations of certain combinatorial
numbers with coefficients given by the probability distribution. Special cases
of interest include the top-to-random shuffle, the random-to-below shuffle
(where position $i$ is selected uniformly at random), and the unweighted
one-sided cycle shuffle (where position $i$ is selected with probability
$\frac{2\left( n+1-i\right) }{n\left( n+1\right) }$). A more explicit
description of the shuffles can be found in Section~\ref{sec.shuffles}.
Two of our main results -- Corollary~\ref{cor.eigen.spec} and Theorem~\ref{thm.eigen.mult} -- give the eigenvalues of all the one-sided cycle
shuffles. These eigenvalues are indexed by what we call \textquotedblleft
lacunar sets\textquotedblright, which are subsets of $\mathbb{Z}$ that do not
contain consecutive integers (see Section~\ref{sec.Lacunarity} for details).
As a consequence, all eigenvalues are real, positive and explicitly described.
Most studies of eigenvalues of Markov chains focus on reversible chains, which
means that their transition matrix is symmetric. In that case, eigenvalues can
be used alone for bounding the mixing time of the Markov chain. This is
however not the case for the one-sided cycle shuffles.
Examples of non-reversible Markov chains whose eigenvalues have been studied
include the riffle shuffle~\cite{BayDia92}, the top-to-random and
random-to-top shuffles~\cite{Phatar91}, the pop shuffles and other `BHR'
shuffling operators~\cite{BiHaRo99}, and the top-$m$-to-random shuffles~\cite{DiFiPi92}.
All these admit a combinatorial description of their
eigenvalues. It is surprising that non-symmetric matrices admit real
eigenvalues, let alone eigenvalues that can be computed by simple formulas. It
is these surprisingly elegant eigenvalues that have given the impetus for the
present study.
To prove and explain our main results, we decompose the one-sided cycle
shuffles into linear combinations of $n$ operators $t_{1},t_{2},\ldots,t_{n}$,
which we call the \emph{somewhere-to-below shuffles}. Each somewhere-to-below
shuffle $t_{\ell}$ moves the card at position $\ell$ to a position weakly
below it, chosen uniformly at random. We show that the somewhere-to-below
shuffles are simultaneously triangularizable by giving explicitly a basis in
which they can be triangularized. This later gives us the eigenvalues. The
triangularity, in fact, is an understatement; we actually find a filtration
$0=F_{0}\subseteq F_{1}\subseteq F_{2}\subseteq\cdots\subseteq F_{f_{n+1}
}=\mathbb{Z}\left[ S_{n}\right] $ of the group ring of $S_{n}$ that is
preserved by all somewhere-to-below shuffles and has the additional property
that each $t_{\ell}$ acts as a scalar on each quotient~$F_{i}/F_{i-1}$. Here,
perhaps unexpectedly, $f_{n+1}$ is the $\left( n+1\right) $-st Fibonacci
number. Thus, the number of distinct eigenvalues of a one-sided cycle shuffle
is never larger than $f_{n+1}$.
A diversity of algebraic techniques for computing the spectrum of shuffling
operators have appeared recently
\cite{ReSaWe14,DiPaRa14,DieSal18,Lafren19,BaCoMR21,Pang22,NesPen22}. This
paper contributes new algebraic methods to this extensive toolkit.
We end the paper by establishing a strong stationary time for one shuffling
operator in our family, the random-to-below shuffle, which happens in an
expected time of at most $n\left( \log n+\log\left( \log n\right)
+\log2\right) +1$. The arguments used here are similar to those used to get a
stationary time for the top-to-random shuffle; see Section
~\ref{sec.stoppingtime}.
\subsection{Remark}
The arXiv version~\cite{s2b1} of this paper is longer and includes some
details that have been omitted from the present journal version. We will thus
refer to~\cite{s2b1} for some proofs that we leave to the reader here.
See also the extended abstract~\cite{fps2024sn} for a brief summary of this
and some related work.
\section{The algebraic setup}
Card shuffling schemes are often understood by mathematicians as drawing,
randomly, a permutation and applying it to a deck of cards. Therefore, our
work takes place in the symmetric group algebra, which we define in this section.
\subsection{Basic notations}
Let $\mathbf{k}$ be any commutative ring. (In most applications, $\mathbf{k}$
is either $\mathbb{Z}$, $\mathbb{Q}$ or $\mathbb{R}$.)
Let $\mathbb{N}:=\left\{ 0,1,2,\ldots\right\} $ be the set of all
nonnegative integers.
For any integers $a$ and $b$, we set $\left[ a,b\right] :=\left\{
a,a+1,\ldots,b\right\} $. This is an empty set if~$a>b$.
For each $n\in\mathbb{Z}$, let $\left[ n\right] :=\left[ 1,n\right]
=\left\{ 1,2,\ldots,n\right\} $.
Fix an integer $n\in\mathbb{N}$. Let $S_{n}$ be the $n$-th symmetric group,
i.e., the group of all permutations of $\left[ n\right] $. We multiply
permutations in the \textquotedblleft continental\textquotedblright\ way: that
is, $\left( \pi\sigma\right) \left( i\right) =\pi\left( \sigma\left(
i\right) \right) $ for all $\pi,\sigma\in S_{n}$ and $i\in\left[ n\right]
$.
For any $k$ distinct elements $i_{1},i_{2},\ldots,i_{k}$ of $\left[ n\right]
$, we let $\operatorname*{cyc}\nolimits_{i_{1},i_{2},\ldots,i_{k}}$ be the
permutation in $S_{n}$ that sends $i_{1},i_{2},\ldots,i_{k-1},i_{k}$ to
$i_{2},i_{3},\ldots,i_{k},i_{1}$, respectively while leaving all remaining
elements of $\left[ n\right] $ unchanged. This permutation is known as a
\emph{cycle}. Note that $\operatorname*{cyc}\nolimits_{i}=\operatorname*{id}$
for any single $i\in\left[ n\right] $.
\subsection{Some elements of \texorpdfstring{$\mathbf{k}\left[ S_{n}\right] $}{k[Sn]}}
Consider the group algebra $\mathbf{k}\left[ S_{n}\right] $. In this
algebra, define $n$ elements $t_{1},t_{2},\ldots,t_{n}$ by setting
\begin{equation}
t_{\ell}:=\operatorname*{cyc}\nolimits_{\ell}+\operatorname*{cyc}
\nolimits_{\ell,\ell+1}+\operatorname*{cyc}\nolimits_{\ell,\ell+1,\ell
+2}+\cdots+\operatorname*{cyc}\nolimits_{\ell,\ell+1,\ldots,n}\in
\mathbf{k}\left[ S_{n}\right] \label{eq.def.tl.deftl}
\end{equation}
for each $\ell\in\left[ n\right] $. Thus, in particular, $t_{n}
=\operatorname*{cyc}\nolimits_{n}=\operatorname*{id}=1$ (where $1$ means the
unity of $\mathbf{k}\left[ S_{n}\right] $). We shall refer to the $n$
elements $t_{1},t_{2},\ldots,t_{n}$ as the \emph{somewhere-to-below shuffles},
due to a probabilistic significance that we will discuss soon.
The first somewhere-to-below shuffle $t_{1}$ is known as the
\emph{top-to-random shuffle}, and appears, e.g., under the name $B_{1}$ in
\cite{DiFiPi92}, where it is studied extensively.
\footnote{The (German) diploma thesis~\cite{Palmes10}
provides a detailed exposition of the results of~\cite{DiFiPi92}
(in particular,~\cite[Satz 2.4.6]{Palmes10} is~\cite[Theorem 4.2]{DiFiPi92}).
\par
See also~\cite{Grinbe18} for an exposition of the most basic algebraic
properties of $t_{1}$ (called $\mathbf{A}$ there).
An unexpected application to machine learning has recently been given in
\cite[proof of Lemma 29]{Reizen19}.} It shares a lot of properties with its
adjoint operator, the \emph{random-to-top shuffle}, also widely studied
(sometimes with other names, such as the Tsetlin Library or the move-to-front
rule, as in~\cite{Hendri72, Donnel91, Phatar91, Fill96, BiHaRo99}), and
described in Section~\ref{sect.furtheralg} as $t_{1}^{\prime}$.
We shall study not just the somewhere-to-below shuffles, but also their
$\mathbf{k}$-linear combinations $\lambda_{1}t_{1}+\lambda_{2}t_{2}
+\cdots+\lambda_{n}t_{n}$ (with $\lambda_{1},\lambda_{2},\ldots,\lambda_{n}
\in\mathbf{k}$), which we call the \emph{one-sided cycle shuffles}.
\subsection{The card-shuffling interpretation}
For $\mathbf{k}=\mathbb{R}$, the elements $t_{1},t_{2},\ldots,t_{n}$ (and many
other elements of $\mathbf{k}\left[ S_{n}\right] $) have an interpretation
in terms of card shuffling.
Namely, we consider a permutation $w\in S_{n}$ as a way to order a deck of $n$
cards\footnote{As is customary in card-shuffling combinatorics, the cards are
bijectively numbered $1,2,\ldots,n$; there are no suits, colors or jokers.}
such that the cards are $w\left( 1 \right) ,w\left( 2 \right)
,\ldots,w\left( n \right) $ from top to bottom (so the top card is~$w\left(
1 \right) $, and the bottom card is $w\left( n \right) $). Shuffling the
deck corresponds to permuting the cards: A permutation $\sigma\in S_{n}$
transforms a deck order~$w\in S_{n}$ into the deck order~$w\sigma$ (that is,
the order in which the cards are $w\left( \sigma(1) \right) ,w\left(
\sigma(2) \right) ,\ldots,w\left( \sigma(n) \right) $ from top to bottom).
A probability distribution on the $n!$ possible orders of a deck of $n$ cards
can be identified with the element $\sum_{w\in S_{n}}P\left( w\right) w$ of
$\mathbb{R}\left[ S_{n}\right] $, where $P\left( w\right) $ is the
probability of the deck having order $w$. Likewise, a nonzero element
$\sum_{\sigma\in S_{n}}P\left( \sigma\right) \sigma$ of $\mathbb{R}\left[
S_{n}\right] $ (with all $P\left( \sigma\right) $ being nonnegative reals)
defines a Markov chain on the set of all these~$n!$ orders, in which the
transition probability from deck order $w$ to deck order $w\tau$ equals~$\dfrac{P\left( \tau\right) }{\sum_{\sigma\in S_{n}}P\left( \sigma\right)
}$ for each $w,\tau\in S_{n}$. This is an instance of a \emph{right random
walk on a group}, as defined (e.g.) in~\cite[Section 2.6]{LePeWi09}.
From this point of view, the top-to-random shuffle $t_{1}$ describes the
Markov chain in which a deck is transformed by picking the topmost card and
moving it into the deck at a position chosen uniformly at random (which may
well be its original, topmost position). This explains the name of $t_{1}$
(and its significance to probabilists). More generally, a somewhere-to-below
shuffle $t_{\ell}$ transforms a deck by picking its $\ell$-th card from the
top and moving it to a weakly lower place (chosen uniformly at random).
Finally, a one-sided cycle shuffle $\lambda_{1}t_{1}+\lambda_{2}t_{2}
+\cdots+\lambda_{n}t_{n}$ (with $\lambda_{1},\lambda_{2},\ldots,\lambda_{n}
\in\mathbb{R}_{\geq0}$ being not all $0$) picks a card at random --
specifically, picking the $\ell$-th card from the top with probability
$\dfrac{(n-\ell+1)\lambda_{\ell}}{\sum_{i=1}^{n}(n-i+1)\lambda_{i}}$ -- and
moves it to a weakly lower place (chosen uniformly at random).
\section{\label{sec.shuffles}The one-sided cycle shuffles}
In this section, we shall explore the probabilistic significance of one-sided
cycle shuffles and several particular cases thereof. We begin by a reindexing
of the one-sided cycle shuffles that is particularly convenient for
probabilistic considerations. Note that, since transition matrices of Markov
chains have their rows summing to $1$, the operators, as we describe them in
this section, are scaled to satisfy this property. However, throughout the
paper, the coefficients can sum up to any numbers; multiplying the operators
by the appropriate number would give the corresponding Markov chain.
For a given probability distribution $P$ on the set $\left[ n\right] $, we
define the \emph{one-sided cycle shuffle governed by }$P$ to be the element
\[
\osc(P,n):=\frac{P(1)}{n}t_{1}+\frac{P(2)}{n-1}t_{2}+\frac{P(3)}{n-2}
t_{3}+\cdots+\dfrac{P\left( n\right) }{1}t_{n}\in\mathbb{R}\left[
S_{n}\right] .
\]
This one-sided cycle shuffle gives rise to a Markov chain on the symmetric
group $S_{n}$, which transforms a deck order by selecting a card at random
according to the probability distribution $P$ (more precisely, we pick the
\textbf{position}, not the value of the card, using $P$), and then applying
the corresponding somewhere-to-below shuffle. The transition probability of
this Markov chain is thus given by
\[
Q(\tau,\sigma)=\left\{
\begin{array}
[c]{ll}
\sum_{i=1}^{n}\frac{P(i)}{n+1-i}, & \text{if }\sigma=\tau;\\
\frac{P(i)}{n+1-i}, & \text{if }\sigma=\tau\cdot\operatorname*{cyc}
\nolimits_{i,i+1,\ldots,j}\text{ for some $j>i;$}\\
0, & \text{otherwise}.
\end{array}
\right.
\]
The $n!\times n!$-matrix $\left( Q\left( \tau,\sigma\right) \right)
_{\tau,\sigma\in S_{n}}$ is the transition matrix of this Markov chain; when
we talk of the eigenvalues of the Markov chain, we refer to the eigenvalues of
the corresponding transition matrix.
These Markov chains are not reversible, which means that their transition
matrices are not symmetric.
\subsection{Interesting one-sided cycle shuffles}
Some probability distributions on~$[n]$ lead to one-sided cycle shuffles that
have an interesting meaning in terms of card shuffling. We shall next consider
three such cases.
\begin{enumerate}
\item \textbf{The top-to-random shuffle.}
The top-to-random shuffle $t_{1}$ is the one-sided cycle shuffle that garnered
the most interest. We obtain it by setting $P(1)=1$, and $P(i)=0$ for all~$i\neq1$.
The transition matrix for the top-to-random shuffle, with $3$ cards $w_{1} :=
w\left( 1 \right) $, $w_{2} := w\left( 2 \right) $ and $w_{3} := w\left(
3 \right) $, is
\[
\operatorname*{T2R}\nolimits_{3}
=\bordermatrix{ &{\scriptstyle [w_1w_2w_3]} & {\scriptstyle [w_1w_3w_2]} &
{\scriptstyle [w_2w_1w_3]} & {\scriptstyle [w_2w_3w_1]} &
{\scriptstyle [w_3w_1w_2]} & {\scriptstyle [w_3w_2w_1]} \cr
{\scriptstyle [w_1w_2w_3]} & \frac{1}{3} & 0 & \frac{1}{3} & \frac{1}{3} & 0 & 0 \cr
{\scriptstyle [w_1w_3w_2]} & 0 & \frac{1}{3} & 0 & 0 & \frac{1}{3} & \frac{1}{3} \cr
{\scriptstyle [w_2w_1w_3]} & \frac{1}{3} & \frac{1}{3} & \frac{1}{3} & 0 & 0 & 0 \cr
{\scriptstyle [w_2w_3w_1]} & 0 & 0 & 0 & \frac{1}{3} & \frac{1}{3} & \frac{1}{3} \cr
{\scriptstyle [w_3w_1w_2]} & \frac{1}{3} & \frac{1}{3} & 0 & 0 & \frac{1}{3} & 0 \cr
{\scriptstyle [w_3w_2w_1]} & 0 & 0 & \frac{1}{3} & \frac{1}{3} & 0 & \frac{1}{3} \cr
}
\]
(where $[w_{i}w_{j}w_{k}]$ is shorthand for the permutation in $S_{3}$ that
sends $1,2,3$ to $w_{i},w_{j},w_{k}$, respectively).
The eigenvalues of this matrix are known since~\cite{Phatar91} to be
$0,\frac{1}{n},\frac{2}{n},\ldots,\frac{n-2}{n},1$, and the multiplicity of
the eigenvalue $\frac{i}{n}$ is the number of permutations in~$S_{n}$ that
have exactly $i$ fixed points.\footnote{Actually,~\cite{Phatar91} studies a
more general kind of shuffling operators with further parameters $p_{1}
,p_{2},\ldots,p_{n}$, but these can no longer be seen as random walks on a
group and do not appear to fit into a well-behaved \textquotedblleft
somewhere-to-below shuffle\textquotedblright\ family in the way $t_{1}$ does.}
In other words, the eigenvalues of~$t_{1}$ are~$0,1,2,\ldots,\mbox{$n-2$},n$
with multiplicities as just said. Other descriptions of the eigenvalues of the
top-to-random shuffle are given in terms of set partitions~\cite{BiHaRo99} and
in terms of standard Young tableaux~\cite{ReSaWe14}.
\\
\item \textbf{The random-to-below shuffle.}
The \emph{random-to-below shuffle} consists of picking any card randomly (with
uniform probability), and inserting it anywhere weakly below (with uniform
probability). This is the one-sided cycle shuffle governed by the uniform
distribution (i.e., by the probability distribution $P$ with $P(i)=\frac
{1}{n}$ for all $i\in\lbrack n]$). Hence, the random-to-below operator is, in
terms of the somewhere-to-below operators,
\[
\rtb_{n}=\frac{1}{n^{2}}t_{1}+\frac{1}{n(n-1)}t_{2}+\frac{1}{n(n-2)}
t_{3}+\cdots+\frac{1}{n}t_{n}.
\]
A sample transition matrix for the random-to-below shuffle is given here for a
deck with $3$ cards:
\[
\rtb_{3} =
\bordermatrix{ &{\scriptstyle [w_1w_2w_3]} & {\scriptstyle [w_1w_3w_2]} &
{\scriptstyle [w_2w_1w_3]} & {\scriptstyle [w_2w_3w_1]} &
{\scriptstyle [w_3w_1w_2]} & {\scriptstyle [w_3w_2w_1]} \cr
{\scriptstyle [w_1w_2w_3]} & \frac{11}{18} & \frac{1}{6} & \frac{1}{9} & \frac{1}{9} & 0 & 0 \cr
{\scriptstyle [w_1w_3w_2]} & \frac{1}{6} & \frac{11}{18} & 0 & 0 & \frac{1}{9} & \frac{1}{9} \cr
{\scriptstyle [w_2w_1w_3]} & \frac{1}{9} & \frac{1}{9} & \frac{11}{18} & \frac{1}{6} & 0 & 0 \cr
{\scriptstyle [w_2w_3w_1]} & 0 & 0 & \frac{1}{6} & \frac{11}{18} & \frac{1}{9} & \frac{1}{9} \cr
{\scriptstyle [w_3w_1w_2]} & \frac{1}{9} & \frac{1}{9} & 0 & 0 & \frac{11}{18} & \frac{1}{6} \cr
{\scriptstyle [w_3w_2w_1]} & 0 & 0 & \frac{1}{9} & \frac{1}{9} & \frac{1}{6} & \frac{11}{18} \cr
}.
\]
A recently studied shuffle admits a similar description, namely the one-sided
transposition shuffle~\cite{BaCoMR21}, that picks a card uniformly at random
and swaps it with a card chosen uniformly at random among the cards below.
Despite its similar-sounding description, it is not a one-sided cycle shuffle
(unless $n\leq2$), and a striking difference between the two shuffles is that
the matrix of the one-sided transposition shuffle is symmetric, unlike the one
for random-to-below.
\\
\item \textbf{The unweighted one-sided cycle.}
Consider a variation of the problem, in which we pick a somewhere-to-below
move uniformly among the possible moves allowed. That is, we choose (with
uniform probability) two integers $i$ and $j$ in $\left[ n\right] $
satisfying $i\leq j$, and then we apply the cycle $\operatorname*{cyc}
\nolimits_{i,i+1,\ldots,j}$. Thus, the probability of applying the cycle
$\operatorname*{cyc}\nolimits_{i,i+1,\ldots,j}$ is $\frac{2}{n(n+1)}$ for all
$i0$. A moment's
thought reveals that this holds for $n=0$ as well (since $\left[ -1\right]
=\varnothing$), and thus holds for each nonnegative integer $n$.
If $I$ is any set of integers, then $I-1$ will denote the set $\left\{
i-1\ \mid\ i\in I\right\} \subseteq \mathbb{Z}$. For instance,
$\left\{ 2,4,5\right\} -1=\left\{ 1,3,4\right\} $. Note that a set $I$ is
lacunar if and only if $I\cap\left( I-1\right) =\varnothing$.
For any subset $I$ of $\left[ n\right] $, we define the following:
\begin{itemize}
\item We let $\widehat{I}$ be the set $\left\{ 0\right\} \cup I\cup\left\{
n+1\right\} $. We shall refer to $\widehat{I}$ as the \emph{enclosure} of~$I$.
For example, if $n=5$, then $\widehat{\left\{ 2,3\right\} }=\left\{
0,2,3,6\right\} $.
\item For any $\ell\in\left[ n\right] $, we let $m_{I,\ell}$ be the number
\[
\left( \text{smallest element of }\widehat{I}\text{ that is }\geq\ell\right)
-\ell\in\left[ 0,n+1-\ell\right] \subseteq\left[ 0,n\right] .
\]
Those numbers $m_{I, \ell}$ already appeared in Subsection
~\ref{sec.eigenvalues_for_osc}, as they play a crucial role in the expression
of the eigenvalues of the one-sided cycle shuffles.
For example, if $n=5$ and $I=\left\{ 2,3\right\} $, then
\[
\left( m_{I,1},\ m_{I,2},\ m_{I,3},\ m_{I,4},\ m_{I,5}\right) =\left(
1,\ 0,\ 0,\ 2,\ 1\right) .
\]
We note that an $\ell\in\left[ n\right] $ satisfies $m_{I,\ell}=0$ if and
only if $\ell\in\widehat{I}$ (or, equivalently,~$\ell\in I$).
\item We let $I^{\prime}$ be the set $\left[ n-1\right] \setminus\left(
I\cup\left( I-1\right) \right) $. This is the set of all $i\in\left[
n-1\right] $ satisfying $i\notin I$ and $i+1\notin I$. We shall refer to
$I^{\prime}$ as the \emph{non-shadow} of $I$.
For example, if $n=5$, then $\left\{ 2,3\right\} ^{\prime}=\left[ 4\right]
\setminus\left\{ 1,2,3\right\} =\left\{ 4\right\} $.
\end{itemize}
\section{\label{sec.transpositions}The simple transpositions \texorpdfstring{$s_{i}$}{si}}
In this section, we will recall the basic properties of simple transpositions
in the symmetric group $S_{n}$, and use them to rewrite the definition
\eqref{eq.def.tl.deftl} of the somewhere-to-below shuffles.
For any $i\in\left[ n-1\right] $, we let $s_{i}:=\operatorname*{cyc}
\nolimits_{i,i+1}\in S_{n}$. This permutation $s_{i}$ is called a \emph{simple
transposition}. It is well-known that $s_{1},s_{2},\ldots,s_{n-1}$ generate
the group $S_{n}$. Moreover, it is known that two simple transpositions
$s_{i}$ and $s_{j}$ commute whenever $\left\vert i-j\right\vert >1$. This
latter fact is known as \emph{reflection locality}.
It is furthermore easy to see that
\begin{equation}
\operatorname*{cyc}\nolimits_{\ell,\ell+1,\ldots,k}=s_{\ell}s_{\ell+1}\cdots
s_{k-1} \label{eq.cyc-via-ss}
\end{equation}
for each $\ell\leq k$ in $\left[ n\right] $. Thus,~\eqref{eq.def.tl.deftl}
rewrites as follows:
\begin{align}
t_{\ell} & =1+s_{\ell}+s_{\ell}s_{\ell+1}+\cdots+s_{\ell}s_{\ell+1}\cdots
s_{n-1} =\sum_{j=\ell}^{n}s_{\ell}s_{\ell+1}\cdots s_{j-1}
\label{eq.def.tl.deftl-s-sum}
\end{align}
for each $\ell\in\left[ n\right] $.
The following relationship between simple transpositions
follows easily from~\eqref{eq.cyc-via-ss}:
\begin{lemma}
\label{lem.si-into-cyc}Let $\ell\in\left[ n\right] $ and $j\in\left[
n\right] $. Let $i\in\left[ \ell,j-2\right] $. Then,
\[
s_{\ell}s_{\ell+1}\cdots s_{j-1}\cdot s_{i}=s_{i+1}\cdot s_{\ell}s_{\ell
+1}\cdots s_{j-1}.
\]
\end{lemma}
\section{The invariant spaces \texorpdfstring{$F\left( I\right) $}{F(I)}}
\label{sec.invariantspaces}
Recall that our goal is to prove Theorem~\ref{thm.Rcomb-main}, which claims
that the one-sided cycle shuffles are triangularizable. To that end, we will
construct a $\mathbf{k}$-submodule filtration of $\mathbf{k}\left[
S_{n}\right] $ that is preserved by all the somewhere-to-below shuffles. In
this section, we first define a family of submodules $F\left( I\right) $ of
$\mathbf{k}[S_{n}]$, which will later serve as building blocks for this
filtration.
\subsection{Definition}
For any subset $I$ of $\left[ n\right] $, we define the following:
\begin{itemize}
\item We let $\operatorname*{sum}I$ denote the sum of all elements of $I$.
This is an integer with $0\leq\operatorname*{sum}I\leq n\left( n+1\right)
/2$.
\item We let
\[
F\left( I\right) :=\left\{ q\in\mathbf{k}\left[ S_{n}\right]
\ \mid\ qs_{i}=q\text{ for all }i\in I^{\prime}\right\} .
\]
This is a $\mathbf{k}$-submodule of $\mathbf{k}\left[ S_{n}\right] $.
Intuitively, it can be understood as follows: Write each permutation $\pi\in
S_{n}$ as the $n$-tuple $\left[ \pi\left( 1\right) \ \pi\left( 2\right)
\ \ldots\ \pi\left( n\right) \right]$ (this is called \emph{one-line
notation}, and we write it without commas between the entries for the sake
of brevity). Thus, each element $q\in\mathbf{k}\left[ S_{n}\right] $ can
be viewed as a
$\mathbf{k}$-linear combination of such $n$-tuples. The group $S_{n}$ acts on
such $n$-tuples from the right by permuting positions, and thus acts on their
linear combinations by linearity. An element $q\in\mathbf{k}\left[
S_{n}\right] $ belongs to $F\left( I\right) $ if and only if it is
invariant under permuting any two adjacent positions $i$ and $i+1$ that both
lie outside of $I$. We thus call $F\left( I\right) $ an \emph{invariant
space}.
In terms of shuffling operators, one can think of $F(I)$ as the set of all
random decks (i.e., probability distributions on the $n!$ orderings of a deck)
that are \emph{fully shuffled} within each contiguous interval of
$[n]\backslash I$. This is to be understood as follows: Let $q \in F(I)$, and
let $\sigma\in S_{n}$ be a term appearing in $q$ with coefficient $c$. Let
$[i,j]$ be an interval of $[n]$ containing no element of $I$. Then, for any
permutation $\tau\in S_{n}$ that fixes each element of $[n]\backslash[i,j]$,
the coefficient of $\sigma\tau$ in $q$ is also $c$. Moreover, this property
characterizes the elements $q$ of $F(I)$.
\end{itemize}
Note that $F\left( \left[ n\right] \right) =\mathbf{k}\left[
S_{n}\right] $, since $\left[ n\right] ^{\prime}= \varnothing$.
Here are some more examples of the sets $F\left( I\right) $:
\begin{example}
\label{exa.F(I).n=3}Let $n=3$. Then, there are $2^{3}=8$ many subsets $I$ of
$\left[ n\right] =\left[ 3\right] $. We shall compute the non-shadow
$I^{\prime}$ and the invariant space $F\left( I\right) $ for each of them:
\begin{itemize}
\item We have $\varnothing^{\prime}=\left[ 2\right] $ and thus
\begin{align*}
F\left( \varnothing\right) & =\left\{ q\in\mathbf{k}\left[ S_{n}\right]
\ \mid\ qs_{i}=q\text{ for all }i\in\left[ 2\right] \right\} \\
& =\operatorname*{span}\left( \left[ 123\right] +\left[ 132\right]
+\left[ 213\right] +\left[ 231\right] +\left[ 312\right] +\left[
321\right] \right) .
\end{align*}
Here, the notation \textquotedblleft$\operatorname*{span}$\textquotedblright
\ means a $\mathbf{k}$-linear span, whereas the notation $\left[ ijk\right]
$ means the permutation $\sigma\in S_{3}$ that sends $1,2,3$ to $i,j,k$,
respectively. (In our case, we are taking the span of a single vector, but
soon we will see some more complicated spans.)
\item We have $\left\{ 1\right\} ^{\prime}=\left\{ 2\right\} $ and thus
\begin{align*}
F\left( \left\{ 1\right\} \right) & =\left\{ q\in\mathbf{k}\left[
S_{n}\right] \ \mid\ qs_{2}=q\right\} \\
& =\operatorname*{span}\left( \left[ 123\right] +\left[ 132\right]
,\ \ \left[ 213\right] +\left[ 231\right] ,\ \ \left[ 312\right]
+\left[ 321\right] \right) .
\end{align*}
\item We have $\left\{ 3\right\} ^{\prime}=\left\{ 1\right\} $ and thus
\begin{align*}
F\left( \left\{ 3\right\} \right) & =\left\{ q\in\mathbf{k}\left[
S_{n}\right] \ \mid\ qs_{1}=q\right\} \\
& =\operatorname*{span}\left( \left[ 123\right] +\left[ 213\right]
,\ \ \left[ 132\right] +\left[ 312\right] ,\ \ \left[ 231\right]
+\left[ 321\right] \right) .
\end{align*}
\item If $I$ is any of the sets $\left\{ 2\right\} $, $\left\{ 1,2\right\}
$, $\left\{ 1,3\right\} $, $\left\{ 2,3\right\} $ and $\left\{
1,2,3\right\} $, then $I^{\prime}=\varnothing$ and thus
\begin{align*}
F\left( I\right) & =\left\{ q\in\mathbf{k}\left[ S_{n}\right] \right\}
=\mathbf{k}\left[ S_{n}\right] \\
& =\operatorname*{span}\left( \left[ 123\right] ,\ \ \left[ 132\right]
,\ \ \left[ 213\right] ,\ \ \left[ 231\right] ,\ \ \left[ 312\right]
,\ \ \left[ 321\right] \right) .
\end{align*}
\end{itemize}
\end{example}
\begin{example}
\label{exa.F(I).n=4}Let $n=4$. Then, $\left\{ 1\right\} ^{\prime}=\left\{
2,3\right\} $ and thus
\begin{align*}
F\left( \left\{ 1\right\} \right) & =\left\{ q\in\mathbf{k}\left[
S_{n}\right] \ \mid\ qs_{i}=q\text{ for all }i\in\left\{ 2,3\right\}
\right\} \\
& =\operatorname*{span}(\left[ 1234\right] +\left[ 1243\right] +\left[
1324\right] +\left[ 1342\right] +\left[ 1423\right] +\left[ 1432\right]
,\\
& \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \left[ 2134\right] +\left[
2143\right] +\left[ 2314\right] +\left[ 2341\right] +\left[ 2413\right]
+\left[ 2431\right] ,\\
& \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \left[ 3124\right] +\left[
3142\right] +\left[ 3214\right] +\left[ 3241\right] +\left[ 3412\right]
+\left[ 3421\right] ,\\
& \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \left[ 4123\right] +\left[
4132\right] +\left[ 4213\right] +\left[ 4231\right] +\left[ 4312\right]
+\left[ 4321\right] ).
\end{align*}
Here, $\left[ ijk\ell\right] $ means the permutation $\sigma\in S_{4}$ that
sends $1,2,3,4$ to $i,j,k,\ell$, respectively.
\end{example}
In Section~\ref{sec.Filtration}, we shall define a filtration of
$\mathbf{k}\left[ S_{n}\right] $ that requires sorting subsets according to
the sum of their elements. Hence, for each $k\in\mathbb{N}$, we set
\begin{equation}
F\left( i+1$. This means that we are in one of two subcases, which we
consider separately:
\begin{itemize}
\item Let us first consider the subcase when $j*j\geq i_{r}$, $i\notin\left[
i_{k}
,i_{r}\right] $, and~\eqref{pf.thm.tl-FI.K'subI'} yields $i\in
I^{\prime}$. Thus, $qs_{i}=q$ (since $q\in F\left( I\right) $). Now,
\[
qs_{\ell}s_{\ell+1}\cdots s_{j-1}\cdot s_{i} =\underbrace{qs_{i}}_{=q}\cdot
s_{\ell
}s_{\ell+1}\cdots s_{j-1}=qs_{\ell}s_{\ell+1}\cdots s_{j-1}.
\]
We have thus proved Claim 1 in the subcase when $j**i+1$ or, equivalently, $i\leq
j-2$. Combining this with $\ell\leq i_{r}\leq i$, we
obtain $i\in\left[ \ell,j-2\right] $. Hence, Lemma~\ref{lem.si-into-cyc}
yields~$s_{\ell}s_{\ell+1}\cdots s_{j-1}\cdot s_{i}=s_{i+1}\cdot s_{\ell
}s_{\ell+1}\cdots s_{j-1}$. Moreover, from $j\in\left[ i_{r}
,i_{r+1}-1\right] \subseteq\left[ n\right] $, we obtain $j\leq n$, so that
$n\geq j>i+1$. Hence, $i+1i+1$, we obtain
$i+1i+1$.
\end{itemize}
We have now covered both possible subcases. Hence, Claim 1 is proved.]
We have now proved all three Claims 1, 2 and 3. Now, consider the sum
$\sum_{j=i_{r}}^{i_{r+1}-1}qs_{\ell}s_{\ell+1}\cdots s_{j-1}$. This sum
contains both an addend for $j=i$ and an addend for $j=i+1$ (since both $i$
and $i+1$ belong to the interval $\left[ i_{r},i_{r+1}-1\right] $). When we
multiply this sum by $s_{i}$ on the right, the
addend for $j=i$ becomes $qs_{\ell}s_{\ell+1}\cdots s_{i-1}\cdot
s_{i}=qs_{\ell}s_{\ell+1}\cdots s_{i}$ (by Claim 2), whereas the addend for
$j=i+1$ becomes $qs_{\ell}s_{\ell+1}\cdots s_{i}\cdot s_{i}=qs_{\ell}
s_{\ell+1}\cdots s_{i-1}$ (by Claim 3), and all remaining addends stay
unchanged (by Claim 1). Hence, multiplying the sum $\sum_{j=i_{r}}^{i_{r+1}
-1}qs_{\ell}s_{\ell+1}\cdots s_{j-1}$ by~$s_{i}$ on the right merely permutes
its addends (specifically, the addend for $j=i$ is swapped with the addend for
$j=i+1$, while all other addends stay unchanged) and therefore does not change
the sum. In other words, we have
\[
q^{\prime}s_i =\sum_{j=i_{r}}^{i_{r+1}-1}qs_{\ell}s_{\ell+1}\cdots s_{j-1}\cdot
s_{i}
=\sum_{j=i_{r}}^{i_{r+1}-1}qs_{\ell}s_{\ell+1}\cdots s_{j-1} = q^{\prime},
\]
proving
$q^{\prime}s_{i}=q^{\prime}$ in Case 4.
Finally, let us consider Case 5, in which $i\geq i_{r+1}$. Thus,
$i\geq i_{r+1}>i_{r}$, so
that $i\notin\left[ i_{k},i_{r}\right] $. From
\eqref{pf.thm.tl-FI.K'subI'}, we obtain $i\in I^{\prime}$, so that $qs_{i}=q$.
Furthermore, from $i\geq i_{r+1}$, we see
that $s_{i}$ commutes with all the permutations $s_{\ell},s_{\ell+1}
,\ldots,s_{i_{r+1}-2}$ that appear on the right hand side of
\eqref{pf.thm.tl-FI.q'=}. Hence, multiplying the
equality~\eqref{pf.thm.tl-FI.q'=} by $s_{i}$, we find
\begin{align*}
q^{\prime}s_{i} & =\sum_{j=i_{r}}^{i_{r+1}-1}qs_{\ell}s_{\ell
+1}\cdots s_{j-1}\cdot s_{i}=\sum_{j=i_{r}}^{i_{r+1}-1}\underbrace{qs_{i}
}_{=q}\cdot s_{\ell}s_{\ell+1}\cdots s_{j-1}=q^{\prime}.
\end{align*}
We have thus proved $q^{\prime}s_{i}=q^{\prime}$ in Case 5.
We have now proved $q^{\prime}s_{i}=q^{\prime}$ in all five cases.
As explained above, this completes
the proof of $q^{\prime}\in F\left( K\right) $. Therefore, $q^{\prime}\in
F\left( K\right) \subseteq F\left( <\operatorname*{sum}I\right) $. But
this is precisely what we needed to prove. Thus, Theorem~\ref{thm.tl-FI} is
proven.
\end{proof}
\section{The Fibonacci filtration}
\label{sec.Filtration}
In this section, we shall build a filtration of $\mathbf{k}\left[
S_{n}\right] $ by $\mathbf{k}$-submodules that are invariant under the
somewhere-to-below shuffles $R\left( t_{\ell}\right) $, which furthermore
has the property that the latter shuffles act as scalars on the subquotients
of the filtration. This filtration will be built up from the submodules
$F\left( I\right) $ defined in the previous section, and its properties will
rely on Theorem~\ref{thm.tl-FI}.
\subsection{Definition and examples}
Recall from Section~\ref{sec.Lacunarity} that the number of lacunar subsets of
$\left[ n-1\right] $ is the Fibonacci number $f_{n+1}$. Let $Q_{1},Q_{2},\ldots,Q_{f_{n+1}}$ be
all the lacunar subsets of $\left[ n-1\right] $, listed in an
order that satisfies
\begin{equation}
\operatorname*{sum}\left( Q_{1}\right) \leq\operatorname*{sum}\left(
Q_{2}\right) \leq\cdots\leq\operatorname*{sum}\left( Q_{f_{n+1}}\right) .
\label{pf.thm.t-simultri.sum-order}
\end{equation}
Then, define a $\mathbf{k}$-submodule
\[
F_{i}:=F\left( Q_{1}\right) +F\left( Q_{2}\right) +\cdots+F\left(
Q_{i}\right) \ \ \ \ \ \ \ \ \ \ \text{of }\mathbf{k}\left[ S_{n}\right]
\]
for each $i\in\left[ 0,f_{n+1}\right] $ (so that $F_{0}=0$). We claim the following:
\begin{theorem}
\label{thm.t-simultri}\
\begin{enumerate}
\item[\textbf{(a)}] We have
\[
0=F_{0}\subseteq F_{1}\subseteq F_{2}\subseteq\cdots\subseteq F_{f_{n+1}
}=\mathbf{k}\left[ S_{n}\right] .
\]
In other words, the $\mathbf{k}$-submodules $F_{0},F_{1},\ldots,F_{f_{n+1}}$
form a $\mathbf{k}$-module filtration of $\mathbf{k}\left[ S_{n}\right] $.
\item[\textbf{(b)}] We have $F_{i}\cdot t_{\ell}\subseteq F_{i}$ for each
$i\in\left[ 0,f_{n+1}\right] $ and $\ell\in\left[ n\right] $.
\item[\textbf{(c)}] For each $i\in\left[ f_{n+1}\right] $ and $\ell
\in\left[ n\right] $, we have
\[
F_{i}\cdot\left( t_{\ell}-m_{Q_{i},\ell}\right) \subseteq F_{i-1}.
\]
\end{enumerate}
\end{theorem}
We will eventually prove this theorem; we will also show that each $F_{i}$ is
a free $\mathbf{k}$-module, so that its dimension $\dim F_{i}$ (also known
as its rank) is well-defined whenever $\mathbf{k}\neq0$. First, let us tabulate
the dimensions of the $F_{0},F_{1},\ldots,F_{f_{n+1}}$ for some small values
of $n$:
\begin{example}
Let $n=3$. Then, the lacunar subsets of $\left[ n-1\right] $ are
$Q_{1}=\varnothing$ and $Q_{2}=\left\{ 1\right\} $ and $Q_{3}=\left\{
2\right\} $ (this is the only possible ordering that satisfies
\eqref{pf.thm.t-simultri.sum-order}, because no two lacunar subsets of
$\left[ n-1\right] $ have the same sum). The corresponding $F\left(
I\right) $'s have already been computed in Example~\ref{exa.F(I).n=3}. Here
are some properties of the corresponding $F_{i}$'s (note that $F_0 = 0$):
\[
\begin{tabular}
[c]{|c||c|c|c|}\hline
$i$ & $1$ & $2$ & $3$\\\hline\hline
$Q_{i}$ & $\varnothing$ & $\left\{ 1\right\} $ & $\left\{ 2\right\}
$\\\hline
$Q_{i}^{\prime}$ & $\left\{ 1,2\right\} $ & $\left\{ 2\right\} $ &
$\varnothing$\\\hline
$\dim F_{i}$ & $1$ & $3$ & $6$\\\hline
$\dim F_{i}-\dim F_{i-1}$ & $1$ & $2$ & $3$\\\hline
\end{tabular}
\ .
\]
\end{example}
\begin{example}
\label{exa.Qi.4}Let $n=4$. Then, the lacunar subsets of $\left[ n-1\right] $
are $Q_{1}=\varnothing$ and $Q_{2}=\left\{ 1\right\} $ and $Q_{3}=\left\{
2\right\} $ and $Q_{4}=\left\{ 3\right\} $ and $Q_{5}=\left\{ 1,3\right\}
$ (again, there is no other ordering). Here are some properties of the
corresponding $F_{i}$'s:
\[
\begin{tabular}
[c]{|c||c|c|c|c|c|}\hline
$i$ & $1$ & $2$ & $3$ & $4$ & $5$\\\hline\hline
$Q_{i}$ & $\varnothing$ & $\left\{ 1\right\} $ & $\left\{ 2\right\} $ &
$\left\{ 3\right\} $ & $\left\{ 1,3\right\} $\\\hline
$Q_{i}^{\prime}$ & $\left\{ 1,2,3\right\} $ & $\left\{ 2,3\right\} $ &
$\left\{ 3\right\} $ & $\left\{ 1\right\} $ & $\varnothing$\\\hline
$\dim F_{i}$ & $1$ & $4$ & $12$ & $18$ & $24$\\\hline
$\dim F_{i}-\dim F_{i-1}$ & $1$ & $3$ & $8$ & $6$ & $6$\\\hline
\end{tabular}
\ \ \
\]
\end{example}
\begin{example}
Let $n=5$. Then, the lacunar subsets of $\left[ n-1\right] $ are
$Q_{1}=\varnothing$ and $Q_{2}=\left\{ 1\right\} $ and $Q_{3}=\left\{
2\right\} $ and $Q_{4}=\left\{ 3\right\} $ and $Q_{5}=\left\{ 4\right\} $
and $Q_{6}=\left\{ 1,3\right\} $ and $Q_{7}=\left\{ 1,4\right\} $ and
$Q_{8}=\left\{ 2,4\right\} $ (this is one of two possible orderings; another
can be obtained by swapping $Q_{5}$ with $Q_{6}$). Here are some properties of
the corresponding $F_{i}$'s:
\begin{center}\resizebox{\linewidth}{!}{ $
\begin{tabular}
[c]{|c||c|c|c|c|c|c|c|c|}\hline
$i$ & $1$ & $2$ & $3$ & $4$ & $5$ & $6$ & $7$ & $8$\\\hline\hline
$Q_{i}$ & $\varnothing$ & $\left\{ 1\right\} $ & $\left\{ 2\right\} $ &
$\left\{ 3\right\} $ & $\left\{ 4\right\} $ & $\left\{ 1,3\right\} $ &
$\left\{ 1,4\right\} $ & $\left\{ 2,4\right\} $\\\hline
$Q_{i}^{\prime}$ & $\left\{ 1,2,3,4\right\} $ & $\left\{ 2,3,4\right\} $ &
$\left\{ 3,4\right\} $ & $\left\{ 1,4\right\} $ & $\left\{ 1,2\right\} $
& $\left\{ 4\right\} $ & $\left\{ 2\right\} $ & $\varnothing$\\\hline
$\dim F_{i}$ & $1$ & $5$ & $20$ & $40$ & $50$ & $70$ & $90$ & $120$\\\hline
$\dim F_{i}-\dim F_{i-1}$ & $1$ & $4$ & $15$ & $20$ & $10$ & $20$ & $20$ &
$30$\\\hline
\end{tabular}
\ .
$}\end{center}
\end{example}
\begin{example}
Let $n=6$. Then, the lacunar subsets of $\left[ n-1\right] $ (in one of
several orderings) can be found in the following table:
\begin{center}
\resizebox{\linewidth}{!}{ $
\begin{tabular}
[c]{|c||c|c|c|c|c|c|c|c|c|c|c|c|c|}\hline
$i$ & $1$ & $2$ & $3$ & $4$ & $5$ & $6$ & $7$ & $8$ & $9$ & $10$ & $11$ & $12$
& $13$\\\hline\hline
$Q_{i}$ & $\varnothing$ & $\left\{ 1\right\} $ & $\left\{ 2\right\} $ &
$\left\{ 3\right\} $ & $\left\{ 4\right\} $ & $\left\{ 1,3\right\} $ &
$\left\{ 5\right\} $ & $\left\{ 1,4\right\} $ & $\left\{ 1,5\right\} $ &
$\left\{ 2,4\right\} $ & $\left\{ 2,5\right\} $ & $\left\{ 3,5\right\} $
& $\left\{ 1,3,5\right\} $\\\hline
$d_{i}$ & $1$ & $6$ & $30$ & $75$ & $115$ & $160$ & $175$ & $255$ & $300$ &
$420$ & $540$ & $630$ & $720$\\\hline
$\delta_{i}$ & $1$ & $5$ & $24$ & $45$ & $40$ & $45$ & $15$ & $80$ & $45$ &
$120$ & $120$ & $90$ & $90$\\\hline
\end{tabular}
\ ,
$}\end{center}
where we set $d_{i}:=\dim F_{i}$ and $\delta_{i}:=\dim F_{i}-\dim F_{i-1}$ for
brevity.
\end{example}
When $\mathbf{k}$ is a field, Theorem~\ref{thm.t-simultri} entails that the
endomorphisms $R\left( t_{1}\right)$, $R\left( t_{2}\right)$, $\ldots$, $R\left(
t_{n}\right) $ on $\mathbf{k}\left[ S_{n}\right] $ can be simultaneously
triangularized (as endomorphisms of the $\mathbf{k}$-module $\mathbf{k}\left[
S_{n}\right] $). So, in particular, a $\mathbf{k}$-linear combination
$R\left( \lambda_{1}t_{1}+\lambda_{2}t_{2}+\cdots+\lambda_{n}t_{n}\right) $
of $R\left( t_{1}\right) ,R\left( t_{2}\right) ,\ldots,R\left(
t_{n}\right) $ has all its eigenvalues in $\mathbf{k}$. However, we will
later prove this more generally, without assuming that $\mathbf{k}$ is a
field, by explicitly constructing a basis of $\mathbf{k}\left[ S_{n}\right]
$ that triangularizes $R\left( t_{1}\right) ,R\left( t_{2}\right)
,\ldots,R\left( t_{n}\right) $.
\subsection{Properties of non-shadows}
So far, it may seem mysterious that the definition of our filtration $F_{0}
\subseteq F_{1} \subseteq F_{2} \subseteq\cdots\subseteq F_{f_{n+1}}$ relies
only on the $F\left( I\right) $ for the lacunar subsets $I$ of $\left[
n-1\right] $, rather than using the $F\left( I\right) $ for all subsets $I$
of $\left[ n\right] $. The reason for this is the observation
(Corollary~~\ref{cor.FI-lac-2} further below) that the lacunar subsets $I$ of
$\left[ n-1\right] $ are ``enough'' (i.e., the $F\left( I\right) $ for
which $I$ is not a lacunar subset of $\left[ n-1\right] $ ``contribute
nothing new'' to the filtration). More precisely, each $F\left( I\right) $
(for any $I \subseteq\left[ n\right] $) is contained in the sum of the
$F\left( J\right) $ where $J \subseteq\left[ n-1\right] $ is lacunar and
satisfies $\operatorname{sum} J \leq\operatorname{sum} I$.
Before we can prove this, we shall show a few combinatorial properties of non-shadows.
\begin{proposition}
\label{prop.K'subI'}Let $I$ be a subset of $\left[ n\right] $. Let $j\in I$.
Set $K:=\left( I\setminus\left\{ j\right\} \right) \cup\left\{
j-1\right\} $ if~$j>1$, and otherwise set $K:=I\setminus\left\{ j\right\}
$. Then:
\begin{enumerate}
\item[\textbf{(a)}] We have $K^{\prime}\subseteq I^{\prime}\cup\left\{
j\right\} $.
\item[\textbf{(b)}] If $j+1\in I$, then $K^{\prime}\subseteq I^{\prime}$.
\end{enumerate}
\end{proposition}
\begin{proof}
(This is a sketch; see~\cite{s2b1} for details.)
\textbf{(a)} Recall that the non-shadow $I^{\prime}$ of $I$ is obtained by
starting with the set $\left[ n-1\right] $ and removing all the numbers $i$
and $i-1$ for $i\in I$. In particular, the numbers $j$ and $j-1$ have to be
removed, since $j\in I$.
The set $K$ is obtained from $I$ by \textquotedblleft moving the element $j$
one unit to the left\textquotedblright\ (and removing $0$ if necessary). Hence,
its non-shadow $K^{\prime}$ is constructed in the same way as $I^{\prime}$,
but instead of removing the numbers $j$ and $j-1$, we now have to remove the
numbers $j-1$ and $j-2$. Therefore, the only element of $K^{\prime}$ that may
fail to belong to $I^{\prime}$ is $j$. In other words, $K^{\prime}\subseteq
I^{\prime}\cup\left\{ j\right\} $. This proves part \textbf{(a)}.
\textbf{(b)} Assume that $j+1\in I$. Then, $j+1\in K$ as well, so that
$j\notin K^{\prime}$. Hence, part~\textbf{(b)} follows from part \textbf{(a)}.
\end{proof}
\begin{proposition}
\label{prop.FI-lac}Let $I\subseteq\left[ n\right] $. Assume that $I$ is not
a lacunar subset of $\left[ n-1\right] $. Then, there exists a subset $K$ of
$\left[ n\right] $ such that $\operatorname*{sum}K<\operatorname*{sum}I$ and
$K^{\prime}\subseteq I^{\prime}$.
\end{proposition}
\begin{proof}
We have assumed that $I$ is not a lacunar subset of $\left[ n-1\right] $.
Thus, we are in one of the following two cases:
\textit{Case 1:} The set $I$ is not a subset of $\left[ n-1\right] $.
\textit{Case 2:} The set $I$ is not lacunar.
Let us first consider Case 1. In this case, the set $I$ is not a subset of
$\left[ n-1\right] $. Hence,~$n\in I$. Setting $K:=\left( I\setminus\left\{ n\right\} \right) \cup\left\{
n-1\right\} $ (or just $K:=I\setminus\left\{ n\right\} $ in the case when~$n=1$),
one can easily verify that
$\operatorname*{sum}K<\operatorname*{sum}I$
and $K^{\prime}\subseteq I^{\prime}$.
Hence, Proposition~\ref{prop.FI-lac} is proved in Case 1.
Let us now consider Case 2. In this case, the set $I$ is not lacunar. In other
words, $I$ contains two consecutive integers $q-1$ and $q$. Consider these
$q-1$ and $q$. Let $K:=\left( I\setminus\left\{ q-1\right\} \right)
\cup\left\{ q-2\right\} $ (or just $K:=I\setminus\left\{ q-1\right\} $ in
the case when $q-2=0$). Then, $\operatorname*{sum}K<\operatorname*{sum}I$
(similarly to Case 1). However, Proposition~\ref{prop.K'subI'} \textbf{(b)}
(applied to $j=q-1$) yields $K^{\prime}\subseteq I^{\prime}$ (since $q-1\in I$
and $\left( q-1\right) +1=q\in I$). Hence, Proposition~\ref{prop.FI-lac} is
proved in Case 2.
We now have proved Proposition~\ref{prop.FI-lac} in both Cases 1 and 2.
\end{proof}
Roughly speaking, Proposition~~\ref{prop.FI-lac} tells us that if a subset $I$
of $\left[ n \right] $ is not a lacunar subset of $\left[ n-1\right] $,
then we can replace it by a subset $K$ that has a smaller sum and a non-shadow that is
contained in that of $I$. The latter subset $K$ may or may not be a lacunar
subset of $\left[ n-1 \right] $. If it is not, then we can apply
Proposition~~\ref{prop.FI-lac} to it again. Repeatedly applying
Proposition~~\ref{prop.FI-lac} like this (and observing that the sum of a
subset of $\ive{n}$ cannot keep decreasing forever),
we obtain the following corollary:
\begin{corollary}
\label{cor.FI-lac-2}Let $I\subseteq\left[ n\right] $. Then, there exists a
lacunar subset $J$ of $\left[ n-1\right] $ such that $\operatorname*{sum}
J\leq\operatorname*{sum}I$ and $J^{\prime}\subseteq I^{\prime}$.
\end{corollary}
Corollary~~\ref{cor.FI-lac-2} is largely responsible for the fact that the
filtration in Theorem~~\ref{thm.t-simultri} uses only the lacunar subsets of
$\left[ n-1 \right] $ (rather than all subsets of $\left[ n \right] $).
Next, we observe a fact that follows directly from the definition of
$F\left( I\right) $ (given at the beginning of
Section~\ref{sec.invariantspaces}): If $A$ and $B$ are two subsets
of $\left[ n\right] $ satisfying $B^{\prime}\subseteq A^{\prime}$, then
$F\left( A\right) \subseteq F\left( B\right)$.
As a consequence, the lacunar subset $J$ in Corollary~~\ref{cor.FI-lac-2}
satisfies $F\tup{I} \subseteq F\tup{J}$.
Thus, for any given $k \in \mathbb{N}$, the sum on the right hand
side of~\eqref{eq.def.Flessk} has many redundant addends, and we can
restrict this sum to just those addends for which $I$ is a lacunar subset
of $\ive{n-1}$. In other words:
\begin{corollary}
\label{cor.FI-lac-cor}Let $k\in\mathbb{N}$. Then,
\[
F\left( w\left( i+1\right) $. This set is denoted by $\operatorname*{Des}w$.
For example, the permutation in $S_{4}$ that sends $1,2,3,4$ to $3,2,4,1$ has
descent set $\left\{ 1,3\right\} $.
\item We define a total order $<$ on the set $S_{n}$ as follows: If $u$ and
$v$ are two distinct permutations in $S_{n}$, then we say that $ux. \label{pf.prop.aw.basis-QI.c2.pf.0}
\end{equation}
We want to show that $q\in\operatorname*{span}\left( \left( a_{w}\right)
_{w\in S_{n};\ I\subseteq\operatorname*{Des}w}\right) $.
We are in one of the following two cases:
\textit{Case 1:} We have $I\not \subseteq \operatorname*{Des}x$.
\textit{Case 2:} We have $I\subseteq\operatorname*{Des}x$.
First, let us consider Case 1. In this case, we have $I\not \subseteq
\operatorname*{Des}x$. Hence, there exists some $k\in I$ such that
$k\notin\operatorname*{Des}x$. Consider this $k$. Then, $k\in I\subseteq
\left[ n-1\right] $. Hence, $x\left( k\right) \leq x\left( k+1\right) $
(since $k\notin\operatorname*{Des}x$), so that $x\left( k\right) x$. Thus,
\eqref{pf.prop.aw.basis-QI.c2.pf.0} yields $\left[
xs_{k}\right] q=0$.
On the other hand, $q\in Z\left( I\right) $, and therefore $qs_{i}=q$ for
all $i\in I$ (by the definition of $Z\left( I\right) $). Applying this to
$i=k$, we obtain $qs_{k}=q$ (since $k\in I$). However,
\eqref{pf.prop.aw.basis-QI.coeff1}
yields
\begin{align*}
\left[ x\right] \left( qs_{k}\right) & =\left[ xs_{k}^{-1}\right]
q=\left[ xs_{k}\right] q =0.
\end{align*}
In view of $qs_{k}=q$, this rewrites as $\left[ x\right] q=0$. In other
words, $\left[ w\right] q=0$ holds for~$w=x$. Combining this with
\eqref{pf.prop.aw.basis-QI.c2.pf.0}, we obtain
\[
\left[ w\right] q=0\ \ \ \ \ \ \ \ \ \ \text{for every }w\in S_{n}\text{
satisfying }w\geq x.
\]
Hence, $q\in\operatorname*{span}\left( \left( w\right) _{w\in S_{n}
;\ w0$.
Now, from $I\setminus K\subseteq\left( K\setminus I\right) -1$, we obtain
\[
\operatorname*{sum}\left( I\setminus K\right) \leq\operatorname*{sum}\left(
\left( K\setminus I\right) -1\right) =\operatorname*{sum}\left( K\setminus
I\right) -\underbrace{\left\vert K\setminus I\right\vert }_{>0}
<\operatorname*{sum}\left( K\setminus I\right) .
\]
Therefore, the right hand side of~\eqref{pf.lem.lac-sum-less2.sumI=} is
smaller than that of~\eqref{pf.lem.lac-sum-less2.sumK=}
(since $K \cap I = I \cap K$).
Thus, the same holds for the left hand sides.
That is, we have $\operatorname*{sum}
I<\operatorname*{sum}K$. This proves Lemma
~\ref{lem.lac-sum-less2}.
\end{proof}
\begin{lemma}
\label{lem.lac-IR}Let $I$ be a subset of $\left[ n\right] $. Let $j\in I$.
Then, there exists a lacunar subset~$K$ of $\left[ n-1\right] $ satisfying
$\operatorname*{sum}K<\operatorname*{sum}I$ and $K^{\prime}\subseteq
I^{\prime}\cup\left\{ j\right\} $.
\end{lemma}
\begin{proof}
Set $R:=\left( I\setminus\left\{ j\right\} \right) \cup\left\{
j-1\right\} $ if $j>1$, and otherwise set $R:=I\setminus\left\{ j\right\}
$. Thus, the set $R$ is obtained from $I$ by replacing the element $j$ by the smaller element~$j-1$ (unless~$j=1$, in
which case $j$ is just removed). In either case, we therefore have
$\operatorname*{sum}R<\operatorname*{sum}I$. Also, it is easy to see that
$R\subseteq\left[ n\right] $ and $R^{\prime}\subseteq I^{\prime}\cup\left\{
j\right\} $ (by Proposition~\ref{prop.K'subI'} \textbf{(a)}, applied to
$K=R$). Thus, Corollary~\ref{cor.FI-lac-2} (applied to $R$ instead of $I$)
yields that there exists a lacunar subset $J$ of $\left[ n-1\right] $ such
that $\operatorname*{sum}J\leq\operatorname*{sum}R$ and $J^{\prime}\subseteq
R^{\prime}$. Consider this $J$. Then, $\operatorname*{sum}J\leq
\operatorname*{sum}R<\operatorname*{sum}I$ and $J^{\prime}\subseteq R^{\prime
}\subseteq I^{\prime}\cup\left\{ j\right\} $. Hence, there exists a lacunar
subset $K$ of $\left[ n-1\right] $ satisfying $\operatorname*{sum}
K<\operatorname*{sum}I$ and $K^{\prime}\subseteq I^{\prime}\cup\left\{
j\right\} $ (namely, $K=J$). This proves Lemma~\ref{lem.lac-IR}.
\end{proof}
\begin{proof}
[Proof of Proposition~\ref{prop.Qind.equivalent}.]$\Longrightarrow:$ Assume
that $\operatorname*{Qind}w=i$.\ We must prove that $Q_{i}^{\prime}
\subseteq\operatorname*{Des}w\subseteq\left[ n-1\right] \setminus Q_{i}$.
In view of the definition of the $Q$-index, our assumption
$\operatorname*{Qind}w=i$ means that~$Q_{i}^{\prime}\subseteq
\operatorname*{Des}w$ and that $i$ is the smallest element of $\left[
f_{n+1}\right] $ with this property. The latter statement means that
\begin{equation}
Q_{k}^{\prime}\not \subseteq \operatorname*{Des}w\ \ \ \ \ \ \ \ \ \ \text{for
each }kj$, we
have $\mu_{k,j}=0$.
\end{statement}
[\textit{Proof of Claim 1:} Let $j\in\left[ n!\right] $. We must prove that
$\mu_{j,j}=g_{\operatorname*{Qind}\left( w_{j}\right) }$.
The equality~\eqref{pf.cor.eigen.spec.1} shows that $\mu_{j,j}$ is the
coefficient of $a_{w_{j}}$ when $\rho\left( a_{w_{j}}\right) $ is expanded
as a $\mathbf{k}$-linear combination of the a-basis.
Let $i:=\operatorname*{Qind}\left( w_{j}\right) $. Then, Equation
\eqref{pf.cor.eigen.spec.2} becomes
\begin{align*}
& \rho\left( a_{w_{j}}\right) =\sum_{\ell=1}^{n}\lambda_{\ell} a_{w_{j}}t_{\ell}\\
& =\sum_{\ell=1}^{n}\lambda_{\ell}m_{Q_{i},\ell}a_{w_{j}} \\
& \qquad +\left( \text{a
}\mathbf{k}\text{-linear combination of }a_{v}\text{'s for }v\in S_{n}\text{
satisfying }\operatorname*{Qind}v**j$. We
must prove that $\mu_{k,j}=0$.
The equality~\eqref{pf.cor.eigen.spec.1} shows that $\mu_{k,j}$ is the
coefficient of $a_{w_{k}}$ when $\rho\left( a_{w_{j}}\right) $ is expanded
as a $\mathbf{k}$-linear combination of the a-basis. Thus, our goal is to show
that this coefficient is $0$.
Let $i:=\operatorname*{Qind}\left( w_{j}\right) $. Just as in the proof of
Claim 1, we obtain the equality~\eqref{pf.cor.eigen.spec.3}, which expands
$\rho\left( a_{w_{j}}\right) $ as a $\mathbf{k}$-linear combination of the
a-basis. The right hand side of this equality is clearly a $\mathbf{k}$-linear
combination of the a-basis. The element $a_{w_{k}}$ of the a-basis does not
appear in this combination (since $k>j$ and
\eqref{pf.cor.eigen.spec.qind-leq} ensure that $w_{k}$ is neither
$w_{j}$ nor a permutation $v\in S_{n}$ satisfying $\operatorname*{Qind}
v**w\left( j+1\right) \ \ \ \ \ \ \ \ \ \ \text{for all
}j\in Q_{i}^{\prime}.
\]
\item[\textbf{(c)}] Write the set $Q_{i}$ in the form $Q_{i}=\left\{
i_{1}w\left(
j+1\right) \text{ for all }j\in Q_{i}^{\prime}\right) \text{ and }\left(
w\left( j\right) < w\left( j+1\right) \text{ for all }j\in
Q_{i}\right) \right) .
\end{align*}
Thus, $\delta_{i}$ equals the number of all permutations $w\in S_{n}$
satisfying
\[
\left( w\left( j\right) w\left( j+1\right)
\text{ for all }j\in Q_{i}^{\prime}\right)
\]
(because $\delta_{i}$ was defined as the number of permutations $w\in
S_{n}$ satisfying $\operatorname*{Qind}w=i$). This proves Theorem
~\ref{thm.deltai.main} \textbf{(b)}.
\textbf{(c)} We introduce a bit of terminology: If $K=\left[ u,v\right] $ is
an interval of $\mathbb{Z}$, and if $T$ is an arbitrary subset of $\mathbb{Z}
$, then a map $f:K\rightarrow T$ will be called \emph{up-decreasing} if it
satisfies
\[
f\left( u\right) f\left( u+2\right) >f\left(
u+3\right) >\cdots>f\left( v\right)
\]
(that is, if it is increasing on $\left[ u,u+1\right] $ and decreasing on
$\left[ u+1,v\right] $). For instance, the map $\left[ 5\right]
\rightarrow\left[ -3,0\right] $ that sends each $k\in\left[ 5\right] $ to
$-\left\vert k-2\right\vert $ is up-decreasing.
The following fact is easy to see:
\begin{statement}
\textit{Claim 1:} Let $h\geq2$ be an integer. Let $K=\left[ u,v\right] $ be
an interval of $\mathbb{Z}$ having size $\left\vert K\right\vert =v-u+1=h$.
Let $T$ be a subset of $\mathbb{Z}$ that has size $h$. Then, the number of
up-decreasing bijections $f:K\rightarrow T$ is $h-1$.
\end{statement}
[\textit{Proof of Claim 1:} We assume, without loss of generality,
that $K=\left[ h\right] $ and
$T=\left[ h\right] $, because we can otherwise rename the elements of $K$
and of $T$ while preserving their relative order. Thus, the bijections
$f:K\rightarrow T$ are precisely the permutations of $\left[ h\right] $, and
we must show that the number of up-decreasing permutations of $\left[
h\right] $ is $h-1$.
But this is easy to show: An up-decreasing permutation of $\left[ h\right] $
is a permutation $f$ of $\left[ h\right] $ satisfying $f\left( 1\right)
f\left( 3\right) >f\left( 4\right) >\cdots>f\left(
h\right) $. Thus, any up-decreasing permutation $f$ of $\left[ h\right] $
is uniquely determined by its first value $f\left( 1\right) $, because its
remaining values must be the remaining elements of $\left[ h\right] $ in
decreasing order (to ensure that $f\left( 2\right) >f\left( 3\right)
>f\left( 4\right) >\cdots>f\left( h\right) $ holds). The first value
$f\left( 1\right) $ cannot be $h$ (since this would violate $f\left(
1\right) w\left( j+1\right) \ \ \ \ \ \ \ \ \ \ \text{for all
}j\in Q_{i}^{\prime}. \label{pf.thm.deltai.main.c.3b}
\end{equation}
In view of~\eqref{pf.thm.deltai.main.c.Qi=} and
\eqref{pf.thm.deltai.main.c.Qi'=}, we can rewrite this as follows: $\delta
_{i}$ is the number of all permutations $w\in S_{n}$ that satisfy
\[
w\left( 1\right) >w\left( 2\right) >w\left( 3\right) >\cdots>w\left(
i_{1}-1\right)
\]
and
\[
w\left( i_{k-1}\right) w\left( i_{k-1}
+2\right) >w\left( i_{k-1}+3\right) >\cdots>w\left( i_{k}-1\right)
\]
for each $k\in\left[ 2,p+1\right] $. In other words, $\delta_{i}$ is the
number of all permutations $w\in S_{n}$ such that the restriction
$w\mid_{J_{1}}$ is strictly decreasing whereas the restrictions $w\mid_{J_{2}}$, $w\mid_{J_{3}}$, $\ldots$,$w\mid_{J_{p+1}}$ are up-decreasing (since
$J_{k}=\left[ i_{k-1},\ i_{k}-1\right] $ for each $k\in\left[ p+1\right]
$). We can construct such a permutation $w$ as follows:
\begin{itemize}
\item First, we choose the \textbf{sets} $w\left( J_{k}\right) $ for all
$k\in\left[ p+1\right] $. In doing so, we must ensure that these $p+1$ sets
are disjoint and cover the entire set $\left[ n\right] $, and have the size
$\left\vert w\left( J_{k}\right) \right\vert =\left\vert J_{k}\right\vert
=j_{k}$ for each $k$. Thus, there are $\dbinom{n}{j_{1},j_{2},\ldots,j_{p+1}}$
many options at this step.
\item At this point, the restriction $w\mid_{J_{1}}$ is already uniquely
determined, since $w\mid_{J_{1}}$ has to be strictly decreasing and its image
$w\left( J_{1}\right) $ is already chosen.
\item Now, for each $k\in\left[ 2,p+1\right] $, we choose the restriction
$w\mid_{J_{k}}$. This restriction has to be an up-decreasing bijection from
the interval $J_{k}$ to the (already chosen) set $w\left( J_{k}\right) $,
which has size $\left\vert w\left( J_{k}\right) \right\vert =\left\vert
J_{k}\right\vert =j_{k}$; thus, by Claim 1 (applied to $h=j_{k}$ and $K=J_{k}$
and $T=w\left( J_{k}\right) $), there are $j_{k}-1$ options for this
restriction $w\mid_{J_{k}}$ (since~\eqref{pf.thm.deltai.main.c.geq2} yields
$j_{k}\geq2$). Hence, in total, we have $\prod\limits_{k=2}^{p+1}\left(
j_{k}-1\right) $ options at this step.
\end{itemize}
\noindent Altogether, the total number of possibilities to perform this
construction is thus $\dbinom{n}{j_{1},j_{2},\ldots,j_{p+1}}\cdot
\prod\limits_{k=2}^{p+1}\left( j_{k}-1\right) $. Hence,
\[
\delta_{i}=\dbinom{n}{j_{1},j_{2},\ldots,j_{p+1}}\cdot
\prod\limits_{k=2}^{p+1}\left( j_{k}-1\right) .
\]
This proves Theorem~\ref{thm.deltai.main} \textbf{(c)}.
\textbf{(d)} Define the integers $i_{0},i_{1},\ldots,i_{p+1}$ and $j_{1}
,j_{2},\ldots,j_{p+1}$ as in Theorem~\ref{thm.deltai.main} \textbf{(c)}. Then,
we have $j_{k}\geq2$ for each $k\in\left[ 2,p+1\right] $ (in fact, this is
the inequality~\eqref{pf.thm.deltai.main.c.geq2}, which has been shown in our
above proof of Theorem~\ref{thm.deltai.main} \textbf{(c)}).
The definition of a multinomial coefficient yields
\[
\dbinom{n}{j_{1},j_{2},\ldots,j_{p+1}}=\dfrac{n!}{j_{1}!j_{2}!\cdots j_{p+1}
!}=\dfrac{n!}{\prod\limits_{k=1}^{p+1}j_{k}!}
=\dfrac{n!}{j_{1}!\prod\limits_{k=2}^{p+1} j_{k}!}.
\]
Hence, we can rewrite~\eqref{eq.thm.deltai.main.c.eq} as
\[
\delta_{i}=\dfrac{n!}{j_{1}!\prod\limits_{k=2}^{p+1}j_{k}!}\cdot
\prod\limits_{k=2}^{p+1}\left( j_{k}-1\right)
=\dfrac{n!}{j_{1}!\cdot \prod\limits_{k=2}^{p+1}\left(
j_{k}!\diagup\left( j_{k}-1\right) \right) }=\dfrac{n!}{j_{1}!\cdot
\prod\limits_{k=2}^{p+1}
\left( \left( j_{k}-2\right) !\cdot j_{k}\right) }
\]
(since a straightforward computation shows that each $k\in\left[
2,p+1\right] $ satisfies $j_{k}!\diagup\left( j_{k}-1\right) =\left(
j_{k}-2\right) !\cdot j_{k}$).
Thus, $\delta_{i}\mid n!$ (since the denominator
$j_{1}!\cdot\prod\limits_{k=2}
^{p+1}\left( \left( j_{k}-2\right) !\cdot j_{k}\right) $ in this equality
is clearly an integer). This proves Theorem~\ref{thm.deltai.main} \textbf{(d)}.
\end{proof}
\subsection{The multiplicities of the eigenvalues}
Finally, we can find the algebraic multiplicities of the eigenvalues of the
endomorphism $R\left( \lambda_{1}t_{1}+\lambda_{2}t_{2}+\cdots+\lambda
_{n}t_{n}\right) $ (when $\mathbf{k}$ is a field and $\lambda_{1},\lambda
_{2},\ldots,\lambda_{n}\in\mathbf{k}$ are arbitrary). Roughly speaking, we
want to claim that each eigenvalue $\lambda_{1}m_{I,1}+\lambda_{2}
m_{I,2}+\cdots+\lambda_{n}m_{I,n}$ (where $I\subseteq\left[ n-1\right] $ is
a lacunar subset) has algebraic multiplicity $\delta_{i}$, where $i\in\left[
f_{n+1}\right] $ is chosen such that~$I=Q_{i}$ (and where $\delta_{i}$ is as
in Theorem~\ref{thm.deltai.main}). This is not fully precise; indeed, if some
lacunar subsets $I\subseteq\left[ n-1\right] $ produce the same eigenvalues
$\lambda_{1}m_{I,1}+\lambda_{2}m_{I,2}+\cdots+\lambda_{n}m_{I,n}$, then their
respective $\delta_{i}$'s need to be added together to form the right
algebraic multiplicity. The technically correct statement of our claim is thus
as follows:
\begin{theorem}
\label{thm.eigen.mult}Assume that $\mathbf{k}$ is a field. Let $\lambda
_{1},\lambda_{2},\ldots,\lambda_{n}\in\mathbf{k}$. For each $i\in\left[
f_{n+1}\right] $, let $\delta_{i}$ be the number of all permutations $w\in
S_{n}$ satisfying $\operatorname*{Qind}w=i$. For each $i\in\left[
f_{n+1}\right] $, we set
\[
g_{i}:=\lambda_{1}m_{Q_{i},1}+\lambda_{2}m_{Q_{i},2}+\cdots+\lambda
_{n}m_{Q_{i},n}=\sum_{\ell=1}^{n}\lambda_{\ell}m_{Q_{i},\ell}\in\mathbf{k}.
\]
Let $\kappa\in\mathbf{k}$ be arbitrary. Then, the algebraic multiplicity of
$\kappa$ as an eigenvalue of~$R\left( \lambda_{1}t_{1}+\lambda_{2}
t_{2}+\cdots+\lambda_{n}t_{n}\right) $ equals
\[
\sum_{\substack{i\in\left[ f_{n+1}\right] ;\\g_{i}=\kappa}}\delta_{i}.
\]
\end{theorem}
\begin{proof}
We shall use the notations introduced in the proof of Corollary
~\ref{cor.eigen.spec}. In that proof, we have shown that the matrix $M$ is upper-triangular.
Recall that the eigenvalues of a triangular matrix are its diagonal entries,
and moreover, the algebraic multiplicity of an eigenvalue is the number of
times that it appears on the main diagonal. We can apply this fact to the
matrix $M$ (since $M$ is upper-triangular). Using Claim 1 from the proof of
Corollary~\ref{cor.eigen.spec}, we recall that the entries on the diagonal of $M$
satisfy $\mu_{j,j}=g_{\operatorname*{Qind}\left( w_{j}\right)}$ for each
$j\in\left[ n!\right]$. We thus conclude that
\begin{align*}
& \left( \text{the algebraic multiplicity of }\kappa\text{ as an eigenvalue
of }M\right) \\
& =\left( \text{the number of times that }\kappa\text{ appears on the main
diagonal of }M\right) \\
& =\left( \text{the number of }j\in\left[ n!\right] \text{ such that }
\mu_{j,j}=\kappa\right) \ \ \ \ \ \ \ \ \ \ \left( \text{since }M=\left(
\mu_{i,j}\right) _{i,j\in\left[ n!\right] }\right) \\
& =\left( \text{the number of }j\in\left[ n!\right] \text{ such that
}g_{\operatorname*{Qind}\left( w_{j}\right) }=\kappa\right) \\
& =\left( \text{the number of }w\in S_{n}\text{ such that }
g_{\operatorname*{Qind}w}=\kappa\right) \\
& =\sum_{\substack{i\in\left[ f_{n+1}\right] ;\\g_{i}=\kappa}
}\left( \text{the number of }w\in S_{n}\text{ such that
}\operatorname*{Qind}w=i\right)\\
& =\sum_{\substack{i\in\left[ f_{n+1}\right] ;\\g_{i}=\kappa}}\delta_{i}.
\end{align*}
This proves Theorem~\ref{thm.eigen.mult}.
\end{proof}
\section{\label{sect.furtheralg}Further algebraic consequences}
In this section, we shall derive some more corollaries from the above. To be
more specific, we first study the algebraic properties of the antipode of the
one-sided cycle shuffle $\lambda_{1}t_{1}+\lambda_{2}t_{2}+\cdots+\lambda
_{n}t_{n}$; this corresponds to the reversal of the corresponding Markov
chain. Then, we discuss the endomorphism $L\left( \lambda_{1}t_{1}
+\lambda_{2}t_{2}+\cdots+\lambda_{n}t_{n}\right) $ corresponding to left
multiplication (as opposed to right multiplication, which we have studied
before) by the shuffle. We next use our notions of $Q$-index and non-shadow to
subdivide the Boolean algebra of the set $\left[ n-1 \right] $ into Boolean
intervals indexed by the lacunar subsets of $\left[ n-1 \right] $. Finally,
we explore what known results about the top-to-random shuffle our results can
and cannot prove.
\subsection{\label{subsect.furtheralg.btr}Below-to-somewhere shuffles}
We have so far been considering the somewhere-to-below shuffles $t_{1}
,t_{2},\ldots,t_{n}$, which are sums of cycles. If we invert these cycles
(i.e., reverse the order of cycling), we obtain new elements of $\mathbf{k}
\left[ S_{n}\right] $, which may be called the \textquotedblleft
below-to-somewhere shuffles\textquotedblright. Here is their precise definition:
For each $\ell\in\left[ n\right] $, we define the element
\begin{equation}
t_{\ell}^{\prime}:=\operatorname*{cyc}\nolimits_{\ell}+\operatorname*{cyc}
\nolimits_{\ell+1,\ell}+\operatorname*{cyc}\nolimits_{\ell+2,\ell+1,\ell
}+\cdots+\operatorname*{cyc}\nolimits_{n,n-1,\ldots,\ell}\in\mathbf{k}\left[
S_{n}\right] . \label{eq.def.tl.deftl'}
\end{equation}
In terms of card shuffling, this element $t_{\ell}^{\prime}$ corresponds to
randomly picking a card from the bottommost $n-\ell+1$ positions in the deck
(with uniform probabilities) and moving it to position $\ell$. Thus, we call
$t_{1}^{\prime},t_{2}^{\prime},\ldots,t_{n}^{\prime}$ the
\emph{below-to-somewhere shuffles}. The first of them, $t_{1}^{\prime}$, is
known as the \emph{random-to-top shuffle} (as it picks a random card and
surfaces it to the top of the deck).
It is natural to ask whether our above properties of $t_{1},t_{2},\ldots
,t_{n}$ have analogues for these new elements $t_{1}^{\prime},t_{2}^{\prime
},\ldots,t_{n}^{\prime}$. For example, an analogue of Theorem
~\ref{thm.eigen.annih-pol} holds:
\begin{theorem}
\label{thm.eigen.annih-pol'}Let $\lambda_{1},\lambda_{2},\ldots,\lambda_{n}
\in\mathbf{k}$. Let $t^{\prime}:=\lambda_{1}t_{1}^{\prime}+\lambda_{2}
t_{2}^{\prime}+\cdots+\lambda_{n}t_{n}^{\prime}$. Then,
\[
\prod\limits_{\substack{I\subseteq\left[ n-1\right] \text{ is}\\
\text{lacunar}
}}\left( t^{\prime}-\left( \lambda_{1}m_{I,1}+\lambda_{2}m_{I,2}
+\cdots+\lambda_{n}m_{I,n}\right) \right) =0.
\]
\end{theorem}
Theorem~\ref{thm.eigen.annih-pol'} can actually be deduced from Theorem
~\ref{thm.eigen.annih-pol} pretty easily:
Let $S$ be the $\mathbf{k}$-linear map $\mathbf{k}\left[ S_{n}\right]
\rightarrow\mathbf{k}\left[ S_{n}\right] $ that sends each permutation $w\in
S_{n}$ to its inverse $w^{-1}$. This map $S$ is known as the \emph{antipode}
of the
group algebra $\mathbf{k}\left[ S_{n}\right] $ (see, e.g.,~\cite[Example
2.2.8]{Meusbu21}); it is an involution (i.e., it satisfies $S\circ
S=\operatorname*{id}$) and a $\mathbf{k}$-algebra antihomomorphism (i.e., it
is $\mathbf{k}$-linear and satisfies $S\left( 1\right) =1$ and $S\left(
uv\right) =S\left( v\right) \cdot S\left( u\right) $ for all
$u,v\in\mathbf{k}\left[ S_{n}\right] $). For any $k$ distinct elements
$i_{1},i_{2},\ldots,i_{k}$ of $\left[ n\right] $, we have
\begin{align}
S\left( \operatorname*{cyc}\nolimits_{i_{1},i_{2},\ldots,i_{k}}\right) &
=\left( \operatorname*{cyc}\nolimits_{i_{1},i_{2},\ldots,i_{k}}\right)
^{-1}\ \ \ \ \ \ \ \ \ \ \left( \text{by the definition of }S\right)
\nonumber\\
& =\operatorname*{cyc}\nolimits_{i_{k},i_{k-1},\ldots,i_{1}}.
\label{eq.bts.Scyc}
\end{align}
Hence, for each $\ell\in\left[ n\right] $, we have
\begin{align}
S\left( t_{\ell}\right) & =S\left( \operatorname*{cyc}\nolimits_{\ell
}+\operatorname*{cyc}\nolimits_{\ell,\ell+1}+\operatorname*{cyc}
\nolimits_{\ell,\ell+1,\ell+2}+\cdots+\operatorname*{cyc}\nolimits_{\ell
,\ell+1,\ldots,n}\right) \ \ \ \ \ \ \ \ \ \ \left( \text{by
\eqref{eq.def.tl.deftl}}\right) \nonumber\\
& =S\left( \operatorname*{cyc}\nolimits_{\ell}\right) +S\left(
\operatorname*{cyc}\nolimits_{\ell,\ell+1}\right) +S\left(
\operatorname*{cyc}\nolimits_{\ell,\ell+1,\ell+2}\right) +\cdots+S\left(
\operatorname*{cyc}\nolimits_{\ell,\ell+1,\ldots,n}\right) \nonumber\\
& =\operatorname*{cyc}\nolimits_{\ell}+\operatorname*{cyc}\nolimits_{\ell
+1,\ell}+\operatorname*{cyc}\nolimits_{\ell+2,\ell+1,\ell}+\cdots
+\operatorname*{cyc}\nolimits_{n,n-1,\ldots,\ell}\ \ \ \ \ \ \ \ \ \ \left(
\text{by~\eqref{eq.bts.Scyc}}\right) \nonumber\\
& =t_{\ell}^{\prime}\ \ \ \ \ \ \ \ \ \ \left( \text{by
\eqref{eq.def.tl.deftl'}}\right) . \label{eq.def.Stl}
\end{align}
Thus, we can obtain properties of $t_{1}^{\prime},t_{2}^{\prime},\ldots
,t_{n}^{\prime}$ by applying the map $S$ to corresponding properties of
$t_{1},t_{2},\ldots,t_{n}$. In particular, we can obtain Theorem
~\ref{thm.eigen.annih-pol'} this way:
\begin{proof}
[Proof of Theorem~\ref{thm.eigen.annih-pol'}.]Let $t:=\lambda_{1}t_{1}
+\lambda_{2}t_{2}+\cdots+\lambda_{n}t_{n}$. Thus,
\begin{align*}
S\left( t\right) & =S\left( \lambda_{1}t_{1}+\lambda_{2}t_{2}
+\cdots+\lambda_{n}t_{n}\right) \\
& =\lambda_{1}S\left( t_{1}\right) +\lambda_{2}S\left( t_{2}\right)
+\cdots+\lambda_{n}S\left( t_{n}\right) \ \ \ \ \ \ \ \ \ \ \left(
\text{since }S\text{ is }\mathbf{k}\text{-linear}\right) \\
& =\lambda_{1}t_{1}^{\prime}+\lambda_{2}t_{2}^{\prime}+\cdots+\lambda
_{n}t_{n}^{\prime}\ \ \ \ \ \ \ \ \ \ \left( \text{by (~\ref{eq.def.Stl}
)}\right) \\
& =t^{\prime}\ \ \ \ \ \ \ \ \ \ \left( \text{by the definition of
}t^{\prime}\right) .
\end{align*}
Let $P$ be the polynomial
$\prod\limits_{\substack{I\subseteq\left[ n-1\right]
\\\text{is lacunar}}}\left( X-\left( \lambda_{1}m_{I,1}+\lambda
_{2}m_{I,2}+\cdots+\lambda_{n}m_{I,n}\right) \right) \in\mathbf{k}\left[
X\right] $. Then,
\[
P\left( t\right)
=\prod\limits_{\substack{I\subseteq\left[ n-1\right] \text{
is}\\\text{lacunar}}}\left( t-\left( \lambda_{1}m_{I,1}+\lambda_{2}
m_{I,2}+\cdots+\lambda_{n}m_{I,n}\right) \right) =0
\]
(by Theorem~\ref{thm.eigen.annih-pol}). Thus, $S\left( P\left( t\right)
\right) =S\left( 0\right) =0$.
However, $S$ is a $\mathbf{k}$-algebra antihomomorphism. Thus, Proposition
~\ref{prop.antihom.unipol} (applied to~$A=\mathbf{k}\left[ S_{n}\right] $,
$B=\mathbf{k}\left[ S_{n}\right] $, $f=S$ and $u=t$) yields that
$S\left( P\left( t\right) \right) =P\left(
S\left( t\right)\right) $. In view of~$S\left( t\right) = t^\prime$, we can rewrite this as
\[
S\left( P\left( t\right) \right)
=P\left( t^{\prime}\right) =\prod\limits
_{\substack{I\subseteq\left[ n-1\right] \text{ is}\\\text{lacunar}}}\left(
t^{\prime}-\left( \lambda_{1}m_{I,1}+\lambda_{2}m_{I,2}+\cdots+\lambda
_{n}m_{I,n}\right) \right)
\]
(by the definition of $P$). Comparing this with $S\left( P\left( t\right)
\right) =0$, we obtain
\[
\prod\limits_{\substack{I\subseteq\left[ n-1\right] \text{ is}\\
\text{lacunar}
}}\left( t^{\prime}-\left( \lambda_{1}m_{I,1}+\lambda_{2}m_{I,2}
+\cdots+\lambda_{n}m_{I,n}\right) \right) =0.
\]
This proves Theorem~\ref{thm.eigen.annih-pol'}.
\end{proof}
A more interesting question is to find an analogue of Theorem
~\ref{thm.Rcomb-main} for the below-to-somewhere shuffles: Is there a basis of
the $\mathbf{k}$-module $\mathbf{k}\left[ S_{n}\right] $ with respect to
which the $\mathbf{k}$-module endomorphisms $R\left( \lambda_{1}t_{1}
^{\prime}+\lambda_{2}t_{2}^{\prime}+\cdots+\lambda_{n}t_{n}^{\prime}\right) $
are represented by triangular matrices for all $\lambda_{1},\lambda_{2}
,\ldots,\lambda_{n}\in\mathbf{k}$? Again, the answer is \textquotedblleft
yes\textquotedblright, but this basis is no longer the descent-destroying
basis $\left( a_{w}\right) _{w\in S_{n}}$ (ordered by increasing $Q$-index);
instead, it is the \textbf{dual} basis to $\left( a_{w}\right) _{w\in S_{n}
}$ with respect to a certain bilinear form (ordered by \textbf{decreasing}
$Q$-index). Let us elaborate on this now.\footnote{Note that, with respect to
the \textbf{standard} basis $\left( w \right) _{w \in S_{n}}$ of
$\mathbf{k}\left[ S_{n} \right] $, the matrix representing the endomorphism
$R\left( \lambda_{1}t_{1}^{\prime}+\lambda_{2}t_{2}^{\prime}+\cdots
+\lambda_{n}t_{n}^{\prime}\right) $ is the transpose of the matrix
representing the endomorphism $R\left( \lambda_{1}t_{1}+\lambda_{2}
t_{2}+\cdots+\lambda_{n}t_{n}\right) $. However, neither of these two
matrices is triangular.}
First, we recall some concepts from linear algebra (although we are working at
a slightly unusual level of generality, since we do not require $\mathbf{k}$
to be a field):
\begin{itemize}
\item The \emph{dual} of a $\mathbf{k}$-module $U$ is defined to be the
$\mathbf{k}$-module $\operatorname*{Hom}\nolimits_{\mathbf{k}}\left(
U,\mathbf{k}\right) $ of all $\mathbf{k}$-linear maps from $U$ to
$\mathbf{k}$. We denote this dual by $U^{\vee}$.
\item A \emph{bilinear form} on two $\mathbf{k}$-modules $U$ and $V$ is
defined to be a map $f:U\times V\rightarrow\mathbf{k}$ that is $\mathbf{k}
$-linear in each of its two arguments. A bilinear form $f:U\times
V\rightarrow\mathbf{k}$ canonically induces a $\mathbf{k}$-module
homomorphism
\begin{align*}
f^{\circ}:V & \rightarrow U^{\vee},\\
v & \mapsto\left( \text{the map }U\rightarrow\mathbf{k}\text{ that sends
each }u\in U\text{ to }f\left( u,v\right) \right) .
\end{align*}
A bilinear form $f:U\times V\rightarrow\mathbf{k}$ is called
\emph{nondegenerate} if the $\mathbf{k}$-module homomorphism $f^{\circ
}:V\rightarrow U^{\vee}$ is an isomorphism.
\item If $U$ and $V$ are two $\mathbf{k}$-modules with bases $\left(
u_{w}\right) _{w\in W}$ and $\left( v_{w}\right) _{w\in W}$,
respectively\footnote{Note that the bases must have the same indexing set in
this definition.}, and if $f:U\times V\rightarrow\mathbf{k}$ is a bilinear
form, then we say that the basis $\left( v_{w}\right) _{w\in W}$ is
\emph{dual} to $\left( u_{w}\right) _{w\in W}$ with respect to $f$ if and
only if we have
\[
\left( f\left( u_{p},v_{q}\right) =\left[ p=q\right]
\ \ \ \ \ \ \ \ \ \ \text{for all }p,q\in W\right) .
\]
Here, we are using the \emph{Iverson bracket notation}: For each statement
$\mathcal{A}$, we let~$\left[ \mathcal{A}\right] $ denote the truth value of
$\mathcal{A}$ (that is, $1$ if $\mathcal{A}$ is true and $0$ if $\mathcal{A}$
is false).
\end{itemize}
The following three general facts about dual bases are easy and known (see
\cite{s2b1} for proofs):
\begin{proposition}
\label{prop.bilf.nondeg-if-bases}Let $U$ and $V$ be two $\mathbf{k}$-modules,
and let $f:U\times V\rightarrow\mathbf{k}$ be a bilinear form. Let $\left(
u_{w}\right) _{w\in W}$ be a basis of the $\mathbf{k}$-module $U$ such that
the set $W$ is finite. Let~$\left( v_{w}\right) _{w\in W}$ be a basis of the
$\mathbf{k}$-module $V$ that is dual to $\left( u_{w}\right) _{w\in W}$.
Then, the bilinear form $f$ is nondegenerate.
\end{proposition}
\begin{proposition}
\label{prop.bilf.dual-bases}Let $U$ and $V$ be two $\mathbf{k}$-modules, and
let $f:U\times V\rightarrow\mathbf{k}$ be a nondegenerate bilinear form. Let
$\left( u_{w}\right) _{w\in W}$ be a basis of the $\mathbf{k}$-module $U$,
where $W$ is a finite set. Then, there is a unique basis of $V$ that is dual
to $\left( u_{w}\right) _{w\in W}$ with respect to $f$.
\end{proposition}
\begin{proposition}
\label{prop.bilf.dual-expansions}Let $U$ and $V$ be two $\mathbf{k}$-modules,
and let $f:U\times V\rightarrow\mathbf{k}$ be a bilinear form. Let $\left(
u_{w}\right) _{w\in W}$ be a basis of the $\mathbf{k}$-module $U$ such that
the set $W$ is finite. Let~$\left( v_{w}\right) _{w\in W}$ be a basis of the
$\mathbf{k}$-module $V$ that is dual to $\left( u_{w}\right) _{w\in W}$. Then:
\begin{enumerate}
\item[\textbf{(a)}] For any $u\in U$, we have
\[
u=\sum_{w\in W}f\left( u,v_{w}\right) u_{w}.
\]
\item[\textbf{(b)}] For any $v\in V$, we have
\[
v=\sum_{w\in W}f\left( u_{w},v\right) v_{w}.
\]
\end{enumerate}
\end{proposition}
Now, we apply the above to the $\mathbf{k}$-module $\mathbf{k}\left[
S_{n}\right] $. We define a bilinear form $f:\mathbf{k}\left[ S_{n}\right]
\times\mathbf{k}\left[ S_{n}\right] \rightarrow\mathbf{k}$ by setting
\begin{equation}
f\left( p,q\right) =\left[ p=q\right] \ \ \ \ \ \ \ \ \ \ \text{for all
}p,q\in S_{n}. \label{eq.bilf.onkSn}
\end{equation}
(This defines a unique bilinear form, since $\left( w\right) _{w\in S_{n}}$
is a basis of the $\mathbf{k}$-module $\mathbf{k}\left[ S_{n}\right] $.)
Clearly, the basis $\left( w\right) _{w\in S_{n}}$ of $\mathbf{k}\left[
S_{n}\right] $ is dual to itself with respect to this form $f$. Thus,
Proposition~\ref{prop.bilf.nondeg-if-bases} (applied to $U=\mathbf{k}\left[
S_{n}\right] $, $V=\mathbf{k}\left[ S_{n}\right] $, $W=S_{n}$, $\left(
u_{w}\right) _{w\in W}=\left( w\right) _{w\in S_{n}}$ and $\left(
v_{w}\right) _{w\in W}=\left( w\right) _{w\in S_{n}}$) yields that the
bilinear form $f$ is nondegenerate. Hence, Proposition
~\ref{prop.bilf.dual-bases} (applied to $U=\mathbf{k}\left[ S_{n}\right] $,
$V=\mathbf{k}\left[ S_{n}\right] $, $W=S_{n}$ and $\left( u_{w}\right)
_{w\in W}=\left( a_{w}\right) _{w\in S_{n}}$) yields that there is a unique
basis of $\mathbf{k}\left[ S_{n}\right] $ that is dual to $\left(
a_{w}\right) _{w\in S_{n}}$ with respect to $f$ (since Proposition
~\ref{prop.aw.basis-kSn} tells us that $\left( a_{w}\right) _{w\in S_{n}}$ is
a basis of $\mathbf{k}\left[ S_{n}\right] $). Let us denote this basis by
$\left( b_{w}\right) _{w\in S_{n}}$. Thus, the basis $\left( b_{w}\right)
_{w\in S_{n}}$ is dual to $\left( a_{w}\right) _{w\in S_{n}}$; in other
words, we have
\begin{equation}
f\left( a_{p},b_{q}\right) =\left[ p=q\right]
\ \ \ \ \ \ \ \ \ \ \text{for all }p,q\in S_{n}. \label{eq.bilf.onkSn-ab}
\end{equation}
Now, we claim the following analogue to Theorem~\ref{thm.Rcomb-conc}:
\begin{theorem}
\label{thm.Rcomb-conc'}Let $w\in S_{n}$ and $\ell\in\left[ n\right] $. Let
$i=\operatorname*{Qind}w$. Then,
\[
b_{w}t_{\ell}^{\prime}=m_{Q_{i},\ell}b_{w}+\left( \text{a }\mathbf{k}
\text{-linear combination of }b_{v}\text{'s for }v\in S_{n}\text{ satisfying
}\operatorname*{Qind}v>i\right) .
\]
\end{theorem}
Once we have proved Theorem~\ref{thm.Rcomb-conc'}, it will follow that if we
order the basis $\left( b_{w}\right) _{w\in S_{n}}$ in the order of
decreasing $Q$-index, the endomorphisms $R\left( t_{1}^{\prime}\right)
,R\left( t_{2}^{\prime}\right) ,\ldots,R\left( t_{n}^{\prime}\right) $
(and thus also their linear combinations $R\left( \lambda_{1}t_{1}^{\prime
}+\lambda_{2}t_{2}^{\prime}+\cdots+\lambda_{n}t_{n}^{\prime}\right) $) will
be represented by upper-triangular matrices. The analogue of Theorem
~\ref{thm.Rcomb-main} for below-to-somewhere shuffles will thus follow. So it
remains to prove Theorem~\ref{thm.Rcomb-conc'}. In order to do so, we need a
simple lemma about the bilinear form $f:\mathbf{k}\left[ S_{n}\right]
\times\mathbf{k}\left[ S_{n}\right] \rightarrow\mathbf{k}$ defined by
\eqref{eq.bilf.onkSn}:
\begin{lemma}
\label{lem.S.self-adj}We have
\[
f\left( u,vS\left( x\right) \right) =f\left( ux,v\right)
\ \ \ \ \ \ \ \ \ \ \text{for all }x,u,v\in\mathbf{k}\left[ S_{n}\right] .
\]
\end{lemma}
\begin{proof}
This is an easy consequence of the $\mathbf{k}$-bilinearity of $f$ (which
allows us to assume that $x,u,v$ all belong to $S_{n}$) and of the definition
of $S$ (which shows that $S\left( x\right) =x^{-1}$ when $x\in S_{n}$).
Details can be found in~\cite{s2b1}.
\end{proof}
\begin{proof}
[Proof of Theorem~\ref{thm.Rcomb-conc'}.]Forget that we fixed $w$ and $i$ (but
keep $\ell$ fixed). For each $u\in S_{n}$, define two elements
\[
\widetilde{a}_{u}:=a_{u}t_{\ell}-m_{Q_{\operatorname*{Qind}u},\ell}
a_{u}\ \ \ \ \ \ \ \ \ \ \text{and}\ \ \ \ \ \ \ \ \ \ \widetilde{b}
_{u}:=b_{u}t_{\ell}^{\prime}-m_{Q_{\operatorname*{Qind}u},\ell}b_{u}
\]
of $\mathbf{k}\left[ S_{n}\right] $.
We know that the family $\left( a_{w}\right) _{w\in S_{n}}$ is a basis of
the $\mathbf{k}$-module $\mathbf{k}\left[ S_{n}\right] $; we called this
basis the descent-destroying basis. We also know that $\left( b_{w}\right)
_{w\in S_{n}}$ is a basis of $\mathbf{k}\left[ S_{n}\right] $ that is dual
to $\left( a_{w}\right) _{w\in S_{n}}$ with respect to $f$. Thus,
Proposition~\ref{prop.bilf.dual-expansions} \textbf{(a)} shows that each
$u\in\mathbf{k}\left[ S_{n}\right] $ satisfies
\begin{equation}
u=\sum_{w\in S_{n}}f\left( u,b_{w}\right) a_{w}
.\label{pf.thm.Rcomb-conc'.u=sum}
\end{equation}
Furthermore, Proposition~\ref{prop.bilf.dual-expansions} \textbf{(b)} shows
that each $v\in\mathbf{k}\left[ S_{n}\right] $
satisfies
\begin{equation}
v=\sum_{w\in S_{n}}f\left( a_{w},v\right) b_{w}
.\label{pf.thm.Rcomb-conc'.v=sum}
\end{equation}
For each $u\in S_{n}$, we have
\begin{equation}
\widetilde{a}_{u}=\sum_{w\in S_{n}}f\left( \widetilde{a}_{u},b_{w}\right)
a_{w} \label{pf.thm.Rcomb-conc'.1}
\end{equation}
(by~\eqref{pf.thm.Rcomb-conc'.u=sum}).
For each $v\in S_{n}$, we have
\[
\widetilde{b}_{v}=\sum_{w\in S_{n}}f\left( a_{w},\widetilde{b}_{v}\right)
b_{w}
\]
(by~\eqref{pf.thm.Rcomb-conc'.v=sum}). Renaming the indices $v$ and $w$ as $w$
and $v$ in this sentence, we
obtain the following: For each $w\in S_{n}$, we have
\begin{equation}
\widetilde{b}_{w}=\sum_{v\in S_{n}}f\left( a_{v},\widetilde{b}_{w}\right)
b_{v}. \label{pf.thm.Rcomb-conc'.2}
\end{equation}
We shall now prove the following:
\begin{statement}
\textit{Claim 1:} Let $u,w\in S_{n}$ be such that $\operatorname*{Qind}
w\geq\operatorname*{Qind}u$. Then, $f\left( \widetilde{a}_{u},b_{w}\right)
=0$.
\end{statement}
\begin{statement}
\textit{Claim 2:} Let $u,w\in S_{n}$. Then, $f\left( a_{u},\widetilde{b}
_{w}\right) =f\left( \widetilde{a}_{u},b_{w}\right) $.
\end{statement}
[\textit{Proof of Claim 1:} Let $j=\operatorname*{Qind}u$. By assumption, we
have $\operatorname*{Qind}w\geq\operatorname*{Qind}u=j$. Thus, $w$ does not
satisfy $\operatorname*{Qind}w*