A Path-Counting Analysis of Phase Shifts in Box-Ball Systems

A Path-Counting Analysis of Phase Shifts
in Box-Ball Systems

Nicholas M. ERCOLANI and Jonathan RAMALHEIRA-TSU

N.M. Ercolani and J. Ramalheira-Tsu

Department of Mathematics, University of Arizona, USA
<EMAIL_ADDRESS><EMAIL_ADDRESS>http://www.math.arizona.edu/~ercolani,
http://www.math.arizona.edu/~jramalheiratsu

Received April 08, 2022, in final form August 20, 2022; Published online
August 25, 2022

In this paper, we perform a detailed analysis of the phase shift phenomenon of
the classical soliton cellular automaton known as the box-ball system,
ultimately resulting in a statement and proof of a formula describing this
phase shift. This phenomenon has been observed since the nineties, when the
system was first introduced by Takahashi and Satsuma, but no explicit global
description was made beyond its observation. By using the
Gessel–Viennot–Lindström lemma and path-counting arguments, we present here a
novel proof of the classical phase shift formula for the continuous-time Toda
lattice, as discovered by Moser, and use this proof to derive a discrete-time
Toda lattice analogue of the phase shift phenomenon. By carefully analysing
the connection between the box-ball system and the discrete-time Toda lattice,
through the mechanism of tropicalisation/dequantisation, we translate this
discrete-time Toda lattice phase shift formula into our new formula for the
box-ball system phase shift.

soliton phase shifts; box-ball system; ultradiscretization;
Gessel–Viennot–Lindström lemma

17B80; 37J70; 37K10

##  1 Introduction

In classical solitary wave theory there are three well-known signature
features of the inherent nonlinearity of these waves that are inter-related.
The first is that in long time, forward and backward, an exact111Exact here
means an $n$-soliton wave-form that propagates without “radiating” any
dispersive oscillations. solitary wave asymptotically separates into distinct
localized wave-forms, referred to as masses, that maintain their form as they
propagate further (both forward or backward). The second feature is that in
long time these individual masses are ordered by their peak amplitudes,
travelling with individual speeds asymptotically proportional to the square
root of the amplitude. This is referred to as the sorting property. Finally,
at intermediate times, when these individual masses interact, they pass
through one another with their wave-forms unchanged but experiencing a
relative phase shift. We illustrate this in the case of the KdV equation [6]
with a space-time plot in Figure 1.

Figure 1: A 2-soliton solution to the KdV equation, $U(x,t)$, with $x$ along
the horizontal axis and $t$ along the vertical. The gradient from red to blue
represents small values to large. We see two coherent waves: one with a higher
peak (blue) and another with a lower peak (orange). The larger wave, initially
behind, collides with the smaller, and emerges after the collision in front.
Note also the phase shift which corresponds to the “breaks” in the linear
evolution of the peaks.

The sorting and phase shift properties are characteristic of integrable
evolution equations exhibiting coherent states of nonlinear wave type. In the
next two sections of this paper, we will discuss two other examples of these
phenomena: the finite Toda lattice and the box-ball system (BBS). They turn
out to be related to one another through a type of semi-classical limit known
as tropicalization or ultra-discretization as has been well-documented [16,
17, 30].

The precise sorting and phase shift formulas for the Toda lattice have been
known for some time going back to Moser [20]. It is also the case that early
work by Tokihiro et al. [29] derives results related to the explicit BBS phase
shift formula that we will present. A comparison to the work of [29] is given
later in Section 8 which discusses this and other related work. In this paper
we give a new proof of the classical phase shift formula for Toda within a
representation theoretic framework closely related to Kostant’s generalized
Toda systems [13]. However, rather than basing the proof on representation
theoretic arguments, as Kostant does, our approach is based on a path counting
construction. The potential advantages of this are, we feel, two-fold. First,
Kostant’s extension of the phase shift formula depends on somewhat complicated
determinantal formulas, whereas what we present is completely geometric and
combinatorial thus making generalizations more natural. Secondly, we found,
subsequent to our initial derivations, that the directed graphs we employ for
our path counting are, in fact, those used by Postnikov [19] to coordinatize
the totally positive Grassmannians and their tropicalization. This reinforces
our belief that this is the right geometric picture for our second main result
which is to derive the explicit, general phase shift formula for BBS by direct
tropical limit of the classical Toda formula.

###  1.1 Outline

In the next two sections we will present the necessary background on the box-
ball system and the Toda lattice to be able to explicitly describe the phase
shift phenomena in these systems. Sections 4 and 5 provide the necessary
representation theoretic background that underlies our arguments. These are
presented in such a way as to make it clear how our analysis would extend to
the setting of generalized Toda lattices as introduced by Kostant [14]. In
Section 6 we present our novel derivation of the classical phase shift formula
for both the classical (Theorem 6.1) and discrete-time (Theorem 6.8) Toda
systems in terms of the Gessel–Viennot–Lindström (GVL) lemma. Finally, in
Section 7, we use this to deduce the phase shift formula for BBS (Theorem
7.1). The appendices expand on details for the path-counting construction of
our GVL formulæ.

##  2 Phase shift in box-ball dynamics

###  2.1 Box-ball systems

A cellular automaton is a special type of discrete dynamical system with both
discrete time steps and a discrete (in fact finite) number of states. Of
particular interest is the box-ball system (BBS) which was introduced in 1990
by Takahashi and Satsuma [26].

######  Definition 2.1.

The (basic) box-ball system consists of a one-dimensional infinite array of
boxes with a finite number of the boxes filled with balls, and no more than
one ball in each box (see, for example, Figure 2).

More formally, the phase space of this system, which we denote by BBS, can be
identified with the space of binary sequences $\\{0,1\\}^{\mathbb{Z}}$, with
all but finitely many entries equal to zero, so that $1$’s correspond to
filled boxes and $0$’s to empty boxes.

$\cdots$$\cdots$ Figure 2: A box-ball state.

###  2.2 The box-ball evolution

A simple evolution rule is provided for the box-ball dynamics:

  1. (1)

Take the left-most ball that has not been moved and move it to the left-most
empty box to its right.

  2. (2)

Repeat (1) until all balls have been moved precisely once.

Since the algorithm requires one to know which balls have been moved, we can,
without technically changing the algorithm, introduce a colour-coding based on
whether balls have moved or not. Balls will be blue until they have moved,
after which they will become red. When all balls are red, the colours should
be reset to blue, ready for the next time step. Or, equivalently, a $0$-th
step of colouring all balls blue should be prescribed. We will use the latter
for a minor benefit in brevity. Below is an example of the evolution with this
colour-coding, with each ball move separated into a sub-step:

$\cdots$$\cdots$

$\cdots$$\cdots$

$\cdots$$\cdots$

$\cdots$$\cdots$

$\cdots$$\cdots$

$\cdots$$\cdots$

$\cdots$$\cdots$

$\cdots$$\cdots$

Figure 3: A box-ball system time evolution (one time step).

###  2.3 Soliton behaviour and the sorting property

The box-ball system is sometimes referred to as a soliton cellular automaton.
To appreciate this reference, we think of an entire box-ball configuration as
being the soliton. In the classical setting, a soliton is thought of as being
composed of masses (or pulses) that are nonlinearly related. In the box-ball
setting, a “mass” corresponds to a consecutive sequence of balls. One may
observe (see below) that such a block travels with velocity equal to the
number of balls in it, so that larger blocks have velocity greater than
smaller blocks. As with classical soliton masses, during the course of its
evolution, the blocks may collide, and temporarily change their sizes.
However, asymptotically in both forward and backward (discrete) time ($t$),
the sizes of blocks comprising the soliton are the same. We will therefore
refer to such a configuration as an $n$-soliton if the total number of blocks
asymptotically is $n$.

After blocks collide, they come out of the collision ordered with the longer
blocks ahead of smaller blocks but having a phase shift due to the
nonlinearity. By phase shift here, we mean the difference between where the
block ends up after the collision and where the block would have been if it
were not for the collision.

In the following figure, we illustrate how the blocks become ordered after
sufficiently many time evolutions. Once sorted, they travel with their
respective velocities, never to collide again.

$\cdots$$\cdots$

$\cdots$$\cdots$

$\cdots$$\cdots$

$\cdots$$\cdots$

$\cdots$$\cdots$

$\cdots$$\cdots$

Figure 4: The sorting property of the box-ball system.

####  2.3.1 Coordinates on the box-ball system

Suppose at time $t$, one has $n$ blocks in the soliton. Let
$Q_{1}^{t},Q_{2}^{t},\dots,Q_{n}^{t}$ denote the lengths of these blocks,
taken from left to right. Let $W_{1}^{t},W_{2}^{t},\dots,W_{n-1}^{t}$ denote
the lengths of the sets of empty boxes between the $n$ sets of filled boxes,
again taken from left to right. Lastly, let $W_{0}^{t}$ and $W_{n}^{t}$ be
formally defined to be $\infty$, reflecting the fact that the empty boxes
continue infinitely in both directions.

The following theorem gives evolution equations for these coordinates. They
can be found, for example, in [28].

######  Theorem 2.2 ([28]).

The coordinates
$\big{(}W_{0}^{t},Q_{1}^{t},W_{1}^{t},\dots,Q_{n}^{t},W_{n}^{t}\big{)}$ evolve
under the box ball dynamics according to

$\displaystyle W_{0}^{t+1}=W_{n}^{t+1}=\infty,\qquad
W_{i}^{t+1}=Q_{i+1}^{t}+W_{i}^{t}-Q_{i}^{t+1},\qquad i=1,\dots,n-1,$ (2.1)
$\displaystyle
Q_{i}^{t+1}=\min\Bigg{(}W_{i}^{t},\sum_{j=1}^{i}Q_{j}^{t}-\sum_{j=1}^{i-1}Q_{j}^{t+1}\Bigg{)},\qquad
i=1,\dots,n.$

######  Remark 2.3.

It follows from Remark 2.6 in [9] that each $W_{i}^{t}>0$ for each $i$ and for
all time. Furthermore, since there are always $n$ blocks, each $Q_{i}^{t}>0$
(by definition of a block).

######  Example 2.4.

Take the initial state in Figure 3:

$\cdots$$\cdots$$W_{0}^{t}$$Q_{1}^{t}$$W_{1}^{t}$$Q_{2}^{t}$$W_{2}^{t}$$Q_{3}^{t}$$W_{3}^{t}$$Q_{4}^{t}$$W_{4}^{t}$

$\cdots$$\cdots$$W_{0}^{t+1}$$Q_{1}^{t+1}$$W_{1}^{t+1}$$\,\,Q_{2}^{t+1}$$W_{2}^{t+1}$$Q_{3}^{t+1}$$\,\,W_{3}^{t+1}$$Q_{4}^{t+1}$$W_{4}^{t+1}$

Figure 5: The box-ball coordinates on a box-ball system and its time
evolution.

Under the time evolution, the coordinates evolve as

$(\infty,3,3,1,2,2,1,1,\infty)\mapsto(\infty,3,1,1,3,1,1,2,\infty).$

###  2.4 Phase shift phenomenon for the BBS

We have seen how, as $t\to+\infty$, the blocks sort themselves by increasing
length. The same holds in reverse time: as $t\to-\infty$, the blocks are
ordered by decreasing lengths. The following example demonstrates why one
cannot simply just count block lengths (the third state does not show the
soliton structure of blocks of length 1 and 3):

$~{}\cdots$$\cdots$$~{}\cdots$$\cdots$$~{}\cdots$$\cdots$$~{}\cdots$$\cdots$$~{}\cdots$$\cdots$
Figure 6: A phase shift interaction between two colliding blocks.

######  Remark 2.5.

In the above example, we can discern the asymptotic ordering in the first,
second, fourth and fifth rows, simply by counting the numbers of balls in each
block of adjacent balls. The middle row (the third) could be misleading, since
it reveals a $(2,2)$ structure for the blocks. If two blocks are spaced far
enough apart, then no such obfuscation occurs.

Barring this intricacy (i.e., when there is enough space between consecutive
blocks), one can take two blocks, evolve sufficiently many times according to
the box-ball evolution, and compare the position of the blocks to where they
would have been if it had not have been for the collision.

In the figure below, we replicate Figure 6. However, we use green balls to
keep track of where the block of three balls would have been without the
collision, and magenta balls to keep track of where the block of one ball
would have been.

$\cdots$$\cdots$

$\cdots$$\cdots$

$\cdots$$\cdots$

$\cdots$$\cdots$

$\cdots$$\cdots$

In the above, we look at the position of the block of three blue balls and
notice that it is shifted two spaces to the right of where it would have been
if it were not for the collision. Similarly, we look at the isolated blue ball
and see that it is shifted left two positions of where it would have been
without the collision. This shifting of blocks from their would-be positions
is the phenomenon of phase shifting described above.

##  3 The Toda lattice

The Toda lattice [27] is a dynamical system on $\mathbb{R}^{2n}$, with
coordinates $(p_{1},\dots,p_{n},q_{1},\dots,q_{n})$. The system is Hamiltonian
with respect to the standard symplectic structure on $\mathbb{R}^{2n}$ with
Hamiltonian

$H(p_{1},\dots,p_{n},q_{1},\dots,q_{n})=\dfrac{1}{2}\sum_{j=1}^{n}p_{j}^{2}+\sum_{j=1}^{n-1}{\rm
e}^{q_{j}-q_{j+1}}.$

The Toda lattice equations are then given by

$\displaystyle\dot{q}_{j}=p_{j},\qquad j=1,\dots,n,$ (3.1)
$\displaystyle\dot{p}_{j}=\begin{cases}-{\rm e}^{q_{1}-q_{2}}&\text{if
}j=1,\\\ {\rm e}^{q_{j-1}-q_{j}}-{\rm e}^{q_{j}-q_{j+1}}&\text{if }1<j<n,\\\
{\rm e}^{q_{n-1}-q_{n}}&\text{if }j=n.\end{cases}$ (3.2)

In this representation, boundary conditions of $q_{0}=-\infty$ and
$q_{n+1}=\infty$ have been imposed, which, formally, result in ${\rm
e}^{q_{0}-q_{1}}={\rm e}^{q_{n}-q_{n+1}}=0$. These boundary conditions are
chosen to truncate the lattice to a finite system.

###  3.1 Flaschka’s transformation and isospectrality

Flaschka’s transformation [10] makes the variable replacement

$(p_{1},\dots,p_{n},q_{1},\dots,q_{n})\mapsto(a_{1},\dots,a_{n},b_{1},\dots,b_{n-1})$

given by setting $a_{j}=-p_{j}$ for $j=1,\dots,n$, and $b_{j}={\rm
e}^{q_{j}-q_{j+1}}$ for $j=1,\dots,n-1$. This is clearly a surjection of
$\mathbb{R}^{2n}$ onto the open subset of $\mathbb{R}^{2n-1}$ with $b_{i}>0$.
It is evident that uniformly translating the position variables,
$(q_{1},\dots,q_{n})\to(q_{1}+c,\dots,q_{n}+c)$ leaves the equations
(3.1)–(3.2) invariant. Fixing a center of mass for this particle system
amounts to a particular cross-section of the fibration that the Flaschka
transformation presents.

In Flaschka variables, the Toda lattice assumes the following simple form:

$\displaystyle\dot{b}_{j}=(a_{j+1}-a_{j})b_{j},\qquad j=1,\dots,n-1,$ (3.3)
$\displaystyle\dot{a}_{j}=\begin{cases}b_{1}&\text{if }j=1,\\\
b_{j}-b_{j-1}&\text{if }1<j<n,\\\ -b_{n-1}&\text{if }j=n.\end{cases}$ (3.4)

One can arrange the variables neatly into a tridiagonal Hessenberg matrix

$X\doteq\left[\begin{array}[]{cccc}a_{1}&1\\\ b_{1}&a_{2}&\ddots\\\
&\ddots&\ddots&1\\\ &&b_{n-1}&a_{n}\end{array}\right].$

It is immediate from (3.4) that $\text{tr}X$ is a constant of motion. This is
conservation of momentum corresponding to the translation symmetry mentioned
above.

Equations (3.3) and (3.4) amount to the following matrix differential
equation:

$\left[\begin{matrix}a_{1}&1\\\ b_{1}&a_{2}&\ddots\\\ &\ddots&\ddots&1\\\
&&b_{n-1}&a_{n}\end{matrix}\right]^{\bullet}=\left[\begin{matrix}b_{1}&0\\\
(a_{2}-a_{1})b_{1}&b_{2}-b_{1}&\ddots\\\ &\ddots&\ddots&0\\\
&&(a_{n}-a_{n-1})b_{n-1}&-b_{n-1}\end{matrix}\right].$

This matrix form of the Toda equations has the form of a Lax equation,

$\dfrac{{\rm d}}{{\rm d}t}X=[X,\pi_{-}(X)],\qquad X(0)=X_{0},$ (3.5)

where $\pi_{-}(X)$ denotes the projection of $X$ into its strictly lower part:

$\pi_{-}(X)=\left[\begin{matrix}0&\\\ b_{1}&0&\\\ &\ddots&\ddots&\\\
&&b_{n-1}&0\end{matrix}\right].$

It is a straightforward application of the product rule using (3.5) to see
that

$\frac{{\rm d}}{{\rm d}t}\text{tr}X^{k}=\text{tr}\frac{{\rm d}}{{\rm
d}t}X^{k}=\text{tr}\big{[}X^{k},\pi_{-}(X)\big{]}=0.$

This implies the so-called isospectrality of the Toda lattice: the eigenvalues
of $X$ remain invariant under the Toda flow.

###  3.2 Sorting for Toda

In Section 4, we will see that for $t\to\infty$, the Toda solution $X(t)$
limits to a matrix of the form

$\epsilon_{\lambda}=\left[\begin{matrix}\lambda_{1}&1\\\
&\lambda_{2}&\ddots\\\ &&\ddots&1\\\ &&&\lambda_{n}\end{matrix}\right],$ (3.6)

where $\lambda_{1}>\dots>\lambda_{n}$ are the eigenvalues of $X_{0}$ which we
will assume to be distinct in the remainder of this paper (by isospectrality
these are the eigenvalues of $X(t)$ for all $t$). It is immediate from (3.5)
that $\epsilon_{\lambda}$ is a fixed point of the Toda flow as are all the
other $n!$ matrices of this form with the eigenvalues permuted along the
diagonal (and these are the only fixed points). We will also see in Section 4
that as $t\to-\infty$, $X(t)$ limits to the fixed point associated to the
longest permutation (which reverses the order of the eigenvalues along the
diagonal). Finally, from the Flaschka representation, one sees that the
asymptotic velocities of the original Toda variables, in forward and backward
time, are the eigenvalues of $X(t)$. So, what we have just described is just
the sorting property of the Toda lattice. Precisely, the asymptotic dynamics
is

$\displaystyle q_{k}(t)=\alpha_{k}^{+}t+\beta_{k}^{+}+O\big{(}{\rm e}^{-\delta
t}\big{)},$ (3.7) $\displaystyle
q_{k}(-t)=-\alpha_{k}^{-}t+\beta_{k}^{-}+O\big{(}{\rm e}^{-\delta t}\big{)}$
(3.8)

as $t\to+\infty$, where

$\alpha_{k}^{+}=\lim_{t\to+\infty}p_{k}(t).$

To relate this to the Hessenberg form of the Toda lattice, recall that

$a_{k}(t)=-p_{k}(t),\qquad b_{k}(t)={\rm e}^{q_{k}(t)-q_{k+1}(t)}.$

So, since the limiting form in forward time of $X(t)$ is given by (3.6) (and
by its reverse permutation in backward time), one has that

$\displaystyle\alpha_{k}^{+}=-\lim\limits_{t\to+\infty}a_{k}(t)=-\lambda_{k},$
$\displaystyle\alpha_{k}^{-}=-\lim\limits_{t\to-\infty}a_{k}(t)=-\lambda_{n-k+1}$

from which we note the symmetry $\alpha_{k}^{-}=\alpha_{n-k+1}^{+}$. Since
$\lambda_{1}>\lambda_{2}>\cdots>\lambda_{n}$,
$q_{k}(t)-q_{k+1}(t)\sim-(\lambda_{k}-\lambda_{k+1})t$ as $t\to+\infty$. So,
it is indeed the case that the particles spread apart linearly and sort, from
which it follows that $b_{k}(t)\to 0$ exponentially, consistent with the
stated limiting form (3.6) of $X(t)$. A similar statement obtains
asymptotically in reverse time.

###  3.3 Symes’s discrete-time matrix dynamics
and the discrete-time Toda lattice

In 1980, Symes [23] proposed a discrete time flow based on matrix
factorization that commutes with the continuous time Toda flow described
previously. This factorization mirrors that described in Theorem 4.1, more
commonly referred to as Gaussian elimination or the $LU$-decomposition.

######  Note.

In this section and what follows, we continue to use $t$ to denote discrete
time, i.e., $t\in\mathbb{Z}$ (as well as for continuous time,
$t\in\mathbb{R}$). The temporal domain intended should be clear from context.

We inductively define Symes’s dynamics as a two-step discrete evolution on
Hessenberg matrices. If at (discrete) time $t$ we have a matrix $X(t)$, we
obtain $X(t+1)$ as follows:

  1. 1.

Perform Gaussian elimination to factor $X(t)=L(t)R(t)$, with $L(t)$ lower
unipotent and $R(t)$ upper triangular.

  2. 2.

Permute the factors to define $X(t+1)=R(t)L(t)$.

######  Remark 3.1.

By construction, one has

$X(t+1)=R(t)L(t)=\big{(}L(t)^{-1}X(t)\big{)}L(t)=L(t)^{-1}X(t)L(t).$ (3.9)

Thus, this discrete evolution is given by conjugating a matrix by its lower
unipotent factor. Since the spectrum of a matrix is invariant under
conjugation, it follows that the eigenvalues are constants of motion for this
discrete evolution; i.e., this discrete flow is isospectral.

Furthermore, if $X(t)$ is tridiagonal, then one can show that $L(t)$ is lower
bi-diagonal with ones on its diagonal and $R(t)$ is upper bi-diagonal with
ones on its superdiagonal. Therefore, the product $X(t+1)=R(t)L(t)$ is itself
once again a tridiagonal Hessenberg matrix; i.e., this flow preserves the Toda
lattice phase space.

It is of course not always the case that a given matrix has an
$LU$-factorization in which the coefficients of the factors do not become
singular. It is possible to continue the dynamics through these singularities,
as we will see in Section 4. For the phase shift behavior that we study, we
are only interested in the long-time dynamics; for $t$ of sufficiently large
magnitude, $LU$-factorization always works.

Symes [23] observed that this discrete evolution extends to a continuous
evolution with Lax equation of the same form as the Toda lattice Lax equation
(equation (3.5)), but with $\pi_{-}(X)$ replaced by $\pi_{-}(\log X)$:

$\dfrac{{\rm d}}{{\rm d}t}X=[X,\pi_{-}(\log X)].$ (3.10)

######  Remark 3.2.

In our applications here we will always take $X$ to have positive eigenvalues
so that $\log X$ may be uniquely defined in terms of the principal branch of
the logarithm along the positive real axis. From this it follows that this
continuous flow is well-defined and commutes with the original Toda flow [5,
31]. The Hamiltonian for (3.10) is $H_{LU}=\operatorname{Tr}(X\log X-X)$. This
is discussed further in Section 4.

To write the Symes discrete-time evolution out explicitly, let

$L(t)=\left[\begin{matrix}1\\\ V_{1}^{t}&1\\\ &\ddots&\ddots\\\
&&V_{n-1}^{t}&1\end{matrix}\right],\qquad\text{and}\qquad
R(t)=\left[\begin{matrix}I_{1}^{t}&1\\\ &I_{2}^{t}&\ddots\\\ &&\ddots&1\\\
&&&I_{n}^{t}\end{matrix}\right],$ (3.11)

then Symes’s discrete-time evolution produces what has come to be known as the
finite discrete-time Toda lattice:

######  Definition 3.3.

The finite discrete-time Toda lattice is the system

$\begin{cases}I_{i}^{t+1}=I_{i}^{t}+V_{i}^{t}-V_{i-1}^{t+1},&i=1,\dots,n,\\\
V_{i}^{t+1}=\dfrac{I_{i+1}^{t}V_{i}^{t}}{I_{i}^{t+1}},&i=1,\dots,n-1,\\\
V_{0}^{t}=V_{n}^{t}=0,&\end{cases}$

which is expressible as

$L(t+1)R(t+1)=R(t)L(t).$

###  3.4 Maslov tropicalisation

Tropical mathematics (see, for example, [16, 17, 30]) is the study of the min-
plus (or the max-plus) semiring, which we will now define. In this section, we
follow the presentation given by Maslov [17]. The structure of the semiring
$(\mathbb{R}_{\geq 0},+,\times)$ is carried over to the set
$\mathbb{R}\cup\\{\infty\\}$ by a family of bijections $D_{\hbar}$, for
$\hbar>0$, given by

$D_{\hbar}(x)=\begin{cases}-\hbar\ln x&\text{if }x\neq 0,\\\ -\infty&\text{if
}x=0.\end{cases}$

This induces a family of semirings, parametrised by $\hbar>0$,
$(\mathbb{R}\cup\\{\infty\\},\oplus_{\hbar},\otimes_{\hbar})$ with operations
given by

$\displaystyle
a\oplus_{\hbar}b=D_{\hbar}\big{(}D_{\hbar}^{-1}(a)+D_{\hbar}^{-1}(b)\big{)}=\begin{cases}-\hbar\ln\big{(}{\rm
e}^{-a/\hbar}+{\rm e}^{-b/\hbar}\big{)}&\text{if }a,b\neq\infty,\\\
\min(a,b)&\text{otherwise},\end{cases}$ $\displaystyle
a\otimes_{\hbar}b=D_{\hbar}\big{(}D_{\hbar}^{-1}(a)D_{\hbar}^{-1}(b)\big{)}=a+b.$

In the limit, $\hbar\to 0$, Maslov ‘dequantises’ $(\mathbb{R}_{\geq
0},+,\times)$ to obtain the tropical semiring
$(\mathbb{R}\cup\\{\infty\\},\allowbreak\min,+)$, where its addition is the
usual $\min$ operation and its multiplication operation is usual addition,
hence the name “min-plus semiring”.

Maslov views this construction as an analogue of the correspondence principle
from quantum mechanics, with $(\mathbb{R}_{\geq 0},+,\times)$ as the quantum
object and $(\mathbb{R}\cup\\{\infty\\},\min,+)$ as its classical counterpart.

######  Remark 3.4.

The limiting process through $D_{\hbar}$ allows tropicalisation to be carried
out precisely on equations by pulling the analogous tropical variables back,
mapping the resulting equation back to $\mathbb{R}\cup\\{\infty\\}$, and then
taking the limit as $\hbar\to 0$. This can be seen in action in equations
(3.12)–(3.19), and again in Section 7.

###  3.5 The ultradiscrete Toda lattice (udToda)

Following [28], we perform the process of ultradiscretisation on the discrete-
time Toda lattice to see that this results in the box-ball system.

Recall the discrete-time Toda lattice:

$\begin{cases}V_{0}^{t}=V_{n}^{t}=0,&\\\
I_{i}^{t+1}=I_{i}^{t}+V_{i}^{t}-V_{i-1}^{t+1},&i=1,\dots,n,\\\
V_{i}^{t+1}I_{i}^{t+1}=I_{i+1}^{t}V_{i}^{t},&i=1,\dots,n-1.\end{cases}$

It can be shown that the discrete-time Toda lattice is equivalent to the
following system

$\begin{cases}V_{0}^{t}=V_{n}^{t}=0,&\\\
I_{i}^{t+1}=V_{i}^{t}+\dfrac{I_{i}^{t}\cdots I_{1}^{t}}{I_{i-1}^{t+1}\cdots
I_{1}^{t+1}},&i=1,\dots,n,\\\
V_{i}^{t+1}I_{i}^{t+1}=I_{i+1}^{t}V_{i}^{t},&i=1,\dots,n-1.\end{cases}$

Making the change of variables

$I_{i}^{t}={\rm e}^{-\frac{1}{\hbar}Q_{i}^{t}(\hbar)},\qquad V_{i}^{t}={\rm
e}^{-\frac{1}{\hbar}W_{i}^{t}(\hbar)},$ (3.12)

one obtains

$\displaystyle
W_{i}^{t+1}(\hbar)=Q_{i+1}^{t}(\hbar)+W_{i}^{t}(\hbar)-Q_{i}^{t+1}(\hbar),\qquad
i=1,\dots,n-1,$ (3.13) $\displaystyle Q_{i}^{t+1}(\hbar)=-\hbar\log\Big{(}{\rm
e}^{-\frac{1}{\hbar}W_{i}^{t}(\hbar)}+{\rm
e}^{-\frac{1}{\hbar}\left(\sum_{j=1}^{i}Q_{j}^{t}(\hbar)-\sum_{j=1}^{i-1}Q_{j}^{t+1}(\hbar)\right)}\Big{)},\qquad
i=1,\dots,n,$ (3.14) $\displaystyle W_{0}^{t}(\hbar)=W_{n}^{t}(\hbar)=\infty.$
(3.15)

Finally, assuming the limits

$\displaystyle W_{i}^{t}:=\lim\limits_{\hbar\to 0^{+}}W_{i}^{t}(\hbar),\qquad$
$\displaystyle W_{i}^{t+1}:=\lim\limits_{\hbar\to 0^{+}}W_{i}^{t+1}(\hbar),$
$\displaystyle Q_{i}^{t}:=\lim\limits_{\hbar\to 0^{+}}Q_{i}^{t}(\hbar),\qquad$
$\displaystyle Q_{i}^{t+1}:=\lim\limits_{\hbar\to 0^{+}}Q_{i}^{t+1}(\hbar),$
(3.16)

exist, one obtains

$\displaystyle W_{i}^{t+1}=Q_{i+1}^{t}+W_{i}^{t}-Q_{i}^{t+1},\qquad
i=1,\dots,n-1,$ (3.17) $\displaystyle
Q_{i}^{t+1}=\min\Bigg{(}W_{i}^{t},\sum_{j=1}^{i}Q_{j}^{t}-\sum_{j=1}^{i-1}Q_{j}^{t+1}\Bigg{)},\qquad
i=1,\dots,n,$ (3.18) $\displaystyle W_{0}^{t}=W_{n}^{t}=\infty,$ (3.19)

which are known as the ultradiscrete Toda (udToda) equations.

###  3.6 Centre of mass

By the isospectrality of dToda (3.9), the trace is also a constant of motion
for dToda, in fact, it is a Casimir of the system. A quick computation of the
diagonal entries of $L(t)R(t)$ in (3.11) reveals that the corresponding
tropicalisation of

$\operatorname{tr}X(t)=\sum_{i=1}^{n}I_{i}^{t}+\sum_{i=1}^{n-1}V_{i}^{t}$

is

$\min\big{(}Q_{1}^{t},\dots,Q_{n}^{t},W_{1}^{t},\dots,W_{n-1}^{t}\big{)}.$

However, with the box-ball interpretation of the ultradiscretised dToda
equations, the balls are seen to be moving right. In this interpretation, one
can assign site numbers to the boxes (indexing them by $\mathbb{Z}$) and the
sum of the site numbers of the first ball in each block can be seen to grow
linearly with rate $M=\sum_{i=1}^{n}Q_{i}^{t}$ which is another constant of
motion (the tropical analogue of the determinant of $X(t)=L(t)R(t)$). This
observation is key to the main result of this paper and is stated precisely
and proved later in Lemma 7.3.

##  4 The principal embedding

###  4.1 Kostant’s theorem and the principal embedding

The matrix reformulation of the Toda lattice in Flaschka’s variables led to an
elegant Lie-theoretic method for its solution that extended to the solving of
Lax equations more generally [1, 13, 24]). This is typically referred to as
the Adler–Kostant–Symes (AKS) factorization theorem. Prior to stating that
theorem we introduce some notation related to Lie theoretic factorizations.

We consider the Lie algebra decomposition of $n\times n$ matrices

$\displaystyle\mathfrak{g}=\mathfrak{gl}(n,\mathbb{R})=\mathfrak{n}_{-}\oplus\mathfrak{b}_{+},$

where $\mathfrak{n}_{-}$ is the lower triangular nilradical subalgebra and
$\mathfrak{b}_{+}$ is a maximal solvable subalgebra, referred to as a Borel
subalgebra:

$\displaystyle\mathfrak{n}_{-}=\left(\begin{matrix}0&&&&\\\ *&0&&&\\\
\vdots&\ddots&\ddots&\ddots&\\\ \vdots&&\ddots&\ddots&\\\
*&\dots&\dots&*&0\end{matrix}\right),\qquad\mathfrak{b}_{+}=\left(\begin{matrix}*&*&\dots&\dots&*\\\
&*&*&&\vdots\\\ &&\ddots&\ddots&\vdots\\\ &&&\ddots&*\\\
&&&&*\end{matrix}\right).$

We will also use $\mathfrak{b}_{-}$, the transpose of $\mathfrak{b}_{+}$.
Employing the regular nilpotent element,

$\displaystyle\epsilon=\left(\begin{matrix}0&1&&&\\\ &0&1&&\\\
&&\ddots&\ddots&\\\ &&&\ddots&1\\\ &&&&0\end{matrix}\right)$

one defines an extended Toda phase space

$\displaystyle\epsilon+\mathfrak{b}_{-}=\left(\begin{matrix}*&1&&&\\\
*&*&1&&\\\ \vdots&\ddots&\ddots&\ddots&\\\ \vdots&&\ddots&\ddots&1\\\
*&\dots&\dots&*&*\end{matrix}\right),$

(which is the space of all lower Hessenberg matrices) on which the Toda Lax
equation (3.5) as well the discrete time Toda equation (3.9) and their
extensions will be defined. To describe explicit solutions one introduces the
natural projections

$\displaystyle\pi_{-}\colon\
\mathfrak{g}\to\mathfrak{n}_{-},\qquad\Pi_{-}\colon\ G\to N_{-},$
$\displaystyle\pi_{+}\colon\
\mathfrak{g}\to\mathfrak{b}_{+},\qquad\Pi_{+}\colon\ G\to B_{+},$

where $G={\rm GL}(n,\mathbb{R})$, $N_{-}$ is the lower unipotent matrices, is
the exponential group of the algebra $\mathfrak{n}_{-}$ and $B_{+}$ is the
invertible upper triangular matrices, is the exponential group of the algebra
$\mathfrak{b}_{+}$. $\Pi_{\pm}$ are defined on the open dense subset of $G$
where there is an $LU$-factorization.

######  Theorem 4.1 (the factorization theorem, [1, 13, 24]).

To solve

$\dfrac{{\rm d}}{{\rm d}t}X=[X,\pi_{-}(X)],\qquad X(0)=X_{0},$ (4.1)

factor ${\rm e}^{X_{0}t}=\Pi_{-}\big{(}{\rm
e}^{X_{0}t}\big{)}\Pi_{+}\big{(}{\rm e}^{X_{0}t}\big{)}$, if possible
$($locally it is$)$. Then, the solution is given by

$X(t)=\Pi_{-}^{-1}\big{(}{\rm e}^{X_{0}t}\big{)}X_{0}\Pi_{-}\big{(}{\rm
e}^{X_{0}t}\big{)}.$ (4.2)

The dynamical system (4.1) on $\epsilon+\mathfrak{b}_{-}$ is referred to as
the full Kostant–Toda lattice and, per the factorization theorem, its solution
is locally given by (4.2). The tridiagonal Hessenberg matrices are an
invariant subspace for the full Toda flow and so basic facts about the
original dynamical systems, (3.5) and (3.9), discussed in Section 3 are
directly recovered from what we do in this section.

This factorization result can be extended to discrete-time Toda. To avoid some
technical complications, in what follows, we fix the spectrum
$\lambda=(\lambda_{1},\dots,\lambda_{n})$ and assume that
$\lambda_{1}>\dots>\lambda_{n}>0$. Under this assumption one has directly the
following extension.

######  Lemma 4.2 ([5, 24, 31]).

To solve the discrete-time Toda lattice with initial condition
$X(0)\\!=\\!X_{0}$, factor ${\rm e}^{t\log
X_{0}}=X_{0}^{t}=\Pi_{-}\big{(}X_{0}^{t}\big{)}\Pi_{+}\big{(}X_{0}^{t}\big{)}$,
if possible. Then, the solution is given by

$X(t)=\Pi_{-}^{-1}\big{(}X_{0}^{t}\big{)}X_{0}\Pi_{-}\big{(}X_{0}^{t}\big{)},$

for all $t\in\mathbb{N}\cup\\{0\\}$.

These factorizations provide the basis for our analysis of the phase shift
formulas in both continuous and discrete time Toda. This is facilitated by a
key result due to Kostant that provides a natural embedding of the Toda
dynamics into a flag manifold that plays a role analogous to action-angle
variables in classical integrable systems theory.

######  Theorem 4.3 ([13]).

For each $X\in\epsilon+\mathfrak{b}_{-}$ there exists a unique lower unipotent
$L\in N_{-}$ such that $X=L\epsilon_{\lambda}L^{-1}$, where
$\epsilon_{\lambda}$ is as defined by (3.6).

Set

$\mathcal{F}_{\lambda}=\\{X\in\epsilon+\mathfrak{b}_{-}\colon\sigma(X)=\lambda_{1}>\cdots>\lambda_{n}\\},$

the isospectral manifold, and define the principal embedding into a compact,
homogeneous space, known as the flag manifold, to be

$\displaystyle\kappa_{\lambda}\colon\ \mathcal{F}_{\lambda}$ $\displaystyle\to
G/B_{+},$ $\displaystyle X$ $\displaystyle\mapsto L^{-1}\mod B_{+}.$

This mapping simultaneously linearizes and completes the Toda flows [7, 8]:

If $X_{0}=L_{0}\epsilon_{\lambda}L_{0}^{-1}$ then

$\displaystyle X(t)=\Pi_{-}^{-1}\big{(}{\rm
e}^{tX_{0}}\big{)}X_{0}\Pi_{-}\big{(}{\rm
e}^{tX_{0}}\big{)}=\Pi_{-}^{-1}\big{(}{\rm
e}^{tX_{0}}\big{)}L_{0}\epsilon_{\lambda}L_{0}^{-1}\Pi_{-}\big{(}{\rm
e}^{tX_{0}}\big{)},$
$\displaystyle\kappa_{\lambda}(X(t))=L_{0}^{-1}\Pi_{-}\big{(}{\rm
e}^{tX_{0}}\big{)}\mod B_{+}$
$\displaystyle\hphantom{\kappa_{\lambda}(X(t))}{}=L_{0}^{-1}\big{(}{\rm
e}^{tX_{0}}\big{)}\mod B_{+}$
$\displaystyle\hphantom{\kappa_{\lambda}(X(t))}{}={\rm
e}^{\epsilon_{\lambda}t}L_{0}^{-1}\mod B_{+}.$

Thus, one sees that under the principal embedding, the Toda flow maps to a
linear semigroup action by ${\rm e}^{\epsilon_{\lambda}t}$ on $G/B_{+}$
through the principal image of the initial value,
$\kappa_{\lambda}(X_{0})=L_{0}^{-1}$ which exists for all time.

In Remark 3.2 we pointed out that the continuous Toda flow commutes with the
discrete time Toda evolution. In fact, there is a hierarchy of continuous
flows commuting with dToda and with one another given by Lax equations of the
form

$\displaystyle\frac{{\rm d}}{{\rm d}t_{m}}X=\big{[}X,\pi_{-}X^{m}\big{]}.$
(4.3)

On $\mathcal{F}_{\lambda}$ the first $n-1$ of these flows are locally
independent and their respective images under the principal embedding has the
form

${\rm e}^{\epsilon^{m}_{\lambda}t_{m}}L_{0}^{-1}\mod B_{+}$

and together they generate a torus action on $G/B_{+}$ [8] (see Section
4.2.2).

###  4.2 The fundamental element $\boldsymbol{\epsilon_{\lambda}}$

As mentioned earlier, we are going to see that the Toda flow limits to
$\epsilon_{\lambda}$ (3.6) in large forward time. This element is
distinguished by the fact that it lies in the intersection
$(\epsilon+\mathfrak{b}_{-})_{\lambda}\cap\mathfrak{b_{+}}$, and in that
regard it is essentially unique. (There are $n!$ elements in this intersection
corresponding to permutations of the distinct eigenvalues. In fact in large
backwards time the Toda flow limits to the element corresponding to the
longest permutation.) Since this element will play such a central role in our
initial calculations, we take a few moments to discuss some of its relevant
features.

####  4.2.1 Diagonalizing $\boldsymbol{\epsilon_{\lambda}}$

Because we assume $\lambda_{i}\neq\lambda_{j}$ for all $i\neq j$, we can of
course diagonalise any matrix in $\mathcal{F}_{\lambda}$. The following
result, which is an explicit form of Lemma 7 in [7], describes a
diagonalisation of $\epsilon_{\lambda}$.

######  Lemma 4.4.

If $\lambda_{1},\dots,\lambda_{n}$ are distinct, then one has
$\epsilon_{\lambda}=UD_{\lambda}U^{-1}$, where $U=(u_{ij})$ is the upper
triangular matrix given by

$u_{ij}=\prod_{k=1}^{i-1}(\lambda_{j}-\lambda_{k}),\qquad 1\leq i\leq j\leq
n,$

and
$D_{\lambda}=\epsilon_{\lambda}-\epsilon=\operatorname{diag}(\lambda_{1},\dots,\lambda_{n})$.

###### Proof.

The matrix $U$ is clearly invertible since

$\det(U)=\prod_{i=1}^{n}\prod_{k=1}^{i-1}(\lambda_{i}-\lambda_{k})=\prod_{1\leq
k<i\leq n}(\lambda_{i}-\lambda_{k})$

and as stated above, we have assumed $\lambda_{i}\neq\lambda_{j}$ for all
$i\neq j$.

It just remains to show that $\epsilon_{\lambda}U=UD_{\lambda}$. Let
$u_{j}=(u_{ij})_{1\leq i\leq n}$ be the $j$-th column of $U$, then for $i<n$:

$\displaystyle(\epsilon_{\lambda}u_{j})_{i}$
$\displaystyle=\sum_{k=1}^{n}(\epsilon_{\lambda})_{ik}u_{kj}=\lambda_{i}u_{ij}+u_{i+1,j}=\lambda_{i}\prod_{k=1}^{i-1}(\lambda_{j}-\lambda_{k})+\prod_{k=1}^{i}(\lambda_{j}-\lambda_{k})$
$\displaystyle=(\lambda_{i}+\lambda_{j}-\lambda_{i})\prod_{k=1}^{i-1}(\lambda_{j}-\lambda_{k})=\lambda_{j}\prod_{k=1}^{i-1}(\lambda_{j}-\lambda_{k})=\lambda_{j}(u_{j})_{i}.$

For $i=n$, we simply have

$\displaystyle(\epsilon_{\lambda}u_{j})_{n}=\lambda_{n}(u_{j})_{n}=\begin{cases}0,&j<n,\\\
\lambda_{j}(u_{j})_{n},&j=n\end{cases}=\lambda_{j}(u_{j})_{n}.$

Thus, $\epsilon_{\lambda}u_{j}=\lambda_{j}u_{j}$ for each $j$. ∎

######  Remark 4.5.

In the remainder of this paper, it is convenient to work with a unipotent
matrix of eigenvectors for $\epsilon_{\lambda}$. Since $U$ is triangular, we
achieve this by scaling each column of the matrix $U$ by the reciprocal of the
diagonal entry for that column. The result is that we can choose

$(U)_{ij}=\begin{cases}\displaystyle\prod\limits_{i\leq
m<j}\dfrac{1}{\lambda_{j}-\lambda_{m}}&\text{for }i\leq j,\\\
0&\text{otherwise},\end{cases}$

and still maintain $\epsilon_{\lambda}=UD_{\lambda}U^{-1}$. From now on, $U$
shall refer to this upper unipotent matrix.

####  4.2.2 Eigenvectors and the torus embedding

In this section we describe a slight modification of the principal embedding
which displays more clearly the linearized character of the Toda flows that
these embeddings reveal. This is the homogeneous space analogue of the
linearization in terms of action-angle variables familiar from classical
integrable systems theory [3].

Combining Lemma 4.4 with Theorem 4.3 provides a diagonalization of
$X\in\epsilon+\mathfrak{b}_{-}$:

$\displaystyle X=LUD_{\lambda}U^{-1}L^{-1}.$ (4.4)

Cross-multiplying in two different ways this is equivalent to each of two
different representations

$\displaystyle\big{(}U^{-1}L^{-1}\big{)}X=D_{\lambda}\big{(}U^{-1}L^{-1}\big{)},$
(4.5) $\displaystyle X(LU)=(LU)D_{\lambda}.$ (4.6)

The representation in (4.5) presents $\big{(}U^{-1}L^{-1}\big{)}$ as a matrix
whose rows are the left eigenvectors of $X$ while (4.6) presents $(LU)$ as a
matrix whose columns are the right eigenvectors of $X$. Based on this one is
led to consider an alternative flag manifold embedding,

$\displaystyle\operatorname{tor}_{\lambda}\colon\ \mathcal{F}_{\lambda}$
$\displaystyle\to G/B_{+},$ $\displaystyle X$ $\displaystyle\mapsto
U^{-1}L^{-1}\mod B_{+}$

from $X$ to its matrix of left eigenvectors. As before one can track the Toda
dynamics through this embedding and find that

$\displaystyle\operatorname{tor}_{\lambda}(X(t))={\rm
e}^{tD_{\lambda}}U^{-1}L^{-1}\mod B_{+}.$

Also, as before, this can be extended to the commuting hierarchy of Toda flows
(4.3),

$\displaystyle\operatorname{tor}_{\lambda}(X(t_{1},\dots,t_{n}))=\exp\left({\sum_{m=1}^{n-1}t_{m}D^{m}_{\lambda}}\right)U^{-1}L^{-1}\mod
B_{+}.$

This amounts to a toric action (left multiplication by $(\mathbb{R}^{*})^{n}$)
on the flag manifold, explaining why $\operatorname{tor}_{\lambda}$ is
referred to as the torus embedding. This is a replacement of the nonlinear
Toda dynamics by a linear semigroup action on $G/B_{+}$.

####  4.2.3 Other Lie algebras

The language we have used in this section to describe the Toda phase space and
dynamics (Borel and nilradical subalgebras, regular nilpotent elements) have
immediate extensions to the setting of general real semisimple Lie algebras to
define the so-called generalized Toda lattices [14]. The structure and results
about the flag manifold embeddings was similarly carried out in [8]. Kostant
also introduces the analogue of $\epsilon_{\lambda}$ in Theorem 1.5 of [14]
and its diagonalization (Lemma 3.52).

###  4.3 Painlevé balances

It was pointed out in Theorem 4.1 that lower-upper factorization of ${\rm
e}^{tX_{0}}$ does not necessarily hold for all values of $t$. When this
happens some entry of $X(t)$ will become infinite. In fact these entries are
meromorphic (which fact is referred to as the Painlevé property). We refer to
[11] for further details about this. But as we saw in the previous section,
the evolution under the torus embedding is just a multi-scaling action in the
flag manifold, which is compact, and so the flows exist for all time. A
geometric understanding of what is happening is provided by the Birkhoff cell
decomposition of $G/B_{+}$. The flag manifold may be written as a disjoint
union,

$\displaystyle G/B_{+}=\bigcup_{\widehat{w}\in W}N_{-}\widehat{w}B_{+}/B_{+}.$

In this representation, $W$ is the group of $n\times n$ permutation matrices.
The $n!$ sets, $N_{-}\widehat{w}B_{+}/B_{+}$, are cells (homeomorphic to a
Euclidean space) called Birkhoff cells. The cell $N_{-}B_{+}/B_{+}$ is open
and dense in $G/B_{+}$ and referred to as the “big cell”. The other cells are
lower dimensional with co-dimension equal to the length of $\widehat{w}$
(corresponding to the minimal number of pivots required to carry out Gaussian
elimination of a representative group element for a point in that cell). By
Kostant’s theorem 4.3, all elements of $\epsilon+\mathfrak{b}_{-}$ embed into
the big cell. Under the Toda flow, “blow-up” of $X(t)$ occurs precisely when
${\rm e}^{tX_{0}}$ cannot be factored. However, under $\kappa_{\lambda}$, this
flow simply continues to a smaller Birkhoff cell corresponding to the sequence
of pivots required to perform Gaussian elimination on ${\rm e}^{tX_{0}}$. Thus
the singularity is “resolved” and the flow may be continued to arbitrary
times. A similar statement applies to the flows of the full Toda hierarchy. A
consequence of this observation is that the meromorphic singularity structure
of the Toda lattice solutions may be explicitly described as follows.

######  Proposition 4.6 ([11]).

Let $\Theta\subseteq\\{1,\dots,n-1\\}$ be nonempty. There is a Laurent series
solution of equations (3.3)–(3.4) having the form

$\displaystyle b_{j}(t)=-\frac{\sigma_{j}^{\Theta}}{t^{2}}+\text{$($Taylor$)$
near}\ t=0,\qquad\text{if }j\in\Theta,$ $\displaystyle
b_{j}(t)=\text{$($Taylor$)$ near}\ t=0,\qquad\text{if }j\not\in\Theta.$

This solution depends on $2(n-1)-|\Theta|$ free parameters.

Each type of series in the proposition is called a Painlevé balance $\Theta$
of dimension equal to the number of free parameters.

######  Corollary 4.7 ([11]).

When $\Theta=\\{1,\dots,n-1\\}$, which is called the lowest balance, its
dimension is $2(n-1)-(n-1)=n-1$.

######  Corollary 4.8 ([7]).

Restricted to the isospectral manifold $\mathcal{F}_{\lambda}$, the Toda flow,
${\rm e}^{\epsilon_{\lambda}t}\widehat{w}_{0}$, passes through
$\widehat{w}_{0}\mod B_{+}$ as $t\to 0$, where $\widehat{w}_{0}$ denotes the
permutation matrix for the reverse permutation, i.e., the longest permutation

###  4.4 Centering the tridiagonal flows

In the remainder of this paper we will restrict attention to the tridiagonal
flows we began with in Section 3 but largely view them in terms of their
embedding in the flag manifold, $G/B_{+}$.

The phase shift formulas we describe do not depend on initial conditions. We
have already seen this reflected in the fact (see Section 3.2) that the total
momentum is a constant (in fact a Casimir) for the motion. Knowing this, it is
helpful to choose an initial point that is appropriately “centered” in the
flag manifold. The centering we use is based on Corollary 4.8. This centering,
based on a different argument, was also used in [21].

Motivated by the discussion at the end of the previous subsection, one begins
with an upper triangular matrix of the form

$b_{0}:=\exp\left(\sum_{i=1}^{n-1}\epsilon_{\lambda}^{i}t_{i}\right),$ (4.7)

where the values of the $t_{i}$ are fixed. Next consider

$b(t)={\rm e}^{\epsilon_{\lambda}t}b_{0},$

where $t$ is the Toda time parameter. Finally, we define from this a path in
$N_{-}$ via

$L(t)=\Pi_{-}\big{[}b(t)\widehat{w}_{0}\big{]}.$

In [7] it is shown that

$b(t)~{}\mapsto~{}L(t)^{-1}\epsilon_{\lambda}L(t)\in\mathcal{F}_{\lambda}.$

$X(t)=L(t)^{-1}\epsilon_{\lambda}L(t)$ solves (3.5) and as the parameters
$t_{i}$ are varied one sweeps out all isospectral solutions. The center of
this invariant set, corresponding to all $t_{i}=0$ is the point which is the
smallest Birkhoff cell in $G/B_{+}$.

##  5 Representation theory and $\boldsymbol{\tau}$-functions

Let $G$ denote the group ${\rm GL}(\ell+1)$ and let $(\rho_{n},V_{n})$ denote
the $n^{\rm th}$ fundamental representation of $G$. $\rho_{1}$ is the birth
representation with $V_{1}=\mathbb{C}^{\ell+1}$ defined by

$\rho_{1}(g)v=gv$

for $v\in V_{1}$. This induces a representation on the exterior algebra of
$V_{1}$ that defines the remaining fundamental representations, respectively,
on $V_{n}=\bigwedge^{n}\mathbb{C}^{\ell+1}$ given by

$\rho_{n}(g)v_{1}\wedge\dots\wedge v_{n}=gv_{1}\wedge\dots\wedge gv_{n}.$

With respect to the standard basis $e_{1},\dots,e_{\ell+1}$ of
$\mathbb{C}^{\ell+1}$ one defines a Hermitian inner product on $V_{n}$ by

$\langle e_{i_{1}}\wedge\dots\wedge e_{i_{n}},e_{j_{1}}\wedge\dots\wedge
e_{j_{n}}\rangle=\delta_{i_{1},j_{1}}\cdots\delta_{i_{n},j_{n}}.$

Set $v^{(n)}=e_{1}\wedge\dots\wedge e_{n}$ and
$v_{(n)}=e_{\ell-n+2}\wedge\dots\wedge e_{\ell+1}$. These are, respectively,
the highest and lowest weight vectors, with respect to lexicographic order, of
the representation $\rho_{n}$ [12].

We can now define the $n^{\rm th}$ $\tau$-function to be

$\tau_{n}(t)=\big{\langle}\exp(tX_{0})v^{(n)},v^{(n)}\big{\rangle},$

which is just the $n^{\rm th}$ principal minor of $\exp{tX_{0}}$.

The solution of the Toda lattice equations in Hessenberg form is then given
explicitly by

$\displaystyle
b_{n}(t)=b_{n}(0)\frac{\tau_{n-1}(t)\tau_{n+1}(t)}{\tau_{n}^{2}(t)},$ (5.1)
$\displaystyle a_{n}(t)=\frac{{\rm d}}{{\rm
d}t}\big{(}\log\tau_{n}(t)-\log\tau_{n-1}(t)\big{)}.$

##  6 Toda phase shift in terms of weighted path counting

We now come to our novel derivation of the phase shift formula for the
continuous time Toda lattice. The original derivation was due to Moser [20]
based on a continued fraction representation. Subsequently, Kostant [14] gave
a fully Lie theoretic derivation. Here we present a direct combinatorial
derivation based on the lemma of Gessel, Viennot and Lindström for enumerating
weighted paths in directed graphs. We feel this approach is less ad hoc than
Moser’s and less technical than Kostant’s while capturing the essential
connection to the principal embedding through $\epsilon_{\lambda}$. This also
makes it more amenable to ultradiscretization which is the main result of this
paper and to future generalizations to other box ball systems.

The full details of our derivation are in the Appendices; this chapter just
summarizes the essential results of that analysis, in Lemmas 6.3 and 6.4,
Corollary 6.5, and shows how to use these to derive the continuous time phase
shift. It is then straightforward, based on what we have already shown, to
modify this formula for discrete time Toda (which is carried out in Section
6.2).

Moser’s phase shift, in terms of the original Hamiltonian variables (see (3.7)
and (3.8)), is given by

$\beta_{n-k+1}^{+}=\beta_{k}^{-}+\sum_{j\neq k}\phi_{jk}(\alpha^{-}),$

where

$\displaystyle\phi_{jk}(\alpha^{-})=\begin{cases}\log(\alpha_{j}^{-}-\alpha_{k}^{-})^{2}&\text{for
}j<k,\\\ -\log(\alpha_{j}^{-}-\alpha_{k}^{-})^{2}&\text{for
}j>k\end{cases}=\begin{cases}\log(\lambda_{n-k+1}-\lambda_{n-j+1})^{2}&\text{for
}j<k,\\\ -\log(\lambda_{n-k+1}-\lambda_{n-j+1})^{2}&\text{for
}j>k.\end{cases}$

We reformulate this in terms of the Hessenberg matrix form of Flaschka’s
variables where it becomes equivalent to an elegant pairwise multiplicative
formula for the sub-diagonal entries.

We have

$b_{k}(-t)={\rm e}^{q_{k}(-t)-q_{k+1}(-t)}={\rm
e}^{(\lambda_{n-k+1}-\lambda_{n-k})t}{\rm
e}^{\beta_{k}^{-}-\beta_{k+1}^{-}+O({\rm e}^{-\delta t})},$

and

$b_{n-k}(t)={\rm e}^{q_{n-k}(t)-q_{n-k+1}(t)}={\rm
e}^{(\lambda_{n-k+1}-\lambda_{n-k})t}{\rm
e}^{\beta_{n-k}^{+}-\beta_{n-k+1}^{+}+O({\rm e}^{-\delta t})}.$

Then consider

$\displaystyle\lim_{t\to+\infty}b_{n-k}(t)b_{k}(-t){\rm
e}^{2(\lambda_{n-k}-\lambda_{n-k+1})t}={\rm
e}^{(\beta_{n-k}^{+}-\beta_{k+1}^{-})-(\beta_{n-k+1}^{+}-\beta_{k}^{-})}$
$\displaystyle\qquad{}=\exp\Bigg{(}\sum_{j\neq
k+1}\phi_{j,k+1}(\alpha^{-})-\sum_{j\neq k}\phi_{j,k}(\alpha^{-})\Bigg{)}$
$\displaystyle\qquad{}=\exp\Bigg{(}\Bigg{(}\sum_{j<k+1}\log(\lambda_{n-k}-\lambda_{n-j+1})^{2}-\sum_{j>k+1}\log(\lambda_{n-k}-\lambda_{n-j+1})^{2}\Bigg{)}$
$\displaystyle\qquad\quad{}-\sum_{j<k}\log(\lambda_{n-k+1}-\lambda_{n-j+1})^{2}+\sum_{j>k}\log(\lambda_{n-k+1}-\lambda_{n-j+1})^{2}\Bigg{)}$
$\displaystyle\qquad{}=\dfrac{\prod\limits_{j<k+1}(\lambda_{n-k}-\lambda_{n-j+1})^{2}\prod\limits_{j>k}(\lambda_{n-k+1}-\lambda_{n-j+1})^{2}}{\prod\limits_{j>k+1}(\lambda_{n-k}-\lambda_{n-j+1})^{2}\prod\limits_{j<k}(\lambda_{n-k+1}-\lambda_{n-j+1})^{2}}.$

This leads us to the following analogue of the Moser’s phase shift formula for
the off-diagonal entries, but in the Hessenberg setting:

######  Theorem 6.1.

In the Hessenberg setting, the following asymptotic formula holds for the
subdiagonal entries of the Toda flow:

$\displaystyle\lim\limits_{t\to+\infty}b_{n-k}(t)b_{k}(-t){\rm
e}^{2(\lambda_{n-k}-\lambda_{n-k+1})t}=\dfrac{\prod\limits_{j<k+1}\\!(\lambda_{n-k}-\lambda_{n-j+1})^{2}\\!\prod\limits_{j>k}\\!(\lambda_{n-k+1}-\lambda_{n-j+1})^{2}}{\prod\limits_{j>k+1}\\!(\lambda_{n-k}-\lambda_{n-j+1})^{2}\\!\prod\limits_{j<k}\\!(\lambda_{n-k+1}-\lambda_{n-j+1})^{2}}.\\!\\!\\!$
(6.1)

Although the analogy between this theorem and Moser’s original result is
apparent, we will provide a novel proof for this result. This analysis
proceeds from a direct deconstruction of $\tau$-functions appearing in the
representation (5.1).

Recall that

$\epsilon_{\lambda}=\left[\begin{matrix}\lambda_{1}&1\\\
&\lambda_{2}&\ddots\\\ &&\ddots&1\\\
&&&\lambda_{n}\end{matrix}\right]=\epsilon+D_{\lambda},$

where $D_{\lambda}=\operatorname{diag}(\lambda_{1},\dots,\lambda_{n})$ and,
from Remark 4.5, that it is diagonalised by the matrix

$(U)_{ij}=\begin{cases}\displaystyle\prod\limits_{i\leq
m<j}\dfrac{1}{\lambda_{j}-\lambda_{m}}&\text{for }i\leq j,\\\
0&\text{otherwise},\end{cases}$

so that

$\epsilon_{\lambda}=UD_{\lambda}U^{-1}.$

We also recall here notation used by [21] for describing certain minor
determinants of matrices:

######  Definition 6.2.

For an $n\times n$ matrix $X$ and $1\leq k\leq m\leq n$, define

$\Delta_{k}^{m}(X)=\det[x_{ij}]_{1\leq i\leq k,m-k+1\leq j\leq m},$

where, by convention, $\Delta_{0}^{m}(X)$ is taken to be $1$. In the
particular case that $m=n$, $\Delta_{k}^{n}(X)$ is the top-right $k\times k$
minor determinant of $X$.

In proving Theorem 6.1, the following three results will be key:

######  Lemma 6.3.

$\Delta_{k}^{n}(U)=\prod_{i=n-k+1}^{n}\prod_{j=1}^{n-k}\dfrac{1}{\lambda_{j}-\lambda_{i}}.$

######  Lemma 6.4.

$(U^{-1})_{ij}=\begin{cases}0&i>j,\\\ \displaystyle\prod_{i<m\leq
j}\dfrac{1}{\lambda_{i}-\lambda_{m}}&i\leq j.\end{cases}$

######  Corollary 6.5.

$\Delta_{k}^{n}(U^{-1})=\prod_{j=1}^{k}\prod_{i=k+1}^{n}\dfrac{1}{\lambda_{j}-\lambda_{i}}.$

Corollary 6.5 will later be shown to follow from Lemmas 6.3 and 6.4.

###  6.1 Proof of multiplicative formula for the classical Toda phase shift

We recall the level set parametrisation (4.7)

$b_{0}:=\exp\left(\sum_{i=1}^{n-1}\epsilon_{\lambda}^{i}t_{i}\right),$

with $\lambda_{1}>\lambda_{2}>\cdots>\lambda_{n}$, define
$L_{0}:=\Pi_{-}(b_{0}\widehat{w}_{0})$, and let
$X_{0}:=L_{0}^{-1}\epsilon_{\lambda}L_{0}$ be the initial Hessenberg matrix.

######  Lemma 6.6.

For each $k$, one has

$b_{k}(0)=\dfrac{\Delta_{k+1}^{n}(b_{0})\Delta_{k-1}^{n}(b_{0})}{(\Delta_{k}^{n}(b_{0}))^{2}}.$

###### Proof.

Define $B_{0}=\Pi_{+}(b_{0}\widehat{w}_{0})$, so that
$b_{0}\widehat{w}_{0}=L_{0}B_{0}$. Then

$\displaystyle B_{0}^{-1}X_{0}B_{0}$
$\displaystyle=(L_{0}B_{0})^{-1}\epsilon_{\lambda}L_{0}B_{0}=\widehat{w}_{0}^{-1}b_{0}^{-1}\epsilon_{\lambda}b_{0}\widehat{w}_{0}$
$\displaystyle=\widehat{w}_{0}^{-1}U{\rm
e}^{-\sum\limits_{i=1}^{n-1}t_{i}D_{\lambda}^{i}}U^{-1}UD_{\lambda}U^{-1}U{\rm
e}^{\sum\limits_{i=1}^{n-1}t_{i}D_{\lambda}^{i}}U^{-1}\widehat{w}_{0}$
$\displaystyle=\widehat{w}_{0}^{-1}UD_{\lambda}U^{-1}\widehat{w}_{0}=\widehat{w}_{0}^{-1}\epsilon_{\lambda}\widehat{w}_{0}.$

From this, we see that

$X_{0}=B_{0}\widehat{w}_{0}^{-1}\epsilon_{\lambda}\widehat{w}_{0}B_{0}^{-1}.$

Splitting $\epsilon_{\lambda}=\epsilon+D_{\lambda}$, we study
$\widehat{w}_{0}^{-1}\epsilon_{\lambda}\widehat{w}_{0}$ as follows

$\displaystyle\widehat{w}_{0}^{-1}\epsilon_{\lambda}\widehat{w}_{0}=\widehat{w}_{0}^{-1}\epsilon\widehat{w}_{0}+\widehat{w}_{0}^{-1}D_{\lambda}\widehat{w}_{0}.$

By recalling that

$\widehat{w}_{0}=\left[\begin{matrix}&&&&1\\\ &&&1\\\ &&1\\\ &\iddots\\\
1\end{matrix}\right],$

one can check that
$\widehat{w}_{0}^{-1}\epsilon_{\lambda}\widehat{w}_{0}=\hat{\epsilon}_{\lambda}$,
where

$\hat{\epsilon}_{\lambda}=\left[\begin{matrix}\lambda_{n}\\\
1&\lambda_{n-1}\\\ &1&\ddots\\\ &&\ddots&\lambda_{2}\\\
&&&1&\lambda_{1}\end{matrix}\right].$

If one writes

$B_{0}=\left[\begin{matrix}d_{1}&&*\\\ &d_{2}\\\ &&\cdots\\\
&&&d_{n}\end{matrix}\right],$

then

$X_{0}=B_{0}\hat{\epsilon}_{\lambda}B_{0}^{-1}=\left[\begin{matrix}*&&&&*\\\
d_{2}d_{1}^{-1}&*\\\ &d_{3}d_{2}^{-1}&\ddots\\\ &&\ddots&*&\\\
&&&d_{n}d_{n-1}^{-1}&*\end{matrix}\right].$

To conclude, we recall that the diagonal part of $L_{0}B_{0}$, which is
$\operatorname{diag}(B_{0})$, is given by

$d_{j}=\frac{\tau_{j}}{\tau_{j-1}},$

where $\tau_{j}$ is the $j\times j$ principal minor of $b_{0}\widehat{w}_{0}$,
hence $\tau_{j}=\Delta_{j}^{n}(b_{0})$. ∎

######  Remark 6.7.

We note here that $b_{0}$ is a totally positive element of $B_{+}$. (A matrix
$b\in B_{+}$ is defined to be totally positive with respect to $B_{+}$ if
every minor that does not identically vanish on $B_{+}$ has a positive value.)
The evident relation between principal minors of $b_{0}\widehat{w}_{0}$ and
upper-right minors of $b_{0}$ reflects a deeper combinatorial relation studied
by Lusztig [4, 18]. This enables one to associate a kind of notion of
positivity to elements of $\epsilon+\mathfrak{b}_{-}$ (Hessenberg matrices).

Using the previous lemma and prior definitions we now proceed to expand the
$\tau$-functions in terms of Plücker coordinates (minors) of $U$ and $U^{-1}$.
In this derivation we employ the refinement of the $LU$-decomposition to the
$LDU$-decomposition for generic $g\in G$:

$g=[g]_{-}[g]_{0}[g]_{+},$

where $[g]_{-}\in N_{-},[g]_{0}$ is diagonal and $[g]_{+}\in N_{+}$, the
subgroup of upper unipotent matrices.

We now proceed to the deconstruction of $\tau_{k}$ with a brief explanation of
the steps given at the end

$\displaystyle\tau_{k}(t)$ $\displaystyle=\big{\langle}{\rm
e}^{tX_{0}}v^{(k)},v^{(k)}\big{\rangle}$ (6.2)
$\displaystyle=\big{\langle}L_{0}^{-1}U{\rm
e}^{tD_{\lambda}}U^{-1}L_{0}v^{(k)},v^{(k)}\big{\rangle}$ (6.3)
$\displaystyle=\big{\langle}U{\rm
e}^{tD_{\lambda}}U^{-1}[b_{0}\widehat{w}_{0}]_{-}v^{(k)},v^{(k)}\big{\rangle}$
(6.4) $\displaystyle=\big{\langle}U{\rm
e}^{tD_{\lambda}}U^{-1}b_{0}\widehat{w}_{0}[b_{0}\widehat{w}_{0}]_{+}^{-1}[b_{0}\widehat{w}_{0}]_{0}^{-1}v^{(k)},v^{(k)}\big{\rangle}$
(6.5) $\displaystyle=\left(\prod_{j=1}^{k}d_{j}^{-1}\right)\big{\langle}U{\rm
e}^{tD_{\lambda}}U^{-1}b_{0}\widehat{w}_{0}v^{(k)},v^{(k)}\big{\rangle}$ (6.6)
$\displaystyle=\left(\prod_{j=1}^{k}d_{j}^{-1}\right)\big{\langle}U{\rm
e}^{tD_{\lambda}}U^{-1}b_{0}v_{(k)},v^{(k)}\big{\rangle}$ (6.7)
$\displaystyle=\left(\prod_{j=1}^{k}d_{j}^{-1}\right)\left\langle U{\rm
e}^{tD_{\lambda}}U^{-1}\exp\left(\sum_{i=1}^{n-1}\epsilon_{\lambda}^{i}t_{i}\right)v_{(k)},v^{(k)}\right\rangle$
(6.8) $\displaystyle=\left(\prod_{j=1}^{k}d_{j}^{-1}\right)\left\langle
U\exp\left(\sum_{i=1}^{n-1}D_{\lambda}^{i}(t_{i}+\delta_{i1}t)\right)U^{-1}v_{(k)},v^{(k)}\right\rangle.$
(6.9)

In (6.3), the diagonalization (4.4) was applied to $X_{0}$ to express it as
$X_{0}=L_{0}^{-1}UD_{\lambda}U^{-1}L_{0}$. In step (6.4), $L_{0}^{-1}$ is
transposed to the right-hand side of the bracket, where it is an upper
unipotent matrix acting on the highest weight vector $v^{(k)}$ and therefore
has no effect. Similarly, from its definition, $L_{0}$ may be replaced by
$[b_{0}\widehat{w}_{0}]_{-}$ which is then rewritten in (6.5) using the
$LDU$-decomposition. This then contracts to (6.6) where $d_{j}$ is the $j$-th
entry along the diagonal of $[b_{0}\widehat{w}_{0}]_{0}$. The reverse
permutation $\widehat{w}_{0}$ moves the highest weight vector to the lowest
weight vector in (6.7). Finally, the last two steps follow from the definition
of $b_{0}$ and the diagonalization of $\epsilon_{\lambda}$, respectively.

By a well-known result from linear algebra (see, for example, [22]), $d_{j}$
is given by

$d_{j}=\dfrac{\Delta_{j}^{n}(b_{0})}{\Delta_{j-1}^{n}(b_{0})}.$

Thus, the factor in front of the inner product is equal to
$(\Delta_{k}^{n}(b_{0}))^{-1}$.

By the Cauchy–Binet formula, we get

$\displaystyle\tau_{k}(t)$
$\displaystyle=\dfrac{1}{\Delta_{k}^{n}(b_{0})}\sum_{S\in{[n]\choose
k}}\det\left(U\exp\left(\sum_{i=1}^{n-1}D_{\lambda}^{i}(t_{i}+\delta_{i1}t)\right)\right)_{[k],S}\det\big{(}U^{-1}\big{)}_{S,]k[}$
$\displaystyle=\dfrac{1}{\Delta_{k}^{n}(b_{0})}\sum_{S\in{[n]\choose
k}}\exp\left(\sum_{s\in
S}\sum_{i=1}^{n}\lambda_{s}^{i}(t_{i}+\delta_{i1}t)\right)\det(U_{[k],S})\det\big{(}U^{-1}_{S,]k[}\big{)},$

where $]k[{}:=\\{n-k+1,n-k+2,\dots,n\\}$.

There are two limits we wish to consider for the $\tau$-functions in what
follows. One of these is the limit in which $t$ tends to infinity while the
eigenvalues, $\lambda_{i}$ remain fixed and the other is the tropical limit in
the eigenvalues while $t$ is held fixed. In the former case, given the
ordering $\lambda_{1}>\lambda_{2}>\cdots>\lambda_{n}$, the term for $S=[k]$
dominates as $t\to+\infty$, and the term for $S={}]k[$ dominates as
$t\to-\infty$. In the latter case, these same terms dominate for $t$ fixed
sufficiently positive and, respectively, for $t$ fixed sufficiently negative.
The only wrinkle in the latter case is that the minors $\det(U_{[k],S})$ and
$\det\big{(}U^{-1}_{S,]k[}\big{)}$ depend on the eigenvalues. However, the
growth of these terms is algebraic and may be crudely estimated to be no worse
than $\lambda_{1}^{2k}$ in one direction and $\lambda_{n}^{2k}$ in the other.
This algebraic growth is beaten by the exponential decay of the time-dependent
factors in the tropical limit once the exponential factor associated to
$S=[k]$, respectively for $S={}]k[$ has been factored out of the Cauchy–Binet
sum. Since in both the $t$ and the tropical limits it is the same single term
that dominates, the two limits manifestly commute.

Focusing now on the $t$ limit, we let $\tau_{k}^{+}$ and $\tau_{k}^{-}$ denote
these terms, respectively. By Lemma 6.3 and Corollary 6.5, we have

$\tau_{k}^{+}=\dfrac{1}{\Delta_{k}^{n}(b_{0})}\exp\left(\sum_{s=1}^{k}\sum_{i=1}^{n}\lambda_{s}^{i}(t_{i}+\delta_{i1}t)\right)\prod_{j=1}^{k}\prod_{i=k+1}^{n}\dfrac{1}{\lambda_{j}-\lambda_{i}}+o(1)$

and

$\tau_{k}^{-}=\dfrac{1}{\Delta_{k}^{n}(b_{0})}\exp\left(\sum_{s=n-k+1}^{n}\sum_{i=1}^{n}\lambda_{s}^{i}(t_{i}-\delta_{i1}t)\right)\prod_{i=n-k+1}^{n}\prod_{j=1}^{n-k}\dfrac{1}{\lambda_{j}-\lambda_{i}}+o(1).$

As $t\to+\infty$, we therefore have

$b_{k}(-t)\sim
b_{k}^{-}:=b_{k}(0)\dfrac{\tau_{k+1}^{-}\tau_{k-1}^{-}}{(\tau_{k}^{-})^{2}},\qquad
b_{n-k}(t)\sim
b_{n-k}^{+}:=b_{n-k}(0)\dfrac{\tau_{n-k+1}^{+}\tau_{n-k-1}^{+}}{(\tau_{n-k}^{+})^{2}}.$

Plugging in, and writing $\Delta_{j}$ for $\Delta_{j}^{n}(b_{0})$, we have

$\displaystyle
b_{k}^{-}=b_{k}(0)\dfrac{(\Delta_{k})^{2}}{\Delta_{k-1}\Delta_{k+1}}\exp\left(\sum_{i=1}^{n}(\lambda_{n-k}^{i}-\lambda_{n-k+1}^{i})(t_{i}-\delta_{i1}t)\right)\times\Upsilon_{k}^{-},$

where

$\Upsilon_{k}^{-}=\dfrac{\left(\prod\limits_{i=n-k}^{n}\prod\limits_{j=1}^{n-k-1}\dfrac{1}{\lambda_{j}-\lambda_{i}}\right)\left(\prod\limits_{i=n-k+2}^{n}\prod\limits_{j=1}^{n-k+1}\dfrac{1}{\lambda_{j}-\lambda_{i}}\right)}{\left(\prod\limits_{i=n-k+1}^{n}\prod\limits_{j=1}^{n-k}\dfrac{1}{\lambda_{j}-\lambda_{i}}\right)^{2}}$

and

$\displaystyle
b_{n-k}^{+}=b_{n-k}(0)\dfrac{(\Delta_{n-k})^{2}}{\Delta_{n-k-1}\Delta_{n-k+1}}\exp\left(\sum_{i=1}^{n}(\lambda_{n-k+1}^{i}-\lambda_{n-k}^{i})(t_{i}+\delta_{i1}t)\right)\times\Upsilon_{n-k}^{+},$

where

$\Upsilon_{n-k}^{+}=\dfrac{\left(\prod\limits_{j=1}^{n-k+1}\prod\limits_{i=n-k+2}^{n}\dfrac{1}{\lambda_{j}-\lambda_{i}}\right)\left(\prod\limits_{j=1}^{n-k-1}\prod\limits_{i=n-k}^{n}\dfrac{1}{\lambda_{j}-\lambda_{i}}\right)}{\left(\prod\limits_{j=1}^{n-k}\prod\limits_{i=n-k+1}^{n}\dfrac{1}{\lambda_{j}-\lambda_{i}}\right)^{2}}.$

Simplifying $\Upsilon_{k}^{-}$ and $\Upsilon_{n-k}^{+}$, one has

$\Upsilon_{k}^{-}=\dfrac{\left[\prod\limits_{i<n-k+1}(\lambda_{i}-\lambda_{n-k+1})\right]\left[\prod\limits_{i>n-k}(\lambda_{n-k}-\lambda_{i})\right]}{\left[\prod\limits_{i<n-k}(\lambda_{i}-\lambda_{n-k})\right]\left[\prod\limits_{i>n-k+1}(\lambda_{n-k+1}-\lambda_{i})\right]},$

and

$\Upsilon_{n-k}^{+}=\dfrac{\left[\prod\limits_{i>n-k}(\lambda_{n-k}-\lambda_{i})\right]\left[\prod\limits_{i<n-k+1}(\lambda_{i}-\lambda_{n-k+1})\right]}{\left[\prod\limits_{i>n-k+1}(\lambda_{n-k+1}-\lambda_{i})\right]\left[\prod\limits_{i<n-k}(\lambda_{i}-\lambda_{n-k})\right]}.$

We see that $\Upsilon_{k}^{-}=\Upsilon_{n-k}^{+}$. Thus, the product
$\Upsilon_{k}^{-}\Upsilon_{n-k}^{+}$ simplifies to

$\displaystyle\Upsilon_{k}^{-}\Upsilon_{n-k}^{+}$
$\displaystyle=\dfrac{\left[\prod\limits_{i>n-k}(\lambda_{n-k}-\lambda_{i})^{2}\right]\left[\prod\limits_{i<n-k+1}(\lambda_{n-k+1}-\lambda_{i})^{2}\right]}{\left[\prod\limits_{i<n-k}(\lambda_{n-k}-\lambda_{i})^{2}\right]\left[\prod\limits_{i>n-k+1}(\lambda_{n-k+1}-\lambda_{i})^{2}\right]}$
$\displaystyle=\dfrac{\left[\prod\limits_{j<k+1}(\lambda_{n-k}-\lambda_{n-j+1})^{2}\right]\left[\prod\limits_{j>k}(\lambda_{n-k+1}-\lambda_{n-j+1})^{2}\right]}{\left[\prod\limits_{j>k+1}(\lambda_{n-k}-\lambda_{n-j+1})^{2}\right]\left[\prod\limits_{j<k}(\lambda_{n-k+1}-\lambda_{n-j+1})^{2}\right]}.$

We also observe that

$\exp\left(\sum_{i=1}^{n}\big{(}\lambda_{n-k}^{i}-\lambda_{n-k+1}^{i}\big{)}(t_{i}-\delta_{i1}t)\right)\exp\left(\sum_{i=1}^{n}\big{(}\lambda_{n-k+1}^{i}-\lambda_{n-k}^{i}\big{)}(t_{i}+\delta_{i1}t)\right)$

is equal to

$\displaystyle\exp\left(\sum_{i=1}^{n}\big{(}\lambda_{n-k}^{i}-\lambda_{n-k+1}^{i}\big{)}([t_{i}-\delta_{1i}]-[t_{i}+\delta_{i1}t])\right)$
$\displaystyle=\exp\left(\sum_{i=1}^{n}-2\delta_{i1}t\big{(}\lambda_{n-k}^{i}-\lambda_{n-k+1}^{i}\big{)}\right)$
$\displaystyle={\rm e}^{2(\lambda_{n-k+1}-\lambda_{n-k})t}.$

Putting all of the above together, one obtains

$\displaystyle b_{k}^{-}b_{n-k}^{+}{\rm
e}^{2(\lambda_{n-k}-\lambda_{n-k+1})t}=\dfrac{b_{k}(0)b_{n-k}(0)(\Delta_{k}\Delta_{n-k})^{2}}{\Delta_{k-1}\Delta_{k+1}\Delta_{n-k-1}\Delta_{n-k+1}}$
$\displaystyle\qquad\quad{}\times\dfrac{\left[\prod\limits_{j<k+1}(\lambda_{n-k}-\lambda_{n-j+1})^{2}\right]\left[\prod\limits_{j>k}(\lambda_{n-k+1}-\lambda_{n-j+1})^{2}\right]}{\left[\prod\limits_{j>k+1}(\lambda_{n-k}-\lambda_{n-j+1})^{2}\right]\left[\prod\limits_{j<k}(\lambda_{n-k+1}-\lambda_{n-j+1})^{2}\right]}$
$\displaystyle\qquad{}=\dfrac{\left[\prod\limits_{j<k+1}(\lambda_{n-k}-\lambda_{n-j+1})^{2}\right]\left[\prod\limits_{j>k}(\lambda_{n-k+1}-\lambda_{n-j+1})^{2}\right]}{\left[\prod\limits_{j>k+1}(\lambda_{n-k}-\lambda_{n-j+1})^{2}\right]\left[\prod\limits_{j<k}(\lambda_{n-k+1}-\lambda_{n-j+1})^{2}\right]},$

where the second equality holds by Lemma 6.6, which completes the proof of
Theorem 6.1.

###  6.2 The discrete-time Toda lattice phase shift (dToda)

We now turn to proving the analogue of equation (6.1) for the discrete-time
Toda lattice. In doing this we again emphasize that $t$ will be discrete
($t\in\mathbb{Z}$) and that the eigenvalues of $X_{0}$ are taken to be
positive and distinct.

######  Theorem 6.8.

$\displaystyle\lim_{t\to+\infty}b_{n-k}(t)b_{k}(-t)\left(\dfrac{\lambda_{n-k}}{\lambda_{n-k+1}}\right)^{2t}=\dfrac{\prod\limits_{j<k+1}(\lambda_{n-k}-\lambda_{n-j+1})^{2}\prod\limits_{j>k}(\lambda_{n-k+1}-\lambda_{n-j+1})^{2}}{\prod\limits_{j>k+1}(\lambda_{n-k}-\lambda_{n-j+1})^{2}\prod\limits_{j<k}(\lambda_{n-k+1}-\lambda_{n-j+1})^{2}}.\\!\\!\\!$
(6.10)

This essentially comes down to the analogous description of the subdiagonal
entries in this setting:

$b_{k}(t)=\dfrac{\Delta_{k+1}^{k+1}\big{(}X_{0}^{t}\big{)}\Delta_{k-1}^{k-1}\big{(}X_{0}^{t}\big{)}}{\big{(}\Delta_{k}^{k}\big{(}X_{0}^{t}\big{)}\big{)}^{2}}b_{k}(0).$

In the above, we recall that $\Delta_{k}^{k}$ is the $k\times k$ principal
minor determinant of a matrix. When one takes this into our proof of Moser’s
continuous-time setting, the only difference is that the ${\rm
e}^{t\epsilon_{\lambda}}$ is replaced with $\epsilon_{\lambda}^{t}$.

When we compute these principal minor determinants, we still use $U$ to
diagonalise, we still have $[b_{0}\widehat{w}_{0}]_{-}$, everything is the
same, except that we have $D_{\lambda}^{t}$ instead of ${\rm
e}^{D_{\lambda}t}$.

##  7 BBS phase shift

We use the basic properties of tropicalisation to tropicalise equation (6.10):

$\lim_{t\to+\infty}b_{n-k}(t)b_{k}(-t)\left(\dfrac{\lambda_{n-k}}{\lambda_{n-k+1}}\right)^{2t}=\dfrac{\prod\limits_{j<k+1}(\lambda_{n-k}-\lambda_{n-j+1})^{2}\prod\limits_{j>k}(\lambda_{n-k+1}-\lambda_{n-j+1})^{2}}{\prod\limits_{j>k+1}(\lambda_{n-k}-\lambda_{n-j+1})^{2}\prod\limits_{j<k}(\lambda_{n-k+1}-\lambda_{n-j+1})^{2}}.$

We first recall that the phase space of dToda consists of tridiagonal
Hessenberg matrices and we write a solution as

$X(t)=\left[\begin{matrix}a_{1}(t)&1\\\ b_{1}(t)&a_{2}(t)&\ddots\\\
&\ddots&\ddots&1\\\ &&b_{n-1}(t)&a_{n}(t)\end{matrix}\right].$ (7.1)

Thus, the $b$’s are the subdiagonal entries of a solution at a given time.

It is important to recall that Tokihiro’s [28] tropicalisation is performed on
the variables in the lower-upper factorisation description of dToda which we
briefly recall from Sections 3.3 and 3.5:

$R(t)=\left[\begin{matrix}I_{1}^{t}&1\\\ &I_{2}^{t}&\ddots\\\ &&\ddots&1\\\
&&&I_{n}^{t}\end{matrix}\right],\qquad L(t)=\left[\begin{matrix}1\\\
V_{1}^{t}&1\\\ &\ddots&\ddots\\\ &&V_{n-1}^{t}&1\end{matrix}\right].$

This evolves under the factorisation dynamics

$L(t+1)R(t+1)=R(t)L(t).$

By setting $X(t)=L(t)R(t)$, one obtains a matrix of the form in (7.1). A quick
comparison reveals $b_{k}(t)=V_{k}^{t}I_{k}^{t}$ for all
$k\in\\{1,2,\dots,n-1\\}$.

By Tokihiro’s calculation, $V_{k}^{t}$ corresponds to the $k$-th finite gap
and $I_{k}^{t}$ corresponds to the $k$-th block size, each at time $t$.
Therefore, the tropical analogue of $b_{k}(t)$ is $W_{k}^{t}+Q_{k}^{t}$.

The other components in equation (6.10) to deal with are the eigenvalues. In
the limit as $t\to+\infty$, we know that the matrix in (7.1) is

$X(t)=\left[\begin{matrix}\lambda_{1}&1\\\ &\lambda_{2}&\ddots\\\
&&\ddots&1\\\ &&&\lambda_{n}\end{matrix}\right].$

We also know that $L(t)$ limits to the identity matrix, so we know that
$\lim\limits_{t\to+\infty}I_{k}^{t}=\lambda_{k}$ for each $k$. Since the
tropicalisation of $I_{k}^{t}$ is $Q_{k}^{t}$ (the $k$-th block size at time
$t$), the tropical analogue of $\lambda_{k}$ is

$\lim_{t\to+\infty}Q_{k}^{t}=\mu_{k},$

where $\mu_{1}<\mu_{2}<\cdots<\mu_{n}$ are the sorted asymptotic block sizes
of the BBS in forwards time.

Recalling that $\lambda_{1}>\lambda_{2}>\cdots>\lambda_{n}>0$, we compute the
tropicalisation of $(\lambda_{i}-\lambda_{j})^{2}$ for each pair $i\neq j$.
For the sake of this calculation, assume $i<j$ so that
$\lambda_{i}-\lambda_{j}>0$. To detropicalise this quantity, we let
$\lambda_{i}={\rm e}^{-\frac{1}{\hbar}\mu_{i}}$ and $\lambda_{j}={\rm
e}^{-\frac{1}{\hbar}\mu_{j}}$ and compute

$\displaystyle-\lim_{\hbar\to 0^{+}}\hbar\log\big{(}\big{(}{\rm
e}^{-\frac{1}{\hbar}\mu_{i}}-{\rm
e}^{-\frac{1}{\hbar}\mu_{j}}\big{)}^{2}\big{)}=-2\lim_{\hbar\to
0^{+}}\hbar\log\big{(}{\rm e}^{-\frac{1}{\hbar}\mu_{i}}-{\rm
e}^{-\frac{1}{\hbar}\mu_{j}}\big{)}=2\min(\mu_{i},\mu_{j})=2\mu_{i},$

where the last equality follows from a computation using l’Hôpital’s rule.

Using the property that tropicalisation sends products to sums and quotients
to differences, the tropical analogue of equation (6.10) is given by

######  Theorem 7.1.

$\displaystyle\lim_{t\to+\infty}\big{(}W_{n-k}^{t}+Q_{n-k}^{t}+W_{k}^{-t}+Q_{k}^{-t}+2t(\mu_{n-k}-\mu_{n-k+1})\big{)}$
$\displaystyle\qquad{}=\sum_{j<k+1}2\mu_{n-k}+\sum_{j>k}2\mu_{n-j+1}-\sum_{j>k+1}2\mu_{n-j+1}-\sum_{j<k}2\mu_{n-k+1}.$

######  Remark 7.2.

Once the blocks of balls have become ordered according to their asymptotic
lengths, which occurs in a finite time frame, all blocks travel freely with
speeds given by their lengths. This means that $Q_{k}^{t}=\mu_{k}$ for each
$k$ and for all time after the sorting. Similarly, in backwards time, the
blocks will become sorted in a finite time frame from largest to smallest, so
that $Q_{k}^{-t}=\mu_{n-k+1}$ for each $k$ and for all sufficiently large
time. Taking $t$ large enough so that the time $t$ and time $-t$ states are
both ordered appropriately, we see that

$\displaystyle W_{n-k}^{t+1}=W_{n-k}^{t}+(\mu_{n-k+1}-\mu_{n-k}),$
$\displaystyle Q_{n-k}^{t+1}=Q_{n-k}^{t}=\mu_{n-k},$ $\displaystyle
W_{k}^{-(t+1)}=W_{k}^{-t}+(\mu_{n-k+1}-\mu_{n-k}),$ $\displaystyle
Q_{k}^{-(t+1)}=Q_{k}^{-t}=\mu_{n-k+1}.$

Consequently,

$\displaystyle
W_{n-k}^{t+1}+Q_{n-k}^{t+1}+W_{k}^{-(t+1)}+Q_{k}^{-(t+1)}+2(t+1)(\mu_{n-k}-\mu_{n-k+1})$
$\displaystyle\qquad{}=W_{n-k}^{t}+(\mu_{n-k+1}-\mu_{n-k})+Q_{n-k}^{t}+W_{k}^{-t}+(\mu_{n-k+1}-\mu_{n-k})+Q_{k}^{-t}$
$\displaystyle\qquad\quad{}+2(t+1)(\mu_{n-k}-\mu_{n-k+1})$
$\displaystyle\qquad{}=W_{n-k}^{t}+Q_{n-k}^{t}+W_{k}^{-t}+Q_{k}^{-t}+2t(\mu_{n-k}-\mu_{n-k+1}).$

Therefore, the quantity in the limit described in Theorem 7.1 becomes constant
in finite time.

Because the limit stabilises in finite time, Theorem 7.1 is equivalent to the
statement that for all sufficiently large $t$, the following holds:

$\displaystyle
W_{n-k}^{t}+\mu_{n-k}+W_{k}^{-t}+\mu_{n-k+1}+2t(\mu_{n-k}-\mu_{n-k+1})$
$\displaystyle\qquad{}=\sum_{j<k+1}2\mu_{n-k}+\sum_{j>k}2\mu_{n-j+1}-\sum_{j>k+1}2\mu_{n-j+1}-\sum_{j<k}2\mu_{n-k+1}.$

Or, equivalently

$\displaystyle W_{n-k}^{t}+W_{k}^{-t}+2t(\mu_{n-k}-\mu_{n-k+1})$
$\displaystyle\quad{}=\sum_{j<k+1}2\mu_{n-k}+\sum_{j>k}2\mu_{n-j+1}-\sum_{j>k+1}2\mu_{n-j+1}-\sum_{j<k}2\mu_{n-k+1}-(\mu_{n-k}+\mu_{n-k+1}).$
(7.2)

###  7.1 Free dynamics versus the phase shift

To see the role phase shifts play in the tropical setting, we will initialise
an $n$-soliton box-ball system sufficiently far back in time so that the
blocks are arranged from largest to smallest.

We consider a special dynamical evolution of this state gotten by treating
each block as a single, immutable object, travelling with velocity given by
its size. If we allow multiple balls to occupy the same box at any given time,
the blocks will eventually pass through one another without experiencing a
phase shift and order themselves from smallest to largest. The point here is
that the intermediate stages may not correspond to box-ball states, but, in
sufficiently large backwards and forwards time, boxes will contain at most one
ball, resulting in a box-ball state.

By definition of the phase-shift, the resulting far enough forward time state
for this special dynamics will differ from the corresponding (same number of
time-steps) box-ball system by the phase shift of each block.

Let $\mu_{1}<\mu_{2}<\cdots<\mu_{n}$ be the ordered block sizes after
sufficiently many time evolutions. In the far past the block sizes are
initially ordered as

$Q_{1}^{-t}=\mu_{n}<Q_{2}^{-t}=\mu_{n-1}<\cdots<Q_{n}^{-t}=\mu_{1}.$

We temporarily introduce some variables by indexing all of the boxes in the
system by the integers $\mathbb{Z}$ and by letting $s_{k}$ be equal to the
index of the first ball of the $\mu_{k}$ block at time $-t$.

From the initial first ball positions and the blocks sizes, one can determine
the values of $W_{k}^{-t}$ for each $k$:

$W_{k}^{-t}=s_{n-k}-s_{n-k+1}-\mu_{n-k+1}.$

In the figure below, we depict how the $s_{k}$’s are set up for this
initialised backward time configuration:

$\cdots$$\cdots$$\cdots$$\cdots$$\cdots$$\cdots$$\cdots$$W_{0}^{-t}=\infty$$Q_{1}^{-t}=\mu_{n}$$W_{1}^{-t}$$Q_{2}^{-t}=\mu_{n-1}$$Q_{n}^{-t}=\mu_{1}$$W_{n}^{-t}=\infty$$s_{n}$$s_{n-1}$$s_{1}$

Recall how this compares to the large positive $t$ picture, in which the
blocks become arranged in the opposite ordering:

$\cdots$$\cdots$$\cdots$$\cdots$$\cdots$$\cdots$$\cdots$$W_{0}^{t}=\infty$$Q_{1}^{t}=\mu_{1}$$W_{1}^{t}$$Q_{2}^{t}=\mu_{2}$$Q_{n}^{t}=\mu_{n}$$W_{n}^{t}=\infty$

The following can be done without this introduction, but it does make the
calculations a little simpler to follow. Under this free dynamics, the
$\mu_{k}$-block travels with velocity $\mu_{k}$. Thus, if $j$ is sufficiently
large, the blocks will be ordered with the first ball of the $\mu_{k}$-block
occupying position $s_{k}+j\mu_{k}$. If we let $\Phi_{k}$ denote the phase
shift experienced in the true BBS dynamics by the $k$-block, one has that the
position of the first ball of the $\mu_{k}$ block is given by
$s_{k}+j\mu_{k}+\Phi_{k}$. As before, and for $j$ sufficiently large, we can
use these positions and the block sizes to determine the values $W_{k}^{-t+j}$
for each $k$:

$\displaystyle W_{k}^{-t+j}$
$\displaystyle=(s_{k+1}+j\mu_{k+1}+\Phi_{k+1})-(s_{k}+j\mu_{k}+\Phi_{k})-\mu_{k}$
$\displaystyle=s_{k+1}-s_{k}+j(\mu_{k+1}-\mu_{k})+\Phi_{k+1}-\Phi_{k}-\mu_{k}.$

Assuming that $t$ was large enough for both the time $-t$ and time $t$ states
to be ordered appropriately, substituting in $j=2t$ and looking at the above
for $n-k$, one has

$W_{n-k}^{t}=s_{n-k+1}-s_{n-k}+2t(\mu_{n-k+1}-\mu_{n-k})+\Phi_{n-k+1}-\Phi_{n-k}-\mu_{n-k}.$

Thus, for $t$ sufficiently large, one has

$W_{n-k}^{t}+W_{k}^{-t}+2t(\mu_{n-k}+\mu_{n-k+1})=\Phi_{n-k+1}-\Phi_{n-k}-(\mu_{n-k}+\mu_{n-k+1})$
(7.3)

Comparing equations (7.2) and (7.3), we now see that we have

$\Phi_{n-k+1}-\Phi_{n-k}=\sum_{j<k+1}2\mu_{n-k}+\sum_{j>k}2\mu_{n-j+1}-\sum_{j>k+1}2\mu_{n-j+1}-\sum_{j<k}2\mu_{n-k+1}$
(7.4)

for $k=1,2,\dots,n-1$. This gives us $n-1$ equations for the $n$ phase shifts,
$\Phi_{i}$ for $i=1,\dots,n$.

###  7.2 Conservation laws

######  Lemma 7.3.

Suppose one initialises an $n$-soliton state at time $t=0$ with coordinates

$\big{(}\infty,Q_{1}^{0},W_{1}^{0},Q_{2}^{0},W_{2}^{0},\dots,Q_{n}^{0},\infty\big{)}.$

Define $\ell_{i}^{0}$ for $i\in\\{1,\dots,n\\}$ as follows

$\ell_{i}^{0}=Q_{i}^{0}+\sum_{j=1}^{i-1}\big{(}Q_{j}^{0}+W_{j}^{0}\big{)}.$

If at time $t=1$, the system has coordinates

$\big{(}\infty,Q_{1}^{1},W_{1}^{1},Q_{2}^{1},W_{2}^{1},\dots,Q_{n}^{1},\infty\big{)},$

define $\ell_{i}^{1}$ for $i\in\\{1,\dots,n\\}$ as follows

$\ell_{i}^{1}=Q_{1}^{0}+Q_{i}^{1}+\sum_{j=1}^{i-1}\big{(}Q_{j}^{1}+W_{j}^{1}\big{)}.$

Then one has

$\sum_{i=1}^{n}\ell_{i}^{1}=M+\sum_{i=1}^{n}\ell_{i}^{0},$ (7.5)

where $M$ is the total mass of the system, i.e.,

$M=\sum_{i=1}^{n}\mu_{i}=\sum_{i=1}^{n}Q_{i}^{t},$

where the latter equality is independent of the choice of $t$.

###### Proof.

Recall the evolution rule for the $W$ coordinates from the box-ball coordinate
dynamics (2.1):

$W_{j}^{t+1}=Q_{j+1}^{t}+W_{j}^{t}-Q_{j}^{t+1}$

for each $i\in\\{1,\dots,n\\}$. Rearranging this and taking $t=0$, one has

$W_{j}^{1}+Q_{j}^{1}=Q_{j+1}^{0}+W_{j}^{0}.$

Therefore,

$\displaystyle\sum_{i=1}^{n}\ell_{i}^{1}$
$\displaystyle=\sum_{i=1}^{n}\left(Q_{1}^{0}+Q_{i}^{1}+\sum_{j=1}^{i-1}\big{(}Q_{j}^{1}+W_{j}^{1}\big{)}\right)=\sum_{i=1}^{n}Q_{i}^{1}+\sum_{i=1}^{n}\left(Q_{1}^{0}+\sum_{j=1}^{i-1}\big{(}Q_{j+1}^{0}+W_{j}^{0}\big{)}\right)$
$\displaystyle=M+\sum_{i=1}^{n}\left(Q_{i}^{0}+\sum_{j=1}^{i-1}\big{(}Q_{j}^{0}+W_{j}^{0}\big{)}\right)=M+\sum_{i=1}^{n}\ell_{i}^{0}.$
∎

######  Remark 7.4.

The significance of the $\ell_{i}$ quantities is realised by labelling all
boxes of the initial box-ball state by $\mathbb{Z}$ such that the left-most
ball in the time $t=0$ state is in box 1. In this configuration, the right-
most ball of the first block occupies box $\ell_{1}^{0}=Q_{1}^{0}$. The right-
most ball of the second block occupies box
$\ell_{2}^{0}=Q_{1}^{0}+W_{1}^{0}+Q_{2}^{0}$. In general, the right-most ball
of the $i$-th block occupies the $\ell_{i}^{0}$-th box. So, the quantity
$\sum\limits_{i=1}^{n}\ell_{i}^{0}$ records the sum of the labels of the
right-most balls of the block.

We provide the following two-time step illustration of the $\ell_{i}^{t}$
assignment for an particular BBS configuration:

$t=0:$123456789101112131415$\ell_{1}^{0}$$\ell_{2}^{0}$$\ell_{3}^{0}$$\cdots$$\cdots$$t=1:$123456789101112131415$\cdots$$\cdots$$\ell_{1}^{1}$$\ell_{2}^{1}$$\ell_{3}^{1}$

Observe not only what the $\ell_{i}$’s are, but also how the sum of the
$\ell_{i}$’s increases by $M=7$ from $t=0$ to $t=1$.

By keeping the above labelling and evolving the dynamics to time $t=1$, the
same argument for the labels of the right-most balls of the blocks carries
through, but everything is shifted to the right by $Q_{1}^{0}$ since the left-
most ball of the system now occupies box $Q_{1}^{0}$. Therefore, equation
(7.5) says that the sum of the positions of the last ball of each block
increases by the total mass of the system from time $t=0$ to time $t=1$. Of
course, one could initialise at any time and the total mass is independent of
time, so this extends to the statement that the sum of the positions of the
last ball of each block at any time increases by $M\cdot j$ after $j$ time
steps, given an initial indexing of the boxes.

######  Remark 7.5.

We note that this ultradiscrete conservation law corresponds to the
conservation at both the continuous and discrete time levels described in
Section 3.6.

######  Lemma 7.6.

The sum of all of the phase shifts is zero $\sum_{i=1}^{n}\Phi_{i}=0$.

###### Proof.

Suppose $t$ is taken large enough so that at time $-t$ the BBS has achieved
its asymptotic block structure with blocks ordered from largest to smallest,
and at time $t$ the BBS has achieved its asymptotic block structure with
blocks ordered from smallest to largest.

At time $-t$, suppose the boxes of the BBS are indexed by $\mathbb{Z}$, with
$\ell_{i}$ denoting the label of the last ball of the $\mu_{i}$ block. Until
the collision, the label of the last ball in the $\mu_{i}$-block increases by
$\mu_{i}$ at each stage. Therefore, the sum of the labels of each last ball of
the blocks increases by $\sum_{i=1}^{n}\mu_{i}=M$ at each time step. If we let
$\hat{\ell}_{i}$ denote the label of the last ball in the $\mu_{i}$-block at
time $t$ in this phase shift-free situation, then it would follow that
$\hat{\ell}_{i}=\ell_{i}+2t\mu_{i}$. Thus,

$\sum_{i=1}^{n}\hat{\ell}_{i}=2tM+\sum_{i=1}^{n}\ell_{i}.$ (7.6)

By definition of the phase shifts, the true label for the last ball of the
$\mu_{i}$ block is given by $\hat{\ell}_{i}+\Phi_{i}$. By Remark 7.4, these
labels satisfy

$\sum_{i=1}^{n}\big{(}\hat{\ell}_{i}+\Phi_{i}\big{)}=2tM+\sum_{i=1}^{n}\ell_{i}.$
(7.7)

Comparing (7.6) and (7.7), we see that $\sum_{i=1}^{n}\Phi_{i}=0$. ∎

As a result of equation (7.4) and Lemma 7.6, we now have that the $n$ phase
shifts satisfy the following system of $n$ linear equations:

$\begin{cases}\displaystyle\Phi_{n-k+1}-\Phi_{n-k}=\sum_{j<k+1}2\mu_{n-k}+\sum_{j>k}2\mu_{n-j+1}-\sum_{j>k+1}2\mu_{n-j+1}-\sum_{j<k}2\mu_{n-k+1},\\\
\displaystyle\sum\limits_{i=1}^{n}\Phi_{i}=0,\end{cases}$ (7.8)

where the first equation is for each $k\in\\{1,\dots,n-1\\}$.

######  Lemma 7.7.

Take the $n\times n$ matrix

$\left[\begin{matrix}-1&1\\\ &-1&1\\\ &&\ddots&\ddots\\\ &&&-1&1\\\
1&1&\cdots&1&1\end{matrix}\right],$

which nest from the bottom-right $($so that for $n=1$, this is just $[1])$.
This matrix is non-singular.

This is a simple exercise in linear algebra (one can show that this matrix has
determinant $n(-1)^{n+1}$. The key point is that it now follows that the
system of equations in (7.8) has a unique solution, which is given by the
phase shifts. We can now state our main theorem:

######  Theorem 7.8.

For $i\in\\{1,\dots,n\\}$, define $\hat{\Phi}_{i}$ via

$\hat{\Phi}_{i}=\sum_{j<i}2\mu_{j}-\sum_{j>i}2\mu_{i}.$ (7.9)

For a box-ball system with asymptotic block sizes given by
$\mu_{1}<\mu_{2}<\cdots<\mu_{n}$, the phase shift, $\Phi_{i}$, of the
$\mu_{i}$-block experienced from $-t$ to $t$ for $t$ sufficiently large is
equal to $\hat{\Phi}_{i}$.

###### Proof.

For each $k=1,\dots,n-1$, one has

$\displaystyle\hat{\Phi}_{n-k+1}-\hat{\Phi}_{n-k}$
$\displaystyle=\sum_{j<n-k+1}2\mu_{j}-\sum_{j>n-k+1}2\mu_{n-k+1}-\sum_{j<n-k}2\mu_{j}+\sum_{j>n-k}2\mu_{n-k}$
$\displaystyle=\sum_{j>k}2\mu_{n-j+1}-\sum_{j<k}2\mu_{n-k+1}-\sum_{j>k+1}2\mu_{n-j+1}+\sum_{j<k+1}2\mu_{n-k}.$

Thus, $(\hat{\Phi}_{i})_{i=1}^{n}$ satisfies the first $n-1$ equations of
(7.8).

Next, let us compute $\sum\limits_{k=1}^{n}\Phi_{k}$ by direct calculation:

$\displaystyle\sum_{k=1}^{n}\hat{\Phi}_{k}$
$\displaystyle=\sum_{k=1}^{n}\left(\sum_{j<k}2\mu_{j}-\sum_{j>k}2\mu_{k}\right)=\sum_{k=1}^{n}\sum_{j<k}2\mu_{j}-\sum_{k=1}^{n}\sum_{j>k}2\mu_{k}.$

These are all finite sums, so we can reverse the order of summation. For the
second double sum, summing from $k=1$ to $n$ with $j>k$ is equivalent to
summing from $j=1$ to $n$ with $k<j$. Therefore, the above is equal to

$\sum_{k=1}^{n}\sum_{j<k}2\mu_{j}-\sum_{j=1}^{n}\sum_{k<j}2\mu_{k},$

which is clearly zero.

We have now established that $(\hat{\Phi}_{i})_{i=1}^{n}$ the full system of
equations in (7.8). Since this system has a unique solution, and the phase
shifts $({\Phi}_{i})_{i=1}^{n}$ satisfy this system, it follows that
$\hat{\Phi}_{i}=\Phi_{i}$ for $i=1,\dots,n$. ∎

##  8 Comparison with the literature

Tokihiro and collaborators [29] have studied a related advanced version of the
box-ball system in which balls are labelled and given priority in their
movements based on the labels. Like the classic box-ball system, the advanced
box-ball system also exhibits the solitonic scattering phenomenon, and they
describe a soliton scattering rule that shows how the ball labels are permuted
within the solitonic blocks in both forwards and backwards asymptotic time.
Instead of the usual discrete-time Toda lattice with tridiagonal Hessenberg
phase space, the advanced box-ball system is obtained via ultradiscretisation
of the so-called hungry Toda molecule equation. This tropical correspondence
allowed the dynamics and scattering rules of the advanced box-ball system to
be understood by detropicalising, passing through the hungry Toda dynamics,
and then re-tropicalising back to an advanced box-ball configuration. This,
when restricted to just one box label, reduces to classical dToda and the
classical box-ball system.

For the restriction to dToda and classical BBS, [29] observed that the phase
shift phenomenon decomposes into pairwise individual 2-soliton phase
interactions and used this observation to justify restricting their attention
to just 2-soliton phase shifts. However, this observation does not seem to be
proved. With our approach, however, we do not make this assumption or
observation a priori. Instead, we take an $n$-soliton configuration and prove
an overall phase shift formula (equation (7.9)) which we recall below:

$\hat{\Phi}_{i}=\sum_{j<i}2\mu_{j}-\sum_{j>i}2\mu_{i}$

and, just as Moser did in [20], we can interpret the formula as saying that
one can think of the overall phase shift phenomenon as decomposing into
pairwise phase shift interactions, even though we do not assume that only two
blocks collide at a time. However, a major point to be made here is that one
can easily construct a box-ball configuration in which multiple collisions
occur simultaneously, and our proof here does not depend on assuming that such
a multi-collision does not occur; the proof applies to such configurations.

Subsequent to the completion of this paper, we were made aware of another more
recent approach to scattering properties of box-ball systems based on a purely
combinatorial method known as the Kerov–Kirillov–Reshetikhin bijection. The
works of [15, 25] use this bijection to construct action-angle coordinates on
(generalised) BBS, involving Young tableaux with riggings. This yields a
linearisation of the BBS dynamics in terms of which the asymptotic behavior of
the soliton blocks can be determined. It may be of interest in future studies
to compare this approach with the diagrammatic phase shift analysis performed
in this paper.

##  Appendix A The Gessel–Viennot–Lindström lemma

The following lemma of Gessel, Viennot and Lindström can be found in [2]:

######  Lemma A.1 (Gessel–Viennot–Lindström).

Let $G=(V,E)$ be a directed acyclic graph with weights on $E$,
$\mathcal{A}=\\{A_{1},\dots,A_{n}\\}$ and
$\mathcal{B}=\\{B_{1},\dots,B_{n}\\}$ be subsets of $V$, and $M$ the path-
matrix from $\mathcal{A}$ to $\mathcal{B}$. Then,

$\det(M)=\sum_{\mathcal{P}\in
VD}(\operatorname{sign}\mathcal{P})w(\mathcal{P}),$ (A.1)

where $VD$ is the set of all vertex-disjoint path systems from
$\mathcal{A}\to\mathcal{B}$, i.e., each $\mathcal{P}\in VD$ is an $n$-tuple of
paths $P_{i}\colon A_{i}\to B_{\sigma(i)}$ for some
$\sigma\in\mathfrak{S}_{n}$ such that $P_{i}$ and $P_{j}$ have no vertices in
common for $i\neq j$. The sign of a vertex-disjoint path system is taken to be
the sign of the permutation $\sigma$, and its weight is the product of all
weights of all edges used in the path system.

Of particular interest to us will be path graphs of the following type:

(1,1)(1,2)(1,3)(1,4)(1,4)(2,1)(2,2)(2,3)(2,4)(2,4)(3,1)(3,2)(3,3)(3,4)(3,4)(4,1)(4,1)(4,2)(4,2)(4,3)(4,3)(4,4)(4,4)(4,4)

In general, these will be graphs whose vertices form an $n\times n$ array with
the following properties:

  1. 1)

the vertices are labelled $(i,j)$ for $1\leq i,j\leq n$, with $i$ describing
the row, and $j$ the column,

  2. 2)

the bottom row vertices $\\{(n,j)\colon 1\leq j\leq n\\}$ will be the set of
sources,

  3. 3)

the last column vertices $\\{(i,n)\colon 1\leq i\leq n\\}$ will be the set of
sinks, sharing $(n,n)$ with the sources,

  4. 4)

all edges are directed either up or right,

  5. 5)

any path from a source $(n,j)$ to a sink $(i,n)$ must pass through $(j,j)$;
therefore, there are only paths from $(n,j)$ to $(i,n)$ for $i\leq j$.

These graphs will be described in more detail (specifying the edge weights),
but, for now, these properties are all that are needed to make the following
key observation: a path from $(n,j)$ to $(i,n)$ separates sources $(n,k)$ from
sinks $(l,n)$ for all $k>j$ and $l<i$.

The following lemma is a consequence of this last observation above.

######  Lemma A.2.

If one has a $k$-set of sources $\mathcal{A}=\\{(n,a_{i})\colon 1\leq i\leq
k\\}$ and a $k$-set of sinks $\mathcal{B}=\\{(b_{i},n)\colon 1\leq i\leq
k\\}$, each ordered so that $a_{1}<a_{2}<\cdots<a_{k}$ and
$b_{1}<b_{2}<\cdots<b_{k}$, then, if there are any vertex-disjoint path
systems from $\mathcal{A}$ to $\mathcal{B}$, then $\sigma\in\mathfrak{S}_{k}$
must be the identity, i.e., the path system must consist of disjoint paths
$P_{i}\colon(n,a_{i})\to(b_{i},n)$ for $1\leq i\leq k$.

###### Proof.

We assume $k>1$, otherwise the statement holds true trivially. Suppose then
that $P_{1}\colon(n,a_{1})\to(b_{i},n)$ for some $i>1$. By the observation,
this path cuts off all sources $(n,a_{i})$ for $i>1$ from the sink
$(b_{1},n)$. This means the path system cannot be completed without violating
the vertex-disjointedness. Thus, one must have
$P_{1}\colon(n,a_{1})\to(b_{1},n)$.

To complete the proof, we show that if
$\mathcal{P}=\\{P_{i}\colon(n,a_{i})\to(b_{\sigma(i)},n),\,1\leq i\leq k\\}$
is a vertex-disjoint path system, for some $\sigma\in\mathfrak{S}_{k}$, and
$\sigma(i)=i$ for $1\leq i\leq j$, then $\sigma(j+1)=j+1$.

The argument is the analogous to the base case: suppose $\sigma(j+1)\neq j+1$,
then, $\sigma(j+1)>j+1$ since $\sigma(i)=i$ for all $i\leq j$. This means that
path $P_{j+1}\colon(n,a_{j+1})\to(b_{\sigma(j+1)},n)$ cuts off all sources
$(n,a_{i})$ for $i>j+1$ from all sinks $(b_{l},n)$ for $l<\sigma(j+1)$. In
particular, since $j+1<\sigma(j+1)$, this means that no source can be paired
with $(j+1,n)$ without violating the vertex-disjoint requirement. Thus, if
such a vertex-disjoint path system were to exist, one would have to have
$\sigma(j+1)=j+1$. Thus, by induction, we have shown that $\sigma(i)=i$ for
each $i$. ∎

By Lemma A.2, the $\text{sign}~{}\mathcal{P}$ piece is always equal to 1 in
equation (A.1) for our graphs of interest, and so we are permitted use of the
following simplified statement of the Gessel–Viennot–Lindström lemma for our
graphs: $\det(M)=\sum_{\mathcal{P}\in VD}w(\mathcal{P})$.

##  Appendix B Proofs of key lemmas

###  B.1 Proof of Lemma 6.3

For $n\in\mathbb{N}$ with $n>1$, we construct a directed, weighted graph
$Q_{n}$ as follows:

  1. 1.

The vertices of the graph will be pairs $(x,y)$ with $1\leq x,y\leq n$
arranged in a rectangular grid with $x$ and $y$ denoting the row and column,
respectively, of the vertex.

  2. 2.

For every $x\in[n-1]$ and for each $y\in[n]$, there will be a vertical arrow
up from $(x+1,y)$ to $(x,y)$. If $x\geq y$, this arrow will be assigned a
weight of 1. Otherwise, the weight $w_{x,y}^{(n)}$ from $(x+1,y)\to(x,y)$ will
be defined by

$w_{x,y}^{(n)}=\dfrac{\prod\limits_{m=y+1}^{n}(\lambda_{m}-\lambda_{x+1})}{\prod\limits_{p=y}^{n}(\lambda_{p}-\lambda_{x})}.$

  3. 3.

For each $x$, $y$ with $1\leq x<y\leq n$, there will be an arrow from
$(x,y-1)$ to $(x,y)$ with weight $1$.

For example, below is $Q_{4}$:

(1,1)(1,2)(1,3)(1,4)(1,4)(2,1)(2,2)(2,3)(2,4)(2,4)(3,1)(3,2)(3,3)(3,4)(3,4)(4,1)(4,1)(4,2)(4,2)(4,3)(4,3)(4,4)(4,4)(4,4)$1$$1$$1$$1$$1$$1$$w_{1,2}^{(4)}$$w_{1,3}^{(4)}$$w_{1,4}^{(4)}$$w_{2,3}^{(4)}$$w_{2,4}^{(4)}$$w_{3,4}^{(4)}$$1$$1$$1$$1$$1$$1$

We associate to $Q_{n}$ its weighted path matrix $P^{(n)}$ defined by taking
$P^{(n)}_{ij}$ to be the sum over all paths to $(i,n)$ from $(n,j)$, where a
path’s contribution to the sum is taken by multiplying all weights of edges
taken by the path. Immediately from the fact that all edges are either up or
right, with the only place to go (via unit weighted paths) from $(n,j)$ is to
$(j,j)$, and the fact that all horizontal paths have unit weight, it is easy
to see that each $P^{(n)}$ is a upper unitary matrix. The first step in
proving Lemma 6.3 is to show that we in fact have
$P^{(n)}=U(\lambda_{1},\dots,\lambda_{n})$ for each $n>1$.

To aid in some of the arguments to come, we include $Q_{2}$, $Q_{3}$ and
$Q_{4}$ below with the weight written out in full:

Here is $Q_{2}$:

(1,1)(1,2)(1,2)(2,1)(2,1)(2,2)(2,2)(2,2)$1$$1$$\frac{1}{\lambda_{2}-\lambda_{1}}$

Here is $Q_{3}$:

(1,1)(1,2)(1,3)(1,3)(2,1)(2,2)(2,3)(2,3)(3,1)(3,1)(3,2)(3,2)(3,3)(3,3)(3,3)$1$$1$$1$$1$$1$$1$$\frac{\lambda_{3}-\lambda_{2}}{(\lambda_{3}-\lambda_{1})(\lambda_{2}-\lambda_{1})}$$\frac{1}{\lambda_{3}-\lambda_{1}}$$\frac{1}{\lambda_{3}-\lambda_{2}}$

Here is $Q_{4}$:

(1,1)(1,2)(1,3)(1,4)(1,4)(2,1)(2,2)(2,3)(2,4)(2,4)(3,1)(3,2)(3,3)(3,4)(3,4)(4,1)(4,1)(4,2)(4,2)(4,3)(4,3)(4,4)(4,4)(4,4)$1$$1$$1$$1$$1$$1$$1$$1$$1$$1$$1$$1$$\frac{(\lambda_{4}-\lambda_{2})(\lambda_{3}-\lambda_{2})}{(\lambda_{4}-\lambda_{1})(\lambda_{3}-\lambda_{1})(\lambda_{2}-\lambda_{1})}$$\frac{\lambda_{4}-\lambda_{2}}{(\lambda_{4}-\lambda_{1})(\lambda_{3}-\lambda_{1})}$$\frac{\lambda_{4}-\lambda_{3}}{(\lambda_{4}-\lambda_{2})(\lambda_{3}-\lambda_{2})}$$\frac{1}{\lambda_{4}-\lambda_{1}}$$\frac{1}{\lambda_{4}-\lambda_{2}}$$\frac{1}{\lambda_{4}-\lambda_{3}}$

We show that $P^{(n)}=U(\lambda_{1},\dots,\lambda_{n})$ by induction on $n$.
One can immediately see from $Q_{2}$ what $P^{(2)}$ is

$\left[\begin{matrix}1&\dfrac{1}{\lambda_{2}-\lambda_{1}}\\\
0&1\end{matrix}\right],$

where we take the convention that there is a path from $(2,2)$ to $(2,2)$ by
which uses no arrows, and the product over the weights is the empty one, hence
is equal to $1$. This is $U(\lambda_{1},\lambda_{2})$, so we have the base
case of $n=2$.

For our induction hypothesis, assume
$P^{(n)}=U(\lambda_{1},\dots,\lambda_{n})$ for some $n>1$ and consider the
weighted graph $Q_{n+1}$. We make two observations on how to translate paths
from $Q_{n}$ to $Q_{n+1}$. The first is that the lower-right subgraph of
$Q_{n+1}$ obtained by deleting all vertices $(x,y)$ with $x=1$ or $y=1$ is
precisely $Q_{n}$, but with all vertices $(x,y)$ replaced by $(x-1,y-1)$ and
the indices of all eigenvalues reduced by $1$. To see this, suppose $1<x<y\leq
n+1$ and consider $w_{x,y}^{(n+1)}$:

$w_{x,y}^{(n+1)}=\dfrac{\prod\limits_{m=y+1}^{n+1}(\lambda_{m}-\lambda_{x+1})}{\prod\limits_{p=y}^{n+1}(\lambda_{p}-\lambda_{x})}$

and compare this to $w_{x-1,y-1}^{(n)}$:

$w_{x-1,y-1}^{(n)}=\dfrac{\prod\limits_{m=y}^{n}(\lambda_{m}-\lambda_{x})}{\prod\limits_{p=y-1}^{n}(\lambda_{p}-\lambda_{x-1})}.$

If we add $1$ to each index on the eigenvalues in $w_{x-1,y-1}^{(n)}$ and
reindex, we obtain

$\dfrac{\prod\limits_{m=y}^{n}(\lambda_{m+1}-\lambda_{x+1})}{\prod\limits_{p=y-1}^{n}(\lambda_{p+1}-\lambda_{x})}=\dfrac{\prod\limits_{m=y+1}^{n+1}(\lambda_{m}-\lambda_{x+1})}{\prod\limits_{p=y}^{n+1}(\lambda_{p}-\lambda_{x})}=w_{x,y}^{(n+1)}.$

This proves the claim. Therefore, to see what $P_{ij}^{(n+1)}$ is for $i,j>1$,
we note that this observation gives us

$P_{ij}^{(n+1)}=\widehat{P_{i-1,j-1}^{(n)}},$

where the right-hand side’s hat tells us to modify all eigenvalues by
increasing their indices by $1$.

By the induction hypothesis, we have

$\displaystyle P_{ij}^{(n+1)}$
$\displaystyle=(U(\lambda_{2},\dots,\lambda_{n}))_{i-1,j-1}=\prod_{i-1\leq
m<j-1}\frac{1}{\lambda_{(j-1)+1}-\lambda_{m+1}}$ $\displaystyle=\prod_{i\leq
m^{\prime}<j}\frac{1}{\lambda_{j}-\lambda_{m^{\prime}}}\
=(U(\lambda_{1},\dots,\lambda_{n+1}))_{ij}.$

This proves the induction hypothesis for the entries $P^{(n+1)}_{ij}$ with
$i,j>1$.

For $j=1$ or $n+1$, the structure of $Q_{n+1}$ makes things simple:

  1. 1.

There is only one vertex of the form $(i,n+1)$ that can be reached from
$(n+1,1)$, and that is $(1,n+1)$, which is via $n$ up arrows (each with unit
weight) followed by $n$ right arrows (also with unit weight). Therefore,
$P_{1j}^{(n+1)}=\delta_{1j}$, as required.

  2. 2.

Each of $(i,n+1)$ can be reached by $(n+1,n+1)$, just by vertical arrows. If
$i=n+1$, this is via the empty path, with weight $1$. Otherwise, the path from
$(n+1,n+1)$ to $(i,n+1)$ has weight

$\prod_{i\leq m<n+1}w_{i,n+1}^{(n+1)}.$

By calculating

$w_{i,n+1}^{(n+1)}=\dfrac{\prod\limits_{m=n+2}^{n+1}(\lambda_{m}-\lambda_{i+1})}{\prod\limits_{p=n+1}^{n+1}(\lambda_{p}-\lambda_{i})}=\dfrac{1}{\lambda_{n+1}-\lambda_{i}},$

we see that

$\prod_{i\leq m<n+1}w_{i,n+1}^{(n+1)}=\prod_{i\leq
m<n+1}\dfrac{1}{\lambda_{n+1}-\lambda_{i}}=(U(\lambda_{1},\dots,\lambda_{n+1}))_{i,n+1}.$

All that remains of the induction step is to show that

$P_{1,j}^{(n+1)}=(U(\lambda_{1},\dots,\lambda_{n+1}))_{1j}$

for $1<j<n+1$. To see, this, we now compare the subgraph of $Q_{n+1}$,
obtained by removing the last column and last row, to the entirety of $Q_{n}$.
We note that they have the same form (with unit weights in the same locations)
and compare $w_{x,y}^{(n)}$ and $w_{x,y}^{(n+1)}$ directly by division for
$1\leq x<y\leq n$:

$\dfrac{w_{x,y}^{(n+1)}}{w_{x,y}^{(n)}}\dfrac{\prod\limits_{m=y+1}^{n+1}(\lambda_{m}-\lambda_{x+1})}{\prod\limits_{p=y}^{n+1}(\lambda_{p}-\lambda_{x})}\dfrac{\prod\limits_{p=y}^{n}(\lambda_{p}-\lambda_{x})}{\prod\limits_{m=y+1}^{n}(\lambda_{m}-\lambda_{x+1})}=\dfrac{\lambda_{n+1}-\lambda_{x+1}}{\lambda_{n+1}-\lambda_{x}}.$

We see that this does not depend on $y$, so, as long as $x<y$, the
(multiplicative) difference in the weights between $Q_{n}$ and the subgraph of
$Q_{n+1}$ is a fixed quantity depending only on the row of the weight.
Furthermore, since each path from a node $(n,j)$ to $(i,n)$ use precisely the
$j-i$ non-unit weight belonging to the consecutive rows terminating in row
$i$, we immediately see that the paths in $Q_{n+1}$ from $(j,n+1)$ to $(n,i)$
must be given by

$\dfrac{\lambda_{n+1}-\lambda_{j}}{\lambda_{n+1}-\lambda_{i}}\times(U(\lambda_{1},\dots,\lambda_{n}))_{ij},$

where the first term comes from multiplying together

$\dfrac{\lambda_{n+1}-\lambda_{j}}{\lambda_{n+1}-\lambda_{j-1}}\times\dfrac{\lambda_{n+1}-\lambda_{j-1}}{\lambda_{n+1}-\lambda_{j-2}}\times\cdots\times\dfrac{\lambda_{n+1}-\lambda_{i+2}}{\lambda_{n+1}-\lambda_{i+1}}\times\dfrac{\lambda_{n+1}-\lambda_{i+1}}{\lambda_{n+1}-\lambda_{i}}.$

We use this information to obtain $P_{1j}^{(n+1)}$ for $1<j<n+1$ by
partitioning the paths from $(n+1,j)$ to $(1,n+1)$ based on the last vertex in
column $n$ of $Q_{n+1}$ that the path hits before moving on to column $n+1$
(i.e., the next arrow must be a right one). These paths then have only one way
of being completed to a path to $(1,n+1)$, which is by a upwards arrows the
rest of the way. Such paths contribute a weight of

$\prod_{1\leq p<i}w_{p,n+1}^{(n+1)}=\prod_{1\leq
p<i}\dfrac{1}{\lambda_{n+1}-\lambda_{p}}.$

Putting this together with the information from the partition, we have

$P_{1j}^{n+1}=\sum_{m=1}^{j}\dfrac{\lambda_{n+1}-\lambda_{j}}{\lambda_{n+1}-\lambda_{m}}\left(\prod_{1\leq
p<m}\dfrac{1}{\lambda_{n+1}-\lambda_{p}}\right)((U(\lambda_{1},\dots,\lambda_{n}))_{mj}.$

Therefore, to complete the final step of the induction step amounts to proving
the following identity:

$\prod_{1\leq
m<j}\dfrac{1}{\lambda_{j}-\lambda_{m}}=\sum_{m=1}^{j}\dfrac{\lambda_{n+1}-\lambda_{j}}{\lambda_{n+1}-\lambda_{m}}\left(\prod_{1\leq
p<m}\dfrac{1}{\lambda_{n+1}-\lambda_{p}}\right)\prod_{m\leq
l<j}\dfrac{1}{\lambda_{j}-\lambda_{l}}.$

######  Lemma B.1.

For all $n\in\mathbb{N}$ and $1<j<n$,

$\prod_{1\leq
m<j}\dfrac{1}{\lambda_{j}-\lambda_{m}}=\sum_{m=1}^{j}\dfrac{\lambda_{n}-\lambda_{j}}{\lambda_{n}-\lambda_{m}}\left(\prod_{1\leq
p<m}\dfrac{1}{\lambda_{n}-\lambda_{p}}\right)\prod_{m\leq
l<j}\dfrac{1}{\lambda_{j}-\lambda_{l}}.$

###### Proof.

By multiplying both sides by

$\prod_{1\leq i<j}(\lambda_{n}-\lambda_{i})(\lambda_{j}-\lambda_{i}),$

the above is equivalent to showing

$\displaystyle\prod_{i=1}^{j-1}(\lambda_{n}-\lambda_{i})$
$\displaystyle=\sum_{m=1}^{j}\dfrac{\lambda_{n}-\lambda_{j}}{\lambda_{n}-\lambda_{m}}\left(\prod_{p=m}^{j-1}(\lambda_{n}-\lambda_{p})\right)\left(\prod_{l=1}^{m-1}(\lambda_{j}-\lambda_{l})\right)$
$\displaystyle=\sum_{m=1}^{j}\left(\prod_{p=m+1}^{j}(\lambda_{n}-\lambda_{p})\right)\left(\prod_{l=1}^{m-1}(\lambda_{j}-\lambda_{l})\right).$

This holds trivially for $j=1$ (by convention for the empty product). For
$j=2$, we want

$\lambda_{n}-\lambda_{1}=(\lambda_{n}-\lambda_{2})\times
1+1\times(\lambda_{2}-\lambda_{1}).$

We proceed by induction: suppose the above identity holds for each $j-1$ and
consider the identity for $j$. The right-hand side is equal to

RHS
$\displaystyle=\sum\limits_{m=1}^{j-2}\left(\prod\limits_{p=m+1}^{j}(\lambda_{n}-\lambda_{p})\right)\left(\prod\limits_{l=1}^{m-1}(\lambda_{j}-\lambda_{l})\right)+\prod\limits_{l=1}^{j-1}(\lambda_{j}-\lambda_{l})+(\lambda_{n}-\lambda_{j})\prod\limits_{l=1}^{j-2}(\lambda_{j}-\lambda_{l})$
$\displaystyle=\sum\limits_{m=1}^{j-2}\left(\prod\limits_{p=m+1}^{j}(\lambda_{n}-\lambda_{p})\right)\left(\prod\limits_{l=1}^{m-1}(\lambda_{j}-\lambda_{l})\right)+(\lambda_{j}-\lambda_{j-1}+\lambda_{n}-\lambda_{j})\prod\limits_{l=1}^{j-2}(\lambda_{j}-\lambda_{l})$
$\displaystyle=(\lambda_{n}-\lambda_{j-1})\left[\sum_{m=1}^{j-2}\left(\prod_{\begin{subarray}{c}p=m+1\\\
p\neq
j-1\end{subarray}}^{j}(\lambda_{n}-\lambda_{p})\right)\left(\prod_{l=1}^{m-1}(\lambda_{j}-\lambda_{l})\right)+\prod_{l=1}^{j-2}(\lambda_{j}-\lambda_{l})\right]$
$\displaystyle=(\lambda_{n}-\lambda_{j-1})\prod_{i=1}^{j-2}(\lambda_{n}-\lambda_{i})=\prod_{i=1}^{j-1}(\lambda_{n}-\lambda_{i}),$

where the penultimate equality was the induction hypothesis applied to the
eigenvalues

$\lambda_{1},\dots,\lambda_{j-2},\lambda_{j},\dots,\lambda_{n}.$

With the equality $U(\lambda_{1},\dots,\lambda_{n})=P^{(n)}$ for all $n>1$ now
established, we have that

$\Delta_{k}^{n}U(\lambda_{1},\dots,\lambda_{n})=\Delta_{k}^{n}\big{(}P^{(n)}\big{)}.$

By the Gessel–Viennot–Lindström lemma, this amounts to considering $k$-tuples
of non-intersecting paths from the set $\\{(n,j)\colon n-k+1\leq j\leq n\\}$
to the set $\\{(i,n)\colon 1\leq i\leq k\\}$. It is clear that the tuple must
have one of its paths being $(n,n)\to(k,n)$ since one can only go straight up
from $(n,n)$ and one must avoid any intersections. Similarly, $(n,n-1)$ must
be linked with $(k-1,n)$, and this path consists of going up to the $(k-1)$-st
row, then across to $(k-1,n)$. Continuing in a similar vein, we see that the
only $k$-tuple of non-intersecting paths available to us is the collection of
up-right hooks from $(n,n-m+1)$ to $(m,n)$ for $1\leq m\leq k$.

For $j\in\\{n-k+1,n-k+2,\dots,n\\}$, we must traverse $n-j$ unit weight arrows
to get to $(j,j)$, after which we must traverse vertical non-unit arrows to
get to row $j+k-n$. The product along these weighted arrows is then

$\prod_{p=j+k-n}^{j-1}w_{p,j}^{(n)}.$

By noting that

$w_{p,j}^{(n)}=\dfrac{\prod\limits_{m=j+1}^{n}(\lambda_{j}-\lambda_{p+1})}{\prod\limits_{m=j}^{n}(\lambda_{m}-\lambda_{p})}=\dfrac{1}{\lambda_{j}-\lambda_{p}}\prod_{m=j+1}^{n}\dfrac{\lambda_{m}-\lambda_{p+1}}{\lambda_{m}-\lambda_{p}},$

the latter part of which telescopes over multiplying for consecutive values of
$p$, we see that

$\prod_{p=j+k-n}^{j-1}w_{p,j}^{(n)}=\left(\prod_{i=l+j-n}^{j-1}\dfrac{1}{\lambda_{j}-\lambda_{i}}\right)\prod_{m=j+1}^{n}\dfrac{\lambda_{m}-\lambda_{j}}{\lambda_{m}-\lambda_{j+k-n}}.$

We proceed to prove Lemma 6.3 showing that the result for $k-1$ and $n-1$
implies the result for $k,n$, and by proving that the result holds true for
all $n$ when $k=1$. Since the lemma only concerns $k<n$, this will prove all
cases of interest.

For $k=1$, we see this directly since

$(U(\lambda_{1},\dots,\lambda_{n}))_{1n}=\prod_{1\leq
m<n}\dfrac{1}{\lambda_{n}-\lambda_{m}}=\prod_{j=n-1+1}^{n}\prod_{i=1}^{n-1}\dfrac{1}{\lambda_{j}-\lambda_{i}}.$

For the induction hypothesis, suppose it is known that

$\Delta_{k}^{n}(U(\lambda_{1},\dots,\lambda_{n}))=\prod_{j=n-k+1}^{n}\prod_{i=1}^{n-k}\dfrac{1}{\lambda_{j}-\lambda_{i}}$

for some $1\leq k<n$.

Consider the graph $Q_{n+1}$ along with the $(k+1)$-tuple of non-intersecting
paths from the set $\\{(n+1,j)\colon n-k+1\leq j\leq n+1\\}$ to the set
$\\{(i,n+1)\colon 1\leq i\leq k+1\\}$. This $(k+1)$-tuple decomposes into a
“large hook” from $(n+1,n-k+1)$ to $(1,n+1)$, and a $k$-tuple of paths from
$\\{(n+1,j)\colon n-k\leq j\leq n+1\\}$ to the set $\\{(i,n+1)\colon 2\leq
i\leq k+1\\}$.

By our earlier observation of how $Q_{n}$ sits in the lower-right part of
$Q_{n+1}$ (we reduce all indices by one, both in the coordinates and in the
eigenvalues), the induction hypothesis (applied to $Q_{n}$, then translated
over to $Q_{n+1}$) tells us that this $k$-tuple of paths has product

$\Delta_{k}^{n}(U(\lambda_{2},\dots,\lambda_{n+1}))=\prod_{j=n-k+1}^{n}\prod_{i=1}^{n-k}\dfrac{1}{\lambda_{j+1}-\lambda_{i+1}}.$

The “large hook” has weight

$\prod_{p=1}^{n-k}w_{p,n-k+1}^{(n+1)}=\left(\prod_{i=1}^{n-k}\dfrac{1}{\lambda_{n-k+1}-\lambda_{i}}\right)\prod_{m=n-k+2}^{n+1}\dfrac{\lambda_{m}-\lambda_{n-k+1}}{\lambda_{m}-\lambda_{1}}.$

Thus, by the Gessel–Viennot–Lindström lemma and the induction hypothesis, we
have that $\Delta_{k+1}^{n+1}(U(\lambda_{1},\dots,\lambda_{n+1}))$ is equal to
the following:

$\displaystyle\left(\prod_{j=n-k+1}^{n}\prod_{i=1}^{n-k}\dfrac{1}{\lambda_{j+1}-\lambda_{i+1}}\right)\left(\prod_{i=1}^{n-k}\dfrac{1}{\lambda_{n-k+1}-\lambda_{i}}\right)\prod_{m=n-k+2}^{n+1}\dfrac{\lambda_{m}-\lambda_{n-k+1}}{\lambda_{m}-\lambda_{1}}$
$\displaystyle\qquad{}=\left(\prod_{j=n-k+2}^{n+1}\prod_{i=1}^{n-k}\dfrac{1}{\lambda_{j}-\lambda_{i+1}}\right)\left(\prod_{i=1}^{n-k}\dfrac{1}{\lambda_{n-k+1}-\lambda_{i}}\right)\prod_{m=n-k+2}^{n+1}\dfrac{\lambda_{m}-\lambda_{n-k+1}}{\lambda_{m}-\lambda_{1}}$
$\displaystyle\qquad{}=\left(\prod_{j=n-k+2}^{n+1}\prod_{i=1}^{n-k-1}\dfrac{1}{\lambda_{j}-\lambda_{i+1}}\right)\left(\prod_{i=1}^{n-k}\dfrac{1}{\lambda_{n-k+1}-\lambda_{i}}\right)\prod_{m=n-k+2}^{n+1}\dfrac{1}{\lambda_{m}-\lambda_{1}}$
$\displaystyle\qquad{}=\left(\prod_{j=n-k+2}^{n+1}\prod_{i=0}^{n-k-1}\dfrac{1}{\lambda_{j}-\lambda_{i+1}}\right)\left(\prod_{i=1}^{n-k}\dfrac{1}{\lambda_{n-k+1}-\lambda_{i}}\right)$
$\displaystyle\qquad{}=\left(\prod_{j=n-k+2}^{n+1}\prod_{i=1}^{n-k}\dfrac{1}{\lambda_{j}-\lambda_{i}}\right)\left(\prod_{i=1}^{n-k}\dfrac{1}{\lambda_{n-k+1}-\lambda_{i}}\right)$
$\displaystyle\qquad{}=\prod_{j=n-k+1}^{n+1}\prod_{i=1}^{n-k}\dfrac{1}{\lambda_{j}-\lambda_{i}},$

which is precisely the formula we wished to prove for
$\Delta_{k+1}^{n+1}U(\lambda_{1},\dots,\lambda_{n+1})$. This completes the
proof of Lemma 6.3.

###  B.2 Proof of Lemma 6.4

###### Proof.

Let $U$ and $V$ be the matrices defined by

$(U)_{ij}=\begin{cases}\displaystyle\prod\limits_{i\leq
m<j}\dfrac{1}{\lambda_{j}-\lambda_{m}}&\text{for }i\leq j,\\\
0&\text{otherwise},\end{cases}$

and

$(V)_{ij}=\begin{cases}0,&i>j,\\\ \displaystyle\prod_{i<m\leq
j}\dfrac{1}{\lambda_{i}-\lambda_{m}},&i\leq j.\end{cases}$

We first remark that the entries of $U$ and $V$ only depend on the indices
$(i,j)$ and not on $n$. Therefore, we see that the matrices have the following
block structure:

$U(\lambda_{1},\dots,\lambda_{n})=\left[\begin{array}[]{c|c}U(\lambda_{1},\dots,\lambda_{n-1})&\vec{u}_{n}\\\
\hline\cr 0&1\end{array}\right],\qquad
V=\left[\begin{array}[]{c|c}V_{[n-1],[n-1]}&\vec{v}_{n}\\\ \hline\cr
0&1\end{array}\right],$

where

$(\vec{u}_{n})_{i}=\prod_{i\leq m<n}\dfrac{1}{\lambda_{n}-\lambda_{m}},\qquad
i=1,2,\dots,n-1,$

and

$(\vec{v}_{n})_{i}=\prod_{i<m\leq n}\dfrac{1}{\lambda_{i}-\lambda_{m}},\qquad
i=1,2,\dots,n-1.$

Multiplying these matrices in these block forms yields:

$U(\lambda_{1},\dots,\lambda_{n})\times
V=\left[\begin{array}[]{c|c}U(\lambda_{1},\dots,\lambda_{n-1})V_{[n-1],[n-1]}&U(\lambda_{1},\dots,\lambda_{n-1})\vec{v}_{n}+\vec{u}_{n}\\\
\hline\cr 0&1\end{array}\right].$

Thus, we see that an induction would be appropriate here: if we have shown the
result for $n-1$, then the top-left block is the $(n-1)\times(n-1)$ identity
matrix, so we need only show that

$U(\lambda_{1},\dots,\lambda_{n-1})\vec{v}_{n}+\vec{u}_{n}=\vec{0}.$

The $n=1$ (base) case trivially holds, so we can proceed with the induction
step for $n>1$. We then need only establish the following to complete the
proof:

$0=\prod_{i\leq
m<n}\dfrac{1}{\lambda_{n}-\lambda_{m}}+\sum_{j=i}^{n-1}\left(\prod\limits_{i\leq
p<j}\dfrac{1}{\lambda_{j}-\lambda_{p}}\right)\left(\prod_{j<q\leq
n}\dfrac{1}{\lambda_{j}-\lambda_{q}}\right),$

which needs to be shown for each $i=1,2,\dots,n-1$.

Viewing the right-hand side as a rational function of $\lambda_{n}$, we see
that one should consider the rational function

$\prod_{i\leq m<n}\dfrac{1}{x-\lambda_{m}}.$

We set up a partial fraction decomposition:

$\prod_{i\leq
m<n}\dfrac{1}{x-\lambda_{m}}=\sum_{j=i}^{n-1}\dfrac{c_{j}}{x-\lambda_{j}}.$

We multiply both sides by $\prod_{i\leq m<n}(x-\lambda_{m})$:

$1=\sum_{j=i}^{n-1}c_{j}\prod_{\begin{subarray}{c}i\leq m<n\\\ m\neq
j\end{subarray}}(x-\lambda_{m}).$

Plugging in $x=\lambda_{j}$, we see that

$c_{j}\prod_{\begin{subarray}{c}i\leq m<n\\\ m\neq
j\end{subarray}}(\lambda_{j}-\lambda_{m})=1$

for each $j$. Hence,

$c_{j}=\prod_{\begin{subarray}{c}i\leq m<n\\\ m\neq
j\end{subarray}}\dfrac{1}{\lambda_{j}-\lambda_{m}}=\left(\prod\limits_{i\leq
p<j}\dfrac{1}{\lambda_{j}-\lambda_{p}}\right)\left(\prod_{j<q<n}\dfrac{1}{\lambda_{j}-\lambda_{q}}\right).$

To conclude, we have

$\displaystyle 0$ $\displaystyle=1-\sum_{j=i}^{n-1}\left(\prod\limits_{i\leq
p<j}\dfrac{1}{\lambda_{j}-\lambda_{p}}\right)\left(\prod_{j<q<n}\dfrac{1}{\lambda_{j}-\lambda_{q}}\right)\dfrac{1}{\lambda_{n}-\lambda_{j}}$
$\displaystyle=1+\sum_{j=i}^{n-1}\left(\prod\limits_{i\leq
p<j}\dfrac{1}{\lambda_{j}-\lambda_{p}}\right)\left(\prod_{j<q<n}\dfrac{1}{\lambda_{j}-\lambda_{q}}\right)\dfrac{1}{\lambda_{j}-\lambda_{n}}$
$\displaystyle=1+\sum_{j=i}^{n-1}\left(\prod\limits_{i\leq
p<j}\dfrac{1}{\lambda_{j}-\lambda_{p}}\right)\left(\prod_{j<q\leq
n}\dfrac{1}{\lambda_{j}-\lambda_{q}}\right).$

This completes the induction, and therefore proves Lemma 6.4. ∎

###  B.3 Proving Corollary 6.5

######  Lemma B.2.

Let $V$ be the matrix as in Lemma 6.4:

$(V)_{ij}=\begin{cases}0,&i>j,\\\ \displaystyle\prod_{i<m\leq
j}\dfrac{1}{\lambda_{i}-\lambda_{m}},&i\leq j.\end{cases}$

Then

$V_{ij}=\widehat{w}_{0}U(\lambda_{n},\dots,\lambda_{1})^{\rm
T}\widehat{w}_{0}.$

###### Proof.

Recall how we defined $U(\lambda_{1},\dots,\lambda_{n})$:

$(U)_{ij}=\begin{cases}\displaystyle\prod\limits_{i\leq
m<j}\dfrac{1}{\lambda_{j}-\lambda_{m}}&\text{for }i\leq j,\\\
0&\text{otherwise}.\end{cases}$

Therefore,

$(U(\lambda_{n},\dots,\lambda_{1}))_{ij}=\begin{cases}\displaystyle\prod\limits_{i\leq
m<j}\dfrac{1}{\lambda_{n-j+1}-\lambda_{n-m+1}}&\text{for }i\leq j,\\\
0&\text{otherwise}.\end{cases}$

We now prove that $V=\widehat{w}_{0}U(\lambda_{n},\dots,\lambda_{1})^{\rm
T}\widehat{w}_{0}$ by direct calculation:

$\displaystyle\big{(}\widehat{w}_{0}U(\lambda_{n},\dots,\lambda_{1})^{\rm
T}\widehat{w}_{0}\big{)}_{ij}$
$\displaystyle=\sum_{l=1}^{n}(\widehat{w}_{0})_{il}\big{(}U(\lambda_{n},\dots,\lambda_{1})^{\rm
T}\widehat{w}_{0}\big{)}_{lj}=\big{(}U(\lambda_{n},\dots,\lambda_{1})^{\rm
T}\widehat{w}_{0}\big{)}_{n-i+1,j}$
$\displaystyle=\sum_{m=1}^{n}\big{(}U(\lambda_{n},\dots,\lambda_{1})^{\rm
T}\big{)}_{n-i+1,m}(\widehat{w}_{0})_{m,j}$
$\displaystyle=\big{(}U(\lambda_{n},\dots,\lambda_{1})^{\rm
T}\big{)}_{n-i+1,n-j+1}=(U(\lambda_{n},\dots,\lambda_{1}))_{n-j+1,n-i+1}$
$\displaystyle=\begin{cases}\displaystyle\prod\limits_{n-j+1\leq
m<n-i+1}\dfrac{1}{\lambda_{i}-\lambda_{n-m+1}}&\text{if }i\leq j,\\\
0&\text{otherwise}\end{cases}$
$\displaystyle=\begin{cases}\displaystyle\prod\limits_{i<m\leq
j}\dfrac{1}{\lambda_{i}-\lambda_{m}}&\text{for }i\leq j,\\\
0&\text{otherwise},\end{cases}$

which is indeed $(V)_{ij}$. ∎

Since $\widehat{w}_{0}^{\rm T}=\widehat{w}_{0}$, the above result can be
equivalently expressed as

$U(\lambda_{1},\dots,\lambda_{n})^{-1}=(\widehat{w}_{0}U(\lambda_{n},\dots,\lambda_{1})\widehat{w}_{0})^{\rm
T}.$

We now use this lemma to prove Corollary 6.5:

###### Proof.

Since $V=U(\lambda_{1},\dots,\lambda_{n})^{-1}$,
$\Delta_{k}^{n}(V)=\Delta_{k}^{n}\big{(}U^{-1}\big{)}$ can be computed as
follows

$\displaystyle\Delta_{k}^{n}(V)$
$\displaystyle=\Delta_{k}^{n}\big{(}\widehat{w}_{0}U(\lambda_{n},\dots,\lambda_{1})^{\rm
T}\widehat{w}_{0}\big{)}$ $\displaystyle=\sum_{S\in{[n]\choose
k}}\det((\widehat{w}_{0})_{[k],S})\det\big{(}(U(\lambda_{n},\dots,\lambda_{1})^{\rm
T}\widehat{w}_{0})_{S,]k[}\big{)}$ $\displaystyle=(-1)^{\lfloor
k/2\rfloor}\det\big{(}(U(\lambda_{n},\dots,\lambda_{1})^{\rm
T}\widehat{w}_{0})_{]k[,]k[}\big{)}$ $\displaystyle=(-1)^{\lfloor
k/2\rfloor}\sum_{S\in{[n]\choose
k}}\det\big{(}U(\lambda_{n},\dots,\lambda_{1})^{\rm
T}\big{)}_{]k[,S})\det((\widehat{w}_{0})_{S,]k[})$
$\displaystyle=(-1)^{2\lfloor
k/2\rfloor}\det\big{(}U(\lambda_{n},\dots,\lambda_{1})^{\rm
T}\big{)}_{]k[,[k]})$
$\displaystyle=\det((U(\lambda_{n},\dots,\lambda_{1}))_{[k],]k[}).$

Therefore, by Lemma 6.3, we can deduce

$\Delta_{k}^{n}(U^{-1})=\Delta_{k}^{n}(V)=\prod_{j=n-k+1}^{n}\prod_{i=1}^{n-k}\dfrac{1}{\lambda_{n-j+1}-\lambda_{n-i+1}}=\prod_{j=1}^{k}\prod_{i=k+1}^{n}\dfrac{1}{\lambda_{j}-\lambda_{i}},$

thus, completing the proof of Corollary 6.5. ∎

### Acknowledgements

This work was supported by NSF grant DMS-1615921. We thank the referees for
their very careful reading of the manuscript.

## References

  * [1] Adler M., On a trace functional for formal pseudo differential operators and the symplectic structure of the Korteweg–de Vries type equations, Invent. Math. 50 (1978), 219–248.
  * [2] Aigner M., A course in enumeration, Graduate Texts in Mathematics, Vol. 238, Springer, Berlin, 2007.
  * [3] Arnold V.I., Mathematical methods of classical mechanics, Graduate Texts in Mathematics, Vol. 60, Springer-Verlag, New York – Heidelberg, 1978\.
  * [4] Berenstein A., Fomin S., Zelevinsky A., Parametrizations of canonical bases and totally positive matrices, Adv. Math. 122 (1996), 49–149.
  * [5] Deift P., Li L.C., Tomei C., Matrix factorizations and integrable systems, Comm. Pure Appl. Math. 42 (1989), 443–521.
  * [6] Drazin P.G., Johnson R.S., Solitons: an introduction, Cambridge Texts in Applied Mathematics, Cambridge University Press, Cambridge, 1989.
  * [7] Ercolani N.M., Flaschka H., Haine L., Painlevé balances and dressing transformations, in Painlevé Transcendents (Sainte-Adèle, PQ, 1990), NATO Adv. Sci. Inst. Ser. B: Phys., Vol. 278, Plenum, New York, 1992, 249–260.
  * [8] Ercolani N.M., Flaschka H., Singer S., The geometry of the full Kostant–Toda lattice, in Integrable Systems (Luminy, 1991), Progr. Math., Vol. 115, Birkhäuser Boston, Boston, MA, 1993, 181–225.
  * [9] Ercolani N.M., Ramalheira-Tsu J., The ghost-box-ball system: a unified perspective on soliton cellular automata, the RSK algorithm and phase shifts, Phys. D 426 (2021), 132986, 22 pages, arXiv:2101.07896.
  * [10] Flaschka H., The Toda lattice. II. Existence of integrals, Phys. Rev. B 9 (1974), 1924–1925.
  * [11] Flaschka H., Haine L., Variétés de drapeaux et réseaux de Toda, Math. Z. 208 (1991), 545–556.
  * [12] Fulton W., Harris J., Representation theory. A first course, Graduate Texts in Mathematics, Vol. 129, Springer-Verlag, New York, 1991.
  * [13] Kostant B., On Whittaker vectors and representation theory, Invent. Math. 48 (1978), 101–184.
  * [14] Kostant B., The solution to a generalized Toda lattice and representation theory, Adv. Math. 34 (1979), 195–338.
  * [15] Kuniba A., Okado M., Sakamoto R., Takagi T., Yamada Y., Crystal interpretation of Kerov–Kirillov–Reshetikhin bijection, Nuclear Phys. B 740 (2006), 299–327, arXiv:math.QA/0601630.
  * [16] Litvinov G.L., Maslov dequantization, idempotent and tropical mathematics: A brief introduction, J. Math. Sci. 140 (2007), 426–444, arXiv:math.GM/0507014.
  * [17] Litvinov G.L., Maslov V.P., Rodionov A.Ya., Sobolevski A.N., Universal algorithms, mathematics of semirings and parallel computations, in Coping with Complexity: Model Reduction and Data Analysis, Lect. Notes Comput. Sci. Eng., Vol. 75, Springer, Berlin, 2011, 63–89, arXiv:1005.1252.
  * [18] Lusztig G., Total positivity in reductive groups, in Lie Theory and Geometry, Progr. Math., Vol. 123, Birkhäuser Boston, Boston, MA, 1994, 531–568.
  * [19] Marsh R.J., Rietsch K., Parametrizations of flag varieties, Represent. Theory 8 (2004), 212–242, arXiv:math.RT/0307017.
  * [20] Moser J., Finitely many mass points on the line under the influence of an exponential potential – an integrable system, in Dynamical Systems, Theory and Applications (Rencontres, Battelle Res. Inst., Seattle, Wash., 1974), Lecture Notes in Phys., Vol. 38, Springer, Berlin, 1975, 467–497.
  * [21] O’Connell N., Geometric RSK and the Toda lattice, Illinois J. Math. 57 (2013), 883–918, arXiv:1308.4631.
  * [22] Strang G., Essays in linear algebra, Wellesley-Cambridge Press, Wellesley, MA, 2012\.
  * [23] Symes W.W., Hamiltonian group actions and integrable systems, Phys. D 1 (1980), 339–374.
  * [24] Symes W.W., Systems of Toda type, inverse spectral problems, and representation theory, Invent. Math. 59 (1980), 13–51.
  * [25] Takagi T., Inverse scattering method for a soliton cellular automaton, Nuclear Phys. B 707 (2005), 577–601, arXiv:math-ph/0406038.
  * [26] Takahashi D., Satsuma J., A soliton cellular automaton, J. Phys. Soc. Japan 59 (1990), 3514–3519.
  * [27] Toda M., Vibration of a chain with a non-linear interaction, J. Phys. Soc. Japan 22 (1967), 431–436.
  * [28] Tokihiro T., Ultradiscrete systems (cellular automata), in Discrete integrable systems, Lecture Notes in Phys., Vol. 644, Springer, Berlin, 2004, 383–424.
  * [29] Tokihiro T., Nagai A., Satsuma J., Proof of solitonical nature of box and ball systems by means of inverse ultra-discretization, Inverse Problems 15 (1999), 1639–1662.
  * [30] Viro O., Dequantization of real algebraic geometry on logarithmic paper, in European Congress of Mathematics, Vol. I (Barcelona, 2000), Progr. Math., Vol. 201, Birkhäuser, Basel, 2001, 135–146, arXiv:math.AG/0005163.
  * [31] Watkins D.S., Isospectral flows, SIAM Rev. 26 (1984), 379–391.