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

Alexander Guterman; Elena Kreines; Alexander Vlasov

Kybernetika (2022)

  • Volume: 58, Issue: 5, page 691-707
  • ISSN: 0023-5954

Abstract

top
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.

How to cite

top

Guterman, Alexander, Kreines, Elena, and Vlasov, Alexander. "Non-surjective linear transformations of tropical matrices preserving the cyclicity index." Kybernetika 58.5 (2022): 691-707. <http://eudml.org/doc/299530>.

@article{Guterman2022,
abstract = {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.},
author = {Guterman, Alexander, Kreines, Elena, Vlasov, Alexander},
journal = {Kybernetika},
keywords = {tropical linear algebra; cyclicity index; linear transformations},
language = {eng},
number = {5},
pages = {691-707},
publisher = {Institute of Information Theory and Automation AS CR},
title = {Non-surjective linear transformations of tropical matrices preserving the cyclicity index},
url = {http://eudml.org/doc/299530},
volume = {58},
year = {2022},
}

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
PB - Institute of Information Theory and Automation AS CR
VL - 58
IS - 5
SP - 691
EP - 707
AB - 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.
LA - eng
KW - tropical linear algebra; cyclicity index; linear transformations
UR - http://eudml.org/doc/299530
ER -

References

top
  1. Baccelli, F., Cohen, G., Olsder, G.J., Quadrat, J.-P., Synchronization and Linearity., Wiley 1992. Zbl0824.93003
  2. Butkovič, P., , Linear Algebra and its Applications 367 (2003), 313-335. Zbl1022.15017DOI
  3. Dieudonné, D.J., 10.1007/BF02038756, Arch. Math. 1 (1949), 282-287. DOI10.1007/BF02038756
  4. Frobenius, G., Über die Darstellung der endlichen Gruppen durch lineare Substitutionen., Sitzungsber Deutsch. Akad. Wiss., Berlin 1997. 
  5. Jones, D., , 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 Algebra and its Applications 307 (2000), 167-182. DOI
  8. Guterman, A., Johnson, M., Kambites, M., , Linear Algebra and its Applications 545 (2018), 1-14. DOI
  9. Guterman, A., Kreines, E., Thomassen, C., , Special Matrices 9 (2021), 112-118. DOI
  10. Guterman, A., Maksaev, A., , 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., , Linear Algebra and its Applications 611 (2021) 279-309. DOI
  13. Merlet, G., Nowak, T., Sergeev, S., , Linear Algebra and its Applications 461 (2014) 163-199. DOI
  14. Pierce, S., al., et, , Linear Multilinear Algebra 33 (1992), 1-119. DOI
  15. Rodman, L., Šemrl, P., , 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., , Linear Algebra and its Applications 431 (2009), 1325-339. DOI

NotesEmbed ?

top

You must be logged in to post comments.