THE EIGENVECTORS OF REDUCIBLE MATRICES OVER MIN-PLUS ALGEBRA
Abstract
The eigenvalues and the eigenvectors of a matrix are fundamental concepts in max-plus algebra, especially for square matrices. A communication graph is classified as strongly connected or not, corresponding to irreducible and reducible matrices, respectively. This study aims to develop methods for determining the eigenvectors of reducible matrices over min-plus algebra. Before determining the eigenvectors, we need to determine the eigenvalues. The methodology used is based on the Frobenius Normal Form and graph condensation to decompose the reducible matrix into spectral classes. The eigenvalues can be found using the graphical method. Eigenvectors can be determined for each corresponding eigenvalue. Once the eigenvectors are known, we can find the set of eigenvectors as a map of a matrix. The main results include a characterization of eigenvector bases for each spectral class, criteria for the existence of finite eigenvectors, and an analysis of computational complexity. An isomorphic correspondence exists between min-plus algebra and max-plus algebra. Hence, the eigenvectors of reducible matrices over min-plus algebra are able to be evaluated according to a concept from eigenvectors of reducible matrices over max-plus algebra. This study is limited to min-plus algebra and does not extend to interval min-plus algebra.
Downloads
References
C. Leake, “SYNCHRONIZATION AND LINEARITY: AN ALGEBRA FOR DISCRETE EVENT SYSTEMS,” J. Oper. Res. Soc., vol. 45, no. 1, pp. 118–119, 1994. doi: https://doi.org/10.1057/jors.1994.15.
K. P. Tam, “OPTIMIZING AND APPROXIMATING EIGENVECTORS IN MAX-ALGEBRA,” 2010. [Online]. Available: Bham.ac.uk
T. Rambow and U. Kiencke, MAX-PLUS-ALGEBRA, TEIL 1 (MAX-PLUS ALGEBRA, PART 1), vol. 53, no. 10. 2005. doi: https://doi.org/10.1524/auto.2005.53.10_2005.A1.
P. Butkovič, MAX-LINEAR SYSTEMS: THEORY AND ALGORITHMS. London: Springer, 2010. doi: https://doi.org/10.1007/978-1-84996-299-5.
M. Akian and R. Bapat, “MAX-PLUS ALGEBRA,” Handb. linear Algebr., 2007, [Online]. doi: https://doi.org/10.1201/9781420010572-25.
B. Heidergott, G. J. Olsder, and J. van der Woude, MAX PLUS AT WORK: MODELING AND ANALYSIS OF SYNCHRONIZED SYSTEMS: A COURSE ON MAX-PLUS ALGEBRA AND ITS APPLICATIONS. Princeton University Press, 2015.
E. Carnia, R. Wilopo, H. Napitupulu, N. Anggriani, and A. K. Supriatna, “MODIFIED KLEENE STAR ALGORITHM USING MAX-PLUS ALGEBRA AND ITS APPLICATION IN THE RAILROAD SCHEDULING GRAPHICAL USER INTERFACE,” Computation, vol. 11, no. 1, 2023. doi: https://doi.org/10.3390/computation11010011.
K. Tunisa, K. Wijayanti, R. Budhiati Veronica, and D. Juni, “NILAI EIGEN DAN VEKTOR EIGEN MATRIKS ATAS ALJABAR MAX-PLUS,” Ujm, vol. 6, no. 2, pp. 189–197, 2017, [Online]. Available: http://journal.unnes.ac.id/sju/index.php/ujm
J. G. Braker and G. J. Olsder, “THE POWER ALGORITHM IN MAX ALGEBRA,” Linear Algebra Appl., vol. 182, no. C, pp. 67–89, 1993. doi: https://doi.org/10.1016/0024-3795(93)90492-7.
M. Subiono and J. van der Woude, “POWER ALGORITHMS FOR (MAX, +)- AND BIPARTITE (MIN, MAX, +)-SYSTEMS,” Discret. Event Dyn. Syst. Theory Appl., vol. 10, no. 4, pp. 369–389, 2000. doi: https://doi.org/10.1023/A:1008315821604.
K. H. Rosen, D. R. Shier, and W. Goddard, HANDBOOK OF DISCRETE AND COMBINATORIAL MATHEMATICS, Second Edition. Chapman and Hall/CRC. doi: https://doi.org/10.1201/9781315156484.
Z. R. Königsberg, “A GENERALIZED EIGENMODE ALGORITHM FOR REDUCIBLE REGULÅ MATRICES OVER THE MAX-PLUS ALGEBRA,” 2009 Chinese Control Decis. Conf. CCDC 2009, no. 24, pp. 5598–5603, 2009. doi: https://doi.org/10.1109/CCDC.2009.5195195.
H. Mursyidah and S. Subiono, “EIGENVALUE, EIGENVECTOR, EIGENMODE OF REDUCIBLE MATRIX AND ITS APPLICATION,” AIP Conf. Proc., vol. 1867, no. June, pp. 0–11, 2017. doi: https://doi.org/10.1063/1.4994447.
R. B. Bapat, D. Stanford, and P. Van den Driessche, “THE EIGENPROBLEM IN MAX ALGEBRA.” 1993.
P. Butkovič, R. A. Cuninghame-Green, and S. Gaubert, “REDUCIBLE SPECTRAL THEORY WITH APPLICATIONS TO THE ROBUSTNESS OF MATRICES IN MAX-ALGEBRA,” SIAM Journal on Matrix Analysis and Applications, vol. 31, no. 3. pp. 1412–1431, 2009. doi: https://doi.org/10.1137/080731232.
A. Spalding, “MIN-PLUS ALGEBRA AND GRAPH DOMINATION,” UMI Co., p. 274, 1998.
A. W. Nowak, “THE TROPICAL EIGENVALUE-VECTOR PROBLEM FROM ALGEBRAIC , GRAPHICAL , AND COMPUTATIONAL PERSPECTIVES,” pp. 1–11, 2014.
S. Watanabe and Y. Watanabe, “MIN-PLUS ALGEBRA AND NETWORKS (NOVEL DEVELOPMENT OF NONLINEAR DISCRETE INTEGRABLE SYSTEMS),” RIMS Kôkyûroku Bessatsu, vol. 47, 2014.
S. Siswanto and A. Gusmizain, “DETERMINING THE INVERSE OF A MATRIX OVER MIN-PLUS ALGEBRA,” JTAM (Jurnal Teor. dan Apl. Mat., vol. 8, no. 1, p. 244, 2024. doi: https://doi.org/10.31764/jtam.v8i1.17432
Z. N. R. Putri, S. Siswanto, and V. Y. Kurniawan, “CRAMER’S RULE IN MIN-PLUS ALGEBRA,” BAREKENG J. Ilmu Mat. dan Terap., vol. 18, no. 2, pp. 1147–1154, 2024. doi: https://doi.org/10.30598/barekengvol18iss2pp1147-1154.
S. M. Al Maghribi, S. Siswanto, and S. Sutrima, “CHARACTERISTIC MIN-POLYNOMIAL AND EIGEN PROBLEM OF A MATRIX OVER MIN-PLUS ALGEBRA,” JTAM (Jurnal Teor. dan Apl. Mat., vol. 7, no. 4, p. 1108, 2023. doi: https://doi.org/10.31764/jtam.v7i4.16498.
E. W. Rahayu, S. Siswanto, and S. B. Wiyono, “MASALAH EIGEN DAN EIGENMODE MATRIKS ATAS ALJABAR MIN-PLUS,” BAREKENG J. Ilmu Mat. dan Terap., vol. 15, no. 4, pp. 659–666, 2021. doi: https://doi.org/10.30598/barekengvol15iss4pp659-666.
Copyright (c) 2026 Siswanto Siswanto, Riko Fajarudin
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
Authors who publish with this Journal agree to the following terms:
- Author retain copyright and grant the journal right of first publication with the work simultaneously licensed under a creative commons attribution license that allow others to share the work within an acknowledgement of the work’s authorship and initial publication of this journal.
- Authors are able to enter into separate, additional contractual arrangement for the non-exclusive distribution of the journal’s published version of the work (e.g. acknowledgement of its initial publication in this journal).
- Authors are permitted and encouraged to post their work online (e.g. in institutional repositories or on their websites) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published works.
1.gif)
