Kybernetika 58 no. 5, 691-707, 2022

Non-surjective linear transformations of tropical matrices preserving the cyclicity index

Alexander Guterman, Elena Kreines and Alexander VlasovDOI: 10.14736/kyb-2022-5-0691

Abstract:

\begin{center} To the memory of Professor Martin Gavalec. \end{center} 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.

Keywords:

tropical linear algebra, cyclicity index, linear transformations

Classification:

05C22, 05C38, 05C50

paper.pdf

References:

  1. F. Baccelli, G. Cohen, G.J. Olsder and J.-P. Quadrat: Synchronization and Linearity. Wiley 1992.   CrossRef
  2. P. Butkovič: Max-algebra: the linear algebra of combinatorics? Linear Algebra and its Applications 367 (2003), 313-335.   DOI:10.1016/s0024-3795(02)00655-9
  3. D.J. Dieudonné: Sur une généralisation du groupe orthogonal á quatre variables. Arch. Math. 1 (1949), 282-287.   CrossRef
  4. G. Frobenius: Über die Darstellung der endlichen Gruppen durch lineare Substitutionen. Sitzungsber Deutsch. Akad. Wiss., Berlin 1997.   CrossRef
  5. D. Jones: Matrix roots in the max-plus algebra. Linear Algebra and its Applications 631 (2021), 10-34.   DOI:10.1016/j.laa.2021.08.008
  6. M. Gavalec: Periodicity in Extremal Algebras. Hradec Králové: Gaudeamus 2004.   CrossRef
  7. M. Gavalec: Linear matrix period in max-plus algebra. Linear Algebra and its Applications 307 (2000), 167-182.   DOI:10.1016/s0024-3795(00)00020-3
  8. A. Guterman, M. Johnson and M. Kambites: Linear isomorphisms preserving Green's relations for matrices over anti-negative semifields. Linear Algebra and its Applications 545 (2018), 1-14.   DOI:10.1016/j.laa.2018.01.023
  9. A. Guterman, E. Kreines and C. Thomassen: Linear transformations of tropical matrices preserving the cyclicity index. Special Matrices 9 (2021), 112-118.   DOI:10.1515/spma-2020-0128
  10. A. Guterman and A. Maksaev: Maps preserving scrambling index. Linear and Multilinear Algebra 66 (2018), 840-851.   DOI:10.1080/03081087.2017.1329814
  11. B. Heidergott, G.J. Olsder and J. van der Woude: Max Plus at Work. Princeton Series in Applied Mathematics 2006.   CrossRef
  12. A. Kennedy-Cochran-Patrick, G. Merlet, T. Nowak and S. Sergeev: 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:10.1016/j.laa.2020.10.032
  13. G. Merlet, T. Nowak and S. Sergeev: Weak CSR expansions and transience bounds in max-plus algebra. Linear Algebra and its Applications 461 (2014) 163-199.   DOI:10.1016/j.laa.2014.07.027
  14. S. Pierce and et al.: A survey of linear preserver problems. Linear Multilinear Algebra 33 (1992), 1-119.   DOI:10.1080/03081089208818176
  15. L. Rodman and P. Šemrl: A localization technique for linear preserver problems Linear Algebra and its Applications 433 (2010), 2257-2268.   DOI:10.1016/j.laa.2010.07.032
  16. I. Schur: Einige Bemerkungen zur Determinantentheorie. Akad. Wiss. Berlin: S.-Ber. Preuss., (1925) 454-463.   CrossRef
  17. S. Sergeev: 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:10.1016/j.laa.2009.04.027