ULTRADISCRETE CONNECTION MATRICES OVER A TROPICAL SEMIRING

C. ORMEROD

Abstract. We consider linear systems of difference equations over the maxplus semiring. We extend theorems of Birkhoff et. al. to the realm of this tropical semiring by showing that under certain conditions one may define a connection matrix analogous to the difference and q-difference theory of systems of linear equations. We do this by lifting the problem to field from which we derive results via a valuation on the field. We also provide some simple examples demonstrating the theory. The motivation is to provide evidence for the integrability of ultradiscrete difference equations.

1. Introduction

Ultra-discrete equations are of interest because they can be interpreted as cellular automata [6]. They arise from a limiting procedure, known as the ultradiscretisation method [5], applied to difference equations. Of particular interest are the ultra-discrete versions of integrable equations. Integrable equations arise as compatibility conditions of linear systems called Lax pairs [14]. Furthermore, these compatibility conditions arise in the context of monodromy preserving deformations of linear systems. Similarly, for discrete systems, there is also an analogous theory of monodromy studied by Birkhoff [1], in the context of connection matrices. The q-difference analogue of monodromy was studied by Carmichael [2]. A brief account of this theory, and the theory of Schlesinger transformations for such systems was recently given by Borodin [10]. Sakai [7] provided evidence that integrable difference equations may be derived by considering connection preserving deformations of linear difference equations. Evidence has been provided that integrable cellular automata can also arise as compatibility conditions of linear systems [8, 9] over the so-called max-plus semiring.

The linear theory behind tropical semirings is relatively new. The crux of the theory relies on lifting a given linear system to a field coupled with a valuation [3, 4]. One novel approach involves lifting to the algebraic closure of the set of algebraic functions in one variable \overline{ℂ[t]} coupled with the valuation bringing an algebraic function to the order of its pole at 0 [15]. Novel as it is, for our purposes

2 C. ORMEROD

we propose a different lifting. We essentially utilize the same idea as in tropical geometry, but adopt a sense of analysis for the valuation ring. In section 2 we describe the field along with the valuation we will use. In section 3 we will look at two symbolic solutions. In the last section we demonstrate a small application of the theory.

2. The Lift

Let Q be an additively closed subset of the real numbers. We may define the max-plus semiring as the semiring S = Q ∪ {−∞} with binary operations of + and max. This ring has been called a tropical semiring or semifield in the literature [12]. The operation of + is considered to be tropical addition in the semiring, while max is considered to be tropical addition. In this way it is distributive. In the semiring, we consider −∞ to be the additive identity and 0 to be the multiplicative identity. Subtraction is the analog of division, but there is no associated additive inversion. The matrix operations are precisely what one would expect if you replace the operations + and × with their tropical counterparts, thus we define the operations ⊗ and ⊕ on matrices A = (a_{ij}) and B = (b_{ij}) over S to be

A ⊗ B = max_{k}(a_{ik} + b_{kj})

A ⊕ B = max(a_{ij}, b_{ij})

To deal with such an object in an analytic manner, we equip S with the metric defined by

d(x, y) = |e^{x} − e^{y}|

where e^{−∞} is defined to be 0. This endows S with a metric with an equivalent topology on when restricted to the reals, but also considers those sequences divergent to −∞ as convergent. To simplify things when we eventually talk about convergence, we will also assume that Q is a closed subset with respect to the imposed topology from ℝ. We impose upon the matrix space a metric defined to be the

d(A, B) = max_{ij}{d(a_{ij}, b_{ij})}

We will talk about convergence on a certain class of matrices with respect to the above metric. As an algebraic object however, Q may not even make sense when equipped with the operation of multiplication. We will now introduce a field Ω with a subset Ω_{0} ⊂ Ω which is a semiring which is homomorphic to S through a

ULTRADISCRETE CONNECTION MATRICES OVER A TROPICAL SEMIRING 3

valuation, furthermore we will introduce a topology on Ω such that the valuation is continuous into S.

The shortcomings of the semiring are all too obvious. Before we delve into the specifics, we review some of the key concepts from algebra we shall use to derive our results. The first concept is the valuation ring. If R is a ring, we define the valuation μ : R → ℝ ∪ {−∞} to be a mapping satisfying the properties

(1) μ(x) = −∞ if and only if x = 0.

(2) μ(xy) = μ(x) + μ(y)

(3) μ(x + y) ≤ max(μ(x), μ(y)) Any valuation is almost a homomorphism from R into S. If there exists a subset R_{0} ⊂ R containing −∞ that is closed under addition and multiplication such that equality holds in the last property of the valuation, we will say that R_{0} is a homomorphic as a semiring to S under μ. We also note that any valuation induces a metric d : R × R → ℝ^{+} defined as

(1)  d(x, y) = e^{v(x−y)}

It is very simple to show that this is indeed a metric for any valuation μ. Now we need to identify a suitable ring R, and more precisely a suitable field such that we map homomorphically into S.

We consider the ring Φ = ℤ[Q] as the ring of ℤ linear combinations of elements of Q where the group Q is considered to be a group under addition. We will represent any element x ∈ Φ by

x = ∑_{i=0}^{m} n_{i}(x_{i})

As a matter of convention, we will fix a representation of x where x_{0} ≥ x_{1} ≥ … ≥ x_{m} ≥ . . .. Let Ω be the field of fractions of Φ. An element of \frac{x}{y} ∈ Ω will be represented by

\frac{x}{y} = \frac{∑ n_{i}(x_{i})}{∑ m_{i}(y_{i})}

We let P be the mapping on Ω defined by

P (\frac{x}{y}) = max_{i}(x_{i}) − max_{i}(y_{i})

We need to show that this map is a valuation. Firstly let x_{1} = ∑ n_{i}^{1}(x_{i}^{1}), x_{2} = ∑ n_{i}^{2}(x_{i}^{2}), y_{1} = ∑ m_{i}^{1}(y_{i}^{1}) and y_{2} = ∑ m_{i}^{2}(y_{i}^{2}). Let x = x_{1}/x_{2} and y = y_{1}/y_{2}. If x = 0 then the there is no real parts at all so that max_{i}(x_{i}^{1}) − max(x_{i}^{2}) = max(∅) − max(x_{i}^{2}) = −∞. Suppose μ(x_{1}/x_{2}) = −∞, then this imposes max(x_{i}^{2}) = −∞ in which case the set of x_{i}^{1} must not contain any real number, thus x = 0. As for

4 C. ORMEROD

the second property, the only possible reals that may appear in the numerator of xy are {x_{i}^{1} + y_{j}^{1}} but the maximal element of this set is max(x_{i}^{1}) + max(y_{i}^{1}) and similarly for the denominator, it is clear that since ℤ is an integral domain that the ℤ multiplier of this element is not 0 thus equality holds. The last property is also obvious if we fix a representation such that max(x_{i}^{2}) = max(y_{i}^{2}) = 0, here μ(x+y) = μ(\frac{x_{i}^{1}y_{i}^{2}+x_{i}^{2}y_{i}^{1}}{x_{i}^{2}y_{i}^{2}} ) = μ(x_{i}^{1}y_{i}^{2}+x_{i}^{2}y_{i}^{1}) ≤ max(x_{i}^{1}, y_{i}^{1}). So this forms a valuation, so we may define our metric on Ω to be the function

d(x, y) = e^{P (x−y)}

thus we may now talk about the convergence in Ω. We also note that this makes the mapping P : Ω → S continuous with respect to the two metrics. We also extend Ω by taking the closure of Ω under this metric.

Let Ω_{0} be the subset of Ω which is the set of elements \frac{x}{y} = \frac{∑ n_{i}(x_{i})}{∑ m_{i}(y_{i})} where n_{i}, m_{i} ∈ ℕ for all i. The subset Ω_{0} forms a semiring in itself. As a valuation, the restriction P |_{Ω_{0}} satisfies the property that P |_{Ω_{0}}(x + y) = max(P |_{Ω_{0}}(x), P |_{Ω_{0}}(y)) and P |_{Ω_{0}}(xy) = P |_{Ω_{0}}(x) + P |_{Ω_{0}}(y). In this sense we may consider the mapping P |_{Ω_{0}} as a homomorphism of semirings. We identify a “standard” lift an element of S to be the mapping x → 1(x).

In the field of integrable equations, Ω is isomorphic to what is known as the inversible max-plus algebra [11]. Although we do not consider equations over Ω to be of interest directly, we are able to prove the existence of certain solutions and use the linear theory of Ω to perform calculations over S.

3. Linear Difference Equations

Linear difference equations are the subject of the classic works of Birkhoff [1] and Carmichael [2]. We wish to extend the work for systems of linear difference equations over the max-plus semiring by studying the problem over the invertible max-plus algebra. Our overall aim is to develop theory for the system over the max-plus semiring

(2)  Y (X + Q) = A(X) ⊗ Y (X)

where the entries in A is an n × n matrix with entries defined rationally in terms of the operations ⊕ and ⊗ and Q is some fixed real number no equal to 0. The first example of such a system shall be useful later. We consider scalar linear equation over S given by

L(X + Q) = max(0, X) + L(X)

ULTRADISCRETE CONNECTION MATRICES OVER A TROPICAL SEMIRING 5

Here L is of the form (2) where the 1×1 matrix is semiring equivalent to polynomially linear in X. We may explicitly solve this equation in terms of some derivable expansion. The function L is given by the expansion

L(X) = \{ \begin{matrix}max_{n≥0}(nX − \frac{n(n−1)Q}{2}) for Q > 0 \\ max_{n≥0}(−nX + \frac{n(n+1)Q}{2}) for Q < 0 \end{matrix}

It is a relatively simple procedure in 1 variable to convert any degree n polynomial,p(X) over S to the form

p(X) = (n − m)X + ∑_{i=1}^{m} max(0, p_{i} + X)

in which the solution to the system y(X + Q) = p(X) ⊗ y(X) is then given by

y(X) = \frac{(n − m)X(X + Q)}{2Q} + ∑ L(X + p_{i})

Before delving into the various results, we state a few of the useful transformations that shall be used to derive some of the later results.

Lemma 1. Given Y (X) is a solution of (2), then (1) Z(X) = α\frac{(X)}{Q} ⊗ Y (X) is a solution of

Z(X + Q) = (α ⊗ A(X)) ⊗ Z(X)

where X ∈ ℤQ.

(2) Z(X) = β \frac{(X)(X+Q)}{2Q} ⊗ Y (X) is a solution of
Z(X + Q) = (βX ⊗ A(X)) ⊗ Z(X)

where X ∈ ℤQ.

(3) Z(X) = T (X) ⊗ Y (X) is a solution of
Z(X + Q) = T (X + Q) ⊗ A(X) ⊗ T^{−1}(X) ⊗ Z(X)

for all X and invertible matrices T over S.

(4) Z(X) = Y (X) ⊗ −L(X + A) is a solution of

Z(X + Q) = (max(0, A + X) ⊗ A(X)) ⊗ Z(X)

for all X.

These statements are easily verifiable by direct calculation. We note that the set of invertible matrices over S is a very small set. The fourth transformation is useful in transforming any rational matrix over S to one that is rational in X. This

6 C. ORMEROD

stems from the fact that any scalar difference equation is solvable in terms of L functions, thus henceforth we shall assume that any matrix is of the form

(3)  A(X) = A_{0} ⊕ A_{1} ⊗ X ⊕ … ⊕ A_{m} ⊗ mX

where A_{i} are constant matrices over S. We may define two symbolic solutions at ∞ and −∞ defined by the infinite products

Y_{−∞}(X) = A(X − Q) ⊗ A(X − 2Q) ⊗ … (4a) (Y_{∞}(X))^{−1} = … A(X + 2Q) ⊗ A(X + Q) ⊗ A(X) (4b)

We call these the fundamental solutions. Unfortunately, many of the techniques applied in the theory of Birkhoff cannot be applied, since we are dealing with a module over a semiring. For one, the matrix A^{−1}(X) may not be defined for all X, in fact, over a semiring, it is more often than not, not invertible for any X. We can however consider the lift of the problem to Ω by considering the problem

(5)  Y (1(X).1(Q)) = (A_{0} + A_{1}1(X) + … + A_{n}1(X)^{n})Y (1(X))

Where the A_{i} are constant matrices over Ω. This can be given either by the standard lift, or any other lift to a matrix over Ω_{0}. As a matter of notation, we consider the function F (1(X)) to be a function of the real variable X taking values in Ω depending on X. We now require analogous transforms over Ω.

Lemma 2. Given Y (1(X)) is a solution of (2), then (1) Z(1(X)) = α^{\frac{(X)}{Q}} Y (X) is a solution of

Z(1(X).1(Q)) = αA(1(X))Z(1(X))

for α ∈ Ω and X ∈ ℤQ.

(2) Z(1(X)) = 1(\frac{βX(X+Q)}{2Q})Y (X) is a solution of

Z(1(X).1(Q)) = (βX ⊗ A(1(X)))Z(1(X))

for β ∈ ℤ and X ∈ ℤQ.

(3) Z(1(X)) = T (1(X))Y (1(X)) is a solution of

Z(1(X).1(Q)) = (T (1(X).1(Q))A(1(X))T^{−1}(1(X)))Z(1(X))

for all 𝕏

This gives us the tools required to prove the following theorem

ULTRADISCRETE CONNECTION MATRICES OVER A TROPICAL SEMIRING 7

Theorem 1. Assume that A_{0} and A_{n} are diagonalizable over Ω to D_{0} = diag(d_{i}^{(0)}) and D_{m} = diag(d_{i}^{(m)}). If |P (d_{i}^{(0)}) − P (d_{j}^{(0)})| < Q, then one fundamental solution Y_{−∞} is given by

(6)  Y_{−∞}(1(X)) = Ŷ_{−∞}(X)D0^{\frac{X}{Q}}

and if |P (d_{i}^{(m)}) − P (d_{j}^{(m)})| < Q for all i, j then the fundamental solution Y_{∞} is given by

(7)  Y_{∞}(X) = 1 (\frac{mX(X − Q)}{2Q}) Ŷ_{∞}(X)Dm^{\frac{X}{Q}}

Where Ŷ_{−∞}(0) and Ŷ_{∞}(0) are defined for Q ∈ ℝ and X ∈ ℤQ.

Proof. We split the proof of this statement into two parts. Showing that Y_{−∞} is well defined, and showing that (Y_{∞})^{−1} is well defined.

Using lemma 2, we transform the problem so that we are interested in solutions of

\underline{Y} (1(X)) = z^{\frac{X}{Q}} T Y (X)

where T is a matrix that diagonalizes A_{0}. The function \underline{Y} then satisfies the equation \underline{Y} (1(X)) = \underline{A}(1(X))\underline{Y} (1(X)) where \underline{A} is given by

\underline{A} = zT^{−1}AT = \underline{A}_{m}1(X)^{m} + … + \underline{A}_{1}1(X) + D_{0}

we restrict our attention to solutions of \underline{Y} (X + Q) = \underline{A}(X)\underline{Y} (X). We choose our z very carefully, firstly we let z be the a multiple of product of all the denominators appearing in the \underline{A}_{i}, and secondly embed a multiplier of this product of the form 1(Z) where Z is chosen to be negatively large enough for all the real parts of the entries of \underline{A}_{i} be non-positive. By being particular about our choice of z, we restrict our attention to the case in which we may represent each entry of \underline{A}_{k} in the form \frac{\underline{a}_{ij}^{(k)}}{1(0)} where a_{ij}^{(k)} is in Φ.

We consider the following sequence of matrices over Ω.

\underline{G}_{k} = (\underline{g}_{ij}^{(k)}) = [A(X − Q) … A(X − kQ)] D_{0}^{1−k}

Let ϵ > 0, we will show that there exists an N such that for n_{1}, n_{2} > N we may express G_{n_{1}} and G_{n_{2}} in the form

\underline{G}_{n_{1}} = T_{ij}(ϵ) + O(ϵ/2)
\underline{G}_{n_{2}} = T_{ij}(ϵ) + O(ϵ/2)

Where T_{ij}(ϵ) denotes terms in common with both \underline{G}_{n_{1}} and \underline{G}_{n_{2}} and O(ϵ/2) stands for terms with distance from 0 is less than ϵ/2. Under our particular choice of

8 C. ORMEROD

metric, the terms T_{ij}(ϵ) will cancel out in our subtraction leaving terms that will be small, and via the triangle inequality, the two terms will be a total distance of less than ϵ away. Given the form of the sequence, it is sufficient to consider the case where X sufficiently large and negative since we have the following relation

\underline{G}_{k}(1(X)) = \underline{A}(1(X − Q)) … \underline{A}(1(X − mQ))G_{k−m}(1(X − mQ))

With this freedom we choose a large and negative X. We write

\underline{G}_{k}(1(X)) = ∑ \underline{G}_{k}^{(j)}1(X)^{j}

We may expand \underline{G}_{k} in terms of D_{0} and the \underline{A}_{i}’s to obtain explicit expressions for the \underline{G}_{k}^{(l)}’s over Ω. It is easy to see the expression for \underline{G}_{k}^{(1)} is given by

\underline{G}_{k}^{(1)} = [\underline{A}_{1}D_{0}^{k−2}(−Q) + D_{0}\underline{A}_{1}D_{0}^{(k−3)}1.(−2Q) + … + D_{0}^{k−2}\underline{A}_{1}1(−kQ)]D_{0}^{1−k}

This gives an expression for our chosen representatives of (\underline{G}_{k}^{(1)})_{ij} as

(\underline{G}_{k}^{(1)})_{ij} = \underline{a}_{ij}^{(1)}1(−Q) (1(0) + \frac{d_{i}^{(0)}}{d_{j}^{(0)}} 1(−Q) + … + (\frac{d_{i}^{(0)}}{d_{j}^{(0)}} 1(−Q))^{k}) d_{i}^{(0)}

If however, the P (\frac{d_{i}^{(0)}}{d_{j}^{(0)}} ) = P (d_{i}^{(0)}) − P (d_{j}^{(0)}) < Q then the contribution attributed larger terms added for k large are smaller and smaller, and so we may pick a N_{1} large enough such that the terms (\frac{d_{i}^{(0)}}{d_{j}^{(0)}} )^{k} 1(X) are less than ϵ/2 away from −∞ for all i, j. This then splits up \underline{G}_{k}^{(1)} into parts of T_{ij}(ϵ) and smaller terms for k > N_{1}. Since we have reduced the case to one in which all entries of the \underline{A}_{i} are nonpositive, and since the \underline{G}_{k}^{(l)} are composed of elements of the entries of \underline{A}_{i}, we need only look at the coefficient matrices such that e^{lX} > ϵ/2, thus we may pick an L such that this is true for l < L. For l < L we may write explicitly the matrices \underline{G}_{k}^{(l)} in terms of the \underline{A}_{i}’s and D_{0}.

\underline{G}_{k}^{(l)} = ((\underline{A}_{l}D_{0}^{k−2}1(−lQ) + … + D_{0}^{k−2}\underline{A}_{l}1(−klQ))+

(\underline{A}_{l−1}\underline{A}_{1}D_{0}^{k−3}1(−(l + 2)Q) + … + D_{0}^{k−2}\underline{A}_{l−1}\underline{A}_{l−1}.1(−\frac{kl(l + 1)}{2}Q)) +

⋮

+ (\underline{A}_{1}^{l}D_{0}(k − l − 2)1(−\frac{l(l − 1)}{2}Q) + … + D_{0}^{k−l−1}\underline{A}_{1}^{l}1(−\frac{l(2k − l)}{2}Q))) D_{0}^{1−k}

where each bracket is any combination, \underline{A}_{t_{1}}, … \underline{A}_{t_{h}}, of the \underline{A}_{i}’s in a way such that t_{1}+…+t_{h} = k. We also note that although we have written \underline{G}_{k}^{(l)} in this manner, the first term does not appear for l > m. We introduce the set ℧_{k}^{l} = {t = (t_{1}, …, t_{k}) such that ∑ t_{i} = l, 0 ≤ t_{i} ≤ m}. This allows us to write

\underline{G}_{k}^{(1)} = ( ∑_{t∈℧_{k}^{l}} \underline{A}_{t_{1}}1(−t_{1}Q)\underline{A}_{t_{1}}1(−2t_{2}Q) … \underline{A}_{t_{k}}1(−kt_{k}Q)) D_{0}^{1−k} = ( ∑_{t∈℧_{k}^{l}} \underline{A}_{t}) D_{0}^{1−k}

Where for convenience \underline{A}_{0} = D_{0}. Furthermore we may express each component of A_{t} at the i, j-th component as

(\underline{A}_{t})_{ij} = ∑_{r} \underline{a}_{ir_{1}}^{t_{1}}1(−t_{1}Q) \underline{a}_{r_{1}r_{2}}^{t_{2}}1(−2t_{2}Q) … \underline{a}_{r_{k}j}^{t_{k}}(d_{j}^{0})^{1−k}

For k > l, any t ∈ ℧_{k+1}^{l} must be obtained through some insertion of a 0 at some place in the sequence t = (t_{0}, …, t_{k}). It is then clear that \underline{A}_{t} = \underline{A}_{(t,0)}, thus all the parts of G_{k}^{(l)} appear in the parts of G_{k+1}^{(l)}. We need to show that through insertion of a 0 anywhere other than the end, decreases the magnitude of the element in some way. Suppose s ∈ ℧ is obtained via the addition of some 0 anywhere but the end, say the (h + 1)-th place, then the effect is shifting nonzero entries of t further down meaning the

(\underline{A_{s}}) = (\underline{A}_{t_{1}}1(−t_{1}Q) … \underline{A}_{t_{h}}1(−ht_{h}Q)D_{0} ×
\underline{A}_{t_{h+1}}1(−(h + 2)t_{h+1}Q) … \underline{A}_{t_{k}}1(−(k + 1)t_{k}Q))D_{0}^{−k}

The effect of this on this addition is the addition of terms at most \frac{d_{r}^{(0)}}{d_{j}^{(0)}} 1(−Q) times smaller than those terms that do come from \underline{G}_{k}^{(l)}, in fact we have a lower bound for how much in magnitude it has decreased by, this is min_{i,j}(|P (d_{i}^{(0)}) − P (d_{j}^{(0)}) − Q|) which is some finite non-identity element. This means the only parts of \underline{G}_{k+1}^{(l)} that are not smaller by some fixed amount are those part that come from \underline{G}_{k}^{(l)}. This means we may find an N_{l} such that any additional parts are less than ϵ/2 away from −∞ in all entries of \underline{G}_{k}^{(l)}1(lX). Now we take N = max(N_{l}) which is an integer large enough so that \underline{G}_{k} = T_{ij} + O(ϵ/2). The \underline{G}_{k} then represents a cauchy convergent sequence in Ω. By relating a shift in k to the way in which we shift X, we let k = \frac{X}{Q}, thus we have the solution for \underline{Y}_{−∞}(1(X)) = lim_{k→∞} \underline{G}_{k}(1(X)) = \underline{G}(1(X)) and Y (1(X)) = z^{\frac{X}{Q}} T^{−1}\underline{Y}, but as an infinite product, the series given by (4a) is given by T^{−1}z^{− \frac{X}{Q}} \underline{G}(1(X))T which we will call Y_{−∞}(1(X)).

Let us now shift our attention to the other direction. In a similar manner, we are interested in solutions of

\overline{Y} (1(X)) = z^{\frac{X}{Q}} 1 (\frac{−mX(X − Q)}{2Q}) SY (X)

where S diagonalizes A_{m}. Here \overline{Y} satisfies \overline{Y} (1(X)1(Q)) = \overline{A}(1(X))\overline{Y} (1(X)) where

\overline{A}(X) = S^{−1}A(X)S1(−mX) = z\overline{A}_{0}1(−mX) + … + \overline{A}_{m−1}1(−X) + D_{m}

By letting z be an element such that \overline{A} is in the image of ϕ under the same inclusion as before. By such a choice of z, we have the entries of \overline{A} be in the image of Φ under the inclusion. We

\overline{G}_{k}(1(X)) = D_{m}^{−k}[\overline{A}(1(X + kQ)) … \overline{A}(1(X))]

we denote the elements of these matrices \overline{g}_{ij}^{k}. We wish to choose an N_{ij} such that d(\overline{g}_{ij}^{m}, \overline{g}_{ij}^{M}) < ϵ for m, M > N_{ij}. We express \overline{G}_{k} in the following way

\overline{G}_{k} = \overline{G}_{k}^{(0)} + \overline{G}_{k}^{(−1)}1(−X) + … + \overline{G}_{k}^{(−km)}1.(−kmX)

The \overline{G}_{k}^{(0)} term is the identity matrix, thus we need only consider non-positive multiples of X, furthermore, due to our choice in z, we need only need to consider l < L for some in which e^{−lX} < ϵ/2 for l > L. We start with the −1 matrix given by

\overline{G}_{k}^{(−1)} = D_{m}^{−k}[\overline{A}_{1}D_{m}^{k−1} + … + D_{m}^{k−1}\overline{A}_{1}1(−kQ)]

We may express the entries in \overline{G}_{k}^{(−1)} by

(\overline{G}_{k}^{(−1)})_{ij} = \frac{\overline{a}_{ij}^{(m−1)}}{d_{i}^{(m)}} (1(0) + \frac{d_{j}^{(m)}}{d_{i}^{(m)}} 1(−Q) + … + (\frac{d_{j}^{(m)}}{d_{i}^{(m)}} 1(−Q))^{k})

which should converge only if P (\frac{d_{j}^{(m)}}{d_{i}^{(m)}} ) = P (d_{j}^{(m)}) − P (d_{i}^{(m)}) ≤ Q. In general the expansion can be made as follows,for l ≤ m < k ≠ 0. We expand \overline{G}_{k}^{(l)} to get the following

\overline{G}_{k}^{(l)}(1(X)) = (D_{m}^{−1}(\overline{A}_{m−l} + … + D_{m}^{−k}\overline{A}_{m−l}D_{m}^{k−1}1(−kQ))
+(D_{m}^{−2}\overline{A}_{m−l+1}\overline{A}_{m−1}1(−3Q) + … + D_{m}^{−k}\overline{A}_{m−1}\overline{A}_{m−l+1}1((−k − l)Q)
⋮ ⋮
+ (\overline{A}_{m−1}^{l}D_{m}(k − l) + … + D_{m}(k − l)A_{m−1}^{l}))

Where each of the brackets contains all possible multiplications of \overline{A}_{m−j_{r}} and D_{m}’s such that ∑ j_{r} = l. Again, the first few terms written may not appear if l > m. Let ℸ_{k}^{l} be the set {t = (t_{0}, t_{1}, …, t_{k}) st 0 ≤ t_{i} ≤ m, t_{1} + … + t_{k} − km = l} where l ≤ 0. Then we may write \overline{G}_{k}^{(l)} as

\overline{G}_{k}^{(l)} = D_{m}^{−k} ( ∑_{t∈ℸ_{k}^{l}} \overline{A}_{t_{0}}1((m − t_{0})kQ)\overline{A}_{t_{1}}1((m − t_{1})(k − 1)Q) … \overline{A}_{t_{k}} )
= ( ∑_{t∈ℸ_{k}^{l}} \overline{A}_{t}) D_{m}^{−k}

Where \overline{A}_{m} = D_{m}. Furthermore we may express each component of \overline{A}_{t} as

(\overline{A}_{t})_{ij} = (d_{j}^{(m)})^{−k}(∑_{r} \overline{a}_{ir_{1}}^{t_{0}}1((m − t_{0})kQ)\overline{a}_{r_{1}r_{2}}^{t_{1}}1((m − t_{1})(k − 1)Q) … \overline{a}_{r_{k}j}^{t_{k}})

Suppose s ∈ ℸ_{k+1}^{l} was obtained via the insertion of a m at the beginning of an element t ∈ ℸ_{k}^{l}, then the elements \overline{A}_{t} = \overline{A}_{s}, thus all the parts of G_{k}^{(l)} are contained within the parts of \overline{G}_{k+1}^{(l)}. Furthermore, for k > l any element of ℸ_{k+1}^{l} must be obtained via the addition of an m in some place. Suppose s ∈ ℸ_{k}^{l} is obtained via the addition of some m anywhere but the front, say the (h + 1)-th place, then the effect is shifting the entries not equal to m of t further down meaning \overline{A}_{s} becomes

\overline{A}_{s} = D_{m}^{−k}\overline{A}_{t_{0}}1((m − t_{0})(k + 1)Q) …
… \overline{A}_{t_{h}}1((m − t_{h})(k − h + 1)Q)D_{m}\overline{A}_{t_{h+1}}1((m − t_{h+1})(k − (h + 1))Q) …
… \overline{A}_{t_{k}})

Which has the effect that any extra terms not contained in \overline{G}_{k}^{(l)} in the i, j-th position are at least \frac{d_{r}^{(m)}}{d_{j}^{(m)}} 1(−Q) times smaller. This is by assumption smaller than the multiplicative identity element thus we may choose an N_{l} and thus an N such that all additional terms are less than ϵ/2 away from −∞. Now \overline{G}_{k} has a limit and then one obtains \overline{Y} (1(X)) in the same manner as above.

To end we simply state a simple relation between the k in G_{k} and X to be k = X/Q. When we substitute into the limit, we obtain the fundamental solution Y_{−∞}(1(X)) and (Y_{∞}(1(X)))^{−1} whose inverse exists and where Ŷ_{−∞} is given by the limit matrix of \underline{G} and Ŷ_{∞} is given by the limiting case of \overline{G}. Thus we have the form given above. □

(Remark: It is true that some of these conditions may be relaxed. Special cases where A_{1} and A_{m−1} are −∞ are special cases in which the d_{i}^{(j)}’s can be 2Q apart. It is difficult to obtain explicit or at least easily expressible minimal conditions for which the fundemental forms can be well defined. )

12 C. ORMEROD

The connection matrix is defined as the matrix that satisfies the relation

(8)  Y_{−∞}(1(X)) = Y_{∞}(1(X))P (1(X))

By using the forms of both Y_{−∞}(X) and Y_{∞}(X), we may formulate P (X) as

(9) P (1(X)) = …⊗A(1(X +2Q))⊗A(1(X +Q))⊗A(1(X))⊗A(1(X −Q)))⊗…

from this formulation it is clear that the matrix P (1(X)) is periodic in X, that is to say that P (X + Q) = P (X). Considering the problem over Ω, we introduce the variable T ∈ S and let

Y (1(X)) = Y (1(X), 1(T))
A_{i} = A_{i}(1(T))
P (1(X)) = P (1(X), 1(T))

then we have the following result.

Theorem 2. Suppose P (1(X), 1(T)) = P (1(X), 1(T + Q)), then there exists a matrix B(1(X), 1(T)) such that Y satisfies the following equation

(10)  Y (1(X), 1(T + Q)) = B(1(X), 1(T))Y (1(X), 1(T))

for all X ∈ ℤQ.

Proof. Suppose P (1(X), 1(T)) = P (1(X), 1(T + Q)), then by definition

(Y_{∞}(1(X), 1(T)))^{−1}Y_{−∞}(1(X), 1(T)) = (Y_{∞}(1(X), 1(T +Q)))^{−1}⊗Y_{−∞}(1(X), 1(T +Q))

so by rearranging we see that

B(1(X), 1(T)) = Y_{∞}(1(X), 1(T + Q))(Y_{∞}(1(X), 1(T)))^{−1}
= Y_{−∞}(1(X), 1(T + Q))(Y_{−∞}(1(X), 1(T)))^{−1}

furthermore, by defining B in this way we deduce that

Y_{∞}(1(X), 1(T + Q)) = B(1(X), 1(T))Y_{∞}(1(X), 1(T))
Y_{−∞}(1(X), 1(T + Q)) = B(1(X), 1(T))Y_{−∞}(1(X), 1(T))

Since these are invertible, any solution may be expressed in the form

Y (1(X), 1(T + Q)) = B(1(X), 1(T))Y (1(X), 1(T))
□

ULTRADISCRETE CONNECTION MATRICES OVER A TROPICAL SEMIRING 13

This now shows that the fundamental solutions exist under certain conditions over Ω. This imposes a necessary condition on the system. That is that the evolution in both variables is independent of the order of computation. This imposes the condition that

(11)  A(1(X), 1(T + Q))B(1(X), 1(T)) = B(1(X + Q), 1(T))A(1(X), 1(T))

This is then the compatibility of a connection preserving deformation.

The study of ultradiscrete systems is concerned with linear systems over the maxplus semiring as it is a more natural setting in terms of ultradiscretized variables. An immediate corollary of our main theorem is the following.

Corollary 1. Suppose there exists a linear system of the form (15) over Ω_{0} that maps to (2) through P. If (15) then satisfies the conditions of the theorem, then the solution Y_{−∞}(X) is defined as is (Y_{∞}(X))^{−1} over S. The matrix P (X) is also defined over S.

Proof. We simply rely on the continuity of the mapping P |_{Ω_{0}}. Given any X ∈ S, we know that Y_{−∞}(X) and (Y_{∞}(X))^{−1} are matrices over Ω_{0} due to the closure of the Ω_{0} under matrix operations. This means we may obtain Y_{−∞} and (Y_{∞}) via P as well as the connection matrix. □

If the additional condition that B(1(X), 1(T)) is a matrix over Ω_{0}, then this translates to the system Y (X) over S to be also considered to be some system over T as well with Y (X, T) satisfying the linear condition

Y (X + Q) = B(X, T) ⊗ Y (X, T)

This imposes a condition on S. That is the through the mapping of (11) we obtain the condition that

(12)  A(X, T + Q) ⊗ B(X, T) = B(X + Q, T) ⊗ A(X, T)

This is then a necessary condition of a connection preserving deformation of linear systems over the max-plus semiring. Here we consider that if any system were derived as such a compatibility condition over S, then the system is considered integrable.

14 C. ORMEROD

4. Application : Ultradiscrete Riccati Equation

This section is devoted to giving an example of a projection preserving transformation may be used to generalize the condition for which we may define fundamental solutions. We begin with the discrete Riccati equation We consider the discrete Riccati equation with rational coefficients given by

(13)  x(qt) = \frac{ax + b}{cx + d}

A suitable ultradiscretization of this equation is given by

(14)  X(T + Q) = max(A(T) + X(T), B(T)) − (C(T) + X(T), D(T))

By letting X(T) = U(T)−V (T) we may write this as U(T +Q)−V (T) = max(A+ U(T), B + V (T)) − max(C + U(T), D + V (T)). From this we derive the following equivalent linear difference equation

(15)  Y (T + Q) = ( \begin{matrix}A & B \\ C & D \end{matrix} ) ⊗ Y (T)

Without loss of generality, we may assume that A, B, C and D are all polynomial in T. Let m be the maximal degree of A, B, C and D, then we may write

A = A_{0} ⊕ A_{1} ⊗ T ⊕ … ⊕ A_{m} ⊗ mT
B = B_{0} ⊕ B_{1} ⊗ T ⊕ … ⊕ B_{m} ⊗ mT
C = C_{0} ⊕ C_{1} ⊗ T ⊕ … ⊕ C_{m} ⊗ mT
D = D_{0} ⊕ D_{1} ⊗ T ⊕ … ⊕ D_{m} ⊗ mT

This now puts (14) in the form of (2). By setting

R_{i} = ( \begin{matrix}A_{i} & B_{i} \\ C_{i} & D_{i} \end{matrix} )

By letting R(T) = R_{0} ⊕ R_{1} ⊗ T ⊕ … ⊕ R_{m} ⊗ mT. We write this equation in the form

(16)  Y (T + Q) = R(T) ⊗ Y (T)

In order to show that the fundamental solution Y_{−∞} exists, we have a condition on the coefficients A_{0}, B_{0}, C_{0} and D_{0}. In order to show that Y_{∞} exists we must assume some condition on A_{m}, B_{m}, C_{m} and D_{m}.

Theorem 3. Suppose R_{0} and R_{m} are upper or lower triangular matrices. If |A_{0} − D_{0}| < Q and |A_{m} − D_{m}| < Q then the connection matrix exists.

ULTRADISCRETE CONNECTION MATRICES OVER A TROPICAL SEMIRING 15

Proof. The standard lift of the triangular matrix is diagonalizable with eigenvalues corresponding to the diagonal elements. The result comes from a direct application of the theorem where the diagonal elements are 1(A_{i}) and 1(D_{i}) for i = 1, m. The requirement is then obtained as a direct application of the main theorems requirement. □

Theorem 4. Suppose A_{i} = D_{i} ≠ B_{i}, C_{i} for i = 1, m, then the connection matrix exists.

Proof. We apply the standard lift to get the matrix R_{i} over Ω_{0} which is

R_{i} = (\begin{matrix}1(A_{i}) & 1(B_{i}) \\ 1(C_{i}) & 1(A_{i}) \end{matrix})

whose eigenvalues may be calculated to be

λ = 1(A_{i}) ± 1 (\frac{B_{i} + C_{i}}{2} )

which both have the same valuation. □

By using the theory of projection preserving transformations we may extend our results

Theorem 5. A sufficient condition for the connection matrix to exist over the max-plus semiring is that B_{i} + C_{i} > A_{i} + D_{i} and B_{i} + C_{i} > 2 max(A_{i}, D_{i}) − Q for i = 0, m.

Proof. The first case is where B_{i} + C_{i} ≥ 2 max(A_{i}, D_{i}), both conditions in this theorem are met. We let R_{i} be the matrix over Ω given by

R′_{i} = (\begin{matrix}1(A_{i}) & 1(B_{i}) \\ 1(C_{i}) & 1(D_{i}) \end{matrix})

From this we pick an E_{i} such that E_{i} such that the matrix R′_{i} ⊕E_{i} is diagonalizable. We let E_{i} be

E_{i} = (\begin{matrix}−∞ & 1(A_{i} + D_{i} − C_{i}) + 1(\frac{B_{i}−C_{i}}{2} )(1(A_{i}) + 1(D_{i})) \\ −∞ & −∞ \end{matrix})

Since B_{i} + C_{i} ≥ 2 max(A_{i}, D_{i}) it can easily verified that the map R_{i} → R_{i} ⊕ E_{i} is a projection preserving transformations. Furthermore that we can directly compute the eigenvalues, these are

d_{1}^{(i)} = −1(\frac{B_{i}}{2} + \frac{C_{i}}{2} )
d_{2}^{(i)} = 1(A_{i}) + 1(D_{i}) + 1(\frac{B_{i}}{2} + \frac{C_{i}}{2} )

16 C. ORMEROD

Since \frac{B_{i}}{2} + \frac{C_{i}}{2} ≥ max(A_{i}, D_{i}), the leading parts are the same, this shows P (d_{1}^{(i)}) − P (d_{2}^{(2)}) = 0 < Q. This is precisely our first condition.

The second case is where A_{i} + D_{i} ≤ B_{i} + C_{i} ≤ 2 max(A_{i}, D_{i}). Let E_{i} be

E_{i} = (\begin{matrix}−∞ & 1(A_{i} + D_{i} − C_{i}) + 1(2B_{i} + C_{i})/(1(A_{i}) + 1(D_{i}))^{2} \\ −∞ & −∞ \end{matrix})

Again, this can be easily verified. Furthermore we may compute the eigenvalues directly to be

d_{1}^{(i)} = \frac{−1(B_{i} + C_{i})}{1(A_{i}) + 1(D_{i})}
d_{2}^{(i)} = \frac{(1(A_{i}) + 1(D_{i}))^{2} + 1(B_{i} + C_{i})}{1(A_{i}) + 1(D_{i})}

now P (d_{1}^{(i)}/d_{2}^{(i)}) = P (1(B_{i} + C_{i})) − P ((1(A_{i}) + 1(D_{i}))^{2} + 1(B_{i} + C_{i}) < Q is the requirement. We write this as B_{i} + C_{i} − max(2A_{i}, 2D_{i}, B_{i} + C_{i}) < Q. But due to the conditions, B_{i} + C_{i} − 2 max(A_{i}, D_{i}) < Q is the requirement for the connection matrix to exist. □

It is possible to diagonalize over Ω under some conditions, in which case it is possible to take arbitrary powers of matrices. There are many choices for the field that we may use to diagonalize and thus find powers of matrices over S. For example, the p-adics coupled with the p-adic valuation is a valuation ring, but with this construction we require Q to be the integers, furthermore the field is not algebraically closed. One other choice is the algebraic closure of the algebraic functions over ℂ in one variable with a valuation defined to be the order of the pole or root of the function at 0. This however restricts ones choice to something isomorphic to the rationals, but is by definition algebraically closed. Ideally, one wants a valuation ring with valuation whose image is all the reals and algebraically closed with a homomorphic sub-semiring homomorphic to the max-plus algebra through that valuation that is also metric space such that the valuation is continuous. But this author thinks it is a lot to ask of a field.

5. Conclusion

This work leads us to the derivation of integrable ultradiscrete systems as compatibility conditions of linear difference equations with rational coefficients in the invertible max-plus algebra and the max-plus semiring. The methods employed to find powers of matrices over a tropical semiring are quite general are possibly require further investigation.

References

[1] Birkhoff, G.D. : General theory of linear difference equations, Trans. Amer. Math. Soc. 12 (2) (1911), 243–284

[2] Carmichael, R.D. : The general theory of linear q-difference equations, Amer. J. Math. 34 (2) (1912), 147–168

[3] Cohen, G., Gaubert,S. and Quadrat,J.-P. : Max-plus algebra and system theory: Where we are and where to go now.Annual Reviews in Control 23 1999, 207219

[4] Cohen, G., Gaubert,S. and Quadrat,J.-P. : Duality and separation theorems in idempotent semimodules. Linear Algebra Appl. 379 (2004), 395–422.

[5] Tokihiro, T., Takahashi, D., Matsukidaira,J., and Satsuma,J.: From Soliton Equations to Integrable Cellular Automata through a Limiting Procedure, Phys. Rev. Lett. 76 (18) (1996), 3247-3250

[6] Grammaticos, B. and Ramani, A. : Painlevé equations and cellular automata: Symmetries and integrability of difference equations(Canterbury 1996) London Math. Soc. Lecture Note Ser. 255 (1999), 325–333

[7] Jimbo, M., Sakai, H. : A q-analog of the sixth Painlevé equation Lett. Math. Phys. 38 (2) (1996), 145–154

[8] Joshi, N., Nijhoff,F., Ormerod, C.M. : Lax pairs for ultra-discrete Painleve’ cellular automata J.Physc A: Math.Gen. 37 (44) (2004). L559-L565

[9] Quispel, G. R. W. and Capel, H. W., Scully, J.:Piecewise-linear soliton equations and piecewiselinear integrable maps, J. Phys. A 34 (11) (2001),2491–2503

[10] Borodin, A. : Isomonodromy transformations of Linear systems of Difference eqautions Preprints math.CA/0209144 (2002)

[11] Ochiai, T., Nacher, J. : Inversible Max-Plus Algebras and Integrable systems, Journal of Mathematical Physics 46(2005)

[12] Speyer, D. and Sturmfels, B. : Tropical Mathematics Preprints math.CO/0408099 (2004)

[13] Takhtajan, L. A.:Integrable cellular automata and AKNS hierarchy : Symmetries and integrability of difference equations, CRM Proc. Lecture Notes,

[14] Ablowitz, M. J. and Clarkson, P. A. : Solitons, nonlinear evolution equations and inverse scattering London Mathematical Society Lecture Note Series 149(1991)

[15] Richter-Gebert, J. ,Sturmfels, B. and Theobald,T. : First Steps in Tropical Geometry Preprints math.CO/0306366 (2003)

School of Mathematics and Statistics F07, University of Sydney, NSW2006 Sydney, Australia

   E-mail address: chriso@maths.usyd.edu.au