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.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.