| Title:
|
Non-surjective linear transformations of tropical matrices preserving the cyclicity index (English) |
| Author:
|
Guterman, Alexander |
| Author:
|
Kreines, Elena |
| Author:
|
Vlasov, Alexander |
| Language:
|
English |
| Journal:
|
Kybernetika |
| ISSN:
|
0023-5954 (print) |
| ISSN:
|
1805-949X (online) |
| Volume:
|
58 |
| Issue:
|
5 |
| Year:
|
2022 |
| Pages:
|
691-707 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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. (English) |
| Keyword:
|
tropical linear algebra |
| Keyword:
|
cyclicity index |
| Keyword:
|
linear transformations |
| MSC:
|
05C22 |
| MSC:
|
05C38 |
| MSC:
|
05C50 |
| idZBL:
|
Zbl 07655855 |
| idMR:
|
MR4538621 |
| DOI:
|
10.14736/kyb-2022-5-0691 |
| . |
| Date available:
|
2023-01-23T16:28:23Z |
| Last updated:
|
2023-03-13 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/151299 |
| . |
| Reference:
|
[1] Baccelli, F., Cohen, G., Olsder, G.J., Quadrat, J.-P.: Synchronization and Linearity..Wiley 1992. Zbl 0824.93003 |
| Reference:
|
[2] Butkovič, P.: Max-algebra: the linear algebra of combinatorics?.Linear Algebra and its Applications 367 (2003), 313-335. Zbl 1022.15017, |
| Reference:
|
[3] Dieudonné, D.J.: Sur une généralisation du groupe orthogonal á quatre variables..Arch. Math. 1 (1949), 282-287. 10.1007/BF02038756 |
| Reference:
|
[4] Frobenius, G.: Über die Darstellung der endlichen Gruppen durch lineare Substitutionen..Sitzungsber Deutsch. Akad. Wiss., Berlin 1997. |
| Reference:
|
[5] Jones, D.: Matrix roots in the max-plus algebra..Linear Algebra and its Applications 631 (2021), 10-34. |
| Reference:
|
[6] Gavalec, M.: Periodicity in Extremal Algebras..Hradec Králové: Gaudeamus 2004. |
| Reference:
|
[7] Gavalec, M.: Linear matrix period in max-plus algebra..Linear Algebra and its Applications 307 (2000), 167-182. |
| Reference:
|
[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. |
| Reference:
|
[9] Guterman, A., Kreines, E., Thomassen, C.: Linear transformations of tropical matrices preserving the cyclicity index..Special Matrices 9 (2021), 112-118. |
| Reference:
|
[10] Guterman, A., Maksaev, A.: Maps preserving scrambling index..Linear and Multilinear Algebra 66 (2018), 840-851. |
| Reference:
|
[11] Heidergott, B., Olsder, G.J., Woude, J. van der: Max Plus at Work..Princeton Series in Applied Mathematics 2006. |
| Reference:
|
[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. |
| Reference:
|
[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. |
| Reference:
|
[14] Pierce, S., al., et: A survey of linear preserver problems..Linear Multilinear Algebra 33 (1992), 1-119. |
| Reference:
|
[15] Rodman, L., Šemrl, P.: A localization technique for linear preserver problems.Linear Algebra and its Applications 433 (2010), 2257-2268. |
| Reference:
|
[16] Schur, I.: Einige Bemerkungen zur Determinantentheorie..Akad. Wiss. Berlin: S.-Ber. Preuss., (1925) 454-463. |
| Reference:
|
[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. |
| . |
