Simplified Forms of the Transition Probabilities of the Two-Species ASEP

Simplified Forms of the Transition Probabilities
of the Two-Species ASEP with Some Initial Orders
of Particles

Eunghyun LEE and Temirlan RAIMBEKOV E. Lee and T. Raimbekov Department of
Mathematics, Nazarbayev University, Nur-sultan, Kazakhstan
<EMAIL_ADDRESS><EMAIL_ADDRESS>https://sites.google.com/a/nu.edu.kz/eunghyun-lee-s-homepage/

Received April 15, 2021, in final form January 24, 2022; Published online
January 29, 2022

It has been known that the transition probability of the single species ASEP
with $N$ particles is expressed as a sum of $N!$ $N$-fold contour integrals
which are related to permutations in the symmetric group $S_{N}$. On other
hand, the transition probabilities of the multi-species ASEP, in general, may
be expressed as a sum of much more terms than $N!$. In this paper, we show
that if the initial order of species is given by $2\cdots 21$, $12\cdots 2$,
$1\cdots 12$ or $21\cdots 1$, then the transition probabilities can be
expressed as a sum of at most $N!$ contour integrals, and provide their
formulas explicitly.

multi-species ASEP; transition probability; Bethe ansatz; symmetric group

82C22; 60J27

##  1 Introduction

###  1.1 Definition of the model and previous results

In the multi-species asymmetric simple exclusion process (ASEP) on
$\mathbb{Z}$, particles belong to a species labelled by one of positive
integers. Each particle chooses a direction to move one step to the right or
to the left after waiting time exponentially distributed with rate 1. The
probability to choose the right direction is $p$ and the probability to choose
the left direction is $q=1-p$. If the target site is empty, the particle moves
to the site, but if the site is already occupied, the following rule is
applied: if a particle belonging to species $l$ tries moving to the target
site occupied by a particle belonging to species $l^{\prime}\geq l$, then the
move is prohibited, but if $l^{\prime}<l$, the particle belonging to $l$ can
move to the target site by interchanging sites with the particle belonging to
$l^{\prime}$. If we assume that there are $N$ particles, a state is denoted by
a pair $(X,\pi)$ where $X=(x_{1},\dots,x_{N})\in\mathbb{Z}^{N}$ with
$x_{1}<\cdots<x_{N}$ for the positions of particles and
$\pi=\pi(1)\pi(2)\cdots\pi(N)$ is a permutation of a multi-set
$\mathcal{M}=[i_{1},\dots,i_{N}]$ with elements taken from $\\{1,\dots,N\\}$
to represent the species of particles. Here, $\pi(i)$ represents the $i^{\rm
th}$ leftmost particle’s species. Since particles can interchange their
positions, the order of species may change over time. The transition
probability from the initial state $(Y,\nu)$ to state $(X,\pi)$ at time $t$ is
denoted by $P_{(Y,\nu)}(X,\pi;t).$ Earlier works on the transition
probabilities and some distributions in the multi-species ASEP are found in
[3, 6, 7, 10, 11, 12, 17, 18]. Also, the multi-species ASEP can be considered
as a special case of the coloured stochastic vertex model (see [1, 2]).
According to [12], the transition probability of the multi-species ASEP with
$N$ particles from the initial state $(Y,\nu)$ to the state $(X,\pi)$ is a
matrix element of an $N^{N}\times N^{N}$ matrix $\mathbf{P}_{Y}(X;t)$ whose
columns $\nu$ and rows $\pi$ are labelled by $11\cdots 1,\dots,NN\cdots N$. In
[12], the formula of $\mathbf{P}_{Y}(X;t)$ is written

$\displaystyle\mathbf{P}_{Y}(X;t)=\mathchoice{{\vbox{\hbox{$\textstyle-$}}\kern-4.86108pt}}{{\vbox{\hbox{$\scriptstyle-$}}\kern-3.25pt}}{{\vbox{\hbox{$\scriptscriptstyle-$}}\kern-2.29166pt}}{{\vbox{\hbox{$\scriptscriptstyle-$}}\kern-1.875pt}}\\!\int_{c}\cdots\mathchoice{{\vbox{\hbox{$\textstyle-$}}\kern-4.86108pt}}{{\vbox{\hbox{$\scriptstyle-$}}\kern-3.25pt}}{{\vbox{\hbox{$\scriptscriptstyle-$}}\kern-2.29166pt}}{{\vbox{\hbox{$\scriptscriptstyle-$}}\kern-1.875pt}}\\!\int_{c}\sum_{\sigma\in{S}_{N}}\mathbf{A}_{\sigma}\prod_{i=1}^{N}\big{(}\xi_{\sigma(i)}^{x_{i}-y_{\sigma(i)}-1}{\rm
e}^{\varepsilon(\xi_{i})t}\big{)}\,{\rm d}\xi_{1}\cdots{\rm d}\xi_{N},$ (1.1)

where $\mathbf{A}_{\sigma}$ is a $N^{N}\times N^{N}$ matrix. Note that the
form of (1.1) resembles (2.3) in [16]. Here,
$\mathchoice{{\vbox{\hbox{$\textstyle-$}}\kern-4.86108pt}}{{\vbox{\hbox{$\scriptstyle-$}}\kern-3.25pt}}{{\vbox{\hbox{$\scriptscriptstyle-$}}\kern-2.29166pt}}{{\vbox{\hbox{$\scriptscriptstyle-$}}\kern-1.875pt}}\\!\int_{c}$
implies $(1/2\pi{\rm i})\int_{c}$ where the contour $c$ is a positively
oriented circle centered at the origin with sufficiently small radius so that
no poles except the one at the origin are included in $c$, and

$\displaystyle\varepsilon(\xi_{i})=\frac{p}{\xi_{i}}+q\xi_{i}-1$

and the sum in (1.1) is over all permutations $\sigma$ in the symmetric group
$S_{N}$. The integral on the right-hand side of (1.1) implies the matrix
element-wise integral, so the $(\pi,\nu)^{\rm th}$ term of
$\mathbf{P}_{Y}(X;t)$ is

$\displaystyle[\mathbf{P}_{Y}(X;t)]_{\pi,\nu}$
$\displaystyle=P_{(Y,\nu)}(X,\pi;t)$
$\displaystyle=\mathchoice{{\vbox{\hbox{$\textstyle-$}}\kern-4.86108pt}}{{\vbox{\hbox{$\scriptstyle-$}}\kern-3.25pt}}{{\vbox{\hbox{$\scriptscriptstyle-$}}\kern-2.29166pt}}{{\vbox{\hbox{$\scriptscriptstyle-$}}\kern-1.875pt}}\\!\int_{c}\cdots\mathchoice{{\vbox{\hbox{$\textstyle-$}}\kern-4.86108pt}}{{\vbox{\hbox{$\scriptstyle-$}}\kern-3.25pt}}{{\vbox{\hbox{$\scriptscriptstyle-$}}\kern-2.29166pt}}{{\vbox{\hbox{$\scriptscriptstyle-$}}\kern-1.875pt}}\\!\int_{c}\sum_{\sigma\in{S}_{N}}[\mathbf{A}_{\sigma}]_{\pi,\nu}\prod_{i=1}^{N}\big{(}\xi_{\sigma(i)}^{x_{i}-y_{\sigma(i)}-1}{\rm
e}^{\varepsilon(\xi_{i})t}\big{)}\,{\rm d}\xi_{1}\cdots{\rm d}\xi_{N}.$ (1.2)

The procedure introduced in [12] to find the matrix $\mathbf{A}_{\sigma}$ is
as follows. Let $T_{i}$ be the simple transposition which interchanges the
number at the $i^{\rm th}$ slot and the number at the $(i+1)^{\rm st}$ slot.
It is well known that simple transpositions $T_{1},\dots,T_{N-1}$ generate the
symmetric group $S_{N}$. Hence, any permutation $\sigma\in S_{N}$ can be
written as a product of simple transpositions, that is,

$\displaystyle\sigma=T_{i_{j}}\cdots T_{i_{1}}$ (1.3)

for some $i_{1},\dots,i_{j}\in\\{1,\dots,N-1\\}$. (Here, the expression (1.3)
is not unique.) If $T_{i}$ is acted on a permutation with $\alpha$ at the
$i^{\rm th}$ slot and $\beta$ at the $(i+1)^{\rm st}$ slot, then

$\displaystyle T_{i}(\cdots\alpha\beta\cdots)=(\cdots\beta\alpha\cdots),$

and we denote this $T_{i}$ by $T_{i}(\beta,\alpha)$ when we need to show
explicitly which numbers are interchanged. For example, for $N=3$,

$\displaystyle
T_{1}T_{2}T_{1}=T_{1}T_{2}T_{1}(123)=T_{1}T_{2}(213)=T_{1}(231)=321,$

and we write $321=T_{1}(3,2)T_{2}(3,1)T_{1}(2,1)$. Hence, we will write (1.3)
as

$\displaystyle\sigma=T_{i_{j}}(\beta_{j},\alpha_{j})\cdots
T_{i_{1}}(\beta_{1},\alpha_{1})$ (1.4)

when necessary. Corresponding to $T_{i}(\beta,\alpha)$, we define $N^{N}\times
N^{N}$ matrix $\mathbf{T}_{i}(\beta,\alpha)$ by

$\displaystyle\mathbf{T}_{i}(\beta,\alpha)=\underbrace{\mathbf{I}_{N}\otimes\cdots\otimes\mathbf{I}_{N}}_{(i-1)~{}\text{times}}\otimes\mathbf{R}_{\beta\alpha}\otimes\underbrace{\mathbf{I}_{N}\otimes\cdots\otimes\mathbf{I}_{N}}_{(N-i-1)~{}\text{times}},$

where $\mathbf{I}_{N}$ is the $N\times N$ identity matrix and
$\mathbf{R}_{\beta\alpha}$ is an $N^{2}\times N^{2}$ matrix whose columns and
rows are labelled by $11,12,\dots,1N,21,\dots,NN$. The matrix elements of
$\mathbf{R}_{\beta\alpha}$ are given by

$\displaystyle[\mathbf{R}_{\beta\alpha}]_{ij,kl}=\begin{cases}S_{\beta\alpha}&\text{if}~{}ij=kl~{}\text{with}~{}i=j,\\\
P_{\beta\alpha}&\text{if}~{}ij=kl~{}\text{with}~{}i<j,\\\
Q_{\beta\alpha}&\text{if}~{}ij=kl~{}\text{with}~{}i>j,\\\
pT_{\beta\alpha}&\text{if}~{}ij=lk~{}\text{with}~{}i<j,\\\
qT_{\beta\alpha}&\text{if}~{}ij=lk~{}\text{with}~{}i>j,\\\ 0&\text{for all
other cases},\end{cases}$ (1.5)

where

$\displaystyle
S_{\beta\alpha}=-\frac{p+q\xi_{\alpha}\xi_{\beta}-\xi_{\beta}}{p+q\xi_{\alpha}\xi_{\beta}-\xi_{\alpha}},\qquad$
$\displaystyle
P_{\beta\alpha}=\frac{(p-q\xi_{\alpha})(\xi_{\beta}-1)}{p+q\xi_{\alpha}\xi_{\beta}-\xi_{\alpha}},$
$\displaystyle
T_{\beta\alpha}=\frac{\xi_{\beta}-\xi_{\alpha}}{p+q\xi_{\alpha}\xi_{\beta}-\xi_{\alpha}},\qquad$
$\displaystyle
Q_{\beta\alpha}=\frac{(p-q\xi_{\beta})(\xi_{\alpha}-1)}{p+q\xi_{\alpha}\xi_{\beta}-\xi_{\alpha}}.$

With this setting, it was obtained that $\mathbf{A}_{\sigma}$ is given by

$\displaystyle\mathbf{A}_{\sigma}=\mathbf{T}_{i_{j}}(\beta_{j},\alpha_{j})\cdots\mathbf{T}_{i_{1}}(\beta_{1},\alpha_{1}),$
(1.6)

when $\sigma$ is written as in (1.4). Although the expression (1.4) is not
unique, (1.6) is well-defined in the sense that (1.6) represents the same
matrix for any expression (1.4) (see [12, Remark 2.2]).

###  1.2 Motivation and main results

####  1.2.1 Motivation

It can be shown that $[\mathbf{A}_{\sigma}]_{\pi,\nu}=0$ in (1.2) unless both
$\pi$ and $\nu$ are from the same multi-set (see Section 2.1), and in this
case, it is obvious that $P_{(Y,\nu)}(X,\pi;t)=0$, which physically also makes
sense. However, in general, the matrix element of $\mathbf{A}_{\sigma}$ is
written as a sum because $\mathbf{A}_{\sigma}$ is a product of matrices as
seen in (1.6). If we want to know the explicit formula of
$P_{(Y,\nu)}(X,\pi;t)$, we should know the corresponding matrix elements,
$[\mathbf{A}_{\sigma}]_{\pi,\nu}$, explicitly, for all $\sigma$. It is
interesting that some elements of $\mathbf{A}_{\sigma}$ that are expressed as
sums can be further factorized. For example, for
$\sigma=321=T_{2}(2,1)T_{1}(3,1)T_{2}(3,2)$,

$\displaystyle[\mathbf{A}_{321}]_{121,211}=[\mathbf{T}_{2}(2,1)\mathbf{T}_{1}(3,1)\mathbf{T}_{2}(3,2)]_{121,221}=pP_{32}Q_{31}T_{21}+pQ_{21}S_{31}T_{32}$

but we can further observe that

$\displaystyle pP_{32}Q_{31}T_{21}+pQ_{21}S_{31}T_{32}=Q_{21}pT_{31}S_{32}.$

Actually, if we use a different expression
$\sigma=321=T_{1}(3,2)T_{2}(3,1)T_{1}(2,1)$, then we directly obtain

$\displaystyle[\mathbf{A}_{321}]_{121,211}=[\mathbf{T}_{1}(3,2)\mathbf{T}_{2}(3,1)\mathbf{T}_{1}(2,1)]_{121,221}=Q_{21}pT_{31}S_{32}$

through matrix multiplication. However, unfortunately, not all
$[\mathbf{A}_{\sigma}]_{\pi,\nu}$ can be simplified to a factorized form. In
this paper, we are interested in the factorized forms of
$[\mathbf{A}_{\sigma}]_{\pi,\nu}$ because single-species models for which the
Bethe ansatz can be applicable have factorized forms in the transition
probabilities and some interesting probability distributions were obtained
from these transition probabilities [5, 8, 9, 12, 13, 14, 15, 16, 19]. In this
paper, we show that if the initial permutation $\nu$ of species is one of
$\nu=2\cdots 21$, $1\cdots 12$, $21\cdots 1$ and $12\cdots 2$, and $\sigma$’s
expression by simple transpositions is obtained in a special way, then
$[\mathbf{A}_{\sigma}]_{\pi,\nu}$ is zero or written as a factorized form

$\displaystyle[\mathbf{A}_{\sigma}]_{\pi,\nu}=\prod_{(\beta,\alpha)}R_{\beta\alpha},$
(1.7)

where $R_{\beta\alpha}$ is one of $S_{\beta\alpha}$, $Q_{\beta\alpha}$,
$P_{\beta\alpha}$, $pT_{\beta\alpha}$ or $qT_{\beta\alpha}$, which is similar
to

$\displaystyle[\mathbf{A}_{\sigma}]_{1\cdots 1,1\cdots
1}=\prod_{(\beta,\alpha)}S_{\beta\alpha}$

in the (single species) ASEP [16]. The notation $\prod_{(\beta,\alpha)}$
implies that the product is taken over all inversions $(\beta,\alpha)$ of
$\sigma$. An inversion of a permutation $\sigma=\sigma(1)\cdots\sigma(N)$ is a
pair of elements $(\sigma(i),\sigma(j))$ with $i<j$ and $\sigma(i)>\sigma(j)$.
It will remain for future works to see if some interesting probability
distributions can be obtained in neat forms from the transition probabilities
with the formulas of $[\mathbf{A}_{\sigma}]_{\pi,\nu}$ given in this paper.

####  1.2.2 Main results

Each permutation in $S_{N}$ may be written as a product of simple
transpositions in many ways via

$\displaystyle\begin{aligned} &T_{i}T_{j}=T_{j}T_{i}&~{}~{}~{}\text{if
$|i-j|\geq 2$},\\\ &T_{i}T_{j}T_{i}=T_{j}T_{i}T_{j}&~{}~{}~{}\text{if
$|i-j|=1$},\\\ &T_{i}^{2}=1.\end{aligned}$ (1.8)

One of the findings in this paper is that if $\sigma$ is expressed as in
Theorem 1.1, which is a known fact, then $[\mathbf{A}_{\sigma}]_{\pi,2\cdots
21}$ is zero or written as (1.7). If $\sigma$ is expressed in a different way
from Theorem 1.1, then the form of $[\mathbf{A}_{\sigma}]_{\pi,2\cdots 21}$
may not be in a factorized form.

######  Theorem 1.1 ([4]).

Consider the following subsets of the symmetric group $S_{N}$.

$\displaystyle\begin{aligned} &\Sigma_{1}=\\{1,T_{1}\\},\\\
&\Sigma_{2}=\\{1,T_{2},T_{2}T_{1}\\},\\\
&\Sigma_{3}=\\{1,T_{3},T_{3}T_{2},T_{3}T_{2}T_{1}\\},\\\ &\hskip
8.5359pt\vdots\\\
&\Sigma_{N-1}=\\{1,T_{N-1},T_{N-1}T_{N-2},\dots,T_{N-1}\cdots
T_{2}T_{1}\\}.\end{aligned}$

For any permutation $\sigma\in S_{N}$, there is a unique element

$\displaystyle(w_{1},\dots,w_{N-1})\in\Sigma_{1}\times\Sigma_{2}\times\cdots\times\Sigma_{N-1}$

such that $\sigma=w_{1}w_{2}\cdots w_{N-1}$.

######  Theorem 1.2.

Let $\sigma=w_{1}\cdots w_{N-1}$ be an expression as in Theorem 1.1 and let

$\displaystyle\mathbf{A}_{\sigma}=\mathbf{T}_{i_{j}}(\beta_{j},\alpha_{j})\cdots\mathbf{T}_{i_{2}}(\beta_{2},\alpha_{2})\mathbf{T}_{i_{1}}(\beta_{1},\alpha_{1})$

be the matrix corresponding to $\sigma$. Then, for all $N\geq 2$,

  * $(a)$

$\big{[}{\mathbf{A}}_{12\cdots N}\big{]}_{2\cdots 21,2\cdots 21}=1$ and
$\big{[}{\mathbf{A}}_{12\cdots N}\big{]}_{\pi,2\cdots 21}=0$ if $\pi\neq
2\cdots 21$.

  * $(b)$

If $\sigma\neq 12\cdots N$, then
$\big{[}{\mathbf{A}}_{\sigma}\big{]}_{\pi,2\cdots 21}$ is zero or written as

$\displaystyle\big{[}{\mathbf{A}}_{\sigma}\big{]}_{\pi,2\cdots
21}=\prod_{(\beta,\alpha)}R_{\beta\alpha}$ (1.9)

where $R_{\beta\alpha}$ is one of $S_{\beta\alpha}$, $P_{\beta\alpha}$,
$Q_{\beta\alpha}$, $pT_{\beta\alpha}$, $qT_{\beta\alpha}$. The product in
(1.9) is taken over all inversions $(\beta,\alpha)$ in $\sigma$.

######  Remark 1.3.

Theorem 1.2(b) asserts the existence of the factorized form but does not
provide information on how to choose the form of $R_{\beta\alpha}$. The choice
for $R_{\beta\alpha}$ in (1.9) depends on $\sigma$ and $\pi$. The explicit
form of (1.9) will be provided in Theorems 1.4 and 1.7.

The method to express $\sigma$ in Theorem 1.1 does not work for other initial
orders $\nu=12\cdots 2,$ $1\cdots 12,$ $21\cdots 1$. In other words,
$[\mathbf{A}_{\sigma}]_{\pi,\nu}$ may not be in a factorized form if $\nu\neq
2\cdots 21$. For $\nu=12\cdots 2,$ $1\cdots 12,$ $21\cdots 1$, we need
different methods to express $\sigma$ by simple transpositions for factorized
forms of $[{\mathbf{A}}_{\sigma}]_{\pi,\nu}$. These methods will be provided
in Sections 2.3 and 2.4.

Now, we state the formulas for $[{\mathbf{A}}_{\sigma}]_{\pi,\nu}$. First, we
find the formula of the diagonal terms. That is, this is the case that initial
order of species and the order at time $t$ are the same.

######  Theorem 1.4.

Let $\nu=2\cdots 21$ and

$\displaystyle\sigma=w_{1}\cdots
w_{N-1}={T}_{i_{j}}(\beta_{j},\alpha_{j})\cdots{T}_{i_{1}}(\beta_{1},\alpha_{1})$

be given as in Theorem 1.1. Let

$\displaystyle\mathbf{A}_{\sigma}=\mathbf{T}_{i_{j}}(\beta_{j},\alpha_{j})\cdots\mathbf{T}_{i_{1}}(\beta_{1},\alpha_{1})$

be the matrix corresponding to $\sigma$. Then,

$\displaystyle[\mathbf{A}_{\sigma}]_{\nu,\nu}$
$\displaystyle=[\mathbf{T}_{i_{j}}]_{\nu,\nu}\cdots[\mathbf{T}_{i_{m}}]_{\nu,\nu}\cdots[\mathbf{T}_{i_{1}}]_{\nu,\nu}$
$\displaystyle=\begin{cases}S_{\beta_{j}\alpha_{j}}\cdots
S_{\beta_{m+1}\alpha_{m+1}}Q_{\beta_{m}\alpha_{m}}S_{\beta_{m-1}\alpha_{m-1}}\cdots
S_{\beta_{1}\alpha_{1}}&\text{if~{}$i_{m}=N-1$},\\\
S_{\beta_{j}\alpha_{j}}\cdots
S_{\beta_{1}\alpha_{1}}&\text{if~{}$i_{i},\dots,i_{j}\neq N-1$}.\end{cases}$
(1.10)

Recall that $T_{N-1}$ appears at most once in $\sigma=w_{1}\cdots w_{N-1}$ in
Theorem 1.1. In (1.10), the appearance of $Q_{\beta\alpha}$ depends on the
existence of $T_{N-1}$ in $\sigma$.

######  Remark 1.5.

We will provide the formula for $[\mathbf{A}_{\sigma}]_{\nu,\nu}$ with
$\nu=12\cdots 2,$ $1\cdots 12,$ $21\cdots 1$ in Section 3.1. Their formulas
are similar to (1.10). The formulas of $[\mathbf{A}_{\sigma}]_{\nu,\nu}$ for
some $\nu$ in the two-species TASEP are found in [10, Lemma 2.2] and [11,
Lemma 3.3]. Moreover, it was shown that the transition probabilities of the
multi-species TASEP are expressed as a determinant when the initial order and
the order at time $t$ are the same (see [12, Theorem 3.1]). In case of the
totally asymmetric model, the matrices $\mathbf{T}$ in (1.6) are upper-
triangular, so $[\mathbf{A}_{\sigma}]_{\nu,\nu}$ is expressed as a product of
some factors over all inversions in $\sigma$ for any $\nu$.

If $\pi\neq\nu$, it is possible that $[\mathbf{A}_{\sigma}]_{\pi,\nu}=0$. Let
$\pi^{(i)}$ be the permutation on the multi-set $[1,2,\dots,2]$ with
$\pi(i)=1$, for example, $\pi^{(1)}=12\cdots 2$ and $\pi^{(N)}=2\cdots
21=\nu.$

######  Theorem 1.6.

Let $\sigma=w_{1}\cdots w_{N-1}$ be expressed as in Theorem 1.1. If $l$ is the
largest integer such that $w_{l}=1$, then
$[\mathbf{A}_{\sigma}]_{\pi^{(i)},\nu}=0$ for all $i=1,\dots,l$ and
$[\mathbf{A}_{\sigma}]_{\pi^{(i)},\nu}\neq 0$ for all $i=l+1,\dots,N$.
Moreover, if $w_{i}\neq 1$ for all $i$ in $\sigma=w_{1}\cdots w_{N-1}$, then
$[\mathbf{A}_{\sigma}]_{\pi^{(i)},\nu}\neq 0$ for all $i$.

According to Theorem 1.6, if $w_{N-1}=1$, then
$[\mathbf{A}_{\sigma}]_{\pi,2\cdots 21}=0$ for all $\pi\neq 2\cdots 21$. Now,
we give the most general formula of $[\mathbf{A}_{\sigma}]_{\pi^{(i)},\nu}$
with $\nu=2\cdots 21$. First, we introduce some notations. In the expression
$\sigma=w_{1}\cdots w_{N-1}$ given by Theorem 1.1, each $w_{i}\in\Sigma_{i}$
is 1 or a product of simple transpositions, that is,

$\displaystyle
w_{i}=T_{i}(\beta_{i},\alpha_{i})T_{i-1}(\beta_{i-1},\alpha_{i-1})\cdots
T_{l}(\beta_{l},\alpha_{l})$

for some $l$. We write

$\displaystyle\mathbf{w}_{i}=\mathbf{T}_{i}(\beta_{i},\alpha_{i})\mathbf{T}_{i-1}(\beta_{i-1},\alpha_{i-1})\cdots\mathbf{T}_{l}(\beta_{l},\alpha_{l})$

for the matrix corresponding to $w_{i}$. We define

$\displaystyle\prod_{i=l}^{m}A_{i}=1\quad\text{if~{}$l>m$}.$

######  Theorem 1.7.

Let $\sigma=w_{1}\cdots w_{N-1}$ be expressed as in Theorem 1.1. Then,

$\displaystyle[\mathbf{A}_{\sigma}]_{\pi^{(i)},\nu}=\prod_{k=1}^{i-1}[\mathbf{w}_{k}]_{\pi^{(i)},\pi^{(i)}}\prod_{k=i}^{N-1}[\mathbf{w}_{k}]_{\pi^{(k)},\pi^{(k+1)}}.$
(1.11)

Theorem 1.7 includes the results in Theorems 1.4 and 1.6. This will be shown
in Section 3.3. The following results implement the formula (1.11).

######  Proposition 1.8.

Let $\sigma=w_{1}\cdots w_{N-1}$ be expressed as in Theorem 1.1 and let
$\mathbf{w}_{k}$ be the matrix corresponding to
$w_{k}={T}_{k_{1}}(\beta_{k_{1}},\alpha_{k_{1}})\cdots{T}_{k_{l}}(\beta_{k_{l}},\alpha_{k_{l}})$.
$($Hence, $k_{1}=k$, $k_{2}=k-1$ and so on.$)$ Then,

$\displaystyle[\mathbf{w}_{k}]_{\pi^{(i)},\pi^{(i)}}=\begin{cases}Q_{\beta_{k_{1}}\alpha_{k_{1}}}S_{\beta_{k_{2}}\alpha_{k_{2}}}\cdots
S_{\beta_{k_{l}}\alpha_{k_{l}}}&\text{if $i=k+1$},\\\
S_{\beta_{k_{1}}\alpha_{k_{1}}}\cdots S_{\beta_{k_{l}}\alpha_{k_{l}}}&\text{if
$i>k+1$}\end{cases}$ (1.12)

and

$\displaystyle[\mathbf{w}_{k}]_{\pi^{(k)},\pi^{(k+1)}}=pT_{\beta_{k_{1}}\alpha_{k_{1}}}S_{\beta_{k_{2}}\alpha_{k_{2}}}\cdots
S_{\beta_{k_{l}}\alpha_{k_{l}}}.$ (1.13)

######  Remark 1.9.

The formulas for $\nu=12\cdots 2,21\cdots 1$ and $1\cdots 12$ corresponding to
(1.11), (1.12) and (1.13) can be obtained in a very similar way by using the
techniques used for the case $\nu=2\cdots 21$, so we omit them in this paper.

######  Remark 1.10.

The technique in [12] provided a method to find the explicit formulas of the
transition probabilities but $[\mathbf{A}_{\sigma}]_{\pi,\nu}$ could be a sum
of multiple terms in general, and it was not sure that it could be simplified
further or not. One advantage of using the method of expressing permutations
in this paper is that we can directly obtain the simplified forms of
$[\mathbf{A}_{\sigma}]_{\pi,\nu}$ without performing factorization. This will
improve the computational efficiency to find the transition probabilities.

###  1.3 Organization of the paper

This paper is organized as follows. In Section 2, we provide special ways of
expressing $\sigma$ as a product of simple transpositions for simplified forms
of $[\mathbf{A}_{\sigma}]_{\pi,\nu}$ for
$\nu=2{\cdots}21,12{\cdots}2,21{\cdots}1,1{\cdots}12$. The proof of Theorem
1.2 is given in Section 2.2. In Section 3.1, we prove Theorem 1.4 and provide
the formulas of $[\mathbf{A}_{\sigma}]_{\nu,\nu}$ for $\nu=12\cdots 2,21\cdots
1,1\cdots 12$ in Propositions 3.2, 3.3, and 3.4. The proof of Theorem 1.6 is
given in Section 3.2, the proofs of Theorem 1.7 and Proposition 1.8 are given
in Section 3.3. In Appendix A, we introduce an alternate approach to find
$[\mathbf{A}_{\sigma}]_{\pi,\nu}$. In particular, the method introduced in
Example A.2 is expected to be useful to write a computer code to find
$[\mathbf{A}_{\sigma}]_{\pi,\nu}$. In Appendices B and C, we provide all
transition probabilities for $N=4$ when initial orders are $2221$ and ${1112}$
so that one can see what probability distribution can be obtained in closed
forms.

##  2 How to express $\boldsymbol{\sigma}$ for simplified
$\boldsymbol{[\mathbf{A}_{\sigma}]_{\pi,\nu}}$

###  2.1 Rearrangement of the columns and the rows

In [12], the columns and the rows of the $N^{N}\times N^{N}$ matrices are
labelled by $1\cdots 1,\dots,N\cdots N$ in the lexicographical order. But, if
we rearrange the columns and the rows by grouping their labels from the same
multi-set $\mathcal{M}$, then $\mathbf{P}_{Y}(X;t)$, $\mathbf{A}_{\sigma}$ and
$\mathbf{T}_{i}(\beta,\alpha)$ become block-diagonal. In each group, we list
the columns and the rows in the lexicographical order. If we follow this
procedure of rearranging the columns and the rows, then, for example, the form
of the matrices $\mathbf{P}_{Y}(X;t)$, $\mathbf{A}_{\sigma}$ and
$\mathbf{T}_{i}(\beta,\alpha)$ with $N=3$ looks as in Figure 1. We denote the
block corresponding to a multi-set $\mathcal{M}$ in the $N^{N}\times N^{N}$
matrix $\mathbf{A}$ by $\mathbf{A}^{\mathcal{M}}$. In other words,
$\mathbf{A}^{\mathcal{M}}$ is a sub-matrix of $\mathbf{A}$ obtained by taking
the columns and the rows whose labels are the permutations of the multi-set
$\mathcal{M}$. Although the columns and the rows of $\mathbf{A}^{\mathcal{M}}$
are labelled by permutations $\pi$, $\nu$ of $\mathcal{M}$ so that
$\big{[}\mathbf{A}^{\mathcal{M}}\big{]}_{\pi,\nu}$ is the $(\pi,\nu)^{\rm th}$
element of $\mathbf{A}^{\mathcal{M}}$, we will sometimes write
$\big{[}\mathbf{A}^{\mathcal{M}}\big{]}_{i,j}$ where $i,j=1,\dots,L$ for the
$(i,j)^{\rm th}$ element in the usual notation for matrix elements when
necessary if there is not confusion. Here, $L$ is the total number of
permutations of $\mathcal{M}$.

$\left[\vbox{\hrule
height=98.66562pt,depth=98.66562pt,width=0.0pt}\right.$$\left.\vbox{\hrule
height=98.66562pt,depth=98.66562pt,width=0.0pt}\right]$ 111 222 333 $\cdots$
122 212 221 $\cdots$ 321 111 222 333 ⋮ $\ddots$ 122 212 221 ⋮ $\ddots$ 321
Figure 1: The form of the matrix after rearranging the columns and the rows.

###  2.2 Proof of Theorem 1.2

An expression of $\sigma$ obtained by Theorem 1.1 is a reduced expression of
$\sigma$, that is, no other expression of $\sigma$ is shorter than that.
Rewriting each $w_{i}$ in $\sigma=w_{1}w_{2}\cdots w_{N-1}$ explicitly by
simple transpositions, we obtain an expression of $\sigma$ in terms of simple
transpositions

$\displaystyle\sigma=w_{1}w_{2}\cdots
w_{N-1}=T_{i_{j}}(\beta_{j},\alpha_{j})\cdots
T_{i_{2}}(\beta_{2},\alpha_{2})T_{i_{1}}(\beta_{1},\alpha_{1})$ (2.1)

and

$\displaystyle\\{(\beta_{1},\alpha_{1}),(\beta_{2},\alpha_{2}),\dots,(\beta_{j},\alpha_{j})\\}$

is the set of all inversions of $\sigma$. Using the notation introduced in
Section 2.1, we note that

$\displaystyle{\mathbf{T}}_{l}^{\mathcal{M}_{N}}(\beta,\alpha)=(S_{\beta\alpha}\mathbf{I}_{l-1})\oplus\left[\begin{matrix}P_{\beta\alpha}&pT_{\beta\alpha}\\\
qT_{\beta\alpha}&Q_{\beta\alpha}\end{matrix}\right]\oplus(S_{\beta\alpha}\mathbf{I}_{N-l-1}),\qquad
l=1,\dots,N-1,$ (2.2)

when $\mathcal{M}_{N}=[1,\underbrace{2,\dots,2}_{N-1}]$. The form of
${\mathbf{T}}_{l}^{\mathcal{M}_{N}}(\beta,\alpha)$ is as in Figure 2.

$\left[\vbox{\hrule
height=98.66562pt,depth=98.66562pt,width=0.0pt}\right.$$\left.\vbox{\hrule
height=98.66562pt,depth=98.66562pt,width=0.0pt}\right]$ $\left[\vbox{\hrule
height=79.5861pt,depth=79.5861pt,width=0.0pt}\right.$$\left.\vbox{\hrule
height=79.5861pt,depth=79.5861pt,width=0.0pt}\right]$ 1 $\cdots$ $\cdots$ $l$
$l+1$ $\cdots$ $\cdots$ $N$ 1 * ⋮ $\ddots$ ⋮ * $l$ * * $l+1$ * * ⋮ * ⋮
$\ddots$ $N$ * Figure 2: The form of the matrix
$\mathbf{T}_{l}^{\mathcal{M}_{N}}$.

Since we are interested in the last column of
$\mathbf{A}_{\sigma}^{\mathcal{M}_{N}}=(\mathbf{w}_{1}\cdots\mathbf{w}_{N-1})^{\mathcal{M}_{N}}$,
we investigate the last column of $(\mathbf{w}_{N-1})^{\mathcal{M}_{N}}$.

######  Lemma 2.1.

For $N\geq 2$ and $l=1,\dots,N-1$,

$\displaystyle\big{[}\mathbf{T}_{N-1}^{\mathcal{M}_{N}}(\beta_{N-1},\alpha_{N-1})\cdots\mathbf{T}_{l}^{\mathcal{M}_{N}}(\beta_{l},\alpha_{l})\big{]}_{i,N}$
$\displaystyle\qquad{}=\begin{cases}0&\text{if $i=1,\dots,N-2$},\\\
pT_{\beta_{N-1}\alpha_{N-1}}S_{\beta_{N-2}\alpha_{N-2}}\cdots
S_{\beta_{l}\alpha_{l}}&\text{if $i=N-1$},\\\
Q_{\beta_{N-1}\alpha_{N-1}}S_{\beta_{N-2}\alpha_{N-2}}\cdots
S_{\beta_{l}\alpha_{l}}&\text{if $i=N$}.\end{cases}$

###### Proof.

If $N=2$, then

$\displaystyle\mathbf{T}_{1}^{\mathcal{M}_{2}}(\beta_{1},\alpha_{1})=\left[\begin{matrix}P_{\beta_{1}\alpha_{1}}&pT_{\beta_{1}\alpha_{1}}\\\
qT_{\beta_{1}\alpha_{1}}&Q_{\beta_{1}\alpha_{1}}\end{matrix}\right].$

Suppose that $N>2$. First, we observe that

$\displaystyle\mathbf{T}^{\mathcal{M}_{N}}_{l}(\beta,\alpha)=\mathbf{T}^{\mathcal{M}_{N-1}}_{l}(\beta,\alpha)\oplus
S_{\beta\alpha}\qquad\text{for $l=1,\dots,N-2$}$ (2.3)

and

$\displaystyle\mathbf{T}_{N-1}^{\mathcal{M}_{N}}(\beta,\alpha)=(S_{\beta\alpha}\mathbf{I}_{N-2})\oplus\left[\begin{matrix}P_{\beta\alpha}&pT_{\beta\alpha}\\\
qT_{\beta\alpha}&Q_{\beta\alpha}\end{matrix}\right].$

Hence,

$\displaystyle\mathbf{T}^{\mathcal{M}_{N}}_{N-1}(\beta_{N-1},\alpha_{N-1})\cdots\mathbf{T}^{\mathcal{M}_{N}}_{l}(\beta_{l},\alpha_{l})$
$\displaystyle\qquad{}=\left((S_{\beta_{N-1}\alpha_{N-1}}\mathbf{I}_{N-2})\oplus\left[\begin{matrix}P_{\beta_{N-1}\alpha_{N-1}}&pT_{\beta_{N-1}\alpha_{N-1}}\\\
qT_{\beta_{N-1}\alpha_{N-1}}&Q_{\beta_{N-1}\alpha_{N-1}}\end{matrix}\right]\right)$
$\displaystyle\qquad\quad{}\times\big{(}\mathbf{T}^{\mathcal{M}_{N-1}}_{N-2}(\beta_{N-2},\alpha_{N-2})\oplus
S_{\beta_{N-2}\alpha_{N-2}}\big{)}\cdots\big{(}\mathbf{T}^{\mathcal{M}_{N-1}}_{l}(\beta_{l},\alpha_{l})\oplus
S_{\beta_{l}\alpha_{l}}\big{)}$
$\displaystyle\qquad{}=\left(\big{(}S_{\beta_{N-1}\alpha_{N-1}}\mathbf{I}_{N-2}\big{)}\oplus\left[\begin{matrix}P_{\beta_{N-1}\alpha_{N-1}}&pT_{\beta_{N-1}\alpha_{N-1}}\\\
qT_{\beta_{N-1}\alpha_{N-1}}&Q_{\beta_{N-1}\alpha_{N-1}}\end{matrix}\right]\right)$
$\displaystyle\qquad\quad{}\times\big{(}\mathbf{T}^{\mathcal{M}_{N-1}}_{N-2}(\beta_{N-2},\alpha_{N-2})\cdots\mathbf{T}^{\mathcal{M}_{N-1}}_{l}(\beta_{l},\alpha_{l})\big{)}\oplus\big{(}S_{\beta_{N-2}\alpha_{N-2}}\cdots
S_{\beta_{l}\alpha_{l}}\big{)},$

whose the last column is clearly

$\displaystyle\Bigg{[}\underbrace{0~{}\cdots~{}0}_{N-2}~{}~{}pT_{\beta_{N-1}\alpha_{N-1}}\prod_{i=l}^{N-2}S_{\beta_{i}\alpha_{i}}~{}~{}Q_{\beta_{N-1}\alpha_{N-1}}\prod_{i=l}^{N-2}S_{\beta_{i}\alpha_{i}}\Bigg{]}^{\rm
T}.$ ∎

###### Proof of Theorem 1.2.

For all $N\geq 2$, if $\sigma$ is the identity permutation, then it is obvious
that $[{\mathbf{A}}_{\sigma}]_{2\cdots 21,2\cdots 21}=1$ and
$[{\mathbf{A}}_{\sigma}]_{\pi,2\cdots 21}=0$ for $\pi\neq 2\cdots 21$ because
$\mathbf{A}_{12\cdots N}$ is the identity matrix. Suppose that $\sigma$ is not
the identity permutation. We prove by induction on $N$. If $N=2$, then
$\mathbf{A}_{21}=\mathbf{R}_{21}$. Hence,

$\displaystyle[\mathbf{A}_{21}]_{21,21}=Q_{21},\qquad[\mathbf{A}_{21}]_{12,21}=pT_{21}.$

Suppose that the statement holds for $N-1$. Recall (2.3). If $w_{N-1}=1$ in
(2.1), then

$\displaystyle\mathbf{A}_{\sigma}^{\mathcal{M}_{N}}$
$\displaystyle=\mathbf{T}_{i_{j}}^{\mathcal{M}_{N}}(\beta_{j},\alpha_{j})\cdots\mathbf{T}_{i_{2}}^{\mathcal{M}_{N}}(\beta_{2},\alpha_{2})\mathbf{T}_{i_{1}}^{\mathcal{M}_{N}}(\beta_{1},\alpha_{1})$
$\displaystyle=\big{(}\mathbf{T}_{i_{j}}^{\mathcal{M}_{N-1}}(\beta_{j},\alpha_{j})\oplus
S_{\beta_{j}\alpha_{j}}\big{)}\cdots\big{(}\mathbf{T}_{i_{1}}^{\mathcal{M}_{N-1}}(\beta_{1},\alpha_{1})\oplus
S_{\beta_{1}\alpha_{1}}\big{)}$
$\displaystyle=\big{(}\mathbf{T}_{i_{j}}^{\mathcal{M}_{N-1}}(\beta_{j},\alpha_{j})\cdots\mathbf{T}_{i_{1}}^{\mathcal{M}_{N-1}}(\beta_{1},\alpha_{1})\big{)}\oplus\prod_{i=1}^{j}S_{\beta_{i}\alpha_{i}}.$

Hence, the last column of $\mathbf{A}_{\sigma}^{\mathcal{M}_{N}}$ is

$\displaystyle\bigg{[}0~{}\cdots~{}f0~{}~{}\prod_{i=1}^{j}S_{\beta_{i}\alpha_{i}}\bigg{]}^{T}.$

If

$\displaystyle w_{N-1}=T_{i_{m}}(\beta_{m},\alpha_{m})\cdots
T_{i_{1}}(\beta_{1},\alpha_{1})$

in (2.1) so that
$T_{i_{m}}(\beta_{m},\alpha_{m})=T_{N-1}(\beta_{m},\alpha_{m})$, then

$\displaystyle\big{[}\mathbf{A}_{\sigma}^{\mathcal{M}_{N}}\big{]}_{\pi,2\cdots
21}$
$\displaystyle\quad{}=\sum_{\nu}\big{[}\mathbf{T}_{i_{j}}^{\mathcal{M}_{N}}(\beta_{j},\alpha_{j})\cdots\mathbf{T}_{i_{m+1}}^{\mathcal{M}_{N}}(\beta_{m+1},\alpha_{m+1})\big{]}_{\pi,\nu}\big{[}\mathbf{T}_{i_{m}}^{\mathcal{M}_{N}}(\beta_{m},\alpha_{m})\cdots\mathbf{T}_{i_{1}}^{\mathcal{M}_{N}}(\beta_{1},\alpha_{1})\big{]}_{\nu,2\cdots
21}.$

We have

$\displaystyle\mathbf{T}_{i_{j}}^{\mathcal{M}_{N}}(\beta_{j},\alpha_{j})\cdots\mathbf{T}_{i_{m+1}}^{\mathcal{M}_{N}}(\beta_{m+1},\alpha_{m+1})$
$\displaystyle\qquad{}=\big{(}\mathbf{T}_{i_{j}}^{\mathcal{M}_{N-1}}(\beta_{j},\alpha_{j})\oplus
S_{\beta_{j}\alpha_{j}}\big{)}\cdots\big{(}\mathbf{T}_{i_{m+1}}^{\mathcal{M}_{N-1}}(\beta_{m+1},\alpha_{m+1})\oplus
S_{\beta_{m+1}\alpha_{m+1}}\big{)}$
$\displaystyle\qquad{}=\big{(}\mathbf{T}_{i_{j}}^{\mathcal{M}_{N-1}}(\beta_{j},\alpha_{j})\cdots\mathbf{T}_{i_{m+1}}^{\mathcal{M}_{N-1}}(\beta_{m+1},\alpha_{m+1})\big{)}\oplus\prod_{i=m+1}^{j}S_{\beta_{i}\alpha_{i}},$

whose the $i^{{\rm th}}$ row ($i=1,\dots,N-3$) is in the form of

$\displaystyle\big{[}~{}\underbrace{*~{}\cdots~{}*}_{N-2}~{}0~{}~{}0~{}\big{]}$

and the $(N-1)^{{\rm st}}$ and the $(N-2)^{{\rm nd}}$ rows are in the form of

$\displaystyle\Bigg{[}\underbrace{*~{}\cdots~{}*}_{N-2}~{}~{}\prod_{i=m+1}^{j}R_{\beta_{i}\alpha_{i}}~{}~{}0\Bigg{]}$

by the induction hypothesis for $N-1$. The $N^{{\rm th}}$ row is

$\displaystyle\Bigg{[}\underbrace{0~{}\cdots~{}0}_{N-1}~{}~{}\prod_{i=m+1}^{j}S_{\beta_{i}\alpha_{i}}\Bigg{]}.$

By Lemma 2.1, the last column of
$\mathbf{T}_{i_{m}}^{\mathcal{M}_{N}}(\beta_{m},\alpha_{m})\cdots\mathbf{T}_{i_{1}}^{\mathcal{M}_{N}}(\beta_{1},\alpha_{1})$
is

$\displaystyle\begin{aligned}
\Bigg{[}\underbrace{0~{}\cdots~{}0}_{N-2}~{}~{}pT_{\beta_{m}\alpha_{m}}\prod_{i=1}^{m-1}S_{\beta_{i}\alpha_{i}}~{}~{}Q_{\beta_{m}\alpha_{m}}\prod_{i=1}^{m-1}S_{\beta_{i}\alpha_{i}}\Bigg{]}^{T}.\end{aligned}$

Hence, $\big{[}\mathbf{A}_{\sigma}^{\mathcal{M}_{N}}\big{]}_{\pi,2\cdots 21}$
is zero or in the form of $\prod_{i=1}^{j}R_{\beta_{i}\alpha_{i}}.$ ∎

###  2.3 Expressions of $\boldsymbol{\sigma}$ for
$\boldsymbol{[\mathbf{A}_{\sigma}]_{\pi,12\cdots 2}}$

If $\sigma\in S_{N}$ is expressed as in Theorem 1.1, then
$[\mathbf{A}_{\sigma}]_{\pi,12\cdots 2}$ may not be in a simplified form. In
this section, we will find another way to express $\sigma$ as a product of
simple transpositions for which $[\mathbf{A}_{\sigma}]_{\pi,12\cdots 2}$ is
directly written as a factorized form. According to [4, Lemma 4.2], every
element $\sigma\in S_{N}$ can be written as a product of $T_{1},\dots,T_{N-1}$
with $T_{N-1}$ appearing at most once. Similarly, we have the following
result.

######  Lemma 2.2.

Every element $\sigma\in S_{N}$ can be written as a product of
$T_{1},\dots,T_{N-1}$ with $T_{1}$ appearing at most once.

Lemma 2.2 can be proved by the mathematical induction in a similar way to the
proof of Lemma 4.2 in [4] by using the fact that the set of all bijections on
$\\{2,\dots,N\\}$ is isomorphic to the set of all bijections on
$\\{1,\dots,N-1\\}$. Proposition 2.3, similar to Theorem 1.1, provides a
method to express $\sigma$ as a product of simple transpositions with $T_{1}$
appearing at most once, and we use this method for simplified forms of
$[\mathbf{A}_{\sigma}]_{\pi,12\cdots 2}$.

######  Proposition 2.3.

Consider the following subsets of the symmetric group $S_{N}$:

$\displaystyle\begin{aligned}
&\Omega_{N-1}=\\{1,T_{1},T_{2}T_{1},\dots,T_{N-1}\cdots T_{2}T_{1}\\},\\\
&\Omega_{N-2}=\\{1,T_{2},T_{3}T_{2},\dots,T_{N-1}\cdots T_{2}\\},\\\ &\hskip
8.5359pt\vdots\\\ &\Omega_{2}=\\{1,T_{N-2},T_{N-1}T_{N-2}\\},\\\
&\Omega_{1}=\\{1,T_{N-1}\\}.\end{aligned}$

For any permutation $\sigma\in S_{N}$, there is a unique element

$\displaystyle(w_{N-1},\dots,w_{1})\in\Omega_{N-1}\times\Omega_{N-2}\times\cdots\times\Omega_{1}$

such that $\sigma=w_{N-1}w_{N-2}\cdots w_{1}$.

###### Proof.

We prove this by induction on $N$. The statement is obvious for $N=2$. Suppose
that the statement holds for $N-1$. It suffices to prove for $\sigma\in S_{N}$
represented by $T_{1},\dots,T_{N-1}$ in which $T_{1}$ appears exactly once by
Lemma 2.2. (If $T_{1}$ does not appear in the representation of $\sigma$, then
$\sigma(1)=1$ and there exist $w_{i}\in\Omega_{i},~{}i=1,\dots,N-2$ such that
$\sigma$ is uniquely written as $\sigma=w_{N-2}\cdots w_{1}$ by the induction
hypothesis for $N-1$.) Let $\sigma=\sigma^{\prime}T_{1}\sigma^{\prime\prime}$
where $\sigma^{\prime}$ and $\sigma^{\prime\prime}$ are words consisting of
$T_{2},\dots,T_{N-1}$. By the induction hypothesis, there exist
$w^{\prime}_{i}\in\Omega_{i},~{}i=1,\dots,N-2$ such that $\sigma^{\prime}$ is
uniquely written as $\sigma^{\prime}=w^{\prime}_{N-2}\cdots w^{\prime}_{1}$ so
that $\sigma=w^{\prime}_{N-2}\cdots w^{\prime}_{1}T_{1}\sigma^{\prime\prime}$.
By (1.8), $T_{1}$ commutes with $w^{\prime}_{1},\dots,w^{\prime}_{N-3}$, so

$\displaystyle\sigma=w^{\prime}_{N-2}T_{1}w^{\prime}_{N-3}\cdots
w^{\prime}_{1}\sigma^{\prime\prime}.$

Since $w^{\prime}_{N-3}\cdots w^{\prime}_{1}\sigma^{\prime\prime}$ is a word
consisting of $T_{2},\dots,T_{N-1}$, it may be written uniquely as
$w^{\prime\prime}_{N-2}\cdots w^{\prime\prime}_{1}$ for some
$w^{\prime\prime}_{i}\in\Omega_{i}$ by the induction hypothesis. It is clear
that $w^{\prime}_{N-2}T_{1}\in\Omega_{N-1}$. ∎

$[\mathbf{A}_{\sigma}]_{\pi,12\cdots 2}$ implies the first column of
$\mathbf{A}_{\sigma}^{\mathcal{M}_{N}}=(\mathbf{w}_{N-1}\cdots\mathbf{w}_{1})^{\mathcal{M}_{N}}$.
Let us find the form of the first column of
$(\mathbf{w}_{N-1})^{\mathcal{M}_{N}}$ (The reason why we consider this will
be clearer soon). Note that non-identity $w_{N-1}\in\Omega_{N-1}$ is in the
form of $T_{l}T_{l-1}\cdots T_{1}$ for some $l$.

######  Lemma 2.4.

For $N\geq 2$ and $l=1,\dots,N-1$,

$\displaystyle\big{[}\mathbf{T}_{l}^{\mathcal{M}_{N}}(\beta_{l},\alpha_{l})\cdots\mathbf{T}_{1}^{\mathcal{M}_{N}}(\beta_{1},\alpha_{1})\big{]}_{i,1}$

is in the form of $\prod_{k=1}^{l}R_{\beta_{k}\alpha_{k}}$ where
$R_{\beta\alpha}$ is one of $S_{\beta\alpha}$, $P_{\beta\alpha}$,
$Q_{\beta\alpha}$, $pT_{\beta\alpha}$ or $qT_{\beta\alpha}$ if $1\leq i\leq
l+1$, and is zero if $l+1<i\leq N$.

###### Proof.

We prove by induction on $N$. If $N=2$,

$\displaystyle\mathbf{T}_{1}^{\mathcal{M}_{2}}(\beta_{1},\alpha_{1})=\left[\begin{matrix}P_{\beta_{1}\alpha_{1}}&pT_{\beta_{1}\alpha_{1}}\\\
qT_{\beta_{1}\alpha_{1}}&Q_{\beta_{1}\alpha_{1}}\end{matrix}\right].$

Suppose that the statement is true for $N-1$. If $l=1,\dots,N-2$, the
induction hypothesis and (2.3) imply that

$\displaystyle\big{[}\mathbf{T}_{l}^{\mathcal{M}_{N}}(\beta_{l},\alpha_{l})\cdots\mathbf{T}_{1}^{\mathcal{M}_{N}}(\beta_{1},\alpha_{1})\big{]}_{i,1}$

is in the form of $\prod_{k=1}^{l}R_{\beta_{k}\alpha_{k}}$ if $1\leq i\leq
l+1$, and is zero if $l+1<i\leq N$. Let $l=N-1$. Then,

$\displaystyle\big{[}\mathbf{T}_{N-2}^{\mathcal{M}_{N}}(\beta_{N-2},\alpha_{N-2})\cdots\mathbf{T}_{1}^{\mathcal{M}_{N}}(\beta_{1},\alpha_{1})\big{]}_{i,1}$

is in the form of $\prod_{k=1}^{N-2}R_{\beta_{k}\alpha_{k}}$ for
$i=1,\dots,N-1$ and is zero for $i=N$ by the induction hypothesis. Noting that

$\displaystyle\mathbf{T}_{N-1}^{\mathcal{M}_{N}}(\beta,\alpha)=\big{(}S_{\beta\alpha}\mathbf{I}_{N-2}\big{)}\oplus\left[\begin{matrix}P_{\beta\alpha}&pT_{\beta\alpha}\\\
qT_{\beta\alpha}&Q_{\beta\alpha}\end{matrix}\right]$

and computing

$\displaystyle\big{[}\mathbf{T}_{N-1}^{\mathcal{M}_{N}}(\beta_{N-1},\alpha_{N-1})\mathbf{T}_{N-2}^{\mathcal{M}_{N}}(\beta_{N-2},\alpha_{N-2})\cdots\mathbf{T}_{1}^{\mathcal{M}_{N}}(\beta_{1},\alpha_{1})\big{]}_{i,1}$
(2.4)

directly, we can show that (2.4) is in the form of
$\prod_{k=1}^{N-1}R_{\beta_{k}\alpha_{k}}$ for all $i$. ∎

Rewriting each $w_{i}$ in $\sigma=w_{N-1}\cdots w_{1}$ in Proposition 2.3
explicitly by simple transpositions, we obtain an expression of $\sigma$ in
terms of simple transpositions

$\displaystyle\sigma=w_{N-1}\cdots
w_{2}w_{1}=T_{i_{j}}(\beta_{j},\alpha_{j})\cdots
T_{i_{2}}(\beta_{2},\alpha_{2})T_{i_{1}}(\beta_{1},\alpha_{1})$

and

$\displaystyle\\{(\beta_{1},\alpha_{1}),(\beta_{2},\alpha_{2}),\dots,(\beta_{j},\alpha_{j})\\}$

is the set of all inversions in $\sigma$.

######  Theorem 2.5.

Let $\sigma=w_{N-1}\cdots w_{1}$ be an expression as in Proposition 2.3 and
let $\mathbf{A}_{\sigma}$ be the matrix corresponding $\sigma$. Then, for all
$N\geq 2$,

  * $(a)$

$\big{[}{\mathbf{A}}_{12\cdots N}\big{]}_{12\cdots 2,12\cdots 2}=1$ and
$\big{[}{\mathbf{A}}_{12\cdots N}\big{]}_{\pi,12\cdots 2}=0$ if $\pi\neq
12\cdots 2$.

  * $(b)$

If $\sigma\neq 12\cdots N$, then
$\big{[}{\mathbf{A}}_{\sigma}\big{]}_{\pi,12\cdots 2}$ is zero or written as

$\displaystyle\big{[}{\mathbf{A}}_{\sigma}\big{]}_{\pi,12\cdots
2}=\prod_{(\beta,\alpha)}R_{\beta\alpha}$ (2.5)

where $R_{\beta\alpha}$ is one of $S_{\beta\alpha}$, $P_{\beta\alpha}$,
$Q_{\beta\alpha}$, $pT_{\beta\alpha}$, $qT_{\beta\alpha}$ and the product in
(2.5) is taken over all inversions $(\beta,\alpha)$ in $\sigma$.

###### Proof.

Let

$\displaystyle\mathbf{A}_{\sigma}=\mathbf{w}_{N-1}\cdots\mathbf{w}_{1}=\underbrace{\mathbf{T}_{i_{j}}(\beta_{j},\alpha_{j})\cdots\mathbf{T}_{i_{m+1}}(\beta_{m+1},\alpha_{m+1})}_{=\mathbf{w}_{N-1}}~{}\underbrace{\mathbf{T}_{i_{m}}(\beta_{m},\alpha_{m})\cdots\mathbf{T}_{i_{1}}(\beta_{1},\alpha_{1})}_{=\mathbf{w}_{N-2}\cdots\mathbf{w}_{1}}.$

For all $N\geq 2$, if $\sigma$ is the identity permutation, then it is obvious
that $[{\mathbf{A}}_{\sigma}]_{12\cdots 2,12\cdots 2}=1$ and
$[{\mathbf{A}}_{\sigma}]_{\pi,12\cdots 2}=0$ for $\pi\neq 12\cdots 2$ because
$\mathbf{A}_{12\cdots N}$ is the identity matrix. Suppose that $\sigma$ is not
the identity permutation. Since there is no $T_{1}$ in $w_{N-2}\cdots w_{1}$,

$\displaystyle(\mathbf{w}_{N-2}\cdots\mathbf{w}_{1})^{\mathcal{M}_{N}}=\prod_{i=1}^{m}S_{\beta_{i}\alpha_{i}}\oplus\mathbf{G}_{N-1}$

for some $(N-1)\times(N-1)$ matrix $\mathbf{G}_{N-1}$ by (2.2). By Lemma 2.4,
$\big{[}(\mathbf{w}_{N-1})^{\mathcal{M}_{N}}\big{]}_{l,1}$ is zero if
$i_{j}+1<l\leq N$, and is in the form of
$\prod_{k=m+1}^{j}R_{\beta_{k}\alpha_{k}}$ if $1\leq l\leq i_{j}+1$. Hence,

$\displaystyle\big{[}(\mathbf{w}_{N-1})^{\mathcal{M}_{N}}(\mathbf{w}_{N-2}\cdots\mathbf{w}_{1})^{\mathcal{M}_{N}}\big{]}_{l,1}=\prod_{i=1}^{m}S_{\beta_{i}\alpha_{i}}\prod_{k=m+1}^{j}R_{\beta_{k}\alpha_{k}}$

for some $R_{\beta_{k}\alpha_{k}}$ if $1\leq l\leq i_{j}+1$, and is zero
$i_{j}+1<l\leq N$. ∎

###  2.4 Expressions of $\boldsymbol{\sigma}$ for
$\boldsymbol{[\mathbf{A}_{\sigma}]_{\pi,21\cdots 1}}$ and
$\boldsymbol{[\mathbf{A}_{\sigma}]_{\pi,1\cdots 12}}$

In order to find $[\mathbf{A}_{\sigma}]_{\pi,21\cdots 1}$ in factorized forms,
$\sigma$ should be expressed as follows.

######  Proposition 2.6.

Consider the following subsets of the symmetric group $S_{N}$:

$\displaystyle\begin{aligned} &\Gamma_{N-1}=\\{1,T_{N-1}\\},\\\
&\Gamma_{N-2}=\\{1,T_{N-2},T_{N-2}T_{N-1}\\},\\\
&\Gamma_{N-3}=\\{1,T_{N-3},T_{N-3}T_{N-2},T_{N-3}T_{N-2}T_{N-1}\\},\\\ &\hskip
8.5359pt\vdots\\\ &\Gamma_{1}=\\{1,T_{1},T_{1}T_{2},\dots,T_{1}\cdots
T_{N-2}T_{N-1}\\}.\end{aligned}$

For any permutation $\sigma\in S_{N}$, there is a unique element

$\displaystyle(w_{N-1},\dots,w_{2},w_{1})\in\Gamma_{N-1}\times\cdots\times\Gamma_{2}\times\Gamma_{1}$

such that $\sigma=w_{N-1}\cdots w_{2}w_{1}$.

###### Proof.

We prove this by induction on $N$. The statement is obvious for $N=2$. Suppose
that the statement holds for $N-1$. It suffices to prove for $\sigma\in S_{N}$
represented by $T_{1},\dots,T_{N-1}$ in which $T_{1}$ appears exactly once by
Lemma 2.2. If $T_{1}$ does not appear in the representation of $\sigma$, then
$\sigma(1)=1$ and $\sigma$ is uniquely written $\sigma=w_{N-1}\cdots w_{2}$ by
the induction hypothesis for $N-1$ because the set of all permutations on
$\\{1,\dots,N-1\\}$ is isomorphic to the set of all permutations on
$\\{2,\dots,N\\}$. Let $\sigma=\sigma^{\prime}T_{1}\sigma^{\prime\prime}$
where $\sigma^{\prime}$ and $\sigma^{\prime\prime}$ are words consisting of
$T_{2},\dots,T_{N-1}$. By the induction hypothesis, there exist
$w^{\prime\prime}_{i}\in\Gamma_{i},~{}i=2,\dots,N-1$ such that
$\sigma^{\prime\prime}$ is uniquely written as
$\sigma^{\prime\prime}=w^{\prime\prime}_{N-1}\cdots w^{\prime\prime}_{2}$ so
that $\sigma=\sigma^{\prime}T_{1}w^{\prime\prime}_{N-1}\cdots
w^{\prime\prime}_{2}$. By (1.8), $T_{1}$ commutes with
$w^{\prime\prime}_{3},\dots,w^{\prime\prime}_{N-1}$, so

$\displaystyle\sigma=\sigma^{\prime}w^{\prime\prime}_{N-1}\cdots
w^{\prime\prime}_{3}T_{1}w^{\prime\prime}_{2}.$

Since $\sigma^{\prime}w^{\prime\prime}_{N-1}\cdots w^{\prime\prime}_{3}$ is a
word consisting of $T_{2},\dots,T_{N-1}$, it may be written uniquely as
$w^{\prime}_{N-1}\cdots w^{\prime}_{2}$ for some
$w^{\prime}_{i}\in\Gamma_{i}$, $i=2,\dots,N-1$ by the induction hypothesis. It
is clear that $T_{1}w^{\prime\prime}_{2}\in\Gamma_{1}$. ∎

######  Corollary 2.7.

Let $\sigma=w_{N-1}\cdots w_{1}$ be an expression as in Proposition 2.6 and
let $\mathbf{A}_{\sigma}$ be the matrix corresponding to $\sigma$. Then, for
all $N\geq 2$,

  * $(a)$

$[{\mathbf{A}}_{12\cdots N}]_{21\cdots 1,21\cdots 1}=1$ and
$[{\mathbf{A}}_{12\cdots N}]_{\pi,21\cdots 1}=0$ if $\pi\neq 21\cdots 1$.

  * $(b)$

If $\sigma\neq 12\cdots N$, then $[{\mathbf{A}}_{\sigma}]_{\pi,21\cdots 1}$ is
zero or written as

$\displaystyle[{\mathbf{A}}_{\sigma}]_{\pi,21\cdots
1}=\prod_{(\beta,\alpha)}R_{\beta\alpha},$ (2.6)

where $R_{\beta\alpha}$ is one of $S_{\beta\alpha}$, $P_{\beta\alpha}$,
$Q_{\beta\alpha}$, $pT_{\beta\alpha}$, $qT_{\beta\alpha}$ and the product in
(2.6) is taken over all inversions $(\beta,\alpha)$ in $\sigma$.

######  Remark 2.8.

Let $\mathcal{N}_{N}$ be the multi-set $[\underbrace{1,\dots,1}_{N-1},2]$.
Then, we observe that

$\displaystyle{\mathbf{T}}_{l}^{\mathcal{N}_{N}}(\beta,\alpha)=(S_{\beta\alpha}\mathbf{I}_{N-l-1})\oplus\left[\begin{matrix}P_{\beta\alpha}&pT_{\beta\alpha}\\\
qT_{\beta\alpha}&Q_{\beta\alpha}\\\
\end{matrix}\right]\oplus(S_{\beta\alpha}\mathbf{I}_{l-1}),\qquad
l=1,\dots,N-1,$ (2.7)

and
$\mathbf{T}_{l}^{\mathcal{N}_{N}}(\beta,\alpha)=\mathbf{T}_{N-l}^{\mathcal{M}_{N}}(\beta,\alpha)$.
Using these properties, Corollary 2.7 can be proved essentially in the same
way as the proof Theorem 1.2.

Simplified forms of $[\mathbf{A}_{\sigma}]_{\pi,1\cdots 12}$ are obtained via
the following method of expressing $\sigma$.

######  Proposition 2.9.

Consider the following subsets of the symmetric group $S_{N}$:

$\displaystyle\begin{aligned}
&\Xi_{N-1}=\\{1,T_{N-1},T_{N-2}T_{N-1},\dots,T_{1}\cdots T_{N-1}\\},\\\
&\Xi_{N-2}=\\{1,T_{N-2},T_{N-3}T_{N-2},\dots,T_{1}\cdots T_{N-2}\\},\\\
&\hskip 8.5359pt\vdots\\\ &\Xi_{2}=\\{1,T_{2},T_{1}T_{2}\\},\\\
&\Xi_{1}=\\{1,T_{1}\\}.\end{aligned}$

For any permutation $\sigma\in S_{N}$, there is a unique element

$\displaystyle(w_{N-1},\dots,w_{1})\in\Xi_{N-1}\times\cdots\times\Xi_{1}$

such that $\sigma=w_{N-1}\cdots w_{1}$.

###### Proof.

We prove this by induction on $N$. The statement is obvious for $N=2$. Suppose
that the statement holds for $N-1$. It suffices to prove for $\sigma\in S_{N}$
represented by $T_{1},\dots,T_{N-1}$ in which $T_{N-1}$ appears exactly once
by [4, Lemma 4.2]. If $T_{N-1}$ does not appear in the representation of
$\sigma$, then $\sigma(N)=N$ and $\sigma$ is uniquely written
$\sigma=w_{N-2}\cdots w_{1}$ by the induction hypothesis for $N-1$. Let
$\sigma=\sigma^{\prime}T_{N-1}\sigma^{\prime\prime}$ where $\sigma^{\prime}$
and $\sigma^{\prime\prime}$ are words consisting of $T_{1},\dots,T_{N-2}$. By
the induction hypothesis, there exist
$w^{\prime}_{i}\in\Xi_{i},~{}i=1,\dots,N-2$ such that $\sigma^{\prime}$ is
uniquely written as $\sigma^{\prime}=w^{\prime}_{N-2}\cdots w^{\prime}_{1}$ so
that $\sigma=w^{\prime}_{N-2}\cdots
w^{\prime}_{1}T_{N-1}\sigma^{\prime\prime}$. By (1.8), $T_{N-1}$ commutes with
$w^{\prime}_{1},\dots,w^{\prime}_{N-3}$, so

$\displaystyle\sigma=w^{\prime}_{N-2}T_{N-1}w^{\prime}_{N-3}\cdots
w^{\prime}_{1}\sigma^{\prime\prime}.$

Since $w^{\prime}_{N-3}\cdots w^{\prime}_{1}\sigma^{\prime\prime}$ is a word
consisting of $T_{1},\dots,T_{N-2}$, it may be written as
$w^{\prime\prime}_{N-2}\cdots w^{\prime\prime}_{1}$ for some
$w^{\prime\prime}_{i}\in\Xi_{i}$ by the induction hypothesis. It is clear that
$w^{\prime}_{N-2}T_{N-1}\in\Xi_{N-1}$. ∎

######  Corollary 2.10.

Let $\sigma=w_{N-1}\cdots w_{1}$ be an expressed as in Proposition 2.9 and let
$\mathbf{A}_{\sigma}$ be the matrix corresponding to $\sigma$. Then, for all
$N\geq 2$,

  * $(a)$

$\big{[}{\mathbf{A}}_{12\cdots N}\big{]}_{1\cdots 12,1\cdots 12}=1$ and
$\big{[}{\mathbf{A}}_{12\cdots N}\big{]}_{\pi,1\cdots 12}=0$ if $\pi\neq
1\cdots 12$.

  * $(b)$

If $\sigma\neq 12\cdots N$, then
$\big{[}{\mathbf{A}}_{\sigma}\big{]}_{\pi,1\cdots 12}$ is zero or written as

$\displaystyle\big{[}{\mathbf{A}}_{\sigma}\big{]}_{\pi,1\cdots
12}=\prod_{(\beta,\alpha)}R_{\beta\alpha}$ (2.8)

where $R_{\beta\alpha}$ is one of $S_{\beta\alpha}$, $P_{\beta\alpha}$,
$Q_{\beta\alpha}$, $pT_{\beta\alpha}$, $qT_{\beta\alpha}$ and the product in
(2.8) is taken over all inversions $(\beta,\alpha)$ in $\sigma$.

######  Remark 2.11.

Corollary 2.10 can be proved essentially in the same way as the proof Theorem
2.5 by using
$\mathbf{T}_{l}^{\mathcal{N}_{N}}(\beta,\alpha)=\mathbf{T}_{N-l}^{\mathcal{M}_{N}}(\beta,\alpha)$.

##  3 Simplified forms of $\boldsymbol{[\mathbf{A}_{\sigma}]_{\pi,\nu}}$

In the previous section, we discussed the existence of the factorized forms of
$[\mathbf{A}_{\sigma}]_{\pi,\nu}$. In this section, we provide the explicit
forms of $[\mathbf{A}_{\sigma}]_{\pi,\nu}$.

######  Remark 3.1.

In this section, sometimes, we will simply write any $N\times N$ sub-matrix
$\mathbf{A}^{\mathcal{M}_{N}}$ of $\mathbf{A}$ as just $\mathbf{A}$ for
notational convenience. Also, recall that we interchangeably use the notations
$[\mathbf{A}]_{i,j}$ where $i,j=1,\dots,N$ and $[\mathbf{A}]_{\pi,\nu}$ where
$\pi$ and $\nu$ are permutations of a multi-set. For example,
$[\mathbf{A}]_{1,N}=[\mathbf{A}]_{12\cdots 2,2\cdots 21}$.

###  3.1 $\boldsymbol{[\mathbf{A}_{\sigma}]_{\nu,\nu}}$

Theorem 1.4 states that $[\mathbf{A}_{\sigma}]_{2\cdots 21,2\cdots 21}$ is
nonzero for each $\sigma$ and expressed as a product over all inversions in
$\sigma$.

###### Proof of Theorem 1.4.

First, recall that $T_{N-1}$ appears at most once in any expression of
$\sigma$ given by Theorem 1.1. Suppose that $i_{m}=N-1$ for some integer
$1\leq m\leq j$ so that

$\displaystyle{T}_{i_{m}}(\beta_{m},\alpha_{m})\cdots{T}_{i_{1}}(\beta_{1},\alpha_{1})={T}_{N-1}(\beta_{m},\alpha_{m})\cdots{T}_{N-m}(\beta_{1},\alpha_{1})=w_{N-1}\in\Sigma_{N-1}.$

By Lemma 2.1 and recalling the form of (2.2),

$\displaystyle[\mathbf{T}_{i_{m}}(\beta_{m},\alpha_{m})\cdots\mathbf{T}_{i_{1}}(\beta_{1},\alpha_{1})]_{N,N}$
$\displaystyle=Q_{\beta_{m}\alpha_{m}}S_{\beta_{m-1}\alpha_{m-1}}\cdots
S_{\beta_{1}\alpha_{1}}$
$\displaystyle=[\mathbf{T}_{N-1}(\beta_{m},\alpha_{m})]_{N,N}\cdots[\mathbf{T}_{N-m}(\beta_{1},\alpha_{1})]_{N,N}.$

Since $\mathbf{T}_{i_{j}},\dots,\mathbf{T}_{i_{m+1}}$ are not from $w_{N-1}$,
the integers $i_{j},\dots,i_{m+1}$ are not equal to $N-1$. Hence, each of
$\mathbf{T}_{i_{j}},\dots,\mathbf{T}_{i_{m+1}}$ is in the form of
$\mathbf{G}_{N-1}\oplus S_{\beta\alpha}$ where $\mathbf{G}_{N-1}$ is an
$(N-1)\times(N-1)$ matrix (recall the form of (2.2)). Hence,

$\displaystyle[\mathbf{T}_{i_{j}}\cdots\mathbf{T}_{i_{m+1}}]_{N,N}=[\mathbf{T}_{i_{j}}]_{N,N}\cdots[\mathbf{T}_{i_{m+1}}]_{N,N}=S_{\beta_{j}\alpha_{j}}\cdots
S_{\beta_{m+1}\alpha_{m+1}}$

and

$\displaystyle[\mathbf{A}_{\sigma}]_{N,N}=\big{[}\mathbf{T}_{i_{j}}\cdots\mathbf{T}_{i_{1}}\big{]}_{N,N}=S_{\beta_{j}\alpha_{j}}\cdots
S_{\beta_{m+1}\alpha_{m+1}}Q_{\beta_{m}\alpha_{m}}S_{\beta_{m-1}\alpha_{m-1}}\cdots
S_{\beta_{1}\alpha_{1}}.$

If $i_{1},\dots,i_{j}\neq N-1$, then each of
$\mathbf{T}_{i_{j}},\dots,\mathbf{T}_{i_{1}}$ is in the form of
$\mathbf{G}_{N-1}\oplus S_{\beta\alpha}$. Hence,

$\displaystyle[\mathbf{A}_{\sigma}]_{N,N}=[\mathbf{T}_{i_{j}}\cdots\mathbf{T}_{i_{1}}]_{N,N}=S_{\beta_{j}\alpha_{j}}\cdots
S_{\beta_{1}\alpha_{1}}.$ ∎

The formulas for other cases of $\nu$ that are considered in this paper can be
similarly obtained by using the same techniques, so we provide their formulas
without proofs.

######  Proposition 3.2.

Let $\nu=12\cdots 2$ and

$\displaystyle\sigma=w_{N-1}\cdots
w_{1}={T}_{i_{j}}(\beta_{j},\alpha_{j})\cdots{T}_{i_{1}}(\beta_{1},\alpha_{1})$

be given as in Proposition 2.3. Let

$\displaystyle\mathbf{A}_{\sigma}=\mathbf{T}_{i_{j}}(\beta_{j},\alpha_{j})\cdots\mathbf{T}_{i_{1}}(\beta_{1},\alpha_{1})$

be the matrix corresponding to $\sigma$. Then,

$\displaystyle[\mathbf{A}_{\sigma}]_{\nu,\nu}$
$\displaystyle=[\mathbf{T}_{i_{j}}]_{\nu,\nu}\cdots[\mathbf{T}_{i_{m}}]_{\nu,\nu}\cdots[\mathbf{T}_{i_{1}}]_{\nu,\nu}$
$\displaystyle=\begin{cases}S_{\beta_{j}\alpha_{j}}\cdots
S_{\beta_{m+1}\alpha_{m+1}}P_{\beta_{m}\alpha_{m}}S_{\beta_{m-1}\alpha_{m-1}}\cdots
S_{\beta_{1}\alpha_{1}}&\text{if~{}$i_{m}=1$},\\\
S_{\beta_{j}\alpha_{j}}\cdots
S_{\beta_{1}\alpha_{1}}&\text{if~{}$i_{i},\dots,i_{j}\neq 1$}.\end{cases}$

$($Note that $T_{1}$ appears at most once in any expression of $\sigma$ in
Proposition 2.3.$)$

######  Proposition 3.3.

Let $\nu=21\cdots 1$ and

$\displaystyle\sigma=w_{N-1}\cdots
w_{1}={T}_{i_{j}}(\beta_{j},\alpha_{j})\cdots{T}_{i_{1}}(\beta_{1},\alpha_{1})$

be given as in Proposition 2.6. Let

$\displaystyle\mathbf{A}_{\sigma}=\mathbf{T}_{i_{j}}(\beta_{j},\alpha_{j})\cdots\mathbf{T}_{i_{1}}(\beta_{1},\alpha_{1})$

be the matrix corresponding to $\sigma$. Then,

$\displaystyle[\mathbf{A}_{\sigma}]_{\nu,\nu}$
$\displaystyle=[\mathbf{T}_{i_{j}}]_{\nu,\nu}\cdots[\mathbf{T}_{i_{m}}]_{\nu,\nu}\cdots[\mathbf{T}_{i_{1}}]_{\nu,\nu}$
$\displaystyle=\begin{cases}S_{\beta_{j}\alpha_{j}}\cdots
S_{\beta_{m+1}\alpha_{m+1}}Q_{\beta_{m}\alpha_{m}}S_{\beta_{m-1}\alpha_{m-1}}\cdots
S_{\beta_{1}\alpha_{1}}&\text{if~{}$i_{m}=1$},\\\
S_{\beta_{j}\alpha_{j}}\cdots
S_{\beta_{1}\alpha_{1}}&\text{if~{}$i_{i},\dots,i_{j}\neq 1$}.\end{cases}$

$($Note that $T_{1}$ appears at most once in any expression of $\sigma$ in
Proposition 2.6.$)$

######  Proposition 3.4.

Let $\nu=1\cdots 12$ and

$\displaystyle\sigma=w_{N-1}\cdots
w_{1}={T}_{i_{j}}(\beta_{j},\alpha_{j})\cdots{T}_{i_{1}}(\beta_{1},\alpha_{1})$

be given as in Proposition 2.9. Let

$\displaystyle\mathbf{A}_{\sigma}=\mathbf{T}_{i_{j}}(\beta_{j},\alpha_{j})\cdots\mathbf{T}_{i_{1}}(\beta_{1},\alpha_{1})$

be the matrix corresponding to $\sigma$. Then,

$\displaystyle[\mathbf{A}_{\sigma}]_{\nu,\nu}$
$\displaystyle=[\mathbf{T}_{i_{j}}]_{\nu,\nu}\cdots[\mathbf{T}_{i_{m}}]_{\nu,\nu}\cdots[\mathbf{T}_{i_{1}}]_{\nu,\nu}$
$\displaystyle=\begin{cases}S_{\beta_{j}\alpha_{j}}\cdots
S_{\beta_{m+1}\alpha_{m+1}}P_{\beta_{m}\alpha_{m}}S_{\beta_{m-1}\alpha_{m-1}}\cdots
S_{\beta_{1}\alpha_{1}}&\text{if~{}$i_{m}=N-1$},\\\
S_{\beta_{j}\alpha_{j}}\cdots
S_{\beta_{1}\alpha_{1}}&\text{if~{}$i_{i},\dots,i_{j}\neq 1$}.\end{cases}$

$($Note that $T_{N-1}$ appears at most once in any expression of $\sigma$ in
Proposition 2.9.$)$

###  3.2 Case $\boldsymbol{[\mathbf{A}_{\sigma}]_{\pi,\nu}=0}$ where
$\boldsymbol{\pi\neq\nu=2\cdots 21}$

If $\pi\neq\nu=2\cdots 21$, then $[\mathbf{A}_{\sigma}]_{\pi,\nu}$ where
$\pi\neq\nu$ is either zero or a product of some factors where the product is
taken over all inversions in $\sigma$. First, let us investigate when it can
be zero. Let $\sigma=w_{1}\cdots w_{N-1}$ be expressed as in Theorem 1.1 and
let

$\displaystyle\mathbf{w}_{m}=\mathbf{T}_{m}(\beta_{m},\alpha_{m})\mathbf{T}_{m-1}(\beta_{m-1},\alpha_{m-1})\cdots\mathbf{T}_{l}(\beta_{l},\alpha_{l})$

if $w_{m}=T_{m}(\beta_{m},\alpha_{m})T_{m-1}(\beta_{m-1},\alpha_{m-1})\cdots
T_{l}(\beta_{l},\alpha_{l})$, and let $\mathbf{w}_{m}$ be the identity matrix
if $w_{m}=1$. Recalling the form of the matrix in (2.2), we see that
$\mathbf{w}_{m}$ is in the form of $\mathbf{G}_{m+1}\oplus\mathbf{D}_{N-m-1}$
where $\mathbf{G}_{m+1}$ is an $(m+1)\times(m+1)$ matrix and
$\mathbf{D}_{N-m-1}$ is an $(N-m-1)\times(N-m-1)$ diagonal matrix. An
immediate consequence of Lemma 2.1 is as follows:

######  Lemma 3.5.

The $(m+1)^{{\rm st}}$ column of $\mathbf{w}_{m}\neq 1$ is given by

$\displaystyle[\mathbf{w}_{m}]_{i,m+1}=\begin{cases}0&\text{if $1\leq i\leq
m-1$},\\\ \displaystyle
pT_{\beta_{m}\alpha_{m}}\prod_{k=1}^{m-l}S_{\beta_{m-k}\alpha_{m-k}}&\text{if
$i=m$},\\\ \displaystyle
Q_{\beta_{m}\alpha_{m}}\prod_{k=1}^{m-l}S_{\beta_{m-k}\alpha_{m-k}}&\text{if
$i=m+1$},\\\ 0&\text{if $m+2\leq i\leq N$}.\end{cases}$

Since we are interested in the last column of $\mathbf{A}_{\sigma}$, that is,
$[\mathbf{w}_{1}\cdots\mathbf{w}_{N-1}]_{i,N}$, we separate
$\mathbf{w}_{1}\cdots\mathbf{w}_{N-1}$ into two parts
$(\mathbf{w}_{1}\cdots)(\cdots\mathbf{w}_{N-1})$ and consider the last column
of the second part. The following result tells that the last column of the
second part is in the form of

$\displaystyle\left[\begin{matrix}0\\\ \vdots\\\ 0\\\ *\\\ \vdots\\\
*\end{matrix}\right].$

######  Lemma 3.6.

Suppose that $\mathbf{w}_{N-k},\dots,\mathbf{w}_{N-1}\neq 1$ for some $1\leq
k\leq N-2$. Then,

$\displaystyle\big{[}\mathbf{w}_{N-k}\cdots\mathbf{w}_{N-1}\big{]}_{i,N}=0$

for all $1\leq i\leq N-k-1$, and
$\big{[}\mathbf{w}_{N-k}\cdots\mathbf{w}_{N-1}\big{]}_{i,N}\neq 0$ for
$N-k\leq i\leq N$.

###### Proof.

If $k=1$, the statement is the same as Lemma 2.1. Let $2\leq k\leq N-2$.
Noting that $\mathbf{w}_{N-2}$ is in the form of $\mathbf{G}_{N-1}\oplus S$
where $\mathbf{G}_{N-1}$ is an $(N-1)\times(N-1)$ matrix and $S$ is a nonzero
scalar, and applying Lemma 2.1 to $\mathbf{G}_{N-1}$, we obtain
$\big{[}\mathbf{w}_{N-2}\big{]}_{i,N-1}=0$ for all $i\neq N-1,N-2$, and
$[\mathbf{w}_{N-2}]_{i,N}=0$ for all $i\neq N$. Hence, computing
$\mathbf{w}_{N-2}\mathbf{w}_{N-1}$ directly, we obtain

$\displaystyle[\mathbf{w}_{N-2}\mathbf{w}_{N-1}]_{i,N}=0$

for $1\leq i\leq N-3$ and $[\mathbf{w}_{N-2}\mathbf{w}_{N-1}]_{i,N}\neq 0$ for
$i=N-2,N-1,N$. Repeating this procedure, we obtain the required result. ∎

Now, we prove Theorem 1.6. Recall that we use the convention about sub-
matrices introduced in the beginning of this section.

###### Proof of Theorem 1.6.

Let $l$ be the largest integer such that $\mathbf{w}_{l}=1$ and

$\displaystyle\mathbf{A}_{\sigma}=\mathbf{w}_{1}\cdots\mathbf{w}_{l-1}\mathbf{w}_{l+1}\cdots\mathbf{w}_{N-1}.$

By Lemma 3.6, $[\mathbf{w}_{l+1}\cdots\mathbf{w}_{N-1}]_{i,N}=0$ for $1\leq
i\leq l$ and $\big{[}\mathbf{w}_{l+1}\cdots\mathbf{w}_{N-1}\big{]}_{i,N}\neq
0$ for $l+1\leq i\leq N$. Recalling the form of the matrix in (2.2), we see
that all matrices $\mathbf{w}_{1},\dots,\mathbf{w}_{l-1}$ are in the form of
$\mathbf{G}_{l}\oplus\mathbf{D}_{N-l}$ where $\mathbf{G}_{l}$ is a $l\times l$
matrix and $\mathbf{D}_{N-l}$ is an $(N-l)\times(N-l)$ diagonal matrix with
some nonzero diagonal entries. Hence,
$[(\mathbf{w}_{1}\cdots\mathbf{w}_{l-1})(\mathbf{w}_{l+1}\cdots\mathbf{w}_{N-1})]_{i,N}$
is zero for $1\leq i\leq l$ and nonzero for $l+1\leq i\leq N$. Now, suppose
that $w_{i}\neq 1$ for all $i$ so that
$\mathbf{A}_{\sigma}=\mathbf{w}_{1}\cdots\mathbf{w}_{N-1}$. By Lemma 3.6,
$[\mathbf{w}_{2}\cdots\mathbf{w}_{N-1}]_{1,N}$ is zero and
$[\mathbf{w}_{2}\cdots\mathbf{w}_{N-1}]_{i,N}\neq 0$ for all $i\neq 1$, and we
note that

$\displaystyle\mathbf{w}_{1}=\mathbf{T}_{1}(\beta,\alpha)=\left[\begin{matrix}P_{\beta\alpha}&pT_{\beta\alpha}\\\
qT_{\beta\alpha}&Q_{\beta\alpha}\end{matrix}\right]\oplus\mathbf{D}_{N-2}$

for some $(\beta,\alpha)$. Hence,
$\big{[}\mathbf{w}_{1}\cdots\mathbf{w}_{N-1}\big{]}_{i,N}\neq 0$ for all $i$.
∎

###  3.3 Case $\boldsymbol{[\mathbf{A}_{\sigma}]_{\pi,\nu}\neq 0}$ where
$\boldsymbol{\pi\neq\nu=2\cdots 21}$

Lemma 3.6 stated that $[\mathbf{w}_{l+1}\cdots\mathbf{w}_{N-1}]_{i,N}=0$ for
$i=1,\dots,l$ and $[\mathbf{w}_{l+1}\cdots\mathbf{w}_{N-1}]_{i,N}\neq 0$ for
$i=l+1,\dots,N$. Now, we give the formulas for these nonzero terms.

######  Theorem 3.7.

Let $\sigma=w_{l+1}\cdots w_{N-1}$ be expressed as in Theorem 1.1 with
$w_{l+1},\dots,w_{N-1}\neq 1$, and let

$\displaystyle\mathbf{A}_{\sigma}=\mathbf{w}_{l+1}\cdots\mathbf{w}_{N-1}$

be the matrix corresponding to $\sigma$. Then,

$\displaystyle[\mathbf{A}_{\sigma}]_{i,N}=\prod_{k=l+1}^{i-1}[\mathbf{w}_{k}]_{i,i}\prod_{k=i}^{N-1}[\mathbf{w}_{k}]_{k,k+1}$
(3.1)

for $i=l+1,\dots,N-1$.

###### Proof.

We prove by induction on $N$. When $N=2$, the statement obviously holds.
Suppose that the statement holds for $N$, that is, for the multi-set
$[1,\underbrace{2,\dots,2}_{N-1}]$. We will show that the statement is true
for $N+1$, that is, for the multi-set $[1,\underbrace{2,\dots,2}_{N}]$. Let
$\sigma^{\prime}=w^{\prime}_{l+1}\cdots w^{\prime}_{N}$ be given as in Theorem
1.1 with $S_{N+1}$. If $T_{i}$ is a simple transposition in $S_{N}$ and
$T^{\prime}_{i}$ is a simple transposition in $S_{N+1}$, then
$\mathbf{T}_{i}(\beta,\alpha)\oplus
S_{\beta\alpha}=\mathbf{T}^{\prime}_{i}(\beta,\alpha)$ for $i=1,\dots,N-1$.
Hence, $\mathbf{w}_{i}\oplus{\mathcal{S}}_{i}=\mathbf{w}^{\prime}_{i}$ for
$i=1,\dots,N-1$ for some scalar ${\mathcal{S}}_{i}$, and so

$\displaystyle\mathbf{A}_{\sigma^{\prime}}$
$\displaystyle=\mathbf{w}^{\prime}_{l+1}\cdots\mathbf{w}^{\prime}_{N}=\mathbf{w}^{\prime}_{l+1}\cdots\mathbf{w}^{\prime}_{N-1}\mathbf{w}^{\prime}_{N}$
$\displaystyle=\big{(}(\mathbf{w}_{l+1}\cdots\mathbf{w}_{N-1})\oplus({\mathcal{S}}_{l+1}\cdots{\mathcal{S}}_{N-1})\big{)}\mathbf{w}^{\prime}_{N},\qquad
l+1\leq N-1.$

Also, note that if $1\leq m,n\leq N$, then

$\displaystyle[\mathbf{w}_{i}\oplus{\mathcal{S}}_{i}]_{m,n}=[\mathbf{w}_{i}]_{m,n}=[\mathbf{w}^{\prime}_{i}]_{m,n},\qquad
i=1,\dots,N-1,$

and $[\mathbf{w}^{\prime}_{N}]_{i,N+1}=0$ for all $1\leq i\leq N-1$ by Lemma
3.5. Hence, for $i=1,\dots,N-1$,

$\displaystyle[\mathbf{A}_{\sigma^{\prime}}]_{i,N+1}$
$\displaystyle=\sum_{k=1}^{N+1}\big{(}(\mathbf{w}_{l+1}\cdots\mathbf{w}_{N-1})\oplus({\mathcal{S}}_{l+1}\cdots{\mathcal{S}}_{N-1})\big{)}_{i,k}[\mathbf{w}^{\prime}_{N}]_{k,N+1}$
$\displaystyle=\big{(}(\mathbf{w}_{l+1}\cdots\mathbf{w}_{N-1})\oplus({\mathcal{S}}_{l+1}\cdots{\mathcal{S}}_{N-1})\big{)}_{i,N}[\mathbf{w}^{\prime}_{N}]_{N,N+1}$
$\displaystyle=(\mathbf{w}_{l+1}\cdots\mathbf{w}_{N-1})_{i,N}[\mathbf{w}^{\prime}_{N}]_{N,N+1}.$

By the induction hypothesis,

$\displaystyle[\mathbf{w}_{l+1}\cdots\mathbf{w}_{N-1}]_{i,N}[\mathbf{w}^{\prime}_{N}]_{N,N+1}$
$\displaystyle=\Bigg{(}\prod_{k=l+1}^{i-1}[\mathbf{w}_{k}]_{i,i}\prod_{k=i}^{N-1}[\mathbf{w}_{k}]_{k,k+1}\Bigg{)}[\mathbf{w}^{\prime}_{N}]_{N,N+1}$
$\displaystyle=\Bigg{(}\prod_{k=l+1}^{i-1}[\mathbf{w}^{\prime}_{k}]_{i,i}\prod_{k=i}^{N-1}[\mathbf{w}^{\prime}_{k}]_{k,k+1}\Bigg{)}[\mathbf{w}^{\prime}_{N}]_{N,N+1}$
$\displaystyle=\prod_{k=l+1}^{i-1}[\mathbf{w}^{\prime}_{k}]_{i,i}\prod_{k=i}^{N}[\mathbf{w}^{\prime}_{k}]_{k,k+1}.$

for $i=l+1,\dots,N-1$. Hence, we obtained

$\displaystyle[\mathbf{A}_{\sigma^{\prime}}]_{i,N+1}=\prod_{k=l+1}^{i-1}[\mathbf{w}^{\prime}_{k}]_{i,i}\prod_{k=i}^{N}[\mathbf{w}^{\prime}_{k}]_{k,k+1}$

for $i=l+1,\dots,N-1$. If $i=N$, then using that
$\mathbf{w^{\prime}}_{l+1}\cdots\mathbf{w^{\prime}}_{N-1}=\mathbf{w}_{l+1}\cdots\mathbf{w}_{N-1}\oplus{\mathcal{S}}$
for some scalar ${\mathcal{S}}$, Theorem 1.4, Lemmas 3.5 and 3.6, we obtain

$\displaystyle[\mathbf{A}_{\sigma^{\prime}}]_{N,N+1}$
$\displaystyle=\sum_{k=1}^{N+1}[\mathbf{w^{\prime}}_{l+1}\cdots\mathbf{w^{\prime}}_{N-1}]_{N,k}[\mathbf{w}^{\prime}_{N}]_{k,N+1}$
$\displaystyle=[\mathbf{w^{\prime}}_{l+1}\cdots\mathbf{w^{\prime}}_{N-1}]_{N,N}[\mathbf{w}^{\prime}_{N}]_{N,N+1}=[\mathbf{w}_{l+1}\cdots\mathbf{w}_{N-1}]_{N,N}[\mathbf{w}^{\prime}_{N}]_{N,N+1}$
$\displaystyle=\Bigg{(}\prod_{k=l+1}^{N-1}[\mathbf{w}_{k}]_{N,N}\Bigg{)}[\mathbf{w}^{\prime}_{N}]_{N,N+1}=\Bigg{(}\prod_{k=l+1}^{N-1}[\mathbf{w}^{\prime}_{k}]_{N,N}\Bigg{)}[\mathbf{w}^{\prime}_{N}]_{N,N+1}.$
∎

Theorem 1.4, Theorem 3.7 and the convention on the product introduced in
Section 1.2.2 imply that (3.1) actually holds for $i=N$.

######  Corollary 3.8.

Let $\sigma=w_{l+1}\cdots w_{N-1}$ be expressed as in Theorem 1.1 with
$w_{l+1},\dots,w_{N-1}\neq 1$, and let

$\mathbf{A}_{\sigma}=\mathbf{w}_{l+1}\cdots\mathbf{w}_{N-1}$

be the matrix corresponding to $\sigma$. Then,

$\displaystyle[\mathbf{A}_{\sigma}]_{i,N}=\prod_{k=l+1}^{i-1}[\mathbf{w}_{k}]_{i,i}\prod_{k=i}^{N-1}[\mathbf{w}_{k}]_{k,k+1}$

for $i=l+1,\dots,N$.

The proof of Theorem 1.7 is based on Corollary 3.8.

###### Proof of Theorem 1.7.

Let $l$ be the largest integer such that $w_{l}=1$ and

$\displaystyle\mathbf{A}_{\sigma}=\big{(}\mathbf{w}_{1}\cdots\mathbf{w}_{l-1}\big{)}\big{(}\mathbf{w}_{l+1}\cdots\mathbf{w}_{N-1}\big{)}.$

Then,

$\displaystyle\big{[}\mathbf{w}_{l+1}\cdots\mathbf{w}_{N-1}\big{]}_{N,N}=\big{[}\mathbf{w}_{l+1}\big{]}_{N,N}\cdots\big{[}\mathbf{w}_{N-1}\big{]}_{N,N}$

by Theorem 1.4, and

$\displaystyle[\mathbf{w}_{l+1}\cdots\mathbf{w}_{N-1}]_{i,N}=\prod_{k=l+1}^{i-1}[\mathbf{w}_{k}]_{i,i}\prod_{k=i}^{N-1}[\mathbf{w}_{k}]_{k,k+1}$

for $i=l+1,\dots,N$ by Corollary 3.8, and

$\displaystyle[\mathbf{w}_{l+1}\cdots\mathbf{w}_{N-1}]_{i,N}=0$

for $i=1,\dots,l$ by Theorem 1.6. Note that each $\mathbf{w}_{i}$ for
$i=1,\dots,l-1$ is written as $\mathbf{G}_{l}\oplus\mathbf{D}_{N-l}$ for some
$l\times l$ matrix $\mathbf{G}_{l}$ and $(N-l)\times(N-l)$ diagonal matrix
$\mathbf{D}_{N-l}$. Hence, $(\mathbf{w}_{1}\cdots\mathbf{w}_{l-1})$ is also in
the same form as $\mathbf{G}_{l}\oplus\mathbf{D}_{N-l}$ and

$\displaystyle[\mathbf{w}_{1}\cdots\mathbf{w}_{l-1}]_{i,i}=[\mathbf{w}_{1}]_{i,i}\cdots[\mathbf{w}_{l-1}]_{i,i}$

for $i=l+1,\dots,N$. Therefore, for $i=l+1,\dots,N$, noting that
$[\mathbf{w}_{l}]_{i,i}=1$,

$\displaystyle[\mathbf{A}_{\sigma}]_{i,N}$
$\displaystyle=\sum_{k=1}^{N}[\mathbf{w}_{1}\cdots\mathbf{w}_{l-1}]_{i,k}[\mathbf{w}_{l+1}\cdots\mathbf{w}_{N-1}]_{k,N}=[\mathbf{w}_{1}\cdots\mathbf{w}_{l-1}]_{i,i}[\mathbf{w}_{l+1}\cdots\mathbf{w}_{N-1}]_{i,N}$
$\displaystyle=[\mathbf{w}_{1}]_{i,i}\cdots[\mathbf{w}_{l-1}]_{i,i}\prod_{k=l+1}^{i-1}[\mathbf{w}_{k}]_{i,i}\prod_{k=i}^{N-1}[\mathbf{w}_{k}]_{k,k+1}=\prod_{k=1}^{i-1}[\mathbf{w}_{k}]_{i,i}\prod_{k=i}^{N-1}[\mathbf{w}_{k}]_{k,k+1}.$

If $i\leq l$, then $[\mathbf{A}_{\sigma}]_{i,N}$ must be zero by Theorem 1.6.
If $i\leq l$, then there exists a factor $[\mathbf{w}_{l}]_{l,l+1}$ in (1.11)
but $[\mathbf{w}_{l}]_{l,l+1}=0$ because $\mathbf{w}_{l}$ is the identity
matrix. Hence, (1.11) holds for all $i=1,\dots,N$. Finally, if there is no
integer $l$ with $w_{l}=1$, we just set $l=0$ in Theorem 3.7 to complete the
proof. ∎

The explicit formulas of $[\mathbf{w}_{k}]_{i,i}$ and
$[\mathbf{w}_{k}]_{k,k+1}$ in (1.11) and in (3.1) are provided in Proposition
1.8.

###### Proof of Proposition 1.8.

Recalling the form of the matrix in (2.2), we can easily obtain (1.12) and
(1.13) by directly performing matrix multiplication in

$\displaystyle\mathbf{w}_{k}=\mathbf{T}_{k}(\beta_{k_{1}},\alpha_{k_{1}})\mathbf{T}_{k-1}(\beta_{k_{2}},\alpha_{k_{2}})\cdots\mathbf{T}_{k-l+1}(\beta_{k_{l}},\alpha_{k_{l}}).$
∎

##  Appendix A Alternate approach

###  A.1 Physical interpretation

We give a physical interpretation for the formulas given in this paper and
provide an alternate approach to find $[\mathbf{A}_{\sigma}]_{\pi,\nu}$. The
cardinality of the set of all permutations of the multi-set
$\mathcal{M}_{N}=[1,2,\dots,2]$ or $\mathcal{N}_{N}=[1,\dots,1,2]$ is $N$. Let
$F$ be the function field of all rational functions of $N$ variables
$\xi_{1},\dots,\xi_{N}\in\mathbb{C}$ over $\mathbb{C}$. Let us consider the
vector space $F^{N}$ over the field $F$ on which a bilinear form
$\langle\cdot\,|\,\mathbf{A}\,|\,\cdot\rangle\colon F^{N}\times F^{N}\to F$ is
defined by

$\displaystyle\langle(f_{1},\dots,f_{N})\,|\,\mathbf{A}\,|\,(g_{1},\dots,g_{N})\rangle=(f_{1},\dots,f_{N})\mathbf{A}(g_{1},\dots,g_{N})^{t}$

for any $N\times N$ matrix $\mathbf{A}$ of rational functions of $N$ variables
$\xi_{1},\dots,\xi_{N}\in\mathbb{C}$. We identify each permutation $\nu$ of
$\mathcal{M}$ as a vector in the standard basis of $F^{N}$. (Here,
$\mathcal{M}$ is either $\mathcal{M}_{N}$ or $\mathcal{N}_{N}$.) In case of
$\mathcal{M}=[1,2,\dots,2]$, we identify the permutation $12\cdots 2$ as
$(1,0,\dots,0)$, $212\cdots 2$ as $(0,1,0,\dots,0)$ and so on. In case of
$\mathcal{M}=[1,\dots,1,2]$, we identify the permutation $1\cdots 12$ as
$(1,0,\dots,0)$, $1\cdots 121$ as $(0,1,0,\dots,0)$ and so on. Using the bra
and the ket notations in physics, we write $|~{}1~{}\rangle=(1,0,\dots,0)$,
$|~{}2~{}\rangle=(0,1,\dots,0)$ and so on. The matrix
$\mathbf{R}_{\beta\alpha}$ in (1.5) is interpreted as so called the $S$-matrix
$($scattering matrix$)$ in physics.

####  A.1.1 Revisit to Theorem 1.4, Propositions 3.2, 3.3, and 3.4

Recall (2.2) and (2.7). We will omit the superscripts $\mathcal{M}_{N}$ and
$\mathcal{N}_{N}$ in $\mathbf{A}^{\mathcal{M}_{N}}$ and
$\mathbf{A}^{\mathcal{N}_{N}}$ for convenience as in Section 3. By using the
bra-ket notation, the matrix elements of $\mathbf{T}_{i}(\beta,\alpha)$ are
given by

$\displaystyle\langle\nu\,|\,\mathbf{T}_{i}(\beta,\alpha)\,|\,\nu\rangle=\begin{cases}S_{\beta\alpha}&\text{if
$\nu(i)=\nu(i+1)$},\\\ P_{\beta\alpha}&\text{if $\nu(i)<\nu(i+1)$},\\\
Q_{\beta\alpha}&\text{if $\nu(i)>\nu(i+1)$},\end{cases}$ (A.1)

and

$\displaystyle\langle\nu^{\prime}\,|\,\mathbf{T}_{i}(\beta,\alpha)\,|\,\nu\rangle=\begin{cases}pT_{\beta\alpha}&\text{if
$\nu^{\prime}(i)=1,\nu^{\prime}(i+1)=2$ and $\nu(i)=2,\nu(i+1)=1$},\\\
qT_{\beta\alpha}&\text{if $\nu^{\prime}(i)=2,\nu^{\prime}(i+1)=1$ and
$\nu(i)=1,\nu(i+1)=2$},\\\ 0&\text{otherwise}.\end{cases}$ (A.2)

The formula

$\displaystyle[\mathbf{A}_{\sigma}]_{\nu,\nu}=[\mathbf{T}_{i_{j}}]_{\nu,\nu}\cdots[\mathbf{T}_{i_{m}}]_{\nu,\nu}\cdots[\mathbf{T}_{i_{1}}]_{\nu,\nu},$

in Theorem 1.4, Propositions 3.2, 3.3, and 3.4 is written

$\displaystyle\langle\nu|\mathbf{A}_{\sigma}|\nu\rangle=\langle\nu|\mathbf{T}_{i_{j}}|\nu\rangle\cdots\langle\nu|\mathbf{T}_{i_{m}}|\nu\rangle\cdots\langle\nu|\mathbf{T}_{i_{1}}|\nu\rangle.$
(A.3)

(A.1) and (A.3) motivate us to define the following operator which does not
change a permutation of species. Let $P$ be the set of all permutations of a
given multi-set $[1,2,\dots,2]$ or $[1,\dots,1,2]$, and let us denote an
element of $S_{N}\times P$ by

$\displaystyle(\sigma,\nu)=\left(\begin{matrix}\sigma\\\
\nu\end{matrix}\right)=\left(\begin{matrix}\sigma(1)\sigma(2)\cdots\sigma(N)\\\
\nu(1)\nu(2)\cdots\nu(N)\\\ \end{matrix}\right).$

For given simple transposition $T_{i}$, define a mapping ${T}^{*}_{i}$ on the
set of all objects written

$\displaystyle R\left(\begin{matrix}\sigma(1)\sigma(2)\cdots\sigma(N)\\\
\nu(1)\nu(2)\cdots\nu(N)\end{matrix}\right),$

where $R$ is 1 or a product of factors in the form of $S_{\beta\alpha}$,
$P_{\beta\alpha}$, $Q_{\beta\alpha}$, $pT_{\beta\alpha}$, $qT_{\beta\alpha}$
by

$\displaystyle{T}^{*}_{i}R\left(\begin{matrix}\sigma(1)&\cdots&\sigma(i)&\sigma(i+1)&\cdots&\sigma(N)\\\
\nu(1)&\cdots&\nu(i)&\nu(i+1)&\cdots&\nu(N)\end{matrix}\right)$
$\displaystyle\qquad{}=\begin{cases}RS_{\sigma(i+1)\sigma(i)}\left(\begin{matrix}\sigma(1)&\cdots&\sigma(i+1)&\sigma(i)&\cdots&\sigma(N)\\\
\nu(1)&\cdots&\nu(i)&\nu(i+1)&\cdots&\nu(N)\end{matrix}\right)&\text{if
$\nu(i)=\nu({i+1})$},\vspace{1mm}\\\
RQ_{\sigma(i+1)\sigma(i)}\left(\begin{matrix}\sigma(1)&\cdots&\sigma(i+1)&\sigma(i)&\cdots&\sigma(N)\\\
\nu(1)&\cdots&\nu(i)&\nu(i+1)&\cdots&\nu(N)\\\ \end{matrix}\right)&\text{if
$\nu(i)>\nu({i+1})$},\vspace{1mm}\\\
RP_{\sigma(i+1)\sigma(i)}\left(\begin{matrix}\sigma(1)&\cdots&\sigma(i+1)&\sigma(i)&\cdots&\sigma(N)\\\
\nu(1)&\cdots&\nu(i)&\nu(i+1)&\cdots&\nu(N)\end{matrix}\right)&\text{if
$\nu(i)<\nu({i+1})$}.\end{cases}$

In other words, $T_{i}^{*}$ acts as the usual simple transposition on
permutations in $S_{N}$ but it acts as the identity on permutations of a
multi-set. Then, $[\mathbf{A}_{\sigma}]_{\nu,\nu}$ in Theorem 1.4,
Propositions 3.2, 3.3 and 3.4 are read off as a by-product obtained after
acting $T^{*}_{i_{j}},\dots,T^{*}_{i_{1}}$ consecutively on
$(12{\cdots}N,\nu)$, that is, $\prod_{(\beta,\alpha)}R_{\beta\alpha}$ in

$\displaystyle T^{*}_{i_{j}}\cdots
T^{*}_{i_{1}}\left(\begin{matrix}1&\cdots&N-1&N\\\
\nu(1)&\nu(2)&\cdots&\nu(N)\end{matrix}\right)=\bigg{(}\prod_{(\beta,\alpha)}R_{\beta\alpha}\bigg{)}\left(\begin{matrix}\sigma(1)&\cdots&\sigma(N-1)&\sigma(N)\\\
\nu(1)&\nu(2)&\cdots&\nu(N)\\\ \end{matrix}\right).$

###  A.2 Revisit to Theorem 1.7

The formula

$\displaystyle[\mathbf{A}_{\sigma}]_{i,N}=\prod_{k=1}^{i-1}[\mathbf{w}_{k}]_{i,i}\prod_{k=i}^{N-1}[\mathbf{w}_{k}]_{k,k+1}$

in Theorem 1.7 is written by using the bra-ket notation

$\displaystyle\langle i|\mathbf{A}_{\sigma}|N\rangle=\langle
i|\mathbf{w}_{1}|i\rangle\cdots\langle i|\mathbf{w}_{i-1}|i\rangle\langle
i|\mathbf{w}_{i}|i+1\rangle\cdots\langle N-1|\mathbf{w}_{N-1}|N\rangle.$

We observe that each $\mathbf{w}_{k}$ with $k=i,\dots,N-1$ changes
$|k+1\rangle$ to $|k\rangle$ but each $\mathbf{w}_{k}$ with $k=1,\dots,i-1$
does not change $|i\rangle$. Also, we observe that

$\displaystyle[\mathbf{w}_{k}]_{k,k+1}=\langle
k|\mathbf{w}_{k}|k+1\rangle=\langle k|\mathbf{T}_{k}|k+1\rangle\langle
k+1|\mathbf{T}_{k-1}|k+1\rangle\cdots\langle
k+1|\mathbf{T}_{k-l+1}|k+1\rangle$

by (1.13), (A.1) and (A.2). Motivated by these observations, let us define the
following operator which changes a permutation of species represented by
$|k+1\rangle$ to a permutation of species represented by $|k\rangle$ and vice
versa to consider all four cases of $\nu=2\cdots 21,12\cdots 2,21\cdots
1,1\cdots 12.$ For given simple transposition $T_{k}$, define a mapping
$\hat{T}_{k}$ on the set of all objects written

$\displaystyle R\left(\begin{matrix}\sigma(1)\sigma(2)\cdots\sigma(N)\\\
\nu(1)\nu(2)\cdots\nu(N)\end{matrix}\right),$

where $R$ is 1 or a product of factors in the form of $S_{\beta\alpha}$,
$P_{\beta\alpha}$, $Q_{\beta\alpha}$, $pT_{\beta\alpha}$, $qT_{\beta\alpha}$
by

$\displaystyle\hat{T}_{i}R\left(\begin{matrix}\sigma(1)&\cdots&\sigma(i)&\sigma(i+1)&\cdots&\sigma(N)\\\
\nu(1)&\cdots&\nu(i)&\nu(i+1)&\cdots&\nu(N)\end{matrix}\right)$
$\displaystyle\qquad{}=\begin{cases}RpT_{\sigma(i+1)\sigma(i)}\left(\begin{matrix}\sigma(1)&\cdots&\sigma(i+1)&\sigma(i)&\cdots&\sigma(N)\\\
\nu(1)&\cdots&\nu(i+1)&\nu(i)&\cdots&\nu(N)\end{matrix}\right)&\text{if
$\nu(i)>\nu({i+1})$},\vspace{1mm}\\\
RqT_{\sigma(i+1)\sigma(i)}\left(\begin{matrix}\sigma(1)&\cdots&\sigma(i+1)&\sigma(i)&\cdots&\sigma(N)\\\
\nu(1)&\cdots&\nu(i+1)&\nu(i)&\cdots&\nu(N)\end{matrix}\right)&\text{if
$\nu(i)<\nu({i+1})$},\vspace{1mm}\\\
RS_{\sigma(i+1)\sigma(i)}\left(\begin{matrix}\sigma(1)&\cdots&\sigma(i+1)&\sigma(i)&\cdots&\sigma(N)\\\
\nu(1)&\cdots&\nu(i)&\nu(i+1)&\cdots&\nu(N)\end{matrix}\right)&\text{if
$\nu(i)=\nu({i+1})$}.\end{cases}$

With the argument in the above, we reformulate Theorem 1.7 in terms of the
operators $T^{*}$ and $\hat{T}$ as follows:

######  Corollary A.1.

Let

$\displaystyle\sigma=w_{1}\cdots w_{N-1}=\underbrace{T_{k_{j}}\cdots
T_{k_{m-1}}}_{w_{1}\cdots w_{i-1}}\underbrace{T_{k_{m}}\cdots
T_{k_{1}}}_{w_{i}\cdots w_{N-1}}$

be expressed as in Theorem 1.1. If $w_{i},\dots,w_{N-1}\neq 1$, then

$\displaystyle T^{*}_{k_{j}}\cdots
T^{*}_{k_{m-1}}\hat{T}_{k_{m}}\cdots\hat{T}_{k_{1}}\left(\begin{matrix}1~{}2~{}\cdots~{}N\\\
\nu(1)\cdots\nu(N)\end{matrix}\right)=[\mathbf{A}_{\sigma}]_{\pi^{(i)},\nu}\left(\begin{matrix}\sigma(1)\cdots\sigma(N)\\\
\pi^{(i)}(1)\cdots\pi^{(i)}(N)\end{matrix}\right),$

and if $i\leq l$ with $w_{l}=1$, then
$[\mathbf{A}_{\sigma}]_{\pi^{(i)},\nu}=0$.

######  Example A.2.

Suppose that we want to find $\big{[}\mathbf{A}_{4321}\big{]}_{2212,2221}$. By
Theorem 1.1, we have

$\displaystyle
4321=\underbrace{(T_{1})}_{w_{1}}\underbrace{(T_{2}T_{1})}_{w_{2}}\underbrace{(T_{3}T_{2}T_{1})}_{w_{3}}.$

Figure 3 shows how Corollary A.1 is used to find

$\displaystyle\big{[}A_{4321}\big{]}_{2212,2221}=S_{43}Q_{42}S_{32}pT_{41}S_{31}S_{21}.$

$\left[\vbox{\hrule
height=98.66562pt,depth=98.66562pt,width=0.0pt}\right.$$\left.\vbox{\hrule
height=98.66562pt,depth=98.66562pt,width=0.0pt}\right]$ $\left[\vbox{\hrule
height=79.5861pt,depth=79.5861pt,width=0.0pt}\right.$$\left.\vbox{\hrule
height=79.5861pt,depth=79.5861pt,width=0.0pt}\right]$
$1$$2$$3$$4$2221$\hat{T}_{1}$$S_{21}$$2$$1$$3$$4$2221$\hat{T}_{2}$$S_{31}$$2$$3$$1$$4$2221$\hat{T}_{3}$$pT_{41}$$2$$3$$4$$1$2212$T^{*}_{1}$$S_{32}$$1$$4$$2$$3$2122$T^{*}_{2}$$Q_{42}$$1$$2$$4$$3$2122$T^{*}_{1}$$S_{43}$$4$$3$$2$$1$2212
Figure 3:
$[\textbf{A}_{4321}]_{2212,2221}=S_{43}Q_{42}S_{32}pT_{41}S_{31}S_{21}$.

##  Appendix B Matrix elements $\boldsymbol{[\mathbf{A}_{\sigma}]_{\pi,2221}}$

$\sigma$ | $[\mathbf{A}_{\sigma}]_{2221,2221}$ | $[\mathbf{A}_{\sigma}]_{2212,2221}$ | $[\mathbf{A}_{\sigma}]_{2122,2221}$ | $[\mathbf{A}_{\sigma}]_{1222,2221}$
---|---|---|---|---
1234 | $1$ | $0$ | $0$ | $0$
1243 | $Q_{43}$ | $pT_{43}$ | $0$ | $0$
1324 | $S_{32}$ | $0$ | $0$ | $0$
1342 | $S_{32}Q_{42}$ | $S_{32}pT_{42}$ | $0$ | $0$
1423 | $Q_{43}S_{42}$ | $pT_{43}Q_{42}$ | $pT_{43}pT_{42}$ | $0$
1432 | $S_{32}Q_{42}S_{43}$ | $S_{32}pT_{42}Q_{43}$ | $pT_{43}pT_{42}S_{32}$ | $0$
2134 | $S_{21}$ | $0$ | $0$ | $0$
2143 | $S_{21}Q_{43}$ | $S_{21}pT_{43}$ | $0$ | $0$
2314 | $S_{21}S_{31}$ | $0$ | $0$ | $0$
2341 | $S_{21}S_{31}Q_{41}$ | $S_{21}S_{31}pT_{41}$ | $0$ | $0$
2413 | $S_{21}Q_{43}S_{41}$ | $S_{21}pT_{43}Q_{41}$ | $S_{21}pT_{43}pT_{41}$ | $0$
2431 | $S_{21}S_{31}Q_{41}S_{43}$ | $S_{21}S_{31}pT_{41}Q_{43}$ | $S_{21}pT_{43}pT_{41}S_{31}$ | $0$
3124 | $S_{32}S_{31}$ | $0$ | $0$ | $0$
3142 | $S_{32}S_{31}Q_{42}$ | $S_{32}S_{31}pT_{42}$ | $0$ | $0$
3214 | $S_{32}S_{31}S_{21}$ | $0$ | $0$ | $0$
3241 | $S_{32}S_{31}S_{21}Q_{41}$ | $S_{32}S_{31}S_{21}pT_{41}$ | $0$ | $0$
3412 | $S_{32}S_{31}Q_{42}S_{41}$ | $S_{32}S_{31}pT_{42}Q_{41}$ | $S_{32}S_{31}pT_{42}pT_{41}$ | $0$
3421 | $S_{32}S_{31}S_{21}Q_{41}S_{42}$ | $S_{32}S_{31}S_{21}pT_{41}Q_{42}$ | $S_{32}S_{31}pT_{42}pT_{41}S_{21}$ | $0$
4123 | $Q_{43}S_{42}S_{41}$ | $pT_{43}Q_{42}S_{41}$ | $pT_{43}pT_{42}Q_{41}$ | $pT_{43}pT_{42}pT_{41}$
4132 | $S_{32}Q_{42}S_{43}S_{41}$ | $S_{32}pT_{42}Q_{43}S_{41}$ | $S_{32}pT_{42}pT_{43}Q_{41}$ | $S_{32}pT_{42}pT_{43}pT_{41}$
4213 | $S_{21}Q_{43}S_{41}S_{42}$ | $S_{21}pT_{43}Q_{41}S_{42}$ | $S_{21}pT_{43}pT_{41}Q_{42}$ | $S_{21}pT_{43}pT_{41}pT_{42}$
4231 | $S_{21}S_{31}Q_{41}S_{43}S_{42}$ | $S_{21}S_{31}pT_{41}Q_{43}S_{42}$ | $S_{21}S_{31}pT_{41}pT_{43}Q_{42}$ | $S_{21}S_{31}pT_{41}pT_{43}pT_{42}$
4312 | $S_{32}S_{31}Q_{42}S_{41}S_{43}$ | $S_{32}S_{31}pT_{42}Q_{41}S_{43}$ | $S_{32}S_{31}pT_{42}pT_{41}Q_{43}$ | $S_{32}S_{31}pT_{42}pT_{41}pT_{43}$
4321 | $S_{32}S_{31}S_{21}Q_{41}S_{42}S_{43}$ | $S_{32}S_{31}S_{21}pT_{41}Q_{42}S_{43}$ | $S_{32}S_{31}S_{21}pT_{41}pT_{42}Q_{43}$ | $S_{32}S_{31}S_{21}pT_{41}pT_{42}pT_{43}$

##  Appendix C Matrix elements $\boldsymbol{[\mathbf{A}_{\sigma}]_{\pi,1112}}$

$\sigma$ | $[\mathbf{A}_{\sigma}]_{1112,1112}$ | $[\mathbf{A}_{\sigma}]_{1121,1112}$ | $[\mathbf{A}_{\sigma}]_{1211,1112}$ | $[\mathbf{A}_{\sigma}]_{2111,1112}$
---|---|---|---|---
1234 | $1$ | $0$ | $0$ | $0$
1243 | $P_{43}$ | $qT_{43}$ | $0$ | $0$
1324 | $S_{32}$ | $0$ | $0$ | $0$
1342 | $P_{42}S_{32}$ | $qT_{42}S_{32}$ | $0$ | $0$
1423 | $P_{43}S_{42}$ | $qT_{43}P_{42}$ | $qT_{43}qT_{42}$ | $0$
1432 | $S_{43}P_{42}S_{32}$ | $S_{43}qT_{42}P_{32}$ | $S_{43}qT_{42}qT_{32}$ | $0$
2134 | $S_{21}$ | $0$ | $0$ | $0$
2143 | $P_{43}S_{21}$ | $qT_{43}S_{21}$ | $0$ | $0$
2314 | $S_{31}S_{21}$ | $0$ | $0$ | $0$
2341 | $P_{41}S_{31}S_{21}$ | $qT_{41}S_{31}S_{21}$ | $0$ | $0$
2413 | $P_{43}S_{41}S_{21}$ | $qT_{43}P_{41}S_{21}$ | $qT_{43}qT_{41}S_{21}$ | $0$
2431 | $S_{43}P_{41}S_{31}S_{21}$ | $P_{43}qT_{41}S_{31}S_{21}$ | $qT_{43}qT_{41}S_{31}S_{21}$ | $0$
3124 | $S_{32}S_{31}$ | $0$ | $0$ | $0$
3142 | $P_{42}S_{32}S_{31}$ | $qT_{42}S_{32}S_{31}$ | $0$ | $0$
3214 | $S_{32}S_{31}S_{21}$ | $0$ | $0$ | $0$
3241 | $P_{41}S_{32}S_{31}S_{21}$ | $qT_{41}S_{32}S_{31}S_{21}$ | $0$ | $0$
3412 | $P_{42}S_{41}S_{32}S_{31}$ | $qT_{42}P_{41}S_{32}S_{31}$ | $qT_{42}qT_{41}S_{32}S_{31}$ | $0$
3421 | $S_{42}P_{41}S_{32}S_{31}S_{21}$ | $P_{42}qT_{41}S_{32}S_{31}S_{21}$ | $qT_{42}qT_{41}S_{32}S_{31}S_{21}$ | $0$
4123 | $P_{43}S_{42}S_{41}$ | $qT_{43}P_{42}S_{41}$ | $qT_{43}qT_{42}P_{41}$ | $qT_{43}qT_{42}qT_{41}$
4132 | $S_{43}P_{42}S_{41}S_{32}$ | $P_{43}qT_{42}S_{41}S_{32}$ | $qT_{43}qT_{42}P_{41}S_{32}$ | $qT_{43}qT_{42}qT_{41}S_{32}$
4213 | $P_{43}S_{42}S_{41}S_{21}$ | $qT_{43}S_{42}P_{41}S_{21}$ | $qT_{43}P_{42}qT_{41}S_{21}$ | $qT_{43}qT_{42}qT_{41}S_{21}$
4231 | $S_{43}S_{42}P_{41}S_{31}S_{21}$ | $P_{43}S_{42}qT_{41}S_{31}S_{21}$ | $qT_{43}P_{42}qT_{41}S_{31}S_{21}$ | $qT_{43}qT_{42}qT_{41}S_{31}S_{21}$
4312 | $S_{43}P_{42}S_{41}S_{32}S_{31}$ | $S_{43}qT_{42}P_{41}S_{32}S_{31}$ | $P_{43}qT_{42}qT_{41}S_{32}S_{31}$ | $qT_{43}qT_{42}qT_{41}S_{32}S_{31}$
4321 | $S_{43}S_{42}P_{41}S_{32}S_{31}S_{21}$ | $S_{43}P_{42}qT_{41}S_{32}S_{31}S_{21}$ | $P_{43}qT_{42}qT_{41}S_{32}S_{31}S_{21}$ | $qT_{43}qT_{42}qT_{41}S_{32}S_{31}S_{21}$

### Acknowledgements

This work was supported by the faculty development competitive research grants
(090118FD5341 and 021220FD4251) by Nazarbayev University. We are thankful to
Kamila Izhanova for assisting in preparation for the manuscript and to
Francesco Sica for valuable comments. Most of all, we deeply appreciate
anonymous referees for providing valuable comments to improve the earlier
version of this paper.

## References

  * [1] Borodin A., Bufetov A., Color-position symmetry in interacting particle systems, Ann. Probab. 49 (2021), 1607–1632, arXiv:1905.04692.
  * [2] Borodin A., Wheeler M., Coloured stochastic vertex models and their specctral theory, arXiv:1808.01866.
  * [3] Chatterjee S., Schütz G.M., Determinant representation for some transition probabilities in the TASEP with second class particles, J. Stat. Phys. 140 (2010), 900–916, arXiv:1003.5815.
  * [4] Kassel C., Turaev V., Braid groups, Graduate Texts in Mathematics, Vol. 247, Springer, New York, 2008.
  * [5] Korhonen M., Lee E., The transition probability and the probability for the left-most particle’s position of the $q$-totally asymmetric zero range process, J. Math. Phys. 55 (2014), 013301, 15 pages, arXiv:1308.4769.
  * [6] Kuan J., Probability distributions of multi-species $q$-TAZRP and ASEP as double cosets of parabolic subgroups, Ann. Henri Poincaré 20 (2019), 1149–1173, arXiv:1801.02313.
  * [7] Kuan J., Determinantal expressions in multi-species TASEP, SIGMA 16 (2020), 133, 6 pages, arXiv:2007.02913.
  * [8] Lee E., Distribution of a particle’s position in the ASEP with the alternating initial condition, J. Stat. Phys. 140 (2010), 635–647.
  * [9] Lee E., The current distribution of the multiparticle hopping asymmetric diffusion model, J. Stat. Phys. 149 (2012), 50–72, arXiv:1203.0501.
  * [10] Lee E., Some conditional probabilities in the TASEP with second class particles, J. Math. Phys. 58 (2017), 123301, 11 pages, arXiv:1707.02539.
  * [11] Lee E., On the TASEP with second class particles, SIGMA 14 (2018), 006, 17 pages, arXiv:1705.10544.
  * [12] Lee E., Exact formulas of the transition probabilities of the multi-species asymmetric simple exclusion process, SIGMA 16 (2020), 139, 9 pages, arXiv:1809.07362.
  * [13] Lee E., Wang D., Distributions of a particle’s position and their asymptotics in the $q$-deformed totally asymmetric zero range process with site dependent jumping rates, Stochastic Process. Appl. 129 (2019), 1795–1828, arXiv:1703.08839.
  * [14] Nagao T., Sasamoto T., Asymmetric simple exclusion process and modified random matrix ensembles, Nuclear Phys. B 699 (2004), 487–502, arXiv:cond-mat/0405321.
  * [15] Rákos A., Schütz G.M., Bethe ansatz and current distribution for the TASEP with particle-dependent hopping rates, Markov Process. Related Fields 12 (2006), 323–334, arXiv:cond-mat/0506525.
  * [16] Tracy C.A., Widom H., Integral formulas for the asymmetric simple exclusion process, Comm. Math. Phys. 279 (2008), 815–844, arXiv:0704.2633.
  * [17] Tracy C.A., Widom H., On the distribution of a second-class particle in the asymmetric simple exclusion process, J. Phys. A: Math. Theor. 42 (2009), 425002, 6 pages, arXiv:0907.4395.
  * [18] Tracy C.A., Widom H., On the asymmetric simple exclusion process with multiple species, J. Stat. Phys. 150 (2013), 457–470, arXiv:1105.4906.
  * [19] Tracy C.A., Widom H., Blocks and gaps in the asymmetric simple exclusion process: asymptotics, J. Math. Phys. 59 (2018), 091401, 13 pages, arXiv:1711.08094.