{'fraction_non_alphanumeric': 0.047044836956521736, 'fraction_numerical': 0.00993546195652174, 'mean_word_length': 3.7871951219512194, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 7, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 20, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Complete solution of tropical vector inequalities using matrix sparsification

We examine the problem to find all solutions of two-sided vector inequalities, given in the tropical algebra setting, where the unknown vector appears on both sides of the inequality. We offer a solution, which uses sparse matrices to simplify the problem and to construct a family of solution sets, each defined by a sparse matrix obtained from a matrix in the inequality by setting some of its entries to zero. All solutions are then combined to represent the result in a parametric form in terms of a matrix whose columns form a complete system of generators for the solution. We describe the computational technique proposed to solve the problem, and illustrate this technique with a numerical example.


Introduction
The problem of solving two-sided vector inequalities (where the unknown vector appears on both sides of the inequality) in the tropical algebra setting occurs in a variety of contexts, from geometry of tropical polyhedral cones [18,2,7] to mean payoff games [1,8]. In its general form, the two-sided inequality is represented as Ax ≤ Bx, where A and B are given matrices, x is the unknown vector, and the matrix-vector multiplication is interpreted in terms of a tropical semifield (a semiring with idempotent addition and invertible multiplication). The available solutions in the general case include various iterative algorithms based on combinatorial optimization procedures [4], Newton iterations [8] and other techniques [6]. For the special form Ax ≤ x of the inequality, a complete solution is known in an explicit closed form (see, e.g., [13]).
Another approach to solve vector inequalities, which exploits matrix sparsification techniques, is developed in [14,15]. Specifically, in [15], a complete solution is derived for an inequality in the form x ≤ Bx. The solution is given as a family of solution sets and in closed form through a generating matrix.
In this paper, we examine the two-sided inequality Ax ≤ Bx, and offer a solution, which uses sparse matrices to simplify the problem and to construct a family of solution sets, each defined by a sparse matrix obtained from the matrix B by setting some of its entries to zero. All solutions are then combined to represent the result in a parametric form in terms of a matrix whose columns form a complete system of generators for the solution. We describe the computational technique proposed to solve the problem, and illustrate this technique with an example.
The rest of the paper is organized as follows. Section 2 presents a short introduction into the tropical algebra to provide an overview of the basic facts, symbols and results to be used in the subsequent sections. In Section 3, we formulate the problem and make some observations on the solution. The main result is included in Section 4, which provides a complete solution of the two-sided inequality. In Section 5, we discuss the computational implementation of the solution, describe a procedure of generating solution sets, and give a numerical example.

Preliminary definitions, notation and results
In this section, we offer a brief overview of basic definitions, notation and preliminary results of the tropical algebra, which underlie the solutions presented in the subsequent sections. For further details, one can consult, e.g., [3,5,12,9,11,10].

Idempotent semifield
Consider a nonempty set X that is closed under addition ⊕ and multiplication ⊗, and has zero 0 and one 1 as the neutral elements of the operations ⊕ and ⊗. It is assumed that (X, ⊕, 0) is a commutative idempotent monoid, (X \ {0}, ⊕, 1) is an Abelian group, and multiplication distributes over addition. Under these conditions, the system (X, ⊕, ⊗, 0, 1) is referred to as the idempotent semifield.
The integer powers are defined in the usual way to represent repeated multiplication: 0 p = 0, x 0 = 1, x p = xx p−1 and x −p = (x −1 ) p , where x −1 is the inverse of x, for any nonzero x ∈ X and natural p. The integer powers are assumed to extend to the powers with rational exponents. In what follows, the multiplication symbol ⊗ is omitted to save writing.
The idempotent addition induces a partial order on X such that x ≤ y if and only if x ⊕ y = y . With respect to this order, the addition possesses the extremal properties (the majority law of addition): x ≤ x⊕y and y ≤ x⊕y , satisfied for any x, y ∈ X. Furthermore, addition and multiplication are isotone, which means that the inequality x ≤ y yields x ⊕ z ≤ y ⊕ z and xz ≤ yz . The inversion is antitone: x ≤ y results in x −1 ≥ y −1 for x, y = 0. Finally, the inequality x⊕y ≤ z is equivalent to the pair of inequalities x ≤ z and y ≤ z . The partial order is assumed to extend to a total order to make X linearly ordered.
An example of the idempotent semifields under consideration is the real semifield R max,+ = (R ∪ {−∞}, max, +, −∞, 0), which is often called (max, +)-algebra. In this semifield, we have the operations defined as ⊕ = max and ⊗ = +, and the neutral elements as 0 = −∞ and 1 = 0. Furthermore, the inverse x −1 of x ∈ R coincides with the opposite number −x in the standard arithmetic. The power x y corresponds to the arithmetic product xy , which is defined for all x, y ∈ R. Finally, the order induced by idempotent addition agrees with the natural linear order on R.

Matrices and vectors
The set of matrices with m rows and n columns over X is denoted by X m×n . A matrix with all entries equal to 0 is the zero matrix denoted 0. A matrix is called row-regular if it has no rows with all entries equal to 0.
The addition and multiplication of conforming matrices, and multiplication of matrices by scalars follow the standard rules, where the arithmetic addition and multiplication are replaced by the scalar operations ⊕ and ⊗.
For any non-zero matrix A = (a ij ) ∈ X m×n , the multiplicative conjugate transpose is the matrix ji if a ji = 0, and a − ij = 0 otherwise. The properties of scalar operations with respect to the order relations are extended to the matrix operations, where the relations are interpreted componentwise.
A square matrix with all diagonal entries equal to 1, and the off-diagonal entries equal to 0 is the identity matrix denoted by I . The non-negative integer powers of a square nonzero matrix A are defined in the usual way: A 0 = I and A p = AA p−1 for any natural p.
The trace of a square matrix A = (a ij ) ∈ X n×n is given by tr A = a 11 ⊕ · · · ⊕ a nn .
Any matrix that consists of one column (row) forms a column (row) vector. All vectors below are considered column vectors unless transposed. The set of column vectors with n elements over X is denoted X n .
A row-regular matrix that has exactly one nonzero entry in each row is called strictly row-monomial. It is not difficult to verify that each strictly row-monomial matrix A satisfies the inequalities A − A ≤ I and AA − ≥ I . If a matrix A is strictly row-monomial, then the inequality Ax ≥ y , where x and y are vectors, is equivalent to x ≥ A − y . Indeed, we can multiply the first inequality by A − on the left to obtain x ≥ A − Ax ≥ A − y , which yields the second. At the same time, the multiplication of the second inequality by A on the left results in the first inequality as Ax ≥ AA − y ≥ y .

Linear dependence
A vector b ∈ X m is linearly dependent on vectors a 1 , . . . , a n ∈ X m if there exist scalars x 1 , . . . , x n ∈ X such that b = x 1 a 1 ⊕ · · · ⊕ x n a n . Specifically, a vector b is collinear with a if b = xa for some scalar x.
The following result, obtained in [16] (see also [5]), offers a formal criterion to check linearly dependence of vectors.

Lemma 1.
A vector b is linearly dependent on vectors a 1 , . . . , a n if and only if the condition (A(b − A) − ) − b = 1 holds with the matrix A = (a 1 , . . . , a n ).
A system of vectors a 1 , . . . , a n is linearly dependent if at least one vector is linearly dependent on others. Two systems of vectors are equivalent if each vector of one system is linearly dependent on vectors of the other system.
Consider a system a 1 , . . . , a n that may have linearly dependent vectors. To construct an equivalent linearly independent system, we can use a procedure that successively reduces the system until it becomes linearly independent. The procedure applies the criterion provided by Lemma 1 to examine the vectors one by one. It removes a vector if it is linearly dependent on others, or leaves the vector in the system otherwise. It is not difficult to see that the procedure yields a linearly independent system, equivalent to the original one.

Solution of vector inequality
We now present a complete solution to a two-sided vector inequality of a special form. Given a matrix A ∈ X n×n , consider the problem to find regular vectors x ∈ X n to satisfy the inequality To represent the solution in an explicit form, we introduce a function that maps any square matrix A ∈ X n×n onto the scalar Suppose that Tr(A) ≤ 1. Then, the following operator (Kleene star operator) takes the matrix A to the sum Note that, under the condition Tr(A) ≤ 1, the inequality A m ≤ A * is valid for all integer m ≥ 0 (see, e.g., [17]).
The next result, which is obtained in [13], offers a complete solution.
Theorem 2. For any matrix A, the following statements hold.
1. If Tr(A) ≤ 1, then all regular solutions to (1) are given in parametric form by x = A * u, where u is any regular vector.
2. If Tr(A) > 1, then there is only the trivial solution x = 0.

Two-sided inequality
We are now in a position to formulate the problem of interest. Given matrices A, B ∈ X m×n , the problem is to find regular vectors x ∈ X that satisfy the inequality Ax ≤ Bx.
It is not difficult to verify that the solution set of inequality (2) is closed under vector addition and scalar multiplication. Indeed, let x and y be vectors such that the inequalities Ax ≤ Bx and Ay ≤ By hold, and consider any vector z = αx ⊕ βy , where α and β are scalars. Then, we have Az = αAx ⊕ βAy ≤ αBx ⊕ βBy = Bz , which means that the vector z is a solution of inequality (2) as well.
Without loss of generality, we may assume that both matrices A and B are row-regular. Otherwise, if the matrix A has a zero row, say row i, then the corresponding scalar inequality a i1 x 1 ⊕ · · · ⊕ a in x n ≤ b i1 x 1 ⊕ · · · ⊕ b in x n trivially holds, and thus this inequality can be removed, whereas row i eliminated from both matrices. Assuming that the matrix A is rowregular, suppose the matrix B has a zero row i, which leads to the inequality a i1 x 1 ⊕ · · · ⊕ a in x n ≤ 0. This inequality holds only if each unknown x j with a ij = 0 is set to zero, which results in a non-regular solution of no interest.
Under additional assumptions, some solutions of inequality (2) can be directly obtained in explicit form. As an example, consider the next result.
Lemma 3. Let A and B be row-regular matrices such that Tr(B − A) ≤ 1. Then, inequality (2) has solutions given by Proof. It follows from Theorem 2 that the condition Tr(B − A) ≤ 1 is equivalent to the existence of regular solutions x of the inequality B − Ax ≤ x. Moreover, all regular solutions of this inequality are given by where u ∈ X n is any regular vector of parameters.
Since the matrix B is row-regular, and thus BB − ≥ I , the multiplication of the inequality B − Ax ≤ x by B on the left yields Ax ≤ BB − Ax ≤ Bx, which shows that all solutions of this inequality satisfy inequality (2) as well.
4 Complete solution of two-sided inequality 4

.1 Solution using matrix sparsification
We now derive a complete solution of inequality (2) by using a matrix sparsification technique to represent all solutions as a family of solution sets in parametric form. Each member of the family is described by a generating matrix that is calculated with a strictly row-monomial matrix, obtained from the matrix B on the right-hand side of (2).
To derive the solution of inequality (2), we first set to 0 each entry of the matrices A and B that do not affect the set of regular solutions of this inequality. The next statement introduces the sparsified matrix obtained as a result.
Then, replacing the matrix A by A and B by B does not change the regular solutions of inequality (2).
Proof. For each i = 1, . . . , m, consider all nonzero solutions x 1 , . . . , x n ∈ X of the inequality, which correspond to row i in the matrices A and B , and takes the form Suppose that the condition a ij ≤ b ij holds for some j = 1, . . . , n. Then, the inequality a ij x j ≤ b ij x j ≤ b i1 x 1 ⊕ · · · ⊕ b in x n is valid for all x j ∈ X, which shows that the term a ij x j cannot be greater than the right-hand side of inequality (4). Observing that this term cannot violate (4), it can be eliminated by setting a ij = 0.
If the condition a ij > b ij is satisfied, then the inequality a ij x j > b ij x j is valid for all x j = 0. Since the term b ij x j does not contribute to the right-hand side of (4), and thus cannot make this inequality hold, we can set b ij = 0 without affecting all regular solutions.
In what follows, the matrices A and B , obtained from the matrices A and B in (2) according to (3), is referred to as refined matrices of the two-sided inequality, or simply as refined matrices.
Theorem 5. Let A and B be refined row-regular matrices, and G be a strictly row-monomial matrix that is obtained from B by fixing one non-zero entry in each row while setting the others to 0. Denote by G the set of the matrices G, which satisfy the condition tr H n ≤ 1, where H = G − (A⊕B).
Then, all regular solutions of inequality (2) are given by the conditions Proof. We prove the theorem by showing that any regular solution, if it exists, of inequality (2) is a vector given by the conditions at (5), and vice versa. We take a regular solution x = (x j ) of (2) with the matrices A = (a ij ) and B = (b ij ), and examine the scalar inequality, corresponding to row p of the matrices, in the form Suppose that this inequality holds for some x 1 , . . . , x n , and consider the sum on the right-hand side. Since the order defined by the relation ≤ is linear, we can pick out a term, say b pq x q , that is maximal among all terms, and thereby provides the value of the sum. Then, we can replace (6) by two inequalities b pq x q ≥ b p1 x 1 ⊕ · · · ⊕ b pn x n and b pq x q ≥ a p1 x 1 ⊕ · · · ⊕ a pn x n , where b pq > 0. We combine these inequalities to obtain the equivalent Further assume that we select maximum terms in all scalar inequalities in (2), and then substitute an inequality in the form of (7) for each scalar inequality. Let G be a strictly row-monomial matrix that is formed from B by fixing the entry, which corresponds to the maximum term in each row, while setting the other entries to 0. By using the matrix G, the inequalities obtained for each row are combined into the vector inequality Gx ≥ (A ⊕ B)x. Since the matrix G is strictly row-monomial, this vector inequality is equivalent to the inequality x ≥ G − (A ⊕ B)x, which, with the notation H = G − (A ⊕ B), takes the form x ≥ Hx.
By assumption, the inequality x ≥ Hx has a regular solution x. Then, it follows from Theorem 2 that the condition Tr(H) ≤ 1 holds, whereas all regular solutions of the inequality are given by x = H * u, where u is a regular vector.
Consider now a vector x = H * u, where u is a regular vector, and H = G − (A⊕B) with is a strictly row-monomial matrix G such that Tr(H) ≤ 1.
To verify that x satisfies inequality (2), we note that H + = HH * ≤ H * since Tr(H) ≤ 1. Moreover, we see that By using the above inequalities, we obtain Therefore, we have Bx = BH * u ≥ AH * u = Ax, and thus x satisfies (2).
It remains to verify that H * = I ⊕ H n−1 and Tr(H) = tr H n to represent the solution as in the statement of the theorem. We observe that and thus conclude that H m+1 ≥ H m for all integer m > 0. Then, the equalities H * = I ⊕ H ⊕ · · · ⊕ H n−1 = I ⊕ H n−1 and Tr(H) = tr H ⊕ · · · ⊕ tr H n = tr H n hold, which completes the proof.

Closed-form representation of solution
The next result shows how to combine all solutions of inequality (2) to represent them in a compact parametric form using a single generating matrix. Corollary 6. Under the conditions and notation of Theorem 5, denote by S the matrix whose columns form the maximal independent system of columns in the matrices Then, all regular solutions of inequality (2) are given in parametric form by Proof. It follows from Theorem 5 that the solution set is the union of sets, each generated by the columns of the matrix I ⊕ H n−1 = I ⊕ (G − (A ⊕ B)) n−1 for all G ∈ G . Observing that the solution set is closed under vector addition and scalar multiplication, we conclude that this union is the linear span of all columns in the generating matrices. Furthermore, we reduce the set of columns by eliminating those, which are linearly dependent on others, and thus can be deleted without affecting the entire linear span. With the matrix S formed from the reduced set of columns, all solutions are given in parametric form by x = Sv , where v is any regular vector of appropriate size.

Computational implementation of solution
To derive a complete solution of the two-sided inequality at (2), we offer a solution procedure that involves: (i) preliminary refinement of the matrices, (ii) generation of the solution sets, and (iii) derivation of the solution matrix.

Refinement of matrices
We begin the solution procedure with the refinement of the matrices according to Lemma 4. Suppose that the matrices A and B are already refined, and look for zero rows in these matrices. Each zero row, if it exists in the matrix A, corresponds to a scalar inequality that has 0 on the left, and thus trivially holds. As a result, the inequality (2) can be simplified by eliminating the scalar inequalities with zero left-hand side, which yields further refinement of the matrices A and B by removing the corresponding rows.
Assume the matrix A has no zero rows, and examine rows in B . Each zero row in the matrix B yields a scalar inequality in (2) that has 0 on the right. Such a scalar inequality does not admit regular solutions, which means that inequality (2) has no regular solutions as well, and thereby completes the entire procedure.
Provided that both matrices A and B upon refinement are columnregular, the procedure passes to the next step of generating the family of solution sets.

Generation of solution sets
Consider the solution offered to inequality (2) by Theorem 2 in the form of a family of solutions sets, and note that each member of the family involves a strictly row-monomial matrix G to calculate the corresponding generating matrix I ⊕ H n−1 from the matrix H = G − (A ⊕ B). The strictly row-monomial matrices are successively obtained from the matrix B by sparsification to set to 0 all but one of the entries in each row of the matrix. Since the number of the strictly row-monomial matrices to examine may be excessively large, we propose a backtracking procedure that aims at rejecting in advance those matrices, which cannot extend the set of solution, and thus allows to reduce the number of matrices under examination.
The procedure consecutively checks rows i = 1, . . . , n of the matrix B to find and fix, over all j = 1, . . . , n, a non-zero entry b ij , while setting the other entries to zero. The selection of a non-zero entry b pq implies that the term b pq x q is taken maximal over all q , which establishes relations between x q and x j with j = q . We exploit these relations to modify non-zero entries in the remaining rows by setting to 0, provided that these entries cannot affect the corresponding scalar inequalities in (2). One step of the procedure is completed when a non-zero entry is fixed in the last row, which makes a new strictly row-monomial matrix is fully defined.
A new step of the procedure is to take the next non-zero entry in the current row if such an entry exists. Otherwise, the procedure has to go back to the previous row to cancel the last selection of non-zero entry, and roll back all modifications made to the matrix in accordance with this selection. Next, the procedure fixes a new non-zero entry in this row, if it exists, or continues back to the previous rows until an unexplored non-zero entry is found. On selection of a new entry, the procedure continues forward to modify and fix non-zero entries in the next rows.
The procedure is repeated until no more non-zero entries can be selected in the first row. A description of the procedure in recursive form is given in Algorithm 5.1. To describe the row modification routine in the procedure in more detail, suppose there are non-zero entries fixed in rows i = 1, . . . , p − 1, and the procedure now selects the entry b pq in row p. Since this selection implies that b pq x q is assumed to be the maximum term with b pq > 0 in the righthand side of inequality (6), it follows from (7) that the inequality x q ≥ b −1 pq (a pj ⊕ b pj )x j holds for all j = 1, . . . , n.
We use two criteria to test whether an entry in the matrix B can be eliminated in the course of the building of a row-monomial matrix. Consider the inequality a i1 x 1 ⊕ · · · ⊕ a in x n ≤ b i1 x 1 ⊕ · · · ⊕ b in x n for i = p + 1, . . . , n. Provided the condition b iq b −1 pq (a pj ⊕b pj ) ≥ a ij is valid for all j , the term b iq x q alone makes this inequality hold, because b iq x q ≥ b iq b −1 pq (a pj ⊕b pj )x j ≥ a ij x j . Observing that the other terms do not contribute to the inequality, the entries b ij can be set to 0 for all j = q without affecting the solution set under construction.
If the above condition is not satisfied, verify the condition b iq b −1 pq (a pj ⊕ b pj ) ≥ b ij for all j = q . Suppose that the last condition holds for some j , and therefore, b iq Since the term b ij x j is now dominated by b iq x q , it does not affect the right-hand side of the inequality, which allows to set b ij = 0.

Derivation of solution matrix
The solution matrix S is formed by combining all columns of the matrices, which generate the members of the solution family. To eliminate linear dependent columns, the procedure examines each new generating matrix as this matrix becomes available. A column of the generating matrix is accepted to extend the matrix S under construction if this column is linearly independent of columns in S , or rejected otherwise.

Numerical example
To illustrate the solution procedure, we present an example problem to solve inequality (2) in terms of the R max,+ semifield. Suppose that the matrices on the left-and right-hand sides of the inequality are given by where we use the symbol 0 = −∞ to save writing. To solve the inequality, we first replace the matrices A 0 and B 0 by the refined matrices A and B , and calculate the sum of the refined matrices to obtain We start deriving the sparse matrices G by fixing the nonzero entry b 11 in the first row of the matrix B . Next, we apply two criteria to check if any nonzero entries in the next rows can be replaced by zero. Observing that b 21 b −1 11 (a 13 ⊕b 13 ) = 2 < a 23 = 3, we see that the first criterion does not allow to eliminate b 22 . At the same time, we have b 21 b −1 11 (a 12 ⊕b 12 ) = 1 > b 22 = 0, which means that b 22 can be eliminated according to the second criterion.
Finally, two nonzero entries in the third row yield two sparsified matrices Since the first two columns in this matrix coincide, we drop one of them to represent all regular solutions of the two-sided inequality as