Polynomial and Pseudopolynomial Procedures for Solving Interval Two-Sided (Max, Plus)-Linear Systems

Abstract

Max-plus algebra is the similarity of the classical linear algebra with two binary operations, maximum and addition. The notation Ax = Bx, where A, B are given (interval) matrices, represents (interval) two-sided (max, plus)-linear system. For the solvability of Ax = Bx, there are some pseudopolynomial algorithms, but a polynomial algorithm is still waiting for an appearance. The paper deals with the analysis of solvability of two-sided (max, plus)-linear equations with inexact (interval) data. The purpose of the paper is to get efficient necessary and sufficient conditions for solvability of the interval systems using the property of the solution set of the non-interval system Ax = Bx. The main contribution of the paper is a transformation of weak versions of solvability to either subeigenvector problems or to non-interval two-sided (max, plus)-linear systems and obtaining the equivalent polynomially checked conditions for the strong versions of solvability.

1. Introduction and Preliminaries

An algebraic structure in which addition is substituted by maximum and multiplication by addition is called max-plus algebra. The solvability of systems of linear equations is one of the crucial questions that are considered in max-plus algebra. Systems of (max, plus)-linear equations are used in the modeling and analysis of discrete dynamic systems and various versions of real-life optimizations.

Consider a generalization of discrete event dynamic systems ([1,2,3]) with m entities $E_1,\dots ,E_m$ producing entity outputs $O_1,\dots ,O_n$ (data, products, etc.) working in stages whereby each entity contributes to the completion of each entity output and works for all outputs simultaneously. The state of entity $E_i$ after some stage k is described by entry $x_i\left(k\right)$ of a vector $x\left(k\right)$, and the element $a_{ij}$ of a matrix A formulates the influence of the activity of $E_j$ in the previous stage on the activity of $E_i$ in the current stage whereby we want to complete the partial entity output $O_i$. Moreover, all entities must wait until their preceding entities finish their activity and necessary influence constraints, formally expressed as ${(A\otimes x\left(k\right))}_i={⨁}_j{a}_{ij}\otimes x_j\left(k\right)$. Further, similarly to in [2], suppose that m other entities $F_1,\dots ,F_m$ prepare partial entity outputs for entity outputs $U_1,\dots ,U_n$, whereby $b_{ij}$ and $y_j$, alike as above, encode the influence of the work and the state of the corresponding entity, respectively, obtaining ${(B\otimes x\left(k\right))}_i={⨁}_j{b}_{ij}\otimes x_j\left(k\right)$.

Consider a model with a synchronization condition: to find the states of all $2m$ entities so that each pair $(O_i,U_i)$ is completed at the same state. Algebraically, we must solve the two-sided max-plus system, $A\otimes x=B\otimes x$.

The study of properties of systems of two-sided (max, plus)-linear systems is important for many applications. If the matrix and vector entries are estimated incorrectly, then one of methods of restoring solvability is to substitute a matrix and vectors by interval matrix and interval vectors, respectively.

In this paper, we consider the properties of matrices and vectors with inexact (interval) entries and analyze several versions of the solvability of the interval systems with respect to quantifiers and their order. The goal of this paper is to present weak and strong versions of the solvability of $\mathit{A}\otimes \mathit{X}=\mathit{B}\otimes \mathit{X}$ and prove its necessary and sufficient conditions for vector X and matrices $\mathit{A},\mathit{B}$ with inexact (interval) entries. Moreover, some of the equivalent conditions of strong versions of solvability can be checked in a polynomial number of arithmetic operations. Systems of two-sided (max, plus)-linear equations $A\otimes x=B\otimes x$ have been studied by many authors [3,4,5,6,7,8,9,10,11,12,13,14,15,16,17]. The motivation for this research are papers [8,10]. Paper [8] studies six types of solutions of systems of two-sided (max, plus)-linear equations $\mathit{A}\otimes x=\mathit{B}\otimes x$ and suggests a method for computing the solution set of a two-sided (max, plus)-linear system. Notice that this paper generalizes the results obtained in [8].

Let us now give more details on the organization of the paper and on the results obtained there. The next section presents the notation and definitions of solvability of a two-sided max-plus system $A\otimes x=B\otimes x$ for $A\le B$. Section 2 and Section 3 deal with definitions and properties of subeigenvectors and two-sided max-plus systems. Section 4 is devoted to classification of interval solutions of interval two-sided max-plus systems and the characterization of the necessary and sufficient conditions for the strong and the weak versions of solvability. Based on the results, we also give a method for testing the equivalent conditions obtained in Theorems 13 and 16.

Denote the set of real numbers by $\mathbb{R}$ and the set of all natural numbers by $\mathbb{N}$. The symbol $\overline{\mathbb{R}}$ will stand for $\mathbb{R}\cup \{-\infty \}$. For two elements $a,b\in \overline{\mathbb{R}}$, we set $a\oplus b=max(a;b)$ and $a\otimes b=a+b$. Throughout the paper, we denote $-\infty$, the neutral element with respect to ⊕, by $\epsilon$ and the neutral element 0 with respect to ⊗, by e. For given natural numbers $n,m\in \mathbb{N}$, we use the notations $N=\{1,2,\dots ,n\}$ and $M=\{1,\dots ,m\}$. The matrix operations over $\mathbb{R}\cup \{-\infty \}$ are defined formally in the same manner (with respect to $\oplus ,\otimes$) as matrix operations over any field. The rth power of a matrix A is denoted by $A^r$.

Suppose that $n\ge 1,m\ge 1$ are given integers. The set of $n\times m$ matrices over $\overline{\mathbb{R}}$ is denoted by $\overline{\mathbb{R}}(n,m)$, especially the set of $n\times 1$ vectors over $\overline{\mathbb{R}}$ is denoted by $\overline{\mathbb{R}}\left(n\right)$. The triple $(\overline{\mathbb{R}},\oplus ,\otimes )$ is called max-plus algebra. If each entry of a matrix $A\in \overline{\mathbb{R}}(n,n)$ (a vector $x\in \overline{\mathbb{R}}\left(n\right)$) is equal to $\epsilon$, we shall denote this as $A=\epsilon$ ($x=\epsilon$).

For $A\in \mathbb{R}(m,n),C\in \mathbb{R}(m,n)$, we write $A\le C$ if $a_{ij}\le c_{ij}$ holds true for all $i,j\in N$. Similarly, for $x={(x_1,\dots ,x_n)}^T\in \mathbb{R}\left(n\right)$ and $y={(y_1,\dots ,y_n)}^T\in \mathbb{R}\left(n\right)$, we write $x\le y$ if $x_i\le y_i$ for each $i\in N$.

By digraph, we understand a pair $\mathcal{G}=(V_{\mathcal{G}},E_{\mathcal{G}})$, where $V_{\mathcal{G}}$ is a non-empty finite set, called the node set, and $E_{\mathcal{G}},E_{\mathcal{G}}\subseteq V_{\mathcal{G}}\times V_{\mathcal{G}}$ is called the arc set. A digraph ${\mathcal{G}}^{\prime }$ is a subdigraph of digraph $\mathcal{G}$, if $V_{{\mathcal{G}}^{\prime }}\subseteq V_{\mathcal{G}}$ and $E_{{\mathcal{G}}^{\prime }}\subseteq E_{\mathcal{G}}$. A walk in $\mathcal{G}$ is the sequence of nodes $W=(i_0,i_1,\dots ,i_l)$ such that $(i_{k-1},i_k)\in E_{\mathcal{G}}$ for all $k=1,2,\dots ,l$. The number $l\ge 0$ is called the length of W and denoted $l\left(W\right)$. If $i_0=i_l$, then W is a cycle of length l. A cycle is elementary if all nodes except the terminal node are distinct. A digraph is called strongly connected if any two distinct nodes of $\mathcal{G}$ are contained in a common cycle.

By a strongly connected component of a digraph $\mathcal{G}=(V_{\mathcal{G}},E_{\mathcal{G}})$, we mean a subdigraph $\mathcal{K}=(V_{\mathcal{K}},E_{\mathcal{K}})$, where the node set $V_{\mathcal{K}}\subseteq V_{\mathcal{G}}$ is such that any two distinct nodes $i,j\in V_{\mathcal{K}}$ are contained in a common cycle, $E_{\mathcal{K}}=E_{\mathcal{G}}\cap (V_{\mathcal{K}}\times V_{\mathcal{K}})$ and $V_{\mathcal{K}}$ is the maximal subset with this property. A strongly connected component $\mathcal{K}$ of a digraph is called non-trivial if there is a cycle of positive length in $\mathcal{K}$.

For a given matrix $A\in \overline{\mathbb{R}}(n,n)$, the weighted digraph $\mathcal{G}\left(A\right)$ associated with A is the digraph with the node set $V_{\mathcal{G}\left(A\right)}=N$ and the edge set $E_{\mathcal{G}}=\{(i,j)\in N\times N;a_{ij}\ne \epsilon \}$. If $\mathcal{G}=\mathcal{G}\left(A\right)$, then the weight of $W=(i_0,i_1,\dots i_l)$ is defined by $w\left(W\right)=a_{i_0{i}_1}+a_{i_1{i}_2}+\dots +a_{i_{l-1}{i}_l}.$ The cycle mean of cycle c is defined by $\overline{w}\left(c\right)=(a_{i_0{i}_1}+a_{i_1{i}_2}+\dots +a_{i_{l-1}{i}_0})/l\left(c\right)$ and the maximum cycle mean of A is defined as $\lambda \left(A\right)=\underset{c}{max}\overline{w}\left(c\right).$

$A\in \overline{\mathbb{R}}(n,n)$ is called irreducible if $\mathcal{G}\left(A\right)$ is strongly connected and reducible otherwise.

For a given matrix $A\in \overline{\mathbb{R}}(n,n)$, the number $\lambda \in \overline{\mathbb{R}}$ and the n-tuple $x\in \mathbb{R}\left(n\right),x\ne \epsilon$ are the so-called eigenvalue (subeigenvalue) and eigenvector (subeigenvector) of A, respectively, if

$$A\otimes x=\lambda \otimes x(A\otimes x\le \lambda \otimes x).$$

2. Subeigenvectors

The column span of a matrix A with columns $A_1,\dots ,A_n$ is defined $\{{\displaystyle \underset{i\in N}{⨁}}{\alpha }_i\otimes A_i;{\alpha }_1,\dots ,$${\alpha }_n\in \mathbb{R}\}$ and will be denoted by $span\left(A\right)$.

For a given $A\in \overline{\mathbb{R}}(n,n)$, $\lambda \in \overline{\mathbb{R}}$ denotes $A_{\lambda }={\lambda }^{-1}\otimes A$ and $A^{\ast }=I\oplus A\oplus A^2\oplus A^3\oplus \dots$, called the Kleene star.

An eigenspace $V(A,\lambda )$ is defined as the set of all eigenvectors of A with associated eigenvalue $\lambda$, i.e.,

$$V(A,\lambda )=\{x\in \overline{\mathbb{R}}\left(n\right)\backslash \left\{\epsilon \right\}:A\otimes x=\lambda \otimes x\},$$

and subeigenspace $V_{\ast }(A,\lambda )$ is defined as the set of all subeigenvectors of A with associated subeigenvalue $\lambda$, i.e.,

$$V_{\ast }(A,\lambda )=\{x\in \overline{\mathbb{R}}\left(n\right);A\otimes x\le \lambda \otimes x\}.$$

The set $\Lambda \left(A\right)=\{\lambda \in \overline{\mathbb{R}};V(A,\lambda )\ne \epsilon \}$ will be called the spectrum of A.

Any reducible matrix A can be transformed by simultaneous permutations of rows and columns to a Frobenius normal form

$$A^{\prime }=\left(\begin{array}{cccc}{A}_{11}& \epsilon & \dots & \epsilon \\ A_{21}& A_{22}& \dots & \epsilon \\ \ddots & \ddots & \ddots & \ddots \\ A_{r1}& A_{r2}& \dots & A_{rr}\end{array}\right),$$

where $A_{11},\dots ,A_{rr}$ are irreducible square submatrices of $A^{\prime }$ ([1,18]). $N_1,\dots ,N_r$ denote the corresponding partition subsets of the node set of $\mathcal{G}\left(A\right)$. The symbol $N_i\to N_j$ means that there is a directed path from $N_i$ to $N_j$ in a reduced digraph with nodes $N_1,N_2,\dots ,N_r$ and the arc set $\{(N_i,N_j);(\exists k\in N_i)(\exists s\in N_j)a_{ks}>\epsilon \}$.

The diagonal block $A_{jj}$ is called spectral if $\lambda \left(A_{jj}\right)=\underset{N_i\to N_j}{max}\lambda \left(A_{ii}\right)$, and we denote ${\lambda }_{min}=min\{\lambda \left(A_{ii}\right);A_{ii}spectral\}(=min\Lambda \left(A\right))$. For the more details see [1,18].

Theorem 1

([18]). Let $A\in \overline{\mathbb{R}}(n,n).$ Then $V_{\ast }(A,\lambda )\ne \left\{\epsilon \right\}$ if and only if $\lambda \ge {\lambda }_{min}$ and $V_{\ast }(A,\lambda )=span\left(G\right)$, where G is the matrix consisting of the columns $g_j$ of the matrix ${\left(A_{\lambda }\right)}^{\ast }$ with indices $j\in {\displaystyle \bigcup _{i\in I_{\ast }\left(\lambda \right)}}{N}_i$, where $I_{\ast }\left(\lambda \right)=\{i\in \{1,\dots ,r\};\lambda \left(A_{ii}\right)\le \lambda ,A_{ii}isspectral\}.$

Notice that the basis of $V_{\ast }(A,\lambda )\ne \left\{\epsilon \right\}$ can be found in $O\left(n^3\right)$ time [19].

3. Systems of Two-Sided (Max, Plus)-Linear Equations

In this section we consider the two-sided max-plus linear system $A\otimes x=B\otimes x$ for $A\le B$.

The set of solutions to the system $A\otimes x=B\otimes x$ will be denoted $S(A,B)$, that is,

$$S(A,B)=\{x\in \overline{\mathbb{R}}\left(n\right)\backslash \left\{\epsilon \right\};A\otimes x=B\otimes x\}$$

and put

$$M_i(A,B)=\{j\in N;a_{ij}=b_{ij}\}.$$

Lemma 1.

Suppose $A\in \overline{\mathbb{R}}(m,n)$, $B\in \overline{\mathbb{R}}(m,n)$ with $A\le B$. If $S(A,B)\ne \varnothing$, then $M_i(A,B)\ne \varnothing$ for any $i\in M.$

Proof. 

Suppose that there is $x\in \overline{\mathbb{R}}\left(n\right)$ such that $A\otimes x=B\otimes x$. Then for an arbitrary but fixed $i\in M$, there are $j,k\in N$ such that $a_{ij}\otimes x_j={(A\otimes x)}_i={(B\otimes x)}_i=b_{ik}\otimes x_k$. Then we get $a_{ij}\otimes x_j=b_{ik}\otimes x_k\ge b_{ij}\otimes x_j$ and hence $a_{ij}\ge b_{ij}$. According to the assumption $a_{ij}\le b_{ij}$, we obtain the equality $a_{ij}=b_{ij}$ and hence $j\in M_i(A,B)$. □

For $J=(j_1,\dots ,j_m)\in \mathcal{M}={\times }_{i\in M}{M}_i(A,B)$, put

$$N_k^J=\{\ell \in M;j_{\ell }=k\}\mathrm{for}\mathrm{any}k\in N$$

and define the matrix $C^J(A,B)=\left(c_{ij}^J\right)\in \overline{\mathbb{R}}(n,n)$, where

$$c_{\ell j}^J=\left\{\begin{array}{c}\underset{k\in N_{\ell }^J}{max}\{b_{kj}-b_{k\ell }\},\mathrm{for}\ell \ne j\hfill \\ \epsilon ,\mathrm{if}{N}_{\ell }^J=\varnothing \mathrm{or}\ell =j.\hfill \end{array}\right.$$

(1)

The matrix $C^J(A,B)$ will be written briefly as $C^J$.

Theorem 2.

Suppose $A,B\in \overline{\mathbb{R}}(m,n)$ and $A\le B$. Then $x\in S(A,B)$ if and only if there is $J\in \mathcal{M}$ such that $C^J(A,B)\otimes x\le x$.

Proof. 

Suppose that $A\le B$ and $J=(j_1,\dots ,j_m)\in \mathcal{M}$. Then x is an element of $S(A,B)$ if and only if

$$\begin{array}{cc}max\{a_{11}+x_1,\dots ,a_{1n}+x_n\}=max\{b_{11}+x_1,\dots ,b_{1n}+x_n\}=b_{1j_1}+x_{j_1}& \\ ⋮& \\ max\{a_{m1}+x_1,\dots ,a_{mn}+x_n\}=max\{b_{m1}+x_1,\dots ,b_{mn}+x_n\}=b_{1j_m}+x_{j_m}& \end{array}$$

(2)

Since $A\le B$ and $J=(j_1,\dots ,j_m)\in \mathcal{M}$, the system (2) is equivalent to

$$\begin{array}{cc}\underset{j\ne j_1}{max}\{b_{1j}+x_j\}\le b_{1j_1}+x_{j_1}& \\ ⋮& \iff \\ \underset{j\ne j_m}{max}\{b_{mj}+x_j\}\le b_{m{j}_m}+x_{j_m}& \end{array}\begin{array}{cc}\underset{j\ne j_1}{max}\{b_{1j}-b_{1j_1}+x_j\}\le x_{j_1}& \\ ⋮& \\ \underset{j\ne j_m}{max}\{b_{mj}-b_{m{j}_m}+x_j\}\le x_{j_m}& \end{array}$$

(3)

Observe that some elements of $J=(j_1,\dots ,j_m)\in \mathcal{M}$ can be equal. Denote the set $\{\ell \in M;j_{\ell }=k\}$ by $N_k^J$ for any $k\in N$. Now we can simplify (3) using $N_k^J$ in the equivalent system $C^J(A,B)\otimes x\le x$, where $C^J(A,B)=\left(c_{ij}^J\right)$ with

$$c_{\ell j}^J=\left\{\begin{array}{c}\underset{k\in N_{\ell }^J}{max}\{b_{kj}-b_{k\ell }\},\mathrm{for}\ell \ne j\hfill \\ \epsilon ,\mathrm{if}{N}_{\ell }^J=\varnothing \mathrm{or}\ell =j.\hfill \end{array}\right.$$

and the assertion follows. □

Thus, Theorem 2 turns the problem of solvability of the system $A\otimes x=B\otimes x$ into the problem of finding $J\in \mathcal{M}$ and a corresponding subeigenvector of $C^J(A,B)$.

Example 1.

Solve the system $A\otimes x=B\otimes x$, where matrices $A,B,A\le B$ have the forms

$$A=\left(\begin{array}{ccc}3& 4& 4\\ 6& 3& 1\\ 1& 5& 4\\ 3& 1& 3\end{array}\right),B=\left(\begin{array}{ccc}5& 4& 6\\ 6& 4& 7\\ 4& 5& 4\\ 3& 2& 4\end{array}\right).$$

Then we obtain $M_1(A,B)=\left\{2\right\},M_2(A,B)=\left\{1\right\},M_3(A,B)=\{2,3\},$$M_4(A,B)=\left\{1\right\}$, $J_1=(2,1,2,1)$, $J_2=(2,1,3,1)$ and $N_1^{J_1}=\{2,4\},$$N_2^{J_1}=\{1,3\}$ and $N_3^{J_1}=\varnothing .$ Similarly for $J_2=(2,1,3,1)$, we have $N_1^{J_2}=\{2,4\},$$N_2^{J_2}=\left\{1\right\}$ and $N_3^{J_2}=\left\{3\right\}.$ To solve the system $A\otimes x=B\otimes x$, we shall consider a solvability of two systems $A\otimes x=B\left(J_1\right)\otimes x$ and $A\otimes x=B\left(J_2\right)\otimes x$, where

$$B\left(J_1\right)=\left(\begin{array}{ccc}5& \mathbf{4}& 6\\ \mathbf{6}& 4& 7\\ 4& \mathbf{5}& 4\\ \mathbf{3}& 2& 4\end{array}\right),B\left(J_2\right)=\left(\begin{array}{ccc}5& \mathbf{4}& 6\\ \mathbf{6}& 4& 7\\ 4& 5& \mathbf{4}\\ \mathbf{3}& 2& 4\end{array}\right).$$

Case (i). System $A\otimes x=B\left(J_1\right)\otimes x$ is transformed into equivalent system $C^{J_1}\otimes x\le x$ as follows:

$$\begin{array}{cc}max\{3+x_1,4+x_2,4+x_3\}=max\{5+x_1,4+x_2,6+x_3\}=4+x_2& \\ max\{6+x_1,3+x_2,1+x_3\}=max\{6+x_1,4+x_2,7+x_3\}=6+x_1& \iff \\ max\{1+x_1,5+x_2,4+x_3\}=max\{4+x_1,5+x_2,4+x_3\}=5+x_2& \\ max\{3+x_1,1+x_2,3+x_3\}=max\{3+x_1,2+x_2,4+x_3\}=3+x_1\end{array}$$

$$\begin{array}{cc}max\{1+x_1,2+x_3\}\le x_2& \\ max\{-2+x_2,1+x_3\}\le x_1& \iff \\ max\{-1+x_1,-1+x_3\}\le x_2& \\ max\{-1+x_2,1+x_3\}\le x_1\end{array}\begin{array}{cc}max\{-1+x_2,1+x_3\}\le x_1& \\ max\{1+x_1,2+x_3\}\le x_2& \\ \end{array}$$

and in vector-matrix form

$$C^{J_1}\otimes x=\left(\begin{array}{ccc}\epsilon & -1& 1\\ 1& \epsilon & 2\\ \epsilon & \epsilon & \epsilon \end{array}\right)\otimes \left(\begin{array}{c}{x}_1\\ x_2\\ x_3\end{array}\right)\le \left(\begin{array}{c}{x}_1\\ x_2\\ x_3\end{array}\right).$$

To obtain the set of all solutions of the system $C^{J_1}\otimes x\le x$ we will use Theorem 1 and look for the set of subeigenvectors for the matrix $C^{J_1}$ with $\lambda =0$, i.e., $V_{\ast }(C^{J_1},0)$. Since $\lambda \left(C^{J_1}\right)={\lambda }_{min}=0$ the set $V_{\ast }(C^{J_1},0)\ne \varnothing$ and $V_{\ast }(C^{J_1},0)=span\left(G_1\right)$, where $G_1$ is the matrix consisting of the columns of ${\left(C^{J_1}\right)}_0^{\ast }.$ Thus, any solution of the system $C^{J_1}\otimes x\le x$ can be expressed as max-plus linear combination of the columns of $V_{\ast }(C^{J_1},0)=span\left(G_1\right)$ (one of solutions is $x={(1,2,0)}^T$), where

$$G_1={\left(C^{J_1}\right)}_0^{\ast }=\left(\begin{array}{ccc}0& -1& 1\\ 1& 0& 2\\ \epsilon & \epsilon & 0\end{array}\right).$$

Case (ii). $A\otimes x=B\left(J_2\right)\otimes x$ is transformed into equivalent system $C^{J_2}\otimes x\le x$ as follows:

$$\begin{array}{cc}max\{3+x_1,4+x_2,4+x_3\}=max\{5+x_1,4+x_2,6+x_3\}=4+x_2& \\ max\{6+x_1,3+x_2,1+x_3\}=max\{6+x_1,4+x_2,7+x_3\}=6+x_1\iff \\ max\{1+x_1,5+x_2,4+x_3\}=max\{4+x_1,5+x_2,4+x_3\}=4+x_3& \\ max\{3+x_1,1+x_2,3+x_3\}=max\{3+x_1,2+x_2,4+x_3\}=3+x_1\end{array}$$

$$\begin{array}{cc}max\{1+x_1,2+x_3\}\le x_2& \\ max\{-2+x_2,1+x_3\}\le x_1& \iff \\ max\{x_1,1+x_2\}\le x_3& \\ max\{-1+x_2,1+x_3\}\le x_1\end{array}\begin{array}{cc}max\{-1+x_2,1+x_3\}\le x_1& \\ max\{1+x_1,2+x_3\}\le x_2& \\ max\{x_1,1+x_2\}\le x_3& \end{array}$$

and in vector-matrix form

$$C^{J_2}\otimes x=\left(\begin{array}{ccc}\epsilon & -1& 1\\ 1& \epsilon & 2\\ 0& 1& \epsilon \end{array}\right)\otimes \left(\begin{array}{c}{x}_1\\ x_2\\ x_3\end{array}\right)\le \left(\begin{array}{c}{x}_1\\ x_2\\ x_3\end{array}\right),$$

whereby according to Theorem 1, the set $V_{\ast }(C^{J_2},0)=\varnothing$ since $\lambda \left(C^{J_2}\right)=3/2>0=\lambda$. We can conclude that x is a solution of $A\otimes x=B\otimes x$ if and only if $x\in V_{\ast }(C^{J_1},0)\cup V_{\ast }(C^{J_2},0)=span\left(G_1\right)$.

Theorem 3.

Suppose given $A\in \overline{\mathbb{R}}(m,n)$, $B\in \overline{\mathbb{R}}(m,n)$ with $A\le B$. Then $S(A,B)\ne \varnothing$ if and only if ${\displaystyle \bigcup _{J\in {\times }_{i\in M}{M}_i(A,B)}}{V}_{\ast }(C^J,0)\ne \epsilon$ and $M_i(A,B)\ne \varnothing$ for any $i\in M$.

Proof. 

The proof follows from Theorem 1, Lemma 1, and Theorem 2. □

Observe that

(i)

solvability of the system $A\otimes x=B\otimes x$ for $A\le B$ can be recognized in $k·O\left(n^3\right)$ time, where $k=|{\times }_{i\in M}{M}_i(A,B)|$ (k can be exponentially large),

(ii)

if $x\in V_{\ast }(C^J,0)$ for some $J\in {\times }_{i\in M}{M}_i(A,B)$, then x can be expressed as max-plus linear combination of basis of $V_{\ast }(C^J,0)\ne \left\{\epsilon \right\}$ which can be found in $O\left(n^3\right)$ time [19].

4. Interval Solutions

Similarly to [7,9,10,11,12,13,14,15,16,17,20,21,22], by an interval of $\overline{\mathbb{R}}(m,n)$, we mean a subset of $\overline{\mathbb{R}}(m,n)$ of the form $\mathit{Y}=\left({\mathit{y}}_{ij}\right)$ for $i\in M,j\in N$, where each ${\mathit{y}}_{ij}$ is an arbitrary interval belonging to $\overline{\mathbb{R}}$. For each $i,j$ we denote ${\underline{y}}_{ij}:=inf{\mathit{y}}_{ij}$ and ${\overline{y}}_{ij}=sup{\mathit{y}}_{ij}$. Then, we also have $\underline{Y}:=\left({\underline{y}}_{ij}\right)=inf\mathit{Y}$ and $\overline{Y}:=\left({\overline{y}}_{ij}\right)=sup\mathit{Y}$. A set $\mathit{Y}=\left({\mathit{y}}_{ij}\right)$ for $i\in M,j\in N$ a subset of $\overline{\mathbb{R}}(m,n)$, is called an interval matrix (a interval vector, if $n=1,\mathit{Y}=\left({\mathit{y}}_i\right)$) if it is of the form $\mathit{Y}=\left({\mathit{y}}_{ij}\right)$ for ${\mathit{y}}_{ij}$ nonempty subsets of $\overline{\mathbb{R}}$ taking any of the following four forms:

$$[{\underline{y}}_{ij},{\overline{y}}_{ij}],({\underline{y}}_{ij},{\overline{y}}_{ij}),({\underline{y}}_{ij},{\overline{y}}_{ij}],[{\underline{y}}_{ij},{\overline{y}}_{ij})$$

$$([{\underline{y}}_i,{\overline{y}}_i],({\underline{y}}_i,{\overline{y}}_i),({\underline{y}}_i,{\overline{y}}_i],[{\underline{y}}_i,{\overline{y}}_i)).$$

Now we can rewrite an interval vector with bounds $\underline{x},\overline{x}\in \overline{\mathbb{R}}\left(n\right)$ and interval matrices with bounds $\underline{A},\overline{A}\in \overline{\mathbb{R}}(m,n),\underline{B},\overline{B}\in \overline{\mathbb{R}}(m,n)$ as follows

$$\mathit{X}=[\underline{x},\overline{x}]=\left\{x\in \overline{\mathbb{R}}\left(n\right);\underline{x}\le x\le \overline{x}\right\},$$

$$\mathit{A}=[\underline{A},\overline{A}]=\left\{A\in \overline{\mathbb{R}}(m,n);\underline{A}\le A\le \overline{A}\right\},$$

$$\mathit{B}=[\underline{B},\overline{B}]=\left\{B\in \overline{\mathbb{R}}(m,n);\underline{B}\le B\le \overline{B}\right\}.$$

We will consider the following various versions of interval solutions of the system

$$\mathit{A}\otimes \mathit{X}=\mathit{B}\otimes \mathit{X},$$

(4)

depending on the used quantifiers and their order, where the aim is either to suggest a polynomial method for its solvability or to transform it into known max-plus linear systems of equations and/or inequalities.

Definition 1.

If A, B and X are given, then X is called weak

• XEA-solution of (4) if $(\exists x\in \mathit{X})(\exists A\in \mathit{A})(\forall B\in \mathit{B})A\otimes x=B\otimes x,$
• EAX-solution of (4) if $(\exists A\in \mathit{A})(\forall B\in \mathit{B})(\exists x\in \mathit{X})A\otimes x=B\otimes x$

and X is called strong

• XEA-solution of (4) if $(\forall x\in \mathit{X})(\exists A\in \mathit{A})(\forall B\in \mathit{B})A\otimes x=B\otimes x,$
• EXE-solution of (4) if $(\exists A\in \mathit{A})(\forall x\in \mathit{X})(\exists B\in \mathit{B})A\otimes x=B\otimes x.$

Notice that the denotation-weak XEA-solution corresponds with quantifiers and their order as follows: weak corresponds with the existence quantifier of X, E corresponds with the existence quantifier of A, and A corresponds with the forall quantifier of B. Similarly, a strong XEA-solution means that strong corresponds with the forall quantifier of X, E corresponds with existence quantifier of A and A corresponds with the forall quantifier of B.

For given indices $i\in M,j\in N$, we define matrix ${\tilde{A}}^{\left(ij\right)}\in \overline{\mathbb{R}}(m,n)$ and vector ${\tilde{x}}^{\left(i\right)}\in \overline{\mathbb{R}}\left(n\right)$ by putting for every $k\in M,l\in N$

$${\tilde{a}}_{kl}^{\left(ij\right)}=\left\{\begin{array}{cc}{\overline{a}}_{ij},\hfill & \mathrm{for}k=i,l=j\hfill \\ {\underline{a}}_{kl},\hfill & \mathrm{otherwise}\hfill \end{array}\right.,{\tilde{x}}_k^{\left(i\right)}=\left\{\begin{array}{cc}{\overline{x}}_i,\hfill & \mathrm{for}k=i\hfill \\ {\underline{x}}_k,\hfill & \mathrm{otherwise}\hfill \end{array}\right..$$

Lemma 2

([23]). Suppose $x\in \overline{\mathbb{R}}\left(n\right)$ and $A\in \overline{\mathbb{R}}(m,n)$. Then

(i) 

$x\in \mathit{X}$ if and only if $x={\displaystyle \underset{i\in N}{⨁}}{\gamma }_i\otimes {\tilde{x}}^{\left(i\right)}$ for some values ${\gamma }_i\in \mathbb{R}$ with ${\underline{x}}_i-{\overline{x}}_i\le {\gamma }_i\le 0$,

(ii) 

$A\in \mathit{A}$ if and only if $A={\displaystyle \underset{i\in M,j\in N}{⨁}}{\alpha }_{ij}\otimes {\tilde{A}}^{\left(ij\right)}$ for some values ${\alpha }_{ij}\in \mathbb{R}$ with ${\underline{a}}_{ij}-{\overline{a}}_{ij}\le {\alpha }_{ij}\le 0$.

Lemma 3.

Suppose A, B and $x\in \mathit{X}$. Then the following equivalences hold true:

(i) 

If $A\in \mathit{A}$, $B\in \mathit{B}$, then $(\forall x\in \mathit{X})A\otimes x=B\otimes x$ if and only if $(\forall k\in N)A\otimes {\tilde{x}}^{\left(k\right)}=B\otimes {\tilde{x}}^{\left(k\right)}$.

(ii) 

If $B\in \mathit{B}$, then $(\forall A\in \mathit{A})A\otimes x=B\otimes x$ if and only if $(\forall i\in M,j\in N){\tilde{A}}^{\left(ij\right)}\otimes x=B\otimes x.$

(iii) 

If $A\in \mathit{A}$, then $(\forall B\in \mathit{B})A\otimes x=B\otimes x$ if and only if $(\forall i\in M,j\in N)A\otimes x={\tilde{B}}^{\left(ij\right)}\otimes x.$

(iv) 

$(\forall A\in \mathit{A})(\forall B\in \mathit{B})A\otimes x=B\otimes x$ if and only if $(\forall j,r\in M,k,s\in N)A^{\left(ij\right)}\otimes x=B^{\left(rs\right)}\otimes x.$

Proof. 

(i) Suppose that $A\in \mathit{A}$, $B\in \mathit{B}$, $x\in \mathit{X}$ and $A\otimes {\tilde{x}}^{\left(k\right)}=B\otimes {\tilde{x}}^{\left(k\right)}$ holds for any $k\in N$. Then in view of Lemma 2 (i) we get $x={⨁}_{k\in N}{\gamma }_k\otimes {\tilde{x}}^{\left(k\right)}.$ Therefore,

$$A\otimes x=A\otimes \underset{k\in N}{⨁}{\gamma }_k\otimes {\tilde{x}}^{\left(k\right)}=\underset{k\in N}{⨁}{\gamma }_k\otimes (A\otimes {\tilde{x}}^{\left(k\right)})=$$

$$\underset{k\in N}{⨁}{\gamma }_k\otimes (B\otimes {\tilde{x}}^{\left(k\right)})=B\otimes \underset{k\in N}{⨁}{\gamma }_k\otimes {\tilde{x}}^{\left(k\right)}=B\otimes x.$$

The reverse implication trivially follows.

(ii) Suppose that there are $A\in \mathit{A}$ and $i\in M$ such that ${(A\otimes x)}_i\ne {(B\otimes x)}_i$. Consider two cases:

• If ${(A\otimes x)}_i>{(B\otimes x)}_i$, then there is $s\in N$ such that

  $$a_{is}\otimes x_s=\underset{j\in N}{⨁}{a}_{ij}\otimes x_j>\underset{j\in N}{⨁}{b}_{ij}\otimes x_j.$$

  Then for the generator ${\tilde{A}}^{\left(is\right)}$, we obtain

  $${({\tilde{A}}^{\left(is\right)}\otimes x)}_i\ge {\tilde{a}}_{is}^{\left(is\right)}\otimes x_s={\overline{a}}_{is}\otimes x_s\ge a_{is}\otimes x_s>{(B\otimes x)}_i.$$
• If ${(A\otimes x)}_i<{(B\otimes x)}_i$, then for the generator ${\tilde{A}}^{\left(ks\right)}$, $k\in M$, $k\ne i$, we obtain

  $$\underset{j\in N}{⨁}{b}_{ij}\otimes x_j>\underset{j\in N}{⨁}{a}_{ij}\otimes x_j\ge \underset{j\in N}{⨁}{\underline{a}}_{ij}\otimes x_j={({\tilde{A}}^{\left(ks\right)}\otimes x)}_i.$$

  We have shown that there are $k\in M,j\in N$ and $i\in M$ such that ${({\tilde{A}}^{\left(ks\right)}\otimes x)}_i\ne {(B\otimes x)}_i.$ The reverse implication trivially follows.

(iii) The proof is analogical as the proof of (ii) after exchanging A to B.

(iv) Suppose that there are $A\in \mathit{A}$, $B\in \mathit{B}$, and $i\in N$ such that ${(A\otimes x)}_i\ne {(B\otimes x)}_i$. Consider two cases:

• ${(A\otimes x)}_i>{(B\otimes x)}_i$. Thus, there is $s,r\in N$ such that

  $$a_{is}\otimes x_s=\underset{j\in N}{⨁}{a}_{ij}\otimes x_j>\underset{j\in N}{⨁}{b}_{ij}\otimes x_j=b_{ir}\otimes x_r.$$

  Then for the generators ${\tilde{A}}^{\left(is\right)}$ and ${\tilde{B}}^{\left(ks\right)}$, $k\ne i$, we obtain

  $${({\tilde{A}}^{\left(is\right)}\otimes x)}_i\ge {\tilde{a}}_{is}^{\left(is\right)}\otimes x_s={\overline{a}}_{is}\otimes x_s\ge a_{is}\otimes x_s>$$

  $$\underset{j\in N}{⨁}{b}_{ij}\otimes x_j\ge \underset{j\in N}{⨁}{\underline{b}}_{ij}\otimes x_j={(B^{\left(ks\right)}\otimes x)}_i.$$
• ${(A\otimes x)}_i<{(B\otimes x)}_i$. The proof of this case is analogical to the proof of the case (iv) 1. We showed that there are $j,r\in M,k,s\in N$, and $i\in M$ such that ${({\tilde{A}}^{\left(jk\right)}\otimes x)}_i\ne {({\tilde{B}}^{\left(rs\right)}\otimes x)}_i.$ The reverse implication trivially follows. □

Theorem 4

([8]). Suppose A, B, and $x\in \mathit{X}$.

(i) 

$(\exists A\in \mathit{A})(\exists B\in \mathit{B})A\otimes x=B\otimes x$ if and only if $\underline{A}\otimes x\le \overline{B}\otimes x$ and $\overline{A}\otimes x\ge \underline{B}\otimes x.$

(ii) 

$(\forall A\in \mathit{A})(\forall B\in \mathit{B})A\otimes x=B\otimes x$ if and only if $\underline{A}\otimes x=\overline{B}\otimes x$ and $\overline{A}\otimes x=\underline{B}\otimes x.$

(iii) 

$(\forall A\in \mathit{A})(\exists B\in \mathit{B})A\otimes x=B\otimes x$ if and only if $\underline{A}\otimes x\ge \underline{B}\otimes x$ and $\overline{A}\otimes x\le \overline{B}\otimes x.$

Theorem 5

([24]). Suppose $A\in \overline{\mathbb{R}}(m,n)$ and $b\in \overline{\mathbb{R}}\left(m\right)$. Then the system $A\otimes x=b$ is solvable if and only if $x^{\ast }(A,b)\in \overline{\mathbb{R}}\left(n\right)$ is its solution, where $x_j^{\ast }(A,b)=\underset{i\in M}{min}\{b_i-a_{ij}\}$ for $j\in N$.

Theorem 6

([25]). Suppose $B,C\in \overline{\mathbb{R}}(m,n)$ and $b,c\in \overline{\mathbb{R}}\left(m\right)$. Then the system of inequalities $B\otimes x\le b,C\otimes x\ge c$ has a solution if and only if $C\otimes x^{\ast }(B,b)\ge c$.

Notice that the solvability of $C\otimes x^{\ast }(B,b)\ge c$ can be recognized in $O\left(mn\right)$ time.

4.1. Weak XEA-Solution

Theorem 7.

Suppose A, B, and X. Then X is a weak XEA-solution of $\mathit{A}\otimes \mathit{X}=\mathit{B}\otimes \mathit{X}$ if and only if

$$(\exists x\in \mathit{X})(\exists A\in \mathit{A})A\otimes x=\underline{B}\otimes x=\overline{B}\otimes x.$$

(5)

Proof. 

Suppose that there are $x\in \mathit{X}$ and $A\in \mathit{A}$ such that $A\otimes x=\underline{B}\otimes x\mathrm{and}A\otimes x=\overline{B}\otimes x.$ The implication follows from the formula

$$A\otimes x=\underline{B}\otimes x\le B\otimes x\le \overline{B}\otimes x=A\otimes x.$$

The reverse implication trivially follows. □

The product $A\otimes x$ can be expressed as a max-plus linear combination of generators of A and X according to Lemma 2, i.e., $A={\displaystyle \underset{i\in M,j\in N}{⨁}}{\alpha }_{ij}\otimes {\tilde{A}}^{\left(ij\right)}$, $x={\displaystyle \underset{i\in N}{⨁}}{\gamma }_k\otimes {\tilde{x}}^{\left(k\right)}$. After a matrix-vector multiplication

$$A\otimes x={\displaystyle \underset{i\in M,j\in N}{⨁}}{\alpha }_{ij}\otimes {\tilde{A}}^{\left(ij\right)}\otimes {\displaystyle \underset{k\in N}{⨁}}{\gamma }_k\otimes {\tilde{x}}^{\left(k\right)}={\displaystyle \underset{i\in M,j\in N}{⨁}}{\displaystyle \underset{k\in N}{⨁}}{\alpha }_{ij}\otimes {\gamma }_k\otimes {\tilde{A}}^{\left(ij\right)}\otimes {\tilde{x}}^{\left(k\right)}$$

we obtain a combination of coefficients ${\gamma }_k$ with ${\alpha }_{ij}$, or in others words, in (5), we get a quadratic part of the equality which we do not know to solve.

Theorem 8.

Suppose given A, B, and X. Then X is a weak XEA-solution of $\mathit{A}\otimes \mathit{X}=\mathit{B}\otimes \mathit{X}$ if and only if

$$(\exists x\in \bigcup _{J\in \mathcal{M}}{V}_{\ast }(C^J,0))(\exists A\in A)A\otimes x=\underline{B}\otimes x.$$

(6)

Proof. 

The proof follows from Theorem 7. □

Observe that according to Theorem 4 (i), the Formula (6) can be rewritten into the next form

$$(\exists x\in \bigcup _{J\in \mathcal{M}}{V}_{\ast }(C^J,0))\underline{A}\otimes x\le \underline{B}\otimes x\le \overline{A}\otimes x.$$

(7)

Suppose that the set of vectors $\{c_1^J,\dots ,c_k^J\}$ is a basis of $V_{\ast }(C^J,0)$ for an arbitrary but fixed $J\in \mathcal{M}={\times }_{j\in M}{M}_j(A,B)$. Then any vector $x\in V_{\ast }(C^J,0)$ can be expressed as a max-plus linear combination of vectors from $\{c_1^J,\dots ,c_k^J\}$, i.e., $x=\underset{i=1}{\overset{k}{⨁}}{\delta }_i\otimes c_i^J$, ${\delta }_i\in \mathbb{R}$. Now we can reformulate the last theorem.

Theorem 9.

Suppose given A, B, and X. Then X is a weak XEA-solution of $\mathit{A}\otimes \mathit{X}=\mathit{B}\otimes \mathit{X}$ if and only if there are $J\in \mathcal{M}$ and $\delta ={({\delta }_1,\dots ,{\delta }_k)}^T\in \mathbb{R}\left(k\right)$ such that

$$\underline{A}\otimes \underset{i=1}{\overset{k}{⨁}}{\delta }_i\otimes c_i^J\le \underline{B}\otimes \underset{i=1}{\overset{k}{⨁}}{\delta }_i\otimes c_i^J\le \overline{A}\otimes \underset{i=1}{\overset{k}{⨁}}{\delta }_i\otimes c_i^J,$$

(8)

where the set of vectors $\{c_1^J,\dots ,c_k^J\}$ is a basis of $V_{\ast }(C^J,0)$.

Proof. 

The proof follows from Theorem 8. □

Observe that (8) can be expressed in the following form

$$\underset{i=1}{\overset{k}{⨁}}\underline{A}\otimes c_i^J\otimes {\delta }_i\le \underset{i=1}{\overset{k}{⨁}}\underline{B}\otimes c_i^J\otimes {\delta }_i$$

(9)

$$\underset{i=1}{\overset{k}{⨁}}\underline{B}\otimes c_i^J\otimes {\delta }_i\le \underset{i=1}{\overset{k}{⨁}}\overline{A}\otimes c_i^J\otimes {\delta }_i,$$

(10)

or as the matrix-vector product

$$\left(\begin{array}{ccc}\underline{A}\otimes c_1^J& \dots & \underline{A}\otimes c_k^J\\ \underline{B}\otimes c_1^J& \dots & \underline{B}\otimes c_k^J\end{array}\right)\otimes \delta \le \left(\begin{array}{ccc}\underline{B}\otimes c_1^J& \dots & \underline{B}\otimes c_k^J\\ \overline{A}\otimes c_1^J& \dots & \overline{A}\otimes c_k^J\end{array}\right)\otimes \delta$$

(11)

and we get a hint for how to decide whether X is a weak XEA-solution of $\mathit{A}\otimes \mathit{X}=\mathit{B}\otimes \mathit{X}$. It suffices to find $J\in \mathcal{M}$ for a polynomial-obtained basis of $V_{\ast }(C^J,0)$ and then to find a solution $\delta$ of (11). The solvability of $A\otimes x=B\otimes x$ is polynomially equivalent to solving a mean-payoff game [26]. Moreover, there are efficient pseudopolynomial algorithms for solving a mean-payoff game but a polynomial algorithm for the solvability of the system $A\otimes x=B\otimes x$ ($A\otimes x\le B\otimes x$) is waiting for an appearance ([8,26]).

4.2. Weak EAX-Solution

Theorem 10.

Suppose A, B, and X. Then X is a weak EAX-solution of $\mathit{A}\otimes \mathit{X}=\mathit{B}\otimes \mathit{X}$ if and only if

$$(\exists A\in \mathit{A})(\forall i\in N,j\in M)(\exists x\in \mathit{X})A\otimes x=B^{\left(kl\right)}\otimes x.$$

Proof. 

The proof follows from Lemma 3 (iii). □

Notice that we are able neither to suggest a transformation of Theorem 10 based on the solvability of the equality $A\otimes x=B^{\left(kl\right)}\otimes x$ into a non-quadratic version, similarly to Theorem 8, nor to prove NP-hardness of this problem.

4.3. Strong XEA-Solution

Theorem 11.

Suppose A, B, and X. Then X is a strong XEA-solution of $\mathit{A}\otimes \mathit{X}=\mathit{B}\otimes \mathit{X}$ if and only if

$$(\forall k\in N)(\exists A\in \mathit{A})(\forall B\in \mathit{B})A\otimes {\tilde{x}}^{\left(k\right)}=B\otimes {\tilde{x}}^{\left(k\right)}.$$

Proof. 

Suppose that there is $x\in \mathit{X}$ such that for an arbitrary but fixed $A\in \mathit{A}$ there are $B\in \mathit{B}$ and $i\in M$ such that ${(A\otimes x)}_i\ne {(B\otimes x)}_i$. We shall show that there is $k\in N$ such that for an arbitrary $A\in \mathit{A}$ there are $B\in \mathit{B}$ and $i\in M$ such that ${(A\otimes {\tilde{x}}^{\left(k\right)})}_i\ne {(B\otimes {\tilde{x}}^{\left(k\right)})}_i$. By the assumption and the proof of Lemma 3 (i), the implication follows.

The reverse implication trivially results. □

Theorem 12.

Suppose given A, B, and X. Then X is a strong XEA-solution of $\mathit{A}\otimes \mathit{X}=\mathit{B}\otimes \mathit{X}$ if and only if

$$(\forall k\in N)(\exists A\in \mathit{A})A\otimes {\tilde{x}}^{\left(k\right)}=\underline{B}\otimes {\tilde{x}}^{\left(k\right)}=\overline{B}\otimes {\tilde{x}}^{\left(k\right)}.$$

Proof. 

At first, we show that X is a strong XEA-solution of $\mathit{A}\otimes \mathit{X}=\mathit{B}\otimes \mathit{X}$ if and only if $(\forall x\in \mathit{X})(\exists A\in \mathit{A})\underline{B}\otimes x=A\otimes x=\overline{B}\otimes x.$ Let $x\in \mathit{X}$ be such that there is $A\in \mathit{A}$ with $A\otimes x=\underline{B}\otimes x\mathrm{and}A\otimes x=\overline{B}\otimes x.$ Then, by monotonicity of operations ⊕ and ⊗, we have $A\otimes x=\underline{B}\otimes x\le B\otimes x\le \overline{B}\otimes x=A\otimes x.$ The reverse implication trivially follows. Hence, the proof follows from Theorem 11. □

For each $k\in N$, define vectors $\tilde{C}\left(k\right)\in \overline{\mathbb{R}}(m+mn)$, $\tilde{D}\left(k\right)\in \overline{\mathbb{R}}(m+mn)$, and the matrix $\tilde{E}\left(k\right)\in \mathbb{R}(m+mn,mn)$ as follows:

$$\tilde{C}\left(k\right)=\left(\begin{array}{c}\underline{B}\otimes {\tilde{x}}^{\left(k\right)}\\ {\underline{a}}_{11}-{\overline{a}}_{11}\\ ⋮\\ {\underline{a}}_{mn}-{\overline{a}}_{mn}\end{array}\right),\tilde{D}\left(k\right)=\left(\begin{array}{c}\underline{B}\otimes {\tilde{x}}^{\left(k\right)}\\ 0\\ ⋮\\ 0\end{array}\right),$$

(12)

$$\tilde{E}\left(k\right)=\left(\begin{array}{cccc}{\tilde{A}}^{\left(11\right)}\otimes {\tilde{x}}^{\left(k\right)}& {\tilde{A}}^{\left(12\right)}\otimes {\tilde{x}}^{\left(k\right)}& \dots & {\tilde{A}}^{\left(mn\right)}\otimes {\tilde{x}}^{\left(k\right)}\\ 0& \epsilon & \dots & \epsilon \\ ⋮\\ \epsilon & \dots & \epsilon & 0\end{array}\right).$$

(13)

Consider max-plus linear system of inequalities

$$\begin{array}{c}\tilde{E}\left(k\right)\otimes y\left(k\right)\le \tilde{D}\left(k\right)\\ \tilde{E}\left(k\right)\otimes y\left(k\right)\ge \tilde{C}\left(k\right)\end{array}$$

(14)

where the vector $y\left(k\right)\in \mathbb{R}\left(mn\right)$ consists of the variables $y_{ij}\in \mathbb{R}$.

Theorem 13.

Suppose given A, B and X. Then X is a strong XEA-solution of $\mathit{A}\otimes \mathit{X}=\mathit{B}\otimes \mathit{X}$ if and only if $\underline{B}\otimes {\tilde{x}}^{\left(k\right)}=\overline{B}\otimes {\tilde{x}}^{\left(k\right)}$ and the max-plus linear system of inequalities (14) is solvable for any $k\in N$.

Proof. 

Suppose that $k\in N$ is arbitrary but fixed, $\underline{B}\otimes {\tilde{x}}^{\left(k\right)}=\overline{B}\otimes {\tilde{x}}^{\left(k\right)}$ and y is a solution of the linear system of inequalities (14) satisfying the condition ${\underline{a}}_{ij}-{\overline{a}}_{ij}\le y_{ij}\le 0,\mathrm{for} \mathrm{every}i\in M,j\in N$. Consider the matrix $A={⨁}_{i\in M,j\in N}{y}_{ij}\otimes {\tilde{A}}^{\left(ij\right)}\in [\underline{A},\overline{A}]$.

From the inequalities $\tilde{E}\left(k\right)\otimes y\left(k\right)\le \tilde{D}\left(k\right),\tilde{E}\left(k\right)\otimes y\left(k\right)\ge \tilde{C}\left(k\right)$, we have the following block inequalities

$$\begin{array}{cc}\hfill \underset{j\in M,l\in N}{⨁}\left({\tilde{A}}^{\left(jl\right)}\otimes {\tilde{x}}^{\left(k\right)}\right)\otimes y_{jl}& \ge \underline{B}\otimes {\tilde{x}}^{\left(k\right)}\iff \hfill \\ \hfill \underset{j\in M,l\in N}{⨁}\left(y_{jl}\otimes {\tilde{A}}^{\left(jl\right)}\right)\otimes {\tilde{x}}^{\left(k\right)}& \ge \underline{B}\otimes {\tilde{x}}^{\left(k\right)}\iff A\otimes {\tilde{x}}^{\left(k\right)}\ge \underline{B}\otimes {\tilde{x}}^{\left(k\right)}\hfill \end{array}$$

and

$$\begin{array}{cc}\hfill \underset{j\in M,l\in N}{⨁}\left({\tilde{A}}^{\left(jl\right)}\otimes {\tilde{x}}^{\left(k\right)}\right)\otimes y_{jl}& \le \underline{B}\otimes {\tilde{x}}^{\left(k\right)}\iff \hfill \\ \hfill \underset{j\in M,l\in N}{⨁}\left(y_{jl}\otimes {\tilde{A}}^{\left(jl\right)}\right)\otimes {\tilde{x}}^{\left(k\right)}& \le \underline{B}\otimes {\tilde{x}}^{\left(k\right)}\iff A\otimes {\tilde{x}}^{\left(k\right)}\le \underline{B}\otimes {\tilde{x}}^{\left(k\right)}.\hfill \end{array}$$

Thus, in view of Theorem 12, X is a strong XEA-solution of $\mathit{A}\otimes \mathit{X}=\mathit{B}\otimes \mathit{X}$.

For the converse implication, assume that X is a strong XEA-solution of $\mathit{A}\otimes \mathit{X}=\mathit{B}\otimes \mathit{X}$, i.e., that for each $x\in [\underline{x},\overline{x}])$, there exists $A\in \mathit{A}$ such that for any $B\in [\underline{B},\overline{B}])$, the inequality $A\otimes x=B\otimes x$ holds true. By Theorem 12 and Lemma 2 (ii), for any $k\in N$ there exist coefficients ${\alpha }_{ij}\in \mathbb{R}$, $i\in M,j\in N$ such that $A={⨁}_{i\in M,j\in N}{\alpha }_{ij}\otimes {\tilde{A}}^{\left(ij\right)}$ and ${\underline{a}}_{ij}-{\overline{a}}_{ij}\le {\alpha }_{ij}\le 0$. Then $y\left(k\right)\in \mathbb{R}(mn,1)$, where $y_{ij}={\alpha }_{ij}$ for any $i\in M,j\in N$, satisfies the inequalities $\tilde{E}\left(k\right)\otimes y\left(k\right)\le \tilde{D}\left(k\right),\tilde{E}\left(k\right)\otimes y\left(k\right)\ge \tilde{C}\left(k\right)$. □

4.4. Strong EXE-Solution

Theorem 14.

Suppose $A\in \mathit{A}$, B and X. Then for each $x\in \mathit{X}$, there is $B\in \mathit{B}$ such that $A\otimes x=B\otimes x$ if and only if for each $k\in N$ the inequalities $\underline{B}\otimes {\tilde{x}}^{\left(k\right)}\le A\otimes {\tilde{x}}^{\left(k\right)}\le \overline{B}\otimes {\tilde{x}}^{\left(k\right)}$ hold true.

Proof. 

The proof follows from Lemma 3 (i) and Theorem 4 (i). □

Theorem 15.

Suppose A, B, and X. Then X is a strong EXE-solution of $\mathit{A}\otimes \mathit{X}=\mathit{B}\otimes \mathit{X}$ if and only if there is $A\in \mathit{A}$ such that $\underline{B}\otimes {\tilde{x}}^{\left(k\right)}\le A\otimes {\tilde{x}}^{\left(k\right)}\le \overline{B}\otimes {\tilde{x}}^{\left(k\right)}$.

Proof. 

The proof follows from Theorem 14. □

To compute $A\in \mathit{A}$ in Theorem 15, define vectors $\tilde{C}\in \overline{\mathbb{R}}\left(2mn\right)$, $\tilde{D}\in \overline{\mathbb{R}}\left(2mn\right)$ and the matrix $\tilde{E}\in \mathbb{R}(2mn,mn)$ as follows:

$$\tilde{C}=\left(\begin{array}{c}\underline{B}\otimes {\tilde{x}}^{\left(1\right)}\\ ⋮\\ \underline{B}\otimes {\tilde{x}}^{\left(n\right)}\\ {\underline{a}}_{11}-{\overline{a}}_{11}\\ ⋮\\ {\underline{a}}_{mn}-{\overline{a}}_{mn}\end{array}\right),\tilde{D}=\left(\begin{array}{c}\overline{B}\otimes {\tilde{x}}^{\left(1\right)}\\ ⋮\\ \overline{B}\otimes {\tilde{x}}^{\left(n\right)}\\ 0\\ ⋮\\ 0\end{array}\right),$$

(15)

$$\tilde{E}\left(\mathit{A}\right)=\left(\begin{array}{cccc}{\tilde{A}}^{\left(11\right)}\otimes {\tilde{x}}^{\left(1\right)}& {\tilde{A}}^{\left(12\right)}\otimes {\tilde{x}}^{\left(1\right)}& \dots & {\tilde{A}}^{\left(mn\right)}\otimes {\tilde{x}}^{\left(1\right)}\\ ⋮\\ {\tilde{A}}^{\left(11\right)}\otimes {\tilde{x}}^{\left(n\right)}& {\tilde{A}}^{\left(12\right)}\otimes {\tilde{x}}^{\left(n\right)}& \dots & {\tilde{A}}^{\left(mn\right)}\otimes {\tilde{x}}^{\left(n\right)}\\ 0& \epsilon & \dots & \epsilon \\ ⋮\\ \epsilon & \dots & \epsilon & 0\end{array}\right).$$

(16)

Consider the max-plus linear system

$$\begin{array}{c}\tilde{E}\left(\mathit{A}\right)\otimes y\le \tilde{D}\\ \tilde{E}\left(\mathit{A}\right)\otimes y\ge \tilde{C}\end{array}$$

(17)

where the vector $y\in \mathbb{R}\left(mn\right)$ consists of the variables $y_{ij}\in \mathbb{R}$.

Theorem 16.

Suppose given A, B, and X. Then X is a strong EXE-solution of $\mathit{A}\otimes \mathit{X}=\mathit{B}\otimes \mathit{X}$ if and only if the max-plus linear system of inequalities, (17) is solvable.

Proof. 

Let y be a solution of (17) satisfying the condition ${\underline{a}}_{ij}-{\overline{a}}_{ij}\le y_{ij}\le 0,\mathrm{for} r\mathrm{every}$$i\in M,j\in N$. Then $A\in \mathbb{R}(m,n)$, $A={⨁}_{i\in M,j\in N}{y}_{ij}\otimes {\tilde{A}}^{\left(ij\right)}\in [\underline{A},\overline{A}]$ in view of Lemma 2 (ii).

Moreover, from the inequalities $\tilde{E}\left(\mathit{A}\right)\otimes y\le \tilde{D}$ and $\tilde{E}\left(\mathit{A}\right)\otimes y\ge \tilde{C}$, we have the following block inequalities for every fixed $i\in N$

$$\begin{array}{cc}\hfill \underset{k\in M,l\in N}{⨁}\left({\tilde{A}}^{\left(kl\right)}\otimes {\tilde{x}}^{\left(i\right)}\right)\otimes y_{kl}& \ge \underline{B}\otimes {\tilde{x}}^{\left(i\right)}\iff \hfill \\ \hfill \underset{k\in M,l\in N}{⨁}\left(y_{kl}\otimes {\tilde{A}}^{\left(kl\right)}\right)\otimes {\tilde{x}}^{\left(i\right)}& \ge \underline{B}\otimes {\tilde{x}}^{\left(i\right)}\iff A\otimes {\tilde{x}}^{\left(i\right)}\ge \underline{B}\otimes {\tilde{x}}^{\left(i\right)}\hfill \end{array}$$

and

$$\begin{array}{cc}\hfill \underset{k\in M,l\in N}{⨁}\left({\tilde{A}}^{\left(kl\right)}\otimes {\tilde{x}}^{\left(i\right)}\right)\otimes y_{kl}& \le \overline{B}\otimes {\tilde{x}}^{\left(i\right)}\iff \hfill \\ \hfill \underset{k\in M,l\in N}{⨁}\left(y_{kl}\otimes {\tilde{A}}^{\left(kl\right)}\right)\otimes {\tilde{x}}^{\left(i\right)}& \le \overline{B}\otimes {\tilde{x}}^{\left(i\right)}\iff A\otimes {\tilde{x}}^{\left(i\right)}\le \overline{B}\otimes {\tilde{x}}^{\left(i\right)}.\hfill \end{array}$$

Thus, according to Theorem 15, X is strong EXE-solution of $\mathit{A}\otimes \mathit{X}=\mathit{B}\otimes \mathit{X}$.

For the converse implication, suppose that X is a strong EXE-solution of $\mathit{A}\otimes \mathit{X}=\mathit{B}\otimes \mathit{X}$; i.e., there is $A\in \mathit{A}$ such that for any $x\in [\underline{x},\overline{x}])$, there is $B\in [\underline{B},\overline{B}])$ such that $A\otimes x=B\otimes x$. By Lemma 2 (ii), there are ${\alpha }_{ij}\in \mathbb{R}$, $i\in M,j\in N$ such that $A={⨁}_{i\in M,j\in N}{\alpha }_{ij}\otimes {\tilde{A}}^{\left(ij\right)}$ and ${\underline{a}}_{ij}-{\overline{a}}_{ij}\le {\alpha }_{ij}\le 0$. Then $y\in \mathbb{R}\left(mn\right)$, where $y_{ij}={\alpha }_{ij}$, for any $i\in M,j\in N$, satisfy $\tilde{E}\left(\mathit{A}\right)\otimes y\le \tilde{D}$ and $\tilde{E}\left(\mathit{A}\right)\otimes y\ge \tilde{C}$. □

5. Conclusions

In this paper, we have dealt with a problem of interval solvability of $\mathit{A}\otimes \mathit{X}=\mathit{B}\otimes \mathit{X}$. Necessary and sufficient conditions for four versions of interval solvability, namely weak XEA-solution, weak EAX-solution, strong XEA-solution, and strong EXE-solution, have been presented, and the computational complexity of methods for checking each of obtained equivalent conditions has been suggested. The way to define the other versions of weak/strong solutions, whereby some of them are each others equivalent, has been presented. The equivalent conditions of all versions of strong solution can be reduced to satisfy some max-plus linear equations and inequalities. Hence, types of strong interval solutions are of polynomial complexity. Weak solutions have been transformed into non-interval two-sided max-plus system for which efficient pseudopolynomial algorithms exist.