%% 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]{FPSAC2025}
\articlenumber{138}
%% 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}
\newcommand{\frakt}{\mathfrak{t}}
\newcommand{\fraks}{\mathfrak{s}}
\newcommand{\frakq}{\mathfrak{q}}
\usepackage{ytableau}

\newcommand{\RS}{\sf{RS}}

\newcommand{\arinj}{\ar@{_{(}->}}
\newcommand{\arinjrev}{\ar@{^{(}->}}
\newcommand{\arsurj}{\ar@{->>}}

\newcommand{\word}{\mathrm{word}}
\newcommand{\proj}{\operatorname{proj}}
\newcommand{\sm}{\setminus}
\newcommand{\basis}{\mathfrak{B}}
\newcommand{\content}{\mathfrak{c}}
\newcommand{\eigen}{\mathcal{E}}
\newcommand{\tHH}{\widetilde{\HH}}
\newcommand{\tT}{\widetilde{T}}
\newcommand{\tB}{\widetilde{\B}}
\newcommand{\tRR}{\widetilde{\RR}}
\newcommand{\gtdom}{\mathrel{\triangleright}}
\newcommand{\geqdom}{\mathrel{\trianglerighteq}}
\newcommand{\leqdom}{\mathrel{\trianglelefteq}}
\newcommand{\ledom}{\mathrel{\triangleleft}}
\newcommand{\res}{{\sf Res}}
\newcommand{\ind}{{\sf Ind}}
\newcommand{\End}{{\sf End}}
\newcommand{\DD}{\mathfrak{D}}
\newcommand{\GL}[1]{\operatorname{GL}_{#1}(\mathbb{F}_q)}
\newcommand{\Fq}{\mathbb{F}_q}
\newcommand{\F}{\mathcal{F}}
\newcommand{\FF}{\mathbb{F}}
\newcommand{\lan}{\langle}
\newcommand{\ran}{\rangle}
\newcommand{\HH}{\mathcal{H}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\btr}{{\sf B2R}}
\newcommand{\syt}{{\sf SYT}}
\newcommand{\B}{{\mathcal{B}}}
\newcommand{\C}{{\mathcal{C}}}
\newcommand{\CC}{{\mathbb{C}}}
\newcommand{\R}{{\mathbb{R}}}

\newcommand{\Z}{{\mathbb{Z}}}
\newcommand{\D}{{\mathcal{D}}}
\newcommand{\RR}{{\mathcal{R}}}
\newcommand{\TT}{{\mathcal{T}}}
\newcommand{\setofcontent}{{\mathfrak{C}}}
\newcommand{\symm}{{\mathfrak{S}}}
\DeclareMathOperator{\im}{im}
\DeclareMathOperator{\shape}{sh}
\usepackage[dvipsnames]{xcolor}

\usepackage{hyperref}
\usepackage{comment}
\usepackage{listings}
\usepackage{algorithm}
\usepackage{array}
\usepackage{longtable}
\usepackage{multirow}
\usepackage[all,cmtip]{xy}
\usepackage[mathscr]{euscript} 


\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{prop}[theorem]{Proposition}
\newtheorem{cor}[theorem]{Corollary}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{question}[theorem]{Question}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{example}[theorem]{Example}
\newtheorem{remark}[theorem]{Remark}
\numberwithin{equation}{section}



%% define your title in the usual way
\title[Spectrum of random-to-random shuffling in the Hecke algebra]{Spectrum of random-to-random shuffling in the Hecke algebra}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
%% for more than 3 names, use the Oxford comma: One Author, Two Author, Red Author, \and MidnightBlue Author
\author[Axelrod-Freed, Brauner, Chiang, Commins, and Lang]{\texorpdfstring{Ilani Axelrod-Freed\addressmark{1} , Sarah Brauner\addressmark{2}\thanks{\href{mailto:sarahbrauner@gmail.com}{sarahbrauner@gmail.com}. S. B. is supported by the NSF MSPRF DMS 2303060.}, Judy Hsin-Hui Chiang\addressmark{3},\\ Patricia Commins\addressmark{3}\thanks{P. C. is supported by NSF Graduate Research Fellowship.}, \and  Veronica Lang\addressmark{4} }{Ilani Axelrod-Freed , Sarah Brauner, Judy Hsin-Hui Chiang, Patricia Commins, and  Veronica Lang }}
\address{\addressmark{1} Massachusetts Institute of Technology, Cambridge, MA, USA \\ \addressmark{2}  Brown University, Providence, RI, USA \\ \addressmark{3} University of Minnesota, Minneapolis, MN, USA  \\ \addressmark{4} University of Michigan, Ann Arbor, MI, USA}

% \author[Optional shorter names]{Sarah Brauner\thanks{\href{mailto:hello@world.c}{hello@world.c}. Longer names me was partially supported by Grant 2017.11.14.$\partial$\;supp.}\addressmark{1} \and you\addressmark{2}}

% \author[Optional shorter names]{Judy Hsin-Hui Chiang\thanks{\href{mailto:hello@world.c}{hello@world.c}. Longer names me was partially supported by Grant 2017.11.14.$\partial$\;supp.}\addressmark{1} \and you\addressmark{2}}

% \author[Optional shorter names]{Patricia Commins\thanks{\href{mailto:hello@world.c}{hello@world.c}. Longer names me was partially supported by Grant 2017.11.14.$\partial$\;supp.}\addressmark{1} \and you\addressmark{2}}

% \author[Optional shorter names]{Veronica Lang\thanks{\href{mailto:hello@world.c}{hello@world.c}. Longer names me was partially supported by Grant 2017.11.14.$\partial$\;supp.}\addressmark{1} \and you\addressmark{2}}

%% then use \addressmark to match authors to institutions here
% \address{\addressmark{1}Department of This, University of That, There \\ \addressmark{2}School of Something, University of Something Else, Somewhere}
% \author[Axelrod-Freed]{Ilani Axelrod-Freed}
% \email{ilani\_af@mit.edu}
% \address{Department of Mathematics, Massachusetts Institute of Technology, Cambridge MA, 02139}
% \author[Brauner]{Sarah Brauner}
% \email{sarahbrauner@gmail.com}
% \address{LACIM,  Universit\'e du Qu\'ebec \`a Montréal, Montréal, QC H2X 3Y7}
% \author[Chiang, Commins]{Judy Hsin-Hui Chiang, Patricia Commins}
% \email{hchiang@umn.edu, commi010@umn.edu}
% \address{School of Mathematics, University of Minnesota, Minneapolis MN 55455}
% \author[Lang]{Veronica Lang}
% \email{langv@umich.edu}
% \address{Department of Mathematics, University of Michigan, Ann Arbor MI 48109}

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

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

%% 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 generalize random-to-random shuffling from a Markov chain on the symmetric group to one on the Type $A$ Iwahori Hecke algebra, and show that its eigenvalues are polynomials in $q$ with non-negative integer coefficients. Setting $q=1$ recovers results of Dieker and Saliola, whose computation of the spectrum of random-to-random in the symmetric group resolved a nearly 20 year old conjecture by Uyemura-Reyes. Our methods simplify their proofs by drawing novel connections to the Jucys--Murphy elements of the Hecke algebra, Young seminormal forms, and the Okounkov--Vershik approach to representation theory. }

%% 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{Hecke algebra, Markov chain, card shuffling, random-to-random, Jucys--Murphy elements, Young seminormal forms }%, Okounkov--Vershik approach to representation theory, integral probability}

%% 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, giveninits]{biblatex}
\addbibresource{bibliography.bib}
%% note the \printbibliography command at the end of the file which goes with these biblatex commands

\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

\section{Introduction}
In this abstract, we generalize the well-known but mysterious shuffling process \emph{random-to-random} $\RR_n$ from a Markov chain on the symmetric group $\symm_n$ to a Markov chain on the Type A Iwahori Hecke algebra $\HH_n(q)$. Building on seminal work by Dieker and Saliola \cite{DiekerSaliola}, we compute the complete spectrum of $\RR_n$ in $\HH_n(q)$, and show that its eigenvalues are polynomials in $q$ with non-negative integer coefficients. Our methods simplify the proof for $q=1$ by adopting the Okounkov--Vershik approach to the representation theory of the symmetric group and Hecke algebra, and drawing connections to the Jucys--Murphy elements and Young seminormal basis of $\symm_n$ and $\HH_n(q)$. 

This project is motivated by a growing interest in studying random walks on $\HH_n(q)$ from a combinatorial perspective. There is a rich connection between $\HH_n(q)$ and interacting particle systems, beginning with the work of Alcaraz--Droz--Henkel--Rittenberg \cite{alcaraz1994reaction} who realized that the generators of \emph{asymmetric simple exclusion processes (ASEPs)} satisfy the algebra relations of $\HH_n(q)$. Bufetov then showed in \cite{bufetov2020interacting} that this connection could be generalized to numerous important interacting particle systems with multiple species arising from statistical mechanics, including  ASEP, $M$-exclusion, TASEP, and stochastic vertex models \cite{bufetov2020interacting}. Many of these systems have been studied using algebraic combinatorics with great success; see for example \cite{ corteel2022compact,corteel2022multiline, diaconis2000analysis}. 

On the other hand, there is a beautiful theory of random walks on hyperplane arrangements (and more generally, left regular bands) pioneered by Bidigare--Hanlon--Rockmore \cite{bidigare1999combinatorial} and Brown \cite{BrownOnLRBs}, which was originally built as a way of understanding and computing the mixing times of card shuffling processes, i.e. Markov chains on the symmetric group. This approach forges important links between combinatorial representation theory, probability, statistical physics and dynamic data storage; see \cite{ assaf2009riffle, athanasiadis2010functions,ayyer2014combinatorial, ayyer2017spectral, diaconis2003mathematical, diaconis1995riffle, diaconis2000analysis, diaconis2023double, DiekerSaliola, Lafreniere-thesis}.  It has since been generalized to a broad class of random walks on semigroups in work of  Ayyer--Schilling--Steinberg--Thi\'ery \cite{ASST} and Rhodes--Schilling \cite{rhodes2019unified}.

Our work serves to unite these two perspectives, by defining and studying one of the most important shuffling processes arising in the latter setting---random-to-random---as a Markov chain on $\HH_n(q)$. This work is an extended abstract of the paper \cite{qr2rpaper}. 

\section{Random-to-random shuffling in the symmetric group}\label{sec:r2rsymmetric}
The random-to-random shuffling process $\RR_n$ acts on a permutation $(w_1, \cdots, w_n) \in \symm_n$ by removing a ``card'' $w_i$ with uniform probability then re-inserting it with uniform probability to a new position in the deck. One can think of this as a two-step process: 
\begin{enumerate}[leftmargin=*]
    \item Apply \emph{random-to-bottom} $\B^*_n$, which moves $w_i$ to the end of the word;
    \item Apply \emph{bottom-to-random} $\B_n$, which moves the last letter of the word to position $j$. 
\end{enumerate}
Formally, $\RR_n: \CC[\symm_n] \rightarrow \CC[\symm_n]$ acts on $\CC[\symm_n]$ by \emph{right} multiplication (i.e. by position):
\begin{align*}
    \RR_n(w):= w \cdot \underbrace{\left( \sum_{i=1}^{n} s_{i} \cdots s_{n-1}\right)}_{=:\B_n^*} \underbrace{\left( \sum_{j = 1}^{n} s_{n-1} \cdots s_{j} \right)}_{=:\B_n},
\end{align*}
where $s_k = (k,k+1) \in \symm_n$. To obtain a random walk on $\CC[\symm_n]$, normalize both $\B_n^*$ and $\B_n$ by $\frac{1}{n}$: the coefficient $[u]\RR_n(w)$ of $u \in \symm_n$ is the probability of obtaining $u$ from $w$. %after one iteration of $\RR_n$. 

\begin{example}
 $\RR_{3}(123) = 3 \cdot (123) + 2 \cdot (213) + 2 \cdot (132) + 1 \cdot (231) + 1 \cdot (312) + 0 \cdot (321)$.   
\end{example}

Random-to-bottom shuffling $\B_n^*$ is very well-studied and has numerous interesting connections to combinatorics.  Bidigare--Halon--Rockmore showed in \cite{bidigare1999combinatorial} that the eigenvalues of $\B_n^*$ acting on $\CC[\symm_n]$ are $0, 1, \cdots, n-2, n$, recovering a result of Phatarfod \cite{Phatarfod1991ONTM}. The multiplicity of the eigenvalue $j$ is $\binom{n}{j} d_{n-j},$
where $d_{n-j}$ is the $(n-j)$-\emph{derangement number} counting the number of permutations in $\symm_{n-j}$ with zero fixed points. The kernel of $\B^*_n$ carries the \emph{derangement representation} $\DD_n$ introduced by D\'esarm\'enien and Wachs \cite{FrenchDesarmenienWachs} (see \eqref{eq:derangementrep}, specialized to $q=1$), which is related to well-loved objects such as Gessel's fundamental quassisymmetric function \cite{Gessel}, the free left regular band \cite{brauner2023invariant}, the complex of injective words \cite{ReinerWebb}, and the configuration space of $n$ points in $\R^3$ \cite{hersh2017representation}. 

Random-to-\emph{random} shuffling is significantly harder to understand. It was first defined by Diaconis (see \cite[p100]{Uyemura-Reyes}), and studied by Uyemura-Reyes in his thesis \cite{Uyemura-Reyes}. Uyemura-Reyes conjectured that the eigenvalues of $\RR_n$ were non-negative integers, and proved this to be true in several cases. The full conjecture was open for almost two decades, until it was resolved by Dieker and Saliola in 2018 \cite{DiekerSaliola}. Random-to-random belongs to a family of ``symmetrized shuffling operators'' whose spectral properties are still quite mysterious, and which have been the topic of FPSAC talks in 2009 (the invited address by Volkmar Welker) and 2019 (a talk by Lafreni{\`e}re \cite{lafreniere2FPSAC}).


To state Dieker and Saliola's solution, recall that a skew shape (i.e., skew Young diagram) $\lambda \sm \mu$ is a \emph{horizontal strip} if it has at most one box in each column. The \emph{content} $ \content_{\lambda\sm \mu}$ of a skew shape $\lambda \sm \mu$ is defined by summing the difference of the column and row number for each box in $\lambda \sm \mu.$ Formally, letting $(i,j)$ indicate the coordinates of the box in the $i$-th row (ordered top-to-bottom, in English notation) and $j$-th column,
\[ \content_{\lambda\sm \mu}:= \sum_{(i,j) \in \lambda \sm \mu} (j-i).\]  
\noindent Dieker and Saliola showed that the eigenvalues of $\RR_n$ acting on $\CC[\symm_n]$ are indexed by horizontal strips $\lambda \sm \mu$, where $|\lambda| = n$.
The horizontal strip $\lambda \sm \mu$ gives  the eigenvalue 
\begin{equation}\label{eq:q=1_eigenvalues} 
\eigen_{\lambda \sm \mu} := \content_{\lambda \sm \mu} + \sum_{k=|\mu|+1}^{n} k. \end{equation}
Equation \eqref{eq:q=1_eigenvalues} implies that, remarkably,  the $\eigen_{\lambda \sm \mu}$ are non-negative integers, thereby proving Uyemura-Reyes's conjecture. Using \eqref{eq:q=1_eigenvalues}, Bernstein--Nestoridi \cite{bernstein2019cutoff} proved that $\RR_n$ exhibits cutoff behavior at $\frac{3}{4} n \log(n) - \frac{1}{4} \log(\log(n)).$

At the heart of the Dieker--Saliola's proofs in \cite{DiekerSaliola} is the representation theory of the symmetric group, which they use to inductively construct eigenvectors of $\RR_n$ from the kernels of $\RR_j$ for $j < n$. Our work will follow a similar strategy, but utilize different tools that both simplify their arguments and deepen the connections between $\RR_n$ and fundamental concepts in representation theory.
\section{Main Results: Deformation to the Hecke algebra}
We now deform $\RR_n$ to a Markov chain on the Hecke algebra $\HH_n(q)$, and describe its spectrum. Recall that the $q$-integer $[n]_q$ is defined for any $n \in \Z$ by 
\newpage
\[ [n]_q:= \frac{1-q^n}{1-q} = \begin{cases}
    1 + q+ \cdots + q^{n-1} & n > 0 \\
    0 & n = 0\\
-q^{-1} - q^{-2} - \cdots - q^{n} & n < 0. 
\end{cases}\]
Given $q \in \CC$, the Type $A$ Iwahori Hecke algebra $\HH_n(q)$ is the associative $\CC$-algebra on the generators $T_{s_1}, \cdots, T_{s_{n-1}}$, subject to the relations

\begin{enumerate}
    \item $T_{s_i}^2 = (q-1)T_{s_i} + q$ for all $1 \leq i \leq n-1$, 
    \item $T_{s_i} T_{s_j} = T_{s_j} T_{s_i}$ when $|i-j| \geq 2$, and 
    \item $T_{s_i} T_{s_{i+1}} T_{s_i} = T_{s_{i+1}} T_{s_i} T_{s_{i+1}}$ for all $1 \leq i \leq n-2$. 
\end{enumerate} 


The Hecke algebra is a $q$-deformation of the symmetric group algebra, in the sense that $\HH_n(1) = \CC[\symm_n]$. It has a $\CC$-basis $\{ T_w  :  w \in \symm_n\}$ where $T_w := T_{s_{i_1}}T_{s_{i_2}}\cdots T_{s_{i_k}}$ for a reduced expression $w = s_{i_1}s_{i_2}\cdots s_{i_k}$. 
We define the following $q$-deformation of $\RR_n$.

\begin{definition}\label{def:qr2r_intro}
For any $q \in \CC$, define $q$-random-to-random shuffling $\RR_n(q): \HH_n(q) \rightarrow \HH_n(q)$ by linearly extending 
\[ {\RR_n(q)}(T_w):= T_w \cdot \underbrace{\left( \sum_{i=1}^{n} T_{s_i} \cdots T_{s_{n-1}} \right)}_{=: {\B^*_n(q)}} \underbrace{\left( \sum_{j=1}^{n} \  T_{s_{n-1}} \cdots T_{s_j} \right)}_{=:{\B_n(q)}}. \]
 \end{definition}
Putting additional assumptions on $q$ allows us to define a random walk $\widetilde{\RR}_n(q)$ on $\HH_n(q)$ using a construction by Diaconis--Ram \cite[Theorem 4.3]{diaconis2000analysis}. Assume $q \geq 1 \in \R$, so that $q^{-1} \in (0,1] \subseteq \R$ can be understood as a probability. Define $\tT_{s_i}:= q^{-1}T_{s_i}$, and more generally let $\tT_w:= q^{-\ell(w)}T_w$, where $\ell(w)$ is the Coxeter length of the reduced word $w \in \symm_n$. Then $\tT_{s_i}$ acts by right multiplication on $\tT_w$: 
\begin{equation}\label{eq:heckeaction}
    \tT_w \cdot \tT_{s_i} := \begin{cases}
        \tT_{w s_i} & \ell(w s_i) > \ell(w) \\
        q^{-1} \tT_{w s_i} + (1-q^{-1}) \tT_w & \ell(w s_i) < \ell(w),
    \end{cases}
\end{equation}
thereby defining a Markov chain on $\HH_n(q)$. To obtain $\widetilde{\RR}_n(q)$, we first rewrite $\RR_{n}(q)$ in terms of the $\tT_{s_i}$, and then normalize. In other words, $\widetilde{\RR}_n(q):= \frac{1}{([n]_q)^2}\RR_n(q)$.


The goal of our work is to characterize the spectrum of ${\RR_n(q)}$ acting by right multiplication on $\HH_n(q)$. The eigenvalues of $\widetilde{\RR}_n(q)$ can be obtained immediately from those of $\RR_n(q)$. by restricting to the case where $q^{-1} \in (0,1] \subseteq \R$ and dividing by $([n]_q)^2$.   

Our spectral formula for $\RR_n(q)$ uses two combinatorial statistics. First, given a skew shape $\lambda \sm \mu$, we define the $q$-content $\content_{\lambda \sm \mu}(q):= \sum_{(i,j) \in \lambda \sm \mu} [j-i]_q.$
%\[ \content_{\lambda \sm \mu}(q):= \sum_{(i,j) \in \lambda \sm \mu} [j-i]_q. \]
Note that $\content_{\lambda \sm \mu}(q)$ is a Laurent polynomial in $q$ with integer coefficients; however, $q^{|\lambda|} \content_{\lambda \sm \mu}(q)$ is a genuine polynomial in $\Z[q]$ (with possibly negative coefficients).
\begin{example}
 Suppose $\lambda = (2,1,1)$ and $\mu = (1,1)$. Then $q^{4}\content_{(2,1,1) \sm (1,1)}(q) = q^{4} ( [1]_q + [-2]_q ).$   
\end{example}
\newpage

\noindent Second, let $\syt(\lambda)$ be the set of standard tableaux of shape $\lambda$ and  $\syt_n := \bigcup_{\lambda \vdash n} \syt(\lambda)$. Then $\frakt \in \syt_n$ has a \emph{descent} at position $i \in [n-1]$ if $i+1$ appears south and weakly west of $i$ in $\frakt$. Let ${\sf Des}(\frakt)$ be the set of descents of $\frakt$. We say $\frakt \in \syt_n$ is a \emph{desarrangement tableau} if the minimum element of $[n] \setminus {\sf Des}(\frakt)$ is even. Let $d^\mu$ be the number of desarrangement tableaux of shape $\mu$ and $f^\mu$ be the number of standard Young tableaux of shape $\mu$. 
\begin{example}\label{ex:derangement}\rm
The desarrangement tableaux of size $5$ are shown below:
\begin{center}
\ytableausetup{smalltableaux}
\begin{tabular}{c|c|c|c|c}
   \begin{ytableau} 1 & 3 & 4 & 5\\ 2 \end{ytableau}  &  \begin{ytableau} 1 & 3 & 4\\ 2 & 5 \end{ytableau} \ \ \ \begin{ytableau} 1 & 3 & 5\\ 2 & 4\end{ytableau} & \begin{ytableau} 1 & 3 & 4\\ 2\\ 5\end{ytableau} \ \ \ \begin{ytableau} 1 & 3 & 5\\ 2\\ 4\end{ytableau} &  \begin{ytableau} 1 & 3\\ 2 & 4\\ 5\end{ytableau} \ \ \ \begin{ytableau} 1 & 3\\ 2 & 5\\ 4\end{ytableau}  & \begin{ytableau} 1 & 3\\ 2\\ 4 \\ 5\end{ytableau} \ \ \ \begin{ytableau} 1 & 5\\ 2\\ 3 \\ 4\end{ytableau}\\[3em]
   $d^{(4,1)} = 1$  & $d^{(3,2)} = 2$ & $d^{(3,1,1)} = 2$ & $d^{(2,2,1)} = 2$ & $d^{(2,1,1,1)} = 2.$
\end{tabular}
\end{center}    
\end{example}
At last we are ready to state our main result, \Cref{thm:intromainthm} below, which computes the spectrum of $\RR_n(q)$. See \Cref{bigexample} for an illustration of the theorem when $n=4$, and \Cref{sec:proofideas} for the main ingredients used in the proof.



\begin{theorem}\label{thm:intromainthm} For any $q \in \CC,$ the right action of $\RR_n(q)$ on $\HH_n(q)$ has the following properties:
\begin{enumerate}
    \item All eigenvalues of $\RR_n(q)$ are of the form 
            \[ \eigen_{\lambda \sm \mu}(q) =  q^{n} \content_{\lambda \sm \mu}(q) + \sum_{k=|\mu|+1}^{n} q^{n-k} \  [k]_q \]
    where $\lambda \sm \mu$ is a horizontal strip with $|\lambda| = n$ and $0 \leq |\mu| \leq n$. 
\item Every eigenvalue $\eigen_{\lambda \sm \mu}(q)$ is a polynomial in $q$ with non-negative integer coefficients.
    \item The (algebraic) multiplicity of a fixed eigenvalue $\eigen(q)$ is given by \[ \sum_{\substack{\lambda \sm \mu \textrm{ a horizontal strip}: \\ \eigen_{\lambda \sm \mu}(q) = \eigen(q)}} f^\lambda  \ d^\mu. \]
\item If $q \in \R_{>0}$, then $\RR_n(q)$ is diagonalizable.
\end{enumerate}
\end{theorem}
\noindent We obtain the following special cases of combinatorial and probabilistic interest. 


\begin{cor}\label{cor:introsecondeigen}
The case $\lambda = (n-k,1^k)$ and $\mu = (j-k,1^k)$ gives the eigenvalue
\[ \eigen_{(n-k,1^k) \sm (j-k,1^k)}(q) = [n-j]_q \ [n+j-k]_q.\]
Setting $j=k=0$ gives
$\eigen_{(n) \sm \emptyset}(q) = [n]_q  [n]_q$, which is the largest eigenvalue of $\RR_n(q)$ when $q \in \R_{>0}$.
The corresponding stationary distribution for $\widetilde{\RR}_n(q)$ is 
the \emph{Mallows measure} of $\symm_n$: 
\[ \mathcal{M}(\symm_n, q^{-1}) = \sum_{w \in \symm_n} q^{\ell(w)} \tT_w. \]
\noindent Setting $j = 2$ and $ k=1$ gives $ \eigen_{(n-1,1) \sm (1,1)}(q) = [n-2]_q [n+1]_q$, which is the second largest eigenvalue of $\RR_n(q)$ when $q \in \R_{>0}$.
\end{cor}

\begin{example}\label{bigexample}\rm
We illustrate the eigenvalues for $\RR_{4}(q)$ below. For each $\lambda \sm \mu$, the shape $\mu$ is shaded in gray and the contents of each box of $\lambda \sm \mu$ are written in \textcolor{MidnightBlue}{blue}. The multiplicity $d^\mu f^\lambda$ of $\eigen_{\lambda \sm \mu}(q)$ is shown in the last column.
\setlength{\extrarowheight}{4mm}
\setlength{\tabcolsep}{.01pt}
\begin{center}
        \begin{longtable}{ccc}
            %Horizontal strip
            $\lambda \sm \mu$ & $\eigen_{\lambda \sm \mu}(q)$ &  Multiplicity in $\HH_n(q)$  \\[1mm] \hline
        %  &   & \\[1mm]
           ${\begin{ytableau}
               \color{MidnightBlue} 0 & \color{MidnightBlue} 1 & \color{MidnightBlue} 2 & \color{MidnightBlue} 3
           \end{ytableau}}$ & 
           $[4]_q \cdot [4]_q$  & $1$\\[1mm]
            \hline
            $\ydiagram[*(lightgray)]{3, 1}$  & $0$ & $3$\\
          ${\begin{ytableau}
              *(lightgray) & *(lightgray) & \color{MidnightBlue}{2}\\
              *(lightgray)
          \end{ytableau}}$  & $q^4\color{MidnightBlue}{[2]_q}\normalcolor + [4]_q = [6]_q$  & $3$\\
          $\begin{ytableau}
              *(lightgray) & \color{MidnightBlue}{1} & \color{MidnightBlue}{2} \normalcolor\\
              *(lightgray)
          \end{ytableau}$ &$q^4\left(\color{MidnightBlue}[1]_q + [2]_q \normalcolor\right) + \left(q[3]_q + [4]_q\right) = [2]_q \cdot [5]_q$  & $3$\\[.6cm]
            \hline
           $\ydiagram[*(lightgray)]{2,2}$ & $0$  & $2$\\
           $\begin{ytableau}
               *(lightgray) & *(lightgray)\\
               *(lightgray) & \color{MidnightBlue}{0}\normalcolor
           \end{ytableau}$  & $q^4\color{MidnightBlue}[0]_q \normalcolor + [4]_q = [4]_q$  & $2$\\[.6cm]
            \hline 
            $\ydiagram[*(lightgray)]{2,1,1}$  & $0$  & $3$\\
           $\begin{ytableau}
               *(lightgray) & *(lightgray)\\
               *(lightgray)\\
               {\color{MidnightBlue}{-2}}\normalcolor
           \end{ytableau}$  & $q^4\color{MidnightBlue}{[-2]_q} + \normalcolor{[4]_q} = [2]_q$  & $3$\\
          $\begin{ytableau}
              *(lightgray) & \color{MidnightBlue}{1}\\
              *(lightgray)\\
              \color{MidnightBlue}{-2}
          \end{ytableau}$   & $q^4\left(\color{MidnightBlue}[-2]_q + [1]_q\normalcolor\right)\normalcolor + \left(q[3]_q + [4]_q\right) = q^{3}[2]_q + [4]_q$ & $3$\\[.8cm]
            \hline 
            $\ydiagram[*(lightgray)]{1, 1, 1, 1}$ & $0$ & $1$
        \end{longtable}
    \end{center}
\end{example}
\section{Proof Ideas}\label{sec:proofideas}
Our overall strategy to prove \Cref{thm:intromainthm} is similar in spirit to \cite{DiekerSaliola}, in that we inductively construct eigenvectors for the action of $\RR_n(q)$ on the irreducible representations of $\HH_n(q)$ from the kernels of $\RR_j(q)$ for $j < n$. We assume $\HH_n(q)$ is semisimple, meaning $q$ is neither $0$ nor a primitive $k$th root of unity for $1 < k \leq n$. The irreducible representations of $\HH_n(q)$ in this case are called \emph{Specht modules} $S^\lambda$, and, like $\symm_n$, are indexed by partitions $\lambda$ of $n$. The branching rules for $\HH_n(q)$ in this setting also mirror those of $\symm_n$.


In fact, it is sufficient to construct an eigenbasis for the right action of $\RR_n(q)$ on a single Specht module $S^\lambda$, using the bimodule decomposition of $\HH_n(q)$
\begin{equation}\label{eq:bimodule} \HH_n(q) \cong \bigoplus_{\lambda \vdash n} (S^\lambda)^* \otimes S^\lambda,\end{equation}
where $S^\lambda$ is a right $\HH_n(q)$-module and $(S^\lambda)^*$ is its dual left $\HH_n(q)$-module. In particular, since $\RR_n(q)$ acts by right multiplication, its eigenspaces are left $\HH_n(q)$ modules. By \eqref{eq:bimodule} constructing a right $\RR_n(q)$-eigenbasis for every $S^\lambda$ determines both the full spectrum of $\RR_n(q)$ on $\HH_n(q)$, as well as the left $\HH_n(q)$-module structure on every eigenspace.


Intuitively, the eigenvalue $\eigen_{\lambda \sm \mu}(q)$ comes from a path in Young's lattice that starts at $\mu$ and ends at $\lambda$. The start of the path corresponds to an eigenvector $u \in S^\mu$ in the kernel of $\RR_{|\mu|}(q)$; through a somewhat miraculous process (described in \Cref{section:eigenvectorconstruction}), we are able to lift $u$ to an eigenvector of $\RR_n(q)$ in $S^\lambda$ with eigenvalue $\eigen_{\lambda \sm \mu}(q)$.



\subsection{Computation of the kernel}
As discussed above, the $\RR_n(q)$-eigenvectors of $S^\lambda$
are built from the kernel of $\RR_{|\mu|}(q)$ acting on $S^\mu$ for $\mu \subset \lambda$. Thus it is essential to understand $\ker\big(\RR_j(q)\big)$ for all $j \leq n$.

To do so, we relate $\B_n^*(q)$ to a Markov chain on $\CC[\F_n]$, the space of complete flags on the finite vector space $\FF_q^n$, introduced by Brown in \cite{BrownOnLRBs} and studied by the second and fourth authors, along with Reiner in \cite{brauner2023invariant}. 
The latter work computes the eigenspaces of the flag operator as $\GL{n}$-representations. The space $\CC[\F_n]$ decomposes as a $(\GL{n} \times \HH_n(q))$-bimodule; using this decomposition, our present work shows that the characteristic polynomial of $\B_n^*(q)$ is determined by that of the flag operator. Applying the branching rules of $\HH_n(q)$ in the semisimple case, we are thus able to prove:


\begin{theorem}\label{thm:kernel}
The right actions of $\B_n^*(q)$ and $\B_n(q)$ on $\HH_n(q)$ have characteristic polynomial 
\[ \chi(y,q) = \prod_{j=0}^{n} (y - [n-j]_q)^{\binom{n}{j}d_{j}},  \]
 where $d_{j}$ is the $j$-derangement number counting permutations in $\symm_{j}$ with zero fixed points. \smallskip
 
\noindent Whenever $\HH_n(q)$ is semisimple, both $\B_n^*(q)$ and $\B_n(q)$ are diagonalizable, and as a left module,
 \begin{equation}\label{eq:derangementrep} \ker \B_n^*(q)  \cong \bigoplus_{\substack{\frakt \in \syt_n \\ \frakt \textrm{ is a desarrangement tableau}}} \left(S^{\shape(\frakt)}\right)^*. \end{equation}
\noindent Whenever $q \in \R_{>0}$, one has $\ker \RR_n(q) = \ker \B_{n}^*(q)$.
\end{theorem}

The description of the kernel of $\B_n^*(q)$ in \eqref{eq:derangementrep} gives an $\HH_n(q)$-analog of the derangement representation $\DD_n$ discussed in \Cref{sec:r2rsymmetric}; see \cite[Proposition 3.1]{brauner2023invariant} for more properties of this fascinating representation. When $q \in \R_{>0}$, \Cref{thm:kernel} implies that the size of the kernel of $\RR_{|\mu|}(q)$ acting on $S^\mu$ will be $d^\mu$, the number of desarrangement tableau of shape $\mu$. This is crucial information, in that it describes how many eigenvectors from $S^\mu$ need to be lifted to $S^\lambda$. Note that $d^\mu$ is often larger than 1 (recall \Cref{ex:derangement}), a subtlety that significantly complicates the analysis of $\RR_n(q)$.


\subsection{Eigenvector construction}\label{section:eigenvectorconstruction}
Having established the starting point of our eigenvector construction, we now turn to the lifting process. Here, our approach diverges from \cite{DiekerSaliola}. The novelty of our method is to recursively relate $\RR_n(q)$ to the \emph{Jucys--Murphy elements of} $\HH_n(q)$:
\[ J_k(q):= \sum_{i=1}^{k-1} q^{i-k} \ T_{(i,k)} =  \sum_{i=1}^{k-1} q^{i-k} \ T_{s_1} T_{s_2} \cdots T_{s_{k-2}} T_{s_{k-1}} T_{s_{k-2}}  \cdots T_{s_2} T_{s_1} \]
and their many wonderful properties\footnote{Sometimes these elements are referred to as the \emph{additive Jucys--Murphy elements}, see \cite{elias2017categorical}.}. 

In particular, we prove the following relationship between $\RR_n(q)$, $\RR_{n-1}(q)$, and $J_n(q)$:

\begin{theorem}\label{thm:introrecursion}
For any $q \in \CC$, the following recursion holds in $\HH_n(q)$:
\[ \B_{n}(q) \RR_{n}(q) = \bigg( \textcolor{OliveGreen}{q \RR_{n-1}(q)} + \textcolor{Plum}{[n]_q} + \textcolor{MidnightBlue}{q^{n} J_{n}(q)} \bigg) \B_{n}(q). \]
\end{theorem}
\noindent (The colors here should be matched with \eqref{eq:recursiveeigenvalue} below). This connection with $J_k(q)$ unlocks a wealth of tools put forth by Dipper--James \cite{DipperJames}, Mathas \cite{Mathas} and others, which develop the representation theory of the Hecke algebra as a parallel to that of the symmetric group. Chief among these are \emph{Young's seminormal forms}, a family of idempotents 
\[ \{ p_{\frakt} \in \HH_n(q): \frakt \in \syt_n \} \]
which give an elegant basis for each $S^\lambda$; see \cite[p504]{MURPHY1992492} for a definition. The $\{ p_\frakt \}$ are a simultaneous eigenbasis for the Jucys--Murphy elements $J_1(q), \cdots, J_n(q)$, with \[ p_{\frakt} \ J_{k}(q) = \content_{\frakt,k}(q) \ p_{\frakt}, \]
where $ \content_{\frakt,k}(q)$ is the $q$-content of the box labeled by $k$ in $\frakt$.


The seminormal forms beautifully encode the connection between representations of $\HH_n(q)$ and $\syt_n$ as follows. For $\frakt \in \syt_n$, let $\frakt|_k$ be the subtableau of $\frakt$ obtained from restricting $\frakt$ to the boxes labeled $1, \cdots, k$, and let $\shape(\frakt|_k)$ be the shape of $\frakt|_k$. Then 
\[ \frakt|_k \in \syt \left(\shape(\frakt|_k)\right) \subseteq \syt_k, \] and we will think of each  $\frakt \in \syt_n$ as being built by a nested sequence of tableaux:
\[ \frakt|_1 \subseteq \frakt|_2 \subseteq \cdots \subseteq \frakt|_n = \frakt. \] 

Crucially, each $p_\frakt \in \HH_n(q)$ can be built from a tower of inclusions in the same way. Algebraically, the nested tableaux correspond to the algebra embedding $\HH_{k}(q) \subseteq \HH_{k+1}(q)$ sending $T_{s_i}$ to $T_{s_i}$. This idea is encapsulated in the \emph{Tower Rule} (\Cref{lem:tower-rule}) below, a folk theorem (see e.g. \cite{elias2017categorical}) which allows us to move between Hecke algebras of different sizes in a precise way. This is essential to our inductive arguments. 


Let $\{ p_\lambda: \lambda \vdash n\} $ be the collection of canonical central orthogonal idempotents that project onto the $S^\lambda$-isotypic components of $\HH_n(q)$. The $p_{\frakt}$ and $p_\lambda$ are related as follows: 

\begin{prop}[Tower Rule]\label{lem:tower-rule}
For any $\lambda \vdash n$ and $\frakt \in \syt(\lambda)$, we have 
\[ p_\lambda = \sum_{\frakt \in \syt(\lambda)} p_{\frakt}, \quad \quad \textrm{and} \quad \quad p_{\frakt} = p_{\shape\left(\frakt\vert_1\right)} \ p_{\shape\left(\frakt\vert_2\right)} \ \cdots \ p_{\shape\left(\frakt\vert_{n-1}\right)}  \ p_{\shape\left(\frakt\vert_n\right)}.  \]
\end{prop}


It will be important for us to state many of our results in terms of skew tableaux.  Given a skew shape $\lambda \sm \mu$, let $\syt(\lambda \sm \mu)$ be the set of skew tableaux of shape $\lambda \sm \mu$ filled with the letters $|\mu|+1, \cdots, |\lambda|$ with entries increasing across rows and down columns.
For $\frakt \in \syt(\lambda \sm \mu)$ with $|\mu| = j$ and $|\lambda| = n$, we use the Tower Rule to define
\[ p_{\frakt}:=   p_{\shape\left(\frakt\vert_j\right)} \ p_{\shape\left(\frakt\vert_j+1\right)} \ \cdots \ p_{\shape\left(\frakt\vert_{n-1}\right)}  \ p_{\shape\left(\frakt\vert_n\right)}.\]


\begin{example}\rm
If $\lambda = (4,3)$, $\mu = (3,1)$ and $\frakt = \text{\small{$\begin{ytableau}
            *(lightgray) & *(lightgray) & *(lightgray) & 6 \\
            *(lightgray) & 5 & 7. 
        \end{ytableau}$} \ ,}$ then $p_{\frakt} = p_{(3,1)} \ p_{(3,2)} \ p_{(4,2)} \ p_{(4,3)}$.
\end{example}
We combine \Cref{thm:introrecursion} with the properties of the seminormal forms to show how, given an eigenvector of $\RR_{n-1}(q)$, one obtains an eigenvector for $\RR_n(q)$. 
\begin{prop}\label{thm:recursive_eigenvector_construction}
Let $\HH_n(q)$ be semisimple and $\lambda' \subset \lambda$ with $|\lambda| = n$ and $|\lambda'| = n-1$.
Suppose that $u' \in S^{\lambda'}$ is an eigenvector for $\RR_{n-1}(q)$ with eigenvalue $\eigen$.
Then
\[ u:= u' \   \B_n(q) \ p_{\lambda} \]
belongs to $S^\lambda$, and is
either zero or an eigenvector for $\RR_n(q)$ with eigenvalue 
\begin{equation}\label{eq:recursiveeigenvalue} \textcolor{OliveGreen}{q \eigen} + \textcolor{Plum}{[n]_q} + \textcolor{MidnightBlue}{q^{n} \content_{\lambda \sm \lambda'}(q)}. \end{equation}
\end{prop}

Using the Tower Rule, we can then iterate the process in \Cref{thm:recursive_eigenvector_construction}.


\begin{cor}\label{cor:eigenvalues}
Let $\HH_n(q)$ be semisimple, and $\mu \subset \lambda$ where $|\mu| = j$ and $|\lambda| = n$. Suppose that $u \in S^\mu$ is in the kernel of $\RR_j(q)$. Then for any $\frakt \in \syt(\lambda \sm \mu)$,
\[ v_{(\frakt,u)}:= u \ p_{\frakt} \ \B_{j+1}(q) \B_{j+2}(q) \cdots \B_{n}(q) \]
belongs to $S^\lambda$, and is either zero or is an eigenvector for $\RR_n(q)$ with eigenvalue 
\[ q^{n} \content_{\lambda\sm \mu}(q)+ \sum_{k=j + 1}^{n} q^{n-k}[k]_q.  \]
\end{cor}
One can think of this process as iteratively adding boxes to a tableau of shape $\mu$ to obtain one of shape $\lambda$: the tableau $\frakt$ records the order that these boxes were added.
\newpage

\subsection{Obtaining an eigenbasis}\label{sec:eigenbasis}
\Cref{cor:eigenvalues} constructs many eigenvectors for $\RR_n(q)$, but it is does not yet explain (1)  when these eigenvectors are linearly independent (or even non-zero) in $S^\lambda$, and (2) whether all eigenvectors for $\RR_n(q)$ can be constructed in this way.


Answering these questions is the most technical and subtle part of proving \Cref{thm:intromainthm}. To do so, we will choose a subset of the vectors arising from \Cref{cor:eigenvalues}, and show that these form an eigenbasis for $S^\lambda$. 

Let $\frakt^{\lambda \sm \mu} \in \syt(\lambda \sm \mu)$ be the tableau given by filling a skew diagram of shape $\lambda \sm \mu$ with the entries $|\mu|+1,\cdots, n$ across each row, starting with the first. There is a sense in which $\frakt^{\lambda \sm \mu}$ is the largest element in $\syt(\lambda \sm \mu)$ with respect to a partial order coming from dominance order on $\syt_n$; see \cite[Definition 2.17]{qr2rpaper}.
\begin{example}\rm
For $\lambda = (5,3)$ and $\mu = (3,1)$, we have $\frakt^{\lambda \sm \mu} = {\text{ \small{$\begin{ytableau}
            *(lightgray) & *(lightgray) & *(lightgray) & 5 & 6\\
            *(lightgray) & 7 & 8 
        \end{ytableau}$}} } \ .$ 
\end{example}
 

\begin{theorem}\label{thm:eigenbasis}
Suppose $\frakt \in \syt(\lambda \sm \mu)$, and let $v_{(\frakt, u)}\in S^\lambda$ be constructed as in \Cref{cor:eigenvalues}. 
\begin{enumerate}
    \item If $\lambda \sm \mu$ is not a horizontal strip, then $v_{(\frakt,u)} = 0$.
    \item For any $\frakt \in \syt(\lambda \sm \mu)$, one has that $v_{(\frakt,u)}$ is a scalar multiple of $v_{(\frakt^{\lambda \sm \mu},u)}$.
    \item Let $q \in \R_{>0}$ and $\kappa_\mu$ be a basis for the kernel of $\RR_{|\mu|}(q)$ acting on $S^\mu$. Then $\basis_\lambda$ is basis for $S^\lambda$, where
    \[ \basis_\lambda:= \{  v_{(\frakt^{\lambda \sm \mu},u)}: \lambda \sm \mu \textrm{ is a horizontal strip and } u \in \kappa_\mu \}. \]
\end{enumerate}
\end{theorem}
\begin{proof}[Proof idea]
Write $\symm_{\lambda} \leq \symm_n$ as the Young subgroup of shape $\lambda$ and $X_{\lambda}$ as the set of minimal length representatives of the right coset $\symm_{\lambda} \sm \symm_n$. We show that   
\begin{equation}\label{eq:factorization} \B_{j+1}(q) \cdots \B_{n}(q)= \bigg( \sum_{w \in \symm_{(1^j,n-j)}} T_w \bigg) \bigg( \sum_{v \in X_{(j,n-j)}} T_v \bigg). \end{equation}
This means that for $u \in S^\mu$, right multiplication by $\B_{j+1}(q) \cdots \B_{n}(q)$ has image contained in the representation $S^{\mu} \otimes S^{(n-j)}$ induced from $\HH_{j}(q) \otimes \HH_{n-j}(q)$ to $\HH_n(q)$. This can be used to prove (1) via Pieri-rules for $\HH_n(q)$. Proving (2) uses a straightening argument: at each step in the iterative construction in \Cref{cor:eigenvalues}, we use properties of the seminormal units and \eqref{eq:factorization} to show that $v_{(\frakt,u)}$ can be rewritten as a scalar multiple of $v_{(\frakt^{\lambda \sm \mu},u)}$. (In fact, the analogous argument for (2) is missing for $\RR_n$ in \cite{DiekerSaliola}; our work at $q=1$ corrects this error.) Finally, (3) follows from (1) and (2) by applying a counting argument, using the fact that by \Cref{thm:kernel}, when $q \in \R_{>0}$, we have $|\kappa_\mu| = d^\mu$.
\end{proof}
\begin{example}\rm
Let $\lambda = (4,1)$. Then $\dim(S^{\lambda}) = f^{\lambda} = 4$, and $\basis_{(4,1)}$ is constructed from: 
\[ \frakt^{(4,1) \sm (1,1)} = \text{\small{$\begin{ytableau}
            *(lightgray) & 3 & 4 & 5 \\
            *(lightgray)
        \end{ytableau}$}} \quad  \frakt^{(4,1) \sm (2,1)} =  \text{\small{$\begin{ytableau}
            *(lightgray) & *(lightgray) & 4 & 5\\
            *(lightgray)
        \end{ytableau}$}} \quad  \frakt^{(4,1) \sm (3,1)} =  \text{\small{$\begin{ytableau}
            *(lightgray) & *(lightgray) & *(lightgray) & 5\\
            *(lightgray)
        \end{ytableau}$}} \quad  \frakt^{(4,1) \sm (4,1)} = 
        \text{\small{$\begin{ytableau}
            *(lightgray) & *(lightgray) & *(lightgray) &*(lightgray) \\
            *(lightgray) 
        \end{ytableau}$}} \]
\end{example}

Note that once we have \Cref{thm:eigenbasis}, the hard work of \Cref{thm:intromainthm} is done: the characteristic polynomial of $\RR_n(q)$ for any $q \in \CC$ is determined by the case $q \in \R_{>0}$.
\acknowledgements{The authors are very grateful to Alexey Bufetov, Benjamin Elias, Darij Grinberg, Vic Reiner, Franco Saliola, and Peter Webb for illuminating discussions.}

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



\end{document}
