×

zbMATH — the first resource for mathematics

On visualization scaling, subeigenvectors and Kleene stars in max algebra. (English) Zbl 1180.15027
A (entrywise) nonnegative matrix \(A\) is called visualized if its elements are \(\leq \lambda(A)\), where \(\lambda(A)\) is the maximum cycle geometric mean of \(A\). It is strictly visualized if there is strict inequality for the entries which do not lie on critical cycles. The main contribution of the article under review is to identify and characterize diagonal matrices \(X\) with a positive diagonal for which \(X^{-1}AX\) is strictly visualized. Here is a sample of the results given: For a definite \(A\), \(X^{-1}AX\) is strictly visualized if and only if \(\text{diag}\,(X)\) is a positive linear combination of all columns of the Kleene star \(A^\star\) of \(A\), \(A\) is irreducible and \(\text{diag}\,(X)\) is a positive log-convex combination of all columns of \(A^\star\). For the unexplained terminology and further results we refer the reader to the paper.

MSC:
15B48 Positive matrices and their generalizations; cones of matrices
15A30 Algebraic systems of matrices
15A21 Canonical forms, reductions, classification
52A20 Convex sets in \(n\) dimensions (including convex hypersurfaces)
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] M. Akian, S. Gaubert, C. Walsh, Discrete max-plus spectral theory, in: G. Litvinov, V. Maslov, (Eds.), Idempotent Mathematics and Mathematical Physics, Contemporary Mathematics, vol. 377, AMS, Providence, 2005, pp. 53-77. E-print: arXiv:math/0405225. · Zbl 1104.47055
[2] Afriat, S.N., The system of inequalities \(a_{\mathit{rs}} > X_r - X_s\), Proc. Cambridge philos. soc., 59, 125-133, (1963) · Zbl 0118.14901
[3] Afriat, S.N., On sum-symmetric matrices, Linear algebra appl., 8, 129-140, (1974) · Zbl 0281.15017
[4] Baccelli, F.L.; Cohen, G.; Olsder, G.-J.; Quadrat, J.-P., Synchronization and linearity, (1992), John Wiley Chichester, New York
[5] Bapat, R.B., A MAX version of the perron – frobenius theorem, Linear algebra appl., 275/276, 3-18, (1998) · Zbl 0941.15020
[6] Berman, A.; Plemmons, R.J., Nonnegative matrices in the mathematical sciences, (1979), Academic Press · Zbl 0484.15016
[7] Butkovic, P., Simple image set of \((\max, +)\)-linear mappings, Discrete appl. math., 105, 73-86, (2000) · Zbl 0976.15013
[8] Butkovic, P., MAX-algebra: the linear algebra of combinatorics?, Linear algebra appl., 367, 313-335, (2003) · Zbl 1022.15017
[9] Butkovic, P.; Schneider, H., Applications of MAX-algebra to diagonal scaling of matrices, Electron. J. linear algebra, 13, 262-273, (2005) · Zbl 1093.15009
[10] P. Butkovic, H. Schneider, On the Visualization Scaling of Matrices, University of Birmingham, 2007. Preprint: 2007/12.
[11] Butkovic, P.; Schneider, H.; Sergeev, S., Generators, extremals and bases of MAX cones, Linear algebra appl., 421, 394-406, (2007) · Zbl 1119.15018
[12] Carré, B.A., An algebra for network routing problems, J. inst. math. appl., 7, 273-299, (1971) · Zbl 0219.90020
[13] Cuninghame-Green, R.A., Minimax algebra, Lecture notes in economics and mathematical systems, vol. 166, (1979), Springer Berlin
[14] Cuninghame-Green, R.A., (), 1-121
[15] M. Develin, B. Sturmfels, Tropical convexity, Doc. Math. 9 (2004) 1-24. E-print: arXiv:math/0308254. · Zbl 1054.52004
[16] Elsner, L.; van den Driessche, P., On the power method in MAX algebra, Linear algebra appl., 302-303, 17-32, (1999) · Zbl 0949.65032
[17] Elsner, L.; van den Driessche, P., Modifying the power method in MAX algebra, Linear algebra appl., 332-334, 3-13, (2001) · Zbl 0982.65042
[18] Engel, G.M.; Schneider, H., Cyclic and diagonal products on a matrix, Linear algebra appl., 7, 301-335, (1973) · Zbl 0289.15006
[19] Engel, G.M.; Schneider, H., Diagonal similarity and diagonal equivalence for matrices over groups with 0, Czechoslovak math. J., 25, 100, 387-403, (1975) · Zbl 0329.15007
[20] Fiedler, M.; Pták, V., Diagonally dominant matrices, Czechoslovak math. J., 17, 92, 420-433, (1967) · Zbl 0178.03402
[21] Fiedler, M.; Pták, V., Cyclic products and an inequality for determinants, Czechoslovak math. J., 19, 94, 428-450, (1969) · Zbl 0281.15014
[22] S. Gaubert, Théorie des systèmes linéaires dans les dioı¨des, Thèse, Ecole des Mines de Paris, 1992.
[23] Gaubert, S., Resource optimization and \((\min, +)\) spectral theory, IEEE trans. automat. control, 40, 11, 1931-1934, (1995) · Zbl 0845.93035
[24] S. Gaubert, R. Katz, The Minkowski theorem for max-plus convex sets, Linear Algebra Appl. 421 (2007) 356-369. E-print: arXiv:math/0605078. · Zbl 1110.52002
[25] Grünbaum, B., Convex polytopes, (1967), Wiley · Zbl 0163.16603
[26] Heidergott, B.; Olsder, G.J.; van der Woude, J., MAX plus at work: modeling and analysis of synchronized systems, A course on MAX-plus algebra, (2006), Princeton University Press · Zbl 1130.93003
[27] Hershkowitz, D.; Schneider, H., One sided simultaneous inequalities and sandwich theorems for diagonal similarity and diagonal equivalence of nonnegative matrices, Electron. J. linear algebra, 10, 81-101, (2003) · Zbl 1020.15020
[28] Johnson, C.R.; Smith, R.L., Path product matrices, Linear and multilinear algebra, 46, 177-191, (1999) · Zbl 0976.15016
[29] Johnson, C.R.; Smith, R.L., Positive, path product and inverse M-matrices, Linear algebra appl., 421, 328-337, (2007), 423 (2007) 519 · Zbl 1124.15018
[30] Johnson, C.R.; Smith, R.L., Path product matrices and eventually inverse M-matrices, SIAM J. matrix anal. appl., 29, 2, 370-376, (2008) · Zbl 1141.15020
[31] M. Joswig, Tropical halfspaces, in: J.E. Goodman, J. Pach, E. Welzl, (Eds.), Combinatorial and Computational Geometry, MSRI publications 52, Cambridge University Press, 2005, pp. 409-432. E-print: arXiv:math/0312068. · Zbl 1090.52500
[32] M. Joswig, K. Kulas, Tropical and ordinary convexity combined, 2008. E-print: arXiv:0801.4835. · Zbl 1198.14060
[33] Karp, R.M., A characterization of the minimum cycle Mean in a digraph, Discrete math., 23, 309-311, (1978) · Zbl 0386.05032
[34] Papadimitriou, C.H.; Steiglitz, K., Combinatorial optimization: algorithms and complexity, (1982), Prentice Hall New Jersey · Zbl 0503.90060
[35] Rothblum, U.G.; Schneider, H.; Schneider, M.H., Characterizations of MAX-balanced flows, Discrete appl. math., 39, 241-261, (1992) · Zbl 0769.05044
[36] Rothblum, U.G.; Schneider, H.; Schneider, M.H., Scaling matrices to prescribed row and column maxima, SIAM J. matrix anal. appl., 15, 1-14, (1994) · Zbl 0833.15006
[37] Schneider, H.; Schneider, M.H., Towers and cycle covers for MAX-balanced graphs, Congr. numer., 78, 159-170, (1990) · Zbl 0691.05039
[38] Schneider, H.; Schneider, M.H., MAX-balancing weighted directed graphs, Math. oper. res., 16, 208-222, (1991) · Zbl 0729.90085
[39] S. Sergeev, On cyclic classes and attraction cones in max algebra, 2009. E-print: arXiv:0903.3960.
[40] Vorobyov, N.N., Extremal algebra of positive matrices, Elektron. informationsverarb. kybernetik, 3, 39-71, (1967), (in Russian)
[41] Young, N.E.; Tarjan, R.E.; Orlin, J.B., Faster parametric shortest path and minimumn-balance algorithm, Networks, 21, 205-221, (2006)
[42] Ziegler, G.M., Lectures on polytopes, (1994), Springer
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.