\documentclass[finalversion]{FPSAC2018}
\articlenumber{46}

\usepackage{xcolor,listings,multicol}
\usepackage{rotating}
\usepackage[vcentermath]{youngtab}
\usepackage{enumerate}
\usepackage[all,cmtip]{xy}
\usepackage{tikz}
\usetikzlibrary{arrows,matrix}
\usepackage{comment}
\usepackage{color}
%\usepackage{subcaption}

%\usepackage[colorlinks=true, pdfstartview=FitV, linkcolor=blue, citecolor=blue, urlcolor=blue]{hyperref}

% use these commands for typesetting doi and arXiv references in the bibliography
%\newcommand{\doi}[1]{\href{https://doi.org/#1}{\texttt{doi:#1}}}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}

% For easier display of e-mail
\newcommand{\email}[1]{\href{mailto:#1}{#1}}

\newcommand{\iso}{\cong}
%\newcommand{\qedbox}{\rule{2mm}{2mm}}
%\renewcommand{\qedsymbol}{\qedbox}
\newcommand{\qbinom}[3]{\genfrac{[}{]}{0pt}{}{#1}{#2}_{#3}}
\newcommand{\absval}[1]{\left\lvert #1 \right\rvert}
\newcommand{\case}[1]{\vspace{12pt}\noindent\underline{#1}:}
\newcommand{\fs}{\mathcal{S}} % flagged Schur function
\newcommand{\mbf}{\mathbf}
\newcommand{\swt}[1]{\left\langle #1 \right\rangle} % Spectral weight or amplitude
\newcommand{\merge}[1]{\vee_{#1}} % merge

\DeclareMathOperator{\supp}{supp} % Support
\DeclareMathOperator{\inter}{int} % queuing interval
\DeclareMathOperator{\wt}{wt} % weight
\DeclareMathOperator{\pr}{pr} % promotion
\DeclareMathOperator{\id}{id} % identity
\DeclareMathOperator{\ch}{ch} % character
\DeclareMathOperator{\gr}{gr} % grading

\newcommand{\xx}{\mathbf{x}}
\newcommand{\mm}{\mathbf{m}}
\newcommand{\qq}{\mathbf{q}}
\newcommand{\MLQ}{\mathbf{S}}

\newcommand{\mcA}{\mathcal{A}}
\newcommand{\mcF}{\mathcal{F}}
\newcommand{\mcM}{\mathcal{M}}
\newcommand{\mcW}{\mathcal{W}}
\newcommand{\mcI}{\mathcal{I}}

\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\CC}{\mathbb{C}}

\newcommand{\bze}{\overline{0}}
\newcommand{\bon}{\overline{1}}
\newcommand{\btw}{\overline{2}}
\newcommand{\bth}{\overline{3}}
\newcommand{\bfo}{\overline{4}}
\newcommand{\bfive}{\overline{5}}
\newcommand{\bsix}{\overline{6}}
\newcommand{\bseven}{\overline{7}}
\newcommand{\beight}{\overline{8}}
\newcommand{\bi}{\overline\imath}
\newcommand{\bk}{\overline{k}}
\newcommand{\brr}{\overline{r}}
\newcommand{\bn}{\overline{n}}
\newcommand{\ellbar}{\overline{\ell}}

%\let\sumnonlimits\sum
%\let\prodnonlimits\prod
%\let\cupnonlimits\bigcup
%\let\capnonlimits\bigcap
%\renewcommand{\sum}{\sumnonlimits\limits}
%\renewcommand{\prod}{\prodnonlimits\limits}
%\renewcommand{\bigcup}{\cupnonlimits\limits}
%\renewcommand{\bigcap}{\capnonlimits\limits}

\newenvironment{verlong}{}{}
\newenvironment{vershort}{}{}
\newenvironment{noncompile}{}{}
\excludecomment{verlong}
\includecomment{vershort}
\excludecomment{noncompile}
\newcommand{\rev}{\operatorname{rev}}
\newcommand{\conncomp}{\operatorname{conncomp}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\powset}[2][]{\ifthenelse{\equal{#2}{}}{\mathcal{P}\left(#1\right)}{\mathcal{P}_{#1}\left(#2\right)}}
% $\powset[k]{S}$ stands for the set of all $k$-element subsets of
% $S$. The argument $k$ is optional, and if not provided, the result
% is the whole powerset of $S$.
\newcommand{\set}[1]{\left\{ #1 \right\}}
% $\set{...}$ yields $\left\{ ... \right\}$.
\newcommand{\abs}[1]{\left| #1 \right|}
% $\abs{...}$ yields $\left| ... \right|$.
\newcommand{\tup}[1]{\left( #1 \right)}
% $\tup{...}$ yields $\left( ... \right)$.
\newcommand{\ive}[1]{\left[ #1 \right]}
% $\ive{...}$ yields $\left[ ... \right]$.
\newcommand{\verts}[1]{\operatorname{V}\left( #1 \right)}
% $\verts{...}$ yields $\operatorname{V}\left( ... \right)$.
\newcommand{\edges}[1]{\operatorname{E}\left( #1 \right)}
% $\edges{...}$ yields $\operatorname{E}\left( ... \right)$.
\newcommand{\arcs}[1]{\operatorname{A}\left( #1 \right)}
% $\arcs{...}$ yields $\operatorname{A}\left( ... \right)$.
\newcommand{\underbrack}[2]{\underbrace{#1}_{\substack{#2}}}
% $\underbrack{...1}{...2}$ yields
% $\underbrace{...1}_{\substack{...2}}$. This is useful for doing
% local rewriting transformations on mathematical expressions with
% justifications.
\newcommand{\mlnode}[1]{\node[circle, draw=black] at (#1){\phantom{c}};}

% Dark red emphasis
\definecolor{darkred}{rgb}{0.7,0,0} % darkred color
\newcommand{\defn}[1]{{\color{darkred}\emph{#1}}} % emphasis of a definition

%% For typesetting code listings                                                
\usepackage{listings}
\lstdefinelanguage{Sage}[]{Python}
{morekeywords={False,sage,True},sensitive=true}
\lstset{
  frame=single,
  showtabs=False,
  showspaces=False,
  showstringspaces=False,
  commentstyle={\ttfamily\color{dgreencolor}},
  keywordstyle={\ttfamily\color{dbluecolor}\bfseries},
  stringstyle={\ttfamily\color{dgraycolor}\bfseries},
  language=Sage,
  basicstyle={\footnotesize\ttfamily},
  aboveskip=0.75em,
  belowskip=0.75em,
  xleftmargin=.15in,
}
\definecolor{dblackcolor}{rgb}{0.0,0.0,0.0}
\definecolor{dbluecolor}{rgb}{0.01,0.02,0.7}
\definecolor{dgreencolor}{rgb}{0.2,0.4,0.0}
\definecolor{dgraycolor}{rgb}{0.30,0.3,0.30}
\newcommand{\dblue}{\color{dbluecolor}\bf}
\newcommand{\dred}{\color{dredcolor}\bf}
\newcommand{\dblack}{\color{dblackcolor}\bf}

\usepackage{xparse}

\makeatletter
% \specialmergetwolists{<coupler>}{<list1>}{<list2>}{<return macro>}
% \specialmergetwolists*{<coupler>}{<listcmd1>}{<listcmd2>}{<return macro>}
\protected\def\specialmergetwolists{%
  \begingroup
  \@ifstar{\def\cnta{1}\@specialmergetwolists}
    {\def\cnta{0}\@specialmergetwolists}%
}
\def\@specialmergetwolists#1#2#3#4{%
  \def\tempa##1##2{%
    \edef##2{%
      \ifnum\cnta=\@ne\else\expandafter\@firstoftwo\fi
      \unexpanded\expandafter{##1}%
    }%
  }%
  \tempa{#2}\tempb\tempa{#3}\tempa
  \def\cnta{0}\def#4{}%
  \foreach \x in \tempb{%
    \xdef\cnta{\the\numexpr\cnta+1}%
    \gdef\cntb{0}%
    \foreach \y in \tempa{%
      \xdef\cntb{\the\numexpr\cntb+1}%
      \ifnum\cntb=\cnta\relax
        \xdef#4{#4\ifx#4\empty\else,\fi\x#1\y}%
        \breakforeach
      \fi
    }%
  }%
  \endgroup
}
\makeatother

\theoremstyle{plain}
\newtheorem{thm}{Theorem}[section]
\newtheorem{lemma}[thm]{Lemma}
\newtheorem{conj}[thm]{Conjecture}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{cor}[thm]{Corollary}
\theoremstyle{definition}
\newtheorem{dfn}[thm]{Definition}
\newtheorem{example}[thm]{Example}
\newtheorem{remark}[thm]{Remark}
\numberwithin{equation}{section}
%\numberwithin{figure}{section}
%\numberwithin{table}{section}
%\setcounter{section}{-1}

% For breaking equations across multiple pages
% \allowdisplaybreaks[1]

\usepackage[colorinlistoftodos]{todonotes}
\newcommand{\erik}[1]{\todo[size=\tiny,color=green!30]{#1 \\ \hfill --- Erik}}
\newcommand{\Erik}[1]{\todo[size=\tiny,inline,color=green!30]{#1
      \\ \hfill --- Erik}}
\newcommand{\darij}[1]{\todo[size=\tiny,color=red!30]{#1 \\ \hfill --- Darij}}
\newcommand{\Darij}[1]{\todo[size=\tiny,inline,color=red!30]{#1
      \\ \hfill --- Darij}}
\newcommand{\travis}[1]{\todo[size=\tiny,color=blue!30]{#1 \\ \hfill --- Travis}}
\newcommand{\Travis}[1]{\todo[size=\tiny,inline,color=blue!30]{#1
      \\ \hfill --- Travis}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\title{Multiline queues with spectral parameters}

\author{Erik Aas\thanks{\href{mailto:eaas@kth.se}{eaas@kth.se}}\addressmark{1},
Darij
Grinberg\thanks{\href{mailto:darij.grinberg@gmail.com}{darij.grinberg@gmail.com}}\addressmark{2},
\and Travis
Scrimshaw\thanks{\href{mailto:tcscrims@gmail.com}{tcscrims@gmail.com}.
Travis Scrimshaw was partially supported by the Australian Research
Council DP170102648 and the National Science Foundation RTG grant
DMS-1148634.}\addressmark{3}}

\address{\addressmark{1}Department of Mathematics, Pennsylvania State
University, McAllister Building, State College, PA 16802, USA
\\ \addressmark{2}School of Mathematics, University of Minnesota, 206 Church St. SE, Minneapolis, MN 55455, USA
\\ \addressmark{3}School of Mathematics and Physics, The University of Queensland, St. Lucia, QLD 4072, Australia}

%\urladdr{http://www.cip.ifi.lmu.de/~grinberg/}
%\urladdr{https://sites.google.com/view/tscrim/home}

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

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

\abstract{
Using the description of multiline queues as functions on words, we introduce the notion of a spectral weight of a word by defining a new weighting on multiline queues.
We show that the spectral weight of a word is invariant under a natural action of the symmetric group, giving a proof of the commutativity conjecture of Arita, Ayyer, Mallick, and Prolhac.
We give a determinant formula for the spectral weight of a word, which gives a proof of a conjecture of the first author and Linusson.
}

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


\keywords{multiline queue, TASEP, R-matrix, symmetric function}
%\subjclass[2010]{05A19,05E05,16T25, 60C05}

\usepackage[backend=bibtex]{biblatex}
\addbibresource{46-Aas-Grinberg-Scrimshaw.bib}

\begin{document}

\maketitle

%=====================================================================
\section{Introduction}
\label{sec:introduction}

The totally asymmetric exclusion process (TASEP) is a non-equilibrium stochastic process  that has received significant attention in various fields, such as probability theory, combinatorics, physics, biology, and civil engineering over the past few decades.
For some examples, we refer the reader to~\cite{AasLin17,AAMP,BE07,BP14,DEHP93,KMO15,KMO16} and references therein.
In this paper, we consider the TASEP on a ring with $n$ sites and $\ell$ species of particles.
Thus, we will consider the states to be words $u$ in the alphabet $\{1, \dotsc, \ell\}$ of length $n$, where we take the indices to be $\ZZ / n \ZZ$.
We will also consider the process to be discrete in time.

The steady state of the TASEP is known in terms of another process introduced in~\cite{FM06} using (ordinary) multiline queues (MLQs) and by applying what is now known as the Ferrari--Martin (FM) algorithm.
In~\cite{KMO15,KMO16}, the FM algorithm was reformulated in terms of the combinatorial $R$-matrix~\cite{NY97,Shimozono02} and using type $A_{n-1}^{(1)}$ Kirillov--Reshetikhin crystals~\cite{KKMMNN92}.
Moreover, it connects the TASEP with five-vertex models, corner transfer matrices, 3D integrable lattice models, and the tetrahedron equation of~\cite{Zam80}, yielding a new matrix product formula for the steady state distribution.

We describe MLQs as functions on words of a fixed length $n$ following~\cite{AAMP}, where it was referred to as the generalized FM algorithm.
We introduce a new weighting of MLQs, which is the weight of the MLQ considered as a tensor product of Kirillov--Reshetikhin crystals.
This allows us to define the spectral weight of a word $u$ to be the sum of the weights of all ordinary MLQs $\qq$ such that $u = \qq(1^n)$.
We also introduce the notation of a $\sigma$-twisted MLQ, where $\sigma$ is a permutation.
Our main result is that for a fixed permutation $\sigma$, the sum of the weights of all $\sigma$-twisted MLQs $\qq_{\sigma}$ such that $u = \qq_{\sigma}(1^n)$ equals the spectral weight of $u$.
To this end, we construct an action of the symmetric group on MLQs that corresponds, under the usual FM algorithm, to the natural action by letters on words.
This action is given by applying a combinatorial $R$-matrix to an
MLQ,\footnote{This operation has also previously appeared in Danilov and
Koshevoy~\cite{DanilovKoshevoy} (see also~\cite[Chapter~4]{Gorodentsev2}).} and we show that does not change the MLQ as a function on words.

As a consequence, we obtain a proof of the commutativity conjecture of~\cite{AAMP} when we specialize all our weight parameters to $1$.
However, we note that the interlacing property of~\cite{AAMP} does not generalize to our weighting of MLQs.
Furthermore, we give a determinant expression for the spectral weight of decreasing words by using the Lindstr\"om--Gessel--Viennot Lemma~\cite{GV85,Lindstrom73}.
By combining these results, we obtain a proof of~\cite[Conjecture 3.10]{AasLin17}.

One potential application is that our weighting could be used to describe the steady state distribution for the inhomogeneous TASEP~\cite{AM13,AL14}.
Furthermore, we expect that our weighting scheme can be extended to the totally asymmetric zero range process (TARZP), where multiple particles can occupy the same site~\cite{KMO16TARZP,KMO16TARZPII}.
This comes from the fact that the TARZP can also be realized using a tensor product of Kirillov--Reshetikhin crystals (under rank-level duality) using combinatorial $R$-matrices with analogous connections to corner transfer matrices and the tetrahedron equation.
Similarly, this extension of our results could be used to describe the steady state distribution for the inhomogeneous TARZP defined in~\cite{KMO16II}.

This extended abstract is organized as follows.
In Section~\ref{sec:background}, we provide the necessary background.
In Section~\ref{sec:result}, we state our results.
In Section~\ref{sec:proof_sketch}, we sketch the proof of our main result.
In Section~\ref{sec:tasep}, we describe the connection between our work and the TASEP.









%=====================================================================
\section{Background}
\label{sec:background}

Fix a positive integer $n$. Let $\ive{n}$ denote the set $\set{1, 2, \dotsc, n}$.
Let $\mcW_n$ be the set of words $u = u_1 \dotsm u_n$ in the ordered alphabet $\mcA := \{1 < 2 < 3 < \cdots \}$.
We will consider the indices of letters in a word to be taken modulo $n$ (that is, $u_{k+n} = u_k$ for all $k$).
Let $\xx := \{x_1, x_2, x_3, \ldots\}$ be indeterminates.

The \defn{type} of a word $u$ is the vector $\mm = (m_1, m_2, \ldots)$, where $m_i$ is the number of occurrences of $i$ in $u$.
We sometimes refer to $u_i = t$ as a \defn{particle at $i$ of class $t$}.
A word $u$ of type $\mm$ is \defn{packed} if there exists an $\ell$ such that $m_i \neq 0$ for $1 \leq i \leq \ell$ and $m_i = 0$ for $i > \ell$. We will also call the type $\mm$ itself packed in this case.
We call $\ell$ the number of \defn{classes} in $u$.
We \defn{merge} two adjacent classes $i,i+1$ in a packed word $u$ to obtain a new packed word as follows: first replace all occurrences of $i+1$ in $u$ by $i$, then replace all occurrences of $j$ in $u$ by $j-1$, for each $j > i$.
We denote the merging of $i$ and $i+1$ in $u$ by $\merge{i} u$, and for $T = \set{t_1 < \cdots < t_k} \subseteq \ive{\ell-1}$, we set $\bigvee_T u := \merge{t_1} \cdots \merge{t_k} u$.

We define an \defn{$r$-queue} $q$ to be any subset of $\ive{n}$ of size $r$. When $r$ is clear, we will simply call $q$ a \defn{queue}.
The \defn{weight} of a queue $q$ is $\wt(q) := \prod_{i \in q} x_i$.
We equate $q$ with a function from $\mcW_n$ to itself as follows.
Fix a word $u \in \mcW_n$, and let $\mm = (m_1, m_2, \ldots)$ be the type of $u$.
Define $p_i(\mm) := m_1 + m_2 + \cdots + m_i$, and when $\mm$ is clear, we simply write $p_i$.
There exists a unique $t$ such that
$
p_{t-1} \leq r < p_t.
$
The output word $v = q(u)$ will have type $(m_1, \dots, m_{t-1}, r-p_{t-1}, p_{t}-r, m_{t+1}, m_{t+2}, \ldots)$.
Note that $p_{t} - r = m_{t} + (p_{t-1} - r)$.
We think of this as splitting the class $t$ into two new classes $t$ and $t+1$. The following algorithm computes $v = q(u)$. In the start no letter of $v$ is set.

\begin{description}
\item[Phase I]
  Go through all $i$ such that $u_i > t$ in any order such that larger letters precede smaller ones.%
  \footnote{The order in which equal letters are processed does not matter, as a simple argument shows.}
  When considering a site $i$, find the first $j$ weakly to the left (cyclically) of $i$ such that $j \notin q$ and $v_j$ is not set.
  Then set $v_j = u_i + 1$.

\item[Phase II]
  Go through all $i$ such that $u_i < t$ in any order such that smaller letters precede larger ones.
  When considering a site $i$, find the first $j$ weakly to the right of $i$ such that $j \in q$ and $v_j$ is not set.
  Then set $v_j = u_i$.

\item[Phase III]
  At this point, there are $m_t$ unset values $v_i$. For such $i$, set $v_i = t$ for $i \in q$ and $v_i = t+1$ for $i\notin q$.
\end{description}

\begin{example}
\label{ex:first_queue}
We consider the $4$-queue $q = \{1, 4, 8, 9\}$ and the word $u = 346613321$.
Thus, the type of $u$ is $\mm = (2, 1, 3, 1, 0, 2, 0, \ldots)$ with $p_2 = 3$ and $p_3 = 6$, and so $t = 3$.
To compute $q(u)$, draw the following diagram
(whose upper row shows $u$, whose lower row shows $q(u)$,
and whose middle row represents the set $q$ by balls in the positions of its elements):
\[
\begin{tikzpicture}[scale=1.3,baseline=0]
\node (i1) at (1,1) {$3$};
\node (i2) at (2,1) {$4$};
\node (i3) at (3,1) {$6$};
\node (i4) at (4,1) {$6$};
\node (i5) at (5,1) {$1$};
\node (i6) at (6,1) {$3$};
\node (i7) at (7,1) {$3$};
\node (i8) at (8,1) {$2$};
\node (i9) at (9,1) {$1$};
\node (t1) at (1,-1) {$2$};
\node (t2) at (2,-1) {$7$};
\node (t3) at (3,-1) {$7$};
\node (t4) at (4,-1) {$3$};
\node (t5) at (5,-1) {$4$};
\node (t6) at (6,-1) {$4$};
\node (t7) at (7,-1) {$5$};
\node (t8) at (8,-1) {$1$};
\node (t9) at (9,-1) {$1$};
\node[circle,draw=black] (q1) at (1,0) {};
\node[circle,draw=black] (q2) at (4,0) {};
\node[circle,draw=black] (q3) at (8,0) {};
\node[circle,draw=black] (q4) at (9,0) {};
\draw[->,red] (i4) -- (4,0.2) .. controls (3.7,0.2) and (3.4,0) .. (3,0) -- (2,0) -- (t2);
\draw[->,red] (i3) -- (t3);
\draw[->,red] (i2) -- (2,0.1) .. controls (1.7,-0.1) and (1.3,-0.2) .. (1,-0.2) -- (0,-0.2);
\draw[>->,red] (10,-0.2) -- (8,-0.2) -- (7,-0.2) -- (t7);
\draw[->,blue] (i5) -- (5,0) -- (q3);
\draw[->,blue] (q3) -- (t8);
\draw[->,blue] (i9) -- (q4);
\draw[->,blue] (q4) -- (t9);
\draw[->,blue] (i8) -- (8,0.2) .. controls (9.5,0.2) .. (10,0.1);
\draw[>->,blue] (0,0.1) -- (q1);
\draw[->,blue] (q1) -- (t1);
\end{tikzpicture}
\]
where the paths in red correspond to Phase I and those in blue are from Phase II. Hence, we have $q(346613321) = 277344511$, which has type $(2,1,1,2,1,0,2,\ldots)$.
\end{example}

Since Phase I only deals with $j \notin q$, and Phase II only with $j\in q$, these two phases commute.
We illustrate the situation $v = q(u)$ with a $2 \times n$ array where the first row is the word $u$, and second row has a circle labelled $v_j$ for $j \in q$ or a square labelled $v_j$ for $j \notin q$ in position $j$.
Using this convention, we can write Example~\ref{ex:first_queue} as
\[
\begin{tikzpicture}[baseline=10]
  \def\ll{0.65}   % level 2
  \foreach \i in {5,9} { \node at (\i,\ll) {$1$}; }
  \foreach \i in {8} { \node at (\i,\ll) {$2$}; }
  \foreach \i in {1,6,7} { \node at (\i,\ll) {$3$}; }
  \foreach \i in {2} { \node at (\i,\ll) {$4$}; }
  \foreach \i in {3,4} { \node at (\i,\ll) {$6$}; }
  \foreach \i in {1,4,8,9} { \draw (\i,0) circle (0.3); }
  \foreach \i in {2,3,5,6,7} { \draw (\i-.3,0-.3) rectangle +(0.6,+0.6); }
  \foreach \i in {8,9} { \node at (\i,0) {$1$}; }
  \foreach \i in {1} { \node at (\i,0) {$2$}; }
  \foreach \i in {4} { \node at (\i,0) {$3$}; }
  \foreach \i in {5,6} { \node at (\i,0) {$4$}; }
  \foreach \i in {7} { \node at (\i,0) {$5$}; }
  \foreach \i in {2,3} { \node at (\i,0) {$7$}; }
\end{tikzpicture}
\]

There is an obvious duality in the definition of the labelling process above.

\begin{lemma}[Duality]
  Let $q$ be a queue and $u$ be a packed word with $\ell$ classes.
  Define a new word $v$ by letting $v_i = \ell + 1 - u_{n+1-i}$ and a new queue $q'$ by letting $i \in q'$ if and only if $n+1-i \notin q$.
 Then $q(u)_i = \ell + 2 - q'(v)_{n+1-i}$.
\end{lemma}

%\begin{remark} (Excision)
%  Fix a queue $q$ and a word $u$, and let $i,j$ be columns. Suppose that the $s$-flow from $j+1$ to $j$ equals the $s$-flow from $i+1$ to $i$ for each $s > t$, and that the $s$-flow from $i$ to $i+1$ equals the $s$-flow from $j$ to $j+1$ for each $s < t$. Then we have $q_{|\inter[i,j]^c}(u_{|\inter[i,j]^c}) = (q(u))_{|\inter[i,j]^c}$. Here, for a (cyclic) word $u$, we let $u_{|\inter[i,j]^c}$ denote the (cyclic) word gotten from simply removing the closed (cyclic) interval $\inter[i,j]$, and similarly for $q_{|\inter[i,j]^c}$.
%\end{remark}

\begin{lemma}[Monotonicity]
\label{le:mono}
  For any $t \in \ZZ_{\geq 1}$, let $f_t \colon \{1,2, \ldots\} \to \{1,2\}$ be given by $f_t(x) = 1$ for $x \leq t$ and $f_t(x) = 2$ for $x > t$.
  Let $q$ be a queue, $u$ be any word, and $i,j \in \ive{n}$.
  We have $q(u)_i \leq q(u)_j$ if and only if each $t$ satisfies $q(f_t(u))_i \leq q(f_t(u))_j$.
\end{lemma}

Lemma~\ref{le:mono} tells us that when $q$ is considered as a function on words, it is completely determined by its values $q(u)$ on words $u \in \{1,2\}^n$.

\begin{dfn}
A (ordinary) \defn{multiline queue} (MLQ) of type $\mm$, with $\ell$ classes, is a sequence of queues $q_1, \dotsc, q_{\ell-1}$ such that $q_i$ is a $p_i(\mm)$-queue.
For a permutation $\sigma$ of $\ive{\ell-1}$, a \defn{$\sigma$-twisted MLQ} of type $\mm$, with $\ell$ classes, is a sequence of queues $q_1, \dotsc, q_{\ell-1}$ such that $q_i$ is a $p_{\sigma(i)}(\mm)$-queue.
\end{dfn}

\begin{remark}
Our notion of an MLQ is equivalent to what is called a ``discrete MLQ''
in~\cite[Section~2.2]{AasLin17}, where we recover the labelling of level $k$ by $q_k( \cdots q_1(1 \dotsm 1) \cdots )$.
We omit the word ``discrete'' as these are the only MLQs in this note.
\end{remark}

\begin{dfn}
For a packed word $u$ of type $\mm$ with $\ell$ classes, we define the \defn{spectral weight} or \defn{amplitude} as
\begin{equation}
\label{eq:amplitude}
  \swt{u} := \sum_{(q_1, \dotsc, q_{\ell-1})} \prod_{i=1}^{\ell-1} \wt(q_i),
\end{equation}
where the sum is over all MLQs $(q_1, \dotsc, q_{\ell-1})$ of type $\mm$ and $u = q_{\ell-1}( \cdots q_1(1 \dotsm 1) \cdots )$.
\end{dfn}

%\subsection{Flagged Schur functions}
%
%Let $\lambda$ be a partition of length $m$ and $b = (b_1 \leq b_2 \leq \cdots \leq b_m)$.
%Let
%\[
%h_d(k) = \sum_{i_1 \leq \cdots \leq i_d \leq k} x_{i_1} \cdots x_{i_d}
%\]
%be the complete homogeneous symmetric function of degree $d$ in the variables $x_1, \dotsc, x_k$.
%A \defn{flagged Schur function} is
%\[
%\fs_{\lambda}(b; \xx) = \det\big[ h_{\lambda_i - i + j}(b_i) \bigr]_{i,j=1}^m.
%\]
%We can also express the flagged Schur function combinatorially using $\mcF_{\lambda}(b)$, the semistandard tableaux of shape $\lambda$ such that the max entry in row $i$ is at most $b_i$.
%From~\cite{Wachs85}, we have
%\[
%\fs_{\lambda}(b; \xx) = \sum_{T \in \mcF_{\lambda}(b)} x^T.
%\]

We will also need the \defn{elementary symmetric function} and \defn{complete homogeneous symmetric function} on the indeterminates $\xx$,
defined for each $N \in \left\{0,1,\ldots,n\right\}$ by
\[
e_k(N) = \sum_{1 \leq i_1 < \cdots < i_k \leq N} x_{i_1} \dotsm x_{i_k},
\qquad\qquad
h_k(N) = \sum_{1 \leq i_1 \leq \cdots \leq i_k \leq N} x_{i_1} \dotsm x_{i_k},
\]
respectively.
We define $e_k(N) = 0$ and $h_k(N) = 0$ for $k < 0$.








%=====================================================================
\section{Main results}
\label{sec:result}

In this section, we state our main results and prove the commutativity
conjecture of~\cite{AAMP} and~\cite[Conjecture~3.10]{AasLin17}.

\begin{thm}
\label{thm:permutation}
  Let $u$ be a packed word of type $\mm$ with $\ell$ classes.
  For any permutation $\sigma$ of $\ive{\ell-1}$, we have 
  \[
  \swt{u} = \sum_{(q_1, \dots, q_{\ell-1})} \prod_{i=1}^{\ell-1} \wt(q_i),
  \]
  where we sum over all $\sigma$-twisted MLQs such that $u = q_{\ell-1}(\cdots q_1(1\dotsm 1) \cdots )$.
\end{thm}

We note that Theorem~\ref{thm:permutation} for the special case of $x_1 = \cdots = x_n = 1$ is proven in~\cite{AAMP} using different techniques.

\begin{cor}
\label{co:merge}
  Let $\mm$ be a type with $m_i \neq 0$ and $m_{i+1} \neq 0$.
  Let $\mm' = (m_1, \dotsc, m_{i-1}, m_i + m_{i+1}, m_{i+2}, \ldots)$.
  For any packed word $v$ of type $\mm'$, we have
\[
  \swt{v} e_{p_i(\mm)}(n) = \sum_u \swt{u},
\]
where we sum over all $u$ of type $\mm$ such that $v = \merge{i} u$.
\end{cor}

\begin{proof}[Proof sketch]
  Note that if $u = q_{r-1}( \cdots q_2(q_1(1 \dotsm 1)) \cdots)$, where $q_1$ is a $p_i(\mm)$-queue, then $v = q_{r-1}( \cdots q_2(1 \dotsm 1) \cdots) = \merge{i} u$.
  The result follows from Theorem~\ref{thm:permutation}.
\end{proof}

\begin{example}
We give an example to illustrate the proof of Corollary~\ref{co:merge}.
To compute $\swt{135452}$, we need to examine MLQs of type $(1,1,1,1,2)$.
We take a particular MLQ and add the $5$-queue $\set{1,2,3,5,6}$ as follows:
\[
\qq =
\begin{tikzpicture}[baseline=82]
\node at (0, 4){2};\node at (1, 4){2};\node at (2, 4){2};\node[circle, draw=black] at (3, 4){1};\node at (4, 4){2};\node at (5, 4){2};\node at (0, 3){3};\node at (1, 3){3};\node[circle, draw=black] at (2, 3){2};\node at (3, 3){3};\node at (4, 3){3};\node[circle, draw=black] at (5, 3){1};\node[circle, draw=black] at (0, 2){1};\node[circle, draw=black] at (1, 2){3};\node at (2, 2){4};\node at (3, 2){4};\node[circle, draw=black] at (4, 2){2};\node at (5, 2){4};\node[circle, draw=black] at (0, 1){1};\node[circle, draw=black] at (1, 1){3};\node at (2, 1){5};\node[circle, draw=black] at (3, 1){4};\node at (4, 1){5};\node[circle, draw=black] at (5, 1){2};
\end{tikzpicture}
\xrightarrow{\hspace{30pt}}
\begin{tikzpicture}[baseline=82]
\node[circle, draw=black] at (0, 5){1};\node[circle, draw=black] at (1, 5){1};\node[circle, draw=black] at (2, 5){1};\node at (3, 5){2};\node[circle, draw=black] at (4, 5){1};\node[circle, draw=black] at (5, 5){1};\node at (0, 4){2};\node at (1, 4){2};\node at (2, 4){3};\node[circle, draw=black] at (3, 4){1};\node at (4, 4){2};\node at (5, 4){2};\node at (0, 3){3};\node at (1, 3){4};\node[circle, draw=black] at (2, 3){2};\node at (3, 3){3};\node at (4, 3){3};\node[circle, draw=black] at (5, 3){1};\node[circle, draw=black] at (0, 2){1};\node[circle, draw=black] at (1, 2){3};\node at (2, 2){4};\node at (3, 2){4};\node[circle, draw=black] at (4, 2){2};\node at (5, 2){5};\node[circle, draw=black] at (0, 1){1};\node[circle, draw=black] at (1, 1){3};\node at (2, 1){5};\node[circle, draw=black] at (3, 1){4};\node at (4, 1){6};\node[circle, draw=black] at (5, 1){2};
\end{tikzpicture}
= \widetilde{\qq}.
\]
Note that we can take any subset of $\ive{6}$ of size $5$, and so the sum over all of these choices contributes a weight change to $\qq$ by $e_5(6)$.
Furthermore, note that $135452 = \merge{5} 135462$.
Now, by Theorem~\ref{thm:permutation}, such queues are in bijection with ordinary queues counting, in this case, $\swt{135462}$.
In more detail, let $R_i(\widetilde{\qq})$ be the MLQ formed by taking the configuration $C = (\widetilde{q}_i, \widetilde{q}_{i+1})$ and replacing it with the dual configuration.
By taking $R_4 R_3 R_2 R_1(\widetilde{\qq})$ to bring the top row to the bottom, we obtain the ordinary MLQ as follows:
\[
\widetilde{\qq} \xrightarrow[\hspace{15pt}]{R_1}
\begin{tikzpicture}[xscale=0.5,yscale=0.7,every node/.style={inner sep=0.8pt},baseline=55]
\node at (0, 5){2};\node at (1, 5){2};\node[circle, draw=black] at (2, 5){1};\node at (3, 5){2};\node at (4, 5){2};\node at (5, 5){2};\node[circle, draw=black] at (0, 4){2};\node[circle, draw=black] at (1, 4){2};\node at (2, 4){3};\node[circle, draw=black] at (3, 4){1};\node[circle, draw=black] at (4, 4){2};\node[circle, draw=black] at (5, 4){2};\node at (0, 3){3};\node at (1, 3){4};\node[circle, draw=black] at (2, 3){2};\node at (3, 3){3};\node at (4, 3){3};\node[circle, draw=black] at (5, 3){1};\node[circle, draw=black] at (0, 2){1};\node[circle, draw=black] at (1, 2){3};\node at (2, 2){4};\node at (3, 2){4};\node[circle, draw=black] at (4, 2){2};\node at (5, 2){5};\node[circle, draw=black] at (0, 1){1};\node[circle, draw=black] at (1, 1){3};\node at (2, 1){5};\node[circle, draw=black] at (3, 1){4};\node at (4, 1){6};\node[circle, draw=black] at (5, 1){2};
\end{tikzpicture}
\xrightarrow[\hspace{15pt}]{R_2}
\begin{tikzpicture}[xscale=0.5,yscale=0.7,every node/.style={inner sep=0.8pt},baseline=55]
\node at (0, 5){2};\node at (1, 5){2};\node[circle, draw=black] at (2, 5){1};\node at (3, 5){2};\node at (4, 5){2};\node at (5, 5){2};\node at (0, 4){3};\node[circle, draw=black] at (1, 4){2};\node at (2, 4){3};\node at (3, 4){3};\node at (4, 4){3};\node[circle, draw=black] at (5, 4){1};\node[circle, draw=black] at (0, 3){3};\node at (1, 3){4};\node[circle, draw=black] at (2, 3){2};\node[circle, draw=black] at (3, 3){3};\node[circle, draw=black] at (4, 3){3};\node[circle, draw=black] at (5, 3){1};\node[circle, draw=black] at (0, 2){1};\node[circle, draw=black] at (1, 2){3};\node at (2, 2){4};\node at (3, 2){4};\node[circle, draw=black] at (4, 2){2};\node at (5, 2){5};\node[circle, draw=black] at (0, 1){1};\node[circle, draw=black] at (1, 1){3};\node at (2, 1){5};\node[circle, draw=black] at (3, 1){4};\node at (4, 1){6};\node[circle, draw=black] at (5, 1){2};
\end{tikzpicture}
\xrightarrow[\hspace{15pt}]{R_3}
\begin{tikzpicture}[xscale=0.5,yscale=0.7,every node/.style={inner sep=0.8pt},baseline=55]
\node at (0, 5){2};\node at (1, 5){2};\node[circle, draw=black] at (2, 5){1};\node at (3, 5){2};\node at (4, 5){2};\node at (5, 5){2};\node at (0, 4){3};\node[circle, draw=black] at (1, 4){2};\node at (2, 4){3};\node at (3, 4){3};\node at (4, 4){3};\node[circle, draw=black] at (5, 4){1};\node[circle, draw=black] at (0, 3){3};\node at (1, 3){4};\node at (2, 3){4};\node at (3, 3){4};\node[circle, draw=black] at (4, 3){2};\node[circle, draw=black] at (5, 3){1};\node[circle, draw=black] at (0, 2){1};\node[circle, draw=black] at (1, 2){3};\node[circle, draw=black] at (2, 2){4};\node[circle, draw=black] at (3, 2){4};\node[circle, draw=black] at (4, 2){2};\node at (5, 2){5};\node[circle, draw=black] at (0, 1){1};\node[circle, draw=black] at (1, 1){3};\node at (2, 1){5};\node[circle, draw=black] at (3, 1){4};\node at (4, 1){6};\node[circle, draw=black] at (5, 1){2};\end{tikzpicture}
\xrightarrow[\hspace{15pt}]{R_4}
\begin{tikzpicture}[xscale=0.5,yscale=0.7,every node/.style={inner sep=0.8pt},baseline=55]
\node at (0, 5){2};\node at (1, 5){2};\node[circle, draw=black] at (2, 5){1};\node at (3, 5){2};\node at (4, 5){2};\node at (5, 5){2};\node at (0, 4){3};\node[circle, draw=black] at (1, 4){2};\node at (2, 4){3};\node at (3, 4){3};\node at (4, 4){3};\node[circle, draw=black] at (5, 4){1};\node[circle, draw=black] at (0, 3){3};\node at (1, 3){4};\node at (2, 3){4};\node at (3, 3){4};\node[circle, draw=black] at (4, 3){2};\node[circle, draw=black] at (5, 3){1};\node[circle, draw=black] at (0, 2){1};\node[circle, draw=black] at (1, 2){3};\node at (2, 2){5};\node[circle, draw=black] at (3, 2){4};\node[circle, draw=black] at (4, 2){2};\node at (5, 2){5};\node[circle, draw=black] at (0, 1){1};\node[circle, draw=black] at (1, 1){3};\node[circle, draw=black] at (2, 1){5};\node[circle, draw=black] at (3, 1){4};\node at (4, 1){6};\node[circle, draw=black] at (5, 1){2};
\end{tikzpicture}
\]
which contributes to $\swt{135462}$.
\end{example}


\begin{example}
Suppose $n = 5$.
Let $v = 13234$, and we have that $v = \merge{3} u$ if and only if $u \in \set{13245, 14235}$.
By examining all possible MLQs for these words, we obtain
\begin{align*}
\swt{13234} & = x_1 x_2 x_3^2 x_4 (x_1^2 + x_1 x_4 + x_1 x_5 + x_4 x_5 + x_5^2),
\\ \swt{13245} & = x_1 x_2 x_3^2 x_4 (x_1^2 + x_1x_4 + x_1x_5 + x_4^2 + x_4x_5 + x_5^2)
\\ & \hspace{20pt} \times (x_1x_2x_3 + x_1x_2x_5+x_1x_3x_5+x_2x_3x_5),
\\ \swt{14235} & = x_1x_2x_3^2x_4^2 (x_1^3x_2 + x_1^3x_3 + x_1^3x_5 + x_1^2x_2x_3 + x_1^2x_2x_4 + 2x_1^2x_2x_5 + x_1^2x_3x_4
\\ & \hspace{65pt} + 2x_1^2x_3x_5 + x_1^2x_4x_5 + x_1^2x_5^2 + x_1x_2x_3x_5 + x_1x_2x_4x_5 + 2x_1x_2x_5^2
\\ & \hspace{65pt} + x_1x_3x_4x_5 + 2x_1x_3x_5^2 + x_1x_4x_5^2 + x_1x_5^3 + x_2x_3x_5^2 + x_2x_4x_5^2
\\ & \hspace{65pt} + x_2x_5^3 + x_3x_4x_5^2 + x_3x_5^3).
\end{align*}
(We have factored the expressions for readability only.)
We verify Corollary~\ref{co:merge} in this case by computing $\swt{13234} e_3(5) = \swt{13245} + \swt{14235}$.
\end{example}


\begin{thm}
\label{thm:determinant_form}
  Let $B = \set{b_1 < b_2 < \cdots < b_r} \subseteq \ive{n}$.
  Let $v_1v_2 \dotsm v_r$ be a weakly decreasing (non-cyclic) packed word of length $r$ with $\ell-1$ classes.
  Define a word $u$ of length $n$ by $u_i = v_j$ if $i = b_j$ for some $j$, otherwise $u_i = \ell$.
  Then
  \[
  \swt{u} = \left( \prod_{i\in B} x_i \right) \det\bigl( h_{i-j-1+\gamma_j}(b_j) \bigr)_{1\leq i,j\leq r},
  \]
  where $\gamma_j$ is the number of distinct letters in $v_1 \dotsm v_j$.
\end{thm}

\begin{figure}[t]
\[
\begin{tikzpicture}[xscale=1.5,yscale=0.9]
  \begin{scope}[yshift=7cm]
    \foreach \i in {1,...,9}{
      \foreach \j in {0,1,2}{
        \node at (\i,\j){$\cdot$};
      }
    }
    \node[circle,fill=white,draw=black] at  (1, 0){$3$};
    \node[circle,fill=white,draw=black,text=blue] at  (2, 0){$3$};
    \node[circle,fill=white,draw=black] at  (4, 0){$2$};
    \node[circle,fill=white,draw=black,text=blue] at  (6, 0){$2$};
    \node[circle,fill=white,draw=black,text=darkred] at  (7, 0){$2$};
    \node[circle,fill=white,draw=black] at  (9, 0){$1$};
    \node[circle,fill=white,draw=black] at  (3, 1){$2$};
    \node[circle,fill=white,draw=black,text=blue] at  (4, 1){$2$};
    \node[circle,fill=white,draw=black,text=darkred] at  (6, 1){$2$};
    \node[circle,fill=white,draw=black] at  (8, 1){$1$};
    \node[circle,fill=white,draw=black] at  (7, 2){$1$};
  \end{scope}

  \draw[densely dotted] (1,1) grid (9,6);

  \draw[draw=red] (1,2)--(2,2);
  \draw[draw=red] (1,3)--(3,3)--(3,2)--(4,2);
  \draw[draw=red] (1,4)--(4,4)--(4,3)--(6,3);
  \draw[draw=red] (1,5)--(6,5)--(6,4)--(7,4);
  \draw[draw=red] (1,6)--(7,6)--(7,5)--(8,5)--(8,4)--(9,4);
  
  \node[circle,fill=white,draw=black,inner sep=1pt] at (1,1) {$3$};
  \node[circle,fill=white,draw=black,text=blue,inner sep=1pt] at (2,2) {$3$};
  \node[circle,fill=white,draw=black,inner sep=1pt] at (4,2) {$2$};
  \node[circle,fill=white,draw=black,inner sep=1pt] at (3,3) {$2$};
  \node[circle,fill=white,draw=black,text=blue,inner sep=1pt] at (4,4) {$2$};
  \node[circle,fill=white,draw=black,text=blue,inner sep=1pt] at (6,3) {$2$};
  \node[circle,fill=white,draw=black,text=darkred,inner sep=1pt] at (6,5) {$2$};
  \node[circle,fill=white,draw=black,text=darkred,inner sep=1pt] at (7,4) {$2$};
  \node[circle,fill=white,draw=black,inner sep=1pt] at (7,6) {$1$};
  \node[circle,fill=white,draw=black,inner sep=1pt] at (8,5) {$1$};
  \node[circle,fill=white,draw=black,inner sep=1pt] at (9,4) {$1$};

  \foreach \i in {2,...,6} {
    \node at (1,\i){\textbullet};
  }
\end{tikzpicture}
\]
\caption{An example of the bijection with $n = 9$, $r = 6$, $\ell = 4$, $v = 332221$, and $B = \set{1,2,4,6,7,9}$ between MLQs and non-intersecting lattice paths coming from the Lindstr\"om--Gessel--Viennot Lemma~\cite{GV85,Lindstrom73} applied to Theorem~\ref{thm:determinant_form}.}
\label{fig:lattice_path_bijection}
\end{figure}

Now, fix a sequence $b_1 < b_2 < \cdots < b_r$, and for a permutation $v$ of $\ive{r}$, let $u(v)$ be the corresponding word as defined in Theorem~\ref{thm:determinant_form}.
Furthermore let $S \subseteq \ive{r-1}$ be such that $i\in S$ implies $i+1 \notin S$, and define the permutation $\sigma_S = \left( \prod_{i \in S} s_i \right) w_0$,\footnote{The elements $\{s_i \mid i \in S\}$ all commute, so the product is well-defined.} where $s_i$ is the simple transposition on $i$ and $i+1$ and $w_0(k) = r+1-k$ is the reverse permutation on $\ive{r}$.
In~\cite{AasLin17}, a formula for the spectral weight $\swt{u \sigma_S}$ is conjectured, where $u \sigma_S = u_{\sigma_S(1)} \cdots u_{\sigma_S(r)}$.

Let $T \subseteq \ive{r-1}$, and let $\phi(T) = \sum_{S \subseteq T} \swt{u \sigma_S}$.
By Theorem~\ref{thm:permutation}, we have
\[
  \psi(T) = \left(\prod_{i\in S} e_{p_i(\mm)}(n) \right) \swt{ \bigvee_T w_0} = \left( \prod_{i\in B} x_i \right) \left(\prod_{i\in S} e_{p_i(\mm)}(n) \right) \det(h_{i-j+1+\gamma_j}(b_j))_{1\leq i,j \leq r},
\]
where $\gamma_i = i - \lvert \{j\in T \mid j < i \} \rvert$ and the second equality is Theorem~\ref{thm:determinant_form}.
By M\"obius inversion we have $\swt{u \sigma_S} = \sum_{T\subseteq S} (-1)^{|S|-|T|} \psi(T)$.
Taken together with $x_1 = \cdots = x_n = 1$, this
proves~\cite[Conjecture~3.10]{AasLin17}.







%=====================================================================
\section{Proof sketch of Theorem~\ref{thm:permutation}}
\label{sec:proof_sketch}

The proof reduces down to defining an action of a simple transposition on a pair of queues since all permutations can be written as a product of simple transpositions.
We call a pair of queues $C = (q_1, q_2)$ an \defn{$(r,s)$-configuration}, where $q_1$ is an $r$-queue and $q_2$ is an $s$-queue.
We consider $C$ as a function on words by $C(u) := q_2\bigr(q_1(u)\bigr)$, and we define the weight of $C$ by $\wt(C) := \wt(q_1) \wt(q_2)$.
Our proof is thus reduced to constructing the \defn{dual} $(s,r)$-configuration $C'$ to $C$, which satisfies $C(u) = C'(u)$, $\wt(C) = \wt(C')$, and $C'' = C$.
Furthermore, we need to show that taking the dual configuration satisfies the braid relations.

To construct $C'$ and show it satisfies the requisite properties, we break it into four parts as follows.
By using the monotonicity, we may assume $u \in \{1,2\}^n$.
For the remainder of this section, we fix an $(r,s)$-configuration $C = (q_1, q_2)$.

%%%%%%%%%%
\subsection*{Part A: Splitting into balanced and unbalanced intervals}

Let $\inter[i,j]$ denote a closed (cyclic) interval from $i$ to $j$.
This is the set $\set{i, i+1, \ldots, j}$, which wraps around the ``circle'' if $i > j$.
Let $\inter(i,j) := \inter[i,j] \setminus \set{i,j}$ denote the open (cyclic) interval.
Let $c^{\uparrow}(i,k)$ (resp.~$c^{\downarrow}(i,k)$) denote the number of $\ell \in \inter[i,k]$ such that $\ell \in q_1$ (resp.~$\ell \in q_2$).
We say that a closed cyclic interval $\inter[i,j]$ is \defn{balanced} if $c^{\uparrow}(i,j) = c^{\downarrow}(i,j)$ and for each $k \in \inter[i,j]$, we have $c^\uparrow(i,k) \geq c^\downarrow(i,k)$.
Note that for a balanced interval $\mcI$, we have $\lvert q_1 \cap \mcI \rvert = \lvert q_2 \cap \mcI \rvert$.
For $i \in \ive{n}$, we say that $i$ is \defn{balanced} if $i$ belongs to some balanced interval, and \defn{unbalanced} otherwise.
The maximal (with respect to set inclusion) balanced intervals are disjoint, and a maximal interval is $[n]$ if and only if $r = s$.

For $r < s$ and $j$ unbalanced, we have $j \notin q_1$ and $j \in q_2$.
Conversely, for $r > s$ and $j$ unbalanced, $j \in q_1$ and $j \notin q_2$.
The following notation will be useful later on: for a word $u \in \mcW_n$, an element $j \in \ive{n}$ and an $(r,s)$-configuration $C = (q_1, q_2)$, we let $T(j)$ be the pair $(u_j, s_j)$ where $s_j = \bigcirc$ if $j \in q_1$ and $s_j = \square$ if $j\notin q_1$.

\begin{figure}[t]
\[
\begin{tikzpicture}[scale=0.9]
  \def\sc{0.85}   % Change this to adjust the x-scaling
  \def\ll{2}   % level 2
  \def\l{1}   % level 1
  \draw[fill=blue!30] (1.5*\sc,\l-.5) rectangle(4.5*\sc,\ll+.5);
  \draw[fill=blue!30] (6.5*\sc,\l-.5) rectangle(7.5*\sc,\ll+.5);
  \draw[fill=blue!30] (8.5*\sc,\l-.5) rectangle(20.5*\sc,\ll+.5);
  \foreach \i in {1,2,5,6,8,11,13,14,17,18,19} { \draw[fill=white] (\i*\sc,\ll) circle (0.3); }
  \foreach \i in {3,4,7,9,10,12,15,16,20} { \draw[fill=white] (\i*\sc-.3,\ll-.3) rectangle +(0.6,+0.6); }
  \foreach \i in {2,12,15,16,18,19,20} { \draw[fill=white] (\i*\sc,\l) circle (0.3); }
  \foreach \i in {1,3,4,5,6,7,8,9,10,11,13,14,17} { \draw[fill=white] (\i*\sc-.3,\l-.3) rectangle +(0.6,+0.6); }
\end{tikzpicture}
\]
\caption{We draw a $\bigcirc$ in position $i$ in row $j$ corresponding to $i \in q_j$ and a $\square$ if $i \notin q_j$.
The maximal balanced intervals are boxed.}
\label{fig:balanced}
\end{figure}

%%%%%%%%%%
\subsection*{Part B: Defining the dual configuration}

We construct $C' = (q'_1, q'_2)$ by letting $q'_i \cap \mcI = q_i \cap \mcI$ for $i=1,2$ and each balanced interval $\mcI$ in $C$.
For unbalanced $j$, we have $j \in q'_i$ if and only if $j \in q_{3-i}$ for $i = 1,2$.
Note that $C$ and $C'$ have the same balanced intervals.
It is clear that $C'' = C$ and $\wt(C) = \wt(C')$.
This corresponds to the action of the combinatorial $R$-matrix~\cite{NY97,Shimozono02}, which satisfies the Yang--Baxter equation/the braid relation.
Note that if $r = s$, then $C = C'$.

\begin{example}
Consider the configuration $C$ given in Figure~\ref{fig:balanced}.
The dual configuration $C'$ is given by sliding all of the circles not in a boxed interval from the upper level to the lower level.
In particular, we have $q_1' = q_1 \setminus \{1,5,6,8\}$ and $q_2' = q_2 \cup \{1,5,6,8\}$.
\end{example}

%%%%%%%%%%
\subsection*{Part C: Reduction to special words}

We reduce the problem to a certain set of words by performing a series of reductions based on the following lemmas.
For this part, we assume $i,j \in \ive{n}$.
We define $u_{i\leftrightarrow j}$ as the result of swapping positions $i$ and $j$ in $u$.

%\begin{lemma}
%\label{le:orig}
%  Suppose that $i \notin q$, $j\in q$, and for $k \in \inter(i,j)$, either $k \in q$ and $u_k=1$ or $k \notin q$ and $u_k = 2$.
%  Then $q(u) = q(u_{i\leftrightarrow j})$.
%\end{lemma}

\begin{lemma}[BB reduction]
\label{le:BB}
  Suppose $\inter[i,j]$ is a balanced interval, $T(i) = (1,\square)$, $T(j) = (2,\bigcirc)$, and $T(k) \in \{(1,\bigcirc),(2,\square)\}$ for all $k \in \inter(i,j)$.
  Then $C(u) = C(u_{i \leftrightarrow j})$.
\end{lemma}

In the following examples, on the first line, we write the word $u$, the second line is the word is $q_1(u)$ with $i \in q_1$ (resp.~$i \notin q_1)$ depicted as $\bigcirc$ (resp.~$\square$), and the third line is $q_2\big(q_1(u)\bigr)$ with similar depiction for $q_2$.

\begin{example}
Suppose $n = 8$.
Let $u = 12121122$, and consider the $(5,3)$-configuration $C = (\{1,2,5,6,8\}, \{5,7,8\})$.
We apply $C$ to $u$ on the left and to $u_{3 \leftrightarrow 8}$ on the right:
\[
\begin{tikzpicture}[baseline=-3]
  \def\sc{0.75}   % Change this to adjust the x-scaling
  \def\lll{1.7}   % level 3
  \def\ll{1}   % level 2
  \def\l{0}   % level 1
  \node[color=blue] at (3*\sc,\lll) {$1$};
  \node[color=blue] at (8*\sc,\lll) {$2$};
  \foreach \i in {1,5,6} { \node at (\i*\sc,\lll) {$1$}; }
  \foreach \i in {2,4,7} { \node at (\i*\sc,\lll) {$2$}; }
  \foreach \i in {1,2,5,6,8} { \draw (\i*\sc,\ll) circle (0.3); }
  \foreach \i in {3,4,7} { \draw (\i*\sc-.3,\ll-.3) rectangle +(0.6,+0.6); }
  \foreach \i in {1,5,6,8} { \node at (\i*\sc,\ll) {$1$}; }
  \foreach \i in {2} { \node at (\i*\sc,\ll) {$2$}; }
  \foreach \i in {3,4,7} { \node at (\i*\sc,\ll) {$3$}; }
  \foreach \i in {5,7,8} { \draw (\i*\sc,\l) circle (0.3); }
  \foreach \i in {1,2,3,4,6} { \draw (\i*\sc-.3,\l-.3) rectangle +(0.6,+0.6); }
  \foreach \i in {3,4,6} { \node at (\i*\sc,\l) {$4$}; }
  \foreach \i in {2} { \node at (\i*\sc,\l) {$3$}; }
  \foreach \i in {1} { \node at (\i*\sc,\l) {$2$}; }
  \foreach \i in {5,7,8} { \node at (\i*\sc,\l) {$1$}; }
  \draw (2.5*\sc,2) -- (2.5*\sc,2.1) -- (8.5*\sc,2.1) -- (8.5*\sc,2);
  \node at (5.5*\sc,2.5) {balanced};
\end{tikzpicture}
% t = 2 for q_1
% t = 1 for q_2
\hspace{20pt} = \hspace{20pt}
\begin{tikzpicture}[baseline=-3]
  \def\sc{0.75}   % Change this to adjust the x-scaling
  \def\lll{1.7}   % level 3
  \def\ll{1}   % level 2
  \def\l{0}   % level 1
  \node[color=blue] at (8*\sc,\lll) {$1$};
  \node[color=blue] at (3*\sc,\lll) {$2$};
  \foreach \i in {1,5,6} { \node at (\i*\sc,\lll) {$1$}; }
  \foreach \i in {2,4,7} { \node at (\i*\sc,\lll) {$2$}; }
  \foreach \i in {1,2,5,6,8} { \draw (\i*\sc,\ll) circle (0.3); }
  \foreach \i in {3,4,7} { \draw (\i*\sc-.3,\ll-.3) rectangle +(0.6,+0.6); }
  \foreach \i in {1,5,6,8} { \node at (\i*\sc,\ll) {$1$}; }
  \foreach \i in {3,4,7} { \node at (\i*\sc,\ll) {$3$}; }
  \foreach \i in {2} { \node at (\i*\sc,\ll) {$2$}; }
  \foreach \i in {5,7,8} { \draw (\i*\sc,\l) circle (0.3); }
  \foreach \i in {1,2,3,4,6} { \draw (\i*\sc-.3,\l-.3) rectangle +(0.6,+0.6); }
  \foreach \i in {3,4,6} { \node at (\i*\sc,\l) {$4$}; }
  \foreach \i in {2} { \node at (\i*\sc,\l) {$3$}; }
  \foreach \i in {1} { \node at (\i*\sc,\l) {$2$}; }
  \foreach \i in {5,7,8} { \node at (\i*\sc,\l) {$1$}; }
  \draw (2.5*\sc,2) -- (2.5*\sc,2.1) -- (8.5*\sc,2.1) -- (8.5*\sc,2);
  \node at (5.5*\sc,2.5) {balanced};
\end{tikzpicture}
\]
\end{example}

\begin{lemma}[BU reduction]
\label{le:BU}
  Suppose $i$ is balanced, $j$ is unbalanced, $T(i) = (1,\square)$, $u_j = 2$, $u_k = 1$ for all unbalanced $k \in \inter (i,j)$, and $T(k) \in \{(1,\bigcirc),(2,\square)\}$ for all balanced $k \in \inter(i,j)$.
  Then $C(u) = C(u_{i \leftrightarrow j})$.
 \end{lemma}
 
\begin{example}
Suppose $n = 8$.
Let $u = 21111122$, and consider the $(4,1)$-configuration $C = (\{1,2,5,6\},\{7\})$.
We apply $C$ to $u$ on the left and to $u_{4\leftrightarrow1}$ (note the interval $\inter[4,1]$ wraps around):
\[
\begin{tikzpicture}[baseline=25]
  \def\sc{0.75}   % Change this to adjust the x-scaling
  \def\lll{2.7}   % level 3
  \def\ll{2}   % level 2
  \def\l{1}   % level 1
  \node[color=blue] at (1*\sc,\lll) {$2$};
  \node[color=blue] at (4*\sc,\lll) {$1$};
  \foreach \i in {2,3,5,6} { \node at (\i*\sc,\lll){$1$}; }
  \foreach \i in {7,8} { \node at (\i*\sc,\lll){$2$}; }
  \foreach \i in {1,2,5,6} { \draw (\i*\sc,\ll) circle (0.3); }
  \foreach \i in {3,4,7,8} { \draw (\i*\sc-.3,\ll-.3) rectangle +(0.6,+0.6); }
  \foreach \i in {1,2,5,6} { \node at (\i*\sc,\ll) {$1$}; }
  \foreach \i in {3} { \node at (\i*\sc,\ll) {$2$}; }
  \foreach \i in {4,7,8} { \node at (\i*\sc,\ll) {$3$}; }
  \foreach \i in {8} { \draw (\i*\sc,\l) circle (0.3); }
  \foreach \i in {1,2,3,4,5,6,7} { \draw (\i*\sc-.3,\l-.3) rectangle +(0.6,+0.6); }
  \foreach \i in {4,6,7} { \node at (\i*\sc,\l) {$4$}; }
  \foreach \i in {8} { \node at (\i*\sc,\l) {$1$}; }
  \foreach \i in {3} { \node at (\i*\sc,\l) {$3$}; }
  \foreach \i in {1,2,5} { \node at (\i*\sc,\l) {$2$}; }
  \draw (2.5*\sc,3) -- (2.5*\sc,3.1) -- (4.5*\sc,3.1) -- (4.5*\sc,3);
  \node at (3.5*\sc,3.5) {balanced};
  \draw (5.5*\sc,3) -- (5.5*\sc,3.1) -- (8.5*\sc,3.1) -- (8.5*\sc,3);
  \node at (7.0*\sc,3.5) {balanced};
\end{tikzpicture}
% t = 1 for q_1
% t = 1 for q_2
\hspace{20pt} = \hspace{20pt}
\begin{tikzpicture}[baseline=25]
  \def\sc{0.75}   % Change this to adjust the x-scaling
  \def\lll{2.7}   % level 3
  \def\ll{2}   % level 2
  \def\l{1}   % level 1
  \node[color=blue] at (4*\sc,\lll) {$2$};
  \node[color=blue] at (1*\sc,\lll) {$1$};
  \foreach \i in {2,3,5,6} { \node at (\i*\sc,\lll){$1$}; }
  \foreach \i in {7,8} { \node at (\i*\sc,\lll){$2$}; }
  \foreach \i in {1,2,5,6} { \draw (\i*\sc,\ll) circle (0.3); }
  \foreach \i in {3,4,7,8} { \draw (\i*\sc-.3,\ll-.3) rectangle +(0.6,+0.6); }
  \foreach \i in {1,2,5,6} { \node at (\i*\sc,\ll) {$1$}; }
  \foreach \i in {3} { \node at (\i*\sc,\ll) {$2$}; }
  \foreach \i in {4,7,8} { \node at (\i*\sc,\ll) {$3$}; }
  \foreach \i in {8} { \draw (\i*\sc,\l) circle (0.3); }
  \foreach \i in {1,2,3,4,5,6,7} { \draw (\i*\sc-.3,\l-.3) rectangle +(0.6,+0.6); }
  \foreach \i in {4,6,7} { \node at (\i*\sc,\l) {$4$}; }
  \foreach \i in {8} { \node at (\i*\sc,\l) {$1$}; }
  \foreach \i in {3} { \node at (\i*\sc,\l) {$3$}; }
  \foreach \i in {1,2,5} { \node at (\i*\sc,\l) {$2$}; }
  \draw (2.5*\sc,3) -- (2.5*\sc,3.1) -- (4.5*\sc,3.1) -- (4.5*\sc,3);
  \node at (3.5*\sc,3.5) {balanced};
  \draw (5.5*\sc,3) -- (5.5*\sc,3.1) -- (8.5*\sc,3.1) -- (8.5*\sc,3);
  \node at (7.0*\sc,3.5) {balanced};
\end{tikzpicture}
\]
\end{example}

\begin{remark}
The BB and, when $r > s$, BU reductions always have $q_1(u) = q_1(u_{i \leftrightarrow j})$. 
\end{remark}

\begin{lemma}[UB reduction]
\label{le:UB}
  Suppose $i$ is unbalanced, $j$ is balanced, $u_i = 1$, $T(j) = (2,\bigcirc)$, $u_k = 2$ for all unbalanced $k \in \inter(i,j)$, and $T(k) \in \{(1,\bigcirc),(2,\square)\}$ for all balanced $k$ in $\inter(i,j)$.
  Then $C(u) = C(u_{i \leftrightarrow j})$.
\end{lemma}

\begin{example}
Suppose $n = 8$.
Let $u = 12221222$, and consider the $(6,2)$-configuration $C = (\{1,2,3,4,5,8\}, \{7,8\})$.
We apply $C$ to $u$ on the left and to $u_{1 \leftrightarrow 8}$ on the right:
\[
\begin{tikzpicture}[baseline=25]
  \def\sc{0.75}   % Change this to adjust the x-scaling
  \def\lll{2.7}   % level 3
  \def\ll{2}   % level 2
  \def\l{1}   % level 1
  \node[color=blue] at (1*\sc,\lll) {$1$};
  \node[color=blue] at (8*\sc,\lll) {$2$};
  \foreach \i in {5} { \node at (\i*\sc,\lll){$1$}; }
  \foreach \i in {2,3,4,6,7} { \node at (\i*\sc,\lll){$2$}; }
  \foreach \i in {1,2,3,4,5,8} { \draw (\i*\sc,\ll) circle (0.3); }
  \foreach \i in {6,7} { \draw (\i*\sc-.3,\ll-.3) rectangle +(0.6,+0.6); }
  \node[color=blue] at (1*\sc,\ll) {$1$};
  \node[color=blue] at (8*\sc,\ll) {$2$};
  \foreach \i in {5} { \node at (\i*\sc,\ll) {$1$}; }
  \foreach \i in {2,3,4} { \node at (\i*\sc,\ll) {$2$}; }
  \foreach \i in {6,7} { \node at (\i*\sc,\ll) {$3$}; }
  \foreach \i in {7,8} { \draw (\i*\sc,\l) circle (0.3); }
  \foreach \i in {1,2,3,4,5,6} { \draw (\i*\sc-.3,\l-.3) rectangle +(0.6,+0.6); }
  \foreach \i in {5,6} { \node at (\i*\sc,\l) {$4$}; }
  \foreach \i in {7,8} { \node at (\i*\sc,\l) {$1$}; }
  \foreach \i in {1,2,3,4} { \node at (\i*\sc,\l) {$3$}; }
  \draw (4.5*\sc,3) -- (4.5*\sc,3.1) -- (8.5*\sc,3.1) -- (8.5*\sc,3);
  \node at (6.5*\sc,3.5) {balanced};
\end{tikzpicture}
% t = 2 for q_1 = {1,2,3,4,5,8}
% t = 2 for q_2 = {7,8}
\hspace{20pt} = \hspace{20pt}
\begin{tikzpicture}[baseline=25]
  \def\sc{0.75}   % Change this to adjust the x-scaling
  \def\lll{2.7}   % level 3
  \def\ll{2}   % level 2
  \def\l{1}   % level 1
  \node[color=blue] at (8*\sc,\lll) {$1$};
  \node[color=blue] at (1*\sc,\lll) {$2$};
  \foreach \i in {5} { \node at (\i*\sc,\lll){$1$}; }
  \foreach \i in {2,3,4,6,7} { \node at (\i*\sc,\lll){$2$}; }
  \foreach \i in {1,2,3,4,5,8} { \draw (\i*\sc,\ll) circle (0.3); }
  \foreach \i in {6,7} { \draw (\i*\sc-.3,\ll-.3) rectangle +(0.6,+0.6); }
  \node[color=blue] at (8*\sc,\ll) {$1$};
  \node[color=blue] at (1*\sc,\ll) {$2$};
  \foreach \i in {5} { \node at (\i*\sc,\ll) {$1$}; }
  \foreach \i in {2,3,4} { \node at (\i*\sc,\ll) {$2$}; }
  \foreach \i in {6,7} { \node at (\i*\sc,\ll) {$3$}; }
  \foreach \i in {7,8} { \draw (\i*\sc,\l) circle (0.3); }
  \foreach \i in {1,2,3,4,5,6} { \draw (\i*\sc-.3,\l-.3) rectangle +(0.6,+0.6); }
  \foreach \i in {5,6} { \node at (\i*\sc,\l) {$4$}; }
  \foreach \i in {7,8} { \node at (\i*\sc,\l) {$1$}; }
  \foreach \i in {1,2,3,4} { \node at (\i*\sc,\l) {$3$}; }
  \draw (4.5*\sc,3) -- (4.5*\sc,3.1) -- (8.5*\sc,3.1) -- (8.5*\sc,3);
  \node at (6.5*\sc,3.5) {balanced};
\end{tikzpicture}
\]
\end{example}

%%%%%%%%%%
\subsection*{Part D: Finishing the proof}

Note that if one of the previous lemmas applies to $C$ for some $u,i,j$, then it applies to $C'$ with the same $u, i, j$.
Thus, we prove that $C(u) = C'(u)$, where $u$ is one of the words such that none of the reduction steps from Part~C apply.








%=====================================================================
% This is now a larger example above
%\begin{figure}
%\[
%\begin{tikzpicture}
%\draw (-0.5,6)--(-0.5,3);
%\draw (5.5,6)--(5.5,3);
%  \node at(-2,6){2};
%  \node at(-1,6){2};
%  \node at (0,6){1};
%  \node at (1,6){1};
%  \node at (2,6){2};
%  \node at (3,6){2};
%  \node at (4,6){2};
%  \node at (5,6){2};
%  \node at (6,6){1};
%  \node at (7,6){2};
%  \node[circle,draw=black] at (0, 5){\0};
%  \node[rectangle,draw=black] at (1, 5){\0};
%  \node[circle,draw=black] at (2, 5){\0};
%  \node[rectangle, draw=black] at (3, 5){\0};
%  \node[circle,draw=black] at (4, 5){\0};
%  \node[rectangle,draw=black] at (5, 5){\0};
%  \node[rectangle,draw=black] at (0, 4){\0};
%  \node[circle, draw=black] at (1, 4){\0};
%  \node[rectangle,draw=black] at (2, 4){\0};
%  \node[rectangle,draw=black] at (3, 4){\0};
%  \node[circle,draw=black] at (4, 4){\0};
%  \node[circle, draw=black] at (5, 4){\0};
%  \node[circle,draw=black] at (-1, 5){\0};
%  \node[circle,draw=black] at (-2, 5){\0};
%  \node at (-3,5){\dots};
%  \node[circle,draw=black] at (6, 5){\0};
%  \node[circle,draw=black] at (7, 5){\0};
%  \node at (8,5){\dots};
%\end{tikzpicture}
%\]
%\[
%\begin{tikzpicture}
%  \node at(-2,6){2};
%  \node at(-1,6){2};
%  \node at (0,6){1};
%  \node at (1,6){1};
%  \node at (2,6){2};
%  \node at (3,6){2};
%  \node at (4,6){2};
%  \node at (5,6){2};
%  \node at (6,6){1};
%  \node at (7,6){2};
%
%\draw (-0.5,6)--(-0.5,3);
%\draw (5.5,6)--(5.5,3);
%  \node[circle,draw=black] at (0, 5){\0};
%  \node[rectangle,draw=black] at (1, 5){\0};
%  \node[circle,draw=black] at (2, 5){\0};
%  \node[rectangle, draw=black] at (3, 5){\0};
%  \node[circle,draw=black] at (4, 5){\0};
%  \node[rectangle,draw=black] at (5, 5){\0};
%
%  \node[rectangle,draw=black] at (0, 4){\0};
%  \node[circle, draw=black] at (1, 4){\0};
%  \node[rectangle,draw=black] at (2, 4){\0};
%  \node[rectangle,draw=black] at (3, 4){\0};
%  \node[circle,draw=black] at (4, 4){\0};
%  \node[circle, draw=black] at (5, 4){\0};
%  
%  \node[rectangle,draw=black] at (-1, 5){\0};
%  \node[rectangle,draw=black] at (-2, 5){\0};
%  \node at (-3,5){$\dotsm$};
%
%  \node[rectangle,draw=black] at (6, 5){\0};
%  \node[rectangle,draw=black] at (7, 5){\0};
%  \node at (8,5){$\dotsm$};
%\end{tikzpicture}
%\]
%\caption{A balanced interval in $C_1$, together with an input word $u = \dotsm 2211222212 \dotsm$.}
%\end{figure}


\section{The TASEP connection}
\label{sec:tasep}

We now explain how our proof of Theorem~\ref{thm:permutation} gives a proof of the commutativity conjecture of~\cite{AAMP}.
The \defn{totally asymmetric simple exclusion process} (TASEP) is a Markov chain on $\mcW_{n}$ with transitions $u_i u_{i+1} \to u_{i+1} u_i$ with rate $1$ for $u_i < u_{i+1}$.
These moves preserve the type of the words, so each irreducible part of the chain corresponds to a type $\mm$.
There are $2^{n-1}$ packed types for words of length $n$ as they are compositions of $n$.
We let the subset $S \subseteq [n-1]$ correspond to the type of the word obtained by merging $i$ and $i+1$ in $12 \dotsm n$ for each $i \in S$.
Denote this type by $\mm_S$.
Note that $\set{p_1(\mm_S), \dotsc, p_{\ell-1}(\mm_S)} = [n-1] \setminus S$, where $\mm_S$ has $\ell$ classes, which is the complement of the usual bijection between subsets of $\ive{n-1}$ and compositions of $n$.
For example when $n = 4$, we have $\mm_{\emptyset} = (1,1,1,1)$ and $\mm_{\{1,2,3\}} = (4)$.

Let $\mcW_S$ denote the set of words of type $\mm_S$.
Let $V_S$ be the vector space over $\RR$ with basis $\set{\epsilon_w \mid w \in \mcW_S}$.
Let $M_S \colon V_S \to V_S$ be the transition matrix of the TASEP on $\mcW_S$.
For $i,S$ such that $i\notin S$, we define $\Psi_i \colon V_{S \cup \{i\}} \to V_S$ by letting $\Psi_i(\epsilon_u) = \sum_{q} \epsilon_{q(u)}$, where the sum is taken over all $i$-queues $q$.

In~\cite{AAMP}, it is shown that $M_S \Psi_i = \Psi_i M_{S\cup\{i\}}$.
Let $\pi_S \in V_S$ be the stationary distribution of $M_S$: the unique vector with non-negative entries summing to $1$ satisfying $\pi_S = M_S \pi_S$.
Thus, the vector $\pi_S$ can be computed from $\pi_{S\cup\{i\}}$ by $\pi_S = \Psi_i \pi_{S\cup\{i\}}$.
This allows us to compute every stationary distribution from the trivial vector $\pi_{[n]} = 1 \in \RR$.

It is conjectured in~\cite{AAMP} that $\Psi_i \Psi_j = \Psi_j\Psi_i$, where it is called the \defn{commutativity conjecture}.
By looking at the $(u,v)$ entry of both sides of this equation, the commutativity conjecture is asking whether the number of $(i,j)$-configurations $C$ such that $v = C(u)$ equals the number of $(j,i)$-configurations $C'$ such that $v = C'(u)$. 
Thus, our proof of Theorem~\ref{thm:permutation} shows that $\widetilde{\Psi}_i \widetilde{\Psi}_j = \widetilde{\Psi}_j \widetilde{\Psi}_i$ for the weighted operators $\widetilde{\Psi}_i$ given by $\widetilde{\Psi}_i(\epsilon_u) = \sum_q \wt(q) \epsilon_{q(u)}$.
Note that $\widetilde{\Psi}_i = \Psi_i$ when we specialize $x_1 = \cdots = x_n = 1$.

We have not found any process similar to the TASEP using only ``local'' moves for which our spectral weights of $u$ are the stationary probabilities.
However, we note that the Markov chain on $\mcW_n$ with transitions $u \to q(u)$ for $r$-queues $q$ (for some fixed $r$) has stationary probabilities given by our spectral weights of $u$. 





\acknowledgements{
We thank Atsuo Kuniba for explaining the results in his papers~\cite{KMO16II,KMO15,KMO16,KMO16TARZP,KMO16TARZPII}.
This work benefited from computations using \textsc{SageMath}~\cite{sage}. %For the main paper, also~\cite{combinat}.
}


%% 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

%\bibliographystyle{alpha}
%\bibliography{queue}{}
%\begin{thebibliography}{ABX}
%\bibitem{AAMP} Chikashi Arita, Arvind Ayyer, Kirone Mallick and Sylvain Prolhac, Recursive structures in the multispecies TASEP, J. Phys. A 44, 335004 (2011).
%\end{thebibliography}
\end{document}
