Integer Eigenvectors and Subeigenvectors in Min-Plus Algebra
Keywords:
Min-plus Algebra, Eigenvectors, Subeigenvectors, Integer, Column SpaceAbstract
We study integer eigenvectors and subeigenvectors in min-plus algebra by adapting theoretical results from max-plus algebra. Min-plus algebra is a commutative semiring with addition and multiplication . An eigenvector of a matrix with respect to a scalar is a vector satisfying the equation . Similarly, a subeigenvector of with respect to is a vector satisfying the inequality . In this paper, we focus on solutions where these vectors consist entirely of integers. We first provide the exact mathematical criteria for integer subeigenvectors to exist. We show that this existence depends on the principal eigenvalue of a scaled and rounded matrix, which is determined by the minimum average circuit weight of its associated graph. If the condition is satisfied, we can explicitly describe the complete set of these subeigenvectors. Secondly, we establish that an integer eigenvector can only correspond to the principal eigenvalue of the matrix. Finally, we demonstrate that determining an integer eigenvector is equivalent to finding an integer image in a column space, which can be solved using an iterative algorithm.
References
[1] F. Baccelli, G. Cohen, G. J. Olsder, and J.-P. Quadrat, Synchronization and Linearity: An Algebra for Discrete Event Systems. New York, NY, USA: Wiley, 1992.
[2] B. Heidergott, G. J. Olsder, and J. van der Woude, Max Plus at Work: Modeling and Analysis of Synchronized Systems. Princeton, NJ, USA: Princeton University Press, 2014.
[3] M. Gondran and M. Minoux, Graphs, Dioids and Semirings: New Models and Algorithms. New York, NY, USA: Springer, 2008.
[4] C. G. Cassandras and S. Lafortune, Introduction to Discrete Event Systems, 2nd ed. New York, NY, USA: Springer, 2008.
[5] J. Stańczyk, “Max-plus algebra as a tool to modelling and performance analysis of manufacturing systems,” Operations Research and Decisions, vol. 28, no. 3, pp. 77–97, 2018.
[6] Subiono, Aljabar Min-Max Plus dan Terapannya, 3rd ed. Surabaya, Indonesia: Institut Teknologi Sepuluh Nopember, 2015.
[7] R. M. P. Goverde, “Railway timetable stability analysis using max-plus algebra,” Control Eng. Pract., vol. 15, no. 1, pp. 43–54, 2007.
[8] B. De Schutter and T. van den Boom, “Model predictive control for max-plus-linear discrete event systems,” Automatica, vol. 37, no. 7, pp. 1049–1056, 2001.
[9] G. Cohen, S. Gaubert, and J.-P. Quadrat, “Max-plus algebra and system theory: Where we are and where to go now,” Annu. Rev. Control, vol. 23, pp. 207–219, 1999.
[10] B. De Schutter, T. van den Boom, J. Xu, and S. S. Farahani, “Analysis and control of max-plus linear discrete-event systems: An introduction,” Discret. Event Dyn. Syst., vol. 30, no. 1, pp. 25–54, 2020.
[11] J. Komenda, S. Lahaye, J.-L. Boimond, and T. van den Boom, “Max-plus algebra in the history of discrete event systems,” Annu. Rev. Control, vol. 45, pp. 240–249, 2018.
[12] M. Akian, R. Bapat, and S. Gaubert, “Max-plus algebra,” in Handbook of Linear Algebra, L. Hogben, Ed., Boca Raton, FL, USA: Chapman and Hall/CRC, 2006, ch. 25.
[13] J. Cochet-Terrasson, G. Cohen, S. Gaubert, M. McGettrick, and J.-P. Quadrat, “Numerical computation of spectral elements in max-plus algebra,” in Proceedings of the IFAC Conference on System Structure and Control, Nantes, France, 1998, pp. 699–706.
[14] S. Sergeev, “Max-algebraic core of a nonnegative matrix,” Linear Algebra Appl., vol. 430, no. 10, pp. 2732–2755, 2009.
[15] N. Krivulin, “Extremal properties of tropical eigenvalues and solutions to tropical optimization problems,” Linear Algebra Appl., vol. 468, pp. 211–232, 2015.
[16] P. Butkovič, Max-linear Systems: Theory and Algorithms. London, U.K.: Springer-Verlag, 2010.
[17] P. Butkovič and M. MacCaig, “On integer eigenvectors and subeigenvectors in the max-plus algebra,” Linear Algebra Appl., vol. 438, no. 8, pp. 3408–3424, 2013, doi: 10.1016/j.laa.2012.12.022.
[18] A. W. Nowak, “The tropical eigenvalue-vector problem from algebraic, graphical, and computational perspectives,” Department of Mathematics, Bates College, Lewiston, ME, USA, 2014.
[19] Siswanto, N. Nurhayati, A. Gusmizain, S. A. Rosyada, E. Widia, and D. A. Adilla, Aljabar Min-Plus. Surakarta, Indonesia: Global Aksara Pers, 2023.
[20] P. Lotito, E. Mancinelli, and J.-P. Quadrat, “A minplus derivation of the fundamental car-traffic law,” IEEE Trans. Automat. Contr., vol. 50, no. 5, pp. 699–705, May 2005.
[21] S. Watanabe and Y. Watanabe, “Min-plus algebra and network,” RIMS Kôkyûroku Bessatsu, vol. B47, pp. 41–54, 2014.
[22] V. Suwanti, P. Bintoto, and R. N. I. Dinullah, “Penerapan min plus algebra pada penentuan rute tercepat distribusi susu,” Limits: Journal of Mathematics and Its Applications, vol. 14, no. 2, pp. 103–112, 2017.
[23] J.-É. Pin, “Tropical semirings,” in Idempotency, vol. 11, J. Gunawardena, Ed., Cambridge, U.K.: Cambridge University Press, 1998, pp. 50–69.
[24] M. MacCaig, “Tropical matrix algebra and discrete event systems,” School of Mathematics, University of Birmingham, Birmingham, U.K., 2015.
[25] K. P. Tam, “Optimizing and approximating eigenvectors in max algebra,” School of Mathematics, University of Birmingham, Birmingham, U.K., 2010.
