February 17, 2026
The tropical semiring is a semiring of extended real numbers, where the operations of ‘max’ and ‘+’ replace the usual addition and multiplication, respectively. Difference equations obtained from the ultradiscrete limit of discrete dynamical systems are described in terms of the tropical semiring. We propose a tropical linearization approach for the stability analysis of difference equations, including those describing ulradiscrete dynamical systems. We show that the fixed point at the tropical origin is asymptotically stable if the maximum eigenvalue of the tropical Jacobian matrix is negative. On the other hand, it is unstable if the maximum eigenvalue of the tropical Jacobian matrix is positive. Since \(0\) is the tropical multiplicative identity, these results are analogous to those in the usual linearization process.
The tropical semiring, or the max-plus algebra, is a semiring of extended real numbers \(\mathbb{R}_{\max}:= \mathbb{R} \cup \{-\infty\}\), where the operations of ‘max’ and ‘+’ replace the usual addition and multiplication, respectively. It has been applied to the analysis of discrete event systems such as manufacturing [1] and railway systems [2]. In these systems, the operation ‘max’ has an advantage in representing the synchronization of events, and the evolution can be expressed as tropical linear difference equations. The tropical semiring is also used to describe ultradiscrete dynamical systems [3], in particular, ultradiscrete integrable systems such as box-ball systems [4]. The tropical discretization, which is a combination of positive-valued discretization and ultradiscrete limiting process, of differential equations also provides ultradiscrete dynamical systems [5]. The asymptotic behaviour of ultradiscrete dynamical systems has been studied for specific cases; for example, the negative feedback model [6] and Sel’kov model [7]. However, to the best of our knowledge, the general case has not been exploited. Ultradiscrete dynamical systems are described using piecewise-linear difference equations; therefore, their stability analysis based on differentiation is not applicable.
As in the cases of usual linear differential or difference equations, tropical linear difference equations can be solved using the spectral theory of matrices. The tropical spectral theory originated in the 1960s [8] and has been developed in many research including the ‘Cyclicity Theorem’ for irreducible matrices [1] and its extension to reducible matrices [9]. These results show that solutions to tropical linear difference equations eventually become periodic, with growth rates given by the eigenvalues.
In this paper, we propose a tropical linearization approach for the stability analysis of difference equations, including non-differentiable ones describing ultradiscrete dynamical systems. Specifically, we focus on the fixed point \(\boldsymbol{\varepsilon}:= (-\infty,\dots,-\infty)^\top\), which is the tropical origin; this is because the shift of the fixed point is not allowed due to the lack of tropical subtraction. We first introduce the tropical linear approximation of a map \(g:\mathbb{R}_{\max}^n \to \mathbb{R}_{\max}\) based on the distance \(d(x,y) := |e^x - e^y|\), resulting the tropical derivative and tropical Jacobian matrix at \(\boldsymbol{\varepsilon}\). Then, we show that the fixed point \(\boldsymbol{\varepsilon}\) is asymptotically stable if the maximum eigenvalue of the tropical Jacobian matrix is negative. On the other hand, it is unstable if the maximum eigenvalue of the tropical Jacobian matrix is positive. Since \(0\) is the tropical multiplicative identity, these results are analogous to those in the usual linearization process.
In the context of tropical functional analysis, tropical integral has been defined as the supremum of a function [10]. On the other hand, tropical differentiation is less studied because the tropical subtraction cannot be defined. Some studies define tropical differentiation algebraically as a linear operation that decreases the degree of a monomial by one [11], [12]. Compared to them, our definition of tropical derivative is analytic and also valid for functions that are not tropical polynomials. The tropical approximation problem has been developed in literature, e.g., in [13], but note that we do not aim at finding a better approximation under some criterion; we just consider the tropical linear approximation that is analytically derived.
The rest of the paper is organized as follows. In Section 2, we introduce basic definitions and results on linear algebra over the tropical semiring. In Section 3, we present the definition of tropical linear approximation and tropical derivative at \(\boldsymbol{\varepsilon}\). In Section 4, we derive the main results of this paper: asymptotic stability and instability of tropical-linearly approximated difference equations. We also present some examples to which our results can be applied. In Section 5, we conclude the paper with some remarks on the fixed point other than \(\boldsymbol{\varepsilon}\).
The tropical semiring, or the max-plus algebra, is a set of numbers \(\mathbb{R}_{\max}:= \mathbb{R} \cup \{-\infty\}\), where the tropical addition \(\oplus\) and multiplication \(\otimes\) are defined as \[\begin{align} a \oplus b:= \max(a,b), \qquad a \otimes b:= a+ b \end{align}\] for \(a,b \in \mathbb{R}_{\max}\). The identities of addition and multiplication are \(\varepsilon:= -\infty\) and \(0\), respectively. In the tropical semiring, the subtraction operation cannot be defined because the inverse element for the addition does not exist, and the tropical division is defined as \(a \oslash b:= a - b\). The tropical power \(a^{\otimes r}\) for \(r \in \mathbb{N}\) is defined as the \(r\)-fold tropical product, i.e., \[\begin{align} a^{\otimes r} = \underbrace{a \otimes a \otimes \cdots \otimes a}_{r\,\text{times}} = ra. \end{align}\] This definition is easily extended to \(r \in \mathbb{R}\) as \(a^{\otimes r} = ra\). For details on the tropical semiring, refer to textbooks [14]–[18].
Let \(\mathbb{R}_{\max}^n\) and \(\mathbb{R}_{\max}^{m \times n }\) denote the sets of all \(n\)-dimensional column vectors and \(m\)-by-\(n\) matrices with entries in \(\mathbb{R}_{\max}\), respectively. For \(A, B \in \mathbb{R}_{\max}^{m \times n}\), the matrix sum \(A \oplus B \in \mathbb{R}_{\max}^{m \times n}\) is defined by \[\begin{align} [A \oplus B]_{ij} = [A]_{ij} \oplus [B]_{ij}, \end{align}\] where \([A]_{ij}\) denotes the \((i,j)\) entry of the matrix \(A\). For \(A \in \mathbb{R}_{\max}^{l \times m}\) and \(B \in \mathbb{R}_{\max}^{m \times n}\), the matrix product \(A \otimes B \in \mathbb{R}_{\max}^{l \times n}\) is defined by \[\begin{align} [A \otimes B]_{ij} = \bigoplus_{k=1}^m [A]_{ik} \otimes [B]_{kj}. \end{align}\] For \(A \in \mathbb{R}_{\max}^{m \times n}\) and \(\alpha \in \mathbb{R}_{\max}\), the scalar multiplication \(\alpha \otimes A \in \mathbb{R}_{\max}^{m \times n}\) is defined by \[\begin{align} [\alpha \otimes A]_{ij} = \alpha \otimes [A]_{ij}. \end{align}\] These operations can be applied to column vectors by regarding them as one-column matrices. The tropical zero vector is \(\boldsymbol{\varepsilon} := (\varepsilon,\dots,\varepsilon)^{\top} \in \mathbb{R}_{\max}^{n}\). For vectors \(\boldsymbol{x}=(x_1,x_2,\dots,x_n)^\top, \boldsymbol{y}=(y_1,y_2,\dots,y_n)^\top \in \mathbb{R}_{\max}^n\), the inequality \(\boldsymbol{x} \leq \boldsymbol{y}\) means \(x_i \leq y_i\) for all \(i=1,2,\dots,n\). Other types of inequalities are understood similarly.
Linearity over the tropical semiring is defined from the viewpoint of semimodules. A nonempty subset \(U \subset \mathbb{R}_{\max}^n\) is called a tropical subspace of \(\mathbb{R}_{\max}^n\) if \(a \otimes \boldsymbol{x} \oplus b \otimes \boldsymbol{y} \in U\) for any \(\boldsymbol{x},\boldsymbol{y} \in U\) and \(a,b \in \mathbb{R}_{\max}\). For tropical subspaces \(U_1 \subset \mathbb{R}_{\max}^n\) and \(U_2 \subset \mathbb{R}_{\max}^m\), a map \(f: U_1 \to U_2\) is said to be tropical linear if \[\begin{align} f(a \otimes \boldsymbol{x} \oplus b \otimes \boldsymbol{y}) = a \otimes f(\boldsymbol{x}) \oplus b \otimes f(\boldsymbol{y}) \end{align}\] for any \(\boldsymbol{x},\boldsymbol{y} \in U_1\) and \(a,b \in \mathbb{R}_{\max}\). Obviously, \(A \in \mathbb{R}_{\max}^{m \times n}\) defines a tropical linear map \(T_A: \mathbb{R}_{\max}^n \to \mathbb{R}_{\max}^m\) by \(T_A(\boldsymbol{x}) = A \otimes \boldsymbol{x}\).
For \(A \in \mathbb{R}_{\max}^{n \times n}\), a scalar \(\lambda \in \mathbb{R}_{\max}\) is called an eigenvalue of \(A\) if there exists \(\boldsymbol{x} \in \mathbb{R}_{\max}^n \setminus \{\boldsymbol{\varepsilon}\}\) satisfying \[\begin{align} A \otimes \boldsymbol{x} = \lambda \otimes \boldsymbol{x}. \end{align}\] Such a vector \(\boldsymbol{x}\) is an eigenvector of \(A\) with respect to \(\lambda\).
To understand the eigenvalues of tropical matrices, we use their associated digraphs. For \(A \in \mathbb{R}_{\max}^{n \times n}\), the weighted digraph \(\mathcal{G}(A)\) is defined by the vertex set \(V = \{1,2,\dots,n\}\) and the edge set \(E = \{ (i,j) \mid [A]_{ij} \neq \varepsilon\}\) with weight \(w((i,j)) = [A]_{ij}\) for \((i,j) \in E\). A path in \(\mathcal{G}(A)\) is a sequence of vertices \((i_0,i_1,\dots,i_{\ell})\) such that \((i_{k-1},i_k) \in E\) for \(k=1,2,\dots,\ell\); if \(i_0 = i_\ell\), this path is called a circuit. The set of edges in a path \(\mathcal{P} = (i_0,i_1,\dots,i_{\ell})\) is \(E(\mathcal{P}) := \{(i_{k-1},i_k) \mid k=1,2,\dots,\ell\}\). The length, weight, and average weight of \(\mathcal{P}\) are defined as \(\ell(\mathcal{P}) := \ell\), \(w(\mathcal{P}) := \sum_{k=1}^{\ell} w((i_{k-1},i_k))\) and \(\mathrm{ave}(\mathcal{P}) = w(\mathcal{P})/\ell(\mathcal{P})\), respectively.
Theorem 1 ([19]). The maximum eigenvalue of \(A \in \mathbb{R}_{\max}^{n \times n}\) is identical to the maximum average weight of all circuits in \(\mathcal{G}(A)\).
A matrix \(A \in \mathbb{R}_{\max}^{n \times n}\) is called irreducible if \(\mathcal{G}(A)\) is strongly connected, i.e., for any \(i,j \in V\) there exists a path from \(i\) to \(j\). If \(A \in \mathbb{R}_{\max}^{n \times n}\) is irreducible, then \(A\) has a unique eigenvalue [19]. In the digraph \(\mathcal{G}(A)\), let \(V^c(A)\) and \(E^c(A)\) be the sets of all vertices and edges, respectively, contained in some maximum average weight circuit. The subgraph \(\mathcal{G}^c(A) = (V^c(A), E^c(A))\) is called the critical digraph of \(A\). The cyclicity of a strongly connected component of \(\mathcal{G}^c(A)\) is the greatest common divisor of the lengths of all circuits contained in that component, and the cyclicity of \(A\) is the least common multiple of the cyclicities of all strongly connected components of \(\mathcal{G}^c(A)\).
For a square matrix \(A \in \mathbb{R}_{\max}^{n \times n}\) and \(k \in \mathbb{N}\), the matrix power is defined as \[\begin{align} A^{\otimes k} = \underbrace{A \otimes A \otimes \cdots \otimes A}_{k\,\text{times}}. \end{align}\] By convention, we define \(A^{\otimes 0}\) as the tropical identity matrix, that is, the square matrix with zeros on the diagonal and \(\varepsilon\) elsewhere. The following fact, known as the Cyclicity Theorem, states that the sequence of matrix powers becomes periodic.
Theorem 2 (Cyclicity Theorem, [1]). Let \(A \in \mathbb{R}_{\max}^{n \times n}\) be an irreducible matrix and \(\lambda\) and \(\sigma\) be its unique eigenvalue and cyclicity, respectively. Then, there exist an integer \(T \geq 1\) such that \[\begin{align} A^{\otimes (t+\sigma)} = \lambda^{\otimes \sigma} \otimes A^{\otimes t} \end{align}\] for any \(t \geq T\).
For \(A \in \mathbb{R}_{\max}^{n \times n}\) and \(k \in \mathbb{N}\), the \((i,j)\) entry of \(A^{\otimes k}\) is identical to the maximum weight of all paths from vertex \(i\) to \(j\) with length \(k\) in \(\mathcal{G}(A)\). If the maximum (average) weight of the circuits in \(\mathcal{G}(A)\) is nonpositive, the maximum weight of all paths from \(i\) to \(j\) is attained by the one with length up to \(n\).
Let us consider a map \(g: \mathbb{R}_{\max}^n \to \mathbb{R}_{\max}\) satisfying \(g(\boldsymbol{\varepsilon}) = \varepsilon\). In this section, we describe a tropical linear approximation \(g(\boldsymbol{x}) \approx \boldsymbol{a} \otimes \boldsymbol{x}\) at \(\boldsymbol{\varepsilon}\), where \(\boldsymbol{a} \in \mathbb{R}_{\max}^{1 \times n}\).
For \(\boldsymbol{x} = (x_1,x_2,\dots,x_n)^\top, \boldsymbol{y} = (y_1,y_2,\dots,y_n)^\top \in \mathbb{R}_{\max}^n\), the distance between them is defined as \[\begin{align} d(\boldsymbol{x}, \boldsymbol{y}) := \max_{i =1,2,\dots,n} |e^{x_i} -e^{y_i}|. \label{eq:dist} \end{align}\tag{1}\] This distance is designed to handle \(\varepsilon\) by setting \(e^{\varepsilon} = 0\). The magnitude of \(\boldsymbol{x}\) is defined as \[\begin{align} \|\boldsymbol{x}\| := d(\boldsymbol{x}, \boldsymbol{\varepsilon}) = \max_{i =1,2,\dots,n} e^{x_i} = e^{\max_i x_i}. \label{eq:norm} \end{align}\tag{2}\] Note that \(\|\boldsymbol{x}\|\) is not a usual norm because \[\begin{align} \|a \otimes \boldsymbol{x}\| = \max_{i =1,2,\dots,n} |e^{a+x_i}| = e^a \|\boldsymbol{x}\| \label{eq:normsp} \end{align}\tag{3}\] for \(a \in \mathbb{R}_{\max}\). We also note that the function \(\|\cdot\|\) is monotonic, that is, if \(\boldsymbol{x} \leq \boldsymbol{y}\), then \(\|\boldsymbol{x}\| \leq \|\boldsymbol{y}\|\).
A tropical linear form \(\boldsymbol{a} \otimes \boldsymbol{x}\) given by \(\boldsymbol{a} \in \mathbb{R}_{\max}^{1 \times n}\) is called a tropical linear approximation of \(g(\boldsymbol{x})\) at \(\boldsymbol{\varepsilon}\), expressed as \(g(\boldsymbol{x}) \approx \boldsymbol{a} \otimes \boldsymbol{x}\), if \(d(g(\boldsymbol{x}), \boldsymbol{a} \otimes \boldsymbol{x}) = o(\|\boldsymbol{x}\|)\), that is, \[\begin{align} \lim_{\boldsymbol{x} \to \boldsymbol{\varepsilon}} \frac{d(g(\boldsymbol{x}), \boldsymbol{a} \otimes \boldsymbol{x})}{\|\boldsymbol{x}\|} = 0. \end{align}\] For \(\boldsymbol{x} = (x_1,x_2,\dots,x_n)^\top \in \mathbb{R}_{\max}^n\), let \(\boldsymbol{x}(i)\) be the vector whose \(i\)th entry is \(x_i\) and other entries are \(\varepsilon\).
Proposition 1. Suppose that \(g: \mathbb{R}_{\max}^n \to \mathbb{R}_{\max}\) satisfies \(g(\boldsymbol{\varepsilon}) = \varepsilon\). If \(\boldsymbol{a} \otimes \boldsymbol{x}\) is a tropical linear approximation of \(g(\boldsymbol{x})\) at \(\boldsymbol{\varepsilon}\) for some \(\boldsymbol{a} = (a_1,a_2,\dots,a_n) \in \mathbb{R}_{\max}^{1 \times n}\), then \[\begin{align} a_i = \lim_{x_i \to \varepsilon} g(\boldsymbol{x}(i)) \oslash x_i \end{align}\] for \(i = 1,2,\dots,n\).
Let us assume that \(\boldsymbol{a} \otimes \boldsymbol{x}\) is a tropical linear approximation of \(g(\boldsymbol{x})\). When \(x_j = \varepsilon\) for \(j \neq i\), we have \(\boldsymbol{a} \otimes \boldsymbol{x} = \max_{j} (a_j + x_j) = a_i+x_i\) and \(\max_{j} x_j = x_i.\) Then, by 1 and 2 , we have \[\begin{align} \frac{d(g(\boldsymbol{x}), \boldsymbol{a} \otimes \boldsymbol{x})}{\|\boldsymbol{x}\|} = \frac{|e^{g(\boldsymbol{x}(i))} - e^{a_i + x_i}|}{e^{x_i}}. \end{align}\] Hence, we obtain \[\begin{align} \lim_{x_i \to \varepsilon} \frac{|e^{g(\boldsymbol{x}(i))} - e^{a_i + x_i}|}{e^{x_i}} = 0, \end{align}\] which implies \[\begin{align} \lim_{x_i \to \varepsilon} |e^{g(\boldsymbol{x}(i)) - x_i} - e^{a_i}| = 0. \end{align}\] Recalling that \(g(\boldsymbol{x}(i)) - x_i = g(\boldsymbol{x}(i)) \oslash x_i\), we have \[\begin{align} a_i = \lim_{x_i \to \varepsilon} g(\boldsymbol{x}(i)) \oslash x_i. \end{align}\] As the above argument is valid for \(i = 1,2,\dots,n\), we have completed the proof.
Based on Proposition 1, when \(g: \mathbb{R}_{\max}^n \to \mathbb{R}_{\max}\) satisfies \(g(\boldsymbol{\varepsilon}) = \varepsilon\), we define the tropical derivative of \(g\) at \(\boldsymbol{\varepsilon}\) as \[\begin{align} D_{i,\boldsymbol{\varepsilon}} g := \lim_{x_i \to \varepsilon} g(\boldsymbol{x}(i)) \oslash x_i \end{align}\] for \(i=1,2,\dots,n\). One may recall that the conventional partial derivative of \(\tilde{g}: \mathbb{R}^n \to \mathbb{R}\) at \(\boldsymbol{p}=(p_1,p_2,\dots,p_n)^\top \in \mathbb{R}^n\) is given by \[\begin{align} \frac{\partial g}{\partial x_i}(\boldsymbol{p}) = \lim_{x_i \to p_i} \frac{\tilde{g}((p_1,\dots,x_i,\dots,p_n)^\top) - \tilde{g}(\boldsymbol{p})}{x_i-p_i} \label{eq:usualpd} \end{align}\tag{4}\] for \(i=1,2,\dots,n\). If \(\boldsymbol{p}=(0,0,\dots,0)^\top\) and \(\tilde{g}(\boldsymbol{p}) = 0\), then the right-hand side of 4 becomes \[\begin{align} \lim_{x_i \to 0} \frac{\tilde{g}((0,\dots,x_i,\dots,0)^\top)}{x_i}, \end{align}\] from which our tropical derivative comes.
Example 1. Let us consider a tropical polynomial function \(g(x) = \bigoplus_{k=1}^m c_k \otimes x^{\otimes k}\). Then, \[\begin{align} \lim_{x \to \varepsilon} g(x) \oslash x = c_1 \oplus \left( \bigoplus_{k=2}^m c_k \otimes x^{\otimes (k-2)} \right) \otimes x. \label{eq:poly} \end{align}\tag{5}\] The second term on the right-hand side of 5 converges to \(\varepsilon\) as \(x \to \varepsilon\). Hence, the tropical linear approximation of \(g\) is \(g(\boldsymbol{x}) \approx c_1 \otimes x\), similar to the usual algebra.
Remark 2. The converse of Proposition 1 is not true. Indeed, let us consider \[\begin{align} g(x,y) = x \oplus y \oplus (x \otimes y)^{\otimes \frac{1}{3}}. \end{align}\] It is easily verified that \[\begin{align} \lim_{x \to \varepsilon} g(x,\varepsilon) \oslash x = \lim_{y \to \varepsilon} g(\varepsilon,y) \oslash y = 0. \end{align}\] However, when \(x=y\), by setting \(\boldsymbol{x} = (x,x)^\top\), we have \[\begin{align} \lim_{x \to \varepsilon}\frac{|e^{g(x,x)} - e^{0\otimes x\oplus 0\otimes x}|}{\|\boldsymbol{x}\|} = \lim_{x \to \varepsilon}\frac{|e^{x \oplus x^{\otimes \frac{2}{3}}} - e^x|}{e^x} = \lim_{x \to \varepsilon} |e^{-\frac{1}{3}x} -1| = +\infty, \end{align}\] which means that \(g(x,y)\) cannot be tropical-linearly approximated.
Based on the tropical linear approximation, the following lemma sets an upper bound of \(g(\boldsymbol{x})\).
Lemma 1. Let \(g: \mathbb{R}_{\max}^n \to \mathbb{R}_{\max}\), \(\boldsymbol{a} \in \mathbb{R}_{\max}^{1 \times n}\) and \(\alpha > 0\). If \(\boldsymbol{x} \in \mathbb{R}_{\max}^n\) satisfies \(d(g(\boldsymbol{x}), \boldsymbol{a} \otimes \boldsymbol{x}) \leq \alpha \|\boldsymbol{x}\|\), then \[\begin{align} g(\boldsymbol{x}) \leq \log(1+\sqrt{\alpha}) \otimes \boldsymbol{a} \otimes \boldsymbol{x} \oplus \log(\alpha+\sqrt{\alpha}) \otimes \boldsymbol{0} \otimes \boldsymbol{x}, \label{eq:gbound} \end{align}\tag{6}\] where \(\boldsymbol{0} = (0,\dots,0) \in \mathbb{R}_{\max}^{1 \times n}\).
Let us assume that \(\boldsymbol{x} \in \mathbb{R}_{\max}^n\) satisfies \[\begin{align} d(g(\boldsymbol{x}), \boldsymbol{a} \otimes \boldsymbol{x}) \leq \alpha \|\boldsymbol{x}\|. \end{align}\] By noting that \(d(g(\boldsymbol{x}), \boldsymbol{a} \otimes \boldsymbol{x}) = |e^{g(\boldsymbol{x})} - e^{\boldsymbol{a} \otimes \boldsymbol{x}}|\) and \(\|\boldsymbol{x}\| = e^{\max_i x_i} = e^{\boldsymbol{0} \otimes \boldsymbol{x}}\), we have \[\begin{align} -\alpha e^{\boldsymbol{0} \otimes \boldsymbol{x}} \leq e^{g(\boldsymbol{x})} - e^{\boldsymbol{a} \otimes \boldsymbol{x}} \leq \alpha e^{\boldsymbol{0} \otimes \boldsymbol{x}}, \end{align}\] which leads to \[\begin{align} e^{g(\boldsymbol{x})} \leq e^{\boldsymbol{a} \otimes \boldsymbol{x}} + \alpha e^{\boldsymbol{0} \otimes \boldsymbol{x}}. \end{align}\]
If \(\boldsymbol{a} \otimes \boldsymbol{x} \geq \log\sqrt{\alpha} \otimes \boldsymbol{0} \otimes \boldsymbol{x}\), that is, \((-\log\sqrt{\alpha} ) \otimes \boldsymbol{a} \otimes \boldsymbol{x} \geq \boldsymbol{0} \otimes \boldsymbol{x}\), then \[\begin{align} e^{\boldsymbol{0} \otimes \boldsymbol{x}} \leq e^{(-\log\sqrt{\alpha} ) \otimes \boldsymbol{a} \otimes \boldsymbol{x}} = e^{(-\log\sqrt{\alpha} ) + (\boldsymbol{a} \otimes \boldsymbol{x})} = e^{\log \sqrt{\alpha}^{-1}} e^{\boldsymbol{a} \otimes \boldsymbol{x}} = (\sqrt{\alpha})^{-1} e^{\boldsymbol{a} \otimes \boldsymbol{x}}. \end{align}\] Hence, we obtain \[\begin{align} e^{\boldsymbol{a} \otimes \boldsymbol{x}} + \alpha e^{\boldsymbol{0} \otimes \boldsymbol{x}} \leq (1+ \sqrt{\alpha})e^{\boldsymbol{a} \otimes \boldsymbol{x}} = e^{\log (1+ \sqrt{\alpha})} e^{\boldsymbol{a} \otimes \boldsymbol{x}} = e^{\log(1+\sqrt{\alpha}) \otimes \boldsymbol{a} \otimes \boldsymbol{x}}, \end{align}\] leading to \[\begin{align} g(\boldsymbol{x}) \leq \log(1+\sqrt{\alpha}) \otimes \boldsymbol{a} \otimes \boldsymbol{x}. \end{align}\]
If \(\boldsymbol{a} \otimes \boldsymbol{x} \leq \log\sqrt{\alpha} \otimes \boldsymbol{0} \otimes \boldsymbol{x}\), then \[\begin{align} e^{\boldsymbol{a} \otimes \boldsymbol{x}} \leq e^{\log\sqrt{\alpha} \otimes \boldsymbol{0} \otimes \boldsymbol{x}} = e^{(\log\sqrt{\alpha}) + (\boldsymbol{0} \otimes \boldsymbol{x})} = e^{\log \sqrt{\alpha}} e^{\boldsymbol{0} \otimes \boldsymbol{x}} = \sqrt{\alpha}\, e^{\boldsymbol{0} \otimes \boldsymbol{x}}. \end{align}\] Hence, we obtain \[\begin{align} e^{\boldsymbol{a} \otimes \boldsymbol{x}} + \alpha e^{\boldsymbol{0} \otimes \boldsymbol{x}} \leq (\sqrt{\alpha} + \alpha)e^{\boldsymbol{0} \otimes \boldsymbol{x}} = e^{\log (\sqrt{\alpha} + \alpha)} e^{\boldsymbol{0} \otimes \boldsymbol{x}} = e^{\log(\alpha+\sqrt{\alpha}) \otimes \boldsymbol{0} \otimes \boldsymbol{x}}, \end{align}\] leading to \[\begin{align} g(\boldsymbol{x}) \leq \log(\alpha+\sqrt{\alpha}) \otimes \boldsymbol{0} \otimes \boldsymbol{x}. \end{align}\]
Since one of the two cases must occur, 6 is proved.
Let us consider a map \(\boldsymbol{f}: \mathbb{R}_{\max}^n \to \mathbb{R}_{\max}^n\) and the dynamical system defined by the following difference equation: \[\begin{align} \boldsymbol{x}^{(t+1)} = \boldsymbol{f}(\boldsymbol{x}^{(t)}), \qquad t \in \mathbb{Z}_{\geq 0}, \label{eq:dyn} \end{align}\tag{7}\] where \(\mathbb{Z}_{\geq 0}\) is the set of nonnegative integers. We denote the \(i\)th entry of \(\boldsymbol{x}^{(t)}\) as \(x^{(t)}_i\). Assume that \(\boldsymbol{\varepsilon}\) is a fixed point of 7 , i.e., \(\boldsymbol{f}(\boldsymbol{\varepsilon}) = \boldsymbol{\varepsilon}\). The fixed point \(\boldsymbol{\varepsilon}\) is said to be stable if for all \(\alpha > 0\) there exists \(\delta > 0\) such that \[\begin{align} \|\boldsymbol{x}^{(0)}\| < \delta \quad \Rightarrow \quad \|\boldsymbol{x}^{(t)}\| < \alpha \text{ for all } t \in \mathbb{Z}_{\geq 0}; \end{align}\] otherwise, it is unstable. Furthermore, \(\boldsymbol{\varepsilon}\) is said to be asymptotically stable if it is stable and there exists \(\delta' > 0\) such that \[\begin{align} \|\boldsymbol{x}^{(0)}\| < \delta' \quad \Rightarrow \quad \lim_{t \to \infty} \boldsymbol{x}^{(t)} = \boldsymbol{\varepsilon}. \end{align}\]
The map \(\boldsymbol{f}\) is represented as a tuple of \(n\) functions \((f_1,f_2,\dots,f_n)\) defined by \(\boldsymbol{f}(\boldsymbol{x}) = (f_1(\boldsymbol{x}),f_2(\boldsymbol{x}),\dots,f_n(\boldsymbol{x}))^\top\) for \(\boldsymbol{x} \in \mathbb{R}_{\max}^n\). The tropical Jacobian matrix \(J_{\boldsymbol{\varepsilon}}\boldsymbol{f} \in \mathbb{R}_{\max}^{n \times n}\) at \(\boldsymbol{\varepsilon}\) is defined by \[\begin{align} [J_{\boldsymbol{\varepsilon}}\boldsymbol{f}]_{ij} = D_{j,\boldsymbol{\varepsilon}} f_i. \end{align}\] If \(f_i\) is tropical-linearly approximated for \(i=1,\dots,n\), then \(\boldsymbol{f}\) is said to be tropical-linearly approximated at \(\boldsymbol{\varepsilon}\), expressed as \[\begin{align} \boldsymbol{f}(\boldsymbol{x}) \approx J_{\boldsymbol{\varepsilon}} \boldsymbol{f} \otimes \boldsymbol{x}. \end{align}\] The main result of this study is presented below.
Theorem 3. Suppose that \(\boldsymbol{\varepsilon}\) is a fixed point of 7 and \(\boldsymbol{f}\) is tropical-linearly approximated at \(\boldsymbol{\varepsilon}\). If the maximum eigenvalue of \(J_{\boldsymbol{\varepsilon}} \boldsymbol{f}\) is negative, then \(\boldsymbol{\varepsilon}\) is asymptotically stable.
Let \(M_0\), \(\lambda\), and \(\sigma\) be the maximum entry, maximum eigenvalue, and cyclicity of \(J_{\boldsymbol{\varepsilon}} \boldsymbol{f}\), respectively. Then, by noting that \(\lambda < 0\) from our assumption, we can choose \(\alpha > 0\) to be sufficiently small such that \(\log(1+\sqrt{\alpha}) < -\lambda\) and \(\log(\alpha+\sqrt{\alpha}) < n\lambda-M_1\), where \(M_1= \max(n(M_0-\lambda),0)\). We define \[\begin{align} A = \log(1+\sqrt{\alpha}) \otimes J_{\boldsymbol{\varepsilon}} \boldsymbol{f} \oplus \log(\alpha+\sqrt{\alpha}) \otimes O, \end{align}\] where \(O\) is the \(n\)-by-\(n\) matrix with all its entries being \(0\). The maximum entry of \(A\) is at most \(\max(M_0-\lambda,0)\). Additionally, the maximum eigenvalue of \(A\) is negative. Indeed, let us consider any circuit \(\mathcal{C}\) in \(\mathcal{G}(A)\). If none of the edges in \(E(\mathcal{C})\) have weight \(\log(\alpha+\sqrt{\alpha})\), then all of them should come from finite entries of \(\log(1+\sqrt{\alpha}) \otimes J_{\boldsymbol{\varepsilon}} \boldsymbol{f}\). Hence, the average weight of \(\mathcal{C}\) in \(\mathcal{G}(A)\) is identical to that in \(\mathcal{G}(J_{\boldsymbol{\varepsilon}} \boldsymbol{f})\) augmented by \(\log(1+\sqrt{\alpha})\). This leads to \[\begin{align} \mathrm{ave}(\mathcal{C}) \leq \lambda + \log(1+\sqrt{\alpha}) < 0, \end{align}\] where the equality of the first inequality holds if \(\mathcal{C}\) is the maximum average weight circuit in \(\mathcal{G}(J_{\boldsymbol{\varepsilon}} \boldsymbol{f})\). On the other hand, if the weight of some edge \(e \in E(\mathcal{C})\) is \(\log(\alpha+\sqrt{\alpha})\), then \[\begin{align} w(\mathcal{C}) = w(e) + \sum_{e' \in E(\mathcal{C}) \setminus \{e\}} w(e') &\leq \log(\alpha+\sqrt{\alpha}) + (n-1) \cdot \max(M_0 - \lambda,0) \\ &= \log(\alpha+\sqrt{\alpha}) + M_1 - \max(M_0 - \lambda,0) \\ &< n\lambda \\ &\leq \ell(\mathcal{C}) \lambda. \end{align}\] Hence, the average weight of \(\mathcal{C}\) is smaller than \(\lambda\). Thus, the maximum eigenvalue of \(A\) is \(\lambda_1:= \lambda + \log(1+\sqrt{\alpha})\). Since \(\lambda_1 < 0\) from our choice of \(\alpha\), the (average) weights of all circuits in \(\mathcal{G}(A)\) are negative. Moreover, by recalling the definition of the cyclicity, the cyclicity of \(A\) is \(\sigma\) because the set of maximum average weight circuits in \(\mathcal{G}(A)\) coincides with that in \(\mathcal{G}(J_{\boldsymbol{\varepsilon}}\boldsymbol{f})\).
Since \(\boldsymbol{f}\) is tropical-linearly approximated at \(\boldsymbol{\varepsilon}\), we have \[\begin{align} \lim_{\boldsymbol{x} \to \boldsymbol{\varepsilon}} \frac{d(f_i(\boldsymbol{x}), [J_{\boldsymbol{\varepsilon}}\boldsymbol{f} \otimes \boldsymbol{x}]_i)}{\|\boldsymbol{x}\|} = 0 \end{align}\] for all \(i=1,2,\dots,n\). This means that for all \(i=1,2,\dots,n\) there exists \(\delta_i > 0\) such that \[\begin{align} \|\boldsymbol{x}\| < \delta_i \quad \Rightarrow \quad d(f_i(\boldsymbol{x}), [J_{\boldsymbol{\varepsilon}}\boldsymbol{f} \otimes \boldsymbol{x}]_i) \leq \alpha \|\boldsymbol{x}\|. \end{align}\] In particular, by setting \(\delta_0 = \min(\alpha, \delta_1,\delta_2,\dots,\delta_n)\), we have \[\begin{align} \|\boldsymbol{x}\| < \delta_0 \quad \Rightarrow \quad \max_{i=1,2,\dots,n} d(f_i(\boldsymbol{x}), [J_{\boldsymbol{\varepsilon}}\boldsymbol{f} \otimes \boldsymbol{x}]_i) \leq \alpha \|\boldsymbol{x}\|. \label{eq:linapprox0} \end{align}\tag{8}\] Applying Lemma 1 to each entry of \(\boldsymbol{f}(\boldsymbol{x})\), we obtain \[\begin{align} \max_{i=1,2,\dots,n} d(f_i(\boldsymbol{x}), [J_{\boldsymbol{\varepsilon}}\boldsymbol{f} \otimes \boldsymbol{x}]_i) \leq \alpha \|\boldsymbol{x}\| \quad \Rightarrow \quad \boldsymbol{f}(\boldsymbol{x}) \leq A \otimes \boldsymbol{x}. \label{eq:lineval} \end{align}\tag{9}\]
Let \(\delta = \delta_0e^{-M_1}\) and consider the initial value problem of 7 starting with any \(\boldsymbol{x}^{(0)} \in \mathbb{R}_{\max}^n\) such that \(\|\boldsymbol{x}^{(0)}\| < \delta\). By induction on \(t\), we show that \[\begin{align} \boldsymbol{x}^{(t)} \leq A^{\otimes t} \otimes \boldsymbol{x}^{(0)} \label{eq:ind} \end{align}\tag{10}\] for any \(t \in \mathbb{Z}_{\geq 0}\). The case where \(t=0\) is trivial because \(A^{\otimes 0}\) is the tropical identity matrix. Let us assume that 10 is satisfied for some \(t \in \mathbb{Z}_{\geq 0}\). Since the weights of all circuits in \(\mathcal{G}(A)\) are negative, the entries of \(A^{\otimes t}\) are at most \(M_1 = n \cdot \max(M_0-\lambda,0)\), see the last paragraph of Section 2. Note that this bound \(M_1\) is determined only by \(J_{\boldsymbol{\varepsilon}}\boldsymbol{f}\) and does not depend on the value of \(\alpha\) used to construct the matrix \(A\). Because of the assumption of induction, the monotonicity of \(\|\cdot \|\), and 3 , we have \[\begin{align} \|\boldsymbol{x}^{(t)}\| \leq \| A^{\otimes t} \otimes \boldsymbol{x}^{(0)}\| \leq \| M_1 \otimes \boldsymbol{x}^{(0)}\| = e^{M_1} \|\boldsymbol{x}^{(0)}\| <e^{M_1}\delta = \delta_0. \end{align}\] Using 8 , 9 and 10 , we obtain \[\begin{align} \boldsymbol{x}^{(t+1)} = \boldsymbol{f}(\boldsymbol{x}^{(t)}) \leq A \otimes \boldsymbol{x}^{(t)} \leq A\otimes (A^{\otimes t} \otimes \boldsymbol{x}^{(0)}) = A^{\otimes (t+1)} \otimes \boldsymbol{x}^{(0)}, \end{align}\] which proves 10 for \(t+1\).
We have shown that \(\|\boldsymbol{x}^{(t)}\| < \delta_0 \leq \alpha\) for all \(t \in \mathbb{Z}_{\geq 0}\), which means \(\boldsymbol{\varepsilon}\) is stable. Since all entries of \(A\) are finite, \(A\) is irreducible. By Theorem 2, there exist \(T \geq 1\) such that \[\begin{align} A^{\otimes (k\sigma+T+r)} = \lambda_1^{\otimes k\sigma} \otimes A^{\otimes (T+r)} \end{align}\] for any \(k \in \mathbb{Z}_{\geq 0}\) and \(r=0,1,\dots,\sigma-1\). This leads to \[\begin{align} \boldsymbol{x}^{(k\sigma+T+r)} \leq \lambda_1^{\otimes k\sigma} \otimes A^{\otimes (T+r)} \otimes \boldsymbol{x}^{(0)} \end{align}\] for any \(k \in \mathbb{Z}_{\geq 0}\) and \(r=0,1,\dots,\sigma-1\). Because \(\lambda_1 < 0\), we have \(\lim_{k \to \infty} \boldsymbol{x}^{(k\sigma+T+r)} = \boldsymbol{\varepsilon}\) for any \(r\), which means that \(\lim_{t \to \infty} \boldsymbol{x}^{(t)} = \boldsymbol{\varepsilon}\). Thus, \(\boldsymbol{\varepsilon}\) is asymptotically stable.
To derive a condition for the instability of the fixed point \(\boldsymbol{\varepsilon}\), we introduce the following result in the visualization of tropical matrices.
Lemma 2 ([20]). Let \(\lambda \in \mathbb{R}\) be the maximum eigenvalue of \(A \in \mathbb{R}_{\max}^{n \times n}\). Then, there exists a vector \((x_1,x_2,\dots,x_n)^\top \in \mathbb{R}^n\) such that \[\begin{align} \begin{cases} [A]_{ij} \otimes x_j = \lambda \otimes x_i, & \text{if } (i,j) \in E^c(A), \\ [A]_{ij} \otimes x_j < \lambda \otimes x_i, & \text{otherwise}. \end{cases} \end{align}\]
Theorem 4. Suppose that \(\boldsymbol{\varepsilon}\) is a fixed point of 7 and \(\boldsymbol{f}\) is tropical-linearly approximated at \(\boldsymbol{\varepsilon}\). If the maximum eigenvalue of \(J_{\boldsymbol{\varepsilon}} \boldsymbol{f}\) is positive, then \(\boldsymbol{\varepsilon}\) is unstable.
Let \(\lambda > 0\) be the maximum eigenvalue of \(J_{\boldsymbol{\varepsilon}} \boldsymbol{f}\). For brevity, we write \(V^c = V^c(J_{\boldsymbol{\varepsilon}} \boldsymbol{f})\) and \(E^c = E^c(J_{\boldsymbol{\varepsilon}} \boldsymbol{f})\). By Lemma 2, there exists a vector \(\hat{\boldsymbol{x}} = (\hat{x}_1,\hat{x}_2,\dots,\hat{x}_n)^\top \in \mathbb{R}^n\) such that \[\begin{align} \begin{cases} [J_{\boldsymbol{\varepsilon}} \boldsymbol{f}]_{ij} \otimes \hat{x}_j = \lambda \otimes \hat{x}_i, & \text{if } (i,j) \in E^c, \\ [J_{\boldsymbol{\varepsilon}} \boldsymbol{f}]_{ij} \otimes \hat{x}_j < \lambda \otimes \hat{x}_i, & \text{otherwise}. \end{cases} \label{eq:visualize} \end{align}\tag{11}\] Let us define \[\begin{align} \eta = \min\left(\lambda,\;\min_{(i,j) \not\in E^c} ((\lambda \otimes \hat{x}_i) - ([J_{\boldsymbol{\varepsilon}} \boldsymbol{f}]_{ij} \otimes \hat{x}_j))\right). \label{eq:defeta} \end{align}\tag{12}\] We choose \(\alpha > 0\) to be sufficiently small such that \[\begin{align} &\log(1+\sqrt{\alpha}) < \frac{\eta}{2}, \tag{13}\\ &\log (1-\sqrt{\alpha}) > -\frac{\eta}{2}, \tag{14}\\ &\log\sqrt{\alpha} < \min_{(i,j) \in E^c} ([J_{\boldsymbol{\varepsilon}} \boldsymbol{f}]_{ij} +\hat{x}_j)- \max_i \hat{x}_i, \tag{15}\\ &\log(\alpha+\sqrt{\alpha}) < \min_i \hat{x}_i-\max_i \hat{x}_i. \tag{16} \end{align}\]
Since \(\boldsymbol{f}\) is tropical-linearly approximated at \(\boldsymbol{\varepsilon}\), there exists \(\delta_0 > 0\) such that \[\begin{align} \|\boldsymbol{x}\| < \delta_0 \quad \Rightarrow \quad \max_{i=1,2,\dots,n} d(f_i(\boldsymbol{x}), [J_{\boldsymbol{\varepsilon}}\boldsymbol{f} \otimes \boldsymbol{x}]_{i}) \leq \alpha \|\boldsymbol{x}\|. \label{eq:linapprox} \end{align}\tag{17}\] Contrary to the assertion of the theorem, let us assume that \(\boldsymbol{\varepsilon}\) is a stable fixed point. Then, there exists \(\delta > 0\) such that \[\begin{align} \|\boldsymbol{x}^{(0)}\| < \delta \quad \Rightarrow \quad \|\boldsymbol{x}^{(t)}\| < \delta_0 \text{ for all } t \in \mathbb{Z}_{\geq 0}. \label{eq:oncont} \end{align}\tag{18}\]
By choosing a sufficiently small \(\rho \in \mathbb{R}\), we take an initial vector \(\boldsymbol{x}^{(0)} := \rho \otimes \hat{\boldsymbol{x}}\) such that \(\|\boldsymbol{x}^{(0)}\| < \delta\). Since \(\lambda-\eta/2 \geq \lambda/2 > 0\), the inequality \[\begin{align} \max_{i=1,2,\dots,n} (x^{(t)}_i -\hat{x}_i) \geq \left(\lambda-\frac{\eta}{2}\right)t + \rho ,\qquad t \in \mathbb{Z}_{\geq 0}, \label{eq:unstable} \end{align}\tag{19}\] will lead to \(\lim_{t \to \infty} \max_i x^{(t)}_i = \infty\), which contradicts the stability. Now, we show 19 together with the fact that the maximum value on the left-hand side is attained by some \(i \in V^c\) by induction on \(t\).
The case where \(t=0\) is trivial because \(x_i^{(0)} - \hat{x}_i = \rho\) for all \(i=1,2,\dots,n\). Let us assume that the claim is true for some \(t \in \mathbb{Z}_{\geq 0}\). Let \(i_1 \in V^c\) be an index \(i\) that maximizes \(x^{(t)}_{i} -\hat{x}_{i}\). Then, \((i_2,i_1) \in E^c\) for some \(i_2 \in V^c\). Note that \[\begin{align} \max_i x^{(t)}_i - \max_i \hat{x}_i \leq \max_i (x^{(t)}_i - \hat{x}_i) = x^{(t)}_{i_1} - \hat{x}_{i_1}. \label{eq:max} \end{align}\tag{20}\] Combining the above inequality with 15 , we obtain \[\begin{align} [J_{\boldsymbol{\varepsilon}} \boldsymbol{f} \otimes \boldsymbol{x}^{(t)}]_{i_2} &\geq [J_{\boldsymbol{\varepsilon}} \boldsymbol{f}]_{i_2i_1} \otimes x^{(t)}_{i_1} \\ &\geq ([J_{\boldsymbol{\varepsilon}} \boldsymbol{f}]_{i_2i_1} +\hat{x}_{i_1}- \max_i \hat{x}_i) + \max_i x^{(t)}_i \\ &> \log \sqrt{\alpha} + \max_i x^{(t)}_i. \end{align}\] Using 17 and 18 and noting that \(\boldsymbol{f}(\boldsymbol{x}^{(t)}) = \boldsymbol{x}^{(t+1)}\), we have \(d(x_{i}^{(t+1)}, [J_{\boldsymbol{\varepsilon}}\boldsymbol{f} \otimes \boldsymbol{x}^{(t)}]_{i}) \leq \alpha \|\boldsymbol{x}^{(t)}\|\) for all \(i=1,2,\dots,n\), yielding \[\begin{align} -\alpha e^{\max_i x^{(t)}_i} \leq e^{x_{i_2}^{(t+1)}} - e^{[J_{\boldsymbol{\varepsilon}} \boldsymbol{f} \otimes \boldsymbol{x}^{(t)}]_{i_2}} \leq \alpha e^{\max_i x^{(t)}_i}. \end{align}\] This leads to \[\begin{align} e^{x_{i_2}^{(t+1)}} &\geq e^{[J_{\boldsymbol{\varepsilon}} \boldsymbol{f} \otimes \boldsymbol{x}^{(t)}]_{i_2}} - \alpha e^{\max_i x^{(t)}_i} \\ &> e^{[J_{\boldsymbol{\varepsilon}} \boldsymbol{f} \otimes \boldsymbol{x}^{(t)}]_{i_2}} - \alpha e^{(-\log\sqrt{\alpha}) + [J_{\boldsymbol{\varepsilon}} \boldsymbol{f} \otimes \boldsymbol{x}^{(t)}]_{i_2}} \\ &= e^{[J_{\boldsymbol{\varepsilon}} \boldsymbol{f} \otimes \boldsymbol{x}^{(t)}]_{i_2}} - \sqrt{\alpha}\, e^{[J_{\boldsymbol{\varepsilon}} \boldsymbol{f} \otimes \boldsymbol{x}^{(t)}]_{i_2}} \\ & = (1-\sqrt{\alpha}) e^{[J_{\boldsymbol{\varepsilon}} \boldsymbol{f} \otimes \boldsymbol{x}^{(t)}]_{i_2}} \\ &= e^{\log(1-\sqrt{\alpha}) + [J_{\boldsymbol{\varepsilon}} \boldsymbol{f} \otimes \boldsymbol{x}^{(t)}]_{i_2}}. \end{align}\] Hence, from 11 and 14 , we obtain \[\begin{align} x^{(t+1)}_{i_2} &> \log(1-\sqrt{\alpha}) + [J_{\boldsymbol{\varepsilon}} \boldsymbol{f} \otimes \boldsymbol{x}^{(t)}]_{i_2} \\ &> \left(-\frac{\eta}{2}\right) + [J_{\boldsymbol{\varepsilon}} \boldsymbol{f}]_{i_2i_1} + x^{(t)}_{i_1} \\ & = \left(-\frac{\eta}{2}\right) + ([J_{\boldsymbol{\varepsilon}} \boldsymbol{f}]_{i_2i_1} \otimes \hat{x}_{i_1}) - \hat{x}_{i_1} + x^{(t)}_{i_1} \\ &= \left(-\frac{\eta}{2}\right) + (\lambda \otimes \hat{x}_{i_2}) + (x^{(t)}_{i_1} - \hat{x}_{i_1}), \end{align}\] which implies \[\begin{align} x^{(t+1)}_{i_2} - \hat{x}_{i_2} &> \left(\lambda-\frac{\eta}{2}\right) + ( x^{(t)}_{i_1} - \hat{x}_{i_1}). \label{eq:tinc} \end{align}\tag{21}\] By induction, we obtain \[\begin{align} x^{(t+1)}_{i_2} - \hat{x}_{i_2}\geq \left(\lambda-\frac{\eta}{2}\right)(t+1) + \rho, \end{align}\] which proves 19 for \(t+1\).
We next prove that the maximum of \(x^{(t+1)}_i -\hat{x}_i\) is attained by some \(i \in V^c\). For any \(i \not\in V^c\) and \(j = 1,2,\dots,n\), we have \[\begin{align} ([J_{\boldsymbol{\varepsilon}} \boldsymbol{f}]_{ij} \otimes x^{(t)}_j) - \hat{x}_i &= ([J_{\boldsymbol{\varepsilon}} \boldsymbol{f}]_{ij} \otimes \hat{x}_j) - \hat{x}_j + x^{(t)}_j - \hat{x}_i \\ &\leq ((\lambda \otimes \hat{x}_i) - \eta) - \hat{x}_j + x^{(t)}_j - \hat{x}_i \\ &= (\lambda -\eta) + (x^{(t)}_j - \hat{x}_j). \end{align}\] because of the fact that \((i,j) \not\in E^c\) and the definition of \(\eta\) in 12 . By taking the maximum for \(j=1,2,\dots,n\), we have \[\begin{align} [J_{\boldsymbol{\varepsilon}} \boldsymbol{f} \otimes \boldsymbol{x}^{(t)}]_i - \hat{x}_i \leq (\lambda -\eta) + \max_j (x^{(t)}_j - \hat{x}_j). \label{eq:noncri} \end{align}\tag{22}\] Recall that \(\|\boldsymbol{x}^{(t)}\| < \delta_0\) induces \(d(f_i(\boldsymbol{x}^{(t)}), [J_{\boldsymbol{\varepsilon}}\boldsymbol{f} \otimes \boldsymbol{x}^{(t)}]_{i}) \leq \alpha \|\boldsymbol{x}^{(t)}\|\). Combining Lemma 1 with 13 and 16 , we obtain \[\begin{align} x^{(t+1)}_i = f_i(\boldsymbol{x}^{(t)}) \leq \frac{\eta}{2} \otimes [J_{\boldsymbol{\varepsilon}} \boldsymbol{f} \otimes \boldsymbol{x}^{(t)}]_i \oplus (\min_j \hat{x}_j - \max_j \hat{x}_j) \otimes (\boldsymbol{0} \otimes \boldsymbol{x}^{(t)}). \end{align}\] Then, using 20 , 21 and 22 , we obtain \[\begin{align} x^{(t+1)}_i - \hat{x}_i &\leq \left(\frac{\eta}{2} + [J_{\boldsymbol{\varepsilon}} \boldsymbol{f} \otimes \boldsymbol{x}^{(t)}]_i - \hat{x}_i \right) \oplus (\min_j \hat{x}_j - \max_j \hat{x}_j + \max_j x^{(t)}_j - \hat{x}_i )\\ & \leq \left(\frac{\eta}{2} + (\lambda -\eta) + \max_j (x^{(t)}_j - \hat{x}_j) \right) \oplus (x^{(t)}_{i_1} - \hat{x}_{i_1} + \min_j \hat{x}_j - \hat{x}_i) \\ & \leq \left(\lambda -\frac{\eta}{2} + (x^{(t)}_{i_1} - \hat{x}_{i_1}) \right) \oplus (x^{(t)}_{i_1} - \hat{x}_{i_1}) \\ &= \left(\lambda -\frac{\eta}{2} \right) + (x^{(t)}_{i_1} - \hat{x}_{i_1}) \\ &< x^{(t+1)}_{i_2} - \hat{x}_{i_2}. \end{align}\] Considering that the above inequality holds for all \(i \not\in V^c\), we proved that \(\max_i (x^{(t+1)}_i - \hat{x}_i)\) is attained by some \(i \in V^c\). Thus, the claim is also true for \(t+1\). By induction, we have proved 19 for all \(t \in \mathbb{Z}_{\geq 0}\). This completes the proof of the theorem.
We demonstrate Theorems 3 and 4 in some examples.
Example 2. Let us consider a difference equation \[\begin{align} \begin{pmatrix} x^{(t+1)} \\ y^{(t+1)} \end{pmatrix} = \begin{pmatrix} (x^{(t)} \oplus a) \otimes y^{(t)} \\ 1 \otimes x^{(t)} \oplus (-1) \otimes y^{(t)} \end{pmatrix}. \end{align}\] As each entry of \(\boldsymbol{f}(x,y):= ((x \oplus a) \otimes y, 1 \otimes x \oplus (-1) \otimes y)^\top\) is a tropical polynomial function, it is tropical-linearly approximated as \[\begin{align} \boldsymbol{f}(x,y) \approx \begin{pmatrix} \varepsilon & a \\ 1 & -1 \end{pmatrix} \otimes \begin{pmatrix} x \\ y \end{pmatrix}. \end{align}\] Since the maximum eigenvalue of \(\begin{pmatrix} \varepsilon & a \\ 1 & -1 \end{pmatrix}\) is \(\max( (a+1)/2, -1)\), the fixed point \(\boldsymbol{\varepsilon}\) is asymptotically stable if \(a < -1\) and unstable if \(a > -1\).
Example 3. Let us define \[\begin{align} H_1(X,Y) &= X \otimes (X \oplus T \otimes F_1(X,Y)) \oslash (X \oplus T \otimes G_1(X,Y)), \\ H_2(X,Y) &= Y \otimes (Y \oplus T \otimes F_2(X,Y)) \oslash (Y \oplus T \otimes G_2(X,Y)), \end{align}\] where \(T\) is a constant, and consider a difference equation \[\begin{align} \begin{pmatrix} X^{(t+1)} \\ Y^{(t+1)} \end{pmatrix} = \begin{pmatrix} H_1(X^{(t)},Y^{(t)}) \\ H_2(X^{(t)},Y^{(t)}) \end{pmatrix}. \label{eq:example2} \end{align}\tag{23}\] This kind of system is derived through the tropical discretization of differential equations \[\begin{align} \begin{cases} \displaystyle \frac{dx}{dt} =f_1(x,y)-g_1(x,y), \\[7pt] \displaystyle \frac{dy}{dt} = f_2(x,y)-g_2(x,y). \end{cases} \end{align}\] See [5] for details on tropical discretization.
We assume that \(F_i(X,Y)\) and \(G_i(X,Y)\) converge to \(F_i(\varepsilon,\varepsilon)\) and \(G_i(\varepsilon,\varepsilon)\), respectively, for \(i=1,2\) as \((X,Y) \to (\varepsilon,\varepsilon)\). If \(\boldsymbol{\varepsilon}\) is a fixed point of 23 , then \(G_i(\varepsilon,\varepsilon) \neq \varepsilon\) for \(i=1,2\). The tropical derivatives at \(\boldsymbol{\varepsilon}\) are computed as \[\begin{align} D_{X,\boldsymbol{\varepsilon}}H_1(X,Y) &= F_1(\varepsilon,\varepsilon) \oslash G_1(\varepsilon,\varepsilon), \\ D_{Y,\boldsymbol{\varepsilon}}H_2(X,Y) &= F_2(\varepsilon,\varepsilon) \oslash G_2(\varepsilon,\varepsilon), \\ D_{Y,\boldsymbol{\varepsilon}}H_1(X,Y) &= D_{X,\boldsymbol{\varepsilon}}H_2(X,Y) = \varepsilon, \end{align}\] and \(H_1(X,Y)\) and \(H_2(X,Y)\) are tropical-linearly approximated as \[\begin{align} \begin{pmatrix} H_1(X,Y) \\ H_2(X,Y) \end{pmatrix} \approx \begin{pmatrix} F_1(\varepsilon,\varepsilon) \oslash G_1(\varepsilon,\varepsilon) & \varepsilon \\ \varepsilon & F_2(\varepsilon,\varepsilon) \oslash G_2(\varepsilon,\varepsilon) \end{pmatrix} \otimes \begin{pmatrix} X \\ Y \end{pmatrix}. \end{align}\] The fixed point \(\boldsymbol{\varepsilon}\) is asymptotically stable if both \(F_1(\varepsilon,\varepsilon) \oslash G_1(\varepsilon,\varepsilon)\) and \(F_2(\varepsilon,\varepsilon) \oslash G_2(\varepsilon,\varepsilon)\) are negative, and it is unstable if either of them is positive.
Example 4. Let us consider a discrete event system on \(n\) processors \(P_1, P_2, \dots, P_n\) that process different products. At each time step, a processor receives products from other processors and then processes their own products as many as possible, using one unit from each per unit of output. Let \(y_i^{(t)}\) be the cumulative number of products processed in \(P_i\) during time steps \(0,1,\dots,t\). If the processor \(P_i\) requires products from \(P_{j_1}, P_{j_2}, \dots, P_{j_r}\), the number of products processed in \(P_i\) up to times step \(t+1\) is \[\begin{align} y_i^{(t+1)} = \min_{k=1,2,\dots,r} (y_{j_k}^{(t)} - a_{i,j_k}(\boldsymbol{y}^{(t)})). \end{align}\] Here, \(a_{i,j_k}(\boldsymbol{y})\) represents changes in the product quantity due to other factors; when \(a_{i,j_k}(\boldsymbol{y})\) is positive, it corresponds to losses occurring during the process, whereas when \(a_{i,j_k}(\boldsymbol{y})\) is negative, it represents an external supply. By setting \(y_i^{(t)} = -x_i^{(t)}\) for \(i=1,2,\dots,n\), this min-plus system can be switched to a max-plus (tropical) model as \[\begin{align} \boldsymbol{x}^{(t)} = A(\boldsymbol{x}^{(t)}) \otimes \boldsymbol{x}^{(t)}. \end{align}\] If the limit \(A:= \lim_{\boldsymbol{x} \to \boldsymbol{\varepsilon}} A(\boldsymbol{x})\) exists and the maximum eigenvalue of \(A\) is negative, then the fixed point \(\boldsymbol{\varepsilon}\) is asymptotically stable. In terms of the min-plus model for \(\boldsymbol{y}^{(t)}\), the system operates continuously without encountering a deadlock when it starts from sufficiently large \(\boldsymbol{y}^{(0)}\).
In this study, we proposed a tropical linear approximation approach for the stability analysis of difference equations at the tropical origin, namely, \(\boldsymbol{\varepsilon}\). A natural question is how to expand this approach to any fixed points in \(\mathbb{R}_{\max}^n\), especially in \(\mathbb{R}^n\). This case is very different from the case where \(\boldsymbol{\varepsilon}\) is a fixed point.
Let us assume that \(\boldsymbol{p} = (p_1,p_2,\dots,p_n)^\top \in \mathbb{R}^n\) is a fixed point of 7 . If \(A \otimes \boldsymbol{x} \oplus \boldsymbol{b}\) is a tropical linear approximation of \(\boldsymbol{f}\) at \(\boldsymbol{p}\), then \(\boldsymbol{p} = A \otimes \boldsymbol{p} \oplus \boldsymbol{b}\) should be satisfied. This linear equation for \(A = (a_{i,j})\) and \(\boldsymbol{b} = (b_1,b_2,\dots,b_n)^\top\) can be solved as \[\begin{align} \begin{cases} a_{1,1} \leq 0 \\ a_{1,2} \leq p_1-p_2 \\ \qquad\vdots \\ a_{1,n} \leq p_1-p_n \\ b_1 \leq p_1 \end{cases},\; \begin{cases} a_{2,1} \leq p_2-p_1 \\ a_{2,2} \leq 0\\ \qquad\vdots \\ a_{2,n} \leq p_2-p_n \\ b_2 \leq p_2 \end{cases},\; \dots,\; \begin{cases} a_{n,1} \leq p_n-p_1 \\ a_{n,2} \leq p_n-p_2 \\ \qquad\vdots \\ a_{n,n} \leq 0\\ b_n \leq p_n \end{cases}, \label{eq:conclusion} \end{align}\tag{24}\] where at least one equality holds for each collection of inequalities. Moreover, the term \(a_{i,j} \otimes x_j\) contributes to evaluating \(A \otimes \boldsymbol{x} \oplus \boldsymbol{b}\) around \(\boldsymbol{p}\) only if \(a_{i,j} = p_i-p_j\). Hence, the tropical linear approximation is determined by the fixed point \(\boldsymbol{p}\) itself rather than the infinitesimal behaviour around \(\boldsymbol{p}\).
Furthermore, if a tropical linear difference equation \(\boldsymbol{x}^{(t+1)} = A \otimes \boldsymbol{x}^{(t)} \oplus \boldsymbol{b}\) has a fixed point \(\boldsymbol{p}\), then we have \[\begin{align} \boldsymbol{p} = A \otimes \boldsymbol{p} \oplus \bigoplus_{k=0}^m A^{\otimes k} \otimes \boldsymbol{b} \end{align}\] for any \(m \in \mathbb{Z}_{\geq 0}\) by using \(\boldsymbol{p} = A \otimes \boldsymbol{p} \oplus \boldsymbol{b}\) repeatedly. When \(\boldsymbol{p}\) and \(\boldsymbol{b}\) are finite vectors, the matrix sequence \(\{A^{\otimes k}\}_{k \in \mathbb{Z}_{\geq 0}}\) should be bounded from above. This implies that the maximum eigenvalue of \(A\) must be nonpositive. Therefore, the stability analysis based on the sign of the maximum eigenvalue would exhibit substantially different behavior. Nonetheless, it would be interesting to investigate how the behavior differs when the maximum eigenvalue is negative versus when it is zero. This is related to whether each inequality \(a_{i,j} \leq p_i-p_j\) in 24 is strict or not. Hence, the stability at the finite fixed point might be explained in terms of the tropical linearization matrix \(A\) as well, which is left for future study.
This work was supported by JSPS KAKENHI (Grant No. 22K13964).
The authors report there are no competing interests to declare.