Sage Journals: Discover world-class research

Abstract

Algorithms for noise removal are either complex or ineffective, and the optimal control with inequality constrains makes the algorithm even more complex. Now the condition is changed completely, and the tropical algebra is an extremely simple tool for this purpose. The tropical algebra-based filter has obvious advantages over traditional ones, and an inequality constrain can be converted to a tropical polynomial, making the tropical algebra much attractive in engineering applications. In this paper, idempotents on multiplicative semigroups of tropical matrices are studied. First, the concepts of tropical algebra and the semigroup of tropical matrices under multiplication are introduced. Second, the structure of idempotents on the semigroup of $3 \times 3$ tropical matrices under multiplication is given. Finally, as examples, the tropical addition is used as a filter for noise removal, and a simple optimization is given where the constraint is given by the tropical algebra. The paper has opened the path for a new way to noise removal and optimization.

Keywords

tropical algebra matrix semigroups idempotents

Introduction

The tropical algebra follows the following simple tropical multiplication and tropical addition¹

a \otimes b = a + b

(1)

a \oplus b = \max {a, b}

(2)

where

a, b \in R \cup {- \infty}

, and

R

is a real number set. As an example, we can find

5 \otimes 10 = 15

and

5 \oplus 10 = 10

. The tropical algebra has been attracted much attention in both mathematics and engineering.

Tropical algebra¹ is a very important content of the algebraic theory. Since the 1970s, it has become a very active research field because it can be applied to the combinatorial optimization,² the discrete event system analysis,³ the statistical inference,⁴ and the algebraic geometry.⁵ The basic idea on the tropical algebra was first proposed to study economical problems to depict the total profit with maximal and minimal levels, and the concept is extremely useful for noise removal.⁶ The tropical addition is a good filtering algorithm to detect and remove the noise.⁷

The tropical algebra has some special properties to describe discontinuous functions which are widely appeared in the optimal control. For example, we consider the following polynomial

y (x) = (3 \otimes x) \oplus 6

(3)

By a simple calculation, we have

y (x) = (3 + x) \oplus 6 = \max {3 + x, 6}

(4)

Equation (4) can be written in a traditional way in an explicit form

y (x) = {\begin{array}{c} 6, & x \leq 3 \\ 3 + x, & x > 3 \end{array}

(5)

So the tropical algebra is extremely suitable for dealing with inequality constrains in the optimization theory.^8,9 In the practical applications, the idempotent method is widely used to nonlinear control problems.¹⁰ We call $a$ is an idempotent of semigroup $S$ when a² = a.

As an example, we can find $5 \oplus 5 = 5$ , so 5 is an idempotent of $(R \cup {- \infty}, \oplus)$ . As another example, we can find that

\begin{array}{l} {(\begin{array}{c} - \infty & - \infty \\ - \infty & - \infty \end{array})}^{2} = (\begin{array}{c} - \infty & - \infty \\ - \infty & - \infty \end{array}) (\begin{array}{c} - \infty & - \infty \\ - \infty & - \infty \end{array}) \\ = (\begin{array}{c} (- \infty \otimes - \infty) \oplus (- \infty \otimes - \infty) & (- \infty \otimes - \infty) \oplus (- \infty \otimes - \infty) \\ (- \infty \otimes - \infty) \oplus (- \infty \otimes - \infty) & (- \infty \otimes - \infty) \oplus (- \infty \otimes - \infty) \end{array}) \\ = (\begin{array}{c} - \infty & - \infty \\ - \infty & - \infty \end{array}) . \end{array}

(\begin{array}{c} - \infty & - \infty \\ - \infty & - \infty \end{array})

is an idempotent of

{((R \cup {- \infty})}^{2 \times 2}, \cdot)

. The idempotent method can be easily incorporated with nonlinear control problems,^10,11 and idempotents on multiplicative semigroups of tropical matrices have been catching skyrocketing attention.^9-11

Idempotents of $3 \times 3$ tropical matrix semigroups

Idempotents have an important influence on the algebraic structure of semigroups.

The tropical algebra was first proposed by Cuninghame-Green,¹ and it is the algebraic system $(T = R \cup {- \infty}, \oplus, \otimes)$ , where $\oplus$ means the maximum value and $\otimes$ is the ordinary addition. Tropical algebra is an important research object of algebraic theory; the semigroup of tropical matrices under multiplication is a main research content of tropical algebra, including its structure of multiplicative semigroups, Green’s relations, regularity, and abundance. In recent years, the study of the semigroup of tropical matrices under multiplication has become a hot research topic. In 1988, Olsder and Roos¹² introduced the concept of matrix characteristic equation of tropical algebra and studied Gramer rule and Cayley-Hamilton theorem of matrix on tropical algebra. In 2001, Il’in¹³ gave the equivalent characterization of the multiplicative semigroup regularity of matrices over arbitrary semirings. In 2008, Develin, Santos, and Sturmfels¹⁴ studied the rank of tropical matrices under three different definitions. In 2010, Izhakian and Margolis¹⁵ studied the identities of semigroups of tropical matrices. In 2011, Johnson and Kambites¹⁶ studied the algebraic structure of the $2 \times 2$ tropical matrix multiplication semigroups, the Green’s relations of multiplicative semigroups of $2 \times 2$ tropical matrices, and the idempotents of multiplicative semigroups of $2 \times 2$ order tropical matrices are given. In 2012, Hollings and Kambites¹⁷ described the Green- $D$ relation on the multiplicative semigroups of $n \times n$ tropical matrices. In 2013, Johnson and Kambites¹⁸ studied the Green $J$ -order relation and $J$ equivalence relation. In 2016, Izhakian, Johnson, and Kambites¹⁹ provided the sufficient and necessary conditions for the semigroup regularization of the multiplicative semigroups of $n \times n$ tropical matrices from the perspective of modular theory. In 2018, Izhakian and Johnson²⁰ studied the structure of finite the group of tropical matrices under multiplication. In 2018, Yang Lin²¹ discussed the maximal subgroup of the semigroup of tropical matrices under multiplication, a characterization of nonsingular regular $D$ -classes is given. In 2019, Gould and Johnson²² studied the Green’s relations, regularity and abundance of matrix semigroups over semirings.

On this basis, this paper will study on the structure of idempotents²³ of the semigroup of $3 \times 3$ tropical matrices under multiplication.

Tropical algebra and its basic properties

Definition 1

Let $T = R \cup {- \infty}$ , define two binary operations $\oplus$ and $\otimes$ on $T$ as follows

(\forall a, b \in T) a \oplus b = \max {a, b}, a \otimes b = a + b,

(T, \oplus, \otimes)

is called the tropical algebra. From the tropical algebraic we get:

(i) $(T, \oplus)$ is a commutative monoid with $- \infty$ as zero element;

(ii) $(T, \otimes)$ is a commutative monoid with $0$ as identity element;

(iii) For any $a, b, c \in T$ , there are

$\begin{array}{l} a \otimes (b \oplus c) = (a \otimes b) \oplus (a \otimes c), \\ (a \oplus b) \otimes c = (a \otimes c) \oplus (b \otimes c); \end{array}$

(iv) For any $a, b \in T$ , $a \oplus a = a, a \oplus b = b \oplus a, a \otimes b = b \otimes a;$

(v) For any $a \in T$ , $a \otimes (- \infty) = (- \infty) \otimes a = - \infty$ .

The above conclusion shows that $(T, \oplus, \otimes)$ is a commutative semiring, called a tropical semiring. Tropical matrix algebra is linear algebra where the base field is replaced by the tropical semiring. For any $a \in T \ {- \infty}$ , we use $a^{- 1}$ to represent the multiplicative inverse of $a$ , actually, $a^{- 1}$ is $- a$ in the traditional sense.

For positive integers $n, m$ , let $M_{m \times n} (T)$ be a matrix of order $m \times n$ with elements from $T$ , in particular, when $m = n$ , abbreviated as $M_{n} (T)$ (see Ref. [16]). The operations of $\oplus$ and $\otimes$ on $T$ can be exported $M_{n} (T)$ corresponding operations. In fact, for $A, B \in M_{n} (T)$ there are

\begin{array}{l} {(A \otimes B)}_{i, j} = \overset{n}{\underset{k = 1}{\oplus}} (A_{i, k} \otimes B_{k, j}) \\ {(A \oplus B)}_{i, j} = (A_{i, j} \oplus B_{i, j}) \end{array}

For any $1 \leq i, j \leq n$ , we use $A_{i, j}$ to denote the element at the intersection of row $i$ and column $j$ of. We usually use $A B$ instead of A $\otimes B$ . Johnson and Kambites¹⁶ have pointed out that $M_{n} (T)$ is a semiring and its multiplicative identity is

I_{n} = (\begin{array}{c} 0 & - \infty & \dots & - \infty \\ - \infty & 0 & \dots & - \infty \\ ⋮ & ⋮ & ⋱ & ⋮ \\ - \infty & - \infty & \dots & 0 \end{array}) .

and the addition identity is

O = (\begin{array}{c} - \infty & \dots & - \infty \\ ⋮ & ⋱ & ⋮ \\ - \infty & \dots & - \infty \end{array}) .

We call $(M_{n} (T), \oplus, \otimes)$ a tropical matrix semiring.

Simply speaking, a tropical semiring is defined as two operations $\oplus$ and $\otimes$ on a tropic algebra $T$ , where $T$ is closed in operations $\oplus$ , satisfies the combination law and the commutative law, and the addition zero element is $- \infty$ , also $T$ is closed in operations $\otimes$ , satisfies the combination law and the commutative law, and the multiplicative identity element is 0, besides the operations of $\oplus$ and $\otimes$ satisfy the distribution law.

Main results

Theorem 1

Let $T$ be a tropical semiring. The idempotents on $M_{3} (T)$ have the following structure

(\begin{array}{c} - \infty & - \infty & - \infty \\ - \infty & - \infty & - \infty \\ - \infty & - \infty & - \infty \end{array}), (\begin{array}{c} 0 & A_{1,2} & A_{1,3} \\ A_{2,1} & 0 & A_{2,3} \\ A_{3,1} & A_{3,2} & 0 \end{array}), (\begin{array}{c} A_{1,3} A_{3,1} & A_{1,3} A_{3,2} & A_{1,3} \\ A_{2,3} A_{3,1} & A_{2,3} A_{3,2} & A_{2,3} \\ A_{3,1} & A_{3,2} & 0 \end{array}),

(\begin{array}{c} A_{1,2} A_{2,1} & A_{1,2} & A_{1,2} A_{2,3} \\ A_{2,1} & 0 & A_{2,3} \\ A_{3,2} A_{2,1} & A_{3,2} & A_{3,2} A_{2,3} \end{array}), (\begin{array}{c} 0 & A_{1,2} & A_{1,3} \\ A_{2,1} & A_{2,1} A_{1,2} & A_{2,1} A_{1,3} \\ A_{3,1} & A_{3,1} A_{1,2} & A_{3,1} A_{1,3} \end{array}), (\begin{array}{c} 0 & A_{1,2} & A_{1,3} \\ A_{2,1} & A_{2,1} A_{1,2} \oplus A_{2,3} A_{3,2} & A_{2,3} \\ A_{3,1} & A_{3,2} & 0 \end{array}),

(\begin{array}{c} 0 & A_{1,2} & A_{1,3} \\ A_{2,1} & 0 & A_{2,3} \\ A_{3,1} & A_{3,2} & A_{3,1} A_{1,3} \oplus A_{3,2} A_{2,3} \end{array}), (\begin{array}{c} A_{1,2} A_{2,1} \oplus A_{1,3} A_{3,1} & A_{1,2} & A_{1,3} \\ A_{2,1} & 0 & A_{2,3} \\ A_{3,1} & A_{3,2} & 0 \end{array})

where A_{i, j} \in T and A_{i, j} A_{j, i} \leq 0, A_{i, k} A_{k, j} \leq A_{i, j} (i \neq j) .

Proof. Let $A = (\begin{array}{c} A_{1,1} & A_{1,2} & A_{1,3} \\ A_{2,1} & A_{2,2} & A_{2,3} \\ A_{3,1} & A_{3,2} & A_{3,3} \end{array})$ , then

A^{2} = (\begin{array}{c} \overset{3}{\underset{k = 1}{\oplus}} (A_{1, k} \otimes A_{k, 1}) & \overset{3}{\underset{k = 1}{\oplus}} (A_{1, k} \otimes A_{k, 2}) & \overset{3}{\underset{k = 1}{\oplus}} (A_{1, k} \otimes A_{k, 3}) \\ \overset{3}{\underset{k = 1}{\oplus}} (A_{2, k} \otimes A_{k, 1}) & \overset{3}{\underset{k = 1}{\oplus}} (A_{2, k} \otimes A_{k, 2}) & \overset{3}{\underset{k = 1}{\oplus}} (A_{2, k} \otimes A_{k, 3}) \\ \overset{3}{\underset{k = 1}{\oplus}} (A_{3, k} \otimes A_{k, 1}) & \overset{3}{\underset{k = 1}{\oplus}} (A_{3, k} \otimes A_{k, 2}) & \overset{3}{\underset{k = 1}{\oplus}} (A_{3, k} \otimes A_{k, 3}) \end{array})

A_{1,1} = \max {A_{1,1} + A_{1,1}, A_{1,2} + A_{2,1}, A_{1,3} + A_{3,1}}

(6)

A_{1,2} = \max {A_{1,1} + A_{1,2}, A_{1,2} + A_{2,2}, A_{1,3} + A_{3,2}}

(7)

A_{1,3} = \max {A_{1,1} + A_{1,3}, A_{1,2} + A_{2,3}, A_{1,3} + A_{3,3}}

(8)

A_{2,1} = \max {A_{2,1} + A_{1,1}, A_{2,2} + A_{2,1}, A_{2,3} + A_{3,1}}

(9)

A_{2,2} = \max {A_{2,1} + A_{1,2}, A_{2,2} + A_{2,2}, A_{2,3} + A_{3,2}}

(10)

A_{2,3} = \max {A_{2,1} + A_{1,3}, A_{2,2} + A_{2,3}, A_{2,3} + A_{3,3}}

(11)

A_{3,1} = \max {A_{3,1} + A_{1,1}, A_{3,2} + A_{2,1}, A_{3,3} + A_{3,1}}

(12)

A_{3,2} = \max {A_{3,1} + A_{1,2}, A_{3,2} + A_{2,2}, A_{3,3} + A_{3,2}}

(13)

A_{3,3} = \max {A_{3,1} + A_{1,3}, A_{3,2} + A_{2,3}, A_{3,3} + A_{3,3}}

(14)

From equations (6), (10), and (14), we have $A_{1,1} + A_{1,1} \leq A_{1,1}, A_{2,2} + A_{2,2} \leq A_{2,2}, A_{3,3} + A_{3,3} \leq A_{3,3}$ . So $A_{1,1} \leq 0, A_{2,2} \leq 0, A_{3,3} \leq 0$ . Thus, there are the following eight situations:

Situation One: $A_{1,1} {< 0, A}_{2,2} {< 0, A}_{3,3} < 0 .$

From equation (7), we have $A_{1,2} = A_{1,3} + A_{3,2}$ , from equation (8), we get $A_{1,3} = A_{1,2} + A_{2,3}$ , from equation (9), we obtain $A_{2,1} = A_{2,3} + A_{3,1}$ , by equation (11), we obtain that $A_{2,3} = A_{2,1} + A_{1,3}$ , equation (12) leads to $A_{3,1} = A_{3,2} + A_{2,1}$ , and from equation (13) we obtain $A_{3,2} = A_{3,1} + A_{1,2}$ .

From equation (9) and equation (11), we have $A_{2,1} = A_{2,1} + A_{1,3} + A_{3,1}$ , and because $A_{1,1} < 0$ we get $A_{1,3} + A_{3,1} < 0$ so $A_{2,1} = - \infty$ , thus $A_{3,1} = - \infty$ . Similarly, there is $A_{2,3} = - \infty$ . From $A_{1,3} = A_{1,2} + A_{2,3}$ , we get $A_{1,3} = - \infty$ . At this time, $A_{1,1} = A_{1,1} + A_{1,1}$ and $A_{1,1} < 0$ so $A_{1,1} = - \infty$ . From equation (7) and equation (13), we get $A_{1,2} = A_{1,3} + A_{3,1} + A_{1,2}$ , and by $A_{1,3} = - \infty$ so $A_{1,2} = - \infty$ . Similarly, we get $A_{3,2} = - \infty$ . In this case, $A_{2,2} = A_{2,2} + A_{2,2}$ and so $A_{2,2} = - \infty$ . Similarly, $A_{3,3} = - \infty$ . So, we have

A = (\begin{array}{c} - \infty & - \infty & - \infty \\ - \infty & - \infty & - \infty \\ - \infty & - \infty & - \infty \end{array}) .

Situation Two: $A_{1,1} < 0, A_{2,2} < 0, A_{3,3} = 0 .$

By equations (6), (10), and (14), we get $A_{1,2} + A_{2,1} < 0, A_{3,2} + A_{2,3} < 0, A_{1,3} + A_{3,1} < 0$ .

By equation (7), we have $A_{1,2} = A_{1,3} + A_{3,2}$ . By equation (8), we obtain $A_{1,3} = \max {A_{1,2} + A_{2,3}, A_{1,3}}$ , by equation (9) we know $A_{2,1} = A_{2,3} + A_{3,1}$ , by equation (11) we have $A_{2,3} = \max {A_{2,1} + A_{1,3}, A_{2,3}}$ , by equation (12) we get $A_{3,1} = \max {A_{3,2} + A_{2,1}, A_{3,1}}$ , and by equation (13) we obtain $A_{3,2} = \max {A_{3,1} + A_{1,2}, A_{3,2}}$ .

By equations (7) and (8), if $A_{1,3} = A_{1,2} + A_{2,3}$ , then

A_{1,3} = (A_{1,3} + A_{3,2}) + A_{2,3} = A_{1,3} + (A_{3,2} + A_{2,3}) < A_{1,3},

This is a contradiction. Therefore, $A_{1,3} > A_{1,2} + A_{2,3}$ . In the same way, we can get $A_{2,3} > A_{2,1} + A_{1,3}$

$A_{3,1} > A_{3,2} + A_{2,1}, A_{3,2} > A_{3,1} + A_{1,2}$ . By equations (7) and (9) we have

A_{1,2} + A_{2,1} = A_{1,3} + A_{3,2} + A_{2,3} + A_{3,1} = (A_{1,3} + A_{3,1}) + (A_{3,2} + A_{2,3}) < A_{1,3} + A_{3,1}

Since $A_{1,1} < 0$ , so $A_{1,1} = A_{1,3} + A_{3,1}$ . It can be obtained $A_{2,2} = A_{2,3} + A_{3,2}$ in the same way.

So we have

A = (\begin{array}{c} A_{1,3} A_{3,1} & A_{1,3} A_{3,2} & A_{1,3} \\ A_{2,3} A_{3,1} & A_{2,3} A_{3,2} & A_{2,3} \\ A_{3,1} & A_{3,2} & 0 \end{array}) and A_{i, k} A_{k, j} \leq A_{i, j} (i \neq j) .

Situation Three: $A_{1,1} < 0, A_{2,2} = 0, A_{3,3} < 0 .$

By equations (6), (10), and (14), we have $A_{1,2} + A_{2,1} < 0, A_{3,2} + A_{2,3} < 0, A_{1,3} + A_{3,1} < 0$ . By equation (7) we get $A_{1,2} = \max {A_{1,2}, A_{1,3} + A_{3,2}}$ , by equation (8) we know $A_{1,3} = A_{1,2} + A_{2,3}$ , by equation (9) we get $A_{2,1} = \max {A_{2,1}, A_{2,3} + A_{3,1}}$ , by equation (11) we obtain $A_{2,3} = \max {A_{2,1} + A_{1,3}, A_{2,3}}$ , by equation (12) we have $A_{3,1} = A_{3,2} + A_{2,1}$ , and by equation (13) we get $A_{3,2} = \max {A_{3,1} + A_{1,2}, A_{3,2}}$ .

By equations (7) and (8), if $A_{1,2} = A_{1,3} + A_{3,2}$ , then

A_{1,2} = A_{1,2} + A_{2,3} + A_{3,2} = A_{1,2} + (A_{2,3} + A_{3,2}) < A_{1,2}

This is a contradiction. Therefore, $A_{1,2} > A_{1,3} + A_{3,2}$ . In the same way, we can get

$A_{2,1} > A_{2,3} + A_{3,1}$ , $A_{2,3} > A_{2,1} + A_{1,3}, A_{3,2} > A_{3,1} + A_{1,2}$ .

By equations (8) and (12) we have

A_{1,3} + A_{3,1} = {A_{1}}_{, 2} + A_{2,3} + A_{3,2} + A_{2,1} = ({A_{2}}_{, 3} + A_{3,2}) + (A_{1,2} + A_{2,1}) < A_{1,2} + A_{2,1}

and since

A_{1,1} < 0

, so

A_{1,1} = A_{1,2} + A_{2,1}

. It can be obtained

A_{3,3} = A_{3,2} + A_{2,3}

in the same way. So we have

A = (\begin{array}{c} A_{1,2} A_{2,1} & A_{1,2} & A_{1,2} A_{2,3} \\ A_{2,1} & 0 & A_{2,3} \\ A_{3,2} A_{2,1} & A_{3,2} & A_{3,2} A_{2,3} \end{array}) and A_{i, k} A_{k, j} \leq A_{i, j} (i \neq j) .

Situation Four: $A_{1,1} = 0, A_{2,2} < 0, A_{3,3} < 0 .$

By equations (6), (10), and (14), we have $A_{1,2} + A_{2,1} < 0, A_{3,2} + A_{2,3} < 0, A_{1,3} + A_{3,1} < 0$ . By equation (7), we get $A_{1,2} = \max {A_{1,2}, A_{1,3} + A_{3,2}}$ , by equation (8) we know $A_{1,3} = \max {A_{1,3}, A_{1,2} + A_{2,3}}$ , by equation (9) we get $A_{2,1} = \max {A_{2,1}, A_{2,3} + A_{3,1}}$ , by equation (11) we obtain $A_{2,3} = A_{2,1} + A_{1,3}$ , by equation (12) we have $A_{3,1} = \max {A_{3,1}, A_{3,2} + A_{2,1}}$ , and by equation (13) we get $A_{3,2} = A_{3,1} + A_{1,2}$ .

By equations (7) and (13), if $A_{1,2} = A_{1,3} + A_{3,2}$ , then

A_{1,2} = A_{1,3} + (A_{3,1} + A_{1,2}) = (A_{1,3} + A_{3,1}) + A_{1,2} < A_{1,2}

This is a contradiction. Therefore, $A_{1,2} > A_{1,3} + A_{3,2}$ . In the same way, we can get $A_{2,1} > A_{2,3} + A_{3,1}$ ,

$A_{1,3} > A_{1,2} + A_{2,3}, A_{3,1} > A_{3,2} + A_{2,1}$ . In the same way, we can get $A_{2,1} > A_{2,3} + A_{3,1}$ ,

$A_{1,3} > A_{1,2} + A_{2,3}, A_{3,1} > A_{3,2} + A_{2,1}$ . By equations (11) and (13), we have

A_{2,3} + A_{3,2} = (A_{2,1} + A_{1,3}) + (A_{3,1} + A_{1,2}) = (A_{2,1} + A_{1,2}) + (A_{1,3} + A_{3,1}) < A_{2,1} + A_{1,2}

and since

A_{2,2} < 0

, thus

A_{2,2} = A_{2,1} + A_{1,2}

. It can be obtained

A_{3,3} = A_{3,2} + A_{2,3}

in the same way. So we conclude

A = (\begin{array}{c} 0 & A_{1,2} & A_{1,3} \\ A_{2,1} & A_{2,1} A_{1,2} & A_{2,1} A_{1,3} \\ A_{3,1} & A_{3,1} A_{1,2} & A_{3,1} A_{1,3} \end{array}) and A_{i, k} A_{k, j} \leq A_{i, j} (i \neq j) .

Situation Five: $A_{1,1} < 0, A_{2,2} = 0, A_{3,3} = 0 .$

By equations (6), (10), and (14), we have $A_{1,2} + A_{2,1} < 0, A_{3,2} + A_{2,3} \leq 0, A_{1,3} + A_{3,1} < 0$ . By equation (6), we have $A_{1,1} = {A_{1,2} A_{2,1}, A_{1,3} A_{3,1}}$ . So we have

A = (\begin{array}{c} A_{1,2} A_{2,1} \oplus A_{1,3} A_{3,1} & A_{1,2} & A_{1,3} \\ A_{2,1} & 0 & A_{2,3} \\ A_{3,1} & A_{3,2} & 0 \end{array}) and A_{i, k} A_{k, j} \leq A_{i, j} (i \neq j) .

Situation Six: $A_{1,1} = 0, A_{2,2} < 0, A_{3,3} = 0 .$

By equations (6), (10), and (14), we have $A_{1,2} + A_{2,1} < 0, A_{3,2} + A_{2,3} < 0, A_{1,3} + A_{3,1} \leq 0$ . By equation (10) we have $A_{2,2} = {A_{2,1} A_{1,2}, A_{2,3} A_{3,2}}$ . So we obtain

A = (\begin{array}{c} 0 & A_{1,2} & A_{1,3} \\ A_{2,1} & A_{2,1} A_{1,2} \oplus A_{2,3} A_{3,2} & A_{2,3} \\ A_{3,1} & A_{3,2} & 0 \end{array}) and A_{i, k} A_{k, j} \leq A_{i, j} (i \neq j) .

Situation Seven: $A_{1,1} = 0, A_{2,2} = 0, A_{3,3} < 0 .$

By equations (6), (10), and (14), we have $A_{1,2} + A_{2,1} < 0, A_{3,2} + A_{2,3} < 0, A_{1,3} + A_{3,1} \leq 0$ . By equation (14) we have $A_{3,3} = {A_{3,1} A_{1,3}, A_{3,2} A_{2,3}}$ . So we get

A = (\begin{array}{c} 0 & A_{1,2} & A_{1,3} \\ A_{2,1} & 0 & A_{2,3} \\ A_{3,1} & A_{3,2} & A_{3,1} A_{1,3} \oplus A_{3,2} A_{2,3} \end{array}) and A_{i, k} A_{k, j} \leq A_{i, j} (i \neq j) .

Situation Eight: $A_{1,1} = 0, A_{2,2} = 0, A_{3,3} = 0 .$ So we have

A = (\begin{array}{c} 0 & A_{1,2} & A_{1,3} \\ A_{2,1} & 0 & A_{2,3} \\ A_{3,1} & A_{3,2} & 0 \end{array}) and A_{i, k} A_{k, j} \leq A_{i, j} (i \neq j) .

Applications

The tropical addition is the good filter for noise removal. We consider that

(ω \oplus σ) \oplus ω = ω \oplus ω = ω

where

σ

is the noise,

ω

is a variable,

| σ | \leq | ω |

, and it can be the amplitude, velocity, or others.

Li L, Yao T, and Zhou C J et al.²⁴ present a new approach to filter signals for discrete-time physical problems with stochastic uncertain in the presence of random data transmission delays, out-of-order packets, and correlated noise. So we can conclude that the tropical addition is the best candidate for noise filtering, which can filter stochastic noise, uncertain noise and fuzzy noise. The tropical addition filters the noise with extreme ease; the tropical algebra-based filter has obvious advantages over traditional filters.²⁵

Now we consider a simple optimization with constraints with tropical algebra

{(x - 11)}^{2} + y^{2} \to \min .

(15)

S u b j e c t t o y (x) = (3 \otimes x) \oplus 6

(16)

The constraint of the tropical polynomial is illustrated in Figure 1, and the optimal value can be obtained as 10 without any difficulty.

Figure 1.

Optimization with the constraint of the tropical polynomial $y (x) = (3 \otimes x) \oplus 6$ .

Discussion and conclusion

Scientists and engineers in noise removal and optimal control might be in shock! They will find that the tropical algebra is an extremely useful tool, and it will lead to an extreme simple algorithm for both noise removal and optimal control, for example, the Nadeem-Faisal-He algorithm²⁶ and Chun-Hui He’s algorithm^27,28 can be incorporated with the tropical algebra. More and more scholars can make use of tropical algebra to carry out frontier research in the fields of noise removal and optimal control, and dig out more methods of tropical algebra to solve practical problems, such as the variational iteration method²⁹ and the homotopy perturbation method³⁰ and Rabbani-He-Duz method.³¹

As the present article has revealed idempotents on multiplicative semigroups of tropical matrices, the applications of the tropical algebra become very much promising and challenging, and this paper can be used as a good paradigm for various practical applications, especially in medical imagine analysis.^32,33

Footnotes

Declaration of Conflicting Interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work was supported by The National Natural Science Foundation of China (No. 12001418).

ORCID iD

Chun-Mei Gong

References

Cuninghame-Green

. Minimax algebra. Lecture notes in economics and mathematical systems. Berlin: Springer, 1979, Vol. 166.

Butkovič

. Max-algebra: the linear algebra of combinatorics? Linear Algebra its Applications 2003; 367: 313–335.

Gonçalves

Maia

Hardouin

. On max-plus linear dynamical system theory: the regulation problem. Automatica 2017; 75: 202–209. DOI: 10.1016/j.automatica.2016.09.019.

Monod

Kalisnik

Patino-Galindo

, et al. Tropical sufficient statistics for persistent homology. SIAM J Appl Algebra Geometry 2019; 3(2): 337–371. DOI: 10.1137/17M1148037.

Maragos

Charisopoulos

Theodosis

. Tropical geometry and machine learning. Proc IEEE 2021; 109(5): 728–755. DOI: 10.1109/JPROC.2021.3065238.

Abdurrazzaq

Mohd

Junoh

, et al. Tropical algebra based adaptive filter for noise removal in digital image. Multimedia Tools Appl 2020; 79(27): 19659–19668. DOI: 10.1007/s11042-020-08847-0.

Abdurrazzaq

Mohd

Junoh

, et al. Modified tropical algebra based median filter for removing salt and pepper noise in digital image. IET Image Process 2019; 13(14): 2790–2795. DOI: 10.1049/iet-ipr.2018.6201.

Krivulin

. Tropical optimization problems with application to project scheduling with minimum makespan. Ann Operat Res 2017; 256(1): 75–92. DOI: 10.1007/s10479-015-1939-9.

Krivulin

Romanovsky

. Solution of mathematical programming problems using tropical optimization methods. Vestnik St Petersbg Univ Math 2017; 50(3): 274–281.

10.

Gaubert

McEneaney

. Min-max spaces and complexity reduction in min-max expansions. Appl Math Optim 2012; 65(3): 315–348. DOI: 10.1007/S00245-011-9158-5.

11.

McEneaney

. Distributed dynamic programming for discrete-time stochastic control, and idempotent algorithms. Automatica 2011; 47(3): 443–451. DOI: 10.1016/j.automatica.201010.006.

12.

Olsder

Roos

. Cramer and Cayley-Hamilton in the max algebra. Linear Algebra Appl 1988; 101(1): 87–108.

13.

Il’In

. Regularity criterion for complete matrix semirings. Math Notes 2001; 70(3): 329–336.

14.

Develin

Santos

Sturmfels

. On the rank of a tropical matrix. Comb Comput Geom 2005; 52: 213–242.

15.

Izhakian

Margolis

. Semigroup identities in the monoid of two-by-two tropical matrices. Semigroup Forum 2010; 80(2): 191–218.

16.

Johnson

Kambites

. Multiplicative structure of 2×2 tropical matrices. Linear Algebra Appl 2011; 435: 1612–1625.

17.

Hollings

Kambites

. Tropical matrix duality and Green’s D relation. J Lond Math Soc 2012; 86(2): 520–538. DOI: 10.1112/jlms/jds015.

18.

Johnson

Kambites

. Green’s J-order and the rank of tropical matrices. J Pure Appl Algebra 2013; 217(2): 280–292. DOI: 10.1016/j.jpaa.2012.06.003.

19.

Izhakian

Johnson

Kambites

. Pure dimension and projectivity of tropical polytopes. Adv Math 2016; 303: 1236–1263. DOI: 10.1016/j.aim.2016.08.033.

20.

Izhakian

Johnson

Kambites

. Tropical matrix groups. Semigroup Forum 2018; 96(1): 178–196. DOI: 10.1007/s00233-017-9894-1.

21.

Lin

. Some Studies of Tropical Martices (In Chinese). Xi’an: Northwest University, 2018.

22.

Gould

Johnson

Naz

. Matrix semigroups over semirings. Int J Algebra Comput 2019; 30(2): 267–337. DOI: 10.1142/S0218196720500010.

23.

Howie

J M

. Fundamentals of Semigroup Theory. Oxford: Clarendon Press, 1995.

24.

Yao

Zhou

, et al. Modeling and filtering for a stochastic uncertain system in a complex scenario. Therm Sci 2021; 25(2 Part B): 1411–1424. DOI: 10.2298/TSCI191201041L.

25.

Qiu

Guo

. A simplified adaptive feedback active noise control system. Appl Acoust 2014; 81: 40–46. DOI: 10.1016/j.apacoust.2014.02.006.

26.

Nadeem

Ali

. New optimal fourth-order iterative method based on linear combination technique. Hacettepe J Math Stat 2021; 50(6): 1692–1708. DOI: 10.15672/hujms.909721.

27.

Khan

. Numerical simulation of Chun-Hui He’s iteration method with applications in engineering. Int J Numer Methods Heat Fluid Flow 2021; 32: 944–955. DOI: 10.1108/HFF-04-2021-0245.

28.

. An introduction to an ancient Chinese algorithm and its modification. Int J Numer Methods Heat Fluid Flow 2016; 26(8): 2486–2491. DOI: 10.1108/HFF-09-2015-0377.

29.

Wang

. Variational iteration method for solving integro-differential equations. Phys Letters A 2007; 367(3): 188–191. DOI: 10.1016/j.physleta.2007.02.049.

30.

Tian

Feng

. A short review on approximate analytical methods for non-linear problems. Therm Sci 2022; 26(3): 2607–2618. DOI: 10.2298/TSCI2203607T.

31.

Rabbani

Duz

. Some computational convergent iterative algorithms to solve nonlinear problems. Math Sci 2021; 15(4): 1–12. DOI: 10.1007/s40096-021-00448-8.

32.

You

Lei

Wang

, et al. Fine perceptive gans for brain mr image super-resolution in wavelet domain. IEEE Transactions Neural Networks Learning Systems 2022; 33(1): 1–13. DOI: 10.1109/TNNLS.2022.3153088.

33.

Lei

Wang

, et al. Bidirectional mapping generative adversarial networks for brain MR to PET synthesis. IEEE Trans Med Imaging 2021; 41(1): 145–157. DOI: 10.1109/TMI.2021.3107013.

Tropical algebra for noise removal and optimal control

Abstract

Keywords

Introduction

Idempotents of 3 × 3 tropical matrix semigroups

Tropical algebra and its basic properties

Main results

Applications

Discussion and conclusion

Footnotes

Declaration of Conflicting Interests

Funding

ORCID iD

References

Idempotents of $3 \times 3$ tropical matrix semigroups