Simple image set of (max,+) linear mappings. (English) Zbl 0976.15013

By defining an addition \(a\oplus b=\max(a,b)\) and a multiplication \(a\otimes b =a+b\) for any \(a,b\in\mathbb{R}\), one can construct a max-algebra of real numbers. Then these operations can be extended to matrices and vectors in the same way as in conventional linear algebra. If \(A\) is a real \(n\times n\) matrix, then the mapping \(x\mapsto A\otimes x\) from \(\mathbb{R}^n\) to \(\mathbb{R}^n\) (\(n>1\)) is neither surjective nor injective. However, for some of such mappings (called strongly regular) there is a nonempty subset (called the simple image set) of the range, each element of which has a unique pre-image. In this paper, a description of simple image sets is presented, from which criteria for strong regularity are obtained. It is also proved that the closure of the simple image set of a strongly regular mapping \(f\) is the image of the \(k\)-th iterate of \(f\) after normalization for any \(k\geq n-1\) or, equivalently, the set of fixed points of \(f\) after normalization.


15A30 Algebraic systems of matrices
15A04 Linear transformations, semilinear transformations
Full Text: DOI


[1] Baccelli, F.L.; Cohen, G.; Olsder J.-P. Quadrat, G.-J., Synchronization and linearity, (1992), Wiley New York
[2] Butkovic, P., Strong regularity of matrices – a survey of results, Discrete appl. math., 48, 45-68, (1994) · Zbl 0804.06017
[3] Butkovic, P.; Cuninghame-Green, R.A., On the regularity of matrices in MIN algebra, Linear algebra appl., 145, 127-139, (1991) · Zbl 0731.15012
[4] Butkovic, P.; Hevery, F., A condition for the strong regularity of matrices in the minimax algebra, Discrete appl. math., 11, 209-222, (1985) · Zbl 0602.90136
[5] Cuninghame-Green, R.A., Describing industrial processes with interference and approximating their steady-state behaviour, Oper. res. quart., 13, 95-100, (1962)
[6] Cuninghame-Green, R.A., Minimax algebra, Lecture notes in economics and mathematical systems, Vol. 166, (1979), Springer Berlin
[7] R.A. Cuninghame-Green, Minimax Algebra and Applications in: Advances in Imaging and Electron Physics, Vol. 90, Academic Press, New York, 1995.
[8] S. Gaubert, Théorie des systèmes linéaires dans les dioı̈des, thèse, Ecole des Mines de Paris, 1992.
[9] M. Gavalec, Private communication, 1999.
[10] M. Gondran, M. Minoux, Valeurs propres et vecteurs propres dans les dioı̈des et leur interprétation en théorie des graphes. EDF Bulletin de la Direction des Études et Recherches, Série C-Math. Info. #2, 1977, pp. 25-41.
[11] Gondran, M.; Minoux, M., Linear algebra of dioı̈ds: a survey of recent results, Ann. discrete math., 19, 147-164, (1984) · Zbl 0568.08001
[12] Karp, R.M., A characterization of the minimum cycle Mean in a digraph, Discrete math., 23, 309-311, (1978) · Zbl 0386.05032
[13] Prou, J.M.; Wagneur, E., Controllability in the MAX-algebra, Kibernetika, 35, 13-24, (1999) · Zbl 1274.93036
[14] Wagneur, E., Moduloids and pseudomodules. I: dimension theory, Discrete math., 98, 57-73, (1991) · Zbl 0757.06008
[15] K. Zimmermann, Extremálnı́ algebra (Výzkumná publikace Ekonomicko-matematické laboratore pri Ekonomickém ústave CSAV, 46, Praha, 1976) (in Czech).
[16] Zimmermann, U., Linear and combinatorial optimization in ordered algebraic structures, Annals of discrete mathematics, Vol. 10, (1981), North-Holland Amsterdam · Zbl 0466.90045
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.