1. On the maximal solution of a linear system over tropical semirings
- Author
-
Fateme Olia, Sedighe Jamshidvand, Amirhossein Amiraslani, and Shaban Ghalandarzadeh
- Subjects
Monomial ,010102 general mathematics ,Linear system ,Inverse ,System of linear equations ,01 natural sciences ,010101 applied mathematics ,Overdetermined system ,Matrix (mathematics) ,ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION ,Applied mathematics ,Automata theory ,0101 mathematics ,Coefficient matrix ,Mathematics - Abstract
Nowadays, certain problems in automata theory, manufacturing systems, telecommunication networks, parallel processing systems and traffic control are intimately linked with linear systems over tropical semirings. Due to non-invertibility of matrices—except monomial matrices—over certain semirings, we cannot generally take advantage of having the inverse of the coefficient matrix of a system to solve it. The main purpose of this paper is to introduce two methods based on the pseudo-inverse of a matrix for solving a linear system of equations over tropical semirings. To this end, under suitable conditions, we first reduce the order of the system through some row–column operational analysis. We then present a necessary and sufficient condition for the system to have a maximal solution. This solution is also obtained through a new version of Cramer’s rule for overdetermined system of equations. Finally, some illustrative examples are given to show the efficiency of the proposed methods, and Maple procedures are also included in the end.
- Published
- 2020