On the Solution of a Two-Sided Vector Equation in Tropical Algebra

Abstract

In the context of tropical mathematics, the problem of solving a vector equation with two given matrices and unknown vectors, each part of which has the form of a product of one of the matrices and an unknown vector, is considered. Such an equation, which has an unknown vector on either side of the equal sign, is often called a two-sided equation. A new procedure for solving two-sided equations is proposed based on minimizing some distance function between the vectors of tropical vector spaces that are generated by the columns of each of the matrices. As a result of the procedure, a pair of vectors is obtained, which provides a minimum distance between the spaces and the value of the distance itself. If the equation has solutions, then the resulting vectors are the solution to the equation. Otherwise, these vectors define a pseudo-solution that minimizes the deviation of one side of the equation from the other. Execution of the procedure consists in constructing a sequence of vectors that are pseudo-solutions of the two-sided equation in which the left and right sides are alternately replaced by constant vectors. Unlike the well-known alternating algorithm, in which the corresponding inequalities are solved one by one instead of equations, the proposed procedure uses a different argument, looks simpler, and allows one to establish natural criteria for completing calculations. If the equation has no solutions, the procedure also finds a pseudo-solution and determines the value of the error associated with it, which can be useful in solving approximation problems.

1 INTRODUCTION

In this study, in the context of tropical mathematics, the problem of solving a vector equation that has the form

$${\mathbf{Ax}} = {\mathbf{By}},$$

where A and B are given matrices; x and y are unknown vectors; the product of a matrix and a vector is defined in terms of operations of some tropical algebra, is considered. This equation has unknown vectors on both sides of the equal sign; therefore, it is often called a two-sided equation in scientific publications.

In tropical (idempotent) algebra, which studies the theory and applications of semirings and semifields with idempotent addition [1–6], the problem of solving a two-sided equation is of significant interest. In particular, this is related to the fact that the procedure of solving many other vector equations, for example, an equation of the form Ax = Bx with one unknown vector x is reduced to such a problem.

The issues of studying and solving two-sided equations were considered in some works, including the first publications on this problem by P. Butkovich [7–9] and other works published later [10–13]. The most often used applications are the problems of optimal planning of production processes [9, 11, 13]. Usually, the results known in publications propose algorithmic methods that, using an iterative computational procedure, make it possible to find one of the solutions, if they exist, or conclude that solutions are absent, otherwise (see, for example, the review of the methods for solving the two-sided equation in ([5], Section 7)).

Existing methods and approaches used to solve the two-sided equation include the following: combinatorial algorithms [8, 14], the elimination method [9], the upper-bound method [15], the algorithm based on the properties of mappings with division on partially ordered sets [16], the alternating algorithm [10], the combinatorial algorithm for equations in the field of rational numbers [11], the method of reducing to systems of equations and inequalities of two variables [12], and the method for solving equations with quadratic matrices of a special type [13]. However, in practice, the mentioned solution algorithms generally prove to be not efficient enough, for example, because of their computational complexity or additional constraints imposed on the condition and solution of the problem. Therefore, the development of new efficient procedures for solving two-sided equations seems to be quite a relevant problem.

In this study, a new procedure is proposed for solving two-sided equations based on the minimization of some function of the distance between the vectors of tropical vector spaces that are generated by the columns of each matrix of the equation. As a result of application of this procedure, one obtains a pair of vectors that provide the minimum distance between the spaces and the value of the distance itself. If the equation has solutions, the obtained vectors are the solution of the equation. Otherwise, these vectors determine a pseudo-solution that minimizes the deviation of one side of the equation from the other.

Execution of this procedure consists in constructing a sequence of vectors that are pseudo-solutions of the two-sided equation, in which the left and right sides are alternately replaced by constant vectors. Unlike the known alternating algorithm [10], in which the corresponding inequalities are alternately solved instead of solving the equations, the proposed procedure uses a different argument, seems to be simpler, and makes it possible to establish natural criteria of completion of calculations. If solutions do not exits, the procedure finds also a pseudo-solution and determines the value of the error associated with it, which can be useful when solving approximation problems.

2 PRELIMINARY INFORMATION

In this section, we present the main definitions, used denotations, and preliminary results of tropical algebra [17] necessary for further analysis and solving the two-sided equation. Further information on the theory and applications of tropical algebra can be found in a number of papers published over the last 25 years, including [1–6].

2.1 Idempotent Semifield

Let us consider a set $\mathbb{X}$, which is closed with respect to the operations of addition ⊕ and multiplication ⊗ and contains their neutral elements: zero $\mathbb{O}$ and unit $\mathbb{1}$. The operations are set so that ($\mathbb{X}$, ⊕, $\mathbb{O}$) forms an idempotent commutative semigroup with zero; ($\mathbb{X}$\{$\mathbb{O}$}, ⊗, $1$) is a commutative group; and multiplication is distributive with respect to addition. The algebraic system ($\mathbb{X}$, ⊕, ⊗, $\mathbb{O}$, $1$) is usually called an idempotent semifield.

In the considered semifield, the operation of addition is idempotent, i.e., for any x ∈ $\mathbb{X}$, the equality x ⊕ x = x is satisfied; the operation of multiplication is invertible, i.e., for any x ≠ $\mathbb{O}$, there is an inverse element x^–1 such that x ⊗ x^–1 = $1$. Below, the sign of the multiplication operation is omitted, implying that xy = x ⊗ y.

The denotation of powers with an integer exponent is understood in the sense of multiplication ⊗. In addition, it is assumed that the equation x^p = a has a unique solution x at any a ∈ $\mathbb{X}$ and integer p > 0. In this case, the power with a rational exponent are also determined; the semifield is called algebraically complete.

The operation of idempotent addition induces a partial order on $\mathbb{X}$, according to the rule: x ≤ y then and only then, when x ⊕ y = y. With respect to this order, the operation of summation has an extremal property in the form of inequalities x ≤ x ⊕ y and y ≤ x ⊕ y, which are valid for any x and y. The inequality x ⊕ y ≤ z is equivalent to the system of inequalities x ≤ z and y ≤ z. The operations of addition and multiplication are monotone: the inequality x ≤ y implies inequalities $x \oplus z$ ≤ $y \oplus z$ and xz ≤ yz for any z. The operator of inversion is antitone: the inequality x ≤ y for x, y ≠ $\mathbb{O}$ implies the inequality x^–1 ≥ y^–1. Finally, it is assumed that the described partial order is completed to the linear order so as to consider that the semifield is linearly ordered.

The examples of real, linearly ordered, algebraically complete idempotent semifields include the following:

$${{\mathbb{R}}_{{\max , + }}} = (\mathbb{R} \cup \{ - \infty \} , - \infty ,0,\max , + ),\quad {{\mathbb{R}}_{{\min , + }}} = (\mathbb{R} \cup \{ + \infty \} , + \infty ,0,\min , + ),$$

$${{\mathbb{R}}_{{\max }}} = ({{\mathbb{R}}_{ + }} \cup \{ 0\} ,0,1,\max , \times ),\quad {{\mathbb{R}}_{{\min }}} = ({{\mathbb{R}}_{ + }} \cup \{ + \infty \} , + \infty ,1,\min , \times ),$$

where $\mathbb{R}$ is a set of real numbers and ${{\mathbb{R}}_{ + }} = \{ x \in \mathbb{R}\,|\,x > 0\}$.

In the idempotent semifield ${{\mathbb{R}}_{{\max , + }}}$, which is usually called (max, +) algebra, addition ⊕ is determined as the operation max; multiplication ⊗ as arithmetic summation +. The role of $\mathbb{O}$ is played by –∞; the role of unit $1$ by the number 0. The power x^y corresponds to arithmetic product xy and is defined for any x, y ∈ $\mathbb{R}$. The inverse element x^–1 for any x ≠ $\mathbb{O}$ coincides with the opposite number –x in conventional arithmetic. The order relation induced by idempotent addition corresponds to the natural linear order for the set $\mathbb{R}$.

In the semifield ${{\mathbb{R}}_{{\min }}}$ (known also as min algebra), the operations are defined as ⊕ = min and ⊗ = × with neutral elements $\mathbb{O}$ = +∞ and $1$ = 1. The notions of power and inverse element have the usual sense. The order set by idempotent addition is inverse to the standard linear order on the set $\mathbb{R}$. All the above idempotent semifields are isomorphic to each other. For example, the semifield ${{\mathbb{R}}_{{\max , + }}}$ is related to ${{\mathbb{R}}_{{\min }}}$ by means of the isomorphism x $\mapsto$ e^–x.

2.2 Algebra of Matrices and Vectors

Let us denote by ${{\mathbb{X}}^{{m \times n}}}$ the set of matrices consisting of m rows and n columns with elements from $\mathbb{X}$. The matrix, all elements of which are $\mathbb{O}$, is zero and is denoted by 0. The matrix that does not have zero columns (rows) is called regular with respect to columns (rows). The matrix with neither zero rows nor zero columns is called regular. The quadratic matrix with elements equal to $1$ at its diagonal and $\mathbb{O}$ at all other positions is a unit matrix and is denoted by I.

The addition and multiplication of matrices and multiplication of a matrix by a scalar is executed according to the conventional rules with replacement of the operation of arithmetic addition and multiplication with the operations ⊕ and ⊗. The monotony and other properties of scalar operations ⊕ and ⊗ associated with the order relation on $\mathbb{X}$ are generalized to operations on matrices with which the inequalities are understood component-wise.

As usual, the matrix consisting of one column (row) forms a column vector (row vector). In what follows, all vectors are considered to be column vectors, unless otherwise indicated. The set of column vectors of n elements is denoted by ${{\mathbb{X}}^{n}}$. The vector, all elements of which are $\mathbb{O}$, is the zero vector and is denoted by 0. A vector is called regular if it does not have zero elements.

For any nonzero vector x = (x_i) ∈ ${{\mathbb{X}}^{n}}$, the multiplicative conjugate row vector x^– = ($x_{i}^{ - }$) with elements $x_{i}^{ - }$ = $x_{i}^{{ - 1}}$, if x_i ≠ $\mathbb{O}$, and $x_{i}^{ - } = 0$ otherwise, is defined.

It is easy to verify that for a regular vector x, the following relations are valid:

$${\mathbf{x}}{{{\mathbf{x}}}^{ - }} \geqslant {\mathbf{I}},\quad {{{\mathbf{x}}}^{ - }}{\mathbf{x}} = 1,$$

while, for the latter equality to be satisfied, the sufficient condition is x ≠ 0.

For regular vectors x and y, the inequality x ≤ y implies x^– ≥ y^–.

If the matrix A ∈ ${{\mathbb{X}}^{{m \times n}}}$ and vectors x ∈ ${{\mathbb{X}}^{n}}$ and y ∈ ${{\mathbb{X}}^{m}}$ are regular, then the products Ax and y^–A are regular vectors.

2.3 Vector Space

Let there be a system of vectors a₁, …, a_n ∈ ${{\mathbb{X}}^{m}}$. The vector b ∈ ${{\mathbb{X}}^{m}}$ is a linear combination of vectors of this system if the equality b = x₁a₁ ⊕ … ⊕ x_na_n holds for some x₁, …, x_n ∈ $\mathbb{X}$. The set of all linear combinations of the system of vectors forms their linear span

$$\mathcal{A} = \{ {{x}_{1}}{{{\mathbf{a}}}_{1}} \oplus \ldots \oplus {{x}_{n}}{{{\mathbf{a}}}_{n}}\,|\,{{x}_{1}}, \ldots ,{{x}_{n}} \in \mathbb{X}\} .$$

It is easy to see that the set of vectors $\mathcal{A}$ is closed under vector addition and scalar multiplication. The set $\mathcal{A}$ is called the tropical vector space over the semifield $\mathbb{X}$ generated by the system of vectors a₁, …, a_n.

2.4 Metric

Let us introduce the distance function on the set of vectors ${{\mathbb{X}}^{m}}$. For any vector a = (a_i), let us consider the support supp(a) = {i | a_i ≠ $\mathbb{O}$, 1 ≤ i ≤ m}, i.e., the set of indices of its nonzero elements.

For any nonzero vectors a = (a_i) and b = (b_i) for which the condition supp(a) = supp(b) is satisfied, we define the distance

$$d({\mathbf{a}},{\mathbf{b}}) = \mathop \oplus \limits_{i \in \operatorname{supp} ({\mathbf{a}})} (b_{i}^{{ - 1}}{{a}_{i}} \oplus a_{i}^{{ - 1}}{{b}_{i}}) = {{{\mathbf{b}}}^{ - }}{\mathbf{a}} \oplus {{{\mathbf{a}}}^{ - }}{\mathbf{b}}.$$

In the case when supp(a) ≠ supp(b), we will assume that the value of the function is larger than any value from $\mathbb{X}$ and write d(a, b) = ∞. If a = b = 0, then we set d(a, b) = $1$.

In the context of the semifield ${{\mathbb{R}}_{{\max , + }}}$, where $1$ = 0, the function d for all a, b ∈ ${{\mathbb{R}}^{m}}$ coincides with the usual Chebyshev distance (metric)

$${{d}_{\infty }}({\mathbf{a}},{\mathbf{b}}) = \mathop {\max }\limits_{1 \leqslant i \leqslant m} \max ({{a}_{i}} - {{b}_{i}},{{b}_{i}} - {{a}_{i}}) = \mathop {\max }\limits_{1 \leqslant i \leqslant m} \left| {{{b}_{i}} - {{a}_{i}}} \right|.$$

For other semifields isomorphic to ${{\mathbb{R}}_{{\max , + }}}$, the distance function d becomes a metric after applying the corresponding isomorphic mapping. For example, in the case of the semifield ${{\mathbb{R}}_{{\min }}}$, the metric is the function d′(a, b) = –lnd(a, b).

The function d defined in terms of any of the above semifields can be considered as a generalized metric with values in the set [$1$, ∞). Below, when measuring distances, we will use the generalized metric d.

3 MEASUREMENT OF DISTANCES AND SOLVING EQUATIONS

Let us consider the distance from the vector b ∈ ${{\mathbb{X}}^{m}}$ to the set $\mathcal{A} \subset {{\mathbb{X}}^{m}}$, which is defined as follows:

$$d(\mathcal{A},{\mathbf{b}}) = \mathop {\inf }\limits_{{\mathbf{a}} \in \mathcal{A}} d({\mathbf{a}},{\mathbf{b}}).$$

Let $\mathcal{A}$ be a tropical vector space generated by the system of nonzero vectors a₁, …, a_n ∈ ${{\mathbb{X}}^{m}}$. Any vector a ∈ $\mathcal{A}$ can be represented in the form of the linear combination a = x₁a₁ ⊕ … ⊕ x_na_n with coefficients x₁, …, x_n ∈ $\mathbb{X}$, as well as with the help of the matrix A = (a₁, …, a_n) composed of vectors of the system, which are taken as column vectors, and the vector x = (x₁, …, x_n)^T in the form of the equality a = Ax.

The distance from the vector b to the vector space $\mathcal{A}$ takes the form

$$d(\mathcal{A},{\mathbf{b}}) = \mathop {\min }\limits_{{\mathbf{a}} \in \mathcal{A}} d({\mathbf{a}},{\mathbf{b}}) = \mathop {\min }\limits_{{\mathbf{x}} \in {{\mathbb{X}}^{n}}} d({\mathbf{Ax}},{\mathbf{b}}) = \mathop {\min }\limits_{{\mathbf{x}} \in {{\mathbb{X}}^{n}}} ({{{\mathbf{b}}}^{ - }}{\mathbf{Ax}} \oplus {{({\mathbf{Ax}})}^{ - }}{\mathbf{b}}).$$

It can be shown (see, for example, [17, 18]) that for a regular vector b, it is sufficient to find the minimum on the right only over the regular vectors x, i.e., the equality

$$d(\mathcal{A},{\mathbf{b}}) = \mathop {\min }\limits_{{\mathbf{x}} > {\mathbf{0}}} d({\mathbf{Ax}},{\mathbf{b}})$$

is satisfied.

It is evident that the equality $d(\mathcal{A},{\mathbf{b}}) = 1$ is equivalent to the condition b ∈ $\mathcal{A}$, while the inequality $d(\mathcal{A},{\mathbf{b}}) \ne 1$ implies that ${\mathbf{b}} \notin \mathcal{A}$.

Let us assume that A ∈ ${{\mathbb{X}}^{{m \times n}}}$ is a regular matrix; b ∈ ${{\mathbb{X}}^{m}}$ is a regular vector. Let us define the function

$${{\Delta }_{{\mathbf{A}}}}({\mathbf{b}}) = {{({\mathbf{A}}{{({{{\mathbf{b}}}^{ - }}{\mathbf{A}})}^{ - }})}^{ - }}{\mathbf{b}}.$$

The following statement was proved in [19] (see also [17, 18]).

Lemma 1. Let A be a regular matrix and b be a regular vector. Then the equality

$$\mathop {\min }\limits_{{\mathbf{x}} > {\mathbf{0}}} d({\mathbf{Ax}},{\mathbf{b}}) = \sqrt {{{\Delta }_{{\mathbf{A}}}}({\mathbf{b}})} $$

is satisfied; while, the minimum is reached at x = $\sqrt {{{\Delta }_{{\mathbf{A}}}}({\mathbf{b}})} {{({{{\mathbf{b}}}^{ - }}{\mathbf{A}})}^{ - }}$.

If $\mathcal{A}$ is a tropical vector space generated by the columns of matrix A, then the distance from the vector b to $\mathcal{A}$ is defined as $d(\mathcal{A},{\mathbf{b}})$ = $\sqrt {{{\Delta }_{{\mathbf{A}}}}({\mathbf{b}})}$; the vector closest to b in the space $\mathcal{A}$ has the form y = $\sqrt {{{\Delta }_{{\mathbf{A}}}}({\mathbf{b}})} {\mathbf{A}}{{({{{\mathbf{b}}}^{ - }}{\mathbf{A}})}^{ - }}$.

It should be noted that the condition b ∈ $\mathcal{A}$ corresponds to the equality Δ_A(b) = $1$ and the condition b ∉ $\mathcal{A}$, to the inequality Δ_A(b) > $1$.

The results of analysis of the distances in the tropical vector space can be applied to solving the equation in the form

$${\mathbf{Ax}} = {\mathbf{b}}$$

(1)

with respect to the vector x ∈ ${{\mathbb{X}}^{n}}$.

This equation has an unknown vector on one side from the equal sign and is often called a one-sided equation.

This equation was studied in [17–19], where the following result was obtained.

Theorem 2. Let A be a regular matrix and b, a regular vector. Then, the following statements are valid.

1. If Δ_A(b) = $1$, then equation (1) has a solution and the vector x = (b^–A)^– is the maximum solution.

2. If Δ_A(b) > $1$, then equation (1) does not have solutions. The best approximation to the solution in terms of the distance function d is the vector x = $\sqrt {{{\Delta }_{{\mathbf{A}}}}({\mathbf{b}})} {{({{{\mathbf{b}}}^{ - }}{\mathbf{A}})}^{ - }}$.

It should be noted that the quantity $\sqrt {{{\Delta }_{{\mathbf{A}}}}({\mathbf{b}})}$ has the sense of the minimum achievable deviation between the left- and right-hand sides of equation (1) measured in accordance with the scale of the distance function d.

Let us assume that A ∈ ${{\mathbb{X}}^{{m \times n}}}$ and B ∈ ${{\mathbb{X}}^{{m \times k}}}$ are given regular matrices; x ∈ ${{\mathbb{X}}^{n}}$ and y ∈ ${{\mathbb{X}}^{k}}$ are unknown regular vectors. Let us investigate the following two-sided equation in which unknown vectors appear in both sides:

$${\mathbf{Ax}} = {\mathbf{By}}.$$

(2)

As in the case of equation (1), the problem of analysis of equation (2) can be reduced to determining the distances between tropical vector spaces. Let us consider the columns of matrices A = (a₁, …, a_n) and B = (b₁, …, b_k). Let us denote by $\mathcal{A}$ the tropical space generated by the system of vectors a₁, …, a_n; by $\mathcal{B}$, the space generated by b₁, …, b_k. Let us determine the distance between the spaces as follows:

$$d(\mathcal{A},\mathcal{B}) = \mathop {\min }\limits_{{\mathbf{a}} \in \mathcal{A},{\mathbf{b}} \in \mathcal{B}} d({\mathbf{a}},{\mathbf{b}}) = \mathop {\min }\limits_{{\mathbf{a}} \in \mathcal{A}} \mathop {\min }\limits_{\mathbf{y}} d({\mathbf{a}},{\mathbf{By}}) = \mathop {\min }\limits_{{\mathbf{b}} \in \mathcal{B}} \mathop {\min }\limits_{\mathbf{x}} d({\mathbf{Ax}},{\mathbf{b}}) = \mathop {\min }\limits_{{\mathbf{x}} > {\mathbf{0}},{\mathbf{y}} > {\mathbf{0}}} d({\mathbf{Ax}},{\mathbf{By}}).$$

If condition d($\mathcal{A}$, $\mathcal{B}$) = $1$ is satisfied, this implies that the spaces $\mathcal{A}$ and $\mathcal{B}$ have a nonempty intersection; then equation (2) will have a solution (x, y).

It the value of the distance d($\mathcal{A}$, $\mathcal{B}$) > $1$, this corresponds to the absence of common points of spaces $\mathcal{A}$ and $\mathcal{B}$ (and, thus, the equation does not have a solution); its value shows the minimum distance between the vectors of these spaces (the minimum possible deviation between both sides of the equation).

Let us fix some regular vector x ∈ ${{\mathbb{X}}^{n}}$. It has a corresponding vector a = Ax of the space $\mathcal{A}$. According to Lemma 1, the minimum distance between the vector a and the vectors of the space $\mathcal{B}$ is the square root of the quantity

$${{\Delta }_{{\mathbf{B}}}}({\mathbf{a}}) = {{\Delta }_{{\mathbf{B}}}}({\mathbf{Ax}}) = {{({\mathbf{B}}{{({{({\mathbf{Ax}})}^{ - }}{\mathbf{B}})}^{ - }})}^{ - }}{\mathbf{Ax}}.$$

The vector of the space $\mathcal{B}$ closest to the vector a can be written in the form

$${\mathbf{b}} = \sqrt {{{\Delta }_{{\mathbf{B}}}}({\mathbf{Ax}})} {\mathbf{B}}{{({{({\mathbf{Ax}})}^{ - }}{\mathbf{B}})}^{ - }}.$$

Similarly, for the fixed y ∈ ${{\mathbb{X}}^{k}}$, the squared distance from vector b = By to the space $\mathcal{A}$ and the vector a ∈ $\mathcal{A}$ closest to vector b are defined by the formulas

$${{\Delta }_{{\mathbf{A}}}}({\mathbf{By}}) = {{({\mathbf{A}}{{({{({\mathbf{By}})}^{ - }}{\mathbf{A}})}^{ - }})}^{ - }}{\mathbf{By}},\quad {\mathbf{a}} = \sqrt {{{\Delta }_{{\mathbf{A}}}}({\mathbf{By}})} {\mathbf{A}}{{({{({\mathbf{By}})}^{ - }}{\mathbf{A}})}^{ - }}.$$

Let us assume that for the vectors ${{{\mathbf{x}}}_{*}} \in {{\mathbb{X}}^{n}}$ and ${{{\mathbf{y}}}_{*}} \in {{\mathbb{X}}^{k}}$, the following is true:

$$d(\mathcal{A},\mathcal{B}) = \mathop {\min }\limits_{{\mathbf{x}} > {\mathbf{0}},{\mathbf{y}} > {\mathbf{0}}} d({\mathbf{Ax}},{\mathbf{By}}) = d({\mathbf{A}}{{{\mathbf{x}}}_{*}},{\mathbf{B}}{{{\mathbf{y}}}_{*}}).$$

It is evident that in this case, the equalities

$${{\Delta }_{{\mathbf{B}}}}({\mathbf{A}}{{{\mathbf{x}}}_{*}}) = {{d}^{2}}({\mathbf{A}}{{{\mathbf{x}}}_{*}},{\mathbf{B}}{{{\mathbf{y}}}_{*}}) = {{\Delta }_{{\mathbf{A}}}}({\mathbf{B}}{{{\mathbf{y}}}_{*}})$$

hold.

Let us introduce the denotation ${{\Delta }_{*}}$ = ${{\Delta }_{{\mathbf{B}}}}({\mathbf{A}}{{{\mathbf{x}}}_{*}})$ = ${{\Delta }_{{\mathbf{A}}}}({\mathbf{B}}{{{\mathbf{y}}}_{*}})$ and note that, according to Theorem 2, the equality ${{\Delta }_{*}}$ = $1$ implies that equation (2) has regular solutions. The value of ${{\Delta }_{*}}$, which is not equal (larger than) $1$, shows that the equality in (2) is not satisfied for any regular vectors x and y; its value determines the minimum possible deviation between both sides of the equation, which is reached at x = ${{{\mathbf{x}}}_{*}}$ and y = ${{{\mathbf{y}}}_{*}}$.

4 PROCEDURE OF SOLVING THE TWO-SIDED EQUATION

The above analysis of two-sided equation (2) provides a background for development of the following procedure for solving. This procedure is based on constructing a sequence of vectors in spaces $\mathcal{A}$ and $\mathcal{B}$, which are generated by columns of the matrices A and B. Vectors are examined taken alternately from each space so that after the choice of some vector from one space, the next vector is chosen in the other space to provide the minimum distance to the previous vector.  In the context of solving equation (2), along with the indicated vectors, the vectors x and y of the coefficients of their decomposition as linear combinations of the columns of the corresponding matrices A and B are considered.

Let us assume that we have chosen an arbitrary regular vector x₀ ∈ ${{\mathbb{X}}^{n}}$. This vector has the corresponding vector a₀ = Ax₀ ∈ $\mathcal{A}$. Applying Theorem 2, we find the least distance from the vector a₀ to the vectors of the space $\mathcal{B}$, according to the formulas

$$d({{{\mathbf{a}}}_{0}},\mathcal{B}) = \sqrt {{{\Delta }_{0}}} ,\quad {{\Delta }_{0}} = {{\Delta }_{{\mathbf{B}}}}({\mathbf{A}}{{{\mathbf{x}}}_{0}}) = {{({\mathbf{B}}{{({{({\mathbf{A}}{{{\mathbf{x}}}_{0}})}^{ - }}{\mathbf{B}})}^{ - }})}^{ - }}{\mathbf{A}}{{{\mathbf{x}}}_{0}}.$$

This value is reached at the vector b₁ ∈ $\mathcal{B}$, which has the form

$${{{\mathbf{b}}}_{1}} = {\mathbf{B}}{{{\mathbf{y}}}_{1}},\quad {{{\mathbf{y}}}_{1}} = \sqrt {{{\Delta }_{0}}} {{({{({\mathbf{A}}{{{\mathbf{x}}}_{0}})}^{ - }}{\mathbf{B}})}^{ - }}.$$

The minimum distance from the vector b₁ to the vectors of the space $\mathcal{A}$ is

$$d({{{\mathbf{b}}}_{1}},\mathcal{A}) = \sqrt {{{\Delta }_{1}}} ,\quad {{\Delta }_{1}} = {{\Delta }_{{\mathbf{A}}}}({\mathbf{B}}{{{\mathbf{y}}}_{1}}) = {{({\mathbf{A}}{{({{({\mathbf{B}}{{{\mathbf{y}}}_{1}})}^{ - }}{\mathbf{A}})}^{ - }})}^{ - }}{\mathbf{B}}{{{\mathbf{y}}}_{1}}$$

and is attained at a vector a₂ ∈ $\mathcal{A}$ such that

$${{{\mathbf{a}}}_{2}} = {\mathbf{A}}{{{\mathbf{x}}}_{2}},\quad {{{\mathbf{x}}}_{2}} = \sqrt {{{\Delta }_{1}}} {{({{({\mathbf{B}}{{{\mathbf{y}}}_{1}})}^{ - }}{\mathbf{A}})}^{ - }}.$$

Similarly, we determine the distance d(a₂, $\mathcal{B}$) based on the value of Δ₂, which is used further to find vectors y₃ and b₃. Next, we calculate the value of Δ₂ to determine the distance d(b₃, $\mathcal{A}$) and find vectors x₄ and a₄.

As a result of repeating the above calculations, the sequence of vectors a₀, b₁, a₂, b₃, a₄, …, which are chosen one by one from the spaces $\mathcal{A}$ and $\mathcal{B}$ so as to minimize the distance between successive vectors, is constructed. At the same time, the sequence of the pairs of vectors (x₀, y₁), (x₂, y₃), … is generated; they represent some approximations of the solution to equation (2).

Let us investigate the sequence Δ₀, Δ₁, Δ₁, … and note that Δ_i ≥ $1$ for all i = 0, 1, …, i.e., this sequence is bounded from below. Now, let us verify that this sequence is not increasing.

Let us show that Δ₁ ≤ Δ₀ and consider the quantity Δ₁ = ${{({\mathbf{A}}{{({{({\mathbf{B}}{{{\mathbf{y}}}_{1}})}^{ - }}{\mathbf{A}})}^{ - }})}^{ - }}{\mathbf{B}}{{{\mathbf{y}}}_{1}}$.

By virtue of the regularity of vector y₁, the regularity of matrix B with respect to its rows, and the regularity of matrix A with respect to its columns, the row vector (By₁)^–A is regular. Taking into account the regularity of the vector x₀, we get the inequality ${{{\mathbf{x}}}_{0}}{\mathbf{x}}_{0}^{ - } \geqslant {\mathbf{I}}$. Premultiplying this inequality by ${{({\mathbf{B}}{{{\mathbf{y}}}_{1}})}^{ - }}{\mathbf{A}}$, we come to the inequality ${{({\mathbf{B}}{{{\mathbf{y}}}_{1}})}^{ - }}{\mathbf{A}}$ ≤ ${{({\mathbf{B}}{{{\mathbf{y}}}_{1}})}^{ - }}{\mathbf{A}}{{{\mathbf{x}}}_{0}}{\mathbf{x}}_{0}^{ - }$, both sides of which are regular. After multiplicative conjugate transposition of both sides of the latter inequality, we obtain

$${{({{({\mathbf{B}}{{{\mathbf{y}}}_{1}})}^{ - }}{\mathbf{A}})}^{ - }} \geqslant {{({{({\mathbf{B}}{{{\mathbf{y}}}_{1}})}^{ - }}{\mathbf{A}}{{{\mathbf{x}}}_{0}}{\mathbf{x}}_{0}^{ - })}^{ - }} = {{({{({\mathbf{B}}{{{\mathbf{y}}}_{1}})}^{ - }}{\mathbf{A}}{{{\mathbf{x}}}_{0}})}^{{ - 1}}}{{{\mathbf{x}}}_{0}}.$$

As a result of premultiplication of both sides of the inequality by A, one more passage to the conjugate vectors and postmultiplication by By₁, we get

$${{({\mathbf{A}}{{({{({\mathbf{B}}{{{\mathbf{y}}}_{1}})}^{ - }}{\mathbf{A}})}^{ - }})}^{ - }}{\mathbf{B}}{{{\mathbf{y}}}_{1}} \leqslant ({{({\mathbf{B}}{{{\mathbf{y}}}_{1}})}^{ - }}{\mathbf{A}}{{{\mathbf{x}}}_{0}}){{({\mathbf{A}}{{{\mathbf{x}}}_{0}})}^{ - }}{\mathbf{B}}{{{\mathbf{y}}}_{1}}.$$

Applying the inequality obtained together with the equality y₁ = $\sqrt {{{\Delta }_{0}}} {{({{({\mathbf{A}}{{{\mathbf{x}}}_{0}})}^{ - }}{\mathbf{B}})}^{ - }}$, which implies that By₁ = $\sqrt {{{\Delta }_{0}}} {\mathbf{B}}{{({{({\mathbf{A}}{{{\mathbf{x}}}_{0}})}^{ - }}{\mathbf{B}})}^{ - }}$, and then using the evident equality ${{({\mathbf{A}}{{{\mathbf{x}}}_{0}})}^{ - }}{\mathbf{B}}{{({{({\mathbf{A}}{{{\mathbf{x}}}_{0}})}^{ - }}{\mathbf{B}})}^{ - }}$ = $1$, we get

$$\begin{gathered} {{\Delta }_{1}} = {{({\mathbf{A}}{{({{({\mathbf{B}}{{{\mathbf{y}}}_{1}})}^{ - }}{\mathbf{A}})}^{ - }})}^{ - }}{\mathbf{B}}{{{\mathbf{y}}}_{1}} \leqslant ({{({\mathbf{B}}{{{\mathbf{y}}}_{1}})}^{ - }}{\mathbf{A}}{{{\mathbf{x}}}_{0}}){{({\mathbf{A}}{{{\mathbf{x}}}_{0}})}^{ - }}{\mathbf{B}}{{{\mathbf{y}}}_{1}} \\ = ({{({\mathbf{B}}{{({{({\mathbf{A}}{{{\mathbf{x}}}_{0}})}^{ - }}{\mathbf{B}})}^{ - }})}^{ - }}{\mathbf{A}}{{{\mathbf{x}}}_{0}}){{({\mathbf{A}}{{{\mathbf{x}}}_{0}})}^{ - }}{\mathbf{B}}({{({\mathbf{A}}{{{\mathbf{x}}}_{0}})}^{ - }}{\mathbf{B}}{{({{({\mathbf{A}}{{{\mathbf{x}}}_{0}})}^{ - }}{\mathbf{B}})}^{ - }} = {{({\mathbf{B}}{{({{({\mathbf{A}}{{{\mathbf{x}}}_{0}})}^{ - }}{\mathbf{B}})}^{ - }})}^{ - }}{\mathbf{A}}{{{\mathbf{x}}}_{0}} = {{\Delta }_{0}}. \\ \end{gathered} $$

Similarly, we can verify that the inequalities Δ₂ ≤ Δ₁ and, thus, the inequalities Δ_i + 1 ≤ Δ_i for all i are fulfilled. Therefore, the sequence Δ₀, Δ₁, … is not increasing. Taking into account the fact that this sequence is bounded from below, it converges to some limit ${{\Delta }_{*}} \geqslant 1$.

It should be noted that each element of the considered sequence has the sense of the squared distance from some vector of one of the spaces $\mathcal{A}$ and $\mathcal{B}$ to the closest vector from another space. Therefore, if the equality Δ_i = $1$ is satisfied for some i, this implies that the spaces $\mathcal{A}$ and $\mathcal{B}$ have a nonempty intersection and equation (2) is solvable. At the same time, if i is an even number, then the intersection contains the vector a_i = Ax_i and the pair of vectors (x_i, y_i + 1) is the solution of the equation. If i is odd, then the intersection contains the vector b_i = By_i and the solution is the pair (x_i + 1, y_i).

Attainment of the equality Δ_i = $1$ indicates that the limit ${{\Delta }_{*}}$ = Δ_i of the sequence Δ₀, Δ₁, … is found and can be used for determining the conditions of completion of the calculation procedure in practical calculations.

If the intersection of the spaces $\mathcal{A}$ and $\mathcal{B}$ is empty, then the value of the limit satisfies the inequality ${{\Delta }_{*}}$ > $1$ and equation (2) does not have solutions. In this case, the procedure should be stopped as soon as a repeating element appears in any of the sequences x₀, x₂, … or y₁, y₃, ….

The above procedure gives us the following algorithm for the analysis of equation (2).

Algorithm 1.

(1) Set i = 0 and choose a regular vector x₀.

(2) Calculate

$${{\Delta }_{i}} = {{({\mathbf{B}}{{({{({\mathbf{A}}{{{\mathbf{x}}}_{i}})}^{ - }}{\mathbf{B}})}^{ - }})}^{ - }}{\mathbf{A}}{{{\mathbf{x}}}_{i}},\quad {{{\mathbf{y}}}_{{i + 1}}} = \sqrt {{{\Delta }_{i}}} {{({{({\mathbf{A}}{{{\mathbf{x}}}_{i}})}^{ - }}{\mathbf{B}})}^{ - }}.$$

(3) If Δ_i = $1$ or y_i + 1 = y_j  for some j < i, then set

$${{\Delta }_{*}} = {{\Delta }_{i}},\quad {{{\mathbf{x}}}_{*}} = {{{\mathbf{x}}}_{i}},\quad {{{\mathbf{y}}}_{*}} = {{{\mathbf{y}}}_{{i + 1}}}$$

and stop the procedure; otherwise, set i = i + 1.

(4) Calculate

$${{\Delta }_{i}} = {{({\mathbf{A}}{{({{({\mathbf{B}}{{{\mathbf{y}}}_{i}})}^{ - }}{\mathbf{A}})}^{ - }})}^{ - }}{\mathbf{B}}{{{\mathbf{y}}}_{i}},\quad {{{\mathbf{x}}}_{{i + 1}}} = \sqrt {{{\Delta }_{i}}} {{({{({\mathbf{B}}{{{\mathbf{y}}}_{i}})}^{ - }}{\mathbf{A}})}^{ - }}.$$

(5) If Δ_i = $1$ or x_i + 1 = x_j for some j < i, then set

$${{\Delta }_{*}} = {{\Delta }_{i}},\quad {{{\mathbf{x}}}_{*}} = {{{\mathbf{x}}}_{{i + 1}}},\quad {{{\mathbf{y}}}_{*}} = {{{\mathbf{y}}}_{i}}$$

and stop; otherwise, set i = i + 1.

(6) Return to step (2).

If, as a result of operation of this algorithm, we obtain ${{\Delta }_{*}}$ = $1$, then equation (2) has solutions, including the found pair of vectors (${{{\mathbf{x}}}_{*}}$, ${{{\mathbf{y}}}_{*}}$). In the case, when ${{\Delta }_{*}}$ > $1$, the equation does not have solutions; the value of ${{\Delta }_{*}}$ shows the minimal possible deviation between both sides of the equation, which is reached at vectors (${{{\mathbf{x}}}_{*}}$, ${{{\mathbf{y}}}_{*}}$).

5 EXAMPLES OF SOLVING A TWO-SIDED EQUATION

Let as first present the example of solving the equation from [10], which is set in the context of (max, +) algebra (the semifield ${{\mathbb{R}}_{{\max , + }}}$). The matrices of the equation and the initial approximation are defined (with the use of the denotation $\mathbb{O}$ = –∞) as follows:

$${\mathbf{A}} = \left( {\begin{array}{*{20}{c}} 3&0&0 \\ 1&1&0 \\ 0&1&2 \end{array}} \right),\quad {\mathbf{B}} = \left( {\begin{array}{*{20}{c}} 1&1 \\ 3&2 \\ 3&1 \end{array}} \right),\quad {{{\mathbf{x}}}_{0}} = \left( \begin{gathered} 5 \\ 3 \\ 1 \\ \end{gathered} \right).$$

To solve the equation, we apply Algorithm 1. Taking into account the fact that the operation of extraction of the square root in (max, +) algebra corresponds to the arithmetic halving, we get the following results for each calculation step:

$${\mathbf{A}}{{{\mathbf{x}}}_{0}} = \left( \begin{gathered} 8 \\ 6 \\ 4 \\ \end{gathered} \right),\quad {{\Delta }_{0}} = 2,\quad {{{\mathbf{y}}}_{1}} = \left( \begin{gathered} 2 \\ 4 \\ \end{gathered} \right);$$

$${\mathbf{B}}{{{\mathbf{y}}}_{1}} = \left( \begin{gathered} 7 \\ 6 \\ 5 \\ \end{gathered} \right),\quad {{\Delta }_{1}} = 1,\quad {{{\mathbf{x}}}_{2}} = \left( \begin{gathered} 9{\text{/}}2 \\ 9{\text{/}}2 \\ 7{\text{/}}2 \\ \end{gathered} \right);$$

$${\mathbf{A}}{{{\mathbf{x}}}_{2}} = \left( \begin{gathered} 15{\text{/}}2 \\ 11{\text{/}}2 \\ 11{\text{/}}2 \\ \end{gathered} \right),\quad {{\Delta }_{2}} = 1,\quad {{{\mathbf{y}}}_{3}} = \left( \begin{gathered} 3 \\ 4 \\ \end{gathered} \right);$$

$${\mathbf{B}}{{{\mathbf{y}}}_{3}} = \left( \begin{gathered} 7 \\ 6 \\ 6 \\ \end{gathered} \right),\quad {{\Delta }_{3}} = 0,\quad {{{\mathbf{x}}}_{4}} = \left( \begin{gathered} 4 \\ 5 \\ 4 \\ \end{gathered} \right).$$

The value ${{\Delta }_{*}}$ = Δ₃ = 0 = $1$ obtained shows that the equation has solutions. In addition, the solution is found to be

$${{{\mathbf{x}}}_{*}} = {{{\mathbf{x}}}_{4}} = \left( \begin{gathered} 4 \\ 5 \\ 4 \\ \end{gathered} \right),\quad {{{\mathbf{y}}}_{*}} = {{{\mathbf{y}}}_{3}} = \left( \begin{gathered} 3 \\ 4 \\ \end{gathered} \right).$$

Let us consider the equation with matrices from the previous example, in each of them, one element in the last row is replaced as follows:

$${\mathbf{A}} = \left( {\begin{array}{*{20}{c}} 3&0&0 \\ 1&1&0 \\ 0&1&3 \end{array}} \right),\quad {\mathbf{B}} = \left( {\begin{array}{*{20}{c}} 1&1 \\ 3&2 \\ 1&1 \end{array}} \right).$$

Provided that the vector of initial approximation x₀ does not change, Algorithm 1 gives the following results:

$${\mathbf{A}}{{{\mathbf{x}}}_{0}} = \left( \begin{gathered} 8 \\ 6 \\ 4 \\ \end{gathered} \right),\quad {{\Delta }_{0}} = 2,\quad {{{\mathbf{y}}}_{1}} = \left( \begin{gathered} 4 \\ 4 \\ \end{gathered} \right);$$

$${\mathbf{B}}{{{\mathbf{y}}}_{1}} = \left( \begin{gathered} 7 \\ 7 \\ 5 \\ \end{gathered} \right),\quad {{\Delta }_{1}} = 2,\quad {{{\mathbf{x}}}_{2}} = \left( \begin{gathered} 5 \\ 5 \\ 3 \\ \end{gathered} \right);$$

$${\mathbf{A}}{{{\mathbf{x}}}_{2}} = \left( \begin{gathered} 8 \\ 6 \\ 6 \\ \end{gathered} \right),\quad {{\Delta }_{2}} = 1,\quad {{{\mathbf{y}}}_{3}} = \left( \begin{gathered} 7{\text{/}}2 \\ 9{\text{/}}2 \\ \end{gathered} \right);$$

$${\mathbf{B}}{{{\mathbf{y}}}_{3}} = \left( \begin{gathered} 15{\text{/}}2 \\ 13{\text{/}}2 \\ 11{\text{/}}2 \\ \end{gathered} \right),\quad {{\Delta }_{3}} = 1,\quad {{{\mathbf{x}}}_{4}} = \left( \begin{gathered} 5 \\ 5 \\ 3 \\ \end{gathered} \right).$$

Taking into account the fact that the equality x₄ = x₂ is fulfilled, provided that Δ₃ = 1 > $1$, the equation does not have solutions. The value ${{\Delta }_{*}}$ = Δ₃ = 1 shows the minimum deviation between both sides of the equation, which is reached at the vectors

$${{{\mathbf{x}}}_{*}} = {{{\mathbf{x}}}_{4}} = \left( \begin{gathered} 5 \hfill \\ 5 \hfill \\ 3 \hfill \\ \end{gathered} \right),\quad {{{\mathbf{y}}}_{*}} = {{{\mathbf{y}}}_{3}} = \left( \begin{gathered} 7{\text{/}}2 \\ 9{\text{/}}2 \\ \end{gathered} \right).$$

6 CONCLUSIONS

In this work, a new computational procedure of solving a two-sided vector equation in idempotent algebra is presented; it is based on analysis of the distances between tropical vector spaces. The procedure is realized as an iterative calculation algorithm described in terms of an arbitrary, linearly ordered, algebraically complete idempotent semifield. If the equation does not have solutions, this procedure finds its pseudo-solution, which provides the minimum deviation of one side of the equation from another and determines the value of this deviation.

Analysis and estimation of the computation complexity of the proposed algorithm is of special interest for further research.