Applications of Mathematics, Vol. 65, No. 6, pp. 785-805, 2020

On the vectors associated with the roots of max-plus characteristic polynomials

Yuki Nishida, Sennosuke Watanabe, Yoshihide Watanabe

Received December 28, 2019.   Published online September 15, 2020.

Abstract:  We discuss the eigenvalue problem in the max-plus algebra. For a max-plus square matrix, the roots of its characteristic polynomial are not its eigenvalues. In this paper, we give the notion of algebraic eigenvectors associated with the roots of characteristic polynomials. Algebraic eigenvectors are the analogues of the usual eigenvectors in the following three senses: (1) An algebraic eigenvector satisfies an equation similar to the equation $A\otimes\boldsymbol{x} = \lambda\otimes\boldsymbol{x}$ for usual eigenvectors. Under a suitable assumption, the equation has a nontrivial solution if and only if $\lambda$ is a root of the characteristic polynomial. (2) The set of algebraic eigenvectors forms a max-plus subspace called algebraic eigenspace. (3) The dimension of each algebraic eigenspace is at most the multiplicity of the corresponding root of the characteristic polynomial.
Keywords:  max-plus algebra; eigenvalue; eigenvector; characteristic polynomial
Classification MSC:  15A18, 15A80

[1] M. Akian, R. Bapat, S. Gaubert: Max-plus algebra. Handbook of Linear Algebra (L. Hogben et al., eds.). Discrete Mathematics and Its Applications 39. Chapman & Hall/CRC, Boca Raton, 2007, 35-1, 18 pages. MR 2279160 | Zbl 1122.15001
[2] M. Akian, S. Gaubert, A. Guterman: Tropical polyhedra are equivalent to mean payoff games. Int. J. Algebra Comput. 22 (2012), Article ID 1250001, 43 pages. DOI 10.1142/S0218196711006674 | MR 2900854 | Zbl 1239.14054
[3] F. Baccelli, G. Cohen, G. J. Olsder, J. P. Quadrat: Synchronization and Linearity: An Algebra for Discrete Event Systems. Wiley Series on Probability and Mathematical Statistics: Probability and Mathematical Statistics. Wiley, Chichester (1992). MR 1204266 | Zbl 0824.93003
[4] P. Butkovič: Max-Linear Systems: Theory and Algorithms. Springer Monographs in Mathematics. Springer, London (2010). DOI 10.1007/978-1-84996-299-5 | MR 2681232 | Zbl 1202.15032
[5] P. Butkovič, H. Schneider, S. Sergeev: Generators, extremals and bases of max cones. Linear Algebra Appl. 421 (2007), 394-406. DOI 10.1016/j.laa.2006.10.004 | MR 2294351 | Zbl 1119.15018
[6] R. A. Cuninghame-Green: The characteristic maxpolynomial of a matrix. J. Math. Anal. Appl. 95 (1983), 110-116. DOI 10.1016/0022-247X(83)90139-7 | MR 0710423 | Zbl 0526.90098
[7] R. A. Cuninghame-Green: Minimax algebra and applications. Adv. Imaging Electron Phys. 90 (1994), 1-121. DOI 10.1016/S1076-5670(08)70083-1
[8] B. Heidergott, G. J. Olsder, J. Van der Woude: Max Plus at Work. Modeling and Analysis of Synchronized Systems: A Course on Max-Plus Algebra and Its Applications. Princeton Series in Applied Mathematics. Princeton University Press, Princeton (2006). MR 2188299 | Zbl 1130.93003
[9] Z. Izhakian, L. Rowen: Supertropical matrix algebra. Isr. J. Math. 182 (2011), 383-424. DOI 10.1007/s11856-011-0036-2 | MR 2783978 | Zbl 1215.15018
[10] Z. Izhakian, L. Rowen: Supertropical matrix algebra II: Solving tropical equations. Isr. J. Math. 186 (2011), 69-96. DOI 10.1007/s11856-011-0133-2 | MR 2852317 | Zbl 1277.15013
[11] Z. Izhakian, L. Rowen: Supertropical matrix algebra III: Powers of matrices and their supertropical eigenvalues. J. Algebra 341 (2011), 125-149. DOI 10.1016/j.jalgebra.2011.06.002 | MR 2824513 | Zbl 1283.15055
[12] D. Maclagan, B. Sturmfels: Introduction to Tropical Geometry. Graduate Studies in Mathematics 161. American Mathematical Society, Providence (2015). MR 3287221 | Zbl 1321.14048
[13] Y. Nishida, K. Sato, S. Watanabe: A min-plus analogue of the Jordan canonical form associated with the basis of the generalized eigenspace. To appear in Linear Multilinear Algebra. DOI 10.1080/03081087.2019.1700892
[14] A. Niv, L. Rowen: Dependence of supertropical eigenspaces. Commun. Algebra 45 (2017), 924-942. DOI 10.1080/00927872.2016.1172603 | MR 3573348 | Zbl 1378.15006

Affiliations:   Yuki Nishida, Doshisha University, 1-3 Tatara Miyakodani, Kyotanabe, Kyoto 610-0394, Japan, e-mail:; Sennosuke Watanabe, National Institute of Technology, Oyama College, 771 Nakakuki, Oyama, Tochigi 323-0806, Japan, e-mail:; Yoshihide Watanabe, Doshisha University, 1-3 Tatara Miyakodani, Kyotanabe, Kyoto 610-0394, Japan, e-mail:

PDF available at: