Abstract
A linear vector equation in two unknown vectors is examined in the framework of tropical algebra dealing with the theory and applications of semirings and semifields with idempotent addition. We consider a two-sided equation where each side is a tropical product of a given matrix by one of the unknown vectors. We use a matrix sparsification technique to reduce the equation to a set of vector inequalities that involve row-monomial matrices obtained from the given matrices. An existence condition of solutions for the inequalities is established, and a direct representation of the solutions is derived in a compact vector form. To illustrate the proposed approach and to compare the obtained result with that of an existing solution procedure, we apply our solution technique to handle two-sided equations known in the literature. Finally, a computational scheme based on the approach to derive all solutions of the two-sided equation is discussed.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Akian, M., Gaubert, S., Guterman, A.: Tropical polyhedra are equivalent to mean payoff games. Int. J. Algebra Comput. 22(1), 1250001–1–1250001–43 (2012). https://doi.org/10.1142/S0218196711006674
Allamigeon, X., Gaubert, S., Goubault, E.: Computing the vertices of tropical polyhedra using directed hypergraphs. Discrete Comput. Geom. 49(2), 247–279 (2013). https://doi.org/10.1007/s00454-012-9469-6
Butkovič, P.: On properties of solution sets of extremal linear programs. In: Burkard, R.E., Cuninghame-Green, R.A., Zimmermann, U. (eds.) Algebraic and Combinatorial Methods in Operations Research, North-Holland Mathematics Studies, vol. 95, pp. 41–54. North-Holland (1984). https://doi.org/10.1016/S0304-0208(08)72952-9
Butkovič, P.: On certain properties of the systems of linear extremal equations. Ekonom.-Mat. Obzor 14(1), 72–78 (1978)
Butkovič, P.: Solution of systems of linear extremal equations. Ekonom.-Mat. Obzor 17(4), 402–416 (1981)
Butkovič, P.: Max-linear Systems. Springer Monographs in Mathematics, Springer, London (2010). https://doi.org/10.1007/978-1-84996-299-5
Butkovič, P., Hegedüs, G.: An elimination method for finding all solutions of the system of linear equations over an extremal algebra. Ekonom.-Mat. Obzor 20(2), 203–215 (1984)
Butkovič, P., Zimmermann, K.: A strongly polynomial algorithm for solving two-sided linear systems in max-algebra. Discrete Appl. Math. 154(3), 437–446 (2006). https://doi.org/10.1016/j.dam.2005.09.008
Cuninghame-Green, R.A., Butkovic, P.: The equation \({A}\otimes x={B}\otimes y\) over (max,+). Theoret. Comput. Sci. 293(1), 3–12 (2003). https://doi.org/10.1016/S0304-3975(02)00228-1
Cuninghame-Green, R.A., Zimmermann, K.: Equation with residuated functions. Comment. Math. Univ. Carolin. 42(4), 729–740 (2001)
Develin, M., Sturmfels, B.: Tropical convexity. Doc. Math. 9, 1–27 (2004)
Gaubert, S., Katz, R.D.: The tropical analogue of polar cones. Linear Algebra Appl. 431(5), 608–625 (2009). https://doi.org/10.1016/j.laa.2009.03.012
Gaubert, S., Katz, R.D., Sergeev, S.: Tropical linear-fractional programming and parametric mean payoff games. J. Symbolic Comput. 47(12), 1447–1478 (2012). https://doi.org/10.1016/j.jsc.2011.12.049
Golan, J.S.: Semirings and Affine Equations Over Them, Mathematics and Its Applications, vol. 556. Kluwer Acad. Publ., Dordrecht (2003). https://doi.org/10.1007/978-94-017-0383-3
Gondran, M., Minoux, M.: Graphs, Dioids and Semirings, Operations Research/ Computer Science Interfaces, vol. 41. Springer, New York (2008). https://doi.org/10.1007/978-0-387-75450-5
Heidergott, B., Olsder, G.J., van der Woude, J.: Max Plus at Work. Princeton series in applied mathematics. Princeton Univ. Press, Princeton (2006)
Jones, D.: On two-sided max-linear equations. Discrete Appl. Math. 254(3), 146–160 (2019). https://doi.org/10.1016/j.dam.2018.06.011
Krivulin, N.K.: On the solution of a two-sided vector equation in tropical algebra. Vestnik St. Petersburg Univ. Math. 56(2), 172–181 (2023). https://doi.org/10.1134/S1063454123020103
Krivulin, N.K., Sorokin, V.N.: Solution of a multidimensional tropical optimization problem using matrix sparsification. Vestnik St. Petersburg Univ. Math. 51(1), 66–76 (2018). https://doi.org/10.3103/S1063454118010065
Krivulin, N.: Extremal properties of tropical eigenvalues and solutions to tropical optimization problems. Linear Algebra Appl. 468, 211–232 (2015). https://doi.org/10.1016/j.laa.2014.06.044
Krivulin, N.: A multidimensional tropical optimization problem with a non-linear objective function and linear constraints. Optimization 64(5), 1107–1129 (2015). https://doi.org/10.1080/02331934.2013.840624
Krivulin, N.: Solving a tropical optimization problem via matrix sparsification. In: Kahl, W., Winter, M., Oliveira, J.N. (eds.) RAMICS 2015. LNCS, vol. 9348, pp. 326–343. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-24704-5_20
Krivulin, N.: Algebraic solution of tropical optimization problems via matrix sparsification with application to scheduling. J. Log. Algebr. Methods Program. 89, 150–170 (2017). https://doi.org/10.1016/j.jlamp.2017.03.004
Krivulin, N.: Complete solution of an optimization problem in tropical semifield. In: Höfner, P., Pous, D., Struth, G. (eds.) RAMICS 2017. LNCS, vol. 10226, pp. 226–241. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-57418-9_14
Krivulin, N.: Complete algebraic solution of multidimensional optimization problems in tropical semifield. J. Log. Algebr. Methods Program. 99, 26–40 (2018). https://doi.org/10.1016/j.jlamp.2018.05.002
Krivulin, N.: Complete solution of tropical vector inequalities using matrix sparsification. Appl. Math. 65(6), 755–775 (2020). https://doi.org/10.21136/AM.2020.0376-19
Lorenzo, E., de la Puente, M.J.: An algorithm to describe the solution set of any tropical linear system \({A}\odot x={B}\odot x\). Linear Algebra Appl. 435(4), 884–901 (2011). https://doi.org/10.1016/j.laa.2011.02.014
Maclagan, D., Sturmfels, B.: Introduction to Tropical Geometry, Graduate Studies in Mathematics, vol. 161. AMS, Providence, RI (2015). https://doi.org/10.1090/gsm/161
Sakarovitch, J.: Elements of Automata Theory. Cambridge University Press, Cambridge (2009). https://doi.org/10.1017/CBO9781139195218
Truffet, L.: A decomposition formula of idempotent polyhedral cones based on idempotent superharmonic spaces. Beitr. Algebra Geom. 51(2), 313–336 (2010)
Walkup, E.A., Borriello, G., Taylor, J.M., Atiyah, M.: A general linear max-plus solution technique. In: Gunawardena, J. (ed.) Idempotency, p. 406-415. Publications of the Newton Institute, Cambridge Univ. Press (1998). https://doi.org/10.1017/CBO9780511662508.024
Zimmermann, K.: A general separation theorem in extremal algebras. Ekonom.-Mat. Obzor 13(2), 179-201 (1977)
Acknowledgments
The author is very grateful to three anonymous reviewers for their valuable comments and suggestions, which have been incorporated in the revised manuscript.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2024 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Krivulin, N. (2024). Using Matrix Sparsification to Solve Tropical Linear Vector Equations. In: Fahrenberg, U., Fussner, W., Glück, R. (eds) Relational and Algebraic Methods in Computer Science. RAMiCS 2024. Lecture Notes in Computer Science, vol 14787. Springer, Cham. https://doi.org/10.1007/978-3-031-68279-7_12
Download citation
DOI: https://doi.org/10.1007/978-3-031-68279-7_12
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-68278-0
Online ISBN: 978-3-031-68279-7
eBook Packages: Computer ScienceComputer Science (R0)