Printer Friendly

The Tropical Matrix Groups with Symmetric Idempotents.

1. Introduction

Tropical algebra (also known as max-plus algebra or max-algebra) is the algebra of the real numbers extended by adding an infinite negative element -[infinity] when equipped with the binary operations of addition and maximum. It has applications in areas such as combinatorial optimization and scheduling, control theory, discrete event dynamic systems, and many other areas of science (see [1-9]). Many problems arising from these application areas are expressed using (tropical) linear equations, so many authors study tropical matrices, i.e., matrices over tropical algebra.

For example, consider the multi-machine interactive production process (MMIPP) [4] where products [P.sub.1], ..., [P.sub.m] are prepared using n machines, every machine contributing to the completion of each product by producing a partial product. It is assumed that every machine can work for all products simultaneously and that all these actions on a machine start as soon as the machine starts to work. Let [a.sub.ij] be the duration of the work of the jth machine needed to complete the partial product for [P.sub.i] (i = 1, ..., m, j = 1, ..., n). If this interaction is not required for some i and j, then [a.sub.ij] is set to -[infinity]. Denote the starting time of the jth machine by [x.sub.j]. Then all partial products for [P.sub.i] (i = 1, ..., m) will be ready at time

max + {[x.sub.1] + [a.sub.ij], ..., [x.sub.n] + [a.sub.in]}. (1)

Hence if [b.sub.i] (i = 1, ..., m) are given completion times then the starting times have to satisfy the system of equations:

([for all]i [member of] {1, ..., m}) max {[x.sub.1] + [a.sub.ij], ..., [x.sub.n] + [a.sub.in]} = [b.sub.i]. (2)

The problem can be converted into a related problem in tropical matrices.

From an algebraic perspective, a key object is the multiplicative semigroup of all square matrices of a given size over the tropical algebra. There are a series of papers in the literature considering this multiplicative semigroup (see [10-17]). Moreover, an important step in understanding tropical algebra is to understand the maximal subgroups of this semigroup. It is a basic fact of semigroup theory that every subgroup of a semigroup S lies in a unique maximal subgroup. Moreover, the maximal subgroups of S are precisely the H-classes (see Section 2 below for definitions) of S which contain idempotents element. Johnson and Kambites [16] give a classification of the maximal subgroups of the semigroup of all 2x2 tropical matrices under multiplication in 2011. Izhakian, Johnson, and Kambites [13] consider the case of matrices without -[infinity]. They prove that every subgroup of the multiplicative semigroup of n x n finite tropical matrices is isomorphic to a direct product of the form R x [SIGMA] for some [SIGMA] [less than or equal to] [S.sub.n]. In the same year, Shitov [17] gives a description of the subgroups of the multiplicative semigroup of n x n tropical matrices up to isomorphism; i.e., every subgroup of the semigroup admits a faithful representation with n x n tropical invertible matrices. In 2017, we showed that a maximal subgroup of the multiplicative semigroup of n x n tropical matrices containing a nonsingular idempotent matrix E is isomorphic to the group of all invertible matrices which commute with E as groups and proved that each maximal subgroup of the multiplicative semigroup of n x n tropical matrices with the identity of the rank r is isomorphic to some maximal subgroup of the multiplicative semigroup of r x r tropical matrices with nonsingular identity. Thus we shall turn our attention towards the invertible matrices that commute with the nonsingular idempotent. The main purpose of this paper is to study the invertible matrices that commute with a nonsingular symmetric idempotent and to give a decomposition of the maximal subgroups of n x n tropical matrices containing a nonsingular symmetric idempotent.

This paper will be divided into five sections. In Section 2 we introduce some preliminary notions and notation. The decompositions of the maximal subgroups of n x n tropical matrices containing an idempotent diagonal block matrix are established in Section 3. This result (see Theorem 11) develops the results obtained by Izhakian et al. in [13]. Finally, in the last section, we prove that each symmetric nonsingular idempotent matrix is equivalent to a block diagonal matrix and a decomposition of the maximal subgroup containing a symmetric idempotent matrix is given (see Theorem 17).

2. Preliminaries

The following notation and definitions can be found in [3, 15, 18, 19]. We write T for the set R [union] {-[infinity]] equipped with the operations of maximum (denoted by [direct sum]) and addition (denoted by [cross product]). Thus, we write

a [direct sum] b = max {a, b} and a [cross product] b = a + b. (3)

As usual, the set of all mxn tropical matrices is denoted by [M.sub.mxn](T). In particular, we shall use [M.sub.n](T) instead of [M.sub.nxn](T). The operations [direct sum] and [cross product] on T induce corresponding operations on tropical matrices in the obvious way. Indeed, if A, B [member of] [M.sub.mxn](T), C [member of] [M.sub.nxp](T), then we have

[mathematical expression not reproducible], (4)

where [x.sub.ij] denotes the (i, j)th entry of the matrix X. For brevity, we shall write AC in place of A [cross product] C. It is easy to see that ([M.sub.n](T), [cross product]) is a semigroup. Other concepts such as transpose and block matrix are defined in the usual way. Unless otherwise stated, we refer to matrix as tropical matrix in the remainder of this paper. Recall that Green's relations R and L [20] on the semigroup [M.sub.n](T) are, respectively, given by

ARB [??] ([there exist]X, Y [member of] [M.sub.n] (T)) A = BX, B = AY; ALB [??] ([there exist]X, Y [member of] [M.sub.n] (T)) A = XB, B = YA. (5)

Green's relation H (D, resp.) is given by H = R [intersection] L(D = R*L, resp.). The H-class (D-class, resp.) containing the matrix A will be written as [H.sub.A] ([D.sub.A], resp.).

We shall be interested in the space [T.sup.n] of affine tropical vectors. We write [x.sub.i] for the ith component of a vector x [member of] [T.sup.n]. We extend [direct sum] to [T.sup.n] componentwise so that [(x [direct sum] y).sub.i] = [x.sub.i] [direct sum] [y.sub.i] for all i. And we define a scaling action of T on [T.sup.n] by

[lambda] [cross product] ([x.sub.1], [x.sub.2], ..., [x.sub.n]) = ([lambda] [cross product] [x.sub.1], [lambda] [cross product] [x.sub.2], ..., [lambda] [cross product] [x.sub.n]), (6)

for each [lambda]] [member of] T and each x [member of] [T.sup.n]. These operations give [T.sup.n] the structure of a T-semimodule.

A tropical convex set in [T.sup.n] is a subset closed under [direct sum] and scaling by elements of T, that is, a T-subsemimodule of [T.sup.n]. If S [subset or equal to] [T.sup.n], then the tropical convex hull of S is the smallest tropical convex set containing S, that is, the set of all vectors in [T.sup.n] which can be written as tropical linear combinations of finitely many vectors from S.

Let X be a finitely generated tropical convex set in [T.sup.n]. A set {[x.sub.1], [x.sub.2], ..., [x.sub.k]} [member of] X is called a weak basis of X if it is a generating set for X minimal with respect to inclusion. It is known that every finitely generated tropical convex set admits a weak basis, which is unique up to permutation and scaling (see [[19], Theorem 5]). In particular, any two weak bases have the same cardinality, in view of which we may define the generator dimension of a finitely generated tropical convex set X to be the cardinality of a weak basis for X, or, equivalently, the minimum cardinality of a generating set for X.

Given an m x n matrix A we define the column space of A, denoted by Col(A), to be the tropical convex hull of the columns of A. Thus Col(A) [member of] [T.sup.m]. Similarly, we define the row space Row(A) [member of] [T.sup.n] to be the tropical convex hull of the rows of A. The column rank of A is the generator dimension for the column space of A. The row rank of A is defined dually; it is well known that the row rank and column rank of a tropical matrix can differ (see [[15] Example 7.1]). The column rank (row rank, resp.) of A is denoted by c(A) (r(A), resp.). We denote the i-th row and the j-th column of A by [a.sub.*i] and [a.sub.*j], respectively. If c(A) = s and r(A) = r, then it is easy to see that there exist s columns [mathematical expression not reproducible] of A such that [mathematical expression not reproducible] is a weak basis of Col(A) and there exist r rows [mathematical expression not reproducible]. of A such that [mathematical expression not reproducible] is a weak basis of Row(A). The submatrix

[mathematical expression not reproducible]. (7)

of A is said to be a column basis submatrix of A (a row basis submatrix of A, a basis submatrix of A, resp.). If c(A) = r(A) = r, then r is called the rank of A. If c(A) = n(r(A) = m, resp.), then A is called column compressed (row compressed, resp.) [21]. The matrix A is called nonsingular if it is both column compressed and row compressed, and singular otherwise.

In the sequel, the following notions and notation are needed for us.

(i) An n x n matrix A is called a symmetric matrix if [A.sup.T] = A.

(ii) diag([A.sub.1], [A.sub.2], ..., [A.sub.n]) denotes the diagonal block matrix

[mathematical expression not reproducible], (8)

where each diagonal block [A.sub.i] is a square matrix, for all 1 [less than or equal to] i [less than or equal to] n. Particularly, the matrix diag([a.sub.1], [a.sub.2], ..., [a.sub.n]) will be called diagonal if all of [a.sub.1], [a.sub.2], ..., [a.sub.n] are real numbers.

(iii) In denotes the identity matrix, i.e., the n x n matrix diag(0, 0, ..., 0).

(iv) An n x n matrix A is called invertible if there exists an n x n matrix B such that AB = BA = [I.sub.n]. In this case, B is called an inverse of A and is denoted by [A.sup.-1].

(v) An n x n matrix is called a monomial matrix if it has exactly one entry in each row and column which is not equal to -[infinity].

(vi) An n x n matrix is called a permutation matrix if it is formed from the identity matrix by reordering its columns and/or rows.

(vii) -[infinity] denotes the zero matrix, i.e., the matrix whose entries are all -[infinity].

It is well known that an n x n matrix A is invertible if and only if A is monomial [22]. Also, the inverse of a permutation matrix is its transpose. Denote the set of all n x n monomial matrices (permutation matrices, resp.) by [GL.sub.n](T) ([P.sub.n](T), resp.). Then [GL.sub.n](T) and [P.sub.n](T) are group under the matrix multiplication.

There are two types of elementary matrices corresponding to the two types of elementary operations.

Type 1. An elementary matrix of Type 1 is a matrix obtained by interchanging two rows (columns, resp.) of [I.sub.n]. We write [E.sub.i,j] as the matrix obtained by trading places of rows (or columns) i and j of [I.sub.n].

Type 2. An elementary matrix of Type 2 is a matrix obtained by multiplying a row (column, resp.) of [I.sub.n] by a constant a [not equal to] -[infinity]. We write [E.sub.i](a) as the matrix obtained by multiplying row (or column) i of the identity matrix by a [not equal to] -[infinity].

Recall that if A is an m x n matrix, and B is a matrix of the same size that is obtained from A by a single elementary row (column, resp.) operation, then there is an elementary matrix of size m (n, resp.) that will convert A to B via matrix multiplication on the left (right, resp.). Thus it is easy to see that a matrix is monomial if and only if it maybe decomposed into the product of a finite number of elementary matrices. Also, it is worth mentioning that an elementary column (row, resp.) operation on a matrix does not change the linear relationship among the row (column, resp.) vectors. That is to say, if A, B [member of] [M.sub.mxn](T) and A = BM for some n x n monomial matrix M, then

[mathematical expression not reproducible], (9)

where [mathematical expression not reproducible] are some rows of A, [mathematical expression not reproducible] are the corresponding rows of B, and [[lambda].sub.1], ..., [[lambda].sub.s] [member of] T.

We say that matrices A and B are equivalent [23] (notation A = B) if B = [PNP.sup.T] for some permutation matrix P, that is, B can be obtained by a simultaneous permutation of the rows and columns of A.

3. Tropical Matrix Groups Containing a Diagonal Block Idempotent

In this section, we study the tropical matrix groups containing a diagonal block idempotent. First, we will need the following notation and results in [13]. Let E be an n x n nonsingular idempotent matrix. We denote the set of all monomial matrices commuting with E by [G.sub.E]. That is to say,

[G.sub.E] = {M | M [member of] [GL.sub.n] (T), ME = EM}. (10)

The H-classes containing an n x n idempotent matrix are the maximal subgroups of the semigroup [M.sub.n](T). By Theorems 4.3 and 5.3 in [13], we have the following.

Lemma 1. Let E be an idempotent of rank r. Then [H.sub.E] is isomorphic to [G.sub.[bar.E]] as groups, where [bar.E] is a basis submatrix of E.

Since each basis submatrix of an idempotent is a nonsingular idempotent matrix, we need only to study the group [G.sub.E], in which E is a nonsingular idempotent matrix. Indeed it is easy to see the following.

Lemma 2. E = diag([E.sub.1], [E.sub.2], ..., [E.sub.k]) is a nonsingular idempotent matrix if and only if [E.sub.1], [E.sub.2], ..., [E.sub.k] are nonsingular idempotent matrices.

We can say immediately that [mathematical expression not reproducible], which is isomorphic to R [??] [S.sub.n] as groups. More generally, we have the following.

Lemma 3. If

[mathematical expression not reproducible] (11)

is an n x n nonsingular idempotent matrix, where the diagonal blocks are k real square matrices, then [G.sub.E] =

[mathematical expression not reproducible]. (12)

Proof. Suppose that E = diag(F, F, ..., F) is an n x n nonsingular idempotent matrix and that F is a real matrix. Then by Lemma 2 we can find that F is an (n/k) x (n/k) real nonsingular idempotent matrix. If M [member of] [G.sub.E], then partition M in the same manner of E, i.e.,

[mathematical expression not reproducible], (13)

where [M.sub.ij] are all (n/k) x (n/k) matrices, and we have

EM = ME. (14)

Thus we can see that

F[M.sub.ij] = [M.sub.ij]F, (15)

for any i, j [member of] [k].

Now we claim that

if [M.sub.ij] [not member of] G[L.sub.n/k] (T), then [M.sub.ij] = -[infinity]. (16)

If [M.sub.ij] [not member of] [GL.sub.n/k](T), then [M.sub.ij] has some row where entries are all -[infinity] or [M.sub.ij] has some column where entries are all -[infinity], since [M.sub.ij] is a submatrix of the monomial matrix M. Without loss of generality, we assume that [M.sub.ij] has one row where entries are all -[infinity]; thus [M.sub.ij]F = F[M.sub.ij] has one row where entries are all -[infinity]. Since F is real matrix, it follows that [M.sub.ij] = -00, for otherwise F[M.sub.ij] does not have one row where entries are all -[infinity].

If, on the other hand, [M.sub.ij] [member of] [GL.sub.n/k](T) such that (15), then [M.sub.ij] [member of] [G.sub.F]. This completes our proof.

For any matrix F, we denote the matrix diag(F, F, ..., F) by [??].

As a consequence, we have the following.

Corollary 4. [G.sub.[??]] is isomorphic to [G.sub.F] [??] [S.sub.n/k] as groups, in which the matrix [??] has the form given in Lemma 3.

Next, we shall want to consider the type of matrices in Lemma 9. And we need some lemmas at first. By [21, Theorem 102], we immediately have the following.

Lemma 5. Let E be an n x n nonsingular idempotent matrix. Then

[D.sub.E] = {MEN | M, N [member of] [GL.sub.n] (T)}. (17)

Lemma 6 (see [24] Proposition 4.5). Let E be a nonsingular idempotent matrix. If there exists a monomial matrix M, such that EME = E, then M = [I.sub.n].

Lemma 7. Let E, F be nonsingular idempotent matrices. Then EDF if and only if there exists a monomial matrix M such that E = [MFM.sup.-1], i.e., such that EM = MF.

Proof. Suppose that E, F are nonsingular idempotent matrices.

If EDF, then by Lemma 5 we can see that E = MFN, for some monomial matrices M and N. It follows that MFN = E = [E.sup.2] = MFN MFN. This implies that F = FNMF. Now by Lemma 6 we have that NM = [I.sub.n]. Hence E = [MFM.sup.-1], and so EM = MF.

To prove the converse half, if there exists a monomial matrix M such that EM = MF, then we let C = EM = MF, and we can see that ERC and CRF. Hence EDF as required.

If M = [([m.sub.ij]).sub.nxn] is a monomial matrix, then there exists a unique [sigma] [member of] [S.sub.n], such that [m.sub.i[sigma](i)] [member of] R and [m.sub.ij] = -[infinity] for all j [not equal to] [sigma](i). Thus from the definition of matrix multiplication it is easy to show that the map

[phi] : [GL.sub.n] (T) [right arrow] [S.sub.n], M [right arrow] [sigma] (18)

is a homomorphism of groups. Now we can show that

Proposition 8. Let E = [([e.sub.ij]).sub.nxn] and F = [([f.sub.ij]).sub.nxn] be real nonsingular idempotent matrices. Then EDF if and only if there exists [sigma] [member of] [S.sub.n], such that, for all i, j [member of] [n],

[mathematical expression not reproducible], (19)

Proof. Suppose that E = [([e.sub.ij]).sub.nxn] and F = [([f.sub.ij]).sub.nxn] are real nonsingular idempotent matrices.

If EDF, then by Lemma 7 we have that there exists a matrix M = [([m.sub.ij]).sub.nxn] [member of] [G.sub.E] such that EM = MF. It follows that

EM = ([e.sub.ij]) ([m.sub.ij]) = MF = ([m.sub.ij]) ([f.sub.ij]). (20)

This implies that, for any i, j [member of] [n],

[e.sub.ij] [cross product] [m.sub.j[sigma](j)] = [m.sub.i[sigma](i)] [cross product] [f.sub.[sigma](i)[sigma](j)]. (21)

Since for all i, j [member of] [n], [e.sub.ij], [m.sub.j[sigma](j)], [m.sub.i[sigma](i)] and [f.sub.[sigma](i)[sigma](j)] are real numbers, then we have

[e.sub.ij] + [m.sub.j[sigma](j)] = [m.sub.i[sigma](i)] + [f.sub.[sigma](i)[sigma](j)]. (22)

Thus we can see that, for any i, j [member of] [n],

[mathematical expression not reproducible]. (23)

Hence for any i, j [member of] [n] we have

[mathematical expression not reproducible]. (24)

Conversely, if there exists [sigma] [member of] [S.sub.n] such that, for any i, j [member of] [n],

[mathematical expression not reproducible], (25)

then the system

[mathematical expression not reproducible] (26)

has the solutions

([m.sub.i[sigma](i)]) = [lambda] [cross product] ([e.sub.i1] - [f.sub.[sigma](i)[sigma](1)]), (27)

where [lambda] [member of] R. This means that if a satisfies (24), then there exists a monomial matrix M, whose (i, [sigma](i))th entry is the real number [m.sub.i[sigma](i)] and the other entries are -[infinity], such that EM = MF, and so EDF.

Lemma 9. Let

[mathematical expression not reproducible] (28)

be an n x n nonsingular idempotent matrix, where the matrix [E.sub.i] is a real matrix of order [n.sub.i], i [member of] [k], and for any i, j [member of] [k], ([E.sub.i], [E.sub.j]) [not member of] D (i [not equal to] j). Then

[mathematical expression not reproducible]. (29)

Proof. Let E = diag([E.sub.1], [E.sub.2], ..., [E.sub.k]) be an n x n nonsingular idempotent matrix. Then by Lemma 2 we can see that [E.sub.i] is an ([n.sub.i]) x ([n.sub.i]) real nonsingular idempotent matrix. Suppose that M [member of] [G.sub.E]. Then partition M into [k.sup.2] blocks

[mathematical expression not reproducible], (30)

where [M.sub.ij] is an [n.sub.i] x [n.sub.j] matrix. It follows EM = ME that

[E.sub.i][M.sub.ij] = [M.sub.ij][E.sub.j], (31)

for any i, j [member of] [k]. Since [M.sub.ij] is a submatrix of the monomial matrix M, it has at most one entry in each row and column which is not equal to -[infinity]. We now distinguish two cases:

(i) i [not equal to] j, (ii) i = j. (32)

In case (i), suppose that [M.sub.ij] is a monomial matrix such that (31). Then by Lemma 7 we have that [E.sub.i]D[E.sub.j]. This contradiction implies that [M.sub.ij] is not a monomial matrix. It follows by a closely similar proof of the claim (16) that [M.sub.ij] = -[infinity].

In case (ii), [M.sub.ij] is a monomial matrix such that (31), since [M.sub.ij] = -[infinity] (i [not equal to] j) and M is a monomial matrix. This implies that [mathematical expression not reproducible] such that [mathematical expression not reproducible]. This completes our proof.

We now immediately deduce the following.

Corollary 10. If the matrix E has the form in Lemma 9, then [G.sub.E] is isomorphic to [mathematical expression not reproducible] as groups.

By the connection between the elementary operations and elementary matrices, it follows by Lemma 7 that if E = diag([E.sub.1], [E.sub.2], ..., [E.sub.k]) is a nonsingular idempotent matrix, then there exists a monomial matrix N, such that

[mathematical expression not reproducible], (33)

where [mathematical expression not reproducible] are diagonal blocks of E and for any [mathematical expression not reproducible]. It is easy to see that the mapping [mathematical expression not reproducible] defined by

[phi](M) = [NMN.sup.-1] (M [member of] [G.sub.E]) (34)

is a group isomorphism. Thus we obtain that [G.sub.E] is isomorphic to [mathematical expression not reproducible] as groups. Hence we have the following theorem.

Theorem 11. Let

[mathematical expression not reproducible] (35)

be an n x n nonsingular idempotent matrix, where [E.sub.1], [E.sub.2], ..., [E.sub.k] are real square matrices. Then there exists a monomial matrix N, such that

[mathematical expression not reproducible], (36)

where [mathematical expression not reproducible] are diagonal blocks of E and for any [mathematical expression not reproducible]. Furthermore, [G.sub.E] is isomorphic to

[mathematical expression not reproducible] (37)

as groups, where [n.sub.h] is the order of the matrix [mathematical expression not reproducible] is the number of the diagonal blocks of [mathematical expression not reproducible].

It follows by Lemma 1 and Theorem 11 that each tropical matrix group containing an idempotent of the form in Theorem 11 is isomorphic to some direct products of some wreath products. This result develops the decomposition of maximal subgroups of the semigroup of n x n real matrices under multiplication as direct products of R with finite groups in [13].

4. Tropical Matrix Groups

Containing a Symmetric Nonsingular Idempotent Matrix

In this section we shall prove that each symmetric nonsingular idempotent matrix is similar to a diagonal block matrix. On this basis, we give a decomposition of the maximal subgroups containing an idempotent of this kind. For this aim, the following lemmas are needed.

Lemma 12 (see [24] Corollary 4.4). All main diagonal entries of a nonsingular idempotent matrix are 0.

It is easy to verify the following lemma.

Lemma 13. Let E be an n x n matrix. Then the following are true.

(i) If E = [([e.sub.ij]).sub.nxn] is a nonsingular idempotent matrix, then

[e.sub.ik] [cross product] [e.sub.kj] [less than or equal to] [e.sub.ij], (38)

for all i, j, k [member of] [n];

(ii) If E is a nonsingular symmetric idempotent matrix, then so is [PEP.sup.T] for any P [member of] [P.sub.n](T).

We can now prove the following proposition.

Proposition 14. Let E be a nonsingular symmetric idempotent matrix. Then there exists a permutation matrix P such that

[mathematical expression not reproducible], (39)

where [E.sub.1], [E.sub.2], ..., [E.sub.k] are real nonsingular symmetric idempotent matrices.

Proof. Suppose that E = [E.sup.(1)] = ([e.sup.(1).sub.ij]) is an n x n nonsingular symmetric idempotent matrix. Then we shall show that E can be reduced to a diagonal block form using some simultaneous elementary rows and columns operations.

Step 1. Since E is a nonsingular idempotent matrix, it follows by Lemma 12 that all main diagonal entries of E are 0. If the i-th row of E has the most -[infinity] entries, then we can interchange 1-row and i-row of E and interchange 1-column and i-column of E. By Lemma 13 (ii), a new nonsingular symmetric idempotent matrix obtained will be

[E.sup.(2)] = [P.sub.1][E.sup.(1)][P.sup.T.sub.1] = [([e.sup.(2).sub.ij]).sub.nxn], (40)

where [P.sub.1] = [E.sub.1,i] is an elementary matrix.

Step 2. By some synchronous permutations of the rows and columns of [E.sup.(2)], we can move the all -[infinity] entries of the first row to the end of this row. This means that we can take a suitable permutation matrix [P.sup.2] and obtain another new matrix

[mathematical expression not reproducible], (41)

where the first row has the most -[infinity] entries and [e.sup.(3).sub.1j] = -[infinity] iff j > k. By Lemma 13 (ii) we have that [E.sup.(3)] is a nonsingular symmetric idempotent matrix. It follows by Lemma 13 (i) that [e.sup.(3).sub.1t] [cross product] [e.sup.(3).sub.tj] [less than or equal to] [e.sup.(3).sub.1j], for all t, j [member of] [n]. When t [less than or equal to] k, j > k, we can see that [e.sup.(3).sub.1t] [member of] R and [e.sup.(3).sub.1j] = -[infinity], and so [e.sup.(3).sub.tj] = -[infinity]. Thus we have

[mathematical expression not reproducible]. (42)

On the other hand, since [E.sup.(3)] is symmetric, it now follows that [E.sup.(3).sub.21] = -[infinity]. Hence

[mathematical expression not reproducible]. (43)

We can find that [E.sup.(3).sub.11] is a real matrix, since the first row of [E.sup.(3)] has the most -[infinity] entries. Now the matrices [E.sup.(3).sub.11] and [E.sup.(3).sub.22] are nonsingular symmetric idempotent matrices. It follows that we can use the same method to reduce [E.sup.(3).sub.22].

After finite steps we will end up with a diagonal block matrix

[mathematical expression not reproducible], (44)

where P = [P.sub.m-1][P.sup.m-2] ... [P.sub.1] is a permutation matrix and [E.sub.1], [E.sub.2], ..., [E.sub.k] are real nonsingular symmetric idempotent matrices. This completes our proof.

This proposition shows that each nonsingular symmetric idempotent matrix E is equivalent to a diagonal block matrix diag([E.sub.1], [E.sub.2], ..., [E.sub.k]), which is a Frobenius normal form [23] of E, where [E.sub.1], [E.sub.2], ..., [E.sub.k] are real matrices. In the following, we will study [G.sub.E], where E is a diagonal block idempotent whose diagonal blocks are all real matrices.

By a similar argument in Proposition 8, we have the following.

Lemma 15. Let E be an n x n real nonsingular idempotent matrix. Then

[mathematical expression not reproducible] (45)

and [G.sub.E] is isomorphic to the group R x [phi]([G.sub.E]).

In [13], Izhakian, Johnson, and Kambites give a result that [G.sub.E] [congruent to] R x [SIGMA] for some [SIGMA] [member of] [S.sub.n]. We use a different method to prove this result in the above lemma and give a necessary and sufficient condition for some permutation [sigma] in [SIGMA]. And we can easily verify that

[mathematical expression not reproducible]. (46)

Especially if E is an n x n symmetric real nonsingular idempotent matrix, then we have the following.

Proposition 16. Let E be an n x n real symmetric nonsingular idempotent matrix. Then

[mathematical expression not reproducible] (47)

and

[G.sub.E] = {[lambda]P | [lambda] [member of] R, P [member of] [G.sub.E] [intersection] [P.sub.n] (T)}, (48)

which is isomorphic to the group R x [phi]([G.sub.E]).

Proof. Following the proof of Proposition 8, we have that for all i, j [member of] {1, 2, ..., n}

[e.sub.ij] = [e.sub.ji] and [e.sub.sigma](i)[sigma](j)] = [e.sub.sigma](j)[sigma](i)] (49)

Thus (26) reduce to

[mathematical expression not reproducible]. (50)

Then we know that the set of solutions to (50) is not empty if and only if

[e.sub.ij] = [e.sub.[sigma](i)[sigma](j)] ([for all]i, j [member of] {1, 2, ..., n}) (51)

and the solutions are

([m.sub.i[sigma](i)]) = ([lambda]) ([for all]i [member of] {1, 2, ..., n}), (52)

in which [lambda] [member of] R. Hence there exist a real number [lambda] and a permutation matrix P [member of] [G.sub.E], such that

M = [lambda]P. (53)

Thus [G.sub.E] = {[lambda]P | [lambda] [member of] R, P [member of] [G.sub.E] [intersection] [P.sub.n](T)}, and so [G.sub.E] is isomorphic to R x [phi]([G.sub.E]).

Proposition 16 enables us to compile the following algorithm.

If the idempotent matrix E is real nonsingular, we have discussed [G.sub.E]. In the following, we will study the symmetric nonsingular idempotent matrix, which is ont only a real matrix. In summation, from Theorem 11 and Proposition 16, we have the following.

Theorem 17. Let E be an n x n symmetric nonsingular idempotent matrix. Then there exists a monomial matrix N, such that

[mathematical expression not reproducible], (54)

where [E.sub.1], [E.sub.2], ..., [E.sub.s] are symmetric real nonsingular idempotent matrices and for any i, j [member of] {1, ..., s}, ([E.sub.i], [E.sub.j]) [not member of] D (i [not equal to] j). Moreover, [G.sub.E] is isomorphic to

[mathematical expression not reproducible] (55)

as groups, where [mathematical expression not reproducible] is the order of the matrix [[??].sub.i]], and [k.sub.i] is the number of the diagonal blocks of [[??].sub.i], i [member of] |1, 2, ..., s}.

Since each basis submatrix of a symmetric idempotent matrix is a symmetric nonsingular idempotent matrix, it follows by Lemma 1 and Theorem 17 that each tropical matrix group containing a symmetric idempotent matrix is isomorphic to some direct products of some wreath products.

Our next aim is to provide an algorithm for [G.sub.E] of any nonsingular idempotent E [member of] [M.sub.n](T).

https://doi.org/10.1155/2018/4797638

Data Availability

Previously reported data were used to support this study and are available at [https://doi.org/10.1155/2018/4797638]. These prior studies (and datasets) are cited at relevant places within the text as references [1-24].

Conflicts of Interest

The author declares that they have no conflicts of interest.

Acknowledgments

The author is supported by National Natural Science Foundation of China (11561044, 11861045).

References

[1] P. Butkovic, "Max-algebra: the linear algebra of combinatorics?" Linear Algebra and its Applications, vol. 367, pp. 313-335, 2003.

[2] G. Cohen, S. Gaubert, and J.-P. Quadrat, "Max-plus algebra and system theory: where we are and where to go now," Annual Reviews in Control, vol. 23, pp. 207-219, 1999.

[3] R. Cuninghame-Green, Minimax algebra, vol. 166 of Lecture Notes in Economics and Mathematical Systems, Springer-Verlag, Berlin-New York, 1979.

[4] R. A. Cuninghame-Green and P. Butkovl, "Generalised eigen-problem in max-algebra," in Proceedings of the 9th International Workshop on Discrete Event Systems, WODES' 08, pp. 236-241, Sweden, May 2008.

[5] F. d'Alessandro and E. Pasku, "A combinatorial property for semigroups of matrices," Semigroup Forum, vol. 67, no. 1, pp. 22-30, 2003.

[6] S. Lahaye, J.-L. Boimond, and J.-L. Ferrier, "Just-in-time-control of time-varying discrete event dynamic systems in (max,+) algebra," International Journal of Production Research, vol. 46, no. 19, pp. 5337-5348, 2008.

[7] L. Murfitt, Discrete event dynamic systems in max-algebra: realisation and related combinatorial problems [PhD. thesis], University of Birmingham, 2000.

[8] J.-E. Pin, "Tropical semirings," in Idempotency (Bristol, 1994), vol. 11 of Publications of the Newton Institute, pp. 50-69, Cambridge University Press, Cambridge, UK, 1998.

[9] I. Simon, "On semigroups of matrices over the tropical semiring," RAIRO Informatique ThEorique et Applications. Theoretical Informatics and Applications, vol. 28, no. 3-4, pp. 277-294, 1994.

[10] R. B. Bapat, D. P. Stanford, and P. van den Driessche, "Pattern properties and spectral inequalities in max algebra," SIAM Journal on Matrix Analysis and Applications, vol. 16, no. 3, pp. 964-976, 1995.

[11] C. Hollings and M. Kambites, "Tropical matrix duality and Green's D relation," Journal of The London Mathematical Society-Second Series, vol. 86, no. 2, pp. 520-538, 2012.

[12] Z. Izhakian, M. Johnson, and M. Kambites, "Pure dimension and projectivity of tropical polytopes," Advances in Mathematics, vol. 303, pp. 1236-1263, 2016.

[13] Z. Izhakian, M. Johnson, and M. Kambites, "Tropical matrix groups," Semigroup Forum, vol. 96, no. 1, pp. 178-196, 2018.

[14] Z. Izhakian and S. W. Margolis, "Semigroup identities in the monoid of two-by-two tropical matrices," Semigroup Forum, vol. 80, no. 2, pp. 191-218, 2010.

[15] M. Johnson and M. Kambites, "Green's J-order and the rank of tropical matrices," Journal of Pure and Applied Algebra, vol. 217, no. 2, pp. 280-292, 2013.

[16] M. Johnson and M. Kambites, "Multiplicative structure of 2x2 tropical matrices," Linear Algebra and its Applications, vol. 435, no. 7, pp. 1612-1625, 2011.

[17] Y. Shitov, "Tropical matrices and group representations," Journal of Algebra, vol. 370, pp. 1-4, 2012.

[18] M. Akian, S. Gaubert, and A. Guterman, "Linear independence over tropical semirings and beyond," in Tropical and Idempotent Mathematics, G. L. Litvinov and S. N. Sergeev, Eds., vol. 495 of Contemporary Mathematics, pp. 1-38, American Mathematical Society, 2009.

[19] E. Wagneur, "Modulods and pseudomodule 1. Dimension theory," Discrete Mathematics, vol. 98, no. 1, pp. 57-73, 1991.

[20] J. M. Howie, Fundamentals of Semigroup Theory, Academic Press, London, UK, 1995.

[21] S. Gaubert, "Two lectures on max-plus algebra," in Proceedings of the 26th Spring School of Theoretical Computer Science, 1998.

[22] H. S. Coxeter and G. Beck, The Real Projective Plane, Springer New York, New York, NY, 1993.

[23] P. Butkovic, Max-Linear Systems: Theory and Algorithms, Springer-Verlag, London, UK, 2010.

[24] L. Yang, "Regular D-classes of the semigroup of n x n tropical matrices," Turkish Journal of Mathematics, vol. 42, no. 4, pp. 2061-2070, 2018.

Lin Yang (iD) (1,2)

(1) School of Science, Lanzhou University of Technology, Lanzhou, Gansu 730050, China

(2) School of Mathematics, Northwest University, Xi'an, Shaanxi 710127, China

Correspondence should be addressed to Lin Yang; yanglinmath@163.com

Received 9 May 2018; Accepted 31 October 2018; Published 2 December 2018

Academic Editor: Victor S. Kozyakin
COPYRIGHT 2018 Hindawi Limited
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2018 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Title Annotation:Research Article
Author:Yang, Lin
Publication:Discrete Dynamics in Nature and Society
Geographic Code:4EUUK
Date:Jan 1, 2018
Words:6138
Previous Article:Investor Sentiment and the Basis of CSI300 Stock Index Futures: An Empirical Study Based on QVAR Model and Quantile Regression.
Next Article:Minimal Wave Speed in a Predator-Prey System with Distributed Time Delay.
Topics:

Terms of use | Privacy policy | Copyright © 2020 Farlex, Inc. | Feedback | For webmasters