%% if you are submitting an initial manuscript then you should have submission as an option here
%% if you are submitting a revised manuscript then you should have revision as an option here
%% otherwise options taken by the article class will be accepted
\documentclass[finalversion]{FPSAC2023}
\articlenumber{15}
%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc

%% note that the class file already loads {amsmath, amsthm, amssymb}

\newtheorem{thm}{Theorem}[section]
\newtheorem{lem}[thm]{Lemma}
\newtheorem{definition}[thm]{Definition}
\newtheorem{example}[thm]{Example}
\newtheorem{question}[thm]{Question}
\newtheorem{prop}[thm]{Proposition}
\theoremstyle{remark}
\newtheorem{remark}[thm]{Remark}

%% define your title in the usual way
\title[Invariant theory for the free left-regular band and a $q$-analogue]{Invariant theory for the free left-regular band and a $q$-analogue}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author{Sarah Brauner\thanks{\href{mailto:braun622@umn.edu}{braun622@umn.edu}. Supported by NSF Graduate Research Fellowship}\addressmark{1}, Patricia Commins\thanks{\href{mailto:commi010@umn.edu}{commi010@umn.edu}. Supported by NSF Graduate Research Fellowship}\addressmark{1}, \and Victor Reiner\thanks{\href{mailto:reiner@umn.edu}{reiner@umn.edu}. Supported by NSF grant DMS-2053288}\addressmark{1}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}School of Mathematics, University of Minnesota, Minneapolis, MN}

%% put the date of submission here
\received{\today}

%% leave this blank until submitting a revised version
%\revised{}

%% put your English abstract here, or comment this out if you don't have one yet
%% please don't use custom commands in your abstract / resume, as these will be displayed online
%% likewise for citations -- please don't use \cite, and instead write out your citation as something like (author year)
\abstract{We examine from an invariant theory viewpoint the monoid algebras for two monoids having large symmetry groups.
%\begin{itemize}    \item the {\it free left-regular band} on $n$ letters, acted on by the symmetric group, and \item  one of its $q$-analogues, %considered by K. Brown,  acted on by the finite general linear group.  \end{itemize}
 The first monoid is the free left-regular band on $n$ letters, defined on the set of all injective words, that is, the words with at most one occurrence of each letter. This monoid carries the action of the symmetric group. The second monoid is one of its $q$-analogues, considered by K. Brown, carrying an action of the finite general linear group.
In both cases, we show that the invariant subalgebras are
 semisimple commutative algebras, and characterize them using \emph{Stirling} and \emph{q-Stirling numbers}.  
 
 We then use results from the theory of random walks and random-to-top shuffling to decompose the entire monoid algebra into irreducibles, simultaneously as a module over the invariant ring and as a group representation. 
 Our irreducible decompositions are described in terms of \emph{derangement symmetric functions} introduced by D\'esarm\'enien and Wachs. }


%% put your French abstract here, or comment this out if you don't have one
%\resume{\lipsum[2]}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{left-regular band, random-to-top, Stirling number, symmetric group, general linear group, unipotent character.}



%% you can include your bibliography however you want, but using an external .bib file is STRONGLY RECOMMENDED and will make the editor's life much easier
%% regardless of how you do it, please use numerical citations; i.e., [xx, yy] in the text

%% this sample uses biblatex, which (among other things) takes care of URLs in a more flexible way than bibtex
%% but you can use bibtex if you want
\usepackage[backend=bibtex]{biblatex}
\addbibresource{sample.bib}
%% note the \printbibliography command at the end of the file which goes with these biblatex commands

\def\freelrb{{\mathcal{F}}}
\def\qfreelrb{\mathcal{F}^{(q)}}
\def\derangement{\mathfrak{d}}
\def\derangementrep{{\mathcal{D}}}
\def\flags{\mathcal{F}}
\def\virtchars{\mathcal{C}}
\def\chambers{\mathfrak{C}}

\DeclareMathOperator{\len}{len}
\DeclareMathOperator{\Des}{Des}

\def\symm{\mathfrak{S}}
\def\ch{{\mathrm{ch}}}
\def\triv{\mathbf{1}}
\def\specht{\chi}
%\def\triv{\mathbf{1}}




\def\kk{\mathbf{k}}
\def\AAA{\mathbf{A}}
\def\BBB{\mathbf{B}}
\def\CCC{\mathbf{C}}
\def\aa{\mathbf{a}}
\def\bb{\mathbf{b}}
\def\cc{\mathbf{c}}
\def\F{{\mathbb{F}}}
\def\Z{{\mathbb{Z}}}


\usepackage{ytableau}
\newcommand{\sarah}[1]{\textcolor{teal}{Sarah:[#1]}}


\begin{document}

\maketitle
%% note that you DO NOT have to put your abstract here -- it is generated by \maketitle and the \abstract and \resume commands above

\begin{center}
\textit{{To the memory of Georgia Benkart.}}
\end{center}

\section{Introduction}
Motivated by results on mixing times for shuffling algorithms on permutations, Bidigare  \cite{Bidigare-thesis} and Bidigare, Hanlon and Rockmore \cite{BHR} developed a complete spectral analysis for a class of random walks on the chambers of a hyperplane arrangement.  Their work relied heavily on the {\it Tits semigroup} structure on the cones of the arrangement.
Later, Brown \cite{BrownOnLRBs} generalized their analysis
to random walks coming from
semigroups $\mathcal{L}$ which form a {\it left-regular band (LRB)}, meaning that $x^2=x$ and $xyx=xy$ for all $x,y$ in $\mathcal{L}$. Left-regular bands have since been studied by many others; see Margolis, Saliola, and Steinberg \cite{MSS} for extensive work along with a historical discussion in their Chapter 1.

Some left-regular bands come equipped with natural symmetry groups. In his PhD thesis \cite{Bidigare-thesis}, Bidigare studied the Tits semigroup algebra of a reflection arrangement under the action of its corresponding reflection group. He discovered that the invariant subalgebra is anti-isomorphic to a well-studied algebra: Solomon's descent algebra. The shuffling operators contained in the invariant subalgebra are random walks on the reflection group (see \cite[Theorem 8]{BrownOnLRBs}) and include interesting examples such as random-to-top shuffling and inverse riffle shuffling. The close relationship between the Tits semigroup algebra and the descent algebra has proved to be useful beyond shuffling; for example, Saliola used this viewpoint of the descent algebra in his computation of its quiver \cite{SALIOLAquiver-descent}.

This abstract is based on \cite{BraunerComminsReiner}, where we study two examples
of left-regular bands $M$, related to those discussed by Brown, with large groups of monoid automorphisms $G$: 
\begin{itemize}
    \item the {\it free LRB on $n$ letters} \cite[\S1.3]{BrownOnLRBs}, denoted $\freelrb_n$,
    with $G$ the symmetric group $\symm_n$, and
    \item a $q$-analogue $\qfreelrb_n$ related to monoids in \cite{BrownOnLRBs}, and $G$ the general linear group \linebreak $GL_n(\F_q)$.
\end{itemize}
Inspired by Bidigare's work, we study these left-regular bands under the action of their symmetry groups. In particular, for both monoids $M=\freelrb_n,\qfreelrb_n$, we examine the {\it monoid algebra} $R:=\kk M$ with coefficients in a commutative ring $\kk$ with $1$, and answer the
two {\it main questions of invariant theory} for $G$ acting on $R$:

\begin{question}
\label{first-main-invariant-theory-question}
What is the structure of the invariant subalgebra $R^G$?
\end{question}

\begin{question}
\label{second-main-invariant-theory-question}
What is the structure of $R$, simultaneously as an $R^G$-module
and a $G$-rep\-re\-sentation?
\end{question}

\noindent
Notably, both questions are answered for the two monoids $M = \freelrb_n, \freelrb_n^{(q)}$ in parallel. 

We answer \cref{first-main-invariant-theory-question} by showing that (when $q \in \kk^\times$)  the invariant subalgebra $R^G$ for both monoids is semisimple, commutative, and generated by a single element. This generator acts semisimply on $R$ with eigenvalues in $0, 1, \cdots, n$ for $M = \freelrb_n$ and $[0]_q, [1]_q, \cdots, [n]_q$ for $M = \qfreelrb_{n}.$ Our analysis uses the combinatorics of Stirling and $q$-Stirling numbers.

Our answer to \cref{second-main-invariant-theory-question} involves decomposing the eigenspaces of the generator of $R^G$  on $R$ as $G$-representations (for $\kk$ a field in which $|G|$ is invertible). We do so by (i) introducing and studying filtrations on $R$ and (ii) inductively constructing eigenvectors.
%Filtrations on $R$ and conceptual eigenvector \sarah{I think I am confused about the phrase conceptual eigenvector.}  constructions are key to our proofs. 
We describe these eigenspaces in terms of \textit{derangement symmetric functions} first introduced by D\'{e}sarm\'{e}nien and Wachs \cite{frenchdesarmenienwachs}.  Derangement symmetric functions have connections to many well-studied objects in combinatorics such as the complex of injective words \cite{ReinerWebb}, random-to-top and random-to-random shuffling \cite{Uyemura-Reyes}, higher Lie characters \cite{Uyemura-Reyes}, and configuration spaces \cite{HershReiner}; see \cite[\S 3.3]{BraunerComminsReiner} for historical details. We add to this list by showing they form crucial building blocks for the invariant theory of $\kk \freelrb_n$ and $\kk \qfreelrb_n$. 
\subsection{Outline}

In \cref{sec:lrbs} we define the two monoids of interest and their respective symmetry groups. In \cref{sec:q1} we determine the structure of the invariant subalgebras for both monoid algebras, answering \cref{first-main-invariant-theory-question} with \cref{semisimplicity-theorem}. In order to present our answer to \cref{second-main-invariant-theory-question} for both monoids in parallel, we use the language of symmetric functions. Accordingly, \cref{sec:symmfun} reviews the famous Frobenius characteristic map and its lesser-known $q$-analogue. We also give background on the \textit{derangement symmetric function} here. Finally, in \cref{sec:q2} we answer \cref{second-main-invariant-theory-question} with \cref{thm:semigroupeigen}.


\section{The left-regular bands and their symmetry groups}\label{sec:lrbs}

\begin{definition} 
\label{defn:freeLRB} \rm
The {\it free left-regular band (or LRB)} on $n$ letters $\freelrb_n$ (see 
\cite[\S1.3]{BrownOnLRBs}, \cite[\S14.3.1]{Steinberg}) consists, as a set, of all words
$\aa=(a_1,a_2,\ldots,a_\ell)$ with letters $a_i$
from $\{1,2,\ldots,n\}$ and no repeated letters,
that is, $a_i \neq a_j$ for $1 \leq i<j \leq n$. The set $\freelrb_n$ becomes a semigroup under the following operation:
if $\bb=(b_1,\ldots,b_m)$ is another word in
$\freelrb_n$, then their product is
$$
\aa \cdot \bb:=(a_1,\ldots,a_\ell,b_1,\ldots,b_m)^{\wedge},
$$
where we adopt the notation from Brown \cite{BrownOnLRBs} that for a sequence $\cc=(c_1,\ldots,c_p)$, the subsequence
$\cc^\wedge=(c_1,\ldots,c_p)^\wedge$
is obtained by removing any letter 
$c_i$ that appears already in the prefix $(c_1,c_2,\ldots,c_{i-1})$.
\end{definition}

\begin{example}
In $\freelrb_5$, one has
$(2, 5, 1) \cdot (4, 2, 3, 1) = (2, 5, 1, 4, 3).$
\end{example}

One can check that the empty word $()$ is an identity element for
this operation, and hence $\freelrb_n$ is not only a semigroup, but a {\it monoid}. For any word $\aa \in \freelrb$, the {\it length} $\ell(\aa):=\ell$ lies
anywhere in the range $0 \leq \ell \leq n$.
There is a left action on $\freelrb_n$ by $\symm_n$, the symmetric group on $n$ letters, where $w \in \symm_n$ acts by $w(a_1,\ldots,a_\ell)=(w(a_1),\ldots,w(a_\ell)).$



The $q$-analogue of $\freelrb_n$ that we will consider will be denoted
$\qfreelrb_n$, defined as follows.
\begin{definition} 
\label{defn:q-freeLRB}
\rm
 As a set, $\qfreelrb_n$ consists
of all partial flags of subspaces
$\AAA=(A_1,\ldots,A_\ell)$ where $A_i$ is an $i$-dimensional $\F_q$-linear subspace of $(\F_q)^n$, and
$A_1 \subset A_2 \subset \cdots \subset A_\ell$.
Again the \textit{length} $\ell(\AAA):=\ell$ lies in the range $0 \leq \ell \leq n$.  We multiply $\AAA$ with another flag  $\BBB=(B_1,\ldots,B_m)$ in $\qfreelrb_n$ by:
$$
\AAA \cdot \BBB:=
(A_1,\ldots,A_\ell,A_\ell+B_1,A_\ell+B_2,\ldots,A_\ell+B_m)^\wedge.
$$
As before, for a sequence $\CCC=(C_1,\ldots,C_p)$ of nested
subspaces $C_1 \subseteq C_2 \subseteq \cdots \subseteq C_p$, the subsequence $\CCC^\wedge$
is obtained by removing any $C_i$ appearing 
in the prefix $(C_1,\ldots,C_{i-1})$.
\end{definition}

As in the $q=1$ case, $\qfreelrb_n$ is not only a semigroup but a {\it monoid} since the empty flag $()$ is an identity element\footnote{The authors thank an anonymous referee for pointing out that
both $\freelrb_n, \qfreelrb_n$ are instances of the (right-) {\it free Rhodes expansion} of the lattice semigroups for the Boolean algebra
and finite vector space lattices, using the rank one elements as generators; see \cite[\S4]{Reilly}.}. Our symmetry group in this case is $GL_n:=GL_n(\F_q)$, and $g \in GL_n$ acts on the left by $g(A_1,\ldots,A_\ell)=(g(A_1),\ldots,g(A_\ell)).$




%there is a left action on $\qfreelrb$ by the finite general linear group $GL_n:=GL_n(\F_q)$. The element $g \in GL_n,$ acts by $g(A_1,\ldots,A_\ell)=(g(A_1),\ldots,g(A_\ell)).$
% $$
% g(A_1,\ldots,A_\ell)=(g(A_1),\ldots,g(A_\ell)).
% $$


Let $\kk$ be a commutative ring with $1$.  For any finite monoid $M$ (such as 
$M=\freelrb_n, \qfreelrb_n$), 
the {\it monoid algebra} $R=\kk M$ is
the free $\kk$-module with basis elements given by
the elements $\aa$ of $M$, and multiplication extended
$\kk$-linearly. A group $G$ of monoid automorphisms of $M$ (such as $G = \symm_n, GL_n$) acts as ring automorphisms on $\kk M$.


%from the monoid operation on the basis elements:
% $$
% \left(
% \sum_\aa p_\aa  \,\, \aa
% \right)
% \left(
% \sum_\bb  q_\bb\,\, \bb
% \right)
% =
% \sum_{\aa,\bb}
% p_\aa q_\bb  \,\, \aa \cdot \bb 
% =
% \sum_\cc \left( \sum_{\aa \cdot \bb=\cc} p_\aa q_\bb  \right) \cc.
% $$
% {\color{orange}{Vic:I would save space by omitting that example of what "monoid algebra" multiplication looks like.  It's standard.}}
Following Brown \cite{BrownOnLRBs}, we use \textit{chambers} to refer to words and flags of maximum length in  $\freelrb_n$ and $\qfreelrb_n$. In $\kk\freelrb_n$, the chamber subspace is $\kk \symm_n.$ In $\kk\qfreelrb_n$, the chamber subspace is spanned by complete flags of $(\F_q)^n,$ equivalent to the coset space $\kk [GL_n / B].$ 



%Note that $G = \symm_n, GL_n$ both act on $R = \kk \freelrb_n, \kk \qfreelrb_n$ by monoid automorphisms. Any group $G$ of monoid automorphisms of $M$ acts as ring automorphisms on $R=\kk M$.  

\section{Answer to \cref{first-main-invariant-theory-question}}\label{sec:q1}
Our first goal is to answer \cref{first-main-invariant-theory-question} by describing the invariant rings $R^G$. Importantly, since the groups $G$ permute the monoid elements $M$, the monoid
algebra $R=\kk M$ becomes a permutation representation of $G$.
Therefore the invariant subalgebra $R^G$ has as a $\kk$-basis
the orbit sums $\{ \sum_{\aa \in \mathcal{O}} \aa\}$
as one runs through all $G$-orbits $\mathcal{O}$ on $M$.

% since the groups $G=\symm_n,GL_n$ act transitively on the subsets 
% $$
% \begin{aligned}
% \freelrb_{n,\ell}&:=\{\aa \in \freelrb_n: \ell(\aa)=\ell\},\\
% \qfreelrb_{n,\ell}&:=\{\AAA \in \freelrb_n: \ell(\AAA)=\ell\}.
% \end{aligned}
% $$
% {\color{orange}{Vic: Could save space by not defining those two subsets $\freelrb_{n,\ell},\qfreelrb_{n,\ell}$, since they don't come up that much in this version.  Instead, in the summations defining $x_\ell, x^{(q)}_\ell$, one could add the length $\ell$ conditions on $\aa$ and $A$.}}

 For both monoids $M=\freelrb_n,\qfreelrb_n$, one can easily identify the $G$-orbits as elements of a fixed length. In particular, the $G$-invariant
subalgebras $R^G$ have  
$\kk$-bases 
$\{x_\ell\}_{\ell=0,1,\ldots,n}$ and $
\{x^{(q)}_\ell\}_{\ell=0,1,\ldots,n}$,
 defined by
\begin{equation*}
\begin{aligned}
x_\ell&:=\sum_{\substack{\aa \in \freelrb_{n}\\ \ell(\aa) = \ell}} \aa, \hspace{ 3em }
x^{(q)}_\ell&:=\sum_{\substack{\AAA \in \qfreelrb_{n} \\ \ell(\AAA) = \ell}} \AAA. 
\end{aligned}
\end{equation*}
\begin{example}
Let $q = 2$, $n=3$, $\ell = 1$,
and let $e_1,e_2,e_3$ be standard basis vectors for $V=(\F_2)^3$. Using the notation $\langle v_1,v_2,\ldots,v_m\rangle$ for the $\F_q$-span
of the vectors $\{v_1,v_2,\ldots,v_m\}$ in $V$,
one has 
{\small\[
\begin{aligned} x^{(2)}_{1} =& (\langle e_1 \rangle ) + (\langle e_2 \rangle ) + (\langle e_3 \rangle ) + (\langle e_1 + e_2 \rangle )+ (\langle e_1 + e_3 \rangle ) + (\langle e_2 + e_3 \rangle ) + (\langle e_1 + e_2 + e_3 \rangle ).
\end{aligned} \]}
\end{example}
We will show that both invariant subalgebras $R^G$ have another natural basis consisting of \textit{powers} of $x_1, x_1^{(q)}$ when $q \in \kk^\times$.  Henceforth, set $x:= x_1$ and $x^{(q)}:= x_1^{(q)}$.% and assume $q \in \kk^\times$. 

Our proof that the powers of $x$ and $x_1^{(q)}$ form a basis of $R^G$ involves Stirling numbers and one of their $q$-analogues\footnote{See \cite[\S 1.1,1.2]{SaganSwanson} for a history of two standard $q$-analogues, one being the $S_q(n,k)$ in \cref{def:stirling}.}. Recall the standard $q$-analogue of $n \in \Z_{\geq 0}:$%nonnegative integers
$$
[n]_q:=1+q+q^2+\cdots+q^{n-1}.
$$

%. Assume that $q \in \kk^\times$. It turns out that the $G$-invariant subalgebras actually have $\kk$-bases consisting of \textit{powers} of $x_1, x_1^{(q)}.$  Henceforth, set $x:= x_1$ and $x^{(q)}:= x_1^{(q)}$. Our proof that the powers of $x$ and $x_1^{(q)}$ form a basis of $R^G$ involves Stirling numbers and one of their $q$-analogues.

%For our purposes, a different basis of $R^G$ will be more useful. When $q \in \kk^\times,$ i

\begin{definition}\label{def:stirling}
Define the classical Stirling numbers $S(n, k)$ and a $q$-analogue $S_q(n, k)$ recursively as follows. When $n = k = 0$, let $S(n, k) = S_q(n, k) = 1.$ When $n + k \geq 1$ with $n = 0$ or $k = 0$, set $S(n, k) = S_q(n, k) = 0$. For $n$ and $k$ both at least $1$, define
\begin{equation}
\label{Stirling-recurrences}
\begin{array}{rccccl}
S(n,k)&=&S(n-1,k-1) &+& k \cdot S(n-1,k),\\
S_q(n,k)&=&q^{k-1}\cdot S_q(n-1,k-1) &+& [k]_q \cdot S_q(n-1,k).
\end{array}
\end{equation}
\end{definition}
The recurrences in \cref{Stirling-recurrences} lead to a change of basis expression in $R^G$.
\begin{lem}
\label{Stirling-corollary}
Let $\kk$ be a commutative ring with $1$,
and let $R=\kk M$ with $M=\freelrb_n$ or $\qfreelrb_n$.
Then the ($q$-)Stirling numbers $S(m,k), S_q(m,k)$ are the expansion
coefficients for the powers 
$\{ x^m \}_{m=0,1,\ldots,n}$ and $\{ (x^{(q)})^m \}_{m=0,1,\ldots,n}$ in the $\kk$-bases
$\{ x_k \}_{k=0,1,\ldots,n}, \{ x^{(q)}_k\}_{k=0,1,\ldots,n}$ of $R^G$:

$$
\begin{aligned}
x^m&=\sum_k S(m,k)\, x_k,\\
(x^{(q)})^m&=\sum_k S_q(m,k)\, x^{(q)}_k.
\end{aligned}
$$
Thus unitriangularity of $ \left \{S(m,k)\right\}$
shows $ \{ x^k \}_{k=0,1,\ldots,n}$
always gives a $\kk$-basis for $R^G$, while
triangularity of $\left \{S_q(m,k)\right\}$ shows 
$ \{ (x^{(q)})^k \}_{k=0,1,\ldots,n}$ are a $\kk$-basis for $R^G$ if and only if $q \in \kk^\times$.
\end{lem}
\begin{proof}[Proof Idea]
The lemma follows from induction on the Stirling recurrences (\ref{Stirling-recurrences}) after proving the following multiplication rules in $R^G$: for $\ell=0,1,\ldots,n$,

\begin{equation*} %\label{Multiplication-rules}
\begin{aligned}
x \cdot x_\ell&= \ell x_{\ell} + x_{\ell+1},\\
x^{(q)} \cdot x^{(q)}_\ell&= [\ell]_q \, x_{\ell}^{(q)} + q^\ell \, x_{\ell+1}^{(q)}.
\end{aligned}
\end{equation*}
Note that these rules allow one to solve for each $x_\ell$ or $x_\ell^{(q)}$
in terms of powers of $x$ or $x^{(q)}$ inductively.  The Stirling
numbers just happen to be the change-of-basis coefficients.
\end{proof}

We use Lemma \ref{Stirling-corollary}, as well as properties of minimal polynomials, to describe the structure of the invariant subalgebras, answering \cref{first-main-invariant-theory-question}. 
\begin{thm}
\label{semisimplicity-theorem}
Let $\kk$ be any commutative ring with $1$, and $R=\kk M$ for either of the monoids $M=\freelrb_n, \qfreelrb_n$,
with symmetry groups $G=\symm_n, GL_n$.
If $M=\qfreelrb_n$, assume that $q$ is in $\kk^\times$.
\begin{enumerate}
\item[(i)] 
The unique $\kk$-algebra map $
\kk[X]{\longrightarrow} R$
defined by
$$
X  \longmapsto 
\begin{cases} 
x & \text{ if }M=\freelrb_n,\\
x^{(q)} & \text{ if }M=\qfreelrb_n,\\
\end{cases}
$$
induces an algebra isomorphism
$
\kk[X]/(f(X)) \cong R^G
$
where
$$
f(X):=
\begin{cases}
X(X-1)(X-2) \cdots (X-n)
& \text{ if }M=\freelrb_n,\\
X(X-[1]_q)(X-[2]_q) \cdots (X-[n]_q)
& \text{ if }M=\qfreelrb_n.\\
\end{cases}
$$
Hence $R^G$ is
commutative and generated by $x$ or $x^{(q)}$.

\item[(ii)]
If  $\kk$ is a field where $|G|$ is invertible, then $x$ or $x^{(q)}$
acts semisimply on any finite-dimensional $R^G$-module,
with eigenvalues contained in the lists
$$
\begin{cases}
0,1,2,\ldots,n & \text{ if }M=\freelrb_n,\\
[0]_q,[1]_q,[2]_q,\ldots,[n]_q
& \text{ if }M=\qfreelrb_n.\\
\end{cases}
$$
\end{enumerate}
\end{thm}
% \begin{proof}[Proof Idea]
% \begin{enumerate}
%     \item[(i)]  From the multiplication rules (\ref{Multiplication-rules}), one can deduce that $x, x^{(q)}$ act on $\kk M$ with characteristic polynomial $f(X)$, and so $\ker(\gamma)$ contains $f(X)$. Noting that $f(X)$ is monic of degree $n + 1$ and applying \cref{Stirling-corollary} proves $\gamma$ is an isomorphism.
%     \item[(ii)] One can check that the cardinality of $\symm_n$ or $GL_n$ being invertible in $\kk$ is equivalent to the distinctness of the lists $0, 1, 2 \cdots, n$ or $[0]_q, [1]_q, \cdots, [n]_q,$ respectively. Distinctness of roots implies that $f(X)$ is further the minimal polynomial of the action of $x, x^{(q)}$ on $R^G.$ Thus, $x, x^{(q)}$ act on any finite-dimensional $R^G$-module semisimply with eigenvalues contained in their corresponding set of roots.
    
% \end{enumerate}

% \end{proof}

An old, but interesting, observation is that multiplication by $x$ acts on the chamber subspace of $\kk \freelrb_n$ as a (rescaled) version of the random-to-top operator,
see for instance B. Steinberg \cite[Prop. 14.5]{Steinberg}. This observation will be used in the proof of \cref{thm:semigroupeigen}.

\begin{example} 
If $n=4$ and $w = (3,1,4,2)$, then 
\[ 
\begin{aligned}
x \cdot w &=
((1)+(2)+(3)+(4)) \cdot (3,1,4,2) \\
&= 
(1,3,4,2)
+(2,3,1,4)
+(3,1,4,2)
+(4,3,1,2)
\end{aligned}
\]
which (after scaling by $\frac{1}{4}$) is
the result of random-to-top shuffling on $w$ as an element of $\kk \symm_4$.
\end{example}

\begin{remark}
In unpublished notes, Garsia \cite{Garsia} (see also Tian \cite{Tian}), studies the {\it top-to-random} shuffling operator, which is adjoint or transpose to the random-to-top operator. There he sketches a proof that its minimal polynomial is $X(X-1)(X-2)\cdots(X-n)$.  In light
of the fact that an operator and its transpose have the same minimal
polynomial, Garsia's sketch is closely related to the part of our proof of Theorem~\ref{semisimplicity-theorem}
dealing with $M=\kk\freelrb_n$.
\end{remark}
\section{Symmetric function background}\label{sec:symmfun}
\subsection{Symmetric functions,  $\symm_n$- and unipotent $GL_n$-representations} 
\label{Frobenius-isomorphism-section}

We review here the relation between the {\it ring of symmetric functions} $\Lambda$ and representations of $\symm_n$;  see Sagan \cite{Sagan}, Stanley \cite{Stanley-EC2} as references, and for undefined terminology.  We then review the parallel story for R. Steinberg's {\it unipotent representations} of $GL_n$; see \cite[\S 4.2, 4.6, 4.7]{GrinbergReiner}
as a reference.

The {\it ring of symmetric functions} $\Lambda$ (of bounded degree, in infinitely many variables) may be viewed as a polynomial algebra $\Z[h_1,h_2,\ldots]=\Z[e_1,e_2,\ldots]$ where $h_n, e_n$ are the {\it complete homogeneous} and {\it elementary} symmetric functions of degree $n$.  One may view $\Lambda$ as a graded $\Z$-algebra $\Lambda=\bigoplus_{n=0}^\infty \Lambda^n$, which we wish to relate to the direct sum 
$$
\virtchars(\symm) := 
\bigoplus_{n=0}^\infty
\virtchars(\symm_n),
$$
where $\virtchars(\symm_n)$ denotes
the $\Z$-module of {\it virtual characters}
of $\symm_n$.  That is, $\virtchars(\symm_n)$ is the free $\Z$-module on the basis of
irreducible characters $\{\specht^\lambda\}$
indexed by the partitions $\lambda$ of $n$, or alternatively, the $\Z$-submodule of class functions on $\symm_n$ of the form $\chi-\chi'$ for genuine characters $\chi,\chi'$.  One makes $\virtchars(\symm)$ a 
graded algebra via the {\it induction product} defined by
\begin{equation*}
%\label{parabolic-induction-defn}
\begin{array}{rcl}
\virtchars(\symm_{n_1}) \times 
\virtchars(\symm_{n_2}) &\longrightarrow& \virtchars(\symm_{n_1+n_2}) \\
(f_1,f_2) &\longmapsto& f_1*f_2:=(f_1 \otimes f_2)\uparrow_{\symm_{n_1} \times \symm_{n_2}}^{\symm_{n_1+n_2}}
\end{array}
\end{equation*}
where $(-)\uparrow_H^G$ is the usual
{\it induction} of class functions on a subgroup $H$ to class functions on $G$. One then has the {\it Frobenius characteristic isomorphism} of $\Z$-algebras $\virtchars(\symm) 
\overset{\ch}{\longrightarrow} \Lambda$, mapping
$$
\begin{array}{rcl}
\virtchars(\symm) &
\overset{\ch}{\longrightarrow} &\Lambda\\ [0.05in]
\triv_{\symm_n} &\longmapsto & h_n,\\ [0.05in]
%\sgn_{\symm_n} & \longmapsto & e_n\\ [0.05in]
\specht^\lambda &\longmapsto & s_\lambda.
\end{array}
$$
Here $s_\lambda$ is the {\it Schur function}. For a composition $\alpha = \alpha_1, \alpha_2, \cdots, \alpha_\ell$, we use the standard shorthand  $h_{\alpha}:= h_{\alpha_1}h_{\alpha_2}\cdots h_{\alpha_\ell}.$%\[h_{\alpha}:= h_{\alpha_1}h_{\alpha_2}\cdots h_{\alpha_\ell}.\] 



There is a parallel story for a certain subset of $GL_n$-representations.  Specifically, there is a collection of irreducible $GL_n$-representations $\{\specht_q^\lambda\}$, 
indexed by partitions $\lambda$ of $n$, which are the irreducible constituents occurring within the $GL_n$-permutation action on
the set $GL_n/B$ of {\it complete flags of subspaces} in 
$V=(\F_q)^n$.  They were studied by R. Steinberg \cite{Steinberg-unipotents}, and are now called
the {\it unipotent characters} of $GL_n$.  
Denoting by $\virtchars(GL_n)$ the free $\Z$-submodule of the
class functions on $GL_n$ with unipotent characters
$\{\specht_q^\lambda\}$ as a basis, one can define the {\it parabolic} or {\it Harish-Chandra induction} product
on the direct sum $\virtchars(GL):=\bigoplus_{n=0}^\infty \virtchars(GL_n)$ as
follows:
$$
\begin{array}{rcl}
\virtchars(GL_{n_1}) \times 
\virtchars(GL_{n_2}) &\longrightarrow& \virtchars(GL_{n_1+n_2}) \\
(f_1,f_2) &\longmapsto&
f_1*f_2:=
\left( 
(f_1 \otimes f_2) \Uparrow_{GL{n_1} \times GL_{n_2}}^{P_{n_1,n_2}}
\right)
\uparrow_{P_{n_1,n_2}.}^{GL{n_1+n_2}}
\end{array}
$$
Here $P_{n_1,n_2}$ is the maximal parabolic subgroup of $GL_{n_1+n_2}$ setwise stabilizing the $\F_q$-span of the first $n_1$ standard basis vectors, and
$(-)\Uparrow_{GL{n_1} \times GL_{n_2}}^{P_{n_1,n_2}}$
is the {\it inflation} operation that creates a $GL{n_1} \times GL_{n_2}$-representation from a 
$P_{n_1,n_2}$-representation, by precomposing with the surjective
homomorphism 
$
P_{n_1,n_2} \twoheadrightarrow  GL_{n_1} \times GL_{n_2}
$
sending
$
\left[ \begin{smallmatrix} A & B \\ 0 & C \end{smallmatrix}\right] 
\longmapsto  
\left[ \begin{smallmatrix} A & 0 \\ 0 & C \end{smallmatrix}\right].
$


This parabolic induction turns out to make $\virtchars(GL)$ into an associative, commutative $\Z$-algebra.  One then has a $q$-analogue of the Frobenius isomorphism
$\virtchars(GL) \overset{\ch_q}{\longrightarrow} \Lambda$ that sends $\triv_{GL_n} \longmapsto  h_n$
and $\specht_q^\lambda \longmapsto s_\lambda$.
%\sgn_{\symm_n} & \longmapsto & e_n\\
%\specht_q^\lambda &\longmapsto & s_\lambda.
%$$
%\begin{array}{rcl}
%\virtchars(GL) &
%\overset{\ch_q}{\longrightarrow} &\Lambda\\ [.05 in]
%\triv_{GL_n} &\longmapsto & h_n\\  [.05 in]
%\sgn_{\symm_n} & \longmapsto & e_n\\
%\specht_q^\lambda &\longmapsto & s_\lambda.
%\end{array}
%$$
For example, the chamber subspaces $\kk \symm_n$ and $\kk[GL_n / B]$ of $\kk \freelrb_n$ and $\kk \qfreelrb_n$ carry the same (q)-Frobenius characteristic image $h_{1^n}$. %which can be seen from viewing both as induced representations.





%%%
\subsection{($q$-)derangement numbers and representations}
\label{sec:derangement}
A central role in this story is played by the classical {\it derangement numbers} $d_n$, and the {\it $q$-derangement numbers} $d_n(q)$ of Wachs \cite{Wachs}:
\begin{equation*}
%\label{derangement-numbers}
\begin{array}{rcl}
d_n&:=&n!\sum_{k=0}^n \frac{(-1)^k}{k!}
=n!
\left(
\frac{1}{1!} 
-\frac{1}{2!}
+\frac{1}{3!} 
-\frac{1}{4!} 
+ \cdots 
+\frac{(-1)^n}{n!}
\right),\\
d_n(q)&:=&[n]!_q \sum_{k=0}^n \frac{(-1)^k}{[k]!_q}.
\end{array}
\end{equation*}
There are two well-known combinatorial models for $d_n$ counting permutations in $\symm_n$:
\begin{itemize}
    \item  {\it derangements}, which are the fixed-point free permutations, or 
    \item {\it desarrangements}, which are permutations $w=(w_1,w_2,\ldots,w_n)$ whose first ascent position $i$ with $w_i< w_{i+1}$ (using $w_{n+1}=n+1$) occurs for an even position $i$.
\end{itemize}  
Wachs \cite{Wachs} and later D\'esarm\'enien and Wachs \cite{desarmenienwachs} gave various interpretations for $d_n(q)$. In particular, $d_n(q)$ is still closely related to derangements and desarrangements. Letting $D_n, E_n$ denote the derangements and desarrangements in $S_n$, and defining the \textit{major index} statistic of a permutation $w=(w_1,\ldots,w_n)$
as $\text{maj}(\sigma)=\sum_{i:w_i > w_{i+1}} i$,
one has 
\[
d_n(q) = \sum_{\sigma \in D_n}q^{\text{maj}(\sigma)} = \sum_{\sigma \in E_n}q^{\text{maj}(\sigma^{-1})}.
\]

These $d_n, d_n(q)$ are the dimensions for a pair of representations
of $\symm_n$ and $GL_n$, which we call the {\it derangement representation} $\derangementrep_n$  and its (unipotent) $q$-analogue
$\derangementrep_n^{(q)}$.  Both have the same symmetric function image
$\derangement_n$ under the Frobenius maps $\ch$ and $\ch_q$. The symmetric function $\derangement_n$ was originally introduced by D\'{e}sarm\'{e}nien and Wachs \cite{frenchdesarmenienwachs} and has many equivalent descriptions (see \cite[Proposition 3.1]{BraunerComminsReiner}). Here, we define $\derangement_n$ by its decomposition into Schur functions; this description is due to Reiner and Webb \cite{ReinerWebb}. To do so, we must define desarrangement tableaux.

A standard Young tableau $Q$ with $n$ cells written in English notation, has {\it descent set}
$$
\Des(w):=\{i \in \{1,2,\ldots,n-1\}: i+1 \text{ appears south and weakly west of }i\text{ in }Q \}.
$$
For example, 
\ytableausetup{smalltableaux}
$
Q=\begin{ytableau}
\ytableausetup{smalltableaux}
1&3\\
2&6\\
4\\
5
\end{ytableau}
$
has $\Des(Q)=\{1,3,4\}$.
A {\it desarrangement tableau} is a standard Young tableau $Q$ with $n$ cells
for which the smallest element of $\{1,2,\ldots,n\}\setminus \Des(Q)$ is even.  Thus
the example tableau $Q$ given above is a desarrangement tableau. 

\begin{definition}
 $\derangement_n = \sum_Q s_{\lambda(Q)}$
    where $Q$ runs through the desarrangement tableaux of size $n$.
    \end{definition}
\begin{example}
We compute $\derangement_n$ for $0 \leq n \leq 4.$
\begin{equation*}
%\label{desarrangement-tableau-table}
\renewcommand\arraystretch{1.5}
\begin{tabular}{|c|c|c|}\hline
$n$ & desarrangement tableaux $Q$ &  $\derangement_n$ \\\hline\hline
$0$ &  $\varnothing$ & $1$\\\hline
$1$& \text{(none)} &$0$\\\hline
$2$ & 
$\ytableausetup{smalltableaux}
\begin{ytableau} 1\\2  
\end{ytableau}$
&$s_{(1,1)}$\\[-20pt]
&&\\\hline
$3$ &
$\ytableausetup{smalltableaux}
\begin{ytableau} 1&3\\2  
\end{ytableau}$
&$s_{(2,1)}$\\[-20pt]
&&\\\hline
$4$ &
$\ytableausetup{smalltableaux}
\begin{ytableau} 1\\2 \\3\\4  
\end{ytableau}$
\quad
$\ytableausetup{smalltableaux}
\begin{ytableau} 1&3\\2\\4  
\end{ytableau}$
\quad
$\ytableausetup{smalltableaux}
\begin{ytableau} 1&3\\2&4  
\end{ytableau}$\quad
$\ytableausetup{smalltableaux}
\begin{ytableau} 1&3&4\\2   
\end{ytableau}$\quad
&$s_{(1,1,1,1)} +
s_{(2,1,1)} +
s_{(2,2)} +
s_{(3,1)}
$\\[-20pt]
&&\\\hline
\end{tabular}
\end{equation*}
\end{example}

\section{Answer to \cref{second-main-invariant-theory-question}}\label{sec:q2}
We are now prepared to answer \cref{second-main-invariant-theory-question} by examining 
%In this section, we examine 
the monoid algebras $R = \kk M$ as modules over both the symmetry groups $\kk G$ and their invariant subalgebras $R^G$. Since $R$ carries commuting actions of
$R^G$ and of $\kk G$,
we will describe $R$ simultaneously as a module over both. Henceforth, assume that $\kk$ is a field in which $|G|$ is invertible. 


We will utilize two important features of our setting. First, since $\kk M$ is finite-dimensional over $\kk$,  it
is semisimple both as an $R^G$-module from Theorem~\ref{semisimplicity-theorem}(ii), and as a $\kk G$-module by Maschke's Theorem. Second, by Theorem~\ref{semisimplicity-theorem}(ii),
we have that $R^G$ is generated by
the single element $x$ or $x^{(q)}$, which acts
diagonalizably with certain eigenvalues $\lambda$ all lying in $\kk$. It follows that in order to understand the simultaneous $R^{G}$- and $\kk G$-module structure of any module $V$, it suffices to decompose
the eigenspaces ($\ker((x-\lambda)|_V)$ or $\ker((x^{(q)}-\lambda)|_V)$)
as $G$-representations.

Hence, we are able to answer Question \ref{second-main-invariant-theory-question} for $j = 0,1, \ldots n$
\begin{itemize}
    \item when $M = \freelrb_n$ by describing $\ker \left((x - j)\vert_{\kk \freelrb_n}\right)$, the $j$-eigenspace of $x$ acting on $\kk \freelrb_n$, as an $\symm_n$-representation, and
    \item when $M = \qfreelrb_n$ by describing $\ker \left((x^{(q)} - [j]_q)\vert_{\kk \qfreelrb_n}\right)$, the $[j]_q$-eigenspace of $x^{(q)}$ acting on $\kk \qfreelrb_n$, as a $GL_n$- representation. 
\end{itemize}

%for $M = \freelrb_n$ by describing the $j$-eigenspaces of $\kk \freelrb_n$, written $\ker \left((x - j)\vert_{\kk \freelrb_n}\right)$, as $\symm_n$-representations, and the  $[j]_q$-eigenspaces of $\kk \qfreelrb_n$, written $\ker \left((x - [j]_q)\vert_{\kk \qfreelrb_n}\right)$, as $GL_n$- representations for $j = 0, 1, \ldots, n$.



\begin{thm}\label{thm:semigroupeigen}
\label{precise-version-of-semigroupeigen}
Let $\kk$ be a field in which $|G|$ is invertible. Then $x, x^{(q)}$ act diagonalizably on $\kk \freelrb_{n}, \kk \qfreelrb_{n}$, and
for each $j=0,1,2,\ldots,n$, their eigenspaces carry $G$-representations with
the same Frobenius map images
$$
\ch \ker\left( (x-j)|_{\kk \freelrb_n} \right)
= \sum_{\ell=j}^n \ h_{(n-\ell,j)} \cdot \derangement_{\ell-j}
= \ch_q \ker\left( (x^{(q)}-[j]_q)|_{\kk \qfreelrb_n} \right).
$$
In other words, one has $G$-representation isomorphisms
$$
\begin{aligned}
\ker\left( (x-j)|_{\kk \freelrb_n} \right)
& \cong \bigoplus_{\ell=j}^n
 \triv_{\symm_{n-\ell}} * \triv_{\symm_j} * \derangementrep_{\ell-j}, \\
\ker\left( (x^{(q)}-[j]_q)|_{\kk \freelrb_n^{(q)}} \right)
& \cong \bigoplus_{\ell=j}^n   \triv_{GL_{n-\ell}} * \triv_{GL_j} * \derangementrep^{(q)}_{\ell-j}.
\end{aligned}
$$
\end{thm}

\begin{proof}[Proof Idea.]
%\begin{enumerate}
   % \item 
    The crucial idea is to introduce a filtration on $\kk M$ by length,
    \begin{align*}
        0 = \kk M_{\geq n + 1} \subset \kk M_{\geq n} \subset \kk M_{\geq n - 1}\subset \cdots \subset \kk M_{\geq 1} \subset \kk M_{\geq 0} = \kk M,
    \end{align*}
    where $M_{\geq \ell}$ is the $\kk$-span of words of length at least $\ell$ for $M = \freelrb_n$ and flags of length at least $\ell$ for $M = \qfreelrb_n$. By semisimplicity, there is an isomorphism of both $R^G$-modules and $G$-representations:
    \begin{equation}\label{vector-space-direct-sum}
        \kk M \cong \bigoplus_{\ell = 0}^n \kk M_{\geq \ell} / \kk M_{\geq \ell + 1}.
    \end{equation} Our approach is to study the eigenspaces of $x, x^{(q)}$ on each summand in \cref{vector-space-direct-sum}.
    %\item 

The bottom of the filtration (when $\ell = n$) is the chamber subspace of $M = \kk \freelrb_n, \kk \qfreelrb_n$, which we write as $\chambers_n$, $\chambers_n^{(q)},$ respectively. We prove that 
    \begin{align}\label{eqn:chambers}
      \ch \ker\left( (x-j)|_{\chambers_n} \right) = h_j \derangement_{n - j} = \ch_q \ker\left( (x^{(q)}-[j]_q)|_{\chambers_n^{(q)}}\right).
    \end{align}
The key ingredients in proving \cref{eqn:chambers} are (i) inductive constructions of explicit $j$-, $[j]_q$-eigenvectors\footnote{The third author is grateful to Michelle Wachs for explaining to him the constructions in the case that $M = \kk \freelrb_n$ in 2002, in the context of random-to-top shuffling.} of $x \vert_{\chambers_n}, \  x^{(q)}\vert_{\chambers^{(q)}_n}$ from nullvectors of $x \vert_{\chambers_{n - j}}, \  x^{(q)}\vert_{\chambers^{(q)}_{n - j}},$  (ii) the dimensions of $\ker \left( x \vert_{\chambers_n}\right), \  \ker \left( x^{(q)} \vert_{\chambers^{(q)}_n}\right)$ following from work of Phatarfod \cite{Phatarfod1991ONTM}, Brown \cite{BrownOnLRBs}, and (iii) a recursive description of $\derangement_n$ from \cite{frenchdesarmenienwachs}: $h_{1^n} = \sum_{j = 0}^n \derangement_{j}h_{n - j}$.

Finally, we address the remaining summands of \cref{vector-space-direct-sum} by reinterpreting the action of $x$, $x^{(q)}$ on $\kk M_{\geq \ell}  / \kk M_{\geq \ell + 1}$ in terms of the eigenspaces of $\chambers_{\ell}, \chambers_{\ell}^{(q)}$ and using properties of induced representations. 
%(ii) recognizing the restricted $j, [j]_q$ eigenspaces as induced representations of the $j, [j]_q$ eigenspaces of $x, x^{(q)}$ on %$\mathscr{C}_{\ell}, \mathscr{C}_{\ell}^{(q)}.$
% acting on the chambers of these smaller monoid algebras.
%     using the following three tools.
%     \begin{enumerate}
%         \item  For $j \geq 1$, we construct explicit $j$-eigenvectors of $x, x^{(q)}$ acting on the chambers in parallel from nullvectors of $x, x^{(q)} (\in \kk \freelrb_{n - j}, \kk \qfreelrb_{n - j})$ acting on the chambers of these smaller monoid algebras. \footnote{The third author is grateful to Michelle Wachs for explaining to him the $\kk \freelrb_n$ version of this construction in 2002, in the context of random-to-top shuffling.} Our constructions show that one has $G$-equivariant
% injections for $j=0,1,2,\ldots,n$:
% $$
% \begin{aligned}
% \triv_{\symm_j} * \ker \left(x|_{\mathcal{C}_{n - j}}\right)  
% & \hookrightarrow \ker\left( (x-j)|_{\mathcal{C}_n} \right),\\
% \triv_{GL_j} * \ker\left(x^{(q)}|_{\mathcal{C}_{n - j}^{(q)}}\right)  
% & \hookrightarrow \ker\left( (x^{(q)}-[j]_q)|_{\mathcal{C}_n^{(q)}} \right).\\
% \end{aligned}
% $$
%         \item We can show these maps are surjections by dimension-counting, in particular using that the dimensions of the kernel of the action of $x, x^{(q)}$ acting on $\mathcal{C}_n$, $\mathcal{C}_n^{(q)}$ are $d_n$, $d_n(q)$, which can be deduced from work of Phatarfod \cite{Phatarfod1991ONTM} and Brown \cite{BrownOnLRBs}, respectively.
%         \item Finally, the recursion \textcolor{blue}{insert once derangement section fixed!} forces $\ch \ker \left( (x) \vert_{\mathcal{C}_{n}}\right) = \derangement_n = \ch_q \ker \left( (x) \vert_{\mathcal{C}_{n}^{(q)}}\right).$ 
%     \end{enumerate}
%\end{enumerate}
\end{proof}


\begin{example}\label{ex:n=2}
We illustrate Theorem~\ref{thm:semigroupeigen} computing the Frobenius map image for each
$j$-eigen\-space of $x$ on $\kk \mathcal{F}_3$, or
equivalently the 
$q$-Frobenius map image
for each 
$[j]_q$-eigenspace of $x^{(q)}$ on $\kk \mathcal{F}_3^{(q)}$.
The table below shows these
symmetric functions in the $j^{th}$ row, decomposed
into columns labeled by $\ell$, which index the filtration factors from \cref{vector-space-direct-sum} that contribute a term.


\begin{center}
{\bf Frobenius map images for eigenspaces of $x, x^{(q)}$ on $\kk \mathcal{F}_3, \kk \mathcal{F}_3^{(q)}$:}\\[.1in]
\begin{tabular}{| c||c  c|c c| c c| c c|}\hline 
 & $ \ell = 0$ & & $\ell = 1$ & & $\ell = 2$ & & $\ell = 3$ & \\ \hline \hline
 & $h_{3}\cdot \derangement_0$ & $=$ & $h_{2}\cdot \derangement_{1}$ & $=$ & $h_{1}\cdot \derangement_2$ & $=$ & $h_0 \cdot \derangement_3$ & $=$\\
 $j=0$ & $h_3 \cdot s_{()}$ & $=$ & $h_2 \cdot 0$ & $=$ & $h_1 \cdot s_{(1,1)}$ & $=$ & $h_0 \cdot s_{(2,1)}$ & $=$\\
 & $s_{(3)}$ & & $0$ & & $s_{(2,1)} + s_{(1, 1, 1)}$ & & $s_{(2,1)}$ & \\[5pt] \hline
  & & & $h_{(2,1)}\cdot \derangement_0$ & $=$ & $h_{(1, 1)}\cdot \derangement_1$ & $=$ & $h_{1}\cdot \derangement_2$ & $=$\\
  $j=1$ & & & $h_{(2,1)}\cdot s_{()}$ & $=$ & $h_{(1,1)} \cdot 0$ & $=$ & $h_1 \cdot s_{(1,1)}$ & $=$\\
   & & & $s_{(3)} + s_{(2, 1)}$ & & $0$ & & $s_{(2,1)} + s_{(1, 1, 1)}$ & \\[5pt] \hline
    & & & & & $h_{(2,1)}\cdot \derangement_0$ & $=$ & $h_{2}\cdot \derangement_1$ & $=$\\
  $j=2$ & & & & & $h_{(2,1)}\cdot s_{()}$ & $=$ & $h_2 \cdot 0$ & $=$\\
   & & & & & $s_{(3)} + s_{(2, 1)}$ & & $0$ & \\[5pt] \hline
    & & & & & & & $h_{3}\cdot \derangement_0$ & $=$\\
  $j=3$ & & & & & & & $h_3 \cdot s_{()}$ & $=$\\
   & & & & & & & $s_{(3)}$ & \\[5pt] \hline
\end{tabular}
\end{center}
\end{example}



\acknowledgements{
The authors are very grateful to Darij Grinberg for helpful references and conversations, to Franco Saliola for useful discussions, and to Peter Webb for organizing a reading seminar on Benjamin Steinberg's text \cite{Steinberg} that helped spark this project.  The third author thanks Michelle Wachs for helpful discussions on random-to-top shuffling.}

%% if you use biblatex then this generates the bibliography
%% if you use some other method then remove this and do it your own way
%\bibliographystyle{abbrv}

\printbibliography


%\bibliography{sample.bib}

\end{document}

.