Geodesic
Non-surjective linear transformations of tropical matrices preserving the cyclicity index
Kybernetika, Tome 58 (2022) no. 5, pp. 691-707
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
DOI : 10.14736/kyb-2022-5-0691
Classification : 05C22, 05C38, 05C50
Keywords: tropical linear algebra; cyclicity index; linear transformations 
@article{10_14736_kyb_2022_5_0691,
     author = {Guterman, Alexander and Kreines, Elena and Vlasov, Alexander},
     title = {Non-surjective linear transformations of tropical matrices preserving the cyclicity index},
     journal = {Kybernetika},
     pages = {691--707},
     year = {2022},
     volume = {58},
     number = {5},
     doi = {10.14736/kyb-2022-5-0691},
     mrnumber = {4538621},
     zbl = {07655855},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.14736/kyb-2022-5-0691/}
}
TY  - JOUR
AU  - Guterman, Alexander
AU  - Kreines, Elena
AU  - Vlasov, Alexander
TI  - Non-surjective linear transformations of tropical matrices preserving the cyclicity index
JO  - Kybernetika
PY  - 2022
SP  - 691
EP  - 707
VL  - 58
IS  - 5
UR  - http://geodesic.mathdoc.fr/articles/10.14736/kyb-2022-5-0691/
DO  - 10.14736/kyb-2022-5-0691
LA  - en
ID  - 10_14736_kyb_2022_5_0691
ER  - 
%0 Journal Article
%A Guterman, Alexander
%A Kreines, Elena
%A Vlasov, Alexander
%T Non-surjective linear transformations of tropical matrices preserving the cyclicity index
%J Kybernetika
%D 2022
%P 691-707
%V 58
%N 5
%U http://geodesic.mathdoc.fr/articles/10.14736/kyb-2022-5-0691/
%R 10.14736/kyb-2022-5-0691
%G en
%F 10_14736_kyb_2022_5_0691
Guterman, Alexander; Kreines, Elena; Vlasov, Alexander. Non-surjective linear transformations of tropical matrices preserving the cyclicity index. Kybernetika, Tome 58 (2022) no. 5, pp. 691-707. doi: 10.14736/kyb-2022-5-0691

[1] Baccelli, F., Cohen, G., Olsder, G.J., Quadrat, J.-P.: Synchronization and Linearity. Wiley 1992. | Zbl

[2] Butkovič, P.: Max-algebra: the linear algebra of combinatorics?. Linear Algebra and its Applications 367 (2003), 313-335. | DOI | Zbl

[3] Dieudonné, D.J.: Sur une généralisation du groupe orthogonal á quatre variables. Arch. Math. 1 (1949), 282-287. | DOI

[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

Cité par Sources :