Article
Full entry |
PDF
(0.4 MB)
Feedback
PDF
(0.4 MB)
Feedback
Keywords:
tropical linear algebra; cyclicity index; linear transformations
tropical linear algebra; cyclicity index; linear transformations
Summary:
The cyclicity index of a matrix is the cyclicity index of its critical subgraph, namely, the subgraph of the adjacency graph which consists of all cycles of the maximal average weight. The cyclicity index of a graph is the least common multiple of the cyclicity indices of all its maximal strongly connected subgraphs, and the cyclicity index of a strongly connected graph is the least common divisor of the lengths of its (directed) cycles. In this paper we obtain the characterization of linear, possibly non-surjective, transformations of tropical matrices preserving the cyclicity index. It appears that non-bijective maps with these properties exist and all maps are exhausted by transposition, renumbering of vertices, Hadamard multiplication with a matrix of a certain special structure, and certain diagonal transformation. Moreover, only diagonal transformation can be non-bijective.
References:
[1] Baccelli, F., Cohen, G., Olsder, G.J., Quadrat, J.-P.: Synchronization and Linearity. Wiley 1992. Zbl 0824.93003
[2] Butkovič, P.: Max-algebra: the linear algebra of combinatorics?. Linear Algebra and its Applications 367 (2003), 313-335. DOI | Zbl 1022.15017
[3] Dieudonné, D.J.: Sur une généralisation du groupe orthogonal á quatre variables. Arch. Math. 1 (1949), 282-287. DOI 10.1007/BF02038756
[4] Frobenius, G.: Über die Darstellung der endlichen Gruppen durch lineare Substitutionen. Sitzungsber Deutsch. Akad. Wiss., Berlin 1997.
[5] Jones, D.: Matrix roots in the max-plus algebra. Linear Algebra and its Applications 631 (2021), 10-34. DOI
[6] Gavalec, M.: Periodicity in Extremal Algebras. Hradec Králové: Gaudeamus 2004.
[7] Gavalec, M.: Linear matrix period in max-plus algebra. Linear Algebra and its Applications 307 (2000), 167-182. DOI
[8] Guterman, A., Johnson, M., Kambites, M.: Linear isomorphisms preserving Green's relations for matrices over anti-negative semifields. Linear Algebra and its Applications 545 (2018), 1-14. DOI
[9] Guterman, A., Kreines, E., Thomassen, C.: Linear transformations of tropical matrices preserving the cyclicity index. Special Matrices 9 (2021), 112-118. DOI
[10] Guterman, A., Maksaev, A.: Maps preserving scrambling index. Linear and Multilinear Algebra 66 (2018), 840-851. DOI
[11] Heidergott, B., Olsder, G.J., Woude, J. van der: Max Plus at Work. Princeton Series in Applied Mathematics 2006.
[12] Kennedy-Cochran-Patrick, A., Merlet, G., Nowak, T., Sergeev, S.: New bounds on the periodicity transient of the powers of a tropical matrix: Using cyclicity and factor rank. Linear Algebra and its Applications 611 (2021) 279-309. DOI
[13] Merlet, G., Nowak, T., Sergeev, S.: Weak CSR expansions and transience bounds in max-plus algebra. Linear Algebra and its Applications 461 (2014) 163-199. DOI
[14] Pierce, S., al., et: A survey of linear preserver problems. Linear Multilinear Algebra 33 (1992), 1-119. DOI
[15] Rodman, L., Šemrl, P.: A localization technique for linear preserver problems. Linear Algebra and its Applications 433 (2010), 2257-2268. DOI
[16] Schur, I.: Einige Bemerkungen zur Determinantentheorie. Akad. Wiss. Berlin: S.-Ber. Preuss., (1925) 454-463.
[17] Sergeev, S.: Max algebraic powers of irreducible matrices in the periodic regime: An application of cyclic classes. Linear Algebra and its Applications 431 (2009), 1325-339. DOI
Search
Partner of
