This paper deals with the max-algebraic linear equation system A ⊗ x = b. As in the conventional linear algebra such a linear system may have none, exactly one or infinitely many solutions. When the number of solutions is exactly one, Cramer’s rule is given as an analogue of the classical linear algebra. When the number of solutions is infinite, the existence of a minimal solution is shown and the formula of minimal solution is given. Furthermore, it is proved that every solution can be expressed as a linear combination of a respective minimal solution and some special vectors. Finally, an algorithm to describe all the solutions of a given max-algebraic linear equation system is proposed when its number of solutions is infinite.
M.Akian, S.Gaubert, and A.Guterman, Linear independence over tropical semirings and beyond, In G. L.Litvinov and S. N.Sergeev, editors, Proceedings of the International Conference on Tropical and Idempotent Mathematics,volume 495 of Contemporary Mathematics, 1–38. American Mathematical Society,2008.
2.
F.Baccelli, G.Cohen, G.J.Olsder, and J.P.Quadrat, Synchronization and Linearity.Wiley, 1992.
3.
R. E.Burkard, P.Butkovič, Max algebra and the linear assignment problem, Math Program Ser B98 (2003), 415–429.
4.
R. E.Burkard and E.Çela, Linear assignment problems and extensions, in: P. M.Pardalos, D. -Z.Du (Eds.), Handbook of Combinatorial Optimization, Supplement Vol. A,Kluwer Academic Publishers, 1999, pp. 75–149.
5.
P.Butkovič, Max-algebra: The linear algebra of combinatorics?Linear Algebra and its Applications367 (2003), 313–335.
6.
P.Butkovič, Strong regularity of matrices-a survey of results, Discrete Appl Math48 (1994), 45–68.
7.
P.Butkovič, Max-linear Systems: Theory and Algorithms, Springer, 2010.
8.
R.A.Cuninghame-Green, Minimax Algebra, Lecture Notes in Economics and Math Systems, Vol. 166, Springer, Berlin, 1979.
9.
R.A.Cuninghame-Green, Minimax Algebra and Applications, in: Advances in Imaging and Electron Physics, Vol. 90, Academic Press, New York, 1995, pp. 1–121.
10.
R.A.Cuninghame-Green, P.Butkovič, Bases in max-algebra, Linear Algebra and its Applications389 (2004), 107–120.
11.
S.Gaubert, Théorie des systèmes linéaires dans les dioïdes, Thèse, Ecole des Mines de Paris, 1992.
12.
M.Gondran, M.Minoux, Linear algebra of dioïds: A survey of recent results, Ann Discr Math19 (1984), 147–164.
13.
G. J.Olsder and C.Roos, Cramer and Cayley-Hamilton in the Max Algebra, Linear Algebra and its Applications101 (1988) 87-10.
14.
M.Plus, Linear systems in (max,+)-algebra, In Proceedings of the 29th Conference on Decision and Control, volume 1, 151–156, Honolulu, Dec.1990.
15.
J.Richter-Gebert, B.Sturmfels, and T.Theobald, Firststepsintropicalgeometry, In Idempotent mathematics and mathematical physics, volume 377 of Contemporary Mathematics, 289–317.American Mathematical Society, Providence, RI, 2005.
16.
Hui-liWang, Xue-pingWang, A polynomial algorithm for solving system of inequalities in max-plus algebra, Information Sciences318 (2015), 1–13.
17.
Xue-pingWang, Hui-liWang, The generators of the solution space for a system of inequalities, Linear Algebra and its Applications459 (2014), 248–263.
