×

zbMATH — the first resource for mathematics

On commuting matrices in max algebra and in classical nonnegative algebra. (English) Zbl 1245.15026
The authors study spectral properties of commuting matrices in max algebra, i.e., in a linear algebra over the max-times semiring of nonnegative numbers under the operation of maximum as addition and ordinary multiplication as multiplication. This is also known as tropical algebra, although the logarithmic notation where multiplication is replaced by ordinary addition and nonnegative numbers by reals (together with \(-\infty\)) is perhaps more common.
In the last section of the paper, it is explained that most of the results hold also in classical nonnegative algebra (Perron-Frobenius theory).
Note that (in both settings) every square matrix has a (nonnegative) eigenvalue. The largest eigenvalue is called the Perron root of the matrix.
The first main result of the paper is that commuting matrices have a common eigenvector. More precisely, if \(A_1\), …, \(A_r\) commute in pairs and \(\alpha_1\) is any eigenvalue of \(A_1\), then there exists an eigenvalue \(\alpha_j\) of \(A_j\) for \(j=2,\dots, r\) and and a nonnegative vector \(v\neq 0\) such that \(A_jv=\alpha_jv\) for \(j=1,2,\dots, r\). As a consequence, \(p(\alpha_1,\alpha_2,\dots, \alpha_r)\) is an eigenvalue of \(p(A_1,A_2,\dots, A_r)\) for any polynomial \(p\). Moreover, if \(\alpha_1\) is no longer fixed, then all eigenvalues of \(p(A_1,\dots, A_r)\) are obtained in this manner. (This is the max analog of a result of F. Frobenius [Borchardt J. LXXXIV, 1–63 (1877; JFM 09.0085.02); Berl. Ber., 601–614 (1896; JFM 27.0109.04)], reproved by I. Schur [Berl. Ber. 120–125 (1902; JFM 33.0171.04)].) It follows that the Perron root of \(p(A_1,\dots, A_r)\) is at most \(p\) of the Perron roots of the \(A_i\).
A more precise max analog of the Frobenius-Schur result is given under the extra assumption that for each \(i\), the diagonal submatrices corresponding to the strongly connected components of the digraph given by the nonzero entries of \(A_i\) have pairwise distinct Perron roots. In this case, it is also shown that the \(A_i\) can be put into Frobenius normal form by a common simultaneous permutation of rows and columns.
For the case of max algebra only, the intersection of eigencones of commuting matrices is described. The authors consider connections with Boolean algebra which enable them to prove that, in max algebra, two commuting matrices having strongly connected digraphs always have a common eigennode. An eigennode of a matrix \(A\) is an index \(i_1\) such that, for some \(1\leq k\leq n\) and some \(i_2,\dots, i_k\), the cycle geometric mean \(({a_{i_1i_2}\cdots a_{i_ki_1}})^{1/k}\) is maximal among all cycle geometric means for all \(k\), i.e., it equals the Perron root of \(A\).
Some of the most important results of the paper are illustrated by numerical examples.

MSC:
15A80 Max-plus and related algebras
15A27 Commutativity of matrices
15A18 Eigenvalues, singular values, and eigenvectors
15B48 Positive matrices and their generalizations; cones of matrices
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Akian, M.; Bapat, R.; Gaubert, S., MAX-plus algebra, (), (Article 25)
[2] Baccelli, F.L.; Cohen, G.; Olsder, G.J.; Quadrat, J.P., Synchronization and linearity: an algebra for discrete event systems, (1992), Wiley
[3] Berman, A.; Plemmons, R., Nonnegative matrices in the mathematical sciences, (1994), SIAM · Zbl 0815.15016
[4] Butkovič, P., MAX-linear systems: theory and applications, (2010), Springer, (in print)
[5] Butkovič, P.; Cuninghame-Green, R.A.; Gaubert, S., Reducible spectral theory with applications to the robustness of matrices in MAX-algebra, SIAM J. matrix anal. appl., 31, 3, 1412-1431, (2009) · Zbl 1204.15019
[6] Butkovic˘, P.; Hegedüs, G., An elimination method for finding all solutions of the system of linear equations over an extremal algebra, Ekonom.-mat. obzor (Prague), 20, 2, 203-215, (1984)
[7] Cayley, A., A memoir on the theory of matrices, Philos. trans. R. soc, 148, 17-37, (1858), (Coll. Math. Papers, vol. 2, Cambridge, 1889, pp. 475-496)
[8] Cochet-Terrasson, J.; Gaubert, S.; Gunawardena, J., A constructive fixed point theorem for MIN-MAX functions, Dyn. stab. syst., 14, 4, 407-443, (1999) · Zbl 0958.47028
[9] R.A. Cuninghame-Green, Minimax algebra, in: Lecture Notes in Economics and Mathematical Systems, vol. 166, Springer, Berlin, 1979.
[10] R.A. Cuninghame-Green, P. Butkovič, Generalised eigenproblem in max algebra, in: Proceedings of the 9th International Workshop WODES 2008, 2008, pp. 236-241. Available from: <http://ieeexplore.ieee.org/stamp/>.
[11] D. Dolžan, P. Oblak, Commuting graphs of matrices over semirings, Linear Algebra Appl. (2010), in press.
[12] D. Dolžan, P. Oblak, Noncommuting graphs of matrices over semirings, Linear Algebra Appl. (2010), in press.
[13] Drazin, M.P., Some generalizations of matrix commutativity, Proc. London math. soc., 3, 1, 222-231, (1951) · Zbl 0043.01701
[14] Drazin, M.P.; Dungey, J.W.; Gruenberg, K.W., Some theorems on commutative matrices, J. London math. soc., 26, 221-228, (1951) · Zbl 0043.25201
[15] Frobenius, F.G., Über lineare substitutionen und bilineare formen, J. reine angew. math., 84, 1-63, (1878), (Ges. Abh., vol. 1, Springer, pp. 343-405) · JFM 09.0085.02
[16] F.G. Frobenius, Über vertauschbare Matrizen. Sitzunsb. Kön. Preuß. Akad. Wiss. Berlin, 1896, pp. 601-614 (Ges. Abh., vol. 2, Springer, 1968, pp. 705-718).
[17] F.G. Frobenius, Über Matrizen aus positiven Elementen. Sitzungsber. Kön. Preuss. Akad. Wiss. Berlin, 1908, pp. 471-476 (Ges. Abh., vol. 3, Springer, Berlin, 1968, pp. 404-409). · JFM 39.0213.03
[18] F.G. Frobenius, Über Matrizen aus positiven Elementen, II. Sitzungsber. Kön. Preuss. Akad. Wiss. Berlin, 1909, pp. 514-518 (Ges. Abh., vol. 3, Springer, Berlin, 1968, pp. 410-414). · JFM 40.0202.02
[19] F.G. Frobenius, Über Matrizen aus nicht negativen Elementen, Sitzungsber. Kön. Preuss. Akad. Wiss., Berlin, 1912, pp. 456-477 (Ges. Abh., vol. 3, Springer, Berlin, 1968, pp. 546-567). · JFM 43.0204.09
[20] F.R. Gantmacher, The Theory of Matrices, Chelsea, 1959. · Zbl 0085.01001
[21] S. Gaubert, Théorie des sytemes linéaires dans les dioı¨des, Thèse, École des Mines des Paris, 1992.
[22] S. Gaubert, R.D. Katz, Minimal half-spaces and external representation of tropical polyhedra, J. Algebr. Combin., 2010, in press, e-print arxiv:0908.1586.
[23] S. Gaubert, M. Plus, Methods and applications of (max,+) linear algebra, in: 14th Annual Symposium on Theoretical Aspects of Computer Science (STACS), LNCS, vol. 1200, Springer, 1997, pp. 261-282.
[24] R.A. Horn, C.R. Johnson, Matrix Analysis, Cambridge, 1985. · Zbl 0576.15001
[25] B. Heidergott, G.J. Olsder, J. van der Woude, Max-plus at Work, Princeton, 2005.
[26] Kolokoltsov, V.N.; Maslov, V.P., Idempotent analysis and its applications, (1997), Kluwer · Zbl 0941.93001
[27] Litvinov, G.L., The Maslov dequantization, idempotent and tropical mathematics: a brief introduction, J math. sci., 140, 3, 426-444, (2007), e-print arXiv:math.GM/0507014 · Zbl 1102.46049
[28] Mc Kinley, T.; Shekhtman, B., On simultaneous block-diagonalization of cyclic sequences of commuting matrices, Linear and multilinear algebra, 58, 245-256, (2010) · Zbl 1188.15011
[29] Perron, O., Grundlagen für eine theorie des jacobischen kettenbruchalgorithmus, Math. ann., 63, 1-76, (1907) · JFM 38.0262.01
[30] Perron, O., Zur theorie der matrices, Math. ann., 6, 248-263, (1907) · JFM 38.0202.01
[31] Radjavi, H., The perron – frobenius theorem revisited, Positivity, 3, 317-331, (1999) · Zbl 0941.15019
[32] Radjavi, H.; Rosenthal, P., Simultaneous triangularization, (2000), Springer · Zbl 0981.15007
[33] Rothblum, U.G., Nonnegative and stochastic matrices, (), (Article 9)
[34] Schneider, H., The influence of the marked reduced graph of a nonnegative matrix on the Jordan form and related properties: a survey, Linear algebra appl., 84, 161-189, (1986) · Zbl 0613.15017
[35] Schur, I., Über einen satz aus der theorie de vertauschbaren matrizen, Sitzunsb. preuß. akad. wiss. Berlin, phys-math. klass, 120-125, (1902), (Ges. Abh., vol. 1, Springer, pp. 73-78) · JFM 33.0171.04
[36] Tam, B.S.; Schneider, H., Matrices leaving a cone invariant, (), (Article 26)
[37] Weyr, E., Zur theorie der bilinearen formen, Monatsh. math. phys., 1, 163-236, (1890) · JFM 22.0141.02
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.