The general theory of linear difference equations over the invertible max-plus algebra

Nalini Joshi (nalini@maths.usyd.edu.au) and Chris Ormerod

(chriso@maths.usyd.edu.au)

School of Mathematics and Statistics F07,The University of Sydney

Abstract. We present the mathematical theory underlying systems of linear difference equations over the invertible max-plus algebra. The result provides an analogue of isomonodromy theory for ultradiscrete Painlevé equations, which are extended cellular automata, and provide evidence for their integrability. Our theory is analogous to that developed by Birkhoff and his school for q-difference linear equations but stands independently of the latter. As an example we derive linear problems in this algebra for ultradiscrete versions of the symmetric P_{IV} equation and show how it acts as the isomonodromic deformation of the linear system.

Keywords: Integrable systems, cellular automata, monodromy, ultradiscrete, Painlevé, Tropical

Mathematical Subject Classification(2000): 39A20,14H70,16Y60

1. Introduction

The discrete Painlevé equations are integrable in the sense that they can be solved through associated systems of linear equations. For difference equations the linear theory necessary for solvability was developed by Birkhoff [1] and his school and improved by Ramis and his school [2]. The purpose of our paper is to provide such a theory for linear ultradiscrete equations, which can be regarded as equations posed over the invertible max-plus algebra.

The classical results of Birkhoff were extended for systems of qdifference equations in [3, 4, 5]. Ramis and his school improved these results for many cases and developed analytic Galois theory for qdifference equations [2].

The discrete Painlevé equations have been an area of intense recent research [6]. Jimbo and Sakai [7] were the first to apply Birkhoffs theory to a q-difference version of the sixth Painlevé equation. In this paper, we consider ultradiscrete versions of such discrete Painlevé equations.

Ultradiscrete equations are obtained through a limiting process introduced in [8]. The ultradiscrete Painlevé equations can be interpreted as integrable cellular automata [6, 9, 10]. Ultradiscrete analogues of integrable equations have been shown to have Lax Pairs over the maxplus semiring [11] and [12]. We consider general systems of linear differ-

\begin{matrix}c \\ ◯ \end{matrix} 2005 Kluwer Academic Publishers. Printed in the Netherlands.

ence equations over the invertible max-plus algebra. In this paper, we announce results on the direct monodromy problem, i.e. the existence of fundamental solutions and the connection matrix relating the solutions defined at positive and negative infinity. We also give Lax pairs for the ultradiscrete symmetric P_{IV} equation and show how our results apply to this case.

2. Difference equations

For properties of the max-plus algebra and invertible max-plus algebra, refer to [13, 14]. Let Ω be the invertible max-plus algebra and Ω_{0} be the subset of Ω that is homomorphic to the max-plus algebra. Our focus lies in matrix equations of the form

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

where the entries in A are defined in terms of the operations ⊕ and ⊗. We will throughout this paper assume that A(X) = (a_{ij}(X)) is of the form

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

where the A_{k} = (a_{ij}^{k}) matrices are constant entries in Ω_{0}.

We remind the reader that multiplication for matrices over the maxplus algebra is defined as

[A ⊗ B]_{i,j} = max(A_{ik} + B_{kj})
[A ⊕ B]_{i,j} = max(A_{ij}, B_{i,j})

We also assume throughout this paper that Q is a fixed real number and Q > 0. The theory for Q < 0 is analogous. We equip the matrix max-plus algebra with the metric

d(A, B) = sup |e^{a_{ij}} − e^{b_{ij}}|  (3)

where we define e^{−∞} = 0.

In order to define convergence in the invertible max-plus algebra we give a slightly different construction to that of [13] of the same object. Let Z be the set Z = (Q⊕ℤ_{2})∪{−∞} where ℤ_{2} = {0, η} and Q is some additively closed subset of ℝ. We order elements with respect to the part in ℝ and −∞ is minimal. Let Φ = ∐_{n∈ℕ} Z^{n} under the equivalence generated by the following relations

(x_{1}, …, x_{i}, x_{i+1}, …, x_{n}) ∼ (x_{1}, …, x_{i+1}, x_{i}, …, x_{n})
(x_{1}, …, x_{n}, −∞) ∼ (x_{1}, …, x_{n})
(x_{1}, …, x_{n}, x_{n} + η) ∼ (x_{1}, …, x_{n−1}, −∞)

We make ϕ a ring by defining operations ⊗ and ⊕

(x_{1}, …, x_{n}) ⊗ (y_{1}, …, y_{m}) = (x_{i} + y_{j})_{i,j}
(x_{1}, …, x_{n}) ⊕ (y_{1}, …, y_{m}) = (x_{1}, …, x_{n}, y_{1}, …, y_{n})

We consider the action of Z on Φ by ⊗ on Z^{1} ⊂ Φ. Let Θ = (Φ × (Φ \ {−∞}))/Z where the equivalence class is such that two elements are equivalent if they differ by the pointwise action of Z. We denote an element of Θ by x = (x)_{0} + (0, (x)_{1}, …, (x)_{n}) − (0, (x)_{−1}, …, (x)_{−m}), and as a matter of convenience we define x_{i} = −∞ for −m < i < n. For x ∈ Φ, (x)_{i} ∈ Z so we distinguish the parts of (x)_{i} by letting (x)_{i} = (x)_{i}^{∗} + (x)_{i}^{+} where (x)_{i}^{∗} ∈ ℝ and (x)_{i}^{+} ∈ ℤ_{2}. If (x)_{i} = −∞, then (x)_{i}^{∗} = −∞ and (x)_{i}^{+} = 0. For x, y ∈ Θ, we define the metric

d(x, y) = sup_{k} |μ((x)_{k}^{+})e^{(x)_{0}^{∗}+(x)_{k}^{∗}} − μ((y)_{k}^{+})e^{(y)_{0}^{∗}+(y)_{k}^{∗}}|  (4)

where we define e^{−∞} = 0. Let x = (x_{1}, x_{2}), y = (y_{1}, y_{2}) ∈ Θ, then we define an equivalence relation such that x ≈ y if and only if x_{1} + y_{2} = x_{2} + y_{1}. The invertible max-plus algebra is defined as Ω = Θ/ ≈. This equivalence relation induces a map ϕ : Θ → Ω. Continuity of multi-

Φ/ ≈ Φ  Θ Ω = Θ/ ≈  \overline{Θ} \overline{Ω} = \overline{Θ}/ ≈ ii  ϕ ϕ′  ϕ′′ ii

Figure 1. This is commutative diagram showing the relations between Θ and Ω. i is the inclusion mapping, and ϕ and ϕ′ are mappings for Θ to the equivalence classes of Θ. \overline{Θ} denotes the closure of Θ with respect to the metric above.

plication and addition with respect to this metric makes this diagram commute. Due to the continuity of ⊕ and ⊗, addition and multiplication makes sense on \overline{Θ} and so then does the equivalence relation. When considering convergence in Ω, it shall be in the sense that a pullback of ϕ is convergent in \overline{Θ} which in turn maps to \overline{Ω}. Let Ω_{0} = \{[x] ∈ Ω such that (x)_{i}^{+} = 0 for all i}. This subset is closed under multiplication and addition, and the mapping P : Ω_{0} → R, P ([x]) = (x)_{0}^{∗} is a continuous mapping from Ω_{0} to the max-plus algebra with respect to (3) and (4).For more details see [18].

2.1. Fundamental Solutions

It is easy to see that the linear system described by (1) has two symbolic solutions given by the infinite products

Y_{−∞}(X) = A(X − Q) ⊗ A(X − 2Q) ⊗ …  (5)
(Y_{∞}(X))^{−1} = … ⊗ A(X + Q) ⊗ A(X)  (6)

The main result of this paper is that under the metric defined by (4), these expressions converge. If all coefficients are elements of Ω_{0} then it is interesting to note that that since Ω_{0} is closed under multiplication and addition, these two expressions can also be mapped to the max-plus algebra.

We will require that given (2), A_{0} and A_{m} are semisimple over Ω. Furthermore, we require that A(X) is invertible for all X ∈ ℤQ.

THEOREM 1. Given that A_{0} and A_{m} are diagonalizable to D_{0} = diag(d_{i}^{(0)}) and D_{m} = diag(d_{i}^{(m)}), if (d_{i}^{(0)} − d_{j}^{(0)})_{0} < Q for all i, j, then one fundamental solution Y_{−∞} is given by

Y_{−∞}(X) = Ŷ_{−∞}(X) ⊗ \frac{XD_{−∞}}{Q}  (7)

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

Y_{∞}(X) = \frac{nX(X − Q)}{2Q} ⊗ Ŷ_{∞}(X) ⊗ \frac{XD_{∞}}{Q}  (8)

Where Ŷ_{−∞} and Ŷ_{∞} are defined for all X ∈ ℤQ.

These two fundamental solutions provide the basis for what we call monodromy. We note that due to the form of equations (7) and (8), we must restrict our X to multiples of Q, otherwise \frac{XD}{Q} does not make sense. These are not necessary conditions, but are sufficient. It is, however, true that a more complicated but more general set of conditions can be stated, but in the interests of simplicity, this shall be disclosed in a separate paper. It is interesting to note that this set of conditions, and their more complicated equivalent conditions are different from the set of ultradiscrete interpretations of the conditions of [3].

2.2. Monodromy Preserving Deformation

We wish to construct the monodromy of an equation. The concept of the monodromy of difference equations come mainly from the classic works of [1]. The monodromy is expressed in terms of the above fundamental solutions. In the theory of monodromy preserving deformations, one introduces a parameter t, and require that the monodromy is then pseudo-constant with respect to t.

DEFINITION 1. For a given system in the form in (1), we define the monodromy matrix or connection matrix to be defined by the relation

(Y_{∞})^{−1} ⊗ Y_{−∞}(X) = P (X)  (9)

We define this to be the monodromy in the max-plus algebra that may also be considered an element of the invertible max-plus algebra. It is clear that P (X + Q) = P (X). By letting A(X) = A(X, T) where the matrix coefficients, A_{i} are rational functions of t. We may write P (X) = P (X, T). An isomonodromy condition is that P is pseudoconstant in t, that is to say that P (X, T) = P (X, T +Q). If this is true, then we infer on their projections to the invertible max-plus algebra that

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

We allow the last combination to be the matrix B(X, T). If we assume that Y_{∞}(X, T) and Y_{−∞}(X, T) are a basis for solutions, then B(X, T) is a matrix that determines the evolution of the solutions in T. We obtain a difference equation in T given by

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

THEOREM 2. Given a linear system such as (1), and there exists a B(X, T) such that (10) determines evolution in time, then the matrix P (X, T) is pseudo-constant in time.

The combination of (1) and (10) gives a compatibility condition. This compatibility condition can be written

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

and thus we may determine the isomonodromy condition to be

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

The next section deals with consequences of the monodromy preserving systems of this form.

THEOREM 3. Suppose Y_{−∞}(X) and Y_{∞}(X) are two matrix functions such that

Y_{−∞}(X) = Y_{∞} ⊗ P (X)

where P (X) = P (X + Q), then there is a matrix A(X) such that

Y_{−∞}(X + Q) = A(X) ⊗ Y_{−∞}(X), Y_{∞}(X + Q) = A(X) ⊗ Y_{∞}(X),

3. Isomonodromy

In this section we look at a system in which the isomonodromy condition leads to a known ultradiscrete Painlevé equation. This can be viewed as an extension of the q-difference equations of [10, 6] or [7], but the systems are of interest in their own respect.

3.1. Derivation of ud-P_{IV}

A linear system required for q-P_{IV} can be deduced from [17]. We choose a different linear system that satisfies the conditions of Theorem (1). We are now interested in the system A(X, T) = A_{0}(T) ⊕ A_{1}(T) ⊗ X ⊕ A_{2} ⊗ 2X where A_{0}(T) and A_{1}(T) are given by

A(X, T) = ( \begin{matrix}(0, 2X) & W_{0}(T) − T + \frac{C_{0}}{3} & −∞ \\ −∞ & (0, 2X) & W_{1}(T) − T + \frac{C_{1}}{3} \\ W_{2}(T) − T + \frac{C_{2}}{3} & −∞ & (0, 2X) \end{matrix} )

For simplicity, we start with identity matrices A_{0} and A_{2}, where the all diagonal entries are 0. This means d_{i}^{(0)} − d_{j}^{(0)} = d_{i}^{(2)} − d_{j}^{(2)} = 0 for all i and j thus the matrix A satisfies the conditions. We note that all the entries in A can be restricted Ω_{0}. We also obtain a matrix B describing the evolution in T, this is given by

B(T) = ( \begin{matrix}−∞ & B_{20} − \frac{2}{3}C_{2} & −∞ \\ −∞ & −∞ & B_{01} − \frac{2}{3}C_{0} \\ B_{12} − \frac{2}{3}C_{1} & −∞ & −∞ \end{matrix} )

Where B_{ij} = (1, C_{i}+W_{i}, C_{i}+C_{j}+W_{i}+W_{j}). By an appropriate choice of variables, we may restrict the entries of the matrix be to be in Ω_{0}. Both A and B can be regarded as matrices over Ω_{0} and so the compatibility condition defined by (12) may be considered over the max-plus algebra. By considering the projection of A and B into the max-plus algebra, we obtain a compatibility condition. By letting Q = \frac{2}{3}C_{0} + \frac{2}{3}C_{1} + \frac{2}{3}C_{2} and looking at the the compatibility condition at the (1, 3) entry we obtain

W_{0}(T + Q) = C_{0} + C_{1} + W_{1} + max(0, C_{2} + W_{2}, C_{0} + C_{2} + W_{0} + W_{2})
− max(0, C_{0} + W_{0}, C_{0} + C_{1} + W_{0} + W_{1})

The entry (2, 1) gives us

W_{1}(T + Q) = C_{1} + C_{2} + W_{2} + max(0, C_{0} + W_{0}, C_{0} + C_{1} + W_{0} + W_{1})
− max(0, C_{1} + W_{1}, C_{1} + C_{2} + W_{1} + W_{2})

and the (3, 2) entry gives us

W_{2}(T + Q) = C_{0} + C_{2} + W_{2} + max(0, C_{1} + W_{1}, C_{1} + C_{2} + W_{1} + W_{2})
− max(0, C_{2} + W_{2}, C_{0} + C_{2} + W_{0} + W_{2})

Other entries give identities. We identify the system of difference equations above with the symmetric form of ud-P_{IV}. We consider this a discrete dynamical system over a time variable T̄ = \frac{3}{2}T with difference constant Q̄ = \frac{3}{2}Q, we may normalize so that C_{0} + C_{1} + C_{2} = Q̄. Under this normalization system above is equivalent to the ultradiscretized symmetric form of ud-P_{IV} given by

q − P_{IV} : \{ \begin{matrix}f_{0}(qt) & = & a_{0}a_{1}f_{1}(t)\frac{1+a_{2}f_{2}(t)+a_{2}a_{0}f_{2}(t)f_{0}(t)}{1+a_{0}f_{0}(t)+a_{0}a_{1}f_{0}(t)f_{1}(t)} \\ f_{1}(qt) & = & a_{1}a_{2}f_{2}(t)\frac{1+a_{0}f_{0}(t)+a_{0}a_{1}f_{0}(t)f_{1}(t)}{1+a_{1}f_{1}(t)+a_{1}a_{2}f_{1}(t)f_{2}(t)} \\ f_{2}(qt) & = & a_{1}a_{2}f_{0}(t)\frac{1+a_{1}f_{1}(t)+a_{1}a_{2}f_{1}(t)f_{2}(t)}{1+a_{2}f_{2}(t)+a_{0}a_{2}f_{0}(t)f_{2}(t)} \end{matrix}  (13)

under the normalization a_{0}a_{1}a_{2} = q. This version of q-P_{IV} was given in [15].

4. Conclusion

Many of the Lax-Pairs for q-difference equations yield analogous Lax-Pairs in the ultradiscrete setting. These require an analysis of the isomonodromy problem in the ultradiscrete setting. We announced the theorems required for this analysis. The conditions of our main theorem, Theorem 1, can be relaxed. Details as well as the proofs of the theorems will be given in a subsequent paper. It is also interesting to consider what the set of Schlesinger equations may be in the ultradiscrete setting. Another interesting question is to consider whether the such piece-wise linear systems may be categorized in terms of rational surfaces in a tropical geometric setting similar to that of [16].

5. Acknowledgements

The authors wish to warmly acknowledge the support and warm encouragement of Kenji Kajiwara.

References

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

2. Sauloy, J. : Galois thoery of Fuchsian q-difference equations,Ann. Sci. École Norm. Sup. (4) (36) (2003), No. 6, 925–968

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

4. Le Caine,J. : The linear q-difference equation of the second order, Amer. J. Math. 65 (1943), 585–600

5. Adams, C. R. : The general theory of a class of linear partial q-difference equations, Trans. Amer. Math. Soc. 26 (3) (1924), 283–312

6. Grammaticos, B. and Nijhoff, F. W. and Ramani, A. : Discrete Painlevé equations: The Painlevé property,CRM Ser. Math. Phys.,Springer (1999), 413–516

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

8. 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

9. 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

10. Ramani, A. and Grammaticos, B. and Hietarinta, J. : Discrete versions of the Painlevé equations Phys. Rev. Lett. 67 (14) (1991), 1829–1832 Amer. Math. Soc.9 (1994), 371–375

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

12. 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

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

14. Pin, J. : Tropical semirings, Idempotency (Bristol, 1994), Publ. Newton Inst. 11 (1998), 50–69

15. Kajiwara, K., Noumi, M., Yamada, Y. : A study on the fourth q-Painleve’ equation, Preprint nlin.SI/0012063

16. Sakai, H. : Rational surfaces associated with affine root systems and geometry of the Painleve’ equations, Comm. Math. Phys. 220 (2001), 165–229

17. Kajiwara, K., Noumi, M. , Yamada, Y. : q-Painlevé Systems Arising from q-KP Hierarchy Lett. Math. Phys. 62 (2002) 259–268

18. Joshi, N. , Ormerod, C. : Ultradiscrete Connection Matrices, in preperation

Address for Offprints: The University of Sydney, NSW 2006