Idempotents of nxn tropical matrices

By externally adjoining a top element to a linearly ordered Abelian group (G,+) we obtain a linearly ordered commutative monoid, say (M,+). The linear order naturally induces a min operation on the group (G,+), and hence the monoid (M,+). In fact (M, min, +) is a semiring. In this talk, we shall consider n x n matrices over such semirings. In the literature, such matrices are called tropical matrices. The tropical product of tropical matrices A and B is defined by replacing the `multiplication' and `addition' in the usual product of matrices over a field by min. and + operations, respectively. One may also define a min operation on tropical matrices in a standard way. The min operation together with the tropical multiplication turns the set of all n x n tropical matrices also into a semiring. We shall consider the connection of tropical matrices with the weighted directed graphs. (These are complete directed graphs with each directed edge being assigned an element of the semiring (M, min, +), called the weight of the edge.) The connection will be instrumental in investigating the idempotents of the semiring of tropical matrices, which will be the main subject of my next talk.