text:
# Tropical Robinson-Schensted-Knuth correspondence and birational Weyl group actions

## Introduction

This paper is an outcome of our attempt to understand internal connections among several appearances of the subtraction-free birational transformations.

There is a well-known procedure for passing from subtraction-free rational functions to piecewise linear functions. Roughly, this is the procedure of replacing the operations

$$aba+b,a/bab,a+b\mathrm{max}\{a,b\}(\text{or}\mathrm{min}\{a,b\}).$$

It can be applied consistently to an arbitrary rational function expressed as a ratio of two polynomials with positive real coefficients, in order to produce a combination of $`+`$, $``$ and $`\mathrm{max}`$ (or $`\mathrm{min}`$), representing a piecewise linear function. In combinatorics, this procedure has been employed for the algebraization of combinatorial algorithms. A large class of combinatorial algorithms can be described as piecewise linear transformations among discrete variables which take integer values. For such a piecewise linear transformation, it is meaningful in many cases to find a good subtraction-free rational counterpart; algebraic computation of subtraction-free rational functions may possibly bring out unexpected solutions to combinatorial problems. For this tropical approach to combinatorics, we refer the reader to ,  and the references therein.

In the context of discrete integrable systems, the same procedure is known as ultra-discretization . A remarkable example is the ultra-discretization of discrete Toda equation which provides with soliton cellular automata, called the box-ball systems . It is already recognized that the theory of box-ball systems is precisely the dynamics of crystal bases which arise as the $`q0`$ limit of representations of quantum groups (see , for example). The ultra-discretization of certain $`q`$-Painlevé systems can also be understood as a non-autonomous deformation of box-ball systems ; the time evolution of such (ultra-)discrete systems arises from the translation lattice of affine Weyl groups.

Another important aspect is the connection with the theory of totally positive matrices. Totally positive matrices have been studied extensively from the viewpoint of geometric approach to canonical bases , , , ; they provide a basic tool for producing nice subtraction-free rational transformations.

The purpose of this paper is to develop a new, elementary approach to the application of subtraction-free birational transformations to combinatorial problems. Our method is based on the decomposition and exchange of matrices, and the path representation of minor determinants. We employ such techniques to construct both subtraction-free rational and piecewise linear transformations for typical combinatorial algorithms, such as the bumping procedure, the Schützenberger involution and the Robinson-Schensted-Knuth correspondence (RSK correspondence, for short). Our matrix approach can be regarded as an integration of the idea of totally positive matrices and the technique of discrete Toda equations. We also investigate certain birational and piecewise linear actions of (affine) Weyl groups on matrices and tableaux.

This work was motivated by the impressive paper  by A.N. Kirillov. It was a great surprise for the authors to find that many formulas in , arising from combinatorics, were essentially the same as what we had encountered with in the context of discrete Painlevé systems. The matrix approach, as we will develop below, was a natural consequence of our attempt to clarify the theoretical background of this remarkable coincidence.

In view of the elementary nature of our approach, we have tried to make this paper as self-contained as possible. Many of the explicit formulas discussed in this paper can already be found in the literature (, , ). Also, many of the statements on decomposition of matrices are essentially contained in a series of works , ,  on totally positive matrices. We expect however that the results and techniques developed in this paper would be applicable to various problems both in combinatorics and in discrete integrable systems.

The authors would like to express their thanks to Professors S. Fomin, A.N. Kirillov, and A. Zelevinsky for valuable discussions.

Notes: The use of the phrase “tropical” comes originally from computer science; as in “tropical semirings”, this word has been used in a restrictive way to refer to the semiring structure on various set of numbers with respect to the pair of operations $`(\text{min},+)`$. We thank Prof. Fomin for directing our attention to this point. In the combinatorial literature, the same phrase seems to be used in a broader sense, mostly in such a situation that subtraction-free rational functions and piecewise linear functions appear more or less exchangeably; it also depends on the author on which side emphasis is put. In this paper, following  we use the word “tropical” tentatively to refer to objects concerning subtraction-free rational functions (see Section 1.3). This may not be identical to the traditional usage, but we could not find a better alternative.

## 1 Preliminaries

In this section, we give some preliminary remarks on the matrix approach to nonintersecting paths. In the last part of this section, we also give a summary on a canonical procedure for passing from subtraction-free rational functions to piecewise linear functions. In what follows, we fix the ground field $`𝕂`$, and set $`𝕂^{}=𝕂\{0\}`$. For a matrix $`X=\left(\begin{array}{c}x_j^i\end{array}\right)_{i,j}`$ given, we denote by

$$X_{j_1,\mathrm{},j_r}^{i_1,\mathrm{},i_r}=\left(\begin{array}{c}x_{j_b}^{i_a}\end{array}\right)_{a,b=1}^r,detX_{j_1,\mathrm{},j_r}^{i_1,\mathrm{},i_r}=det\left(\begin{array}{c}x_{j_b}^{i_a}\end{array}\right)_{a,b=1}^r$$
(1.1)
the $`r\times r`$ submatrix and the $`r`$-minor determinant of $`X`$ with row indices $`i_1,\mathrm{},i_r`$ and column indices $`j_1,\mathrm{},j_r`$, respectively.

### 1.1 Path representation of minor determinants

For an $`n`$-vector $`𝒙=(x_1,\mathrm{},x_n)(𝕂^{})^n`$ given, we introduce the following two matrices $`E(𝒙)`$ and $`H(𝒙)`$:

$$E(𝒙)=\text{diag}(𝒙)+\mathrm{\Lambda },H(𝒙)=(\text{diag}(𝒙)^1\mathrm{\Lambda })^1,$$
(1.2)
where $`\mathrm{\Lambda }=\left(\begin{array}{c}\delta _{j,i+1}\end{array}\right)_{i,j=1}^n`$ stands for the shift matrix. With the notation of matrix units $`E_{ij}=\left(\begin{array}{c}\delta _{a,i}\delta _{b,j}\end{array}\right)_{a,b=1}^n`$, these matrices can be written alternatively as

$$E(𝒙)=\underset{i=1}{\overset{n}{}}x_iE_{ii}+\underset{i=1}{\overset{n1}{}}E_{i,i+1},H(𝒙)=\underset{1ijn}{}x_ix_{i+1}\mathrm{}x_jE_{ij}.$$
(1.3)
For a given sequence of $`n`$-vectors $`𝒙^1,\mathrm{},𝒙^m`$, $`𝒙^i=(x_1^i,\mathrm{},x_n^i)(𝕂^{})^n`$, we define

$`E(𝒙^1,\mathrm{},𝒙^m)=E(𝒙^1)E(𝒙^2)\mathrm{}E(𝒙^m),`$
$`H(𝒙^1,\mathrm{},𝒙^m)=H(𝒙^1)H(𝒙^2)\mathrm{}H(𝒙^m).`$ (1.4)
Note that $`H(𝒙)=DE(\overline{𝒙})^1D^1`$, $`D=\text{diag}((1)^{i1})_{i=1}^n`$, where $`\overline{x}=(\overline{x}_1,\mathrm{},\overline{x}_n)`$, $`\overline{x}_j=\frac{1}{x_j}`$; we use the notation $`\overline{x}`$ for $`x^1`$ in order to avoid the conflict with that of upper indices. With this notation, the two matrices in $`(\text{1.1})`$ are related as

$$H(𝒙^1,\mathrm{},𝒙^m)=DE(\overline{𝒙}^m,\mathrm{},\overline{𝒙}^1)D^1.$$
(1.5)
In the following, we propose graphical expressions for the minor determinants of $`E(𝒙^1,\mathrm{},𝒙^m)`$ and $`H(𝒙^1,\mathrm{},𝒙^m)`$, in terms of nonintersecting paths.

We first consider the case of $`E(𝒙^1,\mathrm{},𝒙^m)`$. We represent the matrix $`E(𝒙)`$ by the diagram

(1.6)
with weight $`x_j`$ attached to the $`j`$-th vertical edge for each $`j=1,\mathrm{},n`$, and weight $`1`$ to each slanted edge. The $`(i,j)`$-component of $`E(𝒙)`$ can then be read off by the weight of paths from $`i`$ at the top to $`j`$ at the bottom. Piling up the diagrams for $`E(𝒙^1)`$,…$`E(𝒙^m)`$ all together, we obtain the following diagram for $`E(𝒙^1,\mathrm{},𝒙^m)`$.

(1.7)
Here we make all the edges oriented downward, to the south or to the southeast. The $`(i,j)`$-component of $`E(𝒙^1,\mathrm{},𝒙^m)`$ is then given as the sum of weights over all paths from $`i`$ at the top to $`j`$ at the bottom. It can also be expressed as

$$E(𝒙^1,\mathrm{},𝒙^m)_j^i=\underset{1k_i<k_{i+1}<\mathrm{}<k_{j1}m}{}\underset{b=i}{\overset{j}{}}\underset{a=k_{b1}+1}{\overset{k_b1}{}}x_b^a,$$
(1.8)
where $`k_{i1}=0`$ and $`k_j=m+1`$. Furthermore, we have

###### Proposition 1.1

For any choice of row indices $`i_1<\mathrm{}<i_r`$ and column indices $`j_1<\mathrm{}<j_r`$, the minor determinant $`detE(𝐱^1,\mathrm{},𝐱^m)_{j_1,\mathrm{},j_r}^{i_1,\mathrm{},i_r}`$ is expressed as the sum of weights over all $`r`$-tuples $`(\gamma _1,\mathrm{},\gamma _r)`$ of nonintersecting paths $`\gamma _k`$ from $`i_k`$ at the top to $`j_k`$ at the bottom $`(k=1,\mathrm{},r)`$.

(1.9)
This proposition is an immediate consequence of the theorem of Gessel-Viennot . In our context, however, it is also meaningful to understand this passage to nonintersecting paths through the multiplicative properties of minor determinants. Proposition 1.1 is essentially reduced to the multiplicative formula

$$det(XY)_{j_1,\mathrm{},j_r}^{i_1,\mathrm{},i_r}=\underset{k_1<\mathrm{}<k_r}{}detX_{k_1,\mathrm{},k_r}^{i_1,\mathrm{},i_r}detY_{j_1,\mathrm{},j_r}^{k_1,\mathrm{},k_r}$$
(1.10)
for minor determinants of the product of matrices. A key step is the following simple lemma. Note that the matrix $`E(𝒙)`$ is decomposed in the form

$$E(𝒙)=\text{diag}(𝒙)(1+\overline{x}_{n1}E_{n1,n})\mathrm{}(1+\overline{x}_2E_{2,3})(1+\overline{x}_1E_{1,2}).$$
(1.11)
Also, the minor determinant

$$det(1+aE_{k,k+1})_{j_1,\mathrm{},j_r}^{i_1,\mathrm{},i_r}(i_1<\mathrm{}<i_r,j_1<\mathrm{}<j_r)$$
(1.12)
vanishes unless either the two index sets $`I=\{i_1,\mathrm{},i_r\}`$ and $`J=\{j_1,\mathrm{},j_r\}`$ are identical, or $`J`$ is obtained from $`I`$ by replacing $`kI`$ by $`k+1`$. From this remark, we have

###### Lemma 1.2

For row indices $`i_1<\mathrm{}<i_r`$ and column indices $`j_1<\mathrm{}<j_r`$ given, the minor determinant $`detE(𝐱)_{j_1,\mathrm{},j_r}^{i_1,\mathrm{},i_r}`$ vanishes unless

$$j_a=i_a\text{or}i_{a+1}\text{for all}a=1\mathrm{},r.$$
(1.13)
If this is the case, $`detE(𝐱)_{j_1,\mathrm{},j_r}^{i_1,\mathrm{},i_r}`$ is the product of $`x_{j_a}`$ over all $`a`$ such that $`j_a=i_a`$.

Proposition 1.1 is then obtained from Lemma 1.2 by applying the multiplicative formula $`(\text{1.10})`$ to the decomposition $`E(𝒙^1,\mathrm{},𝒙^m)=E(𝒙^1)\mathrm{}E(𝒙^m)`$. Path representations as in $`(\text{1.9})`$ can also be translated into the language of tableaux; see for instance .

We now turn to the graphical representation of $`H(𝒙)`$ and $`H(𝒙^1,\mathrm{},𝒙^m)`$. We represent the matrix $`H(𝒙)`$ by the diagram

(1.14)
with weight $`x_j`$ attached to the $`j`$-th vertex ($`j=1,\mathrm{},m`$). Then piling up the diagrams for $`H(𝒙_1),\mathrm{},H(𝒙_m)`$, we obtain the $`m\times n`$ rectangle.

(1.15)
In this diagram for $`H(𝒙_1,\mathrm{},𝒙_m)`$, for each $`a=1,\mathrm{},m`$ and $`b=1,\mathrm{},n`$, we attach the weight $`x_b^a`$ to the vertex with coordinates $`(a,b)`$. This time, the weight of a path $`\gamma `$ is defined to be the product of all $`x_b^a`$’s attached to the vertices on $`\gamma `$.

###### Proposition 1.3

For any choice of row indices $`i_1<\mathrm{}<i_r`$ and column indices $`j_1<\mathrm{}<j_r`$, the minor determinant $`detH(𝐱^1,\mathrm{},𝐱^m)_{j_1,\mathrm{},j_r}^{i_1,\mathrm{},i_r}`$ is expressed as the sum of weights over all $`r`$-tuples $`(\gamma _1,\mathrm{},\gamma _r)`$ of nonintersecting paths $`\gamma _k:(1,i_k)(m,j_k)`$ $`(k=1,\mathrm{},r)`$.

(1.16)
The following corresponds to Lemma 1.2 for $`E(𝒙)`$.

###### Lemma 1.4

For row indices $`i_1<\mathrm{}<i_r`$ and column indices $`j_1<\mathrm{}<j_r`$ given, the minor determinant $`detH(𝐱)_{j_1,\mathrm{},j_r}^{i_1,\mathrm{},i_r}`$ vanishes unless

$$i_1j_1<i_2j_2<\mathrm{}<i_rj_r.$$
(1.17)
If this is the case, one has

$$detH(𝒙)_{j_1,\mathrm{},j_r}^{i_1,\mathrm{},i_r}=x_{i_1}\mathrm{}x_{j_1}x_{i_2}\mathrm{}x_{j_2}\mathrm{}x_{i_r}\mathrm{}x_{j_r}.$$
(1.18)
Note also

$$H(𝒙)=(1+x_1E_{1,2})(1+x_2E_{2,3})\mathrm{}(1+x_{n1}E_{n1,n})\text{diag}(𝒙).$$
(1.19)
In the following, we apply the same idea to nonintersecting paths in triangles and trapezoids. For this purpose, we define

$$\mathrm{\Lambda }_k=\underset{i=k}{\overset{n1}{}}E_{i,i+1}(k=1,\mathrm{},n),$$
(1.20)
so that $`\mathrm{\Lambda }_1=\mathrm{\Lambda }`$ and $`\mathrm{\Lambda }_n=0`$. With these truncated shift matrices, we introduce the following variations of $`E(𝒙)`$ and $`H(𝒙)`$:

$$E_k(𝒙)=\text{diag}(𝒙)+\mathrm{\Lambda }_k,H_k(𝒙)=(\text{diag}(\overline{𝒙})\mathrm{\Lambda }_k)^1$$
(1.21)
for $`k=1,\mathrm{},n`$. When we use these notations, we will tacitly assume that $`𝒙=(1,\mathrm{},1,x_k,\mathrm{},x_n)`$, i.e., $`x_j=1`$ $`(j<k)`$, unless otherwise mentioned. Under this convention, $`E_k(𝒙)`$ and $`H_k(𝒙)`$ are expressed as

$$E_k(𝒙)=\left[\begin{array}{cc}1& 0\\ 0& E(𝒙^{})\end{array}\right],H_k(𝒙)=\left[\begin{array}{cc}1& 0\\ 0& H(𝒙^{})\end{array}\right],$$
(1.22)
respectively, where $`𝒙^{}=(x_k,x_{k+1},\mathrm{},x_n)`$; we will often identify the $`(nk1)`$-vector $`(x_k,\mathrm{},x_n)`$ with the $`n`$-vector $`(1,\mathrm{},1,x_k,\mathrm{},x_n)`$, by putting $`1`$’s in front. Assuming that $`mn`$, let us consider a sequence of $`n`$-vectors $`𝒖^1,\mathrm{},𝒖^m`$, $`𝒖^i=(u_i^i,\mathrm{},u_n^i)`$, and arrange $`u_j^i`$ $`(ij)`$ in the form

$$U=\left(\begin{array}{c}u_j^i\end{array}\right)_{ij}=\left[\begin{array}{cccccc}u_1^1& u_2^1& \mathrm{}& u_m^1& \mathrm{}& u_n^1\\ & u_2^2& \mathrm{}& u_m^2& \mathrm{}& u_n^2\\ & & \mathrm{}& \mathrm{}& & \mathrm{}\\ & & & u_m^m& \mathrm{}& u_n^m\end{array}\right].$$
(1.23)
For such a table $`U`$ given, we define an $`n\times n`$ matrix $`E_U`$ by

$$E_U=E_1(𝒖^1)E_2(𝒖^2)\mathrm{},E_m(𝒖^m).$$
(1.24)
The entries of this matrix can be represented by the diagram

(1.25)
with the weights $`u_j^i`$ attached to the vertical edges; for each $`(i,j)`$ with $`1ijn`$, $`(E_U)_j^i`$ is the sum of weights over all paths $`\gamma `$ from $`i`$ at the top to $`j`$ along the lower rim. The minor determinants of $`E_U`$ are also represented by nonintersecting paths in diagram $`(\text{1.25})`$. We also introduce

$$H_U=H_m(𝒖^m)\mathrm{}H_2(𝒖^2)H_1(𝒖^1),$$
(1.26)
so that $`H_U=DE_{\overline{U}}^1D^1`$. The diagram for $`H_U`$ is given by

(1.27)
or alternatively by

(1.28)
with edges oriented upward or rightward. The minor determinants of $`H_U`$ are expressed in terms of nonintersecting paths in diagram $`(\text{1.27})`$ or $`(\text{1.28})`$.

### 1.2 Minor determinants of triangular matrices

The matrices $`E_U`$ discussed above can be thought of as canonical forms of generic upper triangular matrices $`M`$ of the form

$$M=\left[\text{}\right].$$
(1.29)
Let $`M=\left(\begin{array}{c}a_j^i\end{array}\right)_{i,j=1}^n`$ be an $`n\times n`$ upper triangular matrix satisfying the condition

$$a_j^i=0(j<i\text{or}j>i+m),a_j^i=1(j=i+m);$$
(1.30)
when $`m=n`$, this simply means that $`M`$ is upper triangular. For each $`(i,j)`$ with $`1ijn`$, introduce the notation of minor determinants

$$Q_{i,j}=Q_{i,j}(M)=detM_{i,i+1,\mathrm{},j}^{1,\mathrm{},ji+1};$$
(1.31)
when $`ji+1=0`$, we set $`Q_{i,j}=1`$. We remark that the condition $`(\text{1.30})`$ for an upper triangular matrix $`M`$ is equivalent to the condition

$$Q_{m+1,j}=1,Q_{i,j}=0(m+1<in),$$
(1.32)
for minor determinants. The following proposition is due to A. Berenstein, S. Fomin and A. Zelevinsky .

###### Proposition 1.5

Let $`M=\left(\begin{array}{c}a_j^i\end{array}\right)_{i,j=1}^n`$ be an $`n\times n`$ upper triangular matrix satisfying the condition $`(\text{1.30})`$ for some $`m`$ $`(1mn)`$. Suppose that $`Q_{i,j}0`$ for any $`(i,j)`$ with $`ij`$ and $`im`$. Then $`M`$ can be decomposed uniquely in the form

$$M=E_1(𝒗^1)E_2(𝒗^2)\mathrm{}E_m(𝒗^m),$$
(1.33)
where $`𝐯^i=(1,\mathrm{},1,v_i^i,\mathrm{},v_n^i)`$, $`v_j^i0`$, for $`i=1,\mathrm{},m`$. Furthermore, $`v_j^i`$ are determined by

$$v_i^i=Q_{i,i},v_j^i=\frac{Q_{i,j}Q_{i+1,j1}}{Q_{i+1,j}Q_{i,j1}}(i<j,im).$$
(1.34)
Proof: Assume first that $`M`$ is decomposed as in $`(\text{1.33})`$. Then the minor determinants of $`M`$ are expressed in terms of nonintersecting paths in diagram $`(\text{1.25})`$ for $`V=\left(\begin{array}{c}v_j^i\end{array}\right)_{ij}`$. In particular we have

$$Q_{i,j}=detM_{i,\mathrm{},j}^{1,\mathrm{},ji+1}=\underset{(a,b):ai,bj}{}v_j^i,$$
(1.35)
since there is only one $`(ji+1)`$-tuple of nonintersecting paths relevant to the path representation of this case. Expression $`(\text{1.34})`$ follows immediately from $`(\text{1.35})`$, which also implies the uniqueness of decomposition $`(\text{1.33})`$. It remains to show that $`M`$ has a decomposition of the form $`(\text{1.33})`$ under the condition on $`Q_{i,j}`$. We express $`M`$ in the form

$$M=\left[\begin{array}{cc}A& B\\ C& D\end{array}\right],$$
(1.36)
so that $`B`$ becomes a square matrix of size $`nm+1`$: $`B=M_{m,m+1,\mathrm{},n}^{1,\mathrm{},nm+1}`$. We can apply the Gauss decomposition to the matrix

$$B=\left[\text{}\right]$$
(1.37)
since

$$detB_{1,\mathrm{},r}^{1,\mathrm{},r}=detM_{m,\mathrm{},m+r1}^{1,\mathrm{},r}=Q_{m,m+r1}(M)0$$
(1.38)
for $`r=1,\mathrm{},nm+1`$. It also turns out that the lower and the upper triangular components of the Gauss decomposition $`B=B_{<0}B_0`$ are in the form

$$B_{<0}=\left[\text{}\right],B_0=\left[\text{}\right].$$
(1.39)
Denoting the diagonal entries of $`B_0`$ by $`v_m^m,\mathrm{},v_n^m`$, we introduce the vector $`𝒗^m=(1,\mathrm{},1,v_m^m,\mathrm{},v_n^m)`$. Then we have the following decomposition of $`M`$:

$$M=\left[\begin{array}{cc}A& B\\ C& D\end{array}\right]=\left[\begin{array}{cc}A& B_{<0}\\ C& D^{}\end{array}\right]\left[\begin{array}{cc}1& 0\\ 0& B_0\end{array}\right]=M^{}E_m(𝒗^m),$$
(1.40)
where $`D^{}=DB_0^1`$. The matrix $`M^{}`$ thus obtained satisfies the condition $`(\text{1.30})`$ with $`m`$ replaced by $`m1`$, as can be seen from the decomposition above. Also, if $`im1`$ and $`ij`$, from $`M=M^{}E_m(𝒗)`$ it follows that

$`Q_{i,j}(M)=detM_{i,\mathrm{},j}^{1,\mathrm{},ji+1}`$
$`=det(M^{})_{i,\mathrm{},j}^{1,\mathrm{},ji+1}detE_m(𝒗^m)_{i,\mathrm{},j}^{i,\mathrm{},j}`$
$`=Q_{i,j}(M^{})v_m^m\mathrm{}v_j^m0.`$ (1.41)
Hence we can apply the descending induction on $`m`$ to obtain the decomposition $`(\text{1.33})`$. Q.E.D.

We now translate Proposition 1.5 into a statement concerning the decomposition of type $`H_U`$. Let $`H`$ be an $`n\times n`$ invertible upper triangular matrix. For the decomposition of type $`H=H_U`$, it is convenient to use the following notation

$$\tau _j^i=\tau _j^i(H)=detH_{ji+1,\mathrm{},j}^{1,\mathrm{},i}(1ijn).$$
(1.42)
We also define $`\tau _j^0=1`$ for any $`j`$. Setting $`M=DH^1D^1`$, $`D=\text{diag}((1)^{i1})_{i=1}^n`$, we compare the minor determinants $`\tau _j^i=\tau _j^i(H)`$ and $`Q_{i,j}=Q_{i,j}(M)`$. We remark that

$$detH_{ji+1,\mathrm{},j}^{1,\mathrm{},i}=\frac{detM_{i+1,\mathrm{},n}^{1,\mathrm{},ji,j+1,\mathrm{},n}}{detM}=\frac{detM_{i+1,\mathrm{},j}^{1,\mathrm{},ji}}{detM_{1,\mathrm{},j}^{1,\mathrm{},j}};$$
(1.43)
for these particular minor determinants, we have no minus sign. This implies

$$\tau _j^i=\frac{Q_{i+1,j}}{Q_{1,j}},Q_{i,j}=\frac{\tau _j^{i1}}{\tau _j^j}(ij).$$
(1.44)
Note also that $`\tau _j^j=Q_{1,j}^1`$. Hence we see that the condition $`(\text{1.30})`$ is equivalent to

$$\tau _j^i=\delta _{i,j}\tau _j^m(m<ijn).$$
(1.45)
###### Proposition 1.6

Let $`H`$ be an $`n\times n`$ upper triangular matrix, and suppose that the minor determinants $`\tau _j^i=\tau _j^i(H)`$ $`(1ijn)`$ satisfy the condition

$$\tau _j^i0(1im),\tau _j^i=\delta _{i,j}\tau _j^m(m<in),$$
(1.46)
for some $`m`$ $`(1mn)`$. Then the matrix $`H`$ can be decomposed uniquely in the form

$$H=H_m(𝒖^m)\mathrm{}H_2(𝒖^2)H_1(𝒖^1),$$
(1.47)
where $`𝐮^i=(1,\mathrm{},1,u_i^i,\mathrm{},u_n^i)`$, $`u_j^i0`$, for $`i=1,\mathrm{},m`$. Furthermore $`u_j^i`$ are determined by

$$u_i^i=\frac{\tau _i^i}{\tau _i^{i1}},u_j^i=\frac{\tau _j^i\tau _{j1}^{i1}}{\tau _j^{i1}\tau _{j1}^i}(i<j,im).$$
(1.48)
Under the condition $`(\text{1.46})`$, from Proposition 1.5 we have

$$DH^1D^1=M=E_1(\overline{𝒖}^1)E_2(\overline{𝒖}^2)\mathrm{}E_m(\overline{𝒖}^m),$$
(1.49)
where we have set $`𝒖^i=\overline{𝒗}^i`$ $`(i=1,\mathrm{},m)`$. Once we have the decomposition $`(\text{1.47})`$, the minor determinants of $`H`$ is expressed in terms of nonintersecting paths in diagram $`(\text{1.28})`$ for $`U=\left(\begin{array}{c}u_j^i\end{array}\right)_{i,j}`$. In particular, each $`\tau _j^i`$ is expressed as

$$\tau _j^i=detH_{ji+1,\mathrm{},j}^{1,\mathrm{},i}=\underset{(a,b);ai,bj}{}u_b^a,$$
(1.50)
since there is only one $`i`$-tuple of nonintersecting paths relevant to this minor determinant. Expression $`(\text{1.48})`$ for $`u_j^i`$ follows immediately from $`(\text{1.50})`$.

Proposition 1.6 implies the following theorem concerning the path representation of minor determinants of a triangular matrix.

###### Theorem 1.7

Let $`H`$ be an $`n\times n`$ upper triangular matrix, and suppose that the minor determinants $`\tau _j^i=\tau _j^i(H)`$ $`(ij)`$ satisfy the condition

$$\tau _j^i0(1im),\tau _j^i=\delta _{i,j}\tau _j^m(m<in)$$
(1.51)
for some $`m`$ $`(1mn)`$. For each $`(i,j)`$ with $`1ijn`$, $`im`$, define

$$u_i^i=\frac{\tau _i^i}{\tau _i^{i1}},u_j^i=\frac{\tau _j^i\tau _{j1}^{i1}}{\tau _j^{i1}\tau _{j1}^i}(i<j,im).$$
(1.52)
Then, for any choice of row indices $`i_1<\mathrm{}<i_r`$ and column indices $`j_1<\mathrm{}<j_r`$, the minor determinant $`detH_{j_1,\mathrm{},j_r}^{i_1,\mathrm{},i_r}`$ is expressed as a sum

(1.53)
of weights associated with $`U=\left(\begin{array}{c}u_j^i\end{array}\right)_{i,j}`$, over all $`r`$-tuples of nonintersecting paths $`\gamma _k:(\mathrm{min}\{i_k,m\},i_k)(1,j_k)`$ from $`i_k`$ along the lower rim to $`j_k`$ at the top $`(k=1,\mathrm{},r)`$, in diagram $`(\text{1.28})`$.

###### Remark 1.8

Proposition 1.6 for $`m=n`$ can be reformulated as follows. Let us denote

$$=\{B=\left(\begin{array}{c}b_j^i\end{array}\right)_{i,j=1}^nGL_n(𝕂)b_j^i=0(i>j)\}$$
(1.54)
the group of all $`n\times n`$ invertible upper triangular matrices. For each $`U=\left(\begin{array}{c}u_j^i\end{array}\right)_{i,j=1}^n`$, we define $`H=\left(\begin{array}{c}h_j^i\end{array}\right)_{i,j=1}^n`$ by setting

$$h_j^i=\underset{\gamma :(i,i)(1,j)}{}u_\gamma (ij),h_j^i=0(i>j).$$
(1.55)
We now define two open subsets of $``$ as follows:

$`_0=\{U=\left(\begin{array}{c}u_j^i\end{array}\right)_{i,j=1}^nu_j^i0(ij)\},`$
$`_\tau =\{H=\left(\begin{array}{c}h_j^i\end{array}\right)\tau _j^i(H)0(ij)\}.`$ (1.56)
Then the correspondence $`UH`$ induces the isomorphism of affine varieties $`h:_0\stackrel{}{}_\tau `$. The inverse mapping $`HU`$ is given by

$$u_i^i=\frac{\tau _i^i}{\tau _i^{i1}},u_j^i=\frac{\tau _i^i\tau _{j1}^{i1}}{\tau _i^{i1}\tau _{j1}^i}(i<j),$$
(1.57)
where $`\tau _j^i=\tau _j^i(H)`$ for $`ij`$. Under this correspondence $`UH`$, for any choice of row indices $`i_1<\mathrm{}<i_r`$ and column indices $`j_1<\mathrm{}<j_r`$, the minor determinant $`detH_{j_1,\mathrm{},j_r}^{i_1,\mathrm{},i_r}`$ of $`H`$ is expressed as the sum of weights, associated with $`U`$, over all $`r`$-tuples of nonintersecting paths $`\gamma _k:(i_k,i_k)(1,j_k)`$ ($`k=1,\mathrm{},r`$).

### 1.3 Passage from tropical to combinatorial variables

We now assume that $`𝕂`$ is a field of characteristic 0. Consider the ring of polynomials $`𝕂[x]=𝕂[x_i(iI)]`$ in a set of variables $`x=(x_i)_{iI}`$. Denoting by

$$^{(I)}=\{\alpha =(\alpha _i)_{iI}\alpha _i=0\text{except for a finite number of }i\text{’s}\}$$
(1.58)
the set of multi-indices, we use the notation of multi-indices $`x^\alpha =_{iI}x_i^{\alpha _i}`$ for the monomials in the $`x`$-variables. Note that any polynomial $`a(x)𝕂[x]`$ is expressed uniquely in the form

$$a(x)=\underset{\alpha A}{}a_\alpha x^\alpha (a_\alpha 𝕂^{}),$$
(1.59)
as a sum of monomials over a finite subset $`A^{(I)}`$ of multi-indices, with nonzero coefficients. In this way, a polynomial $`a(x)`$ is identified with a pair $`(A,a)`$ of a finite subset $`A^{(I)}`$ and a mapping $`a:A𝕂`$. Note that $`0𝕂[x]`$ and $`c𝕂[x]`$ ($`c𝕂^{}`$) correspond to $`(\varphi ,\varphi )`$ and $`(\{0\},c)`$, respectively.

In the following, we fix a multiplicative subgroup $`𝕂_{>0}`$ of $`𝕂^{}`$ such that $`c,c^{}𝕂_{>0}c+c^{}𝕂_{>0}`$. We say that a nonzero rational function $`f(x)𝕂(x)=𝕂(x_i(iI))`$ in the $`x`$-variables is subtraction free (or tropical) with respect to the cone $`𝕂_{>0}`$ if it is expressed as a ratio

$$f(x)=\frac{a(x)}{b(x)}(a(x),b(x)𝕂_{>0}[x])$$
(1.60)
of two polynomials with coefficients in $`𝕂_{>0}`$. We denote by $`𝕂(x)_{>0}`$ the set of all subtraction-free rational functions with respect to $`𝕂_{>0}`$. It is clear that $`𝕂(x)_{>0}`$ forms again a multiplicative subgroup of $`𝕂(x)^{}`$ closed under the addition. It is worthwhile to note that all the coefficients of a polynomial $`f(x)𝕂(x)_{>0}`$ may not necessarily belong to $`𝕂_{>0}`$: Observe the example

$$f(x,y)=\frac{x^3+y^3}{x+y}=x^2xy+y^2.$$
(1.61)
For a subtraction-free rational function $`f=f(x)𝕂(x)_{>0}`$ given, choose an expression as $`(\text{1.60})`$. Expressing $`a(x)`$ and $`b(x)`$ as

$$a(x)=\underset{\alpha A}{}a_\alpha x^\alpha ,b(x)=\underset{\beta B}{}b_\beta x^\beta $$
(1.62)
with coefficients in $`𝕂_{>0}`$, we define two piecewise linear functions $`M(f)`$ and $`m(f)`$ on $`^I`$ by

$$\begin{array}{c}M(f)=\mathrm{max}\{\alpha ,x\alpha A\}\mathrm{max}\{\beta ,x\beta B\},\\ m(f)=\mathrm{min}\{\alpha ,x\alpha A\}\mathrm{min}\{\beta ,x\beta B\},\end{array}$$
(1.63)
where $`\alpha ,x=_{iI}\alpha _ix_i`$. In this definition, we have identified $`x=(x_i)_{iI}`$ with the canonical coordinates of $`^I`$. It is easily shown that the definition of $`M(f)`$ and $`m(f)`$ does not depend on the choice of expression $`(\text{1.60})`$. Note also that $`M(c)=m(c)=0`$ for any $`c𝕂_{>0}`$.

###### Proposition 1.9

$`(1)`$ For any subtraction-free rational functions $`f,g𝕂(x)_{>0}`$, one has

$`M(fg)=M(f)+M(g),M({\displaystyle \frac{f}{g}})=M(f)M(g),`$
$`M(f+g)=\mathrm{max}\{M(f),M(g)\},`$ (1.64)
and

$`m(fg)=m(f)+m(g),m({\displaystyle \frac{f}{g}})=m(f)m(g),`$
$`m(f+g)=\mathrm{min}\{m(f),m(g)\}.`$ (1.65)
$`(2)`$ Let $`\iota :𝕂(x)𝕂(x)`$ be the isomorphism defined by $`\iota (x_i)=x_i^1`$ $`(iI)`$. Then one has

$$M(f)=m(\iota (f)^1),m(f)=M(\iota (f)^1)$$
(1.66)
for any $`f𝕂(x)_{>0}`$.

This proposition means that the correspondence $`fM(f)`$ is nothing but the simple procedure of replacing the operations

$$aba+b,\frac{a}{b}ab,a+b\mathrm{max}\{a,b\}.$$
(1.67)
Similarly, the correspondence $`fm(f)`$ is the procedure

$$aba+b,\frac{a}{b}ab,a+b\mathrm{min}\{a,b\}.$$
(1.68)
The second part of the proposition implies that one can interchange “$`\mathrm{max}`$” and “$`\mathrm{min}`$” freely with each other, by using the operation $`f(x)\iota (f)^1=f(x^1)^1`$.

Proposition 1.9 guarantees that these procedures can be applied consistently to arbitrary subtraction-free rational functions to obtain piecewise linear functions. This passage from the subtraction-free rational functions to piecewise linear functions, either by $`\mathrm{max}`$ or $`\mathrm{min}`$, is called in several ways in the literature; it is called the ultra-discretization in the context of discrete integrable systems, and also the tropicalization in the context of totally positive matrices. In this paper, we will use the adjective “tropical” for objects and notions concerning subtraction-free rational functions, and “combinatorial” for those concerning piecewise linear functions. It should be noted that there is no canonical procedure in the opposite direction; when a combinatorial expression is given, it becomes an interesting problem in many occasions to find a good counterpart in the tropical setting.

The passage from the tropical side to the combinatorial side is functorial in the following sense. Consider two fields of rational functions $`𝕂(x)`$ in the variables $`x=(x_i)_{iI}`$ and $`𝕂(y)`$ in the variables $`y=(y_j)_{jJ}`$. We say that an isomorphism $`\phi `$ form $`𝕂(y)`$ into $`𝕂(x)`$ is subtraction free if $`\phi (y_j)𝕂(x)_{>0}`$ for all $`jJ`$. The set of subtraction-free rational functions $`f_j(x)=\phi (y_j)`$ ($`jJ`$) then defines a subtraction-free rational mapping

$$F:y_j=f_j(x)(jJ)$$
(1.69)
from the affine space $`𝕂^I`$ with coordinates $`x=(x_i)_{iI}`$ to $`𝕂^J`$ with coordinates $`y=(y_j)_{jJ}`$. For such a rational mapping $`F`$ given, we define two piecewise linear mappings $`M(F),m(F):^I^J`$ by setting

$$M(F):y_j=M(f_j(x))(jJ),m(F):y_j=m(f_j(x))(jJ),$$
(1.70)
respectively. Then Proposition 1.9 implies

###### Proposition 1.10

Consider the two subtraction-free rational mappings

$$F:y_j=f_j(x)(jJ),G:z_k=g_k(y)(kK).$$
(1.71)
Then the piecewise linear mappings corresponding to the composition $`GF`$ are given by

$$M(GF)=M(G)M(F),m(GF)=m(G)m(F).$$
(1.72)
## 2 Tropical row insertion and tropical tableaux

In this section we introduce a tropical analogue of row insertion by clarifying the internal structure of bumping. Combining this with the matrix approach of Section 1, we give explicit tropical and combinatorial formulas for describing the tableau obtained from a word by row insertion, and for the Schützenberger involution on the set of column strict tableaux.

### 2.1 Row insertion

Taking the set of letters $`\{1,\mathrm{},n\}`$, we consider a column strict tableau $`T`$ of shape $`\lambda `$, where $`\lambda =(\lambda _1,\lambda _2,\mathrm{},\lambda _m)`$ is a partition with $`l(\lambda )m`$. For each $`i=1,\mathrm{},m`$, we define a weakly increasing word

$$w_i=i^{x_i^i}(i+1)^{x_{i+1}^i}\mathrm{}n^{x_n^i}(x_i^i+\mathrm{}+x_n^i=\lambda _i)$$
(2.1)
by reading the $`i`$-th row of $`T`$ from left to right, where $`x_j^i`$ stands for the number of $`j`$’s appearing in the $`i`$-th row of $`T`$ for $`ij`$. For a weakly increasing word $`v=1^{a_1}2^{a_2}\mathrm{}n^{a_n}`$ given, consider the tableau $`T^{}=Tv`$ obtained by the row insertion of $`v`$ into $`T`$; we denote by $`w_i^{}=i^{y_i^i}(i+1)^{y_{i+1}^i}\mathrm{}n^{y_n^i}`$ the weakly increasing word representing the $`i`$-th row of $`T^{}`$ for $`i=1,\mathrm{},m^{}`$. Our question is : How can one describe $`y_j^i`$ explicitly in terms of $`x_j^i`$’s and $`a_j`$’s ?

The bumping procedure $`Tv`$ can be decomposed as follows.

$$\begin{array}{ccc}& v& \\ T& \text{}& T^{}\\ & \varphi & \end{array}:\begin{array}{ccc}& v=v_1& \\ w_1& \text{}& w_1^{}\\ & v_2& \\ w_2& \text{}& w_2^{}\\ & v_3& \\ & \mathrm{}& \end{array}$$
(2.2)
Here $`v_1=v`$, and for $`i=2,3,\mathrm{}`$, $`v_i=i^{a_i^i}(i+1)^{a_{i+1}^i}\mathrm{}n^{a_n^i}`$ stands for the weakly increasing word consisting of the letters that have bumped out from $`w_{i1}`$ by the row insertion of $`v_{i1}`$. In what follows, we use the diagram

$$\begin{array}{ccc}& v& \\ w& \text{}& w^{}\\ & v^{}& \end{array}\left(\begin{array}{cc}w=1^{x_1}2^{x_2}\mathrm{}n^{x_n},\hfill & v=1^{a_1}2^{a_2}\mathrm{}n^{a_n}\hfill \\ w^{}=1^{y_1}2^{y_2}\mathrm{}n^{y_n},\hfill & v^{}=1^{b_1}2^{b_2}\mathrm{}n^{b_n}\hfill \end{array}\right)$$
(2.3)
consisting of four weakly increasing words $`w`$, $`v`$, $`w^{}`$, $`v^{}`$, to indicate a procedure of inserting a word $`v`$ into $`w`$; $`w^{}=wv`$ denotes the resulting word, and $`v^{}`$ is the word of the letters bumped out from $`w`$. (We always have $`b_1=0`$ in this setting.) Our question is thus reduced to the problem of describing $`y_j`$ and $`b_j`$ in terms of $`x_j`$ and $`a_j`$ in this diagram. We also use the diagram of row insertion for the corresponding vectors of integers:

$$\begin{array}{ccc}& 𝒂& \\ 𝒙& \text{}& 𝒚\\ & 𝒃& \end{array}\left(\begin{array}{cc}𝒙=\left(\begin{array}{c}x_1,\mathrm{},x_n\end{array}\right),& 𝒂=\left(\begin{array}{c}a_1,\mathrm{},a_n\end{array}\right)\\ 𝒚=\left(\begin{array}{c}y_1,\mathrm{},y_n\end{array}\right),& 𝒃=\left(\begin{array}{c}b_1,\mathrm{},b_n\end{array}\right)\end{array}\right).$$
(2.4)
We now consider the procedure of row insertion as in $`(\text{2.3})`$. It is convenient to use the variables

$$\xi _j=x_1+x_2+\mathrm{}+x_j,\eta _j=y_1+y_2+\mathrm{}+y_j(j=1,\mathrm{},n).$$
(2.5)
Assume first that $`v=k^a`$ ($`k=1,\mathrm{},n`$); in this case, it is easy to see

$`\eta _j=\xi _j(j<k),\eta _k=\xi _k+a,`$
$`\eta _j=\mathrm{max}\{\xi _k+a,\xi _j\}=\mathrm{max}\{\eta _k,\xi _j\}(j>k).`$ (2.6)
Applying this result repeatedly for $`k=1,\mathrm{},n`$, we obtain following recurrence relations for the general case $`v=1^{a_1}2^{a_2}\mathrm{}n^{a_n}`$:

$`\eta _1=\xi _1+a_1,\eta _2=\mathrm{max}\{\eta _1,\xi _2\}+a_2,`$
$`\eta _3=\mathrm{max}\{\eta _1,\eta _2,\xi _3\}+a_3,\mathrm{}.`$ (2.7)
Since $`\eta _1\eta _2\mathrm{}\eta _n`$, it is equivalent to

$$\begin{array}{cc}\eta _1=\xi _1+a_1,\hfill & \\ \eta _j=\mathrm{max}\{\eta _{j1},\xi _j\}+a_j\hfill & \\ =\mathrm{max}\{\eta _{j1}+a_j,\xi _j+a_j\}(j=2,\mathrm{},n).\hfill & \end{array}$$
(2.8)
Hence we have

$`\eta _j=\mathrm{max}\{\xi _1+a_1+\mathrm{}+a_j,\xi _2+a_2+\mathrm{}+a_j,\mathrm{},\xi _j+a_j\}`$
$`=\underset{1kj}{\mathrm{max}}\{x_1+\mathrm{}+x_k+a_k+\mathrm{}+a_j\}`$ (2.9)
for $`j=1,\mathrm{},n`$. Note that

$$y_1=\eta _1,y_j=\eta _j\eta _{j1}(j=2,\mathrm{},n),$$
(2.10)
and that $`b_j`$ are determined as $`b_1=0`$ and

$$b_j=a_j+x_jy_j=a_j+\xi _j\xi _{j1}\eta _j+\eta _{j1}(j=2,\mathrm{},n),$$
(2.11)
since the number of $`j`$’s is conserved during the process.

###### Example 2.1

Let us consider an example of row insertion

$$\begin{array}{ccc}& v=1245& \\ w=\underset{¯}{2}2\underset{¯}{3}4\underset{¯}{5}\underset{¯}{}& \text{}& w^{}=122445\\ & v^{}=235& \end{array}.$$
(2.12)
In terms of the vectors of integers, this procedure is expressed as

$$\begin{array}{ccc}& 𝒂=(1,1,0,1,1)& \\ 𝒙=(0,2,1,1,1)& \text{}& 𝒚=(1,2,0,2,1)\\ & 𝒃=(0,1,1,0,1)& \end{array}.$$
(2.13)
The numbers

$$\eta _j=\underset{1kj}{\mathrm{max}}(x_1+\mathrm{}+x_k+a_k+\mathrm{}+a_j)$$
(2.14)
can be read off from the table

(2.15)
as

$$\eta _1=1,\eta _2=3,\eta _3=3,\eta _4=5,\eta _5=6.$$
(2.16)
By taking the first difference of this sequence, we have $`𝒚=(1,2,0,2,1)`$.

The general procedure $`T^{}=Tv`$ of inserting a weakly increasing word $`v`$ into a column strict tableau $`T`$ should be described as a superposition of row insertions of type $`(\text{2.3})`$. We will make use of the tropical analogue of combinatorial (piecewise linear) formulas above in order to systematize the superposition of row insertions.

### 2.2 Tropical row insertion

We introduce a tropical analogue of combinatorial formulas for the row insertion $`(\text{2.3})`$. We use the same symbols $`x_j`$, $`a_j`$, $`y_j`$, $`b_j`$ as in $`(\text{2.4})`$ for the tropical variables (indeterminates). Introducing the auxiliary variables

$$\xi _j=x_1\mathrm{}x_j,\eta _j=y_1\mathrm{}y_j(j=1,\mathrm{},n),$$
(2.17)
we define the transformation $`(𝒙,𝒂)(𝒚,𝒃)`$ by

$$\begin{array}{ccc}\eta _1=\xi _1a_1,\hfill & \eta _j=(\eta _{j1}+\xi _j)a_j\hfill & (j=2,\mathrm{},n),\hfill \\ y_1=\eta _1,\hfill & y_j=\frac{\eta _j}{\eta _{j1}}\hfill & (j=2,\mathrm{},n),\hfill \\ b_1=1,\hfill & b_j=a_j\frac{x_j}{y_j}=a_j\frac{\xi _j\eta _{j1}}{\xi _{j1}\eta _j}\hfill & (j=2,\mathrm{},n).\hfill \end{array}$$
(2.18)
We have made these formulas from the combinatorial formulas $`(\text{2.8})`$, $`(\text{2.10})`$, $`(\text{2.11})`$ by the simple rule of replacement

$$\mathrm{max}\{a,b\}a+b,a+babab\frac{a}{b},$$
(2.19)
which is sometimes called the tropical variable change. From the recurrence relations for $`\eta _j`$ above, we easily obtain

$`\eta _j=\xi _1a_1\mathrm{}a_j+\xi _2a_2\mathrm{}a_j+\mathrm{}+\xi _ja_j`$
$`=x_1a_1a_2\mathrm{}a_j+x_1x_2a_2\mathrm{}a_j+\mathrm{}+x_1\mathrm{}x_ja_j.`$ (2.20)
From this formula, we can recover the combinatorial formula $`(\text{2.1})`$ by the standard procedure as we discussed in Section 1.3.

The tropical transformation $`(𝒙,𝒂)(𝒚,𝒃)`$ we have discussed above arises also from the system of algebraic equations of discrete Toda type

$$\begin{array}{ccc}a_1x_1=y_1,\hfill & a_jx_j=y_jb_j\hfill & (j=2,\mathrm{},n),\hfill \\ \frac{1}{a_1}+\frac{1}{x_2}=\frac{1}{b_2},\hfill & \frac{1}{a_j}+\frac{1}{x_{j+1}}=\frac{1}{y_j}+\frac{1}{b_{j+1}}\hfill & (j=2,\mathrm{},n),\hfill \end{array}$$
(2.21)
for $`(y_1,\mathrm{},y_n)`$ and $`(b_2,\mathrm{},b_n)`$, where we regard $`x_j`$, $`a_j`$ as given variables, and $`y_j`$, $`b_j`$ as unknown functions. (For the relationship between $`(\text{2.21})`$ and the discrete Toda equation, see Remark 2.3 below)

###### Lemma 2.2

The system of algebraic equations $`(\text{2.21})`$ is equivalent to the recurrence formulas $`(\text{2.18})`$ together with $`(\text{2.17})`$.

Proof: In fact, by eliminating $`b_j`$ ($`j=2,\mathrm{},n`$) from $`(\text{2.21})`$, and by rewriting the equations in terms of $`\xi _j`$ and $`\eta _j`$, we obtain

$$\frac{\eta _n\eta _{n1}a_n}{\xi _na_n}=\frac{\eta _{n1}\eta _{n2}a_{n1}}{\xi _{n1}a_{n1}}=\mathrm{}=\frac{\eta _2\eta _1a_2}{\xi _2a_2}=\frac{\eta _1}{\xi _1a_1}=1,$$
(2.22)
which is equivalent to $`(\text{2.18})`$. Q.E.D.

This fact is a key to our matrix approach to tropical combinatorics. Note that $`(\text{2.21})`$ is written as a matrix equation:

$`\left[\begin{array}{ccccc}\overline{a}_1& 1& & & \\ & \overline{a}_2& 1& \\ & & \mathrm{}& \mathrm{}& \\ & & & \overline{a}_{n1}& 1\\ & & & & \overline{a}_n\end{array}\right]\left[\begin{array}{ccccc}\overline{x}_1& 1& & & \\ & \overline{x}_2& 1& \\ & & \mathrm{}& \mathrm{}& \\ & & & \overline{x}_{n1}& 1\\ & & & & \overline{x}_n\end{array}\right]`$
$`=\left[\begin{array}{ccccc}\overline{y}_1& 1& & & \\ & \overline{y}_2& 1& \\ & & \mathrm{}& \mathrm{}& \\ & & & \overline{y}_{n1}& 1\\ & & & & \overline{y}_n\end{array}\right]\left[\begin{array}{ccccc}1& 0& & & \\ & \overline{b}_2& 1& \\ & & \mathrm{}& \mathrm{}& \\ & & & \overline{b}_{n1}& 1\\ & & & & \overline{b}_n\end{array}\right],`$ (2.23)
where we have used the notation $`\overline{x}=\frac{1}{x}`$. By using the notation of Section 1, this equation can be expressed as

$$E(\overline{𝒂})E(\overline{𝒙})=E_1(\overline{𝒚})E_2(\overline{𝒃}).$$
(2.24)
It is also equivalent to

$$H(𝒙)H(𝒂)=H_2(𝒃)H_1(𝒚).$$
(2.25)
Each of these two equations $`(\text{2.24})`$ and $`(\text{2.25})`$ can be thought of as a tropical expression of the row insertion

$$\begin{array}{ccc}& 𝒂& \\ 𝒙& \text{}& 𝒚\\ & 𝒃& \end{array}\left(\begin{array}{cc}𝒙=\left(\begin{array}{c}x_1,\mathrm{},x_n\end{array}\right),& 𝒂=\left(\begin{array}{c}a_1,\mathrm{},a_n\end{array}\right)\\ 𝒚=\left(\begin{array}{c}y_1,\mathrm{},y_n\end{array}\right),& 𝒃=\left(\begin{array}{c}b_1,\mathrm{},b_n\end{array}\right)\end{array}\right),$$
(2.26)
where $`b_1=1`$.

We show how the matrix equation $`(\text{2.24})`$ is solved by using the path representations of Section 1. Setting $`H=H(𝒙)H(𝒂)`$, we look at the minor determinants $`\tau _j^i(H)`$ $`(ij)`$. By the argument of Section 1, the minor determinants of $`H`$ are read off from the following diagram.

(2.27)
The result for $`\tau _j^i=\tau _j^i(H)`$ is:

$$\begin{array}{cc}\tau _j^1=\underset{k=1}{\overset{j}{}}x_1\mathrm{}x_ka_k\mathrm{}a_j\hfill & (j1),\hfill \\ \tau _j^2=\tau _j^j=x_1\mathrm{}x_ja_1\mathrm{}a_j\hfill & (j2),\hfill \\ \tau _j^i=0\hfill & (3i<jn).\hfill \end{array}$$
(2.28)
By Proposition 1.6, we already know that equation $`(\text{2.25})`$ has a unique solution such that

$$\tau _j^1=y_1\mathrm{}y_j(j=1,\mathrm{},n),\tau _j^2=y_1\mathrm{}y_jb_1\mathrm{}b_j(j=2,\mathrm{},n).$$
(2.29)
Namely, $`y_j`$ and $`b_j`$ are determined as

$$y_j=\frac{\tau _j^1}{\tau _{j1}^1}(j=1,\mathrm{},n),b_j=\frac{x_ja_j}{y_j}(j=2,\mathrm{},n),$$
(2.30)
consistently with what we have seen before.

###### Remark 2.3

The system of algebraic equations $`(\text{2.21})`$ is closely related to the discrete Toda equation (, ):

$$I_i^{t+1}V_i^{t+1}=I_{i+1}^tV_i^t,I_i^{t+1}+V_{i1}^{t+1}=I_i^t+V_i^t$$
(2.31)
where $`i`$ and $`t`$ stand for the discrete coordinates of space and time, respectively, and $`I_i^t`$, $`V_i^t`$ are the dependent variables. If we set

$$a_i=(I_{i+1}^t)^1,x_i=(V_i^t)^1,y_i=(V_i^{t+1})^1,b_i=(I_i^{t+1})^1,$$
(2.32)
we have

$$a_ix_i=y_ib_i,\frac{1}{a_i}+\frac{1}{x_{i+1}}=\frac{1}{y_i}+\frac{1}{b_{i+1}}(i).$$
(2.33)
Note also that the discrete Toda equation can be expressed as the matrix equation

$$L(t+1)R(t+1)=R(t)L(t)$$
(2.34)
for the $`\times `$ matrices

$$L(t)=\underset{i}{}E_{ii}+\underset{j}{}V_i^tE_{i+1,i},R(t)=\underset{i}{}I_i^tE_{ii}+\underset{i}{}E_{i,i+1}.$$
(2.35)
### 2.3 Tropical tableaux

In the following we discuss the following question both in the tropical and the combinatorial setting.

Question: For a sequence of weakly increasing words $`w_1,\mathrm{},w_m`$ given, find an explicit formula for the column strict tableau

$$P=P(w)=(\mathrm{}(w_1w_2)\mathrm{}w_m)$$
(2.36)
obtained from the word $`w=w_1\mathrm{}w_m`$ by the row insertion.

We can employ $`(\text{2.25})`$ as building blocks for the tropical analogue of various combinatorial algorithms. Let us consider the procedure of successive row insertion

$$P=(\mathrm{}(w_1w_2)\mathrm{}w_m)$$
(2.37)
of weakly increasing word $`w_i=1^{x_1^i}\mathrm{}n^{x_n^i}`$ ($`i=1,\mathrm{},n`$) to obtain a column strict tableau $`P`$. This procedure can be described by the following diagram.

$$\begin{array}{cccccccc}& 𝒙^1=𝒙^{1,1}& & 𝒙^2=𝒙^{2,1}& & 𝒙^3=𝒙^{3,1}& & \\ \varphi & \text{}& 𝒚^{1,1}& \text{}& 𝒚^{2,1}& \text{}& \mathrm{}& \\ & \varphi & & 𝒙^{2,2}& & 𝒙^{3,2}& & \\ & & \varphi & \text{}& 𝒚^{2,2}& \text{}& \mathrm{}& \\ & & & \varphi & & 𝒙^{3,3}& & \\ & & & & \varphi & \text{}& \mathrm{}& \end{array}$$
(2.38)
Passing the tropical variables $`𝒙^i=(x_1^i,\mathrm{},x_n^i)`$ ($`i=1,\mathrm{},m`$), we can compute the row insertion above as

$$\begin{array}{cccccc}\hfill H(𝒙^1)& =H_1(𝒚^{1,1})\hfill & & & & \\ \hfill H(𝒙^1)H(𝒙^2)& =H_1(𝒚^{1,1})H(𝒙^{2,1})\hfill & & & & \\ & =H_2(𝒚^{2,2})H_1(𝒚^{2,1})\hfill & & & & \\ \hfill H(𝒙^1)H(𝒙^2)H(𝒙^3)& =H_2(𝒚^{2,2})H_1(𝒚^{2,1})H(𝒙^3)\hfill & & & & \\ & =H_2(𝒚^{2,2})H_2(𝒙^{3,2})H_1(𝒚^{3,1})\hfill & & & & \\ & =H_3(𝒚^{3,3})H_2(𝒚^{3,2})H_1(𝒚^{3,1})\hfill & & & & \\ & \mathrm{},\hfill & & & & \end{array}$$
(2.39)
where $`𝒚^{k,i}=(1,\mathrm{},1,y_i^{k,i},\mathrm{},y_n^{k,i})`$. When $`mn`$, by setting $`𝒚^{m,i}=𝒑^i`$ , $`𝒑^i=(1,\mathrm{},1,p_i^i,\mathrm{},p_n^i)`$ ($`i=1,\mathrm{},m`$), we finally obtain

$$H(𝒙^1)H(𝒙^2)\mathrm{}H(𝒙^m)=H_m(𝒑^m)\mathrm{}H_2(𝒑^2)H_1(𝒑^1),$$
(2.40)
In this formula, each $`p_j^i`$ ($`ij`$) denotes the tropical variable corresponding to the number of $`j`$’s in the $`i`$-th row of the tableau $`P`$. Namely, we can regard the expression

$$H_P=H_m(𝒑^m)\mathrm{}H_2(𝒑^2)H_1(𝒑^1)$$
(2.41)
as representing the tropical tableau $`P=\left(\begin{array}{c}p_j^i\end{array}\right)_{ij}`$; it provides the tropical analogue of a general column strict tableau whose shape is a partition of length $`m`$.

The argument above shows that our question can be answered by considering the matrix equation

$`H(𝒙^1)H(𝒙^2)\mathrm{}H(𝒙^m)=H_m(𝒑^m)\mathrm{}H_2(𝒑^2)H_1(𝒑^1)(mn),`$
$`H(𝒙^1)H(𝒙^2)\mathrm{}H(𝒙^m)=H_n(𝒑^n)\mathrm{}H_2(𝒑^2)H_1(𝒑^1)(mn)`$ (2.42)
for the unknowns $`𝒑^i=(1,\mathrm{},1,p_i^i,\mathrm{},p_n^i)`$ $`(i=1,\mathrm{},\mathrm{min}\{m,n\})`$. In the following we regard $`x_j^i`$ ($`i=1,\mathrm{}`$, $`j=1,\mathrm{},n`$) as indeterminates, and look for solutions $`p_j^i`$ of $`(\text{2.3})`$ in the filed of rational functions in the $`x`$-variables.

Denoting the left-hand side by $`H`$, consider the minor determinants $`\tau _j^i(H)=detH_{ji+1,\mathrm{},j}^{1,\mathrm{},i}`$ for $`1ijn`$. By Proposition 1.3, $`\tau _j^i(H)`$ is expressed in terms of the nonintersecting paths in the $`m\times n`$ rectangle associated with the matrix $`X=\left(\begin{array}{c}x_j^i\end{array}\right)_{i,j}`$:

(2.43)
When $`m<ijn`$, we have $`\tau _j^i(H)=\delta _{i,j}\tau _j^m(H)`$, $`\tau _j^m(H)=_{(a,b);bj}x_b^a`$. Hence, by Theorem 1.7, we see that the matrix equation $`(\text{2.3})`$ has a unique rational solution in the $`x`$-variables; the solution is expressed by $`\tau _j^i(H)`$ above. To summarize, we have

###### Theorem 2.4

For $`m\times n`$ indeterminates $`x_j^i`$ $`(1im,\mathrm{\hspace{0.17em}1}jn)`$ given, consider the following matrix equation for unknown variables $`p_j^i`$ $`(1il,1jn,ij)`$, $`l=\mathrm{min}\{m,n\}`$$`:`$

$$H(𝒙^1)H(𝒙^2)\mathrm{}H(𝒙^m)=H_l(𝒑^l)\mathrm{}H_2(𝒑^2)H_1(𝒑^1),$$
(2.44)
where $`𝐱^i=(x_1^i,\mathrm{},x_n^i)`$ and $`𝐩^i=(1,\mathrm{},1,p_i^i,\mathrm{},p_n^i)`$. This equation has a unique rational solution in the $`x`$-variables ; it is given explicitly as

$$p_i^i=\frac{\tau _i^i}{\tau _i^{i1}},p_j^i=\frac{\tau _j^i\tau _{j1}^{i1}}{\tau _j^{i1}\tau _{j1}^i}(i<j)$$
(2.45)
for $`1il`$, $`1jn`$, with $`\tau _j^i`$ $`(ij)`$ defined as the sum

$$\tau _j^i=\underset{(\gamma _1,\mathrm{},\gamma _i)}{}x_{\gamma _1}\mathrm{}x_{\gamma _i}$$
(2.46)
of monomials over all $`i`$-tuples of nonintersecting paths $`\gamma _k:(1,k)(m,ji+k)`$ $`(k=1,\mathrm{},i)`$ in the $`m\times n`$ rectangle. Here, the weight $`x_\gamma `$ of a path $`\gamma `$ is the product

$$x_\gamma =\underset{(a,b)\gamma }{}x_b^a$$
(2.47)
of all $`x_b^a`$’s corresponding to the vertices on $`\gamma `$.

The explicit formula for $`p_j^i`$ above is formulated by A.N. Kirillov , Theorem 4.23.

By the standard passage from subtraction-free rational functions to piecewise-linear functions, we obtain the following combinatorial formula (, Theorem 3.5) for the column strict tableaux $`P`$ obtained from a word $`w=w_1w_2\mathrm{}w_m`$ by the row insertion.

###### Theorem 2.5

Taking the set of letters $`\{1,\mathrm{},n\}`$, let $`w_1,\mathrm{},w_m`$ be a sequence of weakly increasing words $`w^i=1^{x_1^i}\mathrm{}n^{x_n^i}`$ $`(i=1,\mathrm{},m)`$. Consider the column strict tableau

$$P=P(w)=(\mathrm{}(w_1w_2)\mathrm{}w_m)$$
(2.48)
obtained from the word $`w=w_1w_2\mathrm{}w_m`$ by row insertion, and denote by $`i^{p_i^i}\mathrm{}n^{p_n^i}`$ the weakly increasing word representing the $`i`$-th row of $`P`$, for $`i=1,\mathrm{},l`$, $`l=\mathrm{min}\{m,n\}`$. Then, for each $`(i,j)`$, the number $`p_j^i`$ of the letter $`j`$ in the $`i`$-th row of $`P`$ is determined explicitly as

$$p_i^i=\tau _i^i\tau _i^{i1},p_j^i=\tau _j^i\tau _j^{i1}\tau _{j1}^i+\tau _{j1}^{i1}(i<j)$$
(2.49)
with $`\tau _j^i`$ $`(ij)`$ defined as the maximum

$$\tau _j^i=\underset{(\gamma _1,\mathrm{},\gamma _i)}{\mathrm{max}}(x_{\gamma _1}+\mathrm{}+x_{\gamma _i})$$
(2.50)
of weights over all $`i`$-tuples of nonintersecting paths $`\gamma _k:(1,k)(m,ji+k)`$ $`(k=1,\mathrm{},i)`$ in the $`m\times n`$ rectangle ; we set $`\tau _j^0=0`$ for all $`j`$. Here, the weight $`x_\gamma `$ of a path $`\gamma `$ is the sum

$$x_\gamma =\underset{(a,b)\gamma }{}x_b^a$$
(2.51)
of all $`x_b^a`$’s corresponding to the vertices on $`\gamma `$.

Note also that each $`\tau _j^i`$ represents the sum of $`p_b^a`$’s in the region $`ai`$, $`bj`$:

$$\tau _j^i=\underset{(a,b):ai,bj}{}p_b^a(ij).$$
(2.52)
###### Example 2.6

We give an example with $`m=3`$, $`n=4`$ by taking the word

$$w=2234134411224=2234|1344|11224,$$
(2.53)
which corresponds to the column strict tableau

$$P=P(w)=\begin{array}{cccccccccc}1\hfill & 1\hfill & 1\hfill & 2\hfill & 2\hfill & 4\hfill & 4\hfill & & & \\ 2\hfill & 2\hfill & 3\hfill & 3\hfill & 4\hfill & & & & & \\ 4\hfill & & & & & & & & & \end{array}.$$
(2.54)
From $`w`$, we first construct the $`3\times 4`$ matrix $`X=\left(\begin{array}{c}x_j^i\end{array}\right)_{i,j}`$ by counting the number of $`j`$’s in the $`i`$-th block of $`w`$:

$$X=\left[\begin{array}{cccc}0& 2& 1& 1\\ 1& 0& 1& 2\\ 2& 2& 0& 1\end{array}\right].$$
(2.55)
The numbers $`\tau _j^i`$ of $`(\text{2.50})`$ are determined from $`X`$ by statistics of nonintersecting paths:

$$𝝉=\left(\begin{array}{c}\tau _j^i\end{array}\right)_{i,j}=\left[\begin{array}{cccc}3& 5& 5& 7\\ & 7& 9& 12\\ & & 9& 13\end{array}\right].$$
(2.56)
For instance, $`\tau _3^2`$ is computed as the maximum of weights over three pairs of nonintersecting paths $`(\gamma _1,\gamma _2)`$ such that $`\gamma _1:(1,1)(3,2)`$ and $`\gamma _2:(1,2)(3,3)`$ :

$$X=\text{}$$
(2.57)
From

$$\begin{array}{c}(0+1+2+2)+(2+0+1+0)=8\hfill \\ (0+1+2+2)+(2+1+1+0)=9\hfill \\ (0+1+0+2)+(2+1+1+0)=7\hfill \end{array}$$
(2.58)
we get

$$\tau _3^2=\mathrm{max}\{8,9,7\}=9.$$
(2.59)
According to $`(\text{2.49})`$, we compute $`p_j^i`$ by taking the discrete Laplacian of $`\tau _j^i`$:

$$𝒑=\left(\begin{array}{c}p_j^i\end{array}\right)_{i,j}=\left[\begin{array}{cccc}3& 2& 0& 2\\ & 2& 2& 1\\ & & 0& 1\end{array}\right].$$
(2.60)
Then $`p_j^i`$ gives the number of $`j`$’s in the $`i`$-th row of the tableau $`P`$ above.

### 2.4 Tropical Schützenberger involution

We now recall the Schützenberger involution on the set of column strict tableaux. Taking the set $`\{1,2\mathrm{},n\}`$ of letters as before, we define an involution $`kk^{}`$ on $`\{1,2\mathrm{},n\}`$ by $`k^{}=nk+1`$ for $`k=1,\mathrm{},n`$. For a word $`w=k_1k_2\mathrm{}k_l`$ consisting of letters in $`\{1,\mathrm{},n\}`$ given, we define the word $`w^{}`$ by

$$w^{}=k_l^{}\mathrm{}k_2^{}k_1^{},$$
(2.61)
by applying $`kk^{}`$ to each letter, and then by reversing the order. Let us denote by $`P=P(w)`$ the column strict tableau obtained from a word $`w`$. Since the involution $`ww^{}`$ on the set of words preserve the Knuth equivalence, it induces an involution $`PP^{\text{ s}}`$ on the set of column strict tableaux such that

$$P(w^{})=P(w)^{\text{ s}}$$
(2.62)
for any word $`w`$; we call this involution $`PP^{\text{ s}}`$ the Schützenberger involution. It is well known that $`P`$ and $`P^{\text{ s}}`$ has the same shape, and that the column strict tableau $`P^{\text{ s}}`$ is obtained from $`P`$ as the evacuation tableau by a successive application of jeu de taquin. We remark that, when the word $`w=k_1\mathrm{}k_n`$ represents a permutation in $`𝑺_n`$, $`w^{}`$ is the conjugation of $`w`$ by the longest element of $`𝑺_n`$. (Schützenberger’s algorithm for column strict tableaux can be obtained essentially from , Theorem 3.9.4, for instance. In , Schützenberger’s algorithm is formulated for permutations, but it is not difficult to extend it to that for words.)

###### Example 2.7

Consider the word $`w=42213132`$ with $`n=4`$. In this case, we have $`w^{}=32424331`$.

$$P=P(w)=\begin{array}{cccccccccc}1\hfill & 1\hfill & 2\hfill & 3\hfill & & & & & & \\ 2\hfill & 2\hfill & 3\hfill & & & & & & & \\ 4\hfill & & & & & & & & & \end{array},P^{\text{ s}}=P(w^{})=\begin{array}{cccccccccc}1\hfill & 2\hfill & 3\hfill & 3\hfill & & & & & & \\ 2\hfill & 4\hfill & 4\hfill & & & & & & & \\ 3\hfill & & & & & & & & & \end{array}.$$
(2.63)
Let us decompose a given word $`w`$ into a chain of weakly increasing words:

$$w=w_1w_2\mathrm{}w_m,w_i=1^{x_1^i}2^{x_2^i}\mathrm{}n^{x_n^i}(i=1,\mathrm{},m).$$
(2.64)
Then we have

$$w^{}=w_n^{}\mathrm{}w_2^{}w_1^{},w_i^{}=1^{x_n^i}2^{x_{n1}^i}\mathrm{}n^{x_1^i}(i=1,\mathrm{},m).$$
(2.65)
Setting $`P=P(w)`$, $`P^{\text{ s}}=P(w^{})`$, we denote by $`p_j^i`$ and by $`\stackrel{~}{p}_j^i`$ the number of $`j`$’s in the $`i`$-th row of $`P`$ and $`P^{\text{ s}}`$, respectively. Passing to the tropical variables, we have the matrix equation

$`H(𝒙^1)H(𝒙^2)\mathrm{}H(𝒙^m)=H_P=H_l(𝒑^n)\mathrm{}H_2(𝒑^2)H_1(𝒑^1),`$
$`H(𝒙_{}^m)\mathrm{}H(𝒙_{}^2)H(𝒙_{}^1)=H_{P^{\text{ s}}}=H_l(\stackrel{~}{𝒑}^n)\mathrm{}H_2(\stackrel{~}{𝒑}^2)H_1(\stackrel{~}{𝒑}^1),`$ (2.66)
where $`l=\mathrm{min}\{m,n\}`$ and, for a vector $`𝒙=(x_1,x_2,\mathrm{},x_n)`$ given, $`𝒙_{}=(x_n,\mathrm{},x_2,x_1)`$ denotes the vector obtained by reversing the order. In the following, we denote by

$$J_n=\left(\begin{array}{c}\delta _{i+j,n+1}\end{array}\right)_{i,j=1}^n$$
(2.67)
the permutation matrix representing the longest element of $`𝑺_n`$. Since $`J_n\mathrm{\Lambda }J_n=\mathrm{\Lambda }^\text{t}`$, from

$$H(𝒙)=(\text{diag}(\overline{𝒙})\mathrm{\Lambda })^1,𝒙=(x_1,x_2,\mathrm{},x_n)$$
(2.68)
we have

$$J_nH(𝒙)^\text{t}J_n=(\text{diag}(\overline{𝒙}_{})\mathrm{\Lambda })^1,𝒙_{}=(x_n,\mathrm{},x_2,x_1),$$
(2.69)
namely, $`J_nH(𝒙)^\text{t}J_n=H(𝒙_{})`$. Hence, $`(\text{2.4})`$ implies $`J_nH_P^\text{t}J_n=H_{P^{\text{ s}}}`$, namely,

$$J_nH_1(𝒑^1)^\text{t}H_2(𝒑^2)^\text{t}\mathrm{}H_n(𝒑^n)^\text{t}J_n=H_n(\stackrel{~}{𝒑}^n)\mathrm{}H_2(\stackrel{~}{𝒑}^2)H_1(\stackrel{~}{𝒑}^1).$$
(2.70)
Supposing that $`mn`$, we take two general tropical tableaux

$$H_U=H_m(𝒖^m)\mathrm{}H_1(𝒖^1),H_V=H_m(𝒗^m)\mathrm{}H_1(𝒗^1),$$
(2.71)
where $`𝒖^i=(u_i^i,\mathrm{},u_n^i)`$ and $`𝒗^i=(v_i^i,\mathrm{},v_n^i)`$ for $`i=1,\mathrm{},m`$. In view of $`(\text{2.70})`$, we define the tropical Schützenberger involution to be the birational transformation $`UV`$ defined through the matrix equation $`J_nH_U^\text{t}J_n=H_V`$ :

$$J_nH_1(𝒖^1)^\text{t}\mathrm{}H_m(𝒖^m)^\text{t}J_n=H_m(𝒗^m)\mathrm{}H_1(𝒗^1).$$
(2.72)
We now propose to solve this matrix equation for $`v_j^i`$ ($`ij`$), regarding $`u_j^i`$ ($`ij`$) as indeterminates. Note that

$$J_n\mathrm{\Lambda }_k^\text{t}J_n=\mathrm{\Lambda }_{nk+1},\mathrm{\Lambda }_k=\underset{i=1}{\overset{k1}{}}E_{i,i+1},$$
(2.73)
for $`k=1,\mathrm{},n`$. Hence, $`(\text{2.72})`$ can be written as

$$\begin{array}{c}(\text{diag}(\overline{𝒖}_{}^1)\mathrm{\Lambda }_n)^1(\text{diag}(\overline{𝒖}_{}^2)\mathrm{\Lambda }_{n1})^1\mathrm{}(\text{diag}(\overline{𝒖}_{}^m)\mathrm{\Lambda }_{nm+1})^1\hfill \\ =(\text{diag}(\overline{𝒗}^m)\mathrm{\Lambda }_m)^1\mathrm{}(\text{diag}(\overline{𝒗}^2)\mathrm{\Lambda }_2)^1(\text{diag}(\overline{𝒗}^1)\mathrm{\Lambda }_1)^1.\hfill \end{array}$$
(2.74)
This equality is expressed graphically as follows. For each $`1ijn`$,

(2.75)
or equivalently,

(2.76)
where $`i^{}=ni+1`$ and $`j^{}=nj+1`$. Hence we have

###### Theorem 2.8

For the indeterminates $`u_j^i`$ $`(1ijn)`$ given, consider the matrix equation

$$J_nH_1(𝒖^1)^\text{t}H_2(𝒖^2)^\text{t}\mathrm{}H_m(𝒖^m)^\text{t}J_n=H_m(𝒗^m)\mathrm{}H_2(𝒗^2)H_1(𝒗^1)$$
(2.77)
for $`v_j^i`$ $`(1ijn)`$, where $`mn`$, and $`𝐮^i=(u_i^i,\mathrm{},u_n^i)`$, $`𝐯^i=(v_i^i,\mathrm{},v_n^i)`$ for $`i=1,\mathrm{},m`$. This equation has a unique rational solution ; it is given by

$$v_i^i=\frac{\sigma _i^i}{\sigma _i^{i1}},v_j^i=\frac{\sigma _j^i\sigma _{j1}^{i1}}{\sigma _j^{i1}\sigma _{j1}^i}(i<j),$$
(2.78)
with $`\sigma _j^i`$ $`(ij)`$ defined as the sum

$$\sigma _j^i=\underset{(\gamma _1,\mathrm{},\gamma _i)}{}u_{\gamma _1}\mathrm{}u_{\gamma _i}$$
(2.79)
of weights over all $`i`$-tuples of nonintersecting paths

$$\gamma _k:(1,ni+k)(\mathrm{min}\{m,nj+k\},nj+k)$$
(2.80)
$`(k=1,\mathrm{},i)`$, where the weight $`u_\gamma `$ of a path $`\gamma `$ is the product of all $`u_b^a`$’s corresponding to the vertices of $`\gamma `$.

Graphically, $`\sigma _j^i`$ ($`ij`$) in the explicit formula above is expressed as follows.

(2.81)
The explicit formula above for the tropical Schützenberger involution is proposed by A.N. Kirillov , Theorem 4.18.

By returning to the combinatorial variables, we obtain the following explicit formula for the Schützenberger involution (with $`m=n`$), due to H. Knight and A. Zelevinsky  (see also , ).

###### Theorem 2.9

Let $`P`$ be a column strict tableau and denote by $`p_j^i`$ the number of $`j`$’s in the $`i`$-th row of $`P`$ for $`1ijn`$. Let $`P^{\text{ s}}`$ be the column strict tableau obtained from $`P`$ by applying the Schützenberger involution, and denote by $`\stackrel{~}{p}_j^i`$ the number of $`j`$’s in the $`i`$-th row of $`P^{\text{ s}}`$ for $`1ijn`$. Then $`\stackrel{~}{p}_j^i`$ are determined from $`p_j^i`$ by the following explicit formula $`:`$

$$\stackrel{~}{p}_i^i=\sigma _i^i\sigma _i^{i1},\stackrel{~}{p}_j^i=\sigma _j^i\sigma _j^{i1}\sigma _{j1}^i+\sigma _{j1}^{i1}(i<j),$$
(2.82)
with $`\sigma _j^i`$ $`(1ijn)`$ defined as the maximum

$$\sigma _j^i=\underset{(\gamma _1,\mathrm{},\gamma _i)}{\mathrm{max}}(p_{\gamma _1}+\mathrm{}+p_{\gamma _i})$$
(2.83)
of weights over all $`i`$-tuples of nonintersecting paths $`\gamma _k:(1,ni+k)(nj+k,nj+k)`$ $`(k=1,\mathrm{},i)`$, where the weight $`p_\gamma `$ of a path $`\gamma `$ is the sum of all $`p_b^a`$’s corresponding to the vertices of $`\gamma `$.

###### Example 2.10

In the case of $`P`$ and $`P^{\text{ s}}`$ of Example 2.7, $`𝒑=\left(\begin{array}{c}p_j^i\end{array}\right)_{ij}`$ and $`\stackrel{~}{𝒑}=\left(\begin{array}{c}\stackrel{~}{p}_j^i\end{array}\right)_{ij}`$ are given by

$$𝒑=\left[\begin{array}{cccc}2& 1& 1& 0\\ & 2& 1& 0\\ & & 0& 1\\ & & & 0\end{array}\right],\stackrel{~}{𝒑}=\left[\begin{array}{cccc}1& 1& 2& 0\\ & 1& 0& 2\\ & & 1& 0\\ & & & 0\end{array}\right].$$
(2.84)
The table $`\stackrel{~}{𝒑}`$ can be determined through $`𝝈=\left(\begin{array}{c}\sigma _j^i\end{array}\right)_{ij}`$:

$$𝝈=\left[\begin{array}{cccc}1& 2& 4& 4\\ & 3& 5& 7\\ & & 6& 8\\ & & & 8\end{array}\right].$$
(2.85)
###### Remark 2.11

With the notation of Remark 1.8, the tropical Schützenberger involution can be formulated as follows. We define the involution $`\theta :`$ by setting

$$\theta (H)=J_nH^\text{t}J_n(H).$$
(2.86)
Then the isomorphism $`h:_0\stackrel{}{}_\tau `$ induces a birational involution $`UU^{\text{ s}}`$ on $`_0`$ such that

$$h(U^{\text{ s}})=\theta (h(U))=J_nh(U)^\text{t}J_n$$
(2.87)
for generic $`U_0`$. We already gave the explicit formula for $`V=U^{\text{ s}}`$ in Theorem 2.8. Note also that the inverse correspondence $`VU`$ is given by the same formula.

## 3 Tropical RSK correspondence

### 3.1 Variations of RSK correspondence

Let $`A=\left(\begin{array}{c}a_j^i\end{array}\right)_{i,j}\text{Mat}_{m,n}()`$ be an $`m\times n`$ matrix of nonnegative integers.

$$A=\left[\begin{array}{cccc}a_1^1& a_2^1& \mathrm{}& a_n^1\\ a_1^2& a_2^2& \mathrm{}& a_n^2\\ \mathrm{}& \mathrm{}& & \mathrm{}\\ a_1^m& a_2^m& \mathrm{}& a_n^m\end{array}\right]$$
(3.1)
Setting $`w_i=1^{a_1^i}\mathrm{}n^{a_n^i}`$ for $`i=1,\mathrm{},m`$, we denote by $`P=P(w)`$ the column strict tableau obtained from the word $`w=w_1\mathrm{}w_m`$ by row insertion. Similarly, setting $`w_j^{}=1^{a_j^1}\mathrm{}m^{a_j^m}`$ for $`j=1,\mathrm{},n`$, we denote by $`Q=P(w^{})`$ the column strict tableau obtained from the word $`w^{}=w_1^{}\mathrm{}w_n^{}`$ by row insertion. The two tableaux $`P`$ and $`Q`$ have the same shape, and the correspondence $`A(P,Q)`$ induces a bijection between the set of all $`m\times n`$ matrices of nonnegative integers and the set of pairs $`(P,Q)`$ of column strict tableaux of a same shape, $`P`$ with contents in $`\{1,\mathrm{},n\}`$ and $`Q`$ with contents in $`\{1,\mathrm{},m\}`$. This bijection $`A(P,Q)`$ is called the Robinson-Schensted-Knuth correspondence (RSK correspondence, for short). In this context, the matrix $`A`$ is sometimes called the transportation matrix. By combining this standard RSK correspondence with the Schützenberger involution, we have the following four variations of RSK correspondences:

$$\begin{array}{cc}A(P,Q),\hfill & A(P,Q^{\text{ s}}),\hfill \\ A(P^{\text{ s}},Q),\hfill & A(P^{\text{ s}},Q^{\text{ s}}).\hfill \end{array}$$
(3.2)
Let us denote by $`p_j^i`$, $`q_j^i`$, $`\stackrel{~}{p}_j^i`$ and $`\stackrel{~}{q}_j^i`$ the number of $`j`$’s in the $`i`$-th row of the tableaux $`P`$, $`Q`$, $`P^{\text{ s}}`$ and $`Q^{\text{ s}}`$, respectively. The common shape $`\lambda =(\lambda _1,\lambda _2,\mathrm{},\lambda _l)`$, $`l=\mathrm{min}\{m,n\}`$, of these four tableaux is given by

$$\lambda _i=p_i^i+\mathrm{}+p_n^i=q_i^i+\mathrm{}+q_m^i=\stackrel{~}{p}_i^i+\mathrm{}+\stackrel{~}{p}_n^i=\stackrel{~}{q}_i^i+\mathrm{}+\stackrel{~}{q}_m^i$$
(3.3)
for $`i=1,\mathrm{},l`$.

###### Example 3.1

Consider the transportation matrix

$$A=\left[\begin{array}{cccc}0& 2& 1& 1\\ 1& 0& 1& 2\\ 2& 2& 0& 1\end{array}\right].$$
(3.4)
The tableaux $`P`$, $`Q`$ for $`A`$, and their counterparts under the Schützenberger involution are determined as follows:

$`P=P(2234|1344|11224)=\begin{array}{cccccccccc}1\hfill & 1\hfill & 1\hfill & 2\hfill & 2\hfill & 4\hfill & 4\hfill & & & \\ 2\hfill & 2\hfill & 3\hfill & 3\hfill & 4\hfill & & & & & \\ 4\hfill & & & & & & & & & \end{array},𝒑=\left[\begin{array}{cccc}3& 2& 0& 2\\ & 2& 2& 1\\ & & 0& 1\end{array}\right]`$ (3.8)
$`Q=P(233|1133|12|1223)=\begin{array}{cccccccccc}1\hfill & 1\hfill & 1\hfill & 1\hfill & 2\hfill & 2\hfill & 3\hfill & & & \\ 2\hfill & 2\hfill & 3\hfill & 3\hfill & 3\hfill & & & & & \\ 3\hfill & & & & & & & & & \end{array},𝒒=\left[\begin{array}{ccc}4& 2& 1\\ & 2& 3\\ & & 1\end{array}\right]`$ (3.12)
$`P^{\text{ s}}=P(13344|1124|1233)=\begin{array}{cccccccccc}1\hfill & 1\hfill & 1\hfill & 1\hfill & 2\hfill & 3\hfill & 3\hfill & & & \\ 2\hfill & 3\hfill & 4\hfill & 4\hfill & 4\hfill & & & & & \\ 3\hfill & & & & & & & & & \end{array},\stackrel{~}{𝒑}=\left[\begin{array}{cccc}4& 1& 2& 0\\ & 1& 1& 3\\ & & 1& 0\end{array}\right]`$ (3.16)
$`Q^{\text{ s}}=P(1223|23|1133|112)=\begin{array}{cccccccccc}1\hfill & 1\hfill & 1\hfill & 1\hfill & 1\hfill & 2\hfill & 3\hfill & & & \\ 2\hfill & 2\hfill & 2\hfill & 3\hfill & 3\hfill & & & & & \\ 3\hfill & & & & & & & & & \end{array},\stackrel{~}{𝒒}=\left[\begin{array}{ccc}5& 1& 1\\ & 3& 2\\ & & 1\end{array}\right]`$ (3.20)
In the arguments of this section, the correspondence $`A(P,Q^{\text{ s}})`$ will play the essential role, rather than the ordinary RSK correspondence. For this reason, we use the following convention. Let $`X=\left(\begin{array}{c}x_j^i\end{array}\right)_{i,j}`$ be an $`m\times n`$ matrix of nonnegative integers. We denote the $`i`$-th row of $`X`$ by $`𝒙^i`$, and the $`j`$-th column of $`X`$ by $`𝒙_j`$ :

$$X=\left[\begin{array}{cccc}x_1^1& x_2^1& \mathrm{}& x_n^1\\ x_1^2& x_2^2& \mathrm{}& x_n^2\\ \mathrm{}& \mathrm{}& & \mathrm{}\\ x_1^m& x_2^m& \mathrm{}& x_n^m\end{array}\right]=\left[\begin{array}{c}𝒙^1\\ 𝒙^2\\ \mathrm{}\\ 𝒙^m\end{array}\right]=\left[𝒙_1𝒙_2\mathrm{}𝒙_n\right].$$
(3.21)
From $`X`$, we construct the column strict tableau

$$U=P(w_mw_{m1}\mathrm{}w_1),w_i=1^{x_1^i}2^{x_2^i}\mathrm{}n^{x_n^i}$$
(3.22)
by reading the rows $`𝒙^m,\mathrm{},𝒙^1`$ of $`X`$ from bottom to top, and

$$V=P(w_n^{}w_{n1}^{}\mathrm{}w_1^{}),w_j^{}=1^{x_j^1}2^{x_j^2}\mathrm{}m^{x_j^m},$$
(3.23)
by reading the columns $`𝒙_n,\mathrm{},𝒙_1`$ from right to left. If we set $`X=J_mA`$, these $`U`$ and $`V`$ correspond to $`P`$ and $`Q^{\text{ s}}`$, determined from $`A`$, so that

$$U=P,V=Q^{\text{ s}},U^{\text{ s}}=P^{\text{ s}},V^{\text{ s}}=Q.$$
(3.24)
In what follows, we refer to this particular correspondence $`X(U,V)`$ as the RSK correspondence.

Before the discussion of tropical RSK correspondences, we formulate an isomorphism theorem concerning the path representation of generic matrices.

### 3.2 A fundamental isomorphism

We first fix a notation of special minor determinants. For an $`m\times n`$ matrix $`\mathrm{\Phi }=\left(\begin{array}{c}\phi _j^i\end{array}\right)_{i,j}`$ given, we introduce the notation

$$\tau _j^i(\mathrm{\Phi })=\{\begin{array}{cc}det\mathrm{\Phi }_{1,\mathrm{},j}^{ij+1,\mathrm{},i}\hfill & (ij),\hfill \\ det\mathrm{\Phi }_{ji+1,\mathrm{},j}^{1,\mathrm{},i}\hfill & (ij),\hfill \end{array}$$
(3.25)
of the minor determinant of $`\mathrm{\Phi }`$ corresponding to the largest square in the rectangle $`\{1,\mathrm{},m\}\times \{1,\mathrm{},n\}`$ whose right-bottom corner is located at $`(i,j)`$.

(3.26)
For convenience, we define $`\tau _k^0(\mathrm{\Phi })=\tau _0^k(\mathrm{\Phi })=0`$ for any $`k`$. We define the subset $`\text{Mat}_{m,n}(𝕂)_\tau `$ of $`\text{Mat}_{m,n}(𝕂)`$ by

$$\text{Mat}_{m,n}(𝕂)_\tau =\{\mathrm{\Phi }\text{Mat}_{m,n}(𝕂)\tau _j^i(\mathrm{\Phi })0\text{for all}(i,j)\}.$$
(3.27)
For an $`m\times n`$ matrix $`X=\left(\begin{array}{c}x_j^i\end{array}\right)_{i,j}`$ given, we now construct an $`m\times n`$ matrix $`\mathrm{\Phi }=\left(\begin{array}{c}\phi _j^i\end{array}\right)_{i,j}`$ by using the paths on the lattice $`\{1,\mathrm{}m\}\times \{1,\mathrm{},n\}`$. When we refer to a path in the rectangular lattice, we mean a shortest path joining two vertices, without specifying the orientation of edges. As before, for each path $`\gamma :(a,b)(c,d)`$, we define the weight $`x_\gamma `$ of $`\gamma `$, associated with $`X`$, to be the product of all $`x_j^i`$’s corresponding the vertices on $`\gamma `$.

(3.28)
With this definition of weight, we define the matrix $`\mathrm{\Phi }=\left(\begin{array}{c}\phi _j^i\end{array}\right)_{i,j}`$ by setting

(3.29)
for each $`(i,j)\{1,\mathrm{},m\}\times \{1,\mathrm{},n\}`$, where the summation is taken over all paths from $`(i,1)`$ to $`(1,j)`$. The mapping $`X\mathrm{\Phi }`$ thus obtained will be denoted by

$$\phi :\text{Mat}_{m,n}(𝕂)\text{Mat}_{m,n}(𝕂),\phi (X)=\left(\begin{array}{c}\phi _j^i(X)\end{array}\right)_{i,j}.$$
(3.30)
This mapping $`\phi `$ provides us with a device for generating nonintersecting paths on the lattice $`\{1,\mathrm{},m\}\times \{1,\mathrm{},n\}`$. In fact, from the theorem of Gessel-Viennot , it follows that, for any choice of column indices $`i_1<\mathrm{}<i_r`$ and row indices $`j_1<\mathrm{}<j_r`$, the corresponding minor determinant of $`\mathrm{\Phi }`$ is expressed as a sum

$$det\mathrm{\Phi }_{j_1,\mathrm{},j_r}^{i_1,\mathrm{},i_r}=\underset{(\gamma _1,\mathrm{},\gamma _r)}{}x_{\gamma _1}\mathrm{}x_{\gamma _r}$$
(3.31)
of the product of weights over all $`r`$-tuples $`(\gamma _1,\mathrm{},\gamma _r)`$ of nonintersecting paths $`\gamma _k:(i_k,1)(1,j_k)`$ ($`k=1,\mathrm{},r`$). Graphically, this summation can be expressed as follows.

(3.32)
Let us look at the special minor determinants $`\tau _j^i(\mathrm{\Phi })`$ introduced above. Notice that, for each $`(i,j)`$, there is only one $`r`$-tuple ($`r=\mathrm{min}\{i,j\}`$) of nonintersecting paths relevant to the summation, so that the minor determinant $`\tau _j^i(\mathrm{\Phi })`$ reduces to the product

$$\tau _j^i(\mathrm{\Phi })=\underset{(a,b);ai,bj}{}x_b^a.$$
(3.33)
This implies that, if $`x_j^i0`$ for all $`i,j`$, then one has $`\tau _j^i(\mathrm{\Phi })0`$ for all $`i,j`$. From formula $`(\text{3.33})`$, it is also clear that the entries $`x_j^i`$ of the matrix $`X`$ are recovered as the ratios of minor determinants of $`\mathrm{\Phi }`$

$$x_j^i=\frac{\tau _j^i\tau _{j1}^{i1}}{\tau _j^{i1}\tau _{j1}^i},\tau _j^i=\tau _j^i(\mathrm{\Phi }),$$
(3.34)
provided that $`x_j^i0`$ for all $`i,j`$. The correspondence $`X\mathrm{\Phi }`$ defined by $`(\text{3.29})`$ induces a mapping

$$\phi :\text{Mat}_{m,n}(𝕂^{})\text{Mat}_{m,n}(𝕂)_\tau .$$
(3.35)
As we have seen above, if $`\mathrm{\Phi }=\phi (X)`$, then the matrix $`X`$ is recovered by the formula $`(\text{3.34})`$.

###### Theorem 3.2

The correspondence $`X\mathrm{\Phi }`$ defined by $`(\text{3.29})`$ induces an isomorphism of affine varieties

$$\phi :\text{Mat}_{m,n}(𝕂^{})\stackrel{}{}\text{Mat}_{m,n}(𝕂)_\tau .$$
(3.36)
Proof: Since $`\phi `$ has a left inverse defined by $`(\text{3.34})`$, we have only to show that $`\phi `$ is surjective. For each $`\mathrm{\Phi }\text{Mat}_{m,n}(𝕂)_\tau `$, we construct an $`X\text{Mat}_{m,n}(𝕂^{})`$ such that $`\phi (X)=\mathrm{\Phi }`$, by the induction on $`m`$. For this purpose, we first investigate the inductive structure of the mapping $`\phi `$. Assuming that $`\phi (X)=\mathrm{\Phi }`$, set

$$\psi _j^i=\underset{\gamma :(i,1)(2,j)}{}x_\gamma (2im,1jn).$$
(3.37)
Then $`\phi _j^i`$ are determined as

$$\phi _j^1=x_1^1x_2^1\mathrm{}x_j^1,\phi _j^i=\underset{k=1}{\overset{j}{}}\psi _k^ix_k^1x_{k+1}^1\mathrm{}x_j^1(i=2,\mathrm{},m),$$
(3.38)
for all $`j`$. In view of this, we consider the $`n\times n`$ upper triangular matrix $`H(𝒙^1)`$, $`𝒙^1=\left(\begin{array}{c}x_1^1,\mathrm{},x_n^1\end{array}\right)`$, associated with the first row of $`X`$. Then the condition $`(\text{3.38})`$ is equivalent to the matrix equation

$$\mathrm{\Phi }=\mathrm{\Psi }H(𝒙^1),\mathrm{\Psi }=\left[\begin{array}{cccc}1& 0& \mathrm{}& 0\\ \psi _1^2& \psi _2^2& \mathrm{}& \psi _n^2\\ \mathrm{}& \mathrm{}& & \mathrm{}\\ \psi _1^m& \psi _2^m& \mathrm{}& \psi _n^m\end{array}\right].$$
(3.39)
Let us show that any $`\mathrm{\Phi }\text{Mat}_{m,n}(𝕂)_\tau `$ can be decomposed in this form by choosing $`x_j^1`$ and $`\psi _j^i`$ appropriately. The condition to be satisfied by the first row $`(x_1^1,\mathrm{},x_n^1)`$ of $`X`$ is:

$$\left(\begin{array}{c}\mathrm{\Phi }H(𝒙^1)^1\end{array}\right)_j^1=\delta _{1,j}(j=1,\mathrm{},n).$$
(3.40)
Since $`H(𝒙^1)^1=\text{diag}(\overline{𝒙}^1)\mathrm{\Lambda }`$, it is easily seen that $`(\text{3.40})`$ is equivalent to

$$x_1^1=\phi _1^1,x_j^1=\frac{\phi _j^1}{\phi _{j1}^1}(j=2,\mathrm{},n).$$
(3.41)
Since $`\phi _j^1=\tau _j^1(\mathrm{\Phi })0`$, we can define $`x_j^1`$ ($`j=1,\mathrm{},n`$) as above. Then the matrix $`\mathrm{\Psi }=\mathrm{\Phi }H(𝒙^1)^1`$ has the first row $`(1,0,\mathrm{},0)`$; hence, $`H(𝒙^1)`$ and $`\mathrm{\Psi }`$ satisfy the condition $`(\text{3.39})`$. Define $`\mathrm{\Phi }^{}`$ to be the $`(m1)\times n`$ matrix obtained from $`\mathrm{\Psi }`$ by removing the first row. We will verify that $`\mathrm{\Phi }^{}\text{Mat}_{m1,n}(𝕂)_\tau `$ so that $`\mathrm{\Phi }^{}`$ can be expressed as $`\mathrm{\Phi }^{}=\phi (X^{})`$ by the induction hypothesis. Then, setting

$$X=\left[\begin{array}{ccc}x_1^1& \mathrm{}& x_n^1\\ \\ & X^{}& \end{array}\right],X^{}=\left[\begin{array}{ccc}x_1^2& \mathrm{}& x_n^2\\ \mathrm{}& & \mathrm{}\\ x_1^m& \mathrm{}& x_n^m\end{array}\right],$$
(3.42)
we must have $`\phi (X)=\mathrm{\Phi }`$, which will complete the proof of Theorem 3.2. We now examine the minor determinants of $`\mathrm{\Phi }=\mathrm{\Psi }H(𝒙^1)`$. Let $`(i,j)\{1,\mathrm{},m\}\times \{1,\mathrm{},n\}`$ and assume $`i>j`$. Then it is clear

$$\tau _j^i(\mathrm{\Phi })=det\mathrm{\Phi }_{1,\mathrm{},j}^{ij+1,\mathrm{},i}=det\mathrm{\Psi }_{1,\mathrm{},j}^{ij+1,\mathrm{},i}x_1^1\mathrm{}x_j^1,$$
(3.43)
since $`H`$ is upper triangular. Hence we have

$$\tau _j^{i1}(\mathrm{\Phi }^{})=det\mathrm{\Psi }_{1,\mathrm{},j}^{ij+1,\mathrm{},i}=\frac{1}{x_1^1\mathrm{},x_j^1}\tau _j^i(\mathrm{\Phi })0(i>j).$$
(3.44)
Next assume $`ij`$. In this case, we have

$$\tau _j^i(\mathrm{\Phi })=det\mathrm{\Phi }_{ji+1,\mathrm{},j}^{1,\mathrm{},i}=\underset{k_1<\mathrm{}<k_i}{}det\mathrm{\Psi }_{k_1,\mathrm{},k_i}^{1,\mathrm{},i}detH(𝒙^1)_{ji+1,\mathrm{},j}^{k_1,\mathrm{},k_i}.$$
(3.45)
Since the first row of $`\mathrm{\Psi }`$ is $`\left(\begin{array}{c}1,0,\mathrm{},0\end{array}\right)`$, we have $`det\mathrm{\Psi }_{k_1,\mathrm{},k_i}^{1,\mathrm{},i}=0`$ unless $`k_1=1`$. When $`k_1=1`$, from Lemma 1.4 it follows that $`detH(𝒙^1)_{ji+1,\mathrm{},j}^{1,k_2,\mathrm{},k_i}=0`$ unless $`(k_2,\mathrm{},k_i)=(ji+2,\mathrm{},j)`$. Since $`detH(𝒙^1)_{ji+1,\mathrm{},j}^{1,ji+2,\mathrm{},j}=x_1^1x_2^1\mathrm{}x_j^1`$, we finally obtain

$$\tau _j^i(\mathrm{\Phi })=det\mathrm{\Psi }_{1,ji+2,\mathrm{},j}^{1,\mathrm{},i}x_1^1\mathrm{}x_j^1.$$
(3.46)
Hence we have

$$\tau _j^{i1}(\mathrm{\Phi }^{})=det\mathrm{\Psi }_{1,ji+2,\mathrm{},j}^{1,\mathrm{},i}=\frac{1}{x_1^1\mathrm{}x_j^1}\tau _j^i(\mathrm{\Phi })0(ij).$$
(3.47)
This argument implies $`\tau _j^i(\mathrm{\Phi }^{})0`$ for all $`(i,j)`$ with $`1im1`$ and $`1jn`$ as desired. This completes the proof of Theorem 3.2. Q.E.D.

It is convenient for our purpose to restate Theorem 3.2 as follows.

###### Theorem 3.3

Let $`\mathrm{\Phi }=\left(\begin{array}{c}\phi _j^i\end{array}\right)_{i,j}`$ be an $`m\times n`$ matrix with coefficients in $`𝕂`$ such that $`\tau _j^i(\mathrm{\Phi })0`$ for all $`(i,j)`$. For such a matrix $`\mathrm{\Phi }`$ given, define the $`m\times n`$ matrix $`X=\left(\begin{array}{c}x_j^i\end{array}\right)_{i,j}`$ by setting

$$x_j^i=\frac{\tau _j^i\tau _{j1}^{i1}}{\tau _j^{i1}\tau _{j1}^i},\tau _j^i=\tau _j^i(\mathrm{\Phi }).$$
(3.48)
Then, for any choice of column indices $`i_1<\mathrm{}<i_r`$ and row indices $`j_1<\mathrm{}<j_r`$, the corresponding minor determinant of $`\mathrm{\Phi }`$ is expressed as a sum

$$det\mathrm{\Phi }_{j_1,\mathrm{},j_r}^{i_1,\mathrm{},i_r}=\underset{(\gamma _1,\mathrm{},\gamma _r)}{}x_{\gamma _1}\mathrm{}x_{\gamma _r}$$
(3.49)
of the product of weights over all $`r`$-tuples $`(\gamma _1,\mathrm{},\gamma _r)`$ of nonintersecting paths $`\gamma _k:(i_k,1)(1,j_k)`$ $`(k=1,\mathrm{},r)`$ in the $`m\times n`$ rectangle.

###### Remark 3.4

An $`m\times n`$ real matrix $`\mathrm{\Phi }`$ ($`𝕂=`$) is said to be totally positive if $`det\mathrm{\Phi }_{j_1,\mathrm{},j_r}^{i_1,\mathrm{},i_r}>0`$ for any choice of row indices $`i_1<\mathrm{}<i_r`$ and column indices $`j_1<\mathrm{}<j_r`$. Theorem 3.2 implies that, if $`\tau _j^i(\mathrm{\Phi })>0`$ for all $`(i,j)`$, then $`\mathrm{\Phi }`$ is already totally positive. In fact, if this condition is satisfied, all the $`x_j^i`$’s are positive; hence, any minor determinant $`det\mathrm{\Phi }_{j_1,\mathrm{},j_r}^{i_1,\mathrm{},i_r}`$ is positive since it is expressed as a sum of weights associated with $`X`$ over $`r`$-tuples of nonintersecting paths as in $`(\text{3.49})`$. Let us denote by $`\text{Mat}_{m,n}()_{\text{tot.pos.}}`$ the open subset of $`\text{Mat}_{m,n}()`$ consisting of all totally positive matrices. Then Theorem 3.2 also implies that $`\phi `$ induces the isomorphism

$$\phi :\text{Mat}_{m,n}(_{>0})\stackrel{}{}\text{Mat}_{m,n}()_{\text{tot.pos}}.$$
(3.50)
In particular, $`\text{Mat}_{m,n}()_{\text{tot.pos}}`$ is isomorphic to $`_{>0}^{mn}`$ as a real analytic manifold. For the theory of totally positive matrices, we refer the reader to .

We apply the fundamental isomorphism of Theorem 3.2 to formulating a prototype of subtraction-free birational involution on the space $`\text{Mat}_{m,n}(𝕂^{})`$ of matrices.

For each $`\mathrm{\Phi }\text{Mat}_{m,n}(𝕂)`$, we define the matrix $`\mathrm{\Phi }^{}`$ by setting

$$\mathrm{\Phi }^{}=J_m\mathrm{\Phi }J_n,$$
(3.51)
where $`J_m=\left(\begin{array}{c}\delta _{i+j,m+1}\end{array}\right)_{i,j=1}^m`$ and $`J_n=\left(\begin{array}{c}\delta _{i+j,n+1}\end{array}\right)_{i,j=1}^n`$ are the permutation matrices representing to the longest element of $`𝑺_m`$ and $`𝑺_n`$, respectively. This correspondence $`\mathrm{\Phi }\mathrm{\Phi }^{}`$ defines an involution on the space $`\text{Mat}_{m,n}(𝕂)`$ of $`m\times n`$ matrices. Then, via the isomorphism

$$\phi :\text{Mat}_{m,n}(𝕂^{})\stackrel{}{}\text{Mat}_{m,n}(𝕂)_\tau ,$$
(3.52)
we obtain a birational involution $`X\iota (X)`$ on $`\text{Mat}_{m,n}(𝕂^{})`$ such that

$$\phi (\iota (X))=\phi (X)^{}=J_m\phi (X)J_n$$
(3.53)
for generic $`X\text{Mat}_{m,n}(𝕂^{})`$.

To be more explicit, let us consider two matrices $`X,Y\text{Mat}_{m,n}(𝕂^{})`$, and set $`\mathrm{\Phi }=\phi (X)`$ and $`\mathrm{\Psi }=\phi (Y)`$. If we impose the relation $`\mathrm{\Psi }=\mathrm{\Phi }^{}`$ between $`\mathrm{\Phi }`$ and $`\mathrm{\Psi }`$, it induces a birational correspondence between $`X`$ and $`Y=\iota (X)`$. As we will see below, this correspondence $`XY`$ provides the essential ingredient of the RSK correspondence. Recall that $`X=\left(\begin{array}{c}x_j^i\end{array}\right)_{i,j}`$ is recovered from $`\mathrm{\Phi }=\left(\begin{array}{c}\phi _j^i\end{array}\right)_{i,j}`$ by the formula

$$x_j^i=\frac{\tau _j^i\tau _{j1}^{i1}}{\tau _j^{i1}\tau _{j1}^i},\tau _j^i=\tau _j^i(\mathrm{\Phi }),$$
(3.54)
and $`Y=\left(\begin{array}{c}y_j^i\end{array}\right)_{i,j}`$ from $`\mathrm{\Psi }=\left(\begin{array}{c}\psi _j^i\end{array}\right)_{i,j}`$ by

$$y_j^i=\frac{\sigma _j^i\sigma _{j1}^{i1}}{\sigma _j^{i1}\sigma _{j1}^i},\sigma _j^i=\tau _j^i(\mathrm{\Psi }).$$
(3.55)
We now look at the determinant $`\sigma _j^i`$. Since $`\mathrm{\Psi }=\mathrm{\Phi }^{}`$, we have

$$\sigma _j^i=\tau _j^i(\mathrm{\Psi })=det\mathrm{\Psi }_{jr+1,\mathrm{},j}^{ir+1,\mathrm{},i}=det\mathrm{\Phi }_{nj+1,\mathrm{},nj+r}^{mi+1,\mathrm{},mi+r},$$
(3.56)
where $`r=\mathrm{min}\{i,j\}`$. Hence, each $`\sigma _j^i`$ is expressed as the sum

$$\sigma _j^i=\underset{(\gamma _1,\mathrm{},\gamma _r)}{}x_{\gamma _1}\mathrm{}x_{\gamma _r}$$
(3.57)
of weights associated with $`X`$, over all $`r`$-tuples of nonintersecting paths

$$\gamma _k:(mi+k,1)(1,nj+k)(l=1,\mathrm{},r).$$
(3.58)
Graphically, $`\sigma _j^i`$ can be expressed as follows.

(3.59)
From symmetry of the construction, $`x_j^i`$ are recovered from $`y_j^i`$ by the same procedure.

###### Theorem 3.5

Let $`X=\left(\begin{array}{c}x_j^i\end{array}\right)_{i,j}`$, $`Y=\left(\begin{array}{c}y_j^i\end{array}\right)_{i,j}`$ be two $`m\times n`$ matrices such that $`x_j^i0`$, $`y_j^i0`$ for all $`i,j`$. Setting $`\mathrm{\Phi }=\phi (X)`$, $`\mathrm{\Psi }=\phi (Y)`$, suppose that $`\mathrm{\Phi }`$ and $`\mathrm{\Psi }`$ are related as $`\mathrm{\Psi }=\mathrm{\Phi }^{}`$ $`:`$

$$X\stackrel{\phi }{}\mathrm{\Phi }\stackrel{}{}\mathrm{\Psi }\stackrel{\phi }{}Y.$$
(3.60)
Then, for each $`(i,j)`$, $`y_j^i`$ is expressed as follows in terms of $`X`$ $`:`$

$$y_j^i=\frac{\sigma _j^i\sigma _{j1}^{i1}}{\sigma _j^{i1}\sigma _{j1}^i},\sigma _j^i=\underset{(\gamma _1,\mathrm{},\gamma _r)}{}x_{\gamma _1}\mathrm{}x_{\gamma _r},$$
(3.61)
where $`r=\mathrm{min}\{i,j\}`$, and the summation is taken over all $`r`$-tuples of nonintersecting paths $`\gamma _k:(mi+k,1)(1,nj+k)`$ $`(k=1,\mathrm{},r)`$. Conversely, each $`x_j^i`$ is expressed as follows in terms of $`Y`$ $`:`$

$$x_j^i=\frac{\tau _j^i\tau _{j1}^{i1}}{\tau _j^{i1}\tau _{j1}^i},\tau _j^i=\underset{(\gamma _1,\mathrm{},\gamma _r)}{}y_{\gamma _1}\mathrm{}y_{\gamma _r},$$
(3.62)
summed over the same set of $`r`$-tuples of nonintersecting paths as above.

Note that the transformation from $`X=\left(\begin{array}{c}x_j^i\end{array}\right)_{i,j}`$ to $`Y=\left(\begin{array}{c}y_j^i\end{array}\right)_{i,j}`$ in Theorem 3.5 is realized as a subtraction-free birational mapping from $`\text{Mat}_{m,n}(𝕂^{})`$ to itself; this birational mapping is in fact an involution on $`\text{Mat}_{m,n}(𝕂^{})`$. Passing to the piecewise linear functions, we obtain

###### Theorem 3.6

For each $`m\times n`$ matrix $`X=\left(\begin{array}{c}x_j^i\end{array}\right)_{i,j}\text{Mat}_{m,n}()`$, define an $`m\times n`$ matrix $`Y=\left(\begin{array}{c}y_j^i\end{array}\right)_{i,j}`$ by

$$y_j^i=\sigma _j^i\sigma _j^{i1}\sigma _{j1}^i+\sigma _{j1}^{i1},\sigma _j^i=\underset{(\gamma _1,\mathrm{},\gamma _r)}{\mathrm{max}}(x_{\gamma _1}+\mathrm{}+x_{\gamma _r}),$$
(3.63)
where $`r=\mathrm{min}\{i,j\}`$, and the maximum is taken over all $`r`$-tuples of nonintersecting paths $`\gamma _k:(mi+k,1)(1,nj+k)`$ $`(k=1,\mathrm{},r)`$; the weight of a path $`\gamma `$ is the sum of all $`x_b^a`$’s corresponding to the vertices of $`\gamma `$. Then the piecewise linear mapping $`XY`$ is an involution on $`\text{Mat}_{m,n}()`$.

### 3.3 Tropical RSK correspondence

Theorem 3.5 is an essential ingredient of the tropical RSK correspondences. Regarding $`x_j^i`$ as indeterminates, we now work within the field of rational functions $`𝕂(x)`$ in $`mn`$ variables $`x_j^i`$ ($`1im,1jn`$). In what follows, we assume that $`mn`$ to fix the idea.

Consider the $`m\times n`$ matrix $`X=\left(\begin{array}{c}x_j^i\end{array}\right)_{i,j}`$ regarding $`x_j^i`$ as indeterminates. We denote the $`i`$-th row of $`X`$ by $`𝒙^i`$, and the $`j`$-th column of $`X`$ by $`𝒙_j`$ :

$$X=\left[\begin{array}{cccc}x_1^1& x_2^1& \mathrm{}& x_n^1\\ x_1^2& x_2^2& \mathrm{}& x_n^2\\ \mathrm{}& \mathrm{}& & \mathrm{}\\ x_1^m& x_2^m& \mathrm{}& x_n^m\end{array}\right]=\left[\begin{array}{c}𝒙^1\\ 𝒙^2\\ \mathrm{}\\ 𝒙^m\end{array}\right]=\left[𝒙_1𝒙_2\mathrm{}𝒙_n\right].$$
(3.64)
From the matrix $`X=\left(\begin{array}{c}x_j^i\end{array}\right)_{i,j}`$, we construct four tropical tableaux

$$U=\left(\begin{array}{c}u_j^i\end{array}\right)_{ij},V=\left(\begin{array}{c}v_j^i\end{array}\right)_{ij},U^{\text{ s}}=\left(\begin{array}{c}\stackrel{~}{u}_j^i\end{array}\right)_{ij},V^{\text{ s}}=\left(\begin{array}{c}\stackrel{~}{v}_j^i\end{array}\right)_{ij}$$
(3.65)
as follows:

$`H(𝒙^m)\mathrm{}H(𝒙^2)H(𝒙^1)=H_m(𝒖^m)\mathrm{}H_2(𝒖^2)H_1(𝒖^1)=H_U,`$
$`H(𝒙_n)\mathrm{}H(𝒙_2)H(𝒙_1)=H_m(𝒗^m)\mathrm{}H_2(𝒗^2)H_1(𝒗^1)=H_V`$
$`H(𝒙_{}^1)H(𝒙_{}^2)\mathrm{}H(𝒙_{}^m)=H_m(\stackrel{~}{𝒖}^m)\mathrm{}H_2(\stackrel{~}{𝒖}^2)H_1(\stackrel{~}{𝒖}^1)=H_{U^{\text{ s}}},`$
$`H(𝒙_1^{})H(𝒙_2^{})\mathrm{}H(𝒙_n^{})=H_m(\stackrel{~}{𝒗}^m)\mathrm{}H_2(\stackrel{~}{𝒗}^2)H_1(\stackrel{~}{𝒗}^1)=H_{V^{\text{ s}}},`$ (3.66)
where $`𝒙_{}^i=(x_n^i,\mathrm{},x_2^i,x_1^i)`$ and $`𝒙_j^{}=(x_j^m,\mathrm{},x_j^2,x_j^1)`$; $`H_U`$, $`H_{U^{\text{ s}}}`$ are $`n\times n`$ matrices, and $`H_V`$, $`H_{V^{\text{ s}}}`$ are $`m\times m`$ matrices. Note that $`U`$ and $`U^{\text{ s}}`$ (resp. $`V`$ and $`V^{\text{ s}}`$) are transformed into each other by the tropical Schützenberger involution. We also introduce the tropical Gelfand-Tsetlin pattern $`𝝁`$ associated with the tropical tableau $`U`$ as

$$𝝁=\left[\begin{array}{c}\mu _1^{(n)}\mu _2^{(n)}\mathrm{}\mu _n^{(n)}\\ \mu _1^{(n1)}\mu _2^{(n1)}\mathrm{}\mu _{n1}^{(n1)}\\ \mathrm{}\\ \mu _1^{(1)}\end{array}\right],$$
(3.67)
where, for $`ij`$, we define $`\mu _i^{(j)}=u_i^i\mathrm{}u_j^i`$ ($`im`$) and $`\mu _i^{(j)}=1`$ ($`i>m`$).

Applying Theorem 2.4 to $`A=J_mX`$, we already know that the variables $`u_j^i`$ ($`ij`$) are determined by

$$u_i^i=\frac{\tau _i^i(H_U)}{\tau _i^{i1}(H_U)},u_j^i=\frac{\tau _j^i(H_U)\tau _{j1}^{i1}(H_U)}{\tau _j^{i1}(H_U)\tau _{j1}^i(H_U)}(i<j),$$
(3.68)
with

(3.69)
Notice that $`\tau _j^i(H_U)`$ for $`ij`$ coincides with

(3.70)
Hence we have

$$\tau _j^i(H_U)=det\mathrm{\Phi }_{ji+1,\mathrm{},j}^{mi+1,\mathrm{},m}=det\mathrm{\Psi }_{nj+1,\mathrm{},nj+i}^{1,\mathrm{},i}=\tau _{nj+i}^i(\mathrm{\Psi }).$$
(3.71)
This implies

$$\sigma _j^i=\tau _j^i(\mathrm{\Psi })=\tau _{nj+i}^i(H_U)=\underset{(a,b);ai,bnj+i}{}u_b^a(ij).$$
(3.72)
Similarly, for $`ij`$, we have

$$\tau _j^i(H_V)=det\mathrm{\Phi }_{ni+1,\mathrm{},i}^{ji+1,\mathrm{},j}=det\mathrm{\Psi }_{1,\mathrm{},i}^{mj+1,\mathrm{},mj+i}=\tau _i^{mj+i}(\mathrm{\Psi }),$$
(3.73)
hence, for $`ij`$,

$$\sigma _j^i=\tau _j^i(\mathrm{\Psi })=\tau _{mi+j}^j(H_V)=\underset{(a,b);aj,bmi+j}{}v_b^a(ij).$$
(3.74)
Summarizing the argument above, we have

$$\sigma _j^i=\tau _j^i(\mathrm{\Psi })=\{\begin{array}{cc}\underset{(a,b);ai,bnj+i}{}u_b^a\hfill & (ij),\hfill \\ \underset{(a,b);aj,bmi+j}{}v_b^a\hfill & (ij),\hfill \end{array}$$
(3.75)
for all $`(i,j)`$ with $`1im`$ and $`1jn`$. Conversely, $`u_j^i`$ and $`v_j^i`$ are determined as

$$u_i^i=\frac{\sigma _n^i}{\sigma _{n1}^{i1}},u_j^i=\frac{\sigma _{nj+i}^i\sigma _{nj+i}^{i1}}{\sigma _{nj+i1}^{i1}\sigma _{nj+i+1}^i}(i<j)$$
(3.76)
and

$$v_i^i=\frac{\sigma _i^m}{\sigma _{i1}^{m1}},v_j^i=\frac{\sigma _i^{mj+i}\sigma _{i1}^{mj+i}}{\sigma _{i1}^{mj+i1}\sigma _i^{mj+i1}}(i<j).$$
(3.77)
###### Remark 3.7

It should be noted that the upper (resp. lower) triangular components of the $`m\times n`$ matrix $`S=\left(\begin{array}{c}\sigma _j^i\end{array}\right)_{i,j}`$ are determined from $`U=\left(\begin{array}{c}u_j^i\end{array}\right)_{ij}`$ (resp. $`V=\left(\begin{array}{c}v_j^i\end{array}\right)_{ij}`$), and vice versa. Formula $`(\text{3.75})`$ is also equivalent to

$$\frac{\sigma _j^i}{\sigma _{j1}^{i1}}=\{\begin{array}{cc}u_i^i\mathrm{}u_{nj+i}^i=\mu _i^{(nj+i)}\hfill & (ij),\hfill \\ v_j^j\mathrm{}v_{mi+j}^j=\nu _j^{(mi+j)}\hfill & (ij),\hfill \end{array}$$
(3.78)
where $`\mu _i^{(j)}`$ and $`\nu _i^{(j)}`$ are the tropical variables representing the Gelfand-Tsetlin pattern of $`U`$ and $`V`$, respectively. Namely, the $`m\times n`$ matrix

(3.79)
defined by the ratios of $`\sigma _j^i`$, is obtained by glueing the two Gelfand-Tsetlin patterns $`𝝁`$ and $`𝝂`$ at the main diagonal, where the diagonal entries

$$\lambda _i=\mu _i^{(n)}=\nu _i^{(m)}(i=1,\mathrm{},m)$$
(3.80)
are the tropical variables representing the common shape of $`U`$ and $`V`$.

From $`(\text{3.75})`$, we obtain the following expression for $`y_j^i`$:

$$y_j^i=\frac{\sigma _j^i\sigma _{j1}^{i1}}{\sigma _j^{i1}\sigma _{j1}^i}=\{\begin{array}{cc}\frac{u_{nj+i}^1\mathrm{}u_{nj+i}^{i1}}{u_{nj+i+1}^1\mathrm{}u_{nj+i+1}^i}\hfill & (i<j),\hfill \\ \frac{\lambda _i}{u_n^1\mathrm{}u_n^{i1}v^1\mathrm{}v_m^{i1}}\hfill & (i=j),\hfill \\ \frac{v_{mi+j}^1\mathrm{}v_{mi+j}^{j1}}{v_{mi+j+1}^1\mathrm{}u_{mi+j+1}^j}\hfill & (i>j).\hfill \end{array}$$
(3.81)
Hence we have

###### Theorem 3.8

Under the assumption of Theorem 3.5, let $`U=\left(\begin{array}{c}u_j^i\end{array}\right)_{ij}`$, $`V=\left(\begin{array}{c}v_j^i\end{array}\right)_{ij}`$ be the tropical tableaux defined by the tropical row insertions

$$H_U=H(𝒙^m)\mathrm{}H(𝒙^2)H(𝒙^1),H_V=H(𝒙_n)\mathrm{}H(𝒙_2)H(𝒙_1),$$
(3.82)
respectively. Then $`u_j^i`$ and $`v_j^i`$ are expressed as $`(\text{3.76})`$ and $`(\text{3.77})`$, respectively, in terms of $`\sigma _j^i`$ defined in Theorem 3.5. Conversely, the matrix $`X=\left(\begin{array}{c}x_j^i\end{array}\right)_{i,j}`$ is recovered from the tropical tableaux $`U`$ and $`V`$ by the formula $`(\text{3.62})`$ with $`y_j^i`$ defined by $`(\text{3.81})`$.

Passing to the combinatorial variables, we obtain the explicit inversion formula for the RSK correspondence.

###### Theorem 3.9

Let $`X=\left(\begin{array}{c}x_j^i\end{array}\right)_{i,j}`$ be an $`m\times n`$ matrix of nonnegative integers. Consider the two column strict tableaux $`U`$ and $`V`$ obtained by the row insertion

$`U=(\mathrm{}(w_mw_{m1})\mathrm{}w_1),`$ $`w_i=1^{x_1^i}2^{x_2^i}\mathrm{}n^{x_n^i}`$ (3.83)
$`V=(\mathrm{}(w_n^{}w_{n1}^{})\mathrm{}w_1^{}),`$ $`w_j^{}=1^{x_j^1}2^{x_j^2}\mathrm{}m^{x_j^m}.`$
Denote by $`u_j^i`$ $`(\text{resp.}v_j^i)`$ be the number of $`j^{}`$s in the $`i`$-th row of $`U`$ $`(\text{resp.}V)`$. Then $`u_j^i`$ and $`v_j^i`$ are expressed as

$`u_i^i=\sigma _n^i\sigma _{n1}^{i1},`$
$`u_j^i=\sigma _{nj+i}^i\sigma _{nj+i1}^{i1}\sigma _{nj+i+1}^i+\sigma _{nj+i}^{i1}(i<j),`$ (3.84)
$`v_i^i=\sigma _i^m\sigma _{i1}^{m1},`$
$`v_j^i=\sigma _i^{mj+i}\sigma _{i1}^{mj+i1}\sigma _i^{mj+i1}+\sigma _{i1}^{mj+i}(i<j)`$ (3.85)
in terms of $`\sigma _j^i`$ defined in Theorem 3.6. Let $`\lambda =(\lambda _1,\mathrm{},\lambda _l)`$, $`l=\mathrm{min}\{m,n\}`$, be the common shape of $`U`$ and $`V`$, and set

$$y_j^i=\{\begin{array}{cccc}_{k=1}^{i1}u_{nj+i}^k_{k=1}^iu_{nj+i+1}^k\hfill & (i<j),\hfill & & \\ \lambda _i_{k=1}^{i1}u_n^k_{k=1}^{i1}v_m^k\hfill & (i=j),\hfill & & \\ _{k=1}^{j1}v_{mi+j}^k_{k=1}^jv_{mi+j+1}^k\hfill & (i>j),\hfill & & \end{array}$$
(3.86)
for each $`i=1,\mathrm{},m`$ and $`j=1,\mathrm{},n`$. Then the matrix $`X`$ is recovered from $`U`$ and $`V`$ by the formulas

$$x_j^i=\tau _j^i\tau _j^{i1}\tau _{j1}^i+\tau _{j1}^{i1},\tau _j^i=\underset{(\gamma _1,\mathrm{},\gamma _r)}{\mathrm{max}}(y_{\gamma _1}+\mathrm{}+y_{\gamma _r}),$$
(3.87)
where $`r=\mathrm{min}\{i,j\}`$, and the maximum is taken over all $`r`$-tuples of nonintersecting paths $`\gamma _k:(mi+k,1)(1,nj+k)`$ $`(k=1,\mathrm{},r)`$ in the $`m\times n`$ rectangle ; the weight of a path $`\gamma `$ is the sum of all $`y_b^a`$’s corresponding to the vertices of $`\gamma `$.

An explicit inversion formula for the usual RSK correspondence is obtained by combining Theorem 3.9 and the Schützenberger involution. The inversion formula discussed above has an obvious theoretical meaning, but is somewhat indirect. We will discuss in the following subsection a different type of inversion formulas for the four variations of RSK correspondences which recovers the transportation matrix directly from the corresponding tableaux.

### 3.4 Inverse tropical RSK via the Gauss decomposition

Keeping the notations $`X`$, $`\mathrm{\Phi }`$, $`\mathrm{\Psi }`$ as before, we now consider the “Gauss decomposition” of the $`m\times n`$ matrix $`\mathrm{\Psi }`$ ($`mn`$):

$$\mathrm{\Psi }=\mathrm{\Psi }_{}\mathrm{\Psi }_0\mathrm{\Psi }_+,$$
(3.88)
where $`\mathrm{\Psi }_+`$, $`\mathrm{\Psi }_0`$ and $`\mathrm{\Psi }_{}`$ are a $`m\times n`$ upper unitriangular matrix, a $`m\times m`$ diagonal matrix, and a $`m\times m`$ lower unitriangular matrix, respectively:

$$(\mathrm{\Psi }_+)_j^i=\delta _{i,j}(ij),(\mathrm{\Psi }_0)_j^i=0(ij),(\mathrm{\Psi }_{})_j^i=\delta _{i,j}(ij).$$
(3.89)
Nontrivial entries of these matrices are given explicitly as follows:

$$\begin{array}{cccccccccc}(\mathrm{\Psi }_+)_j^i\hfill & =\frac{det\mathrm{\Psi }_{1,\mathrm{},i1,j}^{1,\mathrm{},i}}{det\mathrm{\Psi }_{1,\mathrm{},i}^{1,\mathrm{},i}}\hfill & =\frac{det\mathrm{\Phi }_{nj+1,ni+2,\mathrm{},n}^{mi+1,\mathrm{},m}}{det\mathrm{\Phi }_{ni+1,\mathrm{},n}^{mi+1,\mathrm{},m}}\hfill & (ij),\hfill & & & & & & \\ (\mathrm{\Psi }_0)_i^i\hfill & =\frac{det\mathrm{\Psi }_{1,\mathrm{},i}^{1,\mathrm{},i}}{det\mathrm{\Psi }_{1,\mathrm{},i1}^{1,\mathrm{},i1}}\hfill & =\frac{det\mathrm{\Phi }_{ni+1,\mathrm{},n}^{mi+1,\mathrm{},m}}{det\mathrm{\Phi }_{ni+2,\mathrm{},n}^{mi+2,\mathrm{},m}}\hfill & (i=j),\hfill & & & & & & \\ (\mathrm{\Psi }_{})_j^i\hfill & =\frac{det\mathrm{\Psi }_{1,\mathrm{},j}^{1,\mathrm{},j1,i}}{det\mathrm{\Psi }_{1,\mathrm{},j}^{1,\mathrm{},j}}\hfill & =\frac{det\mathrm{\Phi }_{nj+1,\mathrm{},n}^{mi+1,mj+2,\mathrm{},m}}{det\mathrm{\Phi }_{nj+1,\mathrm{},n}^{mj+1,\mathrm{},m}}\hfill & (ij).\hfill & & & & & & \end{array}$$
(3.90)
Comparing the path representations of $`\mathrm{\Phi }`$ and $`H_U`$, $`H_{U^{\text{ s}}}`$, $`H_V`$, $`H_{V^{\text{ s}}}`$, we have

$$det\mathrm{\Phi }_{l_1,\mathrm{},l_r}^{mr+1,\mathrm{},m}=det(H_U)_{l_1,\mathrm{},l_r}^{1,\mathrm{},r}=det(H_{U^{\text{ s}}})_{nr+1,\mathrm{},n}^{l_1^{},\mathrm{},l_r^{}},$$
(3.91)
where $`1l_1<\mathrm{}<l_rn`$ and $`l_i^{}=nl_i+1`$, and

$$det\mathrm{\Phi }_{nr+1,\mathrm{},n}^{k_1,\mathrm{},k_r}=det(H_V)_{k_1,\mathrm{},k_r}^{1,\mathrm{},r}=det(H_{V^{\text{ s}}})_{mr+1,\mathrm{},m}^{k_1^{},\mathrm{},k_r^{}},$$
(3.92)
for $`1k_1<\mathrm{}<k_rm`$ with $`k_i^{}=mk_i+1`$. From these formulas, we see for instance,

$$(\mathrm{\Psi }_0)_i^i=u_i^i\mathrm{}u_n^i=\stackrel{~}{u}_i^i\mathrm{}\stackrel{~}{u}_n^i=v_i^i\mathrm{}v_m^i=\stackrel{~}{v}_i^i\mathrm{}\stackrel{~}{v}_m^i$$
(3.93)
for $`i=1,\mathrm{},m`$. We set $`\lambda _i=(\mathrm{\Psi }_0)_i^i`$, so that the vector $`\lambda =(\lambda _1,\mathrm{},\lambda _m)`$ represents the common shape of $`U`$, $`U^{\text{ s}}`$, $`V`$ and $`V^{\text{ s}}`$. By using formulas $`(\text{3.91})`$, $`(\text{3.92})`$, we can represent $`\mathrm{\Psi }_+`$, $`\mathrm{\Psi }_0`$, $`\mathrm{\Psi }_{}`$ in terms of the tropical tableaux.

###### Proposition 3.10

$`(0)`$ For $`i=1,\mathrm{},m`$,

$$(\mathrm{\Psi }_0)_i^i=\lambda _i=u_i^i\mathrm{}u_n^i=\stackrel{~}{u}_i^i\mathrm{}\stackrel{~}{u}_n^i=v_i^i\mathrm{}v_m^i=\stackrel{~}{v}_i^i\mathrm{}\stackrel{~}{v}_m^i.$$
(3.94)
$`(1)`$ For $`ij`$, $`(\mathrm{\Psi }_+)_j^i`$ is expressed in terms of $`U`$ as the sum

(3.95)
of weights over all path $`\gamma :(i,n)(1,nj+1)`$, with weight $`\overline{u}_b^a=\frac{1}{u_b^a}`$ assigned to the horizontal edge connecting $`(a,b1)`$ and $`(a,b)`$, for each $`ab`$. In terms of $`U^{\text{ s}}`$, $`(\mathrm{\Psi }_+)_j^i`$ is expressed as

(3.96)
$`(2)`$ For $`ij`$, $`(\mathrm{\Psi }_{})_j^i`$ is expressed in terms of $`V`$ as the sum

(3.97)
of weights over all path $`\gamma :(mi+1,1)(j,m)`$, with weight $`\overline{v}_b^a=\frac{1}{v_b^a}`$ assigned to the horizontal edge connecting $`(a,b1)`$ and $`(a,b)`$, for each $`ab`$. In terms of $`V^{\text{ s}}`$, $`(\mathrm{\Psi }_{})_j^i`$ is expressed as

(3.98)
This proposition implies that the matrix $`\mathrm{\Psi }=\mathrm{\Psi }_{}\mathrm{\Psi }_0\mathrm{\Psi }_+`$, as well as $`\mathrm{\Phi }=\mathrm{\Psi }^{}`$, is completely recovered from each of the four pairs of tropical tableaux

$$(U,V),(U,V^{\text{ s}}),(U^{\text{ s}},V),(U^{\text{ s}},V^{\text{ s}}).$$
(3.99)
By combining the graphical representations in Proposition 3.10, we can construct a path representation of $`\mathrm{\Psi }`$, associated with each pair in $`(\text{3.99})`$. According to

$$\mathrm{\Psi }_j^i=\underset{k=1}{\overset{m}{}}(\mathrm{\Psi }_{})_k^i(\mathrm{\Psi }_0)_k^k(\mathrm{\Psi }_+)_j^k,$$
(3.100)
we glue the diagrams of $`(\text{3.95})`$ or $`(\text{3.96})`$ for $`\mathrm{\Psi }_+`$ and $`(\text{3.97})`$ or $`(\text{3.98})`$ for $`\mathrm{\Psi }_{}`$. We show in Figure 1 the diagrams

$$\mathrm{\Gamma }=\mathrm{\Gamma }_{U,V},\mathrm{\Gamma }_{U,V^{\text{ s}}},\mathrm{\Gamma }_{U^{\text{ s}},V},\mathrm{\Gamma }_{U^{\text{ s}},V^{\text{ s}}}$$
(3.101)
obtained in this way. In diagram $`\mathrm{\Gamma }`$, the orientation of the edges are indicated by arrows. We assign the weights, associated with the pair of tropical tableaux, to the thick edges and the vertices marked by $``$. For each path $`\gamma `$ in $`\mathrm{\Gamma }`$, we define the weight $`\text{wt}(\gamma )`$ to be the product of weights attached to all the edges and the vertices. In Figure 1, $`a_1,\mathrm{},a_m`$ and $`b_1,\mathrm{},b_n`$ indicate the entrances and the exits for the path representation of $`\mathrm{\Psi }`$, respectively. Namely, for each $`(i,j)`$, $`\psi _j^i`$ is expressed as the sum

$$\psi _j^i=\underset{\gamma :a_ib_j}{}\text{wt}(\gamma )$$
(3.102)
of weights defined as above, over all paths $`\gamma :a_ib_j`$ in $`\mathrm{\Gamma }`$. Recall that the matrix $`X=\left(\begin{array}{c}x_j^i\end{array}\right)`$ is determined from $`\mathrm{\Phi }`$ through the minor determinants $`\tau _j^i=\tau _j^i(\mathrm{\Phi })`$ of $`\mathrm{\Phi }=\mathrm{\Psi }^{}`$. Hence each $`x_j^i`$ is determined as

$$x_j^i=\frac{\tau _j^i\tau _{j1}^{i1}}{\tau _j^{i1}\tau _{j1}^i},\tau _j^i=\underset{(\gamma _1,\mathrm{},\gamma _r)}{}\text{wt}(\gamma _1)\mathrm{}\text{wt}(\gamma _r),$$
(3.103)
where the summation is taken over all $`r`$-tuples ($`r=\mathrm{min}\{i,j\}`$) of nonintersecting paths

$$\gamma _k:a_{mi+k}b_{nj+k}(k=1,\mathrm{},r)$$
(3.104)
in $`\mathrm{\Gamma }`$. For each pair in $`(\text{3.99})`$, we have thus obtained an explicit inversion formula of the corresponding tropical RSK correspondence in terms of nonintersecting paths. The corresponding combinatorial formula for the inverse RSK correspondence is obtained simply by the standard procedure:

$$x_j^i=\tau _j^i\tau _j^{i1}\tau _{j1}^i+\tau _{j1}^{i1},\tau _j^i=\underset{(\gamma _1,\mathrm{},\gamma _r)}{\mathrm{max}}(\text{wt}(\gamma _1)+\mathrm{}+\text{wt}(\gamma _r)),$$
(3.105)
where the weight of a path is defined as the sum of weights attached to the edges and the vertices; read the weights $`\overline{u}_j^i`$ and $`\overline{v}_j^i`$ in $`\mathrm{\Gamma }`$ as $`u_j^i`$ and $`v_j^i`$ in the combinatorial setting.

In the case of the pair $`(U,V)`$, we can give a rectangular diagram as well, by deforming the diagram $`\mathrm{\Gamma }_{U,V}`$. Note first that the diagram $`\mathrm{\Gamma }_{U,V}`$ is equivalent to the following.

(3.106)
We deform this diagram to

(3.107)
and finally to the $`m\times n`$ rectangle:

(3.108)
By this rectangle, $`\psi _j^i`$ is expressed as the sum

$$\psi _j^i=\underset{\gamma :(i,1)\gamma (1,j)}{}\text{wt}(\gamma )$$
(3.109)
of weights defined as above, over all paths $`\gamma :(i,1)(1,j)`$. (This representation is similar to that by $`Y=\left(\begin{array}{c}y_j^i\end{array}\right)_{i,j}`$, although the weights are defined in a different way.) Hence we have

$$x_j^i=\frac{\tau _j^i\tau _{j1}^{i1}}{\tau _j^{i1}\tau _{j1}^i},\tau _j^i=\underset{(\gamma _1,\mathrm{},\gamma _r)}{}\text{wt}(\gamma _1)\mathrm{}\text{wt}(\gamma _r),$$
(3.110)
where $`r=\mathrm{min}\{i,j\}`$ and the summation is taken over all $`r`$-tuples of nonintersecting paths $`\gamma _k:(mi+k,1)(1,nj+k)`$ ($`k=1,\mathrm{},r`$) in the $`m\times n`$ rectangle. This inversion formula is essentially equivalent to the inverse RSK correspondence discussed in the previous subsection.

###### Remark 3.11

As we have seen above, the RSK correspondence can be thought of as the Gauss (or $`LR`$) decomposition of ultra-discretized matrices with respect to the product defined by

$$(XY)_j^i=\underset{k}{\mathrm{max}}(X_k^i+Y_j^k).$$
(3.111)
## 4 Birational Weyl group actions

In this section, we introduce a subtraction-free birational affine Weyl group action on the space of tropical transportation matrices. It induces an action of the symmetric group on the space of tropical tableaux through the tropical RSK correspondence. In this section, we work with the generic $`m\times n`$ matrix $`X=\left(\begin{array}{c}x_j^i\end{array}\right)_{i,j}`$, regarding $`x_j^i`$ as indeterminates.

### 4.1 Affine Weyl group action on the matrix space

In what follows, we consider the following two (extended) affine Weyl groups $`\stackrel{~}{W}^m`$ and $`\stackrel{~}{W}_n`$ of type $`A_{m1}^{(1)}`$ and $`A_{n1}^{(1)}`$, respectively. We denote by

$$\stackrel{~}{W}^m=r_0,r_1,\mathrm{},r_{m1},\omega $$
(4.1)
the group generated by the simple reflections $`r_0,r_1,\mathrm{},r_{m1}`$ and the diagram rotation $`\omega `$ subject to the fundamental relations

$$\begin{array}{cccc}r_i^2=1,\hfill & & & \\ r_ir_j=r_jr_i\hfill & (ji,i\pm 1\text{ mod }m),\hfill & & \\ r_ir_jr_i=r_jr_ir_j\hfill & (ji\pm 1\text{ mod }m),\hfill & & \\ \omega r_i=r_{i+1}\omega ,\hfill & & & \end{array}$$
(4.2)
where we understand the indices for $`r_i`$ as elements of $`/m`$. Notice that we have not imposed the relation $`\omega ^m=1`$. This version of extended affine Weyl group is isomorphic to the semidirect product of the lattice $`^m`$ of rank $`m`$ (not of $`m1`$) and the symmetric group $`𝑺_m`$ acting on it; the subgroup $`r_1,\mathrm{},r_{m1}`$ of $`\stackrel{~}{W}^m`$ is identified with $`𝑺_m`$ by mapping each $`r_i`$ to the adjacent transposition $`\sigma _i=(i,i+1)`$ $`(i=1,\mathrm{},m1)`$. We define $`\stackrel{~}{W}_n=s_0,s_1,\mathrm{},s_{n1},\pi `$ similarly to be the group generated by simple reflections $`s_0,s_1,\mathrm{},s_{n1}`$ and the diagram rotation $`\pi `$ :

$$\begin{array}{ccc}s_i^2=1,s_is_j=s_js_i(ji,i\pm 1\text{ mod }n),\hfill & & \\ s_is_js_i=s_js_is_j(ji\pm 1\text{ mod }n),\pi s_i=s_{i+1}\pi .\hfill & & \end{array}$$
(4.3)
The subgroup $`s_1,\mathrm{},s_{n1}`$ of $`\stackrel{~}{W}_n`$ is identified with the symmetric group $`𝑺_n`$.

We now propose to realize these two affine Weyl groups as a group of automorphisms of the field of rational functions $`𝕂(x)`$ in $`mn`$ variables $`x=(x_j^i)_{i,j}`$. With two extra parameters $`p,q`$, we take the field of rational functions $`𝕂=(p,q)`$ in $`(p,q)`$ as the ground field. In our realization, the groups $`\stackrel{~}{W}^m`$ and $`\stackrel{~}{W}_n`$ concern the nontrivial permutation of rows and columns of the matrix $`X=\left(\begin{array}{c}x_j^i\end{array}\right)_{i,j}`$, respectively. We first extend the indexing set $`\{1,\mathrm{},m\}\times \{1,\mathrm{},n\}`$ for the matrix $`X=\left(\begin{array}{c}x_j^i\end{array}\right)_{i,j}`$ to $`\times `$ by imposing the periodicity condition

$$x_j^{i+m}=q^1x_j^i,x_{j+n}^i=p^1x_j^i(i,j).$$
(4.4)
We define the automorphism $`r_k`$ ($`k/m`$) and $`\omega `$ of $`𝕂(x)`$ by

$`r_k(x_j^i)=px_j^{i+1}{\displaystyle \frac{P_j^i}{P_{j1}^i}},r_k(x_j^{i+1})=p^1x_j^i{\displaystyle \frac{P_{j1}^i}{P_j^i}}(ik\text{ mod }m),`$
$`r_k(x_j^i)=x_j^i(ik,k+1\text{ mod }m),\omega (x_j^i)=x_j^{i+1}`$ (4.5)
for $`i,j`$, where $`P_j^i`$ is the sum

$$P_j^i=\underset{k=1}{\overset{n}{}}x_{j+1}^{i+1}x_{j+2}^{i+1}\mathrm{}x_{j+k}^{i+1}x_{j+k}^ix_{j+k+1}^i\mathrm{}x_{j+n}^i$$
(4.6)
over all paths $`\gamma :(i+1,j+1)(i,j+n)`$ in the lattice $`\times `$. We define $`s_l`$ $`(l/n)`$ and $`\pi `$ by interchanging the roles of rows and columns, and of $`p`$ and $`q`$:

$`s_l(x_j^i)=qx_{j+1}^i{\displaystyle \frac{Q_j^i}{Q_j^{i1}}},s_l(x_{j+1}^i)=q^1x_j^i{\displaystyle \frac{Q_j^{i1}}{Q_j^i}}(jl\text{ mod }n),`$
$`s_l(x_j^i)=x_j^i(jl,l+1\text{ mod }n),\pi (x_j^i)=x_{j+1}^i`$ (4.7)
for $`i,j`$, where

$$Q_j^i=\underset{k=1}{\overset{m}{}}x_{j+1}^{i+1}x_{j+1}^{i+2}\mathrm{}x_{j+1}^{i+k}x_j^{i+k}x_j^{i+k+1}\mathrm{}x_j^{i+m}$$
(4.8)
summed over all paths $`\gamma :(i+1,j+1)(i+m,j)`$. It is directly seen that these definitions are consistent with the periodicity conditions on $`x_j^i`$. Also, it is clear that $`r_k`$ and $`s_l`$ have rotational symmetry

$$\begin{array}{cccc}\omega r_k=r_{k+1}\omega ,\hfill & \pi r_k=r_k\pi \hfill & (k/m),\hfill & \\ \omega s_l=s_l\omega ,\hfill & \pi s_l=s_{l+1}\pi \hfill & (l/n),\hfill & \end{array}$$
(4.9)
respectively.

###### Remark 4.1

The polynomials $`P_j^i`$ and $`Q_j^i`$ above are characterized by the recurrence relations

$$\begin{array}{cc}x_j^{i+1}P_j^iP_{j1}^ix_{j+n}^i=x_j^{i+1}(x_{j+1}^{i+1}\mathrm{}x_{j+n}^{i+1}x_j^i\mathrm{}x_{j+n1}^i)x_{j+n}^{i+1},\hfill & \\ x_{j+1}^iQ_j^iQ_j^{i1}x_j^{i+m}=x_{j+1}^i(x_{j+1}^{i+1}\mathrm{}x_{j+1}^{i+m}x_j^i\mathrm{}x_j^{i+m1})x_j^{i+m},\hfill & \end{array}$$
(4.10)
and the periodicity conditions $`P_{j+n}^i=p^{n1}P_j^i`$, $`Q_j^{i+m}=q^{m1}Q_j^i`$.

###### Theorem 4.2

The automorphisms $`r_k`$ $`(k/m)`$, $`\omega `$, $`s_l`$ $`(l/n)`$, $`\pi `$ of $`𝕂(x)`$ defined as above give a realization of the direct product $`\stackrel{~}{W}^m\times \stackrel{~}{W}_n`$ of two extended affine Weyl groups. In particular, the actions of $`\stackrel{~}{W}^m=r_0,\mathrm{},r_{m1},\omega `$ and $`\stackrel{~}{W}_n=s_0,\mathrm{},s_{n1},\pi `$ commute with each other.

In the next two subsections, we give a proof of this theorem by using two characterizations of birational actions of $`r_k`$ and $`s_l`$.

###### Remark 4.3

The realization of $`\stackrel{~}{W}^m\times \stackrel{~}{W}_n`$ mentioned above is the same as the one we gave in  ($`p=q=1`$), and ; the variables $`x_j^i`$ above correspond to $`x_{ij}^1`$ in . When $`p=q=1`$, it coincides with the birational realization of $`\stackrel{~}{W}^m\times \stackrel{~}{W}_n`$ constructed in , Theorem 4.12.

### 4.2 First characterization

By introducing the spectral parameter $`z`$, for an $`n`$-vector $`𝒙=(x_1,\mathrm{},x_n)`$ with $`x_i0`$ given, we introduce the following two matrices:

$$E(𝒙;z)=\text{diag}(𝒙)+\mathrm{\Lambda }(z),H(𝒙;z)=(\text{diag}(\overline{𝒙})\mathrm{\Lambda }(z))^1,$$
(4.11)
where

$$\mathrm{\Lambda }(z)=\underset{k=1}{\overset{n1}{}}E_{k,k+1}+zE_{n,1}.$$
(4.12)
Note that the definition of $`H(𝒙;z)`$ makes sense since

$$det(\text{diag}(\overline{𝒙})\mathrm{\Lambda }(z))=\overline{x}_1\mathrm{}\overline{x}_nz.$$
(4.13)
When $`z=0`$, these matrices reduce to $`E(𝒙)`$ and $`H(𝒙)`$ used in previous sections. Note also that $`H(𝒙;z)=DE(\overline{𝒙};z)^1D^1`$, $`D=\text{diag}((1)^{i1})_{i=1}^n`$. We remark that the entries of the matrix $`H(𝒙;z)`$ are expressed explicitly as

$$H(𝒙;z)_j^i=\{\begin{array}{ccc}\frac{x_ix_{i+1}\mathrm{}x_j}{1x_1\mathrm{}x_nz}\hfill & (ij),\hfill & \\ \frac{x_1\mathrm{}x_jx_i\mathrm{}x_nz}{1x_1\mathrm{}x_nz}\hfill & (i>j).\hfill & \end{array}$$
(4.14)
For two $`n`$-vectors $`𝒙=(x_1,\mathrm{},x_n)`$, $`𝒚=(y_1,\mathrm{},y_n)`$ of indeterminates given, we consider the following matrix equation for unknown vectors $`𝒖=(u_1,\mathrm{},u_n)`$, $`𝒗=(v_1,\mathrm{},v_n)`$ such that $`u_j0`$, $`v_j0`$:

$$H(𝒚;z)H(𝒙;pz)=H(𝒗;z)H(𝒖;pz),$$
(4.15)
or equivalently,

$$E(\overline{𝒙};pz)E(\overline{𝒚};z)=E(\overline{𝒖};pz)E(\overline{𝒗};z).$$
(4.16)
As before we extend the indexing set for $`x_j,y_j,\mathrm{}`$ to $``$ by setting $`x_{j+n}=p^1x_j`$, $`y_{j+n}=p^1y_j,\mathrm{}`$. Then the matrix equation $`(\text{4.16})`$ is equivalent to the system of algebraic equations of discrete Toda type

$$x_jy_j=u_jv_j,\frac{1}{x_j}+\frac{1}{y_{j+1}}=\frac{1}{u_j}+\frac{1}{v_{j+1}}(j).$$
(4.17)
(For the discrete Toda equation, see Remark 2.3.) The next lemma is fundamental in the following argument.

###### Lemma 4.4

The matrix equation $`(\text{4.15})`$ has the following two solutions:

$$\begin{array}{cccc}(1)\hfill & u_j=x_j,\hfill & v_j=y_j\hfill & (j=1,\mathrm{},n),\hfill \\ (2)\hfill & u_j=py_j\frac{P_j}{P_{j1}},\hfill & v_j=p^1x_j\frac{P_{j1}}{P_j}\hfill & (j=1,\mathrm{},n),\hfill \end{array}$$
(4.18)
where

$$P_j=\underset{k=1}{\overset{n}{}}y_{j+1}\mathrm{}y_{j+k}x_{j+k}\mathrm{}x_{j+n}(j=0,1,\mathrm{},n).$$
(4.19)
Proof: If $`v_{j+1}=y_{j+1}`$ for some $`j`$, form $`(\text{4.17})`$ it follows that $`u_j=x_j`$, and $`v_j=y_j`$. Hence we have $`u_j=x_j`$, $`v_j=y_j`$ for all $`j`$. Assuming that $`v_jy_j`$ for any $`j`$, we introduce the variable $`h_j`$ ($`j`$) such that

$$\frac{1}{v_{j+1}}=\frac{1}{y_{j+1}}+\frac{1}{h_j}(j),$$
(4.20)
so that $`h_{j+n}=p^1h_j`$. Then by eliminating $`u_j`$ in $`(\text{4.17})`$, we obtain the recurrence relations

$$\frac{h_j}{x_j}=1+\frac{h_{j1}}{y_j},\text{i.e.,}h_j=x_j+\frac{x_j}{y_j}h_{j1}(j)$$
(4.21)
for $`h_j`$. Hence we have

$$\begin{array}{cc}h_{j+n}\hfill & =x_{j+n}+\frac{x_{j+n1}x_{j+n}}{y_{j+n}}+\mathrm{}+\frac{x_{j+1}\mathrm{}x_{j+n}}{y_{j+2}\mathrm{}y_{j+n}}+\frac{x_{j+1}\mathrm{}x_{j+n}}{y_{j+1}\mathrm{}y_{j+n}}h_j\hfill \\ & =\frac{P_j+x_{j+1}\mathrm{}x_{j+n}h_j}{y_{j+1}\mathrm{}y_{j+n}}.\hfill \end{array}$$
(4.22)
Since $`h_{j+n}=p^1h_j`$, this equation determines $`h_j`$ as

$$h_j=\frac{P_j}{p^1y_{j+1}\mathrm{}y_{j+n}x_{j+1}\mathrm{}x_{j+n}}.$$
(4.23)
In fact, these $`h_j`$ satisfy the recurrence relations above, since

$$y_jP_jP_{j1}x_{j+n}=y_jy_{j+1}\mathrm{}y_{j+n}x_{j+n}y_jx_jx_{j+1}\mathrm{}x_{j+n},$$
(4.24)
Hence we have

$$\frac{1}{v_j}=\frac{1}{y_j}+\frac{1}{h_{j1}}=\frac{h_j}{x_jh_{j1}}=\frac{pP_j}{x_jP_{j1}},$$
(4.25)
and

$$\frac{1}{u_j}=\frac{1}{x_j}\frac{1}{h_j}=\frac{h_{j1}}{y_jh_j}=\frac{P_{j1}}{y_jpP_j},$$
(4.26)
which gives the solution (2). Q.E.D.

We remark that the two solutions above are characterized by the conditions

$$\begin{array}{ccc}(1)\hfill & u_1\mathrm{}u_n=x_1\mathrm{}x_n,\hfill & v_1\mathrm{}v_n=y_1\mathrm{}y_n,\hfill \\ (2)\hfill & u_1\mathrm{}u_n=p^1y_1\mathrm{}y_n,\hfill & v_1\mathrm{}v_n=px_1\mathrm{}x_n,\hfill \end{array}$$
(4.27)
respectively. Note here that $`P_n=p^{n1}P_0`$.

Returning to the setting of the previous subsection, we consider the matrix $`X=\left(\begin{array}{c}x_j^i\end{array}\right)_{i,j}`$. We denote the row vectors and the column vectors of $`X=\left(\begin{array}{c}x_j^i\end{array}\right)_{i,j}`$ by $`𝒙^i=(x_1^i,\mathrm{},x_n^i)`$ and $`𝒙_j=(x_j^1,\mathrm{},x_j^m)`$, respectively. Then Lemma 4.4 implies

$$H(𝒙^{k+1};z)H(𝒙^k;pz)=H(r_k(𝒙^{k+1});z)H(r_k(𝒙^k);pz),$$
(4.28)
where we have used the notation $`r_k(𝒙)=(r_k(x_1),\mathrm{},r_k(x_n))`$ for $`𝒙=(x_1,\mathrm{},x_n)`$. Since $`r_k(𝒙^i)=𝒙^i`$ for $`ik\text{ mod }m`$, we have

$`H(𝒙^m;z)H(𝒙^{m1};pz)\mathrm{}H(𝒙^1;p^{m1}z)`$
$`=H(r_k(𝒙^m);z)H(r_k(𝒙^{m1});pz)\mathrm{}H(r_k(𝒙^1);p^{m1}z)`$ (4.29)
for $`k=1,\mathrm{},m1`$. Namely, the product of matrices in the left-hand side is invariant under the action of $`r_k`$ ($`k=1,\mathrm{},m1`$). Hence we see that

$`H(𝒙^m;z)H(𝒙^{m1};pz)\mathrm{}H(𝒙^1;p^{m1}z)`$
$`=H(w(𝒙^m);z)H(w(𝒙^{m1});pz)\mathrm{}H(w(𝒙^1);p^{m1}z)`$ (4.30)
for any composition $`w=r_{k_1}r_{k_2}\mathrm{}r_{k_l}`$ with $`k_1,\mathrm{},k_l\{1,\mathrm{},m1\}`$. In the following, we set

$$H(X;z)=H(𝒙^m;z)H(𝒙^{m1};pz)\mathrm{}H(𝒙^1;p^{m1}z)$$
(4.31)
and

$$M(X;z)=E(\overline{𝒙}^1;p^{m1}z)E(\overline{𝒙}^2;p^{m1}z)\mathrm{}E(\overline{𝒙}^m;z)$$
(4.32)
so that $`H(X;z)=DM(X;z)^1D^1`$. Then we have

$$H(X;z)=H(w(X);z),M(X;z)=M(w(X);z)$$
(4.33)
for any $`w=r_{k_1}r_{k_2}\mathrm{}r_{k_l}`$ ($`k_1,\mathrm{},k_l\{1,\mathrm{},m1\}`$), where $`w(X)=\left(\begin{array}{c}w(x_j^i)\end{array}\right)_{i,j}`$ denotes the matrix obtained from $`X`$ by applying $`w`$ to its entries.

###### Proposition 4.5

All the entries of the matrices $`H(X;z)`$ and $`M(X;z)`$ are invariant under the action of $`r_1,\mathrm{},r_{m1}`$.

Considering $`X=\left(\begin{array}{c}x_j^i\end{array}\right)_{i,j}`$ as given, we now investigate in general the matrix equation $`H(X;z)=H(Y;z)`$ for an $`m\times n`$ unknown matrix $`Y=(y_j^i)_{i,j}`$, $`y_j^i0`$:

$`H(𝒙^m;z)H(𝒙^{m1};pz)\mathrm{}H(𝒙^1;p^{m1}z)`$
$`=H(𝒚^m;z)H(𝒚^{m1};pz)\mathrm{}H(𝒚^1;p^{m1}z).`$ (4.34)
Note that this equation is equivalent to $`M(X;z)=M(Y;z)`$:

$`E(\overline{𝒙}^1;p^{m1}z)E(\overline{𝒙}^2;p^{m2}z)\mathrm{}E(\overline{𝒙}^m;z)`$
$`=E(\overline{𝒚}^1;p^{m1}z)E(\overline{𝒚}^2;p^{m2}z)\mathrm{}E(\overline{𝒚}^m;z).`$ (4.35)
Since $`detH(𝒙;z)=(\overline{x}_1\mathrm{}\overline{x}_nz)^1`$, by comparing the determinants of the both sides of $`(\text{4.2})`$, we see that, for any solution of $`(\text{4.2})`$, there exists a unique permutation $`\sigma 𝑺_m`$ such that

$$p^{mi}y_1^i\mathrm{}y_n^i=p^{m\sigma (i)}x_1^{\sigma (i)}\mathrm{}x_n^{\sigma (i)}(i=1,\mathrm{},m).$$
(4.36)
###### Theorem 4.6

For each permutation $`\sigma 𝐒_m`$, the matrix equation $`(\text{4.2})`$ has a unique solution satisfying the condition $`(\text{4.36})`$. For any choice of expression $`\sigma =\sigma _{k_1}\mathrm{}\sigma _{k_l}`$ of $`\sigma `$ as a product of adjacent transpositions $`\sigma _k=(k,k+1)`$ $`(k=1,\mathrm{},m1)`$, the solution corresponding to $`\sigma `$ is given by

$$y_j^i=w(x_j^i)(i=1,\mathrm{},m;j=1,\mathrm{},n),$$
(4.37)
where $`w=r_{k_1}\mathrm{}r_{k_l}`$.

Proof: Since $`P_n^i=p^{n1}P_0^i`$ for any $`i`$, we have

$$\begin{array}{ccc}r_k(x_1^k\mathrm{}x_n^k)=p^1x_1^{k+1}\mathrm{}x_n^{k+1},r_k(x_1^{k+1}\mathrm{}x_n^{k+1})=px_1^k\mathrm{}x_n^k\hfill & & \\ r_k(x_1^i\mathrm{}x_n^i)=x_1^i\mathrm{}x_n^i(i=1,\mathrm{},k1,k+2,\mathrm{},n)\hfill & & \end{array}$$
(4.38)
for $`k=1,\mathrm{},m1`$. Hence,

$$r_k(x_1^i\mathrm{}x_n^i)=p^{i\sigma _k(i)}x^{\sigma _k(i)}\mathrm{}x_m^{\sigma _k(i)}(i=1,\mathrm{},m).$$
(4.39)
This implies furthermore that, for any composition $`w=r_{k_1}\mathrm{}r_{k_l}`$ of $`r_k`$ ($`k=1,\mathrm{},m1`$), we have

$$w(x_1^i\mathrm{}x_n^i)=p^{i\sigma (i)}x^{\sigma (i)}\mathrm{}x_n^{\sigma (i)}(i=1,\mathrm{},m).$$
(4.40)
where $`\sigma =\sigma _{k_1}\mathrm{}\sigma _{k_l}`$. Namely, $`w(𝒙^1),\mathrm{},w(𝒙^m)`$ give a solution of $`(\text{4.2})`$ satisfying the condition $`(\text{4.36})`$. In order to complete the proof of the theorem, we show that any solution $`𝒚^1,\mathrm{},𝒚^m`$ satisfying $`(\text{4.36})`$ must coincide with this solution. In the following we denote by $`\xi _i=p^{m+i}\overline{x}_1^i\mathrm{}\overline{x}_n^i`$ the pole of $`H(𝒙^i;p^{mi}z)`$. Consider the equality

$`H(w(𝒙^m);z)H(w(𝒙^{m1});pz)\mathrm{}H(w(𝒙^1);p^{m1}z)`$
$`=H(𝒚^m;z)H(𝒚^{m1};pz)\mathrm{}H(𝒚^1;p^{m1}z),`$ (4.41)
and multiply the both sides by $`H(𝒚^m;z)^1`$ from the left to get

$`H(𝒚^m;z)^1H(w(𝒙^m);z)H(w(𝒙^{m1});pz)\mathrm{}H(w(𝒙^1);p^{m1}z)`$
$`=H(𝒚^{m1};pz)\mathrm{}H(𝒚^1;p^{m1}z).`$ (4.42)
Since the right-hand side is regular at $`z=\xi _{\sigma (m)}=\overline{y}_1^m\mathrm{}\overline{y}_n^m`$, the residue of the left-hand side at $`z=\xi _{\sigma (m)}`$ must vanish. It implies

$$\left(\text{diag}(\overline{𝒚}^m)\mathrm{\Lambda }(\xi _{\sigma (m)})\right)\text{Res}_{z=\xi _{\sigma (m)}}(H(w(𝒙^m);z)dz)=0$$
(4.43)
since the matrices $`H(w(𝒙^i);\xi _{\sigma (m)})`$ ($`i=1,\mathrm{},m1`$) are all invertible. If we set $`\stackrel{~}{H}(𝒙;z)=(\overline{x}_1\mathrm{}\overline{x}_nz)H(𝒙;z)`$, it is equivalent to

$$(\text{diag}(\overline{𝒚}^m)\mathrm{\Lambda }(\xi _{\sigma (m)}))\stackrel{~}{H}(w(𝒙^m);\xi _{\sigma (m)})=0.$$
(4.44)
This equation determines $`𝒚^m`$ uniquely since $`\stackrel{~}{H}(w(𝒙^m);\xi _{\sigma (m)})_j^i0`$ for any $`i,j`$. Since $`(\text{diag}(w(\overline{𝒙}^m))\mathrm{\Lambda }(\xi _{\sigma (m)}))\stackrel{~}{H}(w(𝒙^m);\xi _{\sigma (m)})=0`$, we have $`𝒚^m=w(𝒙^m)`$, and also

$$H(w(𝒙^{m1});pz)\mathrm{}H(w(𝒙^1);p^{m1}z)=H(𝒚^{m1};pz)\mathrm{}H(𝒚^1;p^{m1}z).$$
(4.45)
By repeating the same procedure, we finally obtain $`𝒚^i=w(𝒙^i)`$ for all $`i=1,\mathrm{},m`$ as, desired. Q.E.D.

###### Corollary 4.7

Let $`i_1,\mathrm{},i_k`$ and $`j_1,\mathrm{},j_l`$ be two sequences of elements of $`\{1,\mathrm{},m1\}`$ such that

$$\sigma _{i_1}\mathrm{}\sigma _{i_k}=\sigma _{j_1}\mathrm{}\sigma _{j_l}.$$
(4.46)
Then the automorphisms $`r_1,\mathrm{},r_{m1}`$ satisfies the relation

$$r_{i_1}\mathrm{}r_{i_k}=r_{j_1}\mathrm{}r_{j_l}.$$
(4.47)
By this corollary and the rotational symmetry of $`r_k`$, we see that the automorphisms $`r_0,r_1,\mathrm{},r_{m1},\omega `$ satisfy the fundamental relations for the generators of $`\stackrel{~}{W}^m`$. The same statement is valid for $`s_0,s_1,\mathrm{},s_{n1}`$, $`\pi `$ and $`\stackrel{~}{W}_n`$ by the symmetry under the transposition of the matrix $`X`$.

###### Remark 4.8

Lemma 4.4 implies that the action of $`r_k`$ ($`k=1,\mathrm{},m1`$) is characterized by the system of algebraic equations of discrete Toda type

$$x_j^ix_j^{i+1}=y_j^iy_j^{i+1},\frac{1}{x_j^i}+\frac{1}{x_{j+1}^{i+1}}=\frac{1}{y_j^i}+\frac{1}{y_{j+1}^{i+1}}$$
(4.48)
for $`y_j^i=r_k(x_j^i)`$ $`(i,j)`$ with periodicity condition $`y_j^{i+m}=q^1y_j^i`$, $`y_{j+n}^i=p^1y_j^i`$, and an extra constraint

$$y_1^i\mathrm{}y_n^i=p^{i\sigma _k(i)}x_1^{\sigma _k(i)}\mathrm{}x_n^{\sigma _k(i)}(i=1,\mathrm{},m).$$
(4.49)
### 4.3 Second characterization

We give another characterization of $`r_k`$ and $`s_l`$, and use it for proving the commutativity of the actions of $`r_0,r_1,\mathrm{},r_{m1},\omega `$ and $`s_0,s_1,\mathrm{},s_{n1},\pi `$.

We define the $`n\times n`$ matrices $`G_l(u;z)`$, depending on a parameter $`u`$, by setting

$$G_0(u;z)=1+\frac{1}{u}E_{1,n}z^1,G_l(u;z)=1+\frac{1}{u}E_{l+1,l}(l=1,\mathrm{},n1).$$
(4.50)
For $`l=1,\mathrm{},n1`$, we also use the notation $`G_l(u)=G_l(u;z)`$ since they do not depend on $`z`$. Fix an index $`l=0,1,\mathrm{},n1`$, and consider the system of matrix equations

$$G_l(g_{i1};pz)E(\overline{𝒙}^i;z)=E(\overline{𝒚}^i;z)G_l(g_i;z)(i=1,\mathrm{},m)$$
(4.51)
for unknown variables $`𝒚^i`$ ($`i=1,\mathrm{},m`$) and $`g_i`$ ($`i=0,1,\mathrm{},m`$).

###### Theorem 4.9

Under the periodicity condition $`g_m=q^1g_0`$, the system of algebraic equations $`(\text{4.51})`$ has a unique solution. It is given explicitly as

$$\begin{array}{cc}g_i=\frac{Q_l^i}{q^1x_{l+1}^{i+1}\mathrm{}x_{l+1}^{i+m}x_l^{i+1}\mathrm{}x_l^{i+m}}(i=0,1,\mathrm{},m),\hfill & \\ y_j^i=s_l(x_j^i)(i=1,\mathrm{},m;j=1,\mathrm{},n).\hfill & \end{array}$$
(4.52)
Proof: It is easily seen that the matrix equation $`(\text{4.51})`$ is equivalent to the recurrence relations

$$g_i=x_l^i+\frac{x_l^i}{x_{l+1}^i}g_{i1}(i=1,\mathrm{},m),$$
(4.53)
together with

$$\begin{array}{cc}\frac{1}{y_l^i}=\frac{1}{x_l^i}\frac{1}{g_i},\frac{1}{y_{l+1}^i}=\frac{1}{x_{l+1}^i}+\frac{1}{g_{i1}},\hfill & \\ y_j^i=x_j^i(jl,l+1\text{ mod }n).\hfill & \end{array}$$
(4.54)
These are the same recurrence relations as we have discussed in Lemma 4.4. As we already know, $`(\text{4.53})`$ determines $`g_i`$, and $`(\text{4.54})`$ gives rise to the expressions we have used in defining $`s_l`$. Q.E.D.

Note that the matrix equation $`(\text{4.51})`$ implies

$$G_l(g_0;p^mz)M(X;z)=M(Y;z)G_l(q^1g_0;z).$$
(4.55)
Hence, by Theorem 4.9, we see that the action of $`s_l`$ on $`M(X;z)`$ is described by

$$M(s_l(X);z)=G_l(g_0;p^mz)M(X;z)G_l(q^1g_0;z)^1.$$
(4.56)
In terms of the matrix $`H(X;z)`$, this formula can be written as

$$H(s_l(X);z)=G_l(q^1g_0;(1)^nz)^1H(X;z)G_l(g_0;(1)^nz).$$
(4.57)
We remark that the rational function $`g_0`$ can be determined only from $`M(X;z)`$. It is an easy exercise to show

###### Lemma 4.10

Let $`𝔟`$ be the space of all $`n\times n`$ matrix $`M(z)`$ with coefficients in $`𝕂(x)[z]`$ such that $`M(0)`$ is upper triangular. For a matrix

$$M(z)=M_0+M_1z+\mathrm{}+M_dz^d𝔟$$
(4.58)
given, set

$$\begin{array}{cc}\epsilon _i=(M_0)_i^i,& (i=1,\mathrm{},n),\hfill \\ \phi _0=(M_1)_1^n,\phi _i=(M_0)_{i+1}^i& (i=1,\mathrm{},n1).\hfill \end{array}$$
(4.59)
Then we have

$$G_0(u;az)M(z)G_0(q^1u;z)^1𝔟(q^1\epsilon _na\epsilon _1)u=\phi _0,$$
(4.60)
and

$$G_l(u)M(z)G_l(q^1u)^1𝔟(q^1\epsilon _l\epsilon _{l+1})u=\phi _l,$$
(4.61)
for $`l=1,\mathrm{},n1`$. In particular, the parameter $`u`$ is determined uniquely from from $`M(z)`$ if $`\epsilon _i`$ and $`\phi _i`$ are generic.

This lemma implies that $`g_0`$ is expressed as a rational function of entries of $`M(X;z)`$. Hence, by Proposition 4.5, we see that $`g_0`$ in invariant under the action of $`r_1,\mathrm{},r_{m1}`$.

We now prove the commutativity of the actions of $`r_0,r_1,\mathrm{},r_{m1}`$ and $`s_0,s_1,\mathrm{},s_{n1}`$. By the rotational symmetry of $`r_k`$, it suffices to prove $`s_lw=ws_l`$ ($`l=0,1,\mathrm{},n1`$), assuming that $`wr_1,\mathrm{},r_{m1}`$. Applying $`w`$ to $`(\text{4.56})`$, we have

$$M(ws_l(X);z)=G_l(w(g_0);p^mz)M(w(X);z)G_l(q^1w(g_0);z)^1.$$
(4.62)
By Proposition 4.5, we have $`M(w(X);z)=M(X;z)`$, and also, $`w(g_0)=g_0`$ as we remarked above. This implies that $`M(ws_l(X);z)=M(s_l(X);z)`$. By applying $`s_l`$ again, we obtain

$$M(s_lws_l(X);z)=M(s_l^2(X);z)=M(X;z).$$
(4.63)
Note that $`s_l(x_1^i\mathrm{}x_n^i)=x_1^i\mathrm{}x_n^i`$ for any $`i=1,\mathrm{},m`$. Hence, for $`Y=s_lws_l(X)`$, we have

$$y_1^i\mathrm{}y_n^i=p^{i\sigma (i)}x_1^{\sigma (i)}\mathrm{}x_n^{\sigma (i)}(i=1,\mathrm{},m),$$
(4.64)
where $`\sigma 𝑺_m`$ is the permutation corresponding to $`w`$. Then, by Theorem 4.6, we obtain $`Y=w(X)`$. This means that $`s_lws_l(X)=w(X)`$, namely, $`s_lws_l=w`$. This completes the proof of Theorem 4.2.

Recall that the roles of $`r_k`$, $`s_l`$ are interchanged with each other by the transposition of the matrix $`X=\left(\begin{array}{c}x_j^i\end{array}\right)_{i,j}`$. Accordingly, the two characterization we have discussed so far can be applied to both $`r_k`$ and $`s_l`$.

### 4.4 Passage to the tropical tableaux

In what follows we set $`𝑺^m=r_1,\mathrm{},r_{m1}`$ and $`𝑺_n=s_1,\mathrm{},s_{n1}`$.

Let us consider the tropical RSK correspondence $`X(U,V)`$ with the notation as in the previous section:

$`H(𝒙^m)\mathrm{}H(𝒙^2)H(𝒙^1)=H_m(𝒖^m)\mathrm{}H_2(𝒖^2)H_1(𝒖^1)=H_U,`$
$`H(𝒙_n)\mathrm{}H(𝒙_2)H(𝒙_1)=H_m(𝒗^m)\mathrm{}H_2(𝒗^2)H_1(𝒗^1)=H_V.`$ (4.65)
As before we assume that $`mn`$. We regard now the variables $`u_j^i`$ and $`v_j^i`$ ($`ij`$) as elements of $`𝕂(x)`$. Note that by specializing the spectral parameter $`z`$ to zero, we have

$$H(X;0)=H(𝒙^m)\mathrm{}H(𝒙^1)=H_U.$$
(4.66)
By Proposition 4.5, we already know that $`H(X;z)`$, hence $`H(X;0)`$ is invariant under the action of the symmetric group $`𝑺^m=r_1,\mathrm{},r_{m1}`$. Since the variables $`u_j^i`$ are determined uniquely from the matrix $`H_U=H(X;0)`$, we conclude that all $`u_j^i`$ are invariant under the action of $`𝑺^m=r_1,\mathrm{},r_{m1}`$.

We now consider the action of $`𝑺_n=s_1,\mathrm{},s_{n1}`$. For $`l=1,\mathrm{},n1`$, from $`(\text{4.57})`$, we have

$$H(s_l(X);0)=G_l(q^1g_0)^1H(X;0)G_l(g_0),$$
(4.67)
hence

$$s_l(H_U)=G_l(q^1g_0)^1H_UG_l(g_0),$$
(4.68)
where

$$g_0=\frac{{\displaystyle \underset{k=1}{\overset{m}{}}}x_{l+1}^1\mathrm{}x_{l+1}^kx_l^k\mathrm{}x_l^m}{q^1x_{l+1}^1\mathrm{}x_{l+1}^mx_l^1\mathrm{}x_l^m}.$$
(4.69)
This formula is equivalent to

$$s_l(M_U)=G_l(g_0)M_UG_l(q^1g_0),$$
(4.70)
where

$$M_U=DH_U^1D^1=E_1(\overline{𝒖}^1)\mathrm{}E_m(\overline{𝒖}^m).$$
(4.71)
By applying Lemma 4.10 to $`(\text{4.70})`$, we see that $`g_0`$ is expressed as follows in terms of the $`u`$-variables:

$$g_0=\{\begin{array}{cc}\frac{{\displaystyle \underset{k=1}{\overset{l}{}}}u_{l+1}^1\mathrm{}u_{l+1}^ku_l^k\mathrm{}u_l^l}{q^1u_{l+1}^1\mathrm{}u_{l+1}^{l+1}u_l^1\mathrm{}u_l^l}\hfill & (l=1,\mathrm{},m1),\hfill \\ \frac{{\displaystyle \underset{k=1}{\overset{m}{}}}u_{l+1}^1\mathrm{}u_{l+1}^ku_l^k\mathrm{}u_l^m}{q^1u_{l+1}^1\mathrm{}u_{l+1}^mu_l^1\mathrm{}u_l^m}\hfill & (l=m,\mathrm{},n1).\hfill \end{array}$$
(4.72)
Hence, formula $`(\text{4.70})`$ as well as $`(\text{4.68})`$ determines completely the action of $`s_l`$ on the $`u`$-variables.

In order to describe the action of $`s_l`$ on the $`u`$-variables, for each $`0i\mathrm{min}\{l,m\}`$, we define

$$\begin{array}{ccc}A_l^i=u_l^1\mathrm{}u_l^i\underset{k=i+1}{\overset{l}{}}u_{l+1}^{i+1}\mathrm{}u_{l+1}^ku_l^k\mathrm{}u_l^l\hfill & & \\ +q^1u_{l+1}^{i+1}\mathrm{}u_{l+1}^{l+1}\underset{k=1}{\overset{i}{}}u_{l+1}^1\mathrm{}u_{l+1}^ku_l^k\mathrm{}u_l^i\hfill & (1lm1),\hfill & \\ A_l^i=u_l^1\mathrm{}u_l^i\underset{k=i+1}{\overset{m}{}}u_{l+1}^{i+1}\mathrm{}u_{l+1}^ku_l^k\mathrm{}u_l^m\hfill & & \\ +q^1u_{l+1}^{i+1}\mathrm{}u_{l+1}^m\underset{k=1}{\overset{i}{}}u_{l+1}^1\mathrm{}u_{l+1}^ku_l^k\mathrm{}u_l^i\hfill & (mln1).\hfill & \end{array}$$
(4.73)
###### Theorem 4.11

Under the tropical RSK correspondence $`X(U,V)`$, the variables $`u_j^i`$ $`(1im;ijn)`$ are invariant with respect to the action of $`𝐒^m=r_1,\mathrm{},r_{m1}`$. The action of $`s_l`$ $`(l=1,\mathrm{},n1)`$ on $`u_j^i`$ is described as follows $`:`$

$$\begin{array}{c}s_l(u_l^i)=u_{l+1}^i\frac{A_l^i}{A_l^{i1}},s_l(u_{l+1}^i)=u_l^i\frac{A_l^{i1}}{A_l^i},\\ s_l(u_j^i)=u_j^i(jl,l+1)\end{array}$$
(4.74)
for $`1i\mathrm{min}\{l,m\}`$ and $`s_l(u_j^i)=u_j^i`$ for $`\mathrm{min}\{l,m\}+1im`$.

Proof: Fixing the index $`l=1,\mathrm{},n1`$, we consider the system of matrix equations

$$G_l(a_{i1})E_i(\overline{𝒖}^i)=E_i(\overline{𝒕}^i)G_l(a_i)(i=1,\mathrm{},m)$$
(4.75)
for unknown variables $`𝒕^i=(1,\mathrm{},1,t_i^i,\mathrm{},t_n^i)`$ ($`i=1,\mathrm{},m`$) and $`a_i`$ ($`i=0,1,\mathrm{},m`$). We will construct below a solution of this system such that $`a_m=q^1a_0`$, so that

$$G_l(a_0)M_U=M_TG_l(q^1a_0);$$
(4.76)
this equation must imply $`a_0=g_0`$ and $`T=s_l(U)`$. The system of matrix equations $`(\text{4.75})`$ gives the recurrence relations

$$\begin{array}{cc}a_i=u_l^i+\frac{u_l^i}{u_{l+1}^i}a_{i1}(1il),\hfill & \\ a_{l+1}=\frac{1}{u_{l+1}^{l+1}}a_l,a_i=a_{i1}(l+2im).\hfill & \end{array}$$
(4.77)
for $`a_i`$, and also

$$\frac{1}{t_l^i}=\frac{1}{u_l^i}\frac{1}{a_i},\frac{1}{t_{l+1}^i}=\frac{1}{u_{l+1}^i}+\frac{1}{a_{i1}},t_j^i=u_j^i(jl,l+1).$$
(4.78)
for $`1il`$ and $`t_j^i=u_j^i`$ for $`l+1im`$. Under the condition $`a_m=q^1a_0`$, the recurrence relations $`(\text{4.77})`$ for $`a_i`$ are solved by

$$a_i=\frac{A_l^i}{q^1u_{l+1}^1\mathrm{},u_{l+1}^{\mathrm{min}\{l+1,m\}}u_l^1\mathrm{}u_l^l}(0i\mathrm{min}\{l,m\}).$$
(4.79)
Hence we obtain the expression for $`t_j^i=s_l(u_j^i)`$ as $`(\text{4.74})`$. Q.E.D.

By eliminating $`a_i`$ in $`(\text{4.77})`$, $`(\text{4.78})`$, we obtain

###### Proposition 4.12

The action of $`s_l`$ $`(l=1,\mathrm{},n1)`$ on the tropical tableau $`U=\left(\begin{array}{c}u_j^i\end{array}\right)_{ij}`$ is characterized by the following system of algebraic equations of discrete Toda type for $`t_j^i=s_l(u_j^i)`$$`:`$

$$\begin{array}{cccc}t_l^it_{l+1}^i=u_l^iu_{l+1}^i(i=1,\mathrm{},l),\hfill & t_{l+1}^{l+1}=u_{l+1}^{l+1},\hfill & & \\ \frac{1}{t_l^i}+\frac{1}{t_{l+1}^{i+1}}=\frac{1}{u_l^i}+\frac{1}{u_{l+1}^{i+1}}\hfill & (i=1,\mathrm{},l1),\hfill & & \\ \frac{1}{t_l^l}+\frac{q}{t_{l+1}^{l+1}t_{l+1}^1}=\frac{1}{u_l^l}+\frac{q}{u_{l+1}^{l+1}u_{l+1}^1}\hfill & & & \end{array}$$
(4.80)
for $`l=1,\mathrm{},m1`$, and

$$\begin{array}{cccc}t_l^it_{l+1}^i=u_l^iu_{l+1}^i\hfill & (i=1,\mathrm{},m),\hfill & & \\ \frac{1}{t_l^i}+\frac{1}{t_{l+1}^{i+1}}=\frac{1}{u_l^i}+\frac{1}{u_{l+1}^{i+1}}\hfill & (i=1,\mathrm{},m1),\hfill & & \\ \frac{1}{t_l^m}+\frac{q}{t_{l+1}^1}=\frac{1}{u_l^m}+\frac{q}{u_{l+1}^1}\hfill & & & \end{array}$$
(4.81)
for $`l=m,\mathrm{},n1`$, together with the constraint

$`t_l^1\mathrm{}t_l^{\mathrm{min}\{l,m\}}=u_{l+1}^1\mathrm{}u_{l+1}^{\mathrm{min}\{l+1,m\}},`$
$`t_{l+1}^1\mathrm{}t_{l+1}^{\mathrm{min}\{l+1,m\}}=u_l^1\mathrm{}u_l^{\mathrm{min}\{l,m\}}.`$ (4.82)
The action of the tropical Schützenberger involution on the tropical tableau $`U=\left(\begin{array}{c}u_j^i\end{array}\right)_{ij}`$ plays the role of reversing the indices of the transformations $`s_1,\mathrm{},s_{n1}`$ and interchanging $`q`$ and $`q^1`$. Denoting by $`𝕂(u)`$ the field of rational functions in the variables $`u=(u_j^i)_{i,j}`$, we define the involutive automorphism $`𝗌:𝕂(u)𝕂(u)`$ by using the tropical Schützenberger involution of Theorem 2.8 :

$$𝗌(u_i^i)=\frac{\sigma _i^i}{\sigma _i^{i1}},𝗌(u_j^i)=\frac{\sigma _j^i\sigma _{j1}^{i1}}{\sigma _j^{i1}\sigma _{j1}^i}(i<j),$$
(4.83)
where

$$\sigma _j^i=\underset{(\gamma _1,\mathrm{},\gamma _i)}{}u_{\gamma _1}\mathrm{}u_{\gamma _i}$$
(4.84)
is the sum of weights associated with $`U`$, over all $`i`$-tuples of nonintersecting paths $`\gamma _k:(1,ni+k)(\mathrm{min}\{m,nj+k\},nj+k)`$ $`(k=1,\mathrm{},i)`$.

###### Theorem 4.13

For each $`l=1,\mathrm{},n1`$, let $`s_l^q:𝕂(u)𝕂(u)`$ the automorphisms defined as in Theorem 4.11. Then we have $`𝗌s_l^q=s_{nl}^{q^1}𝗌`$ for $`(l=1,\mathrm{},n1)`$.

Proof: The tropical tableau $`𝗌(U)=\left(\begin{array}{c}𝗌(u_j^i)\end{array}\right)_{ij}`$ is characterized by the condition

$$H_{𝗌(U)}=\theta (H_U)=J_nH_U^\text{t}J_n,$$
(4.85)
or equivalently, by

$$M_{𝗌(U)}=\theta (M_U)=J_nM_U^\text{t}J_n.$$
(4.86)
Hence, by applying $`s_l^q`$ to this equality, we have

$$M_{s_l^q𝗌(U)}=\theta (M_{s_l^q(U)}).$$
(4.87)
Recall that the action of $`s_l`$ ($`l=1,\mathrm{},n1`$) is characterized by

$$M_{s_l^q(U)}=G_l(a_0)M_UG_l(q^1a_0)^1.$$
(4.88)
Since $`\theta (G_l(a))=G_{nl}(a)=G_{nl}(a)^1`$, we obtain

$`\theta (M_{s_l^q(U)})=G_{nl}(q^1a_0)\theta (M_U)G_{nl}(a_0)^1`$
$`=G_{nl}(q^1a_0)M_{𝗌(U)}G_{nl}(a_0)^1`$ (4.89)
By combining this with $`(\text{4.87})`$, we obtain

$$M_{s_l^q𝗌(U)}=G_{ml}(q^1a_0)M_{𝗌(U)}G_{nl}(a_0)^1.$$
(4.90)
By applying $`𝗌`$ again, we have

$`M_{𝗌s_l^q𝗌(U)}=G_{ml}(q^1𝗌(a_0))M_{s^2(U)}G_{nl}(𝗌(a_0))^1`$
$`=G_{ml}(q^1𝗌(a_0))M_UG_{nl}(𝗌(a_0))^1`$
$`=M_{s_l^{q^1}(U)}.`$ (4.91)
The last equality is a consequence of Lemma 4.10. This implies $`𝗌s_l^q𝗌(u_j^i)=s_l^{q^1}(u_j^i)`$ for all $`ij`$, as desired. Q.E.D.

### 4.5 Combinatorial formulas for the Weyl group action

By the standard procedure of Section 1.3, we can derive the piecewise linear action of the direct product $`\stackrel{~}{W}^m\times \stackrel{~}{W}_n`$ of affine Weyl groups on the space of transportation matrices $`X`$. Also, via the RSK correspondence, we obtain the piecewise linear action of $`𝑺_n=s_1,\mathrm{},s_{n1}`$ (resp. $`𝑺^m=r_1,\mathrm{},r_{m1}`$ ) on the space of tableaux $`U=\left(\begin{array}{c}u_j^i\end{array}\right)_{ij}`$ (resp. $`V=\left(\begin{array}{c}v_j^i\end{array}\right)_{ij}`$).

Consider the space $`\text{Mat}_{m,n}()`$ of real $`m\times n`$ matrices $`X=\left(\begin{array}{c}x_j^i\end{array}\right)_{i,j}`$, regarding $`x=(x_j^i)_{i,j}`$ as the canonical coordinates. For each multi-index $`\alpha =(\alpha _j^i)_{i,j}^{mn}`$ and $`a,b`$, we define the linear function $`\mathrm{}_{\alpha ,a,b}(x)`$ on $`\text{Mat}_{m,n}()`$ by

$$\mathrm{}_{\alpha ,a,b}(x)=\underset{i,j}{}\alpha _j^ix_j^i+ap+bq,$$
(4.92)
where $`p,q`$ are parameters. Note that $`\mathrm{}_{\alpha ,a,b}(x)=M(x^\alpha p^aq^b)`$ in the notation of Section 1.3. We denote by $`_X`$ the set of all piecewise linear functions $`f=f(x)`$ in the form

$$f(x)=\mathrm{max}\{\mathrm{}_{\alpha ,a,b}(x)(\alpha ,a,b)A\}\mathrm{max}\{\mathrm{}_{\beta ,c,d}(x)(\beta ,c,d)B\},$$
(4.93)
where $`A`$, $`B`$ are nonempty finite sets of triples $`(\alpha ,a,b)`$ of $`\alpha ^{mn}`$ and $`a,b`$. Since $`_X=M((x,p,q)_{>0})`$, $`_X`$ is closed under the addition, the subtraction and “$`\mathrm{max}`$”; it is also closed under “$`\mathrm{min}`$” since $`\mathrm{min}\{f,g\}=f+g\mathrm{max}\{f,g\}`$. We say that an isomorphism $`w:_X_X`$ of $``$-modules is combinatorial if $`w(\mathrm{max}\{f,g\})=\mathrm{max}\{w(f),w(g)\}`$ for any $`f,g_X`$.

We first extend the indexing set for $`x_j^i`$ by setting

$$x_j^{i+m}=x_j^iq,x_{j+n}^i=x_j^ip(i,j).$$
(4.94)
We define the action of $`r_k`$ ($`k=0,1,\mathrm{},m`$), $`\omega `$ and $`s_l`$ $`(l=0,1,\mathrm{},n)`$, $`\pi `$ on the variables $`x_j^i`$ as follows:

$`\begin{array}{c}r_k(x_j^i)=x_j^{i+1}+P_j^iP_{j1}^i+p\hfill \\ r_k(x_j^{i+1})=x_j^i+P_{j1}^iP_j^ip\hfill \end{array}(ik\text{ mod }m),`$ (4.97)
$`r_k(x_j^i)=x_j^i(ik,k+1\text{ mod }m),\omega (x_j^i)=x_j^{i+1},`$
$`\begin{array}{c}s_l(x_j^i)=x_{j+1}^i+Q_j^iQ_j^{i1}+q\hfill \\ s_l(x_{j+1}^i)=x_j^i+Q_j^{i1}Q_j^iq\hfill \end{array}(jl\text{ mod }n),`$ (4.100)
$`s_l(x_j^i)=x_j^i(jl,l+1\text{ mod }n),\pi (x_j^i)=x_{j+1}^i,`$ (4.101)
for $`i,j`$, where

$`P_j^i=\underset{1kn}{\mathrm{max}}\left({\displaystyle \underset{a=1}{\overset{k}{}}}x_{j+a}^{i+1}+{\displaystyle \underset{a=k}{\overset{n}{}}}x_{j+a}^i\right),`$
$`Q_j^i=\underset{1km}{\mathrm{max}}\left({\displaystyle \underset{a=1}{\overset{k}{}}}x_{j+1}^{i+a}+{\displaystyle \underset{a=k}{\overset{m}{}}}x_j^{i+a}\right).`$ (4.102)
These formulas can also be written in terms of “$`\mathrm{min}`$”; for instance,

$$\begin{array}{c}r_k(x_j^i)=x_j^{i+1}R_j^i+R_{j1}^i+p\hfill \\ r_k(x_j^{i+1})=x_j^iR_{j1}^i+R_j^ip\hfill \end{array}(ik\text{ mod }m),$$
(4.103)
where

$$R_j^i=\underset{1kn}{\mathrm{min}}\left(\underset{a=1}{\overset{k1}{}}x_{j+a}^i+\underset{a=k+1}{\overset{n}{}}x_{j+a}^{i+1}\right).$$
(4.104)
###### Theorem 4.14

Define the mappings $`r_k`$ $`(k/m)`$, $`\omega `$ and $`s_l`$ $`(l/n)`$, $`\pi `$ from the set of variables $`x_j^i`$ to $`_X`$ as above. Then each of them extends uniquely to a combinatorial isomorphism $`_X_X`$. Furthermore, they give a realization of the direct product $`\stackrel{~}{W}^m\times \stackrel{~}{W}_n`$ of affine Weyl groups as a group of combinatorial isomorphisms of $`_X`$.

###### Proposition 4.15

By using the action of $`r_k`$ $`(k=1,\mathrm{},m1)`$, set $`y_j^i=r_k(x_j^i)`$ for all $`i,j`$. Then we obtain a solution to the ultra-discrete equation of Toda type

$$x_j^i+x_j^{i+1}=y_j^i+y_j^{i+1},\mathrm{min}\{x_j^i,x_{j+1}^{i+1}\}=\mathrm{min}\{y_j^i,y_{j+1}^{i+1}\}$$
(4.105)
with periodicity condition $`y_j^{i+m}=y_j^iq`$, $`y_{j+n}^i=y_j^ip`$, satisfying the constraint

$$y_1^i+\mathrm{}+y_n^i=x_1^{\sigma _k(i)}+\mathrm{}+x_n^{\sigma _k(i)}+(i\sigma _k(i))p(i=1,\mathrm{},m).$$
(4.106)
###### Remark 4.16

Let $`B=_{l=0}^{\mathrm{}}B_l`$ the crystal basis of the symmetric tensor representation $`S(V)=_{l=0}^{\mathrm{}}S_l(V)`$ of $`𝔤𝔩(n)`$ associated with the vector representation $`V=^n`$. Then $`B`$ is identified with the set of $`n`$-vectors $`𝒙=(x_1,\mathrm{},x_n)`$ of nonnegative integers. The crystal basis $`B^m=B\mathrm{}B`$ ($`m`$ times) for the $`m`$-th tensor product $`S(V)^m`$ is parametrized by $`^{mn}`$. We identify the matrix $`X=\left(\begin{array}{c}x_j^i\end{array}\right)_{i,j}`$ with the coordinates of $`B^m=^{mn}`$, regarding $`𝒙^i=(x_1^1,\mathrm{},x_n^i)`$ as corresponding to the $`i`$-th component. When $`p=q=0`$, the actions of $`r_k`$ $`(k=1,\mathrm{},m1)`$ and $`s_l`$ ($`l=1,\mathrm{},n1`$) on the variables $`x_j^i`$ coincide with the combinatorial $`R`$-matrix acting on the $`k`$-th and $`(k+1)`$-st components of $`B^m`$, and Kashiwara’s Weyl group actions, respectively (see , ).

Assuming that $`mn`$, we consider the variables $`u_j^i`$ ($`1im;ijn`$) and $`v_j^i`$ ($`1ijm`$), associated with the column strict tableaux $`U`$ and $`V`$, through the RSK correspondence $`X(U,V)`$. Recall that each $`u_j^i`$ (resp. $`v_j^i`$) denotes the number of $`j`$’s in the $`i`$-th row of $`U`$ (resp. $`V`$). Then, by the explicit piecewise linear formulas described in Theorem 3.9, $`u_j^i`$ and $`v_j^i`$ are regarded as elements in $`_X`$. We thus obtain a combinatorial action of $`\stackrel{~}{W}^m\times \stackrel{~}{W}_n`$ on the variables $`u_j^i`$ and $`v_j^i`$. We describe below the action of the subgroups $`𝑺^m=r_1,\mathrm{},r_{m1}`$ and $`𝑺_n=s_1,\mathrm{},s_{n1}`$ on $`u_j^i`$; their action on $`v_j^i`$ is given by an obvious modification.

In view of $`(\text{4.73})`$, we define $`A_l^i`$ ($`0i\mathrm{min}\{l,m\}`$) for the combinatorial version by

$$\begin{array}{ccc}A_l^i=\mathrm{max}\{\underset{i+1kl}{\mathrm{max}}(u_l^1+\mathrm{}+u_l^i+u_{l+1}^{i+1}+\mathrm{}+u_{l+1}^k+u_l^k\mathrm{}+u_l^l),\hfill & & \\ \underset{1ki}{\mathrm{max}}(u_{l+1}^{i+1}+\mathrm{}+u_{l+1}^{l+1}+u_{l+1}^1+\mathrm{}+u_{l+1}^k+u_l^k+\mathrm{}+u_l^iq)\}\hfill & & \end{array}$$
(4.107)
for $`1lm1`$, and by

$$\begin{array}{ccc}A_l^i=\mathrm{max}\{\underset{i+1km}{\mathrm{max}}(u_l^1+\mathrm{}+u_l^i+u_{l+1}^{i+1}+\mathrm{}+u_{l+1}^k+u_l^k\mathrm{}+u_l^m),\hfill & & \\ \underset{1ki}{\mathrm{max}}(u_{l+1}^{i+1}+\mathrm{}+u_{l+1}^m+u_{l+1}^1+\mathrm{}+u_{l+1}^k+u_l^k+\mathrm{}+u_l^iq)\}\hfill & & \end{array}$$
(4.108)
for $`mln1`$. Then, from Theorem 4.11 we obtain

###### Theorem 4.17

The variables $`u_j^i`$ are invariant under the action of the symmetric group $`𝐒^m=r_1,\mathrm{},r_{m1}`$ induced via the RSK correspondence. The action of $`s_l`$ $`(l=1,\mathrm{},n1)`$ is given explicitly as follows:

$$\begin{array}{c}s_l(u_l^i)=u_{l+1}^i+A_l^iA_l^{i1},s_l(u_{l+1}^i)=u_l^i+A_l^{i1}A_l^i,\\ s_l(u_j^i)=u_j^i(jl,l+1)\end{array}$$
(4.109)
for $`1i\mathrm{min}\{l,m\}`$ and $`s_l(u_j^i)=u_j^i`$ for $`\mathrm{min}\{l,m\}+1im`$.

Note that $`v_j^i`$ are invariant under the action of $`𝑺_n=\{s_1,\mathrm{},s_{n1}\}`$, and that $`r_k`$ ($`k=1,\mathrm{},m1`$) act on $`v_j^i`$ by explicit piecewise linear formulas similar to those described above.

###### Proposition 4.18

By using the action of $`s_l`$ $`(l=1,\mathrm{},n1)`$, set $`t_j^i=s_l(u_j^i)`$ for $`1im`$, $`ijn`$. Then we obtain a solution to the ultra-discrete equation of Toda type

$$\begin{array}{cccc}t_l^i+t_{l+1}^i=u_l^i+u_{l+1}^i(i=1,\mathrm{},l),t_{l+1}^{l+1}=u_{l+1}^{l+1},\hfill & & & \\ \mathrm{min}\{t_l^i,t_{l+1}^{i+1}\}=\mathrm{min}\{u_l^i,u_{l+1}^{i+1}\}(i=1,\mathrm{},l1),\hfill & & & \\ \mathrm{min}\{t_l^l,t_{l+1}^{l+1}+t_{l+1}^1q\}=\mathrm{min}\{u_l^l,u_{l+1}^{l+1}+u_{l+1}^1q\}\hfill & & & \end{array}$$
(4.110)
for $`l=1,\mathrm{},m1`$, and

$$\begin{array}{cccc}t_l^i+t_{l+1}^i=u_l^i+u_{l+1}^i\hfill & (i=1,\mathrm{},m),\hfill & & \\ \mathrm{min}\{t_l^i,t_{l+1}^{i+1}\}=\mathrm{min}\{u_l^i,u_{l+1}^{i+1}\}\hfill & (i=1,\mathrm{},m1),\hfill & & \\ \multicolumn{2}{c}{\mathrm{min}\{t_l^m,t_{l+1}^1q\}=\mathrm{min}\{u_l^m,u_{l+1}^1q\}}& & \end{array}$$
(4.111)
for $`l=m,\mathrm{},n1`$, satisfying the constraint

$`t_l^1+\mathrm{}+t_l^{\mathrm{min}\{l,m\}}=u_{l+1}^1+\mathrm{}+u_{l+1}^{\mathrm{min}\{l+1,m\}},`$
$`t_{l+1}^1+\mathrm{}+t_{l+1}^{\mathrm{min}\{l+1,m\}}=u_l^1+\mathrm{}+u_l^{\mathrm{min}\{l,m\}}.`$ (4.112)
###### Remark 4.19

The variables $`u_j^i`$ are identified with the coordinates of crystal bases for general finite dimensional irreducible representations of $`𝔤𝔩(n)`$ as in . Then, by using an argument as in , it can be shown that the combinatorial action of $`𝑺_n=s_1,\mathrm{},s_{n1}`$ on $`u_j^i`$ with $`q=0`$ provides with the description of Kashiwara’s Weyl group actions on the crystal bases. This symmetric group action on the set of column strict tableaux thus coincides with the one introduced earlier by A. Lascoux and M.P. Schützenberger (see also ). The corresponding piecewise linear action is discussed in .